On Thu, Sep 4, 2014 at 12:14 PM, Eli Barzilay <eli@barzilay.org> wrote:

On Wed, Sep 3, 2014 at 2:17 AM, Alex Shinn <alexshinn@gmail.com> wrote:
>
> Also for lazy data structures see
> http://www.haskell.org/haskellwiki/Tying_the_Knot,
> for which I have a Scheme version lying around somewhere.

Um, the usual way in which lazy code results in a proper pointer cyclic
is when it goes through some process that translates the lazy structures
into strict ones.

For example, with a (define ones (cons 1 ones)) you don't have a cycle
of pointers, in a similar way that in plain racket you don't get such a
cycle with (define ones (cons 1 (λ() ones))); the cycle is instead
implicit in the semantics of looking up `ones'. This is similar to the
pointer cycle you implicitly get with (define (onses) (cons 1 ones)).
But it does generate *real* cycle when you display the above value --
the process of translating the lazy structure to a strict one (ie,
removing all promises) results in a real #=0(1 . #0#).

It would be very interesting if you have code that achieves such a cycle
without using mutation. (Or similar features, like Racket's
`make-reader-graph' which is what Lazy Racket uses; in addition to the
usual mutation that is needed to implement call-by-need.)

What are these "pointer" things you speak of? o_0

The original question was whether cycles were possible in

"strict immutable structures." I would allow promises as part of

that structure, and consider them immutable so long as they

aren't using mutable variables or data structures. There's no

reason immutable pairs couldn't be implemented in terms of

promises, in which case the tying the knot trick could be used

(under the hood) to provide utilities for generating cyclic

immutable lists.

Anyway, what I did was simply transliterate Oleg's circular

doubly-linked list example into Scheme, making Haskell's

implicit laziness explicit in the usual manner:

(define (force* x)

(if (promise? x) (force* (force x)) x))

(define (dlnode prev x next)

(vector prev x next))

(define (dlnode-prev node) (vector-ref (force* node) 0))

(define (dlnode-value node) (vector-ref (force* node) 1))

(define (dlnode-next node) (vector-ref (force* node) 2))

(define (list->dlist ls)

(define (go prev x next)

(if (null? x)

(list next prev)

(letrec ((this (delay (dlnode prev (car x) rest)))

(tmp (delay (go (force this) (cdr x) next)))

(rest (delay (car (force tmp))))

(last (delay (cadr (force tmp)))))

(list (force this) (force last)))))

(letrec ((tmp (delay (go last ls first)))

(first (delay (car (force tmp))))

(last (delay (cadr (force tmp)))))

(force first)))

(define (take-forward i node)

(if (zero? i)

'()

(cons (dlnode-value node)

(take-forward (- i 1) (dlnode-next node)))))

(define (take-reverse i node)

(if (zero? i)

'()

(cons (dlnode-value node)

(take-reverse (- i 1) (dlnode-prev node)))))

(define (test)

(take-reverse 5 (list->dlist '(1 2 3 4 5 6 7))))

Alex