language agnostic

The Blog Has Moved

2014-06-13T07:46:00.001-07:00

langnostic.blogspot has moved to langnostic.inaimathi.ca (also, atom feed here).

The archives will remain for posterity, but any new posts are probably going to happen there rather than here.

Arbitrary Update 932

2014-05-20T19:36:00.000-07:00

It's been a while. Sadly/happily, I've been busy working on the house write-up for AOSA 4 and thinking pretty hard about a cl-notebook-related submission to this, so any spare writing time I've had has been getting pointed directly away from this blog. This is going to be a pretty incoherent update, mainly focused at getting various things out of my head rather than making any kind of sense. It's a quick cross-section/pressure-release related to things I've been thinking about lately, not a catalyst for learning or external discussion.

cl-notebook/fact-base

I'm noticing that there's a very common pattern in the cl-notebook use-case for fact-base. Specifically, the deletion of a record followed by the insertion of a very similar new record.

  (let ((cont-fact (first (lookup book :a cell-id :b :contents)))
        (val-fact (first (lookup book :a cell-id :b :result)))
        (cell-lang (caddar (lookup book :a cell-id :b :cell-language)))
        (cell-type (caddar (lookup book :a cell-id :b :cell-type))))
    (delete! book cont-fact)
    (insert! book (list cell-id :contents contents))
    (publish! :cl-notebook-updates (update :book (notebook-name book) :cell cell-id :action 'content-changed :contents contents))
  ...

What I'm trying to express there is a change in an existing record. It's mildly annoying for two reasons. First, it means that I need to effectively store every change twice in the form of a before-and-after shot (which, granted, I kind of need to keep doing if I want easy reversibility on edits). Second, and more importantly, it means that a history interface for something being backed by a fact base is going to need to be more complex than I'd like. Instead of naively displaying states, I'll need to make sure to intelligently handle the situation where a user moves history to a point between a deletion and new insertion of a particular fact. I'm going to shortly be making such an interface for cl-notebook, so this is going to get painfully relevant very soon. This has me seriously considering adding a third token to fact-base, :modify, specifically to address this.

Memory

Whatever language you're currently using, managing memory is something that you're ultimately doing. Whether it's manually, or through various schemes that do it on your behalf. The ultimate goal of all of these approaches is twofold:

make sure that a new allocation doesn't clobber a chunk of memory that's still being used by something
make sure that you never build up enough memory junk that you can't allocate a new block when you need to

The general approaches seem to be

Not

For sufficiently short-running programs, a reasonable approach is to just build up junk constantly and let it come out in the wash after the program ends. This is a pretty narrow use case, since you can't clobber memory held by another program, and you can't use more memory than exists on the machine running you, but it's sometimes an option. I'm... not actually aware of a language that takes this approach.

Manual

This is the C/C++ approach. You, the programmer, get to declare exactly what pieces are being used and when. Whether that's on a procedure-by-procedure or datastructure-by-datastructure basis, you're ultimately responsible for memory yourself directly. The upside is that there's no garbage collection overhead. The downside is that every procedure/datastructure has to manage memory acceptably, otherwise things start blowing up in various hard-to-diagnose ways.

Mark-and-sweep and variants

One of the automatic memory management approaches. The general idea here is

keep a free memory list, and track of all things allocated by the program
every so often (either at a time interval, or every n allocations, or maybe just when you try to allocate memory and your free list is empty), traverse the list of all things and free the ones that aren't being used any more

A variant on this known as generational garbage collection is keeping several buckets of allocated things, rather than one. You'd partition objects based on how long they've been around so that you don't waste much time traversing long-lived data every time through. This is the variant that I've seen discussed most often, and I kind of get the impression that it's also the one getting the most research time thrown at it, but I'm not entirely sure why. Oh, incidentally, languages like Common Lisp, Java and Python use this one.

Reference-counting

Another automatic approach, also known as deterministic garbage collection. As far as I understand, Perl does this. The idea is to keep a special eye on language primitives that create or destroy references to objects, and to keep track of how many references to a particular object exist. Every time a relevant primitive is called, modify the reference count for the target, and collect it if that count is zero afterwards. I'm not sure what the pitfalls are in practice, but there seems to be a lot less discussion about this approach than about the previous.

Circular Memory

I only vaguely understand this one, and from what I understand, it's fairly limited, but here goes. The situation you'd want to use this or something like it is when a particular allocation is only needed for a short time before being discarded, and can be discarded sequentially. If you're in that situation, what you can do is figure out how much memory you have, then allocate things to it in order and hop back to the beginning when you're done. You need a pointer to the next block you can use (which you update every time you need to allocate a new thing), and a pointer to the first still-relevant block (which you update every time you free something). If the two ever overlap, you know you have a problem. Shapes other than circular are possible. For instance, you could have some sort of self-referential tree structure that accomplishes the same thing for mildly different use cases.

Decentralization

This isn't a thing related to memory; this is separate.

I've got this pattern of

assuming problem foo is solved
going on about my business for a while
taking a close look at foo for the purposes of implementing something related to it
suddenly realizing that foo is not only unsolved, but can't possibly be solved
thinking about it really hard in an obsessive/compulsive sort of way
learning to live with a deep dissatisfaction about some small part of the universe

This has happened for identity, free will, type systems, authentication, and most recently decentralization.

More will follow, I'm sure.

I heard about the peer-to-peer connection mechanisms in development for HTML5, and figured it would be nice to put something nice and small together using it. To that end, I'd absorbed and discussed the idea of mental poker with a couple of people, and thought I had the hard parts under control. It turns out that this new set of functionality is still going to need central servers to set up the connections though, at which point I dismissed the approach only to notice a cognitive rupture. Every "distributed" protocol seems to need a central server to bootstrap. The web needs DNS, torrents need trackers, cell-phones need satellites and/or transmission stations, etc etc.

This fundamentally shifts the problem in my mind. If we're going to be burdened with some central functional cluster anyway, it looks like a better problem to solve might be "how do we perform tasks with multiple 'central' clusters" rather than "how do we have as few central structures as possible".

Fuck you if it doesn't make sense. It's late and I'm piping a stream of consciousness here. I was also going to talk about a few other things on my mind; assembler and some new revelations about Flow Based Programming in particular, but I'm about to lose coherence entirely, and nobody wants that.

I'll let you know what, if anything, comes of any of these meditations. For the moment, you'll have to tolerate some more radio silence.

cl-notebook Thoughts

2014-04-21T17:28:00.000-07:00

No nuts and bolts this time. Here's a random collection of insights I've had while trying to put together the version 0.1 of a notebook style editor:

Being async Pays

My initial assumption was that evaluation would be an inline thing. That is, you send out a POST request, that code is evaluated synchronously, saved out to your fact base, and the HTTP response consists of that evaluated result which you can then display prettily on the front-end. Turns out that's a big fat no. Even discounting any issues with the Common Lisp return model, and the eventual attempt at making this a multi-user editor, the synchronous approach doesn't quite work. Which I found out the first time I accidentally wrote a loop without the required while. Something like

(loop for next = (pop stack) do (something-to-next))

The trouble should be obvious. That's the sort of computation that you want off in its own isolated thread. And you want to be able to kill that thread if it turns out to be as boneheaded a mistake as that was, which means that you have to notify the front-end of computations in progress, go off and perform it, then notify the front-end again when you're done. And that's not something you can do synchronously.

In the end, I end up spawning a single tracked thread to do the work of evaluation. I notify the front-ends when it begins work, and then again when it completes. At any point in between, a front-end can send a termination signal to kill that thread rather than waiting it out to completion. You can see the implementation here, here, and here. This will entirely coincidentally make it much easier to extend cl-notebook to a multi-user editor later.

Being surgical pays. Sometimes. Not in the way you'd think.

The first version of this editor basically spat out the complete current notebook state at the front-end on each action, and the front-end re-drew the entire thing on every change. You'd think that the sheer inefficiency of this approach would get to me, but you'd be wrong. It was actually fast enough that had performance been the only factor, I'd have left it at that. The problem with that approach is that you end up clobbering giant chunks of client-side state each time. In particular, re-drawing every cell (and hence, re-initializing each of their CodeMirror instances) meant that I was blowing away undo information for each editor window every time anything happened. And that's annoying as fuck. I'm not sure anyone's formalized the point into a commandment yet, but you really should act as though they have: Thou Shalt Not Mangle Thy Clients' Data. That applies no matter how temporary the data is. Even if your job is to take said data and transform it in some way, say for instance by evaluating it, you should do so with a copy instead of a destructive change. And even when you absolutely must be destructive, be as selectively destructive as you possibly can.

Thinking About Space Doesn't Pay. No, not even that much.

I almost left this one out entirely because it seemed so self-evident, but on reflection, it's something I've had to learn too. Space doesn't even begin to matter for systems like this. I'm talking both about memory and about disk space. Yes, there are some applications for which this is not the case, but it's true as a rule.

The fact-base project in particular has been sticking in my craw in this sense. I kept thinking things like 'Holy shit, I'm keeping history for every cell, on every edit forever. This is going to be huge! I'll have to figure out a way to condense these files, or start them off from a non-zero state so that I can throw out history at some point!'

Completely pointless.

At the beginning of the cl-notebook effort, I started a scratch file which I've been steadily editing, putting through various save/auto-save tests and just all round mauling with updates. This thing has been around for months at this point, and it's taken much harder beatings than the average notebook ever will. Wanna know what its current total size is?

inaimathi@self:~/.cl-notebook/books$ ls -lh base-zg1mm23z
-rw-r--r-- 1 inaimathi inaimathi 675K Apr 20 21:47 base-zg1mm23z
inaimathi@self:~/.cl-notebook/books$

That's smaller than many Word and PDF documents I've worked with, and those don't bother keeping my entire editing history around. So I figure I can get away with treating disk space as if it were infinite for my purposes. Absolute worst case scenario, I'll compress it. And since I'm dealing with plaintext files, that should be rather effective.

inaimathi@self:~/.cl-notebook/books$ pack -t tar.gz base-zg1mm23z
base-zg1mm23z
inaimathi@self:~/.cl-notebook/books$ ls -lh base-zg1mm*
-rw-r--r-- 1 inaimathi inaimathi 675K Apr 20 21:47 base-zg1mm23z
-rw-r--r-- 1 inaimathi inaimathi  23K Apr 20 21:47 base-zg1mm23z.tar.gz

Yeah. I think that'll be good enough.

Return Values are Complicated

I mean, I knew that already, but it turns out there are even more intricacies here. I initially assumed I'd be able to just keep a single return value per cell (by which I mean the return from a single Lisp function, which can be zero, one or more values). Then it hit me that a cell might have more than one expression in it. Then it hit me that return values aren't enough; you need to be able to handle *standard-output* emissions and warnings on a per-expression basis rather than on a per-cell basis, and that we'd want type annotations in some places since we'll be serializing various things to strings and it would otherwise get confusing. Then I hit me and sat down to write down something workable. Each cell now stores a result, which is zero or more values, each of which is actually a value and a type.

That lets the front end figure out what it needs to do on a per cell basis, which means that the server-side implementation of a cells' noise becomes very mechanically simple. It's basically just an extra fact we keep around as a label, which the front-end queries to decide how to transform the high-detail result.

`cell-type` is not the same thing as `cell-language`

Early on, I had this idea that I'd be semi-implicit about what's in a cell. At that point there were two cell-types; common-lisp and cl-who. The idea would be that this single cell-type would determine both display and evaluation properties of the contained code. Nope, as it turns out. And the thing that finally made this clear to me is thinking about how I'd treat test code. It's still Common Lisp, you see, so I'd still be evaluating it the same way as any other code cell, but I didn't want it showing up in certain exports.

The solution I ended up settling on is to be explicit about everything. Each cell now has a cell-type as well as a cell-language. The first one being one of markup (for prose blocks), code (for code blocks), and tests (for code blocks that I'd want to separate from actual runtime code).

Naming things is difficult

I think there's a joke about this somewhere. Something along the lines of

The only two difficult problems in programming are naming things, cache invalidation and off-by-one errors.

and man did that ever bite me this time. It's obviously bad to tie the file-system name of something to its display name, if for no reason other than it opens up various injection vectors that you'd rather not open up. It turns out it gets even more complicated when you're dealing with history trees of various documents, and you're trying to reduce headaches for your users. Here, think about this problem for a bit. Say you had a document type that you'd let your users name. We're obviously not naming the on-disk file after the display name of the document, so this is a matter of storing a record in the document that'll keep a user-entered name around for reference purposes. That gives you the additional benefit of being able to roll back renames, and the ability to see what a given document was called at some point in the past. Now, say you want to be able to branch said document. That is, instead of being a single history line, you want to be able to designate certain timelines as belonging to different branches than others. What you need now is four different levels of naming. Five, depending on how ham-handedly you've decided to store and relate those branches. At minimum you need

The filename of the document, which is different from
The display name of the same document (which might be different in different branches, and at different points in time), which is different from
The display name of a particular branch of the document (which might need to be human readable, or user entered) which is different from
The collective, still human-readable name for a set of branches belonging to one document.

If you've stored a branch collective as a file/folder on disk, you'll have to name that too. So, what would you do?

Confronted with this problem, I punted. Branching is basically going to be a copying operation. What you'll eventually get, once I put the branching system together and you try to use it, is a complete, self-contained fact base that happens to (possibly temporarily) have the same display-name as its origin (plus the word 'branch'), and a fact or two that point to a specific time point in that origin. From there, they'll diverge and be entirely separate entities. No, I'm not entirely sure this is the best approach, or even an acceptable approach, but it seems to be the only way to avoid asking the user to manage four different names in the space of one document. So I'll take it.

There's probably more where those came from, but they're all I could pull out of my head at short-ish notice. I'll try to let you know how the rest of the project goes, as it happens.

cl-notebook Introductory Thoughts

2014-04-20T18:49:00.000-07:00

So it's about time I talked about this thing, and what the hell exactly I'm thinking. Because I've been working on it for a while, and while it's still kind of buggy, I've already found myself wanting some of the features it has when working with Emacs, or other text editors I've had to work with.

Notebooks

Actually, before I get to that, a little exposition. As far as I know, notebook-style editors already exist for Python, R, and Clojure. And a second one for Clojure. The general idea is to have a web-based interface, with code being divided into small, re-arrangable chunks called cells, each of which are associated with their evluation results. Some cells are code in whichever language the notebook supports, others are just prose, usually in markdown. The idea is that you get a dynamic environment that lets you selectively evaluate small chunklets of code, and intersperse relevant documentation in the form of prose and tests.

As someone who's been eyeing literate programming techniques for a while, this predictably appeals to me. So I've built my own, for my language of choice.

`cl-notebook`

You can find it at the other end of that github link I start out with. Last time I mentioned this project in passing, I noted that the ultimate goal was replacing Emacs as my Common Lisp IDE of choice, and that's no small task. Despite the existence of subpar, I don't have proper s-expression navigation yet, and I haven't wired up proper auto-completion or argument hinting yet, and there's a bunch of other stuff I still want to build, ranging from the necessary to the frivolous. On the whole, I think I'm on the right track, because certain things are somewhat easier here, and because there are some features that I find myself missing when I hop back into emacs.

Lets just get those out of the way right now, actually. Firstly, I get to program in my browser, which is surprisingly elegant once I hop into full-screen mode. It lets me tab over to search for relevant links to talk about, and since my browser can be set to start up with previously open tabs, I get to resume editing exactly where I was in a later session. Secondly, because of the back-end storage system I'm using, I get to have a running history of all the edits I've ever made, which is updated every time I evaluate a cell (I'm working on having it implicitly updated every so often between evaluations, but don't have that part checked in). Thirdly, I've got exporters wired up that let me put together a book, then export it as an HTML page, or as a .lisp file. And I'm planning to add two more, one to just extract tests and a second to just hand me an executable from the given book.

The first one is minor, and makes it all the easier to randomly check my email or github notifications, so pros and cons. The third could concievably be wired together in Emacs. The second one is huge. I don't know about you, but I've been programmed to hit save every few seconds in whatever editor I've got open just because crashes happen, and I don't want them to be too painful. I guess I could have wired up emacs to do that every so often, but it sounds fiddly as hell. You don't particularly want a standard editor saving every three seconds or so; you might be in the middle of an edit the currently keyed-in part of which doesn't make sense by itself, and most editors 'save' by overwriting your existing file. Which is exactly what you don't want when you've got an unfinished code edit. Hopefully, adding total-history retention to the equation softens the blow.

Core Concepts

Code is organized into books. Each book is the complete history of a bunch of cells. A cell can contain code, tests, or markup in a particular language (currently just Common Lisp, but given how many languages I blog about, it'll probably need at least highlighting support for a few more). The cells' language and type impacts the evaluation approach we take on the back end, as well as which exports it appears in, and in what form. Specifically, common-lisp/markup cells are evaluated as :cl-who forms, don't appear in .lisp exports and only contribute their results to an .html export. By contrast common-lisp/code is straight up evaluated (capturing warnings, errors and standard-output), contribute their contents to .lisp exports, and both their contents and results to .html exports.

In addition to a type, language and id, a cell has a contents, result, and a noise. The contents is what the user has typed in, the result is what that contents evaluates to and the noise dictates how the results are displayed. This is a normal cell:

(+ 1 2)
(+ 2 3)
(format t "Testing ")
(+ 3 4)
(format t "testing")
(format t ". One two.~%")
(format t "Testing.")
(+ 4 5)

Testing testing. One two. Testing.

9 :: integer

This is the same cell with a noise of verbose:

(+ 1 2)
(+ 2 3)
(format t "Testing ")
(+ 3 4)
(format t "testing")
(format t ". One two.~%")
(format t "Testing.")
(+ 4 5)

3 :: integer

5 :: integer

Testing

NIL :: null

7 :: integer

testing

NIL :: null

. One two.

NIL :: null

Testing.

NIL :: null

9 :: integer

And again with terse

(+ 1 2)
(+ 2 3)
(format t "Testing ")
(+ 3 4)
(format t "testing")
(format t ". One two.~%")
(format t "Testing.")
(+ 4 5)

9 :: integer

There's also a silent setting which lets you ignore the evaluation result entirely.

You can edit a cell (changing its contents), evaluate it (changing its result) delete it, change any of its mentioned properties, or change the order of cells in a notebook. Each of these is an event that gets initiated by a POST request and gets completed with an event-stream message to any listening front-ends (which means I'll relatively easily be able to make this a multi-user editor when I get to that point). Enough low level stuff, here's an example.

Example

This is a piece of code I actually wrote using cl-notebook.

A parameter is a thing that starts with #-. It might be nullary or unary. A parameter followed by a parameter or an empty list is interpreted as nullary. A parameter followed by a non-parameter is unary. Command line args are more complicated in the general case, but not in cl-notebook

(defun parse-args! (raw)
   (pop raw)
   (flet ((param? (str) (eql #\- (first-char str)))
          (->param (str) (intern (string-upcase (string-left-trim "-" str)) :keyword))
          (->arg (str) (or (parse-integer str :junk-allowed t) str)))
      (loop for next = (pop raw) while next
            if (and (param? next) (or (not raw) (param? (car raw))))
              collect (cons (->param next) t) into params
            else if (param? next)
              collect (cons (->param next) (->arg (pop raw))) into params
            else collect next into args
            finally (return (values params args)))))

(defun get-param (names params) 
  (loop for (a . b) in params 
     if (member a names) do (return b)))

GET-PARAM :: symbol

(parse-args! '("./prog-name" "-f" "-h" "something"))
(parse-args! '("./prog-name" "a" "b" "c" "d"))
(parse-args! '("./prog-name" "-p" "4040"))

(get-param '(:f :force) (parse-args! '("./prog-name" "-f" "-h" "something")))
(get-param '(:p :port) (parse-args! '("./prog-name" "-p" "4040")))
(get-param '(:p :port) (parse-args! '("./prog-name" "--port" "4040")))
(get-param '(:p :port) (parse-args! '("./prog-name" "--frob" "4040")))

((:F . T) (:H . "something")) :: cons
NIL :: null
NIL :: null
("a" "b" "c" "d") :: cons
((:P . 4040)) :: cons
NIL :: null
T :: boolean
4040 :: integer
4040 :: integer
NIL :: null

It's a small utility function for parsing command line arguments in :cl-notebook. You can see all the relevant features on display there; it starts with some documentation prose in a markup cell, has definitions in a code cell, and finally a bunch of example invocations of each thing in a tests cell. They're not really tests, because they don't encode my assumptions about the return values of those calls, but you could imagine them doing so. The point is, they won't be part of a .lisp export, but will show up in an html export like this one.

That's it for the introductory thoughts. I'll try to gather some insights into such editors into the next piece I put together. And I'll continue dogfooding until it gets good enough to call "delicious".

Querying Fact Bases Redux

2014-04-12T19:10:00.000-07:00

So I put together that thing I talked about last time, only to discover three things.

Firstly, the only places I actually needed lazy operation could be handled by passing a body directly to the query macro.

Secondly, when I loaded the thing up, worked up a 40k fact corpus[1] and ran

(for-all (and (?id :user ?name) (?id :time ?time) (?id :number 62))
         :in *base* :get (list ?id ?time ?name))

I'd get this:

You may have noticed that this isn't an animated gif. It hangs there for something on the order of thirty seconds, more if profiling is on, and then returns the expected result. So that won't really do. There's some interesting points I'll talk about later, that have to do with clause order and the underlying operations. But, even though this is probably the worst way to write this particular query, it should return in under a second.

Thirdly, that I had exactly zero use cases for or goals. This might change, but until then, it looks like I don't even need unification[2].

So as a result, I sat down and took the precise opposite approach to traversal that I tried last time. Instead of trying to keep it elegant and lazy, lets make it hacky and eager. Here's our problem, once again:

(for-all (?id :user ?name) 
         :in *base* :get (list ?id ?name))

should basically be the same as

(loop for (a b c) in (current *base*) when (eq b :user) collect (list a c))

and

(for-all (and (?id :user ?name) (?id :time ?time) (?id :number 62) 
         :in *base* :get ?time))

should more or less be equivalent to

(loop for (a b c) in (current *base*) 
   when (eq b :user)
   append (loop for (d e f) in (current *base*)
             when (and (eq d a) (eq e :time)))
             append (loop for (g h i) in (current *base*)
                       when (and (eq g d) (eq h :number) (= i 62))
                       collect f))

Except, you know, it should be smarter about using indices where it can. But that's a pretty straight-forward specification.

`lookup` and `decide-index` changes - take 1

The first thing I had to do was change lookup and decide-index a bit, because I wanted them to be mildly less naive. And yeah, I broke down and added some macrology to pull out all the repetition in the index-related functions. Turns out that was a good thing.

(defmacro lookup-index (state &rest indices)
  (with-gensyms (st)
    `(let ((,st ,state))
       (cond ,@(loop for i in indices 
                  for syms = (key->symbols i)
                  collect `((and (indexed? (index ,st) ,i)
                                 ,@syms)
                            (list ,i ,@syms)))))))

(defmethod decide-index ((state fact-base) &optional a b c)
  (lookup-index state :abc :ab :ac :bc :a :b :c))

Short version is, the function now takes a fact-base in addition to an a, b and c, and checks whether a particular type of index is kept for a fact base before otherwise seeing whether it would be appropriate for the current query.

(defmethod lookup ((state fact-base) &key a b c)
  (if (every #'not (list a b c))
      (current state)
      (let ((ix (aif (decide-index state a b c)
                     (gethash (rest it) (gethash (first it) (table (index state))))
                     (current state))))
        (loop for f in ix
           when (and (or (not a) (equal a (first f)))
                     (or (not b) (equal b (second f)))
                     (or (not c) (equal c (third f))))
           collect f))))

lookup now has to be mindful of this, and has to check that the indexed facts match the incoming query. Because we're now potentially using a more general index than the query calls for. My gut tells me this is still a net increase in performance since last time, even though our best case is now On with the size of the result rather than 01. If it comes to it, I'll go back and make that more efficient.

Actually, lets fix it right now.

`lookup` and `decide-index` changes - take 2

(defmethod lookup ((state fact-base) &key a b c)
  (if (every #'not (list a b c))
      (current state)
      (multiple-value-bind (index ideal-index) (decide-index state a b c)
        (let ((ix (if index
                      (gethash (rest index) (gethash (first index) (table (index state))))
                      (current state))))
          (if (and index (eq (first index) ideal-index))
              ix
              (loop for f in ix
                 when (and (or (not a) (equal a (first f)))
                           (or (not b) (equal b (second f)))
                           (or (not c) (equal c (third f))))
                 collect f))))))

That more complicated version of lookup expects two values instead of one; which index we're using, and which index we'd ideally use. If the two are the same, we just return the results of our lookup, otherwise we have to do the narrowing traversal. That's about as efficient as it's going to get without making it lazy. Which I guess I could, but not right now. However, we also need a modified decide-index to pull this little trick off. And that's going to be fugly.

(defmacro lookup-index (state &rest indices)
  (with-gensyms (ix ideal applicable?)
    `(let ((,ix (index ,state))
           (,ideal))
       ,@(loop for i in indices 
            for syms = (key->symbols i)
            collect `(let ((,applicable? (and ,@syms)))
                       (when (and (null ,ideal) ,applicable?) (setf ,ideal ,i))
                       (when (and (indexed? ,ix ,i) ,applicable?)
                         (return-from decide-index 
                           (values (list ,i ,@syms) ,ideal)))))
       (values nil ,ideal))))

(defmethod decide-index ((state fact-base) &optional a b c)
  (lookup-index state :abc :ab :ac :bc :a :b :c))

Say what you will about imperative programming; it's efficient. That's a single pass over the relevant indices that returns both the least general applicable index, and the ideal index for a given query. Which means we can now profitably compare the two in lookup, which means that our best case is back up to O1, since we don't need to traverse queries for things we've indexed.

With those modifications, I can pull some fancier crap in translating for-all calls into loops. Specifically, I can do this:

This

(defun goal->destructuring-form (goal &key (bindings (make-hash-table)))
  (labels ((rec (elem)
             (cond ((listp elem)
                    (mapcar #'rec elem))
                   ((or (eq '? elem) (not (variable? elem)))
                    (gensym))
                   ((and (variable? elem) (gethash elem bindings))
                    (gensym))
                   ((variable? elem)
                    (setf (gethash elem bindings) t)
                    elem)
                   (t (error "Somethings' up. goal->destructuring-form~%     ~s~%     ~s~%     ~s"
                             bindings goal elem)))))
    (mapcar #'rec goal)))

(defun goal->lookup (base goal &key (bindings (make-hash-table)))
  (flet ((->ix (elem)
           (cond ((and (variable? elem) (gethash elem bindings))
                  elem)
                 ((any-variables? elem)
                  nil)
                 (t elem))))
    (destructuring-bind (a b c) goal
      `(lookup ,base 
               :a ,(->ix a) 
               :b ,(->ix b)
               :c ,(->ix c)))))

(defun goal->or-expression (a b c goal)
  (flet ((test (term elem) `(equal ,term ,elem)))
    `(and ,(test a (first goal))
          ,(test b (second goal))
          ,(test c (third goal)))))

(defmethod handle-goals ((goal-type (eql 'and)) base goals collecting)
  (let ((bindings (make-hash-table)))
    (labels ((single-goal (destruct lookup tail)
               `(loop for ,destruct in ,lookup ,@tail))
             (rec (goals)
               ;; We want to generate the lookups first, 
               ;; because the bindings are going to be generated
               ;; from the result of the lookup. Meaning, if the bindings 
               ;; are established in a given destruct clause,
               ;; they won't be usable until the NEXT lookup.
               ;; Therefore, even though it isn't immediately obvious, 
               ;; order matters in this let* form

               (let* ((lookup (goal->lookup base (first goals) :bindings bindings))
                      (destruct (goal->destructuring-form (first goals) :bindings bindings)))
                 (if (null (cdr goals))
                     (single-goal destruct lookup `(collect ,collecting))
                     (single-goal destruct lookup `(append ,(rec (rest goals))))))))
      (rec (rest goals)))))

(defmethod handle-goals (goal-type base goals collecting)
  ;; Same story here as in handle-goals (eql 'and) method
  (let* ((bindings (make-hash-table))
         (lookup (goal->lookup base goals :bindings bindings))
         (destruct (goal->destructuring-form goals :bindings bindings)))
    `(loop for ,destruct in ,lookup collect ,collecting)))

(defmacro for-all (goal-term &key in get)
  (with-gensyms (base)
    (let ((template (replace-anonymous (or get `(list ,@(variables-in goal-term))))))
      `(let ((,base ,in))
         ,(handle-goals (first goal-term) base goal-term template)))))

We'll go through it in a minute, but the point of these changes is that writing

(for-all (and (?id :user ?name) (?id :time ?time) (?id :number 62))
         :in *base* :get (list ?id ?time ?name))

should expand directly into something like

(LET ((#:BASE1122 *BASE*))
  (LOOP FOR (?ID #:G1123 ?NAME) 
     IN (LOOKUP #:BASE1122 :A NIL :B :USER :C NIL)
     APPEND (LOOP FOR (#:G1124 #:G1125 ?TIME) 
               IN (LOOKUP #:BASE1122 :A ?ID :B :TIME :C NIL)
               APPEND (LOOP FOR (#:G1126 #:G1127 #:G1128) 
                         IN (LOOKUP #:BASE1122 :A ?ID :B :NUMBER :C 62)
                         COLLECT (LIST ?ID ?TIME ?NAME)))))

rather than the lazy-ish generator tree from last time. Thanks to our re-structuring of lookup, this is about as efficient as it's going to get without re-jigging goal order. The only edge case we have is what happens if the entire goal is perfectly indexable, except it seems that the programmer would use lookup directly in those situations[3].

On to the code review. Reading. Whatever.

(defun goal->destructuring-form (goal &key (bindings (make-hash-table)))
  (labels ((rec (elem)
             (cond ((listp elem)
                    (mapcar #'rec elem))
                   ((or (eq '? elem) (not (variable? elem)))
                    (gensym))
                   ((and (variable? elem) (gethash elem bindings))
                    (gensym))
                   ((variable? elem)
                    (setf (gethash elem bindings) t)
                    elem)
                   (t (error "Somethings' up. goal->destructuring-form~%     ~s~%     ~s~%     ~s"
                             bindings goal elem)))))
    (mapcar #'rec goal)))

step one of the transformation is to put together the destructuring-form for a particular goal

;;             this thing
;;          vvvvvvvvvvvvvvvvvvv
  (LOOP FOR (?ID #:G1123 ?NAME) IN (LOOKUP #:BASE1122 :A NIL :B :USER :C NIL)
...

In order to do that, we have to replace everything other than variables with gensym calls, but keep the same tree structure. loop does deep destructuring, so we can get away with using this as a pattern-matching strategy. We also need to replace already bound variables from previous destructuring-forms with the same gensym calls so they don't get re-assigned unnecessarily.

(defun goal->lookup (base goal &key (bindings (make-hash-table)))
  (flet ((->ix (elem)
           (cond ((and (variable? elem) (gethash elem bindings))
                  elem)
                 ((any-variables? elem)
                  nil)
                 (t elem))))
    (destructuring-bind (a b c) goal
      `(lookup ,base 
               :a ,(->ix a) 
               :b ,(->ix b)
               :c ,(->ix c)))))

The next thing we need to put together is a given goals' lookup clause

;;                                       this thing
;;                                 vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
  (LOOP FOR (?ID #:G1123 ?NAME) IN (LOOKUP #:BASE1122 :A NIL :B :USER :C NIL)
...

We're being conservative at the moment, but there's an optimization or two I could still make here. The way we're dealing with these is:

if a given goal-component is a variable, then look it up by its value in the current bindings[4]
if a given goal-component is a compound form which contains any variables, don't index by it[5]
otherwise, use it as an index

Onwards to handle-goal; the real meat of this approach. Lets take a look at how we deal with singleton goals first

(defmethod handle-goals (goal-type base goals collecting)
  ;; Same story here as in handle-goals (eql 'and) method
  (let* ((bindings (make-hash-table))
         (lookup (goal->lookup base goals :bindings bindings))
         (destruct (goal->destructuring-form goals :bindings bindings)))
    `(loop for ,destruct in ,lookup collect ,collecting)))

Easy, right? grab the results of goal->lookup and goal->destructuring-form and stitch them into a loop along with the collecting clause. Nothing fancy here, except for that cryptic note about a different method definition.

(defmethod handle-goals ((goal-type (eql 'and)) base goals collecting)
  (let ((bindings (make-hash-table)))
    (labels ((single-goal (destruct lookup tail)
               `(loop for ,destruct in ,lookup ,@tail))
             (rec (goals)
               ;; We want to generate the lookups first, 
               ;; because the bindings are going to be generated
               ;; from the result of the lookup. Meaning, if the bindings 
               ;; are established in a given destruct clause,
               ;; they won't be usable until the NEXT lookup.
               ;; Therefore, even though it isn't immediately obvious, 
               ;; order matters in this let* form
               (let* ((lookup (goal->lookup base (first goals) :bindings bindings))
                      (destruct (goal->destructuring-form (first goals) :bindings bindings)))
                 (if (null (cdr goals))
                     (single-goal destruct lookup `(collect ,collecting))
                     (single-goal destruct lookup `(append ,(rec (rest goals))))))))
      (rec (rest goals)))))

And this is the full story[6]. Because of the specific way we want lookup and destruct to interact with their containing bindings, their order matters quite a bit. Play around with the macroexpander if you don't quite see it from just the definition.

Anyhow, the way we deal with and goals is by building up a chain of loop forms, each one dealing with a single goal while taking the previous goals into account. All but the last one need to append their results, while the last needs to collect them. The only part we've got left is the now trivial step of putting together the for-all macro interface to the rest of this compilation pipeline[7].

(defmacro for-all (goal-term &key in collecting)
  (with-gensyms (base)
    (let ((template (replace-anonymous (or get `(list ,@(variables-in goal-term))))))
      `(let ((,base ,in))
         ,(handle-goals (first goal-term) base goal-term template)))))

Tadaah!

I haven't yet put together an equivalent facility for the old apply keyword arg, but because of how we've changed up the underlying code processors, collecting can now trivially handle things like

(for-all (and (?id :user ?name) (?id :time ?time) (?id :number 62))
         :in *base* :collecting (list ?name (+ ?id ?time 62)))

This concludes the part of this post wherein I talk about implementation details. The rest is just one or two interesting notes about traversals. If you're getting bored, or tired, this is a pretty good break-point for you.

Traversal Notes

Near the beginning of this piece, I said

...this is probably the worst way to write this particular query...-Inaimathi

referring to

(for-all (and (?id :user ?name) (?id :time ?time) (?id :number 62))
         :in *base* :get (list ?id ?time ?name))

and the reason should be fairly obvious now that we know exactly how we go about finding these answers. Remember, the expansion for this form, after compensating for the different keyword argument in our new for-all, is

(LET ((#:BASE1262 *BASE*))
  (LOOP FOR (?ID #:G1263 ?NAME) 
    IN (LOOKUP #:BASE1262 :A NIL :B :USER :C NIL)
    APPEND (LOOP FOR (#:G1264 #:G1265 ?TIME) 
              IN (LOOKUP #:BASE1262 :A ?ID :B :TIME :C NIL)
              APPEND (LOOP FOR (#:G1266 #:G1267 #:G1268) 
                        IN (LOOKUP #:BASE1262 :A ?ID :B :NUMBER :C 62)
                        COLLECT (LIST ?ID ?TIME ?NAME)))))

and just so that we're perfectly clear on what that means, here's the Lisp-esque pseudo-code

(for-each goal-1
    append (for-each goal-2 
               append (for-each goal-3
                          collect [some list of components])))

Now granted, we're aggressively using indices where we can, so we can slice a lot of the constant time out of this equation depending on how often such an operation happens, but no matter how efficiently we slice it, we're going to take a number of steps equal to goal-3 * (goal-2 * goal-1). That is, we're going On over the candidates for the last goal, for each candidate of the previous goal, for each candidate of the previous goal and so on.

This is why the indices help us a lot. If we couldn't effectively discount swathes of our initial corpus, the performance characteristic would be On^m where n is the size of our fact base and m is the number of goals. Meaning that it behooves us to cut as many candidates as early as possible, since early reductions in our problem space will give us much better returns.

In other words, to paraphrasingly re-iterate Norvig, even though

(for-all (and (?id :user ?name) (?id :time ?time) (?id :number 62))
         :in *base* :get (list ?id ?time ?name))

and

(for-all (and (?id :number 62) (?id :time ?time) (?id :user ?name))
         :in *base* :get (list ?id ?time ?name))

are logically equivalent, the latter is going to perform noticeably better, because (?id :number 62) has a much smaller set of candidate facts than (?id :user ?name) in our particular corpus. One interesting exercise, which I'll leave for next time, would be to have for-all try to optimally sort its and goals by putting the smallest candidate lists at the beginning so as to reduce the search-space with no thought required from the user. The above is a trivial example; there's one goal that has more indexable terms in it than the others, so in general[8] it will probably yield a smaller candidate list. The real way about this feels like it would be to aggressively index goals at the start of a query and sample their corpus size, then sort on that. Not sure if that would cost more than it buys me though, since it feels like that would get complex fast.

Anyway, like I said, I'll leave it for next time.

If I end up seeing performance issues in the things I'm building out of fact-base.

And I get bored.

Footnotes

1 - [back] - Like this, if you're interested:

(defparameter *base* (make-fact-base :indices '(:a :ab :abc)))

(defmethod test-generate! (n)
  (loop repeat n
     do (multi-insert! 
         *base* `((:number ,(random 100)) (:type :digit) 
                  (:time ,(get-universal-time)) 
                  (:user ,(nth (random 7) '("Inaimathi" "Anon" "Someone Else" "Albert" "Beatrice" "Charles" "Daria")))))))

(test-generate! 10000)

2 - [back] - Which makes things much simpler for this approach. Hopefully, you'll see why as we go.

3 - [back] - and they can, since it's still an :exported symbol itself.

4 - [back] - if it has been bound by a previous destructuring-form, it'll be assigned by this point, which means we'll be able to index by it. Otherwise, gethash will return nil, which is exactly what we want.

5 - [back] - This is where we could be a bit more efficient, in case you're interested. If we wanted to be very precise about it, we'd say that we could use a compound form with variables as an index, provided that all of its variables have been bound prior to this point in the traversal. I'm leaving it out for now because

it would further complicate an already tricky chunk of code
I'm not sure how often this edge case would happen in practice and
if it does happen, the current result will be a slightly less efficient traversal, which doesn't sound too bad. If the consequence were incorrect results instead, I'd have reconsidered

6 - [back] - As an aside, this is the first place I've seen in something like 8 years where a comment is appropriate. It doesn't mirror the code to which it pertains and it explains a non-obvious but necessary facet of the implementation. Usually, I'd either work out some naming scheme that would make the point obvious, or just factor out the chunk of code that needs explanation. There doesn't need to be a simple way of doing either here[9].

7 - [back] - And just to highlight this, it is a compilation pipeline. I mentioned this at a semi-Lisp-related meet-up lately, and it's true enough to repeat to the internets: a good way of conceptualizing a Common Lisp macro is as a compiler that takes some Lisp code and emits different Lisp code. Because of the way Lisp is structured, we get the first chunk of an actual compilation pipeline for free, and essentially start with a tokenized input. It's a pretty powerful technique once you get your head around it.

8 - [back] - Though not necessarily in plenty of specific cases.

9 - [back] - Though I guess I could factor that let out into a with-for-all-forms if it turned out I had to repeat it in many places.

Querying Fact Bases

2014-04-09T21:01:00.002-07:00

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

traverse the database looking for facts that have '(:author "Inaimathi") for a rest
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

2014-04-05T15:04:00.002-07:00

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

2014-03-25T12:04:00.001-07:00

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

the first element
the second element
the second then the third element
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

2014-03-20T16:55:00.000-07:00

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

you can now add indexes to your fact bases, which should make data retrieval faster[1]
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

2014-03-06T09:11:00.001-08:00

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

2014-02-17T12:07:00.001-08:00

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

2014-02-09T00:14:00.000-08:00

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.

Update, and the Finer Points of Quasimodes

2014-01-28T19:39:00.000-08:00

I was going to say "this'll just be a quick update", but on reflection, I'm not sure that's true. I want to discuss two specific things I recently implemented, as well as what's been going on lately project-wise.

First things first.

AOSA Chapter

I'm doing a chapter for the upcoming book called 500 Lines or Less. It's the fourth installment in the Architecture of Open Source Applications series. To, I should hope, no ones' surprise, I'm doing a write-up of the House asynchronous server currently serving as the back-end for the Deal project. I've seen fit to simplify the server a bit for entry, since the real live one masses slightly more than 500 lines. You can see the result here; that's the House server with the session and static file mechanisms stripped out, which happens to weigh in at just over 400 lines of fairly readable Common Lisp. The first 1/2 draft of the prose write-up is here.

This process is new to me. Granted, I write a fuck-ton, but I'm usually also the editor and proofreader. Frankly, I don't envy anyone that job. It may not look like it, but I end up chopping a good half of my output before it gets posted anywhere, and then tweak about a third of the result after the fact. Hopefully, involving other eyes will mean a more refined exposition than I usually manage.

2dmacs

I'm still working on that visual editor at work. Internally, we've taken to calling the project "2dmacs", pronounced "two-dee-macs". Hopefully, I can live up to the name. We're going to do some user trials tomorrow, just to see what the target audience of 5 thinks. It's still missing one or two big features, mostly history related and mostly pretty straight-forward to implement. But based on my own experience, it's already more productive than the alternatives for the sorts of things we'll be doing. I'll let you know how it goes.

Now then, moving on to a couple of implementation details. Except that I still can't show you code. Sorry.

Quasimodes

Quasimodes are another thing I picked up from that Raskin book [1]. The idea is to let holding a particular key kick off a different interaction mode and cancel out of it on release. Raskin's example is of the Caps Lock and Shift keys. Basically, Caps Lock switches the user into a mode where standard keyboard keys do something different, whereas Shift activates a quasimode to the same ends. The argument is that the second is better because there's no confusion about what state the system is currently in. If you're holding shift, you're in shout mode. If you're not, you're not. Comparatively, as long as your keyboard has a Caps Lock key, you might be dumped into Shout mode by an accidental keypress. If you've ever tried to type in a password, you know the problems this can cause. Quasimodes neatly sidestep the issue by keeping a mode active only as long as the user deliberately holds a particular key.

Implementing this in Javascript turns out to be non-trivial. Even after you've built up your own little event system around the various input actions a user can take. What you naively need to do is capture the keydown event, activate a given quasimode[2], and clean up when you get a keyup corresponding to the initiating keydown.

That has some implications, though.

First, it requires the ability to optionally route events through particular functions. Which means that you have to have a layer of indirection between the default HTML event handlers and your systems' commands. Luckily, the system I'm building had that already for unrelated reasons, but if you're trying to do this properly in your system, it might mean some architectural changes.

Second, because we're dealing with browser events, we need to be able to cancel out of a quasimode with something other than the initiating keydown event[3]. In my case, I had already wired <esc> as the generic cancel button. It already drops you out of half-completed keystrokes and resets some small pieces of internal state to their original positions. So it made perfect sense to just add "exit any quasimodes" to the list of things it does.

Finally, unless you want to let quasimodes monopolize the keys they'll be bound to, it means having some logic involved that distinguishes between a regular keypress and a quasimode invocation. That ended up being resolved a touch hackily; if you press a quasimode key, but don't trip any of that modes' internal bindings before releasing it, it gets interpreted as a vanilla keypress. Not sure that's the best approach long-term, but I can't think of a simpler one off the top of my head.

Selections

A particular type of quasimode that gave me some pause is area selection. It turns out this is more complicated than you'd think at first glance. If you have a system that models various things as sets of points, and points as well as things are selectable and groupable, then there are a bunch of independent axes that you might be thinking about selections:

additive/subtractive/replacing You might reasonably be looking to add to your existing selection, remove elements from it, or replace your existing selection with the set of elements you're about to specify by area.

intersecting/containing You might want to select any thing whose bounding box touches your selection, or you might want to limit yourself to objects that are entirely contained inside said selection.

element/point You might want to select things, or you might want to select the points that compose them.

top-level/deep You might want to select the top-level groups of elements, or you might want to select the leaf nodes.

The point here is that these are all axes on which the user might choose independently, and most of them are reasonable choices. However, you don't want to have 24 different quasimodes, or even one quasimode with 23 different modifier keys to accomodate them all. After giving it some thought, I made the drag-select interaction default to an additive, intersecting, element, top-level selection. My intuition is that point and subtractive selections are going to be rare and simple enough that we won't need area support for them, that replacing selections are easy enough to counterfeit by hitting the clear-selection keystroke before making a selection, and that I can add modifier keys to distinguish between intersecting/containing and top-level/deep if needed. I'll let you know how that goes too.

Footnotes

1 - [back] - Which I thoroughly recommend for anyone involved in interface design of any kind. I'm kind of surprised they never made me read it in college, alongside Design of Everyday Things.

2 - [back] - Which means running its bindings instead of the global ones for the duration.

3 - [back] - An alert, or forced focus switch might take the user away from our window before we get the intended key released.

Which Lisp Should I Learn?

2014-01-24T08:28:00.003-08:00

I don't know why this keeps coming up lately, but it does. So, here we go:

My Recommendation

If you want to learn your first Lisp and already know something about the JVM[1], you should learn Clojure [2]. Otherwise, you should learn Scheme. Specifically, I recommend going the route that takes you through Racket [3], and possibly through SICP or HTDP.

If you absolutely, positively must, I guess go ahead and learn Common Lisp.

Why

Clojure the language, as opposed to the current, main, half-fused-with-JVM implementation, is cleaner and more consistent than Common Lisp, which should help you learn it more easily. I've gotten back talk about how there are lots more noobs learning Clojure, and as a result their libraries are in some disarray, and about the fact that the JVM is a sack of donkey balls you have to bite into every time you hit some sort of error[4], and about the general Clojure community pre-disposition to fashion trends. All of which may or may not be true, but I'm specifically talking about the language, not its ecosystem or stalwarts. Now granted, all of Racket, Clojure and Common Lisp

are built out of s-expressions
have defmacro

so depending on how much work you're willing to put in, you can do whatever the fuck you want in all of them[5]. However, in addition to knowing about prefix notation, and macros, and general Lisp program structure, here's an incomplete list of idiosyncrasies of Common Lisp that you have to commit to memory before you can be effective in it:

Functions and variables are in different namespaces, and each has constructs that deal with them explicitly. You need to use defvar/defun and let/flet depending on whether you're using functions or variables. If you're passing symbol names around, symbols that denote variables can be sent around as 'foo whereas symbols that denote functions should be sent around as #'foo. If you're trying to pass a function around in the variable foo, you need to (funcall foo arg) or possibly (apply foo args), rather than just (foo arg).
Most functions that deal with lists are functional, except the standard sort and the default mapcan, both of which destructively modify the list you pass them.
You can define methods for your classes, but can't easily use certain default names that are bound to top-level functions. Such as length, or the arithmetic primitives. Which is why you frequently see methods like duration-add or matrix-mult.
There are 7 commonly used equality operators, eq, eql, equal, equalp, string=, char= and =[6], each of which has mildly different, sometimes implementation-specific, behavior. Granted, because CL isn't a pure language, you need at least 2 of those, but 7 is still a bit much to have people memorize.
There are three different local binding mechanisms that you must decide between depending on whether you want to be able to refer to earlier symbols in the same binding set, or whether you want symbols to be able to refer to themselves. You use let/flet if you don't care, let* for variables where you want later bindings to be able to refer to earlier ones, and labels for functions where you want bindings to be able to refer to themselves or earlier bindings.
There are many, many implementations of Common Lisp. The popular ones at the moment are SBCL and CCL, but I've personally seen CLISP, ECL and Lispworks around too. More are available, and you might run into a lot of them in the wild. If you want to write portable code, you have to jump through some hoops. The implementation-specifics range from the finer points of equality operator behaviors, to the behavior of handler-case[7], to the types you can specialize on with defmethod, to the presence and behavior of threads, to the contexts in which you can pass streams around, to the names of various extension functions. For a small but representative example, take a look at what it takes to temporarily change your current directory in an implementation-independent way.
Indexing into different constructs takes different forms. You need nth for lists, aref for arrays and vectors, gethash for hashes and slot-value for CLOS instances[8].
You can't use the symbol t anywhere. No, not even local scopes. If you try, you'll get warnings or errors[9], because t is the top-level designated Truth symbol, even though anything other than NIL evaluates truthily in a boolean context.
A hash isn't a list, and a CLOS instance isn't anything like either. One way you'd like them to be similar is when you're traversing them. It seems fairly reasonable to expect map-likes to operate on hashes by treating them as a sequence of key/value pairs, and instances by treating their bound slots as key/value pairs. This is not how things work. If you want to map over instances that way, you need to do something like this and this. If you want to map over hashes, you either use the hilariously mis-named maphash[10] or some idiosyncratic piece of the loop DSL that lets you iterate over hash keys and hash values.
Common Lisp is case-insensitive. It takes whatever symbol input from you and upcases it internally. So foo-bar and foo-Bar both become FOO-BAR behind the scenes. This is usually not a huge problem, unless you try to interoperate cleanly with newer data standards like CSS or JSON. That leaves you fumbling with strings in situations where symbols and/or keywords really ought to do.

Like I said, this is a small sample. Just the stuff I thought of off the top of my head. I'm sure I could come up with more if I put a day or two into it. And I'm far from the most experienced Lisper out there, others would have more finer points for you, I'm sure. But that's half the problem with little issues like this; experienced Lispers completely forget about them. It's the newbs that have trouble cramming these things into their heads.

When I take a good look at that list, and then imagine the situations that led to each element, it's difficult to conclude that a wrong decision was made at any given point in time. Unfortunately, the sum of all of those potentially correct decisions is a giant system, the inherent rules of which look inconsistent if not outright hostile to human minds.

I don't know if Clojure solves all of them.

I've done very little work with it, for reasons entirely unrelated to the language. For all I know, when you get deep enough into it, you get to inconsistencies and/or restrictions which are worse than anything I've pointed out or could.

But do me a favor, if you're a CL user, either hop over to this web REPL, or install leiningen then hop into your local lein repl and type along here:

user=> (def thing [8 7 6 5 4 3 2 1])
#'user/thing
user=> (thing 0)
8
user=> (thing 3)
5
user=>(map (fn [n] (+ 3 n)) thing)
(11 10 9 8 7 6 5 4)
user=> (def thing {:a 1 :b 2 :c 3})
#'user/thing
user=> (thing :c)
3
user=> (thing :d 6)
6
user=> (thing :a 6)
1
user=> (map (fn [[k v]] (+ v 2)) thing)
(3 4 5)
user=> (def thing #{1 2 3 4 5}) ;; a set, in case you were wondering
#'user/thing
user=> (thing 3)
3
user=> (thing 0) 
nil
user=> (map (fn [a] (+ a 2)) thing)
(3 4 5 6 7)
user=> (def triple (fn [a] (* a 3)))
#'user/triple
user=> (triple 4)
12
user=> (map triple thing)
(3 6 9 12 15)
user=> (map (fn [a] (let [t (- (triple a) 5)] (* 2 t))) thing)
(-4 2 8 14 20)

Now think about how you would go about explaining to a novice programmer that it has to be more complicated than that.

Footnotes

1 - [back] - And don't have a strong dislike for it, obviously.

2 - [back] - Install it through Leiningen, which is available in the Debian repos in stable and unstable.

3 - [back] - Yes, I'm fully aware that the Racket guys are trying to push this "We're totally not Scheme" thing. They're close enough from an external perspective. Just don't tell Jay McCarthy I said so.

4 - [back] - Which is certainly true, but mildly preferable to the alternative as long as you're used to that sort of thing.

5 - [back] - Except that Clojure is apparently missing Reader macros, which I always thought were kind of half-assedly implemented in Common Lisp. For what I consider the full-ass version, take a look at how Haskell does it.

6 - [back] - Plus how many ever *-equal functions you define for your own classes.

7 - [back] - The Common Lisp answer to the problems that call for try/catch in other languages.

8 - [back] - For the last, you can also define your own selectors using :reader or :accessor declarations.

9 - [back] - Which specific warning or error depends on implementation.

10 - [back] - Because it's not very much like map. It returns nil and works by side-effect. Meaning that if you expect a sequence from it, you'll need to construct it yourself.

Debian Testing, Pi and Git

2014-01-04T14:42:00.000-08:00

That was a vacation, I guess.

It was suspiciously taxing, all in all. Time off from work hasn't been nearly as relaxing since we had a kid, but that's a digression. Over the past little while, I've managed to finally make use the 120G solid state drive I picked up half a year ago, install various distros, and put together about one third of a utility to ease a project or two I'm working on in my spare time.

New Drive

It's at once larger and smaller than the last one. On the one hand, thanks to its smaller physical profile, I can fit it into my laptop with no mods. On the other hand, df -h says 106G[1] instead of ~28G.

That's it, nothing else to see here.

Fresh Install

Since I was between drives anyhow, I took the opportunity to get the fresh version of Debian up and running. That was worth it, by the by, if for no other reason than they've apparently poured enough bucketfulls of time into the networking code that I can now reliably connect to my wifi access point even if I'm not within two meters of it. They also seemed to lick a problem I kept running into wherein the shutdown process would hang the machine[2].

There were a few changes in my install routine, which is still vaguely based on

## temporarily add
## deb http://packages.linuxmint.com debian import
## and `contrib non-free` to /apt/sources.lisp

apt-get install firmware-ralink firmware-realtek
apt-get install screen make emacs24 git gitk wicd-curses pmount htop gnupg unetbootin
apt-get install mplayer feh pacpl imagemagick x-window-system dmenu xmonad gimp inkscape firefox
apt-get install python-pip sbcl vrms

## remove the temporary repos

There are a couple of changes there from my usual. Firstly, Firefox has become my go-to browser. Its absorbed most of the goodness from Chromium, including the reduced toolbar footprint and fantastic JS console. It also has support for adblock, and a fairly good RSS feed reader, and it's no longer slow as molasses[3]. This raises the problem of the Debian packaging though; in the official repos, apt-get install firefox gets you a pretty ham-fisted re-brand with no plugin support called "Iceweasel". What I ended up doing, as you can see above, is temporarily adding the Linux Mint repo to install that[4]. Secondly, I'm installing emacs24 rather than just plain emacs. This is because the current default for emacs in Jessie is Emacs 23.something, and that doesn't have one of the main features I'm looking to finally adopt.

Emacs 24 supports package out of the box. In practice, this means adding

(require 'package)
(add-to-list 'package-archives '("melpa" . "http://melpa.milkbox.net/packages/") t)

to my .emacs instead of toting my old .emacs.d/ around. I can't actually remember every library I used to have around, so the list I settled on this time out ended up being

aes auto-complete autopair highlight-parentheses htmlize skewer-mode magit markdown-mode paredit redo+ smart-tab yasnippet

Which covers pretty much everything. Oh, one thing. I spent about half an hour figuring out what was going wrong with my .emacs config; libraries I was certain had been installed were coming back with not found errors when I tried to require them. It turns out that when you add a directory to the load path, you don't automatically add all its subdirectories. As you can see by the above list of packages, I use quite a few, each of which gets its own sub-directory in .emacs.d/elpa/, and wildcards don't work here either. So I was forced to add the following to convenience.el, just to save myself the tedium

(defun starts-with-dot-p (path)
  (= (aref path 0) ?.))

(defun list-subdirectories (path)
  (let ((all (mapcar 
              (lambda (name) (concat (file-name-as-directory path) name))
              (remove-if #'starts-with-dot-p (directory-files path)))))
    (remove-if-not #'file-directory-p all)))

(defun add-to-load-path (dirs)
  (mapc (lambda (p) (add-to-list 'load-path p)) dirs))

then called this near the top of that .emacs file:

(add-to-load-path (list-subdirectories "~/.emacs.d/elpa"))

This let me continue as normal. The only omission from that emacs package list is slime, which I've lately been installing from sbcl or what-have-you with (ql:quickload :quicklisp-slime-helper) rather than through Emacs itself. It works exactly as well as you'd expect, which is to say flawlessly.

Dicking Around With Pis

Doing that got me into an installing mood, so I also formatted a fresh couple of SD cards with the latest versions of ARM Arch and Raspbian respectively. I did this with the vague intention of getting deal to work with one or both, and it looks like that'll take a bit more work than just a straight-up ql:quickload. Differences before I get to that though.

The RPi arch is much closer to what I'm used to on my laptop. A brutally minimal installation of the few core utilities you need to get basic shit done, and nothing else. Specifically, it gives you pacman, perl, a working ssh server and a minimally intrusive wireless connection mechanism that could replace wicd-curses for me. Raspbian, by contrast, bundles a mandatory window environment along with a bunch of crap that's probably nice for most humans looking to use it as a desktop replacement, but that I'll never end up touching. Also, they bundle Scratch as well as Python 2 and 3. Finally, while they do provide an ssh server, it's off by default, and the first time you boot a Raspbian image, it forces raspi-config, which means that you must connect a Raspbian Pi to a monitor and keyboard at least once.

That minimalism ends up biting Arch a bit though; it doesn't come with the standard raspi-config utility, which lets you mess around with the hardware to some small extent, and easily resize the installation partition to fill the SD card[5]. The other thing that bites ARM Arch in the ass, as far as I'm concerned, is the fact that its package manager has very few of the things I want to install. Out of my usual menagerie, I found screen, make, clisp, python, emacs and nothing else. By contrast, I had to apt-get --purge a bunch of things over on Raspbian, but I was eventually able to get it working with an almost copy of my laptop environment.

Almost, because Lisp still has some problems.

Specifically, clisp segfaults on both ARM Arch and Raspbian when you try to load anything with quicklisp, while the ARM ccl failed to run at all on Arch[6]. Raspbian did run ccl appropriately, but errored out on me for two reasons. Firstly, there's something unsupported about the :ironclad MD5 digest, and secondly, the ARM architecture seems to treat bivalent streams differently than x86. Which means that even running its custom house server, :deal errored out.

I'll be trying to fix that over the next little while.

cl-git-fs

Finally, on a merely semi-related note, I'm working on a couple of projects on my own time that are eventually going to want to do some sort of file management. And I figured it would be nice not to have to bring git into it manually after the fact. To that end, I took a look at how gitit manages the trick of using git as a faux-database for its wiki pages. It's not that complicated, as it turns out. And here's the result of spending an hour or two porting that piece of functionality to Common Lisp.

The biggest problem I'm running into is that there isn't a standard shell-command or run-program defined in the various Lisps I want to support.

I'm tossing it up to my github, but calling it 0.01 because there's a fuckton of functionality and documentation missing. In particular, it currently only supports SBCL on Linux, and a few of the external API functions still return raw string results, rather than properly parsed CLOS instances. The documentation and parsing will be a priority no matter what, but I'll only see how it runs on other platforms and implementations as I need to deploy to them.

Footnotes

1 - [back] - Of course, the drive box says 128G, so Samsung and all drive manufacturers are lying shitbags, but I'm digressing again.

2 - [back] - And therefore keep drawing power until a forced shutdown.

3 - [back] - which it was last time I played around with it.

4 - [back] - No, since you ask, I've never just straight up tried Mint. It has something in common with most of the distros I get recommended, which is that it cribs heavily from Debian on everything that matters, and then tries to differentiate on the desktop environment almost entirely. Not that this is bad for end users I guess, but as you can see from the x-window-system and xmonad items in that installation list above, I do not use what you would think of as "a desktop environment". Don't let that stop you from trying it, of course, but I'm not going to.

5 - [back] - You can still do this externally via gparted when you image your SD card.

6 - [back] - running the included binary gave me a "wrong architecture" error, even though there's no way that's accurate.

Implementing Humane Authentication

2013-12-14T10:04:00.002-08:00

Last time, I mentioned the auth system proposed by Raskin in his book The Humane Interface. This time, lets dissect something concrete.

Actually, before we get to dissecting anything, let me emphasize again that the most humane approach to authentication is not requiring it. If you have a system that could be exposed to anonymous users, that's what you should do. If you've decided that you absolutely must have some sort of authentication step, then this doesn't seem to be a bad way to go.

Now then...

;;;; raskin-auth.asd
(asdf:defsystem #:raskin-auth
  :serial t
  :description "Implementation of the authentication system proposed in The Humane Interface"
  :author "Inaimathi <leo.zovic@gmail.com>"
  :license "AGPL, as usual"
  :depends-on (#:cl-ppcre #:ironclad)
  :components ((:file "package")
               (:file "util")
               (:file "raskin-auth")))

;;;; package.lisp
(defpackage #:raskin-auth
  (:use #:cl)
  (:export #:new-account! #:sign-in))

;;;; util.lisp
(in-package #:raskin-auth)

;;;; Dictionary-related
(defconstant +dict+ (coerce 
                     (with-open-file (s "/usr/share/dict/american-english")
                       (loop for line = (read-line s nil :eof) until (eql line :eof)
                          unless (cl-ppcre:scan "[^a-zA-Z]" line)
                          collect (string-downcase line)))
                     'vector))

(defun random-words (count &optional (dict +dict+))
  (loop repeat count
     collect (aref dict (random (length dict)))))

;;;; Hash-related
(defmethod iterated-digest ((count integer) (digest-spec symbol) (message string))
  (assert (> count 0))
  (loop with res = (ironclad:ascii-string-to-byte-array message)
     repeat count do (setf res (ironclad:digest-sequence digest-spec res))
     finally (return res)))

;;;; raskin-auth.lisp
(in-package #:raskin-auth)

(setf *random-state* (make-random-state t))

(defparameter *users* (make-hash-table :test 'equal))

(defun hash (passphrase)
  (ironclad:byte-array-to-hex-string (iterated-digest 10000 :sha256 passphrase)))

(defun fresh-passphrase ()
  (let ((u-mod (/ (hash-table-count *users*) 100000)))
    (loop for num-words = (+ 2 (floor u-mod) (random (+ 2 (ceiling u-mod))))
       for passphrase = (format nil "~{~(~a~)~^-~}" (random-words num-words))
       unless (gethash passphrase *users*) do (return passphrase))))

(defun new-account! (&optional (user-data t))
  (let ((passphrase (fresh-passphrase)))
    (setf (gethash (hash passphrase) *users*) user-data)
    passphrase))

(defun sign-in (passphrase)
  (gethash (hash passphrase) *users*))

And that's it. In a production system, you'd obviously want to wire everything up to some database system or other rather than using an in-memory hash-table, but this explains the concept well enough. You'd use this module by including it, then calling (new-account! [user account data goes here]) (which will return a newly generated passphrase) and (sign-in "a-passphrase-goes-here") (which will return either nil or the account data you associated with the given passphrase) as necessary.

Lets go through it.

;;;; raskin-auth.asd
(asdf:defsystem #:raskin-auth
  :serial t
  :description "Implementation of the authentication system proposed in The Humane Interface"
  :author "Inaimathi <leo.zovic@gmail.com>"
  :license "AGPL, as usual"
  :depends-on (#:cl-ppcre #:ironclad)
  :components ((:file "package")
               (:file "util")
               (:file "raskin-auth")))

;;;; package.lisp
(defpackage #:raskin-auth
  (:use #:cl)
  (:export #:new-account! #:sign-in))

That's the ASD file and package. The first makes sure you can load this system using asdf or quicklisp, and the second declares your imports and exports. I'm trying something new this time and refusing to use :use or :import-from and friends. I've gotten a couple comments to the effect that it gets a bit confusing if I import symbols directly rather than labeling them inline with the package they came from, so even though raskin-auth does use things from both ironclad and cl-ppcre, the package.lisp file is staying minimal.

;;;; util.lisp
(in-package #:raskin-auth)

;;;; Dictionary-related
(defconstant +dict+ (coerce 
                     (with-open-file (s "/usr/share/dict/american-english")
                       (loop for line = (read-line s nil :eof) until (eql line :eof)
                          unless (cl-ppcre:scan "[^a-zA-Z]" line)
                          collect (string-downcase line)))
                     'vector))

(defun random-words (count &optional (dict +dict+))
  (loop repeat count
     collect (aref dict (random (length dict)))))

;;;; Hash-related
(defmethod iterated-digest ((count integer) (digest-spec symbol) (message string))
  (assert (> count 0))
  (loop with res = (ironclad:ascii-string-to-byte-array message)
     repeat count do (setf res (ironclad:digest-sequence digest-spec res))
     finally (return res)))

random-words creates a list of count random words by picking them out of a dictionary, which is +dict+ by default. You don't necessarily want these words to be unique, so we don't check for that. +dict+ is just some slightly sanitized output from /usr/share/dict/american-english, which is where Debian keeps the default English language dictionary. The result of that read is a vector of all words in the dict file that are composed entirely of lowercase letters. What we're doing, essentially is shuf -n [count] /usr/share/dict/american-english. Except we're filtering for some stuff, so that should really get piped through a grep or two. Use whatever method you'd like; the end goal is to get a list of count random words, from a list of ~60000 different words, each with an equal probability.

iterated-digest takes a count, a digest-spec and a message, and applies the specified digest to the message count times sequentially. We'll take a look at how you call it in a second.

;;;; raskin-auth.lisp
(in-package #:raskin-auth)

(setf *random-state* (make-random-state t))

(defparameter *users* (make-hash-table :test 'equal))

(defun hash (passphrase)
  (ironclad:byte-array-to-hex-string (iterated-digest 10000 :sha256 passphrase)))

(defun fresh-passphrase ()
  (let ((u-mod (/ (hash-table-count *users*) 100000)))
    (loop for num-words = (+ 2 (floor u-mod) (random (+ 2 (ceiling u-mod))))
       for passphrase = (format nil "~{~(~a~)~^-~}" (random-words num-words))
       unless (gethash passphrase *users*) do (return passphrase))))

(defun new-account! (&optional (user-data t))
  (let ((passphrase (fresh-passphrase)))
    (setf (gethash (hash passphrase) *users*) user-data)
    passphrase))

(defun sign-in (passphrase)
  (gethash (hash passphrase) *users*))

*users* is a hash table that'll keep all of our user records[1], and both new-account! and sign-in are hopefully self explanatory. Let me linger on the rest of that though.

First, you absolutely positively need the *random-state* initialization. Without that line, your system will generate the same order of passphrases each time it starts up. Maybe that's not too big a deal in general, but I'm paranoid enough that I want proper, os-seeded randomness out when I'm generating authentication tokens.

Second, you can see the iterated-digest call here:

(defun hash (passphrase)
  (ironclad:byte-array-to-hex-string (iterated-digest 10000 :sha256 passphrase)))

That takes a particular passphrase string and returns the result of applying the :sha256 digest to it 10000 times. I guess you could make that :sha512 if you really wanted to.

Finally, fresh-passphrase does the job of calling random-words, concatenating the result, and checking whether the result of that is already on record. It keeps going until it generates a passphrase that no one else is using at the moment, and returns that. You can see that it scales somewhat with count of users registered, just to make sure we don't get into the situation where a particular passphrase length is particularly easy to guess.

That's it. Again, what I see here is reasonable security.

Thoughts

On the one hand, you don't get to salt passphrase hashes. Which means that if anyone manages to trick a user of this auth system into revealing their ciphertexts, they'll have a mildly easier time cracking the result. And, since every passphrase is unique, they can knock out some tiny number of possibilities as they go. You also can't easily change your hashing tactic in-flight. Hypothetically, if you chose the iterated :sha256 approach from above, and it then turned out that clever people found ways to compromise that hash, you wouldn't be able to switch your tactics on a live system easily, the way you could with a user-name-oriented system. You would be able to increase the number of hashings fairly easily; just modify your hash to do more iterations, and modify your registered users' passwords to make up the difference.

On the other hand, no one will ever have the passphrase 123 with this system. And, since they didn't pick it, they presumably won't have this same passphrase on any other service they frequent, which means a compromise here won't have to result in a mad dash to change their account passwords anywhere else fo fear of exploits.

The only other downsides seem to be that you can't choose a passphrase, and that if you forget your passphrase, you must create a new account.

Footnotes

1 - [back] - Because it's a hash table, and I don't bother doing any kind of locking, the system you see specified here very likely won't do for any multi-threaded use-cases. You can either add locks, or go the whole nine and replace that hash table with an external database, but I don't need either to see the basic properties of the system, so I didn't implement them.

Jef Raskin on Authentication

2013-12-10T10:16:00.001-08:00

I've got an idea to peel, and for a change, it's not even mine. I'm in the middle of reading through a Raskin book entitled "The Humane Interface", in which he suggests a different take on user authentication. In section 6-4-3[1], Raskin suggests that signing on to a system can be accomplished without requiring a user name. That is, instead of ... you know what, here, this is easier:

Users are doing more work than necessary when signing on to most systems. You first state who you are -- your "handle", "online name" or "system name" -- and then you provide a password. The name presumably tells the system who you are, and the password prevents unauthorized persons from using your account.

In fact, you are telling the system who you are twice. All that is logically required is that you type a password. There is no loss of system security: The probability of guessing someone's name and password depends on how the password was chosen, its length and the like. Finding the user's online name is usually trivial; in fact, it is commonly made public so that she can be communicated with. A badly chosen password, such as your dog's name, is the most common reason for poor security.

The technical argument that typing two separate strings of characters gives more security is false. If the online name is j characters and the password is k characters, the user, to sign on, must type j+k characters, of which only k characters are unknown to a potential interloper. If the password was chosen randomly -- this is the best you can do -- from a character set with q characters, the probability of breaking into the account on a single guess is 1 / q^k.
Jef Raskin -- The Humane Interface, p183

If you've given authentication systems anywhere near as much thought as I have, the trouble you should immediately see is that in a system like the one proposed above, a password must be unique to a user. Luckily, Raskin sees that one coming.

The question arises: How can you ensure that everybody has a unique password in a password-only system? What if two or more users chose the same password? The best option is to have the system assign them. This method can result in very unmemorable passwords, such as 2534-788834-003PR7 or ty6*>fj`d%d[2]. Another technique is to use a random pair of dictionary words, such as demijohn-shoestring, confirmed-tweezers or sulphur-dive. If a dictionary of 60,000 words is used, the chance of guessing a password on the first try is one in three billion, six-hundred thousand. Using three words puts the difficulty of guessing them beyond hacking with current technology; there are 2.16 x 10^14
such combinations, and guessing and checking a billion of these a day, beyond what can be done at present, would still take about 10^5 days, or 275 years. That's reasonably secure. User-created passwords, at least those more readily memorized by the user, are inherently less secure.

When the idea of improving the interface to a web site or a computer system by simplifying the sign-on process to require only a password is suggested, it is usually rejected on one of two grounds. Either the programmers say that that's just not the way it's done, or they say that they have no control over the sign-on procedure. But someone, of course, does have that control.
Jef Raskin -- The Humane Interface, p183,184

Before I discuss this idea with my self, I have to disagree with two points. First, the odds of guessing a correct password on the first try is not 1 in 3 600 000 000, or 1 in (* 2.16 (expt 10 14))[3]. It's n in whichever-you-picked, where n is the number of users you have. With a password-only system, an attacker is no longer trying to guess a particular users' password, they are trying to guess any password already assigned by your system. Second, I'm not entirely sure that badly chosen passwords are any longer the most common reason for poor security[4], but rather utterly, mind-fuckingly stupid security design by password DB teams[5].

With that our of the way, lets all don our white hats[6], and imagine the proposed system in enough detail to implement it.

How does a user log in?

In the context of a web application, they've got one field to fill out, "passphrase", and one button to click, "Log In". The passphrase entered is then hashed and looked up in our user database; if it matches a passphrase hash we have on file, the user ID is retrieved and used to get the specified users' program state. We then continue along letting them do what they're actually here to do. In an ideal system, this authentication step would be entirely optional, allowing it to happen at the last possible moment, when a user needed to commit some piece of data to their server-side corpus.

This is easily the biggest introduced weakness I see in the proposed system. Because we only have a passphrase to work with, we can only use either an unsalted hash, or a per-server "salt" to keep our passphrases out of plaintext. If we didn't, that user lookup based on the password would take a long time. Scaling at On with number of users, with some fairly ridiculous constants tacked on. That's dangerous, because we're suddenly gambling that the rest of the application our auth system is embedded in won't allow any injection attacks, or leak database information any other way. Granted, because we're guaranteed to have unique passwords, such a disclosure isn't as easy to take advantage of as it might be, but it's still a concern.

What happens when the user enters a passphrase that isn't currently assigned?

There are really only two reasonable possibilities:

They get an artificial delay, followed by the above message. The standard log-in procedure also needs to have an equivalent delay, otherwise attackers might abort a guess before getting the response back, which would prevent them from actually being delayed in the practical sense. It doesn't have to be long; a second or two would be enough to prevent the kind of guess hammering I've got in mind, and it wouldn't be too annoying to users provided we put in a little spinning graphic in the meanwhile[7].

They get a "logged in" response with the default state in place, and no other warning. Effectively, an "incorrect" passphrase entry becomes a registration. Users might get annoyed at this one, since it would seem at first that their program state is gone.

Having thought about this for a bit, it becomes clear that there's only one reasonable possibility, and it's the first one.

How does the registration process work?

This might be context sensitive by application. For instance, Deal lets users play entirely anonymously. I can easily imagine a system wherein after 10 minutes of play time, a user just automatically got an in-game notice with a passphrase that would let them resume where they were. Because the server controls all the steps to a registration, it can happen behind the scenes with some game time effectively taking the place of a Captcha. This could be used with any system that lets you start off anonymously; wikis, bulletin boards, forums, etc.

That system, elegant as it might be from the implementation and usability side of things, wouldn't work for something like GoGet. Where the only possible reason to use the application is to go back later and check what you put in the first time. In that situation, you'd want the usual up-front "Register" button that would do the Captcha thing to make sure you're not a robot[8], and hand the user an account before they start doing stuff. Really, this might be re-designed too though; have the system start you off on a blank check-list, with an unobtrusive "Log In" form at the top of the page, with the added button "Save", which would register you and hand you a passphrase with which you could access the list you just made.

What do we do when passphrase exhaustion occurs

Granted, 216 000 000 000 000 is a large number, but it's not infinite, which means some clever bastard out there is going to find a way to cut it in half a few times for the purposes of guessing. And it doesn't take very many halvings to get that down to a tractable level. We have to deal with this problem a good deal sooner than "passphrase exhaustion"; if we get to the point where all passphrases are assigned, an attacker suddenly gets access to an account no matter which possibility they guess. But if we did something naive like hand out 2-word passphrases until they ran out, then an attacker who registers and receives a 3-word passphrase would know that any 2-word combination of our dictionary words will give them access to an existing account. We'd really want to generate new passphrases well before we ran out; at something like 10% exhaustion at a guess. Or better yet, don't limit passphrase length to two words, make it n random words, where n is something like

(let ((u-mod (/ user-count 1000000)))
  (random (+ 2 (floor u-mod)) (+ 4 (ceiling u-mod))))

That should give attackers less purchase, and scale naturally with additional users.

What Have We Got?

Switching briefly over to my black hat, I can't see an attack on this system that would get you any traction above and beyond traditional password-based implementations[9]. That doesn't mean there isn't a way, of course. I'll present the idea to some discerning and devious thinkers to see what they can come up with. Otherwise, we've got some interesting properties here, mainly because the server-side is the one putting everything together. We have a passphrase system that

only requires the barest interaction with the user
can be initiated automatically at some point[10]
will not suffer the failure mode that someone will use this same passphrase everywhere[11], meaning that even if the system is compromised, all an attacker has is access to an account for one particular service
will never have to worry about a passphrase as shitty as "password" or "12345"

On the flipside, though:

You can't change your passphrase to something you want
There isn't a way to recover or reset a forgotten passphrase[12]

All in all, barring someone pointing out some egregious security flaw in this approach, it seems to be worth implementing.

I'll see what I can do.

Footnotes

1 - [back] - Starting on pg 183 in the copy I'm holding.

2 - [back] - The actual printed second password contains some unicode characters which were not accurately reproduced here.

3 - [back] - Depending on how many words you decide to pack into each generated password.

4 - [back] - Though it may just be a media imparted bias on my part.

5 - [back] - Such as the refusal to use appropriate hashing algorithms, or inadvertent opening of various injection attacks.

6 - [back] - Mine's a tuque because it's cold out and I'm in Canada, but you should feel free to don your hacking fedora, trilby, stetson, what-have-you as regionally appropriate.

7 - [back] - Most authentication systems I interact with take longer anyhow.

8 - [back] - Or not, really. Depending on how much traffic your system can handle, how much you care about preserving disk spce, and whether you give your users the ability to use SMTP facilities, you might get away with putting in an artificial 3 or 4 second delay before registration completes rather than trying to prevent automatic sign-ups. That's what I plan to do, in any case.

9 - [back] - Apart from the situation where our ciphertext passwords have been leaked. Which, granted, isn't a high bar, but still.

10 - [back] - As in the situation in Deal that would automatically hand the user a passphrase ~10 into active use of an unregistered account.

11 - [back] - Hopefully, at least.

12 - [back] - Since the passphrase acts as both a name and password, if you forget it, you just have to start a new account. Allowing the user to save as much of their data as possible locally would work to alleviate some of the pain from this.

Quick Update on Deal

2013-12-01T19:55:00.002-08:00

Deal proceeds apace.

I've spent the past while putting together a minimal, single-threaded asynchronous server to simplify the deployment process. Almost done, and you can see the progress on this branch in this subdirectory. The remaining stuff left ToDo is:

Better Errors. I need to put together an appropriate assertion mechanism. Straight up assert works fine in a multi-threaded context, but does some mean things when you've only got the one thread. Normally, it wouldn't be that big a deal, but I have to special-case my handler-case statements for SIMPLE-ERROR in order to allow shell interruption. Unfortunately, they're both conditions of type simple-error, which means that if I do it naively, I either let both or neither through. What I'm planning to do is define a macro named something like http-assert, which will throw a type of error I can then safely convert into an HTTP-400 response.

Basic Static Files. Currently, I'm serving static files through nginx only. Which is the efficient way of doing it. However, one use-case I'm thinking of for Deal is that of a small, geographically disparate team setting up a private server for themselves. It's kind of a pain in the ass to have to set up a reverse proxy for that situation, so it would be nice if House provided a basic file handler for people to use.

That's ... going to get complicated though. A first crack at the implementation is here and here. That only works for text files so far[1], and it only works for a laughably small number of mimetypes. A more complete map can be found here or here, but I'm not going to be anywhere near as thorough; remember, this is an edge case. This lightweight server is not in the business of serving out static files in an efficient manner. That's what things like nginx are for, and I've got no doubt they're doing a better job than I could.

Touch Ups Sessions don't expire yet. And when they do, I'll want to give them the same kind of behavior hooks that I've got going for new-session. There's also the non-trivial matter of porting the rest of the Deal system to work better with the House server, but I get the feeling I'm most of the way there already.

Famous last words, right?

Footnotes

1 - [back] - I'm still trying to iron out kinks; in particular there seems to be some kind of character encoding issue left in the way that I just can't get my head around. I'll be asking on SO shortly.

Combining SVG and HTML5 is still a Drag

2013-11-30T12:26:00.000-08:00

Dragging SVG elements is harder than it might appear at first glance.

The underlying implementation of the SVG DOM and the HTML DOM is different in current browsers you see, so the standard HTML5 drag event doesn't apply to SVG nodes. Luckily, mousedown, mousemove and mouseup are supported, so you'd think it would be a straight-forward task to implement the fucker yourself. You probably imagine, as I did initially, something that takes a selector and a list of callbacks, and implements something similar to jQuery's .draggable() in ~30 lines of code by

binding a callback to the targets' mousedown, mousemove, mouseup events
storing the initial position of the element, and its delta from the mouse cursor
preventing default on mousedown
in addition to firing the callback, moving the target element by manipulating x and y coordinates using the current mouse position, initial delta and initial position

Maybe that's possible for the simple cases, but it's the edges that'll get you. And unless an implementation happens to dull all your edges, it's not really good enough.

Minor speed-bump. What if you need to drag multiple elements? If you were dealing with HTML elements, it wouldn't be such a big deal, but SVG elements have different properties to represent their coordinates. Rectangles and similar have an x and y that represents their top-left corner, circles and ellipses have cx and cy that represents their center, text elements have an x and y, but theirs represents the bottom-left coordinate, and I'm not even getting into the path elements. Bottom line, if you want to implement something that works, you're using transform settings. Also, you're not doing it naively through setAttribute, unless you're lucky enough to have a situation where you can guarantee that no other transformations will be applied to any draggable element[1]. The snippet that handles that particular piece looks like this in my codebase

(defpsmacro =translate (elem/s dx dy)
  `(try 
    (=>> ,elem transform base-val (get-item 0) (set-translate ,dx ,dy))
    (:catch (error)
      (=set-attribute ,elem :transform (+ "translate(" ,dx "," ,dy ")")))))

If you're one of the sad bastards who don't have macros at their disposal, I guess you're doing that or something fairly similar manually[2]. Like I said though, no big deal either way.

Medium sized speedbump. If you want to do this on an arbitrarily sized element, specifically a very small one, you'll discover that moving your cursor at even moderate speeds is enough to escape from the mousemove event and leave your draggable behind. One possible solution here is to also bind the mouseleave event and hope you never need to move fast enough to escape that too. Another approach is to have your chosen mousedown set up a global mousemove event, on body or html, use that to drag your element around, and have a global mouseup waiting to cut it off as soon as you're done[3]. A bit hacky, but doable.

Slightly larger speedbump. If you want to make these bindings switchable, you're in for a bit of a harder time. Not switchable as in "different objects should be able to do mildly different things", that's a given. I mean like "it should be possible to jump into a separate interaction mode where the same object does something mildly or wildly different under certain circumstances". If you want that, you need a level of indirection in your listener tree that you can swap out with other functions, and that level of indirection is going to be calling an externally specified function on each event trigger. Basically, you'll want to be working with hooks rather than listeners at this point[4]. I'll keep you posted on how this one goes in real life.

Large speedbump. Suppose you want to be able to use your dragging events, and a mouseup event on the same element. Better yet, suppose you wanted to implement drag/mousedown interactions, but let the user decide what layer to apply them on at any given time. Imagine a situation where you had the elements foo, overlapping bar, overlapping baz, and when a drag or mousedown hits, you want to let the user decide whether they want to be click/dragging foo and/or bar and/or baz. Near I can tell, there is no way of implementing this elegantly in terms of listeners on individual elements. What you need if you want this is a central listener that delegates particular events out to some intermediary functions, or eats them[5] as appropriate.

Keep in mind that the last two speedbumps I hit here probably won't be felt by most people going in the same direction. Still, I went into this figuring it'd take me a half hour at the outside to implement something workable. It ended up taking me the rest of the day, and will probably cost me another hour or two when I get back in on Monday.

Such is development sometimes, I suppose.

Footnotes

1 - [back] - If you are going to have other active transformations, using the setAttribute method would overwrite those, which is why it's a bad idea.

2 - [back] - if you are doing that, I should point out that the only reason I went the try/catch route here is that both =>> and =set-attribute take either an element or a set of elements as their first argument, and I wanted =translate to do the same. Since you probably won't have the same situation, you're likely better off with if/else.

3 - [back] - You wouldn't want to do this naively either, unless you knew there'd be no other mousemove events on that top-level element. If you did have that, you'd want to set up a hook that you could change out rather than messing with event listeners every time you dragged something.

4 - [back] - It just occurred to me that you might have no idea what I mean by "hook" in this context. Basically, something like this:

var mouseMoveHook = null;
document.querySelector("body").addEventListener("mousemove",
  function (event){
    //do other stuff
    if (mouseMoveHook) { mouseMoveHook(event) };
  });

If you have something that looks like that, you can change some of the behavior of your global mousemove event by assigning a new callback to the mouseMoveHook variable. I'm sure it's been used elsewhere, but I learned the term "hook" from Emacs, which provides standard event hooks in a bunch of different situations, and does it more or less this way, modulo some syntactic sugar and multiple hook support.

5 - [back] - In the case of the trailing mouseup event after a drag concludes.

Arbitrary Update 714

2013-11-26T20:19:00.003-08:00

We're working on FBP in Common Lisp. You've heard that one before.

Step one was getting a basic system running. In fact, we've got two we're dealing with concurrently[1]. Both are kind of rickety because I'm still trying to work out what the essential parts of the approach are. One deals with OS threads and the other is built on top of cl-async. I'm liking the second one better for now, but am once again reserving judgment until I see how easily they explode.

Anyhow, that's price of admission, rather than the finish line. Our ultimate goal is to prove out visual programming in the large, without making anyone throw up about it. I have no idea how that's going to end up, except that I've definitely got a couple of interesting years coming up. In order to get to that ultimate goal, step two is finding or building an Acceptable™© Visual Editor.

And we can't find one, so "build" it is.

What we want, being that we're Lispers and polyglots to the last, can best be described as "Emacs for Diagrams". And that doesn't seem to exist. There's a number of general-purpose vector editors out there at various levels of readiness, but those are more like "MS Word for Diagrams". There's a "Sublime for Diagrams" floating around in the form of yEd, and one piece of fallout from the Russian space program is basically "Notepad++ for Diagrams". Microsofts' own flowcharting suite is something like "Eclipse: The Extra Shit Version for Diagrams. Also You Can't See Our Source Code, Which Is Probably For The Best Because It's Mostly Garbage You'd Laugh Out Of Your Company In Any Other Context". Finally, if we want to use Emacs for diagrams, the only thing even remotely workable seems to be artist-mode. It's nice, I guess. Certainly better than prostate cancer. But that's not quite what we're looking for.

The thing we are looking for needs to be

A visual editor. This needs to be a tool to let humans construct diagrams and related diagrammatic artifacts for a variety of media.
A diagram editor. We're not looking for a general purpose editor. In particular, there are very, very few things we'll be rotating, nothing we'll be coloring[2], and we only need one font at a fairy small variety of font sizes and weights. We'll also never be dealing with embedded bitmaps, gradients, brush-strokes, or shapes more complex than rounded rectangles/ellipses. You'd be surprised how much junk that lets you cut out.
Fast. It shouldn't take longer to draw a diagram with this thing than it would take to describe it. This means a keyboard-oriented interface with easily re-bindable keys, reasonable performance, reasonable start-up, and no half-baked expert system getting in your way by trying to guess what you're trying to do.
Scriptable. It should be possible to simply and easily construct sequences of operations to be summoned later. It should be easy to run automated queries and transformations on the programs' output and potentially edit the result in a visual manner. It should be fairly simple to select a particular subset of elements and manipulate them in some way.
Flexible. We have no idea what the visual formalism we're finally going to adopt will look like. It might require fine placement of wires and connectors, it might involve different kinds of connections, and it will certainly involve multiple different connections between two nodes[3]. It also can't make any kind of semantic assumptions about what the content we're editing means, because that might change as we go through the discovery process of what kinds of processes and situations we want to formalize. This also means some sort of proper macro system, an end-user specifiable final/intermediate representation, and source code that we'll be able to tear apart if we need to.

The various editors I list above are split firmly into two camps. First, there are editors aimed at non-programmer humans for general vector construction. They're fairly flexible, but because they're for mouse-pushers, they don't provide a good intermediate representation for our purposes, don't particularly care about ease-of-use or keyboard-centricity, and don't make it particularly easy to script parts of your workflow. In the second camp, there are specialized flow editors aimed at programmers or technical managers, which do provide a good deal of flexibility on the keyboard binding front, and provide appropriate output, but also make all kinds of assumptions about what you're doing, why, and how you should want to go about it.

If you know of something awesome that I missed, let me know, but for the moment we're rolling our own. I've been working on it for about half a week solid now, and it's taking shape pretty quickly. I showed off the pre-alpha to some folks at the Erlang conference last week, and got reactions that didn't look like outright disgust. Once it takes some usable shape, I'm planning on posting some videos for you, and possibly showing it off a bit to the FBP group.

I was also going to talk a little bit about fact bases, and the inherent strength of simple models, but I think I'll leave that for another day. When I get permission to Free this editor, I'll have quite a bit more to say about that in any case.

Footnotes

1 - [back] - Har har, aren't I droll.

2 - [back] - Except for UI purposes, obviously. The various selection/manipulation layers are going to have distinct visual cues that rely on color, but I don't count these as part of the diagram proper, even though they may be visually associated.

3 - [back] - Which incidentally kills any use we might get out of svg-edit's or Inkscape's connection tools. Each of them assume a single connection between two shapes, anchored at each center-point. No idea if said connection can be directional or not, but we've already established that it won't do, so I'm not looking into it.

Toronto FBP Group -- Inaugural Meeting Videos

2013-11-13T13:36:00.003-08:00

I've managed to upload the first two videos from the first Toronto FBP Group Meeting to Vimeo.

First, here's Paul Tarvydas giving a brief introduction to FBP. If you're a programmer that's never really heard of Flow Based Programming before, it's a pretty good start.

Second, here's J. Paul Morrison talking about the history of FBP. He's the guy who first discovered the idea, and formalized it while he was working at IBM in the early 1970s, and he talks a bit about what led to the insight. Near the end, he also demos a visual editor he's currently working on.

Sadly, because of the Vimeo basic account limitations, the JP Morrison video has a pretty crappy resolution, and my quick demo talk about a noflo webserver won't be uploaded until next week.

If you really just want the audio and slides, you can get the relevant files right here. You can probably get about 60% of the gist from the audio, but all three of us used some relevant visuals in our presentations. In the case of Paul T. and Paul M., a powerpoint presentation, and in my case some noflo code. I'll try to put up .torrent links for the HD versions of the videos when I figure out the logistics, and the third video will go up next Tuesday.

There were no videos from the second meetup[1], and there won't be any from today[2]. We're basically trying to figure out how to pay for them; one idea I'm looking into is getting a monthly kickstarter going to let the market decide if there's enough interest to produce videos for a given month. I'm not sure how much advance notice we'll need, or how far we can actually plan out talks, but I'll keep you posted.

EDIT:

Torrents are now up along with the audio and presentation materials. If you do end up downloading these, please seed as long as you can.

Thu, 14 Nov, 2013 FURTHER EDIT:

The third video is now up here. In it, I briefly introduce noflo. If you'd like a half-way decent drinking game, take a shot whenever I say "actually".

Footnotes

1 - [back] - We basically had a giant whiteboarding session.

2 - [back] - We've got Paul T. talking about visual compilation, and Jo'sh talking about the Drakon editor.

From The Archives - Popularity

2013-11-10T15:06:00.003-08:00

EDITOR'S NOTE: This is a piece I wrote about three years ago, then sat down to copy-edit and polish up today. It was very focused on a few particular, topical anecdotes that my then-co-workers were throwing about. Having read over it equipped with three extra years of hindsight, I'm not sure I'd still be quite as vehement about my opinions as I was here, but don't disagree on any large points. Sun, 10 Nov, 2013

I'm writing this post because I've seen one too many comments of the sort "Well, if PHP is so shitty, then why is it so popular?". Typically this is the main claim in a rebuttal to "PHP is a shit language"[1], and the end result seems to be that a lot of people just sit back and think "Oh yeah, I guess it is popular. It must not be shit, but rugged." Substitute "manly", or "quirky" or similar if you like. As in, yeah, it has flaws, but they're endearing flaws. Like mysql_escape_string being the deprecated precursor to a different function named mysql_real_escape_string (itself also deprecated). And static functions having an odd interpretation of "this". And the complete list of deprecated functions being longer than my average blog post thanks to the fact that they never actually get removed.

I don't care that we've known how to do better language design for at least thirty years, PHP is Rugged©™, goddamit! And it's still more popular than whatever properly designed tool it is that you use!

How do technologies get popular?

This probably won't turn into an article where I mention Common Lisp[2], by the way. The idea of language popularity is almost completely irrelevant to what I'm discussing here; this could be a discussion of any sort of tool and how you'd go about picking one for a particular purpose. The source of popularity is obviously difficult to determine because relatively few things get there, so lets back off a little bit.

What does it mean for a tool to be popular?

Does it have to solve some specific problem better than other tools? Does it need to be better/cheaper/faster than solving that particular problem by hand? Does it need to be more fun or easier to use? Does it have better marketing/sales/promotions than the competition? Is it the first tool to solve a problem sufficiently well?

No. To all of the above.

A tool is popular when enough people have chosen it to perform a given task. Any of the above points contribute to a tool getting chosen, but for each, you can find a large number of counterexamples. Both tools that lacked it and became popular, and tools that had it but went nowhere. So no single element of that list of points is going to make or break you.

Lets look at it from the other side instead though.

What does it take for someone to choose a given tool?

That's a simpler question, but it should get us the same answer. If "popularity" is "being chosen by enough people" then figuring out "how do most people choose" should tell us "what it means to be popular".

A big reason to choose a tool[3] is that it'll get you a job. Again, this has nothing to do with language choice. Lots of people claim "I learned [x] to get a job", and [x] can be "Java" or "C#" with the same probability as "MS Word", "Photoshop", "Wordpress", "typing", "cooking" or "how to drive a bus". So one reason people choose is to get a job. Before we drill down to the next level, any other reasons?

For fun. I know about as many people who paint/design professionally as those who just do it on the weekend to relax[4], and I know plenty of people who just plain like to program. For fun. Like, on nights and weekends. Granted, not everyone works this way, and not every tool has this effect on people to the same degree[5], but it's still one possible reason.

Fitness of purpose maybe? Well, not in practice, no. Fitness of purpose is how you pick a specific class of tool. Which is to say, that's how you know you want a rotary cutter as opposed to a reciprocating saw or a pen and not a sable brush. It still doesn't tell you that you want a Dremel as opposed to a DeWalt, or a Pilot instead of a Bic[6], or ahem, a Lua instead of a PHP. It's also not as high a bar as people might think. I try to be objective about it, but from observation, most people tend to treat "fitness of purpose" as "what tool do I currently know how to use that could sort of be put to this use?" rather than "what is the most effective tool for the problem I'm solving?"

Popularity is the only other big reason I can think of that tools get chosen, but I don't want to recur just yet, so we'll leave that one alone. Back up a bit.

Tools are popular if they'll get you a job.

When will a tool get you a job? Well, when enough employers start putting it on their job listings. Until that point, it's not worth learning it just for that. Tools before that point mostly get adopters that come by because it's fun for them or the tiny minority that have performed a sufficient comparison and found that tool to be the best fit for them out of the ones they compared. In other words "I choose tools that will get me jobs" translates to "I choose tools that employers choose".

So how do employers choose tools?

Well, here, I can actually share some small amount of real-world data. Anecdotal, so take it with a grain of salt, but enough to form a theory. If anyone wants to try being the experimentalist on this one, be my guest. If you did it well enough, I'm sure it'd be publishable.

There are a few major points that impact on what an organization does in terms of technical tool choice[7].

The biggest one is "We'll keep using what we're using". Which is to say, if the previous project turned out to be successful, there will be a big push to use the same tools on the next one. Interestingly, this happens even if the success of the last project had everything to do with the team pulling constant overtime, and nothing at all to do with tool choice. The tools can be actively detrimental to the goal and still reap a rep-boost if the project succeeds. This doesn't really answer anything. How does a company choose their tools on the first project?

What do our developers know how to use?
What do our vendors use?
What do our clients want us to use?
What's the industry standard?

The first one at least has some expert input, but works oddly. You don't get choice bias towards the "best"[9] tool, but rather the most popular. If Bleeb is "better" than Blub, but only two people on a team of ten know Bleeb whereas everyone knows Blub, then the team uses Blub[10]. In other words, no help there; this criteria will get you the popular language without requiring any level of quality or rigor in its design principles.

The second one is just plain odd, and before sitting back and observing, I would have sworn that it would be a really weak reason to use a tool. Companies seem to not care though; if a given preferred vendor uses tool [x] for task [y], then the company tends to use tool [x], even if it's ridiculously awkward to actually use. The vendor is also a company, so they use this same process for picking their tools, so substitute that back once we're done.

The third one is obvious, I hope, but it also boils down to "popularity" because very few clients know the problem space. Typically, they listen to the first/best sales people that talk to them. They're a force though; if your target client wants it on MSSQL and .NET, then it'll either be that or it won't be.

The fourth one is the previous answer on a macro scale; "We'll keep using what we're using (as an industry)". In other words, if there were lots of successful companies using tool [x], we'll use it too[11].

Now, we need to go deeper[12].

How does the first company in an industry pick their tools?

Regardless of any other decision factors, the answer is almost by definition "before they really know what problems those tools will have to solve", and I've already discussed that one pretty thoroughly. There are no clients, so they can't pick that way, there are no other companies or vendors so there is no industry standard. They might look at what similar industries do. Would they use the best possible tool for the job though? Well, no. They're likely to go the "What do our developers know how to use?" route, which we've already discussed above.

The big reasons teams[13] pick a given technology include

how easy is it to hire people that know how to use this? (easier the better)
do we have existing code that we'll need to interface with? (if so, weigh whatever we used on that project favorably)
have we used any technologies in the past for similar purposes to what we're doing here? (if so, weigh those favorably)

and the big one

if I choose this, and anything blows up, will I still be able to make the case to non-technical humans that it was the right choice? (if not, weigh it very unfavorably)

1, 2 and 3 mean that the more popular the language is, the more chance it has of getting entrenched[14]. 4 means the same, but this time "popular" means overall, not just within the tech community. A non-tech has heard the name "PHP" before, enough times to associate it with "the web" and "Facebook" and "Wordpress", but probably hasn't looked into it closely enough to catch complaints from developers[15].

The end result is that, in a sufficiently large company, it's safer to use a popular tool that's poor in the technical sense than it is to use an excellent tool no one's heard of. And that's also been discussed thoroughly, and this time it wasn't even by me. The decision is made purely on the basis of popularity once again.

Shit

We just bottomed out our recursion. Just in case you haven't been keeping score, literally every single level at which a tool can be selected is likely to be filled by the most popular tool in some context, and this popularity never requires, therefore never implies, anything other than popularity. One more time: at no point in the process of selecting a toolkit do most choosers even try to see whether it's shit or not. So I don't care how popular your steaming pile of imperative, counter-intuitive security-exploits-waiting-to-happen is; it's still shit.

Don't let me stop you from eating it, but I remember what it tastes like so I won't be joining you. Or shaking your hand afterwards.

Footnotes

1 - [back] - Which I happen to agree with, actually. If you're looking for details on what languages(Spoiler warning) I'd recommend learning, you're better off reading this instead.

2 - [back] - Except for that.

3 - [back] - Generally among the people I know at least, no judgment here.

4 - [back] - That's what I get for going to design school.

5 - [back] - Point of fact, only one person I know drives a bus for fun. It's been his obsession to work for the TTC since grade 8. I haven't heard from him in a while, but I still remember his room being full of papercraft Orion 3s, and I'm pretty sure he spent every internship opportunity he had on some streetcar route or another.

6 - [back] - The pen fanciers among you are probably ready to tell me that these are the worst possible examples; they're just the most popular common brand pens, not the really good stuff, where quality can make a difference. Really, I should have used foo and bar. You can go now, if you ponder that point hard enough, you pretty much got the gist of the article.

7 - [back] - I'm reigning it in a bit to software tools because that's what I have experience with, but this still seems like it might be a general trend; again, experimentalists welcome.

8 - [back] - In varying order, in my experience, but always on these things.

9 - [back] - Which I'm still quoting. In a book, that's called "foreshadowing". In a game or movie, it's called "setting up the sequel".

10 - [back] - And you get a varying amount of childish name-calling and dismissiveness towards Bleeb.

11 - [back] - Again, disregarding whether the tool had any effect at all on success.

12 - [back] - And at this point, all bets are off, I'm just theorizing, because I haven't observed the decision making process in an industry-defining company. That would be an interesting research project though, let me know if you've got one lined up.

13 - [back] - Not individual developers, but groups of corporate developers complete with leaders, technical or not, who are ultimately responsible to non-tech people further up the hierarchy.

14 - [back] - And note that both points are completely unrelated to how "good" a language is, and entirely dependent on how popular it is.

15 - [back] - Or to determine whether there's a lot of overlap between "good developers" and "developers who complain vocally about PHP".

Briefly, Custom Server Redux

2013-11-10T08:34:00.000-08:00

So you already know I'm building a custom HTTP server for Deal. A question has arisen in my mind: how customized do I want it?

My initial assumption was that I'd just make it the usual general purpose HTTP server, with a few pieces focused on my end goal, but now that I'm waist deep in the guts of this thing, it occurs that I could take it further if I wanted to. For my current purposes, a relatively small subset of HTTP would do just fine. Here are the points I've noticed:

Deal never runs into the situation where both a GET and a POST parameter have the same name. As a result, I can do the Hunchentoot-standard thing and mangle parameters so that get-params and post-params are actually kept in the same associative structure. That simplifies the structure of both request objects and of handler functions, at the cost of differentiating between parameter types.
Because there's never an ambiguity between GET and POST parameters, I don't even really need to differentiate between GET and POST requests. That'll simplify the class tree of incoming requests. Specifically, it'll cap its depth at 1.
There are only two handlers that allow session-less requests, the rest require that the requester have a session[1], so what I could do is just make each request start up a session if a valid session token isn't passed in. That'll occasionally burn a few milliseconds of extra work[2], but it'll remove the need to assert session presence at the application level.
Because Deal is already targeting recent browsers[3], there's no need to support any older version of HTTP.
Finally, because there's only one handler that's going to need to handle extended connections, and the rest will always return immediately, I can more or less ignore request headers. In particular, I never care about Connection[4], Accept[5] or Cache-Control[6].

Acting on each of these assumptions is going to narrow the usefulness of the server, but also significantly simplify it. The optimum is eluding me, though I suspect it might be "as simple as possible" given my end goal for this particular project. Interestingly, even if I decide to do the simple thing for each of the choices outlined above, the end result will still probably be a useful general-purpose game server.

The only really funny part is that, now that I've thought it through, implementing this system as a websocket server[7] seems like it would yield an even simpler architecture. I'll save that one for later though. Step one: simple SSE+session based engine, make sure it works, then rip out its guts again and see what the other way looks like.

Footnotes

1 - [back] - And most of those require that the session be associated with a particular, already-instantiated game table, but optimizing for that seems like it would be going too far.

2 - [back] - When someone who just wants to watch rather than play first checks out a table.

3 - [back] - We're using quite a few features of HTML5 to make the whole thing playable.

4 - [back] - That one that I mentioned will be assumed keep-alive, while the rest assume the reverse.

5 - [back] - You're expecting text/html on the main request, text/event-stream on the subscription and application/json on the rest. If you can't handle those, you won't be able to play in any case.

6 - [back] - Everything other than the static file handlers always re-generates content; the static handlers don't need to change unless the files themselves have actually changed.

7 - [back] - Which multiple people have already recommended to me, so I'm not taking credit for that particular insight.

FBP in Common Lisp

2013-11-06T13:34:00.001-08:00

Guess what!

No.

I can finally tell you what I'm doing at work. A friend has suggested that I just not mention that there are things I still can't talk about, so I won't. In any case, all the interesting stuff is fair game. Apparently, I'm allowed to talk about it in much greater detail than I can write about it because a persistent record is still frightening to some humans. Progress, I guess.

We've been doing Flow Based Programming in Common Lisp.

Damn it feels good to finally get that off my chest. I have no idea how Yegge stopped blogging. I'm guessing he hasn't, but rather just stopped publishing the results. I've been writing about one thing for the past little while, and the number of ideas I need to discuss with the rubber duck at some point is staggering. If my output rate were zero, I would probably have a pretty tenuous grip on my sanity.

This is heading off topic. Once more, with feeling

Flow Based Programming in Common Lisp

I'm not sure what I think about it yet. Lets just be clear about that up-front. You'll find plenty of FBP True Believers on the appropriate Google group [1], but I am not one of those. The fact that I'm willing to throw a couple years behind the idea implies curiosity, nothing more.

A matter quite apart from the underlying structure is our implementation of it, and I am certain that it's over-complicated. Granted, based on all the others I've seen, ours is the least over-complicated, but still. That's something I'll aim to fix, with a personal project as a last resort, if I can't convince anyone else about it. But I digress. Again.

Here's why I'm curious. This is what a basic web server looks like in flow-based terms:

And here's what it looks like once you add SSE capability to it:

and finally, here's what it looks like when we add sessions into the mix

The above is by far the most useful set of images I've got for understanding what's actually going on behind the scenes of a page-view. I've worked through the principles in multiple languages and spent quite a bit of time thinking about it, but until I sat down to draw it out, it didn't feel like I really understood what needed to be done. You probably don't know the same languages I do, but the above is still likely intelligible to you. So that's why I'm curious.

Flow Based Programming vs. Functional Programming

Before I go, I want to tackle this, because several people I've talked to have gotten tripped up in the comparison. Including me. I ended up deleting a few lines from this post that said

The underlying problem for my lack of "wow" reaction might actually be my usual languages. I'm used to thinking about streams moving between inter-connected, lazy processors. That's the main way I conceptualize Haskell. In fact, if you squint just a bit, it's the way you can conceptualize most functional programs, pure or not. -Inaimathi

The difference is that functional programming focuses on partial conceptual separation, whereas FBP takes the isolation concept a few steps further by enforcing complete conceptual separation as well as complete temporal separation. Here's the accompanying thought experiment, just to clarify what I mean by that.

Suppose you were writing in a functional language and wrote the following:

def foo():
   ...
   bar("something")
   baz("something else")

def bar(arg):
   ...
   doStuff()

def baz(arg):
   ...
   doOtherStuff()

Firstly, notice that, while the functions are conceptually separate units[2], foo still has to know about bar and baz. That prevents total isolation. Yes, you can re-define bar and baz in-flight if your language is dynamic enough, but you need to have them both defined and you need to have them named bar and baz before foo can actually run.

Secondly, note that what's happening there is most likely a bunch of synchronous work. That is, when foo calls bar and baz, both calls complete and then foo returns the return value of baz[3]. If you wrote the equivalent in a pure-functional language, the actual work may happen in a different order than you see it written out, subject to what the compiler can prove about the behavior of the functions involved, but bar and baz will still complete before foo does. If they didn't, you'd get some unexpected behavior in any callers of foo.

Now, lets take a look at the apparently equivalent, Lisp-flavoured, FBP-style program.

(define-part foo ()
  ...
  (out! :out "something")
  (out! :log "something else"))

(define-part bar ()
  ...
  (do-stuff))

(define-part baz ()
  (do-other-stuff))

(define-container box 
    (:foo (foo) :bar (bar) :baz (baz))
  ((:foo :out) -> (:bar :in))
  ((:foo :log) -> (:baz :in))))

First, notice that foo doesn't know anything about bar or baz, or anything about the existence of either. At some point during its execution, it outputs two messages to some implementation-dependent output structure, but critically foo itself is not responsible for delivering those outputs to their consumers. That allows for total part-agnosticism; you really can shuffle parts around with pin-equivalent parts and have the result work. In functional or actors-based systems, you can almost do the same; the exception is that since each sender/caller has to name targets in some way, you need to change small chunks of code in places where functions/actors interoperate.

Second, note that there's nothing in this system about the timing of bar and baz. This omission includes the fact that both, either or neither may run before foo completes. In this model of the world, if bar takes a while to run, neither baz nor foo, nor any of their callers are prevented from further operation. The second critical difference is, essentially, that asynchronous operation is the norm.

Footnotes

1 - [back] - Currently mostly Javascripters thanks to the hype surrounding noflo.

2 - [back] - Assuming the programmer hasn't done something "clever" with global variables, gotos or comefroms.

3 - [back] - which happens to be the return value of doOtherStuff.

Xmonad Tweaks

2013-10-21T09:10:00.001-07:00

Just a quickie to share a tweak I had to make to my xmonad.hs. Not sure if there's a better way to do this, but hey.

The goal was to finally, actually get working hibernation on my laptop. I usually use it in short bursts, so I just got used to shutting it down between sessions. However, I recently started using a work laptop running Windows 7 and hibernation has been useful there[1], and I'll be damned if the non-free shitbox is going to have a mildly useful feature that my machine doesn't.

The way you get a Debian machine to hibernate or suspend is with the appropriately named pm-hibernate and pm-suspend commands[2], so I figured this would be a fairly easy key binding

...
, ("C-t C-<Delete>", spawn "pm-suspend")
, ("C-t <Delete>", spawn "pm-hibernate")
...

Unfortunately, the pm-* are root user commands. And Xmonad doesn't automatically prompt for a password when you do something like su -c pm-suspend. And, unlike with sudo, you can't pass a password into su. So that approach is right out.

I googled around for alternatives for a little while, but What I ended up doing was finally adding myself to the sudo group, and defining this function for my own nefarious purposes

sudoSpawn command = withPrompt "Password" $ run command
  where run command password = spawn $ concat ["echo ", password, " | sudo -S ", command]

withPrompt is another little utility piece I had written for some desktop changers; it's defined as

withPrompt prompt fn = inputPrompt xpConf prompt ?+ fn

The above defined, I can now bind super-user commands to Xmonad keystrokes

...
, ("C-t C-<Delete>", sudoSpawn "pm-suspend")
, ("C-t <Delete>", sudoSpawn "pm-hibernate")
...

with the caveat that I need to enter my password each time I invoke these. I'll see if that's too annoying. Worst case scenario, I'll pull some trickery to cache it the first time I enter it.

Just in case you care, my complete xmonad.hs now looks like:

import System.Directory
import XMonad
import XMonad.Actions.CycleWS
import XMonad.Actions.CycleWindows
import XMonad.Actions.WindowGo
import XMonad.Actions.GridSelect
import XMonad.Prompt
import XMonad.Prompt.Input
import XMonad.Util.EZConfig
import XMonad.Util.CustomKeys

import qualified XMonad.StackSet as S

main = xmonad $ conf
       `additionalKeysP`
       [ ("C-t C-d C-b", withFilePrompt "Pic: " bgFolder setDesktopBackground)
       , ("<Print>", withFilePrompt "Name: " screenshotFolder capToFile)
         
       , ("C-t C-<Delete>", sudoSpawn "pm-suspend")
       , ("C-t <Delete>", sudoSpawn "pm-hibernate")
         
       , ("C-t p", spawn "dmenu_run")
       , ("C-t C-p", spawn "dmenu_run")
       , ("C-t <Return>", spawn "xterm")
       , ("C-t e", runOrRaise "emacs" (className =? "Emacs"))
       , ("C-t C-e", runOrRaise "emacs" (className =? "Emacs"))
       , ("C-t b", spawn "chromium --proxy-server=\"socks://localhost:9050\" --incognito")
       , ("C-t C-b", spawn "chromium --proxy-server=\"socks://localhost:9050\" --user-agent=\"Mozilla/5.0 (Windows NT 5.1) AppleWebKit/537.4 (KHTML, like Gecko) Chrome/22.0.1229.94 Safari/537.4\"")
         
       , ("C-t s", nextWS)
       , ("C-t C-s", prevWS)
       , ("C-t w", toggleWS)
       , ("C-t C-w", toggleWS)
       , ("C-t C-t", windowSwap)
       , ("C-t t", windows S.swapDown)
       , ("C-t C-j", windows S.swapDown)
       , ("C-t j", windows S.focusDown)
       , ("C-t k", windows S.focusUp)
       , ("C-t C-k", windows S.swapUp)
       , ("C-t g", goToSelected defaultGSConfig)
         
       , ("C-t C-<Space>", sendMessage NextLayout)
       , ("C-t C-h", sendMessage Shrink)
       , ("C-t C-l", sendMessage Expand)
         
       ]
  where conf = defaultConfig { XMonad.startupHook = onStartup, modMask = mod4Mask }

---------- Config Options
bgFolder = "/home/inaimathi/pictures/backgrounds/"
screenshotFolder = "/home/inaimathi/pictures/screenshots/"

onStartup :: X ()
onStartup = do
  spawn "set-monitors"
  spawn "pmount /dev/mmcblk0p1"
  setDesktopBackground "edge-of-the-world.jpg"

---------- Helper Functions
setDesktopBackground :: MonadIO m => String -> m ()
setDesktopBackground pic = spawn $ concat ["feh --no-xinerama --bg-fill ", bgFolder, pic]
        
capToFile :: MonadIO m => String -> m ()
capToFile picName = spawn $ concat ["import ", screenshotFolder, picName]

sudoSpawn command = withPrompt "Password" $ run command
  where run command password = spawn $ concat ["echo ", password, " | sudo -S ", command]

---------- Utility
windowSwap = do
  windows S.focusDown
  windows S.swapUp

xpConf = defaultXPConfig { position = Top }

withPrompt prompt fn = inputPrompt xpConf prompt ?+ fn

withCompletingPrompt prompt completions fn = 
  inputPromptWithCompl xpConf prompt comp ?+ fn
  where comp = mkComplFunFromList completions

withFilePrompt prompt directory fn = do
  files <- liftIO $ getDirectoryContents directory
  let fs = filter relevant files
      relevant f = '.' /= head f
  withCompletingPrompt prompt fs fn

Footnotes

1 - [back] - Granted, because the boot time on that machine is something like 5 minutes instead of the 12 seconds I'm used to waiting, Hibernate is a goddamn necessity, but I digress.

2 - [back] - Ideally, I'd just be using hibernate, but there are some issues. I've upgraded my ram since installing the OS, which means that my swap partition isn't big enough to store a memory dump, and I can't seem to resize it with gparted, with or without swapoff/swapon magic. Luckily, I've had a larger hard drive waiting for me to crack open the box and configure it to my liking, so I'll just do that this week rather than procrastinating. In the meantime though, I'm suspending instead.

language agnostic

The Blog Has Moved

Arbitrary Update 932

cl-notebook/fact-base

Memory

Not

Manual

Mark-and-sweep and variants

Reference-counting

Circular Memory

Decentralization

cl-notebook Thoughts

Being async Pays

Being surgical pays. Sometimes. Not in the way you'd think.

Thinking About Space Doesn't Pay. No, not even that much.

Return Values are Complicated

cell-type is not the same thing as cell-language

Naming things is difficult

cl-notebook Introductory Thoughts

Notebooks

cl-notebook

Core Concepts

Example

Querying Fact Bases Redux

lookup and decide-index changes - take 1

lookup and decide-index changes - take 2

This

Traversal Notes

Footnotes

Querying Fact Bases

Footnotes

Buildapp Minutia

Be careful with your storage folders

Native SBCL shell sucks balls under Windows

Finding dependencies is ... non-trivial

Footnotes

Fact Base Indices

The Idea of an index

The Post-Explanation Version

Footnotes

Housekeeping

cl-cwd

fact-base updates and relevant minutia

Editors

Footnotes

Flow-Based Games

Autocompletion Example with Ports in Elm

Elm Lang

Elm. Again.

The New Part

In Case You're Reading, evancz

Footnotes

Fact Bases and Total History

Let me back up...

Now then...

Storing deletion tokens...

Wrapping up...

Update, and the Finer Points of Quasimodes

AOSA Chapter

2dmacs

Quasimodes

Selections

Footnotes

Which Lisp Should I Learn?

My Recommendation

Why

Footnotes

Debian Testing, Pi and Git

New Drive

Fresh Install

Dicking Around With Pis

cl-git-fs

Footnotes

Implementing Humane Authentication

Thoughts

Footnotes

Jef Raskin on Authentication

How does a user log in?

What happens when the user enters a passphrase that isn't currently assigned?

How does the registration process work?

`cell-type` is not the same thing as `cell-language`

`cl-notebook`

`lookup` and `decide-index` changes - take 1

`lookup` and `decide-index` changes - take 2

The Idea of an `index`

`fact-base` updates and relevant minutia