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

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.