gistfile1.ts

module AST {
    export class Expr {
    }

    export class BooleanExpr extends Expr {
        value: boolean;

        constructor(value: boolean) {
            super();
            this.value = value;
        }
    }

    export class NumberExpr extends Expr {
        value: number;

        constructor(value: number) {
            super();
            this.value = value;
        }
    }

    export class RefExpr extends Expr {
        name: string;

        constructor(name: string) {
            super();
            this.name = name;
        }
    }

    export class LetExpr extends Expr {
        name: string;
        value: Expr;
        in: Expr;

        constructor(name: string, value: Expr, in_: Expr) {
            super();
            this.name = name;
            this.value = value;
            this.in = in_;
        }
    }

    export class CallExpr extends Expr {
        function: Expr;
        argument: Expr;

        constructor(function_: Expr, argument: Expr) {
            super();
            this.function = function_;
            this.argument = argument;
        }
    }

    export class IfExpr extends Expr {
        condition: Expr;
        trueBranch: Expr;
        falseBranch: Expr;

        constructor(condition: Expr, trueBranch: Expr, falseBranch: Expr) {
            super();
            this.condition = condition;
            this.trueBranch = trueBranch;
            this.falseBranch = falseBranch;
        }
    }

    export class FFIExpr extends Expr {
        js: string;

        constructor(js: string) {
            super();
            this.js = js;
        }
    }
}

module JS {
    export class Stmt {
    }

    export class ReturnStmt extends Stmt {
        value: Expr;

        constructor(value: Expr = null) {
            super();
            this.value = value;
        }

        toString() {
            return 'return ' + this.value.toString() + ';';
        }
    }

    export class Expr {
    }

    export class BooleanExpr extends Expr {
        value: boolean;

        constructor(value: boolean) {
            super();
            this.value = value;
        }

        toString() {
            return this.value ? 'true' : 'false';
        }
    }

    export class NumberExpr extends Expr {
        value: number;

        constructor(value: number) {
            super();
            this.value = value;
        }

        toString() {
            return this.value.toString();
        }
    }

    export class RefExpr extends Expr {
        referee: string;

        constructor(referee: string) {
            super();
            this.referee = referee;
        }

        toString() {
            return this.referee;
        }
    }

    export class FunctionExpr extends Expr {
        parameters: string[];
        body: Stmt[];

        constructor(parameters: string[], body: Stmt[]) {
            super();
            this.parameters = parameters;
            this.body = body;
        }

        toString() {
            var result = '(function(';
            result += this.parameters.join(', ');
            result += ') {\n';
            result += this.body.map(stmt => stmt.toString().split('\n').map(line => '    ' + line).join('\n')).join('\n');
            result += '\n})';
            return result;
        }
    }

    export class CallExpr extends Expr {
        function: Expr;
        arguments: Expr[];

        constructor(function_: Expr, arguments: Expr[]) {
            super();
            this.function = function_;
            this.arguments = arguments;
        }

        toString() {
            var result = this.function.toString();
            result += '(';
            result += this.arguments.map(argument => argument.toString());
            result += ')';
            return result;
        }
    }

    export class ConditionalExpr extends Expr {
        condition: Expr;
        trueBranch: Expr;
        falseBranch: Expr;

        constructor(condition: Expr, trueBranch: Expr, falseBranch: Expr) {
            super();
            this.condition = condition;
            this.trueBranch = trueBranch;
            this.falseBranch = falseBranch;
        }

        toString() {
            var result = this.condition.toString();
            result += ' ? ';
            result += this.trueBranch.toString();
            result += ' : ';
            result += this.falseBranch.toString();
            return result;
        }
    }

    export class LiteralExpr extends Expr {
        js: string;

        constructor(js: string) {
            super();
            this.js = js;
        }

        toString() {
            return '(' + this.js + ')';
        }
    }
}

interface Symbol {
    type: Type;

    typeWhenApplied(argumentType: Type): Type;
}

class Environment {
    private parent: Environment;
    private symbols: { [name: string]: Symbol };

    constructor(parent: Environment = null) {
        this.parent = parent;
        this.symbols = {};
    }

    add(name: string, symbol: Symbol) {
        if (this.symbols.hasOwnProperty(name)) {
            throw new Error("'" + name + "' already defined");
        }
        this.symbols[name] = symbol;
    }

    get(name: string) {
        if (this.symbols.hasOwnProperty(name)) {
            return this.symbols[name];
        } else if (this.parent !== null) {
            return this.parent.get(name);
        } else {
            return null;
        }
    }
}

class Type implements Symbol {
    type: Type;

    typeWhenApplied(argumentType: Type): Type {
        throw new Error('types cannot be applied');
    }
}

var AnyType = new Type();
AnyType.typeWhenApplied = (argumentType: Type) => {
    return AnyType;
};

var BooleanType = new Type();

var NumberType = new Type();

class Let implements Symbol {
    type: Type;

    typeWhenApplied(argumentType: Type) {
        return this.type.typeWhenApplied(argumentType);
    }
}

function findCommonType(...types: Type[]) {
    if (types.length === 0) {
        throw new Error('ICE');
    }
    var commonType = types[0];
    for (var i = 1; i < types.length; ++i) {
        if (types[i] !== commonType) {
            return null;
        }
    }
    return commonType;
}

function compileExpr(env: Environment, expr: AST.Expr): { type: Type; js: JS.Expr } {
    switch (true) {
        case (expr instanceof AST.BooleanExpr):
            var booleanExpr = <AST.BooleanExpr>expr;
            return { type: BooleanType, js: new JS.BooleanExpr(booleanExpr.value) };

        case (expr instanceof AST.NumberExpr):
            var numberExpr = <AST.NumberExpr>expr;
            return { type: NumberType, js: new JS.NumberExpr(numberExpr.value) };

        case (expr instanceof AST.RefExpr):
            var refExpr = <AST.RefExpr>expr;
            var referee = env.get(refExpr.name);
            if (referee === null) {
                throw new Error("'" + refExpr.name + "' not in scope");
            }
            return { type: referee.type, js: new JS.RefExpr(refExpr.name) };

        case (expr instanceof AST.LetExpr):
            var letExpr = <AST.LetExpr>expr;

            var letEnv = new Environment(env);
            var let_ = new Let();
            letEnv.add(letExpr.name, let_);

            // TODO: Allow recursive lets.
            var value = compileExpr(env, letExpr.value);
            let_.type = value.type;

            var in_ = compileExpr(letEnv, letExpr.in);

            return {
                type: in_.type,
                js: new JS.CallExpr(new JS.FunctionExpr([letExpr.name], [new JS.ReturnStmt(in_.js)]), [value.js])
            };

        case (expr instanceof AST.CallExpr):
            var callExpr = <AST.CallExpr>expr;

            var function_ = compileExpr(env, callExpr.function);
            var argument = compileExpr(env, callExpr.argument);

            return {
                type: function_.type.typeWhenApplied(argument.type),
                js: new JS.CallExpr(function_.js, [argument.js])
            };

        case (expr instanceof  AST.IfExpr):
            var ifExpr = <AST.IfExpr>expr;

            var condition = compileExpr(env, ifExpr.condition);
            var trueBranch = compileExpr(env, ifExpr.trueBranch);
            var falseBranch = compileExpr(env, ifExpr.falseBranch);

            if (condition.type !== BooleanType) {
                throw new Error('conditions must be Booleans');
            }

            var commonType = findCommonType(trueBranch.type, falseBranch.type);
            if (commonType === null) {
                throw new Error('cannot determine type of if expression');
            }

            return {
                type: commonType,
                js: new JS.ConditionalExpr(condition.js, trueBranch.js, falseBranch.js)
            };

        case (expr instanceof AST.FFIExpr):
            var ffiExpr = <AST.FFIExpr>expr;
            return {
                type: AnyType,
                js: new JS.LiteralExpr(ffiExpr.js)
            };

        default:
            throw new Error('ICE');
    }
}

console.log(compileExpr(new Environment(), new AST.LetExpr('log', new AST.FFIExpr('console.log.bind(console)'), new AST.CallExpr(new AST.RefExpr('log'), new AST.IfExpr(new AST.BooleanExpr(true), new AST.NumberExpr(42), new AST.NumberExpr(3.14))))).js.toString());