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". 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
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 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
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
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
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"?
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
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.
- First and foremost, Q is an equational rather than just a
language, meaning that it is based on general
term rewriting instead of the lambda calculus (which is just one, and
special, rewriting system). In particular, Q has no a priori
between "constructors" and "defined" function symbols, and argument
are not restricted to "constructor terms". This allows you to have
symbolic evaluation rules like the following distributivity rule:
X*(Y+Z) = X*Y+X*Z.
Such rules are not allowed in ML and Haskell because they violate the
"constructor discipline". Moreover, the Q interpreter
also happily reduces expressions involving variables, so that you can
try your definitions with symbolic inputs (e.g.,
map F [X,Y] will
[F X,F Y]),
which is quite useful for debugging purposes.
- While other functional languages are either "eager" or "lazy", Q tries to give
you the best of both worlds: It uses eager (call-by-value) evaluation
by default (which lends itself to an efficient implementation), but
also allows you to define your own special
forms, which can be used to implement both call-by-name
functions and lazy data constructors. Using special forms you can also
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 kind of "macros" and
since constructs like lambda abstractions can be analyzed, transformed
constructed in many ways before they are actually evaluated.
- Q uses dynamic typing.
This has become a rare feature in contemporary functional languages,
which usually employ a Hindley/Milner type system which offers more
safety at the expense of restricting polymorphism. Q gives you back the
flexibility of good old Lisp-style ad-hoc polymorphism and even allows
you to extend the definition of existing operations (including built-in
functions and operators) to your own data types. Moreover, Q has a
Smalltalk-like object-oriented type system which supports data
encapsulation and (single) inheritance. This makes it possible to
manage complex, polymorphic data with ease.
- Q takes the pragmatic route in that it provides (monad-free) imperative programming features
such as imperative I/O and mutable data cells, similar to the
corresponding facilities in ML. While one may argue about these, they
make life easier when programming complex I/O stuff such as graphical
- Last but not least, the Q programming system comes with batteries
included. There are quite a few add-on modules interfacing to
third-party libraries which, while not as comprehensive as the
facilities provided by traditional scripting languages like Perl and
Python, allow you to tackle most practical programming problems with
ease. In particular, multimedia and computer music is an area where Q
shines, providing facilities to handle graphics, digital audio and MIDI
in a convenient and efficient manner (efficient enough for soft
realtime applications), which go well beyond what is currently being
offered for other functional languages.
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 and multimedia programming. Q has an
elaborate MIDI interface
(based on MidiShare)
which works on Linux, Mac OS X and Windows.
Digital audio and graphics interfaces are also available, and there is
an addon package for doing DSP
and modular synthesis via SuperCollider and
software synthesis programs.
- Education (e.g., entry-level courses on functional programming,
computer music courses etc.).
- Shell and web programming. While you would probably use
Perl or Python for that, Q has an extensive system interface which
makes it suitable for scripting purposes, too. Moreover, the Q Apache
module lets you embed the Q interpreter into the Apache webserver, and
the Curl module facilitates the task of transferring web content using
a variety of different protocols.
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: http://q-lang.sourceforge.net/.
Or go directly to the SourceForge
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 call C from Q and vice versa?
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.
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
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. I am not
following a definitive roadmap, but here are
things which would be nice to have:
- Support for wide character (unicode) strings and other
- Interfaces to other graphics, GUI and data visualization toolkits
Qt, Vtk, ...).
- Additional multimedia stuff, in particular a video interface.
- Any other ideas? See the next item!
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.
Dept. of Musicinformatics
Johannes Gutenberg University Mainz
55099 Mainz, Germany