CHR.js - A CHR Transpiler for JavaScript

June 22, 2015

Falco Nogatz

Abstract

CHR sometimes gets called “lingua franca of computer science” (Frühwirth; 2009), due to its unification of several rule-based approaches. Currently the prevalence of CHR is still too small to claim this title. By embedding CHR into JavaScript - the dominating programming language of the web that recently got adopted for server-side frameworks too -, we open this declarative approach to a broad range of developers and new use cases.

In this project report we present a first prototype implementation of a CHR-to-JavaScript transpiler called CHR.js. Our contributions are:

CHR.js: the first integration of CHR with JavaScript,
CHR.js-website: a web application that allows the compilation and execution of CHR in JavaScript, available at chrjs.net.

Introduction

Constraint Handling Rules (CHR) is a declarative programming language extension, that “has become a major declarative specification and implementation language for constraint-based algorithms and applications” (Frühwirth, Raiser; 2009) in the last 20 years. Although there are implementations for popular host languages like Java and Prolog, the distribution of CHR is currently restricted almost entirely to the research community.

One of the reasons that CHR is not widely used in a non-academic environment is the lack of an easy to use programming and software environment: Due to its orientation as a language extension it is always necessary to install its host language first - most common are Prolog, Java and C. By implementing a CHR constraint solver in JavaScript it is possible to use CHR constraints natively in the browser and in server-based JavaScript runtime environments like node.js.

Context of this Work

The aim of this project was to create a prototype implementation of a CHR transpiler for JavaScript, executable directly in the browser. It was realized as individual project as part of the Masters programme in Computer Science at the University of Ulm. It has been supervised by Prof. Dr. Thom Frühwirth and M.Sc. Daniel Gall of the Institute of Software Engineering and Compiler Construction.

Preliminaries

Similar to existing CHR(Prolog), CHR(Java) and CHR(C) systems we built a CHR(JavaScript) application called CHR.js. Before we examine the requirements and implementation details, we want to present existing approaches to implement logic programming languages in general and CHR in particular in imperative host languages.

Existing Tools

CHR can be used in a great many programming languages of different programming paradigms, including Prolog (Schrijvers, Demoen; 2004), Java (Van Weert, Schrijvers, Demoen; 2005), C (Wuille, Schrijvers, Demoen; 2007) and Haskell (Lam, Sulzmann; 2007). In general the given CHR rules are compiled to its host language. Although there a real interpreters like ToyCHR, the most common approach is to build a transpiler.

There are already several Prolog implementations in JavaScript, for instance Yield Prolog and JScriptLog, but there is currently no way to use CHR in web applications. Pengines (project homepage: pengines.swi-prolog.org), a recent approach to use Prolog on websites, communicates over HTTP with a server running a SWI-Prolog instance and would therefore be a possibility to call CHR constraints in the browser too. Nevertheless it does not solve the original problem as there is still a server necessary that accepts these Prolog remote procedure calls. Therefore Pengines is very similar to WebCHR, that also dispatches calls on CHR constraints via HTTP to a backend server, in this particular case running Sicstus Prolog 4.

J. F. Morales et al. presented a lightweight compiler of (constraint) logic programming languages, (C)LP, to JavaScript in 2012. It does not support CHR and is based on a special module system which makes it necessary to implement (C)LP rules in a JavaScript dialect. In contrast to that our aim was to embed CHR rules in existing JavaScript source code and compile this constraint solver to standard JavaScript.

CHR in Imperative Programming Languages

Although the most popular host language for CHR, Prolog, is a representative of the declarative programming paradigm, there has been a lot of research about implementing CHR in imperative programming environments recently. As a consequence, CHR extensions for C and Java evolved, as presented in the previous subsection.

Peter Van Weert explained some advantages of adopting CHR in imperative host languages in his PhD thesis as follows:

Moreover, imperative host languages are better suited for efficient evaluation of rule-based programs. The indexing data structures and complex nested loops required can be implemented more effectively in an imperative language.

The basic compilation scheme presented in this PhD thesis and Peter Van Weert et al., 2008 has been the basis for CHR.js. Besides that the compilation scheme presented by Gregory J. Duck in 2005 was inspiration for the parsing and head and guard normalisation process.

Implementation Goals

The aim of CHR.js was to implement a CHR constraint solver in JavaScript. It allows to run Constraint Handling Rules in a web environment as well as in served-based JavaScript runtime environments like node.js.

Referring to the implementation goals specified for K.U.Leuven JCHR and CCHR, we have set the following requirements for our CHR.js prototype implementation:

CHR.js closely resembles other CHR systems

The syntax used by the CHR(JavaScript) application should feel familiar for CHR- as well as JavaScript-experienced developers. One should be able to use regular JavaScript variables and expressions. On the other hand it should be possible to easily adapt existing CHR source code, written for example for CHR(Prolog) systems, by only changing syntactic elements specific for the host language.

The implementation should follow the refined operational semantics of CHR. Due to its prototype character, efficiency is currently not a requirement.
CHR.js can be used both in browser and server environments

Transpiling programming languages into JavaScript is not new at all. There are currently more than 350 tools that compile to JavaScript. To also work in the browser it is necessary to focus on a small file size of the compiler and its generated JavaScript source code. The compressed source code of the transpiler should not exceed several hundred kilobyte.

The CHR.js Language

The syntax of CHR.js, i.e. JavaScript with embedded CHR, is a good compromise of both worlds. It uses the well-known Prolog CHR syntax to represent the CHR rules. Instead of predicates we use function-like representations for the constraints, that means that a constraint call looks like a function call in JavaScript. While Prolog supports nullary predicates by simply call pred, we modellize the call to nullary constraints in CHR.js as function calls with zero arguments: pred(); only within CHR rules the shorter notation pred is supported.

The CHR rules follow closely the Prolog CHR syntax with the following notable exceptions:

A rule ends in a semi-colon. Although in JavaScript it is not necessary to end expressions and declarations by a semi-colon, it is common practice and helps avoiding edge-cases in the parsing process.
Variables are always locally scoped for the current particular rule.
There is no kind of pattern matching (so called destructuring in JavaScript) in the rule’s head.
There is currently no support for logical variables, that means only ground terms are allowed.

In this prototype implementation we omit the declaration of constraints. The consequential disadvantages of this simplification of design are discussed later in the summary. The most notable consequence is that it is not possible to call user-defined JavaScript functions in the rule’s body.

Example Program

We introduce the CHR.js language by a small example program for the bottom-up computation of the Fibonacci numbers upto a given maximum value, as it has been used to present the syntax of CCHR in Pieter Wuille et al.; 2007 too:

begin  @ upto(A) ==> fib(0,1), fib(1,1);
calc   @ upto(Max), fib(N2,M2) \ fib(N1,M1) <=> 
           N2 === N1+1, N2 < Max | fib(N2+1, M1+M2);

We will assume familiarity with both CHR and JavaScript at this point, and therefore only want to refer to the used built-in JavaScript comparison === in the rule calc.

More examples can be found at the interactive online demo and in the CHR.js repository.

Architecture

In this section we introduce the components which form the CHR.js module. The architecture of the CHR.js-website repository, that provides an online compiler and in-browser CHR playground, is out of the scope of this project report.

The CHR.js module, that is used to transpile and execute JavaScript with embedded CHR rules, consists of the following components:

The Parser, that performs a lexical and syntactical analysis of the source code to return a semantic representation.
The Compiler, that takes this representation and generates the JavaScript code.
The Runtime, which provides data structures needed for the execution of the compiled source code, in particular handling the constraint store and propagation history.

With the help of these three components we created a module that can be used in node.js or as command line tool. To support the usage as a browser script we assemble thes components into a single JavaScript file that can be used in existing websites.

In the following subsections we elaborate the separate components in detail.

Parser

Given a JavaScript source code with embedded CHR rules like in the previous example, we have to parse its components first. Our parser is based on PEG.js, a parser generator for JavaScript that is based on the parsing expression grammar (PEG) formalism. We extended the existing PEG for the JavaScript standard by grammars for CHR. Without getting into detail of the PEG syntax, we present an extract of the added rules:

CHRRule
  = PropagationRule
  / SimplificationRule
  / SimpagationRule

PropagationRule
  = RuleName? CHRConstraints "==>" Guard? Body

SimplificationRule
  = RuleName? CHRConstraints "<=>" Guard? Body

SimpagationRule
  = RuleName? CHRConstraints "\" CHRConstraints "<=>" Guard? Body

RuleName
  = Identifier "@"

Guard
  = BuiltInConstraints "|"

BuiltInConstraints
  = BuiltInConstraint "," BuiltInConstraints
  / BuiltInConstraint

BuiltInConstraint
  = AssignmentExpression       /* JavaScript expression    */

Body
  = Constraint "," Body
  / Constraint

Constraint
  = CHRConstraint
  / AssignmentExpression       /* JavaScript expression    */
  / FunctionExpression         /* JavaScript function call */

CHRConstraint
  = ConstraintName "(" Parameters ")"
  / ConstraintName

For the sake of simplicity we omitted some rules, the whitespace-handling and transformation steps in the presented Parsing Expression Grammar. The PEG syntax is similar to EBNF or Regular Expressions: / separates alternatives, ? indicates optional terms. The complete grammar can be found in the CHR.js repository.

In the previous listing we presented only the parsing grammar. PEG.js allows us to specify a transformation process for every single rule in a code block { ... } to create some kind of semantic representation. For the PropagationRule the exact grammar with transformation code looks like this:

PropagationRule
  = name:RuleName? headConstraints:CHRConstraints
      "==>" guard:Guard? bodyConstraints:Body
    {
      var desc = {
        type: 'PropagationRule',
        kept: headConstraints,
        removed: [],
        body: bodyConstraints,
        guard: guard || []
      };
      if (name) {
        desc.name = name.name;
      }
      desc.constraints = getConstraints(desc);

      desc = headNormalForm(desc);
      desc = addProperties(desc);

      return desc;
    }

In this way we create JavaScript objects that contain all the information about the rules, in particular the rule name, kept and removed constraints and rule body. The headNormalForm() function applies the head and guard normalisation step as presented in section 4.2.2 of Gregory Duck’s PhD thesis, that means:

variables occuring more than once in the rule’s head are renamed,
terminals in constraints of the rule’s head are replaced by fresh variables and appropriate guards are added.

Given the above Parsing Expression Grammar, PEG.js provides a function that can parse JavaScript source code with embedded CHR and return its semantic representation as JavaScript object.

Compiler

This object is passed to the compiler which creates the corresponding JavaScript constraint solver. The compilation scheme is based on Van Weert et al.; 2008 without any optimizations.

For every constraint in we create three kinds of rules:

A Caller function, that is first called if a constraint is manually added or called in the body of a rule. For the fib/2 constraint of the Fibonacci example, this is a generalized CHR.fib() JavaScript function that would be used for all upto constraints regardless of its arity:

CHR.prototype.fib = function fib() {
  var arity = arguments.length
  var callConstraint = "_fib_"+arity+"_activate"
  // for example: "_fib_2_activate"
    
  // Create new Constraint and add it to the Store
  var constraint = new Runtime.Constraint("fib", arity, arguments)
  this.Store.add(constraint)

  // Execute the (arity-depending) activator function
  this[callConstraint](constraint)
}

An Activator function for every (name,arity)-pair. In case of the Fibonacci example we only have two different Activators, namely CHR._upto_1_activate() and CHR._fib_2_activate(). The activators get the recently created constraint and try to execute the application of every CHR rule that contain this (name,arity)-pair in its head. Therefore the occurences of these pairs are passed through from top to bottom (in the order of the CHR rules) and from right to left (in the order of a single CHR rule). This sequence is chosen in Van Weert et al.; 2008 to ensure the refined operational semantic which states that the removed constraints of a simpagation rule are tried for application first.

Therefore the fib/2 constraints in the calc-rule are numbered in that way, that fib(N1,M1) is the first and fib(N2,M2) the second occurence. The Activator tries to execute the application in this order, that means for the fib/2 constraint the Activator function simply looks like this:
```
CHR.prototype._fib_2_activate = function (constraint) {
  this._fib_2_occurence_1(constraint)
  this._fib_2_occurence_2(constraint)
}
```
An Occurence function for every occurence of a constraint in a rule’s head. This function performs a lookup in the constraint store to find all appropriate constraints that are also in the rule’s head and therefore needed for the rule’s application. Depending on the rule’s body and type, new constraints are added, others removed or kept. This Occurence function also performs a check in the propagation history to prevent the repeatedly execution of a rule.

The generated Occurence function CHR._fib_2_occurence_1 for the first occurence of the fib/2 constraint can be found in the Appendix.

Runtime

In the previous code examples we already used the three Runtime components that are necessary for all CHR.js applications:

Runtime.Constraint, a JavaScript object that represents a single instantiated constraint.

// Create a fib(1,0) constraint
var c = new Runtime.Constraint('fib',2,[1,0])

// Properties
c.name                // 'fib'
c.arity               // 2
c.args                // [1,0]
c.id                  // is unique
c.alive               // true or false

// Methods
c.toString()          // 'fib(1,0)'
                      //   used for debug output

Runtime.Store, the Constraint Store that manages the addition and removal of constraints.

// Create a new instance
var s = new Runtime.Store()

// Methods
s.add(c)              // add a constraint
s.kill(c)             // remove a constraint
s.alive(c)            // check if constraint
                      //   is still alive
s.lookup(name,arity)  // search for matching
                      //   constraint

// Events emitted
s.on('add', function(constraint) {})
                      // fired on constraint
                      //   addition

s.on('remove', function(constraint) {})
                      // similar on removal

Runtime.History, the Propagation History to save already executed combinations of constraint identifiers.

// Create a new instance
var h = new Runtime.History()

// Methods
h.add(rule, ids)      // add an application
                      //   to the history
h.notIn(rule, ids)    // check for record

Interface

Code Generation

The CHR.js transpiler can be used in different ways. Either as a command line tool or programmatically as node.js module or browser script.

The easiest way to use the CHR.js transpiler is the executable chrjs provided by its npm package:

$ npm install -g chr
$ chrjs /path/to/fib.chr > transpiled.js

Additional options can be found in the CHR.js repository. There is also an example how to use the transpiler programmatically in node.js or the browser.

CHR.js Usage

Once the CHR code is transpiled as mentioned before, we can bind the generated code to a variable CHR and access the constraints by calling for example CHR.upto(4). In the following we demonstrate the usage of the generated JavaScript constraint solver with the help of the Fibonacci example. For a more verbose output we use the supplied chr/console-module, which is based on tconsole.

$ node
> var CHR = require('./transpiled.js');  // load the generated source
> var konsole = require('chr/console');  // load the graphical console
> konsole(CHR.Store);                    // print the current store
┌────────────┐
│ Constraint │
├────────────┤
│ (empty)    │
└────────────┘
> CHR.upto(4);                           // generate fibs upto 4
> konsole(CHR.Store);                    // print updated store
┌────────────┐
│ Constraint │
├────────────┤
│ upto(4)    │
├────────────┤
│ fib(3,3)   │
├────────────┤
│ fib(4,5)   │
└────────────┘

Cf. Screenshot 4

The constraint calls are chainable, that means CHR.upto(4).upto(10) would be possible too. Because the constraint store instance CHR.Store is an EventEmitter, it is very easy to implement special loggers, activities etc.:

CHR.Store.on('add', function(c) {
  console.log('Constraint '+c.toString()+' has been added.')
})

CHR.Store.on('remove', function(c) {
  console.log('Constraint '+c.toString()+' has been removed.')
})

Summary

In this project we created a prototype implementation of CHR in JavaScript. The module, called CHR.js, allows the transpilation of JavaScript with embedded CHR into standard JavaScript. With chrjs.net a first version of a CHR playground, similar to online tools like JSFiddle and RequireBin, has been created. This is a first step to run Constraint Handling Rules directly in the browser, without having to install a host language like Prolog oder Java first.

Because of its prototype character the current implementation has several missing features. For CHR developers experienced with Prolog as CHR’s host language, the absence of logical variables and pattern matching in the rule’s head constraints might be most notable. Because of the missing constraint declarations it is currently near to impossible to interact with built-in or user-defined functions from CHR rules.

With reference to the research done by Peter Van Weert in 2010, there is a wide range of optimization techniques that should be implemented, too. It also mentions extensions of CHR that can be implemented in imperative application of CHR.

The further development of the CHR.js transpiler as well as its related tools like the CHR.js website will be part of the author’s Master Thesis. The following goals can be stated as of yet as conclusions of the prototype implementation:

Reject the usage of PEG.js in favor of Babel.

This allows to concentrate on the compilation part of the current process. Although Babel is a very new JavaScript transpiler, it is used by a large number of companies, among others Apple and Facebook. The latter one established JSX, a syntax extension for JavaScript which gets transpiled to standard JavaScript with the help of Babel.
Use the new ECMAScript 2015 JavaScript standard, which has been approved in June 2015. Some new language features might be also a starting point for optimizations in performance or resulting file size, most notable:
- Destructuring, for easier pattern matching in constraint arguments
- Tail Calls, to increase the performance
- Template Strings, to embed CHR natively in JavaScript without having to use new keywords
- Generators, for the result set of constraint store lookups
- Promises, which optimizes the current constraint chaining mechanism like CHR.upto(4).upto(10)
- Proxies, which would allow the call of nullary constraints in the form of pred (cf. The CHR.js Language)
- Module Systems, to combine multiple CHR modules
Although these new features aren’t available in all JavaScript environments as of yet, Babel provides polyfills for most of them.
Provide a mechanism to interact with HTML elements in the DOM. CHR seems to be a very suitable and declarative approach to create new HTML elements depending on existing ones.
Implement the optimization techniques mentioned in Peter Van Weert; 2010. Today’s JavaScript runtime engines are highly optimized. That means a CHR(JavaScript) application could benefit by the high performance of runtime engines like Google’s V8, which is the basis for node.js.

Appendix

Example Occurence Function

Referencing the Fibonacci generation example, the following CHR._fib_2_occurence_1 function is generated by the compiler for the first occurence fib(N1,M1) of the fib/2 constraint in the calc-rule:

CHR.prototype._fib_2_occurence_1 = function (constraint) {
  var self = this
  
  // Match the arguments N1 and M1
  var N1 = constraint.args[0]
  var M1 = constraint.args[1]
  
  // Search for an appropriate upto/1 constraint
  self.Store.lookup("upto", 1).forEach(function (id1) {

    // Match the argument M1 of upto/1
    var Max = self.Store.args(id1)[0]
    
    // Search for an appropriate fib/2 constraint
    self.Store.lookup("fib", 2).forEach(function (id2) {

      // Match its arguments N2 and M2
      var N2 = self.Store.args(id2)[0]
      var M2 = self.Store.args(id2)[1]
      
      // Collect the IDs of all sampled constraints
      var ids = [ id1, id2, constraint.id ]

      // ... to check if they are pairwise distinct
      if (Runtime.helper.allDifferent(ids)) {

        // Check the rule's guard
        if (N2 === (N1 + 1) && N2 < Max) {

          // Was the rule already applied with these
          //   these constraints?
          if (self.History.notIn("calc", ids)) {

            // Add rule application to propagation
            //   history
            self.History.add("calc", ids)
          
            // Simpagation rule: Remove the original
            //   constraint
            self.Store.kill(ids[2])

            // ... and add a new `fib/2`
            self.fib(N2 + 1, M1 + M2)
          }
        }
      }
    })
  })
}