lisp

lisp.test.ts

import {
  applyLisp,
  CondAst,
  structTokens,
  DefineAst,
  Env,
  evalLisp,
  IfAst,
  LambdaAst,
  parseLisp,
  PrimitiveAst,
  ProcedureAst,
  SequenceAst,
  SetAst,
  tokenize,
  VariableAst,
  formatLisp,
} from '../lisp'

describe('basic', () => {
  const primitiveAdd = new VariableAst('+')
  const primitiveMore = new VariableAst('>')
  const primitiveLess = new VariableAst('<')
  const primitiveEq = new VariableAst('=')
  it('primitive', () => {
    expect(evalLisp(new PrimitiveAst(1))).toBe(1)
    expect(evalLisp(new PrimitiveAst(false))).toBe(false)
    expect(evalLisp(new PrimitiveAst('hello'))).toBe('hello')
    expect(() => evalLisp(new PrimitiveAst([1, 2]))).toThrowError()
  })
  it('variable', () => {
    expect(evalLisp(new VariableAst('name'), new Env().extend({ name: 'liuli' }))).toBe('liuli')
    expect(() => evalLisp(new VariableAst('name'))).toThrowError()
  })
  describe('if', () => {
    it('basic', () => {
      expect(evalLisp(new IfAst(new PrimitiveAst(true), new PrimitiveAst(true), new PrimitiveAst(false)))).toBe(true)
      expect(evalLisp(new IfAst(new PrimitiveAst(false), new PrimitiveAst(true), new PrimitiveAst(false)))).toBe(false)
    })
    it('variable', () => {
      expect(
        evalLisp(
          new IfAst(new VariableAst('hasName'), new PrimitiveAst(true), new PrimitiveAst(false)),
          new Env().extend({
            hasName: true,
          }),
        ),
      ).toBe(true)
    })
    it('expression', () => {})
  })
  it('cond', () => {
    const cond = new CondAst(
      [
        [new PrimitiveAst(false), new PrimitiveAst(1)],
        [new VariableAst('x'), new PrimitiveAst(2)],
        [new ProcedureAst(primitiveEq, [new VariableAst('y'), new PrimitiveAst(3)]), new PrimitiveAst(3)],
      ],
      new PrimitiveAst(0),
    )
    expect(evalLisp(cond, new Env().extend({ x: true, y: 3 }))).toBe(2)
    expect(evalLisp(cond, new Env().extend({ x: false, y: 3 }))).toBe(3)
    expect(evalLisp(cond, new Env().extend({ x: false, y: 0 }))).toBe(0)
  })
  describe('define', () => {
    it('basic', () => {
      const env = new Env()
      evalLisp(new DefineAst('name', new PrimitiveAst('liuli')), env)
      expect(evalLisp(new VariableAst('name'), env)).toBe('liuli')
    })
    it('repeated define', () => {
      expect(() =>
        evalLisp(
          new SequenceAst([
            new DefineAst('name', new PrimitiveAst('liuli')),
            new DefineAst('name', new PrimitiveAst('liuli')),
          ]),
        ),
      ).toThrowError()
    })
  })
  describe('set', () => {
    it('basic', () => {
      const res = evalLisp(
        new SequenceAst([
          new DefineAst('name', new PrimitiveAst('liuli')),
          new SetAst('name', new PrimitiveAst('li')),
          new VariableAst('name'),
        ]),
      )
      expect(res).toBe('li')
    })
    it('error set', () => {
      expect(() => evalLisp(new SetAst('name', new PrimitiveAst('li')))).toThrowError()
    })
  })
  it('sequence', () => {
    const res = evalLisp(new SequenceAst([new DefineAst('name', new PrimitiveAst('liuli')), new VariableAst('name')]))
    expect(res).toBe('liuli')
  })
  it('lambda', () => {
    const fn = new LambdaAst([], new PrimitiveAst(1), false)
    expect(applyLisp(evalLisp(fn), [])).toBe(1)
    expect(evalLisp(new ProcedureAst(fn, []))).toBe(1)
  })
  describe('procedure', () => {
    it('primitive', () => {
      expect(applyLisp(evalLisp(primitiveAdd), [1, 2])).toBe(3)
      expect(applyLisp(evalLisp(primitiveMore), [1, 2])).toBe(false)
      expect(applyLisp(evalLisp(primitiveLess), [1, 2])).toBe(true)
    })
    it('wrap', () => {
      const add = new LambdaAst(
        ['x', 'y'],
        new ProcedureAst(primitiveAdd, [new VariableAst('x'), new VariableAst('y')]),
        false,
      )
      expect(applyLisp(evalLisp(add), [1, 2])).toBe(3)
      expect(evalLisp(new ProcedureAst(add, [new PrimitiveAst(1), new PrimitiveAst(2)]))).toBe(3)
    })
    it('close', () => {
      const closeFn = new LambdaAst(
        ['x'],
        new ProcedureAst(primitiveAdd, [new VariableAst('x'), new VariableAst('y')]),
        false,
      )
      expect(applyLisp(evalLisp(closeFn, new Env().extend({ y: 1 })), [1])).toBe(2)
      const ast = new SequenceAst([
        new DefineAst('x', new PrimitiveAst(1)),
        new DefineAst('y', new VariableAst('x')),
        new ProcedureAst(closeFn, [new PrimitiveAst(2)]),
      ])
      expect(evalLisp(ast)).toBe(3)
    })
    it('basic', () => {
      const returnSelf = new LambdaAst(['x'], new VariableAst('x'), false)
      expect(applyLisp(evalLisp(returnSelf), [1])).toBe(1)
    })
    it('restArgs', () => {
      const lambda = new LambdaAst(['numbers'], new VariableAst('numbers'), true)
      console.log(applyLisp(evalLisp(lambda), [1, 2]))
      // expect(applyLisp(evalLisp(lambda, {}), [1, 2])).toBe(1)
    })
    describe('cons', () => {
      const cons = new LambdaAst(
        ['car', 'cdr'],
        new LambdaAst(
          ['action'],
          new CondAst(
            [
              [
                new ProcedureAst(primitiveEq, [new VariableAst('action'), new PrimitiveAst('car')]),
                new VariableAst('car'),
              ],
              [
                new ProcedureAst(primitiveEq, [new VariableAst('action'), new PrimitiveAst('cdr')]),
                new VariableAst('cdr'),
              ],
              [
                new ProcedureAst(primitiveEq, [new VariableAst('action'), new PrimitiveAst('setCar')]),
                new LambdaAst(['val'], new SetAst('car', new VariableAst('val')), false),
              ],
              [
                new ProcedureAst(primitiveEq, [new VariableAst('action'), new PrimitiveAst('setCdr')]),
                new LambdaAst(['val'], new SetAst('cdr', new VariableAst('val')), false),
              ],
            ],
            new PrimitiveAst('error'),
          ),
          false,
        ),
        false,
      )
      it('basic', () => {
        const numbers = applyLisp(evalLisp(cons), [1, 2])
        expect(applyLisp(numbers, ['car'])).toBe(1)
        expect(applyLisp(numbers, ['cdr'])).toBe(2)
      })
      const car = new LambdaAst(['cons'], new ProcedureAst(new VariableAst('cons'), [new PrimitiveAst('car')]), false)
      const cdr = new LambdaAst(['cons'], new ProcedureAst(new VariableAst('cons'), [new PrimitiveAst('cdr')]), false)

      it('car/cdr', () => {
        const numbers = applyLisp(evalLisp(cons), [1, 2])
        expect(applyLisp(evalLisp(car), [numbers])).toBe(1)
        expect(applyLisp(evalLisp(cdr), [numbers])).toBe(2)
      })
      const setCar = new LambdaAst(
        ['cons', 'val'],
        new ProcedureAst(new ProcedureAst(new VariableAst('cons'), [new PrimitiveAst('setCar')]), [
          new VariableAst('val'),
        ]),
        false,
      )
      const setCdr = new LambdaAst(
        ['cons', 'val'],
        new ProcedureAst(new ProcedureAst(new VariableAst('cons'), [new PrimitiveAst('setCdr')]), [
          new VariableAst('val'),
        ]),
        false,
      )
      it('set', () => {
        const numbers = applyLisp(evalLisp(cons), [1, 2])
        applyLisp(evalLisp(setCar), [numbers, 11])
        expect(applyLisp(evalLisp(car), [numbers])).toBe(11)
        applyLisp(evalLisp(setCdr), [numbers, 12])
        expect(applyLisp(evalLisp(cdr), [numbers])).toBe(12)
      })
    })
  })
})

describe('parser', () => {
  it('basic', () => {
    expect(structTokens(tokenize('(+ 1 2)'))).toEqual(['+', '1', '2'])
    expect(structTokens(tokenize('(true)'))).toEqual(['true'])
    console.log(tokenize('(begin (define x 1) (define y 2) (+ x y))').length)
    expect(structTokens(tokenize('(begin (define x 1) (define y 2) (+ x y))'))).toEqual([
      'begin',
      ['define', 'x', '1'],
      ['define', 'y', '2'],
      ['+', 'x', 'y'],
    ])
  })
  it('lambda not args', () => {
    expect(evalLisp(parseLisp('((lambda () 1))'))).toBe(1)
    expect(
      evalLisp(
        parseLisp(`
    (begin
      (define x 1)
      (define (foo) (begin
        (set x (+ x 1))
        x
        ))
      (foo)
      (foo)
      (foo)
      )
    `),
      ),
    ).toBe(4)
  })
  it('parse', () => {
    expect(evalLisp(parseLisp('"liuli"'))).toBe('liuli')
    expect(evalLisp(parseLisp('(+ 1 2)'))).toBe(3)
    expect(evalLisp(parseLisp('(+ 1.1 3.3)'))).toBe(4.4)
    expect(evalLisp(parseLisp('true'))).toBe(true)
    expect(evalLisp(parseLisp('(begin (define x 1) (define y 2) (+ x y))'))).toBe(3)
    expect(evalLisp(parseLisp('(if true 0 1)'))).toBe(0)
    expect(evalLisp(parseLisp('(if false 0 1)'))).toBe(1)
    expect(evalLisp(parseLisp('(cond (false 0) (false 1))'))).toBe(null)
    expect(evalLisp(parseLisp('(cond (false 0) (false 1) (else 2))'))).toBe(2)
    expect(evalLisp(parseLisp('(cond (false 0) (true 1) (else 2))'))).toBe(1)
    expect(evalLisp(parseLisp('((lambda (x y) (+ x y)) 1 2)'))).toBe(3)
    expect(evalLisp(parseLisp('(begin (define (add x y) (+ x y)) (add 1 2))'))).toBe(3)
    expect(evalLisp(parseLisp('(begin 1 2)'))).toBe(2)
    expect(evalLisp(parseLisp('(begin (define x 1) (set x 2) x)'))).toBe(2)
    expect(
      evalLisp(
        parseLisp(`
      (
        begin
        (define (cons a b) (
          lambda (action) (
            cond
            ((= action "car") a)
            ((= action "cdr") b)
          )
        ))
        (define (car cons) (cons "car"))
        (define (cdr cons) (cons "cdr"))
        (define v (cons 1 2))
        (+ (car v) (cdr v))
      )
    `),
      ),
    ).toBe(3)
  })
})

describe('format', () => {
  it('basic', () => {
    console.log(formatLisp(parseLisp('1')))
    console.log(formatLisp(parseLisp('(+ 1 2)')))
    console.log(formatLisp(parseLisp('(if true 0 1)')))
    console.log(formatLisp(parseLisp('(cond (false 0) (false 1))')))
    console.log(formatLisp(parseLisp('(cond (false 0) (false 1) (else 2))')))
    console.log(formatLisp(parseLisp('((lambda (x y) (+ x y)) 1 2)')))
    console.log(formatLisp(parseLisp('(define x 1)')))
    console.log(formatLisp(parseLisp('(define add (lambda (x y) (+ x y)))')))
    console.log(formatLisp(parseLisp('(define (add x y) (+ x y))')))
    console.log(formatLisp(parseLisp('(begin (define (add x y) (+ x y)) (add 1 2))')))
    console.log(formatLisp(parseLisp('(begin (define x 1) (set x 2) x)')))
    console.log(formatLisp(parseLisp('(begin 1 2)')))
    console.log(
      formatLisp(
        parseLisp(`
  (
    begin
    (define (cons a b) (
      lambda (action) (
        cond
        ((= action "car") a)
        ((= action "cdr") b)
        ((= action "setCar") (lambda (v) (set a v)))
        ((= action "setCdr") (lambda (v) (set b v)))
      )
    ))
    (define (car cons) (cons "car"))
    (define (cdr cons) (cons "cdr"))
    (define v (cons 1 2))
    (+ (car v) (cdr v))
  )
`),
      ),
    )
  })
})

lisp.ts

type AstType = 'primitive' | 'variable' | 'define' | 'set' | 'if' | 'cond' | 'begin' | 'lambda' | 'application'

export class Env {
  private readonly map = new Map<string, any>()
  constructor(private readonly prototype: Env | null = null) {}
  get(k: string): any {
    return this.map.has(k) ? this.map.get(k) : this.prototype !== null ? this.prototype.get(k) : null
  }
  define(k: string, v: any) {
    if (this.map.has(k)) {
      throw new Error(`变量 ${k} 已定义`)
    }
    this.map.set(k, v)
  }
  set(k: string, v: any): any {
    if (this.map.has(k)) {
      this.map.set(k, v)
      return
    }
    if (this.prototype === null) {
      throw new Error(`当前环境没有定义 ${k}`)
    }
    this.prototype.set(k, v)
  }
  extend(args: Record<string, any>) {
    const env = new Env(this)
    Object.entries(args).forEach(([k, v]) => {
      env.map.set(k, v)
    })
    return env
  }
}

export interface IAst {
  readonly type: AstType
  eval(env: Env): any
}

interface IApplyAst {
  apply(args: any[]): any
}

export class PrimitiveAst implements IAst {
  readonly type: AstType = 'primitive'
  constructor(readonly value: any) {}
  eval() {
    if (this.value === null) {
      return null
    }
    if (!['string', 'number', 'boolean'].includes(typeof this.value)) {
      throw new Error('不支持的类型 ' + typeof this.value)
    }
    return this.value
  }
}

class PrimitiveLambdaAst implements IAst, IApplyAst {
  readonly type: AstType = 'lambda'
  constructor(readonly name: string) {}
  eval(env: Env) {
    return this
  }
  static readonly symbols = ['+', '>', '<', '=']
  apply(args: any[]) {
    if (this.name === '+') {
      return args.reduce((r, i) => r + i, 0)
    }
    if (this.name === '>') {
      return args[0] > args[1]
    }
    if (this.name === '<') {
      return args[0] < args[1]
    }
    if (this.name === '=') {
      return args[0] === args[1]
    }
    throw new Error('不支持的 api ' + this.name)
  }
}

export class VariableAst implements IAst {
  readonly type: AstType = 'variable'
  constructor(readonly name: string) {}
  eval(env: Env) {
    const res = env.get(this.name)
    if (res === null) {
      if (PrimitiveLambdaAst.symbols.includes(this.name)) {
        return new PrimitiveLambdaAst(this.name).eval(env)
      }
      throw new Error('变量未定义 ' + this.name)
    }
    return res
  }
}

export class IfAst implements IAst {
  readonly type: AstType = 'if'
  constructor(readonly predict: IAst, readonly left: IAst, readonly right: IAst) {}
  eval(env: Env) {
    return this.predict.eval(env) ? this.left.eval(env) : this.right.eval(env)
  }
}

export class CondAst implements IAst {
  readonly type: AstType = 'cond'
  constructor(readonly clauses: [predict: IAst, value: IAst][], readonly defaultValue: IAst | null) {}
  eval(env: Env) {
    const findClause = this.clauses.find((item) => item[0].eval(env))
    return findClause ? findClause[1].eval(env) : this.defaultValue ? this.defaultValue.eval(env) : null
  }
}

export class DefineAst implements IAst {
  readonly type: AstType = 'define'
  constructor(readonly name: string, readonly value: IAst) {}
  eval(env: Env) {
    if (env.get(this.name)) {
      throw new Error(`变量 ${this.name} 已存在，不能重复定义`)
    }
    return env.define(this.name, this.value.eval(env))
  }
}
export class SetAst implements IAst {
  readonly type: AstType = 'set'
  constructor(readonly name: string, readonly value: IAst) {}
  eval(env: Env) {
    if (env.get(this.name) === null) {
      throw new Error(`变量 ${this.name} 不存在，不能设置值`)
    }
    return env.set(this.name, this.value.eval(env))
  }
}

export class SequenceAst implements IAst {
  readonly type: AstType = 'begin'
  constructor(readonly exps: IAst[]) {}
  eval(env: Env) {
    return this.exps.reduce((_, exp) => exp.eval(env), null)
  }
}

export class ProcedureAst implements IAst {
  readonly type: AstType = 'application'
  constructor(readonly operator: IAst, readonly operands: IAst[]) {}
  eval(env: Env) {
    return applyLisp(
      this.operator.eval(env),
      this.operands.map((ast) => ast.eval(env)),
    )
  }
}
export class LambdaAst implements IAst, IApplyAst {
  readonly type: AstType = 'lambda'
  constructor(readonly args: string[], readonly body: IAst, readonly restArgs: boolean) {}
  env!: Env
  eval(env: Env) {
    // 绑定环境，然后什么都不做
    this.env = env
    return this
  }
  apply(args: any[]) {
    return this.body.eval(this.env.extend(this.pairArgs(this.args, args)))
  }
  private pairArgs(argNames: string[], args: any[]): Record<string, any> {
    return argNames.reduce((r, k, i) => {
      if (i === argNames.length - 1 && this.restArgs) {
        r[k] = args.slice(i)
      } else {
        r[k] = args[i]
      }
      return r
    }, {} as Record<string, any>)
  }
}

/**
 * 计算 lisp 表达式
 * @param ast
 * @param env
 * @returns
 */
export function evalLisp(ast: IAst, env: Env = new Env()): any {
  return ast.eval(env)
}
/**
 * 执行一个 lisp 函数
 * @param ast
 * @param args
 * @returns
 */
export function applyLisp(ast: IAst & IApplyAst, args: any[]): any {
  return ast.apply(args)
}

/**
 * 解析代码为 token 数组（一维）
 * @param code
 * @returns
 */
export function tokenize(code: string): string[] {
  return code
    .replaceAll('(', ' ( ')
    .replaceAll(')', ' ) ')
    .split(' ')
    .map((i) => i.trim())
    .filter((i) => i.length !== 0)
}

type DeepArray<T> = (T | DeepArray<T>)[]

/**
 * 将平铺的 tokens 结构化，包含层次关系（使用多维数组）
 * @param tokens
 * @returns
 */
export function structTokens(tokens: string[]): DeepArray<string> {
  function iter(i: number, curr: DeepArray<string>): DeepArray<string> {
    if (i === tokens.length) {
      return curr
    }
    if (tokens[i] === '(') {
      curr.push([])
      return iter(i + 1, curr)
    }
    if (tokens[i] === ')') {
      const sub = curr.pop()!
      ;(curr[curr.length - 1] as DeepArray<string>).push(sub)
      return iter(i + 1, curr)
    }
    ;(curr[curr.length - 1] as DeepArray<string>).push(tokens[i])
    return iter(i + 1, curr)
  }
  return iter(0, [[]])[0][0] as DeepArray<string>
}

/**
 * 解析 lisp 代码为 ast
 * @param code
 */
export function parseLisp(code: string): IAst {
  const map: Partial<Record<AstType, (token: string[]) => IAst>> = {
    define(token) {
      const name = token[1]
      if (Array.isArray(name)) {
        return new DefineAst(
          name[0],
          new LambdaAst(name.slice(1) as unknown as string[], readFromToken(token[2]), false),
        )
      }
      return new DefineAst(name, readFromToken(token[2]))
    },
    set(token) {
      const name = token[1]
      return new SetAst(name, readFromToken(token[2]))
    },
    begin(token) {
      return new SequenceAst(token.slice(1).map(readFromToken))
    },
    if(token) {
      return new IfAst(readFromToken(token[1]), readFromToken(token[2]), readFromToken(token[3]))
    },
    cond(token) {
      if (token[token.length - 1][0] === 'else') {
        return new CondAst(
          token.slice(1, token.length - 1).map(([p, v]) => [readFromToken(p), readFromToken(v)]),
          readFromToken(token[token.length - 1][1]),
        )
      } else {
        return new CondAst(
          token.slice(1).map(([p, v]) => [readFromToken(p), readFromToken(v)]),
          null,
        )
      }
    },
    lambda(token) {
      return new LambdaAst(token[1] as unknown as string[], readFromToken(token[2]), false)
    },
  }
  function readFromToken(token: string | string[]): IAst {
    if (Array.isArray(token)) {
      const op = token[0]
      const parse = map[op as AstType]
      return parse ? parse(token) : new ProcedureAst(readFromToken(token[0]), token.slice(1).map(readFromToken))
    }
    if (typeof token !== 'string') {
      throw new Error('不支持的 token 类型 ' + typeof token)
    }
    return atom(token)
  }
  function atom(token: string): IAst {
    if (/^\d$/.test(token)) {
      return new PrimitiveAst(Number.parseInt(token))
    }
    if (/^([0-9]{1,}[.][0-9]*)$/.test(token)) {
      return new PrimitiveAst(Number.parseFloat(token))
    }
    if (/^".*"$/.test(token)) {
      return new PrimitiveAst(token.slice(1, token.length - 1))
    }
    if (['true', 'false'].includes(token)) {
      return new PrimitiveAst(token === 'true')
    }
    return new VariableAst(token)
  }
  return readFromToken(structTokens(tokenize(code)) as any)
}

/**
 * 格式化 ast 为代码
 * 使用非常简单的策略
 * @param ast
 * @returns
 */
export function formatLisp(ast: IAst): string {
  const options = {
    tab: 2,
    length: 80,
  }
  function fill(tab: number) {
    return ' '.repeat(tab * options.tab)
  }
  function layout(s: string) {
    return s
      .split('\n')
      .map((s) => `${fill(1)}${s}`)
      .join('\n')
  }
  const map: Record<AstType, (ast: IAst, tab: number) => string> = {
    primitive(ast) {
      return (ast as PrimitiveAst).value
    },
    variable(ast) {
      return (ast as VariableAst).name
    },
    if(ast, tab) {
      const _ = ast as IfAst
      return `(if ${format(_.predict, tab)}\n${format(_.left, tab)}\n${format(_.right, tab)})`
    },
    cond(ast, tab) {
      const _ = ast as CondAst
      const elseStr = _.defaultValue ? ` else ${format(_.defaultValue, tab)}` : ''
      return `(cond ${_.clauses
        .map(([p, v]) => `\n  (${format(p, tab)} ${format(v, tab)})`)
        .map((s) => layout(s))
        .join('')}${elseStr})`
    },
    lambda(ast, tab) {
      const _ = ast as LambdaAst
      return `(lambda (${_.args.join(' ')}) \n  ${layout(format(_.body, tab))})`
    },
    define(ast, tab) {
      const _ = ast as DefineAst
      return `(define ${_.name} ${format(_.value, tab)})`
    },
    set(ast, tab) {
      const _ = ast as DefineAst
      return `(set ${_.name} ${format(_.value, tab)})`
    },
    begin(ast, tab) {
      const _ = ast as SequenceAst
      return `(begin ${_.exps
        .map((exp) => format(exp, tab + 1))
        .map((s) => `\n  ${s}`)
        .join('')})`
    },
    application(ast, tab) {
      return `(${format((ast as ProcedureAst).operator, tab)} ${(ast as ProcedureAst).operands
        .map((exp) => format(exp, tab))
        .join(' ')})`
    },
  }
  function format(ast: IAst, tab: number): string {
    return map[ast.type](ast, tab)
  }
  return format(ast, 0)
}