Haskell for modeling multi-band traffic?

Question

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

Imagine the situation above, where there are many lanes, many crossings and a large number of cars. In addition, there is a human factor.

The problem is a complex area of ​​research for traffic engineers. When I researched this some time ago, I noticed that many models failed. When people talk about functional programming, the above problem tends to pop up in my opinion.

Can you simulate it in Haskell? Is Haskell really so parallel? What are the limits for parallelizing such parallel events in Haskell?

Answer 1

I am not sure what the question is. Haskell 98 does not indicate anything for concurrency. Specific implementations, such as GHC, provide extensions that implement parallelism and concurrency.

To simulate traffic, this will depend on what you need to simulate, for example. if you want to track individual cars or do it in general statistical mode, do you want to use ticks or a continuous model for time, etc. From there, you could present your data, which would provide yourself with parallels or parallel estimates.

The GHC provides several methods for using several hardware execution units, from traditional semaphores and mutexes, to channels with light threads (which can be used to implement transactional memory software , to pure functional expression parallel evaluation , strategies and experimental nested parallelism data .

So, Haskell has many parallel execution approaches that can certainly be used to simulate traffic, but you need to have a clear idea of ​​what you are trying to do before you can choose the best digital representation for your parallel modeling. Each approach has its advantages and limitations, including the learning curve. You can even find out that concurrency is redundant for the scale of your simulations.

Answer 2

It seems to me that you are trying to make a simulation, not the real world of concurrency. Typically, this issue is resolved using discrete event modeling . A few years ago I did something similar in Haskell and translated my own discrete event modeling library based on the continuation of the monad transformer. I am afraid that it belongs to my employer, so I can not publish it, but it was not too difficult. The continuation is actually a suspended thread, so define something like this (from memory):

type Sim ra = ContT r (StateT ThreadQueue IO a) newtype ThreadQueue = TQ [() -> Sim r ()] 

In a ThreadQueue thread, a queue of currently scheduled threads is inside the state. You can also have other types of queues for storing threads that are not scheduled, for example, in a semaphore (based on "IORef (Int, ThreadQueue)"). When you have semaphores, you can create the equivalent of MVars and MQueues.

To schedule a thread, use "callCC". The callCC argument is the f1 function, which itself takes the c function as an argument. This internal argument "c" is a continuation: calling it resumes the stream. When you do, from this perspective, “callCC” simply returned the value that you gave as an argument to “c”. In practice, you do not need to pass values ​​back to suspended threads, so the type of the parameter is zero.

So, your argument to “callCC” is a lambda function that takes a “c” and puts it at the end of any queue suitable for the action you are executing. He then takes a ThreadQueue head from inside the state and calls it. You do not need to worry about returning this function: it never does.

Answer 3

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

More on Erlang

Answer 4

I think you are asking if you have one thread for each object in the system?

GHC runtime scales well for millions of threads and multiplexes these threads to available hardware through the abstractions mentioned by Chris Smith. Thus, your system may have thousands of threads if you use Haskell / GHC.

In terms of performance, it is usually much faster than Erlang , but pays less attention to the distribution of processes across multiple nodes. GHC, in particular, is more focused on fast concurrency on shared-memory multicore systems.

Answer 5

Erlang, Scala, Clojure are languages ​​that may suit you.

But I think you need more to find a suitable modeling library or Multi-Agents toolkit with bindings to your favorite language.

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

Answer 6

I made one answer to this, but now I would like to add another one from a broader perspective.

It seems that the problem is that each driver bases its actions on mental predictions of what other drivers will do. For example, when I drive, I can tell when the car can move in front of me, even before it indicates, based on how it is built due to the gap between me and the car in front. He, in turn, can say that I saw him because I was retreating to make way for him, so it’s good to draw him in. A good driver picks up a lot of these subtle tips and is very difficult to model.

So, the first step is to find out which aspects of real driving are not included in failed models, and figure out how to insert them.

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

I suspect that the answer will be to give each simulated driver one or more mental models of what each other driver will do. This includes executing a scheduling algorithm for driver 2 using several different assumptions about what Driver 1 can do about Driver 2's intentions. Meanwhile, Driver 2 does the same thing about Driver 1.

This is something that can be very difficult to add to an existing simulator, especially if it was written in a regular language, because the planning algorithm can have side effects, even if it is only in the form in which it passes the data structure. But a functional language may be able to do better.

In addition, the interdependence between drivers probably means that there is somewhere a fixed point from which lazy languages ​​tend to improve.