Building a Typechecker from scratch

1. Type theory and Basic types

1. Introduction to Type theory and checking

类型检查位于解释器顶层

// src/EvaTC.js
/**
 * Typed Eva: static typechecker
 */
class EvaTC {
    /**
     * Infers and validates type of expression
     */
    tc(exp) {
        // -----------------------------------
        // Self-evaluating

        /**
         * Numbers: 10
         */
        if (this._isNumber(exp)) {
            return 'number'
        }
    }

    /**
     * Whether the expression is a number
     */
    _isNumber(exp) {
        return typeof exp === 'number'
    }
}

module.exports = EvaTC

// __test__/run.js
const assert = require('assert')

const EvaTC = require('../src/EvaTC')

const eva = new EvaTC()

assert.equal(eva.tc(1), 'number')

console.log('All assertions passed!')

2. Typing Numbers and Strings Testing

// __test__/self-eval-test.js
const {test} = require('./test-utils')
const Type = require('../src/Types')

module.exports = eva => {
    // numbers
    test(eva, 42, Type.number)
    // strings
    test(eva, '"hello"', Type.string)
}

// __test__/run.js
const EvaTC = require('../src/EvaTC')

const tests = [
    require('./self-eval-test'),
]

const eva = new EvaTC()

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

console.log('All assertions passed!')

// __test__/test-utils.js
const assert = require('assert')

function exec(eva, exp) {
    return eva.tc(exp)
}

function test(eva, exp, expected) {
    const actual = exec(eva, exp)

    try {
        assert.strictEqual(actual.equals(expected), true)
    } catch (e) {
        console.log(`Expected ${expected} type for ${exp}, but got ${actual}.`)
        throw e
    }
}

module.exports = {
    exec, test
}

// src/Types.js
class Type {
    constructor(name) {
        this.name = name
    }

    /**
     * Returns name
     */
    getName() {
        return this.name
    }

    /**
     * String representation
     */
    toString() {
        return this.getName()
    }

    /**
     * Equals
     */
    equals(other) {
        return this.name === other.name
    }
}

/**
 * Number type
 */
Type.number = new Type('number')

/**
 * String type
 */
Type.string = new Type('string')

module.exports = Type

// src/EvaTC.js
const Type = require('./Types')

/**
 * Typed Eva: static typechecker
 */
class EvaTC {
    /**
     * Infers and validates type of expression
     */
    tc(exp) {
        // -----------------------------------
        // Self-evaluating

        /**
         * Numbers: 10
         */
        if (this._isNumber(exp)) {
            return Type.number
        }

        /**
         * Strings: 'hello'
         */
        if (this._isString(exp)) {
            return Type.string
        }
    }

    /**
     * Whether the expression is a number
     */
    _isNumber(exp) {
        return typeof exp === 'number'
    }

    /**
     * Whether the expression is a string
     */
    _isString(exp) {
        return typeof exp === 'string' && exp[0] === '"' && exp.slice(-1) === '"'
    }
}

module.exports = EvaTC

3. Math binary operations String concat

// __test__/math-test.js
const {test} = require('./test-utils')
const Type = require('../src/Types')

module.exports = eva => {
    // Math
    test(eva, ['+', 2, 3], Type.number)
    test(eva, ['-', 1, 3], Type.number)
    test(eva, ['*', 2, 4], Type.number)
    test(eva, ['/', 4, 2], Type.number)
    test(eva, ['%', 5, 6], Type.number)
    // fail(eva, ['%', 5, '"6"'], Type.number) // should throw

    // String concat
    test(eva, ['+', '"hello"', '" world"'], Type.string)
    // test(eva, ['-', '"hello"', '" world"'], Type.string) // should throw
}

// src/Types.js
class Type {
    // ...

    /**
     * Equals
     */
    equals(other) {
        return this.name === other.name
    }
}

// src/EvaTC.js
const Type = require('./Types')

/**
 * Typed Eva: static typechecker
 */
class EvaTC {
    /**
     * Infers and validates type of expression
     */
    tc(exp) {
        // ...

        // -----------------------------------
        // math operator
        if (this._isBinary(exp)) {
            return this._binary(exp)
        }
    }

    /**
     * Whether the expression is a number
     */
    _isBinary(exp) {
        return /^[+\-*/%]$/.test(exp[0])
    }

    /**
     * Binary operators
     */
    _binary(exp) {
        this._checkArity(exp, 2)

        const t1 = this.tc(exp[1])
        const t2 = this.tc(exp[2])

        const allowedTypes = this._getOperandTypesForOperator(exp[0])

        this._expectOperatorType(t1, allowedTypes, exp)
        this._expectOperatorType(t2, allowedTypes, exp)

        return this._expect(t2, t1, exp[2], exp)
    }

    /**
     * Returns allowed operand types for an operator
     */
    _getOperandTypesForOperator(operator) {
        switch (operator) {
            case '+':
                return [Type.string, Type.number]
            case '-':
                return [Type.number]
            case '*':
                return [Type.number]
            case '/':
                return [Type.number]
            case '%':
                return [Type.number]
            default:
                throw `Unknown operator: ${operator}`
        }
    }

    _expectOperatorType(type_, allowedTypes, exp) {
        if (!allowedTypes.some(t => t.equals(type_))) {
            throw `\nUnexpected type: ${type_} in ${exp}, allowed: ${allowedTypes}`
        }
    }

    /**
     * Expects a type
     */
    _expect(actualType, expectedType, value, exp) {
        if (!actualType.equals(expectedType)) {
            this._throw(actualType, expectedType, value, exp)
        }
        return actualType
    }

    /**
     * Throws type error.
     */
    _throw(actualType, expectedType, value, exp) {
        throw `Expected "${expectedType}" type for ${value} in ${exp}, but got "${actualType}" type.\n`
    }

    /**
     * Throws for number arguments
     */
    _checkArity(exp, arity) {
        if (exp.length - 1 !== arity) {
            throw `\nOperator '${exp[0]}' expects ${arity} operands, ${exp.length - 1} given in ${exp}.\n`
        }
    }

    // ...
}

module.exports = EvaTC

4. Variables and Typing Environment, Г

// __test__/variable-test.js
const {test} = require('./test-utils')
const Type = require('../src/Types')

module.exports = eva => {
    // variable declaration;
    test(eva, ['var', 'x', 10], Type.number)
    // Variable declaration with type check:
    test(eva, ['var', ['y', 'number'], 10], Type.number)
    test(eva, ['var', ['y', 'number'], 'x'], Type.number)
    // variable access
    test(eva, 'x', Type.number)
    // global variable
    test(eva, 'VERSION', Type.string)
}

// src/TypeEnvironment.js
/**
 * TypeEnvironment: mapping from names to types
 */
class TypeEnvironment {
    // ...

    /**
     * Returns the type of defined variable,or throws
     * if the variable is not defined.
     */
    lookup(name) {
        // TODO:parent env lookup!
        if (!this.record.hasOwnProperty(name)) {
            throw new ReferenceError(`Variable ${name} is not defined.`)
        }
        return this.record[name]
    }
}

module.exports = TypeEnvironment

// src/EvaTC.js
class EvaTC {
    /**
     * Creates an Eva instance with the global environment
     */
    constructor() {
        /**
         * Create the Global TypeEnvironment per Eva instance.
         */
        this.global = this._createGlobal()
    }

    /**
     * Infers and validates type of expression
     */
    tc(exp, env = this.global) {
        // ...

        // -----------------------------------
        // Variable declaration: (var x 10)
        // with typecheck: (var (x number) "foo") // error
        if (exp[0] === 'var') {
            const [_tag, name, value] = exp

            // Infer actual type
            const valueType = this.tc(value, env)

            // with type check (var (x number) "foo")
            if (Array.isArray(name)) {
                const [varName, typeStr] = name

                const expectedType = Type.fromString(typeStr)

                // check the type
                this._expect(valueType, expectedType, value, exp)

                return env.define(varName, expectedType)
            }

            // simple name
            return env.define(name, valueType)
        }

        // -----------------------------------
        // Variable access:foo
        if (this._isVariableName(exp)) {
            return env.lookup(exp)
        }

        throw `Unknown type for expression ${exp}`
    }

    /**
     * Binary operators
     */
    _binary(exp, env) {
        this._checkArity(exp, 2)

        const t1 = this.tc(exp[1], env)
        const t2 = this.tc(exp[2], env)

        // ...
    }

    /**
     * Creates a Global TypeEnvironment.
     */
    _createGlobal() {
        return new TypeEnvironment({
            VERSION: Type.string
        });
    }

    /**
     * Whether the expression is a variable name.
     */
    _isVariableName(exp) {
        return typeof exp === 'string' && /^[+\-*/<>=a-zA-Z0-9_:]+$/.test(exp);
    }
}

// src/Types.js
class Type {
    /**
     * From string: 'number' -> Type.number
     */
    static fromString(typeStr) {
        if (this.hasOwnProperty(typeStr)) {
            return this[typeStr]
        }
        throw `Unknown type: ${typeStr}`
    }
}

5. Blocks and Local scope

// __test__/block-test.js
const Type = require('../src/Types')
const {test} = require('./test-utils')

module.exports = eva => {
    // Block: sequence of expressions.
    test(eva,
        ['begin',
            ['var', 'x', 10],
            ['var', 'y', 20],
            ['+', ['*', 'x', 10], 'y']
        ], Type.number)
    // Block: local scope
    test(eva,
        ['begin',
            ['var', 'x', 10],

            ['begin',
                ['var', 'x', '"hello"'],
                ['+', 'x', '"world"']
            ],

            ['-', 'x', 5]
        ], Type.number)
    // Block: access parent scopes
    test(eva,
        ['begin',
            ['var', 'x', 10],

            ['begin',
                ['var', 'y', 20],
                ['+', 'x', 'y']
            ],

            ['-', 'x', 5]
        ], Type.number)
    // Block: variable update
    test(eva,
        ['begin',
            ['var', 'x', 10],

            ['begin',
                ['var', 'y', 20],
                ['set', 'x', ['+', 'x', 'y']]
                // ['set', 'x', '"e"']
            ],
        ], Type.number)
}

// src/TypeEnvironment.js
/**
 * TypeEnvironment: mapping from names to types
 */
class TypeEnvironment {
    // ...

    /**
     * Returns the type of 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)
    }
}

// src/EvaTC.js
const Type = require('./Types')
const TypeEnvironment = require('./TypeEnvironment')

/**
 * Typed Eva: static typechecker
 */
class EvaTC {
    // ...

    /**
     * Infers and validates type of expression
     */
    tc(exp, env = this.global) {

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

            // The type of the new value should match to the
            // previous type when the variable was defined:
            const valueType = this.tc(value, env)
            const varType = this.tc(ref, env)

            return this._expect(valueType, varType, value, exp)
        }

        // -----------------------------------
        // Block:sequence of expressions
        if (exp[0] === 'begin') {
            const blockEnv = new TypeEnvironment({}, env)
            return this._tcBlock(exp, blockEnv)
        }

        throw `Unknown type for expression ${exp}`
    }

    /**
     * Checks a block
     */
    _tcBlock(exp, env) {
        let result

        const [_tag, ...expressions] = exp

        expressions.forEach(exp => {
            result = this.tc(exp, env)
        })

        return result;
    }
}

6. Parsing S-expression to AST

// eva-grammar.bnf
/**
   S-expression parser

   Atom: 42, foo, bar, "Hello"

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

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

%lex

%%

\/\/.*                  /* skip comments */
\/\*[\s\S]*?\*\/        /* skip comments */

\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 */ { $$ = [] }
    ;

// __test__/block-test.js
const Type = require('../src/Types')
const {test, exec} = require('./test-utils')

module.exports = eva => {
    // ...
    test(eva, `
        (begin
            (var x 10)
            (var y 20)
            (+ (* x 10) y)
        )
        `, Type.number)
    exec(eva, `(var x 10)`)
    test(eva, `
            (var y 20)
            (+ (* x 10) y)
        `, Type.number)
    // ...
}

// src/EvaTC.js
class EvaTC {
    tcGlobal(exp) {
        return this._tcBody(exp, this.global)
    }

    /**
     * Checks body (global or function).
     */
    _tcBody(body, env) {
        if (body[0] === 'begin') {
            return this._tcBlock(body, env)
        }
        return this.tc(body, env)
    }

    // ...
}

// __test__/test-utils.js
const assert = require('assert')
const evaParser = require('../parser/evaParser')

function exec(eva, exp) {
    if (typeof exp === 'string') {
        exp = evaParser.parse(`(begin ${exp})`)
    }
    return eva.tcGlobal(exp)
}

// ...

7. Control flow If and While expressions

// __test__/while-test.js
const Type = require('../src/Types')
const {exec, test} = require('./test-utils')

module.exports = eva => {
    test(eva, `
        (var x 10)

        (while (!= x 0)
            // (set x (- x 1))
            // x++ -> 一直循环
            // 依然测试通过, 因为类型检查器不关心运行时语义
            (set x (+ x 1))
        )

        x
    `, Type.number)
}

// __test__/if-test.js
const Type = require('../src/Types')
const {exec, test} = require('./test-utils')

module.exports = eva => {
    test(eva, `(<= x 10)`, Type.boolean)

    // If expression: both branches
    // should return the same type
    test(eva, `
        (var x 10)
        (var y 20)

        (if (<= x 10)
            (set y 1)
            (set y 2)
        )

        y
    `, Type.number)
}

// src/EvaTC.js
const Type = require('./Types')
const TypeEnvironment = require('./TypeEnvironment')

/**
 * Typed Eva: static typechecker
 */
class EvaTC {
    // ...

    tc(exp, env = this.global) {
        // -----------------------------------
        // Boolean: true | false
        if (this._isBoolean(exp)) {
            return Type.boolean
        }

        // -----------------------------------
        // boolean binary
        if (this._isBooleanBinary(exp)) {
            return this._booleanBinary(exp, env)
        }

        // -----------------------------------
        // if-expression:
        // rFel bool r e2 :t r H e2 :t
        // rFif el e2 else e2 }:t
        // Both branches should return the same time t.
        if (exp[0] === 'if') {
            const [_tag, condition, consequent, alternate] = exp

            // Boolean condition
            const t1 = this.tc(condition, env)
            this._expect(t1, Type.boolean, condition, exp)

            const t2 = this.tc(consequent, env)
            const t3 = this.tc(alternate, env)

            // Same types for both branches
            return this._expect(t3, t2, exp, exp)
        }

        // -----------------------------------
        // while-expression
        if (exp[0] === 'while') {
            const [_tag, condition, body] = exp

            // boolean condition
            const t1 = this.tc(condition, env)
            this._expect(t1, Type.boolean, condition, exp)

            return this.tc(body, env)
        }

        throw `Unknown type for expression ${exp}`
    }

    /**
     * Whether the expression is a boolean.
     */
    _isBoolean(exp) {
        return typeof exp === 'boolean' || exp === 'true' || exp === 'false';
    }

    /**
     * Whether the expression is boolean binary.
     */
    _isBooleanBinary(exp) {
        return (
            exp[0] === '==' ||
            exp[0] === '!=' ||
            exp[0] === '>=' ||
            exp[0] === '<=' ||
            exp[0] === '>' ||
            exp[0] === '<'
        )
    }

    _booleanBinary(exp, env) {
        this._checkArity(exp, 2)

        const t1 = this.tc(exp[1], env)
        const t2 = this.tc(exp[2], env)

        this._expect(t2, t1, exp[2], exp)

        return Type.boolean
    }
}

// __test__/self-eval-test.js
const {test} = require('./test-utils')
const Type = require('../src/Types')

module.exports = eva => {
    // numbers
    test(eva, 42, Type.number)
    // strings
    test(eva, '"hello"', Type.string)
    // boolean
    test(eva, true, Type.boolean)
    test(eva, false, Type.boolean)
}

// src/Types.js
// ...

/**
 * Boolean type
 */
Type.boolean = new Type('boolean')

2. Functional programming

1. User-defined functions Local environments

// __test__/user-defined-function-test.js
const Type = require('../src/Types')
const {exec, test} = require('./test-utils')

module.exports = eva => {
    test(eva, `
        (def square ((x number)) -> number
            (* x x))

        (square 2)
        // (square "2")
    `, Type.number)
    // Complex body
    test(eva, `
        (def calc ((x number) (y number)) -> number
            (begin
                (var z 30)
                (+ (* x y) z)
            )
        )
        
        (calc 10 20)
    `, Type.number)
}

// src/EvaTC.js

class EvaTC {
    // ...
    tc(exp, env = this.global) {
        // ...
        // -----------------------------------
        // Function declaration:(def square ((x number))->number (xx))
        if (exp[0] === 'def') {
            const [_tag, name, params, _retDel, returnTypeStr, body] = exp

            return env.define(
                name,
                this._tcFunction(params, returnTypeStr, body, env)
            )
        }

        // -----------------------------------
        // Function calls
        // (square 2)
        if (Array.isArray(exp)) {
            const fn = this.tc(exp[0], env)
            const argValues = exp.slice(1)

            // Passed arguments
            const argTypes = argValues.map(arg => this.tc(arg, env))

            return this._checkFunctionCall(fn, argTypes, env, exp)
        }

        throw `Unknown type for expression ${exp}`
    }

    /**
     * Checks function body.
     */
    _tcFunction(params, returnTypeStr, body, env) {
        const returnType = Type.fromString(returnTypeStr)

        // Parameters environment and types:
        const paramsRecord = {}
        const paramTypes = []

        params.forEach(([name, typeStr]) => {
            const paramType = Type.fromString(typeStr)
            paramsRecord[name] = paramType
            paramTypes.push(paramType)
        })

        const fnEnv = new TypeEnvironment(paramsRecord, env)

        // Check the body in the extended environment:
        const actualReturnType = this._tcBody(body, fnEnv)

        // Check return type
        if (!returnType.equals(actualReturnType)) {
            throw `Expected function ${body} to return ${returnType}, but got ${actualReturnType}.`
        }

        // Function type records its parameters and return type,
        // so we can use them to validate function calls:\
        return new Type.Function({
            paramTypes, returnType
        })
    }

    /**
     * Checks function call.
     */
    _checkFunctionCall(fn, argTypes, env, exp) {
        // Check arity
        if (fn.paramTypes.length !== argTypes.length) {
            throw `\nFunction ${exp[0]} ${fn.getName()} expects ${
                fn.paramTypes.length
            } arguments, ${argTypes.length} given in ${exp}.\n`
        }

        // Check if argument types match the parameter types:
        argTypes.forEach((argType, index) => {
            this._expect(argType, fn.paramTypes[index], argTypes[index], exp)
        })

        return fn.returnType
    }
}

// src/Types.js
class Type {
    // ...
    /**
     * From string: 'number' -> Type.number
     */
    static fromString(typeStr) {
        if (this.hasOwnProperty(typeStr)) {
            return this[typeStr]
        }

        // Functions
        if (typeStr.includes('Fn<')) {
            return Type.Function.fromString(typeStr)
        }

        throw `Unknown type: ${typeStr}`
    }
}

/**
 * Function meta type
 */
Type.Function = class extends Type {
    constructor({name = null, paramTypes, returnType}) {
        super(name);
        this.paramTypes = paramTypes
        this.returnType = returnType
        this.name = this.getName()
    }

    /**
     * Returns name:Fn<returnType<p1,p2,...>>
     *
     * Fn<number> - function which returns a number
     * Fn<number<number,number>> - function which returns a number,and accepts two number
     */
    getName() {
        if (this.name == null) {
            const name = ['Fn<', this.returnType.getName()]
            // params
            if (this.paramTypes.length !== 0) {
                const params = []
                for (let i = 0; i < this.paramTypes.length; i++) {
                    params.push(this.paramTypes[i].getName())
                }
                name.push('<', params.join(','), '>')
            }
            name.push('>')
            this.name = name.join('')
        }
        return this.name
    }

    /**
     * Equals
     */
    equals(other) {
        if (this.paramTypes.length !== other.paramTypes.length) {
            return false
        }

        // Same params
        for (let i = 0; i < this.paramTypes.length; i++) {
            if (!this.paramTypes[i].equals(other.paramTypes[i])) {
                return false
            }
        }

        // Return type
        if (!this.returnType.equals(other.returnType)) {
            return false
        }

        return true
    }

    /**
     * From string: 'Fn<number>' -> Type.Function
     */
    static fromString(typeStr) {
        // Already compiled
        if (Type.hasOwnProperty(typeStr)) {
            return Type[typeStr]
        }

        // Function type with return and params:
        let matched = /^Fn<(\w+)<([a-z,\s]+)>>$/.exec(typeStr)

        if (matched != null) {
            const [_, returnTypeStr, paramsString] = matched

            // Param types
            const paramTypes = paramsString
                .split(/,\s*/g)
                .map(param => Type.fromString(param))

            return (Type[typeStr] = new Type.Function({
                name: typeStr,
                paramTypes,
                returnType: Type.fromString(returnTypeStr)
            }))

            // Function type with return type only:
            matched = /^Fn<(\w+)>$/.exec(typeStr);

            if (matched != null) {
                const [_, returnTypeStr] = matched

                return (Type[typeStr] = new Type.Function({
                    name: typeStr,
                    paramTypes: [],
                    returnType: Type.fromString(returnTypeStr)
                }))
            }

            throw `Type.Function.fromString: Unknown type: ${typeStr}.`
        }
    }
}

2. Function calls Built-in functions

// src/EvaTC.js
// ...
_createGlobal()
{
    return new TypeEnvironment({
        VERSION: Type.string,

        sum: Type.fromString("Fn<number<number,number>>"),
        square: Type.fromString("Fn<number<number>>"),
    });
}

// __test__/built-in-function-test.js
const {test} = require('./test-utils')
const Type = require('../src/Types')

module.exports = eva => {
    test(eva, `(sum 1 5)`, Type.number)
    test(eva, `(sum (square 2) 4)`, Type.number)
}

3. Closures Recursive calls

// src/EvaTC.js
// ...
if (exp[0] === 'def') {
    const [_tag, name, params, _retDel, returnTypeStr, body] = exp

    // We have to extend environment with the function name *before*
    // evaluating the body -- this is need to support recursive
    // function calls:
    const paramTypes = params.map(([name, typeStr]) =>
        Type.fromString(typeStr)
    )

    // Predefine from the signature:
    env.define(
        name,
        new Type.Function({
            paramTypes,
            returnType: Type.fromString(returnTypeStr)
        })
    )

    // return env.define(
    //     name,
    //     this._tcFunction(params, returnTypeStr, body, env)
    // )

    // Actually validate the body
    return this._tcFunction(params, returnTypeStr, body, env)
}

// __test__/user-defined-function-test.js
const Type = require('../src/Types')
const {exec, test} = require('./test-utils')

module.exports = eva => {
    // ...
    // Closure
    test(eva, `
        (var value 100)
        
        (def calc ((x number) (y number)) -> Fn<number<number>>
            (begin
                (var z (+ x y))
                
                (def inner ((foo number)) -> number
                    (+ (+ foo z) value)
                )
                
                inner
            )
        )
        
        (var fn (calc 10 20))
        
        (fn 30)
    `, Type.number)
    // Recursive function
    test(eva, `
        (def factorial ((x number)) -> number
            (if (== x 1)
                1
                (* x (factorial (- x 1)))
            )
        )
        
        (factorial 5)
    `, Type.number)
}

4. Lambda functions and IILE Syntactic sugar

// src/EvaTC.js
class EvaTC {
    tc(exp, env = this.global) {

        // -----------------------------------
        // Function declaration:(def square ((x number))->number (xx))
        //
        // Syntactic sugar for:(var square (Lambda ((x number))->number (xx)))
        if (exp[0] === 'def') {
            // const [_tag, name, params, _retDel, returnTypeStr, body] = exp

            // Transpile to a variable declaration
            const varExp = this._transformDefToVarLambda(exp)

            const name = exp[1]
            const params = exp[2]
            const returnTypeStr = exp[4]

            // We have to extend environment with the function name *before*
            // evaluating the body -- this is need to support recursive
            // function calls:
            const paramTypes = params.map(([name, typeStr]) =>
                Type.fromString(typeStr)
            )

            // Predefine from the signature:
            env.define(
                name,
                new Type.Function({
                    paramTypes,
                    returnType: Type.fromString(returnTypeStr)
                })
            )

            // return env.define(
            //     name,
            //     this._tcFunction(params, returnTypeStr, body, env)
            // )

            // Actually validate the body
            // return this._tcFunction(params, returnTypeStr, body, env)
            return this.tc(varExp, env)
        }

        // -----------------------------------
        // Lambda function:(Lambda ((x number))->number (xx))
        if (exp[0] === 'lambda') {
            const [_tag, params, _retDel, returnTypeStr, body] = exp
            return this._tcFunction(params, returnTypeStr, body, env)
        }

        // ...
        throw `Unknown type for expression ${exp}`
    }

    // ...
    /**
     * Transforms def to var-lambda.
     */
    _transformDefToVarLambda(exp) {
        const [_tag, name, params, _retDel, returnTypeStr, body] = exp

        return ['var', name, ['lambda', params, _retDel, returnTypeStr, body]]
    }
}

// __test__/lambda-function-test.js
const Type = require('../src/Types')
const {exec, test} = require('./test-utils')

module.exports = eva => {
    // lambda function
    test(eva, `
        (lambda ((x number)) -> number (* x x))
    `, Type.fromString('Fn<number<number>>'))
    // Pass lambda as a callback
    test(eva, `
        (def onClick ((callback Fn<number<number>>)) -> number
            (begin
                (var x 10)     
                (var y 20)
                (callback (+ x y))
            )
        )
        
        (onClick (lambda ((data number)) -> number (* data 10)))
    `, Type.number)
    // Immediately-invoked lambda expression IILE:
    test(eva, `
        ((lambda ((x number)) -> number (* x x)) 2)
    `, Type.number)
    // Save lambda to a variable:
    test(eva, `
        (var square (lambda ((x number)) -> number (* x x)))
        (square 2)
    `, Type.number)
}

3. Type declarations and Classes

1. Declaring new types Type aliases

// src/EvaTC.js
class EvaTC {
    tc(exp, env = this.global) {
        // ...
        // -----------------------------------
        // Type declaration/alias:(type <namew><base>)
        if (exp[0] === 'type') {
            const [_tag, name, base] = exp

            // Type alias
            if (Type.hasOwnProperty(name)) {
                throw `Type ${name} is already defined: ${Type[name]}`
            }

            if (!Type.hasOwnProperty(base)) {
                throw `Type ${base} is not defined.`
            }

            return (Type[name] = new Type.Alias({
                name,
                parent: Type[base]
            }))
        }
        throw `Unknown type for expression ${exp}`
    }

    // ...
}

// __test__/alias-test.js
const {test, exec} = require('./test-utils')
const Type = require('../src/Types')

module.exports = eva => {
    exec(eva, `
        (type int number)
        (type ID int)
        (type Index ID)
    `)
    test(eva, `
        (def square ((x int)) -> int (* x x))
        (square 2)
    `, Type.int)
    test(eva, `
        (def promote ((userID ID)) -> ID (+ 1 userID))
        (promote 1)
    `, Type.ID)
    test(eva, `
        (var (x Index) 1)
    `, Type.Index)
    test(eva, `x`, Type.ID)
    test(eva, `x`, Type.int)
}

// src/Types.js
class Type {
    // ...
    equals(other) {
        if (other instanceof Type.Alias) {
            return other.equals(this)
        }

        return this.name === other.name
    }
}

/**
 * Type alias
 */
Type.Alias = class extends Type {
    constructor({name, parent}) {
        super(name);
        this.parent = parent
    }

    /**
     * Equals
     */
    equals(other) {
        if (this.name === other.name) {
            return true
        }
        return this.parent.equals(other)
    }

}

2. OOP Classes & 3. OOP Instances

// __test__/class-test.js
const {test} = require('./test-utils');
const Type = require('../src/Types');

module.exports = eva => {

    test(eva,
        `
    (class Point null
      (begin

        (var (x number) 0)
        (var (y number) 0)

        (def constructor ((self Point) (x number) (y number)) -> Point
          (begin
            (set (prop self x) x)
            (set (prop self y) y)
            self))

        (def calc ((self Point)) -> number
          (+ (prop self x) (prop self y)))))

    (var (p Point) (new Point 10 20))

    ((prop p calc) p)

  `,
        Type.number);
};

class EvaTC {
    // ...
    tc(exp, env = this.global) {
        // ...
        if (exp[0] === 'set') {
            const [_, ref, value] = exp

            // 1.Assignment to a property:
            if (ref[0] === 'prop') {
                const [_tag, instance, propName] = ref
                const instanceType = this.tc(instance, env)

                const valueType = this.tc(value, env)
                const propType = instanceType.getField(propName)

                return this._expect(valueType, propType, value, exp)
            }

            // ...
        }

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

            // Resolve super
            const superClass = Type[superClassName]

            // New class (type)
            const classType = new Type.Class({name, superClass})

            // class is accessible by name.
            Type[name] = env.define(name, classType)

            // Body is evaluated in the class environment.
            this._tcBody(body, classType.env)

            return classType
        }

        // -----------------------------------
        // class instantiation:(new <class><Arguments>...)
        if (exp[0] === 'new') {
            const [_tag, className, ...argValues] = exp;
            const classType = Type[className];
            if (classType == null) {
                throw `Unknown class ${name}.`
            }
            const argTypes = argValues.map(arg => this.tc(arg, env))
            return this._checkFunctionCall(
                classType.getField('constructor'),
                [classType, ...argTypes],
                env, exp
            )
        }

        // -----------------------------------
        // Property access:(prop <instance><name>
        if (exp[0] === 'prop') {
            const [_tag, instance, name] = exp
            const instanceType = this.tc(instance, env)
            return instanceType.getField(name)
        }
        throw `Unknown type for expression ${exp}`
    }
}

// src/Types.js
// ...
/**
 * Null type
 */
Type.null = new Type('null')

/**
 * Class type:(class ...
 * Creates a new TypeEnvironment.
 */
Type.Class = class extends Type {
    constructor({name, superClass = Type.null}) {
        super(name)
        this.superClass = superClass
        this.env = new TypeEnvironment({}, superClass != Type.null ? superClass.env : null)
    }

    /**
     * Returns field type
     */
    getField(name) {
        return this.env.lookup(name)
    }

    /**
     * Equals
     */
    equals(other) {
        if (this === other) {
            return true
        }

        // Aliases
        if (other instanceof Type.Alias) {
            return other.equals(this)
        }

        // Super class
        if (this.superClass != Type.null) {
            // type: 子类 == 父类
            return this.superClass.equals(other)
        }

        // Anything else
        return false
    }
}

4. Super calls Inheritance

// src/EvaTC.js 

// -----------------------------------
// Super expressions:(super <ClassName>)
if (exp[0] === 'super') {
    const [_tag, className] = exp

    const classType = Type[className]

    if (classType == null) {
        throw `Unknown class ${name}.`
    }

    return classType.superClass
}

// __test__/class-test.js
const {test} = require('./test-utils');
const Type = require('../src/Types');

module.exports = eva => {

    // ...

    test(eva,
        `
    (class Point3D Point
      (begin

        (var (z number) 0)

        (def constructor ((self Point3D) (x number) (y number) (z number)) -> Point3D
          (begin
            ((prop (super Point3D) constructor) self x y)
            (set (prop self z) z)
            self))

        (def calc ((self Point3D)) -> number
          (+ ((prop (super Point3D) calc) self)
             (prop self z)))))

    (var (p Point3D) (new Point3D 10 20 30))

    ((prop p calc) p)

  `,
        Type.number);
};

4. Generic programming

1. Union type

// src/EvaTC.js

if (exp[0] === 'type') {
    const [_tag, name, base] = exp

    // Union type (e.g. (or number string))
    if (base[0] === 'or') {
        const options = base.slice(1)
        const optionTypes = options.map(option => Type.fromString(option))
        return (Type[name] = new Type.Union({name, optionTypes}))
    }

    // Type alias
    else {
        if (Type.hasOwnProperty(name)) {
            throw `Type ${name} is already defined: ${Type[name]}`
        }

        if (!Type.hasOwnProperty(base)) {
            throw `Type ${base} is not defined.`
        }

        return (Type[name] = new Type.Alias({
            name,
            parent: Type[base]
        }))
    }
}

// src/Types.js 

class Type {
    // ...
    equals(other) {
        if (other instanceof Type.Alias) {
            return other.equals(this)
        }

        if (other instanceof Type.Union) {
            return other.equals(this)
        }

        return this.name === other.name
    }
}

// ...
/**
 * Union type:(or string number)
 */
Type.Union = class extends Type {
    constructor({name, optionTypes}) {
        super(name)
        this.optionTypes = optionTypes
    }

    /**
     * Equals
     */
    equals(other) {
        if (this === other) {
            return true
        }

        // Aliases
        if (other instanceof Type.Alias) {
            return other.equals(this)
        }

        // Other union
        if (other instanceof Type.Union) {
            return this.includesAll(other.optionTypes)
        }

        // Anything else
        return this.optionTypes.some(t => t.equals(other))
    }

    /**
     * Whether this union includes all types.
     */
    includesAll(types) {
        if (types.length !== this.optionTypes.length) {
            return false
        }
        for (const type_ of types) {
            if (!this.equals(type_)) {
                return false
            }
        }
        return true
    }
}

// __test__/union-test.js
const {exec, test} = require('./test-utils');
const Type = require('../src/Types');

module.exports = eva => {

    exec(eva,
        `
    (type value (or number string))

    (type ID (or string number))

  `);

    test(eva,
        `
    (var (x value) 10)

    x

  `,
        Type.value);

    test(eva,
        `
    x
  `,
        Type.number);

    test(eva,
        `
    x
  `,
        Type.string);

    test(eva,
        `
    (var (y value) "hello")

    y 
  `,
        Type.value);

    test(eva,
        ` 
    (var (a value) 10)
    (var (b ID) "x")

    (def process ((id ID)) -> number
      (+ a id))
      // (- "a" id))

    (process b)

    (+ a b) 
  `,
        Type.number);
}

2. Union Type narrowing

// src/EvaTC.js 

class EvaTC {
    tc(exp, env = this.global) {
        // ...
        if (exp[0] === 'if') {
            const [_tag, condition, consequent, alternate] = exp

            // Boolean condition
            const t1 = this.tc(condition, env)
            this._expect(t1, Type.boolean, condition, exp)

            // Initially,environment used to tc consequent part
            // is the same as the main env,however can be updated
            // for the union type with type casting:
            let consequentEnv = env

            // Check if the condition is a type casting rule.
            // This is used with union types to make a type concrete:
            // (if (== (typeof foo) "string")...)
            if (this._isTypeCastCondition(condition)) {
                const [name, specificType] = this._getSpecifiedType(condition)

                // Update environment with the concrete type for this name:
                consequentEnv = new TypeEnvironment(
                    {[name]: Type.fromString(specificType)},
                    env
                )
            }

            const t2 = this.tc(consequent, consequentEnv)
            const t3 = this.tc(alternate, env)

            // Same types for both branches
            return this._expect(t3, t2, exp, exp)
        }

        throw `Unknown type for expression ${exp}`
    }

    // ...

    _expectOperatorType(type_, allowedTypes, exp) {
        // For union type, _all_ sub-types should support this operation:
        if (type_ instanceof Type.Union) {
            if (type_.includesAll(allowedTypes)) {
                return
            }
        }

        // other types
        else {
            if (allowedTypes.some(t => t.equals(type_))) {
                return;
            }
        }

        throw `\nUnexpected type:${type_} in ${exp}, allowed: ${allowedTypes}.`
    }

    _createGlobal() {
        return new TypeEnvironment({
            VERSION: Type.string,

            sum: Type.fromString("Fn<number<number,number>>"),
            square: Type.fromString("Fn<number<number>>"),

            typeof: Type.fromString('Fn<string<any>>')
        });
    }

    _checkFunctionCall(fn, argTypes, env, exp) {
        // ...

        // Check if argument types match the parameter types:
        argTypes.forEach((argType, index) => {
            if (fn.paramTypes[index] === Type.any) {
                return
            }
            this._expect(argType, fn.paramTypes[index], argTypes[index], exp)
        })

        return fn.returnType
    }

    /**
     * Whether the if-condition is type casting/specification.
     *
     * This is used with union types to make a type concrete:
     *
     * (if (=(typeof foo)"string")...)
     */
    _isTypeCastCondition(condition) {
        const [op, lhs] = condition
        return op === '==' && lhs[0] === 'typeof'
    }

    /**
     * Returns specific type after casting.
     *
     * This is used with union types to make a type concrete:
     *
     * (if (=(typeof foo)"string")...)
     */
    _getSpecifiedType(condition) {
        const [op, [_typeof, name], specificType] = condition;
        // Return name and the new type (stripping quotes).
        return [name, specificType.slice(1, -1)];
    }
}

// src/Types.js
/**
 * Any type
 */
Type.any = new Type('any')

// __test__/union-test.js
const {exec, test} = require('./test-utils');
const Type = require('../src/Types');

module.exports = eva => {

    exec(eva,
        `
    (type value (or number string))

    (type ID (or string number))

  `);

    test(eva,
        `
    (var (x value) 10)

    x

  `,
        Type.value);

    test(eva,
        `
    x
  `,
        Type.number);

    test(eva,
        `
    x
  `,
        Type.string);

    test(eva,
        `
    (var (y value) "hello")

    y 
  `,
        Type.value);

    test(eva,
        ` 
    (var (a value) 10)
    (var (b ID) "x")

    (def process ((id ID)) -> number
      (+ a id))
      // (- a id)) // should panic(cause string can't use - operator)
      // (- "a" id))

    (process b)

    (+ a b) 
  `,
        Type.number);

    test(eva,
        `
    (def accept ((x value)) -> value
      (begin
        (if (== (typeof x) "number")
            (- 1 x)
            (+ "y" x))))

    (accept 10)
  `,
        Type.number);

    test(eva,
        `
    (accept "x")
  `,
        Type.string);
}

3. Generics Function declarations

// __test__/generic-test.js
const {test, exec} = require('./test-utils');
const Type = require('../src/Types');

module.exports = eva => {
    // Generic function
    exec(eva, `
        // (def combine ((x number) (y number)) -> number (+ x y))
        // (def combine ((x string) (y string)) -> string (+ x y))
        
        (def combine <K> ((x K) (y K)) -> K (+ x y))
    `)
}

// src/EvaTC.js
class EvaTC {
    tc(exp, env = this.global) {

        if (exp[0] === 'def') {
            // const [_tag, name, params, _retDel, returnTypeStr, body] = exp

            // Transpile to a variable declaration
            const varExp = this._transformDefToVarLambda(exp)

            if (!this._isGenericDefFunction(exp)) {

                const name = exp[1]
                const params = exp[2]
                const returnTypeStr = exp[4]

                // We have to extend environment with the function name *before*
                // evaluating the body -- this is need to support recursive
                // function calls:
                const paramTypes = params.map(([name, typeStr]) =>
                    Type.fromString(typeStr)
                )

                // Predefine from the signature:
                env.define(
                    name,
                    new Type.Function({
                        paramTypes,
                        returnType: Type.fromString(returnTypeStr)
                    })
                )
            }

            // return env.define(
            //     name,
            //     this._tcFunction(params, returnTypeStr, body, env)
            // )

            // Actually validate the body
            // return this._tcFunction(params, returnTypeStr, body, env)
            return this.tc(varExp, env)
        }

        if (exp[0] === 'lambda') {
            // 1. Generic function
            if (this._isGenericLambdaFunction(exp)) {
                return this._createGenericFunctionType(exp, env)
            }

            // 2. Simple function
            return this._createSimpleFunctionType(exp, env)
        }
        throw `Unknown type for expression ${exp}`
    }

    /**
     * Generic function declarations.
     * Such functions are not checked at declaration,
     * instead they are checked at call time,when all
     * generic parameters are bound.
     */
    _createGenericFunctionType(exp, env) {
        const [_tag, genericTypes, params, _retDel, returnType, body] = exp

        return new Type.GenericFunction({
            genericTypesStr: genericTypes.slice(1, -1),
            params, body, returnType,
            env // Closure
        })
    }

    /**
     * Simple function declarations (no generic parameters).
     *
     * Such functions are type-checked during declaration time.
     */
    _createSimpleFunctionType(exp, env) {
        const [_tag, params, _retDel, returnTypeStr, body] = exp
        return this._tcFunction(params, returnTypeStr, body, env)
    }

    /**
     * Whether the function is generic.
     *
     * (def foo <K>((x K))->K (xx))
     */
    _isGenericDefFunction(exp) {
        return exp.length === 7 && /^<[^>]+>$/.test(exp[2])
    }

    /**
     * Whether the function is generic.
     *
     * (lambda <K>((x K))->K (xx))
     */
    _isGenericLambdaFunction(exp) {
        return exp.length === 6 && /^<[^>]+>$/.test(exp[1])
    }

    /**
     * Transforms def to var-lambda.
     */
    _transformDefToVarLambda(exp) {
        // 1. Generic function
        if (this._isGenericDefFunction(exp)) {
            const [_tag, name, genericTypesStr, params, _retDel, returnTypeStr, body] = exp;
            return ['var', name, ['lambda', genericTypesStr, params, _retDel, returnTypeStr, body]];
        }

        // 2. Simple function
        const [_tag, name, params, _retDel, returnTypeStr, body] = exp

        return ['var', name, ['lambda', params, _retDel, returnTypeStr, body]]
    }
} 

// src/Types.js
/**
 * Generic function type.
 * Generic functions create normal function types
 * when a function is called.
 */
Type.GenericFunction = class extends Type {
    constructor({name = null, genericTypesStr, params, body, returnType, env}) {
        super(`${name || 'lambda'} <${genericTypesStr}>`);
        this.genericTypes = genericTypesStr.split(',')
        this.params = params
        this.body = body
        this.returnType = returnType
        this.env = env
    }
}

4. Generics Function calls

// src/EvaTC.js

class EvaTC {
    tc(exp, env = this.global) {
        if (Array.isArray(exp)) {
            const fn = this.tc(exp[0], env)

            // Simple function calls
            let actualFn = fn
            let argValues = exp.slice(1)

            // Generic function call
            if (fn instanceof Type.GenericFunction) {
                // Actual (instantiated) types
                const actualTypes = this._extractActualCallTypes(exp)

                // Map the generic types to the actual types:
                const genericTypesMap = this._getGenericTypesMap(
                    fn.genericTypes,
                    actualTypes
                )

                // Bind parameters and return types:
                const [boundParams, boundReturnType] = this._bindFunctionTypes(
                    fn.params, fn.returnType,
                    genericTypesMap // {K: number}
                )

                // Check function body with the bound parameter types:
                // This creates an actual function type.

                // Notice:we pass environment as fn.env,i.e.closured environment
                // TODO: pre-install to Type combine_number,combine_string,etc.
                actualFn = this._tcFunction(
                    boundParams, boundReturnType,
                    fn.body,
                    fn.env // Closure
                )

                // In generic function calls parameters are passed from index 2:
                argValues = exp.slice(2) // (combine <number> 2 3)
            }

            // Passed arguments
            const argTypes = argValues.map(arg => this.tc(arg, env))

            return this._checkFunctionCall(actualFn, argTypes, env, exp)
        }

        throw `Unknown type for expression ${exp}`
    }

    /**
     * Maps generic parameter types to actual types.
     */
    _getGenericTypesMap(genericTypes, actualType) {
        const boundTypes = new Map()
        for (let i = 0; i < genericTypes.length; i++) {
            boundTypes.set(genericTypes[i], actualType[i])
        }
        return boundTypes
    }

    /**
     * Binds generic parameters and return type to actual types.
     */
    _bindFunctionTypes(params, returnType, genericTypesMap) {
        const actualParams = []

        // 1.Bind parameter types:
        for (let i = 0; i < params.length; i++) {
            const [paramName, paramType] = params[i]

            let actualParamType = paramType

            // Generic type -> rewrite to actual.
            // genericTypesMap({K: number})
            if (genericTypesMap.has(paramType)) {
                actualParamType = genericTypesMap.get(paramType)
            }

            actualParams.push([paramName, actualParamType])
        }

        // 2.Bind return type:
        let actualReturnType = returnType

        if (genericTypesMap.has(returnType)) {
            actualReturnType = genericTypesMap.get(returnType)
        }

        return [actualParams, actualReturnType]
    }

    /**
     * Extracts types for generic parameter types.
     * (combine <string> "hello")
     */
    _extractActualCallTypes(exp) {
        const data = /^<([^>]+)>$/.exec(exp[1])

        if (data == null) {
            throw `No actual types provided in generic call: ${exp}.`
        }

        return data[1].split(',')
    }
}

// __test__/generic-test.js
const {test, exec} = require('./test-utils');
const Type = require('../src/Types');

module.exports = eva => {
    // Generic function
    exec(eva, `
        // (def combine ((x number) (y number)) -> number (+ x y))
        // (def combine ((x string) (y string)) -> string (+ x y))
        
        (def combine <K> ((x K) (y K)) -> K (+ x y))
    `)
    test(eva, `
        (combine <number> 2 3)
    `, Type.number)
    test(eva, `
        (combine <string> "hello" " world")
    `, Type.string)
    test(eva, `
        ((lambda <K> ((x K)) -> K (+ x x)) <number> 2)
    `, Type.number)
    test(eva, `
        ((lambda <K> ((x K)) -> K (+ x x)) <string> "hello")
    `, Type.string)
}

5. Final executable

/**
 * Class declaration.
 */

(class Point null
  (begin

    (var (x number) 0)
    (var (y number) 0)

    (def constructor ((self Point) (x number) (y number)) -> Point
      (begin
        (set (prop self x) x)
        (set (prop self y) y)
        self))

    (def calc ((self Point)) -> number
      (+ (prop self x) (prop self y)))))

(var (p Point) (new Point 10 20))

((prop p calc) p)

/**
 * Child class.
 */

(class Point3D Point
  (begin

    (var (z number) 0)

    (def constructor ((self Point3D) (x number) (y number) (z number)) -> Point3D
      (begin
        ((prop (super Point3D) constructor) self x y)
        (set (prop self z) z)
        self))

    (def calc ((self Point3D)) -> number
      (+ ((prop (super Point3D) calc) self)
         (prop self z)))))

(var (p Point3D) (new Point3D 10 20 30))

((prop p calc) p)


/*

What's next?

1. Shapes (aka Objects, aka Interfaces)

(type User
  (object
    (name string)
    (age number)))

(var (user User)
  (object
    (name "John")
    (age 25)))

// (interface  ...) -> syntactic sugar for (type  (object ...))

(interface User
  (name string)
  (age number))

(class    )

2. Async functions

(async def fetch  )

3. Array literals:

(array ...)

4. Type: valueBelongs, isOperationSupported


5. Values union

(type names (or "alex" "john"))

6. Infer types for generic calls:

(combine  2 3) -> (combine 2 3)

7. etc
*/

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

const EvaTC = require("../src/EvaTC");
const evaParser = require("../parser/evaParser");
const fs = require("fs");

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

    try {
        eva.tcGlobal(exp)
        console.log('No errors!')
    } catch (e) {
        console.error(e)
    }
}

/**
 * Examples:
 *
 * ./bin/eva-tc -e (2 3)'
 * ./bin/eva-tc -f ~/test.eva
 */
function main(argv) {
    const [_node, _path, mode, exp] = argv

    const eva = new EvaTC()

    // 1.Direct expression:
    if (mode === '-e') {
        return tcGlobal(exp, eva)
    }

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

main(process.argv)