Date: Thu, 31 Mar 2022 16:12:20 -0700
From: Bret Victor
Subject: Re: Depth-first when unmatched
Okay, I just implemented a more refined version of the idea from yesterday.  It's mostly self-contained on its own page, and didn't require touching the reactor or matcher or anything.  (I did have to add a couple hooks around the evaluator in order to get the syntax to work.)  I went ahead and added it to your system.  (Which will very soon be replaced by a whole new system.)

The name isn't great, and might change.

Here's my test program:

    -- Consequences test

    

    When (you) is present [converging with consequences]:
        local d = create_unique_id(); print("creating display " .. d)
        When unmatched: print("destroying display " .. d) End
        Claim (d) is a fake display.
    End

    

    When /d/ is a fake display, the fake parameter is /x or 0/ [converging with consequences]:
        local f = create_unique_id(); print("creating framebuffer " .. f)
        When unmatched: print("destroying framebuffer " .. f) End
        Claim (d) has fake framebuffer (f).
    End

    

    When /d/ has fake framebuffer /f/ [converging with consequences]:
        local i = create_unique_id(); print("creating image " .. i)
        When unmatched: print("destroying image " .. i) End
        Claim (f) has fake image (i).
    End

and I see the correct things when I edit it or claim about the parameter:

    creating display *Object 5f588b83ac311433*
    creating framebuffer *Object 9a367b78e2786c33*
    creating image *Object 3cdf233b8b17726f*
    destroying image *Object 3cdf233b8b17726f*
    destroying framebuffer *Object 9a367b78e2786c33*
    destroying display *Object 5f588b83ac311433*


Here's the implementation.  Basically, when we match a rule that's marked [converging with consequences], we first do a Notice which will block until the cares-when responds back to it, and the cares-when converges with priority -100.  That's how we "postpone 5".

We also swap out when_unmatched with our own special when_unmatched, which instead of running the finalizer, adds a statement with the finalizer and a timestamp.  At priority -99, we match all such statements, and run the finalizers from latest to earliest timestamp.  And then we remove the statements that we matched, which is a wild trick that I'd never thought of before, but I think it's legit.  So that's "postponing 4".

So this is a little sneaky, but doesn't intrude on the existing machinery, and doesn't require maintaining any state outside of the frame.

-- Converging with consequences
-- In the example below, ensures that thing is destroyed *after* derived thing (which is destroyed after
-- derived derived things, etc.), and ensures that a new thing is not created until everything derived
-- from the old thing is destroyed.

-- When /p/ wants something [converging with consequences]:
--     local t = create_thing()
--     When unmatched: destroy_thing(t) End
--     Claim (p) has thing (t).
-- End
-- When /p/ has thing /t/ [converging with consequences]:
--     local t2 = create_derived_thing(t)
--     When unmatched: destroy_derived_thing(t2) End
--     Claim (p) has derived thing (t2).
-- End

local when_unmatched_with_consequences  -- forward reference

-- Block matching until priority -100.
function converging_with_consequences ()               -- this is called at the beginning of the body
    Notice consequences for (get_evaluation_id()) are ready.             -- block until priority -100
    _rt.evaluation.special_unmatched = when_unmatched_with_consequences  -- use our own when_unmatched
end

When /someone/ cares when consequences for /id/ are ready [converging with priority (-100)]:
    Claim consequences for (id) are ready.
End

-- Postpone unmatching until priority -99, and call finalizers from latest to earliest.
when_unmatched_with_consequences = function (body)
    local t = next_timestamp()
    _rt.evaluation.special_unmatched = nil                               -- use real when_unmatched
    When unmatched: emit_event("+", Statement (you) wishes (body) at (t) is unmatched after consequences.) End
    _rt.evaluation.special_unmatched = when_unmatched_with_consequences  -- back to our own when_unmatched
end

With all /matches/ for /someone/ wishes /body/ at /descending t/ is unmatched after consequences
     [according to statement /s/] [converging with priority (-99)]:
    for _,m in ipairs(matches) do m.body(); emit_event("-", m.s) end  -- call finalizer, remove trigger statement
End




On Mar 31, 2022, at 10:54 AM, Luke Iannini wrote:

Yeah that makes perfect sense! The resource registration idea was the direction I was heading in but it seemed fundamental enough to be worth thinking through more generally, and the asymmetric unmatching and matching is probably the missing piece I was needing!

(I was thinking of something like, during construction, register the resource either as a “root” resource (e.g. the display) or a resource that’s a child of another (e.g. the display's framebuffer and the framebuffer’s color-image)

register_root_resource(display)
register_child_resource(display, framebuffer) -- adds framebuffer to a free-list keyed by the display
register_child_resource(framebuffer, image) -- adds image to a free-list keyed by the framebuffer

And then we loop through these and figure out the correct ordering to free things depth-first, but I think your list idea is nice and elegant and achieves the same thing.)

Another questionable idea is still leaning on the Lua GC to work out these dependencies for us (since we're basically building a GC of some kind here), but with the addition of a manual garbage collection call before construction to ensure prompt finalization of any prior resources (which would be slow in a scenario of rapid change, but seems fine here since these resources are only rarely re-evaluated)
This actually seems to work but I'm not sure if it's fully deterministic...
-- Create displays
When (your_area) is the rendering area:
    Call collectgarbage("collect"). -- take out the trash
    Call create_display_object() returning /VkDisplay* display/.
    When (display) is garbage collected [capturing (display)]:
        vkDestroyDisplay(display);
    End
    Claim (display) is a “display”.
End

-- Create framebuffers
When /display/ is a “display":
    Call collectgarbage("collect"). -- take out the trash
    Call create_framebuffer_object_for_display(display) returning /VkFramebuffer* framebuffer/.
    -- Capture display to ensure display isn't collected before framebuffer
    When (framebuffer) is garbage collected [capturing (display, framebuffer)]:
        vkDestroyFramebuffer(framebuffer);
    End
    Claim (display) has framebuffer (framebuffer).
End

-- Create color images
When /display/ has framebuffer /framebuffer/:
    Call collectgarbage("collect"). -- take out the trash
    Call create_color_image_for_framebuffer(framebuffer) returning /VkImage* color_image/.
    -- Capture framebuffer to ensure framebuffer isn't collected before color_image
    When (color_image) is garbage collected [capturing (framebuffer, color_image)]:
        vkDestroyImage(color_image);
    End
    Claim (framebuffer) has color image (color_image).
End

On Mar 30, 2022, at 8:54 PM, Bret Victor wrote:

This is very tricky!  But I can think of a way to make it work.  (I think.)

To see the crux of the problem, consider your example, but where the second rule takes a parameter:

When /display/ is a “display", /display/ has some parameter /x/:
    Call create_framebuffer_object_for_display(display) returning /VkFramebuffer* framebuffer/.
    When unmatched [capturing (framebuffer)]:
        vkDestroyFramebuffer(framebuffer);
    End
    Claim (display) has framebuffer (framebuffer).
End

If that parameter changes, we need to reevaluate the body with the new parameter.  "When unmatched" needs to run to clean up the old evaluation before we run the new evaluation -- that's what it's for.  (To destroy the old framebuffer before creating the new framebuffer.).  But it's only after the new evaluation has run that we know if the resulting claims have changed, and only then can any rules downstream (such as your third rule) react to those new claims.

What we want is:
 1. The claim about the framebuffer goes away, which causes:
 2. The claim about the image goes away.
 3. The image is destroyed.
 4. The framebuffer is destroyed.
 5. The new framebuffer is created, and claimed, which causes:
 6. The new image is created and claimed.

With the current reactor, this is impossible, because (1,4,5) always happen back-to-back.  There's no way to "postpone" 4 and 5.

An idea for postponing 4:  in the finalizer ("when unmatched"), instead of directly destroying the resource, enqueue the destructor to be called later at some low priority.

A (weird) idea for postponing 5:  give the rule two priorities, one for matching and one for unmatching.  (In reactor terms, one priority for responding to "+" events, and one for responding to "-" events.)  If the matching priority is low and the unmatching priority is normal, then when the parameter changes, the rule will just unmatch and its claims will simply go away, then everyone else will respond to that, and then later the rule will rematch with the new parameter and make its new claims.

Essentially, everyone gets to see this rule naked while it's changing.  We don't normally want this in Realtalk, but I don't think it violates Realtalk semantics because it all happens within the tick.

I've sketched an implementation below.  It's verbose, but there could be special syntax if this is a common pattern.

I need to think about this a bit more before committing to it, but look through your code and let me know if this would work for what you're planning.  (Or if it even makes sense.)


-- Create displays
When (your_area) is the rendering area [matching and unmatching with priorities (-100) and (0)]:
    Call create_display_object() returning /VkDisplay* display/.
    register_resource(display)                          -- this runs at priority -100
    When unmatched [capturing (display)]:               -- this runs at priority 0
        unregister_resource(display, vkDestroyDisplay)  -- the destructor is called at priority -99
    End
    Claim (display) is a “display”.
End

-- Create framebuffers
When /display/ is a “display" [matching and unmatching with priorities (-100) and (0)]:
    Call create_framebuffer_object_for_display(display) returning /VkFramebuffer* framebuffer/.
    register_resource(framebuffer)
    When unmatched [capturing (framebuffer)]:
        unregister_resource(framebuffer, vkDestroyFramebuffer)
    End
    Claim (display) has framebuffer (framebuffer).
End

-- Create color images
When /display/ has framebuffer /framebuffer/ [matching and unmatching with priorities (-100) and (0)]:
    Call create_color_image_for_framebuffer(framebuffer) returning /VkImage* color_image/.
    register_resource(color_image)
    When unmatched [capturing (color_image)]:
        unregister_resource(color_image, vkDestroyImage)
    End
    Claim (framebuffer) has color image (color_image).
End


-- Resource destruction

_rt.resources = _rt.resources or {}  -- list of resources in order of registration
_rt.resource_destructors = _rt.resource_destructors or {}

function register_resource (resource)
    table.insert(_rt.resources, resource)  -- append resource to list
end

function unregister_resource (resource, destructor)
    _rt.resource_destructors[resource] = destructor  -- mark resource for destruction
end

When the time is /t/ [converging with priority (-99)]:
    if not next(_rt.resource_destructors) then return end
    for i = #_rt.resources, 1, -1 do  -- go through resources from latest to earliest
        local resource = _rt.resources[i]
        local destructor = resource_destructors[resource]
        if destructor then     -- if it's been unregistered, destroy it and remove it
            destructor(resource)
            table.remove(_rt.resources, i)
        end
    end
    _rt.resource_destructors = {}
End




On Mar 30, 2022, at 10:32 AM, Luke Iannini wrote:

On re-encountering the Vulkan construction/destruction conundrum I had an idea I can’t remember if we’ve discussed before (apologies if so!)

If “When unmatched” was guaranteed to run deterministically "depth-first"...

i.e. I could write

-- Create displays
When (your_area) is the rendering area:
    Call create_display_object() returning /VkDisplay* display/.
    When unmatched [capturing (display)]:
vkDestroyDisplay(display);
    End
    Claim (display) is a “display”.
End

-- Create framebuffers
When /display/ is a “display":
    Call create_framebuffer_object_for_display(display) returning /VkFramebuffer* framebuffer/.
    When unmatched [capturing (framebuffer)]:
        vkDestroyFramebuffer(framebuffer);
    End
    Claim (display) has framebuffer (framebuffer).
End

-- Create color images
When /display/ has framebuffer /framebuffer/:
    Call create_color_image_for_framebuffer(framebuffer) returning /VkImage* color_image/.
    When unmatched [capturing (color_image)]:
        vkDestroyImage(color_image);
    End
    Claim (framebuffer) has color image (color_image).
End

and I could be sure that when “Create displays” is edited or removed, the When-unmatcheds will run in a deterministic order of “Create color images” -> then “Create framebuffers” -> then “Create displays”, then everything should work perfectly with no further external state tracking needed.

This is basically the Vulkan API decree — that any Object B that is created from Object A must be destroyed before destroying Object A, and I think it’s common enough in resource acquisition/release APIs that this would be a useful property in general.

I don’t have the latest reactor loaded into my brain at the moment so I don’t know how feasible this is!