Jaki jest najkrótszy kod powodujący przepełnienie stosu? [Zamknięte]

Aby upamiętnić publiczne uruchomienie Stack Overflow, jaki jest najkrótszy kod powodujący przepełnienie stosu? Mile widziane w każdym języku.

ETA: Żeby wyjaśnić to pytanie, ponieważ jestem sporadycznym użytkownikiem Schematu: rekurencja wywołania ogonowego jest tak naprawdę iteracją, a każde rozwiązanie, które można stosunkowo trywialnie przekształcić w rozwiązanie iteracyjne przez przyzwoity kompilator, nie być policzonym. :-P

ETA2: Wybrałem teraz „najlepszą odpowiedź”; zobacz ten post dla uzasadnienia. Dziękujemy wszystkim, którzy wnieśli swój wkład! :-)

Wszystkie te odpowiedzi i brak Befunge? Założę się, że to najkrótsze rozwiązanie ze wszystkich:

1

Nie żartuję. Wypróbuj sam: http://www.quirkster.com/iano/js/befunge.html

EDYCJA: Chyba muszę to wyjaśnić. Operand 1 wypycha 1 na wewnętrzny stos Befunge, a brak czegokolwiek innego umieszcza go w pętli zgodnie z regułami języka.

Korzystając z dostarczonego interpretera, w końcu - i mam na myśli ostatecznie - trafisz w punkt, w którym tablica JavaScript reprezentująca stos Befunge stanie się zbyt duża, aby przeglądarka mogła ją ponownie przydzielić. Gdybyś miał prosty interpreter Befunge z mniejszym i ograniczonym stosem - tak jak w przypadku większości poniższych języków - ten program szybciej spowodowałby bardziej zauważalne przepełnienie.

Przeczytaj ten wiersz i zrób to, co w nim jest, dwa razy .

Możesz również spróbować tego w C # .net

throw new StackOverflowException();

Nemerle :

To powoduje awarię kompilatora z wyjątkiem StackOverflowException:

def o(){[o()]}

Mój obecny najlepszy (w zestawie x86) to:

push eax
jmp short $-1

co daje 3 bajty kodu wynikowego ( 50 EB FD). W przypadku kodu 16-bitowego jest to również możliwe:

call $

co również daje 3 bajty ( E8 FD FF).

PIC18

Odpowiedź PIC18 udzielona przez TK skutkuje następującymi instrukcjami (binarnymi):

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

Jednak samo CALL wykona przepełnienie stosu:

CALL $
1110 1100 0000 0000
0000 0000 0000 0000

Mniejszy, szybszy PIC18

Ale RCALL (wywołanie względne) jest jeszcze mniejsze (nie pamięć globalna, więc nie ma potrzeby dodatkowych 2 bajtów):

RCALL $
1101 1000 0000 0000

Zatem najmniejsza w PIC18 to pojedyncza instrukcja, 16 bitów (dwa bajty). Zajmie to 2 cykle instrukcji na pętlę. Przy 4 cyklach zegara na cykl instrukcji masz 8 cykli zegara. PIC18 ma 31-poziomowy stos, więc po 32. pętli przepełni stos w 256 cyklach zegara. Przy 64 MHz przepełnienie stosu zajmie 4 mikro sekundy i 2 bajty .

PIC16F5x (jeszcze mniejszy i szybszy)

Jednak seria PIC16F5x wykorzystuje instrukcje 12-bitowe:

CALL $
1001 0000 0000

Ponownie, dwa cykle instrukcji na pętlę, 4 zegary na instrukcję, czyli 8 cykli zegara na pętlę.

Jednak PIC16F5x ma stos dwupoziomowy, więc w trzeciej pętli przepełniłby się w 24 instrukcjach. Przy 20 MHz przepełnienie zajmie 1,2 mikrosekundy i 1,5 bajta .

Intel 4004

Intel 4004 posiada 8-bitowe instrukcje wywołanie podprogramu:

CALL $
0101 0000

Dla ciekawskich, co odpowiada ascii „P”. Z 3-poziomowym stosem, który zajmuje 24 cykle zegara, łącznie 32,4 mikrosekundy i jeden bajt . (Chyba że podkręcisz swój 4004 - daj spokój, wiesz, że chcesz.)

Co jest tak małe jak odpowiedź befunge, ale znacznie, dużo szybsze niż kod befunge działający w obecnych interpreterach.

DO#:

public int Foo { get { return Foo; } }

Hoot overflow!

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

Każde zadanie wymaga odpowiedniego narzędzia. Poznaj język SO Overflow , zoptymalizowany do tworzenia przepełnień stosu:

so

TeX:

\def~{~.}~

Prowadzi do:

! Przekroczono pojemność TeX-a, przepraszam [rozmiar stosu wejściowego = 5000].
~ -> ~
    .
~ -> ~
    .
~ -> ~
    .
~ -> ~
    .
~ -> ~
    .
~ -> ~
    .
...
<*> \ def ~ {~.} ~

Lateks:

\end\end

Prowadzi do:

! Przekroczono pojemność TeX-a, przepraszam [rozmiar stosu wejściowego = 5000].
\ end # 1 -> \ csname end # 1
                      \ endcsname \ @checkend {# 1} \ expandafter \ endgroup \ if @ e ...
<*> \ end \ end

Asembler Z-80 - w lokalizacji pamięci 0x0000:

rst 00

jeden bajt - 0xC7 - niekończąca się pętla wpychania bieżącego komputera na stos i przeskakiwania do adresu 0x0000.

Po angielsku:

recursion = n. See recursion.

Kolejny przykład PHP:

<?
require(__FILE__);

A co z następującymi w języku BASIC:

10 GOSUB 10

(Obawiam się, że nie mam tłumacza języka BASIC, więc to przypuszczenie).

Uwielbiałem mnóstwo odpowiedzi Cody'ego, więc oto mój podobny wkład w C ++:

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

typedef Overflow<0>::type Kaboom;

W żadnym wypadku nie jest to kod do gry w golfa, ale nadal nic dla przepełnienia meta stosu! :-P

Oto mój wkład w C, ważący 18 znaków:

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

Jest to o wiele trudniejsze do optymalizacji połączeń końcowych! :-P

Korzystanie z pliku wsadowego okna o nazwie „s.bat”:

call s

Javascript

Aby przyciąć kilka dodatkowych znaków i wyrzucić nas z większej liczby sklepów z oprogramowaniem, przejdźmy do:

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

Groovy:

main()

$ groovy stack.groovy:

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

Powiedz mi proszę, co oznacza skrót „ GNU ”.

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

Mamy nadzieję na brak rekurencji ogona!

C - To nie jest najkrótsze, ale wolne od rekurencji. Nie jest również przenośny: ulega awarii w systemie Solaris, ale niektóre implementacje przydzielania () mogą zwracać tutaj błąd (lub wywoływać malloc ()). Wywołanie printf () jest konieczne.

#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 w 12 znakach:

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

bash 10 znakami (ważna jest spacja w funkcji):

i(){ i;};i

spróbuj umieścić więcej niż 4 paszteciki na jednym burgerze. przepełnienie stosu.

Python :

so=lambda:so();so()

Alternatywnie:

def so():so()
so()

A jeśli zoptymalizowane pod Pythonem wywołania tail ...:

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

Po tym poście wybieram „najlepszą odpowiedź”. Ale najpierw chciałbym podziękować za bardzo oryginalny wkład:

1. aku. Każdy z nich bada nowy i oryginalny sposób powodowania przepełnienia stosu. Pomysł zrobienia f (x) ⇒ f (f (x)) to ten, który omówię w następnym wpisie poniżej. :-)
2. Cody'ego, który dał kompilatorowi Nemerle przepełnienie stosu.
3. I (trochę niechętnie), GateKiller o rzuceniu wyjątku przepełnienia stosu. :-P

Mimo że uwielbiam powyższe, wyzwanie polega na robieniu kodu golfa i aby być uczciwym wobec respondentów, muszę przyznać „najlepszą odpowiedź” najkrótszemu kodowi, czyli wpisowi Befunge; Nie wierzę, że ktokolwiek będzie w stanie to pokonać (chociaż Konrad z pewnością próbował), więc gratuluję Patrickowi!

Widząc dużą liczbę rozwiązań polegających na przepełnieniu stosu przez rekursję, jestem zaskoczony, że nikt (w chwili obecnej) nie przywołał kombinatora Y (zajrzyj do eseju Dicka Gabriela The Why of Y ). Mam rozwiązanie rekurencyjne, które wykorzystuje kombinator Y, a także podejście aku f (f (x)). :-)

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

Oto kolejny interesujący ze Scheme:

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

Jawa

Nieco krótsza wersja rozwiązania Java.

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

xor esp, esp
ret

3 bajty:

label:
  pusha
  jmp label

Aktualizacja

Według (starej?) Dokumentacji Intela (?) Jest to również 3 bajty:

label:
  call label