LABELS vs. local defines

[Kent M Pitman <KMP@SCRC-STONY-BROOK>]

    Date: 7 Mar 1985 23:59:04-EST
    From: linus!ramsdell@Mitre-Bedford
    
    Many Schemes, including the one described in Abelson and Sussman's book,
    eliminate LABELS in favor of local defines.  Local defines allow
    iterative factorial to be written as:
    
    (define (fact n)
      (define (fact n a)
	 (if (zero? n)
	     a
	     (fact (-1+ n) (* n a))))
      (fact n 1))
    
    In essence, all lexical contours are mutatable, as opposed to only
    allowing locales, but not lambda contours to mutate, as is done in T.  I
    once heard the argument as to why T has these two types of enviroments,
    but I am unable to reconstruct it now.  Something about compilation I
    recollect.  Could some one fill in the rest?
    
It's not really an issue of compilation (in the classical sense). 
Superficially, it'd be easy to have DEFINE's such as those above rewritten
as a LABELS invisibly. Note that in that case the LAMBDA wouldn't have
to even be mutable, since the transformation can be done at lexical 
analysis time. Contrast that with:

(DEFINE (FACT N FLAG)
  (IF FLAG (DEFINE (FACT-1 N A) ...))
  (FACT-1 N 1))

which the rewrite for is not so obvious. It also thwarts the
nice property from lambda calculus that ((LAMBDA () EXP)) is
interchangeable with EXP without lexically analyzing EXP to assure
it has no embedded DEFINE's. There are several other irritating
properties which result from this same "feature". Consider:

(LET ((X (COMPUTE-STUFF)))
  (DEFINE (ADDX N) (+ N X)))

which has to be written:

(DEFINE ADDX (LET ((X (COMPUTE-STUFF)))
	       (LAMBDA (N) (+ N X))))

in Abelson/Sussman Scheme. Or consider how much more careful
people must be in writing abstractions. They must document when
LAMBDA contours have to be introduced! What a data abstraction
violation! Consider the innocent-looking:

(DEFINE-SYNTAX (MY-BLOCK . FORMS)
  (COND ((NULL FORMS) '())
	((NULL (CDR FORMS)) (CAR FORMS))
	(ELSE `((LAMBDA (,(GENERATE-SYMBOL "TEMP")) (MY-BLOCK ,@(CDR FORMS))) ,(CAR FORMS)))))

which is one possible implementation for a construct like BLOCK.
Now consider what happens if someone who doesn't know about or
believe in implicit blocks thinks to rewrite your example using
explicit sequentializing, as in:

(DEFINE (FACT N)
  (MY-BLOCK (DEFINE (FACT N A)
              (IF (ZERO? N) A (FACT (-1+ N) (* N A))))
            (FACT N 1)))

Works ok, right? Becomes:

(DEFINE (FACT N)
  ((LAMBDA (TEMP1) (FACT N 1))
   (DEFINE (FACT N A) (IF (ZERO? N) A (FACT (-1+ N) (* N A))))))

Now what happens if someone rewrites MY-BLOCK in the following way:

(DEFINE-SYNTAX (MY-BLOCK . FORMS)
  (LET ((THUNKS (MAP (LAMBDA (FORM) (LIST (GENERATE-SYMBOL "TH")
					  `(LAMBDA () ,FORM)))
		     FORMS)))
    `(LET ,THUNKS
       ,(ITERATE LOOP ((V (REVERSE VARS)))
          (COND ((NULL V) '())
		((NULL (CDR V)) `(,(CAR V)))
		(ELSE `((LAMBDA (IGNORE) ,(LOOP (CDR V))) ,(CAR V))))))))

so that the modified FACT program expands to:

(DEFINE (FACT N)
  (LET ((TH1 (LAMBDA ()
	       (DEFINE (FACT N A) (IF (ZERO? N) A (FACT (-1+ N) (* N A))))))
	(TH2 (LAMBDA () (FACT N 1))))
    ((LAMBDA (IGNORE) (TH2)) (TH1))))

Suddenly, the user program isn't correct. Hence, the writers of macros
that introduce LAMBDA contours are forced to document that aspect of their
implementation. If they later change their implementation to not need the
LAMBDA contour, they may be forced into retaining dummy lambda contours 
in their source code to avoid breaking advertised abstractions.

The idea behind T's decision to go with a non-mutable LAMBDA was to keep
LAMBDA simple so it could be used for what it was originally meant for:
a way of naming quantities. I have lobbied very hard over the years to not
confuse its meaning. Look at PROG in Maclisp -- anyone wanting RETURN was
forced to accept the option of allowing GO (and vice versa) for almost
twenty years before it was finally separated in Common Lisp. We didn't want
this sort of overloading as a primitive feature of the T; we wanted to 
provide primitives to allow it to be built up later when needed.

My argument has been that it's better to have a special primitive that 
identifies places you might want to be mutable. It is indeed a bug -- and
not a design feature -- that you can't just put LOCALE in any old T form
and get efficient code. Hopefully that much will get changed some day.
People who like mutable LAMBDAs for everything ought to be able to trivially
implement an embedded language which has that property, but thus far can't
do that as easily as they should be able to.

Perhaps Jonathan will have more to say on this issue, but since I've made
so much noise about it over the years, I figured I'd throw in my opinions.
Hope you find these comments helpful in understanding why things are as 
they are.
-kmp