Pepsi and Coke (No. 2) - squeakerのブログ

One of Coke's strength is manipulating syntax trees, like any other lispy languages. In Coke, there are some features that lets you transform a syntax tree into another form. It doesn't have all the features that a sophisticated Lisp macro system provides, but still you can have fun with it.

For the way I'm thinking to implement Ruby methods, where the number of actual arguments for a method can be different at a call site to another, I think I need to define a function that generates different functions. Such a generated function sits at a call site, handles the actual arguments, and gives "cooked" arguments to another function that represents the body of the Ruby method.

First, let me see if I can really generate different functions from one function. In Scheme, a function can indeed return different functions. I used an online Scheme interpreter here (http://www.yuasa.kuis.kyoto-u.ac.jp/~yhara/webscheme/demo/nine5.html) and typed:

(define x '())

(define (foo n)
   (if (> n 0)
       (let ((f (lambda (a) (* a n))))
         (set! x (cons f x))
         (foo (- n 1)))))

(foo 3)

((car x) 2)
((cadr x) 2)
((caddr x) 2)

The function "foo" calls itself given number of times, and for each call, it creates a "new" closure and links it to the list "x" (The executable body of the code may be shared but the environment part of the closure are different). The result from the above code is:

(define x (quote ()))
=> ()
(define (foo n) (if (> n 0) (let ((f (lambda (a) (* a n)))) (set! x (cons f x)) (foo (- n 1)))))
=> #lambda
(foo 3)
=> #null
((car x) 2)
=> 2
((cadr x) 2)
=> 4
((caddr x) 2)
=> 6

As you can tell from the last three expressions, the list "x" holds three different functions (or closures). Can we use the same implementation of "foo" in Coke?

It turned out that the answer is no for two reasons. First, you cannot define the following function (due to a compile time error) in Coke:

(define x [Array new: '0])
(define foo
  (lambda (n)
    (if [n > '0]
	(let ((f (lambda (a) [a * n])))
	  (set x [[Array with: f], x])
	  (foo [n - '1])))))

The reason of this compile time error is that "n" in "[a * n]" is a free variable, but I think it can't be an argument of the enclosing environment created by a lambda. As I heard from the author, Coke is a language with C-semantics, so functions are not closures. And, nested functions in Coke cannot be translated to functions in C.

Secondly, the Coke compiler doesn't create different closures or functions for each invocation of lambda. A minor variation of "foo" in Coke would be:

(define x [Array new: '0])
(define r '0)

(define foo
  (lambda (n)
    (if [n > '0]
	(let ((f (lambda (a) [a * r])))
	  (set r [r + '1])
	  (set x [[Array with: f], x])
	  (foo [n - '1])))))

There is still a free variable "r" in the (inner) lambda, but it is a global variable that is updated for each iteration. (Oh, by the way, if you'd write the part "[n - '1]" as "[n - 1]", it wouldn't stop. because "1" is '0. You have to be careful to deal with numbers...)

This code snippet compiles but doesn't work as you wish. The following is the results from the interactive shell after evaluating the code above:

.(foo '3)
 => 0
.([x first] '2)
 => 13
.([x second] '2)
 => 13
.(== [x first] [x second])
 => 1

"13" is "6" in the object world, and it means that 2 multiplied by 3 was computed by both the first entry and the second entry of "x" Array. The last expression shows that "[x first]" and "[x second]" are indeed identical. I'd imagine that a (static) use of lambda is usually compiled just once. It makes sense that it is C semantics, but this is not convenient for what I would like to do. One way I found is to create different syntax trees and compile them to create different functions on the fly. And, of course, creating a syntax tree easily is one of the stuff Coke supports.

Do you know the quasi-quotation mechanism in Lisp-family languages? Coke has it, too.

I leave the detail of quasi-quotation to other materials, but basically you can construct an Expression object from a sort of "template" with holes, and actual values that should go to the holes. For example:

`(* 1 3)

is a template (without a hole). If you print the result, you get:

.[`(* 1 3) size]
 => 7
.[`(* 1 3) print]
(#* 1 3) => 17

It is an Expression whose size is 3 and contains "*", "1", and "3".

To make a hole in the template, you use an identifier with comma:

`(* 1 ,x)

and to fill the hole, you just supply the value for the identifier in the environment:

(define x '3)
`(* 1 ,x)

If you evaluate the expression, "x" is filled with the actual value bound to the identifier. In this case, you get "(#* 1 3)" Expression object as the result. (There is also ,@ that "splices" the actual value, but you can learn about it elsewhere.)

Now, I would like to create an executable function from the Expression object. I figured out that "_eval" message does it. (There may be a simpler way, actually. But couldn't find it yet. Of course, the system is under heavly development so these details are subject to change.)

So, to mimic the foo function in Scheme does, I ended up with:

(define new-function
  (lambda (val)
    [`(lambda (a) [a * ',val]) _eval]))

(define x [Array new: '0])

(define foo
  (lambda (m)
     (if [m > '0]
 	(let ((f (new-function m)))
  	  (set x [[Array with: f], x])
  	  (foo [m - '1])))))

The "new-function" function first creates a new function that multiplies the argument with a constant. The constant is taken from the value of the actual argument for "new-function" and is embedded into the newly created function. The notation "',val" looks tricky, but the single-quote is necessary because converting the value to a string form seems to be done in the object world, but it doesn't put a quote. Resulting Expression is then converted to an executable function by "_eval" and returned. For each invocation of "foo", "new-function" is called and the result is stored into the global "x" Array.

If you evaluate:

.(foo '3)
 => 0
.([x first] '2)
 => 5
.([x second] '2)
 => 9
.([x third] '2)
 => 13
.(== [x first] [x second])
 => 0

you can tell it is doing what you would like it to do. Of course, you can simplify "foo" to something like:

(define foo
  (lambda (m)
     (if [m > '0]
 	(let ((f [`(lambda (a) [a * ',m]) _eval]))
  	  (set x [[Array with: f], x])
  	  (foo [m - '1])))))

Okay, the quotes and stuff can confuse you, but we'll see more confusing stuff that use "syntax" form later on.