examples/mini_cas.viv

# A mini computer-algebra system in Viv: symbolic computation written with no
# pointers, no strings and no Int values, only arrays of numbers.
#
# Expression trees live in flat arrays (a "tape"), exactly like the reverse-mode
# autodiff example: each node is an opcode plus two child INDICES into the same
# arrays. On that encoding this file does the four things a CAS does:
#
#   eval      one forward pass over the tape (a stack machine without the stack)
#   diff      symbolic differentiation: walk the tape, append derivative nodes
#             (run it twice and you have exact second derivatives -- something
#             finite differences can never give you cleanly)
#   simplify  term rewriting to a fixed point: constant folding, x+0, x*1,
#             x*0, x-x, x/x, exp(const). Node replacement is a union-find
#             style representative array -- rewrite by redirection, not surgery.
#   MDL       complexity of an expression in bits, AI-Feynman style: structure
#             pays log2(alphabet) per node, integer constants are cheap,
#             generic floats are expensive -- which makes SNAPPING 1.9999999
#             to 2 measurably profitable.
#
# log2 is built from scratch at the bottom (the point is that the CAS needs
# (atanh series + range reduction) and verified against known values.

# ── The tape ─────────────────────────────────────────────────────────────────
# opcodes: 0 CONST  1 VAR(x)  2 ADD  3 SUB  4 MUL  5 DIV  6 EXP
e_op = zeros(512)
e_a = zeros(512)
e_b = zeros(512)
e_c = zeros(512)
en = zeros(1)

# union-find representative: rep[k] < k means "node k has been rewritten to rep[k]"
rep = zeros(512)

ev = zeros(512)
dd = zeros(512)
seen = zeros(512)

def reset() {
    en[0] = 0.0
    for i to 512 {
        rep[i] = i
    }
}

def push(o, a, b, c) {
    i = en[0]
    e_op[i] = o
    e_a[i] = a
    e_b[i] = b
    e_c[i] = c
    en[0] = i + 1.0
    return i
}

def cst(v) {
    return push(0.0, 0.0, 0.0, v)
}
def vx() {
    return push(1.0, 0.0, 0.0, 0.0)
}