25 minutes ago, Marijn wrote:
>
> My understanding is that it is a finite data structure that refers
> to itself. It is supposed to represent 3 nodes/links of a doubly
> linked list where each node points to its neighbours or #f, so
> really it should only be 3 _dl's big...
Yes, I know what you meant... Here's a simpler demonstration:
#1=(cons 1 #1#)
But the cyclic thing here is *not* the data, it's the code that is
cyclic. IOW, compilers see that as
(cons 1 (cons 1 (cons 1 (cons 1 (cons 1 ...)))))
so they're essentially compiling an infinite piece of code, and the
stack overflows and infinite loops are an obvious result. It's true
that in *some* cases you can find how to compile it into working code.
In Racket that example would involve some use of `make-reader-graph',
and your example will need to have mutable fields or some way to
initialize field values in a circular way. (Search the docs for
`shared'.) Doing that is also questionable for another reason -- for
example, if I write:
(define x1 #1=(cons 1 (lambda () #1#)))
(define x2 #2=(cons 1 (lambda () (cons 1 (lambda () #2#)))))
then the two values that I'd supposedly get are different -- which
you'd see with `eq?'. But that means that compiling code depends on
the identity of the code itself, not just on the code.
In any case, it should be obvious that it's really not a simple thing
to compile. There are old legends about lisp implementations which
would compile even more of these things, so you could have an infinite
loop like:
#1=(begin (printf "hey\n") #1#)
and it would compile the code to the right thing, and with enough
punctuations you could get generic gotos of some limited kind (imagine
using them across functions...). But those implementations were
dropped into a volcano a good while ago. (And I can imagine that a
few lispers jumped right in shouting "my prrrecious".)
[It's still used in CL in two cases: (a) inside a quoted expression,
(b) with tricks like (let ((#1=#:foo)) (* #1# #1#)) where `#:foo' in
CL is read as a fresh unintered symbol, so the #1# is the only way to
refer to it.]
> Alternatives are to use a letrec with `delay' on `left and `right'
> members, but then a new accessor that wraps `force' will have to be
> used everywhere. Finally, mutation can be used to connect links
> together in the desired way. Maybe I'm trying too hard to avoid
> this simple fix?
Yes, that's another way to see why it's not allowed... You need to do
what you wanted the compiler to do, and it's not straightforward.
(And again, see `shared'.)
--
((lambda (x) (x x)) (lambda (x) (x x))) Eli Barzilay:
http://barzilay.org/ Maze is Life!
_________________________________________________
For list-related administrative tasks:
http://lists.racket-lang.org/listinfo/users
