Re: map and siblings

[Jonathan Rees <Rees@YALE.ARPA>]

    From: decvax!ittvax!wxlvax!dann
    
    I'm having trouble interpreting some of the terminology used by the T 
    people in their documentation/discussions.  Terms such as "integrable
    procedures", "open-coding", and "closure consing"  are unfamiliar to me. 
    Is there some basic reference which defines these terms?  If so,
    I'd appreciate pointers to it.

The real reference on all this is the series of papers by Steele and
Sussman.  See the reference list at the end of the T manual.  But
I think the terms are all fairly standard in one computer science
circle or another.

"Procedure integration" is an optimization technique whereby a procedure
definition is substituted in-line.  This prevents the overhead of
doing a procedure call.  For example, if

    (define-integrable (foo x y) (+ (* x x) y))
    
then when a call to FOO is compiled, e.g.

    (foo a 8)
    
a compiler would perform these transformations:

    (foo a 8)
    ==>  ((lambda (x y) (+ (* x x) y)) a 8)     ;Substitute FOO
    ==>  ((lambda (x y) (+ (* a a) 8)) a 8)     ;Substitute X and Y
    ==>  ((lambda () (+ (* a a) 8)))            ;Eliminate unused variables
    ==>  (+ (* a a) 8)                          ;Eliminate useless call

These transformations are performed only when they preserve semantics;
for example, if we instead have

    (foo (bar) 13)

then the call to BAR must happen only once (because it might have
side-effects), so the variable X can't get substituted for, so the
resulting code is:

    ((lambda (x) (+ (* x x) 13)) (bar))

otherwise written as 

    (let ((x (bar))) (+ (* x x) 13)).

"Open-coding" refers more generally to any technique whereby one can
avoid an out-of-line procedure call.  In Lisp and in C, this is usually
done with macros.  In T, this is unnecessary because we can assume
that there is an optimizing compiler capable of doing the above
transformations.  Integrable procedures are much preferable for many
reasons, including:

    - They are traceable in interpreted code.

    - They can be passed as procedure values.

    - One can turn something from integrable to non-integrable
      and vice versa much more easily than between macro and procedure.

    - Client modules will still compile correctly even if the definition
      isn't available at compile time (i.e. the calls can closed-compile
      if necessary).

In T, "closure" means the same thing as "procedure."  The term alludes
to the way that free variable bindings are captured or "closed over"
in languages like T or Scheme that have "upwards" procedure values.
Some languages distinguish this kind of procedure from other kinds.

"Consing" is Lisp-heritage jargon for any kind of storage allocation
in the heap.  This includes the allocation done e.g. by CONS or
MAKE-STRING.  In some cases, "consing" happens implicitly when
LAMBDA-expressions are evaluated.  For example, in

    (define (foo x) (lambda () x))
    
a procedure (closure) is allocated (consed) in the heap each time
FOO is called (that is, when the LAMBDA-expression is evaluated).