Was ist der kürzeste Code, der einen Stapelüberlauf verursacht? [geschlossen]

160

Was ist der kürzeste Code, um einen Stapelüberlauf zu verursachen, um an den öffentlichen Start von Stack Overflow zu erinnern? Jede Sprache willkommen.

ETA: Um bei dieser Frage klar zu sein, da ich gelegentlich Scheme-Benutzer bin: Tail-Call "Rekursion" ist wirklich eine Iteration, und jede Lösung, die von einem anständigen Compiler relativ trivial in eine iterative Lösung konvertiert werden kann, wird dies nicht tun gezählt werden. :-P

ETA2: Ich habe jetzt eine „beste Antwort“ ausgewählt. Weitere Informationen finden Sie in diesem Beitrag . Vielen Dank an alle, die dazu beigetragen haben! :-)

Chris Jester-Young
quelle

Antworten:

212

All diese Antworten und kein Befunge? Ich würde eine ganze Menge wetten, es ist die kürzeste Lösung von allen:

1

Kein Scherz. Probieren Sie es aus: http://www.quirkster.com/iano/js/befunge.html

EDIT: Ich denke, ich muss das erklären. Der 1-Operand schiebt eine 1 auf Befunges internen Stapel, und das Fehlen von irgendetwas anderem bringt ihn nach den Regeln der Sprache in eine Schleife.

Mit dem bereitgestellten Interpreter werden Sie schließlich - und ich meine schließlich - einen Punkt erreichen, an dem das Javascript-Array, das den Befunge-Stapel darstellt, zu groß wird, als dass der Browser es neu zuordnen könnte. Wenn Sie einen einfachen Befunge-Interpreter mit einem kleineren und begrenzten Stapel hätten - wie dies bei den meisten der folgenden Sprachen der Fall ist - würde dieses Programm schneller einen spürbareren Überlauf verursachen.

Patrick
quelle
8
Hmm… aber ist das wirklich ein Stapelüberlauf oder nur eine Endlosschleife? Mein JS-Dolmetscher ist nicht übergelaufen, er ist sozusagen nur in den Urlaub gefahren.
Konrad Rudolph
3
Es ist keine Endlosschleife, da der Befehl 1 eine 1 auf den Stapel schiebt. Möglicherweise wird Ihrem Befunge-Interpreter der Stapelspeicherplatz ausgehen, aber es wird eine Weile dauern. :)
Patrick
18
Sie haben meinen Browser abgestürzt und meinen CPU-Lüfter auf Overdrive geschickt.
Sam152
2
Tolle! Mein Computer oder Browser (Opera) stürzte nicht ab, aber beide Prozessoren liefen zu 100% und die Lüftergeschwindigkeit lag bei 3.
Secko
28
Hier ist ein Befunge-Programm, das schneller überläuft: " Es lädt alle zwei Male 79 Kopien der Nummer 32, anstatt 2 Kopien der Nummer 1.
KirarinSnow
291

Lesen Sie diese Zeile und machen Sie zweimal, was darin steht .

jrudolph
quelle
174

Sie können dies auch in C # .net versuchen

throw new StackOverflowException();
GateKiller
quelle
29
Der Pedant in mir sagt, dass dadurch kein Stapel überläuft, sondern nur eine Ausnahme ausgelöst wird. Das heißt, der schnellste Weg, von Haien angegriffen zu werden, besteht darin, im Meer zu stehen und "Hai-Angriff!" Zu schreien. Trotzdem werde ich darüber abstimmen. :)
Bernard
Nun - gibt es einen Unterschied? Kannst du es fangen und weitermachen? Oder ist es genau wie ein Stackoverflow in c #? In diesem Fall handelt es sich irgendwie um einen Stapelüberlauf, da er nicht von einem zu unterscheiden ist ... Allerdings - aus allen oben genannten Gründen positiv bewerten
Mo.
18
Wenn ein Stapel im Wald überläuft und niemand zu fangen ist, wirft er dann eine Ausnahme?
Ich würde nicht das "kürzeste" sagen, da es nicht so ist, dass man so einen Einzeiler kompilieren kann. Es tut schnell einen Stapelüberlauf werfen , obwohl ich denke.
Dominic K
159

Nemerle :

Dies stürzt den Compiler mit einer StackOverflowException ab:

def o(){[o()]}
Cody Brocious
quelle
119

Mein derzeit bestes Ergebnis (in x86-Assembly) ist:

push eax
jmp short $-1

Dies führt zu 3 Bytes Objektcode ( 50 EB FD). Für 16-Bit-Code ist dies auch möglich:

call $

was auch zu 3 Bytes ( E8 FD FF) führt.

Chris Jester-Young
quelle
6
Das Zählen der Bytes nach dem "Kompilieren" (oder Zusammensetzen) ist kein Code-Golf.
Louis Brandy
37
Die Frage lautet: "[...] Was ist der kürzeste Code, der einen Stapelüberlauf verursacht?" Es gibt keinen Quellcode, interpretierten Code, Maschinencode, Objektcode oder verwalteten Code an ...
Anders Sandvig
Für die Aufzeichnung können Sie mit Shins Golfserver einen zu bewertenden Objektcode senden, obwohl auch alle Ihre ELF-Header gezählt werden. Hmm ....
Chris Jester-Young
Einige Beispiele hierfür finden Sie beispielsweise unter golf.shinh.org/p.rb?FizzBuzz#x86 . (Ich weiß ehrlich gesagt nicht, wie Leute 99-Byte-ELF-Binärdateien erstellen können.) :-P
Chris Jester-Young
7
@lbrandy: Es gibt genug Leute, die Objektcode direkt schreiben können. Ich kann es nicht für x86 machen, aber für einen bestimmten Mikroprozessor kann ich. Ich würde solchen Code zählen.
Joey
113

PIC18

Die von TK gegebene PIC18-Antwort führt zu den folgenden Anweisungen (binär):

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

CALL allein führt jedoch einen Stapelüberlauf durch:

CALL $
1110 1100 0000 0000
0000 0000 0000 0000

Kleinerer, schnellerer PIC18

RCALL (relativer Aufruf) ist jedoch noch kleiner (kein globaler Speicher, daher sind keine zusätzlichen 2 Bytes erforderlich):

RCALL $
1101 1000 0000 0000

Der kleinste auf dem PIC18 ist also ein einzelner Befehl, 16 Bit (zwei Bytes). Dies würde 2 Befehlszyklen pro Schleife dauern. Bei 4 Taktzyklen pro Befehlszyklus haben Sie 8 Taktzyklen. Der PIC18 verfügt über einen Stapel mit 31 Ebenen, sodass er nach der 32. Schleife den Stapel in 256 Taktzyklen überläuft. Bei 64 MHz würden Sie den Stapel in 4 Mikrosekunden und 2 Bytes überlaufen lassen .

PIC16F5x (noch kleiner und schneller)

Die PIC16F5x-Serie verwendet jedoch 12-Bit-Anweisungen:

CALL $
1001 0000 0000

Wieder zwei Befehlszyklen pro Schleife, 4 Takte pro Befehl, also 8 Taktzyklen pro Schleife.

Der PIC16F5x verfügt jedoch über einen zweistufigen Stapel, sodass er in der dritten Schleife in 24 Anweisungen überlaufen würde. Bei 20 MHz würde es in 1,2 Mikrosekunden und 1,5 Bytes überlaufen .

Intel 4004

Der Intel 4004 verfügt über eine 8-Bit-Aufruf-Subroutinenanweisung:

CALL $
0101 0000

Für Neugierige, die einem ASCII 'P' entsprechen. Mit einem 3-Level-Stack, der 24 Taktzyklen für insgesamt 32,4 Mikrosekunden und ein Byte benötigt . (Wenn Sie Ihren 4004 nicht übertakten - kommen Sie, Sie wissen, dass Sie wollen.)

Das ist so klein wie die befunge-Antwort, aber viel, viel schneller als der befunge-Code, der in aktuellen Interpreten ausgeführt wird.

Adam Davis
quelle
77

C #:

public int Foo { get { return Foo; } }
aku
quelle
57

Schrei Überlauf!

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

Jede Aufgabe braucht das richtige Werkzeug. Lernen Sie die SO Overflow- Sprache kennen, die für Stapelüberläufe optimiert wurde:

so
Konrad Rudolph
quelle
7
Wenn Sie eine spezielle Sprache zum Generieren von Überläufen mit einem Minimum an Code erstellen, möchten Sie natürlich (1), dass eine leere Eingabe einen Stapelüberlaufcode erzeugt (wahrscheinlich eine kleine Binärdatei, die den aus dem Assemblycode-Eintrag generierten nativen Code ausführt) oder (2) ) Alle Eingabeprogramme erzeugen diese Binärdatei.
Jared Updike
Hmmm, nicht Turing komplett. Ich weiß noch nicht, ob man es eine Sprache nennen könnte ...
Adam Davis
42

TeX:

\def~{~.}~

Ergebnisse in:

! TeX-Kapazität überschritten, sorry [Eingabestapelgröße = 5000].
~ -> ~
    .
~ -> ~
    .
~ -> ~
    .
~ -> ~
    .
~ -> ~
    .
~ -> ~
    .
...
<*> \ def ~ {~.} ~

Latex:

\end\end

Ergebnisse in:

! TeX-Kapazität überschritten, sorry [Eingabestapelgröße = 5000].
\ end # 1 -> \ csname end # 1
                      \ endcsname \ @checkend {# 1} \ expandafter \ endgroup \ if @ e ...
<*> \ end \ end
Pi.
quelle
Da ~es aktiv ist, kann es anstelle von verwendet werden \a. Und ich habe den LaTeX-Code ganz zufällig entdeckt. :)
Josh Lee
35

Z-80 Assembler - am Speicherort 0x0000:

rst 00

Ein Byte - 0xC7 - Endlosschleife, bei der der aktuelle PC auf den Stapel geschoben und zur Adresse 0x0000 gesprungen wird.

Dennis Munsie
quelle
2
Ich erinnere mich, dass ein leerer Eprom alle 0xffs sind, die die ersten 7 (= 0x0038) Anweisungen sind. Dies wäre nützlich, um Ihre Hardware mit einem Oszilloskop zu debuggen. Der Adressbus würde den 64-KB-Raum durchlaufen, wenn der Stapel wiederholt überläuft, durchsetzt mit Lesevorgängen von 0xff von 0x0038.
Bill Forster
29

Auf Englisch:

recursion = n. See recursion.
Vinko Vrsalovic
quelle
32
Jedes vernünftige menschliche Gehirn wird auch die Interpretation dieses Gehirns optimieren und nicht in die Luft jagen. :-P
Chris Jester-Young
73
Chris, vernünftige menschliche Gehirne werden heutzutage zu einer Seltenheit.
Jason Z
20
Seltenheit ... du meinst, sie existieren?
Adam Lerman
11
Google-Rekursion
CodeFusionMobile
29

Ein weiteres PHP-Beispiel:

<?
require(__FILE__);
disq
quelle
4
Sie könnten sogar kurzgeschlossen werden, indem Sie die Klammer überspringen (aber anstelle der ersten Leerzeichen einfügen).
Alex
26

Wie wäre es mit folgendem in BASIC:

10 GOSUB 10

(Ich fürchte, ich habe keinen BASIC-Dolmetscher, das ist also eine Vermutung).

Stusmith
quelle
3
Kein wirklicher Stapelüberlauf, da BASIC eine stapellose Sprache ist. Sogar VB (das einen Stapel hat) würde nicht überlaufen, da es nur springt und keinen Stapelrahmen erstellt.
Daniel Spiewak
21
Das ist ein GOSUB, kein GOTO. Da es dort ist RETURN, wo es aufgerufen wurde, wird sicherlich ein Stapel verwendet?
Tom
3
Ja ich stimme zu. Ich hatte in den 80ern viele Stapelüberläufe in BASIC.
Nickd
6
Ich habe dieses in Yabasic ausgeführt, nur zum Spaß, und es hat fast meinen Computer heruntergefahren. Gott sei Dank scheiterte Malloc schließlich, aber ich blätterte wie kein Morgen.
Adam Rosenfield
2
Ups sorry Adam ... erinnert mich an eine Zeit an der Uni, als jemand versehentlich ein Programm geschrieben hat, das rekursiv gespalten wurde: einen ganzen Silicon Graphics-Server heruntergefahren hat.
Stusmith
26

Ich habe Codys Antworthaufen geliebt, daher hier mein ähnlicher Beitrag in C ++:

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

typedef Overflow<0>::type Kaboom;

Kein Code-Golf-Eintrag, aber dennoch alles für einen Meta-Stack-Überlauf! :-P

Chris Jester-Young
quelle
21

Hier ist mein C-Beitrag mit 18 Zeichen:

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

Dies ist viel schwieriger zu optimieren! :-P

Chris Jester-Young
quelle
4
Kompiliert nicht für mich: "undefinierter Verweis auf" main "": P.
Andrew Johnson
1
Ich verstehe nicht: warum o () 2x aufrufen?
Dinah
3
@ Dinah: Eine der Einschränkungen meines Wettbewerbs war, dass die Tail-Call-Optimierung nicht als Rekursion gilt. Es ist nur eine iterative Schleife. Wenn Sie o () nur einmal geschrieben haben, kann dies (von einem kompetenten Compiler) in etwa so optimiert werden: "o: jmp o". Bei 2 Aufrufen von o muss der Compiler Folgendes verwenden: "o: call o; jmp o". Es ist die rekursive "Aufruf" -Anweisung, die den Stapelüberlauf verursacht.
Chris Jester-Young
Sie haben Recht - ich habe diesen Teil nicht beachtet. Danke für die Klarstellung.
Dinah
19

Verwenden der Batchdatei eines Fensters mit dem Namen "s.bat":

call s
Jude Allred
quelle
17

Javascript

Um ein paar weitere Zeichen zu kürzen und uns aus weiteren Software-Shops zu werfen, gehen wir wie folgt vor:

eval(i='eval(i)');
Travis Wilson
quelle
15

Groovy:

main()

$ groovy stack.groovy:

Caught: java.lang.StackOverflowError
    at stack.main(stack.groovy)
    at stack.run(stack.groovy:1)
 ...
Chris Broadfoot
quelle
Abgestimmt, weil es ziemlich interessant ist. Zeigt jedoch eine ziemlich nervige Schwäche im Groovy-Compiler (solche Tail-Aufrufe können zur Kompilierungszeit eingefügt werden).
Daniel Spiewak
Bist du sicher, dass es ein Tail Call ist? Wenn Sie vom Ende des Programms fallen, wird die Interpreter-Shell nicht aufgerufen.
Aaron
15

Bitte sagen Sie mir, wofür das Akronym " GNU " steht.

Greg
quelle
4
Oder Eine (Eine ist nicht Emacs) oder Zwei (Zwei war ursprünglich Eine). :-P
Chris Jester-Young
Oder YAML oder WINE oder XNA oder irgendetwas anderes
TM.
Drei (Drei ist wirklich Emacs Incognito), Fier (Fier ist Emacs neu erfunden) - ok, also habe ich mir das nur ausgedacht :-)
Ferruccio
14
Person JeffAtwood;
Person JoelSpolsky;
JeffAtwood.TalkTo(JoelSpolsky);

Wir hoffen auf keine Schwanzrekursion!

Ryan Fox
quelle
1
Hehe, lustig. Im Zusammenhang mit Gesprächen ist auch die Idee des "Echokammer-Effekts" sehr interessant. Nicht ganz stapelüberlaufinduzierend, aber dennoch.
Chris Jester-Young
8
Wäre dies nicht eine Nullzeigerausnahme? Entschuldigung, ich weiß, dass es ein Witz ist.
Jamesh
12

C - Es ist nicht das kürzeste, aber es ist rekursionsfrei. Es ist auch nicht portabel: Es stürzt unter Solaris ab, aber einige alloca () - Implementierungen geben hier möglicherweise einen Fehler zurück (oder rufen malloc () auf). Der Aufruf von printf () ist notwendig.

#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;
}
bk1e
quelle
Sie können auch einfach "ulimit -s16" ausführen, um den Stapel wirklich klein zu machen. Jeder kleiner als ungefähr 16 und das Programm läuft nicht einmal (anscheinend nicht genügend Argumente!).
Andrew Johnson
11

Perl in 12 Zeichen:

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

Bash in 10 Zeichen (das Leerzeichen in der Funktion ist wichtig):

i(){ i;};i
askol
quelle
11

Versuchen Sie, mehr als 4 Pastetchen auf einen einzelnen Burger zu legen. Paketüberfluss.

user8456
quelle
1
Hier in Neuseeland haben wir Burger Wisconsin, wo große, aber dünne Pastetchen verwendet werden. Ich bin sicher, Sie können mehr als 4 davon stapeln, wenn Sie möchten; Es wird allerdings ein sehr teurer Burger!
Chris Jester-Young
Mmm ... In-n-Out. en.wikipedia.org/wiki/In-n-out#Menu
cbednarski
11

Python :

so=lambda:so();so()

Alternative:

def so():so()
so()

Und wenn Python Tail Calls optimiert hat ...:

o=lambda:map(o,o());o()
Cody Brocious
quelle
Glücklicherweise führt Python keine Tail-Call-Optimierung durch. Andernfalls würde es wie zwei andere Antworten bisher disqualifiziert. :-P
Chris Jester-Young
10

Ich wähle nach diesem Beitrag die „beste Antwort“ aus. Aber zuerst möchte ich einige sehr originelle Beiträge anerkennen:

  1. Akus. Jeder untersucht eine neue und originelle Methode, um einen Stapelüberlauf zu verursachen. Die Idee, f (x) ⇒ f (f (x)) zu machen, werde ich in meinem nächsten Eintrag weiter unten untersuchen. :-)
  2. Cody hat dem Nemerle- Compiler einen Stapelüberlauf beschert .
  3. Und (ein bisschen widerwillig) bei GateKiller geht es darum, eine Stapelüberlauf-Ausnahme auszulösen. :-P

So sehr ich das Obige liebe, besteht die Herausforderung darin, Code-Golf zu spielen. Um fair gegenüber den Befragten zu sein, muss ich dem kürzesten Code, dem Befunge-Eintrag, die „beste Antwort“ geben. Ich glaube nicht, dass irgendjemand das schlagen kann (obwohl Konrad es sicherlich versucht hat), also herzlichen Glückwunsch Patrick!

Angesichts der großen Anzahl von Lösungen für Stapelüberlauf durch Rekursion bin ich überrascht, dass (zum Zeitpunkt des Schreibens) niemand den Y-Kombinator aufgerufen hat (siehe Dick Gabriels Aufsatz The Why of Y für eine Grundierung). Ich habe eine rekursive Lösung, die den Y-Kombinator sowie den f (f (x)) -Ansatz von aku verwendet. :-)

((Y (lambda (f) (lambda (x) (f (f x))))) #f)
Chris Jester-Young
quelle
8

Hier ist ein weiteres interessantes aus Schema:

((Lambda (x) (xx)) (Lambda (x) (xx)))
Adam Rosenfield
quelle
Sehr schön, und es gibt auch eine gute Symmetrie. Auch die Verwendung der Formulierung (Lambda (x) (xx)): ((Y (Lambda (x) (xx))) #f) macht auch viel Spaß!
Chris Jester-Young
Oh, das ist hübsch. Es funktioniert auch in Ruby, obwohl es nicht so hübsch ist wie in Schema: Lambda {| x | x.call x} .call lambda {| x | x.call x}
Wayne Conrad
7

Java

Etwas kürzere Version der Java-Lösung.

class X{public static void main(String[]a){main(a);}}
Mischa
quelle
5
Oder (gleiche Anzahl von Zeichen): public static void main (String ... a) {main ();}
Michael Myers
Oder für die TDD-Leute (gleiche Anzahl von Zeichen): public class ${@org.junit.Test public void $ () {$ ();}}
mhaller
Immer noch nicht die kürzeste (siehe meine Antwort)
Draemon
6
xor esp, esp
ret
a1k0n
quelle
Das ist nicht wirklich ein Stapelüberlauf, aber es ist auch schön: D
Botismarius
5

3 Bytes:

label:
  pusha
  jmp label

Aktualisieren

Laut der (alten?) Intel (?) Dokumentation sind dies ebenfalls 3 Bytes:

label:
  call label

Anders Sandvig
quelle
Im 32-Bit-Modus sind es 3 Bytes. Schöne Antwort, wenn man bedenkt, dass sie den Stapel viel schneller ausfüllt als meine Antwort!
Chris Jester-Young
Laut penguin.cz/~literakl/intel/j.html#JMP besteht jmp aus 3 Bytes mit einer relativen Zieladresse von 8, 16 oder 32 Bit. Die Pusha ist auch 1 Bytes, was insgesamt 4
Anders Sandvig
Es gibt drei Arten von JMP: kurz, nah und fern. Short jmp (unter Verwendung von 0xEB-Opcode) besteht aus zwei Bytes. Das Ziel muss zwischen -128 und 127 Byte vom nächsten Befehl entfernt sein. :-)
Chris Jester-Young
Vielleicht hast du Recht. Ich bin zu faul, um meinen Assembler auszugraben und zu überprüfen ...;)
Anders Sandvig