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$演算中，没有布尔值的概念，但是可以定义两个函数来表示布尔逻辑：

$$

$$

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

$$

上面的三个函数都是利用了$$演算中参数可以是函数的性质，输入的$$或$$都可以作为函数继续运算，下面以$$函数为例进行验证：

$$

$$

$$

$$

当且仅当$$与$$均为$$时，$$的值为$$。因此，函数$$的定义正确。

3、$$演算与计算机的联系

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

$$

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

$$

$$函数的工作行为与选择器完全一致！放在硬件中，$$函数是选择器，而在软件中，它就是if语句：

if (sel) {
  a
} else {
  b
}
Copy

三、更进一步

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

$$

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

通过上面的抽象定义，已经实现了预期的功能，但是到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)
Copy

宏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)\
Copy

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

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

下面来看第二个问题，宏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)
Copy

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

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

四、参考资料

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

• $$演算简介