Study #9 Metaprogramming and S-expressions in Qi: rewrite engines and
partial evaluation
This post corresponds to Study #9 in the Qi study series. You can
read it online at
www.lambdassociates.org/studies/study09.htm
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)
or
(define foo
(cons a ()) -> b)
or
(define foo
(cons a NIL) -> b)
or even
(define foo
(list a) -> 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
(get-prop <function> qi::source_code [])
will do the trick. If there is no definition then [] will be
returned.
Here are two examples of the use of these facilities. This study is
also a post so I'm going to keep these short and sweet.
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))))
(get-prop power qi::source_code []) 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 all 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