1#lang scribble/manual 2@(require scribble/eval 3 (for-syntax racket) 4 (for-label racklog 5 (except-in racket _))) 6 7@(define racklog-eval (make-base-eval)) 8@(racklog-eval '(require racklog)) 9 10@title{Racklog: Prolog-Style Logic Programming} 11 12@author{Dorai Sitaram} 13 14@margin-note{Adapted from Schelog by Dorai Sitaram for Racket by Dorai Sitaram, 15 John Clements, and Jay McCarthy.} 16 17@defmodule[racklog] 18 19Racklog is an @emph{embedding} of 20Prolog-style logic programming in Racket. ``Embedding'' 21means you don't lose Racket: You can use Prolog-style and 22conventional Racket code fragments alongside each other. 23Racklog contains the full repertoire of Prolog features, 24including meta-logical and second-order (``set'') 25predicates, leaving out only those features that could more 26easily and more efficiently be done with Racket 27subexpressions. 28 29The Racklog implementation uses the approach to logic 30programming for Scheme described in Felleisen @cite{mf:prolog} and 31Haynes @cite{logick}. In contrast to earlier Lisp simulations of 32Prolog @cite{campbell}, 33which used explicit continuation 34arguments to store failure (backtrack) information, the 35Felleisen and Haynes model uses the implicit reified 36continuations of Scheme. In Racket these are provided by the operator 37@racket[call-with-current-continuation] (aka @racket[call/cc]). This 38allows Racklog to be an @emph{embedding}, ie, logic 39programming is not built as a new language on top of Racket, 40but is used alongside Racket's other features. Both styles 41of programming may be mixed to any extent that a project 42needs. 43 44The Racklog user does not need to know about the 45implementation mechanism or about @racket[call/cc] and 46continuations to get on with the business of 47doing logic programming with Racklog. 48 49This text is a gentle introduction to Racklog syntax 50and programming. It assumes a working knowledge of 51Racket and an awareness of, if not actual programming 52experience with, Prolog. If you need assistance for Prolog, 53you may consult @cite["bratko" "ok:prolog" "aop"] or 54many other excellent books and 55online documents available. 56 57@table-of-contents[] 58 59@section[#:tag "simple"]{Simple Goals and Queries} 60 61Racklog objects are the same as Racket objects. However, there 62are two subsets of these objects that are of special 63interest to Racklog: @emph{goals} and @emph{predicates}. We 64will first look at some simple goals. 65@secref{predicates} will introduce predicates and ways 66of making complex goals using predicates. 67 68A goal is an object whose truth or falsity we can check. A 69goal that turns out to be true is said to succeed. 70A goal that turns out to be false is said to 71fail. 72 73Two simple goals that are provided in Racklog are: 74@racketblock[ 75%true 76%fail 77] 78 79The goal @racket[%true] succeeds. The goal @racket[%fail] 80always fails. 81 82(The names of all Racklog primitive objects 83start with @litchar{%}. This is to avoid clashes with the names 84of conventional Racket objects of related meaning. 85User-created objects in Racklog are not required to 86follow this convention.) 87 88A Racklog user can @emph{query} a goal by wrapping it in a 89@racket[%which]-form. 90 91@racketblock[ 92(%which () %true) 93] 94 95evaluates to @racketresult[()], indicating success, whereas: 96 97@racketblock[ 98(%which () %fail) 99] 100 101evaluates to @racket[#f], indicating failure. 102 103Note 1: The second subexpression of the @racket[%which]-form 104is the empty list @racketresult[()]. Later (@secref{solving-goals}), 105we will see @racket[%which]es 106with other lists as the second subform. 107 108Henceforth, we will use the notation: 109 110@interaction[(eval:alts E 'F)] 111 112to say that @racket[E] @emph{evaluates to} @racket[F]. Thus, 113 114@interaction[#:eval racklog-eval (%which () %true)] 115 116@section[#:tag "predicates"]{Predicates} 117 118More interesting goals are created by applying a special 119kind of Racklog object called a @emph{predicate} (or 120@emph{relation}) to other 121Racklog objects. Racklog comes with some primitive 122predicates, such as the arithmetic operators 123@racket[%=:=] and @racket[%<], 124standing for arithmetic ``equal'' and ``less than'' 125respectively. For example, the following are some goals 126involving these predicates: 127 128@interaction[ 129 #:eval racklog-eval 130 (%which () (%=:= 1 1)) 131 (%which () (%< 1 2)) 132 (%which () (%=:= 1 2)) 133 (%which () (%< 1 1)) 134 ] 135 136Other arithmetic predicates are 137@racket[%>] (``greater than''), 138@racket[%<=] (``less than or equal''), 139@racket[%>=] (``greater than or equal''), and 140@racket[%=/=] (``not equal''). 141 142Racklog predicates are not to be confused with conventional 143Racket predicates (such as @racket[<] and @racket[=]). Racklog 144predicates, when applied to arguments, produce goals 145that 146may either succeed or fail. Racket predicates, when applied 147to arguments, yield a boolean value. Henceforth, we will 148use the term ``predicate'' to mean Racklog predicates. 149Conventional predicates will be explicitly called ``Racket 150predicates''. 151 152@subsection[#:tag "facts"]{Predicates Introducing Facts} 153 154Users can create their own predicates using the Racklog form 155@racket[%rel]. For example, let's 156define the predicate @racket[%knows]: 157 158@racketblock+eval[#:eval racklog-eval 159(define %knows 160 (%rel () 161 [('Odysseus 'TeX)] 162 [('Odysseus 'Racket)] 163 [('Odysseus 'Prolog)] 164 [('Odysseus 'Penelope)] 165 [('Penelope 'TeX)] 166 [('Penelope 'Prolog)] 167 [('Penelope 'Odysseus)] 168 [('Telemachus 'TeX)] 169 [('Telemachus 'calculus)])) 170] 171 172The expression has the expected meaning. Each 173@emph{clause} in the @racket[%rel] establishes a @emph{fact}: 174Odysseus 175knows TeX, Telemachus knows calculus, &c. In general, if we 176apply the predicate to the arguments in any one of its 177clauses, we will get a successful goal. Thus, since 178@racket[%knows] has a clause that reads 179@racket[[('Odysseus 'TeX)]], the goal 180@racket[(%knows 'Odysseus 'TeX)] 181will be true. 182 183We can now get answers for the following types of queries: 184 185@interaction[#:eval racklog-eval 186(%which () 187 (%knows 'Odysseus 'TeX)) 188(%which () 189 (%knows 'Telemachus 'Racket)) 190] 191 192@subsection[#:tag "rules"]{Predicates with Rules} 193 194Predicates can be more complicated than the above bald 195recitation of facts. The predicate clauses can be @emph{rules}, eg, 196 197@racketblock+eval[#:eval racklog-eval 198(define %computer-literate 199 (%rel (person) 200 [(person) 201 (%knows person 'TeX) 202 (%knows person 'Racket)] 203 [(person) 204 (%knows person 'TeX) 205 (%knows person 'Prolog)])) 206] 207 208This defines the predicate 209@racket[%computer-literate] in 210terms of the predicate @racket[%knows]. In effect, a person is 211defined as computer-literate if they know TeX and 212Racket, @emph{or} TeX and Prolog. 213 214Note that this use of 215@racket[%rel] employs a local @emph{logic variable} called @racket[_person]. 216In general, a @racket[%rel]-expression can have a list of symbols 217as its second subform. These name new logic variables that 218can be used within the body of the @racket[%rel]. 219 220The following query can now be answered: 221 222@interaction[#:eval racklog-eval 223(%which () 224 (%computer-literate 'Penelope)) 225] 226 227Since Penelope knows TeX and Prolog, she is computer-literate. 228 229@subsection[#:tag "solving-goals"]{Solving Goals} 230 231The above queries are yes/no questions. Racklog programming 232allows more: We can formulate a goal with @emph{uninstantiated} 233logic variables and then ask the querying process to 234provide, if possible, values for these variables that cause 235the goal to succeed. For instance, the query: 236 237@interaction[#:eval racklog-eval 238(%which (what) 239 (%knows 'Odysseus what)) 240] 241 242asks for an instantiation of the logic variable @racket[_what] 243that satisfies the goal @racket[(%knows 'Odysseus what)]. 244In other words, we are asking, ``What does Odysseus know?'' 245 246Note that this use of @racket[%which] --- like @racket[%rel] 247in the definition of @racket[%computer-literate] --- 248uses a local logic 249variable, @racket[_what]. In general, the second subform of 250@racket[%which] can be a list of local logic variables. The 251@racket[%which]-query returns an answer that is a list of 252bindings, one for each logic variable mentioned in its 253second subform. Thus, 254 255@interaction[#:eval racklog-eval 256(%which (what) 257 (%knows 'Odysseus what)) 258] 259 260But that is not all that wily Odysseus knows. Racklog 261provides a zero-argument procedure (``thunk'') called 262@racket[%more] 263that @emph{retries} the goal in the last 264@racket[%which]-query for a different solution. 265 266@interaction[#:eval racklog-eval 267(%more) 268] 269 270We can keep pumping for more solutions: 271 272@interaction[#:eval racklog-eval 273(%more) 274(%more) 275(%more) 276] 277 278The final @racket[#f] shows that there are no more 279solutions. This is because there are no more clauses in the 280@racket[%knows] predicate that list Odysseus as knowing anything 281else. 282 283@subsection[#:tag "assert"]{Asserting Extra Clauses} 284 285We can add more clauses to a predicate after it has already 286been defined with a @racket[%rel]. Racklog provides the 287@racket[%assert!] form for this purpose. Eg, 288 289@racketblock+eval[#:eval racklog-eval 290(%assert! %knows () 291 [('Odysseus 'archery)]) 292] 293 294tacks on a new clause at the end of the existing clauses 295of the @racket[%knows] 296predicate. Now, the query: 297 298@interaction[#:eval racklog-eval 299(%which (what) 300 (%knows 'Odysseus what)) 301] 302 303gives TeX, Racket, Prolog, and Penelope, as before, but 304a subsequent @racket[(%more)] yields a new result: 305@interaction-eval[#:eval racklog-eval (begin (%more) (%more) (%more))] 306@interaction[#:eval racklog-eval 307(%more) 308] 309 310The Racklog form @racket[%assert-after!] is similar to @racket[%assert!] but 311adds clauses @emph{before} any of the current clauses. 312 313Both @racket[%assert!] and @racket[%assert-after!] assume that the variable 314they are adding to already names a predicate (presumably 315defined using @racket[%rel]). 316In order to allow defining a predicate entirely through 317@racket[%assert!]s, Racklog provides an empty predicate value 318@racket[%empty-rel]. @racket[%empty-rel] takes any number of arguments 319and always fails. A typical use of the 320@racket[%empty-rel] and @racket[%assert!] combination: 321 322@racketblock+eval[#:eval racklog-eval 323(define %parent %empty-rel) 324 325(%assert! %parent () 326 [('Laertes 'Odysseus)]) 327 328(%assert! %parent () 329 [('Odysseus 'Telemachus)] 330 [('Penelope 'Telemachus)]) 331] 332 333(Racklog does not provide a predicate for @emph{retracting} 334assertions, since we can keep track of older versions of 335predicates using conventional Racket features (@racket[let] and @racket[set!]).) 336 337@subsection[#:tag "local-vars"]{Local Variables} 338 339The local logic variables of @racket[%rel]- and 340@racket[%which]-expressions are in reality introduced by the 341Racklog syntactic form called @racket[%let]. (@racket[%rel] and 342@racket[%which] are macros written using @racket[%let].) 343 344@racket[%let] introduces new lexically scoped logic variables. 345Supposing, instead of 346 347@interaction[#:eval racklog-eval 348(%which (what) 349 (%knows 'Odysseus what)) 350] 351 352we had asked 353 354@interaction[#:eval racklog-eval 355(%let (what) 356 (%which () 357 (%knows 'Odysseus what))) 358] 359 360This query, too, succeeds five times, since 361Odysseus knows five things. However, @racket[%which] emits 362bindings only for the local variables that @emph{it} 363introduces. Thus, this query emits @racketresult[()] five times before 364@racket[(%more)] finally returns @racket[#f]. 365 366However, note that, like conventional Racket @racket[let], the body forms 367of @racket[%let] are evaluated in turn with the last form in tail position. 368Thus, to combine multiple goals involving a new logical variable introduced 369by @racket[%let], it is necessary to wrap the body in an @racket[%and] form. 370 371For example: 372 373@interaction[#:eval racklog-eval 374(%which (d) 375 (%let (a p) 376 (%and (%= p (cons 1 2)) 377 (%= p (cons a d))))) 378] 379 380whereas 381 382@interaction[#:eval racklog-eval 383(%which (d) 384 (%let (a p) 385 (%= p (cons 1 2)) (code:comment #,(t "This goal is ignored")) 386 (%= p (cons a d)))) 387] 388 389@section[#:tag "racket-w-logic"]{Using Conventional Racket Expressions in Racklog} 390 391The arguments of Racklog predicates can be any Racket 392objects. In particular, composite structures such as lists, 393vectors, strings, hash tables, etc can be used, as also Racket expressions 394using the full array of Racket's construction and 395decomposition operators. For instance, consider the 396following goal: 397 398@racketblock[ 399(%member x '(1 2 3)) 400] 401 402Here, @racket[%member] is a predicate, @racket[x] is a logic 403variable, and @racket['(1 2 3)] is a structure. Given a suitably 404intuitive definition for @racket[%member], the above goal 405succeeds for @racket[x] = @racketresult[1], @racketresult[2], and @racketresult[3]. 406 407Now to defining predicates like @racket[%member]: 408 409@racketblock[ 410(define %member 411 (%rel (x y xs) 412 [(x (cons x xs))] 413 [(x (cons y xs)) 414 (%member x xs)])) 415] 416 417Ie, @racket[%member] is defined with three local variables: 418@racket[x], @racket[y], @racket[xs]. It has two 419clauses, identifying the two ways of determining membership. 420 421The first clause of @racket[%member] states a fact: For any 422@racket[x], @racket[x] is a member of a list whose head is also @racket[x]. 423 424The second clause of @racket[%member] is a rule: @racket[x] is a 425member of a list if we can show that it is a member of the 426@emph{tail} of that list. In other words, the original 427@racket[%member] goal is translated into a @emph{sub}goal, which is also 428a @racket[%member] goal. 429 430Note that the variable @racket[y] in the definition of 431@racket[%member] occurs only once in the second clause. As such, 432it doesn't need you to make the effort of naming it. (Names 433help only in matching a second occurrence to a first.) Racklog 434lets you use the expression @racket[(_)] to denote an anonymous 435variable. (Ie, @racket[_] is a thunk that generates a fresh 436anonymous variable at each call.) The predicate @racket[%member] can be 437rewritten as 438 439@racketblock[ 440(define %member 441 (%rel (x xs) 442 [(x (cons x (_)))] 443 [(x (cons (_) xs)) 444 (%member x xs)])) 445] 446 447@subsection[#:tag "constructors"]{Constructors} 448 449We can use constructors --- Racket procedures for creating 450structures --- to simulate data types in Racklog. For 451instance, let's define a natural-number data-type where 452@racket[0] denotes zero, and @racket[(succ x)] denotes the natural number 453whose immediate predecessor is @racket[x]. The constructor 454@racket[succ] can 455be defined in Racket as: 456 457@racketblock+eval[#:eval racklog-eval 458(define succ 459 (lambda (x) 460 (vector 'succ x))) 461] 462 463Addition and multiplication can be defined as: 464 465@racketblock+eval[#:eval racklog-eval 466(define %add 467 (%rel (x y z) 468 [(0 y y)] 469 [((succ x) y (succ z)) 470 (%add x y z)])) 471 472(define %times 473 (%rel (x y z z1) 474 [(0 y 0)] 475 [((succ x) y z) 476 (%times x y z1) 477 (%add y z1 z)])) 478] 479 480We can do a lot of arithmetic with this in place. For 481instance, the factorial predicate looks like: 482 483@racketblock+eval[#:eval racklog-eval 484(define %factorial 485 (%rel (x y y1) 486 [(0 (succ 0))] 487 [((succ x) y) 488 (%factorial x y1) 489 (%times (succ x) y1 y)])) 490] 491 492@subsection[#:tag "is"]{@racket[\%is]} 493 494The above is a very inefficient way to do arithmetic, 495especially when the underlying language Racket offers 496excellent arithmetic facilities (including a comprehensive 497number ``tower'' and exact rational arithmetic). One 498problem with using Racket calculations directly in Racklog 499clauses is that the expressions used may contain logic 500variables that need to be dereferenced. Racklog provides 501the predicate @racket[%is] that takes care of this. The goal 502 503@racketblock[ 504(%is _X _E) 505] 506 507unifies @racket[_X] with the value of @racket[_E] considered as a 508Racket expression. @racket[_E] can have logic variables, but 509usually they should at least be bound, as unbound variables 510may not be palatable values to the Racket operators used in 511@racket[_E]. 512 513We can now directly use the numbers of Racket to write a 514more efficient @racket[%factorial] predicate: 515 516@racketblock+eval[#:eval racklog-eval 517(define %factorial 518 (%rel (x y x1 y1) 519 [(0 1)] 520 [(x y) (%is x1 (- x 1)) 521 (%factorial x1 y1) 522 (%is y (* y1 x))])) 523] 524 525A price that this efficiency comes with is that we can 526use @racket[%factorial] only with its first argument already 527instantiated. In many cases, this is not an unreasonable 528constraint. In fact, given this limitation, there is 529nothing to prevent us from using Racket's factorial 530directly: 531 532@racketblock+eval[#:eval racklog-eval 533(define %factorial 534 (%rel (x y) 535 [(x y) 536 (%is y (racket-factorial 537 x))])) 538] 539 540or better yet, ``in-line'' any calls to @racket[%factorial] with 541@racket[%is]-expressions calling @racket[racket-factorial], where the 542latter is defined in the usual manner: 543 544@racketblock+eval[#:eval racklog-eval 545(define racket-factorial 546 (lambda (n) 547 (if (= n 0) 1 548 (* n (racket-factorial 549 (- n 1)))))) 550] 551 552@subsection[#:tag "lexical-scoping"]{Lexical Scoping} 553 554One can use Racket's lexical scoping to enhance predicate 555definition. Here is a list-reversal predicate defined using 556a hidden auxiliary predicate: 557 558@racketblock+eval[#:eval racklog-eval 559(define %reverse 560 (letrec 561 ([revaux 562 (%rel (x y z w) 563 [('() y y)] 564 [((cons x y) z w) 565 (revaux y 566 (cons x z) w)])]) 567 (%rel (x y) 568 [(x y) (revaux x '() y)]))) 569] 570 571@racket[(revaux _X _Y _Z)] uses @racket[_Y] as an accumulator for 572reversing @racket[_X] into @racket[_Z]. (@racket[_Y] starts out as @racketresult[()]. 573Each head of @racket[_X] is @racket[cons]ed on to @racket[_Y]. Finally, when 574@racket[_X] has wound down to @racketresult[()], @racket[_Y] contains the reversed 575list and can be returned as @racket[_Z].) 576 577@racket[revaux] is used purely as a helper predicate for 578@racket[%reverse], and so it can be concealed within a lexical 579contour. We use @racket[letrec] instead of @racket[let] because 580@racket[revaux] is a recursive procedure. 581 582@subsection[#:tag "type-predicates"]{Type Predicates} 583 584Racklog provides a couple of predicates that let the user 585probe the type of objects. 586 587The goal 588@racketblock[ 589(%constant _X) 590] 591 592succeeds if @racket[_X] is an @emph{atomic} object. 593 594The predicate @racket[%compound], the negation of @racket[%constant], 595checks if its argument is not an atomic object. 596 597The above are merely the logic-programming equivalents of 598corresponding Racket predicates. Users can use the 599predicate @racket[%is] and Racket predicates to write more type 600checks in Racklog. Thus, to test if @racket[_X] is a string, the 601following goal could be used: 602 603@racketblock[ 604(%is #t (string? _X)) 605] 606 607User-defined Racket predicates, in addition to primitive Racket 608predicates, can be thus imported. 609 610@section[#:tag "backtracking"]{Backtracking} 611 612It is helpful to go into the following evaluation (@secref{rules}) 613in a 614little detail: 615 616@racketblock+eval[#:eval racklog-eval 617(%which () 618 (%computer-literate 'Penelope)) 619] 620 621The starting goal 622is: 623 624@(define goal litchar) 625@racketblock[ 626G0 = (%computer-literate Penelope) 627] 628 629(I've taken out the quote because @racketresult[Penelope] is the result 630of evaluating @racket['Penelope].) 631 632Racklog tries to match this with the head of the first 633clause of @racket[%computer-literate]. It succeeds, generating a 634binding @racket[[person . Penelope]]. 635 636But this means it now has two new goals --- @emph{subgoals} 637--- to solve. These are the goals in the body of the 638matching clause, with the logic variables substituted by 639their instantiations: 640 641@racketblock[ 642G1 = (%knows Penelope TeX) 643G2 = (%knows Penelope Racket) 644] 645 646For @goal{G1}, Racklog attempts matches with the clauses of 647@racket[%knows], and succeeds at the fifth try. (There are no 648subgoals in this case, because the bodies of these ``fact'' 649clauses are empty, in contrast to the ``rule'' clauses of 650@racket[%computer-literate].) 651Racklog then tries to solve @goal{G2} against the clauses of 652@racket[%knows], and since there is no clause stating that 653Penelope knows Racket, it fails. 654 655All is not lost though. Racklog now @emph{backtracks} to the 656goal that was solved just before, viz., @goal{G1}. It 657@emph{retries} @goal{G1}, ie, tries to solve it in a 658different way. 659This entails searching down the previously unconsidered 660@racket[%knows] 661clauses for @goal{G1}, ie, the sixth onwards. Obviously, 662Racklog fails again, because the fact that Penelope knows 663TeX occurs only once. 664 665Racklog now backtracks to the goal before @goal{G1}, ie, 666@goal{G0}. We abandon the current successful match with the 667first clause-head of @racket[%computer-literate], and try the 668next clause-head. Racklog succeeds, again producing a binding 669@racket[[person . Penelope]], and two new subgoals: 670 671@racketblock[ 672G3 = (%knows Penelope TeX) 673G4 = (%knows Penelope Prolog) 674] 675 676It is now easy to trace that Racklog finds both @goal{G3} and @goal{G4} to be 677true. Since both of @goal{G0}'s subgoals are true, @goal{G0} is 678itself considered true. And this is what Racklog reports. The 679interested reader can now trace why the 680following query has a different denouement: 681 682@interaction[#:eval racklog-eval 683(%which () 684 (%computer-literate 'Telemachus)) 685] 686 687@section[#:tag "unification"]{Unification} 688 689When we say that a goal matches with a clause-head, we mean 690that the predicate and argument positions line up. Before 691making this comparison, Racklog dereferences all already 692bound logic variables. The resulting structures are then 693compared to see if they are recursively identical. Thus, 694@racket[1] unifies with @racket[1], and @racket[(list 1 2)] with @racket['(1 2)]; but @racket[1] and 695@racket[2] do not unify, and neither do @racket['(1 2)] and @racket['(1 3)]. 696 697In general, there could be quite a few uninstantiated logic 698variables in the compared objects. Unification will then 699endeavor to find the most natural way of binding these 700variables so that we arrive at structurally identical 701objects. Thus, @racket[(list _x 1)], where @racket[_x] is an unbound logic 702variable, unifies with @racket['(0 1)], producing the 703binding 704@racket[[_x 0]]. 705 706Unification is thus a goal, and Racklog makes the unification predicate 707available to the user as @racket[%=]. Eg, 708 709@interaction[#:eval racklog-eval 710(%which (x) 711 (%= (list x 1) '(0 1))) 712] 713 714Racklog also provides the predicate @racket[%/=], the @emph{negation} of 715@racket[%=]. @racket[(%/= _X _Y)] succeeds if and only if @racket[_X] does 716@emph{not} unify with @racket[_Y]. 717 718Unification goals constitute the basic subgoals that all 719Racklog goals devolve to. A goal succeeds because all the 720eventual unification subgoals that it decomposes to in at 721least one of its subgoal-branching succeeded. It fails 722because every possible subgoal-branching was thwarted by the 723failure of a crucial unification subgoal. 724 725Going back to the example in @secref{backtracking}, the goal 726@racket[(%computer-literate 'Penelope)] succeeds because 727(a) it unified with 728@racket[(%computer-literate person)]; and then (b) with the binding 729@racket[[person . Penelope]] in place, @racket[(%knows person 'TeX)] 730unified with @racket[(%knows 'Penelope 'TeX)] and 731@racket[(%knows person 'Prolog)] unified with @racket[(%knows 'Penelope 'Prolog)]. 732 733In contrast, the goal @racket[(%computer-literate 'Telemachus)] 734fails because, with @racket[[person . Telemachus]], 735the subgoals @racket[(%knows person 'Racket)] and 736@racket[(%knows person 'Prolog)] have no facts they can 737unify with. 738 739@subsection{The Occurs Check} 740 741A robust unification algorithm uses the @deftech{occurs check}, which ensures that a logic variable 742isn't bound to a structure that contains itself. 743Not performing the check can cause the unification 744to go into an infinite loop in some cases. On the 745other hand, performing the occurs check greatly 746increases the time taken by unification, even in cases 747that wouldn't require the check. 748 749Racklog uses the global parameter 750@racket[use-occurs-check?] to decide whether to 751use the occurs check. By default, this variable is 752@racket[#f], ie, Racklog disables the occurs check. To 753enable the check, 754 755@racketblock[ 756(use-occurs-check? #t) 757] 758 759@section[#:tag "and-or"]{Conjunctions and Disjunctions} 760 761Goals may be combined using the forms @racket[%and] 762and @racket[%or] 763to form compound goals. (For @racket[%not], see @secref{not}.) 764Eg, 765 766@interaction[#:eval racklog-eval 767(%which (x) 768 (%and (%member x '(1 2 3)) 769 (%< x 3))) 770] 771 772gives solutions for @racket[_x] that satisfy both the 773argument goals of the @racket[%and]. 774Ie, @racket[_x] should both be a member of @racket['(1 2 3)] 775@emph{and} be less than @racket[3]. Typing @racket[(%more)] gives another solution: 776 777@interaction[#:eval racklog-eval 778(%more) 779(%more) 780] 781 782There are no more solutions, because @racket[[x 3]] satisfies 783the first but not the second goal. 784 785Similarly, the query 786 787@interaction[#:eval racklog-eval 788(%which (x) 789 (%or (%member x '(1 2 3)) 790 (%member x '(3 4 5)))) 791] 792 793lists all @racket[_x] that are members of either list. 794 795@interaction[#:eval racklog-eval 796(%more) 797(%more) 798(%more) 799(%more) 800(%more) 801] 802 803(Yes, @racket[([x 3])] is listed twice.) 804 805We can rewrite the predicate @racket[%computer-literate] 806from @secref{rules} using @racket[%and] and @racket[%or]: 807 808@racketblock+eval[#:eval racklog-eval 809(define %computer-literate 810 (%rel (person) 811 [(person) 812 (%or 813 (%and (%knows person 814 'TeX) 815 (%knows person 816 'Racket)) 817 (%and (%knows person 818 'TeX) 819 (%knows person 820 'Prolog)))])) 821] 822 823Or, more succinctly: 824 825@racketblock+eval[#:eval racklog-eval 826(define %computer-literate 827 (%rel (person) 828 [(person) 829 (%and (%knows person 830 'TeX) 831 (%or (%knows person 832 'Racket) 833 (%knows person 834 'Prolog)))])) 835] 836 837We can even dispense with the @racket[%rel] altogether: 838 839@racketblock+eval[#:eval racklog-eval 840(define %computer-literate 841 (lambda (person) 842 (%and (%knows person 843 'TeX) 844 (%or (%knows person 845 'Racket) 846 (%knows person 847 'Prolog))))) 848] 849 850This last looks like a conventional Racket predicate 851definition, and is arguably 852the most readable format for a Racket programmer. 853 854@section[#:tag "lv-manip"]{Manipulating Racklog Variables} 855 856Racklog provides special predicates for probing logic 857variables, without risking their getting bound. 858 859@subsection[#:tag "var"]{Checking for Variables} 860 861The goal 862 863@racketblock[ 864(%== _X _Y) 865] 866 867succeeds if @racket[_X] and @racket[_Y] are @emph{identical} objects. This 868is not quite the unification predicate @racket[%=], for @racket[%==] 869doesn't touch unbound objects the way @racket[%=] does. Eg, 870@racket[%==] will not equate an unbound logic variable with a 871bound one, nor will it equate two unbound logic variables 872unless they are the @emph{same} variable. 873 874The predicate @racket[%/==] is the negation of @racket[%==]. 875 876The goal 877 878@racketblock[ 879(%var _X) 880] 881 882succeeds if @racket[_X] isn't completely bound --- ie, it has at 883least one unbound logic variable in its innards. 884 885The predicate @racket[%nonvar] is the negation of @racket[%var]. 886 887@subsection[#:tag "freeze"]{Preserving Variables} 888 889Racklog lets the user protect a term with variables from 890unification by allowing that term to be treated as a 891(completely) bound object. The predicates provided for this 892purpose are 893@racket[%freeze], 894@racket[%melt], @racket[%melt-new], and @racket[%copy]. 895 896The goal 897 898@racketblock[ 899(%freeze _S _F) 900] 901 902unifies @racket[_F] to the frozen version of @racket[_S]. Any lack 903of bindings in @racket[_S] are preserved no matter how much you 904toss @racket[_F] about. 905 906The goal 907 908@racketblock[ 909(%melt _F _S) 910] 911 912retrieves the object frozen in @racket[_F] into @racket[_S]. 913 914The goal 915 916@racketblock[ 917(%melt-new _F _S) 918] 919 920is similar to @racket[%melt], 921except that when @racket[_S] is made, the unbound variables in 922@racket[_F] are replaced by brand-new unbound variables. 923 924The goal 925 926@racketblock[ 927(%copy _S _C) 928] 929 930is an abbreviation for @racket[(%freeze _S _F)] 931followed by @racket[(%melt-new _F _C)]. 932 933@section[#:tag "cut"]{The Cut (@racket[!])} 934 935The cut (called @racket[!]) is a special goal that is used to 936prune backtracking options. Like the @racket[%true] goal, the 937cut goal too succeeds, when accosted by the Racklog 938subgoaling engine. However, when a further subgoal down the 939line fails, and time comes to retry the cut goal, Racklog 940will refuse to try alternate clauses for the predicate in 941whose definition the cut occurs. In other words, the cut 942causes Racklog to commit to all the decisions made from the 943time that the predicate was selected to match a subgoal till 944the time the cut was satisfied. 945 946For example, consider again the @racket[%factorial] 947predicate, as defined in @secref{is}: 948 949@racketblock+eval[#:eval racklog-eval 950(define %factorial 951 (%rel (x y x1 y1) 952 [(0 1)] 953 [(x y) (%is x1 (- x 1)) 954 (%factorial x1 y1) 955 (%is y (* y1 x))])) 956] 957 958Clearly, 959 960@interaction[#:eval racklog-eval 961(%which () 962 (%factorial 0 1)) 963(%which (n) 964 (%factorial 0 n)) 965] 966 967But what if we asked for @racket[(%more)] for either query? 968Backtracking will try 969the second clause of @racket[%factorial], and sure enough the 970clause-head unifies, producing binding @racket[[x . 0]]. 971We now get three subgoals. Solving the first, we get @racket[[x1 . -1]], and then we have to solve @racket[(%factorial -1 y1)]. It 972is easy to see there is no end to this, as we fruitlessly 973try to get the factorials of numbers that get more and more 974negative. 975 976If we placed a cut at the first clause: 977 978@racketblock[ 979... 980[(0 1) !] 981... 982] 983 984the attempt to find more solutions for @racket[(%factorial 0 1)] is nipped in the bud. 985 986Calling @racket[%factorial] with a @emph{negative} number would still cause an 987infinite loop. To take care of that problem as well, we 988use another cut: 989 990@racketblock+eval[#:eval racklog-eval 991(define %factorial 992 (%rel (x y x1 y1) 993 [(0 1) !] 994 [(x y) (%< x 0) ! %fail] 995 [(x y) (%is x1 (- x 1)) 996 (%factorial x1 y1) 997 (%is y (* y1 x))])) 998] 999 1000@interaction[#:eval racklog-eval 1001(%which () 1002 (%factorial 0 1)) 1003(%more) 1004(%which () 1005 (%factorial -1 1)) 1006] 1007 1008Using @emph{raw} cuts as above can get very confusing. For this 1009reason, it is advisable to use it hidden away in 1010well-understood abstractions. Two such common abstractions 1011are the conditional and negation. 1012 1013@subsection[#:tag "if-then-else"]{Conditional Goals} 1014 1015An ``if ... then ... else ...'' predicate can be defined 1016as follows 1017 1018@racketblock+eval[#:eval racklog-eval 1019(define %if-then-else 1020 (%rel (p q r) 1021 [(p q r) p ! q] 1022 [(p q r) r])) 1023] 1024 1025(Note that for the first time we have predicate arguments that 1026are themselves goals.) 1027 1028Consider the goal 1029 1030@racketblock[ 1031G0 = (%if-then-else Gbool Gthen Gelse) 1032] 1033 1034We first unify @goal{G0} with the first clause-head, 1035giving 1036@racket[[p . Gbool]], @racket[[q . Gthen]], @racket[[r . Gelse]]. @goal{Gbool} can 1037now either succeed or fail. 1038 1039Case 1: If @goal{Gbool} fails, backtracking will cause the 1040@goal{G0} to unify with the second clause-head. @racket[r] is bound 1041to @goal{Gelse}, and so @goal{Gelse} is tried, as expected. 1042 1043Case 2: If @goal{Gbool} succeeds, the cut commits to this 1044clause of the @racket[%if-then-else]. We now try @goal{Gthen}. If 1045@goal{Gthen} should now fail --- or even if we simply retry for 1046more solutions --- we are guaranteed that the second 1047clause-head will not be tried. If it were not for the cut, 1048@goal{G0} would attempt to unify with the second clause-head, which will 1049of course succeed, and @goal{Gelse} @emph{will} be tried. 1050 1051@subsection[#:tag "not"]{Negation as Failure} 1052 1053Another common abstraction using the cut is @emph{negation}. 1054The negation of goal @goal{G} is defined as @racket[(%not G)], where 1055the predicate @racket[%not] is defined as follows: 1056 1057@racketblock+eval[#:eval racklog-eval 1058(define %not 1059 (%rel (g) 1060 [(g) g ! %fail] 1061 [(g) %true])) 1062] 1063 1064Thus, @racket[g]'s negation is deemed a failure if @racket[g] 1065succeeds, and a success if @racket[g] fails. This is of course 1066confusing goal failure with falsity. In some cases, this 1067view of negation is actually helpful. 1068 1069@section[#:tag "set-of"]{Set Predicates} 1070 1071The goal 1072 1073@racketblock[ 1074(%bag-of _X _G _Bag) 1075] 1076 1077unifies with @racket[_Bag] the list of all instantiations of 1078@racket[_X] for which @racket[_G] succeeds. Thus, the following query 1079asks for all the things known --- ie, the collection of things 1080such that someone knows them: 1081 1082@interaction[#:eval racklog-eval 1083(%which (things-known) 1084 (%let (someone x) 1085 (%bag-of x (%knows someone x) 1086 things-known))) 1087] 1088 1089This is the only solution for this goal: 1090 1091@interaction[#:eval racklog-eval 1092(%more) 1093] 1094 1095Note that some things --- eg, TeX --- are enumerated 1096more than once. This is because more than one person knows 1097TeX. To remove duplicates, use the predicate 1098@racket[%set-of] 1099instead of @racket[%bag-of]: 1100 1101@interaction[#:eval racklog-eval 1102(%which (things-known) 1103 (%let (someone x) 1104 (%set-of x (%knows someone x) 1105 things-known))) 1106] 1107 1108In the above, the free variable @racket[_someone] in the 1109@racket[%knows]-goal is used as if it 1110were existentially quantified. In contrast, Prolog's 1111versions of 1112@racket[%bag-of] and @racket[%set-of] fix it for each solution of the 1113set-predicate goal. We can do it too with some additional 1114syntax that identifies the free variable. 1115Eg, 1116 1117@interaction[#:eval racklog-eval 1118(%which (someone things-known) 1119 (%let (x) 1120 (%bag-of x 1121 (%free-vars (someone) 1122 (%knows someone x)) 1123 things-known))) 1124] 1125 1126The bag of things known by @emph{one} someone is 1127returned. That someone is Odysseus. The query can be 1128retried for more solutions, each listing the things known by 1129a different someone: 1130 1131@interaction[#:eval racklog-eval 1132(%more) 1133(%more) 1134(%more) 1135(%more) 1136] 1137 1138Racklog also provides two variants of these set predicates, 1139viz., @racket[%bag-of-1] and @racket[%set-of-1]. These act like @racket[%bag-of] 1140and @racket[%set-of] but fail if the resulting bag or set is empty. 1141 1142@section[#:tag "meta"]{Higher-order Predicates} 1143 1144Logic variables which contain predicates may be used as the operator in 1145predicate expressions: 1146 1147@interaction[#:eval racklog-eval 1148(%which () 1149 (%let (p) 1150 (%and (%= p %knows) 1151 (p 'Odysseus 'TeX)))) 1152] 1153 1154First the logic variable @racket[p] is unified with the predicate @racket[%knows]. 1155In the expression 1156 1157@racketblock[(p 'Odysseus 'TeX)] 1158 1159@racket[p] is replaced by its value @racket[%knows] to become 1160 1161@racketblock[(%knows 'Odysseus 'TeX)] 1162 1163which succeeds. 1164 1165This allows us to reason about predicates themselves. For example: 1166 1167@interaction[#:eval racklog-eval 1168(%which (p) 1169 (%member p (list %knows %parent)) 1170 (p 'Odysseus 'Penelope)) 1171(%more) 1172] 1173 1174Here we test which of the predicates @racket[%knows] and 1175@racket[%parent] succeed when given the arguments @racket['Odysseus] 1176and @racket['Penelope]. 1177 1178The goal @racket[(%knows 'Odysseus 'Penelope)] succeeds, but 1179@racket[(%parent 'Odysseus 'Penelope)] fails. Hence the only possible value for 1180@racket[p] is @racket[%knows]. 1181 1182However, logic variables used as a predicate must be instantiated. Since the set 1183of defined predicates is not enumerable by Racklog, an unbound query will fail: 1184 1185@interaction[#:eval racklog-eval 1186(%which (p) (p 'Odysseus 'Penelope)) 1187] 1188 1189We can define a higher-order predicate which tests for unary predicates that 1190succeed with @racket['Odysseus] as their argument: 1191 1192@racketblock+eval[#:eval racklog-eval 1193(define (%odyssean p) 1194 (p 'Odysseus)) 1195] 1196 1197For example: 1198 1199@interaction[#:eval racklog-eval 1200(%which () (%odyssean %computer-literate)) 1201] 1202 1203This succeeds because @racket[(%computer-literate 'Odysseus)] succeeds. 1204 1205@interaction[#:eval racklog-eval 1206(%which () (%odyssean %compound)) 1207] 1208 1209This fails because @racket[(%compound 'Odysseus)] fails. 1210 1211This also works if the predicate argument is a logic variable: 1212 1213@interaction[#:eval racklog-eval 1214(%which (p) 1215 (%member p (list %computer-literate %compound)) 1216 (%odyssean p)) 1217] 1218 1219Compare this with the example above. 1220 1221Racklog also provides two predicates for defining relations involving arbitrary 1222predicates. 1223 1224@subsection{@racket[%apply]} 1225 1226The @racket[%apply] predicate is analogous to convential Racket @racket[apply]. 1227 1228The goal 1229 1230@racketblock[ 1231(%apply P L) 1232] 1233 1234succeeds if @racket[L] is a list with elements @racket[E], ..., and if 1235@racket[P] is a predicate that accepts as many arguments as there are 1236@racket[E]s, and if the goal @racket[(P E ...)] succeeds. For example: 1237 1238@interaction[#:eval racklog-eval 1239(%which () (%apply %knows '(Odysseus TeX))) 1240] 1241 1242In this case, the goal 1243 1244@racketblock[ 1245(%apply %knows '(Odysseus TeX)) 1246] 1247 1248is equivalent to 1249 1250@racketblock[ 1251(%knows 'Odysseus 'TeX) 1252] 1253 1254The list argument to @racket[%apply] must be sufficiently instantiated to 1255determine its length. The following goals succeed: 1256 1257@interaction[#:eval racklog-eval 1258(%which () (%apply %knows (list 'Odysseus 'TeX))) 1259(%which (X) (%apply %knows (list X 'TeX))) 1260] 1261 1262but it is not possible to use @racket[%apply] with a list of unknown length: 1263 1264@interaction[#:eval racklog-eval 1265(%which (X Y) (%apply %knows (cons X Y))) 1266] 1267 1268@subsection{@racket[%andmap]} 1269 1270The @racket[%andmap] predicate is analogous to convential Racket @racket[andmap]. 1271 1272The goal 1273 1274@racketblock[ 1275(%andmap P L ...+) 1276] 1277 1278succeeds if all the @racket[L]s are lists of equal length, and the goal 1279@racket[(P E ...)] succeeds for each set of elements @racket[E], ... 1280of the @racket[L]s. For example: 1281 1282@interaction[#:eval racklog-eval 1283(%which () (%andmap %knows '(Odysseus Penelope) '(TeX Prolog))) 1284] 1285 1286In this case, the goal 1287 1288@racketblock[ 1289(%andmap %knows '(Odysseus Penelope) '(TeX Prolog)) 1290] 1291 1292is equivalent to 1293 1294@racketblock[ 1295(%and (%knows 'Odysseus 'TeX) 1296 (%knows 'Penelope 'Prolog)) 1297] 1298 1299@section{Racklog Module Language} 1300 1301@defmodulelang[@racketmodname[racklog] #:module-paths (racklog/lang/lang)] 1302 1303This module language accepts the syntax of Datalog (except clauses need not be safe) and compiles each predicate to a relation. 1304 1305The accepted syntax is available in the @secref[#:doc '(lib "datalog/scribblings/datalog.scrbl")]{datalog} documentation. 1306 1307@section[#:tag "glossary"]{Glossary of Racklog Primitives} 1308 1309@(define-syntax (defpred stx) 1310 (syntax-case stx () 1311 [(_ (id arg ...) pre ...) 1312 (syntax/loc stx 1313 (defproc (id arg ...) 1314 goal/c 1315 pre ...))])) 1316@(define-syntax-rule (defgoal id pre ...) 1317 (defthing id goal/c pre ...)) 1318 1319@subsection{Racket Predicates} 1320 1321@defproc[(logic-var? [x any/c]) boolean?]{Identifies a logic variable.} 1322 1323@defproc[(atomic-struct? [x any/c]) boolean?]{ 1324 Identifies structures that the @racket[(current-inspector)] cannot inspect.} 1325 1326@defproc[(atom? [x any/c]) boolean?]{ 1327 Identifies atomic values that may appear in Racklog programs. Equivalent to 1328 the contract @racket[(or/c boolean? number? string? bytes? char? symbol? 1329 regexp? pregexp? byte-regexp? byte-pregexp? keyword? null? procedure? void? 1330 set? atomic-struct?)].} 1331 1332@defproc[(compound-struct? [x any/c]) boolean?]{ 1333 Identifies structures that the @racket[(current-inspector)] can inspect.} 1334 1335@defproc[(compound? [x any/c]) boolean?]{ 1336 Identifies compound values that may appear in Racklog programs. Equivalent to 1337 the contract 1338 @racket[(or/c pair? vector? mpair? box? hash? compound-struct?)].} 1339 1340@defproc[(unifiable? [x any/c]) boolean?]{ 1341 Identifies values that may appear in Racklog programs. Essentially either an 1342 @racket[atom?], @racket[logic-var?], or @racket[compound?] that contains 1343 @racket[unifiable?]s.} 1344 1345@defproc[(answer-value? [x any/c]) boolean?]{ 1346 Identifies values that may appear in @racket[answer?]. Essentially 1347 @racket[unifiable?]s that do not contain @racket[logic-var?]s.} 1348 1349@defproc[(answer? [x any/c]) boolean?]{ 1350 Identifies answers returned by @racket[%more] and @racket[%which]. Equivalent 1351 to the contract 1352 @racket[(or/c false/c (listof (cons/c symbol? answer-value?)))].} 1353 1354@defthing[goal/c contract?]{A contract for goals.} 1355 1356@subsection{User Interface} 1357 1358@defform[(%which (V ...) G ...) 1359 #:contracts ([V identifier?] 1360 [G goal/c])]{ 1361Returns an @racket[answer?] 1362of the variables @racket[V], ..., that satisfies all of @racket[G], 1363... If @racket[G], ..., cannot be satisfied, returns @racket[#f]. 1364Calling the thunk @racket[%more] produces more 1365instantiations, if available.} 1366 1367@defproc[(%more) answer?]{ 1368The thunk @racket[%more] produces more instantiations of the 1369variables in the most recent @racket[%which]-form that satisfy the 1370goals in that @racket[%which]-form. If no more solutions can 1371be found, @racket[%more] returns @racket[#f].} 1372 1373@defform[(%find-all (V ...) G ...) 1374 #:contracts ([V identifier?] 1375 [G goal/c])]{ 1376Like @racket[(list (%which (V ...) G ...) (%more) ...)] with as many @racket[(%more)]s as there are answers. (This will not terminate if there are an infinite number of answers.) 1377} 1378 1379@subsection{Relations} 1380 1381@defform/subs[(%rel (V ...) clause ...) 1382 ([clause [(E ...) G ...]]) 1383 #:contracts ([V identifier?] 1384 [E expression?] 1385 [G goal/c])]{ 1386Returns a predicate function. Each clause @racket[C] signifies that 1387the goal created by applying the predicate object to anything that 1388matches @racket[(E ...)] is deemed to succeed if all the goals 1389@racket[G], ..., can, in their turn, be shown to succeed. The 1390variables @racket[V], ..., are local logic variables for 1391@racket[clause], ....} 1392 1393@defpred[(%empty-rel [E unifiable?] ...)]{ 1394The goal @racket[(%empty-rel E ...)] always fails. The @emph{value} 1395@racket[%empty-rel] is used as a starting value for predicates 1396that can later be enhanced with @racket[%assert!] and @racket[%assert-after!].} 1397 1398@defform[(%assert! Pname (V ...) clause ...) 1399 #:contracts ([Pname identifier?] 1400 [V identifier?])]{ 1401Adds the clauses 1402@racket[clauses], ..., to the @emph{end} of the predicate that is the value of 1403the Racket variable @racket[Pname]. The variables @racket[V], ..., are 1404local logic variables for @racket[clause], ....} 1405 1406@defform[(%assert-after! Pname (V ...) clause ...) 1407 #:contracts ([Pname identifier?] 1408 [V identifier?])]{ 1409Like @racket[%assert!], but adds the new clauses to the @emph{front} 1410of the existing predicate.} 1411 1412@subsection{Racklog Variables} 1413 1414@defproc[(_) logic-var?]{ 1415A thunk that produces a new logic variable. Can be 1416used in situations where we want a logic variable but 1417don't want to name it. (@racket[%let], in contrast, introduces new 1418lexical names for the logic variables it creates.) 1419} 1420 1421@defform[(%let (V ...) expr ...) 1422 #:contracts ([V identifier?])]{ 1423Introduces @racket[V], ..., as 1424lexically scoped logic variables to be used in @racket[expr], ...} 1425 1426@subsection{Cut} 1427 1428@defform[(%cut-delimiter . any)]{ 1429Introduces a cut point. See @secref{cut}.} 1430 1431@defidform[!]{ 1432The cut goal, see @secref{cut}. 1433 1434May only be used syntactically inside @racket[%cut-delimiter] or @racket[%rel].} 1435 1436@subsection{Racklog Operators} 1437 1438@defgoal[%fail]{ 1439The goal @racket[%fail] always fails.} 1440 1441@defgoal[%true]{ 1442The goal @racket[%true] succeeds. Fails on retry.} 1443 1444@defpred[(%repeat)]{ 1445The goal @racket[(%repeat)] always succeeds (even on retries). 1446Useful for failure-driven loops.} 1447 1448@defform[(%and G ...) #:contracts ([G goal/c])]{ 1449The goal @racket[(%and G ...)] succeeds if all the goals 1450@racket[G], ..., succeed.} 1451 1452@defform[(%or G ...) #:contracts ([G goal/c])]{ 1453The goal @racket[(%or G ...)] succeeds if one of @racket[G], ..., tried 1454in that order, succeeds.} 1455 1456@defpred[(%not [G goal/c])]{ 1457The goal @racket[(%not G)] succeeds if @racket[G] fails.} 1458 1459@defpred[(%if-then-else [G1 goal/c] [G2 goal/c] [G3 goal/c])]{ 1460The goal @racket[(%if-then-else G1 G2 G3)] tries @racket[G1] first: if it 1461succeeds, tries @racket[G2]; if not, tries @racket[G3].} 1462 1463@subsection{Unification} 1464 1465@defpred[(%= [E1 unifiable?] [E2 unifiable?])]{ 1466The goal @racket[(%= E1 E2)] succeeds if @racket[E1] can be unified with 1467@racket[E2]. Any resulting bindings for logic variables are kept.} 1468 1469@defpred[(%/= [E1 unifiable?] [E2 unifiable?])]{@racket[%/=] is the negation of @racket[%=]. 1470The goal @racket[(%/= E1 E2)] succeeds if @racket[E1] can not be unified 1471with @racket[E2].} 1472 1473@defpred[(%== [E1 unifiable?] [E2 unifiable?])]{ 1474The goal @racket[(%== E1 E2)] succeeds if @racket[E1] is @emph{identical} 1475to @racket[E2]. They should be structurally equal. If containing 1476logic variables, they should have the same variables in the 1477same position. Unlike a @racket[%=]-call, this goal will not bind 1478any logic variables.} 1479 1480@defpred[(%/== [E1 unifiable?] [E2 unifiable?])]{ 1481@racket[%/==] is the negation of @racket[%==]. 1482The goal @racket[(%/== E1 E2)] succeeds if @racket[E1] and @racket[E2] are not 1483identical.} 1484 1485@defform[(%is E1 E2)]{ 1486The goal @racket[(%is E1 E2)] unifies with @racket[E1] the result of 1487evaluating @racket[E2] as a Racket expression. @racket[E2] may contain 1488logic variables, which are dereferenced automatically. 1489Fails if @racket[E2] contains unbound logic variables.} 1490 1491@defparam[use-occurs-check? on? boolean?]{ 1492If this is false (the default), 1493Racklog's unification will not use the occurs check. 1494If it is true, the occurs check is enabled.} 1495 1496@subsection{Numeric Predicates} 1497 1498@defpred[(%< [E1 unifiable?] [E2 unifiable?])]{ 1499The goal @racket[(%< E1 E2)] succeeds if @racket[E1] and @racket[E2] are bound to 1500numbers and @racket[E1] is less than @racket[E2].} 1501 1502@defpred[(%<= [E1 unifiable?] [E2 unifiable?])]{ 1503The goal @racket[(%<= E1 E2)] succeeds if @racket[E1] and @racket[E2] are bound to 1504numbers and @racket[E1] is less than or equal to @racket[E2].} 1505 1506@defpred[(%=/= [E1 unifiable?] [E2 unifiable?])]{ 1507The goal @racket[(%=/= E1 E2)] succeeds if @racket[E1] and @racket[E2] are bound to 1508numbers and @racket[E1] is not equal to @racket[E2].} 1509 1510@defpred[(%=:= [E1 unifiable?] [E2 unifiable?])]{ 1511The goal @racket[(%=:= E1 E2)] succeeds if @racket[E1] and @racket[E2] are bound to 1512numbers and @racket[E1] is equal to @racket[E2].} 1513 1514@defpred[(%> [E1 unifiable?] [E2 unifiable?])]{ 1515The goal @racket[(%> E1 E2)] succeeds if @racket[E1] and @racket[E2] are bound to 1516numbers and @racket[E1] is greater than @racket[E2].} 1517 1518@defpred[(%>= [E1 unifiable?] [E2 unifiable?])]{ 1519The goal @racket[(%>= E1 E2)] succeeds if @racket[E1] and @racket[E2] are bound to 1520numbers and @racket[E1] is greater than or equal to @racket[E2].} 1521 1522@subsection{List Predicates} 1523 1524@defpred[(%append [E1 unifiable?] [E2 unifiable?] [E3 unifiable?])]{ 1525The goal @racket[(%append E1 E2 E3)] succeeds if @racket[E3] is unifiable 1526with the list obtained by appending @racket[E1] and @racket[E2].} 1527 1528@defpred[(%member [E1 unifiable?] [E2 unifiable?])]{ 1529The goal @racket[(%member E1 E2)] succeeds if @racket[E1] is a member 1530of the list in @racket[E2].} 1531 1532@subsection{Set Predicates} 1533 1534@defpred[(%set-of [E1 unifiable?] [G goal/c] [E2 unifiable?])]{ 1535The goal @racket[(%set-of E1 G E2)] unifies with @racket[E2] the @emph{set} 1536of all the 1537instantiations of @racket[E1] for which goal @racket[G] succeeds.} 1538 1539@defpred[(%set-of-1 [E1 unifiable?] [G goal/c] [E2 unifiable?])]{ 1540Similar to @racket[%set-of], but fails if the set is empty.} 1541 1542@defpred[(%bag-of [E1 unifiable?] [G goal/c] [E2 unifiable?])]{ 1543The goal @racket[(%bag-of E1 G E2)] unifies with @racket[E2] the @emph{bag} 1544(multiset) 1545of all the 1546instantiations of @racket[E1] for which goal @racket[G] succeeds.} 1547 1548@defpred[(%bag-of-1 [E1 unifiable?] [G goal/c] [E2 unifiable?])]{ 1549Similar to @racket[%bag-of], but fails if the bag is empty.} 1550 1551@defform[(%free-vars (V ...) G) 1552 #:contracts ([V identifier?] 1553 [G goal/c])]{ 1554Identifies 1555the occurrences of the variables @racket[V], ..., in goal 1556@racket[G] as free. It is used to avoid existential quantification 1557in calls to set predicates (@racket[%bag-of], @racket[%set-of], &c.).} 1558 1559@subsection{Racklog Predicates} 1560 1561@defpred[(%compound [E unifiable?])]{ 1562The goal @racket[(%compound E)] succeeds if @racket[E] is a compound 1563value.} 1564 1565@defpred[(%constant [E unifiable?])]{ 1566The goal @racket[(%constant E)] succeeds if @racket[E] is an atomic 1567value.} 1568 1569@defpred[(%var [E unifiable?])]{ 1570The goal @racket[(%var E)] succeeds if @racket[E] is not completely 1571instantiated, ie, it has at least one unbound variable in 1572it.} 1573 1574@defpred[(%nonvar [E unifiable?])]{ 1575@racket[%nonvar] is the negation of @racket[%var]. 1576The goal @racket[(%nonvar E)] succeeds if @racket[E] is completely 1577instantiated, ie, it has no unbound variable in it.} 1578 1579@subsection{Higher-order Predicates} 1580 1581@defpred[(%apply [P unifiable?] [L unifiable?])]{ 1582The goal @racket[(%apply P L)] succeeds if @racket[L] is a list 1583with elements @racket[E], ..., and if @racket[P] is a predicate 1584accepting as many arguments as there are @racket[E]s, and if the goal 1585@racket[(P E ...)] succeeds. 1586 1587The goal will fail if @racket[L] is not sufficiently instantiated 1588to determine its length. 1589 1590For example, the goal 1591@racketblock[(%apply %= (list 1 X))] 1592is equivalent to 1593@racketblock[(%= 1 X)] 1594which succeeds if @racket[X] can be unified with @racket[1]. 1595} 1596 1597@defpred[(%andmap [P unifiable?] [L unifiable?] ...+)]{ 1598The goal @racket[(%andmap P L ...)] succeeds if all the values 1599@racket[L], ..., are lists of equal length, and if the goal 1600@racket[(P E ...)] succeeds for each set of values @racket[E], ..., 1601taken in turn from each of the lists @racket[L], ... 1602 1603As an example, in particular the goal 1604@racket[(%andmap %<= '(1 2 3) '(4 5 6))] is equivalent to 1605@racketblock[ 1606(%and (%<= 1 4) 1607 (%<= 2 5) 1608 (%<= 3 6)) 1609] 1610} 1611 1612@subsection{Racklog Variable Manipulation} 1613 1614@defpred[(%freeze [S unifiable?] [F unifiable?])]{ 1615The goal @racket[(%freeze S F)] unifies with @racket[F] a new frozen 1616version of the structure in @racket[S]. Freezing implies that all 1617the unbound variables are preserved. @racket[F] can henceforth be 1618used as @emph{bound} object with no fear of its variables 1619getting bound by unification.} 1620 1621@defpred[(%melt [F unifiable?] [S unifiable?])]{ 1622The goal @racket[(%melt F S)] unifies @racket[S] with the thawed 1623(original) form of the frozen structure in @racket[F].} 1624 1625@defpred[(%melt-new [F unifiable?] [S unifiable?])]{ 1626The goal @racket[(%melt-new F S)] unifies @racket[S] with a thawed 1627@emph{copy} of the frozen structure in @racket[F]. This means 1628new logic variables are used for unbound logic variables in 1629@racket[F].} 1630 1631@defpred[(%copy [F unifiable?] [S unifiable?])]{ 1632The goal @racket[(%copy F S)] unifies with @racket[S] a copy of the 1633frozen structure in @racket[F].} 1634 1635@bibliography[ 1636 @bib-entry[#:key "aop" 1637 #:author "Leon Sterling and Ehud Shapiro" 1638 #:url "http://mitpress.mit.edu/books/art-prolog" 1639 #:title "The Art of Prolog, 2nd Edition" 1640 #:location "MIT Press" 1641 #:date "1994" 1642 #:is-book? #t] 1643 @bib-entry[#:key "bratko" 1644 #:author "Ivan Bratko" 1645 #:title "Prolog Programming for Artificial Intelligence" 1646 #:location "Addison-Wesley" 1647 #:date "1986" 1648 #:is-book? #t] 1649 @bib-entry[#:key "campbell" 1650 #:author "J A Campbell (editor)" 1651 #:title "Implementations of Prolog" 1652 #:location "Ellis Horwood" 1653 #:date "1984" 1654 #:is-book? #t] 1655 @bib-entry[#:key "ok:prolog" 1656 #:author "Richard A O'Keefe" 1657 #:url "http://mitpress.mit.edu/books/craft-prolog" 1658 #:title "The Craft of Prolog" 1659 #:location "MIT Press" 1660 #:date "1990" 1661 #:is-book? #t] 1662 @bib-entry[#:key "logick" 1663 #:author "Christopher T Haynes" 1664 #:title "Logic continuations" 1665 #:location "J Logic Program, vol 4, 157--176" 1666 #:date "1987"] 1667 @bib-entry[#:key "mf:prolog" 1668 #:author "Matthias Felleisen" 1669 #:title "Transliterating Prolog into Scheme" 1670 #:location "Indiana U Comp Sci Dept Tech Report #182" 1671 #:date "1985"] 1672 ] 1673 1674 1675@close-eval[racklog-eval] 1676