CHR Introduction

Constraint Handling Rules

  • Rule-based language defined 1991 by Thom Frühwirth
  • Originally created to implement constraint solvers in a high level programming language
  • Today a general-purpose programming language, used for natural language processing, compilation, verification, etc.
  • Typically used as a language extension: CHR(Prolog), CHR(Java), CHR(C)

CHR: Parts

  • Constraints with name/arity
    • CHR Constraints
    • Built-in Constraints by the host language
  • Constraint Store
  • Rules
    • Propagation Rule (… ==> …)
    • Simplification Rule (… <=> …)
    • Simpagation Rule (… \ … <=> …)

CHR: Rules

Propagation Rule

Name @ H1, …, Hn ==> G1, …, Gm | B1, …, Bl

Simplification Rule

Name @ H1, …, Hn <=> G1, …, Gm | B1, …, Bl

Simpagation Rule

Name @ H1, …, Hk \ Hk+1 …, Hn <=> G1, …, Gm | B1, …, Bl

CHR: gcd Example

Pseudocode Implementation

Example Program: Calculation of the greatest common divisor (GCD) using the subtraction-based Euclidean algorithm.

function gcd(a, b)
  while b > 0
    if a > b
      a := a - b
    else
      b := b - a
  return a
end

gcd(15, 12) == 3

CHR: gcd Example

CHR Implementation

gcd1  @  gcd(0) <=> true.
gcd2  @  gcd(N) \ gcd(M) <=> 0 < N, N <= M | gcd(M-N).

?- gcd(15), gcd(12)
...
gcd(3)

Demo: SWI-Prolog

CHR.js
Any application that can be written in JavaScript, will eventually be written in JavaScript.
Atwood's Law

Runtime Components

  • CHR.Constraint
  • CHR.Store
  • CHR.History
  • CHR.Rule
  • CHR (CHR.Rules)

Runtime: CHR.Constraint

let Constraint = CHR.Constraint

let gcd8 = new Constraint('gcd',   1,      [ 8 ])
                   //      name,  arity,  arguments

// some properties:
gcd8.id            // unique
gcd8.alive         // boolean

// prototype methods:
gcd8.toString()    // 'gcd(8)'

Runtime: CHR.Store

let chr = new CHR()
let store = chr.Store     // or:
                          // new CHR.Store()

// some properties:
store.length              // int
store.invalid             // boolean

// prototype methods:
store.add(gcd8)
store.kill(gcd8)
store.alive(gcd8)         // boolean
store.reset()
store.toString()          // tabular string representation
store.lookup(name, args)  // generator

// events:
store.on('add', handler)
store.on('remove', handler)

Runtime: CHR.History

let chr = new CHR()
let history = chr.History // or:
                          // new CHR.History()

// some methods:
history.add(ruleName, constraintIds)
history.has(ruleName, constraintIds)
history.notIn(ruleName, constraintIds)

Runtime: CHR.Rule

let chr = new CHR()
chr`
  ruleName @ gcd(0) <=> true
`                         // or:
                          // new CHR.Rule('gcd(0) <=> true')

let rule = chr.Rules.ruleName

// some methods:
rule.Fire(constraint)

// events resp. breakpoints:
rule.Breakpoints.onTry = handler
let firstGcdOccurrence = rule['gcd/1'][0]
firstGcdOccurrence.Breakpoints.onTry = handler

Runtime: Call Semantics

Preview

let chr = new CHR()
chr`
  gcd1  @  gcd(0) <=> true
  gcd2  @  gcd(N) \\ gcd(M) <=> 0 < N, N <= M | gcd(M-N)
`

// How to call gcd(15), gcd(12) ?
// Not working because of asynchronous functions:
//   chr.gcd(15)
//   chr.gcd(12)
//   let result = chr.store.lookup(...)

The Event Loop
In node.js everything runs in parallel,
except your code.
Felix Geisendörfer, Core Comitter of node.js

JavaScript's Event Loop

Pseudocode Implementation

while queue.waitForMessage()
  queue.processNextMessage()
end

JavaScript's Event Loop

Visualisation

Description
Source: Mozilla Developer Network (MDN)

JavaScript's Event Loop

gcd Example, Naive Recursive Implementation

function gcd (a, b) {
  if (b == 0)
    return a
  if (a > b)
    return gcd(a-b, b)
  return gcd(a, b-a)
}

JavaScript's Event Loop

gcd Example, Asynchronous Implementation

function gcd (a, b, callback) {
  if (b == 0) {
    callback(a)
  } else if (a > b) {
    setTimeout(function () {
      gcd(a-b, b, callback)
    }, 0)
  } else {
    setTimeout(function () {
      gcd(a, b-a, callback)
    }, 0)
  }
}

Runtime: Call Semantics

Example Usage

let chr = ...
chr.gcd(15).then(function () {
  return chr.gcd(12)
}).then(function () {
  // finished
})

Promise
.all([ chr.gcd(15), chr.gcd(12) ])
.then(function () {
  // finished
})

Components

  • Parser
  • Compiler
  • Runtime
  • Builds and Benchmarks

CHR.js Compiler

CHR: gcd Example

CHR Implementation

gcd1  @  gcd(0) <=> true.
gcd2  @  gcd(N) \ gcd(M) <=> 0 < N, N <= M | gcd(M-N).

Example Compilation

function (constraint,replacements) {
  var M = constraint.args[0]
  
  var constraintIds = [
    self.Store.lookup("gcd", 1)
  , [ constraint.id ]
  ]
  
  return new Promise(function (resolve, reject) {
    self.Helper.forEach(constraintIds,
    function iterateConstraint (ids, callback) {
      if (!self.Store.allAlive(ids)) return callback()
      if (self.History.has("gcd2", ids)) return callback()
      
      var N = self.Store.args(ids[0])[0]
      ...
    }
  })
}

Example Compilation

      ...
      var N = self.Store.args(ids[0])[0]

      var guards = [
        new Promise(function (s, j) { (0 < N) ? s() : j() })
      , new Promise(function (s, j) { (N <= M) ? s() : j() })
      ]
      
      Promise.all(guards)
      .then(function () {
        self.History.add("gcd2", ids)
        self.Store.kill(ids[1])
        
        Promise.resolve().then(function () {
          return self.gcd(M - N)
        })
      })
    }, resolve)
  })
}

Demo

Source Code Demo

Benchmarks

Description
CHR-Benchmarks for gcd

Thank you!




question(X) ==> ask(X)

Backup Slides

Parser

Parser

Parse the given CHR source and create a syntax tree.

rem_long @ path(X,Y,L1) \ path(X,Y,L2) <=> L1 <= L2 | true;
path_add @ path(X,Y,L1), path(Y,Z,L2) ==> X !== Z | path(X,Z,L1+L2);

Modifications:

  • Rules (might) end with ;
  • ES2015 destructuring instead of logical variables
  • JavaScript operators and notation

Parsing Expression Grammar

Start
  = Program

CHRRule
  = PropagationRule
  / SimplificationRule
  / SimpagationRule

PropagationRule
  = RuleName? CHRConstraints "==>" Guard? Body {
      ...
    }

RuleName
  = identifier:Identifier "@" {
      return identifier;
    }

JS Optimizations

JS Optimizations

Description
JS Performance of with statement

CHR.js Precompiler

Optimization using Trampolines

function _chr () {
  /**
    ... static implementation for CHR runtime components ...
  */

  function State (constraint, type, step, lookup, scope) {
    this.type = type
    this.constraint = constraint
    this.step = step
    this.lookup = lookup
    this.scope = scope
  }

  function saveState (constraint, step, lookup, scope) {
    return new State(constraint, 'intermediate', step, lookup, scope)
  }

  function constraintState (constraint) {
    return new State(constraint, 'constraint', null, null, null)
  }

Optimization using Trampolines

function _chr () {
  ...

  function tell () {
    var current
    while (chr.Tells.length > 0) {
      current = chr.Tells.pop()
      if (current.type === 'constraint') {
        chr.Store.add(current.constraint)
      }
      dispatchTell(current)(current)
    }
  }

  function dispatchTell (current) {
    switch (current.constraint.functor) {
      case 'gcd/1':
        return gcd_1
      break
    }
  }