Friday, December 20, 2013

An introduction to Functional Programming in F# -- Part 4: Concurrency and Networking

So far we have dealt with entirely pure functions and immutable data, where the program result might just as well be generated at compile-time, like a C++ template meta-program. This time we look at violating these constraints.

As has been the case for the previous posts, this discussion focuses on the principles of functional style and how to achieve the results we want from first principles, rather than going directly to library code, especially when introducing new concepts.

Topics covered in the series


The type of variable that one is familiar with in languages like C# or Java is a reference -- the variable name refers to a box that contains a value. F# has an explicit form or type 'a ref to denote a box that can hold values that are of type 'a, e.g.

where the integer zero is an immutable value all of its own.

We get the value out of the box by the function

We change the value in the box by the function

F# also offers the modifier mutable and the operator <-; a mutable value needs no special treatment to be read, but update is done using the <- operator. Using this we can emulate 'a ref as a record type (as we used to hold computations last time)

We will favour references for the rest of the post, as their mutability is explicit at all sites of use.

Local Persistent State

We can use references to maintain persistent state within program, and encapsulate it, without needing to yet reach for the explicitly object-oriented features of the language. Consider this function:

the function gen produces a generator function that uses a private variable to track the number of times it is called, so producing f 1, then f 2, as in

where successive calls produce 1, 4, 9, 16...

Sharing a Reference Variable

If we have the following functions

to extract the head and the tail of a list, we can model a queue using shared mutable state as

Here stream takes an initializing list, and returns functions add an item, remove an item and test for exhaustion of the queue.

Exercise: This is a naive implementation -- the behaviour of put is linear in the number of elements in the queue. Immutable queues are implemented as pairs of lists with occasional list reversals leading to amortized constant time to flow an item through the queue, and a similar internal representation could be used here. Rewrite stream to use such an implementation.

Simple concurrency

The problem with shared state as in our queue example above comes when multiple concurrent operations attempt to modify the state, rendering its output, or worse, its actual internal state, inconsistent. So, using the familiar thread and lock model for concurrency, we can introduce:

for thread creation, and

to manage locks.

Aside: we could use other concurrency APIs to initiate execution, e.g. Task; what is important here is that there is the possibility for concurrent access to any shared mutable state.

These operations block indefinitely, so prevent data races while offering the opportunity for deadlock instead.

A Concurrent Queue

With the lock operations, we can modify our queue to use a lock to manage access to the shared state, placing a write lock around the mutations and a read lock around the other accesses:

We also introduce the standard type 'a option which has the form

to signal the empty state in a more uniform way than having to test the previous isEmpty function.

Exercise: Add locking to the result of the previous exercise .

Aside: This style of code is of course not safe against exceptions that unwind the stack while a lock is being held.

Asynchronous Composition

We can connect two functions, producer and consumer, by a stream thus:

which will run printing squares until you halt the environment.

Functional networking

We can develop this idea further with the following concepts:

  • It’s asynchronous composition on different computers or between different processes on the same computer.
  • Make byte streams look like lists.
  • Build about the simple idea of null terminates strings as messages.

Depending how we make the connections, we can either model simple one-way messaging (or asynchronous messaging if each counter-party transmits on its own schedule), or request/response (or synchronous messaging).

Aside: This approach is akin to that used by Erlang, though this is only a very first approximation to the Erlang model.

Developing the network model

Taking advantage of the .net library methods that provide a stream-oriented view on a connection, we can write helper methods

and make the interconversion with lists as

A simple echo server and client

Using the same familiar techniques, we can build up string to byte-list inter-conversions, and put together functions to put a string onto a TCP connection and then read it off again. It's then a simple matter of calling the appropriate network APIs to open a listening socket and make connections for the duration of a request and response.

The example code at the end of the listing below spins the server code on a separate thread, allowing the client to execute in the same interactive session.

No comments :