Rewrite the compiler
A few days ago I found a bug in the compiler that I decided merited basically an
entire rewrite of it.
This was long overdue. The compiler kind of grew organically and unhealthily
over time as I wrapped my head around how the whole WAM is structured, and now
that I understand a lot more I can do things right.
This new implementation is a lot "flatter" than the old one. It makes use of
CLOS classes and generic methods to un-nest a lot of the crap that was
previously happening in bigass `labels` blocks. This is a lot easier to read
and understand because you can take things a piece at a time.
Unfortunately, it's currently a lot slower than the old one. But at least it's
*correct*, and now I can start taking a look at optimizing the performance with
a cleaner base to start from.
Notes/ideas for the near future:
* Switch to structs instead of CLOS classes for all the bits and bobs in the
compilation process.
* Inline hot functions in the compilation process.
* Type hint the fucking compiler already. I've put this off for far too long.
* Move the compiler to its own package for easier profiling and to maintain my
shreds of sanity.
* Look into that generic-function-inlining library thing I saw on Reddit...
* Remove the last vestiges of `match` and kill the dependency on optima.
| author |
Steve Losh <steve@stevelosh.com> |
| date |
Tue, 07 Jun 2016 14:49:20 +0000 |
| parents |
d8d6647dd9fb |
| children |
5c914fbcb042 |
(in-package #:bones-test.paip)
(def-suite :bones.paip)
(in-suite :bones.paip)
;;;; Utils
(defun alist-equal (x y)
(set-equal x y :test #'equal))
(defmacro unifies (x y bindings)
`(is (alist-equal ,(if (eql bindings 'no-bindings)
'no-bindings
`',bindings)
(unify ',x ',y))))
(defmacro not-unifies (x y)
`(is (eql bones.paip:fail (unify ',x ',y))))
(defmacro with-db (rules &rest body)
`(progn
(clear-db)
,@(mapcar (lambda (rule) `(rule ,@rule))
rules)
,@body))
(defmacro proves (query)
`(is-true (return-all ,query)))
(defmacro not-proves (query)
`(is-false (return-all ,query)))
(defmacro proves-with (query results)
`(is (set-equal ',results (return-all ,query)
:test #'alist-equal)))
;;;; Unification
(test constant-unification
(unifies 1 1 no-bindings)
(unifies foo foo no-bindings)
(unifies (a) (a) no-bindings)
(unifies (a b c) (a b c) no-bindings)
(not-unifies 1 2)
(not-unifies foo bar)
(not-unifies a (a))
(not-unifies (a) (a b))
(not-unifies () (a)))
(test variable-unification
(unifies ?x 1 ((?x . 1)))
(unifies ?x a ((?x . a)))
(unifies ?x ?y ((?x . ?y)))
(unifies (?x (f ?x)) (2 (f 2)) ((?x . 2)))
(unifies (likes sally ?thing)
(likes ?person cats)
((?thing . cats)
(?person . sally)))
(unifies (?x + ?y)
(10 + (1 + 2))
((?x . 10)
(?y . (1 + 2))))
(unifies (?x + (?y + ?z))
(10 + (1 + 2))
((?x . 10)
(?y . 1)
(?z . 2)))
(not-unifies (?x ?x) (1 2))
(not-unifies (?x ?y ?x) (1 1 3)))
(test occurs-unification
(not-unifies ?x (f ?x))
(not-unifies ?x (f (?x 1)))
(not-unifies ?x (?x ?x))
(not-unifies ?x (?x ?y))
(let ((*check-occurs* nil))
(unifies ?x (f ?x) ((?x . (f ?x))))
(unifies ?x (f (?x 1)) ((?x . (f (?x 1)))))
(unifies ?x (?x ?x) ((?x . (?x ?x))))
(unifies ?x (?x ?y) ((?x . (?x ?y))))))
;;;; Basic Proving
(test prove-facts
(with-db (((likes kim cats))
((likes tom cats)))
(proves (likes kim cats))
(proves (likes tom cats))
(not-proves (likes kim tom))
(not-proves (likes kim))))
(test prove-rules-simple
(with-db (((likes kim cats))
((likes sally ?x) (likes ?x cats)))
(proves (likes sally kim))
(not-proves (likes sally sally))))
(test prove-member
(with-db (((member ?x (?x . ?tail)))
((member ?x (?y . ?tail)) (member ?x ?tail)))
(proves (member 1 (1 2)))
(proves (member 2 (1 2)))
(proves (member (x) (1 (x) 2)))
(not-proves (member 1 ()))
(not-proves (member ?x ()))
(not-proves (member 1 (a b c)))
(proves-with (member ?x (1 2 3))
(((?x . 1))
((?x . 2))
((?x . 3))))
(proves-with (member ?x (1 1 1))
(((?x . 1))))
(proves-with (member (?x ?y) ((a b) (c d) 1))
(((?x . a) (?y . b))
((?x . c) (?y . d))))))
(test prove-last
(with-db (((last ?x (?x)))
((last ?x (?y . ?tail)) (last ?x ?tail)))
(proves (last 1 (1)))
(proves (last 2 (1 2)))
(not-proves (last 1 ()))
(not-proves (last 1 ((1))))
(not-proves (last 1 (1 2)))
(proves-with (last ?x (1 2 3))
(((?x . 3))))
(proves-with (last ?x (1 (2 3)))
(((?x . (2 3)))))))