Finishing the Interval Push type in Klapaucius
Draft of 2016.07.09
May include: GP ↘ Push ↗ learning in public ↖ &c.
Continues “The Interval Push type in Klapaucius”
I’ll get straight to work this morning. I’m thinking of using this Wikipedia page on Interval Arithmetic as a simple guide, and creating pairs of instructions in which either two :interval items or an :interval and a :scalar are involved, like :interval-add and :interval-offset for addition, and so on. Although there really isn’t a good reason to have a separate function adding a :scalar to an :interval, and another subtracting a :scalar from an :interval….
I’ll get to that. I have a suspicion, going in, that division (as ever) will be tricky and not especially fun, what with its contingencies and the description on the Wikipedia page of how Infinity is used explicitly in the calculations of the most common algorithms. But I think I can manage.
Adding adding
Interval addition is relatively simple. The sum is a new :interval with :min equal to the sum of the :min of each argument, and the result’s :min-open? will be true if either argument’s was true. And, of course, the same for :max throughout.
As a side note, I realize this only works because I changed the unsorted :start and :end of Span to a sorted :min and :max in Interval. Otherwise I’d need to to all kinds of checks (as I will with :interval-multiply, shortly).
(def interval-add (build-instruction interval-add "`:interval-add` pops the top two `:interval` items and pushes a new `:interval` which is the sum of the two. If either `:min` (or `:max`) is open, the result `:min` (or `:max`) is also open." :tags #{:interval} (consume-top-of :interval :as :i2) (consume-top-of :interval :as :i1) (calculate [:i1 :i2] #(interval/make-interval (+' (:min %1) (:min %2)) (+' (:max %1) (:max %2)) :min-open? (or (:min-open? %1) (:min-open? %2)) :max-open? (or (:max-open? %1) (:max-open? %2))) :as :result) (push-onto :interval :result)))
I write some tests, and realize an interesting thing about interval arithmetic: it’s not immediately obvious or intuitive what Interval I should add to \([2,3]\) to “zero it out”. The “negative” interval, which I innocently wrote as \([-2,-3]\) in my test, is actually \([-3,-2]\) (because the constructor’s arguments are sorted in creating the interval proper). I don’t think there’s any single interval I can add to \([2,3]\) to “zero it out”. I can subtract an identical interval to get \([0,0]\), but apparently I can’t add one. Which strikes me as freaky somehow, and an interesting peek into some Group Theory stuff I didn’t know was lurking here.
Here are my tests for :interval-add
(tabular (fact ":interval-add returns the sum of two intervals" (register-type-and-check-instruction ?set-stack ?items interval-type ?instruction ?get-stack) => ?expected) ?set-stack ?items ?instruction ?get-stack ?expected :interval (list (s/make-interval 2 3) (s/make-interval 2 3)) :interval-add :interval (list (s/make-interval 4 6)) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; :interval (list (s/make-interval 2 3) (s/make-interval -3 -1)) :interval-add :interval (list (s/make-interval -1 2)) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; :interval (list (s/make-open-interval 2 3) (s/make-interval 2 3)) :interval-add :interval (list (s/make-open-interval 4 6)) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; :interval (list (s/make-open-interval 2 3) (s/make-interval -3 -2)) :interval-add :interval (list (s/make-open-interval -1 1)) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; :interval (list (s/make-interval 3 3 :min-open? true) (s/make-interval 2 2 :max-open? true)) :interval-add :interval (list (s/make-open-interval 5 5)) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; )
Subtraction
I decide to forge ahead and build subtraction, since (it seems at first glance that) it’s essentially identical to addition, only “backwards”. As soon as I start checking, it turns out that it isn’t though. Instead of addition, in which
\[[a,b]+[c,d]=[a+c,b+d]\]subtraction is
\[[a,b]-[c,d]=[a-d,b-c].\]Whaaaaaat?
OK, I can go with that. I’d feel a bit better if, for example, \(A-B=C\) implied that \(C+B=A\), but that is apparently not a thing I get to assume. So it’s not a group or a field or one of those math things I vaguely remember from our over-ambitious 11th-grade pre-calculus exposure to Group Theory at all in the sense I think of them. Ah well. I trust Wikipedia enough to copy from them. I suppose this has something to do with… well, something I can’t quite visualize.
Wish I had a picture.
Anyway, once I discover my confusion, I quickly work this out, which is quite similar to :interval-addition:
(def interval-subtract (build-instruction interval-subtract "`:interval-subtract` pops the top two `:interval` items and pushes a new `:interval` which is the difference of the two. If either `:min` (or `:max`) is open, the result `:min` (or `:max`) is also open." :tags #{:interval} (consume-top-of :interval :as :i2) (consume-top-of :interval :as :i1) (calculate [:i1 :i2] #(interval/make-interval (-' (:min %1) (:max %2)) (-' (:max %1) (:min %2)) :min-open? (or (:min-open? %1) (:max-open? %2)) :max-open? (or (:max-open? %1) (:min-open? %2))) :as :result) (push-onto :interval :result)))
As for the openness of bounds, I assume it works more or less like addition, and try to keep things together. I’ve found a few IEEE standards and academic papers on how bounds are handled (and division, which is starting to worry me to be frank), but I literally can’t read them when they use symbols like upside-down-triangle-surrounding-plus and so forth. So I’m punting here.
At least now I have glanced at multiplication enough to understand what to expect.
Multiplication
Multiplication is relatively simple, at least for determining the values of the bounds. The lower and upper bounds are the min and max, respectively, of {\(ac\), \(ad\), \(bc\), \(bd\)}, for two intervals \([a,b]\) and \([c,d]\).
The first part, the bounds calculation itself, is relatively straightforward:
(def interval-multiply (build-instruction interval-multiply "`:interval-multiply` pops the top two `:interval` items and pushes a new `:interval` which is the product of the two. If either `:min` (or `:max`) is open, the result `:min` (or `:max`) is also open." :tags #{:interval} (consume-top-of :interval :as :i2) (consume-top-of :interval :as :i1) (calculate [:i1 :i2] #(let [a (:min %1) b (:max %1) c (:min %2) d (:max %2)] interval/make-interval (min (*' a c) (*' a d) (*' b c) (*' b d)) (max (*' a c) (*' a d) (*' b c) (*' b d)) ;; :min-open? ??? ;; :max-open? ??? ) :as :result) (push-onto :interval :result)))
but as you can see, I really don’t know what to set as :min-open? and :max-open? in the result.
This starts to feel like yet another place where the association between a numerical bounds value and whether it’s open or not is important. Basically I’d like the result’s :min-open? to be true if either of the bounds used to calculate it were open. Which means I need to know which of the four options was chosen….
I decide to associate the value and its openness up front, and see how messy the calculations get. Clojure seems to like me to fiddle complex structures, so let’s see what Clojure offers me as a mechanism for this task.
Later…
All I can say at this point is that I seem to have it working, based on my tests. But sheesh.
(defn product-of-bounds-from-pair "helper function for interval-multiply, which takes two [number, open?] tuples and returns the product of the number values" [t1 t2] (*' (first t1) (first t2))) (defn disjunction-of-bounds-from-pair "helper function for interval-multiply, which takes two [number, open?] tuples and returns the OR of the openness values" [t1 t2] (or (second t1) (second t2))) (def interval-multiply (build-instruction interval-multiply "`:interval-multiply` pops the top two `:interval` items and pushes a new `:interval` which is the product of the two. If either `:min` (or `:max`) is open, the result `:min` (or `:max`) is also open." :tags #{:interval} (consume-top-of :interval :as :i2) (consume-top-of :interval :as :i1) (calculate [:i1 :i2] #(let [a [(:min %1) (:min-open? %1)] b [(:max %1) (:max-open? %1)] c [(:min %2) (:min-open? %2)] d [(:max %2) (:max-open? %2)] pairs [[a c] [a d] [b c] [b d]] min-choice (apply min-key (fn [x] (apply product-of-bounds-from-pair x)) pairs) max-choice (apply max-key (fn [x] (apply product-of-bounds-from-pair x)) pairs)] (interval/make-interval (apply product-of-bounds-from-pair min-choice) (apply product-of-bounds-from-pair max-choice) :min-open? (apply disjunction-of-bounds-from-pair min-choice) :max-open? (apply disjunction-of-bounds-from-pair max-choice)) ) :as :result) (push-onto :interval :result) ))
So what I’m doing here is once again building a temporary association tuple with the value of a bound (:min or :max) and its openness (:min-open? or :max-open?). Then I create an explicit collection holding the four pairs of comparisons between those tuples; I could have possibly used some combinatoric library stuff to get the powerset here, but I already know this will never be larger than four elements, so easier and tidier to make it explicit.
Then I invoke an extracted “helper function” I’ve called product-of-bounds-from-pair, which reaches back into those two tuples being compared and calculates the product of their numerical values. The new min-choice is thus the pair of tuples of the lowest-valued product, and the new max-choice is the pair of tuples with the highest-valued product.
Finally, in constructing the resulting Interval, I use that same product-of-bounds-from-pair function to set :min and :max, and then invoke another “helper” disjunction-of-bounds-from-pair to or the openness values.
I hates it. But it works.
I spend some time trying to refactor it. But as before, I can’t really see a place to put a tool (as it were): no clean seams along which I could break off and extract a function, nothing repeated very often. If nothing else, there may be a problem with the verbosity of the PushDSL I’m responding too. But the function itself is essentially a relatively long calculation of the base numbers, and a lot of that is creating and juggling those [number, open?] tuples.
I’d like to get done. Maybe division, with its particular oddities, will spark an insight that leads to a general simplification? We’ll see shortly.
Reciprocals and Interval Division
At least based on the Wikipedia entry, the mathematical definition is broken into two steps. For \([a,b]÷[c,d]\), when \(0 \notin [c,d]\) the result is \([a,b] \times [c,d]^{-1}\), and \([c,d]^{-1} = [d^{-1},c^{-1}]\). For \([a,b]÷[c,d]\) when \(0 \in [c,d]\), we have a problem of diviing by zero, so we make a couple of adjustments. We define division by 0 as resulting in positive or negative infinity (depending on the sign of the dividend), and we split the interval \([c,d]\) into two intervals, \([c,0)\) and \([0,d]\).
An example might be good around now.
\[[2,3] \div [-2,3] \\ [2,3] \div [-2,0) \cup [2,3] \div [0,3] \\ [2,3] \times [-2,0)^{-1} \cup [2,3] \times [0,3]^{-1} \\ [2,3] \times (-\infty, -1/2] \cup [2,3] \times [1/3,\infty] \\ \ldots\]And so on.
So I see a few ways to approach this.
First I realize it wouldn’t be a bad thing to have an :interval-reciprocal function on hand. Second—and more conveniently for me—I am reminded that in “idiomatic Push” it might be better to let the intermediate product of the dividend and the reciprocal be calculated by the actual application of :interval-multiply. In other words, I am thinking that :interval-divide will produce a continuation form that invokes :interval-multiply and :interval-reciprocal, and let those instructions do the subsequent work.
I won’t bore you with the wrestling and mistakes (and there were a few), but here’s the function I finally wrote for interval-reciprocal in push.type.definitions.interval:
(defn interval-reciprocal "Takes one Interval record, and returns its reciprocal. If the argument contains 0, then two intervals are returned in a list" [i] (let [s (:min i) e (:max i) so (:min-open? i) eo (:max-open? i) infty Double/POSITIVE_INFINITY ninfty Double/NEGATIVE_INFINITY] (cond (and (zero? s) (zero? e)) (make-interval ninfty infty) (zero? (:min i)) (make-interval (/ 1 (:max i)) infty :min-open? (:max-open? i)) (zero? (:max i)) (make-interval ninfty (/ 1 (:min i)) :max-open? (:min-open? i)) (interval-include? i 0) (list (interval-reciprocal (make-interval s 0 :min-open? so)) (interval-reciprocal (make-interval 0 e :max-open? eo))) :else (make-interval (/ 1 e) (/ 1 s) :min-open? eo :max-open? so) )))
I realized there is a “hidden” behavior tucked into my glib reading of the Wikipedia example, which is what happens when an interval ends in 0. Technically, “ending in zero” is “containing zero”, but really I am enforcing a more stringent criterion: that when the interval includes 0 but not as an end, then I should split it. Testing revealed another “edge case”, which is the interval \([0,0]\), and also made me wonder whether I should bother preserving the “openness” of an infinite bound. As a result, all bounds that are infinite are closed.
The nice thing, to me, was the realization that when splitting an interval I could re-process the components recursively. I always get a little thrill when I find a recursive solution like that. Your mileage may vary.
OK, so having some confidence (since I tested extensively in the process of writing it) of my interval-reciprocal function, I will now implement the Push instruction, and then I think I have all the pieces for the Push :interval-divide instruction as well.
Here’s the Push instruction I design:
(def interval-reciprocal (build-instruction interval-reciprocal "`:interval-reciprocal` pops the top `:scalar` item and pushes its reciprocal to `:exec`. If the span strictly covers zero, then a code block containing _two_ spans is pushed." :tags #{:interval} (consume-top-of :interval :as :i) (calculate [:i] #(interval/interval-reciprocal %1) :as :results) (push-onto :exec :results) ))
I’ve shunted most of the work to the definition of interval-reciprocal, and it’s tempting to do the same with the :interval-multiply instruction that bugged me earlier. I may still do that; don’t know.
One design decision I’ve made here is a common Push idiom that’s developed in the course of the project: When there’s any ambiguity in the return values of an instruction—for instance when the number of items or the type of the result might be contingent on the arguments—I prefer to return a code block containing all the arguments to the :exec stack and let the interpreter’s router push those results to their correct homes. I have a sense (because of another feature coming soon) that this may become more of a rule than an occasional quirk, but for now I’m happy enough to notice it.
I think I have everything in place now for a version of the :interval-divide instruction. Let’s see….
Here’s what the instruction definition ends up looking like:
(def interval-divide (build-instruction interval-divide "`:interval-divide` pops the top two `:interval` items (call them `B` and `A`, respectively) and pushes a continuation that will calculate their quotient(s) `A÷B` onto `:exec`. If `B` strictly covers zero, then two continuations are pushed: one for the positive and one for the negative regions." :tags #{:interval} (consume-top-of :interval :as :divisor) (consume-top-of :interval :as :dividend) (calculate [:divisor] #(interval/interval-reciprocal %1) :as :inverses) (calculate [:dividend :inverses] #(if (seq? %2) (list %1 (first %2) :interval-multiply %1 (second %2) :interval-multiply) (list %1 %2 :interval-multiply)) :as :results) (push-onto :exec :results) ))
That is, if the result of interval-reciprocal are a collection, produce a long continuation that includes both partial calculations in turn; otherwise just one.
There’s a bit of a mathematical glitch I sense here, which is that the reciprocal of a zero-spanning Interval will always produce two Interval items. But I don’t really want to go through the trouble for now of creating some kind of multi-interval arithmetic, which retains the result as the union of two continuous regions. Besides, we’re dividing by zero—I should be happy there is any result at all, and that it makes some sense.
That said, there’s another thing that catches my attention, and that may be more salient when I start stress-testing these new instructions: the appearance of \(\infty\) values in the numeric values of Push items. If \(\infty\) is to be a valid :scalar value, there will almost certainly be consequences somewhere down the line in genetic programming land….
But consequences are something evolutionary search is intended to work around. So let’s just remember this and move along.
Here’s the test that really exercises this “continuation form” approach:
(tabular (fact ":interval-divide works for zero-spanning intervals" (register-type-and-check-instruction ?set-stack ?items interval-type ?instruction ?get-stack) => ?expected) ?set-stack ?items ?instruction ?get-stack ?expected :interval (list (s/make-interval -2 3) (s/make-interval 2 3)) :interval-divide :exec (list (list (s/make-interval 2 3) (s/make-interval Double/NEGATIVE_INFINITY -1/2) :interval-multiply (s/make-interval 2 3) (s/make-interval 1/3 Double/POSITIVE_INFINITY) :interval-multiply)) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; )
And that passes. It manages to break the zero-spanning interval across the origin, and results in a sufficient continuation that after a few more steps will produce two Interval items that represent the two parts of the correct answer.
I think I’m done with arithmetic. I am still tempted to move some of the logic written explicitly into the :interval-multiply instruction up to an interval-multiply function in push.type.definitions.interval, but I think I can save that for another day.
Looking over my list from several days ago, the remaining work is making sure the Push :interval type is connected sufficiently, through conversion and manipulation instructions, to the basic types that comprise it. I can see a few of those already, and they should be (compared to the core arithmetic) relatively simple. Here’s what I think I can and should finish this morning:
:interval-recentermove the center of the interval to zero:interval-minpush the:minto:scalar:interval-maxpush the:maxto:scalar:interval-scalemultiply:minand:maxby a:scalar:interval-shiftadd a:scalarto:minand:max:interval-negatemultiply:minand:maxby -1
There are a few other pieces of functionality that I think should wait a few days. For instance, one of the reasons for having these numerical interval objects at all is to emulate Clojure’s sensible idiom of using a set as a filter for a collection. Eventually I can see using something like \([2,3]\) as an argument in a suite of functional collection-munging instructions, something like :scalars-retain, which would keep only the items in a :scalars item that fall within a given :interval; or :tagspace-remove, which removes all entries from a given :tagspace with keys falling within a given :interval, and so forth.
But those are not for today.
Wiring it up
Before I write those “simple” instructions I’ve just listed, I realize I should register the :interval type I’ve been working on, and check that a Push interpreter can integrate these new instructions into the ecosystem of existing types and instructions.
That process is not yet very polished, and as I move towards a first “finished” release of the Klapaucius interpreter as semantic version 1.0.0 I will want to improve that functionality. At the moment it boils down to three steps:
- add the new type to
push.interpreter.templates.one-with-everything - fix a few badly-written tests that will fail because they check (explicitly) for the list of registered types, which I know is a bad thing but which didn’t I just say I was hoping to improve? Like literally in the preceding paragraph?
- run a few thousand stress tests
As with the embarrassing tests I still need to clean up (which explicitly ask what the known types for a new Interpreter instance are, and which of course fail as soon as you add a new type), the stress test I’ve built is rather primitive as of this writing. Think of it as an acceptance test that basically reads something like “There should be no exceptions at all when I construct 10000 random Push programs, with 20 random inputs each, and run them all 3000 steps each.”
The business of concocting “random programs” is necessarily slapdash in this library, since that responsibility really should reside in the search system one develops: there’s no reason for an interpreter made to run programs to know anything about writing programs. So in this case what I’ve done is simply bashed together the simplest possible “random program” maker. For most (maybe all?) of the defined types, it has a little function that can make a “random one”. A “random :scalar” is some number in a given range, a “random :boolean” is true or false with equal chance, a “random :instruction” is any of the registered instruction names for a new Interpreter, chosen uniformly, and so on.
Because I want to make relatively sure there are Interval items being made and exercised, and especially because those Infinity values floating around are starting to worry me, I add a little “random :interval” function to my stress-testing harness before I trust the results:
(defn random-interval [] (interval/make-interval (random-float) (random-rational) :min-open? (random-boolean) :max-open? (random-boolean)))
I’m not showing the context because I hate it and I want to clean it all up before sharing more of it, but I think you can infer what’s happening here. I’m just slapping together some numbers—random-float returns a float from 0 to 100000, and random-rational is the ratio of two integers somewhere in [1,200], and setting the bounds open with uniform coin flips of random-boolean. Literally no idea what the results will be, except they will be valid Interval items because that’s how I defined them!
When I run this, my computer gets Very Hot (I am partly embarrassed by the code because I never even bothered to make this a parallel algorithm), but all of the 10000 random programs—which include both Interval literals and all my new :interval instructions—run to completion. Which is almost disturbing, so I do some poking around to check, but yes it seems things are working well. I think the recent change in the way numbers are handled (leading to the :scalar unified type in Push, which contains all of Clojure’s integer, double, float, long, rational, biginteger and bigdecimal in one huge pile) shook out a lot of the arithmetic errors I was expecting. I hope so fervently, at least.
So that actually makes :interval an official Push type. Before I merge this branch with master I’d like to add those “few extra” instructions. Then I believe we’re good!
Leftovers and connections
I feel I’m on a roll, so I’ll just report what happens for each instruction on my list in turn
:interval-recenter
The tricky thing here is the possibility that an Interval has one or both bounds infinite. I decide that if either bound is infinite, “centering” an infinite span should result in the span \([-\infty, \infty]\). Makes sense to me, at least.
In working through this, I realize I want a new predicate function, and it seems useful and general enough to be placed in push.util.numerics for use elsewhere:
(defn infinite? [number] (or (= number Double/NEGATIVE_INFINITY) (= number Double/POSITIVE_INFINITY)))
Then the instruction itself (after this utility file has been added to the namespace) becomes
(def interval-recenter (build-instruction interval-recenter "`:interval-recenter` pops the top `:interval` item and pushes a new `:interval` with center at 0. If either bound of the argument is infinite, the result will be infinite in both directions." :tags #{:interval} (consume-top-of :interval :as :i) (calculate [:i] #(if (or (infinite? (:min %1)) (infinite? (:max %1))) (interval/make-interval Double/NEGATIVE_INFINITY Double/POSITIVE_INFINITY) (let [c (/ (-' (:max %1) (:min %1)) 2)] (interval/make-interval (- c) c :min-open? (:min-open? %1) :max-open? (:max-open? %1)))) :as :result) (push-onto :interval :result)))
:interval-min
These two are simple enough getters (if we were in Object Oriented territory). Here they are, with no fuss:
(def interval-min (build-instruction interval-min "`:interval-min` pops the top `:interval` item and pushes its `:min` value to `:scalar`." :tags #{:interval} (consume-top-of :interval :as :i) (calculate [:i] #(:min %1) :as :result) (push-onto :scalar :result))) (def interval-max (build-instruction interval-max "`:interval-max` pops the top `:interval` item and pushes its `:max` value to `:scalar`." :tags #{:interval} (consume-top-of :interval :as :i) (calculate [:i] #(:max %1) :as :result) (push-onto :scalar :result)))
:interval-scale
Without further ado:
(def interval-scale (build-instruction interval-scale "`:interval-scale` pops the top `:interval` item and top `:scalar` item, and pushes a new `:interval` with the original `:max` and `:min` multiplied by the `:scalar`." :tags #{:interval} (consume-top-of :interval :as :i) (consume-top-of :scalar :as :factor) (calculate [:i :factor] #( interval/make-interval (*' %2 (:min %1)) (*' %2 (:max %1)) :min-open? (:min-open? %1) :max-open? (:max-open? %1)) :as :result) (push-onto :interval :result) ))
:interval-shift
And:
(def interval-shift (build-instruction interval-shift "`:interval-shift` pops the top `:interval` item and top `:scalar` item, and pushes a new `:interval` with the original `:max` and `:min` added to the `:scalar`." :tags #{:interval} (consume-top-of :interval :as :i) (consume-top-of :scalar :as :factor) (calculate [:i :factor] #( interval/make-interval (+' %2 (:min %1)) (+' %2 (:max %1)) :min-open? (:min-open? %1) :max-open? (:max-open? %1)) :as :result) (push-onto :interval :result) ))
:interval-negate
I decide to call this one :interval-reflect, since what I’d like it to do is literally flip the :interval across zero. Thus, if the :min of the argument is open, the :max of the result will be, and so forth.
(def interval-reflect (build-instruction interval-reflect "`:interval-reflect` pops the top `:interval` item and pushes a new one with the signs of the `:min` and `:max` reversed, and also the boundedness of the ends." :tags #{:interval} (consume-top-of :interval :as :i) (calculate [:i] #( interval/make-interval (- (:max %1)) (- (:min %1)) :min-open? (:max-open? %1) :max-open? (:min-open? %1)) :as :result) (push-onto :interval :result) ))
Cleanup
That seems to be it. I’ve constructed (finally) an Interval record, added a bunch of functions to that, implemented it as a Push type, and added the requisite instructions to the Push interpreter definition. That’s registered (in the branch I am working in) with the “one-with-everything” interpreter template, and it seems to be passing the “stress” acceptance test.
I go over it all one last time, and notice some things to clean up. The fact that I dropped interval-reciprocal into the “helper” functions, but not interval-multiply bothers me, so I want to shift things over and make the Push instructions simply call the library that handles the type. That seems safer and more elegant, to be honest. Something about separation of responsibility and all, too.
That works simply, and I don’t even bother adding additional tests for the “new” integer-multiply and its helpers. I’m comfortable enough seeing that the instruction, which is the only thing exercising interval-multiply, produces correct results.
I say we ship it. Push now has an :interval type.
Reflections
I realize I should clean up and formalize the process at “both ends”. It should be easier to construct a new “empty” Push type (possibly with a generator function of some kind?), and it should definitely be simpler and easier to add all the types (and modules) to the universal one-with-everything interpreter when I’m done.
When I (the best proxy so far for the proverbial “end user”) want to add a new type to the already-crowded Push ecosystem embodied in the Klapaucius interpreter, there’s a necessary but difficult bit of research that needs to be done. That is, one needs to be able to “look” in some sense at the interconnectedness of the old types and the new ones, as the instruction set transforms them into one another. A good deal of this might be solved with a dynamic visualization of the graph of transformations of arguments to results by all the instructions acting on all the types. But at least a little bit is a reminder that getters, setters, and the things that take structured types apart are important.
For some time I’ve felt that the types in Push should be defined structurally rather than in this sort of ad hoc way. For example, I think :interval should be automatically recognized and detected—in some way I can’t quite put together yet—as a record containing two :scalar and two :boolean values, with appropriate labels. The labels are right there inside the Clojure record, and it seems reasonable and appropriate to let Push also see the keys and do some introspection. But the next step, it seems to me, is to define something like an Interval with this (pseudocode macro warning)
(defpushstructure :interval :min :scalar :max :scalar :min-open? :boolean :max-open? :boolean)
and automatically get instructions like
:interval-min:interval-max:interval-min-open?:interval-max-open?:interval-setmin:interval-setmax:interval-setmin-open?:interval-setmax-open?:interval-new:interval-parts- … and so on
I don’t think I should expect everybody two write those on their own, especially for more complex Clojure record items I have planned, like :graph or :time-series.
But that is definitely for another day.
Finally, there are a few philosophical concerns I should check, involving the notion of Infinity and numbers and how this plays out consistently in the Push language. At the moment, division by zero produces an :error result for a :scalar but a complex assortment of non-:error results for an :interval. But the results from dividing by an :interval that spans zero will include bounds at Infinity.
Specifically I’ve been relying on Clojure’s (and in turn, Java’s) Double/POSITIVE_INFINITY and Double/NEGATIVE_INFINITY constants. These are consistently handled by most of the Clojure functions mathematical functions I’ve checked so far; (Math/sin ∞) is NaN (reasonably, because what’s the phase at ∞?), (/ 1 ∞) produces the java.lang/Double value 0.0, and (-' 7812318273M -∞) produces ∞… also reasonable.
What isn’t so clear is whether this will hold up over time. There will shortly be higher-order functions floating around, and instead of simply worrying about :scalar and :scalars, :complex and :complexes, :interval and :intervals, there will be a sort of combinatorial… well, not “explosion”, but “rapid low-temperature expansion” when those arise. Lots of stuff will be able to interact with lots of other stuff.
This makes me wonder whether I should make my own Infinity, and what that might be, and how it would propagate. I think at the very least I should let Push pay attention to the Java/Clojure infinities when they crop up. The deeper question, though, is whether the behavior of :scalar-divide and :integer-divide are mathematically consistent now. I don’t know.
I commit and merge the changes, and I open some issues in the project repository on GitHub. I think we’re good to go.