Dogelog Runtime, Prolog to the Moon

We got recently interested in the JIT-ing capabilities of JavaScript. So we set sail to write a take on the Albuferia Prolog Interpreter. The result is a first cross compiler, that compiles Prolog with Cut into JavaScript arrays that can then be executed by the Dogelog runtime.

The point of departure was the following paper:

A portable Prolog compiler
Conference: Logic Programming Workshop - Albufeira, Portugal
William Clocksin - January 1983
https://www.researchgate.net/publication/273888197

The above compiler suggests an instruction set that is based on a register window. The instruction set is flexible, in that it can build fresh Prolog terms and/or perform unification. During unification it can avoid building unnecessary fresh Prolog terms.

The compiler goes also into length to compile tail recursion in a smart way. We didn't implement this part. But we provide a already the cut and a primitive trail garbage collection. Built-ins on the other hand are not yet provided.

Cross Compiling

The compiler is currently a cross compiler. One needs to use another Prolog system and run the Prolog program through it. In the future we might let the browser do that, but currently there are the following files that perform the cross compilation:

• Term Compiler term:
  Here we are close to the Albufeira compiler in that we also
  use the instructions var(N), functor(F,N), atom(C) and the
  characteristic pop instruction. Since we do not have memory
  pointers in Java Script we use an index into an array to create terms.

• Clause Compiler solve2:
  Here we divert from the Albufeira compiler in that we chop
  up the instruction stream in a Prolog clause head and body part,
  which sit itself in a list. This will later simplify the
  Dogelog runtime.

• File Compiler dogelog:
  This is a very rudimentary utility that can produce JavaScript
  array statements that can then be embedded in a HTML page. The
  utility makes use of Jekejeke Prolog strings which are coded
  as '$STR'(atom). Other Prolog systems might need something else.

From within Jekejeke Prolog the cross compiler can be invoked as follows:

?- set_prolog_flag(double_quotes, string).

?- doge('examples.pl', 'examples.js').

Dogelog Runtime

The Dogelog runtime needs a full fledged unification. Although the Albufeira instruction stream can build and unify Prolog terms, it falls back to a unification routine in case two instantiated variables meet. The Dogelog runtime consists of:

• Term Handling unify2.js:
  Can perform unification. During unification variables that get
  instantiated get recorded on the trail. The JavaScript file also
  provides routines to mark and sweep the trail, which is later
  used in garbage collection.

• Clause Handling executor2.js:
  Can solve Prolog goals. We use a solver that works on goal list.
  Clauses heads and bodies are difference lists, so that the modify
  the goal list like in resolution. When the trail gets too large
  garbage collection is performed.

When implementing the solver we replicated the Jekejeke Prolog engine with its two modes "call" and "redo". This is a loop that fetches goals from the goal list during when in "call" mode and jumps to choice points when in "redo" mode.

TauProlog Comparison

We were currious how Dogelog compares to TauProlog. So we were running Peano factorials which stretches the tail recursion and garbage collection of any Prolog system. The test files were:

• TauProlog Benchmark:
  We made ourselfs comfortable with the TauProlog API. They required us to
  code a lot of call backs. We realized a logic that did try to execute
  Peano factorials up to 10. But somehow TauProlog gave silently up at 7.

• Dogelog GC Demo:
  The Dogelog API doesn't use inverted programming. The Prolog interpreter
  is viewed as an iterator that can be asked for a next solution. The
  Dogelog runtime is able to reach Prolog factorial 10 in a Chrome browser.

We take performance figures of this test as a judgement whether the Dogelog runtime is a total disaster or not. So we did also some measurement via JavaScript Date.now(). It turns out that the Dogelog runtime fares quite well compared to TauProlog:

Future Outlook

We are mostly interested in the JIT-ing capabilities of JavaScript. So we will need a future version of Dogelog that compiles closer to the metal, either JavaScript code or even maybe Webassembly code. For this project we will have to look again at the many ideas from the Albufeira instruction set.

Dogelog Live Demos
http://www.xlog.ch/izytab/doclet/en/docs/18_live/package.jsp