A lightweight reactive document library.
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

198 lines
10 KiB

1 year ago
1 year ago
1 year ago
1 year ago
5 months ago
  1. # Lwd: a "lightweight document" library
  2. `Lwd` is a library that lets you build values that changes over time. It is a simple form of incremental computation, in the like of [Incremental](https://github.com/janestreet/incremental) and [React](https://github.com/dbuenzli/react).
  3. [TOC]
  4. ## Documents?
  5. `Lwd` shines when constructing a single value, which we call a document, by aggregating many sub-documents. These sub-documents might be updated independently and we want to keep a consistent view on the aggregated document: when we observe it, it should be the aggregate of the sub-documents in their current version.
  6. We will illustrate that with some examples. First we need to define the syntax for the final document:
  7. ```ocaml
  8. type hypertext =
  9. | Text of string
  10. | Link of (unit -> unit) * hypertext
  11. | List of hypertext list
  12. ```
  13. A value of type `hypertext` will be interpreted by a backend. The interpretation is roughly as follows:
  14. - `Text str` simply displays the string `str` to the user (for instance on a terminal)
  15. - `Link (callback, hypertext')` displays the document `hypertext'`.
  16. If the backend determines that the user is interacting with the content in this sub-document, `callback` is called.
  17. - `List (doc1 :: doc2 :: ...)` displays `doc1` followed by `doc2` followed by `...`.
  18. To keep the example simple, we didn't say anything about styling nor how interactions are determined. For instance, the backend could display plain text in a default color, switch to another color for text below a `Link _` constructor, and keep track of _focus_ by cycling between links when `<TAB>` is pressed and choosing a different color for the focused link.
  19. A navigation menu could look like:
  20. ```ocaml
  21. let newline = Text "\n" in
  22. List [
  23. Text "Welcome to my cafe"; newline;
  24. Link (display_drink, Text "See drink options"); newline;
  25. Link (display_food, Text "See food options"); newline;
  26. ]
  27. ```
  28. We don't yet know how to implement the `display_drink` and `display_food` function but we have enough infrastructure to receive user intent. To complete the task, we will look at the idea of implementing a function that "changes its mind": it returned a value but, because of some circumstances, decide that another value should have been returned.
  29. ### Counting clicks
  30. Let's imagine we want to make a button that counts the number of times it has been clicked: at first it displays 0, when triggered the 0 switch to 1, etc.
  31. ```ocaml
  32. let counter = ref 0
  33. let on_click () = counter := !counter + 1
  34. let button clicks =
  35. Link (on_click, Text ("Clicked " ^ string_of_int clicks ^ " times"))
  36. let document = button !counter
  37. ```
  38. We now have a counter that is incremented when the button is clicked. However the content of the button is not updated.
  39. This is where `Lwd` comes into play: the `Lwd.var` type behaves almost like a reference but also tracks data dependencies. Let's update the example:
  40. ```ocaml
  41. let counter = Lwd.var 0
  42. let on_click () = Lwd.set counter (Lwd.peek counter + 1)
  43. let button clicks =
  44. Link (on_click, Text ("Clicked " ^ string_of_int clicks ^ " times"))
  45. let document = Lwd.map button (Lwd.get counter)
  46. ```
  47. We make use of the following `Lwd` functions:
  48. ```ocaml
  49. (* Variable manipulation function *)
  50. val Lwd.var : 'a -> 'a Lwd.var
  51. val Lwd.set : 'a Lwd.var -> 'a -> unit
  52. val Lwd.peek : 'a Lwd.var -> 'a
  53. ```
  54. `var`, `set` and `peek` behave like `ref`, `:=` and `!`. They allocate a mutable cell, change its value and read the value at current time.
  55. ```ocaml
  56. val Lwd.get : 'a Lwd.var -> 'a Lwd.t
  57. ```
  58. `Lwd.get` reads a mutable cell, but while `Lwd.peek` returns the value immediately, `Lwd.get` lets you access the value wrapped in the `Lwd.t` type.
  59. `Lwd` lets you build graph of computations with mutable inputs. The inputs or sources of the graph are made of `Lwd.var` while the inner nodes are built using combinators.
  60. Here `Lwd.map : ('a -> 'b) -> 'a Lwd.t -> 'b Lwd.t` apply a transformation to a varying value. That value might depend on arbitrary inputs, and if one of these input changes, the transformation will be recomputed too.
  61. When the `Link` is triggered, the counter is incremented. Because `document` depends on the value of the counter it is invalidated.
  62. ### Building computation graph
  63. `Lwd.t` implements a few abstractions that should be familiar to seasoned functional programmers:
  64. - it is a _functor_. With `Lwd.map : ('a -> 'b) -> 'a Lwd.t -> 'b Lwd.t` you can transform values and chain the transformations
  65. - it is an _applicative functor_. With `Lwd.map2 : ('a -> 'b -> 'c) -> 'a Lwd.t -> 'b Lwd.t > 'c Lwd.t` you can connect two different chains (making the computation tree shaped, actually with sharing it will form a DAG)
  66. - and, although this should in general be avoided, a _monad_. With `Lwd.join : 'a Lwd.t Lwd.t -> 'a Lwd.t` you can have a first pipeline that computes another pipeline and inject the inner one.
  67. ### Consuming computation graph
  68. So far we described how to build values of type `a Lwd.t` but we don't have a way to get access to those `a` outside of the _Lwd_ graph.
  69. That's what `Lwd.root`s are for:
  70. ```ocaml
  71. type 'a Lwd.root
  72. val Lwd.observe : ?on_invalidate:('a -> unit) -> 'a t -> 'a root
  73. val Lwd.set_on_invalidate : 'a root -> ('a -> unit) -> unit
  74. val Lwd.sample : 'a root -> 'a
  75. val Lwd.is_damaged : 'a root -> bool
  76. val Lwd.release : 'a root -> unit
  77. ```
  78. When you are interested in accessing the content of an `a Lwd.t` value, you create a root by `observe`-ing it.
  79. `Lwd.sample` lets you access the value at the current time.
  80. After calling `Lwd.sample`, the `on_invalidate` callback might be invoked if the value is invalidated: some input changed, the value you sampled is out of date.
  81. When you are done with the `root` and are no longer interested in observing the value, you should call `release`. This call to `release` is very important: the `root` maintain the whole graph alive, so forgetting to `release` leads to memory leaks. After releasing, the on_invalidate callback will not be invoked.
  82. A root can be in three possible states:
  83. - released
  84. - damaged
  85. - sampled
  86. When created, the root is in the `released` state: it does not maintain the graph alive.
  87. Calling `sample` switches the root from the `released` to the `sampled` state.
  88. ```mermaid
  89. graph TD;
  90. R[Released]
  91. S[Sampled]
  92. D[Damaged]
  93. s{{call to sample}}
  94. i{{graph input change, call <tt>on_invalidate</tt>}}
  95. r{{call to release}}
  96. R-->s
  97. s-->S
  98. D-->s
  99. S-->i
  100. i-->D
  101. S-->r
  102. D-->r
  103. r-->R
  104. ```
  105. ## Relation to HTML, DOM, and reactive UI libraries
  106. **Syntax, data description and HTML.** To introduce our first example, we had to build a syntax using the simple `hypertext` algebraic data type. This type serves as an interface between the application and the interactive system: values of this type are produced by the front-end, like our example codes, and consumed by a back-end.
  107. In the case of a web browser, the surface syntax is `HTML` which is much richer and more expressive than `hypertext` but ultimately is just data: a static description of some pieces of information.
  108. **Adding programming languages.** Because static description are too limited for modern websites, Web browsers support the Javascript programming language. Pieces of javascript code can be put in the middle of the HTML syntax.
  109. Similarly the `unit -> unit` parameter of the `Link` constructor allows to inject arbitrary OCaml code in the middle of an `hypertext` document.
  110. **Making things interactive.** Being able to execute arbitrary piece of codes is not enough to make a document interactive: to make things dynamic the code needs to change the contents of the document in return.
  111. Ultimately, interaction comes from this mutual dependency between document and code:
  112. - the document contains codes that are executed in certain circumstances (determined by the meaning of elements of the document).
  113. - when executed, a code can change the document, producing new elements associated to new codes.
  114. - this updated document can then execute new pieces of code, that may update the document, and so on...
  115. **The DOM.** Web browser's solution to allowing document update is the Document Object Model abstraction. The idea is to derive mutable data structures from the syntactic specification: each syntactic construction has a corresponding "DOM class" that can store the same information in mutable fields. Applied to our hypertext example:
  116. ```ocaml
  117. type hypertext_dom =
  118. | Text of { mutable text: string }
  119. | Link of { mutable callback: (unit -> unit)
  120. ; mutable child: hypertext_dom }
  121. | List of { mutable children: hypertext_dom list }
  122. ```
  123. While this might be a natural derivation in imperative languages, it proved difficult and error-prone to manipulate. Thousands of Javascript libraries were proposed to ease DOM manipulation.
  124. Some successful ones drew inspiration from functional programming, in the sense that they discouraged side-effects, producing new documents rather than modifying existing ones.
  125. _Lwd_ rethinks this scaffolding: rather than starting from a static description, deriving mutable data structures to bring dynamism, and then restricting the mutations to make it manageable, we propose to keep the syntax as it is, lift the document in an `Lwd.t` computation graph and use variables nodes to express parts that can changes.
  126. **Reactive UI.** It is difficult to make a fair comparison with these libraries as the term is loosely defined and there many competing approaches. Furthermore Lwd can be presented as an alternative to the DOM so it is effective at a lower-level than what common reactive libraries target.
  127. That being said, we will try to address the following questions:
  128. - can reactive libraries, to a reasonable extent, be reimplemented on top of _Lwd_ rather than _DOM_?
  129. - can _Lwd_ be conveniently used without such layer?
  130. The first question can be answered positively with a naive encoding: put `Lwd.var` everywhere, essentially keeping enough "degrees of freedom" to change things as needed later. No static structure is enforced this way.
  131. To answer the second question, it is interesting to observe that there is no concept of "diffing" here. _Lwd_ does not try to see if things have changed in order to update them. Rather, if an input change, the whole branch that depends on it is recomputed.
  132. While this might lead to inefficient recomputations. ...TODO...