Was this page helpful?
Your feedback about this content is important. Let us know what you think.
Additional feedback?
1500 characters remaining
Overview: Programming with Expressions

Overview: Programming with Expressions

Visual Studio 2010

Applies to: Functional Programming

Published: January 2010

Authors: Tomas Petricek and Jon Skeet

Referenced Image

Get this book in Print, PDF, ePub and Kindle at manning.com. Use code “MSDN37b” to save 37%.

Summary: Functional programs are written as expressions rather than a sequence of statements. This overview shows examples of this style and demonstrates how it simplifies reasoning about code.

This topic contains the following sections.

This article is an excerpt from Real World Functional Programming: With Examples in F# and C# by Tomas Petricek with Jon Skeet from Manning Publications (ISBN 9781933988924, copyright Manning Publications 2009, all rights reserved). No part of these chapters may be reproduced, stored in a retrieval system, or transmitted in any form or by any means—electronic, electrostatic, mechanical, photocopying, recording, or otherwise—without the prior written permission of the publisher, except in the case of brief quotations embodied in critical articles or reviews.

In imperative languages, an expression is simply a piece of code that can be evaluated and yields a result. For example, a method call or any use of a Boolean or integer operator is an expression. Conversely, a statement is a piece of code that affects the state of the program and doesn’t have a result. A call to a method that doesn’t return any value is a statement because it affects the state of the program, depending on whatever the method does. An assignment also changes the state (by changing the value of a variable) but, in the simplest version, it doesn’t return a value.

NoteNote

An assignment in C# returns a value, so it is possible to write, for example, a = (b = 42);. In the simplest form (discussed here), it’s a statement that assigns a value to a variable without returning anything, such as b = 42;.

Another example of a typical statement is returning from a function using return or escaping a loop using break. Neither of these constructs has any “return value,” and, instead, their only purpose is to change the state of the program. return and break change the currently executing statement of the code (return by jumping back to the code that called the method and break by jumping to just after the end of the loop).

In functional languages, the state is represented by what a function returns and the only way to modify a state is to return a new value. Following this logic, in functional languages, everything is interpreted as an expression with some return value. The next two sections compare C# and F# version of a simple function from this perspective.

Writing Code Using Statements

The starting point of the discussion is a Factorial method written in C#. It is similar to an example from Overview: Working with Immutable Data. This article looks at it from a different perspective. A factorial of n is a factorial of n-1 multiplied by n (for n larger than 1) or 1. The function can be implemented using a loop or using a recursion.

The following example uses recursion. However, the method is still not fully functional because it’s written as a series of statements:

int Factorial(int num) {
    if (num = 1) return 1;
    int f = Factorial(num - 1);
    return f * num;
}

The body of the method consists of three statements. It probably doesn't need an explanation, so the purpose of the following description is to show the difference in terminology between the imperative and the functional version.

The first statement tests whether num is 1 and breaks the evaluation of the method by returning 1 as the result. The next statement declares a new variable (adds it to the scope) and initializes it using a recursive call. Finally, the last statement returns the result and exits from the method.

The next section shows a very similar snippet written in F#. Although the difference in the actual code is quite small, there is a big difference in how the code should be understood.

Writing Code as an Expression

In F#, the body of a function is an expression that is evaluated to get the result. It doesn't use return to return the result (and jump out of the function). Instead, it is simply an expression that can be evaluated. The expression can be very simple (such as num * 10) or it can be a more complicated construct.

An interesting thing is that ifthenelse is also an expression in F#. This is more similar to the C# conditional operator (?:) than to ifthenelse construct, which is a statement. The problem with the conditional operator in C# is that it allows only very limited syntax in its branches. In F#, the branches of conditional expressions can contain anything, even value bindings, because everything is an expression. The next snippet shows an F# version of factorial:

let rec factorial num =
    if num = 1 then 1 else
        let f = factorial (num - 1)
        f * num

Even though the example looks very similar to the previous C# snippet, there are quite a few subtle changes. The following list reviews all of the differences (some of them already sketched before the example):

  • The whole body is a single expression that returns a value. It doesn't use return to break the evaluation in the middle.

  • The ifthenelse construct is an expression that evaluates the expression following then when the condition is true and the expression following else otherwise. It needs both of the branches - if the else branch was missing and the condition was false, the expression couldn't be evaluated!

  • The code in the else branch is also just an expression. A value declaration is a special syntactic element that has to be followed by some expression. It says that the symbol f refers to some value in the body of the expression.

The last point is rather interesting. It says that values can be declared in any part of an expression. Doing this is clearly impossible in C#. There is no way to declare a new variable in the middle of some mathematical expression. In F#, this is perfectly possible. The following is valid F# code:

> 1 + (let num = 2 * 3 in num + num);;
val it : int = 13

To write a let declaration on a single line, the declaration needs to use the in keyword, which delimits the expression in which the symbol is available. The snippet above creates a symbol num and initializes it to 6. The symbol is accessible only in a short part of the expression: num + num.

The approach to write the whole function as a single expression is used in functional languages with good reason. It impacts the understanding of code because it removes the state, such as the values of the variables in scope and the currently executing statement. The next section demonstrates reasoning about code written as an expression.

Programs written as expressions provide a new way of thinking about their execution. To understand how an imperative program executes, one has to understand how its state changes. In a program written using an object-oriented imperative language, the state is not only the internal state of all the objects but also the currently executing statement (in each thread!) and the state of all of the local variables in every stack frame. The fact that the currently executing statement is part of the state is important because it makes tracing the state difficult when writing the program execution down on paper.

Functional programmers use an approach called computation by calculation. This approach is particularly important for Haskell and is beautifully described in Hudak's book The Haskell School of Expression (although the details are not important for learning F#). The idea behind computation by calculation is to start with the original expression (such as a function call) and perform a single step (like replacing the call with the body of the function or calculating the result of a primitive mathematical operation). By repeating this step several times, you can easily analyze how the program evaluates. The following example shows how the computation by calculation helps to understand what happens when a function is called.

  1. Start evaluating the call factorial 2:

    factorial 2
    
  2. Expand the function call using the body of the function. Replace all occurrences of function parameters with the value specified as an argument (num = 2):

    if 2 = 1 then 1 else
        let f = factorial (2 - 1)
        f * 2
    
  3. Reduce the conditional operator expression. First, evaluate the condition (2 = 1) and then continue evaluating the false branch:

    let f = factorial (2 - 1)
    f * 2
    
  4. Expand the function call in order to get a value assigned to the f value. Replace all occurrences of function parameters with the value of the argument (num = 1):

    let f =
        if 1 = 1 then 1 else
            let f = factorial (1 - 1)
            f * 1
    f * 2
    
  5. Reduce the conditional operator expression. Evaluate the condition (1 = 1) and replace the ifthenelse expression with the result (1):

    let f = 1
    f * 2
    
  6. Now that the value of f is evaluated, replace all occurrences of the value f in the rest of the expression with its actual value:

    1 * 2
    
  7. Finally, evaluate the call to the primitive * operator:

    2
    

This way of writing down the computation of functional code is easy. Even though functional programmers don’t spend their lives writing down how their program executes, it’s useful to get used to this kind of computation because it is a powerful way of thinking about functional code.

Tracking down the evaluation of imperative code, such as the earlier C# version of the function, involves writing down the state of all variables on the stack and "code pointer" specifying the currently evaluated statement in the method. This wouldn't necessarily be longer, but it would be harder to understand. The beautiful thing about functional evaluation is that a single expression is reduced step by step until a simple value is obtained.

This overview explains one of the several key functional concepts. Functional programs are written as expressions rather than as a sequence of statements. To demonstrate the difference, the article showed two implementations of a factorial. While the code looked quite similar in both versions, it can be thought of from quite a different point of view.

This different thinking has important consequences on reasoning about programs. Together with immutability, it allows using computation by calculation, which is a method for writing down how functional programs run. Instead of keeping track of changes on the stack, you simply need to expand an expression until it evaluates into a single result.

The fact that code is written as an expression is one of several key functional concepts but it is not the only one. The following articles discuss other concepts that form the functional programming style:

This overview focused on explaining how writing code as an expression manifests itself in functional programs. This article didn't explain the benefits and other functional concepts. These particular topics are covered in the following articles:

To download the code snippets shown in this article, go to http://code.msdn.microsoft.com/Chapter-1-Introducing-F-c967460d

This article is based on Real World Functional Programming: With Examples in F# and C#. Chapters related to the content of this article are:

  1. Book Chapter 2: “Core concepts in functional programming” contains a more detailed explanation of writing programs using expressions instead of statements.

  2. Book Chapter 11: “Refactoring and testing functional programs” demonstrates how we can easily refactor functional code thanks to the fact that everything is an expression.

The following MSDN documents are related to the topic of this article:

  • F# Language Reference contains a table with most of the F# expressions. Note that the table lists all syntactical constructs as expressions and there are no statements.

Show:
© 2015 Microsoft