Re: Strong Typing, Dynamic Languages, What to do?

[Shriram Krishnamurthi <sk@cs.brown.edu>]

Chris Uzdavinis wrote:

> As an advanced C++ programmer myself, I think he is representing us
> fairly well, and he is voicing some of my concerns too.  This thread
> was a good opportunity to dispell some misconceptions we may have of
> functional languages, garbage collectors, etc.  

Okay, let's focus.

>		   It seems to me the more objects that exist that
> AREN'T garbage, the worse a GC will perform.  Is that a false premise?

No, that's absolutely true.  However, it's also essentially unrelated
to your question about continuations, which is why I'm answering it
first.

Now for the fun part.

>								 Once
> you start having continuations in the picture you have entire
> callstacks unable to be garbage collected, but the GC has lots of
> objects laying around (in the continuation) needing checking.  

(1) The continuation isn't that different from other large data
structures.

(2) Most uses of continuations (TM) don't keep them around
indefinitely.  Even when the intent is to implement something like
backtracking, there is a semi-definite lifetime for the object.  Put
differently, the "longer" the continuation, the shorter, on average,
its lifetime.  Programmers simply don't jump deep into the middle of
very long call chains on a regular basis -- it's too difficult to
reason about your program.

(3) There is the danger that the continuation will capture objects
that will not be used on return after invocation.  This same problem
is, however, manifest in function calls also.  For this reason, Appel
proposed a notion of "space safety" (one of the neat chapters of his
Compiling With Continuations book).  Roughly, a compiler can shrink
the activation record before making a function call, to rid the record
of variables that are dead at the call locus (ie, they aren't
referenced upon return).  I imagine that in a modern JIT compiler, you
would use call count and duration information to determine when to
perform this shrinkage.  Note this this isn't just a functional
language problem -- Java faces it too, so I expect Java compilers will
soon perform this optimization (if they don't already).

Having said all that, let me point out that it's irrelevant!  Why?
Because continuations are principally control constructs.  The real
question you have to ask yourself is, "How would I accomplish a
continuation-like operation in a language without continuations?"  In
fact, we have an answer to this question: look at interactive Web
scripts, which become utterly straight-forward in a
continuation-enriched language.  What do programmers do in languages
without continuations?  Why, they use (in effect) tail-calling
patterns to simulate the control part of continuations, and ... they
create data structures to hold all the variables that they will need
when the continuation is actually invoked.

How do they know which variables they will need?  There's a simple
syntactic test they can perform: check for which variables are free in
the code that executes upon invocation.  All those variables need
values before the code can run.  So you stick their values in a data
structure at what is effectively continuation creation time; the
mangled code that reflects the continuation gets values from the data
structure, which it is handed at the equivalent of continuation
invocation time.

Here's the beauty of it: Those are the same variables that a
safe-for-space implementation will retain.

Ergo, space safety does automatically what you would have had to do
manually through a highly laborious and error-prone process.  Lovely,
no?

The real bottom line is that there's no free lunch.  If you keep
continuations in your language, yes, you (the implementor) need to do
some extra work -- but it's not clear you need to do much more work
than you had to do already for closures, say.  If you *don't* have
continuations, then for a task that ideally calls for them, you're
stuck building all that machinery by hand (just like others build
closures by hand -- as Oscar rightly pointed out, fie on the STL
designers for not including some notion of LAMBDA!).

In almost all cases, doing it manually creates more work, introduces
the potential for subtle errors, and is likely to make the software
less extensible and robust.  And in almost all cases, you will do the
naive thing to avoid errors and simplify maintenance (think about
hand-CPSing a complex program!).  This erases those hand-optimizations
you thought you would perform.  The compiler, unburdened in this
manner, can perform them.  Who wins?  (Remember: the paradoxical dual
of Oscar's conclusion is this: the more high-level you make your
program, the more opportunities for optimization you expose to a
compiler.  And I don't just mean this hypothetically: I can provide at 
least two real examples of this.)

Shriram