FAQ about the Q Programming Language and System

This FAQ is still in its infancy, so please help its development by sending in questions you would like to see answered here.

1. What is Q?

The pseudo-acronym "Q" stands for "equational". Programming in Q means that you specify an arbitrary system of equations which the interpreter uses as rewrite rules to reduce expressions to normal form. Please note that the Q interpreter is neither a computer algebra system nor an equational theorem prover (although you could use it for such purposes). Like other functional language interpreters, it is just an expression evaluator. However, using term rewriting as the basic model of computation is very powerful, and it allows you to formulate your programs in a high-level, concise and declarative style.

Q is the result of some 10 years work on a term rewriting interpreter based on my earlier research on term pattern matching. By now, Q has evolved into a general-purpose programming language with advanced symbolic processing and functional programming capabilities, multithreading support, a comprehensive standard library, and a C interface. Q scripts execute about as fast as interpreted Lisp or Haskell code. A number of C add-on modules are already available which allow you to interface to Tcl/Tk, Octave and IBM's Data Explorer, and the `clib' module gives you access to important system functions such as file and process manipulation and regular expression matching. For Linux, OS X and Windows, additional modules for doing MIDI and digital audio stuff are also available. This turns Q into a practical programming tool for a variety of application areas.

Using Q is supposed to be fairly simple: you throw together some equations, start the interpreter and then type in the expressions you wish to evaluate. All this can be done with a few keystrokes, if you use the Emacs Q mode supplied with the package. A more windowish GUI frontend for the Q interpreter is also available (screenshot).

NOTE: The problem with one-character acronyms is that the Latin alphabet does not have enough letters. ;-) There are two other programming languages named "Q" I know of. They have nothing to do with the Q language presented here. First, Per Bothner's Q was also developed around the beginning of the 1990s; apparently, it is not being maintained any more. Second, a prerelease of an OO+FP language named "Q" is available from Q Software Solutions, but it does not seem to be under active development any longer.

2. Yet another "Haskell for the poor"?

Even though the syntax and some of the stuff in the standard library looks superficially similar, Q is different in a number of ways. First, Q is an equational rather than just a functional language, meaning that it is based on general term rewriting instead of the lambda calculus (which is just one, and very special, rewriting system). For the programmer this means greater freedom in specifying the computational rules, which can be arbitrary equations instead of just function definitions. In particular, Q has no a priori distinction between "constructors" and "defined" function symbols, and argument patterns are not restricted to "constructor terms". Thus symbolic simplification rules, constructor equations and partial function definitions can all be dealt with in a direct manner.

Second, using Q's "special forms" you can define your own "meta functions" which manipulate arbitrary (not necessarily irreducible) expressions as literal terms. This gives you full control over the reduction strategy, where this is desired, as well as a simple kind of "self-modifying programs", since constructs like lambda abstractions can be analyzed, transformed and constructed in many ways before they are actually evaluated.

Third, Q takes a pragmatic approach in that it uses applicative order evaluation as its default evaluation strategy (data structures with lazy evaluation can be defined using special forms), and has dynamic typing and "impure" imperative-style I/O, very much like more traditional functional languages such as Lisp. While one may argue about these features, they certainly make life easier.

You will also notice that Q lacks most of the syntactic sugar found in Haskell. This is partly due to my laziness, but it also keeps the language and the core system simple. Using Q's symbolic processing capabilities, the usual bits like lambda abstractions, pattern matching conditionals and list comprehensions can easily be written in Q itself (although this does not offer quite the same performance as when they are provided as builtins, of course).

3. So what is it good for?

To name a few areas for which Q might be interesting:

I use Q myself for a variety of scientific and computer music applications, and even for the occasional shell script; I rarely need to go back to C/C++ or other scripting languages these days. I have also used Q in MIDI programming courses where the simplicity of the language (compared to Lisp, ML or Haskell) appears to be a big plus.

4. Where can I get it?

From the Q homepage: http://www.musikwissenschaft.uni-mainz.de/~ag/q.

5. What documentation is available?

The distribution includes a fairly comprehensive (200+ pages) language manual in texinfo format. The manual is also available online on the Q homepage in both HTML and PDF format.

6. Which platforms are supported?

FreeBSD, Linux, Mac OS X, Solaris and Windows are known to work, also, with some limitations, BeOS and Cygwin. The package should also compile with the usual amount of tweaking on most modern UNIXes. Binary packages for FreeBSD 5.1, a variety of Linux systems and 32 bit Windows systems (98/NT/2000/XP) are available.

7. What is the current status of the project?

Q has been in development for over a decade now. The core system is finished, and the definition of the Q language and the standard library interface has been dubbed "stable". Future releases should now enforce backward compatibility and concentrate on bug fixes, optimizations and conservative extensions in the form of external modules.

8. How does Q perform in comparison with other (functional) programming languages?

This is a mixed bag, but all in all I consider Q as efficient enough for practical purposes. Since Q is an interpreted language, you cannot expect it to be as fast as native machine code compiled from languages like C. Nevertheless, pattern matching is done reasonably fast, as it uses some kind of generalized DFA device which only performs a single, non-backtracking left-to-right scan of the target expression in each reduction. Moreover, the basic eager evaluation strategy admits an efficient stack-based implementation. To give you a concrete figure, I found that with simple kinds of definitions on an Athlon 1400 typically some 400-600K reductions are performed per second.

In the benchmarks I did I found that Q scripts implementing simple list processing functions execute about as fast as their equivalents in CLISP, the Common Lisp interpreter by Haible et al, which appears to be a fairly efficient implementation. Heavily recursive functions such as the "tak" benchmark are slower, but still execute almost as fast as in UMB Scheme (which is not a particularly fast interpreter, but not a bad one either).  I also did some comparisons with Hugs (Mark P. Jones' well-known Haskell interpreter), which indicate that Q is faster in plain recursion, about at par in list construction, and slower when traversing list structure. The latter is probably due to Haskell's static typing which allows simple kinds of patterns to be matched very efficiently. It should be interesting to compare the two in situations where substantial pattern matching is involved, i.e., when dispatching over huge sets of overlapping constructor patterns. This hasn't been done yet. (Please note that these are just some of my personal impressions, which still have to be backed up with more systematic testing. As always, your mileage may vary.)

Quite clearly, the major issue in the current implementation is memory requirements. Q deliberately trades memory for execution speed, and thus the overhead in the expression data structure is quite high at present - on a 32 bit machine, the size of an expression node is 24 bytes (12 bytes data and 12 bytes for tagging and other bookkeeping information), which is 3 times the memory of a cell in a typical Lisp or Haskell implementation. (This sounds worse than it actually is, because an expression cell in the Q interpreter is roughly equivalent to two cons cells in Lisp. Thus expressions in Q only need some 50% more memory than fully tagged expression trees in Lisp, and this figure already includes the memory required to implement the reference counting garbage collector. Moreover, Q's memory management is completely dynamic, i.e., the interpreter automatically resizes stack and heap as necessary, which makes it easier to use than Hugs which has to be told its heap size in advance.)

Fortunately, main memory becomes cheaper and bigger all the time, so perhaps the memory requirements are not a major obstacle in practice, except for the most demanding applications. Future versions of the interpreter will probably be optimized in this respect, but some overhead simply cannot be avoided without sacrificing essential features of the language.

The bottomline is that, while I don't think that the interpreter is perfect yet, it appears to be quite usable, provided that you have enough main memory.

9. Can I use Q for large software projects?

With the advent of Q 3.x, a simple but powerful module system has been added to the language. Each module now has its own namespace, and name conflicts can be resolved using qualified identifiers and aliases. Thus you can now structure and maintain large scripts with ease. That said, you'll find that Q code is very dense; the whole standard library is just some 3000 lines. But it is reassuring to know that the usual facilities needed for "programming in the large" are there when you need them.

10. How do I extend the Q interpreter?

Q has an elaborate "external module" (a.k.a. "plugin") interface, which allows you to load C modules into the interpreter. Thus you can easily extend the interpreter with your own new "builtins", in order to access operations from C libraries or benefit from C's higher processing speed for time-critical applications.

The C module interface has been improved considerably in recent releases, and should now work on all systems supported by the GNU libtool package. On systems where this is possible (this includes most modern UNIXes, Linux, BeOS, OS X and Windows) modules are implemented as "shared libraries" (a.k.a. "dlls" on Windows) which can be loaded at runtime. On systems lacking shared library support you must relink the interpreter to make it work with your own modules; see Appendix "C Language Interface" in the language manual for details.

11. Does Q support multithreading?

Yes. As of Q 3.1, on systems where the POSIX threads library or some compatible replacement is available (this includes Windows and most modern UNIXes), the interpreter can be built with POSIX threads support, and is reentrant via the C interface, provided that you register threads which need access to the internals of the interpreter; see the libq header file for details.

Moreover, the clib module now provides a fairly complete set of bindings for the POSIX thread functions. With these facilities you can implement multithreaded scripts which concurrently evaluate expressions in different threads. Besides thread creation, termination and cancellation, the usual synchronization features (mutexes, conditions and semaphores) are all supported. Using semaphores, you can also send expression values from one thread to another.

12. And what's the road ahead?

As far as I am concerned, the core system is finished, and future extensions will mostly be provided through external modules. Here are some things which would be nice to have:

13. How can I contribute?

If you are willing to give a helping hand with any of the above items, or if you'd like to add something else which you are missing, please feel free contact me at:

Albert Graef
Dept. of Musicinformatics
Johannes Gutenberg University Mainz
55099 Mainz, Germany

Office:    ag@muwiinfa.geschichte.uni-mainz.de
Home:    Dr.Graef@t-online.de

WWW:    http://www.musikwissenschaft.uni-mainz.de/~ag

If there is enough interest, I will set up a CVS server or maybe a SourceForge project to ease team development.