LetRec

[Robert Elton Maas <REM%IMSSS@SAIL.Stanford.EDU>]

<M> From: mcvax!pilatus!ceb@uunet.UU.NET

<M> It was mentioned earlier that any scheme of this type would only work
<M> for "special" operators (I forget the exact adjective used, but it was
<M> later stamped as inappropriate or unclear.)  The nature of this
<M> speciality seem to me to be best described as "encapsulating".  A
<M> function is encapsulating when it takes its arguments and buries them
<M> in some topological structure in memory (including, but not limited
<M> to, cons-cell spaghetti) without interfering with them procedurally in
<M> any way.  The functions cons and list are encapsulating, but +, -,
<M> etc. are not, since they feed their arguments back into some
<M> procedural operation.

I nominate using BBN/UCI-lisp editor terminology here, namely "embed".
CONS and LIST are embedding functions.

<M> For simplicity's sake, functions such as car,
<M> cdr, and their descendants should be considered as non-encapsulating,

They do the opposite. Again I nominate using BBN/UCI-lisp editor
terminology, namely "extract". CAR and NTH (in regard to its list
argument) are extracting functions.

IDENTITY is both the trivial embedding and the trivial extracting
function. To avoid recursion loops we should require nontrivial (strict)
embedding functions for LetRec.

<M> (declare (encapsulating-function <myfunc> . . .))

(declare (embedding-function <myfunc> . . .))

Because "encapsulating" is a more elaborate concept usually, having to do
with closures and abstraction etc., I prefer to avoid that term for the
simple structural concept we're discussing here.

<M> ... to permit users to identify their own functions having this property
<M> (and to shoot themselves in the foot if they lie).  

(:- Or cut off their damn heels :-)

(N.B. That's from a comedy album played on KFAT dealing with chain saw.)

<M> The other implementational hurdles then seem surmountable *but* you
<M> would have to change the order in which encapsulating functions are
<M> evaluated - it would no longer be acceptable to grind through its
<M> arguments first.

In this case of LetRec, have low-level mechanism (part of LetRec) pass a
dummy forwarding cell, evaluate normally, then after return more
low-level LetRec mechanism do the replacement for the true value to
create circularity. This localizes the implementation work to LetRec
itself, not random functions such as CONS, thus it can be done outside a
Scheme-style lazy-evaluator within a normal evaluator.

<M> Whether it is worth adding to the language depends on how hard it is
<M> to implement, and how much additional cognitive clutter the language
<M> can stand.

More importantly, it shouldn't become part of CLtL until after it has
been implemented by at least several experimental implementations to work
out the bugs in the basic design and see if it really is useful.