CHR.js - A CHR Transpiler for JavaScript


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


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.


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:, 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:

  1. 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.

  2. 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:

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.


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:

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.


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:

  = PropagationRule
  / SimplificationRule
  / SimpagationRule

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

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

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

  = Identifier "@"

  = BuiltInConstraints "|"

  = BuiltInConstraint "," BuiltInConstraints
  / BuiltInConstraint

  = AssignmentExpression       /* JavaScript expression    */

  = Constraint "," Body
  / Constraint

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

  = 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:

  = name:RuleName? headConstraints:CHRConstraints
      "==>" guard:Guard? bodyConstraints:Body
      var desc = {
        type: 'PropagationRule',
        kept: headConstraints,
        removed: [],
        body: bodyConstraints,
        guard: guard || []
      if (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:

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.


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:


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


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.')


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 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:


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, ]

      // ... 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

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