Search code examples
schemecontinuations

Any history background about the "yin-yang puzzle" in detail?

There are quite a few questions about the "yin-yang puzzle" already in Stackoverflow:

I was wondering when and who find this beautiful programming pearl. So I dig into it. Here is my finding:

  • The first question was posted in 2010 and refers to a wikipedia page.
  • The current version of this page referred to Yin Wang's web blog.
  • Unfortunately he closed his blog but it is available in Web Archive, as at 2012/07/27.
  • This web blog refers to the first stack overflow question.
  • This means the wikipedia article was updated after the first question being asked.
  • The wikipedia article history shows the original yin-yang puzzle was added in 2009 by a registered user without any citation.

Now I lost all clues to track back the history before 2009. It is appear to be the case that this puzzle was well-known in 2009 at least in some society. Since the original puzzle is in Scheme, I assume it is a Scheme user group.

Can any one show more historical detail on this?

Solution

  • From comp.lang.scheme in 1999:

    https://groups.google.com/d/msg/comp.lang.scheme/Fysq_Wplxsw/awxEZ_uxW20J

    From: mad...@news.ens.fr (David Madore)
Subject: call/cc mind-boggler
Date: 1999/06/24
Message-ID: <7ktbid$a29$1@nef.ens.fr>#1/1
X-Deja-AN: 493362808
Organization: Ecole normale superieure
Newsgroups: comp.lang.scheme

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.)