Re: LetRec?

[Barry Margolin <barmar@Think.COM>]

    Date: Fri, 8 Apr 88 12:17:20 PDT
    From: James Rice <Rice@sumex-aim.stanford.edu>

	    Is there a good reason why this was omitted from CL?

	It wasn't.  It is caled LABELS.  It only supports function binding (like
	FLET), but that is the only case where the distinction between LETREC
	and LET* is useful.

    I beg to differ.  I appreciate that I can declare recursive
    local functions with Labels.  I cannot, however refine recusive/
    circular data structures with it.  There seems to me to be a
    good symetry argument in favour of non-function LetRec to
    match with Labels.  There also seems to be an argument in favour
    of it in that those wanting to progam in a pure functional
    style will not be able to declare circular structures in CL.

I don't think you can create circular structures with Scheme's LETREC,
either.  The reason is that you would actually have to evaluate the
variable while creating the structure, and the values of the variables
being bound are undefined until all the initializations have completed.
In the case of procedures this is OK, because you don't actually
evaluate the procedure values until you invoke the procedure; all that
is needed in order to create the procedure is that the environment be
created with a placeholder for the procedure.  So, 

(letrec ((factorial (lambda (x)
		      (if (< 2 x) 1
			  (* x (factorial (- x 1)))))))
  (factorial 100))

works, but

(letrec ((circular (list* 1 2 3 4 circular)))
  circular)

is undefined, because the value of CIRCULAR is undefined at the time the
LIST* form is being evaluated.

In order to create circular structure, you have to do something like

(let ((circular (list 1 2 3 4)))
  (setf (cdr (last circular)) circular)
  circular)

I don't know how to do this kind of thing in a purely functional style.