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:
- First and foremost, 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). In particular, Q has no a priori
distinction
between "constructors" and "defined" function symbols, and argument
patterns
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
evaluate to [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)
expressions
as literal terms. This gives you full control over the reduction
strategy,
where this is desired, as well as a kind of "macros" and
"self-modifying
programs",
since constructs like lambda abstractions can be analyzed, transformed
and
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
certainly
make life easier when programming complex I/O stuff such as graphical
user interfaces.
- 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.
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:
- All kinds of programming tasks in which you have to manipulate
elaborate
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
other OSC-aware
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
something like
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
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:
- Support for wide character (unicode) strings and other
internationalization features.
- Interfaces to other graphics, GUI and data visualization toolkits
(OpenGL, Gtk,
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.
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
