Applying ILC in Sodium

[clinuxrulz]

Inspired from here: https://blog.functorial.com/posts/2018-04-08-Incrementally-Improving-The-DOM.html

The blog posts has a concept a Jet a which is a value paired with a description of the change that will happen to that value. Functions of type Jet a -> Jet b form incremental functions, you have the extra information about what changed in a to allow you to describe what changes in b which can be propagated all the way down to the DOM, providing another information to manipulate only the parts of the DOM that need to change via destructive updates. If you read Phil Freeman's post above you'll get a better idea.

These Jet a s can be thought of as dual values, I'll use the word refer to them as duel below, because Jet might get confused with describing an aircraft if used in project.

Here is some pseudo code that demonstrates pattern I propose for doing incremental lambda calculus in sodium.

Stream<DA> sDA; // <-- defined elsewhere, represents a change to A
StreamLoop<A> slA = new StreamLoop<>();
Cell<A> ca = slA.hold(initA);
Stream<Tuple<A,DA>> sDuelA = sDA.snapshot(ca, (DA da, A a) -> new Tuple(a, da));
slA.loop(sDuelA.map((Tuple<A,DA> duelA) -> patchA.apply(duelA._1(), duelA._2()));
StreamLoop<B> slB = new StreamLoop<>();
Cell<B> cb = slB.hold(nonIncrementalVersionOfF.apply(initA));
Stream<Tuple<B,DB>> sDuelB = sDuelA.snapshot(cb, incrementalVersionOfF);
slB.loop(sDuelB.map((Tuple<B,DB> duelB) -> patchB.apply(duelB._1(), duelB._2());

This pattern allows cB to be incrementally updated from a change to cA.

As an example of what the types of A, DA:
A could be an Array Int, and DA could be a description of changes to that array like ArrayChanges Int where
type ArrayChanges a = [ArrayChange a], and
data ArrayChange a = InsertAt Int a | DeleteAt Int | UpdateAt Int (a->a)`

Then B, DB could be describing the DOM or some half way intermediate data structure.

OK. The pseudo code I've given is very messy indeed. But maybe a cleaner abstraction can be made by wrapping some of the FRP objects up in a data structure and make a FRP kinda Jet.

Sorry if this post does not read well. It is a bit rushed.

Any ideas on building an abstraction are welcome.

[clinuxrulz]

One possible wrapper:

https://gist.github.com/clinuxrulz/506b62b45ede646252f6784b09e7bfe3

At DOM level you could have DuelCell<Unit,DomChanges>, or WebGL you could come up with DuelCell<Unit,WebGLInstructions>. Then listen to deltaStream() to interpret the incremental changes to the back end.

[clinuxrulz]

A simplification. I don't believe we'd need to send the old value of a in (a,Δa) tuple. If we send the new value of a in that tuple instead we eliminate the need for retaining the patch functions. Also feels like a destructive update style of ILC is possible, due to the fact we can deal with the new as.

Requirements:
Δa is a monoid.
There exists a Δa such that a₁ ⊕ Δa = a₂ for any a₁ and a₂ (there exist a description of change which can allow you to move between any two values.)

Edit: Actually still need to retain the patch functions to make a composable wrapper. But at least if there is any Δa that is to hard or inefficient to handle the end user can just process the full a without him/her having to call patch on (a,Δa).

[clinuxrulz]

I haven't been active in sodium stuff for a while. I've been trying to make a big push on incremental lambda calculus over virtual dom, because it feels important.

I've made some progress:

clinuxrulz/vdom_escape/blob/master/src/main/java/org/highj/vdom_escape/dom/El.java

I can define incremental dom elements. The type param I is the model. I have a choice between DuelCell and IncF, both should work fine, I just chose to try IncF first. But DuelCell should have some performance benefits when lifting a collection of child Dom elements into a bigger Dom element.

[clinuxrulz]

I wanna share a technique for managing an incremental collection in sodium.

The reader might be familiar with derivatives from calculus at school. It turns out derivatives do not only apply to equations that can be evaluated to a numerical value. Derivatives apply to other things too, in other fields.

In incremental calculus, the derivative of a type signature that represents a value is the type signature of a representation of the change of that value (think Array from 1st post, its derivative is ArrayChanges).

So here is something I've found very handy:
If f(x) = Cell<g(x)>, then the derivative f'(x) = Stream<g'(x)> . It sort of feels like the chain-rule.

Note: Above is a this is a type-level derivative, not a value-level derivative.

How is this useful? Watch this:

OK. We want to manage this list incrementally:
Cell<List<Tuple<Integer,Foo>>>,

The Integer here is just an ID number for easy removal of existing Foos.

Now Foo has attributes that are also represented by sodium objects too internally. That way each element of our UI can independently be hooked up to each Foo independently, and be updated independently without regenerating the whole UI. But what if Foos are added or removed from this list? We do not want to regenerate the whole UI again. So this is where the derivative comes into play.

let f = Cell<List<Tuple<Integer,Foo>>>
now:
f' = Stream<Tuple<List<Tuple<Integer,Foo>>,List<Integer>>>
In the change structure above I'm just focusing on Foos added in the 1st part of the tuple, then a list of Foo IDs in the 2nd part of the tuple for Foos that are removed. Now using that f for the initial construction of the UI, then using f' for changing UI elements that get added/removed, you now have a completely incremental UI for elements added/removed or changed in place. Only the parts of the UI that are required to be updated will be updated, and the whole UI will not be recalcuated from scratch.

I had a really good run with sodium today at work. I used the technique described above for a custom paperwork creator that allows dragging in viewport of the 3d scene on some paper and adding labels and dimensions on top in paper space. It worked like a dream, all UI elements where updated completely incrementally. So I wanted to share.

Sodium is a truly wonderful language.

[dakom]

Sounds awesome! Can't say I follow enough to like really get it - but I'd love to see some demos, even just for inspiration for something I might understand more down the road...

[clinuxrulz]

It looks like you were right on the money here:

Architecture question - where to loop?

@the-real-blackh - thanks, that's a generous offer! I'll try to keep the problem as generic as possible so that everyone can learn from it... I keep on coming back to the same solutions and problems and haven't quite cracked it yet. I've come close... and I did have a solution that kindof worked but I know it was too convoluted and I'm just missing something. Probably better if I take the time to really describe the exact solutions I tried and where I ran into trouble, but I don't have al…

Your Cell<Array<Cell<Object>>> . The is precisely the type of a incremental collection in sodium, each element of the array can be hooked up to the view avoiding the use of switchC here. Then providing a Stream<Array<Cell<Object>>> sObjectsAdded and a Stream<Array<ObjectID>> sObjectsRemoved and use those to improve the performance of the view, so existing constructed Cell<Object> remain constructed and linked while those objects are alive. (switchC comes particularly useful for doing modes).

sObjectsAdded and sObjectsRemoved above both if merged together form the derivative of Cell<Array<Cell<Object>>>.

[clinuxrulz]

Just a couple more derivatives for interest sake.

f(x) = Tuple<g(x), h(x)> --> f'(x) = Tuple<g'(x),h'(x)>

f(x) = Either<g(x),h(x)> --> f'(x) = Either<g'(x),h'(x)>

Those two are very straightforward.

I'll definitely have to do a small example sometime to demonstrate the concept. Knowing how to construct the derivative of a type signature comes in handy for designing a way to incrementally manage data in other shapes rather than just lists.

[clinuxrulz]

One more

Atomic represents types that completey change or not at all (e.g. a number or a string)

Let x be a atomic type in the expression below:
f(x) = Cell<x> --> f'(x) = Stream<Maybe<x>>

Now f'(x) = Stream<Maybe<x>> may as well be f'(x) = Stream<x> as we can apply filterMaybe/filterOptional. And Stream<x> can be obtained by Operational.updates.

So this means all the information that we need is just in f, and f' is not required.

All this means is sodium does a great job at incremental atomic value types without having to think hard.

[Ziriax]

Very interesting, thanks a lot for sharing this!

[clinuxrulz]

Another good run with Sodium...

One more technique. This one is very handy when you have a very large number of entities in your scene graph.

"Automatic delta for your change structure, plus destructive updates of scene."

Here we go. The general pattern is as follows:

private final ArrayList<Listener> keepAlive = new ArrayList<>();
.
.
.
public App() {
    sodium.Transaction.runVoid(() -> {
        MutableSceneCtx scene = new MutableSceneCtx();
        CellSink<ReadOnlySceneCtx> csSceneCtx = new CellSink<>(scene);
        Stream<SceneChanges> sSceneChanges = scene.sSceneChanges();
        Cell<Mode> cMode =
            Stream
                .orElse(
                    java.util.Arrays.asList(
                        sMode1.map(unused -> mkMode1(csSceneCtx, sSceneChanges)),
                        sMode2.map(unused -> mkMode2(csSceneCtx, sSceneChanges)),
                        sMode3.map(unused -> mkMode3(csSceneCtx, sSceneChanges))
                        . . .
                    )
                )
                .hold(mkDefaultMode(csSceneCtx, sSceneChanges));
        Stream<Consumer<MutableSceneCtx>> sUpdate =
            Cell.switchS(
                cMode.map(Mode::sUpdate)
            );
        keepAlive.add(sUpdate.listenWeak((Consumer<MutableSceneCtx> effect) -> {
            effect.accept(scene); // <-- deltas automatically get constructed here without
                                  //     the rest of the code having to worry about it.
            sodium.Transaction.post(() -> {
                csSceneCtx.send(scene);
                scene.releaseChanges(); // <-- causes sSceneChanges to fire
            });
        }));
    });
}

In the above code csSceneCtx and sSceneChanges form the incremental scene. It is sort of like a DuelCell given in the very 1st post. The idea is for any modes or views that come late to the party, they take a snapshot of the csSceneCtx to initially construct themselves, then from there on only monitor sSceneChanges in order to update themselves incrementally.

To use this code safely the programmer has to promise not to retain a reference to the object they obtain from csSceneCtx beyond the end-of-transaction, he/she can only read it breifly to obtain enough information to construct the initial state to be maintained, then watch sSceneChanges to move from state to state.

Its easy to define helper watch functions from the pair csSceneCtx and sSceneChanges to monitor certain aspects of the scene. (E.g. Monitoring if a mouse is over a particular line, then using it to alter the line thickness in the back end to show it is being hovered over. And if that line is deleted later on, the created watch cell is dropped and that aspect of the scene is no longer processed.)

I probably have not explained this well, but this is the main technique I've use at work and the performance gain I received from switching from an Immutable Scene to a Mutable Scene was quite impressive. A large scene with nearly 1/4 of a million entities (not all visible at once) went from 2 seconds per alteration to seemingly instantanious. (Switching from an immutable IntMap to java.util.HashMap). The performance benifets of O(1) compared to O(log(N)) really start to show themselves with a very large number of entities. My boss was over the moon when he noticed the sudden performance gain.

This touches a little bit on what is described here: http://sodium.nz/t/intersection-of-imperative-and-functional/299?u=clinuxrulz

[clinuxrulz]

Note in the code above MutableScene and SceneChanges contain no sodium objects. A Cell of a list of Cells is not the only way to define a incremental collection. This is beneficial to keep serialization easy. Both MutableScene and SceneChanges are just data.

[clinuxrulz]

The soon to be available Angular Ivy uses incremental dom. It could be a good place to seek inspiration in this area.

https://blog.nrwl.io/understanding-angular-ivy-incremental-dom-and-virtual-dom-243be844bf36