Forcing evaluation

Non-strict programming in Standard ML uses the pre-defined unit type. This peculiar type has only one element, written ``()'', and also called ``unit''. This representation for unit is a derived form for the empty record, ``{ }''. Horrifyingly, that is also the way to represent the type of the empty record so we find that we have { } : { } in Standard ML!

The use of the unit type serves to convey the idea that the parameter which we pass to the function will never be used in any way since there are no operations on the unit element and it also conveys no information because there is only one value of this type. It is possible to delay the evaluation of expressions with unused values of any type but we would not wish to do this. The type of a Standard ML function acts as important documentation about its behaviour and we would not wish it to have a misleading source type, say int or 'a, since the resulting confusion about the type would make our program harder to understand.

The type which delayed expressions have is called a delayed type. This is a parameterised type constructor as defined below.

type 'a delayed = unit -> 'a;

We could then try to label integer expressions as being delayed and thereby turn them into functions of type ``unit -> int''. If we need the integer value which they would compute then we can force the evaluation of the integer expression by applying the function to (). We will now attempt to define the functions which force evaluation and delay evaluation. The force function has type 'a delayed -> 'a. This is a simple function to implement.

val force : 'a delayed -> 'a = fn d => d ();

The function delay below has type 'a -> 'a delayed. It should be the inverse of force and for all expressions exp we should have that force(delay(exp)) evaluates to the same value as exp itself.

val delay : 'a -> 'a delayed = fn d => (fn () => d);

This function has the correct type and has achieved the aim that force(delay(exp)) evaluates to the same value as exp for all expressions but it has not achieved the effect we wanted. The additional requirement was that it should delay the evaluation of an expression. However, consider the evaluation of a typical application of delay using Standard ML's call-by-value semantics.

delay(14 div 2) = ( fn d => ( fn () => d)) (14 div 2)

= ( fn d => ( fn () => d)) (7)

= fn () => 7

This is not the desired effect since we wished to have the expression delay(14 div 2) be identical to ( fn () => 14 div 2). It is not possible to implement a delay function of type 'a -> 'a delayed in Standard ML since the expression will always be evaluated and the resulting value passed to the function. We will write `` fn () => exp'' from now on--or in some circumstances use an equivalent derived form--but continue to pronounce this as ``delay exp''. Our functions delay and force implement call-by-name expressions because repeated applications of force repeat previous computations. The Standard ML library provides a suspension structure called Susp with a type 'a Susp.susp and functions Susp.delay and Susp.force on this type. The type of the function Susp.delay is (unit -> 'a) -> 'a Susp.susp and the type of Susp.force is 'a Susp.susp -> 'a. These functions differ from ours not only in their type but because they implement call-by-need expressions where repeated applications of Susp.force on the same parameter re-use the results of previous calculations.

NEXT ·  UP ·  PREVIOUS ·  CONTENTS ·  INDEX