[plt-scheme] about letrec and continuation : which behavior is correct ? and why ?

From: Eli Barzilay (eli at barzilay.org)
Date: Thu Aug 21 01:26:31 EDT 2008

On Aug 20, Joe Marshall wrote:
> On Wed, Aug 20, 2008 at 7:41 PM, Eli Barzilay <eli at barzilay.org> wrote:
> > On Aug 20, Matthias Felleisen wrote:
> >>
> >> On Aug 20, 2008, at 2:27 PM, Joe Marshall wrote:
> >>
> >> > Which, frankly, is a better way of writing this than the letrec
> >> > because it is obvious that some side-effecting is going on in
> >> > order to create magic circular structure such that
> >> > (eq? x ((car x))) could evaluate to #t.
> >>
> >> Amen.
> >
> > (negated Amen).
> Eli, what's wrong with you?!  Are you sure you're feeling ok?

Yes.  And I still prefer the implicit side-effect over the explicit
one.  Even back in the days where we were happily mutating pairs, I
still considered

  (define foo* (set-cdr! (last-pair foo) foo))

to be a hack.  A slightly better way to achieve this would be

  (define foo* (append! foo foo))

becuase it's clearer what kind of short-circuiting it makes, and the
actual side-effect that is needed to implement it is not for me to
worry.  A better way, when possible, is

  (define foo* '#0=(1 2 3 . #0#))

except that it's very rare to need a circular list of literals, so
it's almost never useful.

But what beats all of these by an order of magnitude is:

  (define foo* (letrec ([foo* (append foo foo*)]) foo*))

I can get *some* of that functionality with `shared', but not
everything.  The best I can do is:

  (require lazy/force)
  (define (cycle l) (!! (letrec ([c (lazy (append l c))]) c)))

The bottom line is that there are certain kinds of well-behaved
circular references that the language can do by itself, and I'm happy
to leave the implementation details for it.  (In the above case, the
(restricted) side effect is implicit in promise caches and in !!'s use
of `make-reader-graph'.)

[This is why I don't really care if Matthew made `letrec' achieve the
magic by a `let'+`set!', by a fixpoint combinator, or by voodoo
machine-code translations.  For all I know he has 5 different methods
and chooses one randomly for every minor version to see which one's
fastest.  If they all work the same, I don't care which one is used.
(Yes, continuations expose some of these details, which is unfortunate
-- I still don't want explicit mutation to get my self references.)]

          ((lambda (x) (x x)) (lambda (x) (x x)))          Eli Barzilay:
                  http://www.barzilay.org/                 Maze is Life!

Posted on the users mailing list.