Programming in Schelog

 Dorai Sitaram 
 Download Version 2018-06-09 
 Installation instructions 

Schelog is an embedding of Prolog-style logic programming in Scheme. “Embedding” means you don’t lose Scheme: You can use Prolog-style and conventional Scheme code fragments alongside each other. Schelog contains the full repertoire of Prolog features, including meta-logical and second-order (“set”) predicates, leaving out only those features that could more easily and more efficiently be done with Scheme subexpressions.

The Schelog implementation uses the approach to logic programming described in Felleisen [4] and Haynes [8]. In contrast to earlier Lisp simulations of Prolog [3], which used explicit continuation arguments to store failure (backtrack) information, the Felleisen and Haynes model uses the implicit reified continuations of Scheme as provided by the operator call‑with‑current‑continuation (aka call/cc). This allows Schelog to be an embedding, ie, logic programming is not built as a new language on top of Scheme, but is used alongside Scheme’s other features. Both styles of programming may be mixed to any extent that a project needs.

The Schelog user does not need to know about the implementation mechanism or about call/cc and continuations to get on with the business of doing logic programming with Schelog.

This text is a gentle introduction to Schelog syntax and programming. It assumes a working knowledge of Scheme and an awareness of, if not actual programming experience with, Prolog. If you need assistance in either language, you may consult [1567911] for Scheme, and [21012] for Prolog. There are doubtless many other excellent books and online documents available.

Contents

    1  Simple Goals and Queries

    2  Predicates
        2.1  Predicates Introducing Facts
        2.2  Predicates with Rules
        2.3  Solving Goals
            2.3.1  A Note on #f vs ()
        2.4   Asserting Extra Clauses
        2.5  Local Variables

    3  Using Conventional Scheme Expressions in Schelog
        3.1  Constructors
        3.2  %is
        3.3  Lexical Scoping
        3.4  Type Predicates

    4  Backtracking

    5  Unification
        5.1  The Occurs Check

    6  Conjuctions and Disjunctions

    7  Manipulating Logic Variables
        7.1  Checking for Variables
        7.2  Preserving Variables

    8  The Cut (!)
        8.1  Conditional Goals
        8.2  Negation as Failure

    9  Set Predicates

    10  Glossary of Schelog Primitives

    11  References

Last modified: Wed, June 8, 2088, 10:48 pm UTC−4