Chapter 6. Effectful Programming Features

Table of Contents
Exceptions
Example: Testing for Braun Trees
References
Example: A Counter Implementation
Arrays
Example: Ordering Permutations
Matrices
Example: Estimating the Constant Pi
Simple Input and Output

Effectful programming features are those that can generate effects at run-time. But what is really an effect? The answer to this question is rather complex as it depends on the model of evaluation. I will gradually introduce various kinds of effects in this book. In sequential programming, that is, constructing programs to be evaluated sequentially (in contrast to concurrently), an expression is effectless if there exists a value such that the expression and the value cannot be distinguished as far as evaluation is concerned. For instance, the expression 1+2 is effectless as it cannot be distinguished from the value 3. An effectless expression is also said to be pure. On the other hand, an effectful expression is one that can be distinguished from any given values. For instance, the expression print("Hello") is effectful as its evaluation results in an observable behavior that distinguishes the expression from any values. In this case, print("Hello") is said to certain I/O effect. If the evaluation of an expression never terminates, then the expression is also effectful. For instance, let us define a function loop as follows:

fun loop(): void = loop()

Then the expression loop() can be distinguished from any values in the following context:

let val _ = [] in print("Terminated") end

If the hole [] in the context is replaced with loop(), then the evaluation of the resulting expression continues forever. If the hole [] is replaced with any value, then the evaluation leads to the string "Terminated" being printed out. The expression loop is said to contain non-termination effect.

I will cover programming features related to exceptional control-flow, persistent memory storage and simple I/O in this chapter, which are all of common use in practical programming.

The code employed for illustration in this chapter plus some additional code for testing is available on-line.

Exceptions

The exception mechanism provides an efficient means for reporting a special condition encountered during program evaluation. Often such a special condition indicates an error, but it is not uncommon to employ exceptions to address issues that are not related to errors.

The type exn is predefined in ATS. One may think of exn as an extensible datatype for which new constructors can always be declared. For instance, two exception constructors are declared as follows:

exception FatalError0 of () exception FatalError1 of (string)

The constructor FatalError0 is nullary while the constructor FatalError1 is unary. Exception values, that is, values of the type exn can be formed by applying exception constructors to proper arguments. For instance, FatalError0() and FatalError1("division-by-zero") are two exception values (or simply exceptions). In the following program, a function for integer division is implemented:

// exception DivisionByZero of () // fun divexn(x: int, y: int): int = if y != 0 then x / y else $raise DivisionByZero() //

When the function call divexn(1, 0) is evaluated, the exception DivisionByZero() is raised. The keyword $raise in ATS is for raising an exception.

A raise-expression is of the form $raise(exp) for some expression exp. Clearly, if the evaluation of exp returns a value, then the evaluation of $raise(exp) leads to a raised exception. Therefore, the evaluation of a raise-expression can never return a value, and this justifies that a raise-expression can be given any type.

A raised exception can be captured. If it is not captured, the raised exception aborts the program evaluation that issued it in the first place. In ATS, a try-expression (or try-with-expression) is of the form (try exp with clseq), where try is a keyword, exp is an expression, with is also a keyword, and clseq is a sequence of matching clauses. When evaluating such a try-expression, we first evaluate exp. If the evaluation of exp leads to a value, then the value is also the value of the try-expression. If the evaluation of exp leads to a raised exception, then we match the exception against the guards of the matching clauses in clseq. If there is a match, the raised exception is caught and we continue to evaluate the body of the first clause whose guard is matched. If there is no match, the raised exception is uncaught. In a try-expression, the with-part is often referred to as an exception-handler.

Let us now see an example that involves raising and capturing an exception. In the following program, three functions are defined to compute the product of the integers in a given list:

fun listprod1 ( xs: list0(int) ) : int = ( case+ xs of | list0_nil() => 1 | list0_cons(x, xs) => x * listprod1(xs) ) (* end of [listprod1] *) fun listprod2 ( xs: list0(int) ) : int = ( case+ xs of | list0_nil() => 1 | list0_cons(x, xs) => if x = 0 then 0 else x * listprod2(xs) // end of [list0_cons] ) (* end of [listprod2] *) fun listprod3 ( xs: list0(int) ) : int = let exception ZERO of () fun aux(xs: list0(int)): int = case+ xs of | list0_nil() => 1 | list0_cons(x, xs) => if x = 0 then $raise ZERO() else x * aux(xs) // end of [list0_cons] // end of [aux] in try aux(xs) with ~ZERO() => 0 end // end of [listprod3]

While these functions can all be defined tail-recursively, they are not so as to make a point that should be clear shortly. Undoubtedly, we all know the following simple fact:

The function listprod1 is defined in a standard manner, and it does not make any use of the stated fact. The function listprod2 is defined in a manner that makes only partial use of the stated fact. To see the reason, let us evaluate a call to listprod2 on [1, 2, 3, 0, 4, 5, 6], which denotes a list consisting of the 7 mentioned integers. The evaluation of this call eventually leads to the evaluation of 1*(2*(3*(listprod([0,4,5,6])))), which then leads to 1*(2*(3*0)), and then to 1*(2*0), and then to 1*0, and finally to 0. However, what we really want is for the evaluation to return 0 immediately once the integer 0 is encountered in the list, and this is accomplished by the function listprod3. When evaluating a call to listprod3 on [1, 2, 3, 0, 4, 5, 6], we eventually reach the evaluation of the following expression:

try 1*(2*(3*(aux([0,4,5,6])))) with ~ZERO() => 0

Evaluating aux([0,4,5,6]) leads to the exception ZERO() being raised, and this raised exception is caught and 0 is returned as the value of the call to listprod3. Note that the pattern guard of the matching clause following the keyword with is ~ZERO(). I will explain the need for the tilde symbol ~ elsewhere. For now, it suffices to say that exn is a linear type and each exception value is a linear value, which must be consumed or re-raised. The tilde symbol ~ indicates that the value matching the pattern following ~ is consumed (and the memory for holding the value is freed).

Exceptions are not a programming feature that is easy to master, and misusing exceptions is abundant in practice. So please be patient when learning the feature and be cautious when using it.