Emulating digital logic circuits in F#

by Pezi 16. February 2012 00:13

In this article we will discover how to emulate simple logic gates, and then build them up to form more complex circuits.  By the end of this 2-part article we will have created:

  • - Half-bit adder
  • - Full adder
  • - n-bit ripple carry adder formed from full adders
  • - 4:1 line decoder
  • - 4:1 multiplexer
  • - 1 bit ALU that supports addition, subtraction, AND and OR operations
  • - n-bit ALU formed from 1 bit ALUs

I have a great love of electronics, and everything covered in this article I have at some point built from scratch, starting from building logic gates from transistors and diodes.  unfortunately my present life dictates I should have no time for electronics, digital logic and robotics, although you can have a brief glimpse of what I used to get up to a long time ago in some other blog posts on this site (which were reposted years later onto this blog).  The love stays strong though, and because of that I decided to re-create some logic simulations in my favourite language F#.  

You are expected to know F# pretty well, there won't be anything too mind-blowing here though. I am not going to teach the ins and outs of digital logic either, but I will give a brief rundown on how the stuff works and provide schematics or all the circuits that we emulate. You should understand pattern matching, recursion and list processing along with all the basic F# syntax.  What we emulate here is the basis for all modern processors, and in future article we may see how this can be extended to create your own rudimentary computer processor!!

Note: There are better and more complex ways to represent and prove circuits using propositional logic, quantified boolean formulae and binary decision diagrams which stem from the symbolic representation of a finite input space.  You can read about these techniques in the mind-blowing Expert F# book.  This article shows a simple, hands-on way to mess around with some logic gates and is aimed at a less advanced functional audience.

Disclaimer : I don't claim to be a master at functional programming, F#, or processor architecture and logic design! Everything I know is self taught.

With my lame excuses out of the way, let's start with basic logic gate representation. A natural way to do this in F# is to use a recursive discriminated union, however I am not going to be doing that here, instead I am going to concentrate on using just functions.  First lets recap on the digital logic gates and the symbols that represent them on a schematic.

I'm sure you all know what a truth table is, and instead of using the boolean logic operators in F#, I am going to define each basic gate explictly using pattern matching which looks almost identical to an actual truth table :) The NOT versions of the gates will simply pipe the results of the gate into the NOT function.

let NOT = function
    | true -> false
    | false -> true
let AND a b =
    match a,b with
    | true, true -> true
    | _ -> false
let OR a b =
    match a,b with
    | false, false -> false
    | _  -> true
let XOR a b = 
    match a, b with
    | true, true -> false
    | true, false -> true
    | false, true -> true
    | false, false -> false
let NAND a b = AND a b |> NOT
let NOR a b = OR a b   |> NOT
let XNOR a b = XOR a b |> NOT

So, no surprises here.  You can test these gates in F# interactive by throwing some booleans at them and they will behave as expected.  Let's move onto something far more interesting.

Half-Bit Adder

A half bit adder is a cool little circuit (and nothing to do with injured snakes) that allows us to add two single bit numbers and output the result in a binary format.  It has two inputs, A and B, and has two outputs, S (sum) and C (carry).  The carry bit forms the most signficant bit (MSB) of the operation, whilst the Sum holds the least significant bit (LSB).  First, let's have a look at the circuit:

As you can see, this simple circuit is composed of two logic gates, XOR and AND.  We simply XOR A and B to produce S, and AND A and B to produce C.  Therefore, our F# definition for the half-bit adder is as follows:

let halfAdder (a,b) = (AND a b,XOR a b)

Which will result in a tuple (C,S).  For the sake of testing this I have created a list of all the possible input pairs and a function that tests them against the half adder.

let trueFalsePairs = [(false,false);(true,false);(false,true);(true,true)]
let halfAdderTest =
    let toBin = function true -> 1y | false -> 0y
    printfn "A\t\tB\t\tC\t\tS\t\tBin"    
    let testValue (a,b) =
        let (c,s) = halfAdder (a,b) 
        printfn "%b\t%b\t%b\t%b\t%A" a b c s (sbyte(toBin c).ToString()+((toBin s).ToString()))
    trueFalsePairs |> List.iter testValue

This code results in the following output

As you can see here, with no inputs the output is 0.  When either A or B is 1 then the output is 1, and when both inputs are 1 then the output is 2 (10 in binary)

The Full Adder

The next circuit we will create is the FULL adder, which also has nothing to do with snakes or food.  This circuit is capable of adding up three bits! First let's look at the schematic:

 

If you look carefully at this circuit, you will notice it is in fact two half-adders and an OR gate.  The second half-adder takes its A input from the Sum output of the first half-adder and its B input from the carry-in bit.  The carry-in bit is the (potential) carry-out bit from a previous adder, and in this way we can chain together adders to add up numbers of any size.   This is called the ripple-carry adder which is slightly inefficient in electrical engineering terms but it is fine for what we will attempt to achieve next.  Before getting ahead of our selves, let's implement the full, all-singng, all-dancing adder in its full venom injecting glory:

let fullAdder (a,b) c =
    let (c1,s1) = halfAdder (a,b)
    let (c2,s) = halfAdder (s1,c)
    (OR c1 c2,s)

Easy huh?  Now, in order to test it, what I am not going to do is what I did before with the half-adder, by creating a list of all possible inputs and then creating some custom test code ...

Testing those blasted reptiles!

 I can tell you now, as this article progresses we will want to be testing all kinds of circuits that will have a dynamic amount of inputs.  For example, in the next part we will create the ability to dynamically create ripple carry adders based purely on the amount of inputs that you give them.  Therefore it makes sense to write the common part of the algorithm and provide a way to supply the custom parts.  In an OOP language we'd be all like "inheritance to the rescue!" (or use the strategy pattern perhaps - in fact, the solution I will use is pretty much identical to the strategy pattern but we use first-class functions and no concrete objects) however we are using a functional language so I won't be using inheritance.  Instead, we will do this the functional way which is to provide the custom parts of the algorithm in (drumroll......) functions!  In order to facilitate this, let's first think about what we are going to need to test our circuits.

- The ability to produce an exhaustive list of all possible combinations of true/false values for n number of bits.  

- The ability to use either all of the above list or maybe only a random slice of the inputs, because we could be dealing with pretty big numbers

- Various helper functions that will make the output readable.  These functions will be able to create binary and decimal representations of our boolean lists.

This will be the first cut of the testing stuff and we can improve on it later if need be.  This isn't supposed to be the best framework on the planet or anything. The functions that each test will have to provide will be supplied via the following interface

type InputType = | All | Range of uint64  
type TestTemplate =
    abstract member NumberOfBits : uint64
    abstract member Execute : (bool list -> unit)
    abstract member InputType : InputType.

Notice here that we are using 64bit unsigned integers all over - this is to allow us maximum flexibility to test larger 32bit numbers.  We have defined a discriminated union InputType that will describe whether to take the whole potential input list or to take a random slice of it, and how bigger slice to take.   The interface TestTemplate will make the magic happen.  NumberOfBits is what the general algorithm will use to decide what list of inputs to create.  Execute is the function that takes each set of inputs, executes the function(s) on it that we are trying to test and prints some output.  Finally, InputType (as above) determines the range of the inputs to take, if not all of them. If this doesn't all make sense, it should do in a minute.

Now let's knock together some utility functions for handling our inputs and outputs. I will go through each one in turn.

let boolOfBin = function 0UL -> false | _ -> true
let binOfBool = function false -> 0UL | true -> 1UL

Two very simple functions that convert 0 and 1 into false and true, and vice versa.

let binOfInt input pad = 
    let rec aux acc pad n =
        match n,pad with
        | 0UL,0UL -> acc
        | 0UL,pad -> aux (0UL::acc) (pad-1UL) 0UL
        | n,pad -> aux ((n&&&1UL)::acc) (pad-1UL) (n>>>1) 
    aux [] pad input 

This is a very useful function that will create a binary representation (in the way of a list of ints) of the passed in number.  That is, passing in 4UL would result in [1UL;0UL;0UL].  It also has a pad parameter which will always ensure the list is of a certain length by way of Cons'ing a bunch of extra zeroes on the front of the list.  This is very important because our circuits will expect a certain amount of bits, so we need to make sure we supply them even if they are all zero.

This conversion from integers to binary can be done in a bunch of different ways, what I have done here seemed most natural.  All we are doing is ANDing the LSB of the input number with 1, adding the result to the accumulator, and then shifting the input along by one bit.  We keep doing this until the input is equivalent to 0, at which point we are done,  unless we still need to pad a few zeroes out. If you are not sure what's going on here you should brush up on your binary maths a little, it will help a lot with the coming stuff.   

let stringOfList input =
    input 
    |> List.fold( fun (acc:System.Text.StringBuilder) e -> acc.Append(e.ToString())) (System.Text.StringBuilder())
    |> fun sb -> sb.ToString()

This very simple code takes any list and converts it to a string by appending the result of calling ToString() on each element into a StringBuilder.  We will use this for converting lists of integers (such as produced in the previous function) into readable strings like "01101". 

let decOfBin input =
    Convert.ToUInt64(input,2).ToString()

This function takes a binary string input (like what is produced in the previous function) and convert it into a unsigned 64-bit integer.  Simples.

let bitsOfBools = List.map toBin >> stringOfList

A function that will take a list of our booleans, convert them to binary, and finally produce a readable string from them.  

let createInputs start max pad =    
    [for x in start..max do yield binOfInt x pad]

And finally, our amazing input generating function.  This guy takes a start and end number, plus a pad, and creates a list with a binary representation (in the form of another list, see the binOfInt function) of each number.  For example, if you call createInputs 0 3UL 2UL the output will be : 

[[0UL; 0UL]; [0UL; 1UL]; [1UL; 0UL]; [1UL; 1UL]]  

Which you might recognise as the same input we used to fully-test the half adder circuit earlier. 

Putting it all together

Ok, we have all of our utility functions defined, so let's go on to write the general test function algorithm :

let rnd = Random(DateTime.Now.Millisecond)
let test (template:TestTemplate) = 
    let max = uint64(2.0**float(template.NumberOfBits)) - 1UL
    match template.InputType with
    | All -> createInputs 0UL max template.NumberOfBits
    | Range(n) -> let n = if n >= max then max else n
                  let start = uint64(rnd.NextDouble() * float(max-n))
                  createInputs start (start+n) template.NumberOfBits
    |> List.map (List.map boolOfBin)
    |> List.iter template.Execute

The test function accepts a parameter template which is an instance of the TestTemplate interface that we defined earlier. First, we declare a random number generator that will be used if the template has specified it would like to use a random range of its possible inputs.  Then we establish the maximum possible number that the range could encompass - this is achieved by raising 2 to the power of whatever the requested number of bits is from the template, and subtracting one. (We subtract one because our binary numbers start at 0 not 1. The maximum number that will fit into a byte is 255, not 256, for example.)  The results of this are then converted into the boolean format that our gates require and then each list is iteratively passed into the function Execute.

So let's define a test template that will test the half adder from earlier:

let testHalfAdder() = 
    test
        { new TestTemplate with 
            member x.InputType = All
            member x.NumberOfBits = 2UL
            member x.Execute = function 
                | a::b::[] -> 
                    let (c,s) = halfAdder (a, b)
                    printfn "%i\t%i\t%s" (binOfBool a) (binOfBool b) (stringOfList([binOfBool c;binOfBool s]))
                | _ -> failwith "incorrect inputs" }

In order to test the full adder, the template is almost identical. The only difference is the amount of inputs goes up to three (because we need a carry-bit), the actual function that executes, and a slight change to the output :

let testFullAdder() = 
    test
        { new TestTemplate with 
            member x.InputType = All
            member x.NumberOfBits = 3UL
            member x.Execute = function 
                | a::b::c::[] -> 
                    let (co,s) = fullAdder (a,b) c
                    printfn "%i\t%i\t%i\t%s" (binOfBool a) (binOfBool b) (binOfBool c) (stringOfList([binOfBool co;binOfBool s]))
                | _ -> failwith "incorrect inputs" }
Running these functions produces the following output :

As you can see, every possible input is executed and the full adder is able to add up to three in binary (11) when all the inputs are high! AMAZING!

Ripple Carry Adders!

Right, now we have all the tools we need to easily test new circuits, so let's step it up a notch.  As I mentioned earlier, a ripple-carry adder is a cool circuit that is essentially a bunch of adders in a sequence, with the carry-out bit being passed into the carry-in bit of the next adder.  This allows us to add up numbers of any size!  First let's have a look at the schematic (which I stole shamelessly from Wikipedia) :

Important things to notice here - The circuit flows from right to left.  The inputs to the adders are formed by taking the respective pair of inputs from each number we are trying to add up.  Eg if we have A=1111 and B=0101, then the first adder's inputs will be (1,1), the second (1,0) the third (1,1) and the fourth (1,0).  Notice here that the first adder takes a carry-in bit C0. This first adder can actually be replaced with a half-adder because we would not have a carry-in bit at the start of the circuit.  In our code though we will simply use a full adder and always supply the initial carry-in bit as 0.  My objective for the nAdder function is not to tell it how many adders to create, but rather drive this from the input it receives.  This turns out to be fairly simple to do using recursion - the only thing we have to worry about is passing the carry-out bit of the previous full adder into the carry-in bit of the next adder:

let nAdder inputs =
    let rec aux c results = function        
        | ab::xs -> 
            let (c1,s) = fullAdder ab c
            aux c1 (s::results) xs
        | [] -> (results  , c)
    aux false [] inputs

Our nAdder implementation takes a list of inputs.  It expects each item of the input list to be a tuple (an,bn) which will be passed along with the carry-in bit into our fullAdder function as defined earlier.  The result of this (sn) is appended to an output list, and the function is then called recursively, passing along the cn bit into the next adder.  When the inputs are exhausted, the final [s0...sn] list is returned along with the final carry-out bit from the last adder.  Once again, the actual implementation of the circuit itself is very simple.  The test template however is going to get much more complicated than the previous ones because we have to deal with any amount of inputs, and now we are taking two full binary numbers and adding them up as opposed to taking 2-3 individual bits and adding them up.  I will show the template first and then go through it afterwards:

let testNBitAdder n = 
    test
        { new TestTemplate with 
            member x.NumberOfBits = (n*2UL)
            member x.InputType = Range(32UL)
            member x.Execute = fun input ->                
                let rec buildInput acc = function
                    | a::b::xs  -> buildInput ((a,b)::acc) xs
                    | [] -> acc
                    | _ -> failwith "incorrect input"
                // exctract input and format the full A and B numbers ready for displaying
                let input = buildInput [] input
                let (A,B) = input |> List.unzip |> fun (A,B) -> (List.rev A |> bitsOfBools, List.rev B |> bitsOfBools )
                // perform the calculation and format result as a binary string
                let result = nAdder input false |> fun (out,c) -> (binOfBool c)::(List.map binOfBool out) |> stringOfList
                // print input number A, B and the result, all in binary
                printf "%s %s %s"  A B result
                // print it again in decimal to show the equivalent sum
                printfn " : %s + %s = %s"  (decOfBin A) (decOfBin B) (decOfBin result) }

First we declare the number of required bits to be 2*n.  This is because if we ask for a 4-bit adder, that actually means we want to add two 4-bit numbers so our input space is 8 bits.   We also set the input type to a range of up to 32 unique inputs - this is because we could generate huge sequences of inputs as we put in higher numbers, so we just want a random slice of those to test with.  Next up is to build the input from the passed in sequences.  This is a bit different to what we have done before.  Because the input sequence generated will effectively be [a0;b0;a1;b1;..an;bn] we need to split this into the tuples (ab,bn) that our nAdder function is expecting.  Once this is done, we use the List.unzip function on the resulting list of tuples to get us the full input numbers for A and B, which are then converted back to strings using List.rev and the bitsOfBools function so that we can show these in the output.  Why are we using List.rev ?  Because our input holds sequences starting from the LSB - to get the actual binary numbers we need to reverse the inputs.

Finally, we call nAdder using the list of input tuples and an initial carry-in bit of false. The results are then formatted so that the final carry-out bit forms the head of a results list where the tail is the output converted into binary.  The whole thing is then transformed into a string ready for ouput.  All that is left is the actual output itself,  and because we are dealing with bigger numbers we give a decimal representation of the sum as well so you can easily see the ripple adder is functioning as intended.  Here are some sample outputs from calling testNBitAdder with various sized inputs:

 

Wow! As you can see our little functions were bolted together, called recursively, and can add up numbers up to 32 bits!  The first part of the article has already gone on longer than I expected. In the next part, I will continue from this point, and we will look at line-level decoders, multiplexers, and then we will take everything and produce a whole arithmetic logic unit that is capable of performing addition, OR and AND operations on n-bit numbers.   The ALU is the core of the CPU so if you don't have any idea about how this stuff works, you are already well on the way!  I have attached the source thus far should you wish to play around with it.

Logic1.fsx (5.28 kb)

 

A basic guide to F# functional techniques part 1

by Pezi 12. February 2012 22:14

Intro

I have been using F# for a year and a half or so now for all sorts of things - general tools, scripts and utilities for work,  XNA games / graphics / AI simulations, some async layers for rx-driven silverlight applications  and so forth.  I'm still pretty new to the functional paradigm, which I have been embracing (with a great deal of mind melting, and destruction of my OOP and procedural shackles). One thing I struggled with initially was the subject of function composition, and its relationship to partial function application and so forth.  I understood the theory behind it but couldn't really see WHY I would want to use it.

Recently I have been learning a bit of Haskell, using the excellent book Haskell : The Craft of Functional Programming.   This really helped switch a lot of lights on with regards to functional programming, introducing function composition in chapter 1.  The books follows a theme of building a simple "Picture" manipulation library based upon function composition, partial application and so forth.  I thought it would be cool to covert these into F# and also have a crack at the various exercises presented in the book, and it has been fun.  I share this experience with you in the hopes that some other novice functional programmers might have some "light switched on!" moments when thinking about functional techniques.

It is assumed the reader will have a working knowledge of the F# language including all the basic syntax, data types, pattern matching, lambda expressions and pipelining. You already know why functional programming is cool and the benefits it offers, but are a bit mystified with how to apply these seemingly complex functional techniques. If you are a C# developer making the move to F# then you will want to go and learn all the basics of the language first, otherwise you are probably not going to be able to follow this all that well.

Setting the Scene!

Our representation of a "picture" is simply a 2-dimensional list of characters, where each character may be '.' or '#'.  In F# this is simply defined as char list list

An example of a suitable picture is shown here, in a string format which is much easier to represent in the script file than a whole bunch of character lists:

Granted, it looks bugger all like a horse, but you can blame the Haskell book for that ;) We create a simple function that will parse this string, dumping whitespace found in the source file, and then converting each line into a list of characters

let pictureOfString (input:string) = 
    input.Split([|'\n'|], StringSplitOptions.RemoveEmptyEntries)  
    |> List.ofArray 
    |> List.map( fun s -> s.Trim().ToCharArray() |> List.ofArray) 

And another little function for showing printing the results 

let printPicture picture =     
    let printer line = 
        line |> List.iter( printf "%c" ) 
        printfn "" 
    picture |> List.iter printer 

Here the inner function printer has inferred the argument line to have a type of char list.  This is because we have applied the line argument to a list processing higher-order function List.iter, so the type inference knows that line must be a list of some description, and we have then used printf "%c" on each item of the list.  The "%c" notation tells printf to look for a char and thus the type of line must be char list.  Notice we have not explicitly applied  the printfn function to each character, this has been done automatically for us by the List.iter function. We will see why this works later.  We could have equally written line |> List.iter( fun c -> printf "c%" c ). Similarly, the argument picture is inferred to have type char list list because we have used List.iter and applied our printer function to it, once again allowing the argument to be automatically applied to the printer function without explicitly applying it.

With that being done, it is now possible to start writing some functions that will perform some processing on the picture.  A desirable function would be one that takes an input picture, flips it along the horizontal plane, and returns a new picture object.  We can think of this mirror flip simply as reversing the order of the outer lines.  Therefore we can create this function as a direct alias to the List.rev library function.

let flipH = List.rev 

So, nothing too amazing has happened here.  We have aliased the inbuilt library function that reverses the given list, and this will produce the behaviour we expect when we put it to the test.  

horse
|> pictureOfString 
|> flipH 
|> printPicture 

Now, for something slightly more interesting.  We wish to write a function that will flip a picture on the vertical plane.  This is a similar operation to the previous one, except it is apparent that the contents of each line needs to be reversed.  That is, rather than reversing the whole list of lines, instead we wish to transform each line in the list with a reverse operation.  When thought about in this way, it should become apparent that the function List.map is appropriate,  as it is designed to call some function on each entity of a given list and create a new list from the results (this is called Select in LINQ). The function we pass into map must be compatible with the type it will be operating on, and since our inner type is another list, we can use any function that takes a list as an input. The function we wish to use in the map command is simply List.rev again which will reverse each inner list, so that

let flipV = List.map (fun x -> List.rev x)

or

let flipV = List.map List.rev 

Note here that once again we have not applied this new function to any arguments, we have just defined a new function by layering two existing functions, so that ultimately we have a function that still accepts an arbitrary list of lists of any type and produces a new value of the same type as the input (because List.rev obviously returns the same type as it was given as an input). All that we have really done here is provided a definition that will feed the result of one function straight into another one.  This is a form of  function composition by way of using functions as first-class values and it works because List.map is a higher-order function. That is, a function that takes another function as a parameter and encapsulates executing some common pattern with that function. This is polymorphism in a functional language (or to be more precise, it is called parametric polymorphism which is the ability to write functions that execute identically regardless of data types). In the case of map it is executing the supplied function on each item of the input list and building a new list with the results. If you apply this function to lists with different types, you might notice that the type inference system has inferred the new function to have a type of 'a list list -> 'a list list and this is because the List.rev function takes a 'a list and so it has determined that the map function must accept a list of lists of 'a.  Pretty clever!

The second version of the function above is written in what is called point-free style (which has something to do with topology in maths I think). Essentially this is the application of arguments to functions without explicitly using the arguments - and in this case we are automatically applying the argument that will be passed in from List.map to List.rev. We have already seen this style in the printPicture function. We shall prefer the point-free style in these articles as it is the more compact and succinct version (and it's more flash! However, it can decrease the readability of a function definition).

For the next function, we would like to be able to rotate the image.  We can already accomplish this using our new functions defined above, as a rotation is the effect of applying a horizontal and vertical flip on an image.  It is interesting to note that these functions can be applied in either order to exactly the same effect. In order to achieve this we could write the function in a variety of ways, including writing an explicitly defined function that take an input and then pipes or applies it into the two functions like so  

let rotate a = a |> flipH |> flipV

or

let rotate a = flipV (flipH a)

However, F# already has operators built in that do exactly the above in a more concise manner, and the ability to compose functions together with an operator can be a powerful technique as we will hopefully see later on.  There are two built in function composition operators, >> and <<, the forward and backward composition operator respectively.  You can think of these as identical to |> and <| but without applying arguments to the resulting functions.  This means you can replace a long pipeline of |> operators with >> operators if you remove the application of the argument  to the first function in the pipeline.  

Therefore,  f >> g means "execute function f and call function g with its result" and the result of this is a new function that accepts whatever the input argument of function f was and results in whatever the output of function g was.  Because the result of f is passed to x, a constraint obviously exists in that the input of g must be the same as the output of f.  The backwards composition operator is the same thing but in reverse, so that g << f has the same meaning as f >> g

let rotate = flipH >> flipV
Let's test the new rotate function:

horse
|> pictureOfString
|> rotate
|> printPicture 

The last two functions we will create in this article will deal with being able to create new pictures by taking two existing pictures and creating a new one out of them.  One function will stack pictures vertically, and the other will put them alongside each other.  First we will look at the stacking function as it is the easier of the two.  Given two pictures, to stack them vertically, all we really need to do is append the two lists, which is easy!  F# already has an operator for this, the @ operator.  Therefore our definition to stack two pictures is simply this operator which we will alias onto our own function name:

let stack = (@)

Here we have wrapped the @ operator in parentheses. This tells the compiler that we want to use the @ operator as a function instead of an operator.  Operators in F# are in fact just functions like everything else, the only difference being that you can apply arguments to the function by placing them on either side of the operator.  Operators are sometimes called symbolic functions - that is, functions that use a symbol instead of a word, and you can define your own symbolic functions (which is awesome).  This is different from the concept of operator overloading which you will be used to in an OOP language.

The second function seems to be more tricky.  If you think about it though, all we need to do is take two lists, and for each line in each list, join them together and output one combined list at the end.  You can visualise this like so:

     List A                    List B

"........###...."  @  "....####......."

"........###...."  @  "....####......."

"........###...."  @  "....####......."

Looking at the wonderful inbuilt functions in the List module, you will see there is a function called List.map2 which has the following type signature ('T1 -> 'T2 -> 'U) -> 'T1 list -> 'T2 list -> 'U list.  These type signatures can be confusing to read at first, but you should learn how to read them well because they can yield a great deal of information about what the function probably does.  Here the first parameter ('T1 -> 'T2 -> 'U) is a function that takes one element of type 'T1, another element of 'T2, performs some logic on them and results in a new value of type 'U.  It then accepts two lists of type 'T1 and 'T2 and finally produces a list of 'U.  This is exactly what we need to perform the side-by-side joining of our pictures.  We can write this explicitly like so:

let sideBySide = List.map2( fun item1 item2 -> item1 @ item2 )

Because we have used the @ operator, the type inference system will know that the items in both lists must be a list of something, but it will not care what type those lists are.  In fact, we can shorten this even further by using the point free style again here like so:

let sideBySide = List.map2 (@)

Which is much more elegant!  Now let's some our functions together in a more complex pipeline.  We will have to be slightly more careful now as the new stack and sideBySide functions will only work if the two input lists are of equal size.  

horse 
|> pictureOfString 
|> fun pic -> sideBySide (rotate pic) pic 
|> fun pic -> stack pic (flipH pic) 
|> printPicture 

What's going on here?  The second part of the pipeline calls sideBySide which is expecting two parameters.  Obviously the pipeline operator is only passing one argument.  What I wanted to do is use the same picture created from pictureOfString, so to facilitate this I have used an anonymous function which captures the horse picture as the argument pic.  I have then applied the unchanged pic as one argument to the sideBySide function, and I have called rotate on pic to produce the second argument to the sideBySide function.  In the third stage of the pipeline I have done almost exactly the same thing, but using stack and flipH on the results of the previous stage of the pipeline.  

Why does the "point free" style work?

In order to understand this, you must first understand that in F#, every function has only one argument. When you apply arguments to a function, F# simply applies the first one, returns a new function which accepts the remaining arguments, then applies the next argument, and so on.  This is called partial function application and this can be used anywhere.  It is totally valid syntax to apply only some arguments to a function, you will simply receive a few function in return which takes the remaining arguments.  We can use this greatly to our advantage in many places.  

If we return to the printPicture function, and look at the definition of the inner function printer.  Here we have used printf but we have not applied all of the arguments to it.  If you execute the command (printf "c%") in F# interactive, it will return  a type of (char -> unit).  What we have done here is partially applied the printf function with only its first argument, and it has returned us a new function that is expecting the remaining char argument and returns a unit (equivalent to void). Now if you look at the definition of List.iter you will see its type is ('T -> unit) -> 'T list -> unit. The first argument is expecting a function of type 'T -> unit which is exactly what our partially applied printf function has given us!  Therefore, when the iteration function executes, at some point it is going to take the passed in function and apply it to an item in the list, which satisfies the rest of the partially applied printf function we have passed in. You can also see this directly at work in the way we call the printer function in the last line.  I hope that makes sense, it is a little awkward to try and explain.

That's it for the first part of these articles, I hope it has helped show how the functional style can be very succinct and elegant.  In the next part, we will create some more interesting functions for the picture library such as superimpose, invertColour, scale and also see how we can use the composition operators in a dynamic way to build up functions that compose themselves with themselves (!!)

If you are really serious about functional programming, I highly recommend you have a go at learning a pure functional language, it will greatly help with the way you design your F# programs.

Footnote: If any expert functional programmers are reading this, I might have messed up the definitions of some techniques, or got some stuff wrong. I'm far from being a master functional programmer, so go easy on me! :)

I have attached an F# script file containing the code covered :

Picture.fsx (1.25 kb)

Tags:

.NET | F#