A simple Prolog

A simple Prolog implementation in Rust. It can solve (mini) sudoku! See sudoku.pl for details.

Example interaction:

$ cargo run
    Finished dev [unoptimized + debuginfo] target(s) in 0.03s
     Running `target/debug/prolog`
> edge(x, y).
> edge(y, z).
> edge(y, w).
> 
> path(A, A).
> path(A, B) :- edge(A, X), path(X, B).
> 
> path(x, Place) ?

Solution:
   Place = x
? ;

Solution:
   Place = y
? ;

Solution:
   Place = z
? ;

Solution:
   Place = w
? 

Yes.
> 

Bye!

TODO

More legit Prolog-ness:

• Exceptions
• Actual toplevel
• Operators
• ISO builtins

More datatypes:

• ~~Integers~~ Done!
• Strings
• Maybe floats, and maybe integers with constraints? (Would be difficult)

More builtins:

• ~~Parse arithmetic operators~~ (but somehow keep negated literals as literals)
• ~~is~~
• ~~call~~
• ~~Negation: not, \=, \+~~
• ~~cpu_time, to run benchmarks~~
• load clauses from file
• Cuts: ! (will probably require a new Command variant)
• -> and *-> (soft cut)
• standard library
• IO

More usability:

• Refactor core engine into library
• Load file in REPL
• Reset REPL
• Command-line args to load files, run queries, optional REPL
• Nicer lexer: allow unicode, base-n literals, etc
• ~~Allow multiple goals in a query~~
• ~~Print atoms as x, not x()~~
• ~~Allow _Variables, and~~ generate warnings for singleton variables
  • Question -- should it report the found values of _Variables? SWI Prolog does but GNU Prolog doesn't
• ~~Errors? Would be nice to have debug info on each clause, and be able to give pretty stacktraces on fatal errors~~ Done!
• Maybe don't abuse codespan_reporting for stack traces
• Debugging facilities?
• Investigate alternatives to rustyline

More fancy datastructures:

• Probably not
• ~~Allocate functor arguments in an arena -- switch Box<[VarId]> to &'arena [VarId]~~ Done!
• Rewrite scoped_map to give a different interface: single map, mutable operations to push and pop scope
• For , operator, figure out something better than CPS
• Build it on a disjoint-stack style typed arena, with unsafe reset operations
• Bytecode VM? Almost certainly not