编程语言实现函数调用的原理是什么？不会担心爆栈吗？

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

V2EX 提问指南

这是一个创建于 1726 天前的主题，其中的信息可能已经有所发展或是发生改变。

撸了将近两个礼拜，撸了一个玩具编程语言的内核，也算对当初编译原理的老师有了交代。

想到一个问题，就是主流编程语言的函数调用都是怎么实现的，是否需要一个栈来保存状态（比如我的实现方法），如果是的话不用担心爆栈吗？

比如如果我要用类似这种调用

a = 1

def in():
    print(a)

def out():
    a = 2
    in()

这里，执行out()的话in里调用的应该是a=2而不是a=1。以我菜鸡的水平，我的实现方式是以把上文中的函数的 ast 拷贝一份，贴到调用的那个地方，本质上是压了个栈。那很自然程序员就会想到一个问题，如果极端情况下嵌套了很多函数调用呢，栈会不会爆掉？我们都知道比如 python 默认限制递归层数不能超过 1000.....

比如如果我要写一些函数式编程的代码 a.in().out().in().out().in()........岂不是问题很大？（不要跟我说函数式调用方式跟上文的例子根本不一样 orz ）

第 1 条附言 · 2020-03-04 02:02:41 +08:00

关键词尾递归优化，v2 上的带哥们说话就是好听，轻松说出了我没听过的词汇。
搜了一下相关文章，基本解答了八成疑问：
https://zhuanlan.zhihu.com/p/36587160

所以结论是传统编程语言的函数调用都是这么实现的，我想来想去只能这么写不是因为我菜。

调用

函数

编程

out

16 条回复 • 2020-03-05 02:30:08 +08:00

crella

2020-03-04 00:37:31 +08:00 via Android

你这个比喻不对，a.in 和 a.out 方法返回的都是空值，不存在下一步执行

我去验证一下先

crella

2020-03-04 00:44:51 +08:00 via Android

不知道是不是这个形式？

puts RUBY_VERSION

class Hi
attr_reader :v
def initialize(v)
@v=v
end
def a
return Hi.new(@v+1)
end
def b
return Hi.new(@v+2)
end
end

script ="c"
c=Hi.new(0)
100.times do
script << ".a.b"
end
d=eval(script)
puts d.v

crella

2020-03-04 00:48:33 +08:00 via Android

不好意思，没看到是函数式编程，溜了溜了

agagega

2020-03-04 00:54:49 +08:00

主流的语言是栈实现的。要优化的思路也很简单直接：把栈去掉。所以可以考虑尾调用优化，或者协程类似的东西（想到什么说什么）

msg7086

2020-03-04 00:55:25 +08:00 via Android

这是作用域绑定的问题？

thedrwu

2020-03-04 00:55:47 +08:00 via Android

传统语言会爆栈，函数语言许多有尾递归优化。比如 Haskell 就重度依赖尾递归

dremy

2020-03-04 01:11:34 +08:00 via iPhone

可以从汇编语言层面分析，就很容易明白了

visitant

2020-03-04 01:37:04 +08:00

汇编语言分析+1,看看 CSAPP 吧.如果递归层次太多,当然会爆栈了, `ulimit -s`可以看 linux 下默认栈大小

251

2020-03-04 01:37:26 +08:00 via Android

原理是把机器码放进 CPU。无论什么东西大了都会爆吧

black11black

2020-03-04 02:20:42 +08:00

@251

这里讨论的大是相对于用户逻辑层面的大，不是相对于计算机数据层面的大。计算机爆内存比如深度学习中调谐几亿个参数会爆显卡这是一种大，相对于用户来说嵌套调用几百个函数就算大了。

ysc3839

2020-03-04 02:33:34 +08:00 via Android

x86 平台上 C 是直接用 call 指令实现的，而 call 又等价于 push 返回地址 + jmp。push 是把值压入栈中，所以肯定有可能爆栈。

CismonX

2020-03-04 03:35:10 +08:00

Q1：是否需要一个栈来保存状态？
A1：可以用，也可以不用。在很多函数式语言的实现中，用的是 CPS (Continuation Passing Style) 而非调用栈。

Q2：不用担心爆栈吗？
A2：为了防止尾递归导致内存占用无限增长，需要进行 TCO (Tail Call Optimization)，也就是我们熟知的尾调用优化。如果是基于调用栈的实现，那就在尾调用发生时跳转到函数首，而非分配一块新的栈帧。如果是基于 CPS 的实现，那就需要用到 Trampoline 来进行 TCO。

Q3：如果我要写一些函数式编程的代码，....，岂不是问题很大？
A3：楼主举的例子不是很恰当，这种链式调用算不上“函数式写法”，而且本身也不会导致“爆栈”，因为后一个方法是在前一个方法执行完成并返回后才被调用的，当后一个方法被调用时，前一个方法调用时的栈帧已经被释放。

PS：正巧我前一阵子也在学习编译原理。我试着实现一个极简的函数式语言 Unlambda 来练手。目前广为流传的实现中多数都引入了 CPS，但我的实现没有采用，而是用了调用栈。楼主可以看我之前的一个帖子： https://www.v2ex.com/t/643109。欢迎与我来探讨。

loading

2020-03-04 08:10:46 +08:00 via Android

建议楼主学习下汇编

lance6716

2020-03-04 09:37:19 +08:00 via Android

可以不把 ast 拷贝，而是留在“代码段”并在编译时正确指示调用和返回的地址。

black11black

2020-03-04 12:05:22 +08:00

@lance6716

我的实现太朴素了，因为 call 和参数寻址都是递归向上调用的，当时没想到传递地址的方式

251

2020-03-05 02:30:08 +08:00 via Android

调用深了，栈肯定会爆。主流语言默认情况不可能通过拷贝的方式调用函数，太占内存了。c ++ 有内联函数就是拷贝，这样执行效率会更高。