Stacky Language (For Educational Purposes) V.3 – With Stack Machine Back-End

stacky-lang-v3.js

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

'use strict'

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

function replicate (times, n) {
    let arr = []
    if (times <= 0) { return arr }
    arr.push (n)
    return arr.concat (replicate (times - 1, n))
}

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

const exampleProgram = [

    ['function', 'replicate', ['times', 'n'], [                          // function replicate (times, n) {

        ['let', 'arr', ['[]']],                                              // let arr = []

        ['if', ['<=', 'times', 0], [                                         // if (times <= 0) {
            ['return', 'arr']                                                //     return arr
        ]],                                                                  // }

        ['push', 'arr', 'n'],                                                // arr.push (n)

        ['return', ['concat', 'arr', ['replicate', ['-', 'times', 1], 'n']]] // return arr.concat (replicate (times - 1, n))
    ]],

    ['console.log', ['replicate', 5, 2]] // console.log (replicate (5, 2))
]

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

function* transpile (...exprs) {

    for (const x of exprs) {
            
        if (!Array.isArray (x)) {
            yield x

        } else {
            const [key, ...what] = x
            switch (key) {
                case 'function': {
                    const [name, params, body] = what
                    yield ['function', name, params, [...transpile (...body)]]
                    break
                }
                case 'if': {
                    const [condition, body] = what
                    yield undefined // обозначает окончание списка аргументов
                    yield* transpile (condition)
                    yield ['if', [...transpile (...body)]]
                    break
                }
                case 'let': {
                    const [name, value] = what
                    yield undefined // обозначает окончание списка аргументов
                    yield* transpile (value)
                    yield ['let', name]
                    break
                }
                default: { // return, function calls...
                    yield undefined                       // обозначает окончание списка аргументов
                    yield* transpile (...what.reverse ()) // загружает аргументы на стек в обратном порядке
                    yield key
                }
            }
        }
    }
}

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

console.dir ([...transpile (...exampleProgram)], { depth: null })

/*

[
  [
    'function',
    'replicate',
    [ 'times', 'n' ],
    [
      undefined,
      undefined,
      '[]',
      [ 'let', 'arr' ],
      undefined,
      undefined,
      0,
      'times',
      '<=',
      [ 'if', [ undefined, 'arr', 'return' ] ],
      undefined,
      'n',
      'arr',
      'push',
      undefined,
      undefined,
      undefined,
      'n',
      undefined,
      1,
      'times',
      '-',
      'replicate',
      'arr',
      'concat',
      'return'
    ]
  ],
  undefined,
  undefined,
  2,
  5,
  'replicate',
  'console.log'
]

*/

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

function interpret (program) {

    const builtinFunctions = {
        '<=' (a, b)             { return a <= b },
        '-' (a, b)              { return a - b },
        '[]' (...elements)      { return elements },
        push (array, value)     { array.push (value) },
        concat (a, b)           { return a.concat (b) },
        'console.log' (...args) { console.log (...args) }
    }

    const userFunctions = {}

    // current stack frame
    let currentStatements = program
    let currentStatementIndex = 0
    let currentDepth = 0
    let localVariables = {}
    let isFunction = true
    
    const stack = []

    function pushFrame (newFrame) {

        if (stack.length > 10000) throw new Error ('stack overflow!')

        stack.push ({ currentStatements, currentStatementIndex, currentDepth, localVariables, isFunction })

        ;({ currentStatements, currentStatementIndex = 0, currentDepth = currentDepth+1, localVariables = {}, isFunction = false } = newFrame)
    }

    function popFrame () {

        const [prevFrame, ...values] = [...popUntil (x => x && x.currentStatements)].reverse ()

        ;({ currentStatements, currentStatementIndex, currentDepth, localVariables, isFunction } = prevFrame)

        for (const x of values) stack.push (x)
    }

    function* popUntil (fn) {
        while (stack.length) {
            const x = stack.pop ()
            yield x
            if (fn (x)) return
        }
        throw new Error ('stack underflow!')
    }

    function popArguments () { return [...popUntil (x => x === undefined)].slice (0, -1) }
    function popArgument ()  { return popArguments ()[0] }

    while (true) {

        const x = currentStatements[currentStatementIndex++]

        if (x !== undefined) console.log ('→' + '  '.repeat (currentDepth), x)

        if (!Array.isArray (x)) {

            if (typeof x !== 'string') {
                stack.push (x)

            } else if (x === 'return') {

                // Q: How do we know if there is a return value on the stack?
                //
                // A: We don't! We don't need it here, because it is the calling side who is suppose to take care
                //    of extracting the value from the stack (if there is expected any)...

                while (!isFunction) popFrame ()
                popFrame ()

            } else if (x in localVariables) {
                stack.push (localVariables[x])

            } else if (x in builtinFunctions) {
                stack.push (builtinFunctions[x] (...popArguments ()))

            } else if (x in userFunctions) {

                const { paramNames, body } = userFunctions[x]
                const args = popArguments ()

                const localVariables = {}
                paramNames.forEach ((name, i) => localVariables[name] = args[i])

                pushFrame ({ currentStatements: body, localVariables, isFunction: true })

            } else {
                throw new Error (`symbol is not defined: ${x}`)
            }

        } else {
            
            const [key, ...what] = x

            switch (key) {

                case 'function': {
                    const [name, paramNames, body] = what
                    userFunctions[name] = { paramNames, body }
                    break
                }

                case 'if': {
                    const [body] = what
                    if (popArgument ()) pushFrame ({ currentStatements: body, localVariables }) 
                    break
                }

                case 'let': {
                    const [name] = what
                    localVariables[name] = popArgument ()
                    break
                }

                default:
                    throw new Error (`unknown instruction: ${key}`)
            }
        }

        if (currentStatementIndex >= currentStatements.length) {

            if (currentDepth > 0) popFrame ()
            else                  break
        }
    }
}

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

interpret ([...transpile (...exampleProgram)])

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