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

On Aug 21, Joe Marshall wrote:
> 
> 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.

Yes.  (And that's why I like the `letrec*' semantics -- it give me
some semi-sane way to mix non-function values, except without the
self-referencing bit.)


> I'm guessing, however, that you want EQ-ness as well.

Only sometimes.  In the examples I gave, eq-ness was important to be
able to actually get the (cyclic) list.  If I stick to the lazy
language, then I could define `cycle' in a much simpler way:

  (define (cycle l) (append l (cycle l)))

But this won't work if you want to get a hold of the list in plain
Scheme -- there's no (easy/efficient) way to know when you have a
loop, which is what you'll need to make the inner call into a cycle
pointer.  So I used a version that had an explicit cycle via a
`letrec' value (in the lazy sense).


> 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.

Well, it's just the above -- I don't care much for `eq?' in itself.
If you manage to solve the forcing-an-infinite-lazy-value problem
(which is the same as, for example, writing such a structure to a
file), and if you gave me `equal?' that was as efficient as `eq?',
then I probably wouldn't even notice when you take away `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 )

Not in the above code.  The actual representation has promises holding
cons cells to more promises, and the promises themselves cannot be
unified unless you have a way to prove that two functions are
equivalent.  (Which might be possible in some simple cases like the
above, but probably too expensive to detect automatically.)


> 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.

Yes, it's the former, mostly -- but a usable version of it.


> 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.

I'd balk at it too -- *unless* you give me this:

  (letrec ([x (list (lambda () x))])
    (equal? x ((car x))))
  --> #t

instead.  Since I can't get that, I need `eq?'.  So I guess that I'm
saying that the side-effect that is (possibly) used to create that
self reference is an unfortunate by-product of working in an eager
language -- which is one more reason I don't want to do it explicitly.

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