From 6bced91bd28f860d830dfda921ee5056ec93f48c Mon Sep 17 00:00:00 2001 From: Jedidiah Barber Date: Fri, 6 Feb 2026 17:19:26 +1300 Subject: Evaluation algorithm changed to inverted interleaved depth first search --- readme.md | 25 ++++++++++++------------- 1 file changed, 12 insertions(+), 13 deletions(-) (limited to 'readme.md') diff --git a/readme.md b/readme.md index 28b1246..8b5fd08 100644 --- a/readme.md +++ b/readme.md @@ -78,12 +78,6 @@ placing them all in the main package would not have made sense due to the math operations needing to know what zero and one are. It would also have made the main package unreasonably large. -Internally a Goal is structured as a directed acyclic graph. Evaluation of -a Goal involves walking the graph while applying relevant operations to the -base State and expanding any Conjuncts to more of the graph as they are -encountered. The expanded portions, bookkeeping data, and memoised partial -results are all discarded once evaluation is complete. - The various cond operations are completely absent, as this implementation instead follows microKanren for its core workings. The cond variations do not really make sense in an object oriented context anyway. Use a Disjunct @@ -95,13 +89,18 @@ implemented. The practical implication of this is there will be a lot of use of the `&` operator when using this library, as can be seen in the example programs. -The State datatype makes use of custom unrolled linked lists, and the -bookkeeping data in the Collector package uses a custom directed acyclic graph -structure that reflects the main Goal graph. This is done instead of using -Vectors or Maps from the standard library both to improve speed and reduce -memory requirements. The improvement due to tail sharing is considerable, -despite the theoretically expensive operations involved in walking the list to -reify a variable. +Internally a Goal is structured as a directed acyclic graph. Evaluation of a +Goal involves inverting the arrows in the graph, interleaving those arrows +according to Disjunct choices made from the top to get there, and then running +a depth-first search from the bottom upwards using the inverted graph. When +a Conjunct node is encountered it is expanded, inverted, and interleaved in a +similar way before the search continues. The inversions and expanded portions +are all discarded once evaluation is complete. + +The State datatype makes use of a Vector of Variable->Term bindings and a +Hashed_Map to get from Variable to the index for the Vector. Both are needed so +that lookups can be fast and truncations of the State to remove the newest +bindings are easy to do when backtracking during the depth-first search. -- cgit