Correct by Construction Programming in Agda


In a dependently typed programming language you can get much stronger static guarantees about the correctness of your program than in most other languages. At the same time, dependent types enable new forms of interactive programming, by letting the types guide the construction of the program. Dependently typed languages have existed for many years, but only recently have they become usable for practical programming.

In this course, you will learn how to write correct-by-construction programs in the dependently typed programming language Agda. Concretely, we will together implement a verified typechecker and interpreter for a small C-like imperative language. Along the way, we will explore several modern features of the Agda language that make this task more pleasant, such as dependent pattern matching, monads and do-notation, coinduction and copattern matching, instance arguments, sized types, and the Haskell FFI.


For the exercises in this course, you need to install Agda, the Agda standard library v1.1, and the BNFC tool.

If you are brave, there is a bash script that installs all of these on a fresh installation of Ubuntu 18.04 or later. Alternatively, below are step-by-step instructions.

Installing Agda on Ubuntu

First, make sure you have git, cabal, and emacs installed. You also need the zlib c library. On Ubuntu and related systems, the following command should work:

sudo apt-get install git cabal-install emacs zlib1g-dev

Make sure that binaries installed by cabal are available on your path by adding the following line to ~/.profile:

export PATH="$PATH:$HOME/.cabal/bin"

Now install Agda and its prerequisites:

cabal update
cabal install alex happy
cabal get Agda && cd Agda- && cabal install
agda-mode setup

Installing Agda on Mac

Follow the instructions in the user manual. Alternatively, you can install the Haskell Platform and follow the instructions above.

Installing Agda on Windows

Follow the instructions by Péter Diviánszky. Alternatively, install a virtual machine with Ubuntu and follow the instructions above.

Installing the standard library

To install the Agda standard library:

git clone
cd agda-stdlib && git checkout v1.1 && cabal install
mkdir $HOME/.agda
echo $PWD/standard-library.agda-lib >> $HOME/.agda/libraries
echo standard-library >> $HOME/.agda/defaults

Installing BNFC

cabal install BNFC


During the exercise sessions, your first goal should be to install Agda (see above for instructions) and make yourself familiar with the Emacs mode to navigate around in the code. Some useful commands:

See the Agda documentation for further information. The important parts of the code are the following:

Once you are familiar with (a part of) the codebase, you can try to extend the language in a way of your choice. Some suggestions:

Further reading