--- a/src/wam/compiler.lisp Mon Apr 18 13:08:47 2016 +0000
+++ b/src/wam/compiler.lisp Mon Apr 18 15:16:22 2016 +0000
@@ -147,19 +147,128 @@
;;;; Parsing
-;;; Turns p(A, q(A, B)) into something like:
+;;; You might want to grab a coffee for this one.
+;;;
+;;; Consider this simple Prolog example: `p(A, q(A, r(B)))`. We're going to get
+;;; this as a Lisp list: `(p :a (q :a (r b)))`.
+;;;
+;;; The goal is to turn this list into a set of register assignments. The book
+;;; handwaves around how to do this, and it turns out to be pretty complicated.
+;;; This example will (maybe, read on) be turned into:
+;;;
+;;; A0 <- X2
+;;; A1 <- (q X2 X3)
+;;; X2 <- :a
+;;; X3 <- (r X4)
+;;; X4 <- :b
+;;;
+;;; There are a few things to note here. First: like the book says, the
+;;; outermost predicate is stripped off and returned separately (later it'll be
+;;; used to label the code for a program, or to figure out the procedure to call
+;;; for a query).
+;;;
+;;; The first N registers are designated as argument registers. Structure
+;;; assignments can live directly in the argument registers, but variables
+;;; cannot. In the example above we can see that A1 contains a structure
+;;; assignment. However, the variable `:a` doesn't live in A0 -- it lives in
+;;; X2, which A0 points at. The books neglects to explain this little fact.
;;;
-;;; X0 -> p(X1, X2)
-;;; X1 -> A
-;;; X2 -> q(X1, X3)
-;;; X3 -> B
+;;; The next edge case is permanent variables, which the book does talk about.
+;;; Permanent variables are allocated to stack registers, so if `:b` was
+;;; permanent in our example we'd get:
+;;;
+;;; A0 <- X2
+;;; A1 <- (q X2 X3)
+;;; X2 <- :a
+;;; X3 <- (r Y0)
+;;; Y0 <- :b
+;;;
+;;; Note that the mapping of permanent variables to stack register numbers has
+;;; to be consistent as we compile all the terms in a clause, so we cheat a bit
+;;; here and just always add them all, in order, to the register assignment
+;;; produced when parsing. They'll get flattened away later anyway -- it's the
+;;; USES that we actually care about. In our example, the `Y0 <- :b` will get
+;;; flattened away, but the USE of Y0 in X3 will remain).
+;;;
+;;; We're almost done, I promise, but there's one more edge case to deal with.
+;;;
+;;; When we've got a clause with a head and at least one body term, we need the
+;;; head term and the first body term to share argument/local registers. For
+;;; example, if we have the clause `p(Cats) :- q(A, B, C, Cats)` then when
+;;; compiling the head `(p :cats)` we want to get:
+;;;
+;;; A0 <- X4
+;;; A1 <- ???
+;;; A2 <- ???
+;;; A3 <- ???
+;;; X4 <- :cats
+;;;
+;;; And when compiling `(q :a :b :c :cats)` we need:
;;;
-;;; And then processes the argument register assignments into:
+;;; A0 <- X5
+;;; A1 <- X6
+;;; A2 <- X7
+;;; A3 <- X4
+;;; X4 <- :cats
+;;; X5 <- :a
+;;; X6 <- :b
+;;; X7 <- :c
+;;;
+;;; What the hell are those empty argument registers in p? And why did we order
+;;; the X registers of q like that?
+;;;
+;;; The book does not bother to mention this important fact at all, so to find
+;;; out that you have to handle this you need to do the following:
+;;;
+;;; 1. Implement it without this behavior.
+;;; 2. Notice your results are wrong.
+;;; 3. Figure out the right bytecode on a whiteboard.
+;;; 4. Try to puzzle out why that bytecode isn't generated when you do exactly
+;;; what the book says.
+;;; 5. Scour IRC and the web for scraps of information on what the hell you need
+;;; to do here.
+;;; 6. Find the answer in a comment squirreled away in a source file somewhere
+;;; in a language you don't know.
+;;; 7. Drink.
+;;;
+;;; Perhaps you're reading this comment as part of step 6 right now. If so:
+;;; welcome aboard. Email me and we can swap horror stories about this process
+;;; over drinks some time.
;;;
-;;; p/2:
-;;; A0 -> A
-;;; A1 -> q(A1, X3)
-;;; X2 -> B
+;;; Okay, so the clause head and first body term need to share argument/local
+;;; registers. Why? To understand this, we need to go back to what Prolog
+;;; clauses are supposed to do.
+;;;
+;;; Imagine we have:
+;;;
+;;; p(f(X)) :- q(X), ...other goals.
+;;;
+;;; When we want to check if `p(SOMETHING)` is true, we need to first unify
+;;; SOMETHING with `f(X)`. Then we search all of the goals in the body, AFTER
+;;; substituting in any X's in those goals with the X from the result of the
+;;; unification.
+;;;
+;;; This substitution is why we need the head and the first term in the body to
+;;; share the same argument/local registers. By sharing the registers, when the
+;;; body term builds a representation of itself on the stack before calling its
+;;; predicate any references to X will be point at the (unified) results instead
+;;; of fresh ones (because they'll be compiled as `put_value` instead of
+;;; `put_variable`).
+
+;;; But wait: don't we need to substitute into ALL the body terms, not just the
+;;; first one? Yes we do, but the trick is that any variables in the REST of
+;;; the body that would need to be substituted must, by definition, be permanent
+;;; variables! So the substitution process for the rest of the body is handled
+;;; automatically with the stack machinery.
+;;;
+;;; In theory, you could eliminate this edge case by NOT treating the head and
+;;; first goal as a single term when searching for permanent variables. Then
+;;; all substitution would happen elegantly through the stack. But this
+;;; allocates more variables on the stack than you really need (especially for
+;;; rules with just a single term in the body (which is many of them)), so we
+;;; have this extra corner case to optimize it away.
+;;;
+;;; We now return you to your regularly scheduled Lisp code.
(defun parse-term (term permanent-variables
;; JESUS TAKE THE WHEEL
@@ -177,7 +286,8 @@
(arguments (rest term))
(arity (length arguments))
;; Preallocate enough registers for all of the arguments. We'll fill
- ;; them in later.
+ ;; them in later. Note that things are more complicated in the head
+ ;; and first body term of a clause (see above).
(local-registers (make-array 64
:fill-pointer (or reserved-arity arity)
:adjustable t
--- a/src/wam/interpreter.lisp Mon Apr 18 13:08:47 2016 +0000
+++ b/src/wam/interpreter.lisp Mon Apr 18 15:16:22 2016 +0000
@@ -143,13 +143,56 @@
;;;; Instruction Definition
+;;; These macros are a pair of real greasy bastards.
+;;;
+;;; Basically the issue is that there exist two separate types of registers:
+;;; local registers and stack registers. The process of retrieving the contents
+;;; of a register is different for each type.
+;;;
+;;; Certain machine instructions take a register as an argument and do something
+;;; with it. Because the two register types require different access methods,
+;;; the instruction needs to know what kind of register it's dealing with.
+;;;
+;;; One possible way to solve this would be to encode whether this is
+;;; a local/stack register in the register argument itself (e.g. with a tag
+;;; bit). This would work, and a previous version of the code did that, but
+;;; it's not ideal. It turns out we know the type of the register at compile
+;;; time, so requiring a mask/test at run time for every register access is
+;;; wasteful.
+;;;
+;;; Instead we use an ugly, but fast, solution. For every instruction that
+;;; takes a register argument we make TWO opcodes instead of just one. The
+;;; first is the "-local" variant of the instruction, which treats its register
+;;; argument as a local register. The second is the "-stack" variant. When we
+;;; compile we can just pick the appropriate opcode, and now we no longer need
+;;; a runtime test for every single register assignment.
+;;;
+;;; To make the process of defining these two "variants" we have these two
+;;; macros. `define-instruction` (singular) is just a little sugar around
+;;; `defun*`, for those instructions that don't deal with arguments.
+;;;
+;;; `define-instructions` (plural) is the awful one. You pass it a pair of
+;;; symbols for the two variant names. Two functions will be defined, both with
+;;; the same body, with the symbol `%wam-register%` macroletted to the
+;;; appropriate access code. So in the body, instead of using
+;;; `(wam-{local/argument}-register wam register)` you just use
+;;; `(%wam-register% wam register)` and it'll do the right thing.
+
(defmacro define-instruction (name lambda-list &body body)
+ "Define an instruction function.
+
+ This is just syntactic sugar over `defun*` that will add the `(returns :void)`
+ declaration for you, and also append a `(values)` to the end of the body to
+ make sure it actually does return void.
+
+ "
`(defun* ,name ,lambda-list
(:returns :void)
,@body
(values)))
(defmacro define-instructions ((local-name stack-name) lambda-list &body body)
+ "Define a local/stack pair of instructions."
`(progn
(macrolet ((%wam-register% (wam register)
`(wam-local-register ,wam ,register)))