(LPE release version 1.1) July 1992 LAZY PARTIAL EVALUATION ======================= Peter Clark, Rob Holte {pclark,holte}@csi.uottawa.ca SUMMARY ======= This code implements Lazy Partial Evaluation (LPE) in Quintus prolog. The paper describing LPE is published in the proceedings of the 9th International Machine Learning Conference, 1992, pp82-91, and is also available from the authors on request or via anonymous ftp to ftp.csi.uottawa.ca in /pub/lpe. To load LPE, do: % prolog | ?- compile(lpe). % load LPE | ?- compile(demo). % load some domain theory | ?- demo. % Run the demo in the `tiger' domain To use LPE, you only need to know two predicates!: lpe_setup(Functor/Arity) % set up for LPE for Goal with F/A lpe_call(+Goal) % evaluate Goal, doing LPE at same time lpe_call/1 behaves similarly to Prolog's call/1, except that it also has the side-effect of lazily partially evaluating the domain theory just as much as is needed to prove Goal. In EBG terminology, `Goal' is the target concept. The domain theory consists of a set of clauses, including clauses for Goal. LPE identifies non-operational predicates as those whose clauses are dynamic. These non-operational clauses must not contain cuts. Three other predicates are also very useful to know: lpe_listing(Functor/Arity) % list current defn of concept with F/A set_tracing_mode(+Mode) % Mode = {on, off} set_learning_mode(+Mode) % Mode = {lpe, pe, ebg, none} More details are given below, and in the file lpe.doc. DEMO OF LPE =========== For a demo of LPE in use on the toy `tiger' domain in the ML92 paper, do % prolog | ?- compile(demo). | ?- demo. This fully illustrates the use of the five predicates defined above. A `*' is printed by LPE every time a non-operational definition is expanded into a new (possibly still non-operational) definition. PROLOG VERSIONS =============== The code was developed under Quintus v2.5.1 on a SunSparc/UNIX, and has also been tested under Quintus v3.1.1. It almost certainly works under other Quintus versions too. It should also port to other Prolog implementations reasonably straightforwardly: email us for assistance if any problems arise. DOCUMENTATION ============= The documentation here assumes familiarity with the Prolog programming language. The documentation uses a two-file style, with the Prolog (.pl) file briefly annotated with comments, and a longer text (.doc) file elaborating on the finer details of the code. USEFUL FACTS ============ The code also contains flags to allow the algorithm to behave in full Partial Evaluation (PE) mode or Explanation-Based Generalisation (EBG) mode, for comparison. For efficiency reasons, LPE copies clauses defining the target concept from Prolog's assert database into another database called the "kassert" database, defined specifically for LPE and implemented in kassert.pl. See "the kassert database" in lpe.doc for more information. MORE DETAILED INFORMATION ========================= The three main predicates which operate LPE behave as follows: | ?- lpe_setup(tiger/1). Call this predicate just for the target concept you wish to apply LPE to. It copies clauses defining tiger/1 from the assert db into the kassert db. This predicate must be called to set up for using LPE for this target concept. It will also reset any previous operationalisation done by LPE for tiger/1. | ?- lpe_listing(tiger/1). Analogous to Prolog's listing/1, list clauses for tiger/1 in the kassert db. | ?- lpe_call(tiger(X)). Behaves as Prolog's call/1, except in addition the target concept definition is lazily partially evaluated as required to prove the goal. Call lpe_listing/1 again to see what the LPE'd theory looks like at any point in time. In addition: | ?- set_tracing_mode(on). switches on tracing so you can watch LPE in action. THE DOMAIN THEORY ================= A domain theory is represented as a set of Prolog clauses. The user must declare which *predicates* are non-operational -- in this implementation, this is done by declaring them to be dynamic, so that the LPE meta-interpreter can access them. Clauses defining non-operational predicates must be written in `pure' Prolog, containing no cuts. See demo.pl for an example. We say a *clause* (ie. part of a concept *definition*) is non-operational if it has at least one non-operational literal in its body, otherwise it is operational. Thus a non-operational predicate may have an operational definition. The goal of LPE, EBG and PE is (loosely) to usefully operationalise the definitions of a target non-operational predicate (the target concept). THE LPE INTERPRETER =================== The implementation of LPE comprises: (i) the LPE interpreter (Fig 2 ML92 paper). (ii) the concept definition ordering algorithm (Fig 3 ML92 paper), which uses the interpreter to generate concept defns from proofs of examples. The LPE intepreter collects the (generalised leaves of a) successful or failed proof of training example. These leaves constitute the body of a revised concept definition. To see just the interpreter alone, use lpe(+Goal,+GenGoal,-ConceptDefn), eg. | ?- lpe(tiger(joe), tiger(X), ConceptDefn). and step through the different solutions for ConceptDefn. As described below, set_learning_mode(+Mode) allows you to switch the LPE interpreter into PE or EBG mode. Try changing the learning mode and repeating the above call to lpe/3. (To tidy ConceptDefn into a tidier form, you can add the goals: ...,tidy_and_split(ConceptDefn,Op,Nonop), join(Op,Nonop,TidyDefn). ) THE DEFINITION ORDERING/EXECUTION ALGORITHM =========================================== The concept definition ordering algorithm ((ii) above) orders and executes concept definitions (ie. clauses, produced by the LPE interpreter) according to their user-defined `quality', so the clause which produces the `best' solution is tried first. The quality of an operational clause can be thought of as the usefulness of the solution it computes (eg. returned by instantiating variables in Goal). The quality of non-operational clauses must be defined as an upper bound on the quality of any operational clauses it may produce through LPE. From an implementation point of view, LPE uses the `quality' metric to decide where to insert the new clauses it creates, and the real constraint is that new clauses must always be inserted *below* the clause which was LPE'd to created them. Thus the quality of a clause must monotonically decrease (or stay equal) as it is LPE'd (or else LPE won't work). By default, a definition's quality is taken its length (the shorter the better), counting the operational literals in its body. This approximates an upper bound on the execution speed of a clause (and of any new LPE'd clauses which it may produce). This notion of quality can be changed by the user if desired (change quality/2 in lpe.pl). For the constraint-satisfaction application in the ML92 paper, quality was re-defined so that `better' meant `returns a solution (= an explanation of why the hypothesis violated a constraint) which blames earlier variable assignments' (allowing greater pruning of the search space). See the csp_demos subdirectory for more information on this. If you don't care about the ordering of clauses defining the target concept, you can just define them all to be of equal quality, eg. quality(_, 0). % (Everything has quality Q = 0) This still satisfies the ordering constraint described above. (Aside: In this case, the use of the kassert db is not strictly necessary: the code could be simplified to use the assert db and assertz/1 (for LPE/PE) or asserta/1 (for EBG)). MODES ===== As illustrated in the `tiger' demo, this code will emulate 4 learning styles: lpe : lazy partial evaluation pe : partial evaluation ebg : explanation-based learning none: no learning To set the learning mode: | ?- set_learning_mode(lpe). The default is lpe. The additional learning styles are included for comparison, and are implemented by simply altering the behaviour of the LPE interpreter at occasional points using an asserted flag (learning_mode/1). This switchability is interesting at the implementation level too, and illustrates the close similarity between LPE, PE and EBG. **NOTE** that this implementation of PE and EBG is not designed for speed, as it still uses the less efficient kassert (rather than assert) db to store the concept definitions. Thus speed comparisons between these modes would be unfair. Note too the published speed comparisons in the paper on LPE were not made using these implementations of PE and EBG, but using more efficient, separate implementations. VARIABLES AND SEMANTICS ======================= Variables can be included in the Goal for lpe_call(Goal). LPE, EBG and PE all preserve the declarative semantics of the original domain theory, so that same set of solutions will be found through backtracking -- although the order and the number of times the same solution is found may differ (size bag of solns LPE/PE =< size bag of solns for original DT =< size bag of solns for EBG. See notes not_equivalent/2 in lpe.doc for more information). MORE SOPHISTICATED DEMOS ======================== LPE was applied to two constraint satisfaction tasks, `cities' and `zebras' (described in the ML92 paper). The domain theories and demos of the constraint-testing part of the CSP can be run by doing: % cd csp_demos % prolog | ?- compile(cspdemo). | ?- compile(cities). % or compile(zebras) | ?- demo. Option? 1. % setup Option? 3. % generate a hypothesis soln % to the CSP and see if it % satisfies the constraints. See csp_demos/README for more detailed information about his demonstration, and also for a demonstration of the full CSP being solved. FILES ===== The files contained in this suite are: README This file lpe.pl Implementation of LPE kassert.pl Implementation of the kassert db, used by LPE utils.pl Other utilities for LPE demo.pl Domain theory and demo in the toy `tigers' domain {lpe,kassert}.doc Documentation And in the csp_demos subdirectory: README Information about LPE with the CSP tasks cspdemo.pl Demo of LPE checking constraints gbj.pl The full constraint-satisfaction algorithm (CSA) {cities,zebras}.pl Two CSP domain theories gbj.doc Brief documentation for the CSA REFERENCES ========== For further information or answers to queries email Peter Clark or Rob Holte ({pclark,holte}@csi.uottawa.ca). Comments are of course always welcome too. The full reference to the ML92 paper is: @inproceedings{lpe, TITLE = "Lazy Partial Evaluation: An Integration of Explanation-Based Generalisation and Partial Evaluation", AUTHOR = "Peter Clark and Rob Holte", BOOKTITLE = "Proc. Ninth Int. Machine Learning Conference (ML-92)", YEAR = 1992, EDITOR = "Derek Sleeman and Peter Edwards", PAGES = "82--91", PUBLISHER = "Kaufmann", ADDRESS = "{CA}" }