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
|
= Nickle Continuations
`poly setjmp ( continuation *c, poly retval )` +
`void lomgjmp ( continuation c, poly retval )`
Arbitrary flow control is accomplished in Nickle with first-class
continuations and the functions `setjmp` and `longjmp`. These are
similar to those in C, but without restrictions on the target.
Setjmp saves the state of the program, including program counter and
names in scope, in `c` and returns `retval`.
Longjmp returns `retval` from the setjmp that set _c_. There
can be two distinctions from this jump and the initial call to setjmp:
the return value may differ, and variables that have changed retain
their new values.
Continuations are often used to implement control structures that do
not exist in the language, interpreters, and escaping from recursive
algorithms. For example, the following is a simple binary tree search
that uses continuations to jump directly to the top instead of
returning up each branch once the result is found.
Here's a binary search function, but instead of unwinding the
recursion once the item is found, it uses longjmp to escape
in one call.
[source,c]
----
typedef struct {
int key;
poly data;
&poly left, right;
} tree;
void _search ( tree t, int key, &continuation c ) {
if ( key < t.key && ! is_void ( t.left ) )
_search ( t.left, key, &c );
else if ( key > t.key && ! is_void ( t.right ) )
_search ( t.right, key, &c );
else if ( key == t.key )
longjmp ( c, t.data );
}
poly search(tree t, int key) {
continuation c;
poly p = setjmp ( &c, <> );
if ( is_void ( p ) )
_search ( t, key, &c );
return p;
}
tree t = { key = 2, data = "blah", left = reference ( <> ), right = reference ( <> ) };
find(t, 2)
----
This is a pretty normal binary tree search, but notice how it is run:
a continuation is set; if setjmp returns `<>` (which it will the first
time), a value is searched for. If an actual value is returned, it
must be from the longjmp in search, and the value is returned. This
optimizes the return from what can be a very deeply nested search.
This sort of escape from a nested search can also be done with
exceptions, raising one when the value is found and catching it at the
top, passing the value as an argument to the exception.
|
