my delimited continuations in soar talk
My slides and my demo video.
Hi.
My name is Johnicholas.
I'm here to tell you about delimited continuations in Soar.
Delimited Continuations are an idea from functional programming. They can be used for concurrency.
I need to clarify, in case anyone is confused
Concurrency is not parallelism.
Parallelism is like having two or more brains,
and trying to do the same thing only faster.
It's very hard, and perhaps John Laird has some insights.
Concurrency is a feature of the domain,
something that makes some domains harder than other domains,
like, say, partial observability or stochastic dynamics.
Concurrency is like having two hands, and needing to do something with one hand,
then context switch and do something with the other hand.
Benefits of concurrency, I don't know why I induded this slide, I'm not going to be able to do all this.
Problems of concurrency. Okay, suppose that a newbie Soar programmer like me is trying to attack a concurrent task. They shoehorn the concurrent task into a rigid explicit task hierarchy, and artificially promote one task, over the other task, WITHOUT using one of the well-thought-out approaches to concurrency, either the Michigan Approach or NGS. They're gonna have a bad time. One of their problems is that now the supertask has an additional non-functional requirement, it needs to run the subtask "often enough". That requirement makes the software engineering of the supertask more difficult. Another of their problems is now the subtask has to choose a stable place to store its state in between invocations - before you say the top state, it could be anywhere that is sufficiently stable. If there are other a third, fourth, or fifth concurrent task, then you might need to allocate namespaces so that they don't step on each other. If there are an arbitrary number of concurrent tasks, finding where they should put their states becomes a big headache.
I'm not going to be able to tell you precisely what the rules of delimited continuations are in this 15 minutes.
But I can tell you what delimited continuations are LIKE.
Imagine an operating system. There's a kernel, there's a kernel/userspace boundary, there's userspace apps, and then there are system calls. The system calls return control flow to the kernel, but they don't just return, they also communicate a package representing the state of the userspace, in particular the stack. That package could be considered a task control block, containing opaque data sufficient to resume the task.
I would like to be able to pick up a chain of arbitrary Soar states, and tuck them safely away in a data structure, and then unpack that chain to resume the task. I'm sorry, I don't know how to do that. But I do have an interpreter, so non-arbitrary Soar states are okay. The interpreter is based on an operational semantics of lambda calculus with shift and reset - there are 15 simple, concrete rules.
The demo is based on an example by Simon Tatham of coroutines. The left task is a run-length decompressor, most of the time it copies its input to its output, except if it sees a special sentinel byte, 123. If it sees that then it reads a count and a byte to repeat, and expands it into a run. The right task is a "parser" really more of a lexer that reads its input and classifies it into punctuation and contiguous sequences of alphabetic characters. The point is that both of these have an outer loop and an inner loop, so you would probably implement them using a little bit of hierarchy.
Now here's the demo - you're going to have to squint in order to see anything interesting here, I apologize. First we run the unit tests. They're all green. Then we run the agent, and you can see the initial ragged edge - that's creating the program in working memory; it could be a single initialize production, but it would be large and difficult to debug, and I was writing it by hand, so I create it in bits and pieces. Then we run the program itself, and you can see that there are ALMOST no substates; but there are some. Then it waits for input. We put in 64, that's an @ sign, and run the agent, and the decompressor copies it to the parser, and the parser says it's punctuation. Then we put in 75, thats a capital H, and the decompressor copies it to the parser, and the parser copies it to the output and doesn't classify it as anything because we're not at the end of the word yet. Then we put in 123, which is the sentinel value marking the start of a run, and a count 4, and a letter to repeat 76 that's capital I, and then the decompressor expands that to 4 75s which go through the parser. So here we're bouncing between an inner loop of one task and an inner loop of the other task. Then we put in another @ sign, and that ends the word, and then it classifies the final @ sign as punctuation.
So the gold and coal is:
This is work towards a general-purpose cooperative task library that provides a learning story for NGS. I believe NGS corresponds expert-level cooperative multitasking and delimited continuations are one way to do novice-level cooperative multitasking, which results in something like NGS after chunking. Also, implementing operational semantics of little languages in Soar is easy, educational and fun.
On the coal side, however,
the example demonstrating concurrency is not very agentish. Or perhaps VERY not-agentish.
Also, the example is fragile, brittle, and arcane; I don't think the interpreter itself is fragile or brittle, but I can't prove it.
In future work, people often use delimited continuations to build backtracking search. Soar has its own traditional way to do backtracking search, and it would be interesting to compare them.
My current scheduler component is not very interesting - it is specialized to exactly two tasks connected by a pipe. It would be more interesting to have an arbitrary number of tasks, something like Kiselyov and Shan's ZipperFS.
A discrete event simulation is basically a very-concurrent system - an agent using delimited continuations to systematically take the perspective of everything in the simulation might be interesting.
There's two kinds of barriers - the kernel/userspace boundary, and the relationship between one app and another app. Soar does not have a lot of techniques for isolating one module from another. It's possible that tasks that sit underneath a well-known scheduler interface would be more composable, forming reusable libraries.
Hi.
My name is Johnicholas.
I'm here to tell you about delimited continuations in Soar.
Delimited Continuations are an idea from functional programming. They can be used for concurrency.
I need to clarify, in case anyone is confused
Concurrency is not parallelism.
Parallelism is like having two or more brains,
and trying to do the same thing only faster.
It's very hard, and perhaps John Laird has some insights.
Concurrency is a feature of the domain,
something that makes some domains harder than other domains,
like, say, partial observability or stochastic dynamics.
Concurrency is like having two hands, and needing to do something with one hand,
then context switch and do something with the other hand.
Benefits of concurrency, I don't know why I induded this slide, I'm not going to be able to do all this.
Problems of concurrency. Okay, suppose that a newbie Soar programmer like me is trying to attack a concurrent task. They shoehorn the concurrent task into a rigid explicit task hierarchy, and artificially promote one task, over the other task, WITHOUT using one of the well-thought-out approaches to concurrency, either the Michigan Approach or NGS. They're gonna have a bad time. One of their problems is that now the supertask has an additional non-functional requirement, it needs to run the subtask "often enough". That requirement makes the software engineering of the supertask more difficult. Another of their problems is now the subtask has to choose a stable place to store its state in between invocations - before you say the top state, it could be anywhere that is sufficiently stable. If there are other a third, fourth, or fifth concurrent task, then you might need to allocate namespaces so that they don't step on each other. If there are an arbitrary number of concurrent tasks, finding where they should put their states becomes a big headache.
I'm not going to be able to tell you precisely what the rules of delimited continuations are in this 15 minutes.
But I can tell you what delimited continuations are LIKE.
Imagine an operating system. There's a kernel, there's a kernel/userspace boundary, there's userspace apps, and then there are system calls. The system calls return control flow to the kernel, but they don't just return, they also communicate a package representing the state of the userspace, in particular the stack. That package could be considered a task control block, containing opaque data sufficient to resume the task.
I would like to be able to pick up a chain of arbitrary Soar states, and tuck them safely away in a data structure, and then unpack that chain to resume the task. I'm sorry, I don't know how to do that. But I do have an interpreter, so non-arbitrary Soar states are okay. The interpreter is based on an operational semantics of lambda calculus with shift and reset - there are 15 simple, concrete rules.
The demo is based on an example by Simon Tatham of coroutines. The left task is a run-length decompressor, most of the time it copies its input to its output, except if it sees a special sentinel byte, 123. If it sees that then it reads a count and a byte to repeat, and expands it into a run. The right task is a "parser" really more of a lexer that reads its input and classifies it into punctuation and contiguous sequences of alphabetic characters. The point is that both of these have an outer loop and an inner loop, so you would probably implement them using a little bit of hierarchy.
Now here's the demo - you're going to have to squint in order to see anything interesting here, I apologize. First we run the unit tests. They're all green. Then we run the agent, and you can see the initial ragged edge - that's creating the program in working memory; it could be a single initialize production, but it would be large and difficult to debug, and I was writing it by hand, so I create it in bits and pieces. Then we run the program itself, and you can see that there are ALMOST no substates; but there are some. Then it waits for input. We put in 64, that's an @ sign, and run the agent, and the decompressor copies it to the parser, and the parser says it's punctuation. Then we put in 75, thats a capital H, and the decompressor copies it to the parser, and the parser copies it to the output and doesn't classify it as anything because we're not at the end of the word yet. Then we put in 123, which is the sentinel value marking the start of a run, and a count 4, and a letter to repeat 76 that's capital I, and then the decompressor expands that to 4 75s which go through the parser. So here we're bouncing between an inner loop of one task and an inner loop of the other task. Then we put in another @ sign, and that ends the word, and then it classifies the final @ sign as punctuation.
So the gold and coal is:
This is work towards a general-purpose cooperative task library that provides a learning story for NGS. I believe NGS corresponds expert-level cooperative multitasking and delimited continuations are one way to do novice-level cooperative multitasking, which results in something like NGS after chunking. Also, implementing operational semantics of little languages in Soar is easy, educational and fun.
On the coal side, however,
the example demonstrating concurrency is not very agentish. Or perhaps VERY not-agentish.
Also, the example is fragile, brittle, and arcane; I don't think the interpreter itself is fragile or brittle, but I can't prove it.
In future work, people often use delimited continuations to build backtracking search. Soar has its own traditional way to do backtracking search, and it would be interesting to compare them.
My current scheduler component is not very interesting - it is specialized to exactly two tasks connected by a pipe. It would be more interesting to have an arbitrary number of tasks, something like Kiselyov and Shan's ZipperFS.
A discrete event simulation is basically a very-concurrent system - an agent using delimited continuations to systematically take the perspective of everything in the simulation might be interesting.
There's two kinds of barriers - the kernel/userspace boundary, and the relationship between one app and another app. Soar does not have a lot of techniques for isolating one module from another. It's possible that tasks that sit underneath a well-known scheduler interface would be more composable, forming reusable libraries.