Functional Languages

Graph Reduction

Functional languages are derived from the lambda-calculus-a formal logic system intended to describe the whole of mathematics. Göodel showed it was unsound (incompleteness-you can't prove everything in a system that can describe itself). Syntax of lambda-calculus is:

[tabular324]

Parentheses are used for grouping. Computing in the lambda-calculus is by reduction, such that if the first element of a combination is a term, then the combination is replaced by the result of substituting the second expression for all occurrences of the bound variable of the term in the body of the term. Note that at any one moment, more than one term could be rewritten: only rewrite the outermost term to ensure termination (diamond property, Church-Rosser theorem). Relates to potential parallelism, abstract interpretation, strictness analysis. Define bound and free variables.

In the search for more efficient execution of languages with special constraints a number of different execution models have been developed. Program is represented as a graph rather than a linear sequence of operations. Execution transforms this graph until it is irreducible under the computation model being employed. The irreducible graph is the answer. Allows sharing-not possible in linear representation-consider a rewriting system in which an argument appears more than once in the body: the linear scheme requires replication, but the graphical form can share. No environment is required-variable binding references are acheived by shared sub-graphs. Normal-order evaluation is readily expressed and fairly efficiently implemented. The graph is reduced (executed) by the left spine of the graph until a non-application node is reached. At this point, unless the node is a literal, in which case the graph is in weak head normal form (WHNF) and no further reduction is possible, the function stored at the node is reduced using the arguments above it, tracing back up the spine. Implementation via stacks or by pointer reversal. Copying on application of functions-otherwise the modification of the graph representing the body will affect the original. Problem arises from treatment of free variables-copies of a body are different for different bindings of the formal parameter. Environment (e.g. SECD machine) is one solution, the other is to ``compile out'' the free references. Combinatory logic is one way to achieve this. Others are lambda-lifting and super-combinators.

Combinators

Aim: faster execution of pure functional languages-cost of call-by-need. Examples: SASL, Miranda, Ponder.

Combinators are a simpler formal logic system than lambda calculus, which were invented by Curry intending to succeed where Church failed (note: he didn't). A combinator in lambda calculus is a term containing no free variables. There is a correspondence between lambda-calculus and combinators, such that a expression can be rewritten (``compiled'') into combinators. In fact, this is a variable abstraction algorithm, thus we have to specify which variable is being removed. If the resulting expression is again applied to the variable that was abstracted the original expression is obtained. The rules for this transformation are:

1. [tex2html_wrap617]
2. [tex2html_wrap619]
3. [tex2html_wrap621]
4. [tex2html_wrap623]

Parentheses are used for grouping. As with the lambda-calculus, computation is by reduction and is defined by the following two rules:

1. [tex2html_wrap625]
2. [tex2html_wrap627]

Note that (finally) there are no variables in combinator expressions-only the constants denoting the combinators. See handout. Show this is equivalent to the lambda-expression we started from. Verbose! Optimise. Turner defines the following four optimisation rules for combinator expressions:

[eqnarray*337]

In fact, these optimisations are applied during transformation (abstraction algorithm, line 3) rather than post-facto. The additional reduction rules are:

1. [tex2html_wrap629]
2. [tex2html_wrap631]

Many other optimisation combinators can be invented to reduce code size (Turner defines 20 in his thesis). Further optimisations are:

commutative operators and [tex2html_wrap633]:

If [tex2html_wrap635] is a primitive commutative function then [tex2html_wrap637] since all [tex2html_wrap639] does is exchange its second and third arguments.

multiple variable abstraction:

Repeated abstraction leads to code bloat in the combinator expression. In fact, expression size is proportional to [tex2html_wrap641] if [tex2html_wrap643] variables are abstracted. Introduce [tex2html_wrap645]-called the reaching form of [tex2html_wrap647]. Now extend abstraction algorithm with the rule

[tex2html_wrap615]

if [tex2html_wrap649] does not occur in [tex2html_wrap651]. Resulting form is only linear in the number of variables abstracted. Similarly for [tex2html_wrap653] and [tex2html_wrap655].

Director Strings

An alternative interpretation of combinators in which the application nodes are annotated to indicate where the arguments (as they percolate down from the root) should be fed, e.g. to both branches for a [tex2html_wrap659] applications, to the left for a [tex2html_wrap661] and the right for a [tex2html_wrap663], ignoring for a [tex2html_wrap665]. These annotations are called directors. An [tex2html_wrap667] acts as a ``hole'' which is filled in by the arrival of the argument-that is, it has reached its correct place in the graph. In this simple form, the scheme can only cope with a single argument, the generalisation is to allow strings of directors at nodes, where the first is used for the first argument etc.

What this serves to illustrate is that the abstraction algorithm from lambda terms to combinators is effectively encoding a route map for the arguments when they are supplied later, so that they are sent back to the places from which they were abstracted. Can also justify the [tex2html_wrap669] and [tex2html_wrap671] optimisations now as if we send an argument to both branches of a [tex2html_wrap673]-node and then discard it ([tex2html_wrap675]), we need only direct to the other branch.

Director strings can be highly space-efficient, because there are only four possibilities (not unrelated to the fact that [tex2html_wrap677] and [tex2html_wrap679] suffice to compile all functions): both, left, right, discard, which can be encoded in two bits.

Lambda-lifting

Problem with combinators is grain-size: the unit of computation per operation is relatively small; in consequence, there is a large number of function applications (reductions). Want to translate programs (lambda expressions) into new combinators (rather than a fixed set) generated from the lambda abstractions involved. Lambda-lifting and super-combinators attempt to address this by increasing the grain-size and hence reducing the number of applications required.

Lambda-lifting is simple, but leads to unnecessary copying and (hence) duplicated reduction. The free variables are ``lifted'' out of the body and the abstraction is replaced by the partial application of a new combinator which has one more parameter. Start from the innermost abstraction. (Note: an applicative expression is one containing only function applications-no abstractions-e.g. combinator expressions.) The algorithm for lifting is:

1. [tex2html_wrap681] if [tex2html_wrap683] is a combinator

2. [tex2html_wrap685] if [tex2html_wrap687] is an applicative expression with [tex2html_wrap689] being the free variables of the abstraction.

3. [tex2html_wrap691] if [tex2html_wrap693] is not an applicative expression

4. [tex2html_wrap695]

5. [tex2html_wrap697]

f = fn x => (fn y => (BIG x) + (y * x));

alpha = fn x => (fn y => (BIG x) + (y * x));

beta = fn x => alpha x;

f = beta;

Consider the partial application f A [tex2html_wrap699] alpha A. The resulting partial function when applied to B will construct the expression (BIG A) + (B * A) so that BIG A is computed each time. This repetition can be avoided by recognising candidate expressions in advance: that is, any non-constant sub-expression of a lambda body not containing the bound variable. Such an expression is called a free expression (FE). In constructing super-combinators we abstract FEs rather than variables.

Super-combinators

Super-combinators are a generalisation on the idea of inventing combinators to improve the code size. Therefore, if we transform each function into a combinator which can then be compiled (a large instruction sequence) functional languages should perform better on conventional architectures.

Super-combinator combinator construction is more complicated than lambda-lifting but does share structure and (hence) avoids duplicated reduction thus retaining full laziness.

The free variables in the lambda body are the minimal FEs. An alternative approach is to define combinators whose parameters are the non-constant maximal FEs (or MFEs). Combinators obtained in this way are called super-combinators (Hughes, 1984). The algorithm is:

1. Find all the MFEs in the lambda body

2. Replace each occurence of an MFE by a new parameter name (a super-combinator bound variable), except in the case of duplicates, where the previous parameter name is used.

1. [tex2html_wrap701]

2. [tex2html_wrap703] where [tex2html_wrap705] is an applicative expression and the [tex2html_wrap707] are the MFEs of [tex2html_wrap709].

3. [tex2html_wrap711] if [tex2html_wrap713] is not an AE.

4. [tex2html_wrap715]

5. [tex2html_wrap717]