lisp.ts

//TODO: add symbol
type List = Array<any>
type Atom = String | Number | Boolean
type Expression = Atom | List | Procedure | Function

const zip = (a: any[], b : any[], zipFunc? : (x : any, y : any) => any) => 
    zipFunc ? a.map((value, index) => zipFunc(value, b[index])) 
        : a.map((value, index) => [value, b[index]]);

class Environment {
    outer : Environment
    context = {}

    constructor (params : Array<any> = [], 
        args:Array<any> = [], 
        outer : Environment = null) {

        this.outer = outer
        Object.assign(this.context, 
            zip(params, args, (parm, arg) => ({key : parm, value : arg }))
            .reduce((obj, item : { key : string, value : any}) =>{
                obj[item.key] = item.value
                return obj
            }, {}))
    }

    public insert = (key: string, expression: Expression): any => { 
        this.context[key] = expression
        return expression
    }

    public find = (key : string) : Expression => 
        (key in this.context) ? this.context[key] : this.outer.find(key)

    static create = (context : any) : Environment => {
        let env = new Environment()
        Object.assign(env.context, context)
        return env
    }
}

class Procedure {
    params : string[]
    body : Expression
    environment : Environment

    constructor (params:string[], body, env : Environment) {
        this.params = params
        this.body = body
        this.environment = env
    }

    public call(...args) {
        return evaluate(this.body, 
            new Environment(this.params, args, this.environment))
    }
}

const tokenise = (chars : string) : string[] => 
    chars.replace(/[(]/g, ' ( ').replace(/[)]/g, ' ) ')
        .trim()
        .split(/\s+/) 

const isNumeric = (s : any) : boolean => !isNaN(s)

const isBoolean = (s : string) : boolean => /(true|false)/.test(s)

const atom = (token : string) : Atom => 
    isNumeric (token) ? Number(token) 
        : isBoolean(token) ? Boolean(token)
        : String(token)

const readFromTokens = (tokens : string[]) : Expression => {
    if (tokens.length == 0) throw SyntaxError('unexpected end of file')

    let currentToken = tokens.shift()
    if (currentToken == '(') {
        let expression : Expression = []
        while (tokens[0] != ')') expression.push(readFromTokens(tokens))
        tokens.shift()
        return expression
    } 

    if (currentToken == ')') throw SyntaxError('unexpected token \')\'')

    return atom(currentToken)
} 

const parse = (program : string) : Expression => readFromTokens(tokenise(program))

const evaluate = (expression : Expression, environment : Environment) : Expression => {
    if (typeof expression == 'string') return environment.find(expression)
    if (typeof expression == 'number') return expression as Number
    if (typeof expression == 'boolean') return expression as Boolean

    let [operator, ...args] = expression as List
    if (operator === 'if') {
        let [_, condition, consequence, alternative] = expression as List
        let exp = evaluate(condition, environment) === true ? consequence : alternative 
        return evaluate(exp, environment)
    }

    if (operator === 'def') {
        let [_, symbol, subExpression] = expression as List
        return environment.insert(symbol, evaluate(subExpression, environment))
    }

    if (operator === '\\' || operator ==='lambda') {
        let [parameters, body] = args
        return new Procedure(parameters, body, environment)
    }

    let proc = evaluate(operator, environment) as Procedure | Function
    let values = args.map(arg => evaluate(arg, environment))
    return proc instanceof Procedure
        ? proc.call(...values)
        : proc(...values)
}

const expressionString = (expression : Expression) : string =>
    expression instanceof Array 
        ? `(${expression.map(exp => expressionString(exp)).join(' ')})`
        : `${expression}`

const standardEnvironment = () : Environment => Environment.create({
    '+': (...x) => x.reduce((sum, i) => sum + i, 0),
    '*': (...x) => x.reduce((acc, i) => acc * i, 1),
    '>': (x, y) => x > y,
    '<': (x, y) => x < y,
    '>=': (x, y) => x >= y,
    '<=': (x, y) => x <= y,
    'apply': (proc, args) => proc(...args),
    //TODO: refactor
    'map' : (func : Function | Procedure, list) => 
        list.map(x => func instanceof Procedure ? func.call(x) : func(x)) ,
    'reduce' : (func : Function | Procedure, init, list) => 
        list.reduce((acc, x) => func instanceof Procedure 
            ? func.call(acc, x) 
            : func(acc, x), init),
    'car': x => x[0],
    'cdr': x => { let [head, ...rest] = x; return rest }, 
    'cons': (...x) => { let [head, rest] = x; return [head, ...rest] },
    'eq?': (x, y) => x === y, 
    'list': (...x) => [...x], 
    'list?': x => Array.isArray(x), 
    'not' : x => x === true ? false : true,
    'null?' : x => x === [],
    'max': Math.max,
    'min': Math.min,
    'log': console.log,
    'pi': Math.PI,
    'go': (...x) => x[x.length - 1]
})

let program = `
    (go 
        (def r 10) 
        (def circle-area (\\ (r) (* pi (* r r))))

        (def area (circle-area 3))

        (def my-list (list 2 3 4))
        (def cons-list (cons area ))
        (car (cdr cons-list) )

        (def sq (\\ (x) (* x 2) ))
        (reduce + 0 (map sq (list 1 2 3 4)))
    )
`

let res = expressionString(evaluate(parse(program), standardEnvironment()))

res