draft of shift reset talk
Hi, my name's Johnicholas, I am going to tell you about implementing delimited continuations in Soar.
There are several possible motivations for working on this, but one of them is as a strategy for concurrency in Soar. Concurrency is distinct from parallel computation. Concurrency is the difficulty of dealing with a parallel world. One strategy is rapidly interleaving thinking about different concerns - for example, pursuing your own goals while also keeping track of the world. Here the real parallelism is that the entire world can be divided into two pieces, the part outside, far away or out of the agent's control, and the part internal or nearby and under the agent's control. That real parallelism causes a requirement of concurrency.
In the Michigan style, you deal with concurrency by identifying your subgoal hierarchy with the architectural stack but being prepared for your current subgoal hierarchy to be destroyed. If you don't want to start over at the beginning of the task again, then you keep some information about where you are in the task on the top state.
To mischaracterize Michigan style somewhat, this is like a code style that forbids local variables, and starts the body of each function with a switch (on a global) that dispatches control flow to the appropriate spot in the body.
void foo() {
int x = bar();
return baz(x);
}
becomes something like:
int foo_state;
int foo_x;
void foo() {
switch (foo_state) {
case 0: foo_x = bar(); foo_state += 1; break;
case 1: return baz(foo_x); break;
}
}
This is recognizably something called 'stack ripping' (See Krohn et al. 'Events can make sense'). There's a couple reasons why this is more pleasant in Soar than it is in C. In C you have nice built-in primitive syntax for doing several things sequentially, conditionals, loop constructs. When you switch to the stack-ripped style, you have to reinvent those using flags and state variables. However, Soar didn't have those primitives to begin with - you were already using flags and state variables to route control flow, they're just on the top state rather than the substate. In C you would have to do something fancy in order to make recursion work with stack-ripped functions. In Soar (if you understand the Goal Dependency system, which I certainly do not) I believe you can "modify" the top state and have the GDS magically restore the previous value. However, there is a problem of modularity - when you put those locals up on the top state, then you have to pick names for them, which is somewhat unpleasant, even in Soar.
In the NGS style, you deal with concurrency by making your subgoal structure (which might be hierarchical or perhaps something else) an explicit data structure, separate from the architectural stack. This means that NGS agents do not chunk over subgoals. This is similar to expert agents, which also do not chunk over subgoals (because they're already chunked).
Delimited, a.k.a. composable continuations are nonlocal control flow operators (yes, like goto, and they're dangerous like goto). The best way to understand them is by analogy to system calls, which return control flow from a specific process back to a boundary (the kernel/userspace boundary), and convey some information, such as what the process is trying to do, including the process's current state in sufficient detail that the kernel can resume the process.
I don't have very much time, let me start explaining the demo. The demo is based on Simon Tatham's coroutines example (TODO: cite). There is a run length decompressor that reads characters, and if there is a sequence of three characters, a special marker byte, a count, and a literal byte, then it replaces those three with a run, repeating the literal byte according to the count. Then there's a lexer, that reads characters and groups them into identifiers (sequences of alphabetic characters) or punctuation (everything else). The point is that both processes have a little bit of state.
If we were writing either one as a single agent, we might put input and output operators at the fringe of the (very simple) operator tree. If we were writing the combination from scratch then we might use Jackson inversion (TODO: cite) on one or the other. But if we want to avoid Jackson inversion, then we can write a top level "operating system" or scheduler that creates a "kernel-userspace boundary" using reset, and replace the input and output operators at the fringe with "system calls" that use shift.
...actually showing the demo...
The major problem with this implementation is that though it does demonstrate shift and reset, and it does do mildly interesting chunking over shift and reset, the two coroutines are not general Soar agents, they're written in a call-by-value lambda calculus, which is written in Soar. So the section of the stack that shift captures isn't a section of an arbitrary Soar stack - it's a known set of possible states, all of which are written with an awareness that they need to be compatible with delimited continuations. I believe it would be possible (if I were more expert) to write real shift and reset for general Soar states.
Another problem is that the environment is currently implemented as an association list, which causes the generated chunks to undergeneralize. They depend on the ordering of the association list, which is irrelevant. However, it's not that bad because the ordering is also pretty stable.
Future work: I'd like to implement Shift and Reset for general soar states. I'd like to write something more like Kiselyov and Shan's ZipperFS, a more operating-system-like kernel than my current 'connect two coroutines together' (though it's still very small). I'd like to do discrete event simulation where different entities have different processes. I'd like to write an agent that, as part of its strategy for acting in the outer world, simulates an agent and a world interacting as coroutines. Continuations can be used for backtracking and for partial evaluation; it would be interesting to see what those look like from Soar.
There's another reason, of course, to practice putting operational semantics into Soar - as part of teaching Soar to write code.
There are several possible motivations for working on this, but one of them is as a strategy for concurrency in Soar. Concurrency is distinct from parallel computation. Concurrency is the difficulty of dealing with a parallel world. One strategy is rapidly interleaving thinking about different concerns - for example, pursuing your own goals while also keeping track of the world. Here the real parallelism is that the entire world can be divided into two pieces, the part outside, far away or out of the agent's control, and the part internal or nearby and under the agent's control. That real parallelism causes a requirement of concurrency.
In the Michigan style, you deal with concurrency by identifying your subgoal hierarchy with the architectural stack but being prepared for your current subgoal hierarchy to be destroyed. If you don't want to start over at the beginning of the task again, then you keep some information about where you are in the task on the top state.
To mischaracterize Michigan style somewhat, this is like a code style that forbids local variables, and starts the body of each function with a switch (on a global) that dispatches control flow to the appropriate spot in the body.
void foo() {
int x = bar();
return baz(x);
}
becomes something like:
int foo_state;
int foo_x;
void foo() {
switch (foo_state) {
case 0: foo_x = bar(); foo_state += 1; break;
case 1: return baz(foo_x); break;
}
}
This is recognizably something called 'stack ripping' (See Krohn et al. 'Events can make sense'). There's a couple reasons why this is more pleasant in Soar than it is in C. In C you have nice built-in primitive syntax for doing several things sequentially, conditionals, loop constructs. When you switch to the stack-ripped style, you have to reinvent those using flags and state variables. However, Soar didn't have those primitives to begin with - you were already using flags and state variables to route control flow, they're just on the top state rather than the substate. In C you would have to do something fancy in order to make recursion work with stack-ripped functions. In Soar (if you understand the Goal Dependency system, which I certainly do not) I believe you can "modify" the top state and have the GDS magically restore the previous value. However, there is a problem of modularity - when you put those locals up on the top state, then you have to pick names for them, which is somewhat unpleasant, even in Soar.
In the NGS style, you deal with concurrency by making your subgoal structure (which might be hierarchical or perhaps something else) an explicit data structure, separate from the architectural stack. This means that NGS agents do not chunk over subgoals. This is similar to expert agents, which also do not chunk over subgoals (because they're already chunked).
Delimited, a.k.a. composable continuations are nonlocal control flow operators (yes, like goto, and they're dangerous like goto). The best way to understand them is by analogy to system calls, which return control flow from a specific process back to a boundary (the kernel/userspace boundary), and convey some information, such as what the process is trying to do, including the process's current state in sufficient detail that the kernel can resume the process.
I don't have very much time, let me start explaining the demo. The demo is based on Simon Tatham's coroutines example (TODO: cite). There is a run length decompressor that reads characters, and if there is a sequence of three characters, a special marker byte, a count, and a literal byte, then it replaces those three with a run, repeating the literal byte according to the count. Then there's a lexer, that reads characters and groups them into identifiers (sequences of alphabetic characters) or punctuation (everything else). The point is that both processes have a little bit of state.
If we were writing either one as a single agent, we might put input and output operators at the fringe of the (very simple) operator tree. If we were writing the combination from scratch then we might use Jackson inversion (TODO: cite) on one or the other. But if we want to avoid Jackson inversion, then we can write a top level "operating system" or scheduler that creates a "kernel-userspace boundary" using reset, and replace the input and output operators at the fringe with "system calls" that use shift.
...actually showing the demo...
The major problem with this implementation is that though it does demonstrate shift and reset, and it does do mildly interesting chunking over shift and reset, the two coroutines are not general Soar agents, they're written in a call-by-value lambda calculus, which is written in Soar. So the section of the stack that shift captures isn't a section of an arbitrary Soar stack - it's a known set of possible states, all of which are written with an awareness that they need to be compatible with delimited continuations. I believe it would be possible (if I were more expert) to write real shift and reset for general Soar states.
Another problem is that the environment is currently implemented as an association list, which causes the generated chunks to undergeneralize. They depend on the ordering of the association list, which is irrelevant. However, it's not that bad because the ordering is also pretty stable.
Future work: I'd like to implement Shift and Reset for general soar states. I'd like to write something more like Kiselyov and Shan's ZipperFS, a more operating-system-like kernel than my current 'connect two coroutines together' (though it's still very small). I'd like to do discrete event simulation where different entities have different processes. I'd like to write an agent that, as part of its strategy for acting in the outer world, simulates an agent and a world interacting as coroutines. Continuations can be used for backtracking and for partial evaluation; it would be interesting to see what those look like from Soar.
There's another reason, of course, to practice putting operational semantics into Soar - as part of teaching Soar to write code.