call/cc mind-boggler

865 views
Skip to first unread message

David Madore

unread,
Jun 24, 1999, 3:00:00 AM6/24/99
to
I sumbled (accidentally as it were) upon the following Scheme program:

(let* ((yin ((lambda (foo) (newline) foo)
(call/cc (lambda (bar) bar))))
(yang ((lambda (foo) (write-char #\*) foo)
(call/cc (lambda (bar) bar)))))
(yin yang))

(If you want the full story, I was inventing a language (called
``Unlambda'', essentially, an implementation of the lambda calculus
without the lambda operation) that is specially designed for
obfuscation, and whose interpreter is written in Scheme; I had written
a single program in it that was over 600 characters long to write the
integers consecutively (writing each integer by a line of asterisks).
Then I added the call/cc operation to the language, and while
experimenting with it I found that a 12-character program performed
exactly the same task as my longer program, namely ``r`ci`.*`ci (where
` means apply, c means call/cc and i is the identity, r and .* are
essentially newline and write *). Converting this program back to
Scheme gives the thing I have printed above. Well, that's the whole
story, I didn't claim it was interesting.)

I must admit I'm pretty clueless as to the modus operandi of this
program. I've tried it under guile, Bigloo and MIT-Scheme, and it
does the same thing, and I've simulated its evaluation by hand, but
this didn't really give me an insight as to how the darned thing works
(and the way these continuations have of ``reproducing'' is especially
mysterious).

So, could somebody come up with a clear and insightful explanation of
this mystery?

Another thing is, it should be possible to rewrite this program in
Continuation Passing Style. I have been completely unable to do so.
So I would be grateful if somebody could post such a rewrite (with an
explanation).

Thanks a lot.

--
David A. Madore
(david....@ens.fr,
http://www.eleves.ens.fr:8080/home/madore/)

Matthias Blume

unread,
Jun 25, 1999, 3:00:00 AM6/25/99
to
mad...@news.ens.fr (David Madore) writes:

> I sumbled (accidentally as it were) upon the following Scheme program:
>
> (let* ((yin ((lambda (foo) (newline) foo)
> (call/cc (lambda (bar) bar))))
> (yang ((lambda (foo) (write-char #\*) foo)
> (call/cc (lambda (bar) bar)))))
> (yin yang))

Ok, this one was fun. Thanks! :-)

Let me take a crack at it:

It is possible to explain the operation of this code in its own terms,
but it will be difficult, and my explanation may be just as hard to
follow as the code itself. :) So, instead, let me transform the code a
bit beforehand:

First, let me "let-float" some of the definitions, so that things
become a bit more readable:

;; rewritten in a more readable form
(define id (lambda (bar) bar))
(let ((yin (call/cc id)))
(newline)
(let ((yang (call/cc id)))
(write-char #\*)
(yin yang)))

Now, let's try to write this in CPS (continuation-passing style). In
order not to clutter the code too much, I will avoid to actually use
full CPS but only pass continuations in places where it is important.

;; CPS-expansion (well, sort-of)
(define (kcallcc k) (k k))
(kcallcc
(lambda (yin)
(newline)
(kcallcc
(lambda (yang)
(write-char #\*)
(yin yang)))))

At this point, my auxiliary function kcallcc (which is a CPS-converted
call/cc simplified to be just adequate for the task at hand) is so
simple that we can expand it away:

;; expanding away the definition of kcallcc
(define (star) (write-char #\*))
((lambda (yin)
(newline)
((lambda (yang)
(write-char #\*)
(yin yang))
(lambda (yang)
(write-char #\*)
(yin yang))))
(lambda (yin)
(newline)
((lambda (yang)
(write-char #\*)
(yin yang))
(lambda (yang)
(write-char #\*)
(yin yang)))))

Here we notice a certain amount of replication in the code, so we do a
common-subexpression eliminiation:

;; common-subexpression-elimination...
(define (yin0 yin)
(define (yang0 yang)
(write-char #\*)
(yin yang))
(newline)
(yang0 yang0))
(yin0 yin0)

First, observe that every invocation of yin0 will produce a newline.
If we number the initial invocation of yin0 with 0, the next
invocation 1, and so forth, then we notice that there will be one star
printed between invocation 0 and 1 (and zero stars before invocation
0). This is relatively easy to figure out "by hand". So we have a
basis for induction. We augment this basis by noticing that on
invocation 0 the argument yin is a function that when called from
within yang0 will produces 0 stars and then re-invoke ying0 with the
same argument.. (This is obvious because on invocation 0 yin is equal
to yin0.)

Our induction hypothesis is that for all k <= n the argument yin of
yin0 on invocation k is a function that when called from within yang0
produces k stars and then performs invocation k+1 of yin0 with the
same argument. From here, we want to show that on invocation n+1, yin
is a function that will produce n+1 stars before performing invocation
n+2 with the same argument.

Now, notice that if during invocation n yin is the argument suitable
for that invocation n, then the local function yang0 is the yin
suitable for invocation n+1 (because it is exactly the same as the
current yin with one more star being printed). After printing its
newline, invocation n will thus first print n+1 stars (by invoking
yang0 = the yin for the next invocation) and then invoke ying0 with
yang0 (= the correct yin for round n+1) because yang0 was passed as an
argument to itself.

Thus, we have found that there will be n stars printed between
invocation n-1 and n of yin0 for every n....

Does anyone STILL not see it? :-)

Best regards,
Matthias

--
Matthias Blume <blume@k_u_r_i_m_s.k_y_o_t_o-u.a_c.j_p>
Kyoto University, Research Institute for Mathematical Sciences
(remove underscores in mail address; they are there to fight spam)

Matthias Blume

unread,
Jun 25, 1999, 3:00:00 AM6/25/99
to
> mad...@news.ens.fr (David Madore) writes:
>
> > I sumbled (accidentally as it were) upon the following Scheme program:
> >
> > (let* ((yin ((lambda (foo) (newline) foo)
> > (call/cc (lambda (bar) bar))))
> > (yang ((lambda (foo) (write-char #\*) foo)
> > (call/cc (lambda (bar) bar)))))
> > (yin yang))

I replied...

> Ok, this one was fun. Thanks! :-)
>
> Let me take a crack at it:

> [ ... and so on ... ]

Just to be sure: My "explanation" was just that -- an explanation, not a
proof.

Chris Bitmead

unread,
Jul 21, 1999, 3:00:00 AM7/21/99
to
If obfuscation is your measure of success, congrats - you're a genius!

David Madore wrote:
>
> I sumbled (accidentally as it were) upon the following Scheme program:
>
> (let* ((yin ((lambda (foo) (newline) foo)
> (call/cc (lambda (bar) bar))))
> (yang ((lambda (foo) (write-char #\*) foo)
> (call/cc (lambda (bar) bar)))))
> (yin yang))
>

Reply all
Reply to author
Forward
0 new messages