Now that the Q programming model has been introduced using a virtual machine model, the formal underpinnings can be discussed. It is possible to describe the Q instruction set architecture without resorting to a machine description. Q is in many ways an architecture for implementing a high-level programming language, Lucid. Q provides an implementation of Lucid which is reduced is some ways and extended in others. Examination of these differences may suggest possible areas for improvement.
The multidimensional Lucid language proposed by Ashcroft, Faustini, Jaggannathan, and Wadge[2] is a intensional, stream-based, multidimensional programming language, derived from Landin's ISWIM[3]. It is an extension of earlier work with the original one-dimensional version of Lucid[5], ferd Lucid, and an early attempt at multidimensionality[1]. Hereafter, the Lucid referred to is the ``new'' multidimensional Lucid[2] unless otherwise noted.
Lucid extends the simple applicative expressiveness of ISWIM with an intensional logic using a multidimensional space. The single variable of a simple algebra is extended into a stream which spans any dimensions over which the variable changes. The use of Lucid as a language for describing stream-based programming is warranted for several reasons. It provides a firm theoretical foundation for streams -- their definition and manipulation. While Q makes little use of it, much work has been done on transformation and proof of Lucid programs.
Equally important is its use of intensional referencing, which promotes development of algorithms supporting stream (data independent) processing. Limited access to variable values ``at other times and places'' is allowed through intensional (relative) addressing primitives.
The requirements that Q places upon functions are a minor divergence from Lucid. In Lucid, functions are allowed to access streams and dimensions which are defined either globally or in where clauses including the function definition. This difference facilitates proper implementation of the hybrid dataflow model, and is mainly a syntactical difference.