Sunday, September 24, 2006

Inference Collection - Fact Modification Semantics

I need to specify the semantics for the various ways to change a fact in the inference engine. There are three ways to reassert a fact. The first is to explicitly retract the existing assertion and then to assert its replacement. The second is to replace an assertion using the replace function. The third is to modify (the fact within) an assertion using the modify function. Each of these has a different set of semantics - largely associated with the level of reuse.
Retract and Assert
By explicitly retracting an assertion, all reference to it should be removed. This is true in terms of the rule network, but currently references to the assertion may still exist in rule instances retained as the reasons for other assertions. I need to think of a better mechanism to retain the relevant information from the rule instance or give up on consistency when reusing assertions or facts.
One approach would be to sanitize the rule instance before using it as a reason. This would involve removing the assertion list (easy) and any assertion variables from the bindings. [These would not be reliable as reasons following any replace or modify of tge assertion.]
An alternative is to try to determine which assertion references are still valid following a replace or modity. We could remove any such references (in reason fields) or we could maintain a generation field and have an explicit assertion reference type with generation checking.
For now, I will document the inconsistence problem and live with it. It only affect debugging at the moment anyway.] I will revisit this when I implement truth maintenance in the future.
In any case, a separate retract and assert does not provide any reuse of assertions and the above problems will not occur.
Replace
Currently, replace literally implements an assert preceded by a retract as above. I will change this to reuse the assertion object for the next release. This will have the inconsistenct problem noted above.
Modify
The new modify functionality will reuse the underlying fact object within the assertion object being modified. Only the fields that are specified will be changed.

Labels:

Thursday, September 21, 2006

PLT Scheme Inference Collection

The PLT Scheme Inference Collection has been released. Version 1.3 is the current released version.
All of the basic functionality has been implemented. There are several examples coded: ancestors, Towers of Hanoi, and Sudoku. The Sudoku example is the most complex requiring a search (using hierarchical inference environments).
I am not satisfied with the current implementation of 'modify'. I am going to rename the current functionality to be 'replace'. The semantics match that new term better.
I need to implement a real modify functionality that does modify the underlying fact object. This will be useful with fact objects with names fields: association lists, structures, and class instances. The primary additional work is how to map field names to their location in the fact object. Association lists aren't a problem since the field names are stored in the association list. I haven't found any way to get the names of structure fields - and I'm not sure there is any way to do so. Class instances are still a future implementation feature - but it does seem to be possible to get the field names for classes.
The initial implementation for modify will just support association lists. This will not require any additional syntax beyond modify itself.
Next, I will implement the modify functionality for structures. This will likely involve a new syntax - define-template - to supply the field names. It will have essentially the same syntax as define-struct. I will also implement define-struct/template that does the structure definition and template definition in one call.
This will also make it easier to implement the rule-based system benchmarks. I would like to code and bechmark the performance of the system before I begin adding more efficient algorithms (i.e. hashing for node matches).

Labels: