Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Next revision		Previous revision
tutorials:beginner:cram_prolog [2015/05/28 18:15] – created gkazhoyatutorials:beginner:cram_prolog [2022/05/26 12:32] (current) – [Using built-in predicates] schimpf
Line 1: Line 1:
 ====== Using Prolog for reasoning ====== ====== Using Prolog for reasoning ======
 +
 +**Description:** In this tutorial you will learn how the Prolog interpreter that we have inside of CRAM works, what does the syntax look like and what it is at all useful for.
 +
 +**Previous Tutorial:** [[tutorials:beginner:simple_plans|Implementing simple plans to move a turtle]]\\
 +**Next Tutorial:** [[tutorials:beginner:motion_designators|Creating motion designators for the TurtleSim]]
 +==== Using built-in predicates ====
  
 This is a short REPL tutorial to demonstrate the usage of CRAM Prolog engine for solving reasoning tasks. This is a short REPL tutorial to demonstrate the usage of CRAM Prolog engine for solving reasoning tasks.
  
 CRAM has its own primitive Prolog interpreter written in Common Lisp which can work natively with the Lisp data structures (as opposed to, e.g., SWI Prolog, which would need a complex mechanism for passing around Lisp data structures and converting Prolog results back into Lisp). CRAM has its own primitive Prolog interpreter written in Common Lisp which can work natively with the Lisp data structures (as opposed to, e.g., SWI Prolog, which would need a complex mechanism for passing around Lisp data structures and converting Prolog results back into Lisp).
-It is implemented in the "cram_reasoning" package, so, first of all, let's load the package:+It is implemented in the ''cram_prolog'' package, so, first of all, let's load the package:
  
 <code lisp> <code lisp>
-CL-USER> (asdf:load-system :cram-reasoning) +CL-USER> (asdf:load-system :cram-prolog) 
-CL-USER> (in-package :cram-reasoning)+CL-USER> (in-package :cram-prolog)
 </code> </code>
  
 Executing Prolog queries is done by calling the ''prolog'' function, where its first argument is a list of symbolic data: Executing Prolog queries is done by calling the ''prolog'' function, where its first argument is a list of symbolic data:
 <code lisp> <code lisp>
-CRS> (prolog '(member ?x (1 2 3)))+PROLOG> (prolog '(member ?x (1 2 3)))
 (((?X . 1)) (((?X . 1))
  . #S(CRAM-UTILITIES::LAZY-CONS-ELEM :GENERATOR #<CLOSURE # {100A55B86B}>))  . #S(CRAM-UTILITIES::LAZY-CONS-ELEM :GENERATOR #<CLOSURE # {100A55B86B}>))
 </code> </code>
-This query means: find such a binding (assignment) for the variable ''?x'' such that the statement "''?x'' is a member of the list ''(1 2 3)'' would be true. Obviously, there are multiple bindings for ''?x'' that satisfy the statement, namely, ''1'', ''2'' or ''3'' are all valid assignments for ''?x''. \\ +This query means: find such a binding (assignment) for the variable ''?x'' such that the predicate (statement) "''?x'' is a member of the list ''(1 2 3)'' would be true. Obviously, there are multiple bindings for ''?x'' that satisfy the statement, namely, ''1'', ''2'' or ''3'' are all valid assignments for ''?x''. \\ 
-Sometimes there can be very many valid bindings for a variable or even an infinite amount of solutions. Thus, CRAM Prolog interpreter returns the bindings as a lazy list and not a normal list. A lazy list returns per default one value at a time and uses a generator function to spit out more values when required.+Sometimes there can be very many valid bindings for a variable or even an infinite amount of solutions. Thus, CRAM Prolog interpreter returns the bindings as a lazy list and not a normal list. A lazy list returns per default one value at a time and uses a generator function to spit out more values when requested. \\ 
 +We can force a lazy list to become a normal list with the function ''force-ll'': 
 + 
 +<code lisp> 
 +PROLOG> (force-ll (prolog '(member ?x (1 2 3)))) 
 +(((?X . 1)) ((?X . 2)) ((?X . 3))) 
 +</code> 
 + 
 +=== Using unbound variables === 
 + 
 +Variables in CRAM Prolog are represented by any symbol that starts with ''?'' (question mark). \\ 
 +If a variable in some predicate of the Prolog query has no value assigned to it we say that the variable is unbound. 
 +We can also have queries with multiple unbound variables, e.g.: 
 +<code lisp> 
 +PROLOG> (defparameter *some-list* '((1) (2 3) (4 5 6))) 
 +*SOME-LIST* 
 +PROLOG> (force-ll (prolog `(and (member ?x ,*some-list*) 
 +                                (length ?x ?x-len)))) 
 +(((?X 1) (?X-LEN . 1)) ((?X 2 3) (?X-LEN . 2)) ((?X 4 5 6) (?X-LEN . 3))) 
 +</code> 
 +Then we get one correct possible assignment for all the variables as one entry of the lazy list. 
 + 
 +It is important to remember that the ` is needed for unbound variables, not the ' or you will get an error. 
 + 
 +=== No solution === 
 +If there are no solutions for the query Prolog returns NIL: 
 +<code lisp> 
 +PROLOG> (prolog '(and (member ?x (1 2 3)) 
 +                      (< ?x 0))) 
 +NIL 
 +</code> 
 + 
 +If there are no unbound variables in the query but the query itself is true, Prolog returns a list where bindings are NIL: 
 +<code lisp> 
 +PROLOG> (force-ll (prolog '(> 4 0))) 
 +(NIL) 
 +</code> 
 +=== Using lisp with prolog code === 
 +The CRAM Prolog interpreter finds solutions by performing a depth first search over the predicate tree, that it, it first searches for possible bindings for the first predicate, then branches into multiple search paths, one per each assignment, and continues with the second predicate, and so on. The mechanism is the same as in any other Prolog implementation. 
 + 
 +One difference between CRAM Prolog and conventional implementations is that some predicates can be proven by using a Lisp function and not through depth-first search over possible solutions. For that predicates ''lisp-fun'' and ''lisp-pred'' can be used: 
 +<code lisp> 
 +PROLOG> (force-ll (prolog '(lisp-pred oddp 3))) 
 +(NIL) 
 +</code> 
 +For solving the problem of finding out if 3 is odd or not in a Prolog way the engine would need to have a database of all the odd numbers and would have to search if 3 is in that database. By calculating the result instead of looking it up through depth first search one can solve continuous and geometric problems such as where on a table should I put the box so that it doesn't obstruct me from seeing the monitor that is standing on the same table. 
 + 
 + 
 +==== Defining custom predicates ==== 
 + 
 +Please note that in Prolog there can (and usually are) multiple ways of proving the same predicate (multiple implementations), which means that predicate implementations don't get overwritten but are always being added up. In order to be able to replace an old implementation with a new one CRAM Prolog has a notion of "fact groups" which are the basic "compilation" units of the Prolog engine. Each time a fact group is being recompiled all the old implementations inside the group are being replaced with the new ones, whereas implementations of the same predicates from other fact groups stay valid as they were. 
 + 
 +We call predicate definitions //rules// or //facts//. For defining custom Prolog predicates CRAM Prolog uses the macro ''def-fact-group'' with ''<-'': 
 + 
 +<code lisp> 
 +PROLOG> (def-fact-group family-predicates () 
 +          (<- (grandparent ?grandparent ?grandkid) 
 +            (parent ?grandparent ?x) 
 +            (parent ?x ?grandkid))) 
 +</code> 
 + 
 +Here we defined a compilation unit called ''family-predicates'' which currently contains only one rule, which says that a predicate ''grandparent'' is true for two variables ''?grandparent'' and ''?grandkid'' if there is a certain binding for ''?x'' such that ''?grandparent'' is a ''parent'' of ''?x'' and ''?x'' is a ''parent'' of ''?grandkid''. Next let's extend our ''family-predicates'' group with some ''parent'' relationships: 
 + 
 +<code lisp> 
 +PROLOG> (def-fact-group family-predicates () 
 + 
 +          (<- (grandparent ?grandparent ?grandkid) 
 +            (parent ?grandparent ?x) 
 +            (parent ?x ?grandkid)) 
 +        
 +          (<- (parent my-dad me)) 
 +          (<- (parent me my-kid))) 
 +</code> 
 + 
 +The definitions for ''parent'' that we specified claim that ''my-dad'' (which is of type ''COMMON-LISP:SYMBOL'') is ''parent'' of ''me'' and ''me'' is ''parent'' of ''my-kid''. These predicates have no body, such predicate definitions are called "facts" and not "rules" in Prolog. 
 + 
 +Finally, let's test our new custom predicates: 
 + 
 +<code lisp> 
 +PROLOG> (force-ll (prolog '(grandparent my-dad my-kid))) 
 +(NIL) 
 +PROLOG> (force-ll (prolog '(and (parent ?parent-of-me me) 
 +                                (grandparent ?grandparent-of-my-kid my-kid)))) 
 +(((?PARENT-OF-ME . MY-DAD) (?GRANDPARENT-OF-MY-KID . MY-DAD))) 
 +</code> 
 + 
 + 
 +Now that we are familiar with the CRAM Prolog syntax, let's dive right into resolving CRAM abstract entity descriptions, called designators, using Prolog ... 
 + 
 +**Next Tutorial:** [[tutorials:beginner:motion_designators|Creating motion designators for the TurtleSim]]