Part of this will be some kind of synchronisation primitive. I don't much care what it is, but somewhere I need a way to make a process wait until something happens rather than just a constant time.

Paul, what you have described sounds like a reactive system. Have you looked into AFRP/Yampa? Although it is based on a continuous time model simulation, it might just work for your scenario nicely. jake

Paul Johnson <paul@cogito.org.uk> wrote in article <43D95CAF.4020601@cogito.org.uk> in gmane.comp.lang.haskell.general:

I want to do some fairly straightforward discrete event simulation. Tasks do side effects, probably in the ST monad. Every so often the current task calls "delay n" where n is a number of seconds. This puts the task back on a list of schedulable processes that is ordered by time, and then takes the head of the list and starts executing it.

Part of this will be some kind of synchronisation primitive. I don't much care what it is, but somewhere I need a way to make a process wait until something happens rather than just a constant time.

You'd be interested in Jan Christiansen and Frank Huch's ICFP 2004 paper, where they build a replacement IO monad to debug concurrent programs. Abstract: "This paper presents an approach to searching for deadlocks in Concurrent Haskell programs. The search is based on a redefinition of the IO monad which allows the reversal of Concurrent Haskells concurrency primitives. Hence, it is possible to implement this search by a backtracking algorithm checking all possible schedules of the system. It is integrated in the Concurrent Haskell Debugger (CHD), and automatically searches for deadlocks in the background while debugging. The tool is easy to use and the small modifications of the source program are done by a preprocessor. In the tool we use iterative deepening as search strategy which quickly detects deadlocks close to the actual system configuration and utilizes idle time during debugging at the best." Ignoring non-integral delays and synchronisation primitives for the moment, your problem is equivalent to breadth-first search (on top of mutable state). Kiselyov, myself, Friedman, and Sabry's functional pearl in ICFP 2005 shows how to build breadth-first search as a monad transformer (which can be applied to a state monad).

I think I want to use something like type Task r s a = ContT r (ST s) a

Indeed continuations need to be involved, in one way or another. The key is that the answer type ("r" above) has to recursively mention the type of tasks, because a suspended task is a function from a resumption signal to a resumed task. This basic idea is behind the last programming example in Filinski's POPL 1999 paper ("a simple resumption-based semantics of concurrency allows us to directly simulate a shared-state program across all possible dynamic interleavings of execution threads"). See also Ganz, Friedman, and Wand's ICFP 1999 paper (and references therein), and Kiselyov's simulation of dynamic delimited-control operators in terms of static ones (Indiana CS TR 611). -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig Can't sleep, clown will eat me. --- "Unlike you I get Windows shoved down my throat at work." Ooh, that's a pane in the neck.