Functional programming multi-threading

[0rthodontist]

Strangely a good introductory internet resource on this subject doesn't seem to be readily available. Where can I look for information on this subject?

--I am mainly interested in the concepts behind functional multi-threading rather than the syntax for any specific language.

 

[rcgldr]

Multi-threading is in essence multiple programs running at the same time as part of single application, as if there were multiple cpu's and in some cases there are multiple cpu's.

One common usage of multiple threading is when an application has to deal with one or more external events, that take a significant amount of time to complete. The goal is to continue processing while these events are in progress.

These multiple threads needs a way to communicate with each other. Sometimes all that is needed is just a counter to indicate how many events one thread has processed, in Windows this is called a semaphore. Another thread can wait for this counter; if the counter is zero, this thread is just waiting and not executing any code. When the counter becomes non-zero, then that waiting thread will be started up by the operating system, and do whatever processing is required to deal with the completion of the event.

In other cases, a thread may need more information than just a counter, so instead of a counter, a queue of messages is used instead. The waiting thread retrieves a message, and peforms the required code for the specific message.

A simple example of a multi-threaded application would be data converter. There would be three threads, an input thread, a converter thread, and a output thread, and 4 pools of messages associated with buffers. The pools would be input-free-pool, input-filled-pool, output-free-pool, output-filled-pool. At start up, the free pools are created with some number of elements. The input thread waits for an element from the input-free-pool to become available (non-zero count), initiates and waits for data to be read, then sends the filled buffer to the input-filled-pool. The output thread waits for an output-filled-pool element, initiates and waits for the data to be written, then sends the empty buffer to the output-free-pool. The conversion thread, which should be lower priority, waits for an input-filled-pool element, and a output-free-pool element, does the data conversion from the input buffer to the output buffer, then sends the output buffer to the output-filled-pool, and returns the input buffer to the input-free-pool. The intertask messages would include a message that the end of the data (end of file) has been reached so that the threads can self terminate after passing the end of data message onto the next thread.

The coding for this data conversion application ends up allowing the data to be converted while the input and outputs are occurring at the same time. In addition, the buffering allows for the speed of the data to vary somewhat without stalling the entire process. It also simplfies the code in each thread as each thread just deals with one step.

In a game, you typicallly have a thread that receives user inputs, another thread that outputs graphics, and one or more threads to deal with the logic of the game itself.

 

[0rthodontist]

I understand the basics of using multiple threads in non-functional programming. I'm looking specifically for how this is done in functional programming.

 

[gwoodhouse]

One issue is that threads are not really a functional concept. A major difference between functional and non-functional programming is that functional programming is timeless. Execution of functional programs consists (in principle, anyway) of reducing expressions to simpler form. But that reduction doesn't (with any important caveat) imply any kind of temporal order, and even in ostensibly single-threaded applications, many different chains of reductions could be carried out concurrently at the implementation level.

You might want to look at a Scheme implementation called PLT Scheme (http://www.plt-scheme.org) and read the documentation on threads. Incidentally, one reason I like his implementation is that it provides excellent support for multi-threading and concurrency.

You should also look at readscheme.org, a collection of papers on functional programming, focused largely on Scheme and Haskell. Incidentally, this website is hosted on a server written in PLT Scheme (and which is part of the standard distribution).

 

[zyh]

I understand the basics of using multiple threads in non-functional programming. I'm looking specifically for how this is done in functional programming.

I still can't understand " non- functional programming" means What's the difference between these two terms.

 

[mgb_phys]

They are orthoganl concepts but do go usefully together.
Functional programming acts on variables but never changes them, a functional language returns a new variable or list containing the results - the name comes from maths where sin(x) doesn't change 'x' but returns a result.
This is different to procedural (or OO) programmjng where func(x) can change x.

The big problem with multi-threaded programming is preventing two threads changing the same variable at the same time, functional programming laguages avoid this - by never changing variables.

So functional languages ( scheme/Haskal/Erlang) don't have to be multihtreaded but they make multithreaded programming much easier than C/C++/etc

 

[gwoodhouse]

In a programming language like Java, you write down the series of steps you need to go through to do something. You tell the computer WHAT to do. In functional languages, you write down an expression for the computer to EVALUATE. How the expression should be evaluated is up to the computer (compiler).

That probably doesn't sound like a very important distinction, but it can have a big effect on how you think about programs, and it opens up a number of important possibilities. One is that the semantics (meaning) of programs can be expressed in a way that makes programs easier to reason about and, perhaps more importantly, can be made very precise. Historically, programming language semantics has only been dealt with informally (e.g., with natural language explanations), and this has led to ambiguities and gaps making program behavior implementation dependent. An important goal of functional languages is to make the language definitions precise, and thus eliminate a significant source of potential errors.

Incidentally, there is a classic text "Structure and Interpretation of Computer Programs" that is part of the core curriculum in Electrical Engineering at MIT. It tackles these issues head on by showing how an interpreter for Scheme (a popular functional language) can be written in Scheme. Why do this? Well, the program that evaluates Scheme expressions is a formal definition of the language in disguise. More importantly, it provides an excellent introduction to the underlying mathematics of computation.

The book is available on-line at

http://mitpress.mit.edu/sicp/full-text/book/book.html

but, in fact, the copy I own is already my second. My first fell apart from being read and re-read. In other words, I highly recommend it. :)

As an aside for physics students, I should mention that there's another text (one I have not yet read) entitled "Structure and Interpretation of Classical Mechanics" about (you guessed it, Lagrangian and Hamiltonian mechanics). I really don't know if it can compete with SICP (as it is often called), but that book is already a classic.

 

[gwoodhouse]

This is starting to get into the details, but the mathematical foundation for pure functional programming languages may be considered the lambda calculus, invented by Alonzo Church. The lambda calculus defines three very simple rules for how complex expressions can be reduced to simpler ones. A question arises as to the order in which these rules should be applied (often there are many choices). In practice, some languages (Scheme, ML) follow what is called "applicative order", and others (Haskell, Erlang) follow what is called "normal order". Now, an important result in the lambda calculus called the Church-Rosser theorem says that it doesn't matter. You always get the same answer.

But this is only true when you do not allow side-effects. If a language allows you to change the value of a variable (instead of creating a new binding), C-R fails. But you can write sophisticated programs in languages without assignment. What's more problematic is input and output (usually just called I/O). As soon as programs have to interact with their environment, all bets are off. In particular, if a program involves multiple threads, network connections, etc., evaluation order very much matters, and this problem cannot be avoided.

Some languages (e.g., Scheme) just provide the programmer with constructs having side effects. Others try to stay purely functional. Haskell is one such language, and its solution is to provide a tool known as monads that can serve to "quarantine" imperative fragments, preventing side effects there from propagating throughout the program. Really, they are constraints imposed on the evaluator that essentially "force" it to carry out reductions in a certain order where necessary. I'll be honest: I've always found monads confusing, and I still do.