尾调用与栈帧复用

普通调用为“回来之后再做什么”保存一个返回位置。尾调用回来以后唯一要做的事情还是立刻返回，于是可以直接继承当前函数原本的返回位置。活动函数换了，等待它完成的外层计算没有增加。

栈帧复用是一种实现，语言层的 proper tail recursion 是空间行为要求。Scheme 的要求还涉及捕获续延，远大于本页简化 ABI。[1] 不能用这里一段 jump 代码声称实现了所有语言的完整尾调用保证。

累加器走四个状态，只留一层帧 ​

sum(n,a) = if n==0 then a else sum(n-1,a+n)
main = sum(3,0)

main 用普通 call 进入 sum。设当前 FP=8144, SP=8112，[8144]=8192、[8152]=main.after_sum、[8136]=55。四次函数体入口参数依次为 (3,0)、(2,3)、(1,5)、(0,6)，FP、SP 和三个保存槽一直相同。最后 R=6，普通尾声恢复 S=55、FP=8192、SP=8160，并跳到 main.after_sum。

尾转移的结果不变量为 $a+n(n+1)/2=6$，初始成立，替换成 $(n-1,a+n)$ 后仍成立，n 每次减一到零。因此程序正确终止，且当前链只占一个 48 字节帧（旧 FP、返回地址共16字节，加局部区32字节）。main 自己的空间另算。

若所有递归边使用普通 call，n=3 时需要同时保留四个 sum 帧，共192字节，随后逐层立即返回。对一般 n≥0，普通版本活动帧数 n+1，而复用版本为1。两者仍执行 n 次加法，尾调用没有把线性时间变成常数时间。

实参必须是平行搬移 ​

尾调用 f(a,b) -> g(b,a) 的两个新值来自旧状态。原 (a,b)=(2,9)，正确结果应传 (9,2)。顺序执行 A0=A1; A1=A0 会得到 (9,9)；先保存 t=A0 再搬 A0=A1; A1=t 才正确。本页让所有新实参先进入临时向量，逻辑上是平行赋值；真实寄存器实现可复用既有并行复制环消解，但不能省去它。

sum(n)=if n==0 then 0 else n+sum(n-1) 的递归调用不在尾位置。若不改变算法便丢掉当前帧，返回时还要加的 n 就不见了。先改写成累加器形式需额外的算术等价证明；在会溢出或有异常的整数语义下也不能不加条件地变换。

正确性、根映射和资源账本 ​

在允许复用的尾边，源当前续延与目标继承的返回槽表达同一个后续计算。新实参与环境先从旧状态求出，故复用不会改变参数值；原调用者保存槽不变，故最终尾声恢复的控制状态正确；当前局部不再被合法引用，故覆盖不会破坏未来数据。三项条件共同给出一次尾边的模拟，沿尾调用链归纳即可。

若目标可能在安全点触发移动 GC，尾转移还必须切换到目标函数体入口对应的根映射理路GC 安全点与根映射GC safepoint and root map · Stack map · 垃圾回收安全点用程序点对应的物理位置表找到全部活动帧中的根，并保证移动回收后不再读取旧指针副本。，旧死槽不再当根，新环境与跨点参数要可找到。搬移中途不允许暂停，或者为中间状态单独提供映射。本页把尾转移作为不可中断的短运行时步骤，未实现并发暂停协议。

一条尾边搬移 k 个参数、初始化 s 个目标局部字，时间为 $O(k+s)$；本例两者固定，所以常数。连续尾链的控制栈空间受最大参与帧大小界定，而非尾调用次数。参数对象、闭包、列表、日志等堆空间仍可能不断增长。checker 默认只保存当前状态和最大帧数；开启逐步 trace 则 n 步输出占 $\mathrm{\Theta }(n)$ 空间，不能把含完整日志的运行器称为常数总空间。教具每步还直接检查累加器等式，会执行乘法与整除；Python 大整数的位成本另随数值位长增长，本页的帧数与参数操作计数不是主机墙钟时间界。

迁移任务：even(n) 与 odd(n) 在 n>0 时尾调用对方并减一，零时分别返回 true、false。even(4) 的函数序列为 even、odd、even、odd、even，结果 true，按同 ABI 仍只有一帧。再在 odd 的返回前加入 log(result)，调用便不再尾部，除非语言证明该日志已进入相同续延或采用另一种变换；不能只依据递归图判断。

本页保留旧调用约定“不承诺尾调用优化”的原模型，新增的是明确受限的替代执行边。外部 ABI 的参数个数、栈对齐、清理责任或展开协议不匹配时，编译器可以保守保留普通调用，不能任意跳入外部函数中部。