Y continued call/cc puzzles
ol...@pobox.com
Scheme. Therefore, it's used frequently in puzzles such as (yin yang)
or ((call/cc call/cc) (call/cc call/cc)). There is however a way to
banish call/cc: to rigorously transform code that uses call/cc into
the code that contains no call/cc. The resulting code is easier to
understand.
For example, if we apply our method to the (yin yang) puzzle:
(let* ((yin ((lambda (foo) (newline) foo)
(call/cc (lambda (bar) bar))))
(yang ((lambda (foo) (write-char #\*) foo)
(call/cc (lambda (bar) bar)))))
(yin yang))
we obtain
(define (yin% k)
(begin (newline)
(k (lambda (a d) (begin (newline) (k a))))))
(define (yang% k)
(begin (write-char #\*)
(k (lambda (a d) (begin (write-char #\*) (k a))))))
(yin%
(lambda (yp)
(yang%
(lambda (ap)
(yp ap k0)))))
Or, after a few trivial transformations,
(define level 0)
(define (wrs a)
(and (< level 10)
(begin (set! level (+ 1 level))
(a (lambda (a2) (begin (write-char #\*) (a a2)))))))
(begin
(newline)
((lambda (a)
(begin (write-char #\*)
(wrs a)))
(lambda (a)
(begin (newline) (begin (write-char #\*)
(wrs a))))))
where we do not iterate wrs for more than 10 levels.
Our approach can help us not only in analysis of old puzzles but also
in building new ones. For example,
(((call/cc call/cc)
(lambda (f)
(lambda (n) (if (zero? n) 1 (* n (((call/cc call/cc) f) (- n 1)))))))
5)
This expression does exactly what you might have expected.
Puzzles like that are easily derived by applying the Y combinator to
appropriate functions and then performing few beta-expansions or
reductions. As you might have guessed, we can indeed write:
(define (Y f)
((call/cc call/cc) (lambda (x) (lambda (n) ((f ((call/cc call/cc) x)) n)))))
((Y (lambda (f) (lambda (n) (if (zero? n) 1 (* n (f (- n 1))))))) 5)
or, if you prefer
(define (Y f)
((lambda (u) (u (lambda (x) (lambda (n) ((f (u x)) n)))))
(call/cc call/cc)))
or even
(define (Y f)
((lambda (u) (u (lambda (x) (lambda (n) ((f (u x)) n)))))
(call/cc (call/cc (lambda (x) x)))))
These formulas are the consequence of a theorem that we have derived
with our method: if p is a call/cc-free function,
((call/cc call/cc) p) <====> (p p)
The explanation of the method will be given at some later time.
BTW, there is a simple proof of that theorem using a higher-order
syntax:
(define (p x) (if (eq? x p) '(p p) `(p ,x)))
and evaluate
((call/cc call/cc) p)
or
((call/cc (call/cc (lambda (x) x))) p)
eli
> (define (p x) (if (eq? x p) '(p p) `(p ,x)))
> and evaluate
> ((call/cc call/cc) p)
> or
> ((call/cc (call/cc (lambda (x) x))) p)
Hmm... you can come to the same conclusions, less formally, by
executing the following.
(eq? ((call/cc call/cc) display) ((call/cc (lambda (x) x)) display))
(eq? ((call/cc (call/cc call/cc)) display) ((call/cc call/cc) display))
now we can also transform ((call/cc call/cc) display) to CPS:
((lambda (k) (k k)) display)
which in english is- call my continuation with an argument of my continuation
where my continuation is the procedure that is my argument -display.
-eli
David Rush
> ol...@pobox.com (ol...@pobox.com) wrote:
> > (define (p x) (if (eq? x p) '(p p) `(p ,x)))
> > and evaluate
> > ((call/cc call/cc) p)
> > or
> > ((call/cc (call/cc (lambda (x) x))) p)
>
> Hmm... you can come to the same conclusions, less formally, by
> executing the following.
> which in english is- call my continuation with an argument of my continuation
> where my continuation is the procedure that is my argument -display.
You'll pardon me if I don't find this text to be particularly ... perspicuous.
david rush
--
The Torah is written in black fire inscribed upon white fire - fire
mixed with fire, hewn out of fire and given from fire
-- 3rd Century Palestinian Merkavah Haggadah
David Rush
> > and evaluate
> > ((call/cc call/cc) p)
> > or
> > ((call/cc (call/cc (lambda (x) x))) p)
>
> Hmm... you can come to the same conclusions, less formally, by
> executing the following.
> which in english is- call my continuation with an argument of my continuation
> where my continuation is the procedure that is my argument -display.
You'll have to pardon me if I don't find this text to be particularly
Anton van Straaten
> e...@woti.com (eli) writes:
...
> > which in english is- call my continuation with an argument of my
continuation
> > where my continuation is the procedure that is my argument -display.
>
> You'll have to pardon me if I don't find this text to be particularly
> ... perspicuous.
As standalone English, that last sentence is a tad opaque, but treated as
comments for the code, its meaning is a bit clearer:
((lambda (k)
(k -- call my continuation
k)) -- with an argument of my continuation
display) -- where my continuation is the procedure
-- that is my argument - display
FWIW...
Anton