Sequence comprehensions

Before digging deeper into advanced language-oriented features of F#, I'll need to do a small digression and talk about sequence comprehensions. This is a language construct that allows us to generate sequences, lists and arrays of data in F# and as we will see later it can be generalized to allow solving several related problems. Anyway, let's first look at an example that filters an F# list:


> let people = [ ("Joe", 55); ("John", 32); ("Jane", 24); ("Jimmy", 42) ];;
val people : (string * int) list
> [ for (name, age) in people
when age <>
-> name ];;
val it : string list = ["Jane"]

In this example we first declared a list with some data and then used a sequence expression, wrapped between square brackets [ and ], to select only some elements from the list. The use of square brackets indicate that the result should be an F# list (you can also use [| .. |] to get an array or seq { .. } to get a sequence as I'll show later). The code inside the comprehension can contain most of the ordinary F# expressions, but in this example I used one extension, the when .. -> construct, which can be used for typical filtering and projection operations. The same code can be written like this:


> [ for (name, age) in people do
if (age <>
yield name ];;
val it : string list = ["Jane"]

In this example, we used an ordinary for .. do loop (in the previous example the do keyword was missing and we used if .. then condition instead of when. Finally, returning a value from a sequence comprehension can be done using the yield construct. The point of this example is to demonstrate that the code inside the comprehension is not limited to some specific set of expressions and can, in fact, contain very complex F# code. I will demonstrate the flexibility of sequence comprehensions in one more example - the code will generate all possible words (of specified length) that can be generated using the given alphabet:


> let rec generateWords letters start len =
seq { for l in letters do
let word = (start ^ l)
if len = 1 then
yield word
if len > 1 then
yield! generateWords letters word (len-1) }
val generateWords : #seq -> string -> int -> seq
> generateWords ["a"; "b"; "c"] "" 4;;
val it : seq = seq ["aaaa"; "aaab"; "aaac"; "aaba"; ...]

This example introduces two interesting constructs. First of all, we're using seq { .. } expression to build the sequence, which is a lazy data structure, meaning that the code will be evaluated on demand. When you ask for the next element, it will continue evaluating until it reaches yield construct, which returns a word and then it will block again (until you ask for the next element). The second interesting fact is that the code is recursive - the generateWord function calls itself using yield! construct, which first computes the elements from the given sequence and then continues with evaluation of the remaining elements in the current comprehension.

Continue

Language Oriented Programming

Defining precisely what the term language oriented programming means in context of the F# language would be difficult, so I will instead explain a few examples that will demonstrate how I understand it. In general, the goal of language oriented programming is to develop a language that would be suitable for some (more specific) class of tasks and use this language for solving these tasks. Of course, developing a real programming language is extremely complex problem, so there are several ways for making it easier. As the most elementary example, you can look at XML files (with certain schema) as language that are processed by your program and solve some specific problem (for example configuring the application). As a side note, I should mention that I'm not particularly happy with the term ‘language’ in this context, because the term can be used for describing a wide range of techniques from very trivial constructs to a complex object-oriented class libraries, but I have not seen any better term for the class of techniques that I’m going to talk about. What I will focus on in this article is using languages inside F# - this means that the custom language will be always a subset of the F# language, but we will look at ways for giving it a different meaning than the standard F# code would have. In some articles you can also see the term domain specific language, which is quite close to what we're discussing here. The domain specific language is a language suitable for solving some class of problems and in general it can be either external, meaning that it is a separate language (e.g. a XML file) or an internal, meaning that it is written using a subset of the host language. Using this terminology, we will focus on writing internal DSLs in F#. Since this term is not as widely used as functional or object oriented programming which we discussed in earlier parts of this document, let me very quickly introduce why I believe that this is an important topic. I think the main reason why language oriented development is appealing paradigm is that it allows very smooth cooperation of people working on the project - there are people who develop the language and those who use it. The language developers need to have advanced knowledge of the technology (F#) and also of the problem that their language is trying to solve (e.g. some mathematical processing), but they don't need to know about all the problems that are being solved using the language. On the other side, the users of the language need only basic F# knowledge and they can fully focus on solving the real problems.

Discriminated Union as Declarative Language
Probably the simplest example of domain-specific language that can be embedded in the F# code is a discriminated union, which can be used for writing declarative specifications of behavior or for example for representing and processing mathematical expressions:

> type Expr =
| Binary of string * Expr * Expr
| Var of string
| Const of int;;
(...)

> let e = Binary("+", Const(2), Binary("*", Var("x"), Const(4)));;
val e : Expr

In this example we created a discriminated union and used it for building a value representing a mathematical expression. This is of course very primitive ‘language’, but when you implement functions for working with these values (for example differentiation or evaluation) you’ll get a simple language for processing mathematical expressions inside F#. Another problem that could be solved using this technique includes for example configuration of some graphical user interface or definition of template for some simple data manipulation.


Active Patterns
A language feature that is closely related to discriminated unions is called active patterns. Active patterns can be used for providing different views on some data type, which allows us to hide the internal representation of the type and publish only these views. Active patterns are similar to discriminated unions, because they can provide several views on a single value (in the previous example we had a value that we could view either as Binary, Var or Const) and similarly as constructors of discriminated union, active patterns can be used in pattern matching constructs. A typical example, where a type can be viewed using different views is a complex number, which can be either viewed in a Cartesian representation (real and imaginary part) or in a polar form (absolute value and phase). Once the module provides these two views for a complex number type, the internal representation of the type can be hidden, because all users of the type will work with the number using active patterns, which also makes it easy to change the implementation of the type as needed. It is recommended to use active patterns in public library API instead of exposing the names of discriminated union constructors, because this makes it possible to change the internal representation without breaking the existing code. The second possible use of active patterns is extending the ‘vocabulary’ of a language built using discriminated union. In the following example we will implement an active pattern Commutative that allows us to decompose a value of type Expr into a call to commutative binary operator:

> let (|Commutative|_|) x =
match x with
| Binary(s, e1, e2) when (s = "+") || (s = "*") -> Some(s, e1, e2)
| _ -> None;;
val ( |Commutative|_| ) : Expr -> (string * Expr * Expr) option

As you can see, the declaration of active pattern looks like a function declaration, but uses a strangely looking function name. In this case we use the (|PatternName|_|) syntax, which declares a pattern that can return a successful match or can fail. The pattern has a single argument (of type Expr) and returns an option type, which can be either Some(...) when the value matches the pattern or None. As we will show later, the patterns that can fail can be used in a match construct, where you can test a value against several different patterns.
As demonstrated in this example, active patterns can be used in a similar sense in which you can use discriminated unions to define a language for constructing the values. The key difference is that discriminated unions can be used for building the value (meaning that they will be used by all users of the language) and active patterns are used for decomposing the values and so they will be used in a code that interprets the language (written usually by the language designer) or by some pre-processing or optimizing code (written by advanced users of the language).
In the next example we will look at one advanced example of using the numerical language that we define earlier. We will implement a function that tests whether two expressions are equal using the commutativity rule, meaning that for example 10*(a+5) will be considered as equal to (5+a)*10:


> let rec equal e1 e2 =
match e1, e2 with
| Commutative(o1, l1, r1), Commutative(o2, l2, r2) ->
(o1 = o2) && (equal l1 r2) && (equal r1 l2)
| _ -> e1 = e2;;
val equal : Expr -> Expr -> bool

> let e1 = Binary("*", Binary("+", Const(10), Var("x")), Const(4));;
let e2 = Binary("*", Const(4), Binary("+", Var("x"), Const(10)));;
equal e1 e2;;
val it : bool = true


As you can see, implementing the equal function that uses the commutativity rule is much easier using the Commutative active pattern than it would be explicitly by testing if the value is a use of specific binary operator. Also, when we’ll introduce a new commutative operator, we’ll only need to modify the active pattern and the equal function will work correctly.

Continue

Object Oriented Programming

Object Types

Object oriented constructs in F# are compatible with the OO support in .NET CLR, which implies that F# supports single implementation inheritance (a class can have one base class), multiple interface inheritance (a class can implement several interfaces and an interface can inherit from multiple interfaces), subtyping (an inherited class can be casted to the base class type) and dynamic type tests (it is possible to test whether a value is a value of an inherited class casted to a base type). Finally, all object types share a common base class which is called obj in F# and is an alias to the CLR type System.Object.
F# object types can have fields, constructors, methods and properties (a property is just a syntactic sugar for getter and setter methods). The following example introduces the F# syntax for object types:

type MyCell(n:int) =
let mutable data = n + 1
do printf "Creating MyCell(%d)" n

member x.Data
with get() = data
and set(v) = data <- v

member x.Print() =
printf "Data: %d" data
override x.ToString() =
sprintf "(Data: %d)" data

static member FromInt(n) =
MyCell(n)


Type MyCell has a mutable field called data, a property called Data, an instance method Print, a static method FromInt and the type also contains one overridden method called ToString, which is inherited from the obj type and returns a string representation of the object. Finally, the type has an implicit constructor. Implicit constructors are syntactical feature which allows us to place the constructor code directly inside the type declaration and to write the constructor arguments as part of the type construct. In our example, the constructor initializes the mutable field and prints a string as a side effect. F# also supports explicit constructors that have similar syntax as other members, but these are needed rarely.
In the previous example we implemented a concrete object type (a class), which means that it is possible to create an instance of the type and call its methods in the code. In the next example we will look at declaration of an interface (called abstract object type in F#). As you can see, it is similar to the declaration of a class:

type AnyCell =
abstract Value : int with get, set
abstract Print : unit -> unit

The interesting concept in the F# object oriented support is that it is not needed to explicitly specify whether the object type is abstract (interface), concrete (class) or partially implemented (class with abstract methods), because the F# complier infers this automatically depending on the members of the type. Abstract object types (interfaces) can be implemented by a concrete object type (class) or by an object expression, which will be discussed shortly. When implementing an interface in an object type we use the interface .. with construct and define the members required by the interface. Note that the indentation is significant in the lightweight F# syntax, meaning that the members implementing the interface type have to be indented further:

type ImplementCell(n:int) =
let mutable data = n + 1
interface AnyCell with
member x.Print() = printf "Data: %d" data
member x.Value
with get() = data
and set(v) = data <- v

The type casts supported by F# are upcast, used for casting an object to a base type or to an implemented interface type (written as o :> TargetType), downcast, used for casting back from a base type (written as o :?> TargetType), which throws an exception when the value isn’t a value of the specified type and finally, a dynamic type test (written as o :? TargetType), which tests whether a value can be casted to a specified type.


Object expressions

As already mentioned, abstract types can be also implemented by an object expression. This allows us to implement an abstract type without creating a concrete type and it is particularly useful when you need to return an implementation of a certain interface from afunction or build an implementation on the fly using functions already defined somewhere else in your program. The following example implements the AnyCell type:

> let newCell n =
let data = ref n
{ new AnyCell with
member x.Print() = printf "Data: %d" (!data)
member x.Value
with get() = !data
and set(v) = data:=v };;
val newCell : int -> AnyCell

In this code we created a function that takes an initial value as an argument and returns a cell holding this value. In this example we use one more type of mutable values available in F#, called reference cell, which are similar to a mutable values, but more flexible (the F# compiler doesn’t allow using an ordinary mutable value in this example). A mutable cell is created by a ref function taking an initial value. The value is accessed using a prefix ! operator and can be modified using := operator. When implementing the abstract type, we use a new ... with construct with members implementing the functionality required by the abstract type (an object expression can’t add any members). In this example we need a reference cell to hold the value, so the cell is declared in a function and captured in a closure, which means that it will exist until the returned object will be garbage collected.

Continue

.NET interoperability

The .NET BCL is built in an object oriented way, so the ability to work with existing classes is essential for the interoperability. Many (in fact almost all) of the classes are also mutable, so the eager evaluation and the support for side-effects are two key features when working with any .NET library. The following example demonstrates working with the mutable generic ResizeArray type from the BCL (ResizeArray is an alias for a type System.Collections. Generic.List to avoid a confusion with the F# list type):

> let list = new ResizeArray<_>()
list.Add("hello")
list.Add("world")
Seq.to_list list;;
val it : string list = ["hello"; "world"]

As you can see, we used the underscore symbol when creating an instance of the generic type, because the type inference algorithm in F# can deduce the type argument from the code (in this example it infers that the type argument is string, because the Add method is called with a string as an argument). After creating an instance we used Add method to modify the list and add two new items. Finally, we used a Seq.to_list function to convert the collection to the F# list. As a fully compatible .NET language, F# also provides a way for declaring its own classes (called object types in F#), which are compiled into CLR classes or interfaces and therefore the types can be accessed from any other .NET language as well as used to extend classes written in other .NET languages. This is an important feature that allows accessing complex .NET libraries like Windows Forms or ASP.NET from F#.

Continue

Imperative Programming and Mutable Values

Similarly as ML and OCaml, F# adopts an eager evaluation mechanism, which means that a code written using sequencing operator is executed in the same order in which it is written and expressions given as an arguments to a function are evaluated before calling the function (this mechanism is used in most imperative languages including C#, Java or Python). This makes it semantically reasonable to support imperative programming features in a functional language. As already mentioned, the F# value bindings are by default immutable, so to make a variable mutable the mutable keyword has to be used. Additionally F# supports a few imperative language constructs (like for and while), which are expressions of type unit:


> // Imperative factorial calculation
let n = 10
let mutable res = 1
for n = 2 to n do
res <- res * n
// Return the result
res;;
val it : int = 3628800


The use of the eager evaluation and the ability to use mutable values makes it very easy to interoperate with other .NET languages (that rely on the use of mutable state), which is an important aspect of the F# language. In addition it is also possible to use the mutable keyword for creating a record type with a mutable field.

Arrays

As mentioned earlier, another type of value that can be mutated is .NET array. Arrays can be either created using [| .. |] expressions (in the following example we use it together with a range expression, which initializes an array with a range) or using functions from the Array module, for example Array.create. Similarly to the mutable variables introduced in the previous section, the value of an array element can be modified using the <- operator:

> let arr = [| 1 .. 10 |]
val arr : array
> for i = 0 to 9 do
arr.[i] <- 11 - arr.[i]
(...)
> arr;;
val it : array = [| 10; 9; 8; 7; 6; 5; 4; 3; 2; 1 |]

Continue

Expressions and Variable Scoping

The F# language doesn’t have a different notion of a statement and an expression, which means that every language construct is an expression with a known return type. If the construct performs only a side effect (for example printing to a screen or modifying a global mutable variable or a state of .NET object) and doesn’t return any value then the type of the construct is unit, which is a type with only one possible value (written as “()”). The semicolon symbol (;) is used for sequencing multiple expressions, but the first expression in the sequence should have a unit as a result type. The following example demonstrates how the if construct can be used as an expression in F# (though in the optional F# lightweight syntax, which makes whitespace significant and which we used in the rest of this overview, the semicolon symbol can be omitted):


> let n = 1
let res =
if n = 1 then
printfn "..n is one..";
"one"
else
"something else";;
..n is one..
val res : string = "one"

When this code executes it calls the true branch of the if expression, which first calls a side-effecting function, which prints a string and then returns a string ("one") as the result. The result is then assigned to the res value.
Unlike some languages that allow one variable name to appear only once in the entire function body (e.g. C#) or even treat all variables declared inside the body of a function as a variable with scope of the whole function (e.g. Visual Basic or JavaScript), the scope of F# values is determined by the let binding and it is allowed to hide a value by declaring a value with the same name. The following (slightly esoteric) example demonstrates this:


> let n = 21
let f =
if n < n =" n"> print_int n)
else
let n = n / 2
(fun () -> print_int n)
let n = 0
f ();;
42
val it : unit


In this example, the value n declared inside a branch of the if expression is captured by a function created using the fun keyword, which is returned from the if expression and bound to the value named f. When the f is invoked it indeed uses the value from the scope where it was created, which is 42. In languages, where the variable named n would refer to a value stored globally, it would be rather problematic to write a code like this. Of course, writing a code similar to what I demonstrated in this example isn't a good idea, because it makes the code very difficult to read. There are however situations where hiding a value that is no longer needed in the code is practical.

Continue

Function Composition

One of the most interesting aspects of working with functions in functional programming languages is the possibility to use function composition operator. This means that you can very simply build a function that takes an argument, invokes a first function with this argument and passes the result to a second function. For example, you can compose a function fst, which takes a tuple (containing two elements) and returns the first element in the tuple with a function uppercase, which takes a string and returns it in an uppercase:


> (fst >> String.uppercase) ("Hello world", 123);;
val it : string = "HELLO WORLD"
> let data = [ ("Jim", 1); ("John", 2); ("Jane", 3) ];;
val data : (string * int) list
> data |> List.map (fst >> String.uppercase);;
val it : string list = ["JIM"; "JOHN"; "JANE"]


In the first command, we just compose the functions and call the returned function with a tuple as an argument, however the real advantage of this trick becomes more obvious in the third command, where we use the function composition operator (>>) to build a function that is given as an argument to a map function that we used earlier. The function composition allows us to build a function without explicitly using a lambda function (written using the fun keyword) and when this features are used reasonably it makes the code more compact and keeps it very readable.

Continue

Functions

Finally, the type that gives name to the whole functional programming is a function. In F#, similarly to other functional languages, functions are first-class values, meaning that they can be used in a same way as any other types. They can be given as an argument to other functions or returned from a function as a result (a function that takes function as an argument or returns function as a result is called high-order function) and the function type can be used as a type argument to generic types - you can for example create a list of functions. The important aspect of working with functions in functional languages is the ability to create closures – creating a function that captures some values available in the current stack frame. The following example demonstrates a function that creates and returns a function for adding specified number to an initial integer:

> let createAdder n = (fun arg -> n + arg);;
val createAdder : int -> int -> int
> let add10 = createAdder 10;;
val add10 : int -> int
> add10 32;;
val it : int = 42


In the body of the createAdder function we use a fun keyword to create a new unnamed function (a function constructed in this way is called a lambda function). The type of createAdder (int -> int -> int) denotes that when the function is called with int as an argument, it produces a value of type function (which takes an integer as a parameter and produces an integer as a result). In fact, the previous example could be simplified, because any function taking more arguments is treated as a function that produces a function value when it is given the first argument, which means that the following code snippet has the same behavior. Also note that the types of the function createAdder declared earlier and the type of the function add are the same):

> let add a b = a + b;;
val add : int -> int -> int
> let add10 = add 10;;
val add10 : int -> int

When declaring the function value add10 in this example, we used a function that expects two arguments with just one argument. The result is a function with a fixed value of the first argument which now expects only one (the second) argument. This aspect of working with functions is known as currying. Many functions in the F# library are implemented as high-order functions and functions as an arguments are often used when writing a generic code, that is a code that can work with generic types (like list<'a>, which we discussed earlier). For example standard set of functions for manipulating with list values is demonstrated in the following example:

> let odds = List.filter (fun n -> n%2 <> 0) [1; 2; 3; 4; 5];;
val odds : list = [1; 3; 5]
> let squares = List.map (fun n -> n * n) odds;;
val squares : list = [1; 9; 25]

It is interesting to note that the functions that we used for manipulating with lists are generic (otherwise they wouldn’t be very useful!). The signature of the filter function is ('a -> bool) -> list<'a> -> list<'a>, which means that the function takes list of some type as a second argument and a function that returns a true or false for any value of that type, finally the result type is same as the type of the second argument. In our example we instantiate the generic function with a type argument int, because we’re filtering a list of integers. The signatures of generic functions often tell a lot about the function behavior. When we look at the signature of the map function (('a -> 'b) -> list<'a> -> list<'b>) we can deduce that map calls the function given as a first argument on all the items in the list (given as a second argument) and returns a list containing the results. In the last example we will look at the pipelining operator (|>) and we will also look at one example that demonstrates how currying makes writing the code easier - we will use the add function declared earlier:

> let nums = [1; 2; 3; 4; 5];;
val nums : list
> let odds_plus_ten =
nums
|> List.filter (fun n-> n%2 <> 0)
|> List.map (add 10)
val odds_plus_ten : list = [11; 13; 15];;

Sequences of filter and map function calls are very common and writing it as a single expression would be quite difficult and not very readable. Luckily, the sequencing operator allows us to write the code as a single expression in a more readable order - as you can see in the previous example, the value on the left side of the |> operator is given as a last argument to the function call on the right side, which allows us to write the expression as sequence of ordinary calls, where the state (current list) is passed automatically to all functions. The line with List.map also demonstrates a very common use of currying. We want to add 10 to all numbers in the list, so we call the add function with a single argument, which produces a result of the type we needed - a function that takes an integer as an argument and returns an integer (produced by adding 10) as the result.

Continue