• 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 https://sh.rustup.rs -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

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

git clone https://github.com/ptal/bonsai.git
cd bonsai
git checkout PPDP19
python3 setup.py

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

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
./run.sh

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

• Depth-bounded discrepancy search (DDS)
• Improved Limited Discrepancy Search (ILDS)
• Highest and lowest discrepancy first variations of LDS can be obtained by changing the queueing strategy from StackLR to StackRL.
• Branch and bound search (BAB)

After installing spacetime, you can simply type:

cd benchmark
./run.sh

The file Benchmark.java 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.