Date: Fri, 29 May 2020 18:26:25 -0700
From: Bret Victor
Subject: caring, convergence priorities, histories
I mentioned last week that the two tasks remaining for full ghost support were to-know-when and past tense.  Instead of reimplementing those directly, I ended up implementing more general mechanisms that we've talked about wanting.

To-know-when has been deprecated in favor of caring.

    When /someone/ cares when /p/ points /direction/ at /something/:
        Claim (p) points (direction) at (target).
    End

Unlike to-know-whens, which affected translation and triggered global recompilation when changed, cares are ordinary statements, noticed by ordinary whens.  They are non-disruptive, more flexible, and just as reactive as Realtalk should be.  Caring should make it much more inviting to generate statements on demand.

I wasn't eager to implement past tense directly because it's expensive to maintain an entire frame which is mostly not used. I surveyed every use of past tense in the ghost pages, and found three categories of use:

- wanting a safe time to perform side effects ("stable frame")
- comparing a value last tick to a value this tick ("last frame")
- actually unnecessary but used mistakenly or "just in case"

For the first use, I implemented convergence priorities, which allow control over the sequencing of evaluations:

    When a is /a/, b is /b/, c is /c/ [converging with priority (-100)]:
        perform_side_effect(a,b,c)
    End

For the second use, I implemented histories:

    When /dial/ is a "dial", /dial/ has value /new_v/, /dial/ has value /old_v/ [(1) tick ago]:
        Claim (dial) moved by (new_v - old_v).
    End

Details are below.  This is all implemented and working in simulation.  Next week, I'll try getting the ghost pages running.


Caring

When this when is evaluated:

    When /dog/ is a "dog":

The matcher makes the statement:

    (you) cares when (Unknown) is a "dog".

Unknown is a unique value that represents an unknown in a query.  For a multi-clause when:

    When /dog/ is a "dog", /dog/ is friends with /bud/:

the care from the first clause is the same as before, and when that first clause matches (say, "Sparky" is a "dog"), the second clause cares:

    (you) cares when "Sparky" is friends with (Unknown).

So, you might write:

    When /someone/ cares when /dog/ is friends with /someone/, /dog/ is in friend group /group/:
        for _, bud in ipairs(group) do
            if bud ~= dog then Claim (dog) is friends with (bud). end
        end
    End

The matcher only cares when looking for claims.  If you write

    When /someone/ wishes /dog/ comes here: 

no care statement is made. That is, only claims can be generated on demand, not wishes (or cares themselves).  This was mostly for syntactic reasons, and although it seems to make sense, it might be a mistake.

"Cares" is a new top-level statement verb, along with "claims" and "wishes".  You can care about things directly:

    Care about the plight of (the_people).

which I hope warms your heart as much as it does mine.  I think that many of the places we used "wish to know" can be rephrased as caring.

Optional footnote on "maybe-unknown"

To-know-when had a "unknown-or-known" parameter type that was subtle and confusing.  It's been replaced by something else that is also subtle and confusing.  Consider these two whens:

    1. When (you) points "up" at /target/:
    2. When /target/ is a "page", (you) points "up" at /target/:

In 1, /target/ is an unknown.  In 2, the first clause is offering the second clause a bunch of candidate targets, so the second clause considers /target/ to be known.  Here are a few ways of writing the generator:

    a. When /someone/ cares when /p/ points /direction/ at (Unknown):
    b. When /someone/ cares when /p/ points /direction/ at /something/:
    c. When /someone/ cares when /p/ points /direction/ at /target/:

a only works for 1.  b just generates statements for every possible target, which works, but might be wasteful for 2 when target is known.  In c, the variable /target/ is bound to either a target or Unknown, so that usually means handling the two cases as two separate blocks of code. The challenge is to write a single when that handles both cases:

    When /someone/ cares when /p/ points /direction/ at /maybe-unknown target/,
         /target/ has region /r/ on /s/:

What happens here is that if target == Unknown in the first clause, the second clause proceeds as if it's defining /target/ for the first time.  If target ~= Unknown in the first clause, then the /target/ in the second clause is bound to the one in the first clause, like normal.  It takes some tricky translation to get this effect, because the two cases compile to completely different code.  Unlike to-know-when, which rewrote the entire body (using gsub!) for each case, maybe-unknown only affects the query it's in, so the weirdness is more localized at least.

As I mentioned earlier, caring is an implementation of a scheme that Josh suggested a couple years ago.  It turns out that the matcher was already making statements to subscribe to updates from the reactor about queries, and that was exactly where these caring statements needed to go.  I think I added one line to the matcher.  (But a whole bunch to the translator.)

There's a backward-compatibility macro that translates "To know when" into the new thing, so old code should all still work, except "unknown-or-known" is no longer supported.  It was only used in a dozen places in the ghost pages, so I just fixed those all by hand.


Convergence priorities

As statements change, the reactor queues up whens that want to update in reaction to those statements.  Now, whens can have priorities, and whatever is highest priority in the queue gets run first.

In the absence of side effects and wall clocks, order doesn't matter, because things just get reevaluated until they converge.  But when you do have whens with side effects, and want to make sure they run only after all their inputs have settled down, you can just give them a low priority:

    When a is /a/, b is /b/, c is /c/ [converging with priority (-100)]:
        perform_side_effect(a,b,c)
    End

You can also use high priority to make a when more "eager", to avoid expensive recomputation downstream.  For example, by giving this a high priority:

    When my image is /image/ [converging with priority (100)]:
        Claim my average color is (average_color(image)).
    End

you ensure that whens like the following will always see a matched set, never a new image paired with an old color:

    When my image is /image/, my average color is /color/:
        do_some_expensive_processing(image, color)
    End

By being more precise with your priorities, I think you can sequence effects in the manner of the "purple boxes" we were discussing last year.  

    When a is /a/, b is /b/ [converging with priority (-10)]:
        Claim my buffer is (malloc(a*b)).
    End
    When a is /a/, b is /b/, my buffer is /buffer/ [converging with priority (-20)]:
        do_something(buffer,a,b)
    End
    When a is /a/, b is /b/, my buffer is /buffer/ [converging with priority (-30)]:
        free(buffer)
    End

(The purple box concept involved reconverging between every purple box.  That effectively happens automatically here -- it's all one big converge, but every time a low-priority when makes a statement, all the normal-priority whens get a chance to chew on it before the next low-priority when takes effect.)

It's really interesting to watch things like this in simulation, and see the re-evaluations as parameters change, and how things sort themselves out as you change the priorities.


Histories

For the first use of past tense (side effects), we really just want to run late in the tick.  For the second use (how much has this dial moved), we actually want to remember something from the previous tick.  I considered various ways of representing this state, and ended up thinking that Realtalk should provide two kinds of state:

- memories ("sticky statements" created with Remember and Forget)
- histories (statements from past ticks)

Instead of keeping track of entire past frames, histories of individual queries are recorded on demand, using the caring mechanism described above.

Here's a normal when, and what it cares about:

    When (dial) has value /v/:
    Care when (dial) has value (Unknown).

Here's what a historical when cares about:

    When (dial) has value /v/ [(2) ticks ago]:
    Care about the (2) tick history (history) of query (query).

The "Histories" page notices this care, and sets up its own when to monitor the query and store the results for later.

    When /someone/ cares about the /n/ tick history /history/ of query /query/:

There's probably a lot of other temporal queries that we'll want besides just matching a statement from (n) ticks ago.  Now that there's a mechanism for recording histories on demand, we can start thinking about that and adding them in as we need them.

I initially thought that updating state for histories and memories would have to be written into the top-level tick loop.  But now with convergence priorities, I could implement histories as a few ordinary whens on an ordinary page, using low priorities to updates the state at the end of the tick, and a high priority to make new statements at the beginning of the tick as soon as the time changes.  All that the tick loop has to do is advance the time.  The matcher and reactor don't know about histories either, it's all just on a page.  (And in the translator.)

So histories ended up relying on both priorities and caring, which both rely on the new reactor.  Histories also rely on the new matcher representing queries as values that can be passed around.