Querying Fact Bases

So it seems that a lot of people are into this logic programming thing I've been reading about lately. There's the already mentioned Reasoned Schemer trio of Friedman/Byrd/Kiselyov behind the beautiful but arcane miniKanren language, a prolog-like contained in Peter Norvig's Paradigms of Artificial Intelligence Programming chapters 11, 12 and 14, another one in Graham's On Lisp chapters 19, 22, 23, 24 and yet another in chapter 4.4 of Abelson and Sussman's SICP. So there's a lot of literature around dealing with how you go about building a unifier or pattern-matcher[1].

Anyway, I've been consuming this literature for a while, and the part I want to zoom in on is searching the database. The other stuff is easy; a unifier can be straight-forwardly built in about ten lines[2] and handling variables is the same tree-traversal stuff you've seen a hundred times before, but the actual search never seems to be the focus of these things. And I'm looking for a particular type of search for fact-base. I showed it off recently at a Toronto Lisp Group meeting along with the app it's supposed to enable and mentioned that querying is mildly annoying when you get to compound queries. Specifically, I took as an example the very simple database

(defparameter base (make-fact-base))
(insert! base (list 0 :message "This is a sample message"))
(insert! base (list 1 :message "This is another one"))
(insert! base (list 1 :author "Inaimathi"))
(insert! base (list 2 :message "That second one was written by me. This one is a meta-message (also by me)."))
(insert! base (list 2 :author "Inaimathi"))
(insert! base (list 2 :type :meta))

and pointed out that in order to find All the message bodies authored by Inaimathi, you'd have to take two steps

1. traverse the database looking for facts that have '(:author "Inaimathi") for a rest
2. get all the facts that have the same first as one of the above and the second :message, and collect their thirds

In actual lisp, that looks like

(loop for (a b c) in (lookup base :b :author :c "Inaimathi") 
      collect (caddar (lookup base :a a :b :message)))

That's even passably fast, thanks to our index system, but it's annoying to write, and it forces me to do a fact-base->objects conversion in some places rather than write out these multi-stage iterations myself. What I'd like to be able to do in the above is something like

(for-all (and (?id :author "Inaimathi") (?id :message ?message)) :in my-fact-base :get ?message)

and have the system figure it out for me. Granted in this situation, you don't gain very much, but it would be a compounding gain for more complex queries. For instance, if I suddenly decided I want to select All the message bodies authored by Inaimathi pertaining to other messages, the query language version handles it very simply:

(for-all (and (?id :author "Inaimathi") (?id :message ?message) (?id :type :meta)) :in my-fact-base :get ?message)

whereas the manual version would add another level of iteration I'd need to work through. Oh, and have fun with the situation where you only want the first 5 or so hits. The easiest solution with the manual approach is searching the entire space and throwing away all but the first n results. You could do better, but you're suddenly in the supremely annoying situation where your queries all look mildly different, but perform the same basic task.

What I figure I'd want is a lazy or lazy-ish way of getting the results. The lazy solution can easily be converted to the eager solution later, but it's really painful to take the eager approach and then find out that you only needed to do about 4% of the work done. I'll be using generators, rather than outright lazy sequences just because they're mildly easier to put together. For a single goal, that's trivial.

(for-all (?id :author "Inaimathi") :in my-fact-base)

All you have to do here is have a generator that runs over the facts in my-fact-base and returns the next matching one it finds. Something like

(defun match-single (goal bindings facts)
  (let ((fs facts))
    (lambda ()
      (loop for res = (unify goal (pop fs) bindings)
         unless (fail? res) do (return res)
         while fs
         finally (return (fail))))))

would do fine. I'm pointedly refusing to commit to an implementation of (fail), unify and bindings at each point for the purposes of this post, but am using the stuff out of Norvig's PAIP source code. For the uninitiated: A goal is the thing you're trying to match; it's an expression that may contain some variables. A variable is a thing that you can substitute; it can either be unbound or assigned a value in a particular set of bindings. If a unification fails, it returns (fail), and if it's successful it returns the set of bindings that would make that unification expression true. For instance, if you unified ?a with 5, starting with empty bindings, unify would return the set of bindings in which ?a is bound to 5.

So the above match-single definition would return a generator which, when called, would either (fail), or return the environment resulting from unifying the next element of facts with goal. Hopefully, straight-forward, though you may need to do a bit of reading up on it if you've never seen the terms before.

The next easiest thing to do would be handling a set of ored goals. That is

(for-all (or (?id :author "Aaron") (?id :author "Bradley")) :in my-fact-base)

It's basically the same thing, except that instead of applying a single goal and checking if it sticks, we're applying several goals in sequence and seeing if any of them stick. Something like

(defun match-ors (goals bindings facts)
  (let ((fs facts))
    (flet ((try-goals (f)
             (loop for g in goals
                for res = (unify g f bindings)
                when res do (return res)
                finally (return (fail)))))
      (lambda ()
        (loop for res = (try-goals (pop fs))
           unless (fail? res) do (return res)
           while fs
           finally (return (fail)))))))

which is by my estimation only marginally more complicated. The tricky part is traversing a fact-base in order to satisfy anded goals. Like in that example I mentioned near the beginning:

(for-all (and (?id :author "Inaimathi") (?id :message ?message) (?id :type :meta)) :in my-fact-base :get ?message)

Think about it.

What you want here is fairly complicated to express in English. I'm still trying to return a generator from the whole thing, but expressing its behavior is a complex.

If you only get one goal, you want to fall through to a call to match-single; that's still fairly straight-forward. The magic happens at more than one goal. And I just deleted about four paragraphs of prose that would have thoroughly confused you. It's not a very easy set of concepts to express in English because it refers to pieces of itself fairly often.

Lets try it this way:

(defun match-ands (goals bindings facts)
  (let ((generator (match-single (first goals) bindings facts))
        (rest-generator))
    (if (null (cdr goals))
        generator
        (labels ((next-gen ()
                   (let ((res (funcall generator)))
                     (if (fail? res)
                         (fail)
                         (setf rest-generator (match-ands (rest goals) res facts)))))
                 (backtrack! ()
                   (if (fail? (next-gen))
                       (fail)
                       (next)))
                 (next ()
                   (if (null rest-generator)
                       (backtrack!)
                       (let ((res (funcall rest-generator)))
                         (if (fail? res)
                             (backtrack!)
                             res)))))
          #'next))))

The image you want, once you've put the initial generator tower together, is one of those combo bike-locks.

If you want to search its entire possibility space, you spin the last ring until it runs out of values. Then you spin the second-to-last ring once, and retry the last ring. When you run out of values on the second-to-last ring, you spin the third-to-last ring once and so on. It's an incredibly tedious exercise, which is why I'd prefer a machine to handle it.

Now, chunk by chunk

(defun match-ands (goals bindings facts)
  (let ((generator (match-single (first goals) bindings facts))
        (rest-generator))
    (if (null (cdr goals))
        generator
        ...

By the time we're calling this function, I assume that it'll be handed at least one goal. You always want the generator of your first goal, and if you only get the one goal, you just return said generator and you're done. Multiple goals are where you need to pull fancy footwork. Again, one chunk at a time:

        ...
        (labels ((next-gen ()
                   (let ((res (funcall generator)))
                     (if (fail? res)
                         (fail)
                         (setf rest-generator (match-ands (rest goals) res facts)))))
                 ...

This is where we set the rest-generator from earlier. It's just the procedure that will return the next result from proving the rest of the goals given the set of bindings built from proving the first goal into the starting set of bindings given to match-ands initially. If calling the first goals' generator fails, we likewise fail; otherwise we set rest-generator to the generator we create by passing the result back up to match-ands.

                 ...
                 (backtrack! ()
                   (if (fail? (next-gen))
                       (fail)
                       (next)))
                 ...

Occasionally, we have to backtrack. Which in this context means we try to call next-gen. If that fails, we likewise fail, otherwise we invoke next. Which...

                 ...
                 (next ()
                   (if (null rest-generator)
                       (backtrack!)
                       (let ((res (funcall rest-generator)))
                         (if (fail? res)
                             (backtrack!)
                             res)))))
                       ...

...sets up an initial rest-generator if there isn't one, then tries to call it. If that fails, we backtrack![3], otherwise we return the result.

          ...
          #'next))))

That next function I just described is the generator we want for a multi-goal proof, which means that it's the final return value from match-ands.

The only required piece of infrastructure left is for-all itself. We want it to be able to provide results, or do something with them lazily. Which means it'll look something like

(defmacro for-all (goal-term &key in get apply)
  (assert in nil "Need a database to query...")
  (when (and get apply)
    (format t ":apply and :get arguments passed in; ignoring :get"))
  (with-gensyms (template gen res facts)
    `(let* ((,facts ,in)
            (,gen ,(cond ((eq 'and (car goal-term))
                          `(match-ands ',(replace-anonymous (rest goal-term)) +succeed+ ,facts))
                         ((eq 'or (car goal-term))
                          `(match-ors ',(replace-anonymous (rest goal-term)) +succeed+ ,facts))
                         (t
                          `(match-single ',goal-term +succeed+ ,facts))))
            ,@(unless apply
              `((,template ',(replace-anonymous (or get goal-term))))))
       (loop for ,res = (funcall ,gen)
          while ,res collect ,(if apply
                                  `(apply (lambda ,(variables-in apply) ,apply)
                                          (subst-bindings ,res ',(variables-in apply)))
                                  `(subst-bindings ,res ,template))))))

Which isn't nearly as complicated as it seems at first glance. Lets go through that too.

(defmacro for-all (goal-term &key in get apply)
  (assert in nil "Need a database to query...")
  (when (and get apply)
    (format t ":apply and :get arguments passed in; ignoring :get"))
    ...

arguments, and trying to be helpful with invocation errors. We want the thing to be readable too, which is why I use "mandatory" keyword arguments in this one.

  ...
  (with-gensyms (template gen res facts)
    `(let* ((,facts ,in)
            (,gen ,(cond ((eq 'and (car goal-term))
                          `(match-ands ',(replace-anonymous (rest goal-term)) +succeed+ ,facts))
                         ((eq 'or (car goal-term))
                          `(match-ors ',(replace-anonymous (rest goal-term)) +succeed+ ,facts))
                         (t
                          `(match-single ',goal-term +succeed+ ,facts))))
   ...

we're setting up some name sanitation for certain words we'd like to use in the definition that should still be usable by the callers of for-all. Note the use of replace-anonymous, the definition can be found in Norvig's prolog implementation. The entirety of that cond decides which of our matchers we're going to use to traverse our corpus.

            ...
            ,@(unless apply
              `((,template ',(replace-anonymous (or get goal-term))))))
            ...

If we get passed the apply argument, we'll be doing something special later. Otherwise, we'll want to slot our results into the template in gen, and failing that, just slot it back into the querying goal form.

       ...
       (loop for ,res = (funcall ,gen)
          while ,res collect ,(if apply
                                  `(apply (lambda ,(variables-in apply) ,apply)
                                          (subst-bindings ,res ',(variables-in apply)))
                                  `(subst-bindings ,res ,template))))))

And that's the meat of it. We're going to be grabbing results out of our generator. As you can see, the special thing we're doing with the apply argument is stitching up a function to apply to a substituted list of our results. If we didn't get an apply, we're just slotting said result back into the template we defined earlier. I find that seeing some macroexpansions really helps understanding at this stage. So, here are the basics:

Plain single-goal:

CL-USER> (macroexpand '(for-all (?id :author "Inaimathi") :in my-fact-base))
(LET* ((#:FACTS1073 MY-FACT-BASE)
       (#:GEN1071
        (MATCH-SINGLE '(?ID :AUTHOR "Inaimathi") +SUCCEED+ #:FACTS1073))
       (#:TEMPLATE1070 '(?ID :AUTHOR "Inaimathi")))
  (LOOP FOR #:RES1072 = (FUNCALL #:GEN1071)
        WHILE #:RES1072
        COLLECT (SUBST-BINDINGS #:RES1072 #:TEMPLATE1070)))
T

or-goals:

CL-USER> (macroexpand '(for-all (or (?id :author "Inaimathi") (?id :message ?message)) :in my-fact-base))
(LET* ((#:FACTS1077 MY-FACT-BASE)
       (#:GEN1075
        (MATCH-ORS '((?ID :AUTHOR "Inaimathi") (?ID :MESSAGE ?MESSAGE))
                   +SUCCEED+ #:FACTS1077))
       (#:TEMPLATE1074 '(OR (?ID :AUTHOR "Inaimathi") (?ID :MESSAGE ?MESSAGE))))
  (LOOP FOR #:RES1076 = (FUNCALL #:GEN1075)
        WHILE #:RES1076
        COLLECT (SUBST-BINDINGS #:RES1076 #:TEMPLATE1074)))
T

and-goals:

CL-USER> (macroexpand '(for-all (and (?id :author "Inaimathi") (?id :message ?message)) :in my-fact-base))
(LET* ((#:FACTS1081 MY-FACT-BASE)
       (#:GEN1079
        (MATCH-ANDS '((?ID :AUTHOR "Inaimathi") (?ID :MESSAGE ?MESSAGE))
                    +SUCCEED+ #:FACTS1081))
       (#:TEMPLATE1078
        '(AND (?ID :AUTHOR "Inaimathi") (?ID :MESSAGE ?MESSAGE))))
  (LOOP FOR #:RES1080 = (FUNCALL #:GEN1079)
        WHILE #:RES1080
        COLLECT (SUBST-BINDINGS #:RES1080 #:TEMPLATE1078)))
T

Using the :get option

CL-USER> (macroexpand '(for-all (and (?id :author "Inaimathi") (?id :message ?message)) :in my-fact-base :get ?message))
(LET* ((#:FACTS1085 MY-FACT-BASE)
       (#:GEN1083
        (MATCH-ANDS '((?ID :AUTHOR "Inaimathi") (?ID :MESSAGE ?MESSAGE))
                    +SUCCEED+ #:FACTS1085))
       (#:TEMPLATE1082 '?MESSAGE))
  (LOOP FOR #:RES1084 = (FUNCALL #:GEN1083)
        WHILE #:RES1084
        COLLECT (SUBST-BINDINGS #:RES1084 #:TEMPLATE1082)))
T

Using the :apply option

CL-USER> (macroexpand '(for-all (and (?id :author "Inaimathi") (?id :message ?message)) :in my-fact-base :apply (format t "~s~%   -Inaimathi" ?message)))
(LET* ((#:FACTS1089 MY-FACT-BASE)
       (#:GEN1087
        (MATCH-ANDS '((?ID :AUTHOR "Inaimathi") (?ID :MESSAGE ?MESSAGE))
                    +SUCCEED+ #:FACTS1089)))
  (LOOP FOR #:RES1088 = (FUNCALL #:GEN1087)
        WHILE #:RES1088
        COLLECT (APPLY
                 (LAMBDA (?MESSAGE) (FORMAT T "~s~%   -Inaimathi" ?MESSAGE))
                 (SUBST-BINDINGS #:RES1088 '(?MESSAGE)))))
T
CL-USER> 

And that's that. Granted, the implementation is a bit more complicated than just writing manual loops, but I'm convinced there are a couple wins here. Firstly, the invocation is simpler, which means that the above definitions will eventually "pay for themselves" in terms of complexity. Secondly, it seems like I could fairly easily mod this into parenscript-friendly forms, which means this'll save me from having to convert fact-bases to object lists on the client side. But that's something I'll tell you about next time.

---

Footnotes

1 - [back] - Almost always using the question-mark-prefix notation for logic variables for some reason. I'm not sure what the approach gains or loses you yet. I guess in the case of miniKanren, it gains you the ability to unify on vectors since there's no ambiguity, and it might make it easier to read the resulting programs, but I'm not banking on that.

2 - [back] - Though do go over Norvig's version to see a dissection of the common bugs.

3 - [back] - And remember, backtrack! itself fails if it runs out of search space.

Buildapp Minutia

Before I get to telling you what I've been up to lately, let me share some insight into what it takes to build Lisp executables on Windows and Linux. This is something I had to do recently at work. I wouldn't normally bother, but we still have Windows dev boxes, and it seemed like an interesting enough exercise. In no particular order, here are things you need to think about when you're putting things together with buildapp.

Be careful with your storage folders

My usual tactic for this sort of thing is to store static files and stored files in the project directory. It's easy to do because I just get to use relative paths everywhere, and it works well enough if your distribution plan is basically git clone https://github.com/you/whatever.git. The only downside is that you have to run the program in the context of its project directory, or have random static folders pop up in random places.

For people who don't just randomly write Lisp code for fun, this isn't exactly acceptable. To do proper binary deployment for a more general audience, you need to make sure that there's a single consistent place for your program to store stuff. And if you want to be cross-platform about it, you can't just do (defvar *storage* "~/project-name/") and call it a day. Fortunately, user-homedir-pathname is a thing, so what I ended up doing is setting my storage directory to (merge-pathnames ".project-name/" (user-homedir-pathname)). However, it wasn't quite that simple.

My other usual tactic is to just put such config variable declarations in the appropriate package.lisp file, and leave it at that. Unfortunately, when I tried that with buildapp, the first teammate who tried it responded with

Why is this complaining that "C:\Users\Inaimathi\2dmacs\" doesn't exist?

The problem is that buildapp takes your image and binary and ships it, including anything you did at compile or config time. What I really wanted was for my binary to check at runtime what the users' home directory is and use that as the starting point for its own storage directory. The way I ended up doing that, though I'm sure others are possible, was to define the appropriate variables where I'd usually put them, then set them again in the entry-point function. Mine happened to be called main, because why not, so what you'd see if you looked into the appropriate files is[1]

;;; package.lisp

...

(defparameter *storage* nil)

...

;;; start.lisp

...

(defun main (&optional argv)
  ...
  (setf *storage* (merge-pathnames ".2dmacs/" (user-homedir-pathname)))
  ...
  )

That lets the appropriate functions access storage files, but makes sure that *storage* will ultimately be set to the appropriate directory on the users' machine rather than yours.

Native SBCL shell sucks balls under Windows

We had a couple problems deploying a specific part of the system that dealt with running external programs. And like the title says, that was balls on Windows. Not that I expected it to run perfectly across operating systems, but it turned out to be particularly thorny. First off, external-program doesn't do what we wanted. It kinda does, but doesn't seem to let you have a hook in to search the users' environment variables for program locations. Luckily, we're using SBCL, and its native sb-ext:run-program does give you this facility in the form of the search keyword argument. Also, for some reason SBCL handles streams really oddly in Windows? Not sure why, but the end result was that I couldn't capture *standard-output* in the way I wanted to in one part of the code. We ended up dealing with that by calling sb-ext:run-program with :output :stream, then collecting the result through sb-ext:process-output instead of direct stream capture. Cool, I guess. It seemed to work in testing. But the particular shell command we were using started seizing up once we hit a particular corpus size[2]. The solution we ended up taking was using uiop:run-program instead. It deals with streams the way I was expecting and handles all shell commands we've thrown at it so far very snappily.

Finding dependencies is ... non-trivial

buildapp doesn't load dependencies automatically. It expects you to pass it a bunch of --load-system command line arguments for things you want included in the final binary. The first thing I did was check the docs. There didn't seem to be a dependency-tree call anywhere, so I wrote this one. On a whim though, I dropped by #lisp, where I got the opportunity to ask Zach about it[3]. It turns out that what I wrote is really only going to get you the dependencies declared in asdf files, and there are apparently enough people out there who hook manual load or ql:quickload statements in through odd, ad-hoc ways that he doesn't go that route. Turns out that what he does is asdf:load-system/ql:quickload the thing he wants to build, then runs ql:write-asdf-manifest-file to find the list of all systems included in the image after everything relevant has been loaded. The buildapp call you make after that needs to look something like buildapp --manifest-file wherever/you/had/ql:write-manifest-file/output.txt --load-system foo --load-system bar ... --entry your-entry-fn --output your-program-name. Mildly annoying, but at least it'll get you what you need.

---

Footnotes

1 - [back] - Ok, it's mildly more complicated than this too, because I wanted to deal with some command line arguments, and I wanted some static files to be optionally re-generated at each program load. You can still see the basic principle.

2 - [back] - If you must know, it was git ls-tree, and the call started hanging around the time that we committed the ~third file into the target repository.

3 - [back] - Here's the transcript, for those of you who want the details:

13:58 <inaimathi> Anyone here who knows things about asdf
                  dependencies, and is willing to answer
                  questions/lend an eye?
13:58 <Xach> inaimathi: I know a bit. What's up?
13:59 <inaimathi> I'm trying to find the dependency tree
                  (preferably ordered) of a given asdf system.
13:59 <inaimathi> Is there a build-in way of doing that?
13:59 <inaimathi> *built
13:59 <inaimathi> Hm
14:00 <inaimathi> Actually, you might be able to help with the
                  larger problem too. The real problem is that I'm
                  trying to run buildapp for a project, and I want
                  to know what systems I need to load as part of
                  the shell command.
14:00 <Xach> oh. the way i do that is to load the project once with
             dependencies downloaded automatically and then note
             what was loaded.
14:00 <Xach> then i load it again with just those things.
14:01 <Xach> it is not great but arbitrary things load during
             find-system time so i'm not sure if there's a nice way
             around it.
14:01 <inaimathi> How do I go about doing that?
14:02 <inaimathi> That is, loading a project while getting output
                  of what's being loaded. Is there a ql flag or
                  something?
14:03 <Xach> inaimathi: i don't actually note the specifics. i just
             load it, and then have quicklisp dump out an index to
             the currently installed libraries via
             (ql:write-asdf-manifest-file
             "/path/to/my/project/system-index.txt")
14:03 <inaimathi> Ah
14:03 <Xach> then i use buildapp --asdf-manifest system-index.txt
             --<the rest of the stuff>
14:04 <Xach> Each time I make a new project I refine the makefile
             technique a little more
14:05 <inaimathi> Ok then. Do you think something like
                  http://stackoverflow.com/a/22732580/190887 could
                  be a valid approach, or is that going to miss
                  things?
14:07 <Xach> inaimathi: One difficulty arises from .asd files with
             things like (eval-when ... (asdf:load-system
             "some-prerequisite"))
14:07 <inaimathi> Right; those wouldn't be noted by the asdf system
                  itself.
14:07 <inaimathi> Dammit.
14:08 <Xach> I also don't know if the slot you're looking at
             includes :defsystem-depends-on dependencies.
14:08 <Xach> inaimathi: I once asked about how to do this on
             asdf-devel and I got an answer I didn't really
             understand (it was complicated) and I haven't
             revisited it. And I'm not sure there's an archive you
             can search for it.
14:09 <rtoym> asdf-devel is on gmane.org
14:10 <inaimathi> Hm. I'll take the asdf-manifest-file approach for
                  the moment, and probably ask around on asdf-devel
                  later.
14:10 <inaimathi> Thanks!

Fact Base Indices

Got through a late-night programming binge, followed by more of the same on my lunch break, followed by a couple more days of thought and work during downtime. It's up at my fact-base implementation. Basically, we have indices now. Fairly naive, simple indices, but they should suffice for what I'm up to[1].

Before we get to discussing any code, lets back up and discuss the idea of an index for a moment.

The Idea of an index

An index in this context is an extra layer on top of our fact storage engine that keeps track of what we've put in/taken out in a way that makes certain things easier to look up. It's easier for fact-bases than it is for relational databases. Since every fact is made up of three components[3], all we have to do is keep an index by one or two slots. What we're basically looking to do is a really fast lookup of some subset of all facts in a base based on one or two of those keys[4]. The way I've chosen to do it, after some advice from friends who've used systems something like this, is by maintaining hash tables[5] in memory that give you shortcuts to some specified indices. We're trading space[6] for time[7].

The Post-Explanation Version

This was a much different article initially; I was going to discuss some bone-headed intermediate states for this code before getting to the "final"[8]. It ended up looking like a stupid idea in this particular instance because the previous versions weren't things I'd consider running after having thought through it a bit more.

I try to do that a fair amount these days.

Not the stupid implementations thing, though that's also true. I mean sit down with another actual human being and talk them through the code I just wrote. It's not quite as good as blogging about it, but it's faster and turns up almost as many issues. It also has an added benefit that blogging doesn't seem to give me, which is showing me when I'm completely off my nut. Anyhow, here's what I had after I explained the thing to someone, poured some shower time into thinking about it, and drafting the first version of this post:

(in-package #:fact-base)

(defclass index ()
  ((table :reader table :initform (make-hash-table :test 'equal))))

(defun make-index (indices)
  (let ((index (make-instance 'index)))
    (loop for ix in indices
       do (setf (gethash ix (table index))
                (make-hash-table :test 'equal)))
    index))

(defmethod indexed? ((state index) (ix-type symbol))
  (gethash ix-type (table state)))

(defun decide-index (&optional a b c)
  (cond ((and a b c) (list :abc a b c))
        ((and a b) (list :ab a b))
        ((and a c) (list :ac a c))
        ((and b c) (list :bc b c))
        ((and a) (list :a a))
        ((and b) (list :b b))
        ((and c) (list :c c))))

(defmethod format-index ((ix-type symbol) (fact list))
  (destructuring-bind (a b c) fact
    (case ix-type
      (:abc (list a b c))
      (:ab (list a b))
      (:ac (list a c))
      (:bc (list b c))
      (:a (list a))
      (:b (list b))
      (:c (list c)))))

(defmethod map-insert! ((facts list) (state index))
  (dolist (f facts) (insert! f state)))

(defmethod insert! ((fact list) (state index))
  (loop for ix being the hash-keys of (table state)
     for ix-table being the hash-values of (table state)
     do (push fact (gethash (format-index ix fact) ix-table))))

(defmethod delete! ((fact list) (state index))
  (loop for ix being the hash-keys of (table state)
     for ix-table being the hash-values of (table state)
     for formatted = (format-index ix fact)
     do (setf (gethash formatted ix-table) 
              (remove fact (gethash formatted ix-table) :test #'equal :count 1))
     unless (gethash formatted ix-table) do (remhash formatted ix-table)))

;;;;; Show methods
;; Entirely for debugging purposes. 
;; Do not use in production. 
;; Seriously.
(defmethod show (thing &optional (depth 0))
  (format t "~a~a" (make-string depth :initial-element #\space) thing))

(defmethod show ((tbl hash-table) &optional (depth 0))
  (loop for k being the hash-keys of tbl
     for v being the hash-values of tbl
     do (format t "~a~5@a ->~%" 
                (make-string depth :initial-element #\space) k)
     do (show v (+ depth 8))
     do (format t "~%")))

(defmethod show ((ix index) &optional (depth 0))
  (show (table ix) depth))

There, that's not so intimidating, is it? The actual interface to these indices is in fact-base.lisp, but the above contains most of the functionality. First, ignore the show methods at the bottom there. That was just a piece of hackery to give me a usable visual representation of an index while I was debugging this beast. Lets start at the top.

(defclass index ()
  ((table :reader table :initform (make-hash-table :test 'equal))))

(defun make-index (indices)
  (let ((index (make-instance 'index)))
    (loop for ix in indices
       do (setf (gethash ix (table index))
                (make-hash-table :test 'equal)))
    index))

(defmethod indexed? ((state index) (ix-type symbol))
  (gethash ix-type (table state)))

An index has a table of bindings. You'd call make-index in a way resembling (make-index '(:a :b :bc :ac)), which would give you back an index with room to dissect a fact base into chunklets keyed off of

1. the first element
2. the second element
3. the second then the third element
4. the first then the third element

No, I have no idea if I'll ever actually need a setup like this. The indexed? method takes an index and an ix-type symbol and tells you whether the given index is tracking that particular type of lookup.

(defun decide-index (&optional a b c)
  (cond ((and a b c) (list :abc a b c))
        ((and a b) (list :ab a b))
        ((and a c) (list :ac a c))
        ((and b c) (list :bc b c))
        ((and a) (list :a a))
        ((and b) (list :b b))
        ((and c) (list :c c))))

(defmethod format-index ((ix-type symbol) (fact list))
  (destructuring-bind (a b c) fact
    `(,ix-type
      ,@ (case ix-type
           (:abc (list a b c))
           (:ab (list a b))
           (:ac (list a c))
           (:bc (list b c))
           (:a (list a))
           (:b (list b))
           (:c (list c))))))

Those both map an index type to the components they'll need for insertion/lookup. I've thought about factoring out the obvious pattern, and even wrote some prototype code to do it, but it turns out that for 6 indices, the macrology involved is more complicated than the trivial lookup-table thing. If fact-base were an arbitrary storage system, this would probably be complicated enough to macro away, but the whole point is that I'm only ever storing triples. Which means I'm never going to need more index types than this, and usually much less.

(defmethod map-insert! ((facts list) (state index))
  (dolist (f facts) (insert! f state)))

(defmethod insert! ((fact list) (state index))
  (loop for ix being the hash-keys of (table state)
     for ix-table being the hash-values of (table state)
     do (push fact (gethash (format-index ix fact) ix-table))))

(defmethod delete! ((fact list) (state index))
  (loop for ix being the hash-keys of (table state)
     for ix-table being the hash-values of (table state)
     for formatted = (format-index ix fact)
     do (setf (gethash formatted ix-table) 
              (remove fact (gethash formatted ix-table) :test #'equal :count 1))
     unless (gethash formatted ix-table) do (remhash formatted ix-table)))

These three utility methods at the end are exactly what you'd expect. insert! takes a fact and an index and inserts one into the other, into how-many-ever particular lookups that index is tracking. map-insert! is a shorthand for inserting a bunch of facts at once into the same index. And finally, delete! takes a fact and removes it from all index lookups, then cleans up empty lookup lists.

And that's that. You've got a quick run-through of how this works out in practice here. I get the feeling I'll be talking about deltas, forking and the applications of fact bases before long, but we shall see.

---

Footnotes

1 - [back] - Granted, because "what I'm up to" at this point "an almost trivial semi-anonymous forum for a local meetup group", and "an almost trivial notebook-style REPL for common lisp", that's true of almost any data storage technique ever, but still. The naive, index-less storage was giving cl-kanren[2] a bit more trouble than I wanted it to when I pushed the stored entry count past 10000 or so. Which is not satisfactory. So yeah, this index is basically a search-space optimization for my database traversals. I'll let you know how it goes.

2 - [back] - Which I'll also have to talk about before long, if for no reason other than to get some ideas out of my head temporarily.

3 - [back] - The second two might be compound structures, but it's still only three top-level elements.

4 - [back] - If you have none of the three components of the fact you're looking for, you can't do better than "all facts"; if you have all of them, you already have the fact you're looking for. So we're only interested in the other two cases.

5 - [back] - There's no particular reason you couldn't use some tree structure if you like, but hashes are easy, and they come with Common lisp, so...

6 - [back] - Which is in ample supply these days.

7 - [back] - Which is always a vanishingly scarce resource.

8 - [back] - Which isn't really final any more; I've updated it several times since the stuff here.

Housekeeping

Just some quick housekeeping while I draft up my next proper piece.

cl-cwd

A friend of mine mentioned that he had to hack up cl-git-fs to make it export cwd and with-cwd. Which was surprising when I heard it, but really shouldn't have been. This is the sort of problem Common Lispers seem to solve by copy/pasting a few implementation-specific snippets into projects that need the functionality. That's not good enough for me. So, here's cl-cwd; a library to get/manipulate/temporarily manipulate your current working directory in a cross-platform and cross-implementation way. Patches and bug reports welcome as always, and hopefully it's useful for you. I haven't gotten around to hacking the same components out of cl-git-fs, but I might eventually. Or, I might just use the os section of UIOP, which was only pointed out to me after I posted that cl-cwd repo. I'm not entirely sure what the right approach here is; are monolithic utility libraries preferable to very small, single-purpose packages? Not sure, but I kind of prefer the smaller, specific ones for my own purposes. Even though it never wastes enough resources to matter to me, it's deeply irritating on some level to include all of :alexandria and :anaphora for, essentially with-gensyms, aif, awhen and alambda.

fact-base updates and relevant minutia

I've gotten some work done on fact-base, which on reflection really should have been called cl-triple-store, with an eye on using it in production. We'll see if it actually happens, or if it just remains an idle fancy, but

1. you can now add indexes to your fact bases, which should make data retrieval faster[1]
2. writing deltas is now quite efficient[2]

Again, let me know if it's useful, or if it's sooooo-close-to-being-useful-if-it-only-had-this-one-feature. I might do something about it at this stage.

The only related piece of minutia is that I've found myself reading a lot about miniKanren, core.logic and logic programming in general. I think it might be a really good way to query structures like these triple-stores I've been building lately. Also, it turns out someone's already done most of the work of implementing that in CL for me, so I forked it and added/changed the few chunklets I needed to. Matthew Swank, if you're reading this and care, let me know and I'll send you patches. I assumed you wouldn't care, since the copyright line said 2008, but I might have been wrong.

Editors

Someone finally sat down and walked me through the installation for Light Table[3]. I haven't been paying attention to the propaganda, so I'm not entirely sure exactly how this is going to revolutionize editing[4], but it looks promising for a prototype. I was able to get to a productive-ish point with it within about an hour, and that's a high bar. I remember learning Emacs[5] over the course of weeks.

Another one I tried enough to appreciate is IPython Notebook. The idea of a browser-based editor has, shall we say, crossed my mind, but the idea of applying it to 1D coding hadn't occurred to me. I gotta say, I like the idea, and I'll be trying to do something about that right here. I've only got the easy part done so far; a front-end of code-mirror rigged up to a Lisp process that evaluates things and sends the result values back[6]. The hard part is going to involve a persistence layer, multiple cells, multiple notebooks and probably some smaller browsing/presentation/generation features to let me do whatever[7]. Spoiler warning: fact-base and its history/indexing operations will feature prominently. The ultimate goal is no less than replacing Emacs as my Common Lisp IDE of choice.

And that's sort of why I've been on another editor/tools kick lately.

I've been talking to some friends in the local programming community, and we seem to have collectively decided that we really, really want Light Table to succeed because it sucks not being able to recommend anything as a starting tool for Common Lisp development to programming newbies. Our options right now are what can charitably be referred to as a very intimidating operating system/rss aggregator/IRC client/moustache trimmer[8], a wannabe very intimidating blah blah blah, a very pretty, passably comfortable pair of handcuffs, a very performant, robust, ridiculously expensive pair of handcuffs, and vim. If you're recommending Scheme, there's also Racket[9], but that still doesn't count as a Common Lisp environment.

Some of those are things I'd recommend to people who are already programmers. One of them is something that I'd recommend to people looking to learn languages for the sake of learning them. But there isn't a tool anywhere on that list that compares to something like Idle or, more to the point, Light Table. I don't think it's quite at the point where I'd switch over to it myself, but I sincerely hope it gets there. And I'll be devoting some effort to pushing that along. You can too, since it's up and properly licensed and all...

---

Footnotes

1 - [back] - There's an article either in the works or already posted, depending on what order I decide to put these up.

2 - [back] - From a macro-optimization perspective; I'm sure I could pull some micro-optimizations on it too, but I'm not into that.

3 - [back] - Turns out that even the Debian Unstable repo doesn't have a recent enough version of Leiningen. I needed to latest using this.

4 - [back] - In fact, the only visible revolutionization of "randomly putting shit in your buffers that you can't edit instead of giving you a goddamn REPL", is profoundly annoying, though it's possible to disagree about these things. I guess I can imagine it looking really snazzy in presentations and demo videos.

5 - [back] - ...and before that jEdit, and before that Eclipse.

6 - [back] - And yes, it handles multiple values as well as *standard-output* emissions, in case you were wondering.

7 - [back] - At minimum the possibility to write :cl-who/:cl-css instead of markdown, a way of installing libraries that doesn't go through quicklisp, and maybe some git/drakma/shell support. I may end up having to add non-shitty static file serving to house for this...

8 - [back] - Pre-built Lisp IDE version optional.

9 - [back] - Which I do wholeheartedly recommend; it's very cool.

Flow-Based Games

So I just tried to write what I thought was a fairly simple game prototype tentatively titled "Gratuitous Resource Gathering" using Elm. Something in the style of Cookie Clicker(DO NOT click that link if you were planning on doing anything today). Here's how far I got:

import Mouse
import Time

port resourceA : Signal Bool
port building : Signal String

buildingCost = foldp (+) 0 <| keepWhen (lift2 (>) (constant 50) balance) 0 <| sampleOn building <| constant 50

tickIncrement = foldp (+) 0 <| sampleOn buildingCost <| constant 0.01
tick = sampleOn (every Time.millisecond) <| constant True

spent = foldp (+) 0 <| merges [ sampleOn building buildingCost ]

gathered = foldp (+) 0 <| merges [ sampleOn resourceA <| constant 1
                                 , sampleOn tick tickIncrement ]

balance = lift round <| lift2 (-) gathered spent

main = lift (flow down) <| combine [ lift asText balance ]

That's almost the complete game, except for one very annoying detail: it doesn't work. When I try to run it in the appropriate HTML harness, I get

s2 is undefined
    Open the developer console for more details.

The reason is that buildingCost signal. When the user purchases a building, I need to check whether they have enough resource balance to buy it. However, the balance is the sum of two other signals, gathered and spent, the second of which is affected by building purchases. Looks like circular signals aren't a thing in Elm right now. I'm not sure how to resolve this inside the language, and I already told you all about ports last time, so my natural first reaction was to think about how I'd go about computing that price check outside the Elm module. Unfortunately, once I started mentally pulling things out of Elm, I quickly arrived at the conclusion that the whole thing would probably need to be turned inside-out. In other words, I'd be using Elm purely as a way of avoiding manual DOM manipulation in one or two components of a mostly Javascript project.

Maybe that'd still be worth it, but it feels quite unsatisfying.

No real idea what to do about it though. I'll talk to some people I consider smarter than me and see what they think. Hopefully there's a reasonable way around the problem that doesn't include doing most of it in manual JS.

In the meantime, I hacked together something in Daimio.

outer
        @resource-click dom-on-click resource
        @building-click dom-on-click building
        @show dom-set-html display

        @timer every-half-second

        $building-cost 5
        $click-increment 1
        $tick-increment 0
        $balance 0

        inc-balance 
                { __ | add $balance | >$balance }
        dec-balance 
                { __ | subtract value __ from $balance | >$balance }

        can-afford
                { __ | ($building-cost $balance) | max | eq $balance }
        
        @resource-click -> {__ | $click-increment } -> inc-balance -> @show
        @building-click -> can-afford -> { __ | then $building-cost else 0} -> dec-balance -> @show
                           can-afford -> { __ | then 10 else 0 | add $tick-increment | >$tick-increment }
                           can-afford -> { __ | then "Buying..." | tap }

        @timer -> {__ | $tick-increment } -> inc-balance -> { __ | $balance } ->  @show

No highlighting mode for that one yet; I'm workin' on it. Also, the above was kind of non-trivial because I had to add my own timer event, and I still want to figure out how to factor out the process of buying a building. But it works well enough on my machine. I'll post the full project up to my github once I do a bit more thinking about it.

Autocompletion Example with Ports in Elm

Two things on the agenda today. First, Elm has gotten some improvements that might mean I end up using it in production at some point. Second, I tried a new language called Pure, which I found by searching for "dynamically typed haskell". Stick around if that sounds interesting.

EDIT:

Do not bother sticking around if that sounds interesting. I ended up talking about Elm so much that I never got into Pure.

Tue, 18 Feb, 2014

Elm Lang

For those of you just joining us, Elm is a pure-functional, statically typed, optionally-type-inferring language closely based on Haskell, which targets a JavaScript-hosted VM for deployment. That is, there's an elm-runtime.js which Elm code compiles to target, and the result is highly reactive web front-ends that don't require any mucking around with the DOM. Now that we're all on the same page...

Elm. Again.

This came up at a recent Code Retreat, and it looks interesting as fuck in context with the FBP stuff I've been doing at work recently. The problem we were solving at the event was autocompletion. That is, given a partial input, return possible completions from some dictionary. Here's a short[1] implementation in Elm.

module Autocomplete where

import String
import Keyboard
import Graphics.Input as Input

(field, content) = Input.field "Enter text"

fState : [String] -> Input.FieldState
fState comps = case comps of
                 [] -> {string = "", selectionStart=0, selectionEnd=0}
                 _  -> {string = (head comps), selectionStart=0, selectionEnd=0}

esc = Keyboard.isDown 27
ctrlSpace = dropRepeats . lift and <| combine [Keyboard.ctrl, Keyboard.space]

empty : Signal Element
empty = sampleOn (merge Keyboard.enter esc) . fst <| Input.field "Enter text"

completeElem : Signal Element
completeElem = lift ((Input.fields Input.emptyFieldState).field id "Enter text") . sampleOn ctrlSpace . lift fState <| lift completions content

completions : String -> [String]
completions partial = if | 0 < String.length partial -> filter (String.startsWith partial) wordList
                         | otherwise          -> []

main = lift2 above (merges [field, completeElem, empty]) . lift asText <| lift completions content

--- Dummy data
wordList : [String]
wordList = String.words "one two three four five six seven eight nine ten"

The point here is: there's an input that displays completions as you type. If you hit the enter or esc keys, that input is cleared, and if you hit Ctrl+Space, it's filled with the top completion. The above doesn't let you select a different completion, which it should, but it's a pretty instructive example.

Lets go through it.

module Autocomplete where

import String
import Keyboard
import Graphics.Input as Input

Module and import declarations. Nothing to see here, move along.

(field, content) = Input.field "Enter text"

fState : [String] -> Input.FieldState
fState comps = case comps of
                 [] -> {string = "", selectionStart=0, selectionEnd=0}
                 _  -> {string = (head comps), selectionStart=0, selectionEnd=(String.length <| head comps)}

The first line in this bit sets up a field, which is represented as a pair of Signals; one for the element and one for the content. Signals are a pretty good way of modeling state changes over time in a purely-functional context. You can think of one as the infinite stream of possible values it'll contain, the current of which your program will be continuously operating. An input field is a pair of signals because you'd like to be able to change it[2], as well as receive updates about its state changes. We'll do that by combining several signals on particular sample points, and FieldState is the type we can eventually funnel into a field.

esc = Keyboard.isDown 27
ctrlSpace = dropRepeats . lift and <| combine [Keyboard.ctrl, Keyboard.space]

These represent two different signals we'd like from the Keyboard module. The first will be True whenever the Escape key is down[3], the second will be True when both the Ctrl and Space key are pressed[4]. The types at each step might be useful. In particular, ctrlSpace : Signal Bool, combine : [Signal a] -> Signal [a] and lift and : Signal [Bool] -> Signal Bool. The dropRepeats is the only chunklet whose type signature will give you no further understanding [5]; it's there to prevent partial signal changes from triggering a "change" in the ctrlSpace signal itself. Also, on a syntax note, the <| is identical to Haskell's $.

Onward.

empty : Signal Element
empty = sampleOn (merge Keyboard.enter esc) . fst <| Input.field "Enter text"

completeElem : Signal Element
completeElem = lift ((Input.fields Input.emptyFieldState).field id "Enter text") . sampleOn ctrlSpace . lift fState <| lift completions content

completions : String -> [String]
completions partial = if | 0 < String.length partial -> filter (String.startsWith partial) wordList
                         | otherwise          -> []

This is the real meat right here. empty is the signal of empty elements which will "changes" whenever the enter or esc keys are pressed[6]. completeElem is the signal of filled elements that "changes" whenever the user hits Ctrl + Space. Finally, completions is the signal of completions of the current text in the main input.

main = lift2 above (merges [field, completeElem, empty]) . lift asText <| lift completions content

--- Dummy data
wordList : [String]
wordList = String.words "one two three four five six seven eight nine ten"

These remaining lines render the input and completions to screen, and set up the extremely minimal test dictionary. That's it. What we have here is exactly what was described. An input, backed by a word list, which is cleared on either Enter or Esc, and completed on Ctrl+Space.

The New Part

None of that was new.

If you've read any of the articles on this blog tagged Elm, you'd have known all of it already. The new part is that you can now have your Elm programs communicate with the outside world. In the case we're considering above, a solitary auto-completing input is pretty useless. But imagine if you could use it essentially as a minibuffer in a larger project. You'd want to be able to pass it new completion lists, and you'd want it to notify you when the user entered some input. It goes without saying that you'd like all this to be encapsulated within a known, non-global namespace, so that you could combine your Elm minibuffer with arbitrary JS projects.

So, lets do it.

module Autocomplete where

import String
import Keyboard
import Graphics.Input as Input

(field, content) = Input.field "Enter text"

fState : [String] -> Input.FieldState
fState comps = case comps of
                 [] -> {string = "", selectionStart=0, selectionEnd=0}
                 _  -> {string = (head comps), selectionStart=0, selectionEnd= (String.length <| head comps)}

esc = Keyboard.isDown 27
ctrlSpace = dropRepeats . lift and <| combine [Keyboard.ctrl, Keyboard.space]

empty : Signal Element
empty = sampleOn (merge Keyboard.enter esc) . fst <| Input.field "Enter text"

completeElem : Signal Element
completeElem = lift ((Input.fields Input.emptyFieldState).field id "Enter text") . sampleOn ctrlSpace . lift fState <| lift2 completions content wordList

completions : String -> [String] -> [String]
completions partial wordList = if | 0 < String.length partial -> filter (String.startsWith partial) wordList
                                  | otherwise          -> []

main = lift2 above (merges [field, completeElem, empty]) . lift asText <| lift2 completions content wordList

port wordList : Signal [String]

port output : Signal String
port output = keepIf (\s -> s/="") "" (sampleOn Keyboard.enter content)

That's a minimally changed .elm file. The differences are

• We've added port declarations at the bottom there. One incoming, which is just a type declaration, and one outgoing, which has a type declaration and a transmitter function.
• We've changed completions so that it takes its wordList as input
• Anywhere we used to call completions with lift completions content, we now have to call it with lift2 completions content wordList

The file you'd embed that module into would look something like this[7]

<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
  <head>
    <title>Embedding Autocomplete - Elm</title>
    <script type="text/javascript" src="/elm-runtime.js"></script>
    <script type="text/javascript" src="/build/Autocomplete.js"></script>
  </head>
  <body>
    <div id="auto" style="position: absolute; left: 50px; top: 50px; width: 600px; height: 100px; border: 2px dashed #000;"></div>
    <script type="text/javascript">
      var can = Elm.embed(Elm.Autocomplete, 
                          document.getElementById("auto"), 
                          {wordList: ["one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten"]});
      can.ports.output.subscribe(function (msg) { console.log("FROM MINIBUFFER :: ", msg) })
    </script>
  </body>
</html>

EDIT:

You can find a running demo of the above here.

Sat, 22 Feb, 2014

The relevant bits are the positioned div, which will contain our program, and the Elm.embed call, which sets it up. Note especially the third argument; you have to do that for any input ports in the component you're embedding. Finally, note the subscribe call which fits that output port we defined with a listener, in this case a naive one that just prints everything it gets to the console.

This is awesome.

It's awesome enough that I'm seriously considering Elm for some production work at work. Because I want to apply Elm in the places where it'll do massive amounts of good, and leave the other stuff to stateful JavaScript programs. Using the ports approach above, I can get exactly that. If there was something similar for Hskell, I'd probably have taken the plunge and built something with it by now[8].

In Case You're Reading, evancz

There are still a few minor headaches with the language, though thankfully I didn't have to stub my toe on most of them this time around. The only ones that ended up being annoying, or will be very shortly are

• No signal defaults from within .elm files. This bites during development. When you have an Elm module that will depend on an outside signal for its operation, you have to set a default value for that signal outside. This is ok once you've got the embedding file together, but it does mean that that second Autocomplete.elm file above will give you the error

  Initialization Error: port 'wordList' was not given an input!
      Open the developer console for more details.

  if you try to run it standalone without modifications. The workaround I've been using is to comment out the port declaration line, and add one that reads wordList = constant ["one", "two", "three", "four", "five", "six"]. It works, but I'd rather not have to do it.
• No Haskell-style sections. It only bit once in this program, and it's tolerable, but I'd much rather write (/="") than the equivalent, but syntactically noisier (\s -> s /= "").
• No Indexing. I'm almost convinced this has to be an omission on my part, and there's actually a way to do it out of the box, because it seems mildly bizarre to have List.head and String.sub in a language, but no list indexing operator or function. If there is one, just point me to it. In the meantime, you can define your own minimal version as (!!) lst ix = lst |> drop ix |> head, or maybe

  (!!) lst ix = case drop ix lst of
                  [] -> Nothing
                  sub -> Just <| head sub

  if getting out of array bounds gives you pause. Neither of these deals with negative indices, but they'll give you trivial indexing capabilities.

That's that, I guess. I was going to talk a bit about Pure. And Forth. And maybe incidentally a bit about C, but this is way longer than I was expecting already, so I think I'll call it for today.

---

Footnotes

1 - [back] - Admittedly this took something like hours total. Writing it involved a lot of experimentation and documentation browsing, and I did a quick clean-up pass afterwards. I'm really hoping the development time goes down as I get more practice with the language and type system.

2 - [back] - Actually hang on. If you're new to the FRP thing, I should clarify that you never really change things. Remember; any stateful component is represented as the lazy, infinite list of its complete history. What I really meant by the shorthand "change it" is "merge multiple signals of the same type in a way that gives one of them primacy in certain situations". It's counter-intuitive the first few times, but it's helpful to keep the perspective in mind when you're dealing with Elms.

3 - [back] - And hence will change on a keyDown or keyUp event for that key.

4 - [back] - And will therefore change on either ctrl/space keyDown, whichever is second and on ctrl/space keyUp, whichever is first.

5 - [back] - It's dropRepeats : Signal a -> Signal a, in case you really, really care.

6 - [back] - That's the (merge Keyboard.enter esc).

7 - [back] - Assuming those were accurate urls for elm-runtime.js and Autocomplete.js on your system.

8 - [back] - For the record, there might be something like it for Haskell, you'll hear excited giggling from me if I happen to find it. For the moment, I'm still evaluating the FRP section of the Hasekellwiki.

Fact Bases and Total History

No, since you ask, I haven't read anything related to datomic, though friends keep telling me I should. This is just stuff we've been talking about at the Toronto SICP reading group, and a couple of other places.

The context was mildly different; we had this conversation in relation to the notional bank accounts from chapter 3 of SICP where they introduce mutable state. The discussed version would have been simpler to optimize and manipulate, since it was entirely numeric, but I've also got fact-bases on my mind thanks to a now co-worker who's thought pretty deeply about them.

The conversation touched on total-history data-structures, and their effects on performance and convenience. The end result is this little project I just put together over the course of half an afternoon.

Let me back up...

Imagine a toy bank account.

The basic one proposed in the book is as simple as a balance, a getter, and a pair of setters named deposit and withdraw. You could add more detail, like interest rates and appropriate calculation functions, authentication mechanisms, and a designated owners list, but that's all beside the point.

Regardless of how much detail you imagined, you probably think about the principal structure being the current balance, hence simple numeric value of some precision. A total-history bank account is not that; it's a starting state (lets say 0), as well as The Total History (hence the name) of all transactions or modifications affecting it. So, instead of something like

$50.34

you're looking at a thing more like

'(...
  (3600901270 :deposit +100)
  (3600913394 :withdraw -20)
  (3600913519 :purchase -29.66))

stretching back from the beginning of the accounts' existence to now. This means that you have access to the "current value" of the account at any given time in its history. You can go back and check what happened and when, and if you like, you can ask questions like "What would it look like today if I had made an extra deposit here, and an extra withdrawal here?" In order to get the current value, you have to project it. That is, you need to go back through history and apply all the recorded events in order to see what falls out the other end. If you really are doing basic numeric modifications, it's pretty easy to parallelize some parts of that projection process, but I'll leave that as a thought experiment for the reader.

Bank accounts aren't the only things you can model this way; specifically, fact-bases can be usefully thought of in this manner.

Now then...

It turns out that total-history structures give you some interesting properties and challenges.

First, if you want all of history, you can never delete anything. You have to put in deletion tokens which remove some element or class of elements from your corpus. Because you can never delete anything, a total-history data-structure has the nice property of being append-only. Which means that you can play some neat optimization tricks in serializing it to disk, like say, clustering deltas. This comes in really handy for very large data sets, or ones which are updated very frequently. Since you're only dealing with shipping diffs around, you can easily save yourself bandwidth on keeping copies in sync, or you could easily break your corpus up across different physical drives. Undo/redo also becomes fairly simple to layer on top of a corpus that already uses this approach.

Second, time-stamping becomes pretty critical. If you took a look at that github link above, and poked around in here, you'll have noticed that I'm using local-time rather than get-universal-time because I need much finer granularity than seconds. Going to microseconds doesn't fully solve the problem, of course; if your throughput is high enough, there might still be collisions, and therefore potential data loss/duplication on updates. Putting something scalable together in Erlang would be easier, because now/0 guarantees unique values on subsequent invocations.

Still open decisions are how to go about storing deletion tokens, and when/how aggressively to prune history. A passable answer for the second is "never", so that's what I'm going with for the moment. The first one doesn't seem to have a right answer.

Storing deletion tokens...

The three approaches I can see off the top of my head are storing a deletion index, storing a deletion value, and storing a deletion template. I'm doing the third at the moment, though I'm not convinced it's the right approach. So lets start with that.

Deletion Template

Basically the deletion primitive looks like (delete! (list _ :subject _) fact-base), which goes through and deletes any fact whose second element is :subject, and also keeps that matching template as an indicator. A deletion entry then looks like

(<timestamp> :delete (list _ :subject _))

When you go to apply this particular deletion token, you'll need to create the function that checks for a match against it, then run that function across your built up state, removing anything it marks. There are three downsides here. First, this deletion token might pick up things other than the specific facts that it actually deletes in any particular traversal, which means that prospective evaluation gets more complicated. Second, because it's ambiguous, you can't easily reverse it; if you're building up state, you can't just back up over a deletion token, you need to throw away your accumulated state and start from the beginning again to get to the point you were at before applying it. Third, because it involves keeping a piece of match logic in the record, this approach means pulling out eval during de-serialization.

On the flip-side, it's easily parallelizable, and it doesn't care one whit about the order of the facts its traversing or the direction of traversal.

Deletion Index

This approach just has you keep the offset of the removed fact. A deletion token looks like

(<timestamp> :delete 37)

or maybe

(<timestamp> :delete (list 13 572 1335))

To apply this one, you go back through your built-up state and drop the nth elements. Mostly the same downsides as the Deletion Template; it gets a bit tricky when you want prospective change projection and it isn't cleanly reversible. It's mildly easier on memory, since we're just slinging integers around, and it doesn't need eval, but it suddenly matters which direction you're traversing your corpus in, it matters how your corpus is ordered, and I could see it getting in the way of parallelization later.

Deletion Value

A deletion value token looks something like

(<timestamp> :delete (<id> :subject "whatever the third value is"))

You apply this by going through the accumulated corpus and removing the first fact that matches it. Granted, it's slower in general (because applying it in general involves an arbitrary tree-compare), and it's more wasteful of disk space (because we have to store those arbitrary trees as well as comparing them with facts to remove). But. Depending on how strictly you enforce it, this one is more easily reversible, and it doesn't need eval either, since it's just storing a value.

Wrapping up...

A couple of other thoughts I'd like to leave percolating:

• It might be possible to get the best of both worlds by making sure that a deletion token remembers the particular members it removed at application time. That would let both the Template and Index approach reverse easily, though it would complicate the projection process somewhat.
• It might be useful to have a layer of meta-tokens. That is, insertions in history that modify other history entries. Off the top of my head, only :ignore or :duplicate seem like they'd be significantly useful. On the plus side, you now have a meta layer to these histories which gives you more flexibility in using them. On the other hand, you now need to have one of efficient reversals, a two-pass loading procedure, or really really shitty performance for heavily meta-tagged histories.

That's that. Not the most flowing narrative I've ever produced, but I think it touched on one or two interesting ideas. And anyhow, I'm still chewing over most of this. I'll let you know how it goes, and if I end up finding a real use for it.