« New build #292 is out | Main | Collections in Base Language »
July 17, 2006
Knowledge Representation in MPS
I've already written about knowledge representation in MPS with aid of OWL, namely MPS based OWL editor. This representation isn't rich enough to present non trivial knowledge however it's rich enough for simple uses like internet shops. So we decided to use a representation that manages this task better than OWL. We decided to create a Horn-clauses based language, like Prolog but a little bit better :).
So what Prolog is. In this language everything is represented by means of rules of sort
A <= B & C & D, where A,B,C,D are some predicated. These rules are called Horn clauses and inference for these rules can be implemented with relative ease. Of course this isn't full predicate logic. In predicate logic all clauses are of sort A | B | C <= D & E & G, however Horn clauses can be used to describe very interesting things, for example it's possible to present arbitrary algorithm with their aid.
What's bad about OWL. OWL is based on the description logic. Description logic is a simplified predicate logic. For this kind of logic you can infer facts in a reasonable time. Because of this limitation there are a lot of interstring facts that can't be described with it. Key concept of description logic is class. In fact description logic class is the same as unary predicate in the full predicate logic. In description logic you can do a lot of manipulations with classes namely do boolean operations, and some others. In description logic you can also declare properties that are the same as binary predicates. But their usages are much more restricted than usages of unary predicates. For example it's impossible to represent such a fact in description logic:
A(x,y) <= B(y,z) C(z,x)But you can describe this fact that's impossible to describe in Horn clauses
A(x)|B(x)|C(x) <=|
I said enough about theory and its time to say about its implementation in MPS. People asked me many times about the time when we will have a language that is entirely implementeed in MPS and now we have it. Our implementation consists of three layers:
- We have Prolog interpreter in Java. It's not exactly Prolog as it's described in books and standards. We have some differences. We have a circularity prevention system and some smart optimizations of inference. Also we implemented unification with occurence check
- We have MPS base language that is generated into Java code that setups Prolog and makes it possible to execute program.
- We have domain specific extensions for base language that are generated to it.
Lets look at some piece of knowledge represented with our language:
We chose general chemistry as a test field for our technologies. In this document we described common anions. At the top of the picture you can see a class. Class is just a convenient form of describing predicate. Also you can see descriptions of sort object o : A [x->y] its also more convenient form of object description. It's inspired by F-Logic created by Ontoprise.
Because when you describe a language it's convenient to have lists maps and have some common predicates we created a standard library. On this picture you can see predicate included in the library that removes an element from a list that:
For lists we have special syntax (standard prolog also has it): [Head|Tail], in the core it's presented as cons(1,cons(2,cons(3,nil))), like in LISP. But generational capabilities of MPS makes it possible to introduce such a syntatic sugar with ease.
Everything that we take a look to is relatively concise and easy to understand but in some fields you can have things that are very hard to grasp without using domain specific notation. For example if you want to present in naked jetbrains.knowledge, without any extensions the simplest amino acid glycine you have to write this:
Looks terrible isn't it? :) It would be much more pleasant to have a convenient formula editor where you can place atoms and create bonds between them without entering these horrible predicates. And we have it. Methane the simplest carbohydrate looks so:
It's impossible to enter glycine now but we are working on a such capability now.
Because we have to write a lot of code in this language we created tools that makes it relatively easy:
Assertions and rules with grey spheres weren't inferred and ones with red were. In this view we have a navigation to used rules and assertions. These things caused us to create plugins framework because main MPS module would have become too large is we hadn't do it.
I'm not a proponent of unit test XP and other buzzwords but if you have a very complex business logic in your code it might be broken with a harmless change. So we created a unit testing framework. It has very simple user interface in a style of JUnit console runner so I didn't create a screenshot of it.
By the way all these things and also my OWL editor is going to be included in the next MPS build so everyone could play with it if they want to :)
Posted by Konstantin Solomatov at July 17, 2006 01:09 PM