Trivial Prolog in Java

001: package ca.draisey.free.tprolog;
002:
003:
004:
005:
006:
007: // Prolog in Java Project
008: // This is a trivial implemetation of a extremely lightweight prolog interpreter written for
009: // purely expository purposes.  It is not intended to be used in a real environment.  It is written
010: // in Java rather than pseudocode so that it may be compiled to check its "superficial" correctness.
011: // I hope that it genuinely is a correct implentation -- that it follows from its overall simplicity.
012:
013:
014:
015:
016:
017: // This is yet a new implementation: the old intantiated individual rules by
018: // copying -- through a deep clone -- the entire rule and zeroing out the
019: // variable bindings.  This is quite expensive both computationally in in
020: // memory consumption.  However, it is not truly necessary to copy the entire
021: // tree of nodes if we introduce a slight degree of indirection and require all
022: // references in the unification algorithm to be not direct references, but
023: // consisting of a reference to the prototypical rule and another to a table
024: // of bindings unique to the instance.  The rule supports this behaviour by
025: // having variable terms which contain an index into the instance table.
026: //
027: // So, we simplify rule instantiation at the cost of increasing the stack
028: // footprint of each recursive step in the unification algorithm and a slight
029: // increase in code complexity at the lowest level.  I think this complication
030: // is worthwhile as it makes the Java implementation slightly more practical.
031: // As a bonus, the unification algorithm is now fully reentrant!
032:
033:
034:
035:
036:
037: // This implementation has unusual control flow.  Successful inference through unification of terms
038: // is not followed by a return from the called subroutine/method, but rather causes the passed
039: // "Successor" routine to be called.  So the successful flow of a prolog programme is to consume
040: // stack space and never release it!  This is kind of like completions in Scheme with the
041: // nondeterminism of prolog added -- i.e. unlike ordinary completions which wrap-up their called
042: // environment and release stack space, successors "interrupt" normal control flow, leaving the
043: // possibility of returning to this environment -- exactly what is necessary for prolog backtracking.
044: //
045: //      success in prolog       ==      unbounded recursion in the java implementation
046: //      failure in prolog       ==      normal control flow in the java implementation
047: //
048: // Needless to say, this is a very expensive way of implementing the nondeterminism required in Prolog.
049: //      -- Because this is written in Java the most important consequence of this implementation
050: //      -- is completely hidden - namely that the only memory we need can be completely contained on
051: //      -- the stack.  In C we need never call "malloc"; instead we would call "alloca" to instantiate
052: //      -- a rule, preferably as a linear block rather than recursing down a tree as I did here.
053:
054:
055:
056:
057:
058: // -- the glue for different implementations of the basic database --
059: //      -- in the first implementation Database used only static methods and fields
060: //      -- now I use instance methods and fields and pass the
061: //              database context through the Successor object
062: //      -- this lets me plug in different user interfaces without recompiling
063: abstract class SuccessionDatabase {
064:         void queryDatabase( final Term goal, final Variables goals, final Successor success )
065:         {
066:                 final java.util.Iterator< Sentence > i = matching( goal.getkey() );
067:                 while( i.hasNext() ) {
068:                         Sentence quantifiedRule = i.next();
069:                         quantifiedRule.dequantifyClause().queryClause( goal, quantifiedRule.instantiateVariables(), goals, success );
070:                 }
071:         }
072:
073:         // this inner class is a convenience used by HornClause and PairTerm
074:         abstract class DatabaseSuccession extends Succession {
075:                 void queryDatabase( final Term goal, final Variables goals, final Successor success )
076:                 {
077:                         SuccessionDatabase.this.queryDatabase( goal, goals, success );
078:                 }
079:         }
080:
081:         /*abstract class NextSuccession extends DatabaseSuccession {
082:                 // blocking wait-for-next
083:                 abstract void next();
084:                 // tell those waiting that the Prolog core has returned its final solution
085:                 //      -- my implementation never knows this so commented out --
086:                 // abstract void last();
087:         }*/
088:
089:         // protected private
090:         abstract java.util.Iterator< Sentence > matching( String key );
091:
092:     // a null value
093:     protected java.util.Iterator< Sentence > NOTMATCHING = new java.util.Iterator< Sentence >() {
094:                 public boolean hasNext() { return false; }
095:                 public Sentence next() { throw new java.util.NoSuchElementException(); }
096:                 public void remove() { throw new UnsupportedOperationException(); }
097:         };
098: }
099:
100: // fin