On Thu, Sep 4, 2014 at 12:14 PM, Eli Barzilay <e...@barzilay.org> wrote:
> On Wed, Sep 3, 2014 at 2:17 AM, Alex Shinn <alexsh...@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
_______________________________________________ Scheme-reports mailing list Scheme-reports@scheme-reports.org http://lists.scheme-reports.org/cgi-bin/mailman/listinfo/scheme-reports
