|
996
|
1 Alex Smith, 2008
|
|
|
2
|
|
|
3 continuation.i is a continuation library for INTERCAL, and a small
|
|
|
4 program at the end to demonstrate how it is used and as a test. (Your
|
|
|
5 most likely use of this is to delete the test program at the end and
|
|
|
6 use the rest as a library in your own source code.) It requires at
|
|
|
7 least the command line options -am to work (so is unfortunately, but
|
|
|
8 inevitably, incompatible with -e). All line numbers in the library
|
|
|
9 part are in the range 8200-8299; there's a dependence on syslib, but
|
|
|
10 only for (1020), so it would be easy to make it a truly independent
|
|
|
11 library. I have avoided computed COME FROM in writing it, because its
|
|
|
12 performance is bad enough as it is, and NEXT FROM didn't turn up, but
|
|
|
13 there is a lot of ABSTAINING, REINSTATING, COMING FROM and NEXTING
|
|
|
14 going on in the code, as well as ONCE and AGAIN (this time I used both
|
|
|
15 of them; AGAIN is normally more useful but ONCE works better for
|
|
|
16 mutexes) and lots and lots of threading.
|
|
|
17
|
|
|
18 A continuation is a copy of the internal state of a program, that can
|
|
|
19 be rewound back to at a later stage. What exactly is copied depends on
|
|
|
20 the language; in INTERCAL, it's everything except the abstention
|
|
|
21 status of commands, as you might expect.
|
|
|
22
|
|
|
23 As INTERCAL doesn't have first-class functions, continuations are
|
|
|
24 represented by onespot numbers; they can send a single one-spot number
|
|
|
25 as their return value (and more data can be sent by ABSTAINING FROM
|
|
|
26 things in a prearranged pattern).
|
|
|
27
|
|
|
28 The library CREATEs three statements:
|
|
|
29
|
|
|
30 GET CONTINUATION IN .1 GETTING .2
|
|
|
31
|
|
|
32 This statement creates a continuation, storing a number that can be
|
|
|
33 used to access it later in .1, and leaves .2 untouched. If that
|
|
|
34 continuation is invoked later, the statement will instead appear to
|
|
|
35 be equivalent to a RESUME #1, but after setting the value of .2 to be
|
|
|
36 whatever value was sent when invoking the continuation (note that only
|
|
|
37 onespot-range values can be sent). So:
|
|
|
38
|
|
|
39 DO (3) NEXT
|
|
|
40 (1) DO GET CONTINUATION IN .1 GETTING .2
|
|
|
41 <do things here>
|
|
|
42 (2) DO FORGET #1
|
|
|
43 (3) DO (1) NEXT
|
|
|
44
|
|
|
45 is effectively a call/cc to <do things here>, with .1 being used as
|
|
|
46 its argument and .2 as its return value. (There are other equivalent
|
|
|
47 ways to properly guard this statement; one simple one is to put the
|
|
|
48 GET CONTINUATION call just /inside/ the procedure that's call/ccd.)
|
|
|
49
|
|
|
50 DO CONTINUE WITH .1 SENDING .2
|
|
|
51
|
|
|
52 This statement invokes a continuation, returning the program to the
|
|
|
53 time that it was created. The first argument is the continuation
|
|
|
54 number (not supplying a number that corresponds to a continuation is
|
|
|
55 undefined behaviour, but most likely an infinite loop); the second
|
|
|
56 argument is a onespot number to send back as 'payload', which will be
|
|
|
57 assigned to the second argument of the GET CONTINUATION IN command
|
|
|
58 that created the continuation in the first place.
|
|
|
59
|
|
|
60 DO KILL ALL THREADS
|
|
|
61
|
|
|
62 Because the continuation system creates a whole load of threads to do
|
|
|
63 its work, a normal GIVE UP will not end the program. Instead, this is
|
|
|
64 provided as an alternative; it's a horrible hack but will usually work
|
|
|
65 if no threads are inside the system library at the time, or after the
|
|
|
66 last PLEASE GIVE UP in the program. (I may implement a DO ABSTAIN FROM
|
|
|
67 ONCING at some point, which would make it possible to make this sort
|
|
|
68 of thing a lot more robust.)
|
|
|
69
|
|
|
70
|
|
|
71 There are several interesting features of the program. The start shows
|
|
|
72 how to CREATE statements that can take a range of different argument
|
|
|
73 types; here I've chosen to cause the GET CONTINUATION statement to
|
|
|
74 accept only lvalues that don't require reverse assignment, and the
|
|
|
75 CONTINUE statement to accept any expression.
|
|
|
76
|
|
|
77 A separate thread is used to keep track of the lowest unused
|
|
|
78 continuation number; it shows how to implement a truly global variable
|
|
|
79 in INTERCAL, and the relevant code (from 8250 to 8299) may be useful
|
|
|
80 in its own right. The routines at (8276) and (8277) are an improvement
|
|
|
81 over those in pass.i in terms of length, and show how to implement the
|
|
|
82 INTERCAL equivalent of a named pipe (that is, data flows along it when
|
|
|
83 one end is being read by one thread and the other end is being read by
|
|
|
84 another thread). The ability to stash/retrieve the global variable
|
|
|
85 (which is remarkably simple to do the way I've implemented it) is also
|
|
|
86 used; see below.
|
|
|
87
|
|
|
88 Continuations are themselves implemented as separate threads, each of
|
|
|
89 which spends most of its time in an infinite loop at (8211); they're
|
|
|
90 created by the simple method of determining a unique number, and
|
|
|
91 splitting off a thread. Most of the non-global-variable-implementing
|
|
|
92 part of the library is taken up with the code for invoking or
|
|
|
93 'unfreezing' a continuation thread. When (8210) is invoked (i.e. the
|
|
|
94 implementation of the CONTINUE command), it STASHes the global
|
|
|
95 variable and assigns the continuation number to it. It then releases
|
|
|
96 the loop at 8211, and all the remaining threads simultaneously (due to
|
|
|
97 the timing guarantees) start trying to read the global variable. There
|
|
|
98 are two problems to overcome: first, the fact that they can't all read
|
|
|
99 the global variable at once (this is solved by the routine (8275),
|
|
|
100 which shows how to use ONCE to implement a mutex), and second, the
|
|
|
101 fact that each thread needs to wait until all the others have finished
|
|
|
102 reading before continuing (because otherwise a fast series of
|
|
|
103 continuation operations in the main program could try to access a
|
|
|
104 thread before it was ready). The second problem is solved by a limited
|
|
|
105 kind of semaphore on the line (8214); its abstention count is
|
|
|
106 incremented by each thread before it starts reading (almost
|
|
|
107 simultaneously due to the timing restrictions), and decreased once the
|
|
|
108 thread has finished. All the threads then block until all of them have
|
|
|
109 finished, which they can do by monitoring the semaphore until it
|
|
|
110 reaches 0. (Normal semaphores can also block below 0 as well as
|
|
|
111 unblocking at 0.) This method means that the threads don't need to
|
|
|
112 know how many other threads are available. The thread that is being
|
|
|
113 unfrozen then RETRIEVES the global variable, uses (8276) and (8277)
|
|
|
114 with the thread that called CONTINUE to get the payload value, then
|
|
|
115 the original CONTINUE-calling thread dies and the unfrozen thread
|
|
|
116 continues in its place.
|
|
|
117
|
|
|
118 Of course, all this thread creation is completely lousy from a
|
|
|
119 performance perspective. Maybe some day I should try to optimise
|
|
|
120 spinlocks somehow...
|
