Haskell for simulating multilane traffic circle?

Question

It was hard for me to come up with a real-world example for a concurrency:

Imagine the above situation, where there are many lanes, many junctions and a great amount of cars. Besides, there is a human factor.

The problem is a hard research area for traffic engineers. When I investigated it a some time ago, I noticed that many models failed on it. When people are talking about functional programming, the above problem tends to pop up to my mind.

Can you simulate it in Haskell? Is Haskell really so concurrent? What are the limits to parallelise such concurrent events in Haskell?

Answer 1

If you need a concurrent programming language with a functional sequential subset, consider Erlang.

More about Erlang

Answer 2

Erlang, Scala, Clojure are languages that might suit you.

But I think what you need more is to find a suitable Multi-Agents simulation library or toolkit, with bindings to your favourite language.

I can tell you about MASON, Swarm and Repast. But these are Java and C libaries...

Answer 3

I'm not sure what the question is exactly. Haskell 98 doesn't specify anything for concurrency. Specific implementations, like GHC, provide extensions that implement parallelism and concurrency.

To simulate traffic, it would depend on what you needed out of the simulation, e.g. if you wanted to track individual cars or do it in a general statistical way, whether you wanted to use ticks or a continuous model for time, etc. From there, you could come up with a representation of your data that lent itself to parallel or concurrent evaluation.

GHC provides several methods to leverage multiple hardware execution units, ranging from traditional semaphores and mutexes, to channels with lightweight threads (which could be used to implement an actor model like Erlang), to software transactional memory, to pure functional parallel expression evaluation, with strategies, and experimental nested data parallelism.

So yes, Haskell has many approaches to parallel execution that could certainly be used in traffic simulations, but you need to have a clear idea of what you're trying to do before you can choose the best digital representation for your concurrent simulation. Each approach has its own advantages and limits, including learning curve. You may even learn that concurrency is overkill for the scale of your simulations.

Answer 4

I imagine you're asking if you could have one thread for each object in the system?

The GHC runtime scales nicely to millions of threads, and multiplexes those threads onto the available hardware, via the abstractions Chris Smith mentioned. So it certainly is possible to have thousands of threads in your system, if you're using Haskell/GHC.

Performance-wise, it tends to be a good deal faster than Erlang, but places less emphasis on distribution of processes across multiple nodes. GHC in particular, is more targetted towards fast concurrency on shared memory multicore systems.

Answer 5

It sounds to me like you are trying to do a simulation, rather than real-world concurrency. This kind of thing is usually tackled using discrete event simulation. I did something similar in Haskell a few years ago, and rolled my own discrete event simulation library based on the continuation monad transformer. I'm afraid its owned by my employer, so I can't post it, but it wasn't too difficult. A continuation is effectively a suspended thread, so define something like this (from memory):

type Sim r a = ContT r (StateT ThreadQueue IO a)

newtype ThreadQueue = TQ [() -> Sim r ()]

The ThreadQueue inside the state holds the queue of currently scheduled threads. You can also have other types of thread queue to hold threads that are not scheduled, for instance in a semaphore (based on "IORef (Int, ThreadQueue)"). Once you have semaphores you can build the equivalent of MVars and MQueues.

To schedule a thread use "callCC". The argument to "callCC" is a function "f1" that itself takes a function "c" as an argument. This inner argument "c" is the continuation: calling it resumes the thread. When you do this, from that thread's point of view "callCC" just returned the value you gave as an argument to "c". In practice you don't need to pass values back to the suspended threads, so the parameter type is null.

So your argument to "callCC" is a lambda function that takes "c" and puts it on the end of whatever queue is appropriate for the action you are doing. Then it takes the head of the ThreadQueue from inside the state and calls that. You don't need to worry about this function returning: it never does.

Answer 6

I've done one answer on this, but now I'd like to add another from a broader perspective.

It sounds like the thing that make this a hard problem is that each driver is basing their actions on mental predictions of what other drivers are going to do. For instance when I am driving I can tell when a car is likely to pull in front of me, even before he indicates, based on the way he is lining himself up with the gap between me and the car in front. He in turn can tell that I have seen him from the fact that I'm backing off to make room for him, so its OK to pull in. A good driver picks up lots of these subtle clues, and its very hard to model.

So the first step is to find out what aspects of real driving are not included in the failed models, and work out how to put them in.

(Clue: all models are wrong, but some models are useful).

I suspect that the answer is going to involve giving each simulated driver one or more mental models of what each other driver is going to do. This involves running the planning algorithm for Driver 2 using several different assumptions that Driver 1 might make about the intentions of Driver 2. Meanwhile Driver 2 is doing the same about Driver 1.

This is the kind of thing that can be very difficult to add to an existing simulator, especially if it was written in a conventional language, because the planning algorithm may well have side effects, even if its only in the way it traverses a data structure. But a functional language may well be able to do better.

Also, the interdependence between drivers probably means there is a fixpoint somewhere in there, which lazy languages tend to do better with.