Documention for: prolog.r Created by: coccinelle on: 24-Nov-2004 Last updated by: coccinelle on: 15-Aug-2005 Format: text/editable Downloaded on: 28-Mar-2024 The Prolog (Like) Inference Engine Documentation prolog.r is an inference engine which can process prolog like clauses in the form of : man [jean] woman [mary] human [X] [man [X]] human [X] [woman [X]] This quick example illustrates how to load the engine, assert clause in the knowledge base and how to submit a goal and how to retrieve all the possible solution: do %prolog.r ex-base: assert none [ man [carl] man [paul] man [marco] ] print [newline "*** Man list ***"] goal ex-base [ man [X] (print ["==>" X "is a man."]) ] =TOC ===Specification ---The interface The engine provide the following interface : :ASSERT - which allows you to assert clauses into a knowledge base :RETRACT - which allows you to retract clauses from a knowledge base :GOAL - which allows to process a goal :FOR-WHICH - which allows you to execute a block of REBOL code for each goal solution :BENCH-GOAL - which allows you to bench your predicates +++assert USAGE: ASSERT base clauses DESCRIPTION: Create or update a KB block with parsed clauses. Return the KB block. ASSERT is a function value. ARGUMENTS: base -- KB block or none for a new base (Type: block none) clauses -- Clauses block to be parsed (Type: block) If you want to create a new knowledge base, give none for the base parameter. If you want to add clauses to a knowledge base, give the base into which the clauses must be added. NB. The clause are always appended to the knowledge base. Perhaps, it will be usefull to have a /head refinement to insert it instead of append it. +++retract USAGE: RETRACT base predicat /all DESCRIPTION: Retract a clause from the block RETRACT is a function value. ARGUMENTS: base -- The KB block (Type: block) predicat -- The predicate to retract (Type: block) REFINEMENTS: /all Retract removes all clauses for which the head of the clause can be matched with the predicate. NB: This is not very well tested up to now. +++goal USAGE: GOAL base goals DESCRIPTION: Try a goal and return the number of solution GOAL is a function value. ARGUMENTS: base -- The KB to use (Type: block) goals -- The goals to try (Type: block) +++for-which USAGE: FOR-WHICH base 'word goals body DESCRIPTION: Try a goal and execute the body for each solutions ARGUMENTS: base -- The KB to use (Type: block) word -- The word or block of word to set for each solutions (will be local) (Type: word block) goals -- The goals to try (Type: block) body -- The block to evaluates for each solutions (Type: block) (SPECIAL ATTRIBUTES) throw +++bench-goal USAGE: BENCH-GOAL count base goals DESCRIPTION: Try a goal n times and return the time to do it BENCH-GOAL is a function value. ARGUMENTS: count -- (Type: integer) base -- The KB to use (Type: block) goals -- The goals to try (Type: block) ---Differences between Prolog syntax and prolog.r dialect The main difference is that the prolog.r dialect use block [] instead of parenthesis (). An other difference is that the body of the predicates is placed within a block. For example, the (Turbo) Prolog : grandfather (X, Y) :- father (X, Z), father (Z, Y). Is in the prolog.r dialect : grandfather [X Y] [ father [X Z] father [Z Y] ] This is simply because it's more simple to parse and manipulate block than strings in REBOL and also, because when you load your script, REBOL check missing brackets if any. An other difference is that you can place REBOL code within your clauses. For example, to print out some information, you can do this : grandfather [X Y] [ father [X Z] father [Z Y] (print [X "is the grandfather of" Y]) ] You can also place REBOL script within the parameters of a predicate. For example the following clauses : sum [X Y (X + Y)] sum [X (Z - X) Z] sum [(Z - Y) Y Z] Will give back the third parameter when you give only two or check that the first plus the second equal the third when you give the three parameters. The last difference, is that you can organize your knowledge into many base. To access to the clauses from one base to another, you must use path, for example : facts: assert none [ father [marco paul] father [arnaldo marco] ] rules: assert none [ grandfather [X Y] [ facts/father [X Z] facts/father [Z Y] ] ] This can be usefull to organize your knowledge base, frequently one base for the rules (your logic) one base for the facts (the knowleddge base) and one base for the case (the deduction done for the applied case). Except these differences, the Prolog syntax is respected. Variables are word that begins with an uppercase letter or an underscore (_). Others words are considered as symbol. The CUT is available (CUT or !) and also the FAIL. CUT and FAIL are the only programed predicates. All others predifefined predicates are standard predicates. ---Predifined predicates prolog.r offers a set of predefined predicates: :NOT - not [X] fails when X succeeds :EQUAL? - equal?[X Y] succeeds when X can be unified with Y :NOT-EQUAL? - not-equal? [X Y] fails when X can be unified with Y :IF - if [value] succeeds when the value is not none or false. If you want to test REBOL script, place it within parenthesis, example if [(X > Y)]. :FREE - free [X] succeeds when X has no value, in other words, when X is none :BOUND - bound [X] succeeds when X has a value, in other words, when X is not none. :ADD - add [X Y Z] succeeds when X + Y equals Z. With ADD you can do addition but also substraction (add [1 Y 3] return with Y set to 2) :MULT - mult [X Y Z] succeeds when X * Y equals Z. Like with ADD, you can do multiplication but also division (mult [2 Y 8] return with Y set to 4] :REPEAT - repeat never fails. repeat [N] fails after N time successfull (usefull for loop) prolog.r offer also another facility which is very simple but quiet difficult to explain. An example is much more simple: mother [anne cathy] mother [cathy cindy] display-all-mother [][ mother? [X _] (print [X "is a mother]) ] In this example you can see that I didn't define the mother? predicates. I can do this because prolog.r defines it automaticaly in the following manner : mother? [X Y] [ mother [X Y] ! ] With this, the predicate succeeds (only one time due to the cut) if the predicate whitout the question mark (?) succeeds. This prevents you to define this kind of predicate. ===Examples Here under, you will find a set of example that I use to test the engine ---Father, mother and so on ... Here, the facts and the predicates ex-base: assert none [ ; The facts ; --------- man [jean] man [pierre] man [jacques] man [albert] man [yvan] man [marco] woman [jeanne] woman [anne] father [jacques pierre] father [jean jacques] father [jacques anne] mother [jeanne anne] mother [jeanne jean] mother [anne pierre] ; The predicates ; -------------- ; A person is a man or a woman person [X] [ man [X] ] person [X] [ woman [X] ] ; A father is a man and is the father of at least one child father [X] [ man [X] father? [X _] ] ; A mother is a woman and mother of at least one child mother [X] [ woman [X] mother? [X _] ] ; A parent is a father or a mother parent [X Y] [ father [X Y] ] parent [X Y] [ mother [X Y] ] ; A parent is a person which is at least one time parent parent [X] [ person [X] parent? [X _] ] ] How to print who is a man print [newline "*** List of man ***"] goal ex-base [ man [X] (print ["==>" X "is a man"]) ] How to print who is a person (a man or a woman) print [newline "*** List of persons ***"] goal ex-base [ person [X] (print ["==>" X "is a person"]) ] How to print who is a father print [newline "*** List of father ***"] goal ex-base [ father [X] (print ["==>" x "is a father"]) ] How to print who is a parent (a father or a mother) print [newline "*** List of parents ***"] goal ex-base [ parent [X] (print ["==>" X "is a parent"]) ] How to print all the couples mother daughter print [newline "*** List of mother/daughter couple (use of for-which) ***"] for-which ex-base [ Y Z ][ mother [Y Z] woman [Z] ][ print [Y "is the mother of" Z] ] The following examples cannot be done with many Prolog (Turbo Prolog and his successor Visual Prolog for example) How to print all the relationship with anne. print [newline "*** List of anne's relationship ***"] goal ex-base [ X [Y anne] (print ["==>" Y "is the" X "of anne"]) ] How to print all the couple mother daughter print [newline "*** List of relationship between anne and pierre ***"] goal ex-base [ X [anne pierre] (print ["==> anne" "is the" X "of pierre"]) ] How to print all relationship two by two print [newline "*** List of all relationship two by two ***"] goal ex-base [ X [Y Z] (print ["==>" mold Y "is the" X "of" mold Z]) ] How to print all the relationship print [newline "*** List of all relationship ***"] goal ex-base [ X Y (print ["==>" X mold Y]) ] ---Reverse and concat of list Here are three example of list manipulation ex-base: assert none [ ; Invert of a list invert [[|X] [|Y]] [ invert [X [] Y] ] invert [[] X X] [!] invert [[X | Y] Z W] [ invert [Y [X | Z] W] ] ; Concat of two lists concat [[] L L] [!] concat [[X | L1] L2 [X | L3]] [ concat [L1 L2 L3] ] ; Reverse known as naive reverse of a list nrev [[] []] [!] nrev [[X | Y] L] [ nrev [Y Z] concat [Z [X] L] ] ] print [newline "*** Invert of [0 1 2 3 4 5 6 7 8 9] ***"] goal ex-base [ invert [[0 1 2 3 4 5 6 7 8 9] [] X] (print ["==> Invert of [0 1 2 3 4 5 6 7 8 9] is" mold X]) ] print [newline "*** Concat of [0 1 2 3 4] ans [5 6 7 8 9] ***"] goal ex-base [ concat [[0 1 2 3 4] [5 6 7 8 9] X] (print ["==> Concat of [0 1 2 3 4] [5 6 7 8 9] is" mold X]) ] print [newline "*** Naive reverse call from outside (for which) ***"] for-which ex-base [ Y ][ nrev [[1 2 3] Y] ][ print ["Naive reverse of [1 2 3] is" mold Y] ] ---How to optimize the cutting of a bar in many pieces I create this example when Guy (a guy which name is Guy) asked on the french forum how to resolve this problem in REBOL. The predicate "combine" receive in input the length, the element list and return the remainder and the solution. ex-base: assert none [ ; If the first element is smaller or equal to the length, it's a solution combine [L [X1 | _] (L - X1) [X1]][ if [(L >= X1)] ] ; If the first element is smaller or equal to the length, ; we try for the rest of the length combine [L [X1 | X] R [X1 | Y]] [ if [(L >= X1)] combine [(L - X1) [X1 | X] R Y] ] ; If the length is greater than 0 ; we try with the rest of the element combine [L [_ | X] R Y] [ if [(L > 0)] combine [L X R Y] ] ] print [newline "*** Optimization of the cutting of a bar of 25 meters in element of 10 4 and 3 ***"] result: copy [] for-which ex-base [RB C] [ combine [25 [10 4 3] RB C] ][ append result reduce [RB C] ] sort/skip result 2 foreach [R C] result [ print ["The remainder is" R "for the combination" mold C] ] ---Resolving a murder Here are the deducting rules rule: assert none [ ; R1 ; Someone (X) could have killed a person (Y) one day (Z) if : ; X have a weapon ; X can wish to kill Y ; X does not have an alibi for day Z can-have-killed [X Y Z] [ fact/has-a-weapon [X] wish-to-kill [X Y] day [Z] does-not-have-an-alibi-for-day [X Z] ] ; R2 ; Someone (X) has not an alibi for the day (Y) if : ; either he does not have an alibi for the day ; either the alibi is given by a doubtful person does-not-have-an-alibi-for-day [X Y] [ not [fact/has-an-alibi [X Y _]] ] does-not-have-an-alibi-for-day [X Y][ fact/has-an-alibi [X Y Z] fact/is-doubtful [Z] ] ; R3 ; Someone (X) can wish to kill a person (Y) if ; maybe if he wishes to be avenged of Y ; maybe if he is the heir of Y ; maybe if he has seen committing a crime by Y ; maybe if he must give back money to Y wish-to-kill [X Y][ fact/wish-to-be-avenged [X Y] ! ] wish-to-kill [X Y][ fact/is-the-heir [X Y] ! ] wish-to-kill [X Y][ fact/has-seen-committing-a-crime [Y X] ! ] wish-to-kill [X Y][ fact/must-give-back-money [X Y] ! ] ; List of the day of the week day [ monday ] day [ tuesday ] day [ wednesday ] day [ thursday ] day [ friday ] day [ saturday ] day [ sunday ] ] Here the result of the investigation fact: assert none [ ; The alibis has-an-alibi [luc tuesday bernard] has-an-alibi [paul tuesday bernard] has-an-alibi [louis tuesday luc] has-an-alibi [alain thursday luc] ; The doubtful person is-doubtful [alain] ; Who wish to be avenged wish-to-be-avenged [paul jean] wish-to-be-avenged [luc jean] ; Who is the heir of who is-the-heir [bernard jean] is-the-heir [jean louis] ; Who must give back money to who must-give-back-money [louis jean] must-give-back-money [luc jean] ; Who has seen committing a crime has-seen-committing-a-crime [jean alain] ; Who has a weapon has-a-weapon [luc] has-a-weapon [louis] has-a-weapon [alain] ] Here we call the goals print [newline "*** Who killed jean Tuesday ***"] goal rule [ can-have-killed [X jean tuesday] (print ["==>" X "can have done it"]) ] print [newline "*** Who could be a murder ***"] goal rule [ fact/has-a-weapon [X] can-have-killed? [X _ _] (print ["==>" X "could be a murder"]) ] print [newline "*** Who could be a victim ***"] goal rule [ can-have-killed? [_ Y _] (print ["==>" Y "could be killed"]) ] print [newline "*** When a crime could take place?***"] goal rule [ day [Z] can-have-killed? [_ _ Z] (print ["==> A crime could take place" Z]) ] === Performance On my PC, the performance of prolog.r is around 650 LIPS (Logical Inference Per Second). It's quiet few but this is mesured on predicate that you will never implement in prolog dialect. The usual bench to mesure LIPS is the NREV predicate (naive reverse of a list) : do %engine.r print "" print "****************************" print "**** Start of benchmark ****" ex-base: assert none probe [ concat [[] L L] [!] concat [[X | L1] L2 [X | L3]] [ concat [L1 L2 L3] ] nrev [[] []] [!] nrev [[X | Y] L] [ nrev [Y Z] concat [Z [X] L] ] ] i: 100 j: 0 t: bench-goal i ex-base [ nrev [[1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30] L] (print ["Boucle :" j: j + 1]) ] print ["Length" t] print ["Performance (LIPS)" (i * (30 + 1) * (30 + 2) / 2) / to-decimal t] print "" print "**** End of benchmark ****" print "**************************" First of all, I am not a specialist of programming langage. I have no particular competence to build things like that and I make it with my own logic just for fun. Certainly a guy with all the necessary competences will make it much more faster and smaller. You should also take prolog.r as an add-on to REBOL and use it only for non-deterministic logic. If you want to reverse a list, use the reverse REBOL function. It's why it was very important to be able to embed REBOL code within the clauses in a simple manner, as it was also important to invoke the goals easyly. So I hope that the obtained performances are good enough for small part of a program where it's much more easy to specify the logic with clauses. And for the remaining part of the programm, we should write it with standard REBOL script. Perhaps Carl will implement a native unify function which will be usefull for prolog.r but also for other REBOL script. In the same manner, if the find/match rafinement functioned on the blocks, prolog.r would be much faster. But this it's another story. ===Conclusion When I was programming in Turbo Prolog, I found very tedious to write all the deterministic part of the program with clauses that you force to be deterministic with a lot of CUT. I believe prolog.r, which allows the mix of REBOL and Prolog within the same script and with a syntax continuity, is a good base to write funny script with Logic Programming. I hope you will have fun with it, Marco. ###