Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

I've been playing around with resumptions lately, mostly from Abramsky's classic paper Retracing Some Paths in Process Algebra. They are quite slick (basically solutions to the domain equation $R = I \to (O \times R)$), and very reminiscent of Kahn networks.

Of course, this observation is not original to me --- they form a traced monoidal category, and this fact was used by Abramsky and Jagadeesan to give semantics to linear logic. At any rate, note that if you feed a resumption $r$ an input of type $I$, you get an output of type $O$ and an updated resumption $r'$, which is what lets you model the fact that a dataflow node can change as it sees inputs come in.

As a result, it seems like they could give a nice API for building I/O transducers in a higher-order language like ML or Haskell, but I can't seem to find any papers describing such a thing. But they've been around for decades, and Gordon Plotkin invented them, so it's not like they've languished in obscurity. So I was wondering if anyone had seen them put to such use.

share|improve this question
2  
As I was reading the question I thought to myself "I bet Neel will answer this one". –  Andrej Bauer Dec 1 '12 at 17:51
    
This might be a nice use-case for Eff-style opearations and handlers. –  Andrej Bauer Dec 1 '12 at 17:52
    
@AndrejBauer: I always think that for Neel's questions. –  Dave Clarke Dec 1 '12 at 22:04

2 Answers 2

up vote 7 down vote accepted

This looks a lot like the I/O API described by Felleisen et al in A Functional I/O System (or Fun for Freshman Kids). Basically, you write (in the simpler, non-distributed setting), a series of event handlers, each of which accepts the current state, and returns an updated state. Finally, there's a to-draw handler, which produces the "output" for each state.

If we recast this API slightly, we can package up the handlers and the current state together, and each time a handler returns both a new state and a new set of handlers. We might call this package of state and operations an "object". :) If we then make the result a pair of this object, and the "output", then we have exactly the type of resumptions.

Interestingly, in the paper, Felleisen et al do exactly this when moving to the distributed setting -- every operation returns a pair of new state and "output" in the form of messages to be sent to the other participants in the system.

share|improve this answer
    
Thanks, that's a really good example. –  Neel Krishnaswami Nov 28 '12 at 9:41

Just came across this post.

Do go back to the early 1980s. Friedman et al @ Indiana invented the concept of 'engines' in the context of Scheme 84 (not Scheme 48). An engine is roughly an element of this type:

E = Unit x Nats -> E + O

You can also use I instead of Unit and the x Nats part is optional. You can think of these as a form of resumptions, and depending on context engines are more practical than resumptions.

share|improve this answer
1  
Thanks! Google found me Haynes and Friedman, "Abstracting Timed Preemption with Engines" (cs.indiana.edu/pub/techreports/TR178.pdf), and Dybvig and Hieb's "Engines from Continuations" (citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.64.6124) Are there any other refs I've missed? –  Neel Krishnaswami Dec 3 '12 at 9:53

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.