Puzzle

[Jens Axel Søgaard]

I just fell over this little gem from the comp.lang.scheme archives.

Can you figure out what it does with out running it?

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

It was written by the master of obfuscation David Madore, who
created Unlambda.

--
Jens Axel Søgaard

[zhaoway]

"Jens Axel S gaard" <use...@soegaard.net> wrote in message news:<Q8M1a.73770$Hl6.7...@news010.worldonline.dk>...

> I just fell over this little gem from the comp.lang.scheme archives.
>
> Can you figure out what it does with out running it?
>
> (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 think yin and yang are not balanced. It is not good! 8-)

[Taylor Campbell]

From what I can tell, it looks like it should print a newline, an
asterisk, a newline, and then repeat printing asterisks infinitely:

(let* ((yin (<f1> ; <f1> being (lambda (foo) (newline) foo)
<k1>)) ; <k1> being the result of
; (call/cc (lambda (bar) bar))
(yang (<f2> ; <f2> being (lambda (foo) (write-char #\*) foo)
<k2>))) ; <k2> being the result of
; (call/cc (lambda (bar) bar))
(yin yang))

First, a newline is printed, from the first call of <f1>. Then an
asterisk is printed from the first call of <f2>. Then control jumps to
<k1> (the starting value of yin), applying a function that writes a
newline and returns its argument the value of yang; i.e.:

(<f1> <k2>)

is bound to yin and the whole thing repeats (a newline is printed, after
which an asterisk is printed), except that yin is now bound to <k2>, not
not <k1>, so control will never go back to:

(let* ((yin (<f1> <k1>))
^^^^

and instead will go to:

(yang (<f2> <k2>)))
^^^^

when yin is called with yang.

Since yin is called with yang again, and the two procedures will jump to
the same point when called, it will always jump to <k2>, calling <f2>
and printing asterisks infinitely.

So that I might correct myself lest I am incorrect without having tried
it yet, would you mind telling me if I was correct?

[felix]

Jens Axel Søgaard wrote:
> I just fell over this little gem from the comp.lang.scheme archives.
>
> Can you figure out what it does with out running it?
>
> (let* ((yin ((lambda (foo) (newline) foo)
> (call/cc (lambda (bar) bar))))
> (yang ((lambda (foo) (write-char #\*) foo)
> (call/cc (lambda (bar) bar)))))
> (yin yang))
>

It gives an "unbound variable: call/cc" error.

That was easy.

cheers,
felix

[Jens Axel Søgaard]

felix wrote:

> It gives an "unbound variable: call/cc" error.
>
> That was easy.

Cheater!

--
Jens Axel Søgaard

[Jens Axel Søgaard]

Taylor Campbell wrote:
> Jens Axel Søgaard wrote:
>> I just fell over this little gem from the comp.lang.scheme archives.
>>
>> Can you figure out what it does with out running it?
>>
>> (let* ((yin ((lambda (foo) (newline) foo)
>> (call/cc (lambda (bar) bar))))
>> (yang ((lambda (foo) (write-char #\*) foo)
>> (call/cc (lambda (bar) bar)))))
>> (yin yang))
>>

> From what I can tell, it looks like it should print a newline, an

> asterisk, a newline, and then repeat printing asterisks infinitely:

The first asterisk is ok, and it's true that it keeps printing, but
the asterisks are interspersed with newlines, to form a certain pattern.

--
Jens Axel Søgaard

[Jeffrey M. Vinocur]

[ including comp.lang.ml ]

In article <Gyd2a.80115$Hl6.7...@news010.worldonline.dk>,

Jens Axel Sgaard <use...@soegaard.net> wrote:
>Taylor Campbell wrote:

Wow. I definitely fell for that one.

However, I found it helpful to work it out with types. It's a
bit awkward in ML because you have to tie the knot yourself to
get the function passed to callcc to have the right type (thus
I guess writing let/cc in ML would be very difficult), but the
result is the same. So I thought I'd share:

local
open SMLofNJ.Cont
datatype 'a knot = K of 'a knot cont
val K(yin) = (callcc K) before (print "\n")
val K(yang) = (callcc K) before (print "*")
in
val life = throw yin (K yang)
end

--
Jeffrey M. Vinocur * jm...@cornell.edu
http://www.people.cornell.edu/pages/jmv16/

[be...@sonic.net]

felix wrote:
>
> It gives an "unbound variable: call/cc" error.
>
> That was easy.

An important part of every scheme library whose implementation fails
to provide it natively:

;;; the universal shortcut notation for
;;; ridiculously-long-named-function....
(define call/cc call-with-current-continuation)

Just bein' helpful....

Bear

[David Rush]

be...@sonic.net writes:
> felix wrote:
> >
> > It gives an "unbound variable: call/cc" error.
>

> An important part of every scheme library whose implementation fails
> to provide it natively:
>
> ;;; the universal shortcut notation for
> ;;; ridiculously-long-named-function....
> (define call/cc call-with-current-continuation)

Would you consider writing this up as a SRFI? ;)

david rush
--
Computer games don't affect kids. If Pac Man affected us as kids, we
would all be running around in darkened rooms, munching pills, and
listening to repetitive music.
-- Andreas Rossberg (on comp.lang.ml)

[Taylor Campbell]

Jens Axel Søgaard wrote:
> The first asterisk is ok, and it's true that it keeps printing, but
> the asterisks are interspersed with newlines, to form a certain pattern.
>
> --
> Jens Axel Søgaard

Hmm. I'll try again, where <f1> is an expression evaluating to a
function that writes a newline and returns its argument, <f2> is an
expression evaluationg to function that writes an asterisk and returns
its argument, <call/ccn> is the expression

(call/cc (lambda (bar) bar))

<kn> is a continuation that corresponds to the value returned by
<call/ccn>, [value] is the place into which control jumps and 'value'
returned, and <ignored> is a place whose value is irrelevant and
discarded due to continuation jumps.

The original let* is expanded down to function creation and application.

=jump to <kx> at contexty-(outer|middle) with <kz>=> indicates a
jump, that the innermost dynamic context that the jump jumped to is the
context specified, and that the value returned by the continuation that
was jumped to is <kz>

context1-outer:
((lambda (yin)
; context1-middle:
; A newline has been written. Note the usage of 'has been written'
; -- it isn't written in the previous or next line, but in the
; arguments to the function, but the comment was put here for
; clarity -- if the comment were put over the line in which a newline
; was written it would appear that the asterisk was written first.
; yin => <k1>
((lambda (yang)
; An asterisk has been written.
; yin => <k1>
; yang => <k2>
(yin yang))
(<f2> <call/cc2>)))
(<f1> <call/cc1>))

Output is:
"
*"

=jump to <k1> at context1-outer with <k2>=>

context1-outer:
((lambda (yin)
; context2-middle: (new context because of jump)
; \n
; yin => <k2>
((lambda (yang)
; *
; yin => <k2>
; yang => <k3>
(yin yang))
(<f2> <call/cc3>)))
(<f1> [<k2>]))

Output is:
"
*
*"

=jump to <k2> at context1-middle with <k3>=>

context1-outer:
((lambda (yin)
; context1-middle:
; yin => <k1> (but no newline: no jump to <k1>)
((lambda (yang)
; *
; yin => <k1>
; yin => <k3>
(yin yang))
(<f2> [<k3>])))
<ignored>)

Output is:
"
*
**"

=jump to <k1> at context1-outer with <k3>=>

context1-outer:
((lambda (yin)
; context3-middle:
; \n
; yin => <k3>
((lambda (yang)
; *
; yin => <k3>
; yang => <k4>
(yin yang))
(<f2> <call/cc4>)))
(<f1> [<k3>]))

Output is:
"
*
**
*"

=jump to <k3> at context2-middle with <k4>=>

context1-outer:
((lambda (yin)
; context1-middle:
; yin => <k2>
((lambda (yang)
; *
; yin => <k2>
; yang => <k4>
(yin yang))
(<f2> [<k4>])))
<ignored>)

Output is:
"
*
**
**"

=jump to <k2> at context1-middle with <k4>=>

context1-outer:
((lambda (yin)
; context1-middle:
; yin => <k1>
((lambda (yang)
; *
; yin => <k1>
; yang => <k4>
(yin yang))
(<f2> [<k4>])))
<ignored>)

Output is:
"
*
**
***"

=jump to <k1> at context1-outer with <k4>=>

context1-outer:
((lambda (yin)
; context4-middle:
; \n
; yin => <k4>
((lambda (yang)
; *
; yin => <k4>
; yang => <k5>
(yin yang))
(<f2> <call/cc5>)))
(<f1> <k4>))

Output is:
"
*
**
***
*"

=jump to <k4> at context3-middle with <k5>=>

context1-outer:
((lambda (yin)
; context2-middle:
; yin => <k3>
((lambda (yang)
; *
; yin => <k3>
; yang => <k5>
(yin yang))
(<f2> [<k5>])))
<ignored>)

Output is:
"
*
**
***
**"

=jump to <k3> at context2-middle with <k5>=>

context1-outer:
((lambda (yin)
; context2-middle:
; yin => <k2>
((lambda (yang)
; *
; yin => <k2>
; yang => <k5>
(yin yang))
(<f2> [<k5>])))
<ignored>)

Output is:
"
*
**
***
***"

=jump to <k2> at context1-middle with <k5>=>

context1-outer:
((lambda (yin)
; context2-middle:
; yin => <k1>
((lambda (yang)
; *
; yin => <k1>
; yang => <k5>
(yin yang))
(<f2> [<k5>])))
<ignored>)

Output is:
"
*
**
***
****"

=jump to <k1> at context1-outer with <k5>=>

context1-outer:
((lambda (yin)
; context5-middle:
; \n
; yin => <k5>
((lambda (yang)
; *
; yin => <k5>
; yang => <k6>
(yin yang))
(<f2> <call/cc6>)))
(<f1> [<k5>]))

Output is:
"
*
**
***
****
*"

=jump to <k5> at context4-middle with <k6>=>

context1-outer:
((lambda (yin)
; context4-middle:
; yin => <k4>
((lambda (yang)
; *
; yin => <k4>
; yang => <k6>
(yin yang))
(<f2> [<k6>])))
<ignored>)

Output is:
"
*
**
***
****
**"

=jump to <k4> at context3-middle with <k6>=>

context1-outer:
((lambda (yin)
; context3-middle:
; yin => <k3>
((lambda (yang)
; *
; yin => <k3>
; yang => <k6>
(yin yang))
(<f2> [<k6>])))
<ignored>)

Output is:
"
*
**
***
****
***"

=jump to <k3> at context2-middle with <k6>=>

context1-outer:
((lambda (yin)
; context2-middle:
; yin => <k2>
((lambda (yang)
; *
; yin => <k2>
; yang => <k6>
(yin yang))
(<f2> [<k6>])))
<ignored>)

Output is:
"
*
**
***
****
****"

=jump to <k2> at context1-middle with <k6>=>

context1-outer:
((lambda (yin)
; context1-middle:
; yin => <k1>
((lambda (yang)
; *
; yin => <k1>
; yang => <k6>
(yin yang))
(<f2> [<k6>])))
<ignored>)

Output is:
"
*
**
***
****
*****"

=jump to <k1> at context1-outer with <k6>=>

context1-outer:
((lambda (yin)
; context1-outer:
; \n
; yin => <k6>
((lambda (yang)
; *
; yin => <k6>
; yang => <k7>
(yin yang))
(<f2> <call/cc7>)))
(<f1> [<k6>]))

I could go on, but it would be pointless, as I already see the pattern,
which is that it prints one asterisk on one line, two on the next,
three on that which follows, four on the yet next, et cetera et cetera:

*
**
***
****
*****
******
*******
********
...

Was I correct this time?

[Taylor Campbell]

Taylor Campbell wrote:
> which is that it prints one asterisk on one line, two on the next,
> three on that which follows, four on the yet next, et cetera et cetera:

Whoops, that should include the fact that it prints one newline first.

[be...@sonic.net]

David Rush wrote:
>
> be...@sonic.net writes:

> > An important part of every scheme library whose implementation fails
> > to provide it natively:
> >
> > ;;; the universal shortcut notation for
> > ;;; ridiculously-long-named-function....
> > (define call/cc call-with-current-continuation)
>
> Would you consider writing this up as a SRFI? ;)
>

I think it's sufficiently universal that a SRFI is not actually
required, as well as being so ridiculously easy for the user to
provide that the implementor doesn't really have to worry about
it if it's absent.

Bear

[David Rush]

be...@sonic.net writes:
> David Rush wrote:
> > be...@sonic.net writes:
> > > An important part of every scheme library whose implementation fails
> > > to provide it natively:

> > > (define call/cc call-with-current-continuation)
> >
> > Would you consider writing this up as a SRFI? ;)
>
> I think it's sufficiently universal that a SRFI is not actually
> required,

...

<Shakes head>

david rush
--
In a profession plagued by, "when all you have is a hammer, everything
looks like a nail," we get really excited when someone is able to come
along and prove that everything really *is* a nail if lambda is the
hammer. -- Bruce R Lewis (on comp.lang.scheme)

[Jens Axel Søgaard]

Taylor Campbell wrote:
> Jens Axel Søgaard wrote:
>> The first asterisk is ok, and it's true that it keeps printing, but
>> the asterisks are interspersed with newlines, to form a certain
>> pattern.

> I could go on, but it would be pointless, as I already see the
> pattern, which is that it prints one asterisk on one line, two on the
> next, three on that which follows, four on the yet next, et cetera et
> cetera:
>
> *
> **
> ***
> ****
> *****
> ******
> *******
> ********
> ...
>
> Was I correct this time?

Yes - indeed. Very nice analysis.

--
Jens Axel Søgaard

[Anton van Straaten]

> > An important part of every scheme library whose implementation fails
> > to provide it natively:
> >
> > ;;; the universal shortcut notation for
> > ;;; ridiculously-long-named-function....
> > (define call/cc call-with-current-continuation)
>
> Would you consider writing this up as a SRFI? ;)

I'd like to propose that this SRFI be made more general. In my upcoming
implementation of Scheme, oriented towards people who type very slowly (on
keyboards, that is), I have abbreviated call-with-current-continuation to
ccc, which is much quicker to type even than call/cc, and thus is clearly
superior for my purposes.

To avoid placing unnecessary restrictions on (possible future) implementors
such as myself, I originally thought that the SRFI that's really needed
would be something more like "A Generalized Facility for the Abbreviation of
Existing Identifiers".

However, it occured to me that the thing needing abbreviation might not
already be an identifier. Based on a rigorous formal analysis of the
semantics of identifier binding in Scheme, I have determined that what's
really needed is "A Generalized Facility for the Binding of Abbreviated
Identifiers to Values".

But wait, there's more: further thorough and careful analysis has indicated
that it is also possible to support *non*-abbreviated names with this new
mechanism!

So I'd like to entitle my proposal "A Generalized Facility for the Binding
of Both Abbreviated and Non-Abbreviated Identifiers to Values". To support
this new mechanism, I propose a new special form named
'bind-abbreviated-or-non-abbreviated-identifier-to-value', which should have
the following form:

(bind-abbreviated-or-non-abbreviated-identifier-to-value <variable>
<expression>)

Since I understand that SRFIs require a reference implementation, I offer
the following:

(define-syntax bind-abbreviated-or-non-abbreviated-identifier-to-value
(syntax-rules ()
((_ identifier value)
(define identifier value))))

I am aware of only one possible problem with my proposal at this time: in
actual implementations, it may be desirable to abbreviate the name of this
new form. Unfortunately, the above reference implementation does not appear
capable of being used to abbreviate its own name. Most likely, this is a
bug in the reference implementation, which I confess was developed rather
hurriedly. OTOH, this limitation may in fact be due to Scheme's notoriously
restrictive hygienic macro facility, which is only Turing-complete when
wielded by Oleg K. or Al-abrador Petrofsky. However, I am confident that
this minor detail will be resolved during the SRFI process. That said, I
think we have the makings of a solid SRFI here, which will occupy an
important place within the SRFI system, similar to that of [1].

Anton

References:
[1] IETF RFC-1149, "A Standard for the Transmission of IP Datagrams on
Avian Carriers", David Waitzman, 1990.

[Feuer]

Anton van Straaten wrote:

> So I'd like to entitle my proposal "A Generalized Facility for the Binding
> of Both Abbreviated and Non-Abbreviated Identifiers to Values".

I think this is a good idea, but I think there are other directions to
explore. In particular, we could exploit long names to make it easier
to tell what we are and are not doing in our programs. For example,
we could add call-without-current-continuation to complement
call-with-current-continuation, and call-without-values and
call-with-great-justice to complement call-with-values. Of course, we
all have been waiting with bated breath for morals, to
complement values.

David