Building an Interpreter from scratch

1. Compilers crash course

1. Parsers, ASTs, Interpreters and Compilers

词法解析器不检查语法, 而是读取字符, 转为Token{类型type: 字面量(值)value}

static time: 编译(静态)时间; 此时只检验语法和转为中间表示(IR), 还没有执行(求值)

parsers

parsers的实现, 我们可以使用递归下降的语法分析器, 或者使用生成器来生成指定语法的解析器

syntax这个github项目为多种语言(java/go/…)生成解析器, 可以看看

runtime semantics 运行时语义

execution就是执行, 也就是运行时

解释器与编译器

解释器会执行代码, 实现语义, 而编译器不执行代码(而是由虚拟机执行编译后的字节码)

解释器分为: 基于AST(递归)的解释器/字节码解释器(虚拟机), 区别在于程序的格式

编译器主要有:

• 提前编译器(将源代码翻译为另一种语言,如c++的编译器)
• JIT即时编译器(将可能执行的代码编译,如果js的编译器)
• AST转换器(修改AST,大多数语法糖和优化都是在AST级别完成的)

2. AST Interpreters and Virtual Machines

将AST不加处理或简单处理传给解释器进行求值, 得到结果, 解释器求值这个阶段就是运行时

字节码解释器

字节码解释器对比AST解释器, AST树更难遍历(字节码数组可以顺序遍历), 也更占空间(字节码数组)

虚拟机

有堆栈虚拟机和寄存器虚拟机

基于堆栈

基于寄存器

大多数虚拟机是混合类型的, 既有寄存器, 也有堆栈

3. Compilers AOT, JIT, Transpiler

AOT

AOT在代码执行前完全翻译源代码

JIT

JIT就是即时编译, 即时就是运行时, 在程序执行时直接翻译源代码

JIT可以提高重量级编译的性能, 他在求值前, 使用生成器生成(编译出)本机目标代码, 然后交给cpu执行, 如果这段代码需要反复使用,
就会使用到生成器的缓存, 而无需每次都重新编译, 可实现特定优化

AST - Transpiler(Transformer + Compiler)

AST编译器的输出是另一个AST, 可以将特定语言的AST转为另一个语言的AST, 然后交给目标语言的编译器进行求值.
AST编译器可以看作一个纯粹的前端

Bad question

xxx语言是解释或编译语言? -> 其实, 解释或编译不是语言, 而是语言的实现

重要的是语义(保留), 所以我们应该首先实现AST的解释器(最简单的语义实现), 然后可以走得更远, 比如将AST编译为字节码 ->
字节码常用部分使用JIT -> …

第一章的checkpoints

2. Interpreters Basic expressions and Variables

1. Eva programming language

AST并不唯一, 我们可以允许索引代替表达式来进行优化等…

我们将实现 eva语言 的编译器

2. Self-evaluating expressions

const assert = require('assert')

/**
 * Eva interpreter
 */
class Eva {
    eval(exp) {
        if (isNumber(exp)) {
            return exp
        }

        if (isString(exp)) {
            // "hello" -> hello
            return exp.slice(1, -1);
        }

        if (exp[0] === '+') {
            // (+ 1 2) -> 3
            return exp[1] + exp[2]
        }
        throw 'Unimplemented'
    }
}

function isNumber(exp) {
    return typeof exp === 'number'
}

function isString(exp) {
    return typeof exp === 'string' && exp[0] === '"' && exp.slice(-1) === '"'
}

// ----- -----
// tests:
const eva = new Eva();

// Self-evaluating 自求值(评估) -> 对应字面量, 编译器不做处理直接返回字面量本身
assert.strictEqual(eva.eval(1), 1)
assert.strictEqual(eva.eval('"hello"'), 'hello')

assert.strictEqual(eva.eval(['+', 1, 5]), 6)
assert.strictEqual(eva.eval(['+', ['+', 3, 2], 5]), 10)

console.log('All assertions passed!')

3. Variables and Environments

// Eva.js
const assert = require('assert')

const Environment = require('./Environment')

/**
 * Eva interpreter
 */
class Eva {
    /**
     * Creates an Eva instance with the global environment
     */
    constructor(global = new Environment()) {
        this.global = global
    }

    /**
     * Evaluates an expression in the given environment
     * @param exp
     * @param env
     * @return {number|*}
     */
    eval(exp, env = this.global) {
        // -------------------------------------
        // Self-evaluating expressions

        if (isNumber(exp)) {
            return exp
        }

        if (isString(exp)) {
            // "hello" -> hello
            return exp.slice(1, -1);
        }

        // -------------------------------------
        // Math operations

        if (exp[0] === '+') {
            // (+ 1 2) -> 3
            return this.eval(exp[1]) + this.eval(exp[2])
        }

        if (exp[0] === '*') {
            // (+ 1 2) -> 3
            return this.eval(exp[1]) * this.eval(exp[2])
        }

        // -------------------------------------
        // Variable declaration

        if (exp[0] === 'var') {
            const [_, name, value] = exp
            return env.define(name, this.eval(value))
        }

        // -------------------------------------
        // Variable access

        if (isVariableName(exp)) {
            return env.lookup(exp)
        }

        throw `Unimplemented: ${JSON.stringify(exp)}`
    }
}

function isNumber(exp) {
    return typeof exp === 'number'
}

function isString(exp) {
    return typeof exp === 'string' && exp[0] === '"' && exp.slice(-1) === '"'
}

function isVariableName(exp) {
    return typeof exp === 'string' && /^[a-zA-Z][a-zA-Z0-9_]*$/.test(exp)
}

// ----- -----
// tests:
const eva = new Eva(new Environment({
    null: null,

    true: true,
    false: false,

    VERSION: '0.1'
}))

// Self-evaluating 自求值(评估) -> 对应字面量, 编译器不做处理直接返回字面量本身
assert.strictEqual(eva.eval(1), 1)
assert.strictEqual(eva.eval('"hello"'), 'hello')

// Math
assert.strictEqual(eva.eval(['+', 1, 5]), 6)
assert.strictEqual(eva.eval(['+', ['+', 3, 2], 5]), 10)
assert.strictEqual(eva.eval(['+', ['*', 3, 2], 5]), 11)

// Variables
assert.strictEqual(eva.eval(['var', 'x', 10]), 10)
assert.strictEqual(eva.eval('x'), 10)

assert.strictEqual(eva.eval(['var', 'y', 100]), 100)
assert.strictEqual(eva.eval('y'), 100)

assert.strictEqual(eva.eval('VERSION'), '0.1')

assert.strictEqual(eva.eval(['var', 'isUser', 'true']), true)

assert.strictEqual(eva.eval(['var', 'z', ['*', 2, 2]]), 4)

console.log('All assertions passed!')

// Environment.js
/**
 * Environment: names storage
 */
class Environment {
    /**
     * Creates an environment with the given record.
     */
    constructor(record = {}) {
        this.record = record
    }

    /**
     * Create a variable with the given name and value.
     * @param name
     * @param value
     */
    define(name, value) {
        this.record[name] = value
        return value
    }

    /**
     * Returns the value of a defined variable, or throws
     * if the variable is not defined
     */
    lookup(name) {
        // 对象是否有指定名称的属性
        if (!this.record.hasOwnProperty(name)) {
            throw new ReferenceError(`Variable "${name}" is not defined.`)
        }
        return this.record[name]
    }
}

module.exports = Environment

4. Blocks expression groups and Nested Scopes

// Eva.js
const assert = require('assert')

const Environment = require('./Environment')

/**
 * Eva interpreter
 */
class Eva {
    /**
     * Creates an Eva instance with the global environment
     */
    constructor(global = new Environment()) {
        this.global = global
    }

    /**
     * Evaluates an expression in the given environment
     * @param exp
     * @param env
     * @return {number|*}
     */
    eval(exp, env = this.global) {
        // ...

        // -------------------------------------
        // Math operations

        if (exp[0] === '+') {
            // (+ 1 2) -> 3
            return this.eval(exp[1], env) + this.eval(exp[2], env)
        }

        if (exp[0] === '*') {
            // (+ 1 2) -> 3
            return this.eval(exp[1], env) * this.eval(exp[2], env)
        }

        // -------------------------------------
        // Blocks: sequence of expressions

        if (exp[0] === 'begin') {
            // 创建新作用域
            const blockEnv = new Environment({}, env)
            return this._evalBlock(exp, blockEnv)
        }

        // -------------------------------------
        // Variable declaration (var foo 1)

        if (exp[0] === 'var') {
            const [_, name, value] = exp
            return env.define(name, this.eval(value, env))
        }

        // -------------------------------------
        // Variable update (set foo 10)

        if (exp[0] === 'set') {
            const [_, name, value] = exp
            return env.assign(name, this.eval(value, env))
        }

        // -------------------------------------
        // Variable access

        if (isVariableName(exp)) {
            // 当前作用域中找变量
            return env.lookup(exp, env)
        }

        throw `Unimplemented: ${JSON.stringify(exp)}`
    }

    _evalBlock(block, env) {
        let result;

        // tag: exp[0] -> 'begin'
        const [_tag, ...expressions] = block

        expressions.forEach(exp => {
            // 块语句内每条语句进行求值, 在对应的env下
            result = this.eval(exp, env)
        })

        return result
    }
}

// ...

// ----- -----
// tests:
const eva = new Eva(new Environment({
    null: null,

    true: true,
    false: false,

    VERSION: '0.1'
}))

// ...
// Blocks:
assert.strictEqual(eva.eval(
    ['begin',
        ['var', 'x', 10],
        ['var', 'y', 20],

        ['+', ['*', 'x', 'y'], 30],
    ]
), 230)

// 嵌套时应该使用各自的作用域
assert.strictEqual(eva.eval(
    ['begin',
        ['var', 'x', 10],

        // 嵌套块里使用的是嵌套块字节的环境
        ['begin',
            ['var', 'x', 20],
            'x'
        ],
        // 这里用的是外层块语句的环境
        'x'
    ]
), 10)

// 嵌套时, 子作用域应该能访问父作用域里的变量
assert.strictEqual(eva.eval(
    ['begin',
        ['var', 'value', 10],

        ['var', 'result', ['begin',
            ['var', 'x', ['+', 'value', 10]],
            'x'
        ]],

        'result'
    ]
), 20)

assert.strictEqual(eva.eval(
    ['begin',
        ['var', 'data', 10],

        ['begin',
            ['set', 'data', 100],
        ],

        'data'
    ]
), 100)

console.log('All assertions passed!')

// Environment.js
/**
 * Environment: names storage
 */
class Environment {
    /**
     * Creates an environment with the given record.
     */
    constructor(record = {}, parent = null) {
        // kv集合
        this.record = record
        // 父作用域
        this.parent = parent
    }

    // ...

    /**
     * Updates an existing variable
     */
    assign(name, value) {
        this.resolve(name).record[name] = value
        return value
    }

    /**
     * Returns the value of a defined variable, or throws
     * if the variable is not defined
     */
    lookup(name) {
        return this.resolve(name).record[name]
    }

    /**
     *  Returns specific environment in which a variable is defined,or
     *  throws if a variable is not defined.
     */
    resolve(name) {
        // 当前环境有目标变量
        if (this.record.hasOwnProperty(name)) {
            return this
        }

        if (this.parent == null) {
            throw new ReferenceError(`Variable "${name}" is not defined.`)
        }
        // 当前环境没有, 从父容器找
        return this.parent.resolve(name)
    }
}

module.exports = Environment

5. Control flow If and While expressions

// __tests__/run-test.js
const Eva = require('../Eva')
const Environment = require("../Environment");

const tests = [
    require('./self-eval-test'),
    require('./math-test'),
    require('./variables-test'),
    require('./block-test'),
    require('./if-test'),
    require('./while-test'),
]
// ----- -----
// tests:
const eva = new Eva(new Environment({
    null: null,

    true: true,
    false: false,

    VERSION: '0.1'
}))

tests.forEach(test => test(eva))

console.log('All assertions passed!')

// Eva.js
const Environment = require('./Environment')

/**
 * Eva interpreter
 */
class Eva {
    /**
     * Creates an Eva instance with the global environment
     */
    constructor(global = new Environment()) {
        this.global = global
    }

    /**
     * Evaluates an expression in the given environment
     * @param exp
     * @param env
     * @return {number|*}
     */
    eval(exp, env = this.global) {
        // ...
        // -------------------------------------
        // Comparison operations

        if (exp[0] === '>') {
            return this.eval(exp[1], env) > this.eval(exp[2], env)
        }
        if (exp[0] === '>=') {
            return this.eval(exp[1], env) >= this.eval(exp[2], env)
        }
        if (exp[0] === '<') {
            return this.eval(exp[1], env) < this.eval(exp[2], env)
        }
        if (exp[0] === '<=') {
            return this.eval(exp[1], env) <= this.eval(exp[2], env)
        }
        if (exp[0] === '==') {
            return this.eval(exp[1], env) === this.eval(exp[2], env)
        }

        // ...

        // -------------------------------------
        // if-expression

        if (exp[0] === 'if') {
            const [_tag, condition, consequent, alternate] = exp
            // 对条件表达式求值, 根据结果进入不同分支
            if (this.eval(condition, env)) {
                return this.eval(consequent, env)
            }
            return this.eval(alternate, env)
        }

        // -------------------------------------
        // while-expression

        if (exp[0] === 'while') {
            const [_tag, condition, body] = exp
            let result
            // 对条件表达式求值, 根据结果进入不同分支
            while (this.eval(condition, env)) {
                result = this.eval(body, env)
            }
            return result
        }

        throw `Unimplemented: ${JSON.stringify(exp)}`
    }
}

// ...

module.exports = Eva

6. Back to parsers S-expression to AST

实现将 字符串 -> s-表达式 的解析器

npm i -g syntax-cli

// __tests__/block-test.js
const assert = require("assert");
const testUtil = require('./test-util')

module.exports = eva => {
    // ...

    testUtil.test(eva, `
        (begin
            (var x 10)
            (var y 20)
            (+ (* x 10) y)
        )
    `, 120)
}

// __tests__/test-util.js
const assert = require("assert");
const evaParser = require("../parser/evaParser");

function test(eva, code, expected) {
    const exp = evaParser.parse(code)
    assert.strictEqual(eva.eval(exp), expected)
}

module.exports = {
    test
}

/**
   S-expression parser

   Atom: 42, foo, bar, "Hello"

   List: (), (+ 5 x), (print "hello")
 */

// -----------------------------
// Lexical grammar (tokens):

%lex

%%

\s+                     /* skip whitespace */

\"[^\"]*\"              return 'STRING'

\d+                     return 'NUMBER'

[\w\-+*=<>/]+           return 'SYMBOL'

/lex

// ------------------------------
// Syntactic grammer (BNF):

%%

Exp
    : Atom
    | List
    ;

// 最简单的表达式, 是数字　字符串和符号
Atom
    : NUMBER { $$ = Number($1) } // 转为实际的数字
    | STRING
    | SYMBOL
    ;

// 复杂表达式
List
    // $$ 表示返回值
    // 返回$2 - ListEntries
    : '(' ListEntries ')' { $$ = $2 }
    ;

// (Exp Exp Exp ...)

// ListEntries Exp
// ListEntries Exp Exp
// ListEntries Exp Exp Exp ...

ListEntries
    : ListEntries Exp { $1.push($2); $$ = $1 }
    | /* empty */ { $$ = [] }
    ;

syntax-cli --grammar parser/eva-grammar.bnf --mode LALR1 --parse '42' --tokenize
syntax-cli --grammar parser/eva-grammar.bnf --mode LALR1 --parse '"hello" '--tokenize
syntax-cli --grammar parser/eva-grammar.bnf --mode LALR1 --parse 'foo' --tokenize
syntax-cli --grammar parser/eva-grammar.bnf --mode LALR1 --parse '(+ 5 foo)' --tokenize
syntax-cli --grammar parser/eva-grammar.bnf --mode LALR1 --parse '(begin (var x 10) (var y 20) (+ x y))' --tokenize
syntax-cli --grammar parser/eva-grammar.bnf --mode LALR1 --output parser/evaParser.js

3. Functions and Functional programming

1. Built-in and Native functions

// Eva.js
const Environment = require('./Environment')

/**
 * Eva interpreter
 */
class Eva {
    /**
     * Creates an Eva instance with the global environment
     */
    // constructor(global = new Environment()) {
    constructor(global = GlobalEnvironment) {
        this.global = global
    }

    /**
     * Evaluates an expression in the given environment
     * @param exp
     * @param env
     * @return {number|*}
     */
    eval(exp, env = this.global) {
        // -------------------------------------
        // Self-evaluating expressions

        if (this._isNumber(exp)) {
            return exp
        }

        if (this._isString(exp)) {
            // "hello" -> hello
            return exp.slice(1, -1);
        }

        // -------------------------------------
        // Blocks: sequence of expressions

        if (exp[0] === 'begin') {
            // 创建新作用域
            const blockEnv = new Environment({}, env)
            return this._evalBlock(exp, blockEnv)
        }

        // -------------------------------------
        // Variable declaration (var foo 1)

        if (exp[0] === 'var') {
            const [_, name, value] = exp
            return env.define(name, this.eval(value, env))
        }

        // -------------------------------------
        // Variable update (set foo 10)

        if (exp[0] === 'set') {
            const [_, name, value] = exp
            return env.assign(name, this.eval(value, env))
        }

        // -------------------------------------
        // Variable access

        if (this._isVariableName(exp)) {
            // 当前作用域中找变量
            return env.lookup(exp, env)
        }

        // -------------------------------------
        // if-expression

        if (exp[0] === 'if') {
            const [_tag, condition, consequent, alternate] = exp
            // 对条件表达式求值, 根据结果进入不同分支
            if (this.eval(condition, env)) {
                return this.eval(consequent, env)
            }
            return this.eval(alternate, env)
        }

        // -------------------------------------
        // while-expression

        if (exp[0] === 'while') {
            const [_tag, condition, body] = exp
            let result
            // 对条件表达式求值, 根据结果进入不同分支
            while (this.eval(condition, env)) {
                result = this.eval(body, env)
            }
            return result
        }

        // -------------------------------------
        // function calls:
        //      (print "hello")
        //      (+ x 5)
        //      (> foo bar)

        if (Array.isArray(exp)) {
            // 在全局查找第一个标识符, 运算符或内置函数
            const fn = this.eval(exp[0], env)

            const args = exp.slice(1).map(arg => this.eval(arg, env))

            // 1. native function
            if (typeof fn === 'function') {
                return fn(...args)
            }

            // 2. user-defined function
            // todo
        }

        throw `Unimplemented: ${JSON.stringify(exp)}`
    }

    _evalBlock(block, env) {
        let result;

        // tag: exp[0] -> 'begin'
        const [_tag, ...expressions] = block

        expressions.forEach(exp => {
            // 块语句内每条语句进行求值, 在对应的env下
            result = this.eval(exp, env)
        })

        return result
    }

    _isNumber(exp) {
        return typeof exp === 'number'
    }

    _isString(exp) {
        return typeof exp === 'string' && exp[0] === '"' && exp.slice(-1) === '"'
    }

    _isVariableName(exp) {
        return typeof exp === 'string' && /^[+\-*/<>=a-zA-Z0-9_]*$/.test(exp)
    }
}

/**
 * Default Global Environment
 */
const GlobalEnvironment = new Environment({
    null: null,

    true: true,
    false: false,

    VERSION: '0.1',

    // operators
    '+'(op1, op2) {
        return op1 + op2
    },
    '-'(op1, op2 = null) {
        if (op2 == null) {
            return -op1
        }
        return op1 - op2
    },
    '*'(op1, op2) {
        return op1 * op2
    },
    '/'(op1, op2) {
        return op1 / op2
    },
    '%'(op1, op2) {
        return op1 % op2
    },

    // Comparison:
    '>'(op1, op2) {
        return op1 > op2
    },
    '>='(op1, op2) {
        return op1 >= op2
    },
    '<'(op1, op2) {
        return op1 < op2
    },
    '<='(op1, op2) {
        return op1 <= op2
    },
    '=='(op1, op2) {
        return op1 === op2
    },
    '!='(op1, op2 = null) {
        if (op2 == null) {
            return !op1
        }
        return op1 !== op2
    },

    // Console output:
    print(...args) {
        console.log(...args)
    },
})

module.exports = Eva

const Eva = require('../Eva')
const Environment = require("../Environment");

const tests = [
    require('./self-eval-test'),
    require('./math-test'),
    require('./variables-test'),
    require('./block-test'),
    require('./if-test'),
    require('./while-test'),
    require('./built-in-function-test'),
]
// ----- -----
// tests:
const eva = new Eva()

tests.forEach(test => test(eva))

eva.eval(['print', '"hello"', '"world"'])

console.log('All assertions passed!')

// __tests__/built-in-function-test.js
const {test} = require('./test-util')

module.exports = eva => {
    // Math functions
    test(eva, `(+ 1 5)`, 6)
    test(eva, `(+ (+ 2 3) 5)`, 10)
    test(eva, `(+ (* 2 3) 5)`, 11)

    // Comparison
    test(eva, `(> 1 5)`, false)
    test(eva, `(< 1 5)`, true)

    test(eva, `(>= 5 5)`, true)
    test(eva, `(<= 5 5)`, true)
    test(eva, `(== 5 5)`, true)
}

2. User-defined functions, Activation Records and Closures

// __tests__/user-defined-function-test.js
const assert = require('assert')
const {test} = require('./test-util')

module.exports = eva => {
    test(eva, `
        (begin
            (def square (x)
                (* x x)
            )
            (square 2)
        )
    `, 4)

    test(eva, `
        (begin
            (def calc (x y)
                (begin
                    (var z 30)
                    (+ (* x y) z)
                )
            )
            (calc 10 20)
        )
    `, 230)

    // Closure
    test(eva, `
        (begin
            (var value 100)
            (def calc (x y)
                (begin
                    (var z (+ x y))
                    (def inner (foo)
                        (+ (+ foo z) value)
                    )
                    inner
                )
            )    
            (var fn (calc 10 20))
            (fn 30)
        )
    `, 160)
}

class Eva {
    /**
     * Creates an Eva instance with the global environment
     */
    // constructor(global = new Environment()) {
    constructor(global = GlobalEnvironment) {
        this.global = global
    }

    /**
     * Evaluates an expression in the given environment
     * @param exp
     * @param env
     * @return {number|*}
     */
    eval(exp, env = this.global) {
        // ...

        // -------------------------------------
        // function declaration: (def square (x) (* x x))
        if (exp[0] === 'def') {
            const [_tag, name, params, body] = exp

            const fn = {
                params,
                body,
                env, // Closure!
            }

            return env.define(name, fn)
        }

        // -------------------------------------
        // function calls:
        //      (print "hello")
        //      (+ x 5)
        //      (> foo bar)

        if (Array.isArray(exp)) {
            // 在全局查找第一个标识符, 运算符或内置函数
            const fn = this.eval(exp[0], env)

            const args = exp.slice(1).map(arg => this.eval(arg, env))

            // 1. native function
            if (typeof fn === 'function') {
                return fn(...args)
            }

            // 2. user-defined function
            const activationRecord = {}

            fn.params.forEach((param, index) => {
                activationRecord[param] = args[index]
            })

            const activationEnv = new Environment(
                activationRecord,
                fn.env // static scope!
            )

            return this._evalBody(fn.body, activationEnv)
        }

        throw `Unimplemented: ${JSON.stringify(exp)}`
    }

    _evalBody(body, env) {
        if (body[0] === 'begin') {
            return this._evalBlock(body, env)
        }
        return this.eval(body, env)
    }

    // ...
}

3. Lambda functions and Functional programming

// Eva.js
const Environment = require('./Environment')

/**
 * Eva interpreter
 */
class Eva {
    // ...

    eval(exp, env = this.global) {
        // ...

        // -------------------------------------
        // function declaration: (def square (x) (* x x))
        // Syntactic sugar for: (var square (lambda (x) (* x x)))
        if (exp[0] === 'def') {
            const [_tag, name, params, body] = exp

            // const fn = {
            //     params,
            //     body,
            //     env, // Closure!
            // }
            // JIT-transpile to a variable declaration
            const varExp = ['var', name, ['lambda', params, body]]

            return this.eval(varExp, env)
            // return env.define(name, fn)
        }

        // -------------------------------------
        // lambda function: (lambda (x) (* x x))
        if (exp[0] === 'lambda') {
            const [_tag, params, body] = exp

            return {
                params,
                body,
                env, // Closure!
            }
        }

        // ...

        throw `Unimplemented: ${JSON.stringify(exp)}`
    }

    // ...
}

// ...

module.exports = Eva

// __tests__/lambda-function-test.js
const assert = require("assert");
const {test} = require("./test-util");

module.exports = eva => {
    test(eva, `
        (begin
            (def onClick (callback)
                (begin
                    (var x 10)   
                    (var y 20)
                    (callback (+ x y))   
                )
            )
            (onClick (lambda (data) (* data 10)))
        )
    `, 300)

    // Immediately-invoked lambda expression - IILE:
    // fn = this.eval(exp[0],env) -> 直接调用exp[0](这里的lambda), 传递参数2
    test(eva, `
        ((lambda (x) (* x x)) 2)
    `, 4)

    // Save lambda to a variable:
    test(eva, `
        (begin
            (var square (lambda (x) (* x x)))
            (square 2)
        )
    `, 4)
}

4. Call-stack and Recursive calls

每个函数调用都会激活新作用域, 当函数执行结束就销毁

5. Syntactic sugar Switch, For, Inc, Dec operators

// __tests__/for-test.js
const {test} = require('./test-util')

module.exports = eva => {
    test(eva, `
        (for (var x 10) (> x 0) (-- x) (print x)) 
    `, undefined)

    test(eva, `
    (begin
        (var x 1)
        (++ x)
        x
    )
    `, 2)

    test(eva, `
    (begin
        (var x 1)
        (-- x)
        x
    )
    `, 0)

    test(eva, `
    (begin
        (var x 1)
        (+= x 5)
        x
    )
    `, 6)

    test(eva, `
    (begin
        (var x 10)
        (-= x 5)
        x
    )
    `, 5)
}

// transform/Transformer.js
/**
 * AST Transformer
 */
class Transformer {
    /**
     * Translates `def`-expression (function declaration)
     * into a variable declaration with a lambda
     * expression.
     */
    transformDefToLambda(defExp) {
        const [_tag, name, params, body] = defExp
        return ['var', name, ['lambda', params, body]]
    }

    transformDefToIf(switchExp) {
        // (switch condition block)
        const [_tag, ...cases] = switchExp

        const ifExp = ['if', null, null, null]

        let current = ifExp

        for (let i = 0; i < cases.length - 1; i++) {
            const [currentCond, currentBlock] = cases[i]

            current[1] = currentCond
            current[2] = currentBlock

            const next = cases[i + 1]
            const [nextCond, nextBlock] = next

            current[3] = nextCond === 'else'
                ? nextBlock
                : ['if']

            // 递归 构建子if
            current = current[3]
        }

        return ifExp
    }

    transformDefToWhile(forExp) {
        // (for init condition modifier body)
        const [_tag, init, condition, modifier, body] = forExp

        // (begin init (while condition (begin body modifier)))
        return ['begin', init, ['while', condition, ['begin', modifier, body]]];
    }

    // (++ x) -> (set x (+ x 1))
    transformIncToSet(exp) {
        return ['set', exp[1], ['+', exp[1], 1]];
    }

    // (-- x) -> (set x (- x 1))
    transformDecToSet(exp) {
        return ['set', exp[1], ['-', exp[1], 1]];
    }

    // (+= x 1) -> (set x (+ x 1))
    transformIncEqToSet(exp) {
        return ['set', exp[1], ['+', exp[1], exp[2]]];
    }

    // (-= x 1) -> (set x (- x 1))
    transformDecEqToSet(exp) {
        return ['set', exp[1], ['-', exp[1], exp[2]]];
    }
}

module.exports = Transformer

// __tests__/switch-test.js
const {test} = require('./test-util')

module.exports = eva => {
    // Pass
    test(eva, `
    (begin
        (var x 10)
        (switch ((== x 10) 100)
                ((> x 10) 200)
                (else     300))
    )
    `, 100)
}

        // -------------------------------------
        // switch-expression: (switch (cond1 block1) ...)
        // syntactic sugar for nested if-expression
if (exp[0] === 'switch') {
    const ifExp = this._transformer
        .transformDefToIf(exp)

    return this.eval(ifExp, env)
}

// -------------------------------------
// for-loop: (for init condition modifier body)
// syntactic sugar for: (begin init (while condition (begin body modifier)))
if (exp[0] === 'for') {
    const whileExp = this._transformer
        .transformDefToWhile(exp)

    return this.eval(whileExp, env)
}

// -------------------------------------
// increment: (++ for)
// syntactic sugar for: (set foo (+ foo 1))
if (exp[0] === '++') {
    const setExp = this._transformer.transformIncToSet(exp)

    return this.eval(setExp, env)
}

// -------------------------------------
// decrement: (-- for)
// syntactic sugar for: (set foo (+ foo 1))
if (exp[0] === '--') {
    const setExp = this._transformer.transformDecToSet(exp)

    return this.eval(setExp, env)
}

// -------------------------------------
// increment: (+= for x)
// syntactic sugar for: (set foo (+ foo x))
if (exp[0] === '+=') {
    const setExp = this._transformer
        .transformIncEqToSet(exp)

    return this.eval(setExp, env)
}

// -------------------------------------
// decrement: (-= for x)
// syntactic sugar for: (set foo (- foo x))
if (exp[0] === '-=') {
    const setExp = this._transformer
        .transformDecEqToSet(exp)

    return this.eval(setExp, env)
}

4. Object-oriented programming

1. Object-oriented Eva Classes

// -------------------------------------
// Variable update (set foo 10)
if (exp[0] === 'set') {
    const [_, ref, value] = exp

    // (set (prop this x) x)
    if (ref[0] === 'prop') {
        const [_tag, instance, propName] = ref
        const instanceEnv = this.eval(instance, env)

        return instanceEnv.define(
            propName,
            this.eval(value, env)
        )
    }

    return env.assign(ref, this.eval(value, env))
}

// -------------------------------------
// class declaration: (class <Name> <Parent> <Body>)
if (exp[0] === 'class') {
    const [_tag, name, parent, body] = exp

    // A class is an environment --- a storage of methods
    // and shared properties
    const parentEnv = this.eval(parent, env) || env

    const classEnv = new Environment({}, parentEnv)

    // body is evaluated in the class environment
    this._evalBody(body, classEnv)

    // class is accessible by name
    return env.define(name, classEnv)
}

// -------------------------------------
// class instantiation: (new <Class> <Arguments> ...)
if (exp[0] === 'new') {
    const classEnv = this.eval(exp[1], env)

    //An instance of a class is an environment!
    //The parent component of the instance environment
    //is set to its class.
    const instanceEnv = new Environment({}, classEnv)

    const args = exp
        .slice(2) // 去掉前两个(new, <Class>)
        .map(arg => this.eval(arg, env))

    this._callUserDefinedFunction(
        classEnv.lookup('constructor'),
        [instanceEnv, ...args]
    )

    // class is an env
    return instanceEnv
}

// -------------------------------------
// Property access:(prop <instance><name>)
if (exp[0] === 'prop') {
    const [_tag, instance, name] = exp

    const instanceEnv = this.eval(instance, env)

    return instanceEnv.lookup(name)
}

// __tests__/class-test.js
const {test} = require('./test-util')

module.exports = eva => {

    test(eva,
        `
    (class Point null
      (begin

        (def constructor (this x y)
          (begin
            (set (prop this x) x)
            (set (prop this y) y)))

        (def calc (this)
          (+ (prop this x) (prop this y)))))

    (var p (new Point 10 20))

    ((prop p calc) p)

  `,
        30);
};

2. Class inheritance and Super calls

// __tests__/test-util.js
const assert = require("assert");
const evaParser = require("../parser/evaParser");

function test(eva, code, expected) {
    const exp = evaParser.parse(`(begin ${code})`);
    assert.strictEqual(eva.evalGlobal(exp), expected);
}

module.exports = {
    test
}

    /**
 * Evaluates global code wrapping into a block.
 */
// evalGlobal(expressions) {
//     return this._evalBlock(
//         ['block', expressions], this.global
//     )
// }
evalGlobal(exp)
{
    return this._evalBody(exp, this.global);
}

// -------------------------------------
// super expression: (super <ClassName>)
if (exp[0] === 'super') {
    const [_tag, className] = exp
    return this.eval(className, env).parent
}

// __tests__/class-test.js
const {test} = require('./test-util')

module.exports = eva => {

    test(eva,
        `
    (class Point null
      (begin

        (def constructor (this x y)
          (begin
            (set (prop this x) x)
            (set (prop this y) y)))

        (def calc (this)
          (+ (prop this x) (prop this y)))))

    (var p (new Point 10 20))

    ((prop p calc) p)

  `,
        30);

    test(eva,
        `
    (class Point3D Point
      (begin

        (def constructor (this x y z)
          (begin
            ((prop (super Point3D) constructor) this x y)
            (set (prop this z) z)))

        (def calc (this)
          (+ ((prop (super Point3D) calc) this)
             (prop this z)))))

    (var p (new Point3D 10 20 30))

    ((prop p calc) p)

  `,
        60);

};

3. Code isolation Modules and Imports

// moudles/Math.eva
(def abs (value)
  (if (< value 0)
      (- value)
      value))

(def square (x)
  (* x x))

(var MAX_VALUE 1000)

(exports
    abs
    square)

// __tests__/module-test.js
const {test} = require('./test-util');

module.exports = eva => {

    test(eva,
        `
    (module Math
      (begin

        (def abs (value)
          (if (< value 0)
              (- value)
              value))

        (def square (x)
          (* x x))

        (var MAX_VALUE 1000)

      )
    )

    ((prop Math abs) (- 10))

  `,
        10);

    test(eva,
        `
    (var abs (prop Math abs))

    (abs (- 10))

  `,
        10);

    test(eva,
        `
    (prop Math MAX_VALUE)

  `,
        1000);

};

// __tests__/import-test.js
const {test} = require('./test-util');

module.exports = eva => {

    test(eva,
        `
    (import Math)

    ((prop Math abs) (- 10))

  `,
        10);

    test(eva,
        `
    (var abs (prop Math abs))

    (abs (- 10))

  `,
        10);

    test(eva,
        `
    (prop Math MAX_VALUE)

  `,
        1000);

    test(eva,
        `
    (prop Math MAX_VALUE)

  `,
        1000);

};

// -------------------------------------
// module declaration: (module <body>)
if (exp[0] === 'module') {
    const [_tag, name, body] = exp

    const moduleEnv = new Environment({}, env)

    this._evalBody(body, moduleEnv)

    return env.define(name, moduleEnv)
}

// -------------------------------------
// module import: (import <name>)
if (exp[0] === 'import') {
    const [_tag, name] = exp

    const moduleSrc = readFileSync(
        `${__dirname}/modules/${name}.eva`,
        'utf8'
    )

    const body = evaParser.parse(`(begin ${moduleSrc})`)

    const moduleExp = ['module', name, body]

    return this.eval(moduleExp, this.global)
}

4. Final executable and specification

#!/usr/bin/env node
// bin/eva.js
'use strict'

const fs = require("fs");
const evaParser = require("../parser/evaParser")
const Eva = require('../Eva')

function evalGlobal(src, eva) {
    const exp = evaParser.parse(`(begin ${src})`)
    return eva.evalGlobal(exp)
}

function main(argv) {
    const [_node, path, mode, exp] = argv

    const eva = new Eva()

    // direct expression
    if (mode === '-e') {
        return evalGlobal(exp, eva)
    }

    // eva file
    if (mode === '-f') {
        const src = fs.readFileSync(exp, 'utf8')
        return evalGlobal(src, eva)
    }
}

main(process.argv)

(import Math)

(var abs (prop Math abs))

(var x (- 10))

(print (abs x))

(class Point null
  (begin

    (def constructor (this x y)
      (begin
        (set (prop this x) x)
        (set (prop this y) y)))

    (def calc (this)
      (+ (prop this x) (prop this y)))))

(class Point3D Point
  (begin

    (def constructor (this x y z)
      (begin
        ((prop (super Point3D) constructor) this x y)
        (set (prop this z) z)))

    (def calc (this)
      (+ ((prop (super Point3D) calc) this) (prop this z)))))

(var p (new Point3D 10 20 30))

(print "Value:" ((prop p calc) p))

// TODO:

- Other data structures:

  (var base (object (value 100)))

  (object
    (x 10)
    (y 20)
    (__proto__ base))

  (var values (list 42 "Hello" foo))

  values[0]

  (idx values 0) // 42
  (idx values 1) // "Hello"