Dorian Corompt's Blog

Bringing the querying power of SQL to JavaScript

DorianCorompt — Mon, 21 Jan 2013 18:02:27 GMT

Hello and Happy New Year to everyone, I have been really busy recently and it has been long time I didn't write, however do not worry I didn’t forget I have to finish my functional programming series of articles.

This post comes directly from a session I presented internally about JavaScript advanced programming concepts. I thought it would be a good idea to share some of its content on this blog. This session was mainly to show how to take advantage of the prototype and functional paradigms that JavaScript supports.

If you read my previous articles about F#, you probably understood how useful functional programming concepts are, when it is about handling sets of data. JavaScript does not have the linked list based on pairs representation that most functional programming have, however it has arrays. Let see how we can easily increase the power of JavaScript by extending its Array type with an SQL like query mechanism based on the most functional programming common functions.

First a word about JavaScript arrays…

JavaScript arrays are associative arrays, also called map or dictionaries in other languages. It means they associate a key to a value. Because JavaScript is dynamically typed you can use arrays with mixed keys, or values types.

As you probably know, almost everything in JavaScript is object. However what you perhaps ignore is that all objects are arrays, I don't mean they are based on the Array JavaScript type nor that they share its prototype, but they behave as arrays. Indeed objects slots may be represented as an associative array of properties, since function are closure in JavaScript (aka. first class values) they can be used as values for properties thus representing the concept of methods. So improving the way we use array is not only good to work on data, but also good to work on the code, for meta-programming.

The code below shows that objects and surprisingly even functions (which are objects) can be used as arrays:

JavaScript function doesn’t really have a fixed parameter prototype, thus function arguments number may vary, so it is important to know they can be obtained through the arguments special object variable (not of type Array):

You can see in the example above that it is possible to use Array methods through the Array prototype on non Array type objects because they behave the same.

About the curry function:

Wikipedia:

In mathematics and computer science, currying is the technique of transforming a function that takes multiple arguments (or a tuple of arguments) in such a way that it can be called as a chain of functions, each with a single argument (partial application). It was originated by Moses Schönfinkel and later re-discovered by Haskell Curry. Because of this, some say it would be more correct to name it schönfinkeling.

So from a practical point of view curry helps us to create partially applied functions on the fly without typing a lot of code.

Fold, map, filter the essential tools

In this section I assume you know what the notion of catamorphism is and what are the fold, map and filter functions, if you don’t please read my previous article 1st Class Functions – Power is in simplicity.

Fold can be defined recursively, but since JavaScript works with array and for performance reasons as it should be considered as a collection processing function building block, I prefer to implement it with a loop. It is interesting to highlight that optimizing terminal recursions is not a part of the JavaScript standard but that the most used script engines optimize it.

Here an implementation of fold left in JavaScript:

Once we have fold, we can define map and filter in terms of it:

We can now do funny things with arrays of data:

Give me some power

Now that we have the map and filter operations, let’s augment and empower the JavaScript Array prototype.

We can now use the select and where methods on any new Array type instances.

Look how easily we can query data!

As shown you can use the built in sort operation, and if you need a join don’t forget the concat method. Since from the past few years applications started to become more and more client based, those short functional helpers defined by less than 10 lines of code appeared to me to be quite useful when processing data incoming from web services. As a comics guys would say “With great power comes great responsibility”. I hope you will have great use of it.

8. Quotations – Say “your name”

DorianCorompt — Mon, 03 Sep 2012 13:53:52 GMT

[DRAFT]

Say your name ! ; Say “your name”! Do you understand the difference between those two sentences?

The first uses the meaning of the words “your name”, while the other refers the words themselves. How do you know that? They are quoted.

Sometimes you would like to be able to do the same thing with programming languages. Being able to manipulate the code from the code help us make programs who generate programs, and as crazy at it may sound, it is really powerful. If you are a C# developer you probably know about .NET reflection, F# allows you to go a little further, by manipulating code expressions in a concise safe and statically typed way.

What can you do with F# quotations ?

Most programmers use language constructs such as functions as a mean of abstraction, however most of them don’t use the power of language abstraction. Quotations are a really interesting to create interpreters and compilers using F# code. But why creating a new F# compiler or interpreter?

Look at the web! How many different languages do you need nowadays to code a simple web site such as a blog? Probably HTML, CSS, JavaScript on the client side, C#, Java or PHP and SQL on the server side, so at least five different languages!

Some people think programming problems have their own specific solution better expressed in a specific language, I think it is totally true, so the use of so many languages to create a web site may be justified.

But what if a language is expressive enough to allow to write more specific language within it syntax? I mean a host language embedding an other. This may sound weird but it is actually something which appears really common to functional programmers, especially LISP programmers. Indeed LISP syntax and core primitives are by design really limited, but powerful enough to create all the others. So big LISP programs consist usually in creating and using different embedded languages specifics to some part of the application, for example a language for the UI, one allowing Object Oriented Programming, one SQL like to query data, and one declarative data language to store data in files. Those specifics embedded languages are called Domain Specific Languages (DSL).

By the way minimalistic doesn’t mean powerless, look the matter in this world is composed of no more than a hundred different types of atoms, and actually all the diversity of living creatures have their DNA encoded with four basic building block molecules known as ATGC. In computer sciences, what about the dilemma RISC vs. CISC? Didn’t we “recently” realize that simple RISC architecture such as ARM, easier to build and minimize, thus consuming less energy have a lot of advantages over complexes ones?

A taste of quotations…

It is really easy to define a quotation in F#, you just have to surround code with <@ and @> for typed quotations and <@@ and @@> for untyped quotations. Look at the example below:

The % splicing operator in front of a variable allows the integration of a quotation expression into an other, there is also an untyped %% splicing operator. The evaluation of this code, shows:

Both favoritePlace and code are bindings whose value are expressions, represented by the generic type Quotations.Expr<’a>. You clearly see that the Abstract Syntax Tree (AST) is directly accessible. Refers to the Quotations.Expr<’a> for more information about the expression type constructors available (http://msdn.microsoft.com/en-us/library/ee370577.aspx).

You could imagine transforming, interpreting or compiling this AST using pattern matching on the different constructors.

Making the web easier !

Although we can regret F# lacks LISP macros, it is one of those languages that are expressive enough to allow multi-paradigm programming and the creation of DSL. We could then use F# as a base language for the web. Instead of having those four languages we talked about earlier. We could just only use one! We could then use F# functions to design declarative languages to represents HTML and CSS, use F# type providers syntax modeled by monads to query data sources as a replacement of SQL and basic F# for the logic to replace JavaScript and C#, Java or PHP.

[Coming Soon]

Windows 8: Time to bite the Apple

DorianCorompt — Tue, 19 Jun 2012 08:25:10 GMT

A short post to share a video featuring a new series of well designed slates running on Windows 8:

Important to notice that these slates would be available on both ARM and PC architectures.

7. Workflows – A Monad alias

DorianCorompt — Fri, 25 May 2012 15:43:00 GMT

Monads are one of the most complex concept to apprehend I encountered while learning functional programming, and unfortunately, like many developers I probably use them without understanding all the possibilities they offer. Before talking about what are Monads, it is interesting to understand where they come from. Monads come from Math, and are used as far as I know by two programming Haskell and F#.

Haskell designers philosophy was to create a pure functional programming language: a language without side effects. However there are side effects that you cannot avoid: The first unavoidable type of side effects coming to mind is IOs. Indeed if your functions have to, given the same input always return the same output, it would be impossible to represent some functions such as the one which gets a line typed on the keyboard by the user and returns it as a string. Interactions with the real world generate side effects.

In order to avoid creating an unusable language Haskell designers looked for a way to separate side effects code from the rest of the code, in way that pure and impure code won’t mix, if you introduce an impure function in a pure function the code is tainted as being impure. That’s where Monads come into play.

Monads represent a really generic powerful concept, which has a lot of other usages, as you will see F# don’t even use Monads for IO.

What are Monads?

Wikipedia:

“In functional programming, a monad is a programming structure that represents computations. Monads are a kind of abstract data type constructor that encapsulate program logic instead of data in the domain model. A defined monad allows the programmer to chain actions together and build different pipelines that process data in various steps, in which each action is decorated with additional processing rules provided by the monad. For example, a sequence of arithmetic operations can be controlled to avoid division by zero in intermediate results. Programs written in functional style can make use of monads to structure procedures that include sequenced operations,^[1]^[2] or to define some arbitrary control flows (like handling concurrency, continuations, side effects such as input/output and variable assignment, or exceptions).

Formally, a monad is constructed by defining two operations (bind and return) and a type constructor M that must fulfill several properties to allow the correct composition of monadic functions (i.e. functions that use values from the monad as their arguments). The return operation takes a value from a plain type and puts it into a monadic container of type M. The bind operation performs the reverse process, extracting the original value from the container and passing it to the associated next function in the pipeline.

A programmer uses an existing monad by composing monadic functions to define a new data-processing pipeline. The monad acts as a framework, as it's a reusable behavior that decides the order in which the specific monadic functions in the pipeline are called, and manages all the undercover work required by the computation.^[3] The bind and return operators interleaved in the pipeline will be executed after each monadic function returns control, and will take care of the particular aspects handled by the monad.

The name is taken from the mathematical monad construct in category theory, though the two concepts are not identical.”

This definition is quite big, and hard to understand, let’s highlight the important ideas:

1- A monad is a programming structure that represents computations

2- A defined monad allows the programmer to chain actions together

3- A monad is constructed by defining two operations (bind and return) and a type constructor M that must fulfill several properties to allow the correct composition of monadic functions

Better an example than precept

Let’s say you want to define a function to look for an element in a key value pair list given its key , this function could have the type: (‘a –> (‘a * ‘b) list –> ‘b) if an equality operator is defined for type ‘a.

In the following example the list of pairs is a phone book. It associates contact names with phone numbers. I want to get a phone number given a contact name:

About the contact names chosen in this example: In Warring States period, the whole Japan history might have changed on June 21, 1582, if Hideyoshi had a mobile phone. Due to simple a letter which didn’t come on time, the most powerful Japanese Daimyou, Oda Nobunaga died, killed by one of his men Mitsuhide who misunderstood his true intentions.

Our function lookFor works nice, however it has a quite heavy behavior when a key is not found, it throws an exception. In dynamic typed languages you could return some meaningful value such as a false boolean value if a key is not found. In typed languages such as C# you could use a null value, however you probably know that it has to be handled carefully, since if not some null reference exceptions may appear in your code, returned values need to be checked on each call. That’s why without exception C#, error handling and propagation would look pretty like C:

It is interesting to notice how with the indentation the code is going to the right, making it hard to read. I will talk about it later.

We wish our functions to be able to either return a valid result or a meaningful value to indicate our computation failed, if failed the status should be propagated skipping the next computing steps. And possibly avoiding the code overhead needed to achieve this propagation (which makes your code little by little indent to the right.)

Believe it or not, but Monads can help us here.

First, we are going to create a type to represent the fact a computation may or may not success in returning a value. And then update our lookFor function definition to use this type.

The maybe type is a generic type, when a function successes it will return Just value, and when it fails it will return Nothing:

Although more meaningful, we now have an equivalent to the return valid value or return null value pattern we showed in C#.

Note: There already is a type equivalent to Maybe<’a>, it is defined in the F# core library and called option<’a>.

Let say I want to create a function which given a phone book will check that all my friends contact are in it, and return their numbers. If one of my contact numbers is not in the phone book the whole function should tell me it failed. If you follow the cascading if pattern, you will get something like:

That’s bad right? We still have these redundant checks on the result values, and the code keeps moving to the right. We are going to try factorize this a little first :

We use here a pattern quite common in functional programming languages which consists in capturing continuations with closures (cf. my article on continuations). If you come from non functional language and worked with some asynchronous code, you may be familiar with the concept of callbacks which is similar.

Here we succeeded in factorizing the conditional (match) expressions by defining a check function. This function takes a Maybe value and a function representing a continuation, and according to the value it stops or continue the computation with the value wrapped by the Just constructor.

We are close from a Monad here, actually, if we generalize our code a little more it is one. Conceptually, we have a context, the type representing a possibility of failure, this context wraps a value, and thanks to a function, check in our example we are able to propagate this context through the different steps of our computation by extracting and wrapping back the value into the context. The function we use to wrap back the value into a context is in our specific case the Just type constructor.

If you remember one of the points we highlighted previously: “A monad is constructed by defining two operations (bind and return) and a type constructor M that must fulfill several properties to allow the correct composition of monadic functions”.

The check function we defined is the bind operation, while the Just constructor is our return operation:

Ok, I know, what you are thinking, I just renamed some functions. But it is important to clearly see those two operations. And by defining them we officially created our first Monad!

A Monad, is it only that???

No, no, don’t worry, there is more to come. The previous pattern I showed you may appear quite specific to my error handling problem, but actually it is really generic! So generic that the concept of Monads got its own syntax in Haskell and F#.

But, first I have to admit I lied to you, Monads aren’t called Monads in F#, they are called workflows, or computational expressions. And if you remember the second point we highlighted in the Monad definition, you can easily understand why: “A defined monad allows the programmer to chain actions together”. It is exactly what we did in our error handling example, we chained functions calls, in a way the failure context is managed and propagated between calls.

To define a Monad in F# and take advantage of a syntax I am going to show you, we need to make a builder type.

A builder is a .NET class that contains methods definitions for the bind and return operations, and possibly other operations related to F# monads. To correctly define this class we need at least to implement three methods Return(value), Bind(value, continuation) and Zero(). The Zero() method returns the default Monadic value. Once we have this class, we make a singleton instance from it.

This is the correct way to define a basic Monad in F#.

We can now enjoy a more friendly syntax to rewrite our getContactNumbers function.

Look how nice this code looks!

Our code which was moving to the right and was hardly readable is now really concise and clear. What happened here? We used our singleton instance, curly braces and the new let! and return keywords to improve the readability. Under the hood let! just calls our Monad Bind(…) operation, implicitly capturing the current continuation while the return keyword calls our Monad Return(…) method. If you are an imperative programmer it is really important to understand that the return keyword has strictly nothing to do with the return keyword you may encounter in C, C++, or C# for example: it won’t break the flow of a computation, it is just a way to wrap a value into the context expressed by the used Monad.

You already know a Monad…

I told you the monad concept, although strange at a first glance, is really powerful and generic. The proof is that if you read my previous article on Sequences, you already met and used Monads.

Indeed F# sequences are Monads! And in Haskell even list are monads. Why? Because if you think about it, list or sequences are just a context around values, and you may want to propagate this sequence context through computations while modifying the value(s) wrapped.

Here the yield keyword is a keyword strictly equivalent to the return keyword, it has been introduced to make the return keyword use in sequences more natural. If you know generators in languages such as Python or C#, you probably understand why.

Windows 8, coming soon…

As you probably know, Windows 8 is going to be released in a few weeks. If you already tried to look at how to develop Metro UI applications in C#, you probably encountered two new keywords (C# 5.0): The async, and await keywords.

WinRT the native library behind Metro, has been designed to use and force the use of an asynchronous model for parallelism. Parallelism is necessary to handle time consuming operations outside the UI thread, and then avoiding freezing the UI and degrade the user experience.

The main asynchronous model advantage is that it prevents most developers (95% of them?) to keep playing randomly with threads and synchronization object: This is indeed a fact, most developers don’t know how to correctly use parallelism and…

NON EXPERT DEVELOPER + THREADING + SIDE EFFECTS = CHAOS

You can replace chaos by:

Deadlocks
Inability to debug programs
Program crashing once or twice a month without any reason
Computer crashes
Train accidents
Aircraft crashes
…
End of the world?

And I wondering if it is not the reason why functional programming languages are recently coming back to the scene.

Indeed we are in the era of parallelism: multicore processors / distributed computations and shared resources with cloud computing / web and communication (part of the IOs in a program increasing). Functional languages by discouraging side effects make parallelism safer, and ease its use with a lot of powerful concepts.

The main asynchronous model drawback is that it is not natural. Look at this C# example:

With all this code, I am just reading three lines from a stream through the use of an asynchronous method, and displaying them. Look how intuitive this code can be… And be happy without closures in C#, you couldn’t write it so easily.

Earlier when we were working on the path leading to Monads, I wrote something about the fact callbacks could be considered as a similar concept for continuations. Look at the code, it is moving to the right, and we are capturing continuations, the “which operation should be done next”. You guess it now, there is a Monad to deal with asynchronous operations.

It is called async,in F# and you use it like this:

The use of let! here captures the current continuation and calls it with the result once the page is downloaded.

C# the next functional programming language?

Believe it or not, but after borrowing the concept of garbage collector (LISP), the OOP paradigm (LISP), closures, Linq, C# is now borrowing an other powerful concept from the functional programming world: Monads, more precisely the async particular monad.

WinRT designers made a choice, between allowing developers to use threads – should be read “Making children play with bazooka” – or make the move to a non natural programming model for imperative languages. To turn the asynchronous C# into something useable, they needed a powerful addition coming from the functional programming world.

But we still have a problem here… Among C# developers, who knows about Monads?

Who knows that the await keyword is a disguised bind operation capturing the current continuation within an async method ?

You could rightly argue it is irrelevant since what is important is to know how to use it. I would answer OS designers thought the same way when they introduced preemptive schedulers, and gave developers process/threading APIs.

Bringing CLR’s Power to non .NET languages - Part 1

DorianCorompt — Wed, 25 Apr 2012 15:35:20 GMT

The .NET Framework helps developer boost their productivity by giving them a set of tools and libraries they need to quickly start implementing the core of their software without loosing time on details. The idea behind the Common Language Infrastructure (CLI) is to allow programming languages to interoperate by sharing code through libraries.

To take advantage of these libraries, a lot of languages got their .NET implementation counterparts, with for example: IronPython, IronRuby, or IronScheme. See http://en.wikipedia.org/wiki/List_of_CLI_languages#CLI_languages for more implementations.

Most of these languages when interpreted are implemented in .NET languages and can easily interact with the underlying platform. For compiled languages they generate IL and the result is a .NET assembly.

In the same way you can dynamically load symbols from a shared library, there are times you would like to be able to interact with the .NET Framework from non .NET languages such as C, C++, Java, Perl or PHP.

Through a short series of articles I am going to show you how to achieve this goal and get the power of .NET in all your favorite languages in less than 500 lines of code.

Back to the origin…

Like for software components at a higher level, the best way to make programming languages interoperate with each other is to define some kind of interfaces. If we look what has been done in the past with native languages we can consider as part of this interface: the processor architecture and its instruction set, the binary format with the way symbols are exported, the type sizes and the conventions to call code.

Assuming that your binaries respect this same interface they can freely share symbols. We are going to respect this interface in order to build a bridge library between the native and the .NET worlds. This native library would be then accessible from non .NET languages.

C++++++…

Did I already tell you how much I like C++? (cf. http://blogs.msdn.com/b/doriancorompt/archive/2012/04/25/6-sequences-being-lazy-is-allowed.aspx)

But don’t worry I have good news for you, a nice version of C++ exists in this world! It is C++/CLI! As you probably guessed this version of C++ is targeting the Common Language Infrastructure. Besides the fact it fills some C++ lacks such as automatic memory management and boilerplate code generation for data member accessors, one of the good thing is that it provides you a seamless and simple way to mix native and managed code. Moreover once compiled the binary has both native and managed sections and can export native symbols such as functions using CLR objects.

As a solution for our problem I then suggest to use C++/CLI to build an interoperability DLL, whose functions are dynamically loadable by non .NET languages and which will allow us to use the .NET Framework.

Bridge the two worlds

Exporting the API

To export our DLL symbols we define a macro CLR_API:

Notice that we use extern “C” to avoid C++ symbol names mangling.

Mapping primitive types

First let’s make some typdefs for primitive types. We do so to ensure that primitive types conserve the same size between architectures. For example a long size is 32 bits on a 32 bits architecture while being 64 bits on a 64 bits architecture. A long long is however always 64 bits which matches the CLR long type alias to Int64.

Note that t_decimal, t_char, and t_string don’t match their CLR counterparts, but exists only for the native to native interoperability interface. Bytes strings are used to ensure that languages that don’t support Unicode can still use the interface. The null macro gives C++ a C# flavor, however C++/CLI null pointer is not 0 but the special value nullptr.

Release dynamically allocated memory

C++/CLI will automatically to the marshaling necessary to map our primitive types however we need to handle the case of CLR object references. In C++/CLI CLR object references are accessed through handles. Our native interface to be exported has to hide these CLR object references. The best way to do it is to wrap CLR object handles within plain native C++ objects. Doing so brings a little complexity, since while CLR object are released by the CLR garbage collector, dynamically allocated native objects have to be released manually through the use of the delete operator.

We don’t know when the language using our library will need to release our objects so one of the best solution here, is to use an object reference tracking method such as reference counting used by COM objects. The class below defines the C++ methods needed for our reference counting.

We define two functions to use these references in our interface:

Wrapping CLR objects

Ok we can have a solution for references, we now need to find a way to wrap CLR objects into a native type inheriting from CLRReference. This is done thanks to the use of the following C++ class template:

CLRWrapper<T> wraps the CLR object handle in its private data member value. The gcroot<T> class template provided by C++/CLI allows us to use CLR object as members for native classes by pinning the handle and preventing the garbage collector to play with our reference in memory. As an example of use CLRWrapper<System::Object>* is a wrapper pointer to a the CLR Object type, and the GetValue getter method can be used to get the wrapped CLR object value.

Boxing/Unboxing primitive types

As you will see in a few paragraph to be generic our interface is going to rely on the fact that all CLR objects inherit from the Object class, and boxing and unboxing will be necessary for primitive types, so let define converter functions to do so:

Catch exceptions

While working within the CLR world exceptions might occur, we need a way to represent and handle possible exceptions in our interface, this is done thanks to the template CLRResult<T> class below which inherits from CLRWrapper<T>:

We define two functions in our interface to work with this class instances:

If the C function CLRResultIsSuccess returns true, no exception occurred and the internal exception wrapper pointer will be null, the latter value available otherwise.

Calling code in

In programming everything is basically code executed thanks to processor instructions, or data located in some memory. In the previous sections I mainly wrote about data with primitive types and objects, it is now time to talk about code.

The main purpose is to be able to call CLR methods on CLR objects from a native interface. There are several way of doing this, I chose the solution which gave me the best performances. This solution consists in generating on the fly a delegate, which captures a call to the target method. Once this delegate created it can be cached, and reuse as much as you want without needing to resolve the method on the type again. Therefore once cached the performance are really good and the time needed to call the delegate is nearly the same as if you were calling it directly from .NET! The on the fly generation is possible thanks to the System::Reflection::Emit namespace classes.

Let’s have a look at the interface we are going to implement:

The first function CLRMethodGet is doing the job of resolving the method on a particular type with the specified name and accepting the given parameter types then it generates a delegate of type Method invoking this particular method. Notice that it returns a CLRResult<T> instance since an exception might occur if no method matching the prototype is found on type.

The second function invokes the delegate of type Method given an instance object and a list of arguments, the result of the call is then returned a possible exception might have occurred during the call and can be checked.

To handle all possibilities with these two functions the rules are:

For CLRGetMethod the target method name should be:

.ctor for a constructor.
get_<name> for a property getter.
set_<name> for a property setter.
add_<name> for an event adder.
remove_<name> for an event remover.

For CLRInvoke the instance object may be null for static methods.

Calling code out

The above sections explains how to call .NET methods from a native interface. What about calling native functions from the .NET world? I mean let say we want one of our target language function to be an event handler to some .NET object events.

For this purpose we declare the following function in the interface:

It creates a delegate with the given type from the specified native function pointer.

We are almost done !

As you perhaps noticed we are close to the end, we are however still missing something, the function GetMethod needs Type and Array of Types wrappers as arguments, and CLRInvoke needs an Array of Objects wrappers as argument. Where are we getting CLR type from? From assemblies of course. So we need a way to load assemblies, get type from them based on their names and a way to create and populate CLR arrays.

Done! With these about 40 native C functions we are able to interoperate with the .NET Framework! And some of them could have been defined in term of CLRGetMethod and CLRInvoke within the target language rather than C++/CLI.

End of part 1

I am going to publish the complete sources as soon as possible on Codeplex.

Although this interface can be used directly from C or C++. My next article will show an example of use of this interface from a non .NET exotic language: Racket.

Thank you for reading !

6. Sequences – Being lazy is allowed

DorianCorompt — Wed, 25 Apr 2012 08:47:26 GMT

I remember the day I got the mind shift about functional programming. I switched from being a fervent defender of Java and C# to a passionate of LISP dialects. At the time I was convinced that there were nothing better than OOP and curly bracket syntaxes. I was then fighting for conventions and simplicity rather than language expressivity.

Why do not C and C++ have a module system ?
Why do not have C and C++ a garbage collector ?
Why C does not have namespaces ?
Why C does not have safer string and array primitives ?
Why aren’t Unicode/UTF-8 strings the default in C and C++ ?
Why are the C and C++ libraries naming convention so bad ?
Why is C++ so complex?

As a good ignorant I thought that languages evolved with the time, and that these problems were not addressed because nobody thought about them before. And I discovered LISP the second oldest programming language with none of these problems and even powerful features other languages don’t have such as macros or continuation capture. I got interested in functional programming languages and I learned Haskell, CAML, and finally F#.

I don’t know why but the concept of sequences in functional programming languages amazed me.

How do you perceive infinity?

“How do we perceive infinity?” This is the way Gerald Jay Sussman and Guy L. Steele introduced their presentation about sequences (streams in LISP).

I never thought about it before, since resources on a computer are finite. But interesting question, let say I want to represent the infinite sequence of numbers, what characterizes this infinity and makes it exist? Is it the fact that these numbers are all present in the computer memory at the same time (which is impossible) or the fact that I can get one of them when needed.

How could we possibly define the infinite sequence of natural integers?

Starting from 0 we can recursively define these numbers just by adding one, however this recursion shouldn’t take place until needed, so that the whole number sequence is never in memory. There is no choice that to delay the evaluation of the recursion building the sequence. We could take advantage of the fact that list are pairs, the car of the pair would be a value and the cdr of the pair a delayed evaluation leading to a pair. Delaying a computation, it’s when laziness comes into play.

What is laziness?

Wikipedia: “Laziness (also called indolence) is a disinclination to activity or exertion despite having the ability to do so. It is often used as a pejorative; related terms for a person seen to be lazy include couch potato, slacker, and bludger.”

We are close to what we need !

Although very useful to deal with infinity, as for human laziness is unfortunately not well considered by programming languages. Indeed most programming languages favor eager evaluation over lazy evaluation.

“Never put off until tomorrow what you can do the day after tomorrow.”

Eager evaluation consists in evaluating as soon as possible expressions whereas lazy evaluations consists in evaluating an expression only when it is actually needed.

Below is an example:

In a language like C# this program does nothing valuable except crashing (by exploding the stack). In a language using lazy evaluation this program does nothing. Why? Because DoNothing does nothing with its argument x, so why computing it? However with eager evaluation we start computing immediately the value of x although we don’t need it!

If you think about it you already know some cases of laziness:

Indeed in all languages conditional expressions are lazy. Why? Because if they weren’t, both the consequence and the alternative branches of the condition would be evaluated! However what is expected from a conditional expression is to first evaluate its condition and then depending on the result either evaluate the consequence or the alternative branch. In the same way the and and or short-circuit operators are lazy.

An other way of achieving laziness is to capture expressions into functions. By doing so we are capturing the future of an expression, the value in becoming of this expression, also called its continuation. The problem in languages which doesn’t favor laziness is that you would have to build all these continuations by hand and call them at the right place when needed.

In F# you can get laziness using the lazy keyword or by building sequences. This will ensure you that this expression will be evaluated only when needed.

Let’s do it

Ok we know that we need to build an infinite sequence using laziness. F# has its own sequence type that I am going to present you later, now I want you to look at a simple implementation of infinite sequences (which is really inefficient due to boxing and unboxing needed to escape static typing), the only purpose is to show you how it works:

Here is the result:

Look the infinite integers sequence is a list which starts by 0 and whose next value is not computed yet: “Value is not created”.

With lazyMap, lazyFilter you can operate on integers to create new infinite lists ! If you look at the lazyMap and lazyFilter function definitions you won’t find any break condition, these functions don’t need to stop, since they are working on data with infinite length !

Why do we need lazy sequences?

Resolve algorithms: Infinite sequences allow us to find results for some recursive algorithms especially on big numbers that we couldn’t resolve with traditional methods. We can for example use the sieve of Eratosthenes to get a list of all primes number without excessive computation.
Performance: When using functional programming languages it is common to compose map, filter, fold functions to get a result, each time you apply one of these on a list you are browsing the list from start to end. Thus to map and filter a list you will browse the list twice. Through the use of sequences this could be avoided, since the sequence elements will be mapped and filtered at the same time once the computation is triggered.
Design Patterns: Did you already think about how to model I/O operations? Most languages usually represents them with the concept of streams that can be read from or written to. That’s good but there is nothing revolutionary. What about representing binary files by possibly infinite sequences of bytes and textual files as sequences of characters, words or lines for example? It would mean all your functions working on list could be used naturally
Avoiding side effects: I already told you that side effects are bad, so how to model change for an object without relying on side effects? Sequences can be use to represent each state of an object through time, so no need for side effects.

What are F# sequences?

F# sequences are created using the seq computation expression (cf. my article to come on Workflows). They are represented by the generic type seq<’a> with ‘a being the type of the elements in the sequence. Under the hood they map the well known .NET type IEnumerable<T>. The Seq module provides for use with sequences most of the functions working with lists. Finally F# arrays and lists are instance of seq<’a>.

5. Generic Parameters – Static typing without typing

DorianCorompt — Sat, 03 Mar 2012 18:24:58 GMT

Typing system

The functional core of F# is statically typed, which means all checks concerning typing are done during compile time. Both Statically typed and dynamically typed system have pros and cons. Dynamic typing allows flexibility while static typing allows safeness and speed. Then a lot of programming languages try to get the benefits of both worlds.

A lot of OOP languages uses both dynamic and static typing. So It is the case of course for C# but also for F# which allows imperative language style OOP to ensure a perfect interoperability with the classes and other languages of the .NET Framework.

Compilers for these languages try to optimize and check the code as much as possible, so they favor static typing and allow dynamic typing only when necessary. The good thing about F# is that if you write functional code thanks to generic parameters that I am going to introduce in this article and don’t lay on the imperative style OOP system you don’t need dynamic typing to get flexibility !

The imperative way

Let’s see how C# before its 2.0 version worked with polymorphism to resolve the flexibility versus safeness and speed dilemma (before C# 2.0 generics didn’t exist). Below are the types of polymorphism it supported:

Inclusion
Overloading
Coercion

Example of C# code using those types of polymorphism:

Description:

1) The IList Add method takes an object as a first argument. Since the String class extends from Object you can use a string, this is a static upcast.

2) We convert 1582 which is by default an int to an uint this operation is not safe, but can be statically done since the number is a constant.

3) We use a virtual method on an object, a dynamic link is necessary to find the method implementation to use.

4) The Console class has several overloads for the static method Write. We choose the one taking an object at compile time, this is static.

5) In this case of coercion we are doing a downcast to convert an instance of Object to an instance of the UInt32 class, this is dynamic.

Even if C# could have used dynamic polymorphism all the time, the compiler limited its use to certain types of inclusion and coercion polymorphisms for performance and safeness reasons. This is the reason behind the use of the virtual and override keywords in C#, the developer has to tell the compiler when to make dynamic links for inclusion polymorphism to avoid doing it all the time like in Java. And it also justifies the as keyword which allows you to do quicker static downcast.

From C# v2.0 a new type of polymorphism appeared thanks to the addition of generics in the language: the parametric polymorphism. And guess what? Don Syme the designer and architect of F# worked on it. The advantage of parametric polymorphism is that it allows you a lot of flexibility dynamic typing does but in a statically typed manner, so you get safeness and speed for free.

The functional way

When you writes a function with F#, the compilers tries to infer types for the input(s) and the output if it can’t it gives by default a generic type, represented by variable parameters called generic parameters. Generic parameters are prefixed by a single quote.

What if you want to build the identity function in C# (without generics)?

Knowing all objects extends from Object you could do:

But later at some point in your program you would need to make downcast to operate on the value, so using some dynamic behaviors.

With F# your function is by default generic and everything is static:

This function type is ‘a –> ‘a where ‘a can be int, string, obj, …

F# allows you to build optimized and checked generic operations without any effort !

The simple example above shows you how you can define a function which represents the generic concept of repeating an action three times whatever the action is.

The practical way

Some generic concepts are really pure, it is the case of the identity function. It works for all input you could give it and you don’t need to define specialized implementation.

As long as you play with generic parameters and generic values your algorithm stay generics. As soon as you introduce literal values or non generic functions in your function definition, it becomes tainted, and types are inferred at the expense of genericity.

Sometimes you may believe that primitive functions such as the mathematics operators (+), (-), (*), (/), (%) … use generic parameters because they work for different types and give you some flexibility, but they are using method overloading. The reason is simple, they need to be implemented at the machine level specifying different implementations. If (+) was generic and that you would have used it to add functions what would be its behavior?

Example of how to make a non generic number algorithm generic:

4. 1st Class Functions – Power is in simplicity

DorianCorompt — Sun, 05 Feb 2012 17:14:21 GMT

One of the most interesting article I read about programming languages has been published by the author of Chibi, a small scheme implementation (http://synthcode.com/blog/2009/06/Small_is_Beautiful). The latter tries to defend the idea that beauty and power of programming languages is achieved through simplicity.

While people understand that hiding complexity behind abstractions is a fundamental concept helping mastering problem complexity, they tend to think that adding syntax, and features to programming languages makes them more powerful. I think it is wrong. Programming languages are before of all languages, what matters is their expressivity, not how much keywords they have. Some simple concepts can be really powerful and add a real value while others are insignificant and just add complexity.

The Revised 5th Report on Scheme (R5RS) even states:

“Programming languages should be designed not by piling feature on top of feature, but by removing the weaknesses and restrictions that make additional features appear necessary.”

The simplicity, power, and expressiveness of functional programming languages come from their core: functions.

Although they may look similar they are not the functions you have in imperative languages. They are lambdas (from the mathematical field of lambda calculus). As imperative functions they allow create a new scope and allow code reuse, however what makes lambdas so special is that:

1- They are 1st class values which means they can be bound, passed as arguments or return values from other functions like any other values :

2- They have the interesting property of capturing a part of their environment of definition (we also call them closures) :

Let’s have a closer look at the definition of the makeAdder function:

Look at the x parameter, this parameter is used in the body of the addX function without being declared in its definition parameter list! What happens here is that the addX function definition captured this parameter from its parent scope, we says that x is a free variable in the context of addX. This lambda property may appear useless at the first sight but actually it is the more powerful!

Thanks to the fact that lambda functions capture data, we don’t need data structures anymore! Functional programming languages make the gap between code and data disappear. If you know OOP, you know that the fundamental idea behind it, is to put data with code and encapsulate it, it is exactly what lambdas provide.

F# provides a complete object layer, but let me show you how you could build OOP objects just by using the concept of lambdas:

makePerson is a constructor for person objects with the getFirstName getLastName and getFullName methods. firstName and lastName are free variables in the context of their respective getter methods. I used the unit operator () as an argument in the let expressions in order to ensure that I am binding functions and not just values, indeed let getFirstName = firstName would have bound the value firstName to the symbol getFirstName not built a function.

We can try to play with this code in the interactive console:

The p object represents a person, we can use method on it like this: (p “methodName”)() if the method doesn’t exist we get a failure exception. This object model is simple and well suited for non dynamically typed languages like LISP or even JavaScript, however it is heavy to use in statically typed languages such as F# or Haskell. Indeed, if you try to add a method with a type different than unit –> string it won’t work (though you could use list of objects for arguments…).

3- They can be partially applied (in F# and Haskell for example) and composed :

Lambda functions are defined in mathematics as single input, single output functions, they have a type of ‘a –> ‘b with ‘a and ‘b generic types. However we can use several lambdas together to model a multiple inputs function from unary functions.

For example if we look at the type of the List.map function in the interpreter we get:

Each time you see the (–>) operator it means you are dealing with an unary function whose input is on the left and output on the right of this operator.

The type ((‘a –> ‘b) –> ‘a list –> b’ list) tells us that List.map is an unary function which takes as first parameter an unary function of type (‘a –> b) and returns an unary function list of ‘b and then returns a list of ‘b. When no parenthesis are present in the type, unary functions are considered as forming a multiple inputs function, the right most type being the type of the output. So List.map is a function taking an unary function of type (‘a –> ‘b) as first parameter and a list of ‘a as second parameter and returning a list of type ‘b.

By the way it is interesting to notice that just by reasoning about the type you can discover what a function does, in the case of map you have a function from ‘a to ‘b and a list of ‘a as input and a list of ‘b as output, you can guess that the unary function is applied to each element of the list, and the result collected in the output list.

Ok now that I tell you that, you may think that it is rather complicated for nothing. Except the fact it fits the mathematical model, from a practical programmer point of view what are the benefits of decomposing multiple parameters functions into unary functions?

It allows you to do something powerful called partial application (left currying), which consists in creating new specialized functions from older ones by omitting parameters:

An other interesting feature is composition, function composition and partial application allow you to write really concise code. To compose functions from right to left (the mathematical way) use the (<<) operator function, to compose functions from left to right (can be more natural) use the (>>) operator function.

Focus on the processData function definition, can you guess what this short line of code does?

It reads data from a file
It tokenizes the text of the file using the ‘:’ separator
It converts textual numbers to integers
It multiplies them by 2
Removes those greater than 30
Returns the list of numbers

Do you see how short this function definition in term of code is! That’s a part of the magic coming with functional programming. Composition works with function, in case you would like you start expression to be your value, you can use the pipe operator we saw previously:

Here, we call readData at the beginning of the pipeline, so we are chaining values. Of course the result is the same.

4- They are anonymous, and can be defined when needed.

Lambdas are anonymous values, if they have a name it is only because you bound them to this name. if you want to declare an anonymous lambda you can use the fun keywords. The advantage of anonymous function is that you can create and use them immediately when you need it (see more about it in my article on Sequences and infinite streams).

Below an example showing three ways of defining the same function:

You can also use the function keyword to build an anonymous unary function which applies pattern matching on its parameter (see my article on pattern matching for more information).

5- They are optimized for tail recursion in a lot of functional programming languages implementations including F#.

If you read my article on Recursion you probably understand how important recursion is in functional programming languages. Since recursion is omnipresent it better has to be optimized. This is the case in F#, the compiler translates tail recursion into loops, avoiding to pileup useless context information on the stack. So well written functional recursive code runs as fast as iterative imperative code without exhausting the stack memory.

Pure functions

If your functions are pure (aka they don’t have side effects), you can reason following a simple substitution model: you can substitute a function application with its body if you replace parameters correctly with the arguments of the application. If you do that you can easily understand how functions act. It is a model all programmers use naturally, however this substitution model is only true when there is no side effect. It is one of the main cause of bugs in imperative code which encourages side effects, since you have to remember all the side effects in your code and how they cascade to reason about it!

Catamorphism and anamorphism

Don’t worry I am not cursing you with these two words. Do you remember I told you that map and filter are two very important functions to work with lists (and sequences in general). Actually there are functions more powerful than them.

Look at these definitions:

Do you see what they have in commons?

They browse lists from start to end while performing an action on the car and the cdr. This is a pattern, and in programming we like to capture and abstract patterns to reuse them. The function under this pattern is fold which types is (('a -> 'b -> 'a) -> 'a -> 'b list -> 'a). This type tells us that fold takes a function with an arity of two whose parameters are of types ‘a and ‘b and which returns an ‘a as well as an ‘a and a list of ‘b and then returns an ‘a.

This is how this functions works, we give it an action as first argument, this action is applied on an accumulator value and the first element of the list , we also provides fold a starting value for the accumulator and finally the list we want to fold.

This is how fold is implemented:

This how fold is used:

The 21 lines of code you wrote earlier are now 9 lines of code and you got two new functions for free! that the power of fold and partial application! xcons is a flipped version of the cons operator and reverse a function to reverse a list.

Ok you could say, I specific examples on purpose, so let’s add new functions you would code in about 10 lines of code in imperative languages that you can now write in one:

In these examples we fold from left to right so when we build list results, the list are reversed and we need to reverse them back. If you want to fold a list from right to left you can use another function traditionally called fold right or (foldBack in F#):

So what are the differences between fold left (fold) and fold right (foldBack), which one should I choose?

As you can see from its definition fold left is a tail recursive function, so you are sure that it will be optimized and that it will not make your stack overflow, however when working on lists fold left generates the elements in reverse, forcing you to reverse them back if you want to keep the ordering. Fold right is not tail recursive, however it generates elements in the right order when building lists, so using fold right for small lists and fold left for medium or long list is a good compromise, if you don’t know opt for the left version. As you will see in my article on Sequences, choosing fold right is meaningful when working on infinite lists.

Guess what? fold and foldBack are catamorphisms! You don’t need to re-implement these functions since they are available in the List module. What about anamorphisms? Anamorphisms represent the opposite process, we are now talking about unfolding not folding. The unfold function helps you build a list from a base element, and a generator function applied until a predicate is satisfied.

Here the unfold implementation:

This function is really powerful when you want to build list, you can for example extract an entire stream of values from a file into a list in one line of code! Below two example functions:

Not completely the end…

All these possible features in a simple function concept, and there would be a lot more to say! I hope that thanks to this article you have started to understand how expressive and powerful functions are in functional programming languages. And with these functions, as a consequence to be concise, highly reusable and modular, statically typed, without side effect, your code is likely to be bug free!

3. Pattern Matching – Be Explicit

DorianCorompt — Thu, 26 Jan 2012 18:01:00 GMT

Pattern matching is a way of writing conditional code by mainly decomposing data into subcomponents. It is a high level construct allowing programmers to think naturally about their algorithms rather than in programming terms. Under the hood pattern matching expressions just are empowered if/switch expressions, so don’t worry to use them, they are efficient.

In F# you can do pattern matching on the terms before the (=) operator in a let expression, using the function syntax or the match with syntax. You can decompose most data structures which have a literal representation in the code such as lists, tuples (kind of array containing values of different types), numbers, strings, booleans etc.…

So you can do:

Let see an examples for each of these constructs:

Here the pattern is firstName, lastName, age, which matches a tuple of three values, indeed the comma operator (,) helps to build tuples. Tuples are defined by their size, and type, which is an union of other types. On the right side of the (=) operator, an other tuple “Dorian”, “Corompt”, 23 of size 3 and of type string * string * int , the (*) operator indicating an union of types. Thanks to pattern matching we decompose this tuples, giving the value “Dorian” to firstName, “Corompt” to lastName and 23 to age.

You could also have written:

You can interpret even simple value binding as pattern matching, making it a more general concept. In the example above person is bound to a tuple, you can think person as a named pattern to match everything, and in this precise case it is a tuple.

In the previous example we named the subcomponents in the pattern to get their values, but in some case you don’t need all subcomponents, in these case you can use the joker/wildcard pattern (_) to mach the values that should be ignored.

Let’s say we want to represent a 3D point with a tuple of type float * float * float we need functions to access each coordinates of this structure:

In functional languages functions are standard values (see my article on 1st Class Functions), so you can define them with let since let helps to bind names to values.The syntax is let functionName argument1 argument2 … = body. In our example each functions take one argument (a tuple of three values), we used the (_) joker pattern to represent coordinates we don’t need.

In the interactive console we can try the functions we just defined:

It works as expected.

You already saw a function using pattern matching on numbers:

The function construct returns as value a function taking a single argument on which pattern matching is applied, even if you don’t see it, this argument exists. The pipe (|) allows to define possible branches for the match, the branches patterns are tested sequentially from top to bottom. In the fact definition the first branch matches the pattern 0 which is the same constant value and attributes an expression value to it, 1. The second branch matches everything (with some constraints on the type which is inferred by the compiler) and name the value matched n so it can be used in the expressions associated to this match which is n * fact(n – 1).

The match with construct allows to apply pattern matching on a specific expression. Actually the previous fact definition is equivalent to the following:

The function construct is therefore just a syntax sugar to allow concise definitions of particular pattern matching functions.

I told you that a named pattern of the form n (aka only a name) matches everything, so you may have questions:

Does it mean that if I call fact “test” this will call factorial on a string, matching it with the n pattern?

No, in F# everything is typed, in the first branch you specify 0 –> 1, the compiler infers that your function returns an int and that it takes an int so that x should be an int. The second branch has to confirm this hypothesis. So the compiler looks at n –> n * fact(n - 1), it looks first at the result n * fact(n - 1) , n is of unknown type, fact is of type: int –> int and the (*) operator is of type int –> int so the whole expression should have type int ->int meaning that n and x are of type int.

What if I give a negative integer to this fact definition?

This function will make your program crash. Indeed, take fact –1 one for example, -1 it will be matched against n and lead to n * fact(n - 1), it continues recursion with fact –2; fact –3,… x being negative will never be matched against 0, so this function will loop indefinitely and because this definition is not recursive it will push its context on the stack on each loop iteration, leading to a stack overflow. Of course there is a solution to this problem, we can use condition (or guards) on pattern to put constraints on them. Pattern conditions are specified through the use of the when keyword:

After adding this pattern condition you will get a warning which tells you that your pattern matching is incomplete. What does it mean? It simply means that your matching expression doesn’t take into account all input it could be given. Indeed if you call now fact –1, where does it branch to? If you don’t define an additional pattern it will leads to a match failure runtime exception.

Let’s just add a third branch to correct this and encompass all possible values:

The third branch uses the (_) joker pattern to match everything else (negative integers) and throw a failure exception with the given message thanks to the failwith function.

What if while decomposing list of the form h :: t, I want to keep a reference of the entire list not only the head and the tail?

You can use the as keyword to name pattern components for example (h :: t) as ls –> ls matches a non empty list (it has a head and a tail) and returns its value.

Real life functions

When I speak about functional programming languages with imperative programmer colleagues, they tend to consider them as unusable.

I always hear “They are toys good for maths, experiments, but not real life applications…”

When I hear these words, it makes me smile. The basis of OOP concept, as well as important programming technics such as garbage collection, exception handling, generics, software threads, closures, predicates, sequences, most list manipulation functions or technologies (LINQ for example) they are proud to use in their imperative languages come from functional programming languages…

I recently noticed that after closures, and LINQ the next “big” feature coming to C# is asynchronous operations handling through the use of the await keyword, a new concept heavily used in Windows 8 Metro Style UI programming. As you will see this feature is just a particular application of F# workflows (Haskell Monads) that I will introduce in a next article.

They try to interpret and criticize functional programming from their imperative programming knowledge. As you cannot judge a culture you don’t know or understand you cannot judge a paradigm you never tried. Be open.

I am going to show you how are implemented some “real life” functions that are the pillars of most functional programming languages. And explain you how these functions relates to the .NET LINQ technology.

Let’s say you have a list employees aliases, you want to get their list of emails, where each email is of the form alias@contoso.com. First, what you need is a function taking an alias and returning an email, then a way of mapping this function to each alias in the list.

C# (without LINQ):

And F#:

Thinking imperatively you would try to decompose the second step in something iterative by thinking at the computer level: “I need to iterate through the list, call the function to create the email from the current iteration alias and then adding to a second list”. With a functional programming you think at a high level, you just do what you said!

The map function represents the pattern of applying a function in a context (a list in our case) and returning a new context containing the result. Its non tail recursive implementation for lists is trivial using pattern matching:

Now that you have this email list, let say you want to sort it alphabetically. You would like to sort it efficiently, looking for a solution you found the quicksort algorithm on Wikipedia (you could use the List.sort function, the purpose is to teach you how to think functionally):

Algorithm

Quicksort is a divide and conquer algorithm. Quicksort first divides a large list into two smaller sub-lists: the low elements and the high elements. Quicksort can then recursively sort the sub-lists.

The steps are:

Pick an element, called a pivot, from the list.
Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
Recursively sort the sub-list of lesser elements and the sub-list of greater elements.

The base case of the recursion are lists of size zero or one, which never need to be sorted.

So we need to choose an element as a pivot in the list, let’s take the first element of the list. Then the result is a recursion on the elements of the list smaller than the pivot, the pivot, and a recursion on the element greater than the pivot.

Here a simple and concise implementation in F#:

I did exactly what is stated above. I took the first element of the list p as a pivot thanks to pattern matching, I applied qsort recursively on a list composed of the elements smaller than p thanks to the List.filter function, and I concatenated the result thanks to the list concatenation operator (@) with a list containing the pivot p and a list composed of the elements greater than p on which qsort has been recursively applied.

The fun … –> … construct is a way of creating anonymous functions, learn more about closures with my article on 1st Class Functions.

The filter function represents the pattern of filtering elements in a sequence satisfying a condition, and returning a new sequence of retained elements. Its non tail recursive implementation for lists is trivial using pattern matching:

Functions like f are called predicates, they represent conditions and return a boolean value. We use f in the guard to know if we need to keep the element in the resulting list, or switch to the next branch and keep filtering the remaining elements discarding the first element.

map and filter are amongst the most important functions in functional programming languages.

Do you know LINQ?

In my first example I showed you how creating a list of emails from a list of aliases in F# was concise and clear compared to C#, but you could quite rightly argue that I didn’t use LINQ.

For example if you want to create a list of emails with aliases that contains the ‘o’ letter and then sort it alphabetically in C# with LINQ you could do it easily:

I wrote earlier, that LINQ was coming from functional programming, do you see the link with the functions map, filter and qsort, I have shown you?

Look:

The Select method is just a map, the Where method a filter, and OrderBy method a sorting function!

The (|>) operator is called the pipe operator (same role as the Powershell or UNIX shell pipe), it allows you to chain expressions by calling the function on its right with its right most parameter equals to the result of the expression on the left. If you know Haskell, it is equivalent to a right currying of the function. You will learn more about it when talking about partial function application and composition in my article on 1st Class Function.

It is not a coincidence if LINQ, inferred typing (var) and closures (F# functions are closures) appeared together in C# 3.0. They all are functional concepts.

So if some of your C# developer colleagues tell you how great is C# with LINQ compared to your toys, don’t tell them you could recode LINQ with your toys in 1 line of code, it could be vexing.

2. List – Cons, Car, Cdr & Co

DorianCorompt — Fri, 13 Jan 2012 10:33:16 GMT

Lists are the most important data structures in functional programming languages. It is not for nothing that the first functional programming language, that is by the way the second oldest programming language (1958) is called LISP which stands for “LISt Processing languages”. LISP is all about working with lists to the point that even its source code is written with lists, so the border between data and code is blur, this strange property called homoconicity is really powerful! No more need for serialization, no need for remote procedure call systems, meta-programming is easy, creating new domain specific languages (DSL) becomes easy! To learn more about LISP (see my article about Macros).

What are the terms “cons”, “car” and “cdr”?

“cons” stands for “construct”, “car” for “Contents of the Address part of Register number” and “cdr” for “Contents of the Decrement part of Register number”. “car” and “cdr” were the names given to registers in the first LISP machines. They are now the names of basic list operations available in LISP. “cons” is still in use in most functional languages to name this same operation.

These operators roles are:

The cons function allocates a pair with two value references.
The car function takes a pair and return its first value.
The cdr function takes a pair and return its second value.

What is the relationship between these operations and lists?

If you think more carefully about it, I wrote that the cons operation makes pairs from two values. So what if you build a first pair holding in its first cell (the car cell) a value and in its second cell (the cdr cell) an other pair which contains as its first cell a value and as its second cell a pair and so on…

As the image above shows it, this would build a single linked list! However we need to know when the list ends. We could just say that if the last value is not a pair then it ends, but in this case it would be a somewhat non regular, and there would be a problem, how to represent an empty list? To solve this problem a special value exists, and surprisingly enough it is called “the empty list” ! So the image above represents a list of integers containing the values 42, 69, 613, the NIL at the end represents the empty list. If you read my article about recursion you may already have an idea about where this list definition is going to lead us.

Time to do it in F#!

In F# the cons operator is (::), it is an infix operator. car and cdr are respectively head and tail from the List module, and finally the empty list is [].

You can use the F# interpreter fsi.exe in interactive mode to see the result of the command you type directly, you need to use ;; to end a command within the interpreter. In Visual Studio pressing Ctrl + Alt + F brings the F# Interactive Console.

You should notice that:

After executing a command the result is displayed. In functional programming languages there is always a result. Everything is expression. To be functional code should avoid side effects. If there is no side effects and a function doesn’t return a value, we can assume that from the outside this function when called does nothing, since it cannot modify the environment (side effects), and it can’t return a result. Functional languages are classified by the notion of purity, which is how much they prevent programmers to use side effects. Haskell is for example a really pure language, F# allows imperative programming so it is less pure, but the way your code in F# can be pure. In non-pure functional programming languages a special value is used to represent the result of a function which does nothing else than side effects, in F# this value is the unit and is represented by the () literal.
When the result is displayed val list indicates we were evaluating a value named “list”, the (:) operator specifies the type which is int list so a list of integer (this type could also have been written list<int>), finally the value is indicated after the (=) operator. The list we built using the cons operation is now written in the result as [42; 69; 613], which the way you usually use to declare list literals in F#. So instead of using the cons operation in our sample we could have directly used the latter syntax.
The car or the head of list is 42, and the cdr or tail is [69; 613] which is a list, since the list is made by pairs of pairs.
List types are parameterized, the generic type is ‘a list (or list<’a>) with ‘a being a type parameter. Type parameters are prefixed with a single quote. Thanks to this you can create different list types, for example int list, float list or string list.

What are the advantages of using single linked list?

Using the concept of pairs linked to each others for lists, makes them perfectly fit with the concept of recursion. Therefore you can easily create function working with lists in functional programming languages.

Look at this F# definition for function to compute the length of list for example:

If you remember the definition of fact in my previous article on recursion, you can describe this function as: length is a recursive function doing pattern matching on its first argument, if this first argument is the empty list then the result is 0, if it is a pair whose head is h and tail is t then add 1 to the length of the tail t (remaining of the list).

An other advantage of using pairs in functional programming is about side effects. If you want to make the list grows, you can just prepend a value to it. You use the cons operation with the element you want to add to the list as a first value, and the old list value as a second value for the pair, then without side effect you make the list grow. In the same way if you want to remove a value from a list, just drop the pair holding the concerned value, and its previous pair from the list and create a new pair with the previous pair value as first argument and the next pair as second argument to recreate the link.

How is this list related to the List class from System.Collections.Generic?

F# lists are not related to this class, since they are implemented using pairs whereas the List class from System.Collections.Generic uses a resizable array internally. To avoid the confusion a type alias ResizeArray has been created in F#. Accessing elements or appending elements in single linked list are not efficient operations since they have a complexity of O(n). In an array or array based list these operations are addressed in constant time. So in these cases you may consider to use ResizeArray or the F# arrays that I will introduce in my article on Sequences.

1. Recursion - Where are my for/while loops?

DorianCorompt — Sun, 08 Jan 2012 14:05:36 GMT

Most imperative programmers who start learning functional programming are lost because they don’t see loop constructs in code. Indeed even if some functional languages such as F# provide looping constructs they rarely or sometimes never use them. Why? Because actually they are not necessary, we can get ride of them thanks to a powerful concept: recursion. We say that a function is recursive when it calls itself within its body.

Let’s have a look at an example using the famous factorial function defined by:

The definition on the left is iterative, factorial (!) is defined by a product. The definition on the right is recursive, n! = (n x (n – 1)!) since the function factorial (!) appears before and after the symbol (=).

The C# code below shows how you could implement this function iteratively using a for loop construct:

This function is using an accumulator to store the intermediate computation during each iteration.

Let’s see how you could have implement this recursively in C#:

We can notice that:

We don’t need the for loop anymore.
We don’t need side-effects (aka no assignment)
The function body is slightly shorter.
We don’t need an explicit accumulator variable to store the intermediate computation, instead the n parameter (allocated implicitly on the stack) is used to hold it.

It seems that recursion is more clear and concise so why don’t we use it in C# instead of loops like in functional programming languages?

The answer is simple, developers should not assume that C# as most other imperative languages (C, C++, …) is optimized for recursion. When a function is called it allocates a block of memory called a frame on the stack to store its local variables and return address (if not stored in a register), nested function calls cause the frames to pile up on the stack. If too many nested calls occur, which is likely to happen with some kind of recursion, the stack gets out of memory and the program crashes. Most functional programming languages implementations optimize the recursion process. One type of recursion can be easily optimized, it occurs when a function returns with its own call, we say that the function is tail recursive. An optimized tail recursion has the same performances than a looping construct.

So what about non tail recursive calls? Isn’t it better to use a loop then?

All non tail recursive calls can be converted to tail recursive calls either explicitly or implicitly (through the language implementation) by using a transformation known as “Continuation Passing Style” (CPS)

So the first iterative factorial definition is better in the case of C#.

Below a way of implementing it recursively in F#:

Look how it is concise and clear! It looks like the mathematical definition! You will notice that this function is not tail recursive, indeed the last operation to happen in the second branch is not a direct call to fact, but a call to the multiplication operator (*) with arguments n and fact(n – 1). (see my article on 1st Class Functions to know how to make this function tail recursive)

About the syntax:

The let keyword allows you to bind symbol/names to values. for example let pi = 3.14 will bind the value 3.14 to the name pi. Binding a value is different from assigning a value to a variable, since in functional languages you should not modify the value once it has been bound. Avoiding side effects is great, it protects us from a lot of bugs especially in a parallel environment. You don’t need to precise a type for the pi, like the Haskell compiler, the F# compiler is smart enough to infer it, F# float type in this case, which corresponds to C# double type. Values defined by let are visible in the let body, which is here visible thanks to its indentation, we speak about lexical scope.
The rec keyword specifies that this binding is recursive, so even if fact is not defined yet it will be visible in its lexical scope.
The function keywords allows to create a function which takes a single argument and does pattern matching on it (see my article on pattern matching for more information). It says that:
- if the value of the function is 0 then the result should be 1
- else if the value of the function is n then the result should be n * fact(n - 1)

F# has a for and while construct, but you will rarely use them, since recursion should be preferred, however they are useful in some cases, when generating sequences for example (see my article on Sequences for more information)

An Overview of Functional Programming

DorianCorompt — Sun, 08 Jan 2012 13:19:23 GMT

Obscure syntax, missing looping constructs, unknown programming patterns, the lack of libraries or documentation, there are a lot of reasons discouraging imperative programmers to start learning and using functional programming languages.

Microsoft released in 2002 F#, a multi-paradigm programming language, targeting the .NET Framework, that encompasses functional programming as well as imperative and object-oriented programming disciplines to help address these issues.

F# is first class .NET language, it has a complete access to the .NET Framework, can consume and generate classes, can be either interpreted or compiled to .NET assemblies, and it is well integrated to the Visual Studio Microsoft IDE.

Through a series of articles I would like to introduce some of the powerful F# features and features common to functional languages:

Recursion - Where are my for/while loops?
Discussion about recursion and why loops are rarely used in functional programming.
List – Cons, Car, Cdr & Co
Showing the importance and the power of list processing in functional languages.
Pattern Matching – Be Explicit
A great feature to write clear and concise code.
1st Class Functions – Power is in simplicity
What does it mean to have first class functions, partial application, how to build abstraction with functions.
Generic Parameters – Static typing without typing
Presentation of generic parameters which will help you to make generalist and reusable algorithms.
Sequences – Being lazy is allowed
Usage of laziness to create on demand computations, and infinite streams of data.
Workflows – A Monad alias
Introduction to the concept of monads, how they can be built in F# and what the power they provide.
Quotations – Say “your name”
An overview of meta-programming in F#.
Continuations – Future is yours
Continuations allow non lexical escapes, it is then possible to get coroutines , exception handling, recursion optimizations and more.
Macros – Do you like parenthesis?
This article will presents IronScheme, a Scheme implementation for the .NET, in order to speak about macros in functional programming

Learning functional programming when coming from the imperative world is not something easy, it takes time, but I encourage all of you to try it, since this mind shift will not only help you become better programmers by mastering new concepts, but it will also bring you a lot of fun!

First Entry !

DorianCorompt — Wed, 04 Jan 2012 13:05:00 GMT

Hello future readers,

I am Dorian Corompt, I am a new developer consultant employee at Microsoft France.

As a good resolution for this new year, I decided to start writing a blog to share with you my passion for technologies.

What I intend to publish on this blog:

Comments and feedbacks about new Microsoft products/technologies:
There will be a lot to write here since Microsoft is releasing a lot of new exciting technologies every years.
My first posts under this section will probably target Windows 8 which is coming really soon!
Quick start/How to tutorials, advices and experience concerning our technologies:
Sometimes we browse the internet for hours trying to resolve a little problem we could resolve in 5 minutes with some hints.
.NET programming languages articles:
I like communication and languages, natural languages as well as programming languages or even music and mathematics.
The .NET framework allows a programming languages abstraction, opening new perspective and new way of elegantly solve problems.

I will try to write most of my posts in English to enlarge the audience, so I apologize in advance for the mistakes. I may write some articles in Japanese. And depending on the subject complexity I could switch back to French.

I hope this first entry will be the first of many,

Thanks

Dorian