[Back]

Chapter 4

4.1 元循环求值器

建立新的语言,或者说新的抽象是对解决一些工程问题的强有力的控制复杂度的策略

DEF.52 元语言抽象 元语言抽象就是建立新的描述语言的技术,通过在新的层面上加以思考,昭示了PL中最基本的思想,求值器决定了一个程序设计语言中各种表达式的意义,而它本身也不过就是另一个程序。而计算机科学本身不过是如何恰当构造描述的学科。

DEF.53 元循环 用与被求值的语言同样的语言写出的解释器被称为元循环

我们的求值器需要有哪几项机能呢?首先是,我们需要有处理嵌套表达式的能力,我们还需要有使用变量的能力,以及定义复合过程和特殊过程的能力。 我们首先来设计eval: eval的参数是一个环境和一个表达式 基本表达式:

  • 对于自求值的表达式,比如各种数,eval会直接返回表达式本身。
  • eval会在环境中查找变量的值
  • 特殊的形式:
  • 对于加引号的表达式,eval返回被引的形式
  • 对变量的赋值或者定义,需要递归的调用eval过程,计算出需要被约束到这个变量的值,然后修改或者建立环境
  • 对if表达式的处理
  • 对一个lambda表达式,我们需要将它的参数表和过程体与相应的环境包装起来。
  • 对begin表达式,我们将会顺序求值。
  • 对cond表达式,我们将其转化为嵌套的if来处理。
  • 组合式:
  • 对一个过程应用,eval会递归的求值组合式的运算符和与运算对象,然后将这样得到的过程和参数送至apply
  • 接下来是apply的过程: 如果需要应用的是一个基本过程,那么我们直接调用它,否则,我们就顺序求值复合过程的各个表达式,这时我们就需要建立一个基本的环境,这个环境是对这个复合环境所包含过程的扩充,并将实际参数约束到这个环境中。

    我们的表达式表示同样采用了数据抽象技术,一个复合表达式的结果,是由表达式的片段递归确定的,我们同样也能建立一些操作,它们和表达式的特定实现方式是无关的。

    DEF.54 派生表达式 如果一些特殊的形式可以被其他特殊形式的表达式定义出来,就称这些表达式为派生 表达式。

    环境的表示多种多样 我们在这里实现的这种环境策略,是一种低效的深搜索方式,往往在现实的Scheme设计中,会引入一个词法作用域的概念来提高性能。

    接下来我们只要将Lisp的基本过程绑定在全局环境中即可开始使用这个元循环求值器了。

    发生在元循环的背后的深刻本质,是我们实质上是建造了一部通用机器(图灵机),这部机器可以以任意的机器作为输入,然后给出正确的执行步骤和结果。 更加深刻的是,由此可以推出的一个结论:任何的求值器都可以执行其他的求值器,这就推广到了一个可计算性的根本概念:图灵-丘奇论题。 有关更多的求值器设计的可行性,见数理逻辑中的递归论。 求值器的另一个惊人方面,在于它沟通起了用户操作的数据对象和程序设计语言本身。

    我们的元循环求值器一个缺陷在于,考虑两个相互递归定义的过程,我们的顺序求值器能够正常工作就必须有限制了:我们必须保证这两个定义在调用之前发生。 有时候我们会认为这样的限制是自然的,只会在一些非良性定义的程序中出现问题,但是引入同时定义的方式,将使得我们在实现编译器的时候避免很多棘手的问题。

    我们给编译器做的接下来一个重要优化在于,将词法分析过程和执行过程做一个分离,或者说,是Parser和Evaluation的分离,这样可以在多次执行中仅仅将分析好的执行过程作为结果返回,大大提高了效率。

     

    4.2 Scheme的变形——惰性求值

    拥有了一个元循环的求值器,我们就能够在此基础上增加新特性,修改Scheme的基本特性,从而更好地检查错误和优劣。 我们首先来实现一个正则序求值的Scheme

    DEF.55 惰性与正则序 一般来说,惰性指的是求值器处理表达式的机制,而正则序则更多地是形式语言层面,当然,两者并没有特别严格的区别,常常可以互相替代使用。

    DEF.56 严格过程和非严格过程 如果一个过程允许参数未被求值就进入到过程体中,我们就说这个过程是非严格的,反之同理。在一个纯的应用序语言中,所有过程都是严格的,而一个纯的正则序语言中,所有复合过程都是非严格的。

    一个技术性的实现问题,就是将延时求值的内容包装成一个被称为槽的对象,以便能够在需要的时候立即求值。 为此,我们需要将这个表达式块和环境一起封装到槽中。

    有了惰性求值,我们的流和表也就没有区别了,也就是说,它们都可以被高阶过程接受了。

     

    4.3 Scheme的变形——非确定性求值

    引入一个搜索机制以后,我们的语言将会向着一个逻辑式断言的方向发展。从原本的过程性语言向一个说明性发展。与流维持了一种共时性的错觉相比,非确定性计算造成了一种时间的分支性错觉。 为此我们需要一种名为amb的新表达式形式,它的描述如下: (amb <a1> <a2> <a3> … <an>) 有歧义地返回参数中的任意一个值。 计算是具有分支的,amb所做的就是尝试着探查所有的分支,并将潜在的可能性返回。 所以amb就是一个每一次都忠实地执行第一个可能值,沿着分支遇到失败后,又能回溯到上一个分支地实现。(深度优先搜索DFS) 关于回溯的发展,参看真值保持和依赖导向的回溯,Winston 1992

    我们还可以试着用非确定计算来解决一些自然语言的语法分析问题。

    我们可以借助继续的概念来实现非确定性计算。 在求值器中传递成功与失败的继续的时候,尽管大部分过程都只需要做简单的再包装,但是需要特别处理定义和赋值的概念。这些都需要将值进行成功执行的判断,再将值和一个失败继续返回。而赋值则需要在失败继续之前封装一个无参的lambda函数,以便撤销赋值带来的影响。 对过程应用的管理需要我们将参数层层封装到lambda表达式中,以便失败过程回溯。

     

    4.4 逻辑程序设计

    计算机科学一直以来,处于的都是一个命令式的地位,也就是说,负责的是验证和计算数学说明中的内容,忠实的指定步骤去执行。但现在,如果我们充分运用语言设计的威力,以高级语言的方法论为支撑,就能够使计算机程序获得说明性的能力,这也是逻辑程序设计语言所尝试的。

    大部分的程序设计语言都是建立在明确的输入输出的表达式,或者数学函数的基础上。而一旦我们的计算模型关注的不再是值,而是程序设计的关系,那么一种新的思维就能为我们提供很好的助益。 逻辑程序设计的发展归功于六十年代发现的合一算法和归结原理。 我们接下来要实现的就是一个适用于数据库的查询语言。

    这个语言除了可以执行简单的查询,还应该可以撰写新的规则以供使用。

    规则给了我们的程序逻辑推理的能力

    为了能够完成简单查询和复合查询,我们需要一种名叫模式匹配的技术。而对整个数据库做模式匹配的代价是高昂的,因此我们需要粗略匹配和精细匹配。 而在数据库建立的时候建立索引来进行粗略匹配的技术就非常常用、 其次我们需要使用合一去处理规则的使用,本质上,这似乎是一种解决联立方程的问题。 认识合一的一个有效方法是将其看作是一个最广模式。 表面上看起来,我们的程序很像数理逻辑中的假言推理,但是实际上,隐藏在表面下的控制结构却会导致等价的逻辑推理往往会有不一样的效率和效果。 逻辑程序所要做的工作是,在数理逻辑中寻找这样的一个子集,它的表达能力尽可能地强,而它的控制过程又要尽可能地弱。尽管如此,很多时候逻辑程序并不能总是和数理逻辑一致,为了一定的语言表达能力,有时候会牺牲一些数理逻辑的完备性。 另外,我们对not的处理也说明了一种封闭世界般的思考,用于检查的所有知识应该被事先包含进数据库。