Bachelor Project: Definitional Interpreters for Logic Programming Languages

Supervisors

Casper Bach Poulsen, Hendrik van Antwerpen, and Eelco Visser.

Project Description

Logic programming languages with constraint solving strike a balance between simplicity and practicality. In particular, logic languages support concise and declarative yet efficiently-executable implementation of programming problems that otherwise require careful and manual implementation of elaborate programming heuristics. This makes such languages attractive for modern software development, such as implementing type checkers for programming languages [1], refactoring programs in meaning-preserving ways [2], or implementing cognitive agents [3].

A classical but illustrative example of the power of logic languages and constraint solving is the n-queens problem: given a chess board of size n × n, place n queens on the board such that no two queens are able to attack each other. Constraint programming lets us state the constraints (no two queens are allowed to attack each other) and automatically and efficiently compute a correct solution. For example, the following logic constraint program implemented in MiniZinc [4] (adapted from the MiniZinc benchmark suite [5]) implements a predicate that must hold for each queen, and uses this predicate to phrase a constraint that must hold for any valid solution:

int: n;                         % The number of queens.
array [1..n] of var 1..n: q;    % Chess board

predicate
  noAttack(int: i, int: j, var int: qi, var int: qj) =
    qi != qj  /\  qi + i != qj + j  /\  qi - i != qj - j;

constraint
  forall (i in 1..n, j in i+1..n) (noAttack(i, j, q[i], q[j]));

Comparing with alternative solutions that can be found online (e.g., on Rosetta Code [6]), this program is more concise than, yet outperforms the vast majority of, available solutions in general-purpose languages.

The n-queens problem is a somewhat theoretical example problem, but there is a wide range of domains where logic languages with constraint solving can and are beginning to revolutionize software development. In this project you will investigate both the basics of constraint solving languages, but also their application to practical software engineering problems. The end goal of this investigation will be to write your own definitional interpreter for a logic programming language targeting a particular problem domain.

  • Concepts of Programming Languages
  • Reasoning and Logic

Individual Research Questions

  1. What are the trade-offs for designing logic programming languages with constraint solving?
  2. How are logic programming languages typically defined and implemented?
  3. What domains have logic programming and constraint solving been applied to?
  4. What are interesting domains that logic constraint programming could be applied to?
  5. How could logic constraint programming be used to automatically generate unit tests for a given program?

References

  1. Hendrik van Antwerpen, Casper Bach Poulsen, Arjen Rouvoet, Eelco Visser: Scopes as types. PACMPL 2(OOPSLA): 114:1-114:30 (2018). DOI
  2. Friedrich Steimann: Constraint-Based Refactoring. ACM Trans. Program. Lang. Syst. 40(1): 2:1-2:40 (2018). DOI
  3. Koen V. Hindriks, Jürgen Dix: GOAL: A Multi-agent Programming Language Applied to an Exploration Game. Agent-Oriented Software Engineering 2014: 235-258. DOI
  4. Nicholas Nethercote, Peter J. Stuckey, Ralph Becket, Sebastian Brand, Gregory J. Duck, Guido Tack: MiniZinc: Towards a Standard CP Modelling Language. CP 2007: 529-543. DOI
  5. https://github.com/MiniZinc/minizinc-benchmarks/blob/master/queens/queens.mzn
  6. http://rosettacode.org/wiki/N-queens_problem