Marvin's Blog【程式人生】

Ability will never catch up with the demand for it

16 May 2021

Scheme随想

漫谈Lambda和连对处理

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

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

  /\
 /\/\

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

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

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

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

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

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

(未完待续)

Categories

Tags