Story of this paper

This paper summarizes and extends the chapters 3 and 4 of my dissertation. In comparison to the conference version, the provided extended version gives the proofs and additional contents in appendix, with minor corrections on the definitions of lattices (Section 3). I present the syntax and semantics of the programming language "spacetime" which merges several paradigms:

• Concurrent constraint programming (CCP) which was introduced some 30 years ago by Saraswat et al. I think CCP is really beautiful because every syntactically correct programs already have good semantical properties (closure operator). However, it never really had a practical implementation, although languages such as Oz took some ideas from it. Spacetime incorporates the ideas of processes exchanging information through ordered structures (lattices in spacetime) and the "ask and tell" operators of CCP.

• Synchronous programming, more precisely Esterel introduced by Berry and others some 30 years ago too. This paradigm is not very well-known neither although its core idea is very useful for programming: it forces the processes in a program to obey a global clock. In each instant of the clock, the processes can only perform a limited number of actions, so we can check at compile-time that they do not generate race conditions (for example if two processes would write contradictory information on a variable). I believe that time is one of the most important concept when programming concurrent systems, and I think synchronous programming should be more well-known!

• Constraint programming is a declarative paradigm to solve constraint satisfaction problems (CSP). Operationally, constraint solvers explore finite combinatorial state space using a backtracking algorithm.

These paradigms do not seem to have much in common, but spacetime is actually a merge of the two first paradigms, which is applied to CSP solving. You can imagine spacetime as a concurrent Prolog with a time abstraction to synchronize the unfolding of nondeterministic predicates. The main idea is that in each instant of the program, we explore one node of the state space (usually a tree-shaped structure). This way, the processes are forced to cooperate as everybody must finish to explore one node before the next is explored. In the paper, we present the CSP state space, and various search strategies and their compositions (key point: a search strategy is a process, therefore we can compose them like we compose processes!).

Spacetime differs substantially from known paradigms, since it merges paradigms that are not themselves mainstream and well-known. Nevertheless, I think the language can be improved and simplified. I wish to make the spacetime environment easy to use, and to write tutorial explaining how it functions.

My next work on spacetime is to add an additional feature called "universe", which are first-class state space. It is actually very useful to program so called "restart-based search strategy" and nested search. I improved a lot the ideas that were sketched in the dissertation, but I still need to experiment and finish the implementation. Another work I really would like to attempt is to use spacetime as a target to compile various languages such as Esterel, Prolog and CHR.

@inproceedings{PPDP19-Talbot,
 author = {Talbot, Pierre},
 title = {{Spacetime Programming: A Synchronous Language for Composable Search Strategies}},
 booktitle = {{Proceedings of the 21st International Symposium on Principles and Practice of Declarative Programming (PPDP 2019)}},
 year = {2019},
 month = {7--9 October},
 isbn = {978-1-4503-7249-7},
 location = {Porto, Portugal},
 pages = {18:1--18:16},
 articleno = {18},
 numpages = {16},
 url = {http://doi.acm.org/10.1145/3354166.3354183},
 doi = {10.1145/3354166.3354183},
 acmid = {3354183},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {concurrent constraint programming, constraint satisfaction problem, search strategy, synchronous programming},
}