I am aware of bonsai/07-flow.md at master · janestreet/bonsai · GitHub , in particular the section on match%sub
From trial & error, I also get the impression that
let%sub x = ... in
match x ...
is NOT the same as
match%sub ... with
It’s been a while since I used Bonsai, but from what I recall, in the snippet you provided with let%sub:
let%sub x = ...
...
x has the type _ Value.t, so to match on it, you’d need to first use let%arr on it:
let%arr x = x in
match x with
| ...
(and having used, let%arr _ = ... in , the rest of the program must have _ Value.t (i.e no using any further computations).
If you wanted to still use computations while still matching on the value of x, you’d have to use some combination of Computation.read @@ Value.map (fun x -> match x with ...) etc.
I agree with all of this so far. I don’t understand the last 2 lines of:
Here is something else I don’t understand:
let%sub lhs = rhs in ...
the rhs has to be a 'a Bonsai.Computation.t
match%sub expr with
expr can be a 'a Value.t
This seems very strange to me; I would have expected that expr also be forced to have type 'a Bonsai.Computation.t
Hey! Bonsai dev here. You’re correct that the equivalence that you’d expect between let%sub x = expr in match expr with ... and match%sub expr with ... does not hold. One reason is that the x you get from let%sub x = expr in .... has the abstract type _ Value.t, so you can’t match on it.
Now, there is an equivalence between the following pieces of code:
let c (input : (int, int) Either.t Value.t) : _ Computation.t =
match%arr input with
| First x -> x + 1
| Second x -> x - 1
and
let c (input : (int, int) Either.t Value.t) : _ Computation.t =
match%sub input with
| Left x ->
let%arr x = x in
x + 1
| Right x ->
let%sarr x = x in
x - 1
There are a bunch of quirks in the second piece of code that I could go into if you’re interested, but the my main point is that for “pure” computation, match%sub and match%arr mean the same thing.
There are two main differences:
match%sub has the potential to be more incremental, since only the “active” branch needs to be kept up-to-date. With match%arr, you have to specify a dependency on all the inputs to all the branches, but with match%sub, you can have each branch use its own list of dependencies.
Since each branch of a match%sub is a _ Computation.t, each branch is allowed to have its own internal state or lifecycle events. let%arr requires all those things to be specified up-front for all the branches.
In short, match%sub is how you tell Bonsai that you have conditional logic. Without it, Bonsai can’t tell what you’re opaque OCaml logic is doing.
Yeah, you’re right. That is what I would expect too, and when we were making the ppx, we knew that was what people would expect. However, we made that position be a _ Value.t for the pragmatic reason that we thought this would be the way more common case, so most matches would look like match%sub return x with ....
Note that neither choice is more powerful than the other. For instance, if you need to match on a computation, you can “sub” on it first.
let%sub x = comp in
match%sub x with
...
Thank you for the detailed response.
Let me take a rain check on this; I think I have finally gotten a hang of fixing bonsai type checking errors, and most things will become clear after writing a high volume of bonsai.
Thanks for developing bonsai; very intellectually satisfying to get something that finally type checks.
That would be nice if you could put some more about the quirks, if you have the time.
(I deleted my last post as I accidentally replied to the wrong message.)
Sure thing. Let me back up and build up from the simple case to the most complex case.
Consider the following code:
let%sub a = b in
c
The types are as follows:
a : 'a Value.t
b : 'a Computation.t
c. : 'b Computation.t
<entire expression> : 'b Computation.t
This is all dictated by the type of the sub function, which is what the let-syntax code above expands to use.
val sub : 'a Computation.t -> f:('a Value.t -> 'b Computation.t) -> 'b Computation.t
The expansion of the let-syntax code above is
sub b ~f:(fun a -> c)
This should be nothing new if you’re familiar with let%bind and let%map from ppx_let.
Now consider this code:
let%sub a, b = c in
d
The types are:
a : 'a Value.t
b : 'b Value.t
c : ('a * 'b) Computation.t
d : 'c Computation.t
Think about this for a few minutes; something should feel a bit off. Note that the pattern can actually be any pattern - triples, records, variants, you name it. But all the variables that show up in those patterns will have type _ Value.t
The reason this is possible is that let%sub does some magic whenever it sees something other than a simple variable pattern. The above code expands to this:
let%sub temp = c in
let%sub a =
let%arr a, _ = temp in
a
in
let%sub b =
let%arr _, b = temp in
b
in
d
Why would you want this? Well, Bonsai is a layer on top of incremental, so the incrementality of this code is significant. If c changes , then both projections will run, but only the components that have changed will continue to propagate changes.
Now we can get to match%sub. Here’s some code similar to what I put in the first post, except the First case contains a tuple now, to illustrate the destructuring point from the previous section.
let c (input : (int * int, int) Either.t Value.t) : _ Computation.t =
match%sub input with
| Left (x, y) ->
let%arr x = x
and y = y in
x + y
| Right x ->
let%sarr x = x in
x - 1
Again, all the variables in the patterns are of type _ Value.t. For the same reason as with the let%sub, the fact that we can pattern match is really weird; if all this expanded to was a call to sub, we couldn’t pattern match because all we get from sub is an opaque _ Value.t. Yet somehow we’re able to explode the various components of the patterns. Here’s what the above code expands to.
let c (input : (int * int, int) Either.t Value.t) : _ Computation.t =
let%sub temp = input in
let%sub index =
let%arr temp = temp in
match temp with
| Left (_, _) -> 0
| Right _ -> 1
in
switch
~branches:2
~match_:index
~with_:(function
| 0 ->
let%sub x, y =
let%arr temp = temp in
match temp with
| Left (x, y) -> x, y
| Right _ -> assert false
in
let%arr x = x and y = y in x + y
| 1 ->
let%sub x =
let%arr temp = temp in
match temp with
| Left (_, _) -> assert false
| Right x -> x
in
let%arr x = x in x + 1)
Here’s what’s going on.
switch function provided by Bonsai. This functions job is to call with_ ahead of time with all the numbers from 0 to branches. Only one of those branches is active and alive and updating at one time. Whenever match_ changes, the active branch switches to its new value.assert false should never get hit because it only gets hit in “impossible” conditions for each branch.Clear as mud, right?
@philip : I’m not sure if this is on-topic. I’m currently trying to read bonsai/web_ui/partial_render_table at v0.15 · janestreet/bonsai · GitHub
I understand this is so we only render the visible rows of a table, instead of all the rows of the table.
Previously, (with much help from this forum), I got the ts-gui example running, which shows a sample trading system with 10,000 virtual rows and 35-ish visible rows. (Technically, this was with incremental directly, not bonsai).
Here is what I don’t understand:
What is the high level design / implementation strategy of partial render in bonsai ?
Any non-intuitive things to keep in mind while reading the source ?
Thanks!
When dealing with long (Vdom.Node.t list) , how do we provide hints for diffing ?
For exajmple:
old = [ a100; a101; a102; ... ; a200 ]
new = [ a99; a100; a101; ...; a199 ]
in a normal/dumb diff, it will find 101 different elements; however, I’d prefer to do a ‘hinted’ diff, where a99/a200 don’t match up, but for a100-a199, the old/new ones match up.
Thanks!
There’s a bunch of features unrelated to partial rendering that this table has, such as focus handling, resizable columns, sortable columns, and dynamic row heights, and all of them get harder when you bring partial rendering into the mix. Then there’s the partial rendering itself, which is probably not too difficult to implement just by itself. However, we made our job a little harder by exposing enough in the interface to make server-side collation (i.e. sorting, filtering, and range-restriction) possible.
We use the incr_map_collate library to turn the input _ Map.t Value.t into an Incr_map_collate.t, which represents a map that is sorted according to some comparison function, filtered according to a predicate, and trimmed according to some range. All three of those things are controlled by parameters to the main collate function of that library. While it’s interesting to look at how the library works, it’s probably out of scope for this explanation.
The rendering code takes this pared down map and renders all the items in it. To make sure the user’s scrollbar works as expected, we add a ton of padding to the top of the rendered items so that they show up in the right place. To be precise, we add row_height * num_items_above_collated_map, where num_items_above_collated_map is provided inside the Incr_map_collate.t type.
To summarize so far, the strategy we take to partial rendering is that we pretend to render the entire map all the time, but we only actually render items that would be visible, and those that aren’t visible are just filled with blank space.
The last piece thing we need is a way to which part of the container element is actually visible. For this, we use this library to track the visible portion of that element; that library runs element.getBoundingClientRect() every frame, which allows it to notice whenever the visible rect has changed. Whenever it changes, we update which range that we pass to collate, which then changes which elements are included in the map that is rendered to the screen; if all goes correctly, those new items will cover the whole viewport so that the user is none the wiser.
Hope that helps a bit.
All the node-creation functions take a ?key:string argument as the “hint”. I’m not too familiar with exactly how virtual-dom uses that hint, but I’m pretty sure that in your example, providing a unique key for all those elements will cause the diff to be just “add a99, remove a200”.
Thank you for this detailed response. I learned quite a lot. If you have time, a few more clarification questions:
Suppose we have a table with N rows where k << N are visible.
In order to support dynamic row heights, does this mean:
You need to calculate the height of all N rows ?
Does this involve constructing the Vdom.Node.t for all N rows ?
If not: how do you support dynamic row height ? If so, this seems awfully wasteful just to figure out where the visible blob is relative to a not-rendered “outer div”.
I think there is alot of “I don’t know what I don’t know” here regarding how you efficiently compute the dynamic row heights of giant tables. (this seems very expensive)
I am curious how much of this simplifies if we throw away the dynamic-row-height requirement and only supported static row height (I might try to implement this myself) say h.
So now we have 3 “constants”; N the # of rows in the table; h (specified in pixels), the constant row height. And k = ceiling( visible height / h).
In this simplified model, would the following suffice:
construct a div of height N * h ;; O(1) time
inside this div, have k rows, where each row has:
2.1 a “key” for easy diffing for vdom
2.2 css position = “absolute top = …” (here ‘absolute’ means absolute relative to parent)
This would pretty much suffice for “partial rendering given fixed height rows” right ? the giant outer div ensures the scrollbars; the keys ensures efficient vdom diff; and the “position top = …” places the divs at the right place relative to the giant outer div.
Thanks!
I think I misunderstood this. Is partial-render-table doing something like:
[ row 0 ---+
; row 1 |
; ro2 2 |
| -- approx this as row_height * k
.... |
|
---+
; row k <-- first visible row
; row k+1 dynamically calculate neights here
; row k+2
; row k+3
; row k+4
; row k+5
; row k+6 <-- last visible row
....
; row 9998
; row 9999
]
We simplified the problem by rendering all rows the same height. By “dynamic row height”, I mean that the row height is a _ Value.t, so it’s allowed to change while the app is running. This is actually a recent feature addition; if I recall correctly, the basic idea was easy to implement, but we also wanted to preserve the scroll position as the row height changes.
Anyway, you’re “static-row” suggestion sounds close-ish to what we do. There are some minor technical differences (we use padding instead of absolute positioning), but the main idea is the same.
I have thought of trying your idea of allowing each row to have a different height by assuming all the off-screen rows have the same height. I think this would could work, but it would have the downside of the scrollbar positioning not being totally accurate. Maybe it’s worth the trade-off, though. I haven’t thought it through enough to know how complicated it would be, either.
I think this clarifies up all known errors/confusions on my part. Thanks for your time / explanations.
@philip : If you have time, I have one more question.
Consider the following recursive type
module MyTest = struct
type t = Symbol of string | Int of int | List of t list
end
Is there a way, perhaps through using bonsai/04-forms.md at master · janestreet/bonsai · GitHub that can build a graphical editor for the above type ?
The part that is throwing me off is that the type here is recursive. It is not obvious to me if the approach is to:
Have a Sexp.t Value.t , then figure out how to store “paths” to inner parts of the struct, which we then use later for update.
Modify the Sexp.t to use ref , this makes “pointing to inner part” easier, as we just point to the ref, but it is not obvious how rendering / checking for equality works
modify the Sexp.t so that each inner node becomes a (Value.t, inject) pair. I have not thought this out in detail.
Question: is there an example of how to build an graphical editor / GUI for a “recursive type” ?
Thanks!
One more thing, can you offer insights on the overhead of
_, inject = Bonsai.state_machine# ...
?
In particular, is this on the cost of a single ref, or something much higher?
The XY problem is: for a recursive data structure I’d like to build a editor for, I’m trying to figure out if having a Value/Inject/State_Machine# for every node is affordable.
There are a few approaches to building a UI for that type.
let%sub and match%sub.bonsai_web_ui_form, so that you don’t have to deal with all the boilerplate of separately composing the view, setter, and getter for each individual form.I’ll skip (1), since it isn’t any more interesting for this type than for any other type, and it sounds like your question is more about (2).
The bonsai_web_ui_form library provides a Typed module which has Record and Variant sub-modules. Here’s some code that might work for that type. I’m feeling lazy right now, so I’m not even looking at the mli or a type-checker while I write this - no guarantees that this code compiles.
module Form = Bonsai_web_ui_form
let rec form : MyTest.t Form.t Computation.t =
Bonsai.lazy_ (lazy
Form.Typed.Variant.make
(module struct
module Typed_variant = MyTest.Typed_variant (* Make sure to [@@deriving typed_variants] in the [MyTest] module. *)
let form_for_variant : type a. a Typed_variant.t -> a Form.t Computation.t =
function
| Symbol -> Form.Elements.Textbox.string ()
| Int -> Form.Elements.Number.int ()
| List -> Form.Elements.Multiple.list form
end))
The two interesting parts of this code, in my mind, are (a) how the make function is able to abstract over an arbitrary variant by taking a first-class module, and (b) how we can build recursive Bonsai computations using laziness.
Worth mentioning is that we have a library for auto-generating forms for types that have a sexp-grammar.
The last thing I’ll say is that while the forms library, and especially the auto-generated forms, make building forms really quick and easy, they are a bit inflexible with how the view part is constructed. If you are particular about how the forms appear, then you may be better off building it from scratch.
Although Bonsai.state_machine0 and its friends look like they are minting a mutable thing at the leaf of the computation, in the implementation we take an approach similar to the “Elm Architecture” popularized by the Elm programming language. That is, we have a single top-level mutable Incr.Var.t (which is basically just a ref) for representing the “model” [1] Thus, the cost is quite a bit higher than a single ref. The overall model ends up being a tree of nested tuples, with each let%sub being a point where we introduce two incremental nodes to project the components of that tuple (each component represents that model that came from each of the two sub-computations inside a let%sub expression). Conversely, each “action” (the thing that says how to update the model) is a “tree” of Either.ts. Every time someone runs inject, the action it sends encodes all the decisions you have to make to get to the part of the tuple for that state-machine.
We’ve had discussions in the past about making state-machines be as cheap as a ref, and we may still do it. However, we haven’t been super motivated to work on it because in practice it hasn’t been a huge deal.
[1] “model” is the term we use to refer to the internal state of a computation. Bonsai.state_machine0 is how that internal state peeks through into the result of the computation.
Thank you for the sample code, I’ll go build on this.
There is one thing that is immediately confusing me – why do we need lazy ?
My mental model of lazy is as follows:
type 'a My_Lazy_Inner =
| Done 'a
| To_Eval of (fun () -> 'a)
type 'a My_Lazy = 'a My_Lazy_Inner ref
where it’s basically memoize + thunk, expressed as a ref of either (1) unevaluated thunk or (b) memoization of evaluated
I also understand that stream is useful for dealing with things like infinite streams, i.e. the classical example of:
; something like this; making up syntax
fib = 1 :: 1 :: (map2 + fib (drop 1 fib))
take 10 fib
Here is the part I’m confused:
What is the connection between recursive Bonsai computations & laziness ?
In most cases, I expect the full Vdom to be constructed, so laziness is unlikely to save us any computation. Thus, what is the connection between recursive component and bonsai lazy ?
Thanks!