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