logicjs

Logic programming for JavaScript.

Downloads in past

Stats

StarsIssuesVersionUpdatedCreatedSize
logicjs
1.0.08 years ago8 years agoMinified + gzip package size for logicjs in KB

Readme

LogicJS
LogicJS adds logic programming to JavaScript.
Logic programming is typically known by the language Prolog.
Installation
Download the logic.js file and move it to your project.
Introduction
var or = logic.or,
	and = logic.and,
	eq = logic.eq,
	run = logic.run,
	lvar = logic.lvar,
	between = logic.between
	
//creates two unique logic variables
var x = lvar(),
  y = lvar()
  
//creates a 'goal'
g1 = or(
  and(eq(x,2), eq(y,3)),
  and(eq(x,y), eq(y,'dog'))
)
	
//runs goal asking for the possible values of x and y
run(g1, x) //[2, 'dog']
run(g1, y) //[3, 'dog']
run(g1, [x,y]) //[ [2, 3], ['dog', 'dog'] ]

//a goal is a sequence of assertions
//here, we assert that x is a value from 1 to 3
//and that y is either 1 or 2
g2 = and(
	between(1,3,x),
	or(eq(1,y), 
		eq(2,y))
)

//get only the first 2 answers
run(g2, [x,y], 2) //[ [1, 1], [1, 2] ]
//get all answers
run(g2, [x,y]) //[ [1, 1], [1, 2], [2, 1], [2, 2], [3, 1], [3, 2] ]

Goals

Programmers may create their own goals by combining primitive goals such as or, and and eq.
function father(x,y) {
	//mcbob is father of bob
	//bob is father of bill
	return or(
		and(eq(x,'mcbob'), eq(y,'bob')),
		and(eq(x,'bob'), eq(y,'bill'))
	)
}

function grandfather(x,y) {
	var z = lvar() //dummy variable
	return and(father(x,z), father(z,y))
}

//who is father of bob?
run(father(x,'bob'), x) //['mcbob']
//who is grandfather of who?
run(grandfather(x,y), [x,y]) //[ ['mcbob', 'bill'] ]

The win and fail goals simply succeed or not succeed. They are analogous to the true and false constants in logic.
run(logic.win, x) //[ undefined ]
run(logic.fail, x) //[]

Note that failure means there are no answers (empty array), while success means there is at least one answer (in this case the answer is undefined, since we still don't know the value of x).

Constraints

In pure logic programming, it doesn't matter which arguments of a goal have been instantiated.
This works for the arithmetic relations.
var add = logic.add, sub = logic.sub, mul = logic.mul, div = logic.div

run(add(x,2,6), x) //[ 4 ]
run(sub(2,x,6), x) //[ -4 ]
run(mul(2,6,x), x) //[ 12 ]
run(div(x,2,6), x) //[ 12 ]

When not enough arguments are instantied, some goals will propagate a constraint (such as "x+1=y" or "x is less or equal to 2"). When it's still not possible to find a value for the variable, it'll return a domain with the possible values of that variable.
var less_equal = logic.less_equal
var write = console.log

v = run(and(add(x,y,3), eq(y,1)), x)[0]
write(v) //2

v = run(less_equal(1,2), x)[0]
write(v) //undefined
d = run(less_equal(x,2), x)[0]
write(d.min, d.max) //-inf, 2
d = run(less_equal(2,x), x)[0]
write(d.min, d.max) //2, inf
d = run(less_equal(x,y), x)[0]
write(d.min, d.max) //-inf, inf

Unification (done by the goal logic.eq) is the most basic kind of constraint. Constraint logic programming adds further constraints.
An example of an impure goal included in LogicJS is between, which requires the first two arguments to be numbers.
Implementation
The implementation of LogicJS is based on MiniKanren/SICP.
  • Bindings associate a variable to a value (e.g. X=2).
  • Streams are similar to lists, but they are evaluated on the fly and thus are potentially infinite.
  • Packages contain a list of bindings (sometimes called a frame) and a list of constraints. Logic programming without support for constraints might only use frames instead of packages.
  • Goals take a package as input and return a stream of packages (since a goal can have zero or infinite answers).