¿Cuál es el código más corto para causar un desbordamiento de pila? [cerrado]

160

Para conmemorar el lanzamiento público de Stack Overflow, ¿cuál es el código más corto para causar un desbordamiento de pila? Cualquier idioma de bienvenida.

ETA: Solo para ser claro en esta pregunta, ya que soy un usuario ocasional de Scheme: la "recursión" de cola es realmente una iteración, y cualquier solución que pueda convertirse en una solución iterativa relativamente trivialmente por un compilador decente no lo hará. ser contados. :-PAGS

ETA2: ahora he seleccionado una "mejor respuesta"; ver esta publicación para justificación. ¡Gracias a todos los que contribuyeron! :-)

Chris Jester-Young
fuente

Respuestas:

212

Todas estas respuestas y no Befunge? Apostaría una buena cantidad, es la solución más corta de todas:

1

No bromeo. Pruébelo usted mismo: http://www.quirkster.com/iano/js/befunge.html

EDITAR: Supongo que necesito explicar esto. El 1 operando empuja un 1 en la pila interna de Befunge y la falta de otra cosa lo coloca en un bucle bajo las reglas del lenguaje.

Usando el intérprete provisto, eventualmente, y quiero decir eventualmente, llegará a un punto donde la matriz de Javascript que representa la pila Befunge se vuelve demasiado grande para que el navegador la reasigne. Si tuviera un intérprete Befunge simple con una pila más pequeña y limitada, como es el caso con la mayoría de los idiomas a continuación, este programa causaría un desbordamiento más notable más rápido.

Patrick
fuente
8
Hmm ... pero, ¿es realmente un desbordamiento de pila o simplemente un bucle infinito? Mi intérprete JS no se desbordó, simplemente se fue de vacaciones, por así decirlo.
Konrad Rudolph
3
No es un ciclo infinito, porque la instrucción 1 empuja un 1 a la pila. Eventualmente, su intérprete Befunge se quedará sin espacio de pila, pero tomará un tiempo. :)
Patrick
18
Usted ... bloqueó mi navegador y ... envió mi ventilador de CPU a toda marcha.
Sam152
2
¡Asombroso! Mi computadora o navegador (Opera) no se bloqueó pero ambos procesadores estaban funcionando al 100% y la velocidad del ventilador era de 3.
Secko
28
Aquí hay un programa Befunge que se desborda más rápido: " carga 79 copias del número 32 cada dos veces que se envuelve, en lugar de 2 copias del número 1.
KirarinSnow
291

Lea esta línea y haga lo que dice dos veces .

revs jrudolph
fuente
174

También puedes probar esto en C # .net

throw new StackOverflowException();
GateKiller
fuente
29
El pedante en mí dice que no hace que ninguna pila se desborde, solo lanza una excepción. Es como decir que la forma más rápida de ser atacado por tiburones es pararse en el mar y gritar "¡Ataque de tiburón!". A pesar de esto, lo votaré. :)
Bernard
Bueno, ¿hay alguna diferencia? ¿Puedes atraparlo y continuar? ¿O es exactamente como un stackoverflow en C #? En ese caso, de alguna manera es un desbordamiento de pila, ya que no se puede distinguir de uno ... Sin embargo, votar por todas las razones anteriores
Mo.
18
Si una pila se desborda en el bosque sin nadie a quien atrapar, ¿arroja una excepción?
No diría el 'más corto', ya que no es como si pudieras compilar una frase como esa. Sin embargo, supongo que arroja un desbordamiento de pila rápidamente.
Dominic K
159

Nemerle :

Esto bloquea el compilador con una excepción StackOverflowException:

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

Mi mejor actual (en ensamblaje x86) es:

push eax
jmp short $-1

que da como resultado 3 bytes de código objeto ( 50 EB FD). Para el código de 16 bits, esto también es posible:

call $

que también da como resultado 3 bytes ( E8 FD FF).

Chris Jester-Young
fuente
66
Contar los bytes después de "compilar" (o ensamblar) no es code-golf.
Louis Brandy
37
La pregunta dice "¿[...] cuál es el código más corto para causar un desbordamiento de pila? No especifica el código fuente, el código interpretado, el código de máquina, el código de objeto o el código administrado ...
Anders Sandvig
Para el registro, el servidor de golf de Shin le permite enviar código objeto para ser juzgado, aunque también contará todos sus encabezados ELF. Hmm ....
Chris Jester-Young
Consulte, por ejemplo, golf.shinh.org/p.rb?FizzBuzz#x86 para ver algunos ejemplos de esto. (Sinceramente, no sé cómo la gente puede hacer binarios ELF de 99 bytes). :-P
Chris Jester-Young
77
@lbrandy: Hay suficientes personas que pueden escribir código objeto directamente. No puedo hacerlo para x86 pero sí para un cierto microprocesador. Contaría ese código.
Joey
113

PIC18

La respuesta PIC18 dada por TK da como resultado las siguientes instrucciones (binarias):

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

Sin embargo, CALL solo realizará un desbordamiento de pila:

CALL $
1110 1100 0000 0000
0000 0000 0000 0000

PIC18 más pequeño y más rápido

Pero RCALL (llamada relativa) es aún más pequeña (no es memoria global, por lo que no es necesario los 2 bytes adicionales):

RCALL $
1101 1000 0000 0000

Entonces, el más pequeño en el PIC18 es una sola instrucción, 16 bits (dos bytes). Esto tomaría 2 ciclos de instrucción por ciclo. Con 4 ciclos de reloj por ciclo de instrucción, tiene 8 ciclos de reloj. El PIC18 tiene una pila de 31 niveles, por lo que después del ciclo 32 desbordará la pila, en 256 ciclos de reloj. A 64MHz, desbordaría la pila en 4 microsegundos y 2 bytes .

PIC16F5x (incluso más pequeño y más rápido)

Sin embargo, la serie PIC16F5x utiliza instrucciones de 12 bits:

CALL $
1001 0000 0000

Nuevamente, dos ciclos de instrucción por ciclo, 4 relojes por instrucción, entonces 8 ciclos de reloj por ciclo.

Sin embargo, el PIC16F5x tiene una pila de dos niveles, por lo que en el tercer bucle se desbordaría, en 24 instrucciones. A 20MHz, se desbordaría en 1.2 microsegundos y 1.5 bytes .

Intel 4004

El Intel 4004 tiene una instrucción de subrutina de llamada de 8 bits:

CALL $
0101 0000

Para los curiosos que corresponde a una ascii 'P'. Con una pila de 3 niveles que toma 24 ciclos de reloj para un total de 32.4 microsegundos y un byte . (A menos que overclockees tu 4004, vamos, sabes que quieres).

Que es tan pequeño como la respuesta inicial, pero mucho, mucho más rápido que el código inicial que se ejecuta en los intérpretes actuales.

Adam Davis
fuente
77

C#:

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

¡Desbordamiento de pitido!

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

Cada tarea necesita la herramienta adecuada. Conozca el lenguaje SO Overflow , optimizado para producir desbordamientos de pila:

so
Konrad Rudolph
fuente
77
Si está creando un lenguaje especializado para generar desbordamientos con un mínimo de código, obviamente querría (1) la entrada vacía produce código desbordado de pila (probablemente un pequeño binario que ejecuta el código nativo generado a partir de la entrada del código de ensamblaje) o (2 ) todos los programas de entrada producen dicho binario.
Jared Updike
Hmmm, no Turing completo. No sé si podría llamarlo un idioma todavía ...
Adam Davis
42

Texas:

\def~{~.}~

Resultados en:

! Capacidad de TeX excedida, lo siento [tamaño de pila de entrada = 5000].
~ -> ~
    .
~ -> ~
    .
~ -> ~
    .
~ -> ~
    .
~ -> ~
    .
~ -> ~
    .
...
<*> \ def ~ {~.} ~

Látex:

\end\end

Resultados en:

! Capacidad de TeX excedida, lo siento [tamaño de pila de entrada = 5000].
\ end # 1 -> \ csname end # 1
                      \ endcsname \ @checkend {# 1} \ expandafter \ endgroup \ if @ e ...
<*> \ end \ end
Pi.
fuente
Como ~está activo, se puede usar en lugar de \a. Y descubrí el código LaTeX completamente por accidente. :)
Josh Lee
35

Ensamblador Z-80 - en la ubicación de memoria 0x0000:

rst 00

un byte - 0xC7 - ciclo sin fin de empujar la PC actual a la pila y saltar a la dirección 0x0000.

Dennis Munsie
fuente
2
Recuerdo que un eprom en blanco sería todo 0xffs que son las primeras 7 (= llamar a 0x0038) instrucciones. Eso sería útil para depurar su hardware con un osciloscopio. El bus de direcciones recorrería el espacio de 64K a medida que la pila se desbordara repetidamente, intercalada con lecturas de 0xff de 0x0038.
Bill Forster
29

En inglés:

recursion = n. See recursion.
Vinko Vrsalovic
fuente
32
Cualquier cerebro humano sensato también optimizará la interpretación de este, y no explotará. :-P
Chris Jester-Young
73
Chris, los cerebros humanos sensibles se están convirtiendo en una rareza en estos días.
Jason Z
20
rareza ... quieres decir que existen?
Adam Lerman
11
Google recursion
CodeFusionMobile 03 de
29

Otro ejemplo de PHP:

<?
require(__FILE__);
disq
fuente
44
Incluso podría acortarse omitiendo el paréntesis (pero incluyendo el espacio en lugar del primero).
alex
26

¿Qué tal lo siguiente en BASIC:

10 GOSUB 10

(No tengo un intérprete BÁSICO, me temo que eso es una suposición).

stusmith
fuente
3
No es realmente un desbordamiento de pila, ya que BASIC es un lenguaje sin pila. Incluso VB (que tiene una pila) no se desbordaría en esto ya que solo está saltando, no creando un marco de pila.
Daniel Spiewak
21
Eso es un GOSUB, no un GOTO. Ya que RETURNes de donde fue llamado, ¿seguramente está usando una pila?
Tom
3
Si estoy de acuerdo. Tuve muchos desbordamientos de pila en BASIC en los años 80.
nickd
66
Ejecuté este en yabasic solo por el gusto de hacerlo, y casi destruyo mi computadora. Gracias a Dios, Malloc finalmente falló, pero estaba buscando como si no hubiera mañana.
Adam Rosenfield
2
Vaya, lo siento, Adam ... me recuerda un momento en la universidad en el que alguien escribió accidentalmente un programa que bifurcaba recursivamente: derribó todo un servidor de Silicon Graphics.
stusmith
26

Me encantaron los montones de respuestas de Cody, así que aquí está mi contribución similar, en C ++:

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

typedef Overflow<0>::type Kaboom;

¡No es una entrada de código de golf de ninguna manera, pero aún así, cualquier cosa para un desbordamiento de meta stack! :-PAGS

Chris Jester-Young
fuente
21

Aquí está mi contribución en C, con un peso de 18 caracteres:

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

¡Esto es mucho más difícil de optimizar! :-PAGS

Chris Jester-Young
fuente
44
No se compila para mí: "referencia indefinida a 'main'": P
Andrew Johnson
1
No entiendo: ¿por qué llamar a o () 2x?
Dinah
3
@Dinah: Una de las limitaciones de mi concurso fue que la optimización de la cola no cuenta como recursividad; Es solo un bucle iterativo. Si solo escribió o () una vez, eso puede optimizarse en algo así (por un compilador competente): "o: jmp o". Con 2 llamadas de o, el compilador tiene que usar algo como: "o: call o; jmp o". Es la instrucción recursiva de "llamada" que hace que la pila se desborde.
Chris Jester-Young
Tienes razón, no presté atención a esa parte. Gracias por la aclaración.
Dinah
19

Usando un archivo por lotes de Windows llamado "s.bat":

call s
Jude Allred
fuente
17

Javascript

Para recortar algunos personajes más y sacarnos de más tiendas de software, vamos con:

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

Maravilloso:

main()

$ groovy stack.groovy:

Caught: java.lang.StackOverflowError
    at stack.main(stack.groovy)
    at stack.run(stack.groovy:1)
 ...
Chris Broadfoot
fuente
Votado porque es bastante interesante. Sin embargo, expone una debilidad bastante molesta en el compilador Groovy (tales llamadas de cola se pueden incorporar en tiempo de compilación).
Daniel Spiewak
¿estás seguro de que es una llamada de cola? que caerse al final del programa no invoca el intérprete shell?
Aaron
15

Por favor, dime qué significa el acrónimo " GNU ".

Greg
fuente
44
O Eine (Eine no es Emacs), o Zwei (Zwei era Eine inicialmente). :-P
Chris Jester-Young
O YAML, o WINE, o XNA, o cualquiera de los demás en en.wikipedia.org/wiki/Recursive_acronym
TM.
Drei (Drei es realmente Emacs de incógnito), Fier (Fier es Emacs reinventado) - ok, así que acabo de inventarlos :-)
Ferruccio
14
Person JeffAtwood;
Person JoelSpolsky;
JeffAtwood.TalkTo(JoelSpolsky);

¡Esperamos que no haya recursión de la cola!

Ryan Fox
fuente
1
Jeje, gracioso. Relacionado con las conversaciones, la idea del "efecto de cámara de eco" también es bastante interesante. No es suficiente para inducir el desbordamiento de pila, pero aún así
Chris Jester-Young
8
¿No sería esta una excepción de puntero nulo? Lo siento, sé que es una broma.
jamesh
12

C - No es el más corto, pero no tiene recurrencia. Tampoco es portátil: se bloquea en Solaris, pero algunas implementaciones alloca () pueden devolver un error aquí (o llamar a malloc ()). La llamada a printf () es necesaria.

#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
fuente
También puede hacer "ulimit -s16" para configurar la pila realmente pequeña. Si es más pequeño que aproximadamente 16 y el programa ni siquiera se ejecuta (¡argumentos insuficientes aparentemente!).
Andrew Johnson
11

perl en 12 caracteres:

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

bash en 10 caracteres (el espacio en la función es importante):

i(){ i;};i
revs askol
fuente
11

Python :

so=lambda:so();so()

Alternativamente:

def so():so()
so()

Y si Python optimiza las llamadas de cola ...:

o=lambda:map(o,o());o()
Cody Brocious
fuente
Afortunadamente para usted, Python no hace la optimización de llamadas de cola; de lo contrario, sería descalificado como otras dos respuestas hasta ahora. :-P
Chris Jester-Young
10

Estoy seleccionando la "mejor respuesta" después de esta publicación. Pero primero, me gustaría agradecer algunas contribuciones muy originales:

  1. los de aku. Cada uno explora una forma nueva y original de causar el desbordamiento de la pila. La idea de hacer f (x) ⇒ f (f (x)) es una que exploraré en mi próxima entrada, a continuación. :-)
  2. La de Cody que le dio al compilador de Nemerle un desbordamiento de pila.
  3. Y (un poco de mala gana), la de GateKiller acerca de lanzar una excepción de desbordamiento de pila. :-PAGS

Por mucho que me encante lo anterior, el desafío es hacer golf de código, y para ser justos con los encuestados, tengo que otorgar la "mejor respuesta" al código más corto, que es la entrada de Befunge; No creo que nadie pueda vencer eso (aunque Konrad lo ha intentado), ¡así que felicidades a Patrick!

Al ver la gran cantidad de soluciones de desbordamiento de pila por recursión, me sorprende que nadie (al momento de la redacción actual) haya presentado el combinador Y (ver el ensayo de Dick Gabriel, The Why of Y , para una introducción). Tengo una solución recursiva que utiliza el combinador Y, así como el enfoque f (f (x)) de aku. :-)

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

Aquí hay otro interesante de Scheme:

((lambda (x) (xx)) (lambda (x) (xx)))
Adam Rosenfield
fuente
Muy agradable, y también tiene una buena simetría. Además, para usar la formulación (lambda (x) (xx)): ((Y (lambda (x) (xx))) #f) ¡también es muy divertido!
Chris Jester-Young
Oh, eso es lindo También funciona en Ruby, aunque no es tan bonito como en Scheme: lambda {| x | x.call x} .call lambda {| x | x.call x}
Wayne Conrad
7

Java

Versión ligeramente más corta de la solución Java.

class X{public static void main(String[]a){main(a);}}
Misha
fuente
55
O (mismo número de caracteres): public static void main (String ... a) {main ();}
Michael Myers
O para los chicos de TDD (mismo número de caracteres): clase pública ${@org.junit.Test public void $ () {$ ();}}
mhaller
Sin embargo, aún no es el más corto (ver mi respuesta)
Draemon
6
xor esp, esp
ret
a1k0n
fuente
eso no es realmente un desbordamiento de pila, pero de todos modos es agradable: D
botismarius
5

3 bytes:

label:
  pusha
  jmp label

Actualizar

De acuerdo con la documentación (¿antigua?) De Intel (?) , Esto también es de 3 bytes:

label:
  call label

Anders Sandvig
fuente
Son 3 bytes en modo de 32 bits. Buena respuesta, ¡considerando que llenará la pila mucho más rápido que mi respuesta!
Chris Jester-Young
De acuerdo con penguin.cz/~literakl/intel/j.html#JMP , jmp es de 3 bytes con una dirección de destino relativa de 8, 16 o 32 bits. El pusha también tiene 1 bytes, lo que hace un total de 4
Anders Sandvig
Hay tres tipos de jmp, corto, cercano y lejano. El jmp corto (usando el código de operación 0xEB) es de dos bytes. El destino debe estar entre -128 y 127 bytes de la siguiente instrucción. :-)
Chris Jester-Young
Quizás tengas razón. Soy demasiado vago para desenterrar mi ensamblador y verificar ...;)
Anders Sandvig