FAQ about the Q Programming Language and System
This FAQ is still in its infancy, so please help its development by
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
to normal form. Please note that the Q interpreter is neither a
system nor an equational
theorem prover (although you could use it for such purposes). Like
functional language interpreters, it is just an expression evaluator.
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
Q is the result of some 10 years work on a term rewriting
on my earlier research on term pattern matching. By now, Q has evolved
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
of C add-on modules are already available which allow you to interface
Tcl/Tk, Octave and IBM's Data Explorer, and the `clib' module gives you
to important system functions such as file and process manipulation and
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
the interpreter and then type in the expressions you wish to evaluate.
this can be done with a few keystrokes, if you use the Emacs Q mode
with the package. A more windowish GUI frontend for the Q interpreter
also available (screenshot).
NOTE: The problem with one-character acronyms is that the
alphabet does not have enough letters. ;-) There are two other
languages named "Q" I know of. They have nothing to do with the Q
presented here. First,
Per Bothner's Q was also developed around the beginning of the
apparently, it is not being maintained any more. Second, a prerelease
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
special, rewriting system). For the programmer this means greater
in specifying the computational rules, which can be arbitrary equations
of just function definitions. In particular, Q has no a priori
between "constructors" and "defined" function symbols, and argument
are not restricted to "constructor terms". Thus symbolic simplification
constructor equations and partial function definitions can all be dealt
in a direct manner.
Second, using Q's "special forms" you can define your own "meta
functions" which manipulate arbitrary (not necessarily irreducible)
as literal terms. This gives you full control over the reduction
where this is desired, as well as a simple kind of "self-modifying
since constructs like lambda abstractions can be analyzed, transformed
constructed in many ways before they are actually evaluated.
Third, Q takes a pragmatic approach in that it uses applicative
as its default evaluation strategy (data structures with lazy
can be defined using special forms), and has dynamic typing and
imperative-style I/O, very much like more traditional functional
such as Lisp. While one may argue about these features, they
make life easier.
You will also notice that Q lacks most of the syntactic sugar found
Haskell. This is partly due to my laziness, but it also keeps the
and the core system simple. Using Q's symbolic processing capabilities,
usual bits like lambda abstractions, pattern matching conditionals
and list comprehensions can easily be written in Q itself (although
does not offer quite the same performance as when they are provided as
3. So what is it good for?
To name a few areas for which Q might be interesting:
- All kinds of programming tasks in which you have to manipulate
list- and tree-like data structures.
- Experimenting with functional language implementations and
computer algebra algorithms.
- Scientific programming. The graph library and the interfaces to
Octave and OpenDX are very helpful for this kind of applications.
- Computer music applications. Q has an elaborate MIDI interface
(based on MidiShare) which works on Linux, Mac OS X and Windows. A
digital audio interface is also available. Additional modules for DSP
and modular synthesis applications are in the planning stage.
- Education (e.g., entry-level courses on functional programming,
computer music courses etc.).
- Shell programming. While you would probably use something like
Perl or Python for that, Q has an extensive system interface which
makes it suitable for scripting purposes, too.
I use Q myself for a variety of scientific and computer music
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
language (compared to Lisp, ML or Haskell) appears to be a big plus.
4. Where can I get it?
From the Q homepage:
5. What documentation is available?
The distribution includes a fairly comprehensive (200+ pages) language
texinfo format. The manual is also available online on the Q homepage
in both HTML
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
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
8. How does Q perform in comparison with other (functional)
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
Nevertheless, pattern matching is done reasonably fast, as it uses
some kind of generalized DFA device which only performs a single,
left-to-right scan of the target expression in each reduction.
Moreover, the basic eager
evaluation strategy admits an efficient stack-based implementation. To
you a concrete figure, I found that with simple kinds of definitions on
Athlon 1400 typically some 400-600K reductions are performed
In the benchmarks I did I found that Q scripts implementing simple
list processing functions execute about as fast as their equivalents in
Lisp interpreter by Haible et al, which appears to be a fairly
Heavily recursive functions such as the "tak" benchmark are slower, but
execute almost as fast as in UMB
(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
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
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
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
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
is roughly equivalent to two cons cells in Lisp. Thus expressions in Q
some 50% more memory than fully tagged expression trees in Lisp, and
already includes the memory required to implement the reference
collector. Moreover, Q's memory
management is completely dynamic, i.e., the interpreter automatically
stack and heap as necessary, which makes it easier to use than Hugs
has to be told its heap size in advance.)
Fortunately, main memory becomes cheaper and bigger all the time, so
the memory requirements are not a major obstacle in practice, except
the most demanding applications. Future versions of the interpreter
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
yet, it appears to be quite usable, provided that you have enough main
9. Can I use Q for large software projects?
With the advent of Q 3.x, a simple but powerful module system has been
the language. Each module now has its own namespace, and name conflicts
resolved using qualified identifiers and aliases. Thus you can now
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
reassuring to know that the usual facilities needed for "programming in
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
to load C modules into the interpreter. Thus you can easily extend
the interpreter with your own new "builtins", in order to access
from C libraries or benefit from C's higher processing speed for
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
(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
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
which concurrently evaluate expressions in different threads. Besides
creation, termination and cancellation, the
usual synchronization features (mutexes, conditions and semaphores) are
supported. Using semaphores, you can also send expression values from
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
things which would be nice to have:
- Support for wide character (unicode) strings and other
- Interfaces to other GUI and data visualization toolkits (Gtk,
Qt, Vtk, ...).
- Portable bitmap graphics interface (probably ggi-based).
- Additional sound stuff, in particular software synthesis.
13. How can I contribute?
If you are willing to give a helping hand with any of the above items,
you'd like to add something else which you are missing, please feel
Dept. of Musicinformatics
Johannes Gutenberg University Mainz
55099 Mainz, Germany
If there is enough interest, I will set up a CVS server or maybe a
SourceForge project to ease team development.