Pattern Matching on Arrays in Javascript
I was working through a quite accessible AI book called AI Algorithms, Data Structures, and Idioms in Prolog, Lisp, and Java by Luger and Stubblefield, during my flirtations with Prolog and stumbled across an implementation of pattern matching in Common Lisp that was very elegant and so decided to port it Javascript.
My implementation allows you to pass unbound variables as sentinel values that can match against any data
/** pattern matching on arrays in js
* by Joe Attueyi */
var assert = require("assert");
/* a few helper functions */
var typeString = function(x){
return Object.prototype.toString.call(x) ;
}
var isObj = function(x){
return typeString(x) === "[object Object]";
}
var isArray = function(x){
return typeString(x) === "[object Array]";
}
var matchAtom = function(l1, l2){
return l1 === l2 || typeof(l1) === "undefined"|| typeof(l2) === "undefined";
}
var isAtom = function(l){
if (typeof(l) === "string" ||
typeof(l) === "number" ||
typeof(l) === "undefined" ||
typeof(l) === "boolean"){
return true;
}else{ false; }
}
/* check if 2 arrays match */
var match = function(l1, l2){
if( isAtom(l1) || isAtom(l2) ){
return matchAtom(l1,l2);
}
else if( l1.length !== l2.length){ return false;
}
else if(isArray(l1) && l1.length === 0 && isArray(l2) && l2.length === 0){
return true;
}
else if (l2.length !== 0 || l1.length !== 0){
return match(l1.slice(0,1)[0], l2.slice(0,1)[0]) && match(l1.slice(1), l2.slice(1));
}
}
var getMatches = function(l, db){
var res = [];
for(var i=0; i<db.length; i++){
if(match(l, db[i])){
res.push(db[i]);
}
}
return res;
}
You can use this to make queries that match structured data in a database as shown below. I'd like to make this work for data structures other than Lists/Arrays/Vectors, my experience with the pattern matching and the closely related unification have been in languages that used Lists for everything.
You can use pattern matching as replacement for control flow as is commonly done is languages such as ML, but for it to really shine in Javascript you'd need pattern matching on objects as well
var _p;
var db = [
[["lovelace", "ada"], 50000, 1234],
[["turing", "alan"], 45000, 3927],
[["shelley", "mary"], 3500, 2850],
[["vonNeumann", "john"], 40000, 7955],
[["simon", "herbert"], 50000, 1374],
[["mccarthy", "john"], 48000, 2864],
[["russell", "bertrand"], 35000, 2950]];
getMatches([["turing", "alan"], 45000, 3927], db);
// matches [["turing", "alan"], 45000, 3927]
getMatches([_p, 50000, _p], db);
// matches [["lovelace", "ada"], 50000, 1234] & [["simon", "herbert"], 50000, 1374]
getMatches([[_p, "john"], _p, _p], db);
// matches [["mccarthy", "john"], 48000, 2864] & [["vonNeumann", "john"], 40000, 7955]
assert( match(["likes", "bill", "wine"], ["likes", "bill", "wine"]) == true);
assert( match(["likes", "bill", "wine"], ["likes", "bill", "milk"]) == false);
var _a;
assert( match(["likes", "bill", _a], ["likes", "bill", "wine"]) == true);
assert( match(["likes", _a, "wine"], ["likes", "bill", _a]) == true);
assert( match(["likes", "bill", _a], ["likes", "bill", ["prolog", "lisp", "smalltalk"]]) == true)
assert( match(["likes", _a], ["likes", "bill", "wine"]) == false );
A Very Basic Fibres Implementation in Javascript Using Generators
I've been playing around with concurrency models in different languages and have quite enjoyed learning about them.
For my money the CSP derived ones in ML,Clojure and Go seem to me to be the most flexible and allow for you to build higher abstractions on top of them. I think Rich Hickey has it right, when he talks about the splitting of conveyance and execution being beneficial.
Anyways here is a hacky first attempt at a form of concurrency in javascript. Im using generators so that my functions can park and unpark their execution and context, this coupled with a run loop allows one to simulate concurrently executing functions in javascript
Here is the implementation.
function fibre(){
return {id: gen_id(), context: {}, active: false, body: null};
}
function lib_fibre(){
var fibre_q = {};
return{
gen_id : function(){
return Math.floor(Math.random() * 10000000);
},
spawn: function(fn){
_f = fibre();
_f.body = fn();
fibre_q[_f.id] = _f;
},
go: function(){
while (Object.keys(fibre_q).length > 0){
//l(fibre_q);
for(var v in fibre_q){
//l(v , fibre_q[v] );
var fn = fibre_q[v].body;
//l(fn);
var ref = fn.next();
//l(ref);
if(ref.done){
//l("in delete");
delete fibre_q[v];
}
//fibre_q[v].body = fn.next;
}
}
},
};
}
And here is the implementation in action.
var lf = lib_fibre();
var a = function *(){
yield l("Hi");
yield l("Joe");
yield l("Welcome");
yield l("!!!!!!");
}
var b = function *(){
var x = 10;
while (x > 0){
yield l(x);
x -= 1;
}
}
var c = function *(){
yield l("END");
}
lf.spawn(c);
lf.spawn(a);
lf.spawn(b);
lf.go();
Running this, you would see the interleaving of the functions. This is just a basic implementation, one could easily couple these with queues independent of processes and you could start to emulate CSP. Thankfully, through the wonderful magic of open source someone has already done this for you :)
I WROTE A LISP
A few weeks ago, i spent some time writing a Lisp in Javascript. This was due to having enjoyed writing Clojure and researching Lisps in general. I watched a few of the SICP lectures online and read Peter Norvig's How to Write a Lisp Interpreter in Python for some pointers and went on my way.
The lisp which I've imaginatively named Joelisp is a bit different to standard Lisps in terms of syntax as it inherits a lot of Clojure syntax and also uses mori's data structures.
It differs from most Lisps in that I have special semantics for evaluating code in depth first order. Code wrapped in an rx function will figure out the implicit dependency graph in your code and will run your code in topologically sorted order.
This kind of feature would be useful for doing reactive programming as it ensures that the values in variables propagate through the whole program even after the variable is mutated.
It also lets you make forward declarations on variables that don't exist yet which is pretty handy.
An example use of the rx tag is
(rx
(def c (+ a b))
(def d (* a b c))
(def b (+ a 1))
(def a 1)
(set! a 100)
)
(print a)
(print b)
(print c)
(print d)
returns you
100
101
201
2030100
pretty cool huh!
HE'S BACK
$ say "why joe???"
I'm coming out of blogging retirement trying to relive the glory days of the late 00s/early 10s. I can hear u asking why anyone would want to do that, and i'm not sure why either but hopefully we can find out together.
Til next time