说人话的编译原理概念解释

仅提供最基本的概念解释,如果想要自动化实现下述概念的普适情况,我也不会

CPS变换

CPS = Comtinuation-passing-style。 是一种编程风格

1
2
def add(x, y){return x + y} print(add(x, y)) // 普通方法
def add(x, y, func) {return func(x + y)} // CPS方法

将后续操作都写给第一个函数,这种方法可以整一个很长的调用链,每一个调用链处,都可以保存中间状态,如阶乘的例子

1
2
def fact(x){x==1? 1 : x * fact(x-1)} // 普通方法
def fact(x, func) {x == 1? func(1): fact(x-1, lambda y: func(y * x)} // CPS方法

如果执行f(4)普通方法的调用链是

1
4*fact(3) ==> 4 * 3 * fact(2) ==? 4 * 3 * 2 * fact(1) ==> 4 * 3 * 2 * 1

CPS方法的调用链是

1
2
fact(4, func) ==> fact(3, lambda y: func(y * 4)) 
==> fact(2, lambda y: [lambda y :func(y * 4)] (y * 3))

注意中括号里面的部分,这个是lambda整体带入,因为func本身就是一个参数,所以将上式整体带入,替换后面的func,这样一来,调用链就变成了

1
y = 1 => 1 * y => 2 * y ==? 3 * y

按照顺序进行计算了,而且,还有,这个y,是一个中间变量,是可以保存的,每一次都可以保存一个中间变量,所以能够随时重建计算过程

Lambda演算

两条规则,Alpha规则和Beta规则。还有所有的东西都是函数,包括数字都是函数

Alpha 规则

两条规则,第一条是确定自由变量的,所谓自由变量,指的就是随意进行替换也不会改变的变量

比如在一条规则中

1
2
lambda x. x + 2
等价于 def func(x) {return x+2}

上式可以变化为

1
lambda y. y+2

这个x是毫无影响的,因此这个x就是自由变量

Beta 规则

替换,调用的规则

在一条规则中

1
2
(lambda x. x+2)(4)
等价于 def func(x){return x+2} func(4)

对其中对应的变量进行替换得到计算结果

1
4 + 2

如果是多参数

1
(lambda x y. x y) (lambda z. z * z) 3

其中(lambda z. z*z)对应的是第一个参数x, 3对应的是第二个参数y,随后进行替换

1
(lambda z. z*z) 3
1
3 * 3

比较简单,真正难的是,如何用函数来表示一个数,随后用函数进行计算,这就是lambda演算的核心

1
2
3
0 = lambda s z. z // z 代表0, 0乘任何数都是0
1 = lambda s z. s z // 1 乘 任何数都是它本身

具体看这里

https://zhuanlan.zhihu.com/p/30510749

函数柯里化

说人话就是实现一个类似于数组里面apply 的功能

比方说我们有一个数组

1
2
3
4
s = [1, 2, 3, 4, 5]
def sum(x, y):
return x + y
ss = s.apply(sum)

思想是类似的,如果说我们想要计算加法,但是只有一个参数怎么办呢?

1
2
3
def add(x, y): return x+y
def add_curry(x): return lambda y: x + y
add_curry(3)(4) = 7

返回一个保存当前变量的函数,然后进行调用,这就是柯里化的过程