Blog of Raivo Laanemets

Some time ago I experimented with a Prolog Virtual DOM implementation to create and manipulate the webpage DOM inside a web browser. I wanted to see how suitable would Prolog terms be for representing the page elements. My second goal was to see if SWI-Prolog can be easily ported to run on WebAssembly. SWI-Prolog is the most popular Open Source Prolog implementation.

Prolog for browser

There are many ways to run Prolog in browser. There are numerous implementations for JavaScript, each having various level of support for common Prolog features. However, I wanted something with full support of features that one can expect from Prolog, including modules.

WebAssembly is a relatively new browser technology that makes it possible to run standardised bytecode on browsers. Its design started in 2015 and the core spec was released in early 2018. WebAssembly is comparable to Java applets, an ancient technology once popular 20 years ago. However, compared to Java applets, WebAssembly bytecode is much more lower-level, suitable for efficient compilation from C and C++. WebAssembly is not tied to any particular high-level language. The sandbox is much stricter and a lot more secure than Java applets ever were. WebAssembly (a core version) is supported by all major browsers today and the implementation is not tied to a single company as it was with Java applets.

It would be nice to have a Prolog to WebAssembly compiler but instead of building another Prolog implementation (someone else can do it), I decided to port SWI-Prolog to WebAssembly. SWI-Prolog itself is written in the C language. Once we can run SWI-Prolog on WebAssembly, we have a high-quality feature-complete Prolog in browsers.

SWI-Prolog on WebAssembly

WebAssembly is a bare sandbox, a raw blob of memory. It has no concept of OS. Lots of C code, including SWI-Prolog, depends on the C standard library to read files and interact with out-of-process resources. Emscripten is a compiler that provides all this. It emulates the common OS interfaces and provides some glue code for things like the virtual file system.

The biggest roadblock in porting SWI-Prolog to WebAssembly turned out to be a file system issue. SWI-Prolog compiles a set of predicates into a so-called boot file. The file needs to be created during the build process. We had to modify the build process to run the WebAssembly build of SWI through Node.js (another WebAssembly implementation besides modern browsers) to generate the boot file. The porting process is more-less described here.

Boot file issue aside, the porting process went quite smooth. Not many C language related code changes had to be done. Jan Wielemaker, the main SWI-Prolog author, helped me out with those changes.

Virtual DOM

WebAssembly lacks a DOM interface. It cannot currently access DOM directly. It can call JavaScript but can only pass primitive number types to it. WebAssembly DOM interface will likely be specified and implemented in the future. For now, some sort of workaround has to be provided.

We can fake the DOM tree, manipulate with this fake tree and then somehow magically transfer the manipulation effects to the actual DOM tree. This approach called Virtual DOM (VDOM). With VDOM, you construct a tree that corresponds to the actual tree of DOM elements, except that the VDOM tree does not contain real DOM elements. It only needs to contain enough information to construct the real DOM elements.

In the case of Prolog, the VDOM tree would simply be a specifically shaped Prolog term. Here is an example of a div element containing an unordered list:

div([], [
  ul([className=my_list], [
    li([], ['Item1'])
    li([], ['Item2'])
  ])
])

VDOM diff/patch

To transfer the effect of VDOM manipulations onto the real DOM, we take the snapshot of our VDOM tree before each manipulation and compare it to the VDOM tree after the manipulation. This gives us the VDOM tree difference. We can serialize this difference into a data structure that can be exchanged between WebAssembly and the page JavaScript. In the page JavaScript, we use a small piece of code to deserialize the difference and apply it to the actual DOM tree.

Declarative VDOM

We do not need to use low-level VDOM manipulations, like adding a child node here, or manually changing an attribute there. VDOM can be produced declaratively from the application state and there is a clever way to avoid re-rendering the whole VDOM tree at each modification. This uses so-called components, parts of a VDOM tree that only depend on the input data. The component's VDOM tree can be skipped in the difference calculation algorithm altogether if the components input data has not been modified. This approach is similar to what is used in React. React is a JavaScript framework that popularized VDOM.

Example of a component:

:- vdom_component_register(hello, render_hello).

render_hello(Name, _, VDom):-
  VDom = div([], [
    'Hello ', Name
  ]).

and its usage in elsewhere of the application:

div([], [
  hello([data='World'], [])
])

DOM events

DOM events are implemented by using a piece of JavaScript glue code and event delegation. The event handlers are added to the document.body element. Whenever an event is caught, a Prolog-side predicate is called. The target element's id attribute is passed to the predicate. The predicate will modify the application state, render a new VDOM tree and calculate the difference from the previous VDOM tree. This difference is automatically applied by the JavaScript-side event handling code.

Example of a click event handler:

event_click(Id, Diff, true):-
  atom_concat('task-', _, Id), !,
  update_state(toggle_task_done(Id)),
  diff(Diff).

WebAssembly bridge

Communication between JavaScript and SWI-Prolog is initiated from the JavaScript side. SWI-Prolog has the Foreign Language Interface (FLI) that is meant for embedding. FLI assumes that C or C++ is used for calling it. We use the cwrap interface, provided by Emscripten, to call the FLI functions.

Demo

I created a small ToDo application. The app can be viewed from here. The difference terms can be seen using by opening the browser's developer console. The demo should work with the latest versions of all major browsers (Chrome, Firefox, Edge and Safari).

Thoughts

Prolog terms are a good fit for representing DOM elements. This representation was borrowed from the SWI-Prolog server-side HTML support package. The bigger issue is embedding loop-like constructs or general expressions. Some time ago I built a Prolog server-side templating language and I had to come up with my own expression language in there.

The biggest issue with WebAssembly is complexity. Here we have a 4-level language interface:

JavaScript <> WebAssembly <> C <> Prolog

Virtual DOM itself is relatively opaque to debugging. The diffing algorithm does 3 things in a single pass:

• Calculate diff;
• Produce full VDOM tree (as components are either rendered or reused);
• Render components.

The algorithm is not very easy to follow step-by-step. This is made harder by the fact that the diff result is batched up and ran through the JavaScript side glue code that actually creates or modified the real DOM based on it.

There is also a practical issue of having to download a Prolog runtime. The compiled core is 1.3MB. The virtual file system file (VFS) containing the boot file and the standard library is 2MB. For a simple page this is quite a lot. Runtime and the VFS file can be effectively cached so that subsequent page visits are fast. Prepared WebAssembly bytecode can be cached by the browser (although Emscripten does not support it at the moment), making repeated visits faster again.

I'm quite exited that web browsers have come so far and finally provide opportunity (with a relative ease and performance) to run different languages without transpilation to JavaScript. I'm pretty amazed that my VDOM experiment worked despite all the complexity.

More information

• SWI-Prolog WebAssembly version build instructions.
• Virtual DOM and demo app code.