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

On Wed, Aug 20, 2008 at 10:26 PM, Eli Barzilay <eli at barzilay.org> wrote:
>
> 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.)]

Ok, I get what you're saying.  You want circularity in the data space
as well as in the function space and letrec does that.

I'm guessing, however, that you want EQ-ness as well. This leads
to a real problem.  EQ is a very weird function because it's quite
useful in the absence of side effects, but absolutely critical in
the presence.

I don't understand why you want circularity, though.  If you don't
intend on using side effects, then there's no way, other than via EQ,
to determine if a structure is circular.  And if you don't intend to
use side effects, then a non-circular, but infinite structure would be
observationally equivalent for every function *except* EQ.  In other words,
you couldn't write a program that would return a different answer
for circular vs. infinite *unless* you explicitly used EQ.  (And depending
on the philosophy of the implementor, a `pure' implementation of Scheme
could use hash-consing to fold equivalent structure and the circular
and infinite structure would be indistinguishable.  Baker argues for
this in  http://home.pipeline.com/~hbaker1/ObjectIdentity.html )

So either you are using letrec because

  1)  You want infinite, self-similar objects and you don't care
       about `circularity' per-se,

  2)  You really want *circular* objects because you intend to
       do something that can distinguish between truly circular
       objects and inifinite ones.  This implies the intent of
       side effects.

The last paragraph where you say `` I don't really care if Matthew
made `letrec' achieve the magic by a `let'+`set!', by a fixpoint
combinator, or by voodoo''  seems to indicate the former.

If *that's* the case, we don't have much of a problem.
Abdulaziz Ghuloum's example:

 (letrec ([x (list (lambda () x))])
   (eq? x ((car x))))

would simply be allowed to return #T or #F depending on
the implementation.  I could definitely live with that, but
I expect other people will balk at it.



-- 
~jrm