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". What this somewhat cryptic jargon actually means is that expressions are evaluated in a symbolic fashion, very much like formulas are manipulated in algebra, only much faster than you could ever do it by hand.

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 my work on a term rewriting interpreter which started in the 1990s 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 various useful third-party libraries. 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"?

Not quite. Even though the syntax and some of the stuff in the standard library looks superficially similar, Q is different in a number of ways:
Some of Q's flexibility comes at a price. In particular, Q's symbolic evaluation capabilities as a term rewriting language dictate that the language is essentially exception-free. This means that an "ill-formed" expression (such as "division by zero" or, more generally, the application of a function to data for which there is no corresponding definition) does not, by default, raise an exception, but instead the expression is already in "normal form", i.e., it evaluates to itself. As a remedy, Q provides facilities to add explicit error rules which raise exceptions, and to handle exceptions in a suitable manner. Another limitation is that Q does not allow you to have arbitrary local definitions in the style of Haskell and ML's "let" and "where" clauses. In Q, "where" clauses are limited to variable definitions (similar to Haskell's pattern bindings), but local rewriting rules are not supported as they would wreak havoc on the term rewriting semantics.

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://q-lang.sourceforge.net/. Or go directly to the SourceForge project website.

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 call C from Q and vice versa?

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.

As of Q 5.0, it is now also possible to go the other way round, i.e., embed Q in your C/C++ applications. This is useful to, e.g., employ Q as a macro language or term rewriting engine in other programs.

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. I am not following a definitive roadmap, but here are some things which would be nice to have:

13. How can I contribute?

Want to join the fun? Contact me! (See below for my email addresses.) The central location for Q development is the SourceForge project website, which also provides CVS access to the latest development sources, and the developer and user mailing lists.

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