how to interpret a lisp string

eval.coffee

# 这个文件是上边代码的注释版本
# 这里的代码是 lispy 解释器的思路用 CoffeeScript 完成的
# lispy: http://www.googies.info/articles/lispy.html
# 实现方面有一些不同, 主要是思路, 对不同语言是要紧的

echo = console.log
err = (str) -> throw new Error str

# 代码形如 "(+ x (+ y z))" 假想作为 str 初始输入
# 经过 (split str) 打碎, 被解析到一个列表, 大致是:
# ['(', '+', 'x', '(', '+', 'y', '+', 'z', ')', ')']
# 然后 (parse (split str)) 将其折叠成为数组, 定义 arr:
# ['+', 'x', ['+', 'y', 'z']] 这样再交给 runit 函数运行
# 这里用空格分割字段的确过于取巧了, 现实中复杂些

split = (str) ->
  str.replace(/([()])/g, " $1 ")
    .split(' ')
    .filter (x) -> (x.trim().length > 0)

parse = (arr) ->
  do recurse = ->
    head = do arr.shift
    if head is '('
      in_brackets = []
      in_brackets.push do recurse until arr[0] is ')'
      do arr.shift
      in_brackets
    else head

# 作用域大致这样理解, 每个作用域用一个 JSON 对象保存
# 比如我把作用域内的变量全部存放到 here 属性里面
# 接着需要一个检索作用域的方法, 定义为 seek
# scope_zero 是全局作用域, scope_new 创建新的作用域
# 而定义函数产生的新作用域要查看上层作用域是否有变量
# 执行代码过程中如果局部作用域找不到变量就会检索上层作用域
# 因此用一个 parent 传值, 未来返回上层搜索的结果
# 直到全局作用域也没有, 将返回一个 undefined
# 注意这里返回的是指向一个对应作用域 here 属性的链接

scope_zero =
  here: {}
  seek: (key) -> @here

scope_new = (parent) -> obj =
  here: {}
  parent: parent
  seek: (key) ->
    if @here[key]? then @here else
      upper = @parent.seek key
      if upper then upper else @here

# 每段代码执行时要指定作用域的, 用 runit 执行一个数组
# 比如上面写过的 ['+', 'x', ['+', 'y', 'z']] 这样
# 这边处理和 lispy 不同, 所有操作放到全局作用域的函数里了
# 而 lispy 有两部分的, 这里可以说我偷懒了, 有点错误

runit = (scope, arr) ->
  here = scope.seek arr[0]
  if here? then here[arr[0]] scope, arr[1..]
  else err 'no function found'

# read 函数用在读参数, 因为参数的内容并不确定
# 有时参数是变量, 有时参数是表达式, 那就要先执行

read = (scope, x) ->
  if Array.isArray x then runit scope, x else
    here = (scope.seek x) or scope.here
    here[x]

# 操作符当成全局变量 明显会有被后续操作覆盖的危险
# 但开始时, 只要调用检索就能找到变量和函数, 算方便

scope_zero.here =

  # v 是在 runit 内处理过的参数, 结构变化比较乱

  set: (scope, v) ->
    (scope.seek v[0])[v0] = read scope, (
      if v.length is 2 then v[1] else v[1..].map (x) ->
        read scope, x)

  echo: (scope, v) ->
    v = v.map (x) -> read scope, x
    echo.apply console, v
    v

  '+': (scope, v) ->
    v.map((x)-> read scope, x).reduce (x, y) ->
      (Number x) + (Number y)

  '-': (scope, v) ->
    v.map((x)-> read scope, x).reduce (x, y) ->
      (Number x) - (Number y)

  # 输入的字符串不是数值, lispy 是将符合数字的转换数字的
  # 但我为了图形操作一些考虑, 用函数显式进行转换了
  # 因此有了 number 和 string 方法, 可以造更多方法

  number: (scope, v) ->
    v = v.map (x) -> Number x
    if v.length is 1 then v[0] else v

  string: (scope, v) -> v.join(' ')

  # 定义函数格式是 "(def (f_name arg1 arg) exp1 exp2)"
  # 这里是建一个函数, 将其复制到 f_name 变量去
  # 注意作用域是在函数执行的时候, 在函数内部才创建的
  # 这里的 scope 是定义函数过程中数据所在的作用域
  # 而 scope_in 是函数调用执行所在的作用域
  # 有个把执行时的作用域传递给定义时的作用域的过程
  # 于是函数调用的时候就开始执行定义时写的代码了

  def: (scope, v) ->
    here = (scope.seek v[0][0]) or scope.here
    here[v[0][0]] = (scope_in, arr) ->
      scope_sub = scope_new scope
      for item, index in v[0][1..]
        scope_sub.here[item] = read scope_in, arr[index]
      runit scope_sub, exp for exp in v[1..]

  # if 的格式是 "(if (p) exp_true exp_false)"
  # 也就是只能有一个表达式, 一般函数足够用了
  # 需要的话可以另外写一个方法, 顺序执行多个表达式

  if: (scope, v) ->
    if runit scope, v[0] then runit scope, v[1]
    else runit scope, v[2]

  '>': (scope, v) ->
    v = v.map (x) -> read scope, x
    base = v.shift()
    for item in v
      return false if base <= item
      base = item
    true

# 显然类 Lisp 语言执行时候受累花括号太多, 看得人眼花
# 没有好的工具时手写就太艰难了. 这里个 fibonacci 啊亲

s1 = '(number 1)'
s2 = '(number 2)'
s4 = "(+ (f (- x #{s1})) (f (- x #{s2})))"
s3 = "(if (> x #{s2}) #{s4} #{s1})"
str = "(def (f x) #{s3})"
str2 = "(echo (f (number 10)))"
arr = parse (split str)
arr2 = parse (split str2)
echo arr2, str
runit scope_zero, arr
runit scope_zero, arr2

# 从这里能看到, 空格和括号在编程语言多么重要
# 我因此怀疑过度的符号依赖影响了编程语言的灵活
# 因此尝试直接操作数组, (str -> arr) 阶段在编写过程完成
# 结果是标识符任意用字符, 括号的优先级被自动管理
# 想像自动管理内存那样自动管理语法, 不过目前还浅薄