maths_ast.js (1312198) - rtensor · DKL9 GitList

Import v2.3-dev from a demonic ritual

dkl9 commited 1312198 at 2023-184 18:25:57

maths_ast.js

Blame History Raw

"use strict";

const isArray = x => (typeof x == "object" && x.constructor == Array);
const NUMERIC_TYPES = {
    integer: BigInt,
    complex: Complex,
    real: Number,
};
const nti = (new URLSearchParams(window.location.search)).get("nt") || "a";
const NumericType = NUMERIC_TYPES[nti] || Number;

// a: tensor, b: tensor, o: binary function of numbers
function vecOp(a, b, o) {
    const tra = tensorRank(a);
    const trb = tensorRank(b);
    if (tra == trb && tra >= 1 && a.length == b.length) {
        return a.map((x, i) => vecOp(x, b[i], o));
    } else if (tra > trb) {
        return a.map(x => vecOp(x, b, o));
    } else if (trb > tra) {
        return b.map(x => vecOp(a, x, o));
    } else if (tra == trb && tra == 0) {
        return o(a, b);
    }
}

// true iff any elements of v is null or NaN
function anyNaN(v) {
    return v.map ?
        v.map(x => anyNaN(x)).reduce((a, b) => (a || b), false) :
        (v == null || (typeof v == "number" && isNaN(v)) || (v.invalid && v.invalid()));
}

// the rank of t -- 0 for scalars, 1 for vectors, 2 for matrices, etc
// see https://mathworld.wolfram.com/TensorRank.html
function tensorRank(t) {
    return (typeof t == "object" && t.constructor == Array) ? 1 + t.map(st => tensorRank(st)).reduce((a, b) => Math.max(a, b), 0) : 0;
}

// node in an abstract syntax tree, as produced by NewParser
class AST {
    constructor(ts, l, m, r, len) {
        switch (ts) {
            // identifier: l == Token (tt == 1), m, r == undefined
            case 1: this.v = l.v; break;
            // literal: l == Token (tt == 2)
            case 2: this.v = l.v; break;
            // operation: l == AST, m == Token (tt == 3), r == AST
            case 3: this.l = l; this.m = m.v; this.r = r; break;
            // statement: l == bool
            // l true: m == AST, r == AST
            // l false: m == AST, r == undefined
            case 4: this.l = l; this.m = m; this.r = r; break;
            // unary operation: l == Token (tt == 3), m == AST, r == undefined
            case 5: this.l = l.v; this.m = m; break;
            // indexing operation: l == AST, m == AST
            case 6: this.l = l; this.m = m; break;
            // function call (lvalue): l == AST, m == Array of AST, r == bool (square brackets?)
            case 7: this.l = l; this.m = m; this.r = r; break;
            // function call (non-lvalue): l == AST, m == Array of AST, r == bool (square brackets?)
            case 8: this.l = l; this.m = m; this.r = r; break;
            default: dl("error: invalid AST node type " + ts);
        }
        this.ts = ts;
        this.len = len;
    }
    
    // de is an object for variables
    // wv is the AST for the value to write
    // returns the evaluated value saved on success or null on failure
    lvalueWrite(de, wv) {
        switch (this.ts) {
            // identifier: write to variable
            case 1:
                const ewv = wv.evaluate(de);
                de[this.v] = ewv;
                return ewv;
            // literal, binary operation, statement, unary operator: invalid
            case 2:
            case 3:
            case 4:
            case 5:
                return null;
            // indexing operation: write to indexed position
            case 6:
                let oldv, ind;
                try {
                    oldv = this.l.evaluate(de);
                    ind = this.m.evaluate(de);
                } catch (err) {
                    throw err;
                }
                if (isArray(oldv) && oldv[ind - 1] != null) {
                    const er = wv.evaluate(de);
                    ind = ind.mag();
                    if (er.length == 1) {
                        oldv[ind - 1] = er[0];
                        return this.l.lvalueWrite(de, { "evaluate": () => oldv });
                    } else {
                        throw `cannot insert vector ${fts(er)} into ${fts(oldv)} as a scalar`;
                    }
                } else {
                    throw `index ${fts(ind + 1)} out of range for vector ${fts(oldv)}`;
                }
                break;
            // function call: add case to corresponding function
            case 7:
            case 8:
                let oldf;
                try {
                    oldf = this.l.evaluate(de);
                } catch (err) {
                    oldf = null;
                }
                if (oldf && oldf.constructor === MathsFunc) {
                    oldf.addCase([this.m, function(args, ide) {
                        const tde = Object.fromEntries(Object.entries(ide));
                        for (const ak in args) {
                            tde[ak] = args[ak];
                        }
                        return wv.evaluate(tde);
                    }], de, false);
                    return oldf;
                // don't know what to do in this case, but it's a possibility
                } else if (oldf && oldf.constructor == Function) {
                } else if (oldf && oldf.constructor == Array) {
                    let ind;
                    try {
                        // TODO: handle multi-indexing
                        ind = this.m[0].evaluate(de);
                    } catch (err) {
                        throw err;
                    }
                    if (oldf[ind - 1] != null) {
                        const er = wv.evaluate(de);
                        ind = ind.mag();
                        oldf[ind - 1] = er;
                        return this.l.lvalueWrite(de, { "evaluate": () => oldf });
                    } else {
                        throw `index ${fts(ind + 1)} out of range for vector ${fts(oldf)}`;
                    }
                } else {
                    const confn = false ?
                        new MathsFunc([[this.m, function(args, ide) {
                            const wvc = wv.clone();
                            for (const ak in args) {
                                wvc.substitute(ak, args[ak]);
                            }
                            const tde = Object.fromEntries(Object.entries(ide));
                            return wvc.evaluate(tde);
                        }]], de, true) :
                        new MathsFunc([[this.m, function(args, ide) {
                            const tde = Object.fromEntries(Object.entries(ide));
                            for (const ak in args) {
                                tde[ak] = args[ak];
                            }
                            return wv.evaluate(tde);
                        }]], de, false);
                    return this.l.lvalueWrite(de, { "evaluate": () => confn });
                }
                break;
            default:
                return null;
        }
    }
    
    // de is an object for variables
    evaluate(de) {
        let ret;
        switch (this.ts) {
            // identifier: get variable value
            case 1:
                const dev = de[this.v];
                if (dev != null) {
                    return dev;
                } else {
                    throw `variable ${this.v} not found`;
                }
                break;
            // literal: return scalar
            case 2:
                const pf = parseFloat(this.v);
                return NumericType.ify(pf);
            // binary operation: evaluate operands and combine
            case 3:
                // maplet is anonymous function
                if (this.m == 10) {
                    let csat = this.l;
                    const csal = [];
                    while (csat.ts == 3 && csat.m == 8) {
                        csal.unshift(csat.r);
                        csat = csat.l;
                    }
                    csal.unshift(csat);
                    const mfn = new MathsFunc([[csal, (args, ide) => {
                        const tde = Object.fromEntries(Object.entries(ide));
                        for (const ek in de) {
                            tde[ek] = de[ek];
                        }
                        for (const ak in args) {
                            tde[ak] = args[ak];
                        }
                        return this.r.evaluate(tde);
                    }]], de, false);
                    return mfn;
                }
                // equal sign is assignment
                if (this.m == 11) {
                    return this.l.lvalueWrite(de, this.r);
                }
                let a;
                let b;
                try {
                    a = this.l.evaluate(de);
                    b = this.r.evaluate(de);
                } catch (err) {
                    throw err;
                }
                if (a.constructor == AST || b.constructor == AST) {
                    return new AST(3, a, { v: this.m }, b);
                }
                switch (this.m) {
                    case 0: ret = vecOp(a, b, (x, y) => NumericType.ify(x).add(NumericType.ify(y))); break;
                    case 1: ret = vecOp(a, b, (x, y) => NumericType.ify(x).sub(NumericType.ify(y))); break;
                    case 2: ret = vecOp(a, b, (x, y) => NumericType.ify(x).mul(NumericType.ify(y))); break;
                    case 3: ret = vecOp(a, b, (x, y) => NumericType.ify(x).div(NumericType.ify(y))); break;
                    // exponent
                    case 4: ret = vecOp(a, b, (x, y) => NumericType.ify(x).pow(NumericType.ify(y))); break;
                    // base x logarithm
                    case 5: ret = vecOp(a, b, (x, y) => NumericType.ify(y).log(NumericType.ify(x))); break;
                    case 6: ret = vecOp(a, b, (x, y) => NumericType.ify(x).eq(NumericType.ify(y))); break;
                    // yth root
                    case 7: ret = vecOp(a, b, (x, y) => NumericType.ify(y).pow(NumericType.ify(x).recip())); break;
                    // comma of vector joining
                    case 8:
                        ret = (tensorRank(b) + 1 <= tensorRank(a)) ?
                            a.concat([b]) : [a, b];
                        break;
                    case 9: ret = vecOp(a, b, (x, y) => NumericType.ify(x).lt(NumericType.ify(y))); break;
                    case 12:
                        if (a.rangeTo && b.rangeTo) {
                            ret = a.rangeTo(b);
                        } else if (isArray(a) && isArray(b)) {
                            ret = a.concat(b);
                        } else {
                            ret = null;
                        }
                        break;
                    default: ret = dl("error: unrecognised operator id " + this.m);
                }
                if (ret == null || anyNaN(ret)) {
                    throw `operation ${OPS[this.m]} between ${fts(a)} and ${fts(b)} failed`;
                } else {
                    return ret;
                }
                break;
            // statement: assign after evaluation or just evaluate
            case 4:
                return this.l ?
                    this.m.lvalueWrite(de, this.r) :
                    this.m.evaluate(de);
            // unary operator: evaluate operand and modify
            case 5:
                let c;
                try {
                    c = this.m.evaluate(de);
                } catch (err) {
                    throw err;
                }
                switch (this.l) {
                    case 0: ret = c; break;
                    case 1: ret = vecOp(c, 0, (x, _y) => NumericType.ify(x).neg()); break;
                    // unary * is undefined
                    case 2: ret = null; break;
                    case 3: ret = vecOp(c, 0, (x, _y) => NumericType.ify(x).recip()); break;
                    case 4: ret = vecOp(c, 0, (x, _y) => NumericType.ify(x).exp()); break;
                    case 5: ret = vecOp(c, 0, (x, _y) => NumericType.ify(x).ln(x)); break;
                    case 6: ret = vecOp(c, 0, (x, _y) => NumericType.ify(x).eq(NumericType.zero())); break;
                    case 7: ret = vecOp(c, 0, (x, _y) => NumericType.ify(x).sqrt()); break;
                    // unary , is undefined
                    case 8: ret = null; break;
                    case 9: ret = vecOp(c, 0, (x, _y) => NumericType.ify(x).isNeg()); break;
                    // unary => is undefined
                    case 10: ret = null; break;
                    // unary = is undefined
                    case 11: ret = null; break;
                    case 12: ret = [c]; break;
                    default: ret = dl("error: unrecognised operator id " + this.l);
                }
                if (ret == null || anyNaN(ret)) {
                    throw `operation ${OPS[this.l]} on ${fts(c)} failed`;
                } else {
                    return ret;
                }
                break;
            // indexing: evaluate vector and index, access vector element
            case 6:
                let v, i;
                try {
                    v = this.l.evaluate(de);
                    i = this.m.evaluate(de);
                } catch (err) {
                    throw err;
                }
                i = i.mag();
                if (!isArray(v)) {
                    throw `${fts(v)} cannot be indexed`;
                } else if (v[i - 1] == null) {
                    throw `index ${fts(i)} out of range for vector ${fts(v)}`;
                } else {
                    return v[i - 1];
                }
                break;
            // function call: call function on arguments
            case 7:
            case 8:
                const f = this.l.evaluate(de);
                if (f && f.apply) {
                    const args = this.m.map(x => (this.r ? x : x.evaluate(de)));
                    return f.apply(f, [args, de]);
                } else if (f && f.constructor == Array) {
                    // TODO: handle multi-indexing
                    const args = this.m.map(x => x.evaluate(de));
                    const i = args[0].mag ? args[0].mag() - 1 : null;
                    if (f[i] == null) {
                        throw `index ${fts(i + 1)} out of range for vector ${fts(f)}`;
                    } else {
                        return f[i];
                    }
                } else {
                    throw f ? `${fts(f)} is not a function or vector` : "function not found";
                }
                break;
            default:
                return null;
        }
    }
    
    // deep-copy this AST
    clone() {
        let cl, cm, cr;
        switch (this.ts) {
            case 1: case 2: cl = { v: this.v }; break;
            case 3: cl = this.l.clone(); cm = { v: this.m }; cr = this.r.clone(); break;
            case 4: cl = this.l; cm = this.m.clone(); cr = this.r && this.r.clone(); break;
            case 5: cl = { v: this.v }; cm = this.m; break;
            case 6: cl = this.l.clone(); cm = this.m.clone(); break;
            // function call (lvalue): l == AST, m == Array of AST, r == bool (square brackets?)
            case 7: case 8: cl= this.l.clone(); cm = this.m.map(a => a.clone()); cr = this.r; break;
            default: dl("error: invalid AST node type " + ts);
        }
        const ra = new AST(this.ts, cl, cm, cr, this.len);
        return ra;
    }
    
    // replace all instances of variable name x with AST expression y
    substitute(x, y) {
        switch (this.ts) {
            // identifier
            case 1:
                if (this.v == x) {
                    this.ts = y.ts;
                    this.v = y.v;
                    this.l = y.l;
                    this.m = y.m;
                    this.r = y.r;
                }
                break;
            // literal
            case 2: break;
            // operation
            case 3: this.l.substitute(x, y); this.r.substitute(x, y); break;
            // statement
            case 4: this.m.substitute(x, y); this.l && this.r.substitute(x, y); break;
            // unary operation
            case 5: this.m.substitute(x, y); break;
            // indexing operation
            case 6: this.l.substitute(x, y); this.m.substitute(x, y); break;
            // function call (lvalue)
            case 7: case 8: this.l.substitute(x, y); this.m.forEach(a => a.substitute(x, y)); break;
            default: dl("error: invalid AST node type " + this.ts);
        }
    }
    
    // convert this AST to postfix expression notation
    // not used in vecalc, and out of date wrt new syntactical structures
    toPostfix() {
        switch (this.ts) {
            case 1:
            case 2:
                return "" + this.v;
            case 3:
                return this.l.toPostfix() + " " +
                    this.r.toPostfix() + " " + OPS[this.m];
            case 4:
                return this.l ?
                    (this.m.toPostfix() + " " + this.r.toPostfix() + " =") :
                    this.m.toPostfix();
        }
    }
    
    // string representation of the AST -- the inverse of parsing
    toString() {
        switch (this.ts) {
            case 1:
            case 2:
                return `${this.v}`;
            case 3:
                return `(${this.l} ${OPS[this.m]} ${this.r})`;
            case 4:
                return this.l ? `${this.m} = ${this.r}` : `${this.m}`;
            case 5:
                return `${OPS[this.l]}(${this.m})`;
            case 6:
                return `${this.l}[${this.m}]`;
            case 7:
            case 8:
                return `${this.l}(${this.m.map(x => x.toString()).join(", ")})`;
        }
    }
}