Rash thoughts about .NET, C#, F# and Dynamics NAV.

This is the third part in a “Questions and Answers”-series about the F# BootCamp in Leipzig. This time we will look at lazy evaluation.

Question 5 – What is the difference between “Lazy Evaluation” and “Eager evaluation”?

Lazy evaluation is a technique of delaying a computation until the result is required. If we use eager evaluation an expression is evaluated as soon as it gets bound to a variable.

One participant answered that lazy evaluation is used in most programming languages to calculate boolean expressions faster. For instance in the expression “x() or y()” the function y() is never called if x() returns true.

Of course this answer is correct, but this "short-circuit evaluation" is only a special case of lazy evaluation. The program would also work correctly without it. But if we want to define an infinite sequence then we can not use eager evaluation. Let’s look at an example:

// val fibs: seq<int>
let fibs = (1, 1) |> Seq.unfold(fun (n0, n1) -> Some(n0, (n1, n0 + n1)))

We do not need to understand the concrete syntax of this code here. We’ll discuss this later. Let’s just say fibs is bound to an infinite sequence (IEnumerable<int>) of Fibonacci numbers. You could also write this in C#:

/// <summary>
/// Infinite sequence of Fibonacci numbers.
/// </summary>
public static IEnumerable<int> Fibs()
{
    var n0 = 1;
    var n1 = 1;
    while(true)
    {
        yield return n0;
        var t = n1;
        n1 = n1 + n0;
        n0 = t;
    }
}

The trick is IEnumerable evaluates the elements lazy. Only at the time we take an element from the sequence the element will be computed:

fibs
  |> Seq.take 10
  |> Seq.to_list
  |> printfn "%A" // prints [1; 1; 2; 3; 5; 8; 13; 21; 34; 55]

If we would use eager evaluation then “Seq.take” would never been called. But we can go one step further. If we want to get the first 10 even-valued terms in the Fibonacci sequence, we can write this code:

fibs 
  |> Seq.filter (fun fib -> fib % 2 = 0) // lazy (via pipe)
  |> Seq.take 10                         // lazy (via pipe)
  |> Seq.to_list                         // eager
  |> printfn "%A" 
  
// prints [2; 8; 34; 144; 610; 2584; 10946; 46368; 196418; 832040]

This would be a little bit tricky if we use eager evaluation, but of course this nice laziness comes with some costs for storing intermediate results (and code). So eager evaluation is still often the better choice and sometimes (e.g. DateTime.Now()) it makes no sense to use lazy evaluation – at least not if we don’t reevaluate the function.

Yesterday I was talking about F# at the .NET Developer Group Braunschweig. It was my first talk completely without PowerPoint (just Live-Coding and FlipChart) and I have to admit this is not that easy. But the event was really a big fun and we covered a lot of topics like FP fundamentals, concurrency and domain specific languages (of course I showed “FAKE – F# Make”).

Now I have a bit time before I go to the next BootCamp in Leipzig. Today Christian Weyer will show us exciting new stuff about WCF and Azure.

In the meanwhile I will write here about another important question (see first article) from the F# BootCamp in Leipzig:

Question 4 – Try to explain “Currying” and “Partial Application”. Hint: Please show a sample and use the pipe operator |>.

Obviously this was a tricky question for FP beginners. There are a lot of websites, which give a formal mathematical definition but don’t show the practical application.

“Currying … is the technique of transforming a function that takes multiple arguments (or more accurately an n-tuple as argument) in such a way that it can be called as a chain of functions each with a single argument”

[Wikipedia]

I want to show how my pragmatic view of the terms here, so let’s consider this small C# function:

public int Add(int x, int y)
{
   return x + y;
}

Of course the corresponding F# version looks nearly the same:

let add(x,y) = x + y

But let’s look at the signature: val add : int * int –> int. The F# compiler is telling us add wants a tuple of ints and returns an int. We could rewrite the function with one blank to understand this better:

let add (x,y) = x + y

As you can see the add function actually needs only one argument – a tuple:

let t = (3,4)         // val t : int * int
printfn "%d" (add t)  // prints 7 – like add(3,4)

Now we want to curry this function. If you’d ask a mathematician this a complex operation, but from a pragmatic view it couldn’t be easier. Just remove the brackets and the comma – that’s all:

let add x y = x + y

Now the signature looks different: val add : int -> int –> int

But what’s the meaning of this new arrow? Basically we can say if we give one int parameter to our add function we will get a function back that will take only one int parameter and returns an int.

let increment = add 1      // val increment : (int -> int)
printfn "%d" (increment 2) // prints 3

Here “increment” is a new function that uses partial application of the curryied add function. This means we are fixing one of the parameters of add to get a new function with one parameter less.

But why are doing something like this? Wouldn’t it be enough to use the following increment function?

let add(x,y) = x + y       // val add : int * int -> int 
let increment x = add(x,1) // val increment : int -> int
printfn "%d" (increment 2) // prints 3

Of course we are getting (nearly) the same signature for increment. But the difference is that we can not use the forward pipe operator |> here. The pipe operator will help us to express things in the way we are thinking about it.

Let’s say we want to filter all even elements in a list, then calculate the sum and finally square this sum and print it to the console. The C# code would look like this:

var list = new List<int> {4,2,6,5,9,3,8,1,3,0};
Console.WriteLine(Square(CalculateSum(FilterEven(list))));

If we don’t want to store intermediate results we have to write our algorithm in reverse order and with heavily use of brackets. The function we want to apply last has to be written first. This is not the way we think about it.

With the help of curried functions, partial application and the pipe operator we can write the same thing in F#:

let list = [4; 2; 6; 5; 9; 3; 8; 1; 3; 0]

let square x = x * x

list
 |> List.filter (fun x -> x % 2 = 0) // partial application
 |> List.sum
 |> square
 |> printfn "%A"                     // partial application

We describe the data flow in exactly the same order we talked about it. Basically the pipe operator take the result of a function and puts it as the last parameter into the next function.

What should we learn from this sample?

1. Currying has nothing to do with spicy chicken.
2. The |> operator makes life easier and code better to understand.
3. If we want to use |> we need curryied functions.
4. Defining curryied functions is easy – just remove brackets and comma.
5. We don’t need the complete mathematical theory to use currying.
6. Be careful with the order of the parameter in a curryied function. Don’t forget the pipe operator puts the parameter from the right hand side into your function – all other parameters have to be fixed with partial application.

Last Friday we had a fantastic LearningByTeaching F# BootCamp in Leipzig. Each attendee got homework and had to solve one theoretical question and one programming task. For this two questions they had to present their results to the rest of us and after this I gave my solution in addition.

It was very interesting to see the different strategies and solutions. In this post series I will discuss the questions and some of the possible solutions.

Question 1 – What is “Functional Programming” in contrast to “Imperative Programming”?

This seems to be an easy question but in fact, the attendees had some problems to give a short definition of both functional and imperative Programming.

I didn’t find a formal definition of the terms so my intention was to clarify things with an informal description like the one from Wikipedia:

“In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state. Functional programming has its roots in the lambda calculus, a formal system developed in the 1930s to investigate function definition, function application, and recursion.”

Wikipedia

I think the main aspect here is: avoiding state and mutable data. Maybe the words “side-effect”, recursion and “higher-order functions” could also be used, but they will be discussed in later questions.

On my slides I covered the following aspects:

• Functional programming is a paradigm
• FP tries to avoid shared state
• Functions are first class citizens, enabling higher-order functions
• Pure functions
• no side-effects
• Results calculated only on the basis of input values
• No information storage
• Deterministic
• ==> Debugging and testing benefits
• ==> Thread-safe without locking of data

For further reading I recommend "Conception, evolution, and application of functional programming languages" (Paul Hudak) or “Functional Programming For The Rest of Us” (Slava Akhmechet).

Question 2 – Explain the keyword “let”. In F# we are talking about “let-bindings” and not “variables”. Why?

Basically you use the let keyword to bind a name to a value or function. It won’t change any more, so a binding is immutable at default and not “variable”.

I was glad to see the presenter showing the problem with an imperative assignment like
x = x + 1, which from a mathematical view is paradoxical. There is no x which equals x plus one. I think choice of the F# assignment operator is better than equality sign. The statement x <- x + 1 shows the real intention. I want to put the old value of x plus one into the memory cell where x was before.
So we discussed some basic terms like scope and mutability here and I showed how we can explicitly tell the compiler to use mutable data using reference cells or mutable variables.

Maybe it wasn’t that good idea to discuss “Imperative F#” at such an early point (without knowing any functional concepts), but it showed the contrast to immutable let-Bindings.

Question 3 – What is a recursion? Try to explain why we often want recursions to be tail-recursive. Hint: Look at the following C# program. What is the problem and how could you solve it?

public static Int64 Factorial(Int64 x)
{
    if (x == 0) return 1;
    return x*Factorial(x - 1);
}
…
Factorial(10000);

It was interesting to see that nearly nobody expected a real problem in such a short code snippet. Some attendees thought this program might have an integer overflow – but only the presenters (they tested the program) gave the right answer (stack overflow). In fact they gave a very good and deep explanation about recursion and the problem on the stack.

As the question hinted, a possible solution was adding a accumulator variable and using tail-recursion:

public static BigInt FactorialTailRecursive(BigInt x, BigInt acc)
{
    if (x == BigInt.Zero) return acc;
    return FactorialTailRecursive(x - BigInt.One, x*acc);
}

Unfortunately this "trick" doesn’t work in C# (the compiler doesn’t use tail calls), but it leads to the correct idea – converting it to a while-loop. Of course I would prefer the tail-recursive F# solution:

/// Tail recursive version
let factorial x = 
  let rec tailRecursiveFactorial x acc =
    match x with
      | y when y = 0I -> acc
      | _ -> tailRecursiveFactorial (x-1I) (acc*x)           

  tailRecursiveFactorial x 1I

We didn’t cover continuation passing here. I think this could be something for an advanced session.

Next time I will discuss the rest of the introduction and show some of the first programming tasks.