Overview: Programming with Expressions

Article
09/12/2011

Applies to: Functional Programming

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.

Using Expressions Instead of Statements
Computation by Calculation
Summary
Additional Resources
See Also

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.

Using Expressions Instead of Statements

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.

Note

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 if … then … else is also an expression in F#. This is more similar to the C# conditional operator (?:) than to if … then … else 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 if … then … else 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.

Computation by Calculation

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.

Start evaluating the call factorial 2:
```
factorial 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
```
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
```
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
```
Reduce the conditional operator expression. Evaluate the condition (1 = 1) and replace the if … then … else expression with the result (1):
```
let f = 1
f * 2
```
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
```
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.

Summary

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.

Additional Resources

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 https://code.msdn.microsoft.com/Chapter-1-Introducing-F-c967460d