CODEWITHSUNDEEP
javaunification
Choas
Choas

Reputation:

implementing unification algorithm

I worked the last 5 days to understand how unification algorithm works in Prolog . Now ,I want to implement such algorithm in Java ..

I thought maybe best way is to manipulate the string and decompose its parts using some datastructure such as Stacks ..

to make it clear :

suppose user inputs is: a(X,c(d,X)) = a(2,c(d,Y)).

I already take it as one string and split it into two strings (Expression1 and 2 ). now, how can I know if the next char(s) is Variable or constants or etc.. , I can do it by nested if but it seems to me not good solution .. I tried to use inheritance but the problem still ( how can I know the type of chars being read ?)

Upvotes: 0

Views: 2588

Answers (3)

Stephen C
Stephen C

Reputation: 718946

First you need to parse the inputs and build expression trees. Then apply Milner's unification algorithm (or some other unification algorithm) to figure out the mapping of variables to constants and expressions.

A really good description of Milner's algorithm may be found in the Dragon Book: "Compilers: Principles, Techniques and Tools" by Aho, Sethi and Ullman. (Milners algorithm can also cope with unification of cyclic graphs, and the Dragon Book presents it as a way to do type inference). By the sounds of it, you could benefit from learning a bit about parsing ... which is also covered by the Dragon Book.

EDIT: Other answers have suggested using a parser generator; e.g. ANTLR. That's good advice, but (judging from your example) your grammar is so simple that you could also get by with using StringTokenizer and a hand-written recursive descent parser. In fact, if you've got the time (and inclination) it is worth implementing the parser both ways as a learning exercise.

Upvotes: 1

Pete Kirkham
Pete Kirkham

Reputation: 49321

Before you get to do the semantics of the language, you have to convert the text into a form that's easy to operate on. This process is called parsing and the semantic representation is called an abstract syntax tree (AST).

A simple recursive descent parser for Prolog might be hand written, but it's more common to use a parser toolkit such as Rats! or Antlr

In an AST for Prolog, you might have classes for Term, and CompoundTerm, Variable, and Atom are all Terms. Polymorphism allows the arguments to a compound term to be any Term.

Your unification algorithm then becomes unifying the name of any compound term, and recursively unifying the value of each argument of corresponding compound terms.

Upvotes: 0

please delete me
please delete me

Reputation:

It sounds like this problem is more to do with parsing than unification specifically. Using something like ANTLR might help in terms of turning the original string into some kind of tree structure.

(It's not quite clear what you mean by "do it by nested", but if you mean that you're doing something like trying to read an expression, and recursing when meeting each "(", then that's actually one of the right ways to do it -- this is at heart what the code that ANTLR generates for you will do.)

If you are more interested in the mechanics of unifying things than you are in parsing, then one perfectly good way to do this is to construct the internal representation in code directly, and put off the parsing aspect for now. This can get a bit annoying during development, as your Prolog-style statements are now a rather verbose set of Java statements, but it lets you focus on one problem at a time, which is usually helpful.

(If you structure things this way, this should make it straightforward to insert a proper parser later, that will produce the same sort of tree as you have until then been constructing by hand. This will let you attack the two problems separately in a reasonably neat fashion.)

Upvotes: 0

Related Questions