Scheme - continuation galore

Author

continuation galore

Johannes Ahlmann

2005-08-04, 10:02 pm

hi,

i have tried for many times to defy all stupidity and learn
continuations for good, but only recently did i have a real
break-through.
but, as it goes with such elusive features, i am having some advanced
(for me at least) problems; not to say that i went too deep into
dangerous waters ;-)

what i wanted to do, was to implement continuous fractions with a
generator|call/cc, and totally awed that i actually managed to implement
it, i then found out that my "

" solution captured a little more of
its environment than i wanted and i simply don't know why...

continuous fractions look like this for example:

1/(1+ 1/(1+ 1/(1+ ... 1/(1+ 1))..))
this would be the "series" converging on the inverse of the golden
ratio.

so if any of you have ideas how to implement this, or what might be
wrong with my implementation; i'd be really thankful to know why this
won't work, but nearly identical code does!

<begin code>

;; macros to make the code more readable...
(define-syntax yield
(syntax-rules ()
((yield to from value)
(call/cc
(lambda (state)
(set! from (lambda () (state 'dummy)))
(to value))))))

(define-syntax with-caller
(syntax-rules ()
((with-caller caller iterator body ...)
(let ((caller #f))
(letrec ((iterator
(lambda ()
body ...)))
(lambda ()
(call/cc
(lambda (caller-cont)
(set! caller caller-cont)
(iterator)))))))))

;; collect the first n result of a generator.
(define (takeN n gen)
(if (< n 0)
'()
(cons (gen) (takeN (- n 1) gen))))

;; working code
(define (fac-generator)
(with-caller
caller gen
(let loop ((i 1)
(n 1))
(yield caller gen n)
(loop (+ i 1) (* n (+ i 1))))))
(takeN 10 (fac-generator))

;; this is the offending code!
(define (cont-frac op1 op2 num den)
(with-caller
caller gen
(letrec ((next-step 'dummy)
(cont-frac-inner
(lambda (n)
(op1 (num n)
(op2 (den n)
(call/cc
(lambda (k)
(set! next-step
(lambda ()
(cont-frac-inner (+ n 1))))
(set! gen
(lambda () (k (next-step))))
1)))))))
(caller (cont-frac-inner 1)))))

(define (golden)
(cont-frac / +
(lambda (i) 1)
(lambda (i) 1)))

(takeN 10 (golden))

</end code>

while the factorial generator works fine and DOESN'T continuously
capture "takeN"s environment, the implementation of "cont-frac" leads to
an infinite loop in "takeN", as the counter in said function will not be
reduced below 9 in the above case.

sorry i posted so much code, but i didn't see how to show working and
non-working code side by side...

the only real difference i see, is that in "cont-frac" the caller
continuation is not invoked within a "call/cc" block, but i fail to see
how this could lead to such problems.

more seriously, i don't see why "fac-generator" can even work, as it
captures the callers continuation just once and then keeps invoking this
initial continuation, even though the calling code has in the meantime
altered its variables and maybe even reentered the captured inner
continuation from somewhere completely different.

well, i'd be thankful for any kind of feedback,

Johannes

Abdulaziz Ghuloum

2005-08-05, 9:02 am

Johannes Ahlmann wrote:

> hi,
> [...]
> continuous fractions look like this for example:
>
> 1/(1+ 1/(1+ 1/(1+ ... 1/(1+ 1))..))
> this would be the "series" converging on the inverse of the golden
> ratio.
>
> so if any of you have ideas how to implement this, or what might be
> wrong with my implementation; i'd be really thankful to know why this
> won't work, but nearly identical code does!
>
> <begin code>
>
> ;; macros to make the code more readable...
> (define-syntax yield
> (syntax-rules ()
> ((yield to from value)
> (call/cc
> (lambda (state)
> (set! from (lambda () (state 'dummy)))
> (to value))))))

You might want to get rid of the dummy and do the following:

(define-syntax yield
(syntax-rules ()
((yield to from value)
(call/cc
(lambda (state)
(set! from state)
(to value))))))

> (define-syntax with-caller
> (syntax-rules ()
> ((with-caller caller iterator body ...)
> (let ((caller #f))
> (letrec ((iterator
> (lambda ()
> body ...)))
> (lambda ()
> (call/cc
> (lambda (caller-cont)
> (set! caller caller-cont)
> (iterator)))))))))

This looks fine.

> ;; collect the first n result of a generator.
> (define (takeN n gen)
> (if (< n 0)
> '()
> (cons (gen) (takeN (- n 1) gen))))

> ;; working code
> (define (fac-generator)
> (with-caller
> caller gen
> (let loop ((i 1)
> (n 1))
> (yield caller gen n)
> (loop (+ i 1) (* n (+ i 1))))))
> (takeN 10 (fac-generator))

This returns (39916800 3628800 362880 40320 5040 720 120 24 6 2 1)

i should probably start with 0 instead of 1 to give us the more familiar
sequence: (3628800 362880 40320 5040 720 120 24 6 2 1 1)

> ;; this is the offending code!
> (define (cont-frac op1 op2 num den)
> (with-caller
> caller gen
> (letrec ((next-step 'dummy)
> (cont-frac-inner
> (lambda (n)
> (op1 (num n)
> (op2 (den n)
> (call/cc
> (lambda (k)
> (set! next-step
> (lambda ()
> (cont-frac-inner (+ n 1))))
> (set! gen
> (lambda () (k (next-step))))
> 1)))))))
> (caller (cont-frac-inner 1)))))
>
> (define (golden)
> (cont-frac / +
> (lambda (i) 1)
> (lambda (i) 1)))
>
> (takeN 10 (golden))

This looks too complicated!
How about something simpler like:

(define (golden-gen)
(with-caller caller gen
(let loop ([n 1])
(yield caller gen n)
(loop (+ 1 (/ 1 n))))))

> (takeN 10 (golden-gen))
(144/89 89/55 55/34 34/21 21/13 13/8 8/5 5/3 3/2 2 1)

Or:
> (map exact->inexact (takeN 10 (golden-gen)))
(1.6179775280898876
1.6181818181818182
1.6176470588235294
1.619047619047619
1.6153846153846154
1.625
1.6
1.6666666666666667
1.5
2.0
1.0)

I took your factorial code and modified it to match the equation you
gave for the golden ratio. Looks correct (modulo the floating point
accuracy).

Aziz,,,

Sponsored Links