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
- Introduction to Functional Programming via circuits
- Lexing and Parsing
- Simple ‘Functional’ Distributed/Concurrent Programming (this part)
- Non-Functional bits - Assignment, Exceptions, Objects, Libraries, etc.
- Advanced stuff - Continuations, Monads, Generative Programming (Language Based programming), etc.
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
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:
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
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.
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
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.
We can connect two functions, producer and consumer, by a stream thus:
which will run printing squares until you halt the environment.
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.