函数调用的时候,现场一定要保存在操作系统提供的栈空间里面么?
石奇偲
有人说写一个无限递归的程序 如果是函数式语言就不会出现栈溢出,而是无限循环,如果是命令式语言就会抛出栈溢出的异常.
但是我想
1.如果这个无限递归不是尾递归的形式写出来的,在函数式语言里面,递归的时候就不要保留现场到栈空间了?
然后在DrScheme里随便敲了一个
(define (f1.11a count)
(cond( (< count 4) count)
( else (+ (f1.11a (- count 1)) (+ (* 2 (f1.11a (- count 2))) (* 3 (f1.11a (- count 3))))))))
(f1.11a 512)
程序跑了很长的时间,最后提示内存用尽,而不是栈溢出!
2.基于以上实验,我想 一般来说编译器会把递归的现场保存在操作系统提供的栈空间里,但是一般操作系统给每个进程提供的栈空间有限,超过了,程序就抛出异常.现代编译器是不是把递归现场保存在堆里(这里的堆不是数据结构里的堆,是相对于栈空间来说的另外的内存空间)堆的大小一般没有限制,所以不会出现栈溢出.
然后我用c#写了一段:
using System;
using System.Collections.Generic;
using System.Text;
namespace testStack
{
class Program
{
static void Main(string[] args)
{
System.Console.WriteLine(Digui(200));
}
static int Digui(int i)
{
if (i == 0) return 0;
else return Digui(i--) + 1;
}
}
}
运行一瞬间就报栈溢出了.
显然1不能用DrScheme使用了类似动态规划的表格技术来优化递归,那么怎么解释程序1?
函数调用的现场不能保存在堆里面么?如果是,为什么?如果不是,怎么解释程序2?
Jeffrey Zhao
yuan zhu
石奇偲
而且我觉的
(define (f1.11a count)
(cond( (< count 4) count)
( else (+ (f1.11a (- count 1)) (+ (* 2 (f1.11a (- count 2))) (* 3 (f1.11a (- count 3))))))))
(f1.11a 512)
我写了一个我以为是尾递归的版本
(define (f1.11b a b c count)
(if(= count 3);小于3的视为无意义
a
(f1.11b (+ a (+ (* 2 b) (* 3 c))) a b (- count 1))))
(f1.11b 512)
这个版本的执行速度比前者快很多.
而且如果第一个版本编译器优化成尾递归了,就是用迭代来执行,应该不会占用那么多的内存吧?
Jeffrey Zhao
石奇偲
那么Scheme的例子,每次运行递归调用都会保留现场,如果是保留到栈里,为什么会是在执行了几分钟之后报内存耗尽,而不是像c#的例子在运行之后一瞬间报栈溢出?
石奇偲
Jeffrey Zhao
Jeffrey Zhao
石奇偲
至少在栈快溢出的时候把现场的保存转到堆里,这样的话如果我写的不是一个无限的递归而是一个比较深的递归,可能可以跑出结果,而不是在程序刚一运行的时候就报栈空间溢出?
qiaojie
石奇偲
sagasw
如果这玩意做成内置的，那得确定每个程序员都想这样做
------------------------------------------
blog: http://sunxiunan.com/
C++, Lua, living in Dalian
http://twitter.com/sagasw
------------------------------------------
Jeffrey Zhao
Jeffrey Zhao
Jeffrey Zhao
{
if (i == 0) return 0;
else return Digui(i--) + 1;
}
sagasw
首先如果要比较，那得确定Scheme也是用的栈来保持调用数据。
其次，一般来讲程序栈都是有限的，大概也就是几M左右，当然很快溢出。
------------------------------------------
blog: http://sunxiunan.com/
C++, Lua, living in Dalian
http://twitter.com/sagasw
------------------------------------------
就像第一个Scheme的程序,如果调用的是(f1.11a 28)而不是(f1.11a 512),则在4,5秒之后就出了结果,而c#的程序,即使是调用 System.Console.WriteLine(
石奇偲
改成else return Digui(--i) + 1;就行了.而且运行的速度还很快.
看来c#也是把现场放到堆里了?
我把Scheme那个程序改写成c#版本的试一试不知道会怎么样?
up duan
这就是我的问题,第一个Scheme的例子和第二个c#的例子,我都特意写了不是尾递归的版本,所以不是应该按照普通的函数调用来执行么?
那么Scheme的例子,每次运行递归调用都会保留现场,如果是保留到栈里,为什么会是在执行了几分钟之后报内存耗尽,而不是像c#的例子在运行之后一瞬间报栈溢出?
sagasw
我有一篇不科学没结论的博客有点近似
http://sunxiunan.com/?p=1784
------------------------------------------
blog: http://sunxiunan.com/
C++, Lua, living in Dalian
http://twitter.com/sagasw
------------------------------------------
Jeffrey Zhao
Larry, LIU Xinyu
抛开尾递归不说。
其实你耐心的继续看SICP，看到求值器的环境模型那一章就明白了，
FP语言的模型和procedural语言的模型是不同的，后者assume用户（也就是程序员）不会大量使用递归。故而使用栈来简化编译器实现。
我记得当年在DOS上使用Turbo Pascal时，语言的手册里明确标明，递归的使用不得超过7层，否则会发生栈溢出。
我再给一个类比问题，很经典。相信你一看就明白了。
这就是深度优先搜索迷宫问题，我们知道深度优先的最简单实现是递归实现。并且这个递归不是尾递归。
在DOS时代，迷宫的深度造成可以轻易大于7，故而递归一定会溢出，那时候竞赛遇到这类题目我们的典型解法就是使用stack。
每次搜索扩展时把当前走法压栈，然后回溯的时候弹出。
还有一个名题是八皇后，8正好比7大一，所以如果使用DFS解八皇后，就必须使用自定义的stack。
最后我再强调一点，许多多范式语言最近也争先恐后的加入了FP的一些库，这也算是感时髦吧。但是他们背后的计算模型是procedural的。
所以你可以轻易判断这些FP工具是否可以支持你来实现工业级别的应用，这个方法就是实现一个尾递归的阶乘：
例如python:
# I tested that python doesn't support tail recursion.
# as below:
# def fact(n):
# if(n==0):
# return 1
# else:
# return n*fact(n-1)
# if we call fact(1000), the error is:
# RuntimeError: maximum recursion depth exceeded
虽然python里有map, reduce, filter等等看似functional的东西，但是它用的不是FP模型。
--
LIU
https://sites.google.com/site/algoxy/home
On Feb 12, 10:51 am, 石奇偲 <shiqi...@gmail.com> wrote:
> 按照"如果某人写个Scheme解释器，
> 函数调用时不用栈，所有数据往堆上搞，自然不会栈溢出"的思路,
> c#的编译器为什么不把函数调用的现场保存在堆里?
> 至少在栈快溢出的时候把现场的保存转到堆里,这样的话如果我写的不是一个无限的递归而是一个比较深的递归,可能可以跑出结果,而不是在程序刚一运行的时候就报栈空间溢出?
>
> 在 2011年2月12日 上午10:48，Jeffrey Zhao <je...@live.com>写道：
>
> > 听不懂了，你没写成尾递归，C#怎么做优化？你的Scheme版本也没有优化啊，还是会内存不足。
>
> > Jeffrey Zhao
> > Blog:http://blog.zhaojie.me/
> > Twitter:http://twitter.com/jeffz_cn
>
> > *From:* 石奇偲 <shiqi...@gmail.com>
> > *Sent:* Saturday, February 12, 2011 10:45 AM
> > *To:* pon...@googlegroups.com
> > *Subject:* Re: [TL] 函数调用的时候,现场一定要保存在操作系统提供的栈空间里面么?
石奇偲
明白你们的意思了.
Scheme里函数调用用的是Continuation方法,有点类似动态规划,而不是用栈.
c#里面用的是栈
石奇偲
Jeffrey Zhao
if(n==0):
return 1
else:
return n*fact(n-1)
��Ȼ��ȷPython��һ�����β�ݹ��Ż��������������ȷ����β�ݹ顣
��������Ϊ������ģ����һ�֣�ִ�л�������һ�֡�Ϊ�˱�֤���ܵ����أ�û�취˭�÷�ŵ������ǹ��ʽ�ģ���FP����Ҳ���п�������ջ�ġ����Ի���Ҫ�����ס��ض����ԡ��Ĵ��?ʽ���ú���ʽ�����ʽ���л�������̫���ˡ���
Jeffrey Zhao
Blog: http://blog.zhaojie.me/
Twitter: http://twitter.com/jeffz_cn
-----ԭʼ�ʼ�-----
From: Larry, LIU Xinyu
Sent: Saturday, February 12, 2011 11:19 AM
To: TopLanguage
Subject: [TL] Re: ������õ�ʱ��,�ֳ�һ��Ҫ�����ڲ���ϵͳ�ṩ��ջ�ռ�����ô?
Hi,
��β�ݹ鲻˵��
��ʵ�����ĵļ���SICP��������ֵ���Ļ���ģ����һ�¾������ˣ�
FP���Ե�ģ�ͺ�procedural���Ե�ģ���Dz�ͬ�ģ�����assume�û���Ҳ���dz���Ա���������ʹ�õݹ顣�ʶ�ʹ��ջ��������ʵ�֡�
�Ҽǵõ�����DOS��ʹ��Turbo Pascalʱ�����Ե��ֲ�����ȷ�������ݹ��ʹ�ò��ó���7�㣬����ᷢ��ջ�����
���ٸ�һ��������⣬�ܾ��䡣������һ���������ˡ�
�����������������Թ����⣬����֪��������ȵ����ʵ���ǵݹ�ʵ�֡���������ݹ鲻��β�ݹ顣
��DOSʱ���Թ��������ɿ������״���7���ʶ�ݹ�һ�����������ʱ��������������Ŀ���ǵĵ��ͽⷨ����ʹ��stack��
ÿ��������չʱ�ѵ�ǰ�߷�ѹջ��Ȼ����ݵ�ʱ����
����һ�������ǰ˻ʺ�8��ñ�7��һ���������ʹ��DFS��˻ʺͱ���ʹ���Զ����stack��
�������ǿ��һ�㣬���ʽ�������Ҳ���ȿֺ�ļ�����FP��һЩ�⣬��Ҳ���Ǹ�ʱ�ְɡ��������DZ���ļ���ģ����procedural�ġ�
��������������ж���ЩFP�����Ƿ����֧������ʵ�ֹ�ҵ�����Ӧ�ã������������ʵ��һ��β�ݹ�Ľ׳ˣ�
����python:
# I tested that python doesn't support tail recursion.
# as below:
# def fact(n):
# if(n==0):
# return 1
# else:
# return n*fact(n-1)
# if we call fact(1000), the error is:
# RuntimeError: maximum recursion depth exceeded
��Ȼpython����map, reduce, filter�ȵȿ���functional�Ķ������������õIJ���FPģ�͡�
--
LIU
https://sites.google.com/site/algoxy/home
On Feb 12, 10:51 am, ʯ��� <shiqi...@gmail.com> wrote:
> ����"���ij���Scheme��������
> �������ʱ����ջ�������������ϸ㣬��Ȼ����ջ���"��˼·,
> c#�ı�����Ϊʲô���Ѻ�����õ��ֳ������ڶ���?
> ������ջ�������ʱ����ֳ��ı���ת������,����Ļ������д�IJ���һ�����ĵݹ����һ���Ƚ���ĵݹ�,���ܿ����ܳ����,�����ڳ����һ���е�ʱ��ͱ�ջ�ռ����?
>
> �� 2011��2��12�� ����10:48��Jeffrey Zhao <je...@live.com>���
>
> > ���ˣ���ûд��β�ݹ飬C#��ô���Ż������Scheme�汾Ҳû���Ż��������ǻ��ڴ治�㡣
>
> > Jeffrey Zhao
> > Blog:http://blog.zhaojie.me/
> > Twitter:http://twitter.com/jeffz_cn
>
> > *From:* ʯ��� <shiqi...@gmail.com>
> > *Sent:* Saturday, February 12, 2011 10:45 AM
> > *To:* pon...@googlegroups.com
> > *Subject:* Re: [TL] ������õ�ʱ��,�ֳ�һ��Ҫ�����ڲ���ϵͳ�ṩ��ջ�ռ�����ô?
>
> > ��,��Ҳ���ҵĿ���.����Ϊʲô��ô��Ȼ���Ż�,c#����?
>
> > �� 2011��2��12�� ����10:04��Jeffrey Zhao <je...@live.com>���
>
> >> �������C#��������Ͳ���β�ݹ飬ִ��ʱ���Ҫ���ϱ���ռ�ռ��ˡ�����DrScheme��˭֪��������ôִ�е��ء����ij��д��Scheme���������������ʱ����ջ�������������ϸ㣬��Ȼ����ջ��������ǻ��ڴ��þ��ˡ�
>
> >> ���������β�ݹ��Ż��ģ������ջ��������Ҳ�������¿ռ�ȵȣ���������ѭ��������ռ���ڴ档
jinhu wang
然后函数的临时变量调用过程不放在栈里面，那栈还能干什么？
最后，如果你用vxworks操作系统，它提供给你一个taskInit函数，你可以指定你申请的堆内存作为任务的栈空间。
qiaojie
首先，堆内存的维护者是用户，谁申请谁释放。栈内存的维护者是系统。
jinhu wang
有GC的语言指的是啥语言？做这么个实验吧，启动一个线程，你在线程里用你的容器（带GC的）申请例如1M堆内存。在外边把这个线程强行终止。然后你看看内存是不是释放了。
至于栈空间，一般是创建线程的时候，系统调用（例如createthread）申请了一段内存（大小或者缺省或者指定）作为栈空间，有的系统提供灵活的api，你可以申请好一段堆内存直接作为线程的初始化参数来替代系统自己申请的动作。后者的好处是你可以很好的加一些栈越界判断之类的机制到里面，也有利于内存管理。
机械唯物主义 : linjunhalida
2011/2/12 qiaojie <qia...@gmail.com>:
jinhu wang
Xuefeng Chang
jinhu wang
The _resetstkoflw function recovers from a stack overflow condition, allowing a program to continue instead of failing with a fatal exception error. If the _resetstkoflw function is not called, there are no guard page after the previous exception. The next time that there is a stack overflow, there are no exception at all and the process terminates without warning.
If a thread in an application causes an EXCEPTION_STACK_OVERFLOW exception, the thread has left its stack in a damaged state. This is in contrast to other exceptions such as EXCEPTION_ACCESS_VIOLATION or EXCEPTION_INT_DIVIDE_BY_ZERO, where the stack is not damaged. The stack is set to an arbitrarily small value when the program is first loaded. The stack then grows on demand to meet the needs of the thread. This isLarry, LIU Xinyu
I can't read the content because of wrong encoding. Do you mean the
fact function can compute 1000! in your machine?
I am currently using Python 2.5, it report this error at least in my
PC.
BTW: the python version of reduce, map, and filter internally use
iterative implementation so that they seem can recurs over big
numbers. For instance:
>>> reduce(lambda x, y: x+y, range(100000))
4999950000L
see Python-2.6.5\Modules\_functoolsmodule.c line 12
--
LIU
https://sites.google.com/site/algoxy/home
On Feb 12, 11:40 am, "Jeffrey Zhao" <je...@live.com> wrote:
> def fact(n):
> if(n==0):
> return 1
> else:
> return n*fact(n-1)
>
> Ȼ ȷPython һ β ݹ Ż ȷ β ݹ顣
>
> Ϊ ģ һ ֣ ִ л һ ֡ Ϊ ˱ ֤ ܵ أ û 취˭ ÷ ŵ ǹ ʽ ģFP Ҳ п ջ ġ Ի Ҫ ס ض ԡ Ĵ ?ʽ ú ʽ ʽ л̫ ˡ
>
> Jeffrey Zhao
> Blog:http://blog.zhaojie.me/
> Twitter:http://twitter.com/jeffz_cn
> -----ԭʼ ʼ -----
> From: Larry, LIU Xinyu
> Sent: Saturday, February 12, 2011 11:19 AM
> To: TopLanguage
> Subject: [TL] Re: õ ʱ , ֳ һ Ҫ ڲ ϵͳ ṩ ջ ռ ô?
>
> Hi,
>
> β ݹ鲻˵
>
> ʵ ĵļ SICP ֵ Ļ ģ һ ¾ ˣ
>
> FP Ե ģ ͺ procedural Ե ģ Dz ͬ ģ assume û Ҳ dz Ա ʹ õݹ顣ʶ ʹ ջ ʵ ֡
> Ҽǵõ DOS ʹ Turbo Pascalʱ Ե ֲ ȷ ݹ ʹ ò ó 7 㣬 ᷢ ջ
>
> ٸ һ ⣬ ܾ 䡣 һ ˡ
>
> Թ ⣬ ֪ ȵ ʵ ǵݹ ʵ ֡ ݹ鲻 β ݹ顣
> DOSʱ Թ ɿ ״ 7 ʶ ݹ һ ʱ Ŀ ǵĵ ͽⷨʹ stack
> ÿ չʱ ѵ ǰ ߷ ѹջ Ȼ ݵ ʱ
>
> һ ǰ˻ʺ 8 ñ 7 һ ʹ DFS ˻ʺͱ ʹ Զ stack
>
> ǿ һ 㣬 ʽ Ҳ ȿֺ ļ FP һЩ ⣬ Ҳ Ǹ ʱ ְɡ DZ ļ ģprocedural ġ
> ж ЩFP Ƿ ֧ ʵ ֹ ҵ Ӧ ã ʵ һ β ݹ Ľ׳ˣ
> python:
> # I tested that python doesn't support tail recursion.
> # as below:
> # def fact(n):
> # if(n==0):
> # return 1
> # else:
> # return n*fact(n-1)
> # if we call fact(1000), the error is:
> # RuntimeError: maximum recursion depth exceeded
>
> Ȼpython map, reduce, filter ȵȿ functional Ķ õIJ FPģ ͡
>
> --
> LIUhttps://sites.google.com/site/algoxy/home
>
> On Feb 12, 10:51 am, ʯ <shiqi...@gmail.com> wrote:
>
> > " ij д Scheme
> > ʱ ջ ϸ㣬 Ȼ ջ " ˼·,
> > c# ı Ϊʲô Ѻ õ ֳ ڶ ?
> > ջ ʱ ֳ ı ת , Ļ д IJ һ ĵݹ һ Ƚ ĵݹ, ܿ ܳ , ڳ һ е ʱ ͱ ջ ռ ?
>
> > 2011 2 12 10:48 Jeffrey Zhao <je...@live.com>д
>
> > > ˣ ûд β ݹ飬C# ô Ż Scheme 汾Ҳû Ż ǻ ڴ治 㡣
>
> > > Jeffrey Zhao
> > > Blog:http://blog.zhaojie.me/
> > > Twitter:http://twitter.com/jeffz_cn
>
> > > *From:* ʯ <shiqi...@gmail.com>
> > > *Sent:* Saturday, February 12, 2011 10:45 AM
> > > *To:* pon...@googlegroups.com
> > > *Subject:* Re: [TL] õ ʱ , ֳ һ Ҫ ڲ ϵͳ ṩ ջ ռ ô?
>
> > > , Ҳ ҵĿ . Ϊʲô ô Ȼ Ż ,c# ?
>
> > > 2011 2 12 10:04 Jeffrey Zhao <je...@live.com>д
>
> > >> C# Ͳ β ݹ飬ִ ʱ Ҫ ϱ ռ ռ ˡ DrScheme ˭֪ ôִ еء ij д Scheme ʱ ջ ϸ㣬 Ȼ ջ ǻ ڴþ ˡ
Jeffrey Zhao
def fact(n):
if(n==0):
return 1
else:
return n*fact(n-1)
Jeffrey Zhao
Blog: http://blog.zhaojie.me/
Twitter: http://twitter.com/jeffz_cn
-----原始邮件-----
From: Larry, LIU Xinyu
Sent: Saturday, February 12, 2011 2:00 PM
To: TopLanguage
Subject: [TL] Re: 函数调用的时候,现场一定要保存在操作系统提供的栈空间里面么?
石奇偲
直觉上,我觉得对系统栈的操作都应该放到核心态里面运行,因为一般情况下用户没有理由显式的操作系统栈(一个函数被调用之后,从另外一个函数返回?)
不过刚才查了一下,有一些函数也可以对系统栈进行操作.但是封装的很严.
不知道在汇编级或者更底层有没有可以直接访问系统栈的方法,总之直接操作系统栈我觉得是很不可思议的事情.
qiaojie
石奇偲
好吧,我看书去了.
jinhu wang
Larry, LIU Xinyu
What about this one?
def fact(n, acc = 1):
if n == 0:
return acc
else:
return fact(n-1, acc*n)
>>> fact(5)
120
>>> fact(1000)
Traceback (most recent call last):
File "<pyshell#13>", line 1, in <module>
fact(1000)
.....
RuntimeError: maximum recursion depth exceeded.
Cheers.
--
LIU
https://sites.google.com/site/algoxy/home
up duan
red...@gmail.com
于 2011/2/12 10:56, qiaojie 写道:
真把函数调用的现场保存在堆里你又要抱怨C#性能太差了
Jeffrey Zhao
up duan
qiaojie
up duan
lzprgmr
Blog: http://www.cnblogs.com/baiyanhuang/
Douban:http://www.douban.com/people/baiyanhuang/
Jeffrey Zhao
but the code you showed at the first time is not tail recursion. :D
Jeffrey Zhao
Blog: http://blog.zhaojie.me/
Twitter: http://twitter.com/jeffz_cn
-----原始邮件-----
From: Larry, LIU Xinyu
Sent: Saturday, February 12, 2011 3:10 PM
Larry, LIU Xinyu
This depends on platform and compiler. I guess you built it with MS/
DevStudio and actually you got it run in .Net.
Here is my test:
//-------------fact.cpp-------------
#include <iostream>
typedef long long N;
N fact(N n, N acc=1){
if(n==0) return acc; else return fact(n-1, acc*n);}
int main(){ std::cout<<fact(100000); }
And the result under different level of optimization is as the
following:
liuuuxin@wl025474 ~/temp/cpp
$ g++ fact.cpp -o fact
liuuuxin@wl025474 ~/temp/cpp
$ ./fact
>>>fact.exe.stackdump
liuuuxin@wl025474 ~/temp/cpp
$ g++ fact.cpp -O2 -o fact
liuuuxin@wl025474 ~/temp/cpp
$ ./fact
0
liuuuxin@wl025474 ~/temp/cpp
$ g++ fact.cpp -O3 -o fact
liuuuxin@wl025474 ~/temp/cpp
$ ./fact
0
No mater what optimization level, correct answer can't be output.
--
LIU
https://sites.google.com/site/algoxy/home
On Feb 12, 6:00 pm, lzprgmr <baiyanhu...@gmail.com> wrote:
> 我试了一下，在C++中是会对尾递归做优化，从而不会stack overflow~
>
> int factorial_tail_recursion(int n, int acc)
> {
> if (n == 1)
> {
> return acc;
>
> }
>
> return factorial_tail_recursion(n-1, acc * n);
>
> }
>
> int factorial(int n)
> {
> if (n == 1)
> {
> return 1;
>
> }
>
> return n * factorial(n-1);
>
> }
>
> int main(int argc, const char *argv[])
> {
>
> // no stack overflow
> int v1 = factorial_tail_recursion(1000000000, 1);
> cout << v1 << endl;
>
> // stack overflow
> int v2 = factorial(1000000000);
>
> cout << v2 << endl;
>
> return 0;
>
> }
>
> Blog:http://www.cnblogs.com/baiyanhuang/
> Douban:http://www.douban.com/people/baiyanhuang/
>
Larry, LIU Xinyu
I don't think relay on tail recursion optimization is a good idea when
you programming in functional way.
Compare the two `fact' programs with and without tail recursion, it is
obvious that the latter is expressive.
It's not possible to re-write all functional algorithms in tail
recursion manner. This limits the usage of functional
paradigm in procedural languages.
My suggestion is that: Think and prototype in functional way, then
evaluate if it is suitable in your host language.
If so (for example, O(lg N) deduce to very small recursion depth),
translate it directly to your implementation,
otherwise, eliminate the recursion by iteration or turn it into tail
recursion if your platform support optimization.
Larry, LIU Xinyu
Atry
张国锋
Jeffrey Zhao
张国锋
Jeffrey Zhao
phenix y
张国锋
你说的call指令-也即函数调用指令-实际上应该来自高级语言。计算机语言中的函数（function），最早应该是在1958年出现，分别是Fortran II 和Lisp，不过它们的含义应该是不一样的，Fortran的函数实际上是一种代码组织手段，而Lisp的函数更接近来自λ演算。而当时的计算机还十分落后，指令系统很简单（好象连变址寻址都没有）。后来才出现专为函数调用服务的call指令（称为用户级指令，当时还没有现代意义上的操作系统，专门为当时唯一的实用高级语言Fortran优化可是一大卖点）。