Companion guide (PPDP19)

  • Reference: P. Talbot, “Spacetime Programming: A Synchronous Language for Composable Search Strategies,” in Proceedings of the 21st ACM International Symposium on Principles and Practice of Declarative Programming (PPDP 2019), Porto, Portugal, 2019.
  • The paper is available here.
  • Tagged version of the language used in the paper on Github.

This supplementary material gives instructions to compile and run the examples and benchmarks presented in the paper.


  • rustup: curl -sSf | sh (do not forget to source your profile or restart your terminal).
  • Maven, it is usually available in the package manager of your distribution:
    1. MacOSX: sudo brew install maven
    2. Linux Ubuntu: sudo apt-get install maven

Installing Bonsai (tag PPDP19)

If you want to replicate any benchmark and running examples, first install the compiler and runtime as follows:

git clone
cd bonsai
git checkout PPDP19

If you have any issue, please consult Getting Started for further instructions.

Demo of the examples in the paper

We provide a demonstration of the programs given in the paper in the directory PPDP19. After installing spacetime, you can simply type:

cd examples/bonsai/PPDP19

Additional examples of strategies

Examples are provided in the standard library of spacetime. In particular, we have the following:

How to run the benchmark

After installing spacetime, you can simply type:

cd benchmark

The file contains some parameters that can be tweaked such as the size of the instances.


The compiler and runtime of spacetime are well tested, you can run the tests of the compiler with:

cargo test
cd runtime
mvn test

There are about 200 tests, ranging from the static analysis of the compiler (compile-fail and compile-pass), to the runtime behavior (run-pass), and the correctness of the lattice library.