Mini Kanren: updates

Several updates to Mini Kanren, covering syntax, semantics and documentation.

Syntax
Implicit conversions now allow you to write the more idiomatic x === y to mean mkEqual(x,y) . Likewise, you can use x =/= y to mean neverEqual(x,y) (see below for explanation).


Semantics
The =/= (neverEqual) goal has been added, specifying that x and y should never be unified with each other. This requires reworking the substitution system; previously, a substitution is simply a list of var -> x mappings, together with assorted functions.

Supporting neverEqual involves adding more checks to unify; in addition, functions like lookup need different implementations depending on whether they operate on simple or extended substitutions.

The implementation is now more object-oriented, using a pattern similar to Haskell typeclasses:

  • Subst specifies the operations available to any substitution, together with default implementations for a simple substitution, whenever possible
  • ConstraintSubst extends Subst. It does not actually add any more methods, but it overrides the implementation of some methods (such as unify)

There is a reason both of these provide the same public interface: it allows the same code to run, with either a simple or a constrained substitution, with no change at all (neverEqual-related operations just become no-ops if a simple substitution is used).

Performance

Surprisingly, the change to the substitution system actually results in a performance boost. Previously, the palprod_o benchmark takes around 110 seconds to run on a Core 2 Duo (single thread), compared with around 40 seconds for Petite Chez Scheme. The new code, using linked case classes instead of linked lists, come in at around 44 seconds. (fastest time with constraints disabled is around 43.5 seconds; with it enabled (but no constraints) the overhead is around a couple of seconds).

More systematic benchmark numbers will be forthcoming.

Misc
The standard prelude and examples are now better documented. The examples now have their own namespace (info.hircus.kanren.examples), and a second example, SendMoreMoney, has been implemented.

Technorati Tags: , , , , , ,

Comments are closed.