nju-pa摸鱼记2-计算机与λ演算

一、前言

在上一篇中，讨论了如何使用预处理指令或是宏来识别某个宏是否被定义，以实现通过配置进行有选择的编译。不过，仅使用上一篇讨论的isdef宏还不能达到和预处理指令一样的效果，本篇将继续讨论框架中如何使用宏来实现“如果某个宏被定义，则预处理后保留某些语句或代码块，反之抛弃这些部分”的功能。之所以提到\(\lambda\)演算，是由于我在搞明白代码框架中的宏是如何运作之后，发现其颇有“函数式编程”的风格，而\(\lambda\)演算是函数式编程的基础，遂记录于此。

二、浅谈\(\lambda\)演算

1、简介

\(\lambda\)演算是一种和图灵机等价的计算模型（丘奇-图灵论题），它可以描述任何可计算问题，又称为“最小的编程语言”。简单来说，\(\lambda\)演算的核心是抽象化定义的函数，它的参数没有类型的限制，可以是数字，函数或者字符串等等。一个最基础的函数是恒等函数：

\[\lambda x.x\]

其中\(\lambda\)后的\(x\)是这个函数的输入，点号后的\(x\)是函数的输出。可以将这个函数作用在变量\(a\)上，就得到：

\[\lambda x.x(a) = a\]

通过柯里化方法，可以定义二输入函数：

\[\lambda x.\lambda y.x+y\]

其中\(x\)和\(y\)是该函数的两个输入，该函数的输出是两个输入的和。

2、用抽象化函数表示布尔逻辑

在\(\lambda\)演算中，没有布尔值的概念，但是可以定义两个函数来表示布尔逻辑：

\[\text{TRUE} = \lambda x.\lambda y.x\]

\[\text{FALSE} = \lambda x.\lambda y.y\]

用自然语言来描述\(\text{TRUE}\)函数的作用：“输入两个参数\(x\)和\(y\)，输出第一个参数”，\(\text{FALSE}\)函数的功能同理。这样的话，可以把布尔值\(1\)和\(0\)分别定义成\(\text{TRUE}\)函数和\(\text{FALSE}\)函数。接下来可以定义最基本的非、与、或运算：

\[ \begin{cases} \text{NOT} &= \lambda x.x\ \text{FALSE}\ \text{TRUE} \\ \text{AND} &= \lambda x.\lambda y.x\ y\ \text{FALSE} \\ \text{OR} &= \lambda x.\lambda y. x\ \text{TRUE}\ y \\ \end{cases} \]

上面的三个函数都是利用了\(\lambda\)演算中参数可以是函数的性质，输入的\(\text{TRUE}\)或\(\text{FALSE}\)都可以作为函数继续运算，下面以\(\text{AND}\)函数为例进行验证：

\[ \begin{align*} \text{AND}(\text{FALSE})(\text{FALSE}) &= \text{FALSE}(\text{FALSE})(\text{FALSE}) \\ &= \text{FALSE} \end{align*} \]

\[ \begin{align*} \text{AND}(\text{FALSE})(\text{TRUE}) &= \text{FALSE}(\text{TRUE})(\text{FALSE}) \\ &= \text{FALSE} \end{align*} \]

\[ \begin{align*} \text{AND}(\text{TRUE})(\text{FALSE}) &= \text{TRUE}(\text{FALSE})(\text{FALSE}) \\ &= \text{FALSE} \end{align*} \]

\[ \begin{align*} \text{AND}(\text{TRUE})(\text{TRUE}) &= \text{TRUE}(\text{TRUE})(\text{FALSE}) \\ &= \text{TRUE} \end{align*} \]

当且仅当\(x\)与\(y\)均为\(\text{TRUE}\)时，\(\text{AND}\)的值为\(\text{TRUE}\)。因此，函数\(\text{AND}\)的定义正确。

3、\(\lambda\)演算与计算机的联系

\(\text{TRUE}\)和\(\text{FALSE}\)这两个函数的功能用一个词来概括就是“选择”，在数字电路中，也有一个可以做选择的模块：选择器。选择器有三个输入端口\(a\)，\(b\)和\(sel\)，一个输出端口\(y\)，根据\(sel\)的值可以决定\(y\)的值是和\(a\)相同还是和\(b\)相同（比如当\(sel = \text{TRUE}\)时，\(y=a\)；\(sel = \text{FALSE}\)时，\(y = b\)），类似的，可以构建函数：

\[\text{MUX} = \lambda a.\lambda b.\lambda sel.sel\ a\ b\]

这个函数看起来有些奇怪，似乎只是把三个参数排列在一起输出了，并不能看出其中的“选择功能”，但是\(\lambda\)表达式的特别之处就在于输入的参数可以是函数，从而可以进一步作用在后面的参数上。下面来验证一下的功能：

\[ \begin{align*} \text{MUX}(a)(b)(\text{TRUE}) &= \text{TRUE}(a)(b) = a \\ \text{MUX}(a)(b)(\text{FALSE}) &= \text{FALSE}(a)(b) = b \\ \end{align*} \]

\(\text{MUX}\)函数的工作行为与选择器完全一致！放在硬件中，\(\text{MUX}\)函数是选择器，而在软件中，它就是if语句：

if (sel) {
  a
} else {
  b
}

三、更进一步

有了\(\text{MUX}\)函数，就可以实现宏定义的“条件编译”了，只需要改变一下它0的输入参数即可：

\[ \text{MUX}(code\_block, , \text{isdef}(macro)) \]

其中isdef是在上一篇定义的宏函数，如果\(macro\)已经被定义了，它将返回\(\text{TRUE}\)，反之返回\(\text{FALSE}\)。\(code_block\)是在宏\(macro\)被定义后希望在预处理时被保留下来的代码块。传给\(\text{MUX}\)函数的第二个参数是一个空串，也就是说在\(macro\)未被定义时，预处理后会留下一个空串，对于最后的预处理结果没有任何影响。

通过上面的抽象定义，已经实现了预期的功能，但是到C语言中，还面临着一些细节问题。首先，isdef的值是1或0，而不是上面定义的和函数。这就导致C语言预处理器并不会把isdef替换为1或0后再当作一个“函数”来解释。其次，isdef中使用了strcmp函数，这显然不能在函数外面使用，函数的运行结果在运行时才被计算出来。

对于第一个问题，如何将isdef的值解释为一个函数呢？由于1和0在C语言中被解释为整型字面量，所以可以给这个1或者0“加点东西”，然后定义新的宏，这里用到了##运算符：

#define concat(a, b) a ## b
#define MUX_MID(a, b, p, sel) MUX(a, b, concat(p, sel))
#define MUX_OUT(a, b, sel) MUX_MID(a, b, PREFIX_, sel)

宏concat将两个参数粘连起来，MUX仍然是上面抽象的函数。假设MUX_OUT的输入参数是(code_block, , isdef(foo)，并且宏foo已经被定义过，先不考虑其他问题，经过宏MUX_MID和concat，最终传入MUX的参数将会变为(code_block, , PREFIX_1)。如果我们继续定义宏函数PREFIX_1和PREFIX_0，就可以解决第一个问题了：

#define TRUE(a, b) a
#define FALSE(a, b) b

#define PREFIX_1(a, b) TRUE(a, b)
#define PREFIX_0(a, b) FALSE(a, b)\

这里定义的TRUE和FALSE宏函数其实就是上面\(\lambda\)演算中的\(\text{TRUE}\)和\(\text{FALSE}\)！现在，考虑宏MUX怎么定义，我们想要将最后的PREFIX_1或者PREFIX_0作用在a和b上，那么只需要改一下参数的顺序，再加个括号就行了：

#define MUX(a, b, sel) sel(a, b)

下面来看第二个问题，宏isdef在预处理阶段不会被替换为1或0，因此，不能通过MUX_OUT(a, b, isdef(macro))来使用这个宏，这样肯定是有问题的。需要一个宏，能在预处理阶段就产生1或0的结果。由于我们是在配置编译时使用，所以对于某个选项，要么它被定义了，要么它没被定义，而被定义的宏我们并不在乎它是什么值，所以可以限制为：“一旦定义，就将它定义为t”（这个限制只在本篇中成立）。

再整理一下，现在需要一个宏，来检测一个“一旦定义，就被一定被定义成t”的宏是否被定义，如果被定义了，预处理时它会被替换成1，否则被替换成0。在这个假设下，被定义了的宏会被替换为t，而没有被定义的宏在预处理阶段会保留为宏名。可以使用刚才的“加点东西”技术，把替换后的t再进一步替换为别的东西：

#define choose2nd(a, b, ...) b
#define PREFIX_t t,
#define choose2nd_mid(p_macro, a, b) choose2nd(p_macro a, b)
#define choose2nd_out(macro, a, b) choose2nd_mid(concat(PREFIX_, macro), a, b)
#define IFDEF(macro) choose2nd_out(macro, 1, 0)

这一系列宏的关键之处在于choose2nd_mid宏定义中p_macro和a之间没有逗号，如果macro被定义成了t，则会被替换为“t,”（t后面有一个逗号分隔），从而成为了第二个参数；当未被定义或者被定义成别的，是第二个参数。

上面的讨论中已经涉及了大部分NEMU框架中所使用的技巧和方法，实现这些宏的思路与\(\lambda\)演算关系密切，这种思路也许就是“函数式编程”。

四、参考资料

• 南京大学ics-pa在github上的项目

• \(\lambda\)演算简介