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).
Topics covered in the series
- Introduction to Functional Programming via circuits (this part)
- Lexing and Parsing
- Simple ‘Functional’ Distributed/Concurrent Programming
- Non-Functional bits - Assignment, Exceptions, Objects, Libraries, etc.
- Advanced stuff - Continuations, Monads, Generative Programming (Language Based programming), etc.
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# 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.
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,...).
// introduce simple type definitions type Bits = Zero | One;; // introduce functions over type by pattern matching let AND x y = match (x,y) with (Zero,Zero) -> Zero |(Zero, One) -> Zero |(One, Zero) -> Zero |(One, One) -> One ;; let XOR x y = match (x,y) with (Zero,Zero) -> Zero |(Zero, One) -> One |(One, Zero) -> One |(One, One) -> Zero;;
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
OR, NOT, NAND, NOR
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.
// Introducing function definitions by composition let Half_Adder x y = (XOR x y, AND x y);; let Full_Adder x y carry = let (s1, c1) = Half_Adder x y let (s2, c2) = Half_Adder s1 carry (s2, OR c1 c2);;
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
// Introducing the built in type of lists: this is both recursive and polymorphic // type 'a list =  | (::) of 'a * '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
// simple recursive function definition using structural recursion over the list structure let rec length l = match l with  -> 0 | (x::xs) -> 1 + (length xs);;
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
let rec append l1 l2 = match l1 with  -> l2 | (x::xs) -> x::(append xs l2) ;;
to create the concatenation of two lists, or
//simple and inefficient reverse by structural recursion let rec rev l = match l with  ->  | (x::xs) -> append (rev xs) [x];;
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
//using an accumulator to speed things up; introducing auxiliary function definition let reverse l = let rec reverse_acc l a = match l with  -> a | (x::xs) -> reverse_acc xs (x::a) reverse_acc l ;;
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
// simple higher-order function let twice f x = f(f x);; // a free-standing function to square a number fun x -> x*x;; //Let's use it (fun x -> x*x) 4;; // yields 16 twice (fun x -> x*x) 4;; //Yields: // (fun x -> x*x)((fun x -> x*x) 4) = // (fun x -> x*x) 16 = // 256
And we can generalize
let rec power f n x = if n<= 0 then x else (power f (n-1) (f x));;
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.
//Create a new list by transforming each element of the input list let rec map f l = match l with  ->  | (x::xs) -> (f x)::(map f xs);; //Accumulate the elements of the list (in a general way) // yields f(x1,f(x2,f(x3,f(x4,c)))) if l is [x1, x2, x3, x4] let rec reduce f c l = match l with  -> c | (x::xs) -> f x (reduce f c xs);; // Combine them to provide a different way to define length for a list let len l = reduce ( + ) 0 (map (fun x -> 1) l);;
where we use the fact that
+ is just a function with some syntactic sugar that allows us to write it like an infix operator.
zipwhich 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
itlistwhich takes a function
f, an initial value
v, and a non-negative integer
nand returns a list of the iterates of
itlist f v nis
[v, f v, f(f v), f(f(f v))), ...., fExercise: Define the function
R_reduce f l cwhich returns
f(f(f(f (x1, c) , x2) , x3), x4)if
[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:
// note the reverse order of the lists at this point let rec R_Adder bl1 bl2 c = match (bl1, bl2) with (,) ->  | (x::xs, y::ys) -> let (out, carry) = (Full_Adder x y c) out::(R_Adder xs ys carry) | (_) -> ;;
Numbers may not be same length, so
- Drop leading zeros
- Pad with new leading zeros until they are the same length
// get rid of leading Zero's let rec dropleadingzeros l = match l with  ->  | (Zero::xs) -> dropleadingzeros xs | x -> x // add n leading Zero's let rec padby n l = if n <= 0 then l else padby (n-1) (Zero::l);; // pad two lists to the same length let rec pad (l1, l2) = let len1 = length l1 let len2 = length l2 if (len1 = len2) then (l1,l2) else if (len1 < len2) then (padby (len2-len1) l1, l2) else (l1, padby (len1-len2) l2) ;;
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
let Adder bl1 bl2 = let (l1,l2) = pad ((dropleadingzeros bl1), (dropleadingzeros bl2)) reverse(R_Adder (reverse (Zero::l1)) (reverse (Zero::l2)) Zero);;
Generalising: Synchronous State Machine
The adder we saw above is a special case of a general form
which we can represent in code as
let rec StateMachine f s l = match l with  ->  | (x::xs) -> let (out, state) = (f x s) out::(StateMachine f state xs);;
and in this form, the LSB-first implementation of the adder looks like
let X_R_Adder bl1 bl2 c = let UC_Full_Adder (a,b) c = Full_Adder a b c StateMachine UC_Full_Adder Zero (zip bl1 bl2) ;;