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.
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”
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?
Currying has nothing to do with spicy chicken.
The |> operator makes life easier and code better to understand.
If we want to use |> we need curryied functions.
Defining curryied functions is easy – just remove brackets and comma.
We don’t need the complete mathematical theory to use currying.
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.”
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
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.
"Implementing Microsoft Dynamics NAV 2009" is a new book by David Roys (MVP for Dynamics NAV) and Vjekoslav Babic (Dynamics NAV consultant). It shows the new features of Dynamics NAV 2009 in step-by-step explanations of real-world examples.
If you are interested in this book you can read the complete seventh chapter right here on navision-blog.de:
The purpose of this chapter is a teaser introduction to get you excited about the product, what’s in it in general, and what’s in it as compared to previous versions, to give you a little taste of what’s coming up in the book, and explain what the fuss about this new release is all about.
Chapter 2
The RoleTailored client is the new user interface for users of Microsoft Dynamics NAV 2009, and it is completely different to the pervious versions. We’ll take you through the different components of the interface, introduce the terminology, explore the navigation components and page types, and teach you how to personalize the application to meet your own requirements using the extensive personalization features.
Chapter 3
Microsoft Dynamics NAV 2009 introduces a new paradigm to ERP. Instead of the system being focused on the forms that capture and present data and the functions the user can perform, the system is based around the individuals within an organization, their roles, and the tasks they perform. We cover how Microsoft researched the roles and explore the departments, roles, and tasks that have been identified in the Microsoft Dynamics Customer Model. We also show the reader how to assign the standard roles to users, how to create new roles, and how to allow departmental super users to configure the application for their role so that the change is applied to all users with the same profile.
Chapter 4
Microsoft Dynamics NAV is not a product with a Next-Next-Finish type of installation, and it takes a lengthy project to deploy it successfully. We focus on the six phases of the implementation process, and explain each phase with detailed dos and don’ts for a typical implementation. Based on the Dynamics Sure Step implementation methodology with advice liberally sprinkled throughout, special attention is given to new features of Microsoft Dynamics NAV 2009, and where the new capabilities must be taken into account to make most out of the implementation project.
Chapter 5
Every implementation of Microsoft Dynamics NAV 2009 will require the system to be configured to meet the needs of the business. This chapter tells the implementation consultant how to do this from a core financials perspective and provides valuable information that will allow developers to understand more about the application they are changing. We cover basic accounting for programmers, dimensions, and posting groups, and how to use the Rapid Implementation Methodology (RIM) Toolkit to speed things along.
Hardly any standard system can fit the needs of a business out of the box. Either the customer must shape their processes to match the system, or the consultant must shape the system to match the processes, and usually the latter prevails. This chapter explains the process of modifying the system, how to design a viable data model, and how to design and develop a functional user interface for both RoleTailored and Classic clients, without writing any code.
The three-tiered architecture of Microsoft Dynamics NAV 2009 and native Web Services Enablement open up a whole new world of possibilities for NAV implementations. We cover some of the many possibilities for extending the application, allowing the consultant and developer to understand the technologies that are available and their respective design considerations. Our practical examples introduce the NAV programmer to the world of .NET and show how you can use the information available on the internet to develop your own killer .NET add-ons.
Chapter 8
There’s much more to development than programming. It starts with understanding what customer really needs, and usually extends way beyond the system being deployed to a test environment. This chapter focuses on the development phase, and what it takes to get from a concept to a live and working solution.
Chapter 9
After the system goes live, or as it grows, there are periods when new problems may arise, and often their source is far from obvious. This chapter explores the tools and techniques available for detecting problems, pinpointing the source, and helping to remove them from the system quickly and painlessly. It explains how to debug the Service Tier, how to troubleshoot performance issues, what can be done to avoid problems, and how proper planning before design can help to get it right the first time.
Chapter 10
Our sample application focuses on requirements gathering, functional specification creation, solution design, and the eventual build of a prototype. We look at how a business problem can be explored using techniques such as interviewing, use-case modeling, and object-role modeling to create a solution design that can be molded into a working prototype.
Test-Driven development (TDD) is a well known software development technique and follows the mantra “Red-Green-Refactor”. Behavior-Driven Development (BDD) is a response to TDD and introduces the idea of using natural language to express the Unit Test scenarios.
There are a lot of popular testing frameworks around which can be used for BDD including xUnit.net ,NUnit, StoryQ, MSpec, NSpec and NBehave. Most of them can be used with fluent interfaces and therefore provides a good readability of the sources. Some of them even provide the possibility to generate a spec in natural language out of passed Unit tests.
What is a spec?
“A specification is an explicit set of requirements to be satisfied by a material, product, or service.”
American Society for Testing and Materials (ASTM) definition
A spec is an important document for the communication process – it enables domain experts to communicate with developers. But how can you verify the compliance with the spec? The answer is: you have to write unit tests. Even with the mentioned frameworks there is a lot of work to do in order to translate a spec scenario into a Unit Test.
Question 7 in the famous Joel Test is “Do you have a spec?”.
The idea of NaturalSpec is to give domain experts the possibility to express their scenarios directly in compilable Unit Test scenarios by using a Domain-specific language (DSL) for Unit Tests. NaturalSpec is completely written in F# – but you don’t have to learn F# to use it. You don’t even have to learn programming at all.
Example 1 – Specifying a list
Let’s consider a small example. If we want to test a new List implementation a spec could look like this:
[<Scenario>]
let When_removing_an_3_from_a_small_list_it_should_not_contain_3() =
Given [1;2;3;4;5] // “Arrange” test context
|> When removing 3 // “Act”
|> It shouldn't contain 3 // “Assert”
|> It should contain 4 // another assertion
|> Verify // Verify scenario
I used BDD style here and expressed my scenario in a quite natural language. As the comments are indicating the scenario is following the Arrange Act Assert (“AAA”) pattern.
With the Keyword “Given” I can create a test context (the objects I want to test). In this sample I created a list with 5 elements. With the keyword “When” I call a function which does something with my test context. In this case I want to remove the value 3. In the Assert section (keywords “It should” or “It shouldn’t”) I can give some observations, which should hold for my manipulated test context.
When I run this scenario via a NUnit runner (i am using TestDriven.Net) I get the following output:
Scenario: When removing an 3 from a small list it should not contain 3
– Given [1; 2; 3; 4; 5]
– When removing 3
=> It should not contain 3
=> It should contain 4
==> OK
Example 2 – Specifying a factorial function
If you implement factorial function the spec could look like this:
[<Scenario>]
let When_calculating_fac_5_it_should_equal_120() =
Given 5
|> When calculating factorial
|> It should equal 120
|> Verify
[<Scenario>]
let When_calculating_fac_1_it_should_equal_1() =
Given 1
|> When calculating factorial
|> It should equal 1
|> Verify
[<Scenario>]
let When_calculating_fac_0_it_should_equal_0() =
Given 0
|> When calculating factorial
|> It should equal 1
|> Verify
And the output of NaturalSpec would look like this:
Scenario: When calculating fac 0 it should equal 0
– Given 0
– When calculating factorial
=> It should equal 1
==> OK
Scenario: When calculating fac 1 it should equal 1
– Given 1
– When calculating factorial
=> It should equal 1
==> OK
Scenario: When calculating fac 5 it should equal 120
– Given 5
– When calculating factorial
=> It should equal 120
==> OK
Am 20.01.2009 findet zwischen 19:30 und 21:30 Uhr der 1. Stammtisch der .NET User Group Leipzig im Jahr 2009 statt. Treffpunkt ist das TELEGRAPH Café in Leipzig und als besonderes Highlight hat sich Ralf Westphal angekündigt. Eine Anmeldung ist nicht nötig.
Warning: Creating default object from empty value in /www/htdocs/w007928a/blog/wp-content/plugins/wp-referencesmap/GoogleMapsWrapper.php on line 55
