Sunday, January 27, 2008 5:28 PM bart

Foundations of Functional Programming - Part 1

Welcome back to this blogging series on functional programming. After some scene-setting in the previous post, let's get into the real stuff now.

 

A quick analysis

So, what's functional programming all about? It might be a little shocking, but it's all about programming with functions. The first part should be well-known to all readers of my blog, but what's a function? And by function we mean - yes, fasten your seatbelts - the mathematical concept.

A function is a special type of a relation that associates the members of one set (called the domain) uniquely with the members of another set (called the codomain or range).

I won't go in much more theoretic details (such as explaining what a relation is, the relation with set theory, etc), for full details I refer to great sources on the internet such as Wolfram Mathworld (where geeks will even find the "function of the day" webpage).

Let's make it more concrete starting from some notation:

f : D -> R, f(x) = ...

where f is the name of our function, D denotes the domain (for example, the natural numbers, say int) and R stands for the range (for example, the same set of natural numbers int). The ... part is intentional and can contain anything that "does something with some variable x from the domain, returning a single value from the range", requiring that the operations used in it are well-defined (e.g. mathematical operators on natural numbers).

So, what are the key takeaways?

  • Uniqueness: members in the domain correspond uniquely to one (and only one) member from the domain.
  • Time-invariant: the application of a function to give (constant) argument always yields the same result, regardless of the moment of application.

 

Our own little syntax

What's next? Some nice and smooth syntax that doesn't look too frightening (once we get into lambda expressions I'll introduce a more terse syntax), so let's stick with some C#-ish style:

R f(D)

stands for the signature of a function mapping arguments in the domain D onto values in the range R. Let's give a simple sample:

bool IsEven(int)

Notice I don't give the arguments a name yet, first we'll just reason about the signatures. We can go even further, by eliminating the function's name as follows:

bool(int)

Which is the signature of any function taking in an int and returning a bool (yes I know there is some .NET 3.5 class that does precisely this, relax we'll get there eventually :-)).

Notice we didn't cover functions with more than one argument yet. Strictly speaking we don't need these (I'll explain why in a moment) which might be shocking once more. More important however is the fact that a function returns one single value, so what if we want to return more than just one "thing"? Just wrap it in a more complicated structured "thing", called a tuple:

(int,int)

This tuple has two ints and could represent a point (or a complex number, or a monetary value, or ...). All of a sudden a signature like this:

(int, int) (int, int)

denotes a function taking in a tuple of two ints, returning another of these. Did I mention already we don't need multiple arguments (okay, this is a lame escape route, but we'll see a more appealing argument later on)?

Now, what about a function like the following:

bool (bool(int), int)

This function takes in a function with signature bool(int) itself, as well as an int, and returns a bool. What the function does inside remains a mystery though, so let's define the function.

 

Function definitions

The missing piece above is the definition of what a function does. From our takeaways we remembered that functions don't change their value across calls with the same arguments. Keep this in mind (the reason why this is important follows later). Now, let's define a function:

bool IsEven(int) := IsEven(a) = a % 2 == 0

where := stands for "is defined as". Notice we're repeating the function name on the right-hand side, this time replacing the "int" argument with a dummy name "a". The word dummy is very important for the discussion: in the function definition it doesn't have any meaning, it just acts as a placeholder. The reason for repeating the function name might look a little weird since we could well write:

bool IsEven(int a) := a % 2 == 0

Again, there are some good reasons for doing it the more verbose way and we'll get back to it when introducing pattern matching.

 

Function application

Given the function from the previous paragraph, we can apply the function as follows:

IsEven(5)

Applying the function is a mechanical thing, binding the value 5 to the dummy a, which is based on substitution:

IsEven(5)
= [IsEven(a)][a := 5]
= [a % 2 == 0][a := 5]
= 5 % 2 == 0
= 1 == 0
= false

which literally means we can drop the IsEven(5) occurrence and replace it by false. Why is this important? Assume you have a "program" (loosely defined) where you find two occurrences of IsEven(5), it's sufficient to do the mechanical transformation once and only once (since a function always returns the same value for the given argument, regardless of when you call it). The pure characteristic of functions allows us to apply various optimizations in the evaluation strategy, which is one of the places where functions touch the multi-core trends.

 

The formal way

What we've discussed above is lambda calculus in disguise. Lambda calculus was created by Church and Kleene around 1930. Some properties of lambda calculus are its declarative nature, the fact it's stateless (which we'll elaborate on quite a bit) and operates in an immutable way (you can trust it to give an argument, it's value won't be changed by it). Let's redefine the Even function in lambda calculus:

λa . a % 2 == 0

The part on the left of the dot denotes the function's parameter a being prefixed by the Greek letter lambda. Again, the parameter just acts as a dummy that happens to occur (although that's not really needed) somewhere in the part on the right of the dot.

Having the possibility to declare a function is one thing, manipulating it is another thing. To do this, we need a set of rules which happen to be called after other Greek letters:

  • α (alpha) conversion is used to rename dummies, that is: our function from above can be rewritten as:

    λx . x % 2 == 0

    by renaming a into x. You could see this as a lightweight refactoring mechanism. Of course, alpha conversion can only occur if there's no "name clash" (which needs discussion of free and bound variables). Alpha conversion is not just a convenience rule, in many cases it's a much required tool to eliminate name clashes when composing functions.
  • β (beta) conversion is the difficult word for function application. Function application is defined in terms of substitution, i.e.:

    (λx . f) y = f[x := y]

    The left hand side should be read as "a function f of an argument x, applied y" while the right hand side says this is the same as replacing all occurrences of dummy x in f by y. For example:

    (λx . (x % 2 == 0)) 5 = (x % 2 == 0)[x := 5] = (5 % 2 == 0) = (1 == 0) = (false)

    introducing a few additional pairs of parentheses for "clarity". As you can see, function application gets rid of one parameter at a time.
  • η (eta) conversion might be the most exotic one in this discussion. It's a means to deal with extensionality, a big word to say that two functions can be compared for equality (Leibniz). Essentially, it says that the abstraction of a function application is the function itself:

    (λx . f) x = f

    Strictly speaking this can only be done if x doesn't occur as a free variable in f.

Notice the way we write down functions and their arguments in a prefix manner; the fact lots of today's programming languages have infix operators is just a matter of convenience:

add = (λxy . x + y)

add 1 2 = 1 + 2

People who had prior exposure to LISP (just to name one language) will be familiar with the prefix-notation (and lots of parentheses of course), like:

+ 1 2

Higher order functions

Let's step back for a second. In the sample above I introduced a function add that takes two arguments as having the argument list λxy. But do we really need such a syntax? Strictly speaking we could write:

λx . λy . x + y

An important thing to move forward is to point out the associativity (give me parentheses!):

λx . (λy . x + y)

Hmm, a function with one argument x? Exactly! So, what does it return? The left hand side reveals it: another function. Let's apply it to see what happens:

(λx . (λy . x + y)) 3
= (λy . x + y)[x := 3]
= (λy . 3 + y)

So, we don't need multiple arguments if we allow a function to return a function by itself, meaning that each function "eats" one argument, possibly returning a function that takes care of eating the remainder arguments.

In our previous notation this could be written as:

int(int) (int)

Which is a function that takes in an int and returns a function that on its turn takes in an int and returns an int. So, a concrete function Sum is now a function of one argument, returning a new function that takes another argument:

int(int) Sum(int) := Sum(x)(y) = x + y

Look at the syntax on the right-hand side: a Sum with two parameters (each with their own set of parentheses).

In Haskell style of notation this would be written as int -> int -> int, or equivalently int -> (int -> int) due to right associativity. The technique of partial application is also known as currying (from Haskell Curry); the fact that a function can return a function by itself reveals the fact we should think of functions as data. In F# the above looks like this:

let add a b = a + b
let addtwo = add 2

where the first function is capable of taking a maximum of two arguments, but less arguments are welcome too, as done in the second line. So, the second function can only consume one (remaining) argument. A sample run in F# is shown below (we'll dedicate separate posts to F# later):

image

In C#, there's no such thing as partial application out-of-the-box, although you could work around it (as we'll see later).

 

Evaluation order

After this (important!) side step to higher order functions, let's come back to our lambda calculus rules: why do we care about these at all? One very good reason is to discuss the evaluation order of function applications (geeks might want to learn about the Church-Rosser theorem to get the bigger picture). Let's start by defining a few (recursive) functions, for which I'll use F# notation again:

let rec fib n = match n with
      1 -> 1
    | 2 -> 1
    | n -> fib(n - 1) + fib(n - 2)

let rec fac n = match n with
      1 -> 1
    | n -> n * fac(n - 1)

The first function calculates a number of the Fibonacci sequence (1 1 2 3 5 8 13 21 ...) and the second defines the faculty function (n! = 1 * 2 * ... * (n - 1) * n). I leave it as an exercise annex brain-teaser to define these in terms of lambda calculus (hint: anonymous or not?)...

The F# notation can be read as "let the recursive function fib with argument n be defined as a match of n with ..." where the ellipsis indicates a | separated list of matches written down as l -> r, where l is the match criterion and r is the result. You can compare this with a switch statement although it differs significantly: it's much more powerful and it's an expression (which implies it has a value) rather than a statement (yes, even if's are expressions in F#).

Now define a function like this one:

λx . x * x

which is a simple square function. Let's apply the function to an argument now:

(λx . x * x) (fac 10)

Say we do beta conversion first, also known as normal-order reduction, we'll end up with:

(fac 10) * (fac 10)

and further reduction will calculate "fac 10" (= 3628800) twice, which is definitely a waste of time. Even worse, every argument to the square function will be evaluated twice, no matter how complex it is (it could well be one page long, requiring an hour of calculation).

An other application would evaluate the (fac 10) part first, yielding:

(λx . x * x) 3628800

which is clearly more efficient. So, I hear you wondering already what's the most efficient one? It depends. The latter form we discussed is one you see quite often in familiar programming languages, where the arguments of a function call are evaluated before pushing them on the stack (call by value). However, this can be harmful as well. Consider the following:

let cond c f g = match c with
      true -> f
    | false -> g

Now, what happens if we call the function cond as follows?

cond true (fac 10) (fac 1000000)

When applying call by value evaluation, the system will be quite busy calculating (fac 1000000) only to discard the result of it when cond is reduced. This problem occurs with the Iif function in VB, while a ternary operator (?: in C# and the new use of the If keyword in VB 9.0, see an earlier post of mine on the subject) avoids the problem altogether, by applying call by need reduction (a form of lazy evaluation, Haskell is the most proficient user of this strategy). By the way, in languages that allow side-effects, call by need can be considered harmful by itself since the side-effects are now no longer predictable (as far as predictability goes in a world of side-effects of course) just by looking at an expression (i.e. when seeing a function call, you know arguments needs to be evaluated prior to making the call itself).

For geeks, the cond function defined above can be rewritten nicely in terms of lambda calculus using Church Booleans (a similar concept as Church numerals):

true := λab . a
false := λab . b

(yes, true and false are functions too!) which can be used as:

cond := λcfg . c f g

applied in an example:

cond true (fac 10) (fac 1000000)
= (λcfg . c f g) (λab . a) (fac 10) (fac 1000000)
= (λfg . (λab . a) f g) (fac 10) (fac 1000000)
= (λfg . f) (fac 10) (fac 1000000)
= (fac 10)

clearly, this evaluation is more efficient than blind applicative order reduction, which would

cond true (fac 10) (fac 1000000)
= (λcfg . c f g) (λab . a) (fac 10) (fac 1000000)
= (λfg . (λab . a) f g) (fac 10) (fac 1000000)
= (λfg . f) (fac 10) (fac 1000000)
= (fac 10)

Another evaluation methodology is call by name which comes close to call by need. In this strategy, the arguments to a function are captured in little thunks and passed on to the function which can evaluate it when required (by calling through the thunk). Algol uses this strategy. The main difference with call by need is that results of invoked functions aren't kept around for subsequent calls (e.g. calling fac 10 twice, maybe in two completely different places throughout an execution flow, could be optimized by keeping the calculated value in some sort of cache, given that the function fac is pure), a technique called memoization.

 

Purity

The word you've been waiting for... The whole discussion above boils down to the question whether or not we consider functions to be "pure" (meaning all the lambda calculus rules apply in a strict way). If there's no notion about global state, what's a program supposed to look like? A bunch of calculations that can be reduced to a constant? All good questions, but let's keep the answers for later. First of all, I want to convince the reader about the useful constructs offered by this functional style.

 

The C# way

Enough theory for now, let's make it somewhat more concrete using real C# style of notation. First, let's introduce a function in terms of a generic delegate:

delegate R Func<R>();
delegate R Func<T1, R>(T1 t1);
delegate R Func<T1, T2, R>(T1 t1, T2 t2);
delegate R Func<T1, T2, T3, R>(T1 t1, T2 t2, T3 t3);
...

which is what we have in the System namespace from .NET 3.5 on. Since we don't have "params" functionality on generic parameter lists, the number of overloads is limited (which means there's an upper bound on the number of parameters) but feel free to define additional ones yourself if you need more parameters (but keep in mind you don't need additional parameters per se, as illustrated two paragraphs ago). We'll stick (for now) with a limited view on the world:

delegate R Func<T1, R>(T1 t1);

So, how would you define IsEven? Let's start by creating a method:

bool IsEven(int x) { return x % 2 == 0; }

which can be referred to by means of the delegate as follows:

Func<int, bool> f = IsEven;

allowing for function application like this:

bool is5Even = f(5);

Now, if we don't want to go through the burden of defining a helper method to achieve this result, we could use a lambda expression (new in C# 3.0) instead:

Func<int, bool> f = x => x % 2 == 0;

which is essentially the same as (C# 2.0):

Func<int, bool> f = delegate (int x) { return x % 2 == 0; };

The mechanical translation to a theoretic lambda expression (starting from the C# 3.0 syntax) is trivial.

What about our higher-order Add function defined earlier? Remember the working of it, consuming only one argument, returning another function to carry out the rest of the calculation. Here's a way to write it in C# 3.0:

Func<int,int> Add(int a) { return b => a + b; }

That is, you can call it like:

Func<int,int> addTwo = Add(2);
int four = addTwo(2);
int five = addTwo(3);

Essentially, we've lifted the function to become a higher order one by breaking it in pieces, which gives us the power to pass around partial functions:

IEnumerable<int> GetRange(int from, int to, Func<int,int> transformer)
{
   for (int i = from; i <= to; i++)
      yield return transformer(i);
}

...

GetRange(1, 10, Add(2))

will produce the numbers 3 to 13, or we could write (using a lambda):

GetRange(1, 10, a => a + 3);

or

GetRange(1, 10, a => a * 2);

etc.

In the above we've already stepped back from a pure functional world and allowed for imperative constructs (loops, iterators) to sneak in. Diehards can think of other mechanisms to eliminate some of these (tip: recursion).

 

What's next?

In the next post, we'll play a bit more with the C# style of function notation and see how functions compose nicely. In a later post, F# will make its appearance.

Del.icio.us | Digg It | Technorati | Blinklist | Furl | reddit | DotNetKicks

Filed under:

Comments

# re: Foundations of Functional Programming - Part 1

Monday, January 28, 2008 1:03 AM by Sam

Nice stuff! I hope you have some good examples how to use this for real world problems, since I think applying this kind of thinking on daily stuff will be the biggest challenge.

# re: Foundations of Functional Programming - Part 1

Monday, January 28, 2008 7:39 AM by Thomas Krause

Very interesting. Thanks! Can't wait to see the next one...

# re: Foundations of Functional Programming - Part 1

Monday, January 28, 2008 5:32 PM by Andrew Tearle

Excellent ! Many Thanx ...

# Continuing Adventures in F#

Tuesday, January 29, 2008 8:44 AM by Matthew Podwysocki's Blog

Update: Added more F# samples and the foundations of functional programming In a previous post , I've

# Pages tagged "immutable"

Tuesday, January 29, 2008 9:03 PM by Pages tagged "immutable"

Pingback from  Pages tagged "immutable"

# Functional Exercise

Saturday, February 02, 2008 6:51 PM by Functional Exercise

Pingback from  Functional Exercise

# Link List: Language Topics, Data Service, jQuery,F#, Spec#, Specs Reading, etc...

Monday, February 04, 2008 4:08 AM by Guru Stop

It started an email Mohamed Hossam (AKA, Bashmohandes) sent to my company's local office here in Egypt

# Adventures in F# - F# 101 Part 2

Thursday, February 21, 2008 4:52 PM by Matthew Podwysocki's Blog

I know it's been a little bit too long since I began this series from when I continued, but plenty of

# http://communities.bartdesmet.net/blogs/bart/archive/2008/01/27/foundations-of-functional-programming-part-1.aspx

# Love and Theft &raquo; Blog Archive &raquo; F#, .NET and Functional Languages

Pingback from  Love and Theft  &raquo; Blog Archive   &raquo; F#, .NET and Functional Languages

# http://blog.bartdesmet.net/blogs/bart/archive/2008/01/27/foundations-of-functional-programming-part-1.aspx

# Recent Faves Tagged With "codomain" : MyNetFaves

Monday, September 29, 2008 8:35 AM by Recent Faves Tagged With "codomain" : MyNetFaves

Pingback from  Recent Faves Tagged With "codomain" : MyNetFaves

# fredrikholmstrom.se &raquo; F#, .NET and Functional Languages

Wednesday, August 05, 2009 7:26 AM by fredrikholmstrom.se » F#, .NET and Functional Languages

Pingback from  fredrikholmstrom.se &raquo; F#, .NET and Functional Languages

# Adventures in F# &#8211; F# 101 &laquo; Khurram Nazir&#039;s Blog

Tuesday, November 03, 2009 6:00 AM by Adventures in F# – F# 101 « Khurram Nazir's Blog

Pingback from  Adventures in F# &#8211; F# 101 &laquo; Khurram Nazir&#039;s Blog

# F# Database Programming &#8211; FunctionalNHibernate? &laquo; Tales from a Trading Desk

Pingback from  F# Database Programming &#8211; FunctionalNHibernate? &laquo; Tales from a Trading Desk

# Link List: Language Topics, Data Service, jQuery,F#, Spec#, Specs Reading, etc&#8230; | GuruStop.NET

Pingback from  Link List: Language Topics, Data Service, jQuery,F#, Spec#, Specs Reading, etc&#8230; | GuruStop.NET