如何制造SCP018

编程语言话题下的优秀答主

什么是Tail Call？

Tail Call（尾调用）指，我们调用一个函数后，立刻返回。

def triple(x): # 返回的不是函数
    return x * 3

def is_tail_call(x): # 是尾调用，因为我们调用后就返回了
    return triple(x)

def not_tail_call(x): # 不是尾调用，因为我们调用完还要1 + result
    return 1 + triple(x)

def half_tail_call(x): # 外面的是尾调用，里面的不是
    return triple(triple(x))

在以上例子中，is_tail_call的triple，跟half_tail_call的外面的triple，是tail call。

为什么Tail Call很重要？

因为Tail Call提供了很好的优化。

假设我们是register machine，return address存在一个register里面，如果我们tail call，我们需要：把argument放对位置，然后goto function就可以了！

如果是non tail call，我们需要把argument放对位置，保存旧的return address（比如说塞上stack），设定return address为下一行，goto function，把旧的return address restore掉，然后该干啥干啥。

这样，我们额外的多做了一push一pop，space & time overhead一下子上来了，怪不得60~70年代的人不肯用函数。。

当我们递归的时候，不做这个优化导致了big O上的空间差距 - 一个要不停的push stack，一个说，stack是啥？

另一点是，当递归的时候，argument的位置是对的，‘放对位置’这一步就没有了，于是就成为了一个goto self - 也就是loop。

尾递归优化，其实就是Tail Call Optimization在taill call self下的优化。（见Debunking the 'Expensive Procedure Call' Myth, or, Procedure Call Implementations Considered Harmful, or, Lambda: The Ultimate GOTO）

如果你会continuation，Tail Call说的就是，当你call进去的continuation，跟你自己的cont是eta equivalent时，直接传就好了。

Continuation某种程度下对应返回地址，所以这也是说，如果没有必要，不需要动返回地址。

但是：

很不幸的，有些解释器/编译器不做tail call optimization。这代表上面写递归函数，会占用大量空间。怎么办？

假设我们是C语言。

那很简单，直接inline asm啊！啥地方要tail call，直接inline一个goto过去，一切解决。

当然，inline asm没多少语言支持 - 连C也要开编译器扩展才行。

那，我们在程序里面模拟一个program counter，不就一切OK了吗？

# 转换：
# 在函数头插入global pc
# 所有尾调用变成pc = ...
# 改用eval

pc = None # program counter

def eval(f):
    global pc
    pc = f
    while True:
        pc()

cnt = 0
def naive_rec():
    global cnt
    print(cnt)
    cnt += 1
    naive_rec()
    
# naive_rec() # 错误：达到最深递归层次

cnt = 0
def rec():
    global pc
    global cnt
    print(cnt)
    cnt += 1
    pc = rec

# eval(rec) # 远远超过了递归限制！

好像可以呢！

但是函数参数是不是要像register那样手动设置？那样实在太丑了。

幸好，python有closure，我们放进closure里面就行了。

# 转换：
# 尾调用变lambda
# eval加上lambda

pc = None # program counter

def eval(f):
    global pc
    pc = f
    while True:
        pc()

def naive_rec_arg(cnt):
    print(cnt)
    naive_rec_arg(cnt + 1)

# naive_rec_arg(0) # 毫无意外，同一错误

def rec_arg(cnt):
    global pc
    print(cnt)
    pc = lambda: rec_arg(cnt + 1)

# eval(lambda: rec_arg(0)) # 再一次超越极限！

一切都好。但是，函数有输入，当然也有输出，现在怎么办？

要注意的是，我们不能用全局变量来模拟。

原因很简单，eval是个死循环，永远不返回，就算返回值assign到某全局变量，我们也不能让当前函数调用完，让调用者使用返回结果。

既然核心问题是eval，我们使得eval不是死循环就可以了啊！

规定：如果pc为None，则表明返回。

# 转换：
# 对尾调用，pc = lambda: ... 跟上 return None
# 对普通返回，pc = None 跟上 return ...
# 函数尾：pc = None

pc = None # program counter

def eval(f):
    global pc
    old_pc = pc # 如果eval里面用eval怎么办？保存老pc就OK
    pc = f
    result = None
    while pc:
        result = pc()
    pc = old_pc
    return result

def naive_is_even_0(x):
    if x > 1:
        return naive_is_even_1(x - 2)
    if x == 1: # 故意这样写，测试early return正确性
        return False
    else:
        return True # 通过互递归提高难度

def naive_is_even_1(x):
    return naive_is_even_0(x)

assert not naive_is_even_0(123)
# assert not naive_is_even_0(2345) # 又是你

def is_even_0(x):
    global pc
    if x > 1:
        pc = lambda: is_even_1(x - 2)
        return None # 没有这行会接着运行！
    if x == 1:
        pc = None
        return False
    else:
        pc = None
        return True
    pc = None # 这很二，但是我们希望转换越简单越好！

def is_even_1(x):
    global pc
    pc = lambda: is_even_0(x)
    return None
    pc = None

assert not eval(lambda: is_even_0(2345)) # 过！

很好。但是我们看一下，这代码很危险！

很简单，我们要先set pc，然后再return一些东西。

但是，如果我们手滑了一下，忘了set pc，会怎么样？

这样，我们就会进入死循环，而得益于我们的优化，我们甚至不能stack overflow来表示无限递归了！

我们也希望，pc set成lambda的时候，返回值是None：那时，返回值是被无视的，但是限制返回为None能更早暴露程序的问题。

我们希望，有一个python语句，SetFunAndReturnNone，来保证set pc后才能return。

同理，如果有个python语句，SetNoneAndReturnVal，保证set None后会返回一个值（没有返回的就返回None，表示没忘）也好，这样能确定程序员在用pc修改器的时候，不会忘记设返回值。

python没有这两个语句，但是还好，这两个表达式都是会立刻返回的。

既然eval已经在操控pc了，我们可以让他担任更多解释器的工作：我们可以定义代表这两语句的class，pc的返回值只能是这两语句（如果忘记设定，导致pc返回None，算作错误，因为这情况下pc也会忘记更新了）

# 转换：
# 去掉global pc
# pc = lambda:... 接 return None 改写成 return SetFunAndReturnNone(...)
# pc = None 接 return ... 改写成 return SetNoneAndReturnVal(...)
# 行尾插入SetNoneAndReturnVal(None)

class SetFunAndReturnNone:
    def __init__(self, f):
        self.f = f

class SetNoneAndReturnVal:
    def __init__(self, x):
        self.x = x

pc = None # program counter

def eval(f):
    global pc
    old_pc = pc # 如果eval里面用eval怎么办？保存老pc就OK
    pc = f
    result = None
    while pc:
        command = pc()
        if isinstance(command, SetFunAndReturnNone):
            pc = command.f
            result = None
        else:
            assert isinstance(command, SetNoneAndReturnVal)
            pc = None
            result = command.x
    pc = old_pc
    return result

def is_even_0(x):
    if x > 1:
        return SetFunAndReturnNone(lambda: is_even_1(x - 2))
    if x == 1:
        return SetNoneAndReturnVal(False)
    else:
        return SetNoneAndReturnVal(True)
    return SetNoneAndReturnVal(None)

def is_even_1(x):
    return SetFunAndReturnNone(lambda: is_even_0(x))
    return SetNoneAndReturnVal(None)

assert not eval(lambda: is_even_0(2345)) # 过!

我们现在架构的改动已经做完了。但是，还能优化下这个文件。

最基本的，pc只有eval在用了，能搬进去，也不用担心重入的问题了，因为每个eval的调用都会有自己的pc

def eval(f):
    pc = f # program counter
    result = None
    while pc:
        command = pc()
        if isinstance(command, SetFunAndReturnNone):
            pc = command.f
            result = None
        else:
            assert isinstance(command, SetNoneAndReturnVal)
            pc = None
            result = command.x
    return result

pc = None的时候能直接返回，不需要在while里面：

def eval(f):
    pc = f # program counter
    result = None
    while pc:
        command = pc()
        if isinstance(command, SetFunAndReturnNone):
            pc = command.f
            result = None
        else:
            assert isinstance(command, SetNoneAndReturnVal)
            return command.x
    return result

result可以去掉了，因为只会assign成None

def eval(f):
    pc = f # program counter
    while pc:
        command = pc()
        if isinstance(command, SetFunAndReturnNone):
            pc = command.f
        else:
            assert isinstance(command, SetNoneAndReturnVal)
            return command.x

如果我们假设SetFunAndReturnNone.f不会是None，f也不是None，pc在循环中不会变成None。我们就能直接while True:

我们也假设f不会是None - 我们的所有代码都不会传个None进去

def eval(f):
    pc = f # program counter
    while True:
        command = pc()
        if isinstance(command, SetFunAndReturnNone):
            pc = command.f
        else:
            assert isinstance(command, SetNoneAndReturnVal)
            return command.x

这两个class名字好长。。。而且pc已经是内部实现了，我们不应该暴露出来。

我们重命名SetFunAndReturnNone做More（需要更多计算），同样的，重命名SetNoneAndReturnVal为Done（搞定）。

我们最后，再优化一下使用代码，去掉不需要的return。

class More:
    def __init__(self, f):
        self.f = f

class Done:
    def __init__(self, x):
        self.x = x

def eval(f):
    pc = f # program counter
    while True:
        command = pc()
        if isinstance(command, More):
            pc = command.f
        else:
            assert isinstance(command, Done)
            return command.x

def is_even_0(x):
    if x > 1:
        return More(lambda: is_even_1(x - 2))
    if x == 1:
        return Done(False)
    else:
        return Done(True)

def is_even_1(x):
    return More(lambda: is_even_0(x))

assert not eval(lambda: is_even_0(2345)) # pass!

大功告成。

我们最后，跟小杰站着世界树之巅，找爸爸之余看看我们实现了什么：

当我们eval的时候，我们会先调用pc。

然后，我们会push一个stack frame。

当tail call出现的时候，与其去apply之（并且把这个stack frame也push进去），我们直接返回！

这样，我们当前的stack frame就会pop掉。

pop掉后，我们又立刻进入该 call，再push一个frame。

我们的frame数量，就会这样0-1-0-1-0-1，循环往复。故此，这个方法叫做trampoline。

如果你觉得trampoline很有趣，我推荐去看http://blog.higher-order.com/assets/trampolines.pdf，简单又漂亮的一篇paper。

如何制造SCP018

如何制造SCP018

Recommend

LibSubmarine: Temporarily hide transactions on ethereum (cheaply!)

Serverless架构开发与SCF部署实践

师傅领进门之6步教你跑通一个AI程序！

Migrating your PHP application to Laravel

C和Go相互调用

Code Your First API With Node.js and Express: Connect a Database

推荐一款开源、免费的标记语言转换工具，各种文档格式自由转换

Issue 148 – August 28th 2018

组合拳出击-Self型XSS变废为宝

Staying sane as a solo developer

About Joyk