[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

9. Special Forms

As discussed in 7. Equations and Expression Evaluation, the Q interpreter evaluates expressions in applicative, i.e., leftmost-innermost, order. This means that the arguments of a function are usually evaluated before the function is applied to them, which is also known as call by value. Occasionally, it is useful or even essential to defer the evaluation of arguments until they are actually required in the course of a computation. For this purpose, the Q language lets you introduce so-called special forms which receive their arguments unevaluated (i.e., using call by name). This chapter discusses how these constructs are defined and used.

9.1 Basic Concepts  
9.2 Special Constructors  
9.3 Built-In Special Forms  
9.4 The Quote Operator  


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

9.1 Basic Concepts

Consider the following definition from the standard library which implements a simple kind of conditional expression (see also 11.10 Conditional Expressions):

 
ifelse P X Y            = X if P;
                        = Y otherwise;

The ifelse function takes as its first argument a truth value which is used to determine whether the second or third argument is to be returned as the value of the conditional expression. Although the above definition is perfectly correct, using applicative order evaluation with this definition is clearly inappropriate since all arguments must already have been evaluated before the ifelse function gets applied to them. Since either the second or third argument is simply thrown away, the effort involved in the evaluation of this argument is wasted. As an extreme case, e.g., Y might not have a terminating evaluation at all, in which case the evaluation of ifelse P X Y would not terminate either even though Y is actually not required if P happens to evaluate to true.

Instead, we would like to have ifelse evaluate its arguments only as they are required. In the Q language, this can be done by simply declaring ifelse as a special form. All we have to do is to precede the above equations with the following declaration:

 
public special ifelse P X Y;

The syntax of such declarations has already been introduced in 5. Declarations. The special keyword must be followed by a function identifier and a sequence of variable symbols (the variable symbols only serve to specify the number of arguments, and are otherwise treated as comments). If the argument list is omitted, the function symbol is actually treated as an ordinary (non-special) symbol. Otherwise the given arguments are declared as special (a.k.a. call by name) arguments, i.e., arguments which are treated as literals and hence are not evaluated when the given function is applied to them. Special arguments will be left unevaluated as long as they are "protected" by a special form; but as soon as the corresponding values are referred to in a "non-special" context, the interpreter will automatically evaluate them.

Thus the above declaration of the ifelse function tells the Q interpreter that this function expects three special arguments P, X and Y which should be left unevaluated until their values are actually required in the qualifier or the right-hand side of an equation in ifelse's definition. Consequently, when the interpreter comes to consider the first rule,

 
ifelse P X Y            = X if P;

it will first evaluate P to obtain the value of the condition part of this rule. If P evaluates to true, X will be evaluated and returned as the value of the left-hand side expression. Otherwise (if P evaluates to false), X will be left unevaluated, and the interpreter considers the next rule,

 
ifelse P X Y            = Y otherwise;

which causes it to evaluate Y and reduce ifelse P X Y to this value.

Note that a special argument is evaluated each time its value is required on the right-hand side of a definition. Consider, for instance:

 
special foo X;
foo X                   = bar X X;

When this rule is applied, X actually gets evaluated twice, once for each occurrence on the right-hand side of the equation. If this is not desired, you can introduce a local variable binding, e.g.:

 
special foo X;
foo X                   = bar Y Y where Y = X;

Another important point is that in the Q language, special forms are indeed a runtime feature. This means that special forms are not only recognized at compile time, but also when they are passed as arguments or returned as function results in the course of a computation (which usually cannot be predicted at compile time). For instance, if we define foo as follows:

 
special bar X;
foo                     = bar;

then foo (1+1) evaluates to bar (1+1) and not to bar 2, although foo itself is not declared to be a special form. This also works if you pass bar as a functional parameter:

 
special bar X;
foo F X                 = F (X+1);

Given the above definition, foo bar 1 will evaluate to bar (1+1).

On the other hand, you must take care that arguments to special functions which are passed on by other functions are not evaluated too early. For instance, if the apply function is defined as follows:

 
apply F X               = F X;

and is then invoked as apply bar (1+1) then (1+1) will be evaluated even though bar is a special form. The reason is that the argument (1+1) is evaluated before apply is applied to it, since we have not declared apply as a special form as well. As a general rule, you should make any function a special form that passes its arguments to another special form, unless you explicitly wish to evaluate these arguments.

Up to now, we have only considered "pure" special forms, which receive all their arguments unevaluated. Many functions, however, require a mixture of special and non-special arguments. The Q language provides two different methods for dealing with such situations. First, you can force the evaluation of a special argument at runtime using the `~' (tilde or "force") operator:

 
special foo P X;
foo P X                 = ifelse ~P (bar X) X;

Here, the condition P is evaluated before it is passed on to the ifelse special form (which is as defined above). This method is useful if we only occasionally have to evaluate a parameter of a special form.

We remark that you can also force expressions outside a special form; in this case `~' acts as the identity operation, i.e., the argument expression (which is already in normal form) is simply returned as is.

If we always want to evaluate a given parameter of a special function, we can also declare the corresponding argument as non-special which effectively turns the argument into an ordinary call by value parameter. This is done by preceding the argument with the `~' symbol in the declaration of the function symbol. For instance, in the above definition of the ifelse function the first argument will be evaluated anyway. Hence we may as well make it a non-special argument. The corresponding declaration reads as follows:

 
public special ifelse ~P X Y;

With this declaration (which is precisely how ifelse is actually declared in the cond.q standard library module), the ifelse function always receives its first argument evaluated, while the other two arguments are special. This works exactly like an explicit application of the `~' operator, but releases you from the burden of having to force evaluation of the argument in every application of the ifelse function. It is also slightly more efficient since the argument does not have to be constructed as a literal expression, but can be evaluated right away before the ifelse function is applied to it.

Let us briefly comment on Q's special forms versus "real" lazy evaluation in functional languages like Haskell. It should be clear by now that Q allows you to keep a special argument from being evaluated as long as you like, maybe "to eternity". That is, the interpreter actually computes so-called "weak" normal forms in which special arguments are left unevaluated, even if these arguments are reducible. This is similar to the way deferred evaluation is handled in traditional functional languages featuring a basic eager evaluation strategy. In contrast, a pure lazy functional language interpreter will eventually reduce each expression to a "true" normal form to which no definition is applicable. Both approaches have their pros and cons. The leftmost-outermost strategy of lazy functional language interpreters is in fact only truly lazy for the lambda and combinatorial calculi used by these systems, which are very special kinds of rewriting system. In general term rewriting, however, there is no single "optimal" evaluation strategy; in fact, the problem to devise a terminating, let alone an optimal reduction strategy for a given rewriting system, even for a single input expression, amounts to solving the infamous halting problem which is undecidable. Although the Q interpreter uses a fixed built-in leftmost-innermost evaluation strategy, special forms effectively give you full control over the evaluation strategy. Moreover, special forms are also a powerful device for implementing "meta functions" which operate on other, literal expressions. This is discussed in more detail in 9.4 The Quote Operator.


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

9.2 Special Constructors

Special forms prevent their arguments from being evaluated until they are used in a context which is not "protected" by another special form. In particular, you can also have special constructors which protect their arguments until they are extracted in an ordinary context. A prime example for this are streams, a kind of infinite list data structure. We can implement streams using a type definition like the following:

 
type Stream = special const nil, bin X Xs;

Just like lists, a stream consists of a head element, X, and a stream of remaining elements, Xs. Now the "head" and "tail" operations for lists (cf. 7.1 Equations) carry over to streams as follows:

 
hd (bin X _)            = X;
tl (bin _ Xs)           = Xs;

Lisp programmers should note that this implementation does not require any explicit "delay" and "force" operations; all necessary evaluations are performed implicitly by the Q interpreter. For instance, consider the stream of all integers starting from N:

 
ints N                  = bin N (ints (N+1));

With leftmost-innermost evaluation, the above definition would certainly cause grief, because the recursive invokation of ints would send the interpreter into an infinite recursion. However, since bin is a special form, the evaluation of the nested ints term is deferred, and we have the following:

 
==> def nat = ints 1

==> nat
bin 1 (ints (1+1))

==> hd nat; tl nat
1
bin 2 (ints (2+1))

We can also have finite streams if we use the nil constant to signal the end of a stream, and most common list operations carry over to streams accordingly. In difference to lists, streams produce their elements only "on demand". This paves the way for some important and powerful programming techniques. For instance, streams are a useful device to implement different kinds of backtracking and dynamic programming algorithms in a uniform setting. Please refer to [Abelson/Sussman 1985] for more details. The standard library includes an implementation of streams which is described in 11.9 Streams.


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

9.3 Built-In Special Forms

Some built-in operations of the Q language are actually implemented as special forms. This is necessary, in particular, in the case of the logical connectives and then and or else which are evaluated in "short-circuit mode", see 6.4.4 Logical and Bit Operators. The first argument of these operations is non-special, but the second argument is only evaluated if it is needed. For instance, the and then operator first checks whether its first (evaluated) argument is a truth value (if not, the built-in rule fails). Then, if the first argument is false, false is returned -- there is no need to take a look at the second argument. Otherwise, the second argument is evaluated and returned as the value of the expression. The or else operation is defined analogously. These rules allow the Q interpreter to perform the following reductions immediately, without ever having to evaluate the second argument foo X:

 
true or else foo X      => true
false and then foo X    => false


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

9.4 The Quote Operator

Another built-in special form is the predefined quote operator `'', which acts as a constructor that protects its single argument expression from being evaluated. This construct is useful if you wish to treat certain expressions (which may or may not be in normal form) as literal objects rather than having them evaluated. For instance:

 
==> '(1+1)
'(1+1)

Lisp programmers should note that the quote operator is in fact a constructor, and not an operation which returns its single argument unevaluated. This is essential since in the Q language an expression only remains unevaluated as long as it is protected by a special form -- an expression which occurs outside the context of a special form is always in normal form.

Another fact that deserves mentioning is that `'' is just an "ordinary" special form, and does not involve any special "magic" on the side of the interpreter. In particular, `'' does not inhibit variable replacements in rules like the following:

 
special foo X;
foo X                   = '(X+1);

Given the above definition, foo Y => '(Y+1), i.e., the X variable on the right-hand side is not treated as a literal. However, as the very same example shows, you can employ `'' to quote a free variable, and thereby defer its evaluation:

 
==> def Y = 99; foo Y
'(Y+1)

==> foo ~Y
'(99+1)

The force operator `~' works in quoted expressions as usual:

 
==> '(1+~(2+3))
'(1+5)

Moreover, there is another, similar operation, the ``' (backquote or "splice") operator, which forces evaluation of its argument like the `~' operator, but also "unquotes" the result. For instance, using the same foo function as above, we have:

 
==> '(`(foo Y)/2)
'((Y+1)/2)

Like the force operator, the splice operator also works outside a special form, in which case the unquoted expression is evaluated as usual. Moreover, if the evaluated argument is an unquoted expression, it is returned as is; in this case, ``' does exactly the same as the `~' operator.

The splice operator is the fundamental operation when constructing quoted expressions from smaller quoted pieces, by "splicing" the pieces into a "template" expression. Lisp programmers will be familiar with this technique. However, there are some notable differences between Q's `~'/``' and Lisp's `,'/`@,' constructs:

We also remark that, in contrast to the quote operator, the force and splice operations do need special support from the interpreter. They are the only operations which are evaluated while a special form is being processed.

When used in concert, the quotation operators `'', ``' and `~' become powerful tools for the symbolic manipulation of literal expressions. They allow you to define functions which analyze and transform an expression before the modified expression is finally evaluated. Such "meta-functions" are useful in many applications, and are an essential requisite in artificial intelligence algorithms. Substantial examples can be found in the standard library scripts, see 11. The Standard Library; in particular, take a look at how the lambda and listof functions are implemented. As a simple (and somewhat contrived) example, let us write a function which takes an arbitrary quoted expression and replaces each instance of a foo X subterm by a corresponding bar X expression:

 
foo X                   = X-1;
bar X                   = X+1;

foobar '(foo X)         = '(bar `(foobar 'X));
foobar '(X Y)           = '(`(foobar 'X) `(foobar 'Y));
foobar '(X|Y)           = '(`(foobar 'X)|`(foobar 'Y));
foobar '[X|Y]           = '[`(foobar 'X)|`(foobar 'Y)];
foobar X                = X otherwise;

To see foobar in action, try the following:

 
==> def x = 12, y = 14, X = '(x+foo (y+foo (x*y)))

==> `X
192

==> foobar X
'(x+bar (y+bar (x*y)))

==> `_
196


[ << ] [ >> ]           [Top] [Contents] [Index] [ ? ]

This document was generated by Albert Gräf on October, 14 2003 using texi2html