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

[black11black]

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

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

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

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 ）

[crella]

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

我去验证一下先

[crella]

不知道是不是这个形式？

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]

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

[agagega]

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

[msg7086]

这是作用域绑定的问题？

[thedrwu]

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

[dremy]

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

[visitant]

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

[251]

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

[black11black]

@251

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

[ysc3839]

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

[CismonX]

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]

建议楼主学习下汇编

[lance6716]

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

[black11black]

@lance6716

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

[251]

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