Bulk Moving
As Vera was iterated on and refined, moving large sums between facts was becoming a growing problem. For example, take the following multiplicities:
pen x:700 pen y:300
Early designs of Vera obeyed the following rule: rules can only move a single pebble between bins. If we wanted to move pen x into @pixel x and pen y into @pixel y using the following rules:
|pen x| @pixel x |pen y| @pixel y
It would need 1,000 steps. In other words, our runtime depended on counter sizes. This was an unacceptable cost for anything moving medium sized quantities frequently. Additionally, it made it functionally impossible to move 32-bit and 64-bit values. But, eventually a solution was found: min semantics.
Min Semantics
Lets start with a Vera program to examine:
|red paint, blue paint, mix paint|
, purple paint
, mix paint
|| red paint:100
, blue paint:32
, mix paint:10
The goal of min semantics is to find the largest possible move we can make with the counters on hand. We achieve this in the following steps:
- Find the smallest counter in the condition.
- Subtract that quantity from ever fact in the condition.
- Add that quantity to every fact in the results for each time it appears.
In our current state, the largest unit of work we can do is 10. So we apply that to our quantities to get the following state:
|| red paint:90 , blue paint:22 , mix paint:10 , purple paint:10
Since our rules run in a loop, we continue this process until we can't evaluate anything. So, applying min semantics again, the largest unit of work we can do is 10:
|| red paint:80 , blue paint:12 , mix paint:10 , purple paint:20
Repeating the process again, the largest unit of work we can preform is 10. This gives us the following state:
|| red paint:70 , blue paint:2 , mix paint:10 , purple paint:30
On this iteration, we are starting to run low on blue paint. Now, we can only do 2 units of work. This gives us our final state:
|| red paint:68 , mix paint:10 , purple paint:32
Without min semantics, this would have taken 32 steps. But, with min semantics, it only needed 5 steps.
Quirks of min semantics
Min semantics can be thought of as providing fuel for your operations. We could have made this take one step by providing mix paint:100 rather than mix paint:10.
Additionally, you can make accelerating operations. The follow Vera program demonstrates this ability:
|move x -> y, x| move x -> y, move x -> y, y || move x -> y, y:1000000
Every time it executes it doubles that amount of move x -> y available in the system. This lets you process |move x -> y, x| in logarithmic time.
Why These Semantics
There are many possibly ways to provide this kind of rapid bulk move. However, our design goals for Nova require both syntactic simplicity and implementation simplicity. Min semantics requires no syntactic changes to Nova. Furthermore, these semantics can be implemented trivially using either a built-in min function or if (acc > count) { acc = count; } statement. This makes it very friendly to low-level languages.
Other ideas required adding variables that could hold the multiplicity of a fact. Many of these proved to be inelegant and clumsy. Further more, you'd still need some way to take the difference of two counts. Thus, this route was abandoned for Nova. It required too many additional layers of abstraction and implementation detail.
In the end, it was decided that this min operation was an acceptable addition to the implementation that preserved the simplicity of Nova. However, other rewriting systems may find value in exploring alternative routes.