1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
|
[Note: need to come up with an answer to the expression-with-goto-in-it
problem - see TODO];
Go To Statement Considered Powerful
Oort is a programming language I have been working on, on and off
(mostly off), since 2007. It is a statically typed, object-oriented,
imperative language with a set of features that one has come to
expect: Classes, functions and methods can be nested arbitrarily, and
functions and methods are full closures, ie., they can be stored in
variables and returned from functions.
It also has an unusual feature that to my knowledge isn't present in
any other language: goto labels are *first class* [1].
What does it mean for labels to be first class? It means they can be
used as values. They can be stored in data structures and returned
from functions. They are lexically scoped, so they are visible from
inside nested functions.
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 Sprog this might look like this:
table: array[employee];
table.foreach (fn (e: employee) -> void {
print e.name;
print e.age;
});
A note about syntax. In Sprog, anonymous functions are defined like this:
fn (<arguments>) -> <return type> {
...;
}
so the code above defines an anonymous function that prints the name
and the age of an employee and passes that function to the foreach
method of the table.
What if we want to stop the iteration? In some languages the iterator
function should return true when if it wishes the iteration to
stop. In others, you are expected to throw an exception. With first
class labels there is a simple solution. Just use goto to jump out of
the callback:
table.forech (fn (e: employee) -> void {
if (e.name == "Soren")
goto done;
});
@done:
In Scheme and some other languages there is a feature called call/cc,
which is famous for being both powerful and mind-bending. What is 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 call/cc can in effect return more than
once.
It turns out that first-class goto labels are at least as expressive,
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 (...);
with an anonymous function (the continuation):
fn() -> void {
goto current_continuation;
}
@current_continuation:
that jumps to the point where call_cc returns. So when callback
decides to invoke the anonymous function, 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.
One of the examples on the Wikipedia page about call/cc is a
cooperative thread system. With the call_cc() function above, we could
easily translate the Wikipedia code into Oort, but using the fact that
first class labels can be directly stored 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.push_back (me);
child();
@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 is a list of the current positions of all the active
threads. To create a new thread, we first save our own current
position on the list and then we call the child function. To yield to
another thread, we save our own position and jump to the next thread
on the list. Exiting consists of jumping to the first process if there
is one, and exiting the process if there isn't.
The code above doesn't actually run because the current Oort
implementation is lame and doesn't support genericity, but [here] is a
somewhat uglier version that still demonstrates the principle while
also actually running.
[1] GCC has an extension to the C langauge that is sometimes called
"first class labels", but these are not first class at all since they
cannot 'escape' from functions and don't represent real continuations
in the sense of call/cc.
|
