[Haskell] Re: Discrete event simulation

[Chung-chieh Shan]

Paul Johnson <paul at cogito.org.uk> wrote in article <43D95CAF.4020601 at 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.