Explore addition of a Virtual/Incremental DOM mechanism

[OlivierBlanvillain]

Especially needed to deal with mutable Seqs. Here is an abstract for the project:

Functional reactive programming (FRP) is a popular paradigm for developing web interfaces, but care needs to be taken in the DOM binding mechanism in order to have good performance.

State of the art DOM binding libraries such as Facebook React relie on (virtual) DOM diffing mechanism to obtain best performances. On every update, a complete view of the application is generated in memory. The framework then compute a diff between current and previous view to finally apply the minimum changes to the DOM.

Another approach, called precise binding, makes use of FRP constructs to build views while maintaining a dependency graph of Rxs, values susceptible to changes over time. This mechanism, currently using in the monadic-html library, allows changes to be propagate very precisely to the DOM. However, depending on the granularity of mutations, idiomatic monadic-html can be inefficient when re-rendering large portions of the DOM for small changes.

The goal of this project is to design a DOM diffing algorithm in Scala.js which could be combined with the existing precise binding mechanism to obtain an hybrid approach. Depending on time, the project would include benchmarks to compare this hybrid binding approach with existing solutions.

[OlivierBlanvillain]

Something like this sounds simple enough: https://github.com/localvoid/kivi/blob/26eae1043efb9cc4ba7e54c1c4ab30389a669149/lib/vnode.ts#L1284-L1518

[nartamonov]

If I understand correctly, Binding.scala resolves this issue with observable sequence (Vars), so when some elements are updated/removed/inserted, library knows exactly what part of DOM should be mutated. monadic-html only have observable cell (Var) which can contain sequence, but when sequence are mutated library should rerender whole DOM tree for that sequence. Why can't we introduce observable sequence like in Binding.scala? Sorry if question is silly, I'm really novice in reactive programming.

[OlivierBlanvillain]

If I understand correctly...

You'r spot on!

Why can't we introduce observable sequence like in Binding.scala?

We could, but I would personally like to implement the more general solution of tree diffing. Let me explain what I dislike about a sequence only solution:

• The API to manipulate Vars is imperative, in a way, it's exposing the diff API to the user.

• It does not solve the case where you update one field of a case class Foo(s1: String, s2: String, ..., s22: String), you have to rerender a fooView. You could of have case class Foo(s1: Var[String], s2: Var[String], ..., s22: Var[String]), but that does not looks idiomatic to me, and ideally a pure performance optimization should not affect the current nice immutable code I have.

• Similarly, if you are rendering large trees, maps or tuples, you have to fall back to the less appropriate abstraction of sequences to get nice performances.

[nartamonov]

Thanks, @OlivierBlanvillain! I understand now difficulties with Vars :relieved:

[bbarker]

Would it make sense at all to make a separate library that does patch directly on scala.xml.Node? Such a project might be useful elsewhere, and could be used by mhtml. Of course, there are many subtleties (or maybe obvious points) I haven't grasped yet. Possible example: https://github.com/andyglow/scala-xml-diff

[OlivierBlanvillain]

@bbarker I think that could work, here are a few things to take into consideration:

• mhtml currently uses a custom version of scala.xml, which means we should either rollback to https://github.com/scala/scala-xml now that is cross compiles to scala.js (and lose some type safety), cross compile the xml diff library against mhtml fork of scala.xml, or simply add more stuff directly in mhtml. The latter option might be more pleasant given that it gives the implementer full control over the AST.

• Half of the work of a dom diffing algorithm is to apply patches to the actual dom. This will likely be tightly coupled with the way notes are mounted to the dom, so decoupling in diffing might increase the friction for patching.

[fdietze]

MetaRx solves the problem with delta objects: http://metastack.pl/metarx/latest.html#buffers

[OlivierBlanvillain]

@fdietze This looks like the same solution that what's used in Binding.scala. As explained in this previous comment, I would rather go for a solution that does not require users to write in an imperative style.

Let me give an example of why I dislike the delta objects approach. Suppose I want to implement this page: https://en.lichess.org/games. I already have all my business logic implemented in term of the following:

case class Chessboard(...)          // Something that's easy to display on the screen
case class Move(from: Pos, to: Pos) // Any move on the board

def applyMove(m: Move, c: Chessboard): Chessboard =
  ??? // All the game logic goes here

def renderBoard(c: Chessboard): scala.xml.Node =
  ??? // All the front-end work goes here

If I want to animate the boards on the /games pages in a reactive way, I would have to turn my Chessboard data structure into a delta objects and, most importantly, rewrite all the logic in applyMove in a mutable/imperative style.

With React style dom diffing, I can keep all the existing logic (and the super simple renderBoard rendering function), and still count on the diff algorithm to save the browser from re-rendering every chessboard on every move.

[fdietze]

Ok, I understand. So maybe a hybrid approach would make sense. Delta updates only for common data-structures (like Lists) and Virtual DOM diffs for custom ones.

[OlivierBlanvillain]

Everything in the library was built to encourage immutability / referential transparency, I don't think exposing a mutable API for a few data-structures would fit well with what's already there...

Also, with a diff algorithm in place, why would you ever want to formulate your business logic in term of patches instead of functions over immutable data structures?

[fdietze]

I think the delta-approach doesn't necessarily need to be implemented with mutable data structures. The whole point are efficient updates which is also achievable with immutable datastructures. This should preserve the referential transparency property. Am I overlooking something?

I agree that you probably never want to formulate patches in your business logic. That's why some common data structures like lists should do that automatically. The usage would only shift from manipulating the immutable list manually to using methods to manipulate the reactive immutable list (and automatically handling the diff-part). Does that make sense?

[OlivierBlanvillain]

I think the delta-approach doesn't necessarily need to be implemented with mutable data structures

I have the impression that this is not the way it works in other libraries implementing delta objects, for example looking at the js-framework-benchmark for Binding.scala none of this is referentially transparent (they are mutations happening under the hood).

But if you have ideas for a different design I'm all yours!

[Atry]

Binding.scala users usually use normal case class as data source and still get the benefits of partial updating.

They usually performs coarse-grained source updating, which triggers fine-grained dom updating. For example: https://github.com/walfie/gbf-raidfinder/blob/master/client/src/main/scala/walfie/gbf/raidfinder/client/ViewModel.scala#L72

[OlivierBlanvillain]

This is exactly what I mean by imperative style. In a way, Binding.scala imposes the use of mutable data structures (to get good performances). In the Chessboard example, it might be unrealistic to require a rewrite from

// Pure function
def applyMove(m: Move, c: Chessboard): Chessboard

to

// Updates the Var in c: Chessboard
def applyMove(m: Move, c: Chessboard): Unit

Diff/patch algorithms solves this, you can use immutable data structures and pure functions while still getting the benefits of minimal DOM updates.

[Atry]

@OlivierBlanvillain That's why the library name is Binding.scala 😄

[Atry]

I think FRP is a good tool for modelling state machine. On the other hand, data-binding is better for UI.

[OlivierBlanvillain]

I would personally pick referential transparently over the alternatives any day of the week, but what's better ultimately comes down to preferences, so let's not get into that :wink:.

Regarding FRP vs data-binding, I think the two are not mutually exclusive! Indeed, putting Vars aside, the Binding.scala APIs are a subset of what's implemented in mhtml. In addition to pure/map/flatMap on Rx[T] and := on Var[T] (which is also <: Rx[T]), we also have a bunch of elm inspired operators like dropRepeats, merge and foldp. Any the two play quite nicely together!

When handling users inputs, say button clicks, you essentially have the choice between directly mutating your business logic state on some existing Var (which would be more imperative), or modeling these clicks as a Rx[Unit] to be composed with other Rxs (that would be more functional). Then all Rxs can be binded to HTML nodes, independently of whether they were constructed imperatively with data-binding style assignments, or compositionally with FRP-style methods.

Anyway, that's a really interesting discussion, I should factor some of this out in the FAQ as it nicely summaries the hybrid nature of the design :smile:

[Atry]

Maybe data-binding can be seen as a special case of FRP. However, if you need only data-binding, you can perform some optimizations. For example, caching values, preventing re-calculate when the cached value is not changed. https://scalafiddle.io/sf/5vXgQDL/1

And of course, patching data on BindingSeq is another optimization.

[sometao]

Any update for this issue?

[bbarker]

With regard to data binding and cached values, this is being handled in

94. I don't know of any work so far being done on vdom diffing.

On Sat, Mar 17, 2018 at 1:32 AM, Tao notifications@github.com wrote:

Any update for this issue?

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/OlivierBlanvillain/monadic-html/issues/13#issuecomment-373895998, or mute the thread https://github.com/notifications/unsubscribe-auth/AA37jslY4Q6AkHt9q4oRbgpvWaif5HNeks5tfJ_ogaJpZM4KlMs4 .

-- Brandon Barker brandon.barker@gmail.com

[fdietze]

I found some relevant papers which could help building a good alternative to vdom: https://github.com/raquo/Laminar/issues/14