13.8 Additional Features of Logikus


 
Building Parsers with Java
By Steven  John  Metsker

Table of Contents
Chapter  13.   Logic Programming

    Content

At this point, we have covered the fundamentals of logic programming. If you understand structures, variables , facts, and rules, you can create logic programs to model logical problems in the real world. In practice, several other features enhance this modeling, including

  • Comments

  • Evaluations

  • Negation

  • Anonymous variables

  • Lists

13.8.1 Comments

The Logikus parser that comes with this book accepts comments in the same format that Java does. A comment that begins with // extends to the end of the line on which it appears. For example, the line

 founded(rome, bc750); // according to legend... 

provides a comment on the stated fact.

A comment that begins with /* comments out all text until the next */ . If there is no matching */ comment terminator, the Logikus parser accepts the end of the program as the end of the comment.

13.8.2 Evaluations

Logikus provides an evaluation structure that unifies its first term with an evaluation of its second term . The functor for the evaluation structure is "#". For example, if you enter the query

 #(X, (100 - 1)*(100 + 1)) 

and click Next, the Results area displays

 X = 9999.0 

As with comparisons, evaluations are gateways, which can be true no more than once in a proof. If you click Next again, the Results area displays

 no 

The second term in an evaluation can be a string or an arithmetic expression. Logikus recognizes arithmetic operators for multiplication (" * "), division (" / "), addition (" + ") and subtraction (" - ").

You can use evaluation structures as parts of queries or rules. Figure 13.4 shows an evaluation in action. (This Logikus program is on the CD in the file art.txt .)

Figure 13.4. An evaluation structure in action. The painterAge rule calculates an artist's age at the time he or she completed a particular painting.

graphics/13fig04.gif

If the first term in an evaluation is an unbound variable, the evaluation acts as if it were an assignment command: The variable in the first term binds to the value of the second term. However, it is not always correct to think of evaluation as assignment. The evaluation structure unifies its first term with the value of its second term. For example, consider the evaluation

 #(X, X + 1) 

This evaluation can never succeed. If X has a value, the evaluation attempts to unify X with the value of X + 1 . For example, if X is bound to 7 , the evaluation attempts to unify 7 with 8 . On the other hand, if X is not bound to a value, the evaluation fails when it attempts to evaluate X + 1 .

Given that the evaluation #(X, X + 1) always fails, you might think that it is impossible to achieve iteration in a Logikus program. Perhaps this would be no great loss because iteration goes against the grain of logic programming. Rather than direct the flow of execution, a logic program models truth and works with a query to find variable values that make the query true. However, it turns out that you can effect iteration in a logic program. Section 13.12.5, "Altitude Bands," gives an example.

13.8.3 Negation

It can be useful to determine that the engine cannot prove a structure. The not qualifier in Logikus modifies the proof of a structure so that the proof fails if the structure can prove itself against a program and succeeds if the structure cannot prove itself. For example, consider the following logic program:

 bachelor(X) :- male (X), not married(X);  married(jim); male(jeremy); male(jim); 

Against this program, the query

 bachelor(B) 

finds that the only bachelor in the program is jeremy . The query unifies with the program's bachelor rule, unifying the query's B variable with the rule's X variable. The query asks the rule to prove its remaining structures. The rule proves male(X) by unifying with the fact male(jeremy) . Then the rule attempts to prove not married(jeremy) . This proof proceeds by trying to prove married(jeremy) . This fails, and so not married(jeremy) succeeds.

If asked for another proof, the query begins by asking the rule it unified with for another proof. This rule in turn asks its last structure for another proof. Not structures are gateways (and thus true no more than once), so the not structure fails, and the rule backtracks to the male structure. This structure successfully unifies with male(jim) , and the rule moves forward again. The rule asks the structure not married(jim) to prove itself. This not structure tries to prove married(jim) and succeeds because the program contains this exact fact. The structure not married(X) fails if X has unified with jim , because Jim is married.

Like comparisons and evaluations, not structures are gateways. If a not structure succeeds as part of a proof, when the rule or query it is in backtracks to the not structure, it automatically fails.

13.8.4 Not Dangerous

The meaning of not leads to subtleties. For example, the engine query

 not dangerous 

usually returns true. This means that the engine cannot find the fact dangerous in the program.

The fact that not declares that a structure is unprovable can lead to mystifying results. For example, suppose you change the bachelor program to read

 badBachelor(X) :- not married(X), male(X);  married(jim); male(jeremy); male(jim); 

Then the query

 badBachelor(B) 

finds no bachelors at all. The engine matches this query with the badBachelor rule and then attempts to prove not married(X) . Because X is unbound, this is a request to prove that no one is married. The structure married(X) succeeds with the binding X = jim . Because married(X) succeeds, not married(X) is false, and badBachelor(X) is false.

Negations usually make sense only if they appear later in a rule's body than other structures that establish values for variables on which the negated structure relies. In the original bachelor program, not married(X) appears later than male(X) . Thus, not married(X) tries to prove itself only after X has unified with a value, such as jim or jeremy .

13.8.5 Anonymous Variables

Anonymous variables let you avoid creating variable names for variables that you are not interested in. To indicate that you want an anonymous variable, you use an underscore (" _ "). For example, Figure 13.5 shows a query that uses anonymous variables with data from coffee.txt .

Figure 13.5. Anonymous variables. The query in this figure uses two anonymous variables to reduce the information it retrieves from the program.

graphics/13fig05.gif

Anonymous variables do not unify with corresponding terms in other structures, but they do allow unification to succeed. Note that the following query finds no coffee:

 coffee(Name, X, X, Price) // bad 

For the coffees in Figure 13.5, this query fails because the variable X first unifies with a coffee's roast, and then it tries to unify with a coffee's country, which is different in every case. (You could use this query to find coffees whose roast and country are identical, but no such coffees exist in the given program.)

You can use anonymous variables in rules to provide projections, or views of relations, including relational joins. For example, suppose that you are modeling a family tree with these facts:

 begat(900, jim, 19350801, male);  begat(901, janie, 19370310, female); begat(902, kyle, 19600829, male); begat(903, kirk, 19550404, male); begat(904, kevin, 19580815, male); marriage(001, jim, janie, 19560512, present); begat(001, karla, 19570114, female); begat(001, katie, 19590712, female); marriage(002, kevin, karla, 19790623, 19831112); begat(002, leo, 19800115, male); begat(002, lisa, 19810226, female); marriage(003, kirk, karla, 19900114, present); marriage(004, katie, kyle, 19951203, present); begat(004, laura, 19980217, female); 

These facts are a subset of the sample Logikus program contained in the CD file family.txt . The facts model each child as the product of a marriage; marriage structures have an ID, the names of the parents, and the dates of the marriage. In this model, begat structures refer to the marriage that begat the individual; they have the person's name, birth date, and sex. With this foundation, you can use anonymous variables to produce views of the data, such as

 male(X)         :- begat(_, X, _, male);  female(X)       :- begat(_, X, _, female); birthdate(X, D) :- begat(_, X, D, _); 

In addition to simplifying the creation of logical views, anonymous variables can help keep extraneous data from interfering in a logical relationship. For example, here is a rule for defining siblings:

 siblings(X, Y) :-      begat(MarriageID, X, _, _),     begat(MarriageID, Y, _, _),     !=(X, Y); 

The siblings rule uses anonymous variables to keep birth date and sex from affecting the sibling relationship. This rule uses the " != " comparison to avoid counting a child as his or her own sibling. However, this rule finds every pair of siblings twice. To avoid this, you can introduce the rule

 siblingPair(X, Y) :-      begat(MarriageID, X, Dx, _),     begat(MarriageID, Y, Dy, _),     <(Dx, Dy); 

This rule finds only sibling pairs in which one child is born first. In the case of twins, that requires more precision in modeling birth times.


   
Top


Building Parsers with Java
Building Parsers With Javaв„ў
ISBN: 0201719622
EAN: 2147483647
Year: 2000
Pages: 169

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net