NEXT ·  UP ·  PREVIOUS ·  CONTENTS ·  INDEX

Derived forms

Standard ML takes pattern matching and binding names to values as essential primitive operations. It provides additional syntactic constructs to help to make function declarations compact and concise. This additional syntax does not add to the power of the language, it merely sweetens the look of the functions which are being defined. Syntactic constructs which are added to a programming language in order to make programs look neater or simpler are sometimes called syntactic sugar but Standard ML calls them derived forms. The use of this more dignified term can be justified because the language has a formal semantic definition and that terminology seems appropriate in that context.

The derived form notation for functions uses the keyword fun. After this keyword comes the function identifier juxtaposed with the patterns in their turn. For example, the integer successor function can be declared thus: fun succ x = x + 1. The fun keyword applies also to recursive functions so we might re-implement the sum function as shown here.

fun sum 1 = 1
  | sum n = sum (n - 1) + n;

We begin to see that derived forms are needed when we consider curried functions with several arguments. The definitions of curry, uncurry and compose are much more compact when written as shown below.

fun curry f x y = f (x, y);
fun uncurry f (x, y) = f x y;
fun compose (f, g) x = f (g x);

Other notation in the language is defined in terms of uses of functions. The most evident is the case .. of form which together with the fun keyword can be used to clarify the implementation of the reduce function to a significant extent. Compare the function declaration below with the previous version in order to understand how the case construct is defined as a derived form.

fun reduce (g, e, m, n, f) =
    case m > n of true => e
                | false => g (reduce (g, e, m, n-1, f), f n);

The division of function definitions on the truth or falsehood of a logical condition occurs so frequently in the construction of computer programs that most programming languages provide a special form of the case statement for the type of truth values. Standard ML also provides this. Again, compare the function declaration below with the previous version in order to understand how the conditional expression is defined as a derived form.

fun reduce (g, e, m, n, f) =
    if m > n then e else g (reduce (g, e, m, n-1, f), f n);

Other keywords are derived forms which obtain their meanings from expressions which use a conditional. The logical connectives andalso and orelse are the short-circuiting versions of conjunction and disjunction. This means that they only evaluate the expression on the right-hand side if the expression on the left-hand side does not determine the overall result of the expression. That is just the behaviour which would be expected from a conditional expression and hence that is why the definition works.

Note in particular that andalso and orelse are not infix functions because they are not strict in their second argument--that is, they do not always force the evaluation of their second argument--and such functions cannot be defined in a strict programming language such as Standard ML. Thus we cannot apply the op keyword to andalso or orelse.

Exercise

By using only constructors in pattern matching we could write four-line functions for the binary logical connectives which simply mimicked their truth tables. By allowing variables in patterns the declarations could all be shorter. Write these shorter versions of conj, disj, impl and equiv.

Exercise

Would it be straightforward to rewrite the reduce function [*] using local rather than let? What would be the difficulty?

Exercise

The semifactorial of a positive integer n is 1 × 3 × 5 × ... × n if n is odd and 2 × 4 × 6 × ... × n if n is even. Use the reduce function to define a semifac function which calculates semifactorials.

Exercise

Which, if either, of the following are well defined?
(1) compose (compose, uncurry compose)
(2) compose (uncurry compose, compose)

Exercise

Use the predefined Standard ML version of function composition to define a function, iter', which behaves identically to the function iter given earlier.

Exercise

How would you define exp1 andalso exp2 and exp1 orelse exp2 in terms of exp1, exp2, conditional expressions and the constants true and false? Try out your definitions against the expressions with the derived forms when exp1 is ``true'' and exp2 is ``10 div 0 = 0''. Then change exp1 to ``false'' and compare again.

NEXT ·  UP ·  PREVIOUS ·  CONTENTS ·  INDEX