# Adding a Span type to Push; part 2

Draft of 2016.07.04

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

*continues “Adding a Span type to Push”*

## Actually fixing that bug

Well, I had a nap and some idea of how to fix the problem I encountered with an edge case in `:span-surrounds?`

, which cropped up when the enclosing `Span`

had open ends and the enclosed one also does. That is, \((2,3]\) should surround \((2,3)\).

The current implementation doesn’t catch this case correctly, because it checks to see if the *endpoints* of the interior `Span`

fall strictly within the prospective enclosing one. In this case, the endpoints *don’t* fall within the enclosing one, but that should be OK because the endpoints are *open*, and thus are not part of the set they define.

Here’s where I am right now:

(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) )))

All this is doing is checking whether the endpoints of the “enclosed” `Span`

are strictly within the “encloser”. I want to modify it to handle the case (which `span-include?`

doesn’t actually check, because that makes no sense) that the “point” is actually an open endpoint.

The subjective experience of thinking about this has been fascinating and more than a little strenuous. Because I *know* that `span-include?`

works for checking whether a point is inside an open-ended or closed-ended `Span`

, I kept focusing on how to circumvent that logic. That is, I’ve been trying in my head—and in conditional logic (not shown)—to “work around” this by checking whether the point is “open” in some way. But that would mean I’d be changing the logic of a well-defined function to handle a case caused by something *defined on a higher level*, and that makes me back away every time.

See, it’s like this: A *point* (or a *number*) can’t be “open” or not. It is what it is. The number that represents the end of a `Span`

, similarly, cannot be “open” or “closed” in itself. The `Span`

*as a whole*, as a higher-order object, has the characteristic of being “open”. It’s a definition in terms of the set of values the entirety describes, not the end point itself.

That’s why the `Span`

\((2,2)\) is so problematic, when you see it. It’s an empty set “located” somewhere between… 2… and 2? No, no, no.

Anyway, what taking a nap had the same effect taking a walk sometimes does: I let my mind wander a little bit, and fell asleep for a few minutes, and when I woke up I realized I was thinking to myself, “A *closed* `Span`

would always enclose any partially-open one.” Aha.

So here’s what I just typed, more or less cold and with very little backtracking:

(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 [span1closed (make-span (:start span1) (:end span1)) s2 (:start span2) e2 (:end span2) s2o? (:start-open? span2) e2o? (:end-open? span2)] (and (if s2o? (span-include? span1closed s2) (span-include? span1 s2)) (if e2o? (span-include? span1closed e2) (span-include? span1 e2)) )))

That is: If the `:start`

of the “enclosed” `Span`

is open, then it will *definitely* be contained inside a *closed version* of the “enclosing” `Span`

. Same with the other end. I thought for a moment that I could just get away with creating a new `span1closed`

and checking all cases against that, but it was not to be. What fails if I do that is the case where the ends of the “enclosed” `Span`

are closed, and should fall outside the “enclosing” one.

But I did it. I still frown at all the conditionals in these. I like to see my Clojure functions at about 6 lines each, and these are getting long and heavily indented. And I don’t know what to do about it. In a once-bitten-twice-shy sort of way, I’m a bit worried that `:span-overlaps?`

will pose the same sort of problem. We’ll see.

Later…

Yup. Same problem. This test fails now:

(tabular (fact ":span-overlap? returns the true if the top Span shares even one point with 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-open-span 3 4)) :span-overlap? :boolean '(false) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; )

It wants to think the open end of the second `Span`

is inside the first `Span`

… I think? When I glance at `push.types.definitions.span/span-overlap?`

it’s *totally* different from the `span-surrounds?`

function I just fixed. This is troubling.

(defn span-overlap? "Takes two spans, and returns `true` if they strictly overlap (taking into account openness of ends)." [span1 span2] (let [s1 (:start span1) e1 (:end span1) s2 (:start span2) e2 (:end span2)] (cond (contains-closed-end? span1 span2) true (contains-closed-end? span2 span1) true (fully-contains-end? span1 span2) true (fully-contains-end? span2 span1) true (span-surrounds? span1 span2) true (span-surrounds? span2 span1) true (span-coincide? span1 span2) true :else false )))

I don’t like the looks of `fully-contains-end?`

, which was a helper predicate I wrote to make the definitions tests pass. Obviously I missed this edge case there as well.

I wonder if I can massage that into being more like what I’ve already done. That is, make it something like `contains-open-end?`

, which is really the intention of `full-contains-end?`

anyway. It communicates the idea better, too.

At this point I take to drawing little ASCII diagrams, like this:

•---• o---• => false •---o o---• => false •---• •---• => true •---o •---• => false

Doing so, I realize that this really depends on the ends of both `Span`

items. Dang. So there’s more rewriting in order. *At least all the tests I have so fr should help me rewrite these checkers more correctly.*

Also, looking at the ASCII diagram, I see that the only case where the ends overlap and there *really* is an overlap is when both are closed. If either is open, we have no intersection. It’s definitely more complicated than “does the point fall in the `Span`

?”

If the `:start`

of the second `Span`

is open, then (I feel) it *really* has to fall inside a “fully open” version of the first `Span`

. That is, if I make the first open at both ends, then an open end in the second one triggering `:span-include?`

will mean that the endpoint doesn’t overlap either end of the first *at all*.

Like I did yesterday, I encounter a “mysterious bug” here too. And like yesterday, it’s because of a typo in some Clojure code. Good old Clojure: always willing to execute code like `(if test-function (test-arg true-clause) false-clause)`

even though what you *mean* was `(if (test-function test-arg) true-clause false-clause)`

.

*Le sigh….*

OK, so once I got through that rigamarole, I refactored the `:contains-span-end?`

predicate quite a bit, and as a result simplified and rejiggered a few other things in `push.type.definitions.span`

as well. Here are the three salient functions, as of this writing:

(defn contains-span-end? "Takes two spans. Returns `true` if either end of the second one falls strictly within the first, whether or not it is open." [span1 span2] (let [s1 (:start span1) e1 (:end span1) s1open (make-open-span s1 e1) s2 (:start span2) e2 (:end span2)] (or (if (:start-open? span2) (span-include? s1open s2) (span-include? span1 s2)) (if (:end-open? span2) (span-include? s1open e2) (span-include? span1 e2))))) (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 [span1closed (make-span (:start span1) (:end span1)) s2 (:start span2) e2 (:end span2) s2o? (:start-open? span2) e2o? (:end-open? span2)] (and (if s2o? (span-include? span1closed s2) (span-include? span1 s2)) (if e2o? (span-include? span1closed s2) (span-include? span1 e2))))) (defn span-overlap? "Takes two spans, and returns `true` if they strictly overlap (taking into account openness of ends)." [span1 span2] (let [s1 (:start span1) e1 (:end span1) s2 (:start span2) e2 (:end span2)] (cond (contains-span-end? span1 span2) true (contains-span-end? span2 span1) true (span-coincide? span1 span2) true :else false)))

But I’m still not out of the woods. This test fails, now:

(tabular (fact ":span-overlap? returns the true if the top Span shares even one point with 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)) :span-overlap? :boolean '(true) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; )

Again, I’m somehow failing because the `Span`

\((2,3)\) isn’t being detected as overlapping \([2,3]\).

More diagrams? Here are the cases I can see:

•---• o---o => true •---o o---• => true o---o o---o => true etc...

Interestingly, it’s only the top case in my diagram that’s failing. Of these three tests, only the first fails, and the second and third pass:

(tabular (fact ":span-overlap? returns the true if the top Span shares even one point with 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)) :span-overlap? :boolean '(true) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; :span (list (s/make-span 2 3 :start-open? true) (s/make-span 2 3)) :span-overlap? :boolean '(true) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; :span (list (s/make-open-span 2 3) (s/make-open-span 2 3)) :span-overlap? :boolean '(true) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; )

Right! I… guess? Remember, these are tests of the Push language, where the second argument appears first. The failing test is stating the expectation that “`Span`

\((2,3)\) should be detected as overlapping `Span`

\([2,3]\)”. Looking at the function called:

(defn span-overlap? "Takes two spans, and returns `true` if they strictly overlap (taking into account openness of ends)." [span1 span2] (let [s1 (:start span1) e1 (:end span1) s2 (:start span2) e2 (:end span2)] (cond (contains-span-end? span1 span2) true (contains-span-end? span2 span1) true (span-coincide? span1 span2) true :else false )))

Here, \([2,3]\) does *not* contain either (open) end of \((2,3)\), and so neither of the top two conditions ever trigger. But `span-coincide?`

only checks to see the spans are identical or exact reversals of one another, and that doesn’t apply in this test either. Instead, I guess I’ll have to do some more fiddling.

I add a bunch more tests, just out of pure paranoia, until it looks like this:

(tabular (fact ":span-overlap? returns the true if the top Span shares even one point with 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)) :span-overlap? :boolean '(true) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; :span (list (s/make-span 2 3) (s/make-span 3 2)) :span-overlap? :boolean '(true) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; :span (list (s/make-span 2 3) (s/make-span 3 4)) :span-overlap? :boolean '(true) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; :span (list (s/make-span 2 3) (s/make-open-span 3 4)) :span-overlap? :boolean '(false) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; :span (list (s/make-open-span 2 3) (s/make-span 2 3)) :span-overlap? :boolean '(true) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; :span (list (s/make-span 2 3 :start-open? true) (s/make-span 2 3)) :span-overlap? :boolean '(true) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; :span (list (s/make-open-span 2 3) (s/make-open-span 2 3)) :span-overlap? :boolean '(true) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; :span (list (s/make-span 3 3) (s/make-span 2 3)) :span-overlap? :boolean '(true) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; :span (list (s/make-open-span 3 3) (s/make-span 2 3)) :span-overlap? :boolean '(false) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; :span (list (s/make-span 3 3 :start-open? true) (s/make-span 2 3)) :span-overlap? :boolean '(true) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; :span (list (s/make-open-span 2 5) (s/make-span 3 4)) :span-overlap? :boolean '(true) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; )

And with much frowning and beard-scratching, here’s where my function ends up:

(defn span-overlap? "Takes two spans, and returns `true` if they strictly overlap (taking into account openness of ends)." [span1 span2] (let [s1 (:start span1) e1 (:end span1) s1open (make-open-span s1 e1) s2 (:start span2) e2 (:end span2) s2open (make-open-span s2 e2)] (cond (span-empty? span1) false (span-empty? span2) false (and (span-coincide? s1open s2open)) true (contains-span-end? span1 span2) true (contains-span-end? span2 span1) true (span-coincide? span1 span2) true :else false )))

My thinking works like this: If the two `Span`

items coincide, they overlap. But `span-coincide?`

only returns `true`

if the ends match exactly. Rather than write a new function, I just made an “opened up” version of both `Span`

items.

I worry, a bit, that the case of an empty `Span`

might fail. That’s why these three particularly weird tests are included:

(tabular (fact ":span-overlap? returns the true if the top Span shares even one point with 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 3 3) (s/make-span 2 3)) :span-overlap? :boolean '(true) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; :span (list (s/make-open-span 3 3) (s/make-span 2 3)) :span-overlap? :boolean '(false) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; :span (list (s/make-span 3 3 :start-open? true) (s/make-span 2 3)) :span-overlap? :boolean '(false) )

The weirdest one is the last. What *is* \((3,3]\), anyway? Is it even a thing? It should be *empty*, and therefore it shouldn’t actually overlap anything at all, no matter what. That should apply to both spans: an empty one can’t be overlapped, nor overlap another.

The function `span-empty?`

has actually been lurking in the library for a while now. I wrote it early on—basically while I was warming up and getting a sense of how these things work with one another—but really didn’t have any use for it once I wrote it. That’s why I haven’t mentioned it before.

Here it is:

(defn span-empty? "Takes a Span and returns `true` if it has identical `:start` and `:end`, and either is open" [span] (and (= (:start span) (:end span)) (or (:start-open? span) (:end-open? span))))

An empty `Span`

is one where both ends are the same, and at least one is open. Make sense?

I hope so. Seriously… I hope so. It *feels* consistent, but… this has been a long two-day ordeal, to be frank. Maybe I made a misstep early on? Maybe it’s just hubris? Maybe I’ve discovered a fun training case for people to undertake when they want to experience annoying edge case overflows?

## A record, for the ages

I think I’d better quit today, while I’m ahead and all the tests pass. But I liked those little diagrams I drew before, when I was confused, and I want to try to draw all the combinatorial possibilities.

These overlap: •---• •---• •---• •---• •---• •---• •---o •---o •---o •---o •---o •---o o---• o---• o---• o---• o---• o---• o---• o---• o---• •---o •---o •---o o---o o---o o---o o---o •---• •---• •---• • • • •---o •---o • • o---• o---• • • o---o • •-----• •-----• •-----• •-----• •-----• •-----• •-----• •---• •---• •---• •---• •---• •---• •---• o-----• o-----• o-----• o-----• o-----• o-----• •---• •---• •---• •---• •---• •---• •-----o •-----o •-----o •-----o •-----o •-----o •---• •---• •---• •---• •---• •---• o-----o o-----o o-----o o-----o o-----o •---• •---• •---• •---• •---• •-----• •-----• •-----• •-----• •-----• •-----• o---• o---• o---• o---• o---• o---• ... etc! These do not overlap: •---o •---o o---• o---o •---o o---• o---• o---o •---o o---• o---o o---o • • • • *---* *---* *---* o o o o-----• o-----o ... •---• •---• ...

Well, I *wanted* a complete catalog, but I got tired. Sheesh. I think maybe now I have a practical sense of why I’ve found this challenging.

Tomorrow I will finish the Push `:span`

type definitions, and if all goes well I can release it into the world as part of the `master`

branch of the Klapaucius interpreter.

Continued in “Rethinking the Push span as an undirected interval”