Advanced Flow Control

The basic control flow expressions in Slogan are the if and when conditions. Recursion and the imperative for loop construct also enable control flow, but they depend on the conditional expressions for their implementation. Conditional expressions are important in another way – they enable the implementation of a basic error handling mechanism. For example, this is how we may implement a (hypothetical) function that tries to open a file:

function open_file(file_name)
  if (file_exists(file_name))
  else false

The callers of this function should handle a case where the file is missing with an if expression:

let (f = open_file("some_file"))
  if (f) do_something_to_the_file(f)
  else showln("failed to open file")

This is the declarative way to deal with exceptional situations like trying to open a nonexistent file, dividing by zero etc. But it is cumbersome and error prone to add checks throughout the program. An elegant alternative is to add an exception-handling mechanism to the language. In the first section of this chapter, we will learn about exception-handling in Slogan. Later we will learn how to design abstractions that can control program flow in any way imaginable!

10.1 Exceptions

When an expression cannot be evaluated correctly, we often speak of "raising an error". But what should this statement exactly do? It should, in a controlled way, transfer execution to another part of the program that knows how to deal with the error, without crashing the running program. This part of the program that specializes in dealing with errors is known as the exception handler. While an error is thrown, a value describing the error is passed to the exception handler.

Slogan's exception handling mechanism is designed around the error confinement principal which states that the error in a component should be catchable at the component boundary. Outside the component, the error is either invisible or reported in a nice way. That means raising an error will cause the program control to "jump" from inside the component to its boundary. This is a single operation, able to exit from arbitrarily many levels of nested context1.

In Slogan, the function raise is the basic mechanism for raising exceptions. The try-catch expression is used for handling raised exceptions. Try-catch has the following general syntax:

catch (err)

The expression expr can raise an error by calling raise() with an arbitrary object as argument. This object represents the error condition and is passed as argument to catch. The handle_err_expr is an expression that should decide what to do about the error object.

As an example of using exceptions in practice, consider an implementation of the stack data type. We can implement a stack on top of an array, the size of which is specified when the stack is created. An attempt to push more items than the stack can hold will be blocked by raising an error. Similarly, an attempt to remove an item from an empty stack will also raise an error.

function make_stack(size)
  let (elems = make_array(size),
       index = 0)
  { function push(e)
      if (index >= size)
        raise("too many elements")
      { elems[index] = e
        index = index + 1 }

    // Return the top element.
    function top()
      if (index == 0)
        raise("empty stack")
      else elems[index - 1]

    // Remove and return the top element.
    function pop()
      if (index == 0)
        raise("empty stack")
      else let (e = elems[index - 1])
      { index = index - 1
        e }

    | 'push -> push
    | 'top -> top
    | 'pop -> pop
    | _ -> raise("invalid message") }

Any attempt to violate the invariants on a stack object will be prevented by the raising errors.

let s = make_stack(3)
// 23
// 23
// 10
//> error: This object was raised: "empty stack"

Using exception handlers, we can contain and deal with such exceptions in a cleaner way. The following function implements a "safer" alternative to pop stack. It handles the error by logging it to the console and returning a default value to the caller:

function safe_pop(stack, @optional default)
  catch (err)
  { showln("stack error: ", err)
    default }

//> stack error: empty stack
// false

safe_pop(s, 10)
//> stack error: empty stack
// 10

// 100

Code that handles exceptions may not get enough information about the error, if that has been thrown by a call to raise(obj). The argument to raise can be an arbitrary object, it may not even be a string. So the exception handler should know how to interpret the error object beforehand to do proper error logging and handling. The function error can help make life easier for code that has to process information about errors.

Instead of raising an arbitrary object, the error function always raises an object of type error-exception record which has a message field and a list of "argument" fields which can contain additional information about the error.

10.1.1 Performing Cleanup

A try expression can specify a finally clause which is always executed, whether or not the expression raises an exception. This is useful when dealing with entities that are managed external to the language runtime. With finally, we can guarantee that some "cleanup" action gets performed on the entity, whether or not an exception occurs. An example of such an external entity is the handle to an open file, which is a limited resource managed by the operating system. The program must make sure it returns this handle back to the operating system by closing the file handle, even if an exception was raised while using (reading/writing) it.

let f = false          
{ f = file_reader("abc.txt")
  read_all_chars(f) }
catch (err)
  showln("failed to read file - ", err)
  when (f)
  { showln("closing file...")
    close_reader(f) }

If you want the exception to be handled in an outer layer, you can omit the catch clause. This will cause the exception to be re-raised, after the finally clause is executed.

let f = false          
{ f = file_reader("abc.txt")
  read_all_chars(f) }
  when (f)
  { showln("closing file...")
    close_reader(f) }

Mixing file operations and exception handling leads to lot of boilerplate code. Slogan provide abstractions that let us express input/output operations in a concise, declarative style. The call_with_stream function is one such abstraction.

10.2 Abstracting Control Flow

So far in this book we have discussed quite a few programming constructs that can control how the program flows - the if and when expressions, the try-catch expression, the yield statement, the imperative for loop and so on. You might have encountered some or all of these in other languages as well. Programming language designers will bake in those control structures they feel are the only ones their users will ever need. When programmers talk about a language being "extensible" what they mean is that the language allows them to define new data abstractions. Can a language be extensible in the sense that users can add new control structures to the language? This is the question we are dealing with in this section.

A language with higher-order functions can define functions that behave like built-in control structures. For example, the following program defines a function that behaves like the while loop found in most imperative programming languages:

function while(cond, body)
  when (cond())
  { body()
    while(cond, body) }

While() take two functions as arguments. The first one return true as long as a particular condition holds. The second function is called if the condition holds and while is called again recursively, creating the effect of a loop. Here is how we would use our new looping construct:

let i = 0
while (^() i < 5,
       ^() { showln(i); i = i + 1 })
//> 0

"Functional" control structures like this one have two immediate problems. First is that, they do not introduce new "syntax" to the language. Invoking them are basically just function calls and building their function arguments can be verbose. The construct might be cleaner and easier to use if users are allowed to type something like:

while (i < 5)
{ showln(i)
  i = i + 1 }

The second problem is that a function is not allowed to return to and execute code in an arbitrary position in the program. This flexibility is required for implementing constructs like try-catch and yield. Slogan exposes the ability to completely control the execution order of instructions as a first-class language entity. This will allow users to build control structures that have the same power and expressiveness as the ones that are baked into the language.

10.2.1 Continuations

During the evaluation of an expression, Slogan needs to keep track of two things - (1) what to evaluate and (2) what to do with the value. Consider the evaluation of is_empty(x) within the expression below.

if (is_empty(x))

Slogan has to first evaluate is_empty(x) and, based on the result, evaluate either 'empty or head(x). "What to evaluate?" is is_empty(x) and "what to do with the value?" is to choose between 'empty and head(x) to evaluate next. The "what to do with the value?" is the continuation of the computation.

Slogan allows the continuation of any expression to be captured with the function callcc (for call_with_current_contiunuation). Callcc must be passed a function f of one argument. Callcc constructs a concrete representation of the current continuation and passes it to f. The continuation itself is represented by a function k. Each time k is applied to a value, it returns the value to the continuation of the callcc application. This value becomes, in essence, the value of the application of callcc.

If f returns without invoking k, the value returned by the function becomes the value of the application of callcc.

Let us consider a few simple examples.

callcc(^(k) 5 * 4)
// 20
callcc(^(k) 5 * k(4))
// 4
2 + callcc(^(k) 5 * k(4))
// 6

In the first example, the continuation is captured and bound to k, which is never used. So the value is simply the product of 5 and 4. In the second, the continuation is invoked before the multiplication, so the value is the value passed to the continuation, 4. In the third, the continuation includes the addition by 2; thus, the value is the value passed to the continuation, 4, plus 2.

Here is a less trivial example, showing the use of callcc to provide a nonlocal exit from a recursion.

function product(xs)
     letfn loop(xs = xs)
       if (is_empty(xs)) 1
       else if (is_zero(head(xs))) return(0)
       else head(xs) * loop(tail(xs)))

product([1, 2, 3, 4, 5])
// 120
// 0

The nonlocal exit allows product to return immediately, without performing the pending multiplications, when a zero value is detected.

In the chapter on designing new languages, we will complete our journey into building new control abstractions. There we will implement a whole new sub-language in Slogan that will enable us to write nondeterministic programs.

1In our case, "components" are mostly functions and "nested contexts" are created by function calls.

Next | Previous | Contents