Awesome

Overview

Rust implementation of prolog (originally) based on miniprolog: http://andrej.com/plzoo/html/miniprolog.html

I translated miniprolog from the above SML sources to Rust for two primary reasons:

• Firstly, I wanted a project to explore programming in Rust
• Secondly, prolog is interesting but I never felt like I properly learned it

Starting from an existing implementation was nice because it shortened the time to a working version. The current version in this repository is very much a work in progress and overly simplistic. I plan to improve it to better learn Rust and I plan to improve it as I learn Rust :)

In other words, this is really a playground for me to play with both Rust and prolog.

Installation

Tested on Linux (Fedora), OSX, and Windows.

Should be as simple as: cargo run

Example

$ cargo run
Welcome to rust-prolog!
This prolog interpreter is based on the ML code at the PLZoo:
  http://andrej.com/plzoo/html/miniprolog.html

Input syntax: 
    ?- query.            Make a query.
    a(t1, ..., tn).      Assert an atomic proposition.
    A :- B1, ..., Bn.    Assert an inference rule.
    $quit                Exit interpreter.
    $use "filename"      Execute commands from a file.
Prolog> $use "src/likes.pl"
Prolog> ?- likes(X,Y).
Y = mary
X = john 

more? (y/n) [y] 

Roadmap

I haven't figured out exactly which directions I want to take this in, but some ideas I've been kicking around include:

• Add a type system
• Add constraints and constraint checker.
• Add a bottom-up search procedure (perhaps even replace the existing top-down search procedure entirely).
• Add program transformations to generate more efficient queries (for instance, magic sets and entailment elimination).
• Change the syntax to one that supports mixfix declarations.

Completed:

• Change the search procedure to a complete search. This is now done. It uses iterative deepening with an admissable heuristic that does a lower bound estimate on the number of unifications required to solve the current goal. It also generates contrapositives (instead of using restarts).
• Add more primitive types, lists, numbers, etc and make a small standard library.
• Improve the garbage collection. Currently cycles are allowed but due to the hash consing, nothing is ever collected. A simple scheme that should allow some collection is to throw away terms generated by unification and terms that are part of a query after the query has terminated. This should lend itself to a simplistic form of regions.

Old goals that I may not pursue after all:

• Compile to the Warren Abstract Machine. The reason I've reconsidered this one is because my search procedure is slowing moving towards a more general constraint logic search procedure. The WAM is still rather elegant and I may follow the development at some point and see if I can adapt it to fit the general CPL algorithm. Perhaps someone else has already done this work.