漫谈Lambda和连对处理

Lambda用吸力字母表示是λ，有点像汉字中的入字。这个字母的意象很好，基本上由两个笔划构成，由一撇和一捺形成了一个分叉。它和Scheme语言中的基本数据结构，也就是连对中的对子形成很好的呼应。对子也是由两部分构成，可以使用car和cdr两个元始操作来获取相应的内容。隐隐然，car和cdr对应着λ中的撇和捺。

我们可以使用嵌套的思维对λ进行展开思考，如果把λ的撇或捺嫁接另外的λ会有什么效果呢？其实就形成了树状结构，变成了经典数据结构二叉树：

  /\
 /\/\

所以，在Scheme中通过对子间的嫁接，就能够形成就二叉树是这种二维的数据结构。具体的嫁接可以使用cons操作来实现。既然连对是Scheme的核心数据结构，可以把Scheme说成是基于二叉树的编程语言。反观C语言，则是以一维数据结构为核心，也就是基于数组的编程语言。（虽然C语言中数组的元素可以指向另外一个数据，从而形成多维数据，但是其元始操作是基于一维数据的）。

二叉树继承了树形意象的特点：易发散和收敛。这很适合用来模拟运算过程。运算过程一般是先展开后收敛。展开可以看作是把表示运算的树形结构越长越大，而收敛是对树形结构进行局部或者整体求值，使树形结构变小。一个程序往往由一系列的运算构成，这些运算的展开和收敛构成了程序运算的行径图。使用二叉树来表示运算结构有这么些好处：

  • 二叉树是最元始的树形结构，其他树形结构都能够转换为二叉树
  • 二叉树的上下级结构，可以避免运算间互相引用，从而产生死循环

其实二叉树这种树形结构也可用于组织程序。程序虽然由一系列运算组成，但实际组织的时候往往会划分成若干个独立部分（简称独部），然后由这些独部进行组合形成一个个不同规模的程序。独部当然也是由一些列运算构成，随可以看成是一个运算体。独部和独部之间可以相互引用，形成依赖关系。但是同样地，就像运算之间不能有死循环，独部之间也不能有死循环。所以独部之间地依赖关系也适合用树形结构表示。

前面提到，二叉树地特点是易于发散和收敛。在运算的时候，有一个概念叫做递归，可以看作是发散和收敛这两者的结合体。递归可以看成是由数据驱动的，受模板控制的发散和收敛行为。它在发散和收敛的过程中都将数据输入模板，从而产生运算。递归一般带有终止条件，以将发散转为收敛，否则会进入无穷递归，等同于死循环。

这可谓是s-表达式的力量。

（未完待续）