• RSS
  • Facebook
  • Twitter

Nunc rutrum nunc in enim bibendum at pellentesque est pellentesque. Pellentesque sodales bibendum elit non pulvinar. Mauris fermentum lectus ac risus dapibus cursus eu non ipsum.

  • Example Title 1

    Replace this sample description with your own description. A free premium template by NewBloggerThemes.com.

  • Example Title 2

    Replace this sample description with your own description. A free premium template by NewBloggerThemes.com.

  • Example Title 3

    Replace this sample description with your own description. A free premium template by NewBloggerThemes.com.

    Tuesday, December 30, 2008

    The types used for storing collections of values are list and array. F# list is a typical linked-list type known from many functional languages – it can be either an empty list (written as []) or a cell containing a value and a reference to the tail, which is itself a list (written as value::tail). It is also possible to write a list using a simplified syntax, which means that you can write [1; 2; 3] instead of 1::2::3::[] (which is exactly the same list written just using the two basic list constructors). Array is a .NET compatible mutable array type, which is stored in a continuous memory location and is therefore very efficient – being a mutable type, array is often used in imperative programming style, which will be discussed later. The following example shows declaration of a list value and an implementation of a recursive function that adds together all elements in the list:


    > let nums = [1; 2; 3; 4; 5];;
    val nums : list
    > let rec sum list =
    match list with
    | h::tail -> (sum tail) + h
    | [] -> 0
    val sum : list -> int


    Similarly as earlier we declared a recursive function using let rec and inside the body we used pattern matching to test whether the list is an empty list or a list cell. Note that list is a generic type, which means that it can store values of any F# type. The type in our example is list, which means that the declared instance of list contains integers. Functions working with generic types can be restricted to some specific type - for example the sum function above requires a list of integers that can be added (this is inferred by the type inference, because the default type used with the + operator is int). Alternatively, the function can be generic as well, which means that it works with any lists - for example a function that returns the last element in the list doesn’t depend on the type and so it can be generic. The signature of a generic function to return the last element would be last : list<'a> -> 'a. An important feature when writing recursive functions in F# is the support for tail-calls. This means that when the last operation performed by the function is a call to a function (including a recursive call to itself), the runtime drops the current stack frame, because it isn’t needed anymore - the value returned by the called function is a result of the caller. This minimizes a chance for getting a stack overflow exception. The sum function from the previous example can be written using an auxiliary function that uses a tail recursion as following:

    > // 'acc' is usually called an 'accumulator' variable
    let rec sumAux acc list =
    match list with
    | h::tail -> sumAux (acc + h) tail
    | [] -> acc
    val sum : int -> list -> int
    > let sum list = sumAux 0 list
    val sum : list -> int
    The next data type that we will look at is a record type. It can be viewed as a tuple with named members (in case of record these are called labels), which can be accessed using a dot-notation and as mentioned earlier it is good to use this type when it would be difficult to understand what the members in a tuple represent. One more difference between a record type and a tuple is that records have to be declared in advance using a type construct:


    > // Declaration of a record type
        type Product = { Name:string; Price:int };;


    > // Constructing a value of the 'Product' type
        let p = { Name="Test"; Price=42; };;
    val p : Product


    > p.Name;; val it : string = "Test"



    > // Creating a copy with different 'Name'
        let p2 = { p with Name="Test2" };;
    val p2 : Product



    The last command uses an interesting construct - the with keyword. The record types are by default immutable, meaning that the value of the member can’t be modified. Since the members are immutable you will often need to create a copy of the record value with one (or more) modified members. Doing this explicitly by listing all the members would be impractical, because it would make adding a new members very difficult, so F# supports the with keyword to do this.
    F# records are in many ways similar to classes and they can be, indeed, viewed as simplified classes. Record types are by default immutable, which also means that F# use a structural comparison when comparing two values of a record type (instead of the default reference comparison used when working with classes) and if you need this behavior (e.g. for storing records as a keys in a dictionary) it is very practical to use them. Also, using a record instead of a class is a good idea in a functional code where you can use the with construct. Exposing a record type in a public interface of the module requires additional care and it is often useful to make the labels available as members, which makes it easier to modify implementation of the type later. This topic will be further discussed in the third part of this article series.

    Monday, December 8, 2008

    In the next sample we demonstrate working with the discriminated union type. This type is used for representing a data type that store one of several possible options (where the options are well known when writing the code). One common example of data type that can be represented using discriminated unions is an abstract syntax tree (i.e. an expression in some programming language):


    > // Declaration of the 'Expr' type
    type Expr =
    | Binary of string * Expr * Expr
    | Variable of string
    | Constant of int;;
    (...)
    > // Create a value 'v' representing 'x + 10'
    let v = Binary("+", Variable "x", Constant 10);;
    val v : Expr

    To work with the values of a discriminated union type, we can again use pattern matching. In this case we use the match language construct, which can be used for testing a value against several possible patterns – in case of the Expr type, the possible options are determined by all identifiers used when declaring the type (these are called constructors), namely Binary, Variable and Constant. The following example declares a function eval, which evaluates the given expression (assuming that getVariableValue is a function that returns a value of variable):

    > let rec eval x =
    match x with
    | Binary(op, l, r) ->
    let (lv, rv) = (eval l, eval r)
    if (op = "+") then lv + rv
    elif (op = "-") then lv - rv
    else failwith "Unknonw operator!"
    | Variable(var) ->
    getVariableValue var
    | Constant(n) ->
    n;;
    val eval : Expr -> int


    When declaring a function we can use the let keyword that is used for binding a value to a name. I don’t use a term variable known from other programming languages for a reason that will be explained shortly. When writing a recursive function, we have to explicitly state this using the rec keyword as in the previous example.
    Discriminated unions form a perfect complement to the typical object-oriented inheritance structure. In an OO hierarchy the base class declares all methods that are overridden in derived classes, meaning that it is easy to add new type of value (by adding a new inherited class), but adding a new operation requires adding method to all the classes. On the other side, a discriminated union defines all types of values in advance, which means that adding a new function to work with the type is easy, but adding a new type of value (new constructor to the discriminated union) requires modification of all existing functions. This suggests that discriminated unions are usually a better way for implementing a Visitor design pattern in F#.

    Saturday, December 6, 2008

    Tuples

    The first example demonstrates constructing and deconstructing a tuple type. Tuple is simple type that groups together two or more values of any (possibly different) types, for example int and string:


    >let tuple = (42, "Hello world!");;
    val tuple : int * string
    > let (num, str) = tuple;;
    val num : int val str : string


    As you can see, the compiler deduced a type of the expression that is present on the right side of the equals sign and the F# interactive printed the type, so we can review it. In this example the type of a first element in a tuple is int and the type of the second element is string. The asterisk denotes that the type is a tuple. Similarly, you can define a tuple with more than three elements, but the type changes with the number of elements in a tuple, which means that tuples can't be used for storing an unknown number of values. This can be done using lists or arrays, which will be discussed later.

    The syntax used for deconstructing the value into variables num and str is in general called pattern matching and it is used very often in the F# language – the aim of pattern matching is to allow matching a value against a pattern that specifies different view of the data type – in case of tuple, one view is a single value (of type tuple) and the second view is a pair of two values (of different types). Pattern matching can be used with all standard F# types, most notably with tuples, discriminated unions and record types. In addition, F# also supports generalized pattern matching constructs called active patterns, which are discussed later in this overview.

    Tuple types are very handy for returning multiple values from functions, because this removes the need to declare a new class or use references when writing a function that performs some simple operation resulting in more returned values (especially in places where C# uses ref and out parameters). In general, I would recommend using tuples when the function is either simple (like division with remainder), local (meaning that it will not be accessed from a different module or file) or it is likely to be used with pattern matching. For returning more complicated structures it is better to use record types which will be discussed shortly.
    As already mentioned, F# is a typed functional language, by which I mean that types of all values are determined during the compile-time. However, thanks to the use of a type inference, the types are explicitly specified in the code very rarely as we will see in the following examples. The type inference means that the compiler deduces the type from the code, so for example when calling a function that takes int as an argument and returns string as a result, the compiler can infer the type of the variable where the result is assigned (it has to be string) as well as the type of the variable that is given as an argument (it has to be int). Basic data types (aside from a standard set of primitive numeric and textual types that are present in any .NET language) available in F# are tuple, discriminated union, record, array, list, function and object. In the following quick overview, we will use the F# interactive, which is a tool that compiles and executes the entered text on the fly.
    The F# interactive can be either used from Visual Studio or by running the fsi.exe from the F# installation directory. In the whole article series we will also use the F# lightweight syntax, which makes the code white-space sensitive, but simplifies many of the syntactical rules. To enable the lightweight syntax enter the following command in the FSI:

    > #light;;

    The double semicolon is used as the end of the FSI input and sends the entered text to the compiler. This allows us to enter multiple lines of code in a single command. With a few exceptions (mostly when showing a declaration of a complex type) all the code samples in this article are written as commands for FSI including the double semicolon and the result printed by the FSI. Longer code samples can be entered to FSI as well - just add the double semicolon to terminate the input.

    In one of the papers about F#, the F# designers gave the following description: "F# is a multi-paradigm .NET language explicitly designed to be an ML suited to the .NET environment. It is rooted in the Core ML design and in particular has a core language largely compatible with OCaml". In other words this means that the syntax of the F# language is similar to ML or OCaml (don’t worry if you don’t know these languages, we’ll look at some examples shortly), but the F# language targets .NET Framework, which means that it can natively work with other .NET components and also that it contains several language extensions to allow smooth integration with the .NET object system.

    Another important aspect mentioned in this description is that F# is multi-paradigm language. This means that it tries to take the best from many programming languages from very different worlds. The first paradigm is functional programming (the languages that largely influenced the design of F# in this area are ML, OCaml and other), which has a very long tradition and is becoming more important lately for some very appealing properties, including
    the fact that functional code tends to be easier to test and parallelize and is also extensible in a ways where object oriented code makes extending difficult.

    The second paradigm is widely adopted object oriented programming, which enables interoperability with other .NET languages. In F# it is often used for implementing elementary data types (meaning that the operations on the type are well known and change very rarely), for grouping a set of elementary functions that are together used to perform some complicated operation (i.e. implementing an interface) and also when working with object oriented user
    interface frameworks.

    Finally, the third paradigm supported by F# is language oriented programming (the design of F# in this area is largely influenced by ML, Haskell and also by LINQ). In general, language oriented programming is focused on developing executors for some code which has a structure of a language (be it a declarative language like XML, or a fully powerful language like some subset of F#). In this overview, I will focus on two techniques provided by F# that allow you to give a different meaning to blocks of F# code. In a programming language theory, this is often called internal domain specific languages, because the code is written in the host language, but is specifically designed as a way for solving problems from some specific domain. An example of such language (and an associated executor) is a block of code that is written as a linear code, but is executed asynchronously (in F# this can be implemented using computation expressions), or a query that is written in F#, but is executed as a SQL code by some database server (this can be implemented using F# quotations).

    This text is based on a short overview of the F# language that was included in my bachelor thesis, but I extended it to cover all the important F# aspects and topics. The goal of this article is to introduce all the features in a single (relatively short) text, which means that understanding of a few advanced topics discussed later in the text may require some additional knowledge or previous experience with functional programming.

    Anyway, the article still tries to introduce all the interesting views on programming that the F# language provides and the goal is to show that these views are interesting, even though not all of them are fully explained as they would deserve. Of course, this text won’t teach you everything about F#, but it tries to cover the main F# design goals and (hopefully) presents all
    the features that make F# interesting and worth learning. In this first part I will shortly introduce F# and the supported paradigms that will be discussed further in the text.