Logical programming in JavaScript
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
src
test
.babelrc
.gitignore
LICENSE
README.md
package.json

README.md

Logic programming in JavaScript

The library is based on Backtracking, Interleaving, and Terminating Monad Transformers

Using it with @mfjs/compiler turns JavaScript into a logical programming language.

For example, here is almost literal translation of classical Prolog bi-directional list append function to JavaScript (defined in separate samples project):

function append(a,b,r) {
  const [h, t, rt] = newRefs()
  unify(a, cons(h, t))
  unify(r, cons(h, rt))
  append(t, b, rt)
  M.answer()
  unify(a, nil())
  unify(r, b)
}

with usages:

let l1 = List.from([1,2,3])
let l2 = List.from(['a','b','c'])
// free variables:
let [l3,l4,l5] = newRefs()

append(l1, l2, l3)
console.log('append:', List.toArray(l3))
// ==> append: [ 1, 2, 3, 'a', 'b', 'c' ]

append(l1, l4, l3)
console.log('suffix', List.toArray(l4))
// ==> suffix [ 'a', 'b', 'c' ]

append(l5, l2, l3)
console.log('prefix', List.toArray(l5))
// ==> prefix [ 1, 2, 3 ]

or non-determenistic with only result defined:

let [x,y] = newRefs()
let z = List.from([1,2,3,4])
// only result is instantied 
append(x,y,z)
console.log('x:', List.toArray(x))
console.log('y:', List.toArray(y))
console.log('z:', List.toArray(z))

outputs all 5 possible answers:

x: [ 1, 2, 3, 4 ]
y: []
z: [ 1, 2, 3, 4 ]

x: [ 1, 2, 3 ]
y: [ 4 ]
z: [ 1, 2, 3, 4 ]

x: [ 1, 2 ]
y: [ 3, 4 ]
z: [ 1, 2, 3, 4 ]

x: [ 1 ]
y: [ 2, 3, 4 ]
z: [ 1, 2, 3, 4 ]

x: []
y: [ 1, 2, 3, 4 ]
z: [ 1, 2, 3, 4 ]

API

In standard Prolog language there is only depth first search options for possible answer lookup. The library provides means to add arbitrary search strategies. By default it provides depth-first and breadth-first searches.

Result object returned from L.run is ES iterable. Its default iterator traverses answers in depth-first order. The result object also has bfs function returning iterator for breadth first order.

There are a few additional functions in logic monad definition:

  • once - takes logical computation and returns only its first answer if any
  • level - for logical computation returns object with either field value or alts, the first is final result of the computation and the second is a list of other logical computations if original one was non-deterministic

Usage

$ npm install --save-dev @mfjs/compiler
$ npm install --save @mfjs/core @mfjs/logic
$ mfjsc input.js --output=out
# or for browser
$ browserify -t @mfjsc/compiler/monadify input.js -o index.js

License

Copyright © 2016 Vitaliy Akimov

Distributed under the terms of the The MIT License (MIT).