newby macro question

48 views
Skip to first unread message

yyc...@gmail.com

unread,
May 31, 2007, 3:31:30 AM5/31/07
to
Hello,

I'm learning macro by implementing simple list comprehension based on
Philip Wadler's transformation rules(the unoptimized ones for
simplicity). . The problem is, my program always returns the properly
converted s-expression instead of executing it. Below is my code. When
I tested it, I always got S-expression back. For example, if my test
case is (list-of x (x <- '(1 2 3 4)) (> x 2)), then I will get back
(map (lambda (x) (list-of x (> x 2))) '(1 2 3 4)), instead of the
result of *executing* the returned expression. I guess this is because
Scheme interprets that the quasiquoted expressions are returned result
instead of part of the transformation. Therefore, I also tried
removing quasiquotes, and simply using normal evaluation. However, by
doing that I couldn't get it work. Any suggestions? Thanks a bunch!


(define (generator? expr)
(eq? (cadr expr) '<-))

(define (gen-var expr)
(car expr))

(define (gen-list expr)
(caddr expr))

(define-syntax list-of
(syntax-rules ()
((_ e . rules)
(if (null? 'rules) e
(let ((rule (car 'rules))
(remaining (cdr 'rules)))
(cond
((not (generator? rule)) `(if ,rule (list-of
e ,@remaining)))
(else
(let ((var (gen-var rule))
(data (gen-list rule)))
`(map (lambda (,var) (list-of
e ,@remaining)) ,data)))))))))

The transformation rules I used are:
(a) TE[[E | v<- L: Q]] = map (lambda (v). TE[[E | Q]]) TE[L]
(b) TE[[E|B; Q]] = if TE[B] TE[[E|Q]] NIL
(c) TE[ [e |]] = Cons TE[E] NIL

DETm...@gmx.de

unread,
May 31, 2007, 7:46:43 AM5/31/07
to
Hi

> I'm learning macro by implementing simple list comprehension based on
> Philip Wadler's transformation rules(the unoptimized ones for
> simplicity).

You should mention the source where you got those rules from:
http://research.microsoft.com/~simonpj/papers/slpj-book-1987/index.htm

> The problem is, my program always returns the properly
> converted s-expression instead of executing it. Below is my code. When
> I tested it, I always got S-expression back. For example, if my test
> case is (list-of x (x <- '(1 2 3 4)) (> x 2)), then I will get back
> (map (lambda (x) (list-of x (> x 2))) '(1 2 3 4)), instead of the
> result of *executing* the returned expression. I guess this is because
> Scheme interprets that the quasiquoted expressions are returned result
> instead of part of the transformation.

Syntax-rules is not a computational macro-system, but rewrite rule
based (basically it does the thing you try to do, but automatic).

So with your macro:

(list-of e . rules)

is expanded into

(if (null? 'rules) e
(let ((rule (car 'rules))
(remaining (cdr 'rules)))
(cond

[...])))

which is then run and computes the s-expression. If you want an
computational macro system you should search for one of '(syntax-case
explicit-renaming-macros syntactic-closures define-macro). Mote that
these are not in the current scheme standard (but syntax-case might be
in the next). Common Lisps defmacro also falls into the class of
computational macro systems.

> Therefore, I also tried
> removing quasiquotes, and simply using normal evaluation. However, by
> doing that I couldn't get it work. Any suggestions? Thanks a bunch!

All the quoting and unquoting is allready done by syntax-rules in an
automated fashion, so you dont have to :)

You should also note that wadler does not use map but flat-map, which
is NOT the same as schemes map.

=== SPOILER ===

i have posted a version of list-of implemented with syntax-rules at:
http://paste.lisp.org/display/42060


Phil Bewig

unread,
May 31, 2007, 8:54:32 AM5/31/07
to
(define-syntax list-of
(syntax-rules (in is)
((_ 'aux expr base) (cons expr base))
((_ 'aux expr base (x in xs) clauses ...)
(let loop ((z xs))
(if (null? z)
base
(let ((x (car z)))
(list-of 'aux expr (loop (cdr z)) clauses ...)))))
((_ 'aux expr base (x is y) clauses ...)
(let ((x y))
(list-of 'aux expr base clauses ...)))
((_ 'aux expr base pred? clauses ...)
(if pred?
(list-of 'aux expr base clauses ...)
base))
((_ expr clauses ...)
(list-of 'aux expr '() clauses ...))))

(list-of (+ y 6) (x in '(1 2 3 4 5)) (odd? x) (y is (* x x))) => (7 15
31)

Joe Marshall

unread,
May 31, 2007, 5:49:36 PM5/31/07
to

This will fail in odd ways:

(list-of (add1 y) (x in '(1 2 3 4 5)) (odd? x) (y is (* x x)))
. reference to undefined identifier: x


Jens Axel Søgaard

unread,
May 31, 2007, 7:08:06 PM5/31/07
to
> I'm learning macro by implementing simple list comprehension based on
> Philip Wadler's transformation rules(the unoptimized ones for
> simplicity). . The problem is, my program always returns the properly
> converted s-expression instead of executing it. Below is my code. When
> I tested it, I always got S-expression back. For example, if my test
> case is (list-of x (x <- '(1 2 3 4)) (> x 2)), then I will get back
> (map (lambda (x) (list-of x (> x 2))) '(1 2 3 4)), instead of the
> result of *executing* the returned expression. I guess this is because
> Scheme interprets that the quasiquoted expressions are returned result
> instead of part of the transformation. Therefore, I also tried
> removing quasiquotes, and simply using normal evaluation. However, by
> doing that I couldn't get it work. Any suggestions? Thanks a bunch!

As the others write syntax-rules can't do arbitrary computations.
Despair not - syntax-case can. Here is a syntax-case version
written by turning

' into #'
` into #`
,@ into #,@

and then inserting syntax->list everywhere you car, cdr, null?
and friends to examine the syntax.

The snippet is *not* in good style, but it shows how to
use syntax-case in the "define-macro" style.

(begin-for-syntax
(define (generator? expr)
(eq? (cadr (syntax-object->datum expr)) '<-))

(define (gen-var expr)
(car (syntax->list expr)))

(define (gen-list expr)
(caddr (syntax->list expr))))

(define-syntax (list-of stx)
(syntax-case stx ()
((_ e . rules)
(let ([rules (syntax->list #'rules)])
(if (null? rules)
#'e


(let ((rule (car rules))
(remaining (cdr rules)))
(cond
((not (generator? rule))

#`(if #,rule (list-of e #,@remaining)))


(else
(let ((var (gen-var rule))
(data (gen-list rule)))

#`(map (lambda (#,var)
(list-of e #,@remaining)) #,data))))))))))

Welcome to DrScheme, version 370.2-svn29may2007 [3m].
Language: Pretty Big (includes MrEd and Advanced Student); memory limit:
900 megabytes.


> (list-of x
(x <- '(1 2 3 4))
(> x 2))

(#<void> #<void> 3 4)

--
Jens Axel Søgaard

Phil Bewig

unread,
Jun 1, 2007, 2:30:13 PM6/1/07
to


Maybe someday I will reach macro nirvana. But not today. This one
works. Thanks, Joe.

Reply all
Reply to author
Forward
0 new messages