Scheme初探

大学的时候读过一点SICP但是当时没有理解，只对lisp/scheme和函数式编程产生了朦胧的概念。上周读了《the little schemer》一书对scheme这门语言和程序的基本构造有了大致的了解。

结构

scheme是一种lisp，其语法构造简单，一个表达式有两种结构，一是原子，二是列表。所以对列表的操作非常重要，有三个原生函数就是用来操作列表的他们是:

  1. 假设以下list为(1 2 3)
  2. cons 把一个原子拼在一个列表前面得到新列表 (cons 0 list) = (0 1 2 3)
  3. car 取列表的第一项 (car list) = 1
  4. cdr 取余下的列表 (cdr list) = (2 3)

列表和原子组合起来产生的东西叫做S表达式，scheme的数据和逻辑全都是使用他来表达的。即可以使用(add1 5)来表达一个计算，也可以使用(1 2 3)来表达一个列表。那我们如何判断一个列表是一个逻辑还是数据呢？就要用到一些特定的语法。比如(quote s-exp)当(car 列表)是一个叫quote的原子的时候，(cdr 列表)就被当作一个数据结构。其余的列表都是逻辑。类似quote的基础语法结构还有lambda, cond,等等。

列表的求值规则是这样的： 如果列表的第一项是

  1. 语法规则 -> 应用特定的语法规则到列表并返回值

  2. 其余的 -> 计算列表每一项的值并写把(cdr 列表)作为(car 列表)的参数做计算

cond是一个类似if...elseif的结构，其作用是找到一个为真的条件表达式并且返回相对应的表达式的值。在学习scheme初期我常常会疑惑：为什么cond不使用函数来实现，而是需要一个语法结构呢？后来在实现解释器的时候我明白了，因为如果cond是一个函数，那就意味着cond放弃了他的参数的处理权。这些参数在解释器调用cond之前全都会被求值，而现实当中的cond只对一部分表达式求值。相当于短路了一部分条件表达式和相应值表达式。后来我观察所有的语法都是需要对列表进行控制而存在的。

作用域

作用域是一个key-value对组成的集合，记录了变量的值和参数的值。表达式需要作用域才能进行求值。作用域会扩展，老的作用域加上一些键值对而生成新的作用域（子作用域）。子作用域中如果存在和老的作用域同名的变量则会覆盖老作用域中的变量，但老的作用域不会发生改变。作用域的扩展主要发生在计算自定义的函数上。计算一个函数的时候会把参数求值之后扩展到老的作用域，然后用生成的子作用域来计算函数的函数体。

continuation

一般普通的函数其返回值就是表达式的值，而带有continuation函数的函数，其值不是直接返回，而是通过调用continuation函数传递出去，javascript中，这个概念很像callback，不过这两者想解决的问题不太一样，在javascript中，callback更多是为了异步，而scheme中的continuation通过把递归调用返回之后的逻辑放到continuation函数中去，从而把普通的递归变成尾递归。

y-combinator

在函数式编程中递归是非常常用的，y-combinator能够只用lambda来描述递归。我理解的y-combinator就是用函数本身作为参数调用函数以此来达到在函数内部引用本身的目的。其结构是这样的:

(lambda (fun)
  (
    (lambda (f) (f f))
    (lambda (f) (fun (lambda (x) ((f f) x))))
  )
)

最后

在学习的过程中，我使用javascript实现了一个基础的scheme解释器

⌂