为了纪念 Stack Overflow 的公开发布,最短的导致栈溢出的代码是什么?欢迎任何语言。
ETA:只是为了明确这个问题,因为我是一个偶尔的 Scheme 用户:尾调用“递归”实际上是迭代,任何可以通过体面的编译器相对简单地转换为迭代解决方案的解决方案都不会被计算在内。:-P
ETA2:我现在选择了一个“最佳答案”;看到这个帖子的理由。感谢所有贡献的人!:-)
为了纪念 Stack Overflow 的公开发布,最短的导致栈溢出的代码是什么?欢迎任何语言。
ETA:只是为了明确这个问题,因为我是一个偶尔的 Scheme 用户:尾调用“递归”实际上是迭代,任何可以通过体面的编译器相对简单地转换为迭代解决方案的解决方案都不会被计算在内。:-P
ETA2:我现在选择了一个“最佳答案”;看到这个帖子的理由。感谢所有贡献的人!:-)
阅读这一行,并按照它所说的做两次。
所有这些答案,没有Befunge?我敢打赌,这是所有解决方案中最短的:
1
不开玩笑。自己试试吧:http ://www.quirkster.com/iano/js/befunge.html
编辑:我想我需要解释一下。操作数 1 将 1 推入 Befunge 的内部堆栈,并且没有其他任何内容将其置于语言规则下的循环中。
使用提供的解释器,您最终会——我的意思是最终——会遇到表示 Befunge 堆栈的 Javascript 数组变得太大而浏览器无法重新分配的点。如果你有一个简单的 Befunge 解释器,它的堆栈更小且有界——就像下面大多数语言的情况一样——这个程序会更快地导致更明显的溢出。
你也可以在 C#.net 中试试这个
throw new StackOverflowException();
内默尔:
这会使编译器崩溃并出现 StackOverflowException:
def o(){[o()]}
我目前最好的(在 x86 汇编中)是:
push eax
jmp short $-1
这会产生 3 个字节的目标代码 ( 50 EB FD
)。对于 16 位代码,这也是可能的:
call $
这也导致 3 个字节 ( E8 FD FF
)。
TK 给出的PIC18 答案导致以下指令(二进制):
overflow
PUSH
0000 0000 0000 0101
CALL overflow
1110 1100 0000 0000
0000 0000 0000 0000
但是,单独的 CALL 将执行堆栈溢出:
CALL $
1110 1100 0000 0000
0000 0000 0000 0000
但是 RCALL(相对调用)仍然更小(不是全局内存,所以不需要额外的 2 个字节):
RCALL $
1101 1000 0000 0000
所以 PIC18 上最小的是一条指令,16 位(两个字节)。每个循环需要 2 个指令周期。每个指令周期有 4 个时钟周期,你有 8 个时钟周期。PIC18 有一个 31 级堆栈,因此在第 32 次循环之后它将在 256 个时钟周期内溢出堆栈。在 64MHz 时,您将在 4 微秒和 2 个字节内溢出堆栈。
但是,PIC16F5x 系列使用 12 位指令:
CALL $
1001 0000 0000
同样,每个循环两个指令周期,每个指令 4 个时钟,因此每个循环 8 个时钟周期。
但是,PIC16F5x 有一个两级堆栈,因此在第三个循环中它会在 24 条指令中溢出。在 20MHz 时,它将在 1.2 微秒和 1.5 字节内溢出。
Intel 4004有一个 8 位调用子程序指令:
CALL $
0101 0000
对于对应于 ascii 'P' 的好奇。使用 3 级堆栈,需要 24 个时钟周期,总共32.4 微秒和一个字节。(除非你超频你的 4004 - 来吧,你知道你想要。)
这与 befunge 答案一样小,但比当前解释器中运行的 befunge 代码快得多。
C#:
public int Foo { get { return Foo; } }
热溢出!
// v___v
let rec f o = f(o);(o)
// ['---']
// -"---"-
每项任务都需要正确的工具。满足SO 溢出语言,优化以产生堆栈溢出:
so
特克斯:
\def~{~.}~
结果是:
!TeX 容量超出,抱歉 [输入堆栈大小=5000]。 ~->~ . ~->~ . ~->~ . ~->~ . ~->~ . ~->~ . ... <*> \def~{~.}~
乳胶:
\end\end
结果是:
!TeX 容量超出,抱歉 [输入堆栈大小=5000]。 \end #1->\csname end#1 \endcsname \@checkend {#1}\expandafter \endgroup \if@e... <*> \结束\结束
Z-80 汇编器——在内存位置 0x0000:
rst 00
一个字节 - 0xC7 - 将当前 PC 推入堆栈并跳转到地址 0x0000 的无限循环。
用英语:
recursion = n. See recursion.
另一个 PHP 示例:
<?
require(__FILE__);
BASIC中的以下内容如何:
10 GOSUB 10
(恐怕我没有 BASIC 解释器,所以这是一个猜测)。
我喜欢 Cody 的大量回答,所以这是我在 C++ 中的类似贡献:
template <int i>
class Overflow {
typedef typename Overflow<i + 1>::type type;
};
typedef Overflow<0>::type Kaboom;
无论如何都不是代码高尔夫条目,但仍然是元堆栈溢出的任何东西!:-P
这是我的 C 贡献,共有 18 个字符:
void o(){o();o();}
这很难进行尾调用优化!:-P
使用名为“s.bat”的 Window 批处理文件:
call s
Javascript
为了修剪更多的字符,并让我们自己被踢出更多的软件商店,让我们开始吧:
eval(i='eval(i)');
时髦的:
main()
$ groovy stack.groovy:
Caught: java.lang.StackOverflowError
at stack.main(stack.groovy)
at stack.run(stack.groovy:1)
...
请告诉我首字母缩略词“ GNU ”代表什么。
Person JeffAtwood;
Person JoelSpolsky;
JeffAtwood.TalkTo(JoelSpolsky);
这里希望没有尾递归!
C - 它不是最短的,但它是无递归的。它也不是可移植的:它在 Solaris 上崩溃,但某些 alloca() 实现可能会在此处返回错误(或调用 malloc())。调用 printf() 是必要的。
#include <stdio.h>
#include <alloca.h>
#include <sys/resource.h>
int main(int argc, char *argv[]) {
struct rlimit rl = {0};
getrlimit(RLIMIT_STACK, &rl);
(void) alloca(rl.rlim_cur);
printf("Goodbye, world\n");
return 0;
}
蟒蛇:
so=lambda:so();so()
或者:
def so():so()
so()
如果 Python 优化了尾调用...:
o=lambda:map(o,o());o()
perl 12 个字符:
$_=sub{&$_};&$_
bash in 10 个字符(函数中的空格很重要):
i(){ i;};i
尝试在一个汉堡上放 4 个以上的肉饼。堆栈溢出。
我在这篇文章之后选择“最佳答案”。但首先,我要感谢一些非常原创的贡献:
尽管我很喜欢上述内容,但挑战在于打代码高尔夫,为了公平起见,我必须将“最佳答案”授予最短代码,即 Befunge 条目;我不相信任何人能够击败它(尽管康拉德肯定已经尝试过),所以恭喜帕特里克!
看到大量递归堆栈溢出解决方案,我很惊讶没有人(截至目前)提出 Y 组合器(参见 Dick Gabriel 的文章,Y 的原因,作为入门)。我有一个使用 Y 组合器以及 aku 的 f(f(x)) 方法的递归解决方案。:-)
((Y (lambda (f) (lambda (x) (f (f x))))) #f)
这是 Scheme 中另一个有趣的例子:
((λ (x) (xx)) (λ (x) (xx)))
爪哇
Java 解决方案的略短版本。
class X{public static void main(String[]a){main(a);}}
xor esp, esp
ret
Java(尴尬):
public class SO
{
private void killme()
{
killme();
}
public static void main(String[] args)
{
new SO().killme();
}
}
编辑 当然可以大大缩短:
class SO
{
public static void main(String[] a)
{
main(null);
}
}
在 Lua 中:
function f()return 1+f()end f()
你必须对递归调用的结果做一些事情,否则尾调用优化将允许它永远循环。代码高尔夫的弱点,但很高兴拥有!
我想这和冗长的关键字意味着 Lua 不会很快赢得代码高尔夫。
向前:
: a 1 recurse ; a
解释器内部gforth
:
: a 1 recurse ; a
*the terminal*:1: Return stack overflow
: a 1 recurse ; a
^
Backtrace:
在打开固件提示的 Power Mac G4 上,这只会挂起机器。:)
作为 C 函数中的局部变量:
int x[100000000000];
红宝石:
def s() s() end; s()
GWBASIC 输出...
OK
10 i=0
20 print i;
30 i=i+1
40 gosub 20
run
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
22 23 24 25 26 27 28 29 30 31 32 33
Out of memory in 30
Ok
那里没有太多的堆栈深度:-)
名为 call.cmd 的批处理程序;
调用 call.cmd
****** B A T C H R E C U R S I O N exceeds STACK limits ******
Recursion Count=1240, Stack Usage=90 percent
****** B A T C H PROCESSING IS A B O R T E D ******
在 Scheme 中,这将导致解释器内存不足:
(define (x)
((x)))
(x)
Ruby,到目前为止比其他的短:
def a;a;end;a
(13 个字符)
C#
class _{static void Main(){Main();}}
请注意,我的是一个可编译的程序,而不仅仅是一个函数。我还删除了多余的空格。
出于天赋,我使班级名称尽可能小。
如果你认为调用帧是一个进程,堆栈是你的 Unix 机器,你可以认为一个 fork 炸弹是一个并行程序来创建堆栈溢出条件。试试这个 13 个字符的 bash 编号。无需保存到文件。
:(){ :|:& };:
在 Irssi(基于终端的 IRC 客户端,不是“真正的”编程语言)中,$L 表示当前命令行。因此,您可以通过以下方式导致堆栈溢出(“达到最大递归限制”):
/eval $L
图 18:
溢出
PUSH CALL overflow
CIL/MSIL :
loop: ldc.i4.0
br loop
对象代码:
16 2B FD
语言
(defun x() (x)) (x)
a{return a*a;};
编译:
gcc -D"a=main()" so.c
扩展为:
main() {
return main()*main();
}
F#
人们一直在问“F# 有什么用?”
let rec f n =
f (n)
性能优化版本(失败更快:))
let rec f n =
f (f(n))
在空白处,我认为:
它可能不会出现。:/
哈斯克尔:
let x = x
print x
好吧,还没有人提到Coldfusion,所以...
<cfinclude template="#ListLast(CGI.SCRIPT_NAME, "/\")#">
那应该做。
除非存在空程序导致堆栈溢出的语言,否则以下内容应该是最短的。
Befunge:
:
一遍又一遍地复制顶部堆栈值。
编辑:帕特里克的更好。用 1 填充堆栈比用 0 填充堆栈更好,因为解释器可以优化将 0 推入空堆栈作为空操作。
时髦的(5B):
run()
C#
class Program
{
class StackOverflowExceptionOverflow : System.Exception
{
public StackOverflowExceptionOverflow()
{
throw new StackOverflowExceptionOverflow();
}
}
static void Main(string[] args)
{
throw new StackOverflowExceptionOverflow();
}
}
我意识到这不是最短的(甚至打高尔夫球的代码也不会接近短),但我根本无法抗拒抛出一个异常,在被抛出时会抛出一个 stackoverflowexception,然后才能终止运行时本身^^
{/}loop
在 GhostScript 中运行时,抛出此异常:
GS>{/}loop
Error: /stackoverflow in --execute--
Operand stack:
--nostringval--
Execution stack:
%interp_exit .runexec2 --nostringval-- --nostringval-- --nostringval-- 2 %stopped_push --nostringval-- --nostringval-- %loop_continue 1753 2 3 %oparray_pop --nostringval-- --nostringval-- false 1 %stopped_push .runexec2 --nostringval-- --nostringval-- --nostringval-- 2 %stopped_push --nostringval-- --nostringval-- %loop_continue
Dictionary stack:
--dict:1150/1684(ro)(G)-- --dict:0/20(G)-- --dict:70/200(L)--
Current allocation mode is local
Last OS error: 11
Current file position is 8
这是不使用变量(51 个字符)的递归版本:
[{/[aload 8 1 roll]cvx exec}aload 8 1 roll]cvx exec
爪哇:
class X{static{new X();}{new X();}}
实际上会导致初始化 X 类的堆栈溢出。在调用 main() 之前,JVM 必须加载该类,并且当它这样做时会触发任何匿名静态代码块:
static {
new X();
}
如您所见,它使用默认构造函数实例化 X 。JVM 甚至会在构造函数之前调用匿名代码块:
{
new X();
}
这是递归部分。
Java:35 个字符
我认为为时已晚,但我仍然会发布我的想法:
class A{{new A();}static{new A();}}
使用静态初始化器和实例初始化器功能。
这是我电脑上的输出(注意它显示了两条错误消息):
Exception in thread "main" java.lang.StackOverflowError
at A.<init>(A.java:1)
......
at A.<init>(A.java:1)
Could not find the main class: A. Program will exit.
另见:http: //download.oracle.com/docs/cd/E17409_01/javase/tutorial/java/javaOO/initial.html
template<int n>struct f{f<n+1>a;};f<0>::a;
输出:
$ g++ test.cpp;
test.cpp:1: error: template instantiation depth exceeds maximum of 500 (use -ftemplate-depth-NN to increase the maximum) instantiating ‘struct f<500>’
test.cpp:1: instantiated from ‘f<499>’
test.cpp:1: instantiated from ‘f<498>’
......
即使编译器通过了模板,也会出现下一个错误:missing main
。
/* In C/C++ (second attempt) */
int main(){
int a = main() + 1;
return a;
}
c# 再次:
class Foo { public Foo() {new Foo(); } }
完成德尔福程序。
program Project1;
{$APPTYPE CONSOLE}
uses SysUtils;
begin
raise EStackOverflow.Create('Stack Overflow');
end.
so.c 15 个字符:
main(){main();}
结果:
antti@blah:~$ gcc so.c -o so
antti@blah:~$ ./so
Segmentation fault (core dumped)
编辑:好的,它会使用-Wall 发出警告,并且不会使用-O2 导致堆栈溢出。但它有效!
Java脚本:
Huppies 回答一行:
(function i(){ i(); })()
相同数量的字符,但没有换行:)
Java(X.java的完整内容):
class X {
public static void main(String[] args) {
main(null);
}}
考虑到所有的语法糖,我想知道是否可以在 Java 中完成更短的操作。任何人?
编辑:哎呀,我错过了已经发布了几乎相同的解决方案。
编辑 2:我会说,这个是(字符明智的)最短的可能
class X{public static void main(String[]a){main(null);}}
编辑 3:感谢安德斯指出 null 不是最佳论点,所以它更短:
class X{public static void main(String[]a){main(a);}}
已经有一个 perl 了,但这是几个字符短(9 对 12) - 它不会递归 :)
s//*_=0/e
我在 E2 上的Infinite Loop上有一个列表- 仅查看标题中指示为“堆栈溢出”的列表。
我认为最短的是
[dx]dx
编辑:显然这不起作用......至少在 GNU dc 上。也许是在 BSD 版本上。
包含换行符在内的10 个字符的 Shell 脚本解决方案:
好吧,从技术上讲不是堆栈溢出,但从逻辑上讲,如果您考虑生成一个新进程作为构造一个新的堆栈帧。
#!sh
./so
结果:
antti@blah:~$ ./so
[disconnected]
哎呀。注意:不要在家里尝试这个
电源外壳
$f={&$f};&$f
“由于调用深度溢出,脚本失败。调用深度达到1001,最大值为1000。”
在汇编语言中(x86 处理器,16 或 32 位模式):
call $
这将产生:
在 32 位模式下:0xe8;0xfb;0xff;0xff;0xff
在 16 位模式下:0xe8;0xfd;0xff
在 C/C++ 中:
int main( ) {
return main( );
}
TCL:
proc a {} a
我没有可以进行尾递归的 tclsh 解释器,但这可能会欺骗这样的事情:
proc a {} "a;a"
不会是最短的,但我必须尝试一些东西...... C#
字符串[] f = 新字符串[0];主要(f);
短一点
static void Main(){Main();}
这是另一个 Ruby 答案,这个答案使用 lambdas:
(a=lambda{a.call}).call
JavaScript中的另一个:
(function() { arguments.callee() })()
VB6
Public Property Let x(ByVal y As Long)
x = y
End Property
Private Sub Class_Initialize()
x = 0
End Sub
K&R C中的简短解决方案,可以编译:
main(){main()}
14 字节
作为对 Y 组合器评论的回应,我不妨通过 SKI 演算中的 Y 组合器:
S (K (S I I)) (S (S (K S) K) (K (S I I)))
我知道没有任何 SKI 解释器,但我曾经在 actionscript 中大约一个小时内写了一个图形解释器。如果有兴趣,我愿意发布(尽管我从来没有让布局非常有效地工作)
在这里阅读所有相关信息: http ://en.wikipedia.org/wiki/SKI_combinator_calculus
在 perl 中:
`$0`
事实上,这适用于任何支持反引号命令语法并将自己的名称存储在$0
错误的:
[1][1]#
(False 是一种堆栈语言:# 是一个 while 循环,它需要 2 个闭包,一个条件闭包和一个主体。主体是导致溢出的那个)。
一行CMD溢出
echo @call b.cmd > b.cmd & b
在哈斯克尔
fix (1+)
这试图找到 (1+) 函数 ( λ n → n + 1
) 的固定点。修复的实现是
fix f = (let x = f(x) in x)
所以
fix (1+)
变成
(1+) ((1+) ((1+) ...))
注意
fix (+1)
只是循环。
一个更好的lua解决方案:
function c()c()end;
将其粘贴到 SciTE 或交互式命令提示符中,然后调用它。繁荣!
GNU 使:
创建一个名为“Makefile”的文件,其内容如下:
a:
make
然后运行make:
$ make
请注意,必须使用制表符来偏移单词“make”。该文件有 9 个字符,包括 2 个换行符和 1 个制表符。
我想你可以用 bash 做类似的事情,但它可能太容易有趣了:
创建一个文件名“b”并将其标记为可执行文件(chmod +xb):
b ## ties the winning entry with only one character (does not require end-of-line)
现在执行文件
$ ( PATH=$PATH:. ; b )
很难说这种方法在技术上是否会导致堆栈溢出,但它确实会构建一个堆栈,该堆栈会不断增长,直到机器耗尽资源。使用 GNU make 执行此操作的一个很酷的事情是,您可以看到它在构建和销毁堆栈时输出状态信息(假设您在崩溃发生之前的某个时间点按了 ^C)。
PHP是递归的缩写
C++:
int overflow(int n)
{
return overflow(1);
}
int main(){
int a = 20;
return main();
}
JavaScript:
function i(){ i(); }
i();
int main(){
int (*f)() = &main;
f();
}
C#,用 20 个字符完成(不包括空格):
int s(){
return s();
}
号角:
Poke(0)
我试图在 Erlang 中做到这一点:
c(N)->c(N+1)+c(N-1).
c(0).
自身的双重调用使内存使用率上升O(n^2)
而不是O(n)
.
然而,Erlang 解释器似乎并没有崩溃。
递归是老帽子。这里是相互递归。通过调用任一函数开始。
a()
{
b();
}
b()
{
a();
}
PS:但是您要求的是最短的方式..不是最有创意的方式!
在 cell spus 上,没有堆栈溢出,因此不需要递归,我们只需擦除堆栈指针即可。
asm("andi $1, $1, 0" );
PHP - 递归只是为了好玩。我想需要一个 PHP 解释器才能让它停止运行,但是嘿 - 它会导致崩溃。
function a() { a(); } a();
//lang = C++... it's joke, of course
//Pay attention how
void StackOverflow(){printf("StackOverflow!");}
int main()
{
StackOverflow(); //called StackOverflow, right?
}
Perl 10 个字符
sub x{&x}x
最终耗尽所有可用内存。
MS-DOS 批处理:
copy CON so.bat
so.bat
^Z
so.bat
具有 27 个非空白字符的 C# - 包括调用。
Action a = null;
a = () => a();
a();
bash:只有一个进程
\#!/bin/bash
of() { of; }
of
几乎任何外壳:
sh $0
(5 个字符,仅在从文件运行时有效)
16 位汇编中的五个字节将导致堆栈溢出。
push cs
push $-1
ret
VB.Net
Function StackOverflow() As Integer
Return StackOverflow()
End Function
为了好玩,我不得不查找摩托罗拉 HC11 组件:
org $100
Loop nop
jsr Loop
不是很短,但很有效!(JavaScript)
setTimeout(1, function() {while(1) a=1;});
我认为这是我以前从未玩过的作弊 ;) 但这里有
8086汇编器:
org Int3VectorAdrress ;这是作弊吗?
诠释 3
1 个字节 - 或 5 个生成代码的字符,你说什么?
Ruby,虽然不是那么短:
class Overflow
def initialize
Overflow.new
end
end
Overflow.new
在C#中,这将创建一个 stackoverflow ...
static void Main()
{
Main();
}
为什么不
mov sp,0
(堆栈向下增长)
在名为 so.ps的PostScript文件中会导致 execstackoverflow
%!PS
/increase {1 add} def
1 increase
(so.ps) run
Actionscript 3: 全部用数组完成...
var i=[];
i[i.push(i)]=i;
trace(i);
也许不是最小的,但我认为它很可爱。特别是返回新数组长度的 push 方法!
在 x86 汇编中,将除以 0 指令放在中断处理程序的内存位置以除以 0!
序言
该程序在咨询时会导致 SWI-Prolog 和 Sicstus Prolog 崩溃。
p :- p, q.
:- p.
不尾调用可以破坏尾调用优化。在 Common Lisp 中:
(defun f () (1+ (f)))
D中的元问题:
class C(int i) { C!(i+1) c; }
C!(1) c;
编译时栈溢出
_asm t: call t;
OCaml
let rec f l = f l@l;;
这个有点不同。堆栈上只有一个堆栈帧(因为它是尾递归的),但它的输入一直在增长,直到溢出堆栈。只需像这样调用f
一个非空列表(在解释器提示下):
# f [0];;
Stack overflow during evaluation (looping recursion?).
虽然它没有真正的堆栈...
Brainf * ck 5个字符
+[>+]
Z80汇编语言...
.org 1000
loop: call loop
这会在位置 1000 处生成 3 个字节的代码......
1000 光盘 00 10
红宝石(再次):
def a(x);x.gsub(/./){a$0};end;a"x"
已经有很多红宝石解决方案,但我想我会投入一个正则表达式来衡量。
另一个 Windows 批处理文件:
:a
@call :a
main(){
main();
}
简单而漂亮的C。对我来说感觉很直观。
real n(0)
n(1)=0
end
或者
call main
end
第二种情况是依赖于编译器的;对于 GNU Fortran,它需要使用-fno-underscoring
.
(这两个计数都包括必需的换行符)
哈斯克尔:
main = print $ x 1 where x y = x y + 1
对话 APL
fib←{
⍵∊0 1:⍵
+/∇¨⍵-1 2
}
int main(void) { return main(); }
Python:
import sys
sys.setrecursionlimit(sys.maxint)
def so():
so()
so()
eval(t="eval(t)")
t="Execute(t)":Execute(t)
红宝石:
def i()i()end;i()
(17 个字符)
序言
p:-p。
= 5 个字符
然后启动它并查询 p
我认为这很小,并且在序言中用完了堆栈。
在 swi prolog 中仅查询一个变量会产生:
?- X. % ... 1,000,000 .... 10,000,000 年后 % % >> 42 << (最新版本给出了问题)
这是另一个 bash fork 炸弹::(){ :|:& };:
我认为这将在 Java 中工作(未尝试):
enum A{B.values()}
enum B{A.values()}
由于缺少 main(String[]),它甚至有机会失败之前,应该在静态初始化中溢出。
Redmond.Microsoft.Core.Windows.Start()
哎呀,我不知道,我从来没有写过导致堆栈溢出的代码;)