Skip to content

dagit/rust-prolog

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

89 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

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.

About

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

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published