Retaining state in a recursive macro
leppie
What is the best way to retain a state between recursive macro calls?
Lets say I have something like this (state will be maintained in s, ignore
the output):
(define-syntax foo
(let ((s '()))
(lambda (x)
(syntax-case x (bar)
[(foo l bar)
(let ((r #'(something)))
(set! s '()) ; reset
r)]
[(foo l rest ... bar)
(begin
(set! s (cons 'a s)) ; modify
#'(foo (something) rest ... bar))]
))))
Now that works, but obviously is a no go in a mutlithreaded environment.
(you can see a runnable (on R6RS and Chez) version of the 'pseudo' code at
http://xacc.wordpress.com/2008/04/15/linq-for-r6rs-scheme-take-6/)
cheers
leppie
jos koot
Is this what you want?
(define-syntax foo
(lambda (x)
(letrec
((s '())
(trafo
(lambda (x)
(syntax-case x (bar)
[(l bar)
(let ((r #'(something)))
(set! s '()) ; reset
r)]
[(l rest ... bar)
(begin
(set! s (cons 'a s)) ; modify
(trafo #'((something) rest ... bar)))]))))
(syntax-case x () ((foo . rest) (trafo #'rest))))))
Jos
leppie
Thanks, that seems to work, now to figure out the details :)
Cheers
leppie
leppie
Thanks again, it works great. It does 'uglify' the macro a bit :(
You can view the result here - http://xacc.wordpress.com/2008/04/16/linq-for-r6rs-scheme-take-7/
Cheers
leppie
Abdulaziz Ghuloum
> On Apr 16, 9:39 am, jos koot <jos.k...@telefonica.net> wrote:
>> Is this what you want?
>
> Thanks again, it works great. It does 'uglify' the macro a bit :(
Why do you need the set! anyways? I may not fully understand what
you're trying to do but it seems to me that you're being just lazy:
instead of parsing the expression in one go, you're breaking the
problem into steps and use set! to pass the data. This will cause
you more trouble than it's worth (and it already is doing that).
So, can you solve it without set!? Also, did you need all these
syntax->datum and datum->syntax in that macro? I don't see why
they were needed from the usage example.
Aziz,,,
leppie
wrote:
> Why do you need the set! anyways? I may not fully understand what
> you're trying to do but it seems to me that you're being just lazy:
> instead of parsing the expression in one go, you're breaking the
> problem into steps and use set! to pass the data. This will cause
> you more trouble than it's worth (and it already is doing that).
>
> So, can you solve it without set!? Also, did you need all these
> syntax->datum and datum->syntax in that macro? I don't see why
> they were needed from the usage example.
>
The set! is just needed to accumulate a list of identifiers introduced
in the query, these identifiers need to be available in any subsequent
'clause' in the macro. I am not sure how I would do it without set!.
Suggestions or pointers welcome :)
I think I can maybe get rid of some of the syntax<->datum conversions
though. I am still very much a macro noob :p
Cheers
leppie
Abdulaziz Ghuloum
> The set! is just needed to accumulate a list of identifiers introduced
> in the query, these identifiers need to be available in any subsequent
> 'clause' in the macro. I am not sure how I would do it without set!.
> Suggestions or pointers welcome :)
You can accumulate them in the output of the macro (where the output
is a call to another macro that expects the accumulated variables).
For example, how would you write a flatten macro such that
(flatten (a (b (c)) . d)) expands to (a b c d)
using syntax-rules? You use an accumulator.
(define-syntax flatten-aux
(syntax-rules ()
[(_ () () ac) ac]
[(_ () (x . y) ac) (flatten-aux y x ac)]
[(_ (x . y) q ac) (flatten-aux y (q . x) ac)]
[(_ x q ac) (flatten-aux () q (x . ac))]))
(define-syntax flatten
(syntax-rules ()
[(_ something) (flatten-aux something () ())]))
But anyways, as I said, I don't think you need any of this since it
seems that you should be able to parse the form directly.
Aziz,,,
leppie
wrote:
Thanks
What do you mean by parsing it directly? Do you mean I should not have
to resort to a recursive application of the macro?
Something like the case or cond macro in the R6RS Library spec (http://
www.r6rs.org/final/html/r6rs-lib/r6rs-lib-Z-H-1.html#node_toc_node_sec_12.8)
?
Cheers
leppie
Abdulaziz Ghuloum
> What do you mean by parsing it directly? Do you mean I should not have
> to resort to a recursive application of the macro?
> Something like the case or cond macro in the R6RS Library spec (http://
> www.r6rs.org/final/html/r6rs-lib/r6rs-lib-Z-H-1.html#node_toc_node_sec_12.8)
> ?
That's what I meant, yes. But given that I don't know what this
LINQ thing is, I might be mistaken.
Aziz,,,
leppie
news:fu54n8$13f$1...@aioe.org...
Thanks, I will try it that way (if possible!).
LINQ is Microsoft based query language built into their C# 3.0 compiler.
LINQ stands for Language INtegrated Query (see more @
http://msdn2.microsoft.com/en-za/library/bb397896(en-us).aspx). It is meant
to be similar to SQL (IMO it's a lot better than making SQL strings!). My
macro is simply based on the same syntax. LINQ itself creates a query
expression from a LINQ statement, that is not actually executed until
iterated.
I am hoping to use the Streams SRFI to allow for something similar, maybe
'pluggable' functions for map, filter and sort.
Thanks again
Cheers
leppie
Abdulaziz Ghuloum
> LINQ is Microsoft based query language built into their C# 3.0 compiler.
> LINQ stands for Language INtegrated Query (see more @
> http://msdn2.microsoft.com/en-za/library/bb397896(en-us).aspx). It is
> meant to be similar to SQL (IMO it's a lot better than making SQL
> strings!). My macro is simply based on the same syntax. LINQ itself
> creates a query expression from a LINQ statement, that is not actually
> executed until iterated.
It will be easier for you and everybody if you'd just write down the
language grammar that the macro accepts. I can see you've written an
example:
(define al ‘((a 4) (d 3) (a 2) (c 9) (a 11)))
(write
[
from y in al
let a = (car y) ; the symbol
let b = (cadr y) ; the number
let c = y ; alias
orderby b asc
where (and (eq? a 'a) (even? b))
from x in c
let d = x
select d
])
(newline) ;=> (a 2 a 4)
Rules:
- No duplicate identifiers
- from and let requires an unique identifier
- you can use normal expressions in the latter parts of from and let, as
well as select, where and orderby
Maybe if you'd expand that a little, giving the full grammar as well as
a brief description of what the from macro does, it would be useful for
everybody.
Aziz,,,
leppie
> Maybe if you'd expand that a little, giving the full grammar as well as
> a brief description of what the from macro does, it would be useful for
> everybody.
Here is the basic grammar (what I implement so far):
id => any scheme identifier
expr => any scheme expression
query => from_clause query_clauses* select_clause
from_clause => 'from' id 'in' expr
query_clause => 'where' expr
| 'orderby' expr ( 'asc' | 'desc' )?
| 'let' id '=' expr
| from_clause
select_clause => 'select' expr
Explanations/examples (braces omitted from 'from expressions'):
from x in '(1 2 3 4)
select x
translates to
(map (lambda (x) x) '(1 2 3 4)) => (1 2 3 4)
(ignore the fact that this is no-op for now)
So in from, the id determines the variable introduced, and expr is a list.
from x in '(1 2 3 4)
where (even? x)
select x
translates to
(filter (lambda (x) (even? x)) '(1 2 3 4)) => (2 4)
So in where the expr is a predicate.
from x in '(1 2 3 4)
orderby (- x)
select x
translates to something like
(sort (lambda (x) (- x)) '(1 2 3 4)) => (4 3 2 1)
So in orderby the expr is value to be sorted against.
from x in '(1 2 3 4)
let y = (* x x)
select y
translates to
(map
(lambda (x)
(apply
(lambda (y x) y) x))
(map
(lambda (x)
(list (* x x) x))
'(1 2 3 4))) => (1 4 9 25)
So in let the id introduces a new variable into the lexical scope, and get
assigned the value of expr.
from x in '((a 1) (b 2))
from y in x
select y
translates to
(flatten (from x in '((a 1) (b 2))
select
(from y in x
select y))) => (a 1 b 2)
So in from the id introduces a new variable into the lexical scope and expr
is a list, and the result it flattened one level.
More complex example:
As per the grammar you can chain an infinite amount of query clauses, hence
you can combine them to from something like the following example.
from y in '((a 4) (d 3) (a 2) (c 9) (a 11))
let a = (car y) ; the symbol
let b = (cadr y) ; the number
orderby b asc
where (and (eq? a 'a) (even? b)) ; filter
from x in c
let d = x
select d
=>
(a 2 a 4)
It is quite easy if you just read the expression from the start. It is just
iteration and manipulation of a list.
It runs on any R6RS Scheme and Petite Chez too.
My implementation is by no means optimized (I will leave that for later).
Hope this explains a bit better :)
Cheers
leppie
Tzvetan Mikov
> "Abdulaziz Ghuloum" <aghul...@cee.ess.indiana.edu> wrote in message
>
> news:fu57kd$i5d$1...@aioe.org...
>
> > Maybe if you'd expand that a little, giving the full grammar as well as
> > a brief description of what the from macro does, it would be useful for
> > everybody.
>
> Here is the basic grammar (what I implement so far):
>
> id => any scheme identifier
> expr => any scheme expression
>
> query => from_clause query_clauses* select_clause
>
> from_clause => 'from' id 'in' expr
> query_clause => 'where' expr
> | 'orderby' expr ( 'asc' | 'desc' )?
> | 'let' id '=' expr
> | from_clause
> select_clause => 'select' expr
I am very new, so I might be way off base, but wouldn't Lisp-style
macros be much better suited to this kind of transformation ?
regards,
Tzvetan
leppie
> I am very new, so I might be way off base, but wouldn't Lisp-style
> macros be much better suited to this kind of transformation ?
I am not sure myself, but I think that 'select expr' at the end of the
list might cause some trouble.
Cheers
leppie
andreu...@yahoo.com
> What is the best way to retain a state between recursive macro calls?
>
> (define-syntax foo
> (let ((s '()))
> (lambda (x) .....
This technique would also be problematic in interactive systems
if a syntax error occurs, since you only remove the accumulated state
upon successful completion of the parsing. If the parsing does not
complete, the next time you try to use the macro, you will get
nonsense.
As Aziz noted, it is better to parse the whole thing in one go.
Yes, the syntax-case COND example is a good one to follow.
Do not do the syntax->datum conversions. Keep identifiers as
identifiers and compare them using bound-identifier=? instead
of id=?.
Your macro has an occurrence of CONS with just one argument.
Andre
leppie
news:08a74023-1c4b-4d2d...@x41g2000hsb.googlegroups.com...
> This technique would also be problematic in interactive systems
> if a syntax error occurs, since you only remove the accumulated state
> upon successful completion of the parsing. If the parsing does not
> complete, the next time you try to use the macro, you will get
> nonsense.
I will keep that in mind.
> As Aziz noted, it is better to parse the whole thing in one go.
> Yes, the syntax-case COND example is a good one to follow.
Scary, if you ask me :) But I will try decipher it.
>
> Do not do the syntax->datum conversions. Keep identifiers as
> identifiers and compare them using bound-identifier=? instead
> of id=?.
I have changed my code to do exactly that yesterday :)
>
> Your macro has an occurrence of CONS with just one argument.
>
I noticed that too, and fixed it, was meant to be list.
Thanks
leppie
andreu...@yahoo.com
> <andreuri2...@yahoo.com> wrote in message
>
> > As Aziz noted, it is better to parse the whole thing in one go.
> > Yes, the syntax-case COND example is a good one to follow.
>
> Scary, if you ask me :) But I will try decipher it.
No, no. It is a simple transformation. Just convert your
recursive macro into a procedure. For example, instead of
(define-syntax foo
(let ((s '()))
(lambda (x)
(syntax-case x (bar)
[(foo l bar)
(let ((r #'(something)))
(set! s '()) ; reset
r)]
[(foo l rest ... bar)
(begin
(set! s (cons 'a s)) ; modify
#'(foo (something) rest ... bar))]
))))
you just do:
(define-syntax foo
(lambda (x)
(let recur ((s '())
(x x))
(syntax-case x (bar)
[(foo l bar)
#'(something)]
[(foo l rest ... bar)
(recur (cons 'a s)
#'(foo (something) rest ... bar))]))))
Andre
leppie
news:0ba8de06-e26e-4cc0...@2g2000hsn.googlegroups.com...
> (define-syntax foo
> (lambda (x)
> (let recur ((s '())
> (x x))
> (syntax-case x (bar)
> [(foo l bar)
> #'(something)]
> [(foo l rest ... bar)
> (recur (cons 'a s)
> #'(foo (something) rest ... bar))]))))
I have definitely been doing too much procedural programming :)
A named let is a particular one that my mind just cant read naturally, but
after looking at the example for while, it is starting to come to me.
Cheers
leppie
leppie
> No, no. It is a simple transformation. Just convert your
> recursive macro into a procedure.
I think I got it now :)
Here is what I came up with:
(define-syntax from
(lambda (x)
(define valid-id?
(lambda (e vars)
(and (identifier? e)
(not (memp
(lambda (x)
(bound-identifier=? e x))
vars)))))
(define id=?
(lambda (e o)
(eq? (syntax->datum e) o)))
(syntax-case x (in)
[(_ e in l rest rest* ...)
(identifier? #'e)
(let recur ((vars (list #'e))
(l #'l)
(x #'(rest rest* ...)))
(syntax-case x (where let = in select from orderby)
[(select s)
#`(map
(lambda (K)
(let-values (((#,@vars) K)) s))
#,l)]
[(where p rest ...)
(recur
vars
#`(filter
(lambda (K)
(let-values (((#,@vars) K)) p))
#,l)
#'(rest ...))]
[(from e* in l* rest ...)
(valid-id? #'e* vars)
(recur
(cons #'e* vars)
#`(flatten
(map
(lambda (K)
(let-values (((#,@vars) K))
(map
(lambda (K*)
(values K* #,@vars))
l*)))
#,l))
#'(rest ...))]
[(let a = b rest ...)
(valid-id? #'a vars)
(recur
(cons #'a vars)
#`(map
(lambda (K)
(let-values (((#,@vars) K))
(values b #,@vars)))
#,l)
#'(rest ...))]
[(orderby p dir rest ...)
(or (id=? #'dir 'asc) (id=? #'dir 'desc))
(recur
vars
; let conflicts with normal let so just use let*
; and it will be transformed into a normal let later
#`(let* ((p*
(lambda (K)
(let-values (((#,@vars) K)) p))))
(sort #,(id=? #'dir 'asc) #,l p* p*))
#'(rest ...))]
[(orderby p rest ...)
(recur
vars
l
#'(orderby p asc rest ...))]
))])))
Abdulaziz Ghuloum
> [(select s)
> #`(map
> (lambda (K)
> (let-values (((#,@vars) K)) s))
> #,l)]
That doesn't look right from a quick scan. How can you bind
a single value K to multiple variables? Try again.
Aziz,,,
leppie
Yeah I noticed that :) (I really need to get proper continuation support in
IronScheme :( )
Anyway, here it is, again (and tested on Ikarus):
(import (rnrs))
(define (compare asc? a b)
(cond
[(and (number? a) (number? b))
((if asc? < >) a b)]
[(and (char? a) (char? b))
((if asc? char<? char>?) a b)]
[(and (string? a) (string? b))
((if asc? string<? string>?) a b)]
[(and (symbol? a) (symbol? b))
(let ((a (symbol->string a))
(b (symbol->string b)))
((if asc? string<? string>?) a b))]
[else
(assertion-violation 'compare "not supported" a b)]))
(define (sort asc? l a b)
(list-sort
(lambda (a* b*)
(compare asc? (a a*) (b b*)))
l))
(define (flatten lst)
(apply append lst))
(define-syntax bind
(syntax-rules ()
[(bind var body)
(lambda (var) body)]
[(bind vars ... body)
(lambda (K)
(apply
(lambda (vars ...) body)
K))]))
(define-syntax from
(lambda (x)
(define valid-id?
(lambda (e vars)
(and (identifier? e)
(not (memp
(lambda (x)
(bound-identifier=? e x))
vars)))))
(define id=?
(lambda (e o)
(eq? (syntax->datum e) o)))
(syntax-case x (in)
[(_ e in l rest ...)
(identifier? #'e)
(let recur ((vars (list #'e))
(l #'l)
(x* #'(rest ...)))
(syntax-case x* (where let = in select from orderby join equals
on)
[() (syntax-violation 'from "missing select" x)]
[(select s)
#`(map (bind #,@vars s) #,l)]
[(where p rest ...)
(recur vars
#`(filter (bind #,@vars p) #,l)
#'(rest ...))]
[(from e* in l* rest ...)
(if (valid-id? #'e* vars)
(recur (cons #'e* vars)
#`(flatten
(map
(bind #,@vars
(map
(lambda (K*)
(list K* #,@vars))
l*))
#,l))
#'(rest ...))
(syntax-violation 'from "not a unique identifier" #'e* x*))]
[(let a = b rest ...)
(if (valid-id? #'a vars)
(recur (cons #'a vars)
#`(map (bind #,@vars (list b #,@vars)) #,l)
#'(rest ...))
(syntax-violation 'from "not a unique identifier" #'a x*))]
[(orderby p dir rest ...)
(or (id=? #'dir 'asc) (id=? #'dir 'desc))
(recur vars
#`(let* ((p*
(bind #,@vars p)))
(sort #,(id=? #'dir 'asc) #,l p* p*))
#'(rest ...))]
[(orderby p rest ...)
(recur vars l #'(orderby p asc rest ...))]
[(join e* in l* on a equals b rest ...)
(recur vars l
#'(from e* in l* where (eqv? a b) rest ...))]
))])))
(define z '((1 2) (3 4)))
(define l '(1 2 3 4))
(write
(
from x in l
let y = x
select y
))
(newline) ;=> (1 2 3 4)
(write
(
from x in z
from a in x
let b = a
orderby (- a)
where (even? b)
select (* b a)
))
(newline) ;=> (16 4)
(write
(
from a in '(1 2 3 4 5)
let x = a
join b in '(1 2 6 4 5) on a equals b
select (list a b)
))
(newline) ;=> ((1 1) (2 2) (4 4) (5 5))
(define args (list (string->list "hello") (string->list "world")))
(display
[
from K in args
from K* in K
where (not (char=? #\l K*))
orderby K*
select K*
])
(newline) ;=> (d e h o o r w)
Abdulaziz Ghuloum
> More complex example:
>
> As per the grammar you can chain an infinite amount of query clauses,
> hence you can combine them to from something like the following example.
>
> from y in '((a 4) (d 3) (a 2) (c 9) (a 11))
> let a = (car y) ; the symbol
> let b = (cadr y) ; the number
> orderby b asc
> where (and (eq? a 'a) (even? b)) ; filter
> from x in c
> let d = x
> select d
>
> =>
>
> (a 2 a 4)
What's the c in "from x in c"?
leppie
wrote:
Oops! I think I missed copied it somehow (need to concentrate more!).
from y in '((a 4) (d 3) (a 2) (c 9) (a 11))
let a = (car y) ; the symbol
let b = (cadr y) ; the number
let c = y
orderby b
where (and (eq? a 'a) (even? b))
from x in c
let d = x
select d
Cheers
leppie
andreu...@yahoo.com
> (define id=?
> (lambda (e o)
> (eq? (syntax->datum e) o)))
You could also get rid of this and instead use
(free-identifier=? #'dir #'asc) and so on, since
you effectively are using free-identifier=? equivalence
to match all the other keywords (where let = in select
from orderby join equals on).
Andre