Day 3: Dependent Types in Action

In Day 2, you built some dependent data types, including vectors and a leap year. You may have noticed that these types took more up-front work than before. What features could possibly make all that extra effort worthwhile? Settle in. We’re on the case.

First, we’ll look at the spectacular ways the type system can help you write programs. With more information, Idris can take code completion places you’ve likely never been before. Then, we’ll look at using the type system to reason about the way our programs behave by constructing a proof. Finally, we’ll see how reasoning in Idris can help us improve our programs in other languages. It’s a busy day, so let’s get started.

Smarter Completion

In this section, we’re going to use the Vim editor with an Idris plugin called idris-vim to get a powerful development environment with autocompletion. This tool doesn’t come with the main Idris package, but you can install it easily using the instructions on the project page.^[82]

The plugin works by communicating with a running Idris shell. Launch Idris with a nonexistent file, proof.idr, and then edit the file in Vim by typing :e from within Idris:

​	> idris proof.idr
​	*proof> :e

Now, add the following code to the file in Vim:

idris/day3/proof.idr
​	​module​ ​Proof​
​
​	​data​ ​Natural​ = ​Zero​ | ​Suc​ ​Natural​
​
​	plus : ​Natural​ -> ​Natural​ -> ​Natural​

At this point, you’ve done the heavy lifting: you’ve defined a data type to represent natural numbers. Now, you’re going to write a function to add two natural numbers—but with the help of Idris.

Since Idris knows what your type looks like, it can help with the structure of the program. With the cursor at the end of the last line, type d, the default key to ask idris-vim for a template definition. The skeleton of your function will appear:

​	plus : ​Natural​ -> ​Natural​ -> ​Natural​
​	plus x x1 = ?plus_rhs

Idris has generated a function body from our signature and left a hole, ?plus_rhs, for us to fill (we’ll see how later). This is something any IDE could do. But now, we’re going to go a step further.

Take a peek at the type definition again. We have two cases to cover: Zero and Suc. Idris can use that information to provide a better function definition. Put the cursor over x and hit c. The body of the function will expand to two cases:

​	plus : ​Natural​ -> ​Natural​ -> ​Natural​
​	plus ​Zero​ x1 = ?plus_rhs_1
​	plus (​Suc​ x) x1 = ?plus_rhs_2

Look at that. Idris read your type definition and correctly produced the pattern match on the second argument. Let’s see how far the tool can take us. Place your cursor over the first hole, ?plus_rhs_1, and type o (for obvious):

​	plus ​Zero​ x1 = x1
​	plus (​Suc​ x) x1 = ?plus_rhs_2

This is indeed the correct behavior for adding Zero to any value x. And we didn’t even have to write the code! The only part we have to provide on our own is the body of the second hole:

​	plus : ​Natural​ -> ​Natural​ -> ​Natural​
​	plus ​Zero​ x1 = x1
​	plus (​Suc​ x) x1 = ​Suc​ (plus x x1)

You could switch over to a console to run the program, but there’s a faster way to run a quick test. In idris-vim, you can type e followed by an expression you want to evaluate:

​	​Expression​: plus (​Suc​ ​Zero​) (​Suc​ ​Zero​)

Idris will run the code and show you the result:

​	= ​Suc​ (​Suc​ ​Zero​) : ​Natural​
​
​	​Press​ ​ENTER​ or ​type​ command to continue

1 + 1 never looked so sweet.

As your type definitions get more sophisticated, the tool will be able to write more of your program for you. In the exercises, you’ll get the chance to practice this technique. If you’d like to try it now, have a look at the first medium-difficulty assignment in ​Your Turn​ before we move on.

QED, Dear Watson

Idris can do more than just check types and write parts of programs. It can also prove theorems. There is a deep and beautiful relationship between checking types and proving theorems.^[83] In the limited time we have today, we’ll just be cracking the door into this world.

Idris has an arsenal of different proof strategies. Today, we’re going to combine a few of the simpler tactics to write a proof by induction, a staple of mathematics and computer science.^[84]

What are we going to prove? Let’s show that the plus function we just wrote is commutative—in other words, that plus x y is equal to plus y x for all natural numbers x and y.

A proof by induction has two parts:

• The base case, where we show the property (commutativity) is true for zero

• The inductive step, where we show that, if the property is true for y, then it’s also true for y + 1

For our plus function, that means we need to prove the following two statements:

• plus Zero y = plus y Zero

• If plus x y = plus y x, then plus (Suc x) y = plus y (Suc x)

Where will these proofs go? With Idris, you can embed proofs in your source code files, or you can build them interactively in the REPL. We’re going to hop back and forth between these techniques today.

Anatomy of a Proof

Let’s start by putting the outline of our proof in the source code, and then we’ll fill in the gaps at the console. Add the following line to the end of your proof.idr file:

idris/day3/proof.idr
​	plusCommutes : (x : ​Natural​) -> (y : ​Natural​) -> plus x y = plus y x

Our proof has a signature, just like any other function. Now, it needs a body. Let’s put in the base case first, leaving a hole that we’ll fill in later:

idris/day3/proof.idr
​	plusCommutes ​Zero​ y = ?plusCommutes_0_y

The final piece of the outline is the inductive step.

idris/day3/proof.idr
​	plusCommutes (​Suc​ x) y = ​let​ hypothesis = plusCommutes x y ​in​
​	?plusCommutes_Sx_y

On the right side, you can see how we’ve assumed that plusCommutes x y. It’s up to us to get from there to plusCommutes (Suc x) y, using tiny steps that nudge the proof forward one expression at a time.

The outline of our proof is ready for us to fill in. But we’re going to need some axioms, which are a bit like helper functions. They’re properties of addition that we’re going to use in our proof. Add the following two axioms just before your proof outline:

idris/day3/proof.idr
​	plusZero : (x : ​Natural​) -> plus x ​Zero​ = x
​	plusSuc : (x : ​Natural​) -> (y : ​Natural​) -> ​Suc​ (plus x y) = plus x (​Suc​ y)

plusZero says that any number plus zero is itself. plusSuc deals with adding numbers and then taking the successor. Both of these will come in handy for our proof.

Isn’t it cheating just to assume these two properties are true? Shouldn’t we prove them first, before we’re allowed to use them in another proof? Don’t worry; you’re going to get the chance to do exactly that in the exercises.

Interactive Proof

For now, though, let’s press on. Launch the REPL and load your proof.idr file:

​	Idris>​ :l proof.idr​
​	Type checking ./proof.idr

Now, ask Idris which parts of our proof are missing, using the :m command:

​	*proof> :m
​	Global metavariables:
​	[Proof.plusCommutes_Sx_y,Proof.plusCommutes_0_y]

We see the two holes we left in our outline. Let’s prove the base case first. The :p command starts a proof:

​	*proof> :p plusCommutes_0_y
​	---------- Goal: ----------
​	{ hole 0 }:
​	(y : Natural) -> y = Proof.plus y Zero

Idris is telling us what we have to do to satisfy the conditions of the proof. We have to show that, given y is a natural number, y = plus y Zero.

The first simplfication we can make is to assume that y is indeed a natural number. We do so with the intros proof tactic, which essentially means, “Yes, assume we have the arguments to our function.”

​	-Proof.plusCommutes_0_y>​ intros​
​	---------- Other goals: ----------
​	{ hole 0 }
​	---------- Assumptions: ----------
​	y : Natural
​	---------- Goal: ----------
​	{ hole 1 }:
​	y = Proof.plus y Zero

Idris has filled in our assumption (that y is a natural number), and has given us a new and simpler goal. There’s a bunch of bookkeeping in the middle: holes we haven’t filled yet and assumptions we’ve made so far. From now on, we’ll skip over that stuff in the output.

Look at the bottom line: y = plus y Zero. That’s our new goal. We need to transform the left side of the equals sign until it matches the right.

Do we have any axioms that say we’re allowed to transform y into plus y Zero? Indeed, the plusZero axiom spells out exactly this property. We’ll use Idris’s rewrite proof tactic to rewrite y using plusZero:

​	-Proof.plusCommutes_0_y>​ rewrite (plusZero y)​
​	...​​
​	---------- Goal: ----------
​	{ hole 2 }:
​	Proof.plus y Zero = Proof.plus y Zero

Now, all we have left to prove is that plus y Zero matches plus y Zero. But these already match! The trivial proof tactic exists for this situation:

​	-Proof.plusCommutes_0_y>​ trivial​
​	plusCommutes_0_y: No more goals.

No more goals; that means we’re done with the base case. Use the qed command to finish the proof:

​	-Proof.plusCommutes_0_y>​ qed​
​	Proof completed!
​	Proof.plusCommutes_0_y = proof
​	intros
​	rewrite (plusZero y)
​	trivial

Idris has helpfully summarized our proof steps for us. You can now paste those three lines into proof.idr like so:

idris/day3/proof.idr
​	plusCommutes_0_y = proof {
​	intros
​	rewrite (plusZero y)
​	trivial
​	}

And that’s it for the base case.

The Next Step

Back in the REPL, we can ask Idris which holes still need filling:

​	*proof> :m
​	Global metavariables:
​	[Proof.plusCommutes_Sx_y]

Ah, yes, the inductive step. Let’s start the proof for it:

​	*proof> :p plusCommutes_Sx_y
​	---------- Goal: ----------
​	{ hole 0 }:
​	(x : Natural) ->
​	(y : Natural) ->
​	(Proof.plus x y = Proof.plus y x) -> Suc (Proof.plus x y) = Proof.plus y (Suc x)

As before, we use the intros tactic to assume we have natural numbers for arguments:

​	-Proof.plusCommutes_Sx_y>​ intros​
​	...​​
​	---------- Goal: ----------
​	{ hole 3 }:
​	Suc (Proof.plus x y) = Proof.plus y (Suc x)

Now, we need to transform the left side of the equals sign to match the right side. We need to change Suc (plus x y) into plus y (Suc x). Our plusSuc axiom will make this transformation for us. Let’s apply it, using the rewrite tactic again:

​	-Proof.plusCommutes_Sx_y>​ rewrite (plusSuc y x)​
​	...​​
​	---------- Goal: ----------
​	{ hole 4 }:
​	Suc (Proof.plus x y) = Suc (Proof.plus y x)

So close! The only change left to make is to transform plus x y into plus y x. Do we have anything in our toolbox to fit this situation? Indeed, we do.

Recall that we’re in the inductive step of our proof. We’re showing that, if commutativity holds for x, then it also holds for x + 1. In other words, we’re allowed to assume that plus x y = plus y x. In our proof skeleton, we defined this as the hypothesis variable:

idris/day3/proof.idr
​	plusCommutes (​Suc​ x) y = ​let​ hypothesis = plusCommutes x y ​in​
​	?plusCommutes_Sx_y

Once again, we use the rewrite tactic to change the expression on the left:

​	-Proof.plusCommutes_Sx_y>​ rewrite hypothesis​
​	---------- Goal: ----------
​	{ hole 5 }:
​	Suc (Proof.plus x y) = Suc (Proof.plus x y)

We’re left with a matching left and right side that we can dispatch trivially:

​	-Proof.plusCommutes_Sx_y>​ trivial​
​	plusCommutes_Sx_y: No more goals.
​	-Proof.plusCommutes_Sx_y>​ qed​
​	Proof completed!
​	Proof.plusCommutes_Sx_y = proof
​	intros
​	rewrite (plusSuc y x)
​	rewrite hypothesis
​	trivial

Go ahead and paste the proof steps into your source file:

​	plusCommutes_Sx_y = proof {
​	intros
​	rewrite (plusSuc y x)
​	rewrite hypothesis
​	trivial
​	}

Whew! Let’s take a step back and look at what we’ve accomplished.

What Proofs Do for Us

Imagine how you might make sure plus is commutative in another programming language. You’d probably write a few test cases: zero, equal numbers, large numbers, and so on. Every time you changed your function, you’d rerun your tests.

With Idris, you don’t have to worry about thinking up enough test cases to gain confidence. Your proof shows that plus is commutative for all natural numbers, not just a few arbitrary test values. And it runs every time you compile your source code!

Now, let’s look at a slightly different definition of plus. Can you spot the error?

idris/day3/badProof.idr
​	plus : ​Natural​ -> ​Natural​ -> ​Natural​
​	plus ​Zero​ x1 = x1
*	plus (​Suc​ x) x1 = ​Suc​ (​Suc​ (plus x x1))

When we try to load the program in Idris, we can see the result:

​	Idris>​ :l proof.idr​
​	Type checking ./proof.idr
​	proof.idr:72:19:When elaborating right hand side of Proof.plusCommutes_Sx_y:
​	Can't unify
​	Suc (Proof.plus x y) = Suc (Proof.plus x y)
​	with
​	Suc (Suc (Proof.plus x y)) = Suc (Proof.plus x y)
​
​	Specifically:
​	Can't unify
​	Proof.plus x y
​	with
​	Suc (Proof.plus x y)

Indeed, x + y does not equal x + y + 1.

Commutativity is a pretty simple property. But Idris allows you to construct longer and more useful proofs about your functions and their types. On a typical day, you might try a few different strategies in interactive mode, and then combine them into a programmatic proof.

You can’t prove that every line of your program is correct, of course. But you can check a lot more than you might think. You can show that a function’s behavior is defined for all inputs, or that you’re encrypting your critical data correctly. Once you’ve been down this road, you might be shocked at how little we protect our important programs today.

Does all this talk of theorems and proofs sound a bit lofty? Do dependent types seem like an academic idea that’s difficult to apply in the real world? If so, read on. In the next section, we’re going to see how to use Idris to understand and improve programs written in more mainstream languages.

The Real World

Ideas move faster than codebases can. Most of us will find ourselves working on an older programming language sometimes, or even most of the time. Old programming languages usually fall out of favor because they can no longer express ideas as concisely or powerfully as new ones.

Surely we have to leave the beauty of Idris behind when we go back to our day-to-day programming tasks. Or do we?

Old languages will shape the way you think as surely as newer ones will. As we’ll see, the lessons Idris teaches us apply perfectly well in the real world. In this section, we’re going to use the clean mathematical notation of Idris to design the types for a C++ program.

Part of the joy of defining types in this way is that the implementations are obvious. Accordingly, we’re just going to focus on the types today. If you’d like to implement and compile them, you can do so with the tools we used in ​Outfitting for Adventure​.

A C++ Mess

Let’s say we’re building a GPS application for a bike computer. We will need to track our bike as it moves from location to location. If you’ve read or written much C++ code, you’ve probably seen some classes that look like this:

idris/day3/gps.h
​	#include <string>
​	#include <vector>
​
​	class Trip
​	{
​	public:
​	class Point
​	{
​	public:
​	Point(​double​ lat, ​double​ lon, ​double​ time);
​
​	​double​ lat() ​const​;
​	​double​ lon() ​const​;
​	​double​ time() ​const​;
​
​	​// ...​
​	};
​
​	​void​ addPoint(​double​ lat, ​double​ lon, ​double​ time);
​
​	​void​ setName(​const​ std::string& name);
​	std::string name() ​const​;
​
​	size_t count() ​const​;
​	​const​ Point& getPoint(size_t index) ​const​;
​
​	​// ...​
​	};

A Ride is a list of Points, each of which consists of a latitude, longitude, and time. Each time we get an updated location from the GPS unit, we add a new item to the list.

Our API also allows us to find out how many locations we’ve collected and to get the properties for any particular location.

This design may not get us on the pages of The Daily WTF, but it is definitely a little chaotic. The API doesn’t really capture the intent of what we’re doing, and it’s going to be difficult to answer critical questions:

• Where was the vehicle at a given point in time?

• When was a vehicle closest to a given location?

We can get this information out of the API indirectly, by grabbing the individual points and then doing a bunch of math. As we write more and more code, you’re going to see more and more duplication of effort, and you’ll have to work harder and harder to express the intention behind the design. We need to take a step back.

Denotational Design

We’ll use Idris as a virtual whiteboard for exploring the shape of our program. This technique is called denotational design. Despite the intimidating name, the concept is quite simple. Conal Elliott describes it eloquently in his 2009 term paper Denotational design with type class morphisms.^[85]

Elliott says that programmers should follow two steps to design their types:

1. Describe in mathematical notation what each type should do, without worrying about implementation details.

2. Implement the type using whatever languages, performance hacks, and trade-offs you need.

Idris gives us a nice mathematical notation to describe each type, including the operations we want to perform with it. We’re not just talking about basic function signatures here; we can specify what these operations do. For instance, we could describe a collection’s clear method, and then assert that the collection is empty after clear is called.

Back to the Roots

Let’s boil our GPS example down to its essentials. What is a bike trip? More generally, what is a trip?

Switching to Idris for a second, we want to say that a trip is a sequence of locations over time. We can already hear you jumping ahead to implementation: internal arrays of data points, sampling frequency, and so on. Hold those thoughts and just think about what we need from this type.

What is a location? It doesn’t matter. Maybe it’s a pair of degree coordinates. Maybe it’s a three-dimensional point. Maybe it’s a named waypoint. Any of these concepts would work, and it’s too early to nail down this implementation detail.

At its most basic level, a trip just gives us a location at a point in time. With Idris, we don’t actually have to say what the location type is yet. Thanks to parameterized types, we can write a function that’s valid no matter what the details are.

Here’s how we might express this idea in Idris:

idris/day3/gps.idr
​	​Trip​ : (​Location​ : ​Type​ ** (​Float​ -> ​Location​))

That is, a Trip is a pair of two items: a Location type (whatever that might eventually be) and a function that gives us the location at a particular time (represented by a Float).

An Improvement

Now that we’ve spilled some hard-earned ink on our virtual whiteboard, let’s shift back to C++. How do we express a pair, where one element is a data type and the other is a function?

In C++, we can’t pass data types into ordinary functions. We can, however, pass them into templates, C++’s closest equivalent to dependent types:

idris/day3/gps.h
​	​template​ <​typename​ Location>
​	​class​ Trip
​	{
​	​public​:
​	Location ​operator​()(​double​);
​
​	​// ...​
​	};

This template takes as input a Location type and generates—what, exactly? Not quite a function, like we did in Idris. Instead, we generate the next best thing: a class that we can call like a function; that’s what the operator() method does.

As we did with Idris, we’re using floating-point numbers to represent time.

So, what is a Location? It depends on the application. For this GPS device, it may be something simple like a latitude/longitude pair:

idris/day3/gps.h
​	​typedef​ std::pair<​double​, ​double​> BikeLocation;
​	​typedef​ Trip<BikeLocation> BikeTrip;

For the aerospace simulator we’re writing tomorrow, it’ll be three-dimensional Cartesian coordinates.

Because we started by sketching in Idris, we have a much better conceptual start for our GPS tool. We’ve captured the core idea of our type: providing the location at any given time.

In the first version of the C++ code, we were thinly wrapping a collection type from the standard library. Callers had to worry about individual data points, indices, and counts. But now, we’re exposing only what the user needs. And we’re doing a better job of answering the questions the user cares about.

Even though this is a toy example, you can see the benefit of building a conceptual type in a stronger language and then moving it to C++. As your problem domains get more complex, this benefit grows even stronger.

With a powerful and rich language like Idris, we can only just begin scratch the surface in one short chapter of a book.

It’s time to wrap things up so that you can go make your own discoveries.

Your Turn

Find…

• The mathematical definitions of total function and partial function

• Video and slides for David Sankel’s C++Now 2013 talk, “The Intellectual Ascent to Agda”

• The source code to the Prelude library’s Nat module, which contains several example proofs

• A list of proof tactics available in Idris

Do (Easy):

• Write the signature of a function, typeNamed, that will take the name of a type and return that type. For example, typeNamed "Int" would return the type Int.

• Implement your typeNamed function for a few different types.

Do (Medium):

• Use the techniques in ​Smarter Completion​ to write a Vector data type and a vectorAdd function to add two vectors together.

• Add the keyword total to the beginning of your typeNamed function signature from the Easy section—that is, total typeNamed : .... Reload your file, and see that your function is not total (defined for all inputs). Make your function total by giving it behavior for bad inputs such as "ThisIsNotAType".

Do (Hard):

• Prove the plusZero and plusSuc axioms from ​Anatomy of a Proof​.

• The bike GPS example currently uses plain floating-point numbers to represent time. Change the type definition to allow a custom Time type to be passed in.