Apa kode terpendek yang menyebabkan stack overflow? [Tutup]

Untuk memperingati peluncuran publik Stack Overflow, apa kode terpendek yang menyebabkan stack overflow? Selamat datang dalam bahasa apa pun.

ETA: Hanya untuk memperjelas pertanyaan ini, mengingat saya pengguna Skema sesekali: "rekursi" panggilan ekor benar-benar iterasi, dan solusi apa pun yang dapat dikonversi ke solusi berulang relatif sepele oleh kompiler yang layak tidak akan Dihitung. :-P

ETA2: Saya sekarang telah memilih "jawaban terbaik"; lihat posting ini untuk alasan. Terima kasih untuk semua orang yang berkontribusi! :-)

Semua jawaban ini dan tidak ada Befunge? Saya akan bertaruh dalam jumlah yang adil itu solusi terpendek dari semuanya:

1

Tidak bercanda. Coba sendiri: http://www.quirkster.com/iano/js/befunge.html

EDIT: Saya kira saya perlu menjelaskan ini. 1 operan mendorong 1 ke tumpukan internal Befunge dan kurangnya hal lain menempatkannya dalam satu lingkaran di bawah aturan bahasa.

Menggunakan penerjemah yang disediakan, Anda pada akhirnya - dan maksud saya akhirnya - memukul titik di mana array Javascript yang mewakili tumpukan Befunge menjadi terlalu besar bagi peramban untuk dialokasikan kembali. Jika Anda memiliki juru bahasa Befunge sederhana dengan tumpukan yang lebih kecil dan terbatas - seperti halnya dengan sebagian besar bahasa di bawah ini - program ini akan menyebabkan luapan yang lebih nyata lebih cepat.

Baca baris ini, dan lakukan apa yang dikatakannya dua kali .

Anda juga dapat mencoba ini di C # .net

throw new StackOverflowException();

Nemerle :

Ini membuat crash kompiler dengan StackOverflowException:

def o(){[o()]}

Terbaik saya saat ini (dalam perakitan x86) adalah:

push eax
jmp short $-1

yang menghasilkan 3 byte kode objek ( 50 EB FD). Untuk kode 16-bit, ini juga memungkinkan:

call $

yang juga menghasilkan 3 byte ( E8 FD FF).

PIC18

The jawaban PIC18 diberikan oleh TK hasil dalam petunjuk berikut (biner):

overflow
   PUSH
   0000 0000 0000 0101
   CALL overflow
   1110 1100 0000 0000
   0000 0000 0000 0000

Namun, CALL saja akan melakukan stack overflow:

CALL $
1110 1100 0000 0000
0000 0000 0000 0000

PIC18 lebih kecil, lebih cepat

Tetapi RCALL (panggilan relatif) masih lebih kecil (bukan memori global, jadi tidak perlu tambahan 2 byte):

RCALL $
1101 1000 0000 0000

Jadi yang terkecil pada PIC18 adalah instruksi tunggal, 16 bit (dua byte). Ini akan membutuhkan 2 siklus instruksi per loop. Pada 4 siklus clock per siklus instruksi Anda punya 8 siklus clock. PIC18 memiliki tumpukan level 31, jadi setelah loop ke-32 ia akan meluap tumpukan, dalam 256 siklus clock. Pada 64MHz, Anda akan meluap tumpukan dalam 4 detik mikro dan 2 byte .

PIC16F5x (bahkan lebih kecil dan lebih cepat)

Namun, seri PIC16F5x menggunakan instruksi 12 bit:

CALL $
1001 0000 0000

Sekali lagi, dua siklus instruksi per loop, 4 jam per instruksi jadi 8 siklus clock per loop.

Namun, PIC16F5x memiliki tumpukan dua level, sehingga pada loop ketiga akan meluap, dalam 24 instruksi. Pada 20MHz, itu akan meluap dalam 1,2 detik mikro dan 1,5 byte .

Intel 4004

The Intel 4004 memiliki 8 bit panggilan subroutine instruksi:

CALL $
0101 0000

Untuk penasaran yang sesuai dengan ascii 'P'. Dengan tumpukan 3 level yang membutuhkan 24 siklus clock untuk total 32,4 detik mikro dan satu byte . (Kecuali jika Anda overclock 4004 Anda - ayolah, Anda tahu Anda ingin.)

Yang sekecil jawaban befunge, tapi jauh lebih cepat daripada kode befunge yang berjalan pada interpreter saat ini.

C #:

public int Foo { get { return Foo; } }

Hoot overflow!

//              v___v
let rec f o = f(o);(o)
//             ['---']
//             -"---"-

Setiap tugas membutuhkan alat yang tepat. Memenuhi bahasa SO Overflow , dioptimalkan untuk menghasilkan stack overflow:

so

TeX:

\def~{~.}~

Hasil dalam:

! Kapasitas TeX terlampaui, maaf [ukuran tumpukan input = 5000].
~ -> ~
    .
~ -> ~
    .
~ -> ~
    .
~ -> ~
    .
~ -> ~
    .
~ -> ~
    .
...
<*> \ def ~ {~.} ~

Getah:

\end\end

Hasil dalam:

! Kapasitas TeX terlampaui, maaf [ukuran tumpukan input = 5000].
\ end # 1 -> \ csname end # 1
                      \ endcsname \ @checkend {# 1} \ expandafter \ endgroup \ if @ e ...
<*> \ end \ end

Assembler Z-80 - di lokasi memori 0x0000:

rst 00

satu byte - 0xC7 - loop tanpa akhir untuk mendorong PC saat ini ke stack dan melompat ke alamat 0x0000.

Dalam Bahasa Inggris:

recursion = n. See recursion.

Contoh PHP lain:

<?
require(__FILE__);

Bagaimana dengan yang berikut di BASIC:

10 GOSUB 10

(Saya tidak punya penerjemah DASAR yang saya takutkan jadi itu dugaan).

Saya menyukai tumpukan jawaban Cody, jadi inilah kontribusi saya yang serupa, di C ++:

template <int i>
class Overflow {
    typedef typename Overflow<i + 1>::type type;
};

typedef Overflow<0>::type Kaboom;

Bukan entri kode golf dengan cara apa pun, tapi tetap saja, apa pun untuk tumpukan meta yang melimpah! :-P

Inilah kontribusi C saya, dengan bobot 18 karakter:

void o(){o();o();}

Ini jauh lebih sulit untuk mengoptimalkan panggilan! :-P

Menggunakan file batch Window bernama "s.bat":

call s

Javascript

Untuk memangkas beberapa karakter, dan untuk mengeluarkan diri dari lebih banyak toko perangkat lunak, mari kita ikuti:

eval(i='eval(i)');

Asyik:

main()

$ groovy stack.groovy:

Caught: java.lang.StackOverflowError
    at stack.main(stack.groovy)
    at stack.run(stack.groovy:1)
 ...

Tolong beritahu saya apa singkatan " GNU ".

Person JeffAtwood;
Person JoelSpolsky;
JeffAtwood.TalkTo(JoelSpolsky);

Inilah harapan agar tidak ada rekursi ekor!

C - Ini bukan yang terpendek, tetapi bebas rekursi. Ini juga tidak portabel: crash di Solaris, tetapi beberapa alokasi alokasi () mungkin mengembalikan kesalahan di sini (atau panggil malloc ()). Panggilan ke printf () diperlukan.

#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;
}

perl dalam 12 karakter:

$_=sub{&$_};&$_

bash dalam 10 karakter (ruang dalam fungsi itu penting):

i(){ i;};i

coba dan taruh lebih dari 4 roti di satu burger. stack overflow.

Python :

so=lambda:so();so()

Kalau tidak:

def so():so()
so()

Dan jika Python dioptimalkan panggilan ekor ...:

o=lambda:map(o,o());o()

Saya memilih "jawaban terbaik" setelah posting ini. Tetapi pertama-tama, saya ingin mengakui beberapa kontribusi yang sangat orisinal:

1. yang aku. Masing-masing mengeksplorasi cara baru dan asli yang menyebabkan stack overflow. Gagasan untuk melakukan f (x) ⇒ f (f (x)) adalah ide yang akan saya eksplorasi di entri saya berikutnya, di bawah ini. :-)
2. Cody yang memberi Nemerle compiler stack overflow.
3. Dan (sedikit enggan), salah satu GateKiller tentang melemparkan pengecualian stack overflow. :-P

Seperti halnya saya menyukai hal di atas, tantangannya adalah tentang melakukan golf kode, dan untuk bersikap adil kepada responden, saya harus memberikan "jawaban terbaik" untuk kode terpendek, yaitu entri Befunge; Saya tidak percaya ada orang yang bisa mengalahkan itu (walaupun Konrad sudah mencoba), jadi selamat Patrick!

Melihat sejumlah besar solusi stack-overflow-by-recursion, saya terkejut bahwa tidak ada yang (pada tulisan saat ini) mengangkat kombinator Y (lihat esai Dick Gabriel, The Why of Y , untuk primer). Saya punya solusi rekursif yang menggunakan kombinator Y, serta pendekatan aku (f (x)). :-)

((Y (lambda (f) (lambda (x) (f (f x))))) #f)

Berikut ini satu lagi yang menarik dari Skema:

((lambda (x) (xx)) (lambda (x) (xx)))

Jawa

Versi solusi Java yang sedikit lebih pendek.

class X{public static void main(String[]a){main(a);}}

xor esp, esp
ret

3 byte:

label:
  pusha
  jmp label

Memperbarui

Menurut dokumentasi (lama?) Intel (?) , Ini juga 3 byte:

label:
  call label