[plt-scheme] Getting Serious with Learning Macros

From: Doug Williams (m.douglas.williams at gmail.com)
Date: Wed Sep 16 11:58:25 EDT 2009

I'm finally getting serious about using complex macros for (properly)
parsing and processing domain specific languages in PLT Scheme. To date, I
have just been using syntax-rules to do the minimum parsing needed to break
out the basic elements of a construct and generate code that passes them to
the code that does the real work at run-time. This is relatively easy to
write, but pretty much limits error messages to 'bad syntax', which isn't
real useful. But, I haven't found any really good tutorial material to help
me get started.

So first, can anyone point me to some good material to get started with
syntax-case, define-for-syntax, and so on for doing this right? I've gotten
started by looking at things like package.ss (in the scheme collection) that
have some complex macros.

An example of what I would like to do is the define-rule macro in the
inference collection.

Here is a contrived example of a forward-chaining rule:

(define-rule (test-rule-1 test-rule)
    (class1 ?a b c)
    ?class2 <- (class2 ?a b c)
    (or (and (class3 ?a b c)
             (class4 ?a b c))
        (class5 ?a b c))
    (retract ?class2)
    (printf "a = ~s~n" ?a))

And, here is an example of a backward-chaining rule:

(define-rule (example-rule ancestor-rules)
    (ancestor ?x >y)
    (ancestor ?x ?z)
    (ancestor ?z ?y))

In the current (not so good) implementation, the define-rule macro just
breaks the rule clauses into goal clauses, pattern clauses, and action
expressions using <== and >== as delimiters. Then, it just passes those raw
chunks in the run-time code to actually parse and process them.

I would like to do is to do all of the parsing and checking at expansion
time and provide decent error messages. So, at expansion time, I'd like to
(1) parse out the clauses, (2) check the syntax of the goal and pattern
clauses, (3) normalize the form of the pattern clauses to (or (and .
atomic-patterns) ...), and (4) generate the appropriate code. (Note that the
action expressions are 'just code' that will be generated into a procedural
object and 'checked' that way.) I am comfortable with (1) and (4) - at least
with syntax-rules - and I have a working version using syntax-case with
error checking at that level (e.g., the rule name must be an identifier;
there can't be multiple <== or ==>; if both <== and ==> are present, they
must be in that order). I can do (2) in run-time code, but don't know how to
convert that into expansion-time code - maybe it's easy, maybe not. Finally,
(3) is some pretty complex run-time code with several mutually recursive
procedures doing the normalization. I don't even know where to start doing
this (in something other than brute force pattern matching with
syntax-rule/syntax case, but there are several dozens of cases and there has
to be a better way).

So, can someone point me in the right direction to get started? Good
examples in the current PLT Scheme code base would work.

And, just for the curious, here is a real example of a forward-chaining rule
to show what they can look like.

;;; If a cell is numbered, remove that number from any other cell in the
;;; same row, col, or box.
(define-rule (rule-5 sudoku-rules)
    (cell ?row ?col ?box ?value : (number? ?value))
    cell-1 <- (or (cell ?row-1 : (= ?row-1 ?row)
                        ?col-1 : (not (= ?col-1 ?col))
                        ?value-1 : (and (pair? ?value-1)
                                        (memv ?value ?value-1)))
                  (cell ?row-1 : (not = (= ?row-1 ?row))
                        ?col-1 : (= ?col-1 ?col)
                        ?value-1 : (and (pair? ?value-1)
                                        (memv ?value ?value-1)))
                  (cell ?row-1
                        ?box-1 : (and (= ?box-1 ?box)
                                      (or (not (= ?row-1 ?row)
                                          (not (= ?col-1 ?col))))
                        ?value-1 : (and (pair? ?value-1)
                                        (memv ?value ?value-1))))
    (replace ?cell-1 `(cell ,?row-1 ,?col-1 ,?box-1 ,(delete ?value

As always, thanks in advance for any advice, directions, mentoring, ...
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20090916/307f8234/attachment.html>

Posted on the users mailing list.