RE: dynamic vs. static typing

["Anton van Straaten" <address@hidden>]

Steve Dekorte wrote:
> Yes, and the only union may be introspection methods. In which case we
> might be able to validly send any method that the introspection API
> reveals to us, even though our type system (which restricted us to the
> introspection methods) wouldn't allow it.

If it's allowed to happen without error, then clearly the type system allows
it.  I think that "type system" above is being used to refer exclusively to
static type checking, whereas even most "ST" systems include both static and
dynamic checks.

Matt Hellige wrote:
> This brings up the question of what the difference really is between
> "type errors" and other run-time errors (like pattern matching failure
> in particular), but we've been over that...

Can I go over it again?  ;o)

The whole question of what happens at "run-time" vs. "compile time"
shouldn't be seen as the either/or choice that the ST vs. DT debate frames
it as.  We've had that discussion, but I'd like to try to give a broader
perspective on it, and look at what the distinction between static and
dynamic type checking really refers to.

The static/dynamic type checking distinction is strongly rooted in the
limitations of current technology, so perhaps shouldn't be the primary focus
of discussion about future directions.  Instead, we should think in terms of
concepts like staged computation and abstract interpretation.

Abstract interpretation is, essentially, running a program before runtime -
i.e. before a full set of inputs exist.  Compilers effectively do this when
they analyze a program's types.  In a program containing type annotations,
those annotations essentially form part of an independent program that can
be run before the program in which they are embedded is run.  The notes that
Shriram previously referenced are a nice and accessible intro for this
concept[1].

Since we tend to attach all sorts of unrelated meanings to the term
"compiler", it's useful to separate out the various early stage computations
of our program which compilers can do, and consider them conceptually as
part of the lifecycle of the execution of the program.  Forget whether or
not the "compiler" does them, or if they're done at "compile time" - many of
these compuations could equally well be done by some other kind of tool, and
besides, type checking can also happen at link time, for example, and of
course linking can happen at runtime.  So the execution lifecycle of a
program can have many stages, especially if you introduce a feature like
macros into the picture.

Given this multi-stage lifecycle of the execution of a program, it can make
good sense to shift computations to a point as early on in the cycle as
possible, as long as this doesn't result in the loss of desired
functionality.  The reasons it can make sense are well known, such as being
able to make certain kinds of guarantees about program behavior, detecting
errors earlier, as well as the ability to reduce the computational load
during the final computation (at "runtime").  Another benefit of computing
as early as possible is that it forces one to make explicit exactly what is
known when.  This then means that programs contain more explicit
information, which can be useful even to human readers, not just to the
machine.

Naturally, there's a flip side to this picture: delaying computations as
long as possible can also provide benefits, perhaps making it easier to
change behavior dynamically, etc.  Also, in an evolving system, providing
static information that turns out to be incorrect may be more costly than if
we didn't bother to encode that information explicitly (an arguable point).
If we insist that we are unable to decide anything static about our
computations ahead of time, then of course every decision must be deferred
to runtime.  In practice, this is never the case, even in the purest DT
systems.

But even where extreme runtime flexibility is desired, it's possible to make
use of static techniques.  To take a mainstream example, Java supports the
recompilation and replacement of individual classes at "runtime" without
interrupting a program's execution.  The Java compiler can essentially be
treated as providing an 'eval' capability to a running Java program.  So we
shouldn't assume that the need for dynamism implies the need for languages
which perform no pre-runtime computations, i.e. purely DT languages.  We
should remember that both compile time and link time can be coincident with
runtime, for example, and that this can change the equation.

Pure ST systems attempt to shift as many computations (of a certain kind) as
theoretically possibly into compile time, and pure DT systems do the same
for runtime.  Of course, as has been observed, the sweet spots usually lie
somewhere between the extremes.  Do a good job of figuring out what can be
made static - i.e. what can be shifted to earlier in the computation -  and
you'll benefit from that.  If you can express what's known to be static to
your tools and have them be able to tell you useful things about your
programs before you run them, that's even better.

This is an area where we absolutely can have the cake and eat most of it
too, but only if we don't think about it in popular dualistic[2] terms.

Anton

[1] http://www.cs.brown.edu/courses/cs173/2003/Textbook/2003-11-03.pdf
[2] www.m-w.com dualism, n. 3(a): "a doctrine that the universe is under the
dominion of two opposing principles one of which is good and the other evil"