LetRec the way you want it IS in Common-lisp

[mcvax!pilatus!ceb@uunet.UU.NET]

   Date: Fri, 8 Apr 88 19:08:52 PDT
   From: Jim McDonald <cernvax!mcvax!edsel!jlm>

   . . .

   To return to the original question:
   Assuming that backquote (or whatever) could give you dynamically
   created recursive data structures, and that recursive forms in general
   are impossible to handle, is there something in-between that you want?

   Date: Sat, 9 Apr 88 05:20:53 PDT
   From: Jon L White <cernvax!mcvax!edsel!jonl>

   . . .

   Now, maybe what he wanted was a freshly-consed-up copy of some circular
   structure; say, something equivalent to  `#1=(a . ,#1#).  . . .

   [On the other hand, although this sort of data-pattern is just what a
   programmer might like, I'm not sure that the folks who thought this
   suggestion meant solving simultaneous recursive equations were way off
   base.  Give that man a turing machine.  Complete with halting problem.]

I would find it useful to have dynamic functional specification of
non-arborescent structures in CL, but the problems are indeed large.
In response to jlm's question about something in-between, the
following suggestion is made:

It was mentioned earlier that any scheme of this type would only work
for "special" operators (I forget the exact adjective used, but it was
later stamped as inappropriate or unclear.)  The nature of this
speciality seem to me to be best described as "encapsulating".  A
function is encapsulating when it takes its arguments and buries them
in some topological structure in memory (including, but not limited
to, cons-cell spaghetti) without interfering with them procedurally in
any way.  The functions cons and list are encapsulating, but +, -,
etc. are not, since they feed their arguments back into some
procedural operation.  For simplicity's sake, functions such as car,
cdr, and their descendants should be considered as non-encapsulating,
although I haven't ruled out for myself the possibility of getting
around *their* particular kind of procedural hacking with a modicum of
cleverness.

This concept in place, in implementing this feature in the context of
something like backquote, it would then be simple only to permit
references to recursive reference points when these appear as
arguments to encapsulating functions, and to permit these to refer
only to constants, or other encapsulating functions.  There
would, of course, have to be a "(declare (encapsulating-function
<myfunc> . . .))" form to permit users to identify their own functions
having this property (and to shoot themselves in the foot if they
lie).  

The other implementational hurdles then seem surmountable *but* you
would have to change the order in which encapsulating functions are
evaluated - it would no longer be acceptable to grind through its
arguments first.  However, it seems that under the definition of
encapsulability, this will always be legal, and you will still be able
to satisfy the thrust of the original suggestion.