An introduction to Functional Programming in F# -- Part 1 : Functional Programming via circuits

The other day I came across the notes from a series of informal lunchtime seminars that I organised about five years ago, and thought it would be worth putting them into order and posting them (actually à propos of a recent question about lexing from first principles on the MSDN F# forum, a topic which we will come to in a subsequent post).

Credit where credit is due

My thanks to co-conspirators Will Harwood and Laurence Jordan who did all the heavy lifting to prepare the material for the original set of seminars.

Topics covered in the series

• Introduction to Functional Programming via circuits (this part)
• Lexing and Parsing
• Interpreters
• Simple ‘Functional’ Distributed/Concurrent Programming
• Non-Functional bits - Assignment, Exceptions, Objects, Libraries, etc.
• Advanced stuff - Continuations, Monads, Generative Programming (Language Based programming), etc.

Scope

This series covers functional-programming concepts, as illustrated in F# syntax -- a way for beginners who have started to use the language to avoid just writing FORTRAN C# in any other language. It is not intended as an introductory guide to the language syntax itself, though I'll put in asides about the notations used where appropriate.

F#'s Background

F# descends from the ML series of languages; The initial ML was originally developed as part of the LCF project (1978)‏ by Milner et al.; this split into separate strands (SML; and Cambridge ML, or CAML). CAML development proceeded at INRIA, grew objects in the OCAML variant from the turn of the century, and that in turn provided the basis for F#, which has continued to evolve in what is now more than a decade since Don Syme first brought us that language.

As an ML language, we expect functions to be first-class objects, like any other type (passed as arguments; returned from functions; stored in data-structures; nested inside other functions, where they are lexically scoped, just like any other local variable); and that evaluation is strict (arguments are evaluated before a function call is entered).

Similarly, we expect a static type system that includes polymorphic types, but that type inference will actually lift the burden of pervasive type annotations from the programmer. Most types -- built-in, supplied in libraries or user-defined -- will have immutable value behaviour, though reference types exist that can provided controlled destructive update.

And, while these are standard fare nowadays, we expect the language environment to provide garbage collection and exception handling.

Digital Circuits

Now we actually start to use the language; these examples are intended to execute in the F# interactive console, so are punctuated by the ";;" syntax which is an ML end-of-expression mark, usually optional in project-based code, but needed in the interactive case as a way of signalling that there is now a compilable unit to deal with.

We can use F# to model simple logic gates (1 or 2 signals of either 0 or 1 in, and some Boolean function -- AND, OR, XOR,...).

Here we have defined an algebraic data-type (similar to an enum) and two functions that take a pair of values to return a single result. The functions themselves use match expressions (roughly, what a switch statement wants to be when it grows up) to say "if the input looks like this, then the result must be that".

Exercise: Define the standard Bit functions: OR, NOT, NAND, NOR

Binary Addition

An adder is a circuit that takes two streams of bits and produces a steam of bits as the answer

In standard fashion, we build an adder from two half-adders (which take two inputs and produce the XOR as the sum stream and the AND as the carry stream).

One half-adder takes the two inputs; the sum stream from that is passed into the second half-adder along with the previous carry bit, and the resulting sum forms the final output. Meanwhile the two intermediate carry streams are OR'd together to form the full carry stream.

Exercise: Write Full_Adder as a ‘pattern match’ function definition (i.e. substitute and simplify)

Some Basic Tools: Lists and Streams

A well typed list is a sequence of values where all the values are of the same type,say, 'a. This is an 'a list e.g. Bit list in ML notation (F# allows the more C++-like synonym list<'a> for convenience). A list is either empty or it is a pair of values composed of a value of type 'a and an 'a list.

We can define functions operating on lists by exploiting the structural recursion -- define a function by what it must do on each clause of the type definition. Example: computing the length of a list as

• The length of an empty list is 0
• The length of a non-empty list is 1 + the length of the second list

Here the rec keyword has the effect of bringing the function's own name into scope inside itself, thus allowing the recursive call.

We can perform more complex operations such as

to create the concatenation of two lists, or

Observe that in each case, the original lists are left undisturbed (there is no forward pointer pointing towards the head of the list, so in the append case, l2 is not affected by having some other list know about it, whereas the list cells of l1 are copied as they are appended).

A better implementation of reverse

This is an example of a function, reverse_acc, being defined as a local value inside the enclosing function, just as we might define an integer or string value.

Higher order functions

These are simply functions that have function arguments, like

And we can generalize twice like

to apply f n times.

Lists naturally lead us to higher order functions, as that is how we would describe operations that apply some simpler transformation to every element of the list.

where we use the fact that + is just a function with some syntactic sugar that allows us to write it like an infix operator.

Exercise: Define the function zip which when given two lists of the same length and returns a single list of pairs e.g. zip [1,2,3] [zero, one, zero] is [(1,zero),(2,one), (3,zero)]

Exercise: Define itlist which takes a function f, an initial value v, and a non-negative integer n and returns a list of the iterates of f on v, so itlist f v n is [v, f v, f(f v), f(f(f v))), ...., fn v]

Exercise: Define the function R_reduce f l c which returns f(f(f(f (x1, c) , x2) , x3), x4)if l is [x1, x2, x3, x4]

All these and more (though not always under the same names) are actually provided in the F# Lists module; these and the related functions in the other collections modules are your standard tools when working in the language. Not everything is list processing, but a surprising amount can be cast in that form.

The adder revisited

Now we have lists, we can model the way that the adder is supplied by sequences of bits representing a number, not just one at a time:

Numbers may not be same length, so

• Drop leading zeros
• Pad with new leading zeros until they are the same length

Numbers are fed to the adder LSB first, so would also need to be reversed from the natural MSB first form before and restored after, giving

Generalising: Synchronous State Machine

The adder we saw above is a special case of a general form

which we can represent in code as

and in this form, the LSB-first implementation of the adder looks like