2008-04-02

LISA, Multislots and thoughts about Pattern matching

LISA has no multislots. That's just the way it is. You can add a list to a slot, but you have to match it as-is unless you provide a custom test-function.

About a week ago, Pedro Kröger announced on the Lisa Users mailing list that he was converting the Zebra puzzle from CLIPS to LISA. The rule syntax is so similar between the engines that it ought to have been a quite straightforward and simple exercise. But, since the CLIPS solution uses implied deftemplates (which are implemented as multislots) the LISA program wouldn't work.

This, and many other situations like it, has made me wonder about why nested fact structures aren't supported. Matching, on any level in a nested list, is actually described in Forgy's thesis (from 1979) but hasn't, for some reason, been implemented in most rule engines. Probably because it's faster to only allow flat structures.

The Rete implementation described in the thesis constructs an awful lot of nodes but I'm not sure you need all of them. A rule compiler ought to be able to figure out which part of a structure to test without doing too many feature-tests ("is the second subelement a list of 3 subelements" etc).

12 kommentarer:

woolfel sa...

one of the challenges is the rule syntax. If the nested object is a multislot, it gets tricky. CLIPS syntax to my knowledge does not provide an easy to way to declare which element in the multislot the condition should compare to. then there's the issue of consistency.

if the engine is just an expert system and the facts aren't external objects, it's probably safe. there's still the language issue of how to express the rule.

Johan Lindberg sa...

Hi Peter,

I think CLIPS multislots is a different beast. Since there's no nesting multislots in CLIPS it won't work for this anyway. Also, since $? creates all possible combinations of a pattern match I think the purpose of it's design is something else completely.

there's still the language issue of how to express the rule.

Yes, that's true but if we assume a Lisp-style syntax it should be straight forward to allow:

|(defrule foo
| (fact (slot (?a (?b (?c ?) ?) ?)))
| =>)

for Python I'm thinking something like:

|def foo(fact = Fact):
| if fact(slot == [a [b [c _] _] _]):
| pass

but this assumes matching exactly 1 item for each ?. If we were to allow, for example, ?* and ?+ to express match 0 or more and match 1 or more it gets a lot more complicated and we'd also end up with the combinatorial explosion of multislots unless we'd only allow those for placeholder variables.

woolfel sa...

yeah, as far as I know, or as I am told by art people. it is the explosion that is the main concern. JESS multislots work differently, so they could nest multislot, if the java object is modeled that way :)

Johan Lindberg sa...

and how do you handle Multislots in Jamocha?

woolfel sa...

jamocha handles it the same way as JESS. I only make shallow copies of the java objects to deffacts. if the user doesn't assert the nested object, the engine might not be able access the nested value.

for example, if the user declares the object with defclass, but doesn't declare the nested object, Jamocha wouldn't know how to access the nested slots.

in theory, the engine could traverse the object graph and automatically declare every unique class, but that runs into a potential problem with deftemplate name collision.

Johan Lindberg sa...

Ok. I see. It's of course difficult to handle something that hasn't been declared. But I was more thinking about, for example, arrays of primitive values.

Say I have a 3D Java ArrayList which could be referenced using: value = arrayList[x][y][z]. Is it possible to match an individual value using multifields?

If you're only making shallow copies I guess you won't even have access to all of the ArrayList.

Johan Lindberg sa...

Is it possible to match an individual value using multifields?

What I meant to ask was: Is it possible to match an individual value in such a multislot?

woolfel sa...

One way to do that is with TESTCE, which looks like this in a rule.

(test (member$ ?var $?multivar) )

What I've done in the past is write a custom function and use it in a testce.

Johan Lindberg sa...

Yes, but (test (member$ ?var $?multivar)) tests if a value *exists* in the MultiField.

What I meant was if you could assign a value to a variable (value) given three other variables (x, y and z) to indicate a position within a nested multislot?

woolfel sa...

From Jess docs, it supports this.

Jess> (defrule match-list-with-bacon
(grocery-list $? bacon $?)
=>
(printout t "Yes, bacon is on the list" crlf))
TRUE

Jess> (assert (grocery-list eggs milk bacon))
<Fact-0>

Jess> (run)
Yes, bacon is on the list
1


does that answer your question?

Johan Lindberg sa...

does that answer your question?

Well, no.

I'm afraid we're talking past each other. I guess it's true what they say about communicating via blog posts, comments and forums ;-)

It's quite possible (and probable) that I'm chasing after something I've misread in one of your comments.

I'm sorry to have wasted your time on this. It's very kind of you to keep answering and keep coming up with examples but I'll check out the latest Jamocha from SVN and experiment instead. That way, we can continue the discussion around working code instead of figments of my imagination ;-)

woolfel sa...

no problem. I think I see where I mis-interpreted it. You want to know the position of a given variable binding in a multislot right?

I think by default, JESS doesn't support that. You could always write a user function and use it from a TEST CE to determine the position of value in a multislot.