RE: Icon

[Guy Steele - Sun Microsystems Labs <address@hidden>]

   Date: Wed, 19 Dec 2001 22:39:27 -0800 (PST)
   From: Paul Graham <paulgraham@yahoo.com>
   Subject: RE: Icon
   To: Todd Proebsting <toddpro@microsoft.com>
   Cc: ll1-discuss@ai.mit.edu
   
   Could you give us a longer example (say 10 or 20 lines)
   that shows why you grumble when you have to use other
   languages?  These little examples do help explain what
   GD is, but don't show why it is so great.  What would
   convince me would be a useful program that is easy to 
   express using GD and awkward to express without it.
   
   (Then stand back while Cozens rewrites it as one line
   of Perl...;-)
   
   Another Q: how hard would GD be to implement using closures
   and macros?  It feels a bit like Waters' series macros.

It's not that difficult if you use CPS translation.  I did a
term paper on a related topic for Ira Goldstein in 1977 or so.

The basic idea is to think of every function as taking two
continuations, one for success and one for failure, and
returning two values, which are a result and a retry-function.
(More precisely, a success continuation is a function
of two arguments, which are a result and a retry-function.
A failure continuation is a function of no arguments.  What is a
retry-function?  It's actually just a failure continuation!)  If you
then consider what the code looks like in continuation-passing style,
it's easy to express in YFFL (Your Favorite Functional Language).

An "ordinary function" such as + looks something like this:

	(define (+ a b sc fc)
	  (sc (add a b) fc))

where "add" is the addition operator of the functional meta-language.
Given two values, the basic addition operation always succeeds, so
it just calls the success continuation, giving it the sum and the
failure continuation.  If the success continuation decides it wants
to retry, the failure continuation given to + will be called;
at that point + itself is out of the picture.

The operation "fail" looks like this:

	(define (fail sc fc) (fc))

It is simply an operation that discards its success continuation
and calls its failure continuation.

The operation "to" looks like this:

	(define (to lower upper sc fc)
	  (if (> lower upper)
	      (fc)
	      (sc lower (lambda () (to (add lower 1) upper sc fc)))))

If the lower bound is above the upper bound, there are no more
numbers to generate, so it calls its failure continuation.
otherwise, it feeds the value "lower" to the success continuation;
the retry-function recursively generates values from lower+1 to upper.
(Actually, iteratively, not recursively, because the recursive call
to "to" is a tail-call!)


It is also necessary to explain how expressions are translated into
this variant CPS so that you get the cross-product effect when multiple
generators are involved.  Let [e sc fc] be a CPS translation operator
that translates expression e into CPS using two continuations.
I'll explain the translation of literal constants, variables,
and function calls, because that's all I need for my simple example:

[<literal> sc fc]  =>  (sc <literal>)

[<variable> sc fc]  =>  (sc <variable>)

[(f a b) sc fc] => [f (lambda (xf fc1)
			 [a (lambda (xa fc2)
			       [b (lambda (xb fc3)
			             (xf xa xb sc fc3))
			          fc2])
			    fc1])
		      fc]

assuming that xf, xa, xb, fc1, fc2, fc3 are fresh variable names
not already appearing in the program.  Then, if you crank it through,
doing translations and beta-reductions (that is, substituting
arguments for parameters of lambda-expressions), you find that the
translation

	[(+ (1 to 3) (4 to 6)) sc fc]

produces (I show just some of the intermediate steps)


[(+ (to 1 3) (to 4 6)) sc fc]

[+ (lambda (xf fc1)
     [(to 1 3) (lambda (xa fc2)
	          [(to 4 6) (lambda (xb fc3)
	                       (xf xa xb sc fc3))
	                    fc2])
               fc1])
   fc]

[(to 1 3) (lambda (xa fc2)
             [(to 4 6) (lambda (xb fc3)
	                  (+ xa xb sc fc3))
	               fc2])
          fc])

[to (lambda (xf1 fc1a)
       [1 (lambda (xa1 fc2a)
             [3 (lambda (xb1 fc3a)
		  (xf1 xa1
		       xb1
		       (lambda (xa fc2)
			 [(to 4 6) (lambda (xb fc3)
				     (+ xa xb sc fc3))
			 fc2])
		       fc3a))
		fc2a])
	  fc1a])
    fc]

(to 1
    3
    (lambda (xa fc2)
      [(to 4 6) (lambda (xb fc3)
		  (+ xa xb sc fc3))
                fc2])
    fc)

(to 1 3 (lambda (xa fc2) (to 4 6 (lambda (xb fc3) (+ xa xb sc fc3)) fc2)) fc)

and if you study this and the definition of "to", you will see that
it generates the sequence 5 6 7 6 7 8 7 8 9, as advertised.  (To test
this, I translated it into Common Lisp by using defun syntax instead
of define, inserting #' as needed, and renaming some functions to avoid
collisions with Common Lisp's built-in functions:

(defun plus (a b sc fc) (funcall sc (+ a b) fc))

(defun to (lower upper sc fc)
  (if (> lower upper)
      (funcall fc)
    (funcall sc lower #'(lambda () (to (+ lower 1) upper sc fc)))))

;;; The following function is the translation of (plus (to 1 3) (to 4 6)).
(defun try (sc fc)
  (to 1 3 #'(lambda (xa fc2)
              (to 4 6 #'(lambda (xb fc3) (plus xa xb sc fc3)) fc2)) fc))

and then I ran it with this test case (note that the "success continuation"
prints the value and then calls the failure continuation to force
generation of another possibility):

(try #'(lambda (v fc) (print v) (funcall fc)) #'(lambda () 'done))

This code indeed produces the output

5 
6 
7 
6 
7 
8 
7 
8 
9 
DONE

which I have just copied-and-pasted from my terminal window.

See?  it's easy!  :-)

--Guy