Help us understand the problem. What are the problem?

posted at

updated at

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

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:

Bildschirmfoto 2021-05-02 um 01.59.03.png

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

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Sign upLogin
Help us understand the problem. What are the problem?