Published
Edited
Jul 28, 2020
md`# Expression`
Ex = {
let symtab = {};
let stack = [symtab];
class Ex {
static makeSymbol(name) {
const sym = new Ex();
sym.head = Ex.Symbol;
sym.tail = [name];
sym.up = [];
sym.down = [];
stack[stack.length-1][name] = sym;
return sym;
}
static push() {
stack.push({});
}
static pop() {
stack.pop();
}
static getSymbol(name) {
for(let i = stack.length-1;i>=0;--i) {
if(stack[i][name]!==undefined) {
return stack[i][name];
}
}
}
isBlank() {
return this.head === Ex.Blank ||
this.head === Ex.BlankSequence ||
this.head === Ex.BlankNullSequence;
}
isAtom() {
return this.head === Ex.Symbol ||
this.head === Ex.Integer ||
this.head === Ex.Rational ||
this.head === Ex.String;
}
constructor(ex, vars = {}) {
if(ex===undefined) {
return;
}
if(typeof(ex) === 'number' && Number.isInteger(ex)) {
this.head = Ex.Integer;
this.tail = [ex];
return;
}
if(typeof(ex) === 'object') {
this.head = ex.head;
this.tail = ex.tail;
return;
}
function traverse(node) {
// console.log(node.type, node.fn, node.value, node.args);
switch(node.type) {
case 'OperatorNode':
switch(node.fn) {
case 'add': {
const a = traverse(node.args[0]);
const b = traverse(node.args[1]);
return new Ex('Plus(a,b)', {a,b});
}
break;
case 'multiply': {
const a = traverse(node.args[0]);
const b = traverse(node.args[1]);
return new Ex('Times(a,b)', {a,b});
}
break;
case 'pow': {
const a = traverse(node.args[0]);
const b = traverse(node.args[1]);
return new Ex('Power(a,b)', {a,b});
}
break;
case 'subtract': {
const a = traverse(node.args[0]);
const b = traverse(node.args[1]);
return new Ex('Plus(a,Times(mo,b))', {a, mo: Ex.minusOne, b});
}
break;
case 'unaryMinus': {
const a = traverse(node.args[0]);
return new Ex('Times(mo,a)', {mo: Ex.minusOne, a});
}
break;
case 'divide': {
const a = traverse(node.args[0]);
const b = traverse(node.args[1]);
return new Ex('Times(a,Power(b,mo))',{a, mo: Ex.minusOne, b});
}
break;
}
break;
case 'ParenthesisNode':
return traverse(node.content);
break;
case 'FunctionNode': {
const tail = node.args.map((n)=> traverse(n));
return new Ex({head: Ex.getSymbol(node.fn.name), tail: tail});
}
break;
case 'SymbolNode': {
const sp = node.name.split('_');
if(sp.length==1) {
if(vars[node.name]!==undefined) {
return vars[node.name];
}
return Ex.getSymbol(node.name);
} else if(sp.length==2) {
const str = new Ex({head: Ex.String, tail: [sp[0]]});
if(sp[1] === "") return new Ex({head: Ex.Blank, tail: [str] });
return new Ex({head: Ex.Blank, tail: [str, Ex.getSymbol(sp[1])] });
} else if(sp.length==3) {
const str = new Ex({head: Ex.String, tail: [sp[0]]});
if(sp[2] === "") return new Ex({head: Ex.BlankSequence, tail: [str] });
return new Ex({head: Ex.BlankSequence, tail: [str, Ex.getSymbol(sp[2])] });
} else if(sp.length==4) {
const str = new Ex({head: Ex.String, tail: [sp[0]]});
if(sp[3] === "") return new Ex({head: Ex.BlankNullSequence, tail: [str] });
return new Ex({head: Ex.BlankNullSequence, tail: [str, Ex.getSymbol(sp[3])] });
}
}
break;
case 'ConstantNode':
return new Ex(node.value);
break;
}
}
let pex = math.parse(ex);
let {head, tail} = traverse(pex);
this.head = head;
this.tail = tail;
}
equal(ex) {
// console.log('equal:',this.toString(), ex.toString());
if(this.head !== ex.head) return false;
if(this.isAtom() && ex.isAtom()) {
for(let i=0; i<this.tail.length; ++i) {
if(this.tail[i] !== ex.tail[i]) return false;
}
return true;
}
if(!this.isAtom() && !ex.isAtom()) {
for(let i=0; i<this.tail.length; ++i) {
if(!this.tail[i].equal(ex.tail[i])) return false;
}
return true;
}
return false;
}
matchR(pat, cap) {
if(pat.isAtom()) return this.equal(pat);
if(pat.head === Ex.Blank) {
const name = pat.tail[0].tail[0];
const head = pat.tail[1];
if(head !== undefined && !head.equal(this.head)) return false;
if(name === '') return true;
let en = cap[name];
if(en !== undefined) {
return this.equal(en);
} else {
cap[name] = this;
return true;
}
}
if(!this.head.matchR(pat.head, cap)) return false;
for(let i=0; i<pat.tail.length; ++i) {
const pati = pat.tail[i];
if((pati.head === Ex.BlankNullSequence ||
pati.head === Ex.BlankSequence) && i != pat.tail.length-1 ) throw "BlankSequence not at last";
if( pati.head === Ex.BlankNullSequence ||
(pati.head === Ex.BlankSequence && i < this.tail.length) ) {
const name = pati.tail[0].tail[0];
const head = pati.tail[1];
let exr = [];
for(let j=i; j<this.tail.length; ++j) {
exr.push(this.tail[j]);
if(head !== undefined && !this.tail[j].head.equal(head)) return false;
}
exr = new Ex({head: Ex.Sequence, tail: exr});
if(name === '') return true;
let en = cap[name];
if(en !== undefined) {
return exr.equal(en);
} else {
cap[name] = exr;
return true;
}
}
if(i == this.tail.length) return false;
if(!this.tail[i].matchR(pati, cap)) return false;
}
if(pat.tail.length < this.tail.length) return false;
return true;
}
match(pat, cap) {
let cap2 = {};
let r = this.matchR(pat, cap2);
if(r) for(let k in cap2) cap[k] = cap2[k];
return r;
}
isNumeric() {
return this.head === Ex.Integer || this.head === Ex.Rational;
}
numericValue() {
if(this.head === Ex.Integer) return this.tail[0];
if(this.head === Ex.Rational) return this.tail[0]/this.tail[1];
}
comp(ex) {
// O1
if(this.isNumeric() && ex.isNumeric())
return this.numericValue() < ex.numericValue();
// O2
if(this.head === Ex.Symbol && ex.head === Ex.Symbol)
return this.tail[0] < ex.tail[0];
// O3
if((this.head === Ex.Plus && ex.head === Ex.Plus) ||
(this.head === Ex.Times && ex.head === Ex.Times)) {
let m = this.tail.length-1;
let n = ex.tail.length-1;
while(m>=0 && n>=0) {
if(this.tail[m].equal(ex.tail[n])) {
m = m-1;
n = n-1;
} else {
return this.tail[m].comp(ex.tail[n]);
}
}
return m < n;
}
// O4
if(this.head === Ex.Power && ex.head === Ex.Power) {
if(this.tail[0].equal(ex.tail[0])) {
return this.tail[1].comp(ex.tail[1]);
} else {
return this.tail[0].comp(ex.tail[0]);
}
}
// O6
if(this.head === ex.head) {
let m = this.tail.length;
let n = ex.tail.length;
let i = 0;
while(i<m && i<n) {
if(this.tail[i].equal(ex.tail[i])) {
i = i+1;
} else return this.tail[i].comp(ex.tail[i]);
}
return m < n;
}
// O7
if(this.isNumeric() && !ex.isNumeric()) return true;
else if(!this.isNumeric() && ex.isNumeric()) return false;
// O8
if(this.head === Ex.Times) {
return this.comp(new Ex('Times(a)', {a: ex}));
} else if(ex.head === Ex.Times) {
return (new Ex('Times(a)', {a: this})).comp(ex);
}
// O9
if(this.head === Ex.Power) {
return this.comp(new Ex('Power(a,1)', {a: ex}));
} else if(ex.head === Ex.Times) {
return (new Ex('Power(a,1)', {a: this})).comp(ex);
}
// O10
if(this.head === Ex.Plus) {
return this.comp(new Ex('Plus(a)', {a: ex}));
} else if(ex.head === Ex.Plus) {
return (new Ex('Plus(a)', {a: this})).comp(ex);
}
// O12
if(ex.head === Ex.Symbol && this.head.equal(ex)) return false;
else if(this.head === Ex.Symbol && this.equal(ex.head)) return true;
if(this.head === Ex.String && ex.head === Ex.String)
return this.tail[0] < this.tail[1];
}
eval() {
if(this.head === Ex.Symbol) {
if(this.value !== undefined) return this.value;
else return this;
}
if(this.isAtom()) return this;
let ex = [];
if(this.head.holdAll) {
for(let i=0;i<this.tail.length; ++i) ex.push(this.tail[i]);
} else {
for(let i=0;i<this.tail.length; ++i) {
if(this.head.holdFirst && i == 0) {
ex.push(this.tail[i]);
} else {
ex.push(this.tail[i].eval());
}
}
}
if(!this.head.sequenceHold) {
let i = 0;
while(i<ex.length) {
let exi = ex[i];
if(exi.head === Ex.Sequence) {
ex.splice(i,1,...exi.tail);
i = i+exi.tail.length;
} else i = i+1;
}
}
if(this.head.flat) {
let i = 0;
while(i<ex.length) {
let exi = ex[i];
if(this.head === exi.head) {
ex.splice(i,1,...exi.tail);
i = i+exi.tail.length;
} else i = i+1;
}
}
if(this.head.orderless) {
ex.sort((a,b) => (a.comp(b) ? -1 : 1));
}
ex = new Ex({head: this.head, tail: ex});
let tex;
for(let i=0;i<ex.tail.length;++i) {
let exi = ex.tail[i];
if(exi.head.up) {
for(let j=0;j<exi.head.up.length;++j) {
tex = exi.head.up[j](ex);
if(tex) {
return tex.eval();
}
}
}
}
if(ex.head.down) {
for(let j=0;j<ex.head.down.length;++j) {
tex = ex.head.down[j](ex);
if(tex) {
return tex.eval();
}
}
}
return ex
}
addRule(rule, fn) {
rule = new Ex(rule);
let tab;
if(this === rule.head) tab = this.down;
else tab = this.up;
tab.push( (ex) => {
let cap = {};
if(ex.match(rule, cap)) {
return fn(cap);
}
return null;
});
}
toString() {
if(this.head === Ex.Blank) {
return this.tail[0].tail[0]+'_'+(this.tail[1] !== undefined ? this.tail[1].toString() : '' );
}
if(this.head === Ex.BlankSequence) {
return this.tail[0].tail[0]+'__'+(this.tail[1] !== undefined ? this.tail[1].toString() : '' );
}
if(this.head === Ex.BlankNullSequence) {
return this.tail[0].tail[0]+'___'+(this.tail[1] !== undefined ? this.tail[1].toString() : '' );
}
if(this.head === Ex.Rational) {
return this.tail[0]+'/'+this.tail[1];
}
if(this.isAtom()) return this.tail[0].toString();
let r = this.head.toString()+'(';
let t = this.tail.map((e) => e.toString());
return r+t.toString()+')';
}
}
Ex.Symbol = Ex.makeSymbol('Symbol');
Ex.Symbol.head = Ex.Symbol;
Ex.Integer = Ex.makeSymbol('Integer');
Ex.Rational = Ex.makeSymbol('Rational');
Ex.String = Ex.makeSymbol('String');
Ex.Plus = Ex.makeSymbol('Plus');
Ex.Plus.orderless = true;
Ex.Plus.flat = true;
Ex.Times = Ex.makeSymbol('Times');
Ex.Power = Ex.makeSymbol('Power');
Ex.Sequence = Ex.makeSymbol('Sequence');
Ex.Blank = Ex.makeSymbol('Blank');
Ex.BlankSequence = Ex.makeSymbol('BlankSequence');
Ex.BlankNullSequence = Ex.makeSymbol('BlankNullSequence');
Ex.Sqrt = Ex.makeSymbol('Sqrt');
Ex.Sqrt.addRule('Sqrt(a_)', (cap)=> new Ex('Power(a,Rational(1,2))', cap));
Ex.minusOne = new Ex(-1);
return Ex;
}
{
const ex = (new Ex('Plus(4,3,Rational(7,2),Sqrt(2),Plus(4,2))')).eval();
return ex.toString();
}
math = require('mathjs');
One platform to build and deploy the best data apps
Experiment and prototype by building visualizations in live JavaScript notebooks. Collaborate with your team and decide which concepts to build out.
Use Observable Framework to build data apps locally. Use data loaders to build in any language or library, including Python, SQL, and R.
Seamlessly deploy to Observable. Test before you ship, use automatic deploy-on-commit, and ensure your projects are always up-to-date.