Apply staged meta-programming to Virtual DOM construction

[dmjio]

Staged meta-programming allows for the creation of domain specific optimization. This process can occur during type-checking where a partial evaluation will run on a lambda calculus expression (or typed template Haskell splices) creating a reduced expression that is more efficient at runtime. This has the potential to remove intermediate allocations (performing fusion / deforestation, etc.) that would otherwise need to occur at runtime.

We believe this technique could be applied to miso's View DSL to great effect.

Right now the process for Virtual DOM generation looks like:

-- miso's DSL
data View model action where
  VText :: MisoString -> View model action
  VNode :: Tag -> Namespace -> [Attribute action] -> [ View model action ] -> View model action

-- DSL converted into JS object, held in `JSVal`
newtype VTree = VTree JSVal -- Ptr () to JS value.

-- Functions used to compile the DSL into `JSVal`, 
-- subject to performance improvement via staging.

view :: model -> View model action 
-- ^ user-defined templating function

buildVTree :: View model action -> IO VTree 
-- ^ for client Virtual DOM construction from miso View DSL

renderVTree :: View model action -> ByteString 
-- ^ for server HTML serialization

Above the user's view function (which takes a model) gets applied to buildVTree for creation of the Virtual DOM in JavaScript (in IO). Since user application templates can be very large, staging could potentially have a very dramatic impact on runtime performance (and a potentially negative effect on compile time performance).

If we had a staged buildVTree variant we believe this could have the effect of fusing away many View model action allocations that impact performance. The resulting optimized function should look equivalent to buildVTree :: model -> IO VTree, where most of the templates have been compiled into FFI calls to construct a JS object that will be evaluated at runtime.

The same process could be applied to renderVTree (HTML generation) as well.

Below I've included a simple example of a staged variant of renderVTree, for staging HTML generation from the View m a DSL.

-- Main.hs
import Lib

main :: IO ()
main = BL8.putStrLn $$(stagedView () view)

-- Lib.hs
stagedView :: model -> (model -> View) -> Code Q ByteString
stagedView model view = renderTree (view model)

view :: model -> View
view x = div_ [ id_ "foo" ] [ text "bar" ]
  where
    div_ = VNode "div"
    id_ x = ("id", x)
    text = VText

renderTree :: View -> Code Q ByteString
renderTree (VText "") = [|| " " ||]
renderTree (VText s) = [|| BL8.pack s ||]
renderTree (VNode tag attrs children) =
  [||
    BL8.concat
    [ "<"
    , BL8.pack tag
    , renderAttrs attrs
    , ">"
    , $$(renderTreeChildren children)
    , "</"
    , BL8.pack tag
    , ">"
    ]
  ||]

renderTreeChildren :: [View] -> Code Q ByteString
renderTreeChildren = \case
  [] -> [|| "" ||]
  (x : xs) -> [|| $$(renderTree x) <> $$(renderTreeChildren xs) ||]

We should apply the same technique above to virtual DOM construction, evaluating three things:

• Ergonomics for end user (ideally users wouldn't know this process is occurring, the external API of the DSL should remain unchanged as well)

• Performance, specifically applied to HTML generation; show benchmarks w/ and w/o staging. For virtual DOM construction, test the FPS and heap allocations on various SVG-heavy games (like the tetris example) and the classic virtual DOM benchmarks w/ both staged and unstaged variants.

• Stage restrictions, this approach might not be feasible to use in a web framework library because it requires users to define their view function code alongside the staged, internally-defined, not publicly accessible, buildVTree function. This is still being evaluated.

For more information see the Staging with class paper from @xnning, and MetaOCaml from Oleg Kiselyov.

[dmjio]

To follow up on this, in order to fuse away b in (a -> b) -> (b -> c) -> a -> c we need to stage functions a -> Code Q b, and b -> Code Q c to get an efficient a -> c

This means both the construction and deconstruction of b is staged (our View m a in this case). This means user's will need to participate (hopefully unknowingly) in building staged templates.

We obviously can't change the view API, but we could potentially swap out the View m a implementation for

newtype View m a = View (Code Q (ViewCore m a)) 

So users would be constructing staged templates w/o realizing it when using div_, p_, etc.