4 初试去语法糖

我们从非常斯巴达式的算术语言开始。下一步我们来看看,在现有语言框架下怎么支持更多算术操作。我们只加2种,以做示范。

4.1 扩展:添加双目减法操作

首先,我们来添加减法。由于我们的语言已经包含了数、加法和乘法,用这些操作足以定义减法了:

a - b = a + -1 × b

好的,这很简单!但是我们要怎样将它变成可运行的代码呢。首先,我们面临一个决定,将减法操作符放在哪?将其像其它两个操作符一样处理,在现有的ArithC数据类型中添加一条规则?这种想法看上去很自然,也很诱人。

思考题

修改ArithC这种做法有什么不好的地方呢?

这会导致几个问题。首先,显然地,我们将需要修改所有处理ArithC的代码。就目前而言,还很简单,只涉及到了我们的解释器。但是如果在更为复杂的语言实现中,这会是个问题。其次,要添加的结构是可以用已实现的语法结构定义的,去修改已有数据结构的方式让人觉得代码不够模块化。最后一点,也是最微妙的一点,修改ArithC这种行为有概念上的错误。因为ArithC描述的是我们语言的核心部分。而减法(和其他类似添加特性)是用户交互的部分,属于表层语言。明智的做法是,将不同类型的概念放到不同的数据类型中,而不是把它们硬塞到一起。有时候这么做看上去有点笨拙,不过长远来看,它会让我们的程序更易于阅读易于维护。此外,你可能会将不同的功能扩展放在不同的层次上,这么做(将核心语法和表层语法区分开)正有利于这么做。

因此,我们尝试定义新的数据类型来反应我们的表层语言语法结构:

(define-type ArithS  ;表层算术
  [numS (n : number)]
  [plusS (l : ArithS) (r : ArithS)]
  [bminusS (l : ArithS) (r : ArithS)]
  [multS (l : ArithS) (r : ArithS)])

它看起来和ArithC基本相同,遵从了相似的递归结构,唯一的区别就是加了一个子句。

数据类型定了,接下来需要做两件事。第一是要修改语法解析器,让其返回ArithS类型数据(而不是ArithC类型)。第二是要实现去语法糖(desugar)函数,它需要能把ArithS值转换成ArithC值。

先来实现去语法糖函数简单的部分:

<desugar> ::=  ;去语法糖

    (define (desugar [as : ArithS]) : ArithC
      (type-case ArithS as
        [numS (n) (numC n)]
        [plusS (l r) (plusC (desugar l)
                            (desugar r))]
        [multS (l r) (multC (desugar l)
                            (desugar r))]
        <bminusS-case>))  ;二元减法子句

把数学描述转化为代码:

<bminusS-case> ::=  ;二元减法子句

    [bminusS (l r) (plusC (desugar l)
                          (multC (numC -1) (desugar r)))]

思考题

️常见错误是忘了递归地对lr进行desugar操作。忘了会发生什么?请自行尝试。

4.2 扩展:取负数操作

让我们来考虑另一种更有意思的扩展,取负数操作(unary negation)。这使得你需要对语法解析器进行一定修整,当读到-符号时,需要往前读以判断它是减法还是取负操作。但这不是有意思的部分!

取负数操作可以有几种去语法糖的方法。很自然的我们会想到:

-b = 0 - b

继续完成减法的去语法糖操作,我们得到:

-b = 0 + -1 × b

思考题

你觉得这两种中哪个更好呢?为什么?

大家可能希望使用第一种方式,因为它看起来更为简单。假设我们扩展了ArithS数据类型,添加取负数的表示法:

[uminusS (e : ArithS)]  ;一元减法表达式

对应去语法糖的实现也很直接:

[(uminusS (e) (desugar (bminusS (numS 0) e)))]

检查看看有没有类型错误。eArithS类型,所以它可以被当作参数传递给bminusS来进行去语法糖操作。所以这里要做的不是对e去语法糖,而是将其直接嵌入到生成的表达式中。在去语法糖的工具中,这种直接将某个输入项嵌入到另一个项中,然后递归调用去语法糖函数的做法很常见,被称之为宏(macro)。(在我们这个例子中,“宏”是umiunsS的定义。)

然而该定义存在两个问题:

1. 第一个问题是,该递归是生成的(generative),这需要我们得对其进行特别关注。【注释】我们可能会希望使用下面这种方式来重写它:

[uminusS (e) (bminusS (numS 0) (desugar e))]

它确实消除了生成性(generativity)。

如果你没听过生成递归,可以阅读《程序设计方法》(又译《如何设计程序》)一书第五部分。简单来说在生成递归中,子问题是输入的计算结果,而不是输入的子成分。我们这个例子还是很简单的,这里的“计算”就是bminusS构造函数。

思考题

很不幸的是,上面的转换有问题,试着找出问题吧。找不出的话,运行一下试试。

第二个问题是,它依赖于bminusS的意义;如果bminusS的意义发生变化,uminusS的意义也就发生了变化,即使我们并没打算改变uminusS的意义。作为对比,另一种更鲁棒的做法是,定义函数,其输入是两个项,输出是第一个项加上-1乘以第二个项的表示法,然后用该函数来定义uminusSbminusS

你可能会说,减法的意义不可能发生改变,这么做有啥意义呢?事情并不总是这样的。确实减法的意义不太可能改变;但是另一方面,它的实现可能会改变。例如,开发者决定为减法操作打印日志。采用前一种做法(宏展开),所有取负数操作就也会打出日志;而采用后一种做法就不会。

很幸运,这个例子我们还有更简单的选择:

-b = -1 × b

这种展开方式完全可行,而且还是结构递归。我们花这些篇幅讨论各种不同展开方式的原因是,告诉你各种选择和其带来的问题,毕竟现实中你不会总是那么幸运。

results matching ""

    No results matching ""