实现一个玩具 lisp 运行时与解析器

前言

之前看元循环求值器一节中使用 lisp 实现了一个 lisp 的运行时，吾辈也尝试使用 ts 来实现它。首先，这里展示一张曾经在书中出现过的图，表示一个运行时的基本组成是由 eval 和 apply 组成（看起来很像太极就是了）。eval 负责执行一个表达式，在 lisp 中，所有的代码都是表达式，这没什么问题。apply 则负责执行一个函数，将计算实参列表，并创建一个新的闭包环境绑定到形参上。

环境是一个有趣的话题，最初，吾辈了解到的是代换模型，即 (+ (+ 1 2) 3) 也可以被替换为 (+ 1 2 3)。后来，接触到修改变量后，每个函数就会绑定环境，然后动态获取某些值。

例如执行代码

(define (add x y)
  (+ x y))
(add 1 2)

实现运行时

最初，吾辈也尝试使用 cons 实现，但后来发现面向对象更适合做这种事情（抽象语法树有不同的类型）。

考虑到复杂度的问题，目前实现了以下几种 ast

• primitive: 原始值，例如 number/boolean/string
• variable: 变量，从当前环境中获取值
• define: 在当前环境中定义新的值
• set: 修改当前环境中指定的值
• if: 条件判断，类似于三元表达式
• cond: 条件判断，类似于 if/else-if/else
• begin: 一系列表达式，结果为最后一个表达式的值
• lambda: 函数，包含参数、函数体与定义时的环境，可以被 apply 执行
• procedure: 一个需要执行的函数+参数

先定义基础的 ast 接口，其中 eval 是每种 ast 都必须实现的方法，apply 则仅在 lambda ast 中存在。

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

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

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

环境

然后实现 Env 环境变量，应该能够获取、新增、修改以及扩展为一个新的环境

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
  }
}

接下来我们分别实现每一个

原始值

原始值很简单，例如 1,2,3,4,5… 这样的数字，或 true/false 布尔值，亦或是 “hello world” 这种字符串，它们都是原始值，可以直接声明和使用，所以 ast 也仅仅是保存值，并且执行的时候返回而已。

export class PrimitiveAst implements IAst {
  readonly type: AstType = 'primitive'
  readonly value
  constructor(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
  }
}

variable/define/set 环境

variable/define/set 都是在操作环境，分别是获取、新增和修改。

有两点需要注意的地方

• variable 有点特殊，因为某些函数预先定义在语言中，例如 + - * / cons car cdr，它们不需要定义就可以使用（类似于浏览器的 native function），所以这里有一个仅在内部使用的 PrimitiveLambdaAst 类型，可以看到其中实现了 + > < = 这几个原生函数。
• 环境应该保存指向上一个环境的索引，这里为了简单实现使用了引用复制。

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 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))
  }
}

if/cond 条件判断

条件分支的 ast 很简单，许多语言中都有这种功能。

if/cond 可以相互替代，所以可以仅实现一种，然后替换另一种即可，这里由于比较简单所以实现了两种。

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
  }
}

sequence/procedure

sequence 表示一系列表达式，全部执行并返回最后一个的结果。例如以下代码应该返回 3

(begin
  (define (add x y) (+ x y))
  (define a 1)
  (define b 2)
  (add a b))

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)
  }
}

lambda/procedure

procedure/lambda 是最有趣的一部分，前者负责定义一个函数，后者则负责具体的调用。lambda ast 执行仅绑定了环境，并未真的执行。apply 则才会开辟一个新的环境，并将参数绑定新的环境上，然后执行函数体的代码。procedure 则计算一个表达式，表达式包含函数部分与参数部分，它会分别计算两者并最后应用 lambda ast 的 apply 方法。

考虑以下代码如何执行

(((lambda (x) (lambda (y) (+ x y))) 1) 2)

分为几步看

1. (lambda (x) (lambda (y) (+ x y))) 创建一个函数，它返回一个新的函数
2. ((lambda (x) (lambda (y) (+ x y))) 1) 应用了上面的函数，创建了一个新的环境，x 被绑定为 1，返回了一个新的函数，可以被认为转换为了表达式 (lambda (y) (+ 1 y))
3. 应用返回的函数，创建新的环境，将 y 绑定到 2
4. 是一个原生函数 +，直接得到结果 3

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>)
  }
}
export class ProcedureAst implements IAst {
  readonly type: AstType = 'procedure'
  constructor(readonly operator: IAst, readonly operands: IAst[]) {}
  eval(env: Env) {
    return applyLisp(
      this.operator.eval(env),
      this.operands.map((ast) => ast.eval(env)),
    )
  }
}

统一入口

然后，统一的入口 evalLisp/applyLisp 就很简单了

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

验证一下

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)
      })
    })
  })
})

解析代码为 ast

上面实现了执行 lisp ast 的功能，但如何将 lisp 代码解析为这种 ast 还没有实现，下面就来完成这一步。

解析代码为字符流

简单的处理为一个 token 数组很简单

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

将字符流结构化

但我们需要结构化的，所以还需要做一次转换

基本思路是每次处理一个字符

1. 如果是 (，则添加一个临时数组存储之后的值，直到遇到 ) 为止
2. 如果是 )，则将当前的临时数组合并到上一个临时数组
3. 如果是其他字符，则将之追加到当前临时数组中
4. 如果到了结尾，则返回当前的数组
5. 初始数组是 [[]]，最后返回 res[0][0]

这是一个基本的流程图

下面是解析代码 (begin (define x 1) (define y 2) (+ x y)) 的 tokens 流程中数组的状态

step	code	arr
init		[[]]
1	(	[[], []]
2	begin	[[], [begin]]
3	(	[[], [begin], []]
4	define	[[], [begin], [define]]
5	define	[[], [begin], [define]]
6	x	[[], [begin], [define, x]]
7	1	[[], [begin], [define, x, 1]]
8	)	[[], [begin, [define, x, 1]]]
9	(	[[], [begin, [define, x, 1]], []]
10	define	[[], [begin, [define, x, 1]], [define]]
11	y	[[], [begin, [define, x, 1]], [define, y]]
12	2	[[], [begin, [define, x, 1]], [define, y, 2]]
13	)	[[], [begin, [define, x, 1], [define, y, 2]]]
14	(	[[], [begin, [define, x, 1], [define, y, 2]], []]
15	+	[[], [begin, [define, x, 1], [define, y, 2]], [+]]
16	x	[[], [begin, [define, x, 1], [define, y, 2]], [+, x]]
17	y	[[], [begin, [define, x, 1], [define, y, 2]], [+, x, y]]
18	)	[[], [begin, [define, x, 1], [define, y, 2], [+, x, y]]]
19	)	[[[begin, [define, x, 1], [define, y, 2], [+, x, y]]]]

具体实现

/**
 * 解析代码为 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

最终，我们将结构化的 token 转换为 ast

/**
 * 解析 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)
}

我们可以验证它的正确性

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)

结语

在上面，吾辈实现了 lisp 的玩具运行时和解析器，虽然还不支持许多 lisp 的功能（例如 ' 引用功能），但核心的功能已经实现了，它可以完成一些基本的数值逻辑运算了。另一种有趣的思路是编译器，它不直接运行 lisp 代码，而是将 lisp 代码编译为一种其他可以运行的代码，例如将 lisp 代码编译为汇编代码执行，或者更有趣的方法是 – 编译为 js，就像 ts 做的一样，那样它就可以与 js 互操作了。