Lazy evaluation *is* coroutines, in a way. Or you may be interested in Concurrent Haskell See section 4 of "Tackling the awkward squad" http://research.microsoft.com/~simonpj/papers/marktoberdorf.htm Simon | -----Original Message----- | From: Andreas Gruenbacher [mailto:gruenbacher@geoinfo.tuwien.ac.at] | Sent: 19 March 2001 17:00 | To: haskell-cafe@haskell.org | Subject: Coroutines | | | Hello, | | has anybody thought about how to implement Simula style coroutines in | Haskell? What I have in mind is several "procedures" that | communicate via | message passing in a co-operative way. That would give clear | and intuitive | code for things like simulations... | | Thanks, | Andreas. | | -------------------------------------------------------------- | ---------- | Andreas Gruenbacher gruenbacher@geoinfo.tuwien.ac.at | Research Assistant Phone +43(1)58801-12723 | Institute for Geoinformation Fax +43(1)58801-12799 | Technical University of Vienna Cell phone +43(664)4064789 | | | _______________________________________________ | Haskell-Cafe mailing list | Haskell-Cafe@haskell.org | http://www.haskell.org/mailman/listinfo/haskell-cafe |
On Mon, 19 Mar 2001, Simon Peyton-Jones wrote:
Lazy evaluation *is* coroutines, in a way.
What I had in mind was something like the following (pseudocode), which could easily be implemented on top of coroutines: class Channel c t where send :: t -> c -> IO () receive :: c -> IO t sender :: Int -> Channel -> ... sender n receiver = do send n receiver return (sender (n+1) receiver) receiver :: Channel -> ... receiver sender = do i <- receive sender return (receiver sender) c :: Channel Int c = ... main = run_them [ sender 1 c, receiver c ] Maybe there is also a way to achieve something similar using higher order functions---I just don't see how.
Or you may be interested in Concurrent Haskell See section 4 of "Tackling the awkward squad" http://research.microsoft.com/~simonpj/papers/marktoberdorf.htm
Thanks, I'm chewing on this paper of yours since a couple of days already. I particularly like the introduction to monads---it's the best I have seen so far. --Andreas.
Hello! On Mon, Mar 19, 2001 at 06:43:55PM +0100, Andreas Gruenbacher wrote:
On Mon, 19 Mar 2001, Simon Peyton-Jones wrote:
Lazy evaluation *is* coroutines, in a way.
What I had in mind was something like the following (pseudocode), which could easily be implemented on top of coroutines:
class Channel c t where send :: t -> c -> IO () receive :: c -> IO t
sender :: Int -> Channel -> ... sender n receiver = do send n receiver return (sender (n+1) receiver)
receiver :: Channel -> ... receiver sender = do i <- receive sender return (receiver sender)
c :: Channel Int c = ...
main = run_them [ sender 1 c, receiver c ]
Now, you can do this: sender :: Int -> [Int] sender n = n:(sender (n+1)) receiver :: [Int] -> () receiver (x:xs) = receiver xs main = let sent_stuff = sender 1 receiver_result = receiver sent_stuff in receiver_result `seq` return () I.e. lazy lists work like coroutine channels often enough. You can do that a bit more abstractly: send :: a -> [a] -> [a] send = (:) receive :: (a -> [a] -> result) -> [a] -> result receive f (x:xs) = f x xs sender n = send n $ sender (n+1) receiver = receive $ \received_thing -> receiver main = (as above) Note that the definition of sender now looks not too unsimilar to your monadic things: sender n = send n >> sender (n+1) === sender n = do send n sender (n+1) -- your 'return' above is redundant receiver = receive >>= \received_thing -> receiver === receiver = do received_thing <- receive receiver Now, in fact, you could achieve this effect with a continuation+state monad quite well (state for input, continuation as *one* way for lazy output).
[...]
Kind regards, Hannah.
On Mon, 19 Mar 2001, Hannah Schroeter wrote:
Hello!
On Mon, Mar 19, 2001 at 06:43:55PM +0100, Andreas Gruenbacher wrote:
On Mon, 19 Mar 2001, Simon Peyton-Jones wrote:
Lazy evaluation *is* coroutines, in a way.
What I had in mind was something like the following (pseudocode), which could easily be implemented on top of coroutines:
class Channel c t where send :: t -> c -> IO () receive :: c -> IO t
sender :: Int -> Channel -> ... sender n receiver = do send n receiver return (sender (n+1) receiver)
receiver :: Channel -> ... receiver sender = do i <- receive sender return (receiver sender)
c :: Channel Int c = ...
main = run_them [ sender 1 c, receiver c ]
Now, you can do this:
sender :: Int -> [Int] sender n = n:(sender (n+1))
receiver :: [Int] -> () receiver (x:xs) = receiver xs
main = let sent_stuff = sender 1 receiver_result = receiver sent_stuff in receiver_result `seq` return ()
I.e. lazy lists work like coroutine channels often enough.
I see your point, and I must admit that this approach has its charm. It's not what I had in mind, though. Simon's MVars (in the Awkward Squad) come pretty close, but they're still not the sort of (cooperative) multitasking that I'm thinking of. I'm not looking for a process or thread model of concurrency. That's too expensive for simulations due to the frequency of task switches. (And thanks Rita, for the Eden reference. That's comparable to Concurrent Haskell.) The sort of lazy evaluation employed in your solution is in a way similar to coroutines, with the following restrictions (correct me if I'm wrong): * It is not possible to implement cyclic communication. * It is not possible to implement processes with multiple asynchronous output channels. I really would like to preserve the elegance of simulations in Simula, but with all the advantages Haskell offers. I believe that in current Haskell implementations all the components needed for "proper" coroutines are more or less there (because lazy evaluation is pretty close). Any more ideas? Thanks, --Andreas.
Tue, 20 Mar 2001 18:07:25 +0100 (CET), Andreas Gruenbacher
The sort of lazy evaluation employed in your solution is in a way similar to coroutines, with the following restrictions (correct me if I'm wrong):
* It is not possible to implement cyclic communication.
I see no problem in this. In fact laziness is really about the ability to cycle anything.
* It is not possible to implement processes with multiple asynchronous output channels.
Again I see no problem: splitEvenOdd:: [a] -> ([a], [a]) splitEvenOdd [] = ([], []) splitEvenOdd (x:xs) = (x:ys, zs) where (ys, zs) = splitOddEven xs splitOddEven:: [a] -> ([a], [a]) splitOddEven [] = ([], []) splitOddEven (x:xs) = (ys, x:zs) where (ys, zs) = splitEvenOdd xs What it cannot do is to multiplex input. Code is purely functional and thus the result cannot depend on the order in which inputs become available. Concurrent Haskell provides nondeterministic merge from lazy lists (mergeIO and nmergeIO in module Concurrent). -- __("< Marcin Kowalczyk * qrczak@knm.org.pl http://qrczak.ids.net.pl/ \__/ ^^ SYGNATURA ZASTÊPCZA QRCZAK
On Tue, Mar 20, 2001 at 06:07:25PM +0100, Andreas Gruenbacher wrote:
The sort of lazy evaluation employed in [Hannah's] solution is in a way similar to coroutines, with the following restrictions (correct me if I'm wrong):
* It is not possible to implement cyclic communication.
It certainly is, and that seems to me a neat way to do process-driven simulation: a process generates a list of future events, which a controller merges into its pool, from which it selects the next event to simulate, starting the next process, and so on. You could use a monad to hide the event output if required.
* It is not possible to implement processes with multiple asynchronous output channels.
Again, should be no problem, but what do you need these for?
I really would like to preserve the elegance of simulations in Simula, but with all the advantages Haskell offers. I believe that in current Haskell implementations all the components needed for "proper" coroutines are more or less there (because lazy evaluation is pretty close).
Indeed, you may be able to do all the simulation primitives in pure Haskell, if you take a step back from the channel view.
Eden (http://www.mathematik.uni-marburg.de/inf/eden) is a parallel extension of Haskell that provides processes which communicate via streams (lazy lists). In Eden, your pseudocode would look like: sender :: Int -> Process () [Int] sender n = process () -> [n,n+1..] receiver :: Process [Int] [Results] receiver = process xs -> consume xs where consume :: [Int] -> [Results] main = print (receiver # (sender # ())) The type Process a b belongs to a process abstraction which defines a process consuming input of type a and producing output of type b. # :: Process a b -> a -> b applies a process abstraction to input. This leads to the creation of the process and its interconnecting channels. Regards Rita -- Rita Loogen Fachbereich Mathematik und Informatik, Philipps-Universitaet Marburg, Germany http://www.mathematik.uni-marburg.de/~loogen --
participants (6)
-
Andreas Gruenbacher -
Hannah Schroeter -
qrczak＠knm.org.pl -
Rita Loogen -
Ross Paterson -
Simon Peyton-Jones