[racket] "compiling" evaluation of an arbitrary s-expression

From: Matthias Felleisen (matthias at ccs.neu.edu)
Date: Tue Jun 7 11:43:08 EDT 2011

Oops. Thanks. 

In addition to a closure pass, you can also ask to generate two values: a symbolic representation, ready for printing, and a closure. It's just a couple of lines extra. In plain Racket, I'd use values to do dit. In *SL you have to use lists of pairs. 

This is indeed a nice example of using lambda for *representation* and not for abstraction. Good idea. 


On Jun 7, 2011, at 11:41 AM, Robby Findler wrote:

> [ I think Matthias probably meant to lift
> 
>  (generate-expression (sub1 i))
> 
> out of the (lambda (x y) ...). ]
> 
> Robby
> 
> On Tue, Jun 7, 2011 at 8:31 AM, Matthias Felleisen <matthias at ccs.neu.edu> wrote:
>> 
>> Why don't you teach them how closure compilers work:
>> 
>> #|
>>                 EXPR = x |
>>                        y |
>>                        (,sinpi EXPR) |
>>                        (,cospi EXPR) |
>>                        (,* EXPR EXPR) |
>>                        (,avg EXPR EXPR)
>> |#
>> 
>> ;; N -> EXPR
>> ;; generate an expression of depth i
>> (define (generate-expression i)
>>  (local ((define select (random 6)))
>>    (cond
>>      [(= select 0) (lambda (x y) x)]
>>      [(= select 1) (lambda (x y) y)]
>>      [(= select 2) (lambda (x y) (sin ((generate-expression (sub1 i)) x y)))]
>>      [(= select 3) (lambda (x y) (cos ((generate-expression (sub1 i)) x y)))]
>>      [(= select 4) (lambda (x y)
>>                      (* ((generate-expression (sub1 i)) x y)
>>                         ((generate-expression (sub1 i)) x y)))]
>>      [(= select 5) (lambda (x y)
>>                      (avg ((generate-expression (sub1 i)) x y)
>>                           ((generate-expression (sub1 i)) x y)))])))
>> 
>> (define (avg x y)
>>  (/ (+ x y)
>>     2))
>> 
>> 
>> ((generate-expression i) -1.0 +1.0)
>> 
>> You may have to fix the details. -- Matthias
>> 
>> 
>> 
>> On Jun 7, 2011, at 10:19 AM, Stephen Bloch wrote:
>> 
>>> I was looking at <a href="http://nifty.stanford.edu/2009/stone-random-art/">this Nifty Assignment</a>, which of course lends itself very nicely to my picturing-programs teachpack.
>>> 
>>> The random-expression generator to produce random trees over the algebra
>>>       EXPR = x |
>>>                       y |
>>>                       (sinpi EXPR) |
>>>                       (cospi EXPR) |
>>>                       (* EXPR EXPR) |
>>>                       (avg EXPR EXPR)
>>> is an easy student exercise.  (Note that each of these functions maps [-1,1] to [-1,1], so composing them at random makes sense.)
>>> 
>>> If I copy-and-paste the random expressions thus generated into the body of a function definition, I (or my students) can produce cool graphics like the ones at the Nifty Assignment web page, reasonably efficiently (e.g. a 300x300 pixel image, each pixel of which requires 26 trig functions, in 1.5 seconds).  But that requires manual intervention to copy-and-paste the expressions into a definition and then re-"Run".
>>> 
>>> Or I can take the random expression as a parameter and "eval" it (or more precisely, insert it into a backquoted expression to bind "x" and "y", and "eval" that).  Much more elegant, not to mention scriptable, than doing the copy-and-paste... but it takes c. 200 times longer to run, presumably because the expression is being rebuilt and re-parsed for each pixel.
>>> 
>>> (define (eval-with-x-y x y fmla)
>>>  (eval `(let ((x ,x)  (y ,y)) ,fmla)
>>>        eval-ns))
>>> 
>>> Is there a way I can get the best of both worlds?  I'd like to take an arbitrary s-expression (containing the free variables "x" and "y" as well as a limited set of function names) and "compile" it into a function of x and y that can be called efficiently on each of tens of thousands of pixels.
>>> 
>>> Assuming the answer is "yes" (this IS Racket, after all :-)), the next challenge is to package it so it's accessible from student programs in *SL.
>>> 
>>> 
>>> 
>>> Stephen Bloch
>>> sbloch at adelphi.edu
>>> 
>>> 
>>> _________________________________________________
>>>  For list-related administrative tasks:
>>>  http://lists.racket-lang.org/listinfo/users
>> 
>> 
>> _________________________________________________
>>  For list-related administrative tasks:
>>  http://lists.racket-lang.org/listinfo/users
>> 




Posted on the users mailing list.