From posting-system@google.com Fri Feb 15 17:40:22 2002 Date: Fri, 15 Feb 2002 14:40:19 -0800 From: oleg@pobox.com (oleg@pobox.com) Newsgroups: comp.lang.functional,comp.lang.scheme Subject: Haskell functions as CL/Scheme macros Message-ID: <7eb8ac3e.0202151440.44b67bcb@posting.google.com> Status: OR CL or Scheme macros turn out rather similar to Haskell functions. Macro-expansion is performed in the normal order, that is, in a non-strict fashion. This makes the macros closely resemble Haskell functions. However, to really emulate the run-time behavior of Haskell as CL macros we need a way to force a computation when the value is required. Fortunately, CL and some versions of Scheme offer a 'macroexpand' form. The latter serves as a 'strictness' annotation. The examples of lazy computation on infinite lists below run on a Scheme system SCM. Although it is a Scheme implementation, its macro system is identical to that of CL. It is straightforward to re-write the examples in CL. Let's start with a simple example of an infinite list: ; Haskell: ones = 1:ones (defmacro ones () '(1 . (ones))) ; Haskell: ; take 0 _ = [] ; take _ [] = [] ; take n (x:xs) | n>0 = x : take (n-1) xs ; SCM: (defmacro take (n lst) (cond ((zero? n) '()) ((null? lst) '()) (else (let ((lst (macroexpand lst))) (cons (car lst) `(take ,(- n 1) ,(cdr lst))))))) The translation is straightforward. To see how it works, we need a strict function that actually prints something. Consider the following printl-strict macro an analogue of a Haskell show function for lists. (defmacro printl-strict (lst) (let loop ((lst lst) (result '())) (let ((lst (macroexpand lst))) (if (null? lst) `(begin #f ,@(reverse result)) (loop (cdr lst) (cons `(begin (display ,(car lst)) (newline)) result)))))) ==> (printl-strict (take 2 (ones))) prints 1 1 as expected. To see what really goes on, we can do ==> (macroexpand '(printl-strict (take 2 (ones)))) which yields (begin #f (begin (display 1) (newline)) (begin (display 1) (newline))) That was easy. Let's try Fibonacci numbers: ; Haskell: fibs = 1:1:(zipWith (+) fibs (tail fibs)) First, we need to define add, tail and zipWith macros: (defmacro tail (lst) (cdr (macroexpand lst))) (defmacro add (a b) (+ (macroexpand a) (macroexpand b))) (defmacro zipWith (op lst1 lst2) (let ((lst1 (macroexpand lst1)) (lst2 (macroexpand lst2))) (cond ((null? lst1) '()) ((null? lst2) '()) (else (cons (macroexpand `(,op ,(car lst1) ,(car lst2))) `(zipWith ,op ,(cdr lst1) ,(cdr lst2))))))) Note that zipWith is a higher-order function (er, macro). Now, we can write (defmacro fibs () '(1 1 . (zipWith add (fibs) (tail (fibs))))) As you see, the code looks identical to its Haskell equivalent modulo parentheses and some syntax. ==> (printl-strict (take 7 (fibs))) 1 1 2 3 5 8 13 ;Evaluation took 7 mSec (0 in gc) 476 cells work, 1638 env, 33 bytes other Which is expected. The computation is performed at macro-expand time. Expression (printl-strict (take 7 (fibs))) macro-expands into code (begin #f (begin (display 1) (newline)) (begin (display 1) (newline)) (begin (display 2) (newline)) (begin (display 3) (newline)) (begin (display 5) (newline)) (begin (display 8) (newline)) (begin (display 13) (newline))) which is then evaluated by the SCM. P.S. Anonymous functions are more challenging to implement in this framework. CPS approach is more beneficial in this respect, see http://pobox.com/~oleg/ftp/Computation/rewriting-rule-lambda.txt