Q tutorial

Q (a functional PL based on term rewriting) has been mentioned on LtU a few times before, so I thought I should point out that there is a new tutorial available, which is supposed to provide a quick and informal introduction to the language.

From the preface: "In a nutshell, Q is a kind of functional programming language with a syntax similar to Miranda and Haskell, but with general term rewriting instead of the lambda calculus as the underlying computational model. [...] Q has some fairly unique features, in particular its user-definable special forms and algebraic types with inheritance, which makes it a somewhat exotic but powerful member of the FP language zoo."

You can download the tutorial here (PDF): Q in a Nutshell

More information about Q can be found here: http://q-lang.sf.net/

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.


Just as I was getting interested in term rewriting systems.

I've found Term Rewriting Systems (1992) - Klop and Rewrite Systems (1990) - Dershowitz & Jouannaud. Are there other good papers on this subject?

Rewriting literature

Are there other good papers on this subject?

Lots. This is a fairly mature field, and there are many different topics revolving around, e.g., equational theorem proving, confluence, termination and complexity and the use of rewriting in the implementation of FPLs. What I find so nice about rewriting is that it has both a well-developed theory and important applications.

To get started, I'd recommend having a look at the pages of the IFIP Rewriting Group and the website of the Rewriting Techniques and Application conference. If nothing else, you can find a lot of pointers to the literature there. And then there's the book Term Rewriting and All That by Baader and Nipkow.

Keep up posted on what you

Keep up posted on what you find.

Clean & term graph rewriting

The semantics of Clean was given in terms of term graph rewriting, and the Concurrent Clean language has some tool support. Check out Graph Rewriting Semantics for Functional Programming Languages. Detlef Plump's habilitation thesis, Computing by Graph Rewriting, gives a thorough overview of the area as of 1999, although unfortunately it is not available electronically; likewise his entry in the Handbook of Graph Grammars.

Plump's handbook article available

Detlef Plump, 1999. Term Graph Rewriting. In vol 2 of Handbook of Graph Grammars and Computing by Graph Transformation, pages 3-61. World-Scientific.

Q sounds a lot like Wm

Q sounds a lot like Wm Leler's language Bertrand. His thesis was published as the book Constraint Programming Languages which is an extremely readable introduction to term-rewriting systems.

I was a bit surprised not to find it in the Q tutorial's bibliography.



Yes, I remember coming across Wm Leler's website a few years ago. The lack of mentioning Bertrand is due to the fact that unfortunately I know next to nothing about it; there seems to be no real information about Bertrand on the web, the software doesn't appear to be available anywhere (the download link at Leler's page is dead), and the book is out of print and hard to find over here.

Do you have some more information about Bertrand and maybe a sample program that you could share? I'd really be interested in that.

Here's a Bertrand program

Here's a Bertrand program that solves an electrical circuit:

resistance'linear resistor {
voltagein: aNumber;
voltageout: aNumber;
current: aNumber;
voltagein - voltageout = current × resistance
} 'eob

voltage'linear battery {
voltagein: anumber;
voltageout: aNumber;
current: aNumber;
-voltage = voltagein - voltageout
} 'eob

a'eob series b'eob {
a.current = b.current &
a.voltageout = b.voltagein

n kilo { 1000 × n }
n volt { n }
n ohm { n }
ground { 0 }

main {
b1: 10 volt battery;
r1: 100 ohm resistor;
r2: 100 ohm resistor;

b1 series r1;
b1 series r2;
b2 series b1;
b1.voltagein = ground;

note the 'foo type guards (he uses the same word, guards!) on terms, and definitions that construct equations. this uses a simple equation solver prelude (which is where the 'linear comes from) but there's nothing in the language about electronics.

Unfortunately, Leler didn't follow up on Bertrand after the book, (as his website shows!) and nobody else did either. Q is pretty much the heir apparent. Leler had some very promising results, mostly with constraint-based graphics -- it'd be neat to see someone try that from Q.


Thanks. I must see that I

Thanks. I must see that I get that book somewhere...

I did find one other

I did find one other Bertrand-related thing on the web -- it's the reference implementation of the interpreter in Scheme here, as given in appendix C of Constraint Programming Languages.



I was just pointed to this discussion. Bertrand was recently resurrected. I updated the code, fixed some bugs, added a few more examples, and updated the documentation. See the Bertrand Constraint Google Group at http://groups.google.com/group/bertrand-constraint

You still probably need a copy of the book to use Bertrand; Amazon still has copies at http://www.amazon.com/gp/offer-listing/0201062437. If someone has a suggestion on getting the book scanned in so anyone can access it for free, let me know (I've tried Google Books). Unfortunately, I don't have an electronic version, or I'd post it myself.

I've been thinking about reimplementing Bertrand, coincidentally in Pure. Unfortunately, nobody is paying me to do this, so I'm doing it in my spare time for fun (so it might take a while). Trying to figure out if it would be better to implement a version of Bertrand as a thin layer on top of Pure. If anyone is interested in helping with something like this, let me know!

Wm Leler

Bertrand and Pure

Thanks Wm, I was just about to post an update to this old thread. :)

Since Wm mentioned it, let me also add a remark about Pure. Since April 2008 I've been working on Q's successor, which now uses LLVM as its backend to compile term rewriting systems to fast native code, and adds some more FP goodies that Q didn't have, like lexical closures. Information about Pure and the sources can be found at the Pure website. (I'll probably do a separate announcement when Pure 1.0 comes out, which should be Real Soon Now.)