Asynchronous Programming in Functional Languages

Question

I'm mostly a C/C++ programmer, which means that the majority of my experience is with procedural and object-oriented paradigms. However, as many C++ programmers are aware, C++ has shifted in emphasis over the years to a functional-esque style, culminating finally in the addition of lambdas and closures in C++0x.

Regardless, while I have considerable experience coding in a functional style using C++, I have very little experience with actual functional languages such as Lisp, Haskell, etc.

I've recently began studying these languages, because the idea of "no side-effects" in purely functional languages has always intrigued me, especially with regards to its applications to concurrency and distributed computing.

However, coming from a C++ background I'm confused as to how this "no side-effects" philsophy works with asynchronous programming. By asynchronous programming I mean any framework/API/coding style which dispatches user-provided event handlers to handle events which occur asynchronously (outside the flow of the program.) This includes asynchronous libraries such as Boost.ASIO, or even just plain old C signal handlers or Java GUI event handlers.

The one thing all of these have in common is that the nature of asynchronous programming seems to require the creation of side-effects (state), in order for the main flow of the program to become aware that an asynchronous event handler has been invoked. Typically, in a framework like Boost.ASIO, an event handler changes the state of an object, so that the effect of the event is propagated beyond the life-time of the event handler function. Really, what else can an event handler do? It can't "return" a value to the call point, because there is no call point. The event handler is not part of the main flow of the program, so the only way it can have any effect on the actual program is to change some state (or else longjmp to another execution point).

So it seems that asynchronous programming is all about asynchronously producing side-effects. This seems completely at odds with the goals of functional programming. How are these two paradigms reconciled (in practice) in functional languages?

Answer 1

All of your logic is sound, except that I think your understanding of functional programming is a bit too extreme. In the real world functional programming, just like object-oriented, or imperative programming is about mindset and how you approach the problem. You can still write programs in the spirit of functional programming while modifying application state.

In fact, you have to modify application state to actually do anything. The Haskell guys will tell you their programs are 'pure' because they wrap all of their state changes in a monad. However, their programs still do interact with the outside world. (Otherwise what is the point!)

Functional programming emphasis "no side effects" when it makes sense. However, to do real-world programming, like you said, you do need to modify the state of the world. (For example, responding to events, writing to disk, and so on.)

For more information on asynchronous programming in functional languages, I strongly urge you to look into F#'s Asynchronous Workflows programming model. It allows you to write functional programs while hiding all the messy details of thread transition within a library. (In a manner very similar to Haskell style monads.)

If the 'body' of the thread simply computes a value, then spawning multiple threads and having them compute values in parallel is still within the functional paradigm.

Answer 2

One note: a functional language is pure, but its runtime is not.

For example, the Haskell runtimes involve queues, thread multiplexing, garbage collection, etc... all of which is not pure.

A good example is laziness. Haskell supports lazy evaluation (that is the default, actually). You create a lazy value by preparing an operation, you can then create multiple copies of this value, and it's still "lazy" as long as it's not required. When the result is needed, or if the runtime finds some time, the value is actually computed, and the state of the lazy object changes to reflects that it is no longer required to perform the computation (once more) to get its result. It is now available through all references, so the state of the object has changed, even though it is a pure language.

Answer 3

This is a fascinating question. The most interesting take on it is, in my view, the approach adopted in Clojure and explained in this video:

http://www.infoq.com/presentations/Value-Identity-State-Rich-Hickey

Basically the "solution" proposed is as follows:

• You write most of your code as classic "pure" functions with immutable data structures and no side effects
• Side effects are isolated via the use of managed references which control change subject to software transactional memory rules (i.e. all your updates to mutable state take place within a proper isolated transaction)
• If you take this view of the world, you can see asynchronous "events" as triggers for a transactional update of mutable state where the update is itself a pure function.

I've probably not expressed the idea as clearly as others have done, but I hope this gives the general idea - basically it's using a concurrent STM system to provide the "bridge" between pure functional programming and asynchronous event handling.

Answer 4

I'm confused as to how this "no side-effects" philsophy works with asynchronous programming. By asynchronous programming I mean ...

That would be the point, then.

A sound, no side-effect style is incompatible with frameworks that depend on state. Find a new framework.

Python's WSGI standard, for example, allows us to build no side-effect applications.

The idea is that the various "state changes" are reflected by an environment of values that can be built incrementally. Each request is a pipeline of transformations.

Answer 5

Having learned encapsulation from Borland C++ after learning C, when Borland C++ lacked templates that enabled generics, the object orientation paradigm made me uneasy. Somewhat more natural way to compute seemed filtering data through pipes. The outward stream had separate and independent identity from the inward immutable input stream, rather than be thought of as side-effect, i.e. every data source(or filter) was autonomous from others. The keypress( an example event) constrained the asynchronous user input combinations to the available keycodes. Functions operate on input parameter arguments, and the state encapsulated by class is just shortcut to avoiding explicitly passing repetitive arguments between small subset of functions, besides being precautious to bound context preventing abusing those arguments from any arbitrary function.

Adhering rigidly to particular paradigm causes inconvenience to deal with leaky abstractions, for eg. commercial runtimes such as JRE, DirectX, .net target object oriented proponents foremost. To constrain the inconvenience, languages either opt for scholarly sophisticated monads like Haskell does, or flexible multi-paradigm support like F# eventually got. Unless encapsulation is useful from some multiple inheritance use case, multi-paradigm approach might be superior alternative to some, sometimes complex, paradigm-specific programming patterns.

Answer 6

Functional programming is about sharing information through function composition, recursion but not through shared state/memory (move semantics would be considered purity preserving in that sense).

Asynchronous programming is orthogonal to functional programming. Asynchronous programming is merely about how should tasks/chunks of work be scheduled as a response to events. Events include task invocation events internally generated at run-time.

Contrary to your reasoning, as long as state information of a task/function is fully encapsulated within the closure/scope of that function, I do not see how asynchronous programming would violate purity as such. In other words, I see asynchronous programming naturally co-existing with functional programming, as long as we keep all our tasks/chunks of work pure/stateless. For example, in a pure function, program counter (state) must not exist, thus we cannot generate events/function invocations in a sequence of "calls" inside from inside an asynchronous task as no program counter state should exist. Instead, functional primitives for function composition should be asynchronously scheduled instead.

Think of a Haskell runtime that implements purely functional code as asynchronous invocations of functions. The asynchrony in this case is totally hidden from the developer, as it turns out to be more of an implementation detail, thus hiding any state required for its operation, inside the runtime.

Long story short, you can very well gain the benefits of both worlds by hiding asynchrony to part of the functional language runtime.

Answer 7

Since the question was posed side effect concept might have gotten uncluttered when posting the answer according to wikipedia page:

In computer science, an operation, function or expression is said to have a side effect if it modifies some state variable value(s) outside its local environment, which is to say if it has any observable effect other than its primary effect of returning a value to the invoker of the operation.

Asynchronously passing a state to a function that transforms it to a return value is different than side effect.

The "no side-effects" philosophy is turning what has to be changed to a function local environment. In the meanders of the concrete referring to UI components to change the visual of a component have a function getting the component's reference and pass it along the functional chain to be changed. This way the functional chain from one end to the other just transforms the state passed by the event. Differently said functional programming is about transforming.

"A good traveler leaves no tracks"