Adding a Span type to Push

continues “When do continuous spans overlap?”

Yesterday I spent some time working on what I called (in my innocence) the “simple infrastructure” for creating a Span type in the Klapaucius interpreter. I got as far as a working implementation of a notional span primitive represented with a :start and :end value, each of which could be “open” or “closed”.

There were a lot of edge cases. I suspected I’d think of new ones overnight, but this morning I haven’t found any. We’ll see if that holds up as I proceed with building the actual Push language type today.

Starting a Klapaucius type definition

As I said yesterday, given the “infrastructure” I feel I need, I think I can go ahead and start constructing the Push type using the Klapaucius library’s functions. In broad terms, I’ll want a file like push.type.item.span where I define the instruction code for all of the actual :span-related instructions I want to create (like those in the list I appended to yesterday’s essay, plus the more mundane ones that convert between :span and other Push items). And also, because I know how much of an idiot I can be, push.instructions.base.span_test to actually exercise those instruction definitions and ensure they do what I intend them to do.

There’s one thing I will need first, to define a proper Push type: I’ll need a recognizer function for the :span type, and I may as well add that to the push.type.definitions.span file I was working in yesterday. This needs to be a predicate function that returns true when the item is something I want to be recognized as a :span item by the interpreter, and I need it whether it will appear in a program passed in as an argument to an interpreter, or as an intermediate result of some calculation produced while such a program is running.

I look at some of the recognizers I’ve written before, just to get a sense of what I’m supposed to do. push.types.definition.complex has the complex? function, which looks like this

(defn complex?
  "a type checker that returns true if the argument is
  a Complex record; note that this does not recognize 
  'trivially' complex numbers (reals or pure imaginary 
  ones)"
  [item]
  (instance? push.type.definitions.complex.Complex item))

That’s pretty straightforward (it’s just checking that the item is a Complex record as defined in the same file), so I emulate it in push.types.definitions.span with this function:

(defn span?
  "a type checker that returns true if the argument is a Span record"
  [item]
  (instance? push.type.definitions.span.Span item))

I’ve never been entirely comfortable with Clojure’s namespace system, and this particular class name is especially awkward-feeling because it’s way down in the tree so far (five layers?), but I’m not going to get side-tracked into refactoring all the references to all the definitions files right now.

I should test even this trivial thing, after yesterday’s fiasco with the edge cases. So I add a quick check in push.type.definitions.span_test like this:

(fact "span? recognizes a Span item"
  (span? 99) => false
  (span? (make-span 1 1)) => true
  )

That’s working well enough, so I create a new file push.type.item.span by… well, you can call it “emulating what I see in other files”, but really what I did was copy-and-paste from push.type.item.complex and then delete all the stuff I didn’t think I needed yet.

(ns push.type.item.span
  (:require [push.type.core :as t]
            ))

(def span-type
  (-> (t/make-type  :span
                    :recognized-by push.type.definitions.span/span?
                    :attributes #{:numeric :set})
  ))

In the present incarnation of the Klapaucius interpreter system, this uses push.type.core/make-type to construct a new PushType record in a var. The Clojure keyword :span is the “name” of the type, and will be the name o fthe stack onto which the interpreter pushes items it recognizes. The :recognized-by function is stored (for now) in the var, but when the type defined here is registered with a new interpreter, that will be copied over into the interpreter’s :router table so it can send items to the correct stacks. Finally the :attributes, which… well, they’re complicated. For the moment they’re the residuum of an unfinished functionality. Think of them here as being “tags” I can use to recall what a given type “acts like”, although very soon they’ll have a proper function.

I ain’t perfect, as you can tell by now.

This type definition is absolutely bare-bones, though. There are no instructions, no functionality at all beyond the recognition by an interpreter that these things are things that should go to a stack called :span. I think I’ll add some common aspects first, just to get rolling.

In Klapaucius, an aspect is a whole suite of programmatically-constructed instructions associated with a type or module. For instance, making :span an equatable type grants it two new instructions: :span-equal? and :span-notequal?. Similarly, visible includes :span-stackdepth and :span-empty? instructions, and so on. Most of these aspects provide reasonable and helpful-seeming functionality, and in general almost all new types and modules will want them all, except perhaps for comparable (which only applies to items which are, surprisingly comparable using < and >), and the ones that work on collections. While my new Span thing is a Clojure record and therefore technically a sort of very small collection, I’d rather not have it chopped up and parceled out into a :tagspace or :generator, so I’ll leave those off.

Here’s what I add—and it also points out the reason for that -> function left over from my copy-and-paste trip from the :complex type definition.

(ns push.type.item.span
  (:require [push.type.core :as t]
            [push.instructions.aspects :as aspects]
            ))

;; (instructions will be defined here)

(def span-type
  (-> (t/make-type  :span
                    :recognized-by push.type.definitions.span/span?
                    :attributes #{:numeric :set})
        aspects/make-equatable
        aspects/make-movable
        aspects/make-printable
        aspects/make-quotable
        aspects/make-repeatable
        aspects/make-returnable
        aspects/make-storable
        aspects/make-taggable
        aspects/make-visible 
  ))

Temporarily—but also to get a sense of ways I might simplify this process in future, since I personally find it kind of onerous and complex—I create push.instructions.base.span_test now, and make it look like this:

(ns push.instructions.base.span_test
  (:require [push.interpreter.core :as i])
  (:use midje.sweet)
  (:use [push.util.test-helpers])
  (:use [push.type.item.span])
  )


(fact "the :span type knows some instructions"
  (keys (:instructions span-type)) => 88
  )

The headers are things all the other push.instructions.*.*_test namespaces use, so I’ve really just copied-and-pasted again. I should spend a day making some generators, I realize… but again, not today.

In that simple check, I’m using Midje’s excellent error reporting to produce an intentional “failure” so I can just glance at it and make sure the instructions defined by the aspects I’ve already loaded are actually present. When I run the tests, the failure message gives me the information I actually wanted for my own peace of mind:

======================================================================
Loading (push.instructions.base.span_test)

FAIL "the :span type knows some instructions" at (span_test.clj:11)
    Expected: 88
      Actual: (:span-liftstack :span-flush :span-pop :span-cutflip
      :span-notequal? :span-print :span-save :span-swap
      :span-rotate :span-echoall :span-return-pop :span-yankdup
      :span-storestack :span-againlater :span-cutstack :span-echo
      :span-store :span-empty? :span->code :span-stackdepth
      :span-rerunall :span-equal? :span-later :span-shove 
      :span-dup :span-savestack :span-yank :span-tag 
      :span-flipstack :span-return)
FAILURE: 1 check failed. 
[Completed at 08:51:57]

When I started working on this interpreter, I would copy that list over to the check itself and then leave those sorts of tests lying around, but of course you already can see they’re not maintainable as they exist. Every time I’d add a new type, or aspect, or make some other change with consequences, the items on the list would change. A few of them are still sitting around in the pile of tests, but when I come across them now I delete them, since they don’t check something I want or need to check any more. After all, I don’t want to know there are exactly those 30 instructions for this particular type; indeed, as soon as I get back to defining the type, the list will expand!

Tests themselves need to be maintainable. So I delete this one, satisfied for now that my automatically-constructed instructions are present already in the span-type definition.

Making Spans “do things”

Now it’s time to add some of those instructions I described yesterday, plus any other obvious ones. There are a few things I am reminded to keep in mind, though:

1. Basic functionality and behavior be handled by explicit instructions; “simple” stuff like whether two :span items coincide isn’t handled by the equatable aspect, which just checks whether they’re identical or nonidentical
2. Some of the instructions I sketched yesterday use the “helper” definitions I developed yesterday too; others seem like they can manipulate the structures “in place” right in the instruction definitions. I’ll see soon enough if I need more “helpers”.
3. There need to be conversion instructions to build, disassemble, set and get the component values of :span items. Lacking those, the type is “detached” from the rest of the language, and tends in automated searches to become a dead end.

Looking at the list of instructions already “known” by span-type, I think I’d like to add a :span-coincide? checker first. It’s simple, and it feels like it might be useful.

In the year I’ve been working on this, I’ve developed a variety of crufty but helpful test helpers, building on Midje’s tabular test format. Here’s a tabular test I find very useful: It constructs a new interpreter, registers the specified type (span-type, here), sets the initial stack specified to the values I provide, executes the indicated instruction (span-coincide?), and then checks the stack I specify to ensure it matches my expectation.

(ns push.instructions.base.span_test
  (:require [push.interpreter.core :as i])
  (:use midje.sweet)
  (:use [push.util.test-helpers])
  (:require [push.type.definitions.span :as s])
  (:use [push.type.item.span])
  )

(tabular
  (fact ":span-coincide? returns the true if two Spans are equal or reversed orientation"
    (register-type-and-check-instruction
        ?set-stack ?items span-type ?instruction ?get-stack) => ?expected)

    ?set-stack  ?items       ?instruction        ?get-stack     ?expected
    
    :span    (list (make-span 2 3) (make-span 2 3))
                             :span-coincide?     :boolean       '(true)
    )

Here I’m saying “When there are two identical :span items present, and :span-coincide? is executed, I want the top item on the :boolean stack to be the value true.” This fails, of course, because I haven’t defined the :span-coincide? instruction yet. But it does what I wanted.

Now I define :span-coincide? and attach it to span-type. I run into some namespace glitches (like I already said, I’m not entirely comfy with the Clojure tendency to build big Jenga towers out of path information), and restructure the namespace headers a bit for clarity as well. The new type definition file looks like this, now:

(ns push.type.item.span
  (:use     [push.instructions.dsl]
            [push.type.core]
            [push.instructions.core])
  (:require [push.instructions.aspects :as aspects]
            [push.type.definitions.span :as span]
            ))


(def span-coincide?
  (build-instruction
    span-coincide?
    "`:span-coincide?` pops the top two `:span` items and pushes `true` if they coincide: that is, if they are equal or one is the reverse of the other (including open ends)"
    :tags #{:span}
    (consume-top-of :span :as :arg2)
    (consume-top-of :span :as :arg1)
    (calculate [:arg1 :arg2] #(span/span-coincide? %1 %2) :as :result)
    (push-onto :boolean :result)
    ))


(def span-type
  (-> (make-type  :span
                  :recognized-by push.type.definitions.span/span?
                  :attributes #{:numeric :set})
        aspects/make-equatable
        aspects/make-movable
        aspects/make-printable
        aspects/make-quotable
        aspects/make-repeatable
        aspects/make-returnable
        aspects/make-storable
        aspects/make-taggable
        aspects/make-visible 
        (attach-instruction , span-coincide?)
  ))

I’ve cleaned up the namespace chaff a bit by using :use in the headers, but the important things are (1) the definition of the Push instruction span-coincide?, which is written in the PushDSL, and (2) the attach-instruction line near the bottom, which actually attaches the PushInstruction record to the span-type record.

I’ve gone over details elsewhere in depth, but here’s what that build-instruction macro call actually does:

1. The :token of the new instruction becomes :span-coincide?
2. The docstring is associated with it
3. The :tags set is associated with it
4. The four function calls that follow are, as a unit saved as the :transaction of the instruction. Whenever this instruction is executed by an interpreter, those four steps will be invoked on the interpreter state. What they do is:
   1. pop the top :span item and call it :arg2
   2. pop the (new) top :span item, and call it :arg1
   3. determine the results of applying the helper span/span-coincide? to those two arguments, and call the result :result
   4. push :result onto the :boolean stack

My first test passes now, and so I add a few more test cases to exercise the new instruction and make sure it does more or less what I expect:

(ns push.instructions.base.span_test
  (:require [push.interpreter.core :as i])
  (:use midje.sweet)
  (:use [push.util.test-helpers])
  (:require [push.type.definitions.span :as s])
  (:use [push.type.item.span])
  )



(tabular
  (fact ":span-coincide? returns the true if two Spans are equal or reversed orientation"
    (register-type-and-check-instruction
        ?set-stack ?items span-type ?instruction ?get-stack) => ?expected)

    ?set-stack  ?items       ?instruction        ?get-stack     ?expected

    :span    (list (s/make-span 2 3) (s/make-span 2 3))
                             :span-coincide?     :boolean       '(true)
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
    :span    (list (s/make-span 2 3) (s/make-span 2 4))
                             :span-coincide?     :boolean       '(false)
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
    :span    (list (s/make-open-span 2 3) (s/make-span 2 3))
                             :span-coincide?     :boolean       '(false)
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
    :span    (list (s/make-span 2 3) (s/make-span 3 2))
                             :span-coincide?     :boolean       '(true)
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
    :span    (list (s/make-span 2 3 :start-open? true)
                   (s/make-span 3 2 :end-open? true))
                             :span-coincide?     :boolean       '(true)
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
    :span    (list (s/make-span 2 3 :start-open? true)
                   (s/make-span 3 2 :start-open? true))
                             :span-coincide?     :boolean       '(false)
    )

It’s not especially pretty, especially when I paste it into this editor and render it on the web, but it acts the way I’d expect and desire.

More functions

Yesterday I wrote Clojure functions that defined behavior in the context of the Span record. But the Clojure type is not the Push type, so now I need to add Push instructions, like the one above, to handle the behavior I want Push to implement.

The biggest reason for this is, I suppose, a sort of interconnected parts argument. In Clojure, a human-writable language, when I say (defn foo [x y]...) I am defining a function that will be applied by me when I know I have an x and a y already in my hand. In the Push language, which is designed to be evolved, the invocation of a given instruction can happen at any time, in any order or context. There might not be an x or y on hand, or there might not even be a :span type registered in the interpreter I’m running! Thus, every Push instruction is wrapped in a substantial suite of argument-checking, validation, failure checking, and more. Not only is this the argument for the weird-seeming PushDSL definitions—because the PushDSL constructs almost all of that transparently for me—but it’s the reason I need both Clojure and Push definitions of essentially the “same functionality”.

But they’re not the same functionality, of course. The Clojure (defn foo [x y]...) creates Clojure code. The Push interpreter, written in Clojure, is designed to read and execute Push code, which is a completely different language.

Anyway, here are some things I think :span should do, and which should probably be made into Push instructions:

• :span-reverse
• :span-empty?
• :span-direction (returns -1, 0 or 1 depending on the relation between :start and :end, with 1 meaning “vector in the positive direction”)
• :span-include? (which checks whether a :scalar is inside the :span)
• :span-surrounds?
• :span-overlaps?
• :span-flip (switches :start and :end but not their openness)
• :span-extent
• :span-combine
• :span-gap
• :span-space
• :span-error
• :span-reverse
• :span-close
• :span-open
• :span-subtract
• :span-xor
• :span-intersection
• :span-open?
• :span-closed?

Oh, and also here are some instructions in support of interoperability with other Push types:

• :span-new
• :span->scalars
• … maybe some more?

I’m not going to bore you with the (essentially copy-and-paste work I do for all these, but I’ll come back and report on some highlights and observations as I get these done.

Later…

I mentioned I’d constructed a few kludgey test helpers through the months I’ve been working on the Klapaucius interpreter, and here’s another one that comes up when I need to test :span-include?. For this one, the setup state involves items on multiple interpreter stacks (one :scalar and one :span). So here (and for subsequent tests of the same sort) I use a slightly different template I’ve built, which arranges that all the stacks I specify are set up, and checks all the stacks I specify against the resulting interpreter state.

(tabular
  (fact ":span-include? says whether a :scalar falls in a :span"
    (check-instruction-with-all-kinds-of-stack-stuff
        ?new-stacks span-type ?instruction) => (contains ?expected))

    ?new-stacks                ?instruction             ?expected
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
    {:span (list (s/make-span 2 3))
     :scalar  '(2)}           :span-include?            {:boolean '(true)}
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
    {:span (list (s/make-span 2 3))
     :scalar  '(4)}           :span-include?            {:boolean '(false)}
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
    {:span (list (s/make-span 3 2))
     :scalar  '(2.7)}         :span-include?            {:boolean '(true)}
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
    {:span (list (s/make-span 3 2 :start-open? true))
     :scalar  '(2)}           :span-include?            {:boolean '(true)}
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
    {:span (list (s/make-span 3 2 :start-open? true))
     :scalar  '(3)}           :span-include?            {:boolean '(false)}
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
    {:span (list (s/make-open-span 3 3))
     :scalar  '(3)}           :span-include?            {:boolean '(false)}
    )

That is to say, “when the top :span item is such-and-such, and the top :scalar is this, and I execute the :span-include? instruction, then the :boolean stack should be this….”

This instruction is pretty simple, by the way, since I wrote the Clojure code it invokes yesterday:

(def span-include?
  (build-instruction
    span-include?
    "`:span-include?` pops the top `:span` and top `:scalar`, and pushes `true` if the `:scalar` value falls (strictly!) within the `:span`, taking openness of the ends into account"
    :tags #{:span}
    (consume-top-of :span :as :span)
    (consume-top-of :scalar :as :number)
    (calculate [:span :number] #(span/span-include? %1 %2) :as :result)
    (push-onto :boolean :result)
    ))

Make sense?

In Which an Accident Occurs

Aha! I said I’d find more edge cases that I’d missed yesterday, and I did.

I thought the :span-surrounds? instruction would pretty easy, since like the :span-include? one above it just calls the function I created yesterday. But I wrote the tests, and this one failed:

(tabular
  (fact ":span-surrounds? returns the true if the top Span is surrounded by the second"
    (register-type-and-check-instruction
        ?set-stack ?items span-type ?instruction ?get-stack) => ?expected)

    ?set-stack  ?items       ?instruction        ?get-stack     ?expected

    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
    :span    (list (s/make-span 2 3) (s/make-span 2 3 :start-open true))
                             :span-surrounds?     :boolean       '(false)
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
    )

Which is to say, the Span (make-span 2 3) should not be surrounded by (make-span 2 3 :start-open true). Why? Because the :start of the former is not part of the latter Span.

In an eye-rolling state of mind, I look back over the helpers in push.type.definitions.span, and sure enough:

(defn span-surrounds?
  "Takes two spans, and returns `true` if the first one completely surrounds the second one; that is if both ends fall strictly within the first span."
  [span1 span2]
  (let [s2 (:start span2)
        e2 (:end span2)]
    (and (span-include? span1 s2) (span-include? span1 e2))))

That doesn’t even try to check the openness conditions. Dagnabbit. In fact, it’s exactly the concern I had yesterday: I actually check the openness state of the ends of … hang on.

Nope nope nope. Nope!

Here’s what happened:

1. I saw the test failed
2. I knew it relied on push.types.definitions.span/span-surrounds?
3. I glanced at that definition, and realized it didn’t check openness of ends, so I was immediately suspicious because of all the rigamarole yesterday
4. I looked at the tests and definition for push.types.definitions.span/span-include?, but that looked pretty sound. In particular, it actually does check the openness of the ends of the span, when checking to see if a point falls within it…
5. Something’s not quite right
6. I look at the tests for push.types.definitions.span/span-surrounds? and notice there’s one exactly like the one I just wrote… or is it?
7. I look at the test I wrote, which started this whole tirade, and it’s missing a question mark. That is: (list (s/make-span 2 3) (s/make-span 2 3 :start-open true)) is not the same as (list (s/make-span 2 3) (s/make-span 2 3 :start-open? true)). The former creates a closed record, not a half-open one, since undefined keyword arguments are ignored by default in Clojure, and :start-open is not :start-open?.

Object lesson? When things start to feel too complicated to handle just by being more careful, it’s not just a superstition. I don’t immediately see how to simplify the definitions I’ve already got, but I’m actually pleased that the tests told me more or less what I wanted them to say.

Now imagine what might have happened if I hadn’t bothered testing the “helpers” I wrote yesterday. When I overhear colleagues in the Clojure community talking about “mysterious bugs”, I always end up wondering what kind of tests, if any, they could have written to help them.

The point of extensive unit testing isn’t to eliminate bugs. It’s to help you understand and explain them when you inevitably introduce a new one.

That really warms the cockles of my heart, that does. I swear I didn’t plan it. OK, back to work….

Later…

I didn’t get very far.

(tabular
  (fact ":span-surrounds? returns the true if the top Span is surrounded by the second"
    (register-type-and-check-instruction
        ?set-stack ?items span-type ?instruction ?get-stack) => ?expected)

    ?set-stack  ?items       ?instruction        ?get-stack     ?expected

    :span    (list (s/make-open-span 2 3) (s/make-span 2 3 :start-open? true))
                             :span-surrounds?     :boolean       '(true)
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
    )

This test checks that a fully-open span is surrounded by an identical one except with one closed end. Mathematically I guess I’m saying that “\((2,3) \subset (2,3]\)”, where I really mean strict subset by “\(\subset\)”.

Amusingly, this is exactly the edge case I thought my typo was pointing out. Which means it’s time to take a nap….

Continued in “Adding a Span type to Push, part 2”…