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