Term rewriting. It looks to be powerful!

August 5, 2007 Pivotal Labs

This weekend I discovered the Q language. Check this out: Into a file called sq.q I type:

sq X = X * X;
X+(Y+Z) = (X+Y)+Z; X*(Y*Z) = (X*Y)*Z;
X*(Y+Z) = X*Y+X*Z; (X+Y)*Z = X*Z+Y*Z;

This is the definition of square, followed by the laws for distributivity and associativity as they could be copied directly out of a textbook. Then I evaluate this file in the Q VM-based interpreter, whose speed apparently rivals that of the Glasgow Haskell Compiler or CLISP:

q sq.q

In the interepretter window I then type a term, and using my rules Q reduces it to normal form:

==> sq (A+B)
A*A+B*A+A*B+B*B

I am pretty sure this language is going to unleash an unreal amount of metaprogramming power. Term rewriting is a genius idea.

About the Author

Biography

More Content by Pivotal Labs
Previous
Cacheable Flash
Cacheable Flash

Page caching is an easy way to get massive performance and scalability increases with little up front effor...

Next
Lovely Demeter, Meter Maid
Lovely Demeter, Meter Maid

Wes and Parker pointed us to this article: Misunderstanding the Law of Demeter by Dan Manges which ...