RE: What's so cool about Scheme?

[Guy Steele - Sun Microsystems Labs <address@hidden>]

   From: "Anton van Straaten" <anton@appsolutions.com>
   To: "Guy Steele - Sun Microsystems Labs" <Guy.Steele@sun.com>, 
<mike@newhall.net>
   Cc: <ll1-discuss@ai.mit.edu>
   Subject: RE: What's so cool about Scheme?
   Date: Wed, 4 Jun 2003 12:51:20 -0400
   Importance: Normal
   
   Guy Steele wrote:
   > On the contrary.  In original Lisp, LAMBDA expressions
   > were not evaluable constructs at all.  Instead, one
   > wrote
   >
   > (MAPCAR (QUOTE (LAMBDA (X) ...)) MYLIST)
   >
   > Only later, when this piece of list structure beginning
   > with the symbol LAMBDA was applied to an argument, was the
   > list structure regarded as code and an execution environment
   > imputed to it.  This delay in regarding the list structure
   > as code was the entire source of the FUNARG problem.
   
   Thanks very much for the correction.  Sorry Mike, for the misunderstanding.
   For the record, I now understand the connection Mike was making between
   having a language having eval, and the need for closures.
   
   Is the term "FUNARG problem" then used to refer both to this old Lisp issue
   with quoted variable names not being evaluated in their original context, as
   well as the case I mentioned where binding does occur in the original
   context, but the context is later lost?
   
   For example, at
   http://www.stanford.edu/class/cs242/readings/vocabulary.html , it says:
   
   "funarg problem - The failure of traditional stack-based implementations of
   procedure calls in the presence of "first-class" functions (functions that
   can be passed as procedure parameters and returned as procedure results).
   Upwards funarg problem: the problem of returning a function as a procedure
   result; requires allocating activation records on the heap and returing a
   closure containing a pointer to code and a pointer to the enclosing
   activation record.  Downwards funarg problem: the problem of passing a
   function as a procedure parameter; requires a tree structure for activation
   records."
   
   It's definitions like this that led to my misunderstanding.  The original
   Lisp FUNARG problem seems to me to only marginally qualify under this
   definition.  The issue in the LISP case doesn't seem to be whether or not
   procedure calls are stack-based, etc. - it's simply that there's not even an
   attempt to bind values in the original context.  This seems like two
   completely separate problems to me - the bind-too-late problem (old Lisp),
   and the binding-context-lost problem, which seems to me what the above
   definition describes.
   
   Is it that in solving the bind-too-late problem, the binding-context-lost
   problem came up, and thus both became referred to as the FUNARG problem?

But "bind-too-late" did work (mostly) in "old Lisp" because bindings
obeyed a dynamic, stack-based discipline.

(DEFINE ADD-TO-ALL (LAMBDA (N LS)
  (MAPCAR (QUOTE (LAMBDA (X) (PLUS N X))) LS)))

(DEFINE MAPCAR (LAMBDA (F Z)
  (COND ((NULL Z) Z) (T (CONS (APPLY F (LIST (CAR Z))) (MAPCAR F (CDR Z)))))))

This all worked fine, even though the LAMBDA expression (LAMBDA (X) (PLUS N X))
was not really regarded as code until given to APPLY by MAPCAR, because
the binding of N was still active in the dynamic execution environment.

The FUNARG problem arises if there is a name clash.  Suppose the first
function had instead been:

(DEFINE ADD-TO-ALL (LAMBDA (Z LS)
  (MAPCAR (QUOTE (LAMBDA (X) (PLUS Z X))) LS)))

The only difference here is that the variable name Z has been used instead
of N for the quantity to be added to each element in the list.  But now
you crash and burn, because when the function (LAMBDA (X) (PLUS Z X))
tries to access the variable Z in the dynamic binding environment, it
finds the the most recent dynamic binding of Z is that made in MAPCAR,
not the one in ADD-TO-ALL, so PLUS ends up getting a list rather than
a number as its first argument.

An example very close to this spurred the original recognition that there
was a problem here yet to be solved.  Later it was separated into the
"downward" case (where the desired binding still exists but has been
dynamically shadowed by a more recent binding) and the "upward" case
(where the desired binding was earlier discarded because of the stack
discipline of dynamic binding).

--Guy Steele