Overview: Understanding What a Program Does

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: This overview explains the practical benefits of using immutable data types. It shows how to define immutable types in C# and F# and how immutability makes it easier to understand and test our code. (9 pages)

This topic contains the following sections.

Introducing Imperative and Functional Styles
Understanding Imperative and Functional Code
Declaring Immutable Types
Reading and Refactoring Functional Programs
Testing Immutable Types
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.

Introducing Imperative and Functional Styles

In the usual object-oriented imperative programming style, applications consist of objects that have an internal state that can be changed either directly or by calling some method of the object. The purpose of methods is to encapsulate and hide modifications of the object state. When a method is called, it is difficult to tell what state is affected. Not only because the object may change itself but, more importantly, because it can call other objects that can also change. A single call can cause an entire cascade of updates.

This makes it difficult to understand programs. To find the possible causes of changes to an object's field, the developer needs to find which methods of the object can change the field. Then, you need to find all of the other objects that can call any of these methods. And, the same step needs to be repeated over and over again. As a result, it becomes difficult to refactor and test programs, because small change in source code can have huge consequences. For example, mocking is used to check that a call resulted in an expected state change (a specific method call) in some other part of a program.

This overview discusses how immutability makes it easier to reason about programs. Immutable types are types whose instances cannot change once created. This means that a function or a method cannot change other objects. The only thing it can do is to return some value as a result.

Understanding Imperative and Functional Code

The first example demonstrates a usual snippet that manipulates some objects in C#. The following listing creates an ellipse, gets its bounding box, and calls a method on the returned rectangle. Finally, the ellipse is returned to whatever has called the code block.

Ellipse ellipse = new Ellipse(new Rectangle(0, 0, 100, 100));
Rectangle boundingBox = ellipse.BoundingBox;
boundingBox.Inflate(10, 10);
return ellipse;

How to find out what the state of the Ellipse will be after the code runs just by looking at it? This is hard because boundingBox could be a reference to the bounding box of the ellipse and Inflate could modify the rectangle, changing the ellipse at the same time. Or maybe the Rectangle type is a value type (declared using the struct keyword in C#) that’s copied when we assign it to a variable. Perhaps, the Inflate method doesn’t modify the rectangle and returns a new rectangle as a result, so the third line has no effect.

In functional programming, data structures are typically immutable, which means that they can’t be modified. After the Ellipse or Rectangle is created, it can’t be changed. The only thing that can be done is to create a new Ellipse with a new bounding box. This makes it easy to understand what a program does. The next listing shows what the previous snippet would look like if Ellipse and Rectangle were immutable. Understanding the program’s behavior becomes much easier:

Ellipse ellipse = new Ellipse(new Rectangle(0, 0, 100, 100));
Rectangle boundingBox = ellipse.BoundingBox;
Rectangle smallerBox = boundingBox.Inflate(10, 10);
return new Ellipse(smallerBox);

When writing programs using immutable types, the only thing a method can do is return a result—it can’t modify the state of any objects. In the snippet above, Inflate returns a new rectangle. To return an ellipse with a modified bounding box, a new ellipse is constructed. This approach may feel a bit unfamiliar the first time, but it isn’t a new idea to .NET developers. String is probably the best-known immutable type in the .NET world, but there are many examples, such as DateTime and other value types. In fact, .NET guidelines recommend implementing all value types as immutable.

Functional programming takes this idea further, which helps you to see what a program does because the result of a method fully specifies what the method does. Just like most of the functional concepts, immutability isn’t limited to functional languages.

Declaring Immutable Types

This section declares a simple immutable type in C# and uses it to demonstrate several benefits of the functional programming style. Then, it looks at the same snippet written in F#. In C#, types are mutable by default, so declaring an immutable type is a bit cumbersome. On the other hand, values and types in F# are immutable by default, so the F# version of the snippet will be simpler.

Creating Immutable Game Characters in C#

Immutable types can be demonstrates using a first-person shooting game. The game has some environment (represented by the World type), items that can appear in the world (the Item type), and several characters that live (and die!) in the world. The following snippet shows a part of the class representing the character:

class GameCharacter {
    // All fields are declared as read-only
    readonly int health;
    readonly Point location;

    // Create a character and initialize all the fields
    public GameCharacter(int health, Point location) {
        this.health = health;
        this.location = location;
    }
    // Handle shooting in the game world
    public GameCharacter HitByShooting(Point target) {
        // Returns new instance of the object with updated health
        int newHealth = this.CalculateHealth(target);
        return new GameCharacter(newHealth, this.location);
    }
    // Tests whether the game character is alive
    public bool IsAlive {
        get { return health > 0; } 
    }
    // Find an item in the world that the character wants to pick
    public PickRequest PickItems(World world) {
        foreach(Item it in world.Objects) {
            if (it.Location.IsCloseTo(location))
                return new PickRequest(it);
        } 
        return PickRequest.Empty;
    }

   // NOTE: Other methods and properties omitted
}

A field in C# can be explicitly marked as immutable using the readonly keyword. Even when a field is immutable, the target object can be mutated if the field is a reference to a class that’s not immutable. A truly immutable class needs to have all fields marked as readonly and the types of these fields must be primitive types, value types, or other immutable classes.

According to these conditions, the GameCharacter class is immutable. All of its fields are marked using the readonly modifier—int is a primitive type and Point is a value type. A read-only field can be set only when creating the object, so the state of the object cannot change once it’s initialized. What can be done when an operation needs to modify the state of the game character?

The HitByShooting method gives an answer. It implements a reaction to a shot being fired in the game. It uses the CalculateHealth method (not shown in the sample) to calculate the new health of the character. In an imperative style, it would then update the state of the character, but that’s not possible because the type is immutable. Instead, the method creates a new GameCharacter instance to represent the modified character and returns it as a result.

Implementing a truly immutable type in C# is somewhat cumbersome. It is not possible to use automatically implemented properties (because they always create a field that is not readonly) and all values have to be initialized in a constructor. Writing the same type in F# is much easier…

Creating Immutable Game Character in F#

F# makes implementing immutable types easy. The purpose of this section isn’t to explain type definitions in F# in detail. It just tries to demonstrate that declaring immutable types can be a very simple task if the language supports it.

It is worth noting that, from the .NET point of view, the type produced by the F# compiler will be essentially the same as the type produced by C# compiler. If the two types were compiled to .NET assemblies and referenced from C#, there wouldn’t be any visible difference.

// Declares class with constructor taking two parameters
type GameCharacter(health, location) =

    // Handle shooting in the game world
    member this.HitByShooting(target) =
        // Returns new instance of the object with updated health
        let newHealth = this.CalculateHealth(target)
        GameCharacter(newHealth, location)

    // Tests whether the game character is alive
    member this.IsAlive = health > 0

    // Find an item in the world that the character wants to pick
    member this.PickItems(world:World) =
        world.Objects |> Seq.tryFind (fun it ->
            it.Location.IsCloseTo(location))

   // NOTE: Other methods and properties omitted

When you declare a class in F#, you use the name of the type (in the example GameCharacter) followed by parameters in parentheses. This syntax specifies the primary constructor of the class. Parameters of this constructor are automatically turned into immutable fields of the class if they are used anywhere in the body of the type. This eliminates a large amount of boilerplate code that would otherwise be needed to declare fields and the constructor and copy all the values. Also note that the types of constructor parameters could be omitted—F# infers the type from the usage of the values.

The class contains the same three members as the previous C# version, but there are a few differences in the declarations:

The declaration of HitByShooting method is similar to the C# method. The only difference is that the declaration needs to explicitly name the reference to the current instance (automatically named this in C#), which is done by writing an identifier before the name of the method. For consistency, the sample uses this, but the name could be any F# identifier.
The declaration of IsAlive property is even simpler. F# provides a simplified syntax for read-only properties because this is the most common type of properties in F#. When a property name is followed by an equals sign, it turns the body into a property getter.
Finally, the PickItems method uses type annotations to specify that the parameter is of type World. This is needed because the next line uses world.Objects (to access collection of all objects in the world). This doesn’t give the compiler enough information about the type. The snippet also uses Seq.tryFind function to find the first object that matches a condition. This is just a more functional way of encoding the same behavior.

We’ve seen how to declare an immutable .NET class. As you can see, this can be done in both C# and F# although F# makes it a little easier by automatically turning parameters of a primary constructor into fields and by having simpler syntax for read-only properties. Now, let’s finally answer the question, “How does immutability make code more readable and maintainable?”

Reading and Refactoring Functional Programs

This section analyzes two simple snippets that use the GameCharacter type. The snippets could appear somewhere in the source code of a functional game. What can a person who sees the code for the first time deduce about the two snippets just by looking at them?

var movedMonster = monster.PerformStep();
var inDanger = player.Location.IsCloseTo(movedMonster.Location);
(...)

var demonMonsterHit = 
  demonMonster.HitByShooting(world.GetShotBy(player)); 
var spiderMonsterHit = 
  spiderMonster.HitByShooting(world.GetShotBy(player));
(...)

The first snippet calls the PerformStep method to perform a single step of the game monster AI. Then, it checks whether the monster is close to the player to detect whether the player is in danger. The second snippet handles the shooting by the player in the virtual world. There are two different monsters, and both are updated to reflect a gunshot fired by the player.

Understanding the First Snippet

When all objects in a game are immutable, a method call can't modify any object. Several observations about the examples follow from this simple fact. The first snippet starts by calling the PerformStep method of the monster. The method returns a new monster, and the result is assigned to a variable called movedMonster. The monster is used on the next line to check whether the player is close to it and is thus in danger.

The second line of the code relies on the first one. If the order were changed, the program wouldn’t compile because movedMonster wouldn’t be declared on the first line. In an imperative implementation, the method wouldn’t typically return any result and it would only modify the state of the monster object. The program would still compile after changing the order of lines, but it would start behaving incorrectly.

Refactoring the Second Snippet

The second snippet consists of two lines that create two new monsters in the game with a health property that updates when shooting occurs in the game. The two lines are independent, meaning that we could change their order. Can this operation change the meaning of the program? It appears that it shouldn’t, and when all objects are immutable, it doesn’t. Surprisingly, it might change the meaning in the imperative version if the HitByShooting method changed something in the world. The first call could, for example, destroy the gunshot, so it would affect only the monster tested as the first one.

The snippet also calls world.GetShotBy(player) to find the latest gunshot fired by the current player. This operation may need to search all gunshots currently in the world, so it may take some time to complete. The following refactored version calls the GetShotBy method just once and then uses the result two times:

var shot = world.GetShotBy(player);
var deamonMonsterHit = deamonMonster.HitByShooting(shot); 
var spiderMonsterHit = spiderMonster.HitByShooting(shot);
(...)

Can this modification change the behavior of a program? In imperative programming, it could. If the HitByShooting method destroyed the gunshot object, the code would need to get a new gunshot for each of the lines. Immutability guarantees that calling a method with the same argument twice gives the same result. This means that the results of both GetShotBy calls in the earlier snippet are the same. It also guarantees that the gunshot object shot in the later snippet cannot be changed. As a result, the refactoring is correct no matter what the methods actually do.

As this section demonstrates, immutability simplifies the understanding and maintenance of programs. However, it is also useful for testing…

Testing Immutable Types

An important property of functional code is that the only thing a method can do is to return some values or objects as the result. It cannot modify the state of the object and it cannot change any global states because all objects are immutable. This greatly simplifies testing. A unit test only needs to check that a method returned the right result and it doesn’t need to worry about the rest of the world.

Testing World Interactions

The GameCharacter type has a method PickItems that iterates over all items present in the world looking for items that the character could pick. When it finds an item that is close to it, it returns a PickRequest object specifying that this is an item it wants to pick up. Since the world is also immutable, it cannot directly remove the item from the world.

The code written this way is much easier to test. The following snippet shows a unit test that checks whether the PickItems method correctly finds a nearby object:

[Test]
public void TestPickNearbyItem() {
  // Create world containing objects 
  // and a character close to one object
  var bfg = new Item("XYZ 9000", new Point(21, 31));
  var saw = new Item("Chainsaw", new Point(53, 97));
  var world = World.Empty.AddObjects(bfg, saw);
  var character = new GameCharacter(100, new Point(20, 30));
 
  // Test if character picks the nearby object 
  var pick = character.PickItems(world);
  Assert.Equal(bfg, pick.Object);
}

The test first constructs the world in a certain state. It creates two items (XYZ 9000 and Chainsaw) and then create a world that contains them. To do that, it takes an empty world, World.Empty, and creates a copy that also contains our two items using the AddObjects method. Next, a character is created near to one of the two items (XYZ 9000). The test just calls PickItems method and receives a PickRequest value back. Then, it verifies whether the object to be picked is the expected one.

Writing the same test for a game that uses mutable objects would be a lot more difficult. The PickItems method would change the world so the test would need to verify that the item was removed from the world. But that's not enough! It would also need to check that no other thing in the world was changed. (For example, picking an item in the world shouldn't kill any enemies.)

Writing such tests is very difficult, so there are other ways to test mutable code (for example, using mocking frameworks). Instead of testing whether the world changes correctly, mocking frameworks test whether correct methods of the world (that are used to change it) were called.

Of course, when picking an item, the world actually needs to be modified somehow. This is demonstrated in the next section.

Testing World Changes

When a character wants to pick an item from the world, it returns a PickRequest object specifying which item should be picked. It cannot actually remove the object from the world, because the world is immutable. So, how does the world change?

One option is that the world could have a method ProcessRequests. The method takes a collection of all requests for changes and returns a new state of the world. This way, the world doesn't have to be copied unnecessarily often. Also, the method can resolve conflicts between requests. For example, if two characters want to pick the same item, the game logic can choose which one should pick it. If the world were mutable, it would depend simply on which character was processed first.

The following snippet shows a simple test for the ProcessRequest method:

[Test]
public void TestPickNearbyItem() {
  // Create world containing an object
  var item = new Item("XYZ 9000", new Point(21, 31));
  var world = World.CreateRandom().AddObject(object);

  // Test if updating of the world removes picked object
  var newWorld = world.ProcessRequests(new PickRequest(item));
  var removed = world.Objects.Except(newWorld.Objects)
  // Test that only one item (XYZ 9000) was removed
  Assert.Equal(1, removed.Count());
  Assert.Equal(item, removed.FirstOrDefault());
}

Just as in the previous example, the snippet first constructs a world. For simplicity, it uses a CreateRandom method that generates a random world with various items in it. Then the snippet adds the XYZ 9000 item using AddObject. The test gives a single PickRequest to ProcessRequest to remove the item.

The result of the call is a value representing the new state of the world. The test uses a LINQ method Except to get a collection of all objects that were in the old world but are not included in the new one. Then, it just verifies that there is only one such item and that the item is the one created earlier. The fact that a test could be written nicely using LINQ is not a coincidence. LINQ fits well with the functional style of programming. When writing functional programs, LINQ becomes even more useful.

Summary

This overview started with an example showing some of the problems with understanding programs that use the mutable state. A single method call can cause a cascade of changes in almost any part of the program. Functional programming avoids this problem by using immutable types that cannot change. This makes the code much easier to understand, maintain, and test.

The article demonstrated how to implement an immutable class in C# and F#. In F#, this was more natural because the language supports this style of programming, but you can use immutable types in C# as well. Thanks to immutability, it is possible to determine a surprising amount of information about code without looking at the implementation of the classes or methods.

The end of the overview discussed the testing of functional programs. Because of the single principle that a method can only return some result, testing becomes easier. A test just needs to verify that the returned object matches the requirements.

Additional Resources

The fact that immutability makes code easier to understand isn’t the only benefit of functional languages. For some of the other benefits, you can read the next two sections:

These benefits arise from the fact that functional programming is based on a different set of core principles. The focus on immutable data types and expression-based programming changes the way we think about programs. The following articles give an overview of functional concepts:

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