# The Interval Push type in Klapaucius

Draft of 2016.07.06

May include: Push ↗ GP ↖ learning in public ↙ &c.

Continues “Rethinking the Push Span type”

I feel somehow as if I were on the right track again. Interesting how a bit of frustration and code smell can divert you from a path towards delivering working features, and (as several people have pointed out) it’s always good to be reminded of the First Law of Holes.

Back to the track.

In the last episode, with a very few changes and some cunning improvements in naming, I managed to rework the `Span`

structure I had been developing into a more elegant `Interval`

. I like this much better because it has a robust and common interpretation—the first idea I had, which became `Span`

, was derived from this same source, but I did one of my ill-considered “why not?” moves when it came to the bounds. The `Span`

was defined as a continuous set between a `:start`

and `:end`

point, and thus could be oriented in either direction, which surprisingly led to several confusions on my part and (I think) pushed the combinatorial set of edge cases for testing over a magical limit my brain couldn’t handle.

More in keeping with its mathematical origins, the new `Interval`

has a `:min`

and `:max`

rather than `:start`

and `:end`

, and as a result it handles a lot of the mental overhead about numerical geography *for* me. The `:min`

will be less than (or equal to) the `:max`

, so all `Interval`

records are implicitly ordered in the same way.

As a bonus, at least for me, the word “interval” is actually more appropriate, and comes with some nice robust lists of use cases and algebraic habits. For instance, interval arithmetic is feasible, in addition to my scant subset of instructions inspired by `Span`

manipulations.

My goal today is to finish and release a working type in the `master`

branch of Klapaucius. Once I’ve reached the point where it “feels” simple and straightforward to add new instructions to the type—which I sense I might have now—I get a sense that some or all of the “weirder” instructions might be left aside as project Issues for another day. One of the core design goals in Klapaucius itself to include sufficient diversity of instruction behavior and interconnectedness that there’s a *prospect* of reaching a solution by at least two different paths. This is a bit vague and philosophical, but in practice it boils down to being most concerned for interconversion of types.

I think I’ll work on that next.

## Making an `Interval`

The Klapaucius library recently went through a big rewrite, in which the traditional Push `:float`

and `:integer`

were consolidated into a single `:scalar`

type. Things like `:interval`

become much easier to construct as a result, since one doesn’t need to *pick* `:integer`

or `:float`

(or `:rational`

or…) endpoints to build one.

(def interval-new (build-instruction interval-new "`:interval-new` pops the top two `:scalar` items (`B` and `A`, respectively) and creates a new `:interval` item [A,B]. Both ends are closed." :tags #{:interval} (consume-top-of :scalar :as :arg2) (consume-top-of :scalar :as :arg1) (calculate [:arg1 :arg2] #(interval/make-interval %1 %2) :as :result) (push-onto :interval :result) ))

and an accompanying test:

(tabular (fact ":interval-new builds one out of two :scalar values" (register-type-and-check-instruction ?set-stack ?items interval-type ?instruction ?get-stack) => ?expected) ?set-stack ?items ?instruction ?get-stack ?expected :scalar '(2 3) :interval-new :interval (list (s/make-interval 2 3)) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; :scalar '(3 2) :interval-new :interval (list (s/make-interval 2 3)) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; :scalar '(3 3) :interval-new :interval (list (s/make-interval 3 3)) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; )

This instruction consumes `:scalar`

values to build an `:interval`

, but it doesn’t leave the possibility of either end being open. In my testing I’ve made do with `make-interval`

and `make-open-interval`

, so I wonder if I could take that route in Push as well, maybe with something that *toggles* the openness of the ends. Seems like a plan.

I implement a Push instruction called `:interval-newopen`

, which calles `make-open-interval`

, and discover a bug left over from the conversion of `Span`

to `Interval`

, in which the `:min`

and `:max`

weren’t sorted. Feels like I should consolidate that behavior somehow, but I don’t immediately see a place to do so.

Later…

I decide to make this work using two `:boolean`

values, for the moment. In a Slack conversation about it, Matthew Weitzel wonders (as I do) whether something like binary `filemode`

would work as well, using a `:scalar`

reduced to a sequence of bits, but I think that is actually a nice thing to make an Issue in the project: there are several places I can see that being a way for programs to summarize structured binary states, like with filtering collections.

But with `:interval-new`

, `:interval-newopen`

and `:interval-rebracket`

(def interval-rebracket (build-instruction interval-rebracket "`:interval-rebracket` pops the top `:scalar` item and two `:boolean` values (`B` and `A`, respectively). The `:min-open?` value is set to `A`, the `:max-open?` value is set to `B`, and the resulting `:interval` is pushed as a result." :tags #{:interval} (consume-top-of :boolean :as :max?) (consume-top-of :boolean :as :min?) (consume-top-of :interval :as :i) (calculate [:i :min? :max?] #(interval/make-interval (:min %1) (:max %1) :min-open? %2 :max-open? %3) :as :result) (push-onto :interval :result) ))

This seems to be working pretty well. I am reminded there was a list of possible `:span`

instructions I’d sketched back in the very first stage of this work. I want to revisit that now before tacking interval arithmetic.

## Interacting intervals

There was a thing called `:span-extent`

, which I think is better called `:interval-hull`

now. That is, it takes two `:interval`

items and returns a new one with the maximum extent of both, preserving the inclusiveness of the ends.

This turns out to be rather painless:

(def interval-hull (build-instruction interval-hull "`:interval-hull` pops the top two `:interval` items and pushes a new `:interval` whose extent is the hull of the arguments. That is, it reaches from the smallest `:min` to the largest `:max`, preserving inclusiveness of the ends." :tags #{:interval} (consume-top-of :interval :as :i2) (consume-top-of :interval :as :i1) (calculate [:i1 :i2] #(interval/make-interval (min (:min %1) (:min %2)) (max (:max %1) (:max %2)) :min-open? (and (:min-open? %1) (:min-open? %2)) :max-open? (and (:max-open? %1) (:max-open? %2))) :as :result) (push-onto :interval :result) ))

Here I’m taking advantage of the fact that the `:min`

of the result will be the `min`

of both `:min`

values. Confusing nomenclature, but valid. The openness is slightly more challenging, but basically if two ends coincide, I only want the result to be open if both arguments were. That is, if the endpoint of an `Interval`

is included as part of that interval, I want it to be part of the result as well.

Next, there was an idea in `:span-net`

, which was thinking of connecting the start of one `Span`

to the end of another. This depends, in a real way, on the fact that `Span`

was oriented; I can no longer think about these with `Interval`

, as such. Also, there were four variations on this theme: `start->end`

, `end->start`

, `start->start`

and `end->end`

.

I’m tempted to consolidate these into a sort of *crossover* operation on `Interval`

. That is, it takes two as arguments, but produces all four results. Let some other process sort through them to discover the useful one. There’s a long-running suspicion of mine that far too many Push instructions reduce the number of literals on hand, too, resulting in a sort of *argument starvation* of running Push programs. I’m going to err on the side of diversification here.

The result is wordier than I expect, but that’s honest work; it returns a code block of four `:interval`

items.

(def interval-crossover (build-instruction interval-crossover "`:interval-crossover` pops the top two `:interval` items (call them `B` and `A`, respectively) and pushes a code block containing the four FOIL `:interval` items onto `:exec`. The results (in order) are `(make-interval (:min A) (:min B))`, `(make-interval (:min A) (:max B))`, `(make-interval (:max A) (:min B))` and `(make-interval (:max A) (:max B))`, and they preserve the openness of the points included the resulting intervals." :tags #{:interval} (consume-top-of :interval :as :B) (consume-top-of :interval :as :A) (calculate [:A :B] #(interval/make-interval (:min %1) (:min %2) :min-open? (:min-open? %1) :max-open? (:min-open? %2)) :as :first) (calculate [:A :B] #(interval/make-interval (:min %1) (:max %2) :min-open? (:min-open? %1) :max-open? (:max-open? %2)) :as :outer) (calculate [:A :B] #(interval/make-interval (:max %1) (:min %2) :min-open? (:max-open? %1) :max-open? (:min-open? %2)) :as :inner) (calculate [:A :B] #(interval/make-interval (:max %1) (:max %2) :min-open? (:max-open? %1) :max-open? (:max-open? %2)) :as :last) (calculate [:first :outer :inner :last] #(list %1 %2 %3 %4) :as :foil) (push-onto :exec :foil) ))

Yes, I could extract the four calculations to a Clojure function, but that seems as if it would mask the details. In this case, I am being carefully explicit about *which* `:min-open?`

and `:max-open?`

I’m working with in each case. It’s confusing, but I don’t think it would be any *less* confusing if it were all in some other function. Could be that someday it irritates me enough to change. We’ll see.

## Set theory stuff

I think that now `Interval`

really represents a formal set (as opposed to the weird “oriented set” that `Span`

captured), I’d like to have `:interval-union`

, `:interval-intersection`

and `:interval-subtract`

, which are just implementations of the set-theoretic operations.

The `:interval-intersection`

instruction feels easier, not least because the result will always be either *nothing* (if there is no overlap) or a set I can represent as a single `:interval`

. The result of `:interval-union`

is more than one `:interval`

, and I don’t have a clear sense at the moment what that should be: should it return a code block, or a `:set`

of `:interval`

items, or an `:intervals`

tuple? I don’t know.

Anyway, I’ll elide the inevitable edge-case chasing, though there was a bunch of it. Here’s the function I wrote in `push.type.definitions.interval`

(defn interval-intersection "Takes two Interval records, and returns a new one that contains their intersection, or nil if there is none." [i1 i2] (if (interval-overlap? i1 i2) (let [min1 (:min i1) min2 (:min i2) max1 (:max i1) max2 (:max i2) sorted (sort-by first [ [min1 (:min-open? i1)] [min2 (:min-open? i2)] [max1 (:max-open? i1)] [max2 (:max-open? i2)]]) new-min (nth sorted 1) new-max (nth sorted 2) ] (make-interval (first new-min) (first new-max) :min-open? (if (= min1 min2) (or (:min-open? i1) (:min-open? i2)) (second new-min)) :max-open? (if (= max1 max2) (or (:max-open? i1) (:max-open? i2)) (second new-max)) )) nil))

A lot of the work being done here arises because the `Interval`

record (intentionally?) dissociates the numerical value of `:min`

from whether it’s open or closed, so I build some tuples of `[number open?]`

pairs so that when I actually sort the numbers the openness of the “overlapping” ends can be managed. I won’t go into it in detail; it’s basically a somewhat more succinct way of handling the same edge cases as the `interval-overlap?`

function.

Indeed, I wonder if maybe there’s a simpler more Clojure-flavored way of doing this, just by returning the overlap *itself* instead of a strictly `true`

/`false`

result from `interval-overlap?`

. Maybe. Not today.

Now for `interval-union`

. I think that if the two `Interval`

items don’t overlap, then the result should be a code block containing them both. If they overlap at all (or have no intervening space, like \([2,3) \cup [3,4]\) which have no gaps or overlaps), then the result should be a single `Interval`

reaching from the smallest `:min`

to the larges `:max`

, and it should retain the openness of the constituent arguments.

Maybe I’ll return a list of results in any case.

Later…

It’s certainly quite a bit simpler than it was when these were `Span`

items, but it’s not… well, it’s still not *succinct*. The edge case for `interval-union`

is interesting. It’s the one I described above, like \([2,3) \cup [3,4]\). This isn’t detected by the predicate I already have, `interval-overlap?`

, so I needed a new predicate I called `interval-snug?`

. Using that, I could cover all the edge cases in `interval-union`

, like so:

(defn interval-snug? "Takes two Interval records, and returns `true` when they do not overlap, and the max of the first is the same as the :min of the second, and at least one of those ends is closed. `[2,3)` and `[3,4)` are snug. NOTE: this only checks whether i1 is snug to i2, not vice versa" [i1 i2] (and (not (interval-overlap? i1 i2)) (and (= (:max i1) (:min i2)) (or (max-closed? i1) (min-closed? i2))))) (defn interval-union "Takes two Interval records. If they are strictly discontinuous, they are returned in the order given in a list. If they have no gap between them, the list will contain one Interval that is their union." [i1 i2] (let [min1 (:min i1) min2 (:min i2) max1 (:max i1) max2 (:max i2) sorted (sort-by first [ [min1 (:min-open? i1)] [min2 (:min-open? i2)] [max1 (:max-open? i1)] [max2 (:max-open? i2)]]) new-min (first sorted) new-max (last sorted)] (cond (interval-overlap? i1 i2) (list (make-interval (first new-min) (first new-max) :min-open? (if (= min1 min2) (and (:min-open? i1) (:min-open? i2)) (second new-min)) :max-open? (if (= max1 max2) (and (:max-open? i1) (:max-open? i2)) (second new-max)))) (or (interval-snug? i1 i2) (interval-snug? i2 i1)) (list (make-interval (first new-min) (first new-max) :min-open? (second new-min) :max-open? (second new-max))) :else (list i1 i2))))

But boy, that second one is a rambler, isn’t it?

I should refactor it.

Later…

I can’t seem to get any foothold, to be honest. Maybe I’m too close to it, or have spent too much time invested in this particular (rambling) structure, but whenever I try to extract a function or reduce the number of clauses, I find something that’s too tightly coupled to the part I’m trying to reduce.

For instance. there are several occurrences of code that looks (generally) like this:

... :min-open? (if (= min1 min2) (and (:min-open? i1) (:min-open? i2)) (second new-min)) ...

That is, “if two particular numbers are the same, then the openness of this interval is such-and-such.” But both the arguments and outcomes would need to passed in as arguments if I did that, and… meh.

It’s going to want to be simplified another day, I think. I can’t see a place to set a tool yet.

Tomorrow—since today is long gone—I will add some simple arithmetic to the `Interval`

type, and be done I think.

Continued in “Finishing the Interval Push type in Klapaucius”