#compiler #traits #prolog

nightly chalk-engine

Core trait engine from Chalk project

12 releases (breaking)

0.9.0 Dec 17, 2018
0.8.1 Oct 31, 2018
0.7.2 Sep 7, 2018
0.6.0 May 24, 2018
0.3.0 Mar 27, 2018

#1 in #traits

Download history 5514/week @ 2019-01-22 5147/week @ 2019-01-29 7969/week @ 2019-02-05 6586/week @ 2019-02-12 6138/week @ 2019-02-19 6958/week @ 2019-02-26 5867/week @ 2019-03-05 6035/week @ 2019-03-12 5142/week @ 2019-03-19 6118/week @ 2019-03-26 6792/week @ 2019-04-02 6767/week @ 2019-04-09 5076/week @ 2019-04-16 5616/week @ 2019-04-23 5830/week @ 2019-04-30

27,098 downloads per month


1.5K SLoC

The core trait solving engine used in Chalk. This engine is meant to be reused by rustc. Other projects may of course re-use it too, if you have a need, but don't expect much stability in the interface yet.


An alternative solver based around the SLG algorithm, which implements the well-formed semantics. This algorithm is very closed based on the description found in the following paper, which I will refer to in the comments as EWFS:

Efficient Top-Down Computation of Queries Under the Well-formed Semantics (Chen, Swift, and Warren; Journal of Logic Programming '95)

However, to understand that paper, I would recommend first starting with the following paper, which I will refer to in the comments as NFTD:

A New Formulation of Tabled resolution With Delay (Swift; EPIA '99)

In addition, I incorporated extensions from the following papers, which I will refer to as SA and RR respectively, that describes how to do introduce approximation when processing subgoals and so forth:

Terminating Evaluation of Logic Programs with Finite Three-Valued Models Riguzzi and Swift; ACM Transactions on Computational Logic 2013 (Introduces "subgoal abstraction", hence the name SA)

Radial Restraint Grosof and Swift; 2013

Another useful paper that gives a kind of high-level overview of concepts at play is the following, which I will refer to as XSB:

XSB: Extending Prolog with Tabled Logic Programming (Swift and Warren; Theory and Practice of Logic Programming '10)

While this code is adapted from the algorithms described in those papers, it is not the same. For one thing, the approaches there had to be extended to our context, and in particular to coping with hereditary harrop predicates and our version of unification (which produces subgoals). I believe those to be largely faithful extensions. However, there are some other places where I intentionally dieverged from the semantics as described in the papers -- e.g. by more aggressively approximating -- which I marked them with a comment DIVERGENCE. Those places may want to be evaluated in the future.

Glossary of other terms:

  • WAM: Warren abstract machine, an efficient way to evaluate Prolog programs. See http://wambook.sourceforge.net/.
  • HH: Hereditary harrop predicates. What Chalk deals in. Popularized by Lambda Prolog.