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

2020-03-04 00:31:53 +08:00
 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 )

2198 次点击
所在节点    问与答
16 条回复
crella
2020-03-04 00:37:31 +08:00
你这个比喻不对,a.in 和 a.out 方法返回的都是空值,不存在下一步执行

我去验证一下先
crella
2020-03-04 00:44:51 +08:00
不知道是不是这个形式?

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
不好意思,没看到是函数式编程,溜了溜了
agagega
2020-03-04 00:54:49 +08:00
主流的语言是栈实现的。要优化的思路也很简单直接:把栈去掉。所以可以考虑尾调用优化,或者协程类似的东西(想到什么说什么)
msg7086
2020-03-04 00:55:25 +08:00
这是作用域绑定的问题?
thedrwu
2020-03-04 00:55:47 +08:00
传统语言会爆栈,函数语言许多有尾递归优化。比如 Haskell 就重度依赖尾递归
dremy
2020-03-04 01:11:34 +08:00
可以从汇编语言层面分析,就很容易明白了
visitant
2020-03-04 01:37:04 +08:00
汇编语言分析+1,看看 CSAPP 吧.如果递归层次太多,当然会爆栈了, `ulimit -s`可以看 linux 下默认栈大小
251
2020-03-04 01:37:26 +08:00
原理是把机器码放进 CPU。无论什么东西大了都会爆吧
black11black
2020-03-04 02:20:42 +08:00
@251

这里讨论的大是相对于用户逻辑层面的大,不是相对于计算机数据层面的大。计算机爆内存比如深度学习中调谐几亿个参数会爆显卡这是一种大,相对于用户来说嵌套调用几百个函数就算大了。
ysc3839
2020-03-04 02:33:34 +08:00
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
建议楼主学习下汇编
lance6716
2020-03-04 09:37:19 +08:00
可以不把 ast 拷贝,而是留在“代码段”并在编译时正确指示调用和返回的地址。
black11black
2020-03-04 12:05:22 +08:00
@lance6716

我的实现太朴素了,因为 call 和参数寻址都是递归向上调用的,当时没想到传递地址的方式
251
2020-03-05 02:30:08 +08:00
调用深了,栈肯定会爆。主流语言默认情况不可能通过拷贝的方式调用函数,太占内存了。c ++ 有内联函数就是拷贝,这样执行效率会更高。

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/649615

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX