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”