zebrajs facts: take that prolog :D

Today for fun I decided to implement some mathematical operators/logic operator on the zebrajs lib.

So I decided to make a post on the add operator.

The add implementation uses the idea of facts in prolog.
In prolog a fact is expressed like this:

father(rolando, filipe);
father(rolando, isabel);

Above I am simple saying that rolando is the father of filipe and isabel, and that is fact.
When I execute for example father(X, filipe), X will take the value rolando.

On the zebrajs there is no notion of facts, but a similar behaviour can be implemented, this is how I did it:

function Facts (values, factory, args, callback) {
	return function () {
		values.forEach(function (value) {
			if (value.length === args.length) {
				var ok = true;
				factory.save();
				for (var i=0; i<args .length; i++) {
					ok = value[i].unify(args[i]);
					if (!ok) {break;}
				}
			
				if (ok) {
					callback(args);
				}
				
				factory.load();
			}
		});
	};
};

And the function can be used like this to define for example AND operator:

function AND (p, q, r, callback) {
	return Facts ([
		[v({domain: [0]}), v({domain: [0]}), v({domain: [0]})],
		[v({domain: [0]}), v({domain: [1]}), v({domain: [0]})],
		[v({domain: [1]}), v({domain: [0]}), v({domain: [0]})],
		[v({domain: [1]}), v({domain: [1]}), v({domain: [1]})]
	], factory, [p, q, r], callback);	
};

The fact functions takes a table of values, and return a function that will try to unify the input variables with the variables on the table if it succeeds to unify a full table line then a solution was found and a callback function is called.

For example:

var AND(v(), v(), v({domain: [1]}), function (vars) {
  console.log(vars[0].getValue() + " AND " + vars[1].getValue() + " = " + vars[2].getValue());
});

It will print: “1 AND 1 = 1″, because the only line that can be unified with the input values is the last one “[v({domain: [1]}), v({domain: [1]}), v({domain: [1]})]”

Now the same thing can be done to define a simple 1 bit ADD operator, I will define
the ADD with input: p + q = r, c (previews operation carry) and cc (carry).
The table will contain all possible values to compute 1-bit add operation, for example:
p + q + c = r, cc
0 + 0 + 0 = 0, 0
0 + 0 + 1 = 1, 0
0 + 1 + 0 = 1, 0

1 + 1 + 1 = 1, 1

function ADD (p, q, c, r, cc, callback) {
	return Facts ([
		[v({domain: [0]}), v({domain: [0]}), v({domain: [0]}), v({domain: [0]}), v({domain: [0]})],
		[v({domain: [0]}), v({domain: [0]}), v({domain: [1]}), v({domain: [1]}), v({domain: [0]})],
		[v({domain: [0]}), v({domain: [1]}), v({domain: [0]}), v({domain: [1]}), v({domain: [0]})],
		[v({domain: [0]}), v({domain: [1]}), v({domain: [1]}), v({domain: [0]}), v({domain: [1]})],
		[v({domain: [1]}), v({domain: [0]}), v({domain: [0]}), v({domain: [1]}), v({domain: [0]})],
		[v({domain: [1]}), v({domain: [0]}), v({domain: [1]}), v({domain: [0]}), v({domain: [1]})],
		[v({domain: [1]}), v({domain: [1]}), v({domain: [0]}), v({domain: [0]}), v({domain: [1]})],
		[v({domain: [1]}), v({domain: [1]}), v({domain: [1]}), v({domain: [1]}), v({domain: [1]})],
	], factory, [p, q, c, r, cc], callback);
};

This operator can now be used to construct a n-bit operator, the input now would
be an array of variables (on reverse order), for example, p=2=[v({domain: [0]}), v({domain: [1]})]=10 (binary).

function ADDn (p, q, r, callback) {
	var c = v({domain: [0]});
	
	var f = function () {
		callback(p, q, r);
	};
	
	p.forEach (function (_p, index) {
		var cc = v();
		f = ADD(_p, q[index], c, r[index], cc, f);
		c = cc;
	});
		
	return f;
};

This function will construct a sequence of ADDs passing carry flag from one operation to other, a 2 bits operation would look something like this:
- ADD(p1, q1, v({domain: [0]), r1, cc, ADD(p2, q2, cc, r2, cc2, callback));
Notice that cc is the carry of first operation that is passed to the second operation.

Now I can use add function like this:

var add = ADDn([v(), v()], [v(), v()], [v(), v()], callback);

To make things simpler I defined a function to generate variables from decimal number to zebrajs vars and wrap it up on a nice add function.

And now the fun part :), use add function to solve [simple] equations, like this a+b=9:

var a = add(undefined, undefined, 9, 5 /* number of bits */, add_print); a();

And the result would is:

decimal: 2 + 7 = 9
bits: 00010 + 00111 = 01001

decimal: 3 + 6 = 9
bits: 00011 + 00110 = 01001

decimal: 6 + 3 = 9
bits: 00110 + 00011 = 01001

decimal: 7 + 2 = 9
bits: 00111 + 00010 = 01001

decimal: 4 + 5 = 9
bits: 00100 + 00101 = 01001

decimal: 5 + 4 = 9
bits: 00101 + 00100 = 01001

decimal: 0 + 9 = 9
bits: 00000 + 01001 = 01001

decimal: 1 + 8 = 9
bits: 00001 + 01000 = 01001

decimal: 8 + 1 = 9
bits: 01000 + 00001 = 01001

decimal: 9 + 0 = 9
bits: 01001 + 00000 = 01001

decimal: 10 + -1 = 9
bits: 01010 + 11111 = 01001

decimal: 11 + -2 = 9
bits: 01011 + 11110 = 01001

decimal: 14 + -5 = 9
bits: 01110 + 11011 = 01001

decimal: 15 + -6 = 9
bits: 01111 + 11010 = 01001

decimal: 12 + -3 = 9
bits: 01100 + 11101 = 01001

decimal: 13 + -4 = 9
bits: 01101 + 11100 = 01001

decimal: -6 + 15 = 9
bits: 11010 + 01111 = 01001

decimal: -5 + 14 = 9
bits: 11011 + 01110 = 01001

decimal: -2 + 11 = 9
bits: 11110 + 01011 = 01001

decimal: -1 + 10 = 9
bits: 11111 + 01010 = 01001

decimal: -4 + 13 = 9
bits: 11100 + 01101 = 01001

decimal: -3 + 12 = 9
bits: 11101 + 01100 = 01001

decimal: -14 + -9 = 9
bits: 10010 + 10111 = 01001

decimal: -13 + -10 = 9
bits: 10011 + 10110 = 01001

decimal: -10 + -13 = 9
bits: 10110 + 10011 = 01001

decimal: -9 + -14 = 9
bits: 10111 + 10010 = 01001

decimal: -12 + -11 = 9
bits: 10100 + 10101 = 01001

decimal: -11 + -12 = 9
bits: 10101 + 10100 = 01001

decimal: -16 + -7 = 9
bits: 10000 + 11001 = 01001

decimal: -15 + -8 = 9
bits: 10001 + 11000 = 01001

decimal: -8 + -15 = 9
bits: 11000 + 10001 = 01001

decimal: -7 + -16 = 9
bits: 11001 + 10000 = 01001

Some results are not mathematical right, this is due to overflow, in this case the number of bits is limited to 5, the same problem would occur on a normal CPU.

The cool part of defining operator this way is that they work on any direction, so we can have any number of unknown variables. The operator can be chained to make a equation and they can be solved by just running it.

For example I had defined a multiply function, this function can easily be used to calculate
a square root, example: x*x=16, x would be solved to 4.

The multiply function is much more complicated and really slow:

function MULn (p, q, r, callback) {

	var grid = [];
	var l = p.length;
		
	var f = function () {
		callback(p, q, r);
	};
	
	for (var i=0; i<l ; i++) {
		var line = [];
		for (var j=0; j<i; j++) {
			line.push(v({domain: [0]}));
		}

		p.forEach(function (_p, index) {
			var a = v();
			var b = q[i];

			f = AND(_p, b, a, f);
			line.push(a);
		});
		
		for (var j=line.length; j<r.length; j++) {
			line.push(v({domain: [0]}));
		}
		
		grid.push(line);
		var gl = grid.length;
		if ((gl > 0) && !(grid.length&1)) {
			// 1, 2, [3], 4, [5]
			// save intermidiate add results.
			var line;
			if (i===l-1) {
				line = r;
			}
			else {
				line = [];
				for (var j=0; j<r .length; j++) {
					line.push(v());
				}
			}

			grid.push(line);
			// 0 1 [2], 2-2=0, 2-1=1, 2
			
			f = ADDn(grid[gl-2], grid[gl-1], grid[gl], f);
		}
	}
	
	return f;
};

It was fun to define this operators but there are still a lot of problems before any practical use for this.

Problems

  • Operations are too slow, not only operators should be optimized but also the zebrajs lib
  • Overflow results on wrong mathematical results, it should be a way to handle and avoid this.

The code is not yet on the repository, I will try to at least clean the code before a commit ;)

Posted in logic, zebrajs | Leave a comment

zebrajs improvements

Hi,

(** Zebrajs a constrain problem solving lib **)

Recently I discover that my zebrajs lib was broken, mostly because of type conversion, so I decided that was time to start adding automated testing to the lib.

I didn’t want anything to much complicated so I choose the mocha with should.js and I am very happy with it.

The test file is here they are pretty simple.

Now with tests I hope to avoid breaking the lib and that it became much more stable.

Try it out :D and give me some feedback.

Posted in Uncategorized | Leave a comment