language-agnostic - tipos - que es underflow
¿Cuál es el código más corto para causar un desbordamiento de pila? (30)
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 lenguaje bienvenido.
ETA: Solo para ser claro con esta pregunta, dado 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 de manera relativamente trivial por un compilador decente no lo hará ser contados. :-PAG
ETA2: ahora he seleccionado una "mejor respuesta"; mira esta publicación para justificación. ¡Gracias a todos los que contribuyeron! :-)
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
Más pequeño, más rápido PIC18
Pero RCALL (llamada relativa) es aún más pequeña (no es la memoria global, por lo que no es necesario contar con los 2 bytes adicionales):
RCALL $
1101 1000 0000 0000
Por lo tanto, el más pequeño en el PIC18 es una única instrucción, 16 bits (dos bytes). Esto tomaría 2 ciclos de instrucciones por ciclo. En 4 ciclos de reloj por ciclo de instrucción, tienes 8 ciclos de reloj. El PIC18 tiene una pila de 31 niveles, por lo que después del bucle 32 se desbordará la pila, en 256 ciclos de reloj. A 64MHz, desbordarías la pila en 4 microsegundos y 2 bytes .
PIC16F5x (incluso más pequeño y más rápido)
Sin embargo, la serie PIC16F5x usa instrucciones de 12 bits:
CALL $
1001 0000 0000
De nuevo, dos ciclos de instrucciones por bucle, 4 relojes por instrucción, de modo que 8 ciclos de reloj por bucle.
Sin embargo, el PIC16F5x tiene una pila de dos niveles, por lo que en el tercer ciclo se desbordará, en 24 instrucciones. A 20MHz, se desbordaría en 1.2 micro segundos 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 un 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 anterior, pero mucho, mucho más rápido que el código de ejecución que se ejecuta en los intérpretes actuales.
¡Desbordamiento de pitidos!
// v___v
let rec f o = f(o);(o)
// [''---'']
// -"---"-
¿Qué tal lo siguiente en BASIC:
10 GOSUB 10
(No tengo un intérprete BÁSICO, me temo, así que eso es una suposición).
3 bytes:
label: pusha jmp label
Actualizar
Según la (¿antigua?) Documentación de Intel (?) , Esto también es de 3 bytes:
label: call label
Aquí está mi contribución C, con un peso de 18 caracteres:
void o(){o();o();}
¡Esto es mucho más difícil de optimizar! :-PAG
Aquí hay otra interesante de Scheme:
((lambda (x) (x x)) (lambda (x) (x x)))
Cada tarea necesita la herramienta correcta. Conozca el lenguaje SO Overflow , optimizado para producir desbordamientos de pila:
so
DO#:
public int Foo { get { return Foo; } }
En inglés:
recursion = n. See recursion.
Ensamblador Z-80 - en la ubicación de la memoria 0x0000:
rst 00
un byte - 0xC7 - bucle sin fin de empujar la PC actual a la pila y saltar a la dirección 0x0000.
Estoy seleccionando la "mejor respuesta" después de esta publicación. Pero primero, me gustaría reconocer algunas contribuciones muy originales:
- los de aku. Cada uno explora una forma nueva y original de provocar el desbordamiento de la pila. La idea de hacer f (x) ⇒ f (f (x)) es una que exploraré en mi siguiente entrada, a continuación. :-)
- Cody es uno que le dio al compilador Nemerle un desbordamiento de pila.
- Y (un poco a regañadientes), GateKiller es uno sobre lanzar una excepción de desbordamiento de pila. :-PAG
Por mucho que me guste lo anterior, el reto es hacer golf por 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 sea capaz de vencer eso (aunque Konrad ciertamente lo ha intentado), ¡así que felicito a Patrick!
Al ver la gran cantidad de soluciones de desbordamiento de pila por recursión, me sorprende que nadie (a partir de la redacción actual) haya sacado el combinador en Y (ver el ensayo de Dick Gabriel, The Why of Y , para una introducción). Tengo una solución recursiva que usa el combinador Y, así como el enfoque f (f (x)) de aku. :-)
((Y (lambda (f) (lambda (x) (f (f x))))) #f)
Groovy:
main()
$ groovy stack.groovy:
Caught: java.lang.Error
at stack.main(stack.groovy)
at stack.run(stack.groovy:1)
...
Java
Versión un poco más corta de la solución Java.
class X{public static void main(String[]a){main(a);}}
Lee esta línea y haz lo que dice dos veces .
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 golf de código de ninguna manera, pero aún así, cualquier cosa para un desbordamiento de meta stack! :-PAG
Mi mejor actual (en ensamblaje x86) es:
push eax
jmp short $-1
que resulta en 3 bytes de código de objeto ( 50 EB FD ). Para el código de 16 bits, esto también es posible:
call $
que también resulta en 3 bytes ( E8 FD FF ).
Otro ejemplo de PHP:
<?
require(__FILE__);
Por favor, dígame qué significa el acrónimo " GNU ".
También puedes probar esto en C # .net
throw new Exception();
Texas:
/def~{~.}~
Resultados en:
! TeX capacity exceeded, sorry [input stack size=5000]. ~->~ . ~->~ . ~->~ . ~->~ . ~->~ . ~->~ . ... <*> /def~{~.}~
Látex:
/end/end
Resultados en:
! TeX capacity exceeded, sorry [input stack size=5000]. /end #1->/csname end#1 /endcsname /@checkend {#1}/expandafter /endgroup /if@e... <*> /end/end
Todas estas respuestas y no Befunge? Apostaría una cantidad justa, 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: Creo que necesito explicar esto. El 1 operando empuja un 1 en la pila interna de Befunge y la falta de cualquier otra cosa lo pone en un bucle bajo las reglas del lenguaje.
Utilizando el intérprete provisto, finalmente (y me refiero a eventualmente) encontrará un punto en el que la matriz de Javascript que representa la pila de Befunge se vuelve demasiado grande para que el navegador la reasigne. Si tuviera un intérprete de 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.
Usando un archivo por lotes de Windows llamado "s.bat":
call s
perl en 12 caracteres:
$_=sub{&$_};&$_
bash en 10 caracteres (el espacio en la función es importante):
i(){ i;};i
prueba y pon más de 4 hamburguesas en una sola hamburguesa. desbordamiento de pila.
C - No es el más corto, pero es sin recursión. 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;
}
Javascript
Para recortar algunos personajes más, y para que nos echen de más tiendas de software, vamos con:
eval(i=''eval(i)'');
Nemerle :
Esto bloquea el compilador con Exception:
def o(){[o()]}
Python :
so=lambda:so();so()
Alternativamente:
def so():so()
so()
Y si Python optimiza las llamadas de cola ...:
o=lambda:map(o,o());o()
Person JeffAtwood;
Person JoelSpolsky;
JeffAtwood.TalkTo(JoelSpolsky);
¡Aquí está esperando que no se repita la cola!
xor esp, esp
ret