Metaprogramming

Metaprogramming and S-expressions:
rewrite engines and partial evaluation

One misapprehension about Qi is that it does not or cannot use S-expression syntax and hence, unlike Lisp, Qi is not a good metaprogramming language. It seems a good time to lay this to rest. Qi is a very powerful metaprogramming language. Qi does have S-expression syntax, although as user you don't generally use it. So

(define foo
[a] -> b)

is short for

(define foo
(cons a []) -> b)

for

(define foo
(cons a ()) -> b)

(define foo
(cons a NIL) -> b)

You get the idea. You can write Qi in a 'Lispy' syntax.

If you want to see your Qi program in S-expression syntax you can do it by reading your program file through the Qi reader without loading the file. The 1-place Qi function read-file does that - it reads the file through the Qi reader and converts it to Lispy form. Try (read-file "Put your Qi file name here") to see this.

If you want to see the Lisp function corresponding to your Qi function then (ps <function>) will do the trick. If there is no definition then [] will be returned.

Here are two examples of the use of these facilities.

Example 1 Generating a Rewrite Engine from a Confluent and Terminating Set of Equations

Lets assume that you've generated a confluent and terminating set of equations from a Knuth-Bendix program and you want to turn your set E of equations into a rewrite engine. We'll assume that the equations are represented as two element lists; so [a b] represents the equation a = b. This program will do it.

(define make-rewrite-engine
E -> [define rewrite | (append (mapcan make-rewrite-rule E) (default))])

(define mapcan
_ [] -> []
F [X | Y] -> (append (F X) (mapcan F Y)))

(define make-rewrite-rule
[X Y] -> [(cons-form X) -> [rewrite (cons-form Y)]])

(define cons-form
[X | Y] -> [cons (cons-form X) (cons-form Y)]
X -> X)

(define default
-> [[cons X Y] -> [map rewrite [cons X Y]]
X -> X])

So if I try this

(make-rewrite-engine [[a b] [b c]])

I get

[define rewrite
a -> [rewrite b]
b -> [rewrite c]
[cons X Y] -> [map rewrite [cons X Y]]
[X -> X]]

Ok so far; however this is just a list, not a function. But Qi has its own version of eval which works like this.

The normal form of (eval e) is the normal form of e* where e* results from e by the uniform substitution of round brackets for square ones.

e.g. (eval [+ 2 3]) = (+ 2 3) = 5

So to generate the function we make one small change.

(define make-rewrite-engine
E -> (eval [define rewrite | (append (mapcan make-rewrite-rule E) (default))]))

we define a function normalise that rewrites an input to a fixpoint (fix is a higher-order Qi function that does that)

(define normalise
X -> (fix rewrite X))

and our top level that tests for equality w.r.t. the equations.

(define equal?
X Y -> (= (normalise X) (normalise Y)))

Quick test

(77-) (equal? [f a] [f b])
true

Example 2: Partial Evaluation

Lisp is a great language for doing partial evaluation because unfolding is so simple; effectively unfolding is a kind of beta-reduction using the lambda body of the defined function. Because Lisp is so simple syntactically, its a lovely (object) language to reason about.

But it does not follow that it is necessarily the best (meta) language to reason with. Partial evaluation is a case in point. It is very useful to have pattern-matching when reasoning over Lisp functions. Using Qi as the metalanguage and Lisp as the object language gives you the best of both worlds.

Ok, lets have an example. We define power in Qi.

(define power
_ 0 -> 1
X Y -> (* X (power X (- Y 1))))

(ps power) gives

[DEFUN power [V16 V17]
[COND [[EQL 0 V17] 1] [T [THE NUMBER [* V16 [power V16 [1- V17]]]]]]]

We want to partially evaluate [power X 3] where the variable X signifies the unknown.

My partial evaluator is greatly simplified because the purpose of this piece is to show you how to do it and not to do it myself (which would take up too much space and take away your fun). Here it is.

(define partially-evaluate
[X | Y] -> (let Z (simplify (unfold [X | Y]))
(if (= [X | Y] Z)
(map partially-evaluate Z)
(partially-evaluate Z)))
X -> X)

Unfolding uses the Lisp definition.

(define unfold
[F | X] -> (let Body (lambda-body (def F))
(if (empty? Body)
[F | X]
(beta-reduce Body X)))
X -> X)

def gets the definition;

(define def
F -> (get-prop F qi::source_code []))

(define lambda-body
[] -> []
[Defun F Params Body] -> [lambda Params Body])

Here is a lazy man's beta reduction which ignores variable clashes

(define beta-reduce
[lambda [] Body] [] -> Body
[lambda [V | Vs] Body] [X | Y] -> (beta-reduce [lambda Vs (subst X V Body)] Y))

simplify is not too hard - the only thing to note is that Lisp-in-Qi uses uppercase for all the Lisp system functions and Qi uses uppercase for variables (except NIL which is still the empty list). So if we write a function test-cond that returns true if the input is COND like this

(define test-cond
COND -> true
_ -> false)

it will not work - it will return 'true' for every input. The correct way is.

(define test-cond
X -> true where (= X COND)
_ - > false)

Once that's clear the rest is easy.

(define simplify
[Cond [NIL _] | Code] -> [Cond | Code] where (= Cond COND)
[Cond [True X] | _] -> X where (and (= Cond COND) (= True T))
[Eql X X] -> T where (= EQL Eql)
[Eql X Y] -> NIL where (and (number? X) (number? Y))
[1- X] -> (- X 1) where (number? X)
[* X 1] -> X
[X | Y] -> (map simplify [X | Y])
X -> X)

So if I type in

(partially-evaluate [power X 3])

I get

[THE NUMBER [* X [THE NUMBER [* X [THE NUMBER X]]]]]

which is correct.

Mark