Ocaml/bonsai: simple JS repl

Learning
1 
> 1 + 2
out: 3
> x = 20
out: 20
> x + 2
> out: 22
[ input text box ]

Imagine we are building a dumb JS repl in ocaml/bonsai. The page has two parts:

top-div: list of previous input/output pairs
bot-div: input text box

Now, I can build a solution where on every update it takes O(n) for the vdom to rebuild; i.e. it has to rebuild the all n (in[i], out[i]) pairs then do a vdom tree diff. Then I get into the mess of trying to cache vdom trees for each (in[i], out[i]) pair so it is built once, taken ref of in the future, and have fast diffs.

I am wondering if there is a smarter way to do this ?

2

I think there is something interesting here in the way the counters example handles multiple counters, but it is not obvious to me how Bonsai.assoc interacts with this: https://github.com/janestreet/bonsai/blob/v0.16/examples/counters/lib/bonsai_web_counters_example.ml#L69-L74

3

Heyo! Really good question!

A short answer is that if you can turn your Vdom.Node.t list into a Vdom.Node.t Key.Map.t, ideally also computed incrementally via an assoc or incremental map functions within Bonsai.Map.*, you can use Vdom_node_with_map_children.make [1] for “optimal” diffing behavior so that bonsai can do less work calculating the diff.

In the counters example you linked, the “counters” map is computed incrementally with Bonsai.assoc, but Map.data takes O(n) time to run, so constructing the Vdom.Node.t list is still O(n).

Also happy to answer any other follow up questions you may have!

4

Is Bonsai.assoc the right way to implement a file tree viewer ? (Using map with key = filename)

The ops I want to support are:

  • expand/collapse directory
  • rm directory
  • new directory
  • create / delete file
    and everything always sorted in order.

Thanks!

5

Oooh I think this is an interesting/hard question. I don’t have much context on the specific requirements, but I think that implementing expand/collapse on top of just Bonsai.assoc on a map of filename -> file might be hard. (I am assuming that you can collapse arbitrary directories, and collapsing those directories, also collapses all of their children, which might be hard to track on a flat map.)

Another construct that might be useful to use - in addition to Bonsai.assoc - is Bonsai.lazy_. It lets you have “recursive” components which might let you implement the recursively-collapsing behavior with OCaml recursion.

let rec directory (name : string Value.t) : Vdom.Node.t Computation.t =
  Bonsai.lazy_
    (lazy
      (let%sub is_collapsed, toggle = Bonsai.toggle ~default_model:false in
       match%sub is_collapsed with
       | true -> (* collapsed view, maybe just the filename is shown *)
       | false ->
         let%sub children = (* ... *) in
         let%sub rendered_children =
           Bonsai.assoc
             (module String)
             children
             ~f:(fun ~key ~data:_ -> directory key)
         in
         (* title with children is shown. *)
      ))
;;

Something worth mentioning is that laziness is required because bonsai traverses the entire computation graph when starting. Otherwise, you might get a sad stack overflow error as bonsai attempts to traverse an infinite graph.

I took a stab at this and mocked a very rough/ugly >.> directory structure showcasing a usage of Bonsai.lazy_ here: (Edit: Oh whoops! The bundled JS is 25MB!! Please don’t click if you’re on a data plan/have limited connectivity. I’ll look into lowering the bundle size, but in the meantime, don’t click if you’re on a data plan!) Bonsai filesystem demo!

The source code for it is found here: https://github.com/Enoumy/bonsai-filesystem-question/blob/main/lib/filesystem.ml#L99

Happy to answer any follow-up questions you may have!

2 Likes
6

Sorry to be so pedantic/paranoid; would you mind throwing a MIT / BSD / Apache license on that repo? (I’m building something commercial in Bonsai).Thanks!

7

No worries! Totally reasonable, I’ve just added an MIT license.

1 Like
8

  1. Thank you for the amazing sample code; I am still in the process of studying it. I will be posting followup questions to this in the following days.

  2. Meanwhile, I am reading up on precisely what let%sub, let%map, let%arr, match%sub, match%arr desugars to, to better understand what is going on.

Quoting https://github.com/janestreet/bonsai/blob/master/ppx_bonsai/readme.md?plain=1#L8-L59 I want to focus on the last part:

The difference is that the second option binds a and b to the
computations that map temp_var to its components, but the first option
binds a and b to the components after the mappings have occurred.
Conceptually this means that for the first, correct desugaring, reusing a and
b does not duplicate the mapping computation, but for the second desugaring, every
usage of a or b refers to a duplicate of its computation.

This seems a bit over dramatic to me. My understanding is that even in the “incorrect” usage of:

let%sub temp_var = c in
let a = map ~f:(fun (a, _) -> a) temp_var in
let b = map ~f:(fun (_, b) -> a) temp_var in
BODY

even in this “incorrect” usage, the c/temp_var is only computed once. The only duplicated work on reusing a/b are the:

fun (a, _) -> a
fun (_, b) -> a

I understand that when we “reuse” a Value.t, we have to redo the work – but in this case, it seems this is not a very convincing examples, as the “redo work” is very cheap.

What this example be better written as

let%sub temp_var = c in
let a = map ~f:(fun (a, _) -> some_expensive_func1 a) temp_var in
let b = map ~f:(fun (_, b) -> some_expensive_func2 a) temp_var in
BODY

note the addition of the ‘some_expensive_func1/2’ – in this case, we’d want to use a %sub/return to cache the result instead of recomputing on it on the re-use of a/b.

However, this would no longer fit into the point of explaining let%sub (a, b) = c.

My current confusion here is I’m not sure if the situation is:

  1. I am misunderstanding something OR

  2. The example in the highlighted section is not very convincing, as all the “extra work” is merely pulling the first/second elem of a tuple.

Thanks!

1 Like
9

Yup! You are correct, all of the extra work is just pulling out the first/second element of a tuple which isn’t very expensive + it may not necessarily be duplicated.

It is only duplicated anytime it’s used; so if it’s used as an input to two other computations, then it’ll be done twice, but if it’s only used once, it’ll not be duplicated.

  let ok = map ... in
  let dup2 = map ... in
  let dup5 = map ... in
  let%map ok = ok
  and x1 = dup2
  and x2 = dup2
  and x3 = dup5
  and x4 = dup5
  and x5 = dup5
  and x6 = dup5
  and x7 = dup5 in
  ...

ok is only used once so no duplicated work occurs. dup2 is used twice, so it’s computed twice. dup5 is computed 5 times.

Something implicit about “duplicated” work is that once you’ve duplicated work, it’s really easy to accidentally do exponential work.

  let x = map ... in
  let y = let%map x1 = x and x2 = x in ... in
  let z = let%map y1 = y and y2 = y in ... in
  let q = let%map z1 = z and z2 = z in ... in
  let%map q1 = q and q2 = q in
  ...

Where the work in x is duplicated 16, times (assuming I counted correctly >.>).

This answer really doesn’t have a satisfying “why” let%map results in duplicate work though. I highly recommend reading this blogpost:

10

I’ve read that blog post, @askvortsov suggested it multiple times. :slight_smile:

The issue I was struggling with was:

  1. based on that blog post, the overhead of the “wrong” method was not all that much – only calling (x, ) → x and (, x) → x
  2. the bonsai_ppx readme.md made it sound as if it was a big deal

Thanks for sharing the O(n) lines → 2^n work edge case; it is obvious in retrospect but I did not recognize it until now. Looks like let%map is far more dangerous than I thought.

1 Like