bones-rfc-1.markdown

The past few months I've been working on implementing Prolog in Common Lisp. The current code is here. It's an implementation of the Warren Abstract Machine, which is what most real-world, modern Prologs use (SWIProlog, gprolog, YAP, Eclipse, etc).

Current State

It's not done yet, but it's coming along nicely. It's missing a few key pieces, but it can run basic logic queries, e.g. for searching a game tree, and it runs pretty fast compared to PAIProlog (despite there being lots more optimizations on the list to add):

sjl at fenrir in ~/src/bones on default!
><((°> make bench
sbcl-rlwrap --noinform --load examples/bench.lisp  --eval '(quit)'
To load "bones":
  Load 1 ASDF system:
    bones
; Loading "bones"

To load "paiprolog":
  Load 1 ASDF system:
    paiprolog
; Loading "paiprolog"



========================================================
((SPEED 3) (SAFETY 1) (DEBUG 1))
--------------------------------------------------------
PAIP (Compiled) --------------------
Searched 21845 nodes.
Evaluation took:
  33.839 seconds of real time
  33.822605 seconds of total run time (33.206471 user, 0.616134 system)
  [ Run times consist of 1.455 seconds GC time, and 32.368 seconds non-GC time. ]
  99.95% CPU
  54 forms interpreted
  360,562 lambdas converted
  84,402,489,629 processor cycles
  15,227,843,824 bytes consed

PAIP (Interpreted) -----------------
Searched 21845 nodes.
Evaluation took:
  17.624 seconds of real time
  17.615951 seconds of total run time (17.546394 user, 0.069557 system)
  [ Run times consist of 0.303 seconds GC time, and 17.313 seconds non-GC time. ]
  99.95% CPU
  43,956,944,198 processor cycles
  4,057,979,056 bytes consed

WAM --------------------------------
Searched 21845 nodes.
Evaluation took:
  2.462 seconds of real time
  2.457234 seconds of total run time (2.444625 user, 0.012609 system)
  [ Run times consist of 0.042 seconds GC time, and 2.416 seconds non-GC time. ]
  99.80% CPU
  6,139,620,330 processor cycles
  420,087,936 bytes consed

Not terribly scientific (yet), but a good indicator that I'm on the right track here.

Advice Needed

Now that I've got something runnable, I want to start hammering out the "UI" for the library. Up til now I just hacked together a thin veneer over the compiler so I could test things, but I want to start designing it for real now.

I'm trying to decide a few basic questions, and if anyone has any Thoughts, Opinions, or Hot Takes I'd love to hear them.

Variables

PAIProlog uses symbols whose name starts with a question mark as Prolog variables. For example:

;; PAIProlog
;; Sally likes anyone who likes cats
((likes sally ?person)
 (likes ?person cats))

This seemed ugly to me (you have to pull out the string representation of the symbol name to determine whether something is a variable) so up til now I've used keywords instead:

;; Bones
;; Sally likes anyone who likes cats
((likes sally :person)
 (likes :person cats))

Now determining whether something is a variable is simply a keywordp. This seems cleaner, but since I started I've thought of two advantages of the non-keyword symbol approach:

1. Variable symbols can be gensymed.
2. You could potentially bind them to variables with a macro, e.g.: (do-query (likes sally ?who) (format t "Sally likes ~A~%" ?who)).

Should I just bite the bullet and switch to the ugly ?foo syntax?

Prolog Lists

A couple of days ago I added support for Prolog lists to the Bones WAM. My initial UI treats (quote (...)) in a query as a Prolog list, which means you end up writing:

(rules
  ((member :thing '(:thing . :rest)))

  ((member :thing '(:other . :rest))
   (member :thing :rest)))

This seems okay at first glance, but it can get hairy when you need to nest lists, because unlike in vanilla Lisp you need to quote each list. It's also easy to forget a quote and inadvertently create a Prolog structure instead of a list:

(member :thing '((a b c) (d e f)))   ; wrong :(
(member :thing '('(a b c) '(d e f))) ; right :\

One idea I had for this was to repurpose the cl:list and cl:list* symbols:

(rules
  ((member :thing (list* :thing :rest)))

  ((member :thing (list* :other :rest))
   (member :thing :rest)))

(member :thing (list a b c))
(member :thing (list (list a b c) (list d e f)))

This is more verbose but much more clear. I could potentially add an optional reader macro on top that could expand into the verbose list/list* form:

(rules
  ((member :thing #[:thing * :rest]))

  ((member :thing #[:other * :rest])
   (member :thing :rest)))

(member :thing #[a b c])
(member :thing #[#[a b c] #[d e f]])

I'm sure there are other ways to do this I haven't thought of, so let me know!

Thanks!

Personally, I like the ?foo syntax. You can find some good ideas for lisp-y prolog syntax in the Franz prolog docs (check out the Zebra example at the bottom).

Ah yeah, I think Allegro's prolog is based on the Prolog from PAIP? At least that's what http://weitz.de/cl-recipes/ tells me :)

• Although I'm not keen on ?foo, I can't think of a better alternative. One could create a class represtring a variable and a reader macro, (eg #L"FOO") that works as a constructor but I don't think that would be a better solution.
• Having to quote lists inside quotes is a deal-braker. Using list/list* is a better solution although not optimal. One also has to consider how backquotes are handled (which is implementation dependent). It maybe be viable to use a reader-macro quasiquote implementation like fare-quasiquote and provide integration like optima (now trivia also) does.

Most importantly, keep up the good work! 🎉 🎈

A (truncated) example of the Prolog and Lisp syntax excerpted from the Zebra puzzle:

zebra(H, W, Z) :-
    H = [house(norwegian, _, _, _, _), _, house(_, _, _, milk, _), _, _],
     member(house(englishman, _, _, _, red), H),
     member(house(spaniard, dog, _, _, _), H),
     member(house(_, _, _, coffee, green), H),
     member(house(ukrainian, _,  _, tea, _), H),

vs.

(<-- (zebra ?h ?w ?z)
     (= ?h ((house norwegian ? ? ? ?)   
            ?
            (house ? ? ? milk ?) ? ?))  
     (member (house englishman ? ? ? red) ?h)
     (member (house spaniard dog ? ? ?) ?h) 
     (member (house ? ? ? coffee green) ?h) 
     (member (house ukrainian ? ? tea ?) ?h) 

... which looks pretty reasonable to me. Also, as PP said, keep up the good work! 😸