A micro-intrepreter written in plain JavaScript.

micro-interpreter.js

/**
----------------------------------------------------------------
// Interpreter callstack
type CallStack = { vars: { name: string, value: Value }[] }[]
----------------------------------------------------------------
// A runtime value
type Value = Integer | Function | PrimFunction
type Integer = { type: 'Integer', value: int }
type Function = { type: 'Function', args: string[], block: ASTBlock }
type PrimFunction = { type: 'PrimFunction', val: (Value...) => Value }
---------------------------------------------------------------
// Any node in the AST
type ASTNode = ASTBlock | ASTLet | ASTReturn | ASTExpr | ASTFunDef
// "{ instrs... }"
type ASTBlock = { type: 'ASTBlock', instrs: ASTNode[] }
// "(let var value)"
type ASTLet = { type: 'ASTLet', name: string, val: ASTExpr }
// "(return value)"
type ASTReturn = { type: 'ASTReturn', val: ASTExpr }
// "(func f (params...) { instrs... })"
type ASTFunDef = { type: 'ASTFunDef', name: string, args: string[], val: ASTBlock }
// An expression
type ASTExpr = ASTInteger | ASTFunCall
// An integer
type ASTInteger = { type: 'ASTInteger', value: int }
// A function call
type ASTFunCall = { type: 'ASTFunCall', name: string, args: ASTExpr[] }
// An identifier
type ASTId = { type: 'ASTId', name: string }
*/

function add(args/*: Value... */)/*: Value */ {
    let accumulator = 0

    for (const integer of args) {
        if (integer.type !== 'Integer')
            continue //! should rather be an error
        accumulator += integer.value
    }

    return { type: 'Integer', value: accumulator }
}

let defaultFunctions = [
    { name: 'print', value: { type: 'PrimFunction', val: console.log }, },
    { name: '+', value: { type: 'PrimFunction', val: add, }, },
]

let callStack/*: CallStack */ = [ { vars: defaultFunctions } ]

//--------------------------------------------------------------------------

function evalProgram(p/*: ASTBlock */)/*: undefined */ {
    evalBlock(p)
    return undefined
}

function evalBlock(b/*: ASTBlock */)/*: (Value|undefined, bool) */ {
    if (typeof this.instrEvaluators === 'undefined') {
        this.instrEvaluators =
            new Map()
                .set('ASTBlock', evalBlock)
                .set('ASTLet', evalLet)
                .set('ASTReturn', evalReturn)
                .set('ASTFunDef', evalFunDef)
                // all expressions
                .set('ASTInteger', (i) => [evalExpr(i), false])
                .set('ASTFunCall', (i) => [evalExpr(i), false])
                .set('ASTId', (i) => [evalExpr(i), false])
    }

    for (const inst of b.instrs) {
        const res = this.instrEvaluators.get(inst.type)(inst)

        if (res[1]) {
            return res
        }
    }
    return [undefined, false]
}

function evalFunDef(f/*: ASTFunDef */)/*: (undefined, bool) */ {
    let currentStackFrame = callStack[callStack.length - 1]

    currentStackFrame.vars.push({ name: f.name, value: { type: 'Function', args: f.args, block: f.val } })
    return [undefined, false]
}


function evalLet(l/*: ASTLet */)/*: (undefined, bool) */ {
    let currentStackFrame = callStack[callStack.length - 1]

    currentStackFrame.vars.push({ name: l.name, value: evalExpr(l.val) })
    return [undefined, false]
}

function evalReturn(r/*: ASTReturn */)/*: (Value, bool) */ {
    return [evalExpr(r.val), true]
}

function evalExpr(e/*: ASTExpr */)/*: Value|undefined */ {
    if (typeof this.exprEvaluators === 'undefined') {
        this.exprEvaluators =
            new Map()
                .set('ASTInteger', evalInteger)
                .set('ASTFunCall', evalFunCall)
                .set('ASTId', evalId)
    }

    return this.exprEvaluators.get(e.type)(e)
}

function evalInteger(i/*: ASTInteger */)/*: Value */ {
    return { type: 'Integer', value: i.value }
}

function evalFunCall(c/*: ASTFunCall */)/*: Value|undefined */ {
    let varMap = new Map()
    for (const stackFrame of callStack) {
        for (const variable of stackFrame.vars) {
            varMap.set(variable.name, variable.value)
            // Map.prototype.set() overrides the value at the given key if already present
        }
    }

    if (typeof this.valueEvaluators === 'undefined') {
        this.valueEvaluators =
            new Map()
                .set('Integer', (i, _) => i) //! should rather be an error
                .set('PrimFunction', evalPrimFunction)
                .set('Function', evalFunction)
    }

    let fun = varMap.get(c.name)
    return this.valueEvaluators.get(fun.type)(fun, c.args)
}

function evalId(id/*: ASTId */)/*: Value */ {
    let varMap = new Map()
    for (const stackFrame of callStack) {
        for (const variable of stackFrame.vars) {
            varMap.set(variable.name, variable.value)
            // Map.prototype.set() overrides the value at the given key if already present
        }
    }

    return varMap.get(id.name)
}

function evalPrimFunction(fun/* PrimFunction */, args/*: ASTExpr[]|undefined */)/*: Value */ {
    return fun.val(...(args || []).map(evalExpr))
}

function evalFunction(fun/*: Function */, args/* ASTExpr[]|undefined */)/*: Value|undefined */ {
    let bindings = fun.args.map((name, i) => ({ name, value: evalExpr(args[i]) }))

    callStack.push({ vars: bindings })
    let val = evalBlock(fun.block)
    callStack.pop()

    return val[0]
}

//-----------------------------------------------------------------------
//----------------------------- TEST ------------------------------------
//-----------------------------------------------------------------------

let program = {
    type: 'ASTBlock',
    instrs: [
        {
            type: 'ASTLet',
            name: 'i',
            val: { type: 'ASTInteger', value: 10 }
        },
        {
            type: 'ASTFunDef',
            name: 'length',
            args: [ 'el', ],
            val: {
                type: 'ASTBlock',
                instrs: [
                    {
                        type: 'ASTLet',
                        name: 'i',
                        val: { type: 'ASTInteger', value: 0 }
                    },
                    { 
                        type: 'ASTReturn', 
                        val: { type: 'ASTId', name: 'i' }
                    }, 
                ],
            },
        },
        {
            type: 'ASTFunCall',
            name: 'print',
            args: [
                {
                    type: 'ASTFunCall',
                    name: 'length',
                    args: [
                        { type: 'ASTInteger', value: 0 },
                        { type: 'ASTInteger', value: 1 },
                    ],
                }
            ],
        },
    ],
}
evalProgram(program)

/*
Input program:
'''
{
  (let i 10)
  (func length (el) {
    (let i 0)
    (return i)
  }
  (print (test 0))
}
'''

Output:
'''
{ type: "Integer", value: 0 }
'''
*/