2 Mar 2014 ssp   » (Master)

First Class Goto

Oort is an experimental programming language I have been working on, on and off (mostly off), since 2007. It is a statically typed, object-oriented, imperative language, where classes, functions and methods can be nested arbitrarily, where and functions and methods are full closures, ie., they can be stored in variables and returned from functions. The control structures are the usual ones: if, for, while, do, goto, etc.

It also has an unusual feature: goto labels are first class.

What does it mean for labels to be first class? It means two things: (1) they are lexically scoped so that they are visible from inside nested functions. This makes it is possible to jump from any point in the program to any other location that is visible from that point, even if that location is in another function. And (2) labels can be used as values: They can be passed to and returned from functions and methods, and they can be stored in data structures.

As a simple example, consider a data structure with a “foreach” method that takes a callback function and calls it for every item in the data structure. In Oort this might look like this:

table: array[person_t];

table.foreach (fn (p: person_t) -> void {
        print p.name;
        print p.age;
    });

A note about syntax. In Oort, anonymous functions are defined like this:

fn (<arguments>) -> <return type> {
    ...;
}

and variables and arguments are declared like this:

<name>: <type>

so the code above defines an anonymous function that prints the name and the age of person and passes that function to the foreach method of the table.

What if we want to stop the iteration? You could have the callback return true to stop, or you could have it throw an exception. However, both methods are a little clumsy: The first because the return value might be useful for other purposes, the second because stopping the iteration isn’t really an exceptional situation.

With lexically scoped labels there is a direct solution – just use goto to jump out of the callback:

  table.foreach (fn (e: person_t) -> void {
          print p.name;
          print p.age;

          if (p.age > 50)
              goto done;
      });

@done:

Note what’s going on here: Once we find a person older than 50, we jump out of the anonymous callback and back into the enclosing function. The git tree has a running example.

Call/cc in terms of goto
In Scheme and some other languages there is a feature called call/cc, which is famous for being both powerful and mind-bending. What it does is, it that it takes the concept of “where we are in the program” and packages it up as a function. This function, called the continuation, is then passed to another, user-defined, function. If the user-defined function calls the continuation, the program will resume from the point where call/cc was invoked. The mind-bending part is that a continuation can be stored in data structures and called multiple times, which means the call/cc invocation can in effect return more than once.

Lexically scoped labels are at least as expressive as call/cc, because if you have them, you can write call/cc as a function:

call_cc (callback: fn (k: fn()->void)) -> void
{
    callback (fn() -> void { 
        goto current_continuation;
    });

@current_continuation:
}

Let’s see what’s going on here. A function called call_cc() is defined:

call_cc (...) -> void
{
}

This function takes another function as argument:

callback: fn (...) -> void

And that function takes the continuation as an argument:

k: fn()->void

The body of call/cc calls the callback:

callback (...);

passing an anonymous function (the continuation):

    fn() -> void {
        goto current_continuation;
    }

@current_continuation:

that just jumps to the point where call_cc returns. So when callback decides to invoke the continuation, execution will resume at the point where call_cc was invoked. Since there is nothing stopping callback from storing the continuation in a data structure or from invoking it multiple times, we have the full call/cc semantics.

Cooperative thread system
One of the examples on the Wikipedia page about call/cc is a cooperative thread system. With the call_cc function above, we could directly translate the Wikipedia code into Oort, but using the second aspect of the first-class-ness of labels – that they can be stored directly in data structures – makes it possible to write a more straightforward version:

run_list: list[label] = new list[label]();

thread_fork (child: fn() -> void)
{
    run_list.append (me);
    child();
    goto run_list.pop_head();
@me:
}

thread_yield()
{
    run_list.append (me);
    goto run_list.pop_head ();
@me:
}

thread_exit()
{
    if (!run_list.is_empty())
        goto run_list.pop_head();
    else
        process_exit();
}

The run_list variable is a list of labels containing the current positions of all the active threads. The keyword label in Oort is simply a type specifier similar to string.

To create a new thread, thread_fork first saves the position of the current thread on the list, and then it calls the child function. Similarly, thread_yield yields to another thread by saving the position of the current thread and jumping to the first label on the list. Exiting a thread consists of jumping to the first thread if there is one, and exiting the process if there isn’t.

The code above doesn’t actually run because the current Oort implementation doesn’t support genericity, but here is a somewhat uglier version that actually runs, while still demonstrating the principle.

Syndicated 2014-03-02 00:00:00 from Søren Sandmann Pedersen

Latest blog entries     Older blog entries

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!