Какой самый короткий код вызывает переполнение стека? [закрыто]

160

Чтобы отметить публичный запуск переполнения стека, какой самый короткий код вызывает переполнение стека? Любой язык приветствуется.

ETA: Просто чтобы прояснить этот вопрос, поскольку я случайный пользователь Scheme: хвостовой вызов "recursion" - это действительно итерация, и любое решение, которое может быть преобразовано в итеративное решение относительно тривиально приличным компилятором, не будет быть посчитанным. :-П

ETA2: я сейчас выбрал «лучший ответ»; см. этот пост для обоснования. Спасибо всем, кто внес свой вклад! :-)

Chris Jester-Young
источник

Ответы:

212

Все эти ответы и не Befunge? Держу пари, что это самое короткое решение из всех:

1

Без шуток. Попробуйте сами: http://www.quirkster.com/iano/js/befunge.html

РЕДАКТИРОВАТЬ: Я думаю, мне нужно объяснить это. Операнд 1 помещает 1 во внутренний стек Befunge, а отсутствие чего-либо еще помещает его в цикл в соответствии с правилами языка.

Используя предоставленный интерпретатор, вы в конечном итоге - и я имею в виду - в конечном итоге - попадете в точку, когда массив Javascript, представляющий стек Befunge, становится слишком большим для перераспределения браузера. Если бы у вас был простой интерпретатор Befunge с меньшим и ограниченным стеком - как это имеет место с большинством языков ниже - эта программа вызовет более заметное переполнение быстрее.

Патрик
источник
8
Хм ... но действительно ли это переполнение стека или просто бесконечный цикл? Мой переводчик JS не переполнился, он просто ушел в отпуск, так сказать.
Конрад Рудольф
3
Это не бесконечный цикл, потому что инструкция 1 помещает 1 в стек. В конце концов, вашему интерпретатору Befunge не хватит места в стеке, но это займет некоторое время. :)
Патрик
18
Вы .. разбили мой браузер и ... отправили мой вентилятор процессора в перегрузку.
Sam152
2
Удивительный! Мой компьютер или браузер (Opera) не зависали, но оба процессора работали на 100%, а скорость вентилятора была на уровне 3.
Secko
28
Вот программа Befunge, которая переполняется быстрее: " она загружает 79 копий числа 32 каждые два раза, а не две копии числа 1.
KirarinSnow
291

Прочитайте эту строку и сделайте то, что она говорит дважды .

оборота юрдольф
источник
174

Вы также можете попробовать это в C # .net

throw new StackOverflowException();
GateKiller
источник
29
Педантик во мне говорит, что это не вызывает переполнения стека, просто выдает исключение. Это все равно, что сказать, что самый быстрый способ нападения акул - это стоять в море и кричать «Акула нападает!». Несмотря на это, я проголосую за это. :)
Бернард
Хорошо - есть ли разница? Можете ли вы поймать это и продолжить? Или это так же, как стекопотока в C #? В этом случае это как-то является переполнением стека, так как он неотличим от одного ... Однако - upvote по всем вышеуказанным причинам
Пн.
18
Если в лесу переполняется стек, и никто не может его поймать, это исключение?
Я бы не сказал «самый короткий», потому что это не так, как если бы вы могли скомпилировать однострочную версию таким образом. Это делает бросить переполнение стека быстро , хотя я думаю.
Доминик К
159

Nemerle :

Это приводит к сбою компилятора с исключением StackOverflowException:

def o(){[o()]}
оборота Cody Brocious
источник
119

Мой текущий лучший (в сборке x86):

push eax
jmp short $-1

в результате получается 3 байта объектного кода ( 50 EB FD). Для 16-битного кода это также возможно:

call $

что также приводит к 3 байта ( E8 FD FF).

Крис Шут-Янг
источник
6
Подсчет байтов после «компиляции» (или сборки) - не код-гольф.
Луи Бренди
37
Вопрос говорит: «[...] какой самый короткий код вызывает переполнение стека?» Он не указывает исходный код, интерпретируемый код, машинный код, объектный код или управляемый код ...
Андерс Сандвиг
Напомним, что сервер гольфа Shin позволяет отправлять объектный код для оценки, хотя он также учитывает все ваши заголовки ELF. Хм ....
Крис Шестер-Янг
См., Например, golf.shinh.org/p.rb?FizzBuzz#x86 для некоторых примеров этого. (Честно говоря, я не знаю, как люди могут создавать 99-байтовые двоичные файлы ELF.) :-P
Крис Джестер-Янг
7
@lbrandy: Есть достаточно людей, которые могут написать объектный код напрямую. Я не могу сделать это для x86, но для определенного микропроцессора я могу. Я бы посчитал такой код.
Джои
113

PIC18

PIC18 Ответ дается ТЗ приводит к следующим инструкциям (бинарными):

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

Однако только CALL выполнит переполнение стека:

CALL $
1110 1100 0000 0000
0000 0000 0000 0000

Меньше, быстрее PIC18

Но RCALL (относительный вызов) еще меньше (не глобальная память, поэтому нет необходимости в дополнительных 2 байтах):

RCALL $
1101 1000 0000 0000

Таким образом, самая маленькая на PIC18 - это одна команда, 16 бит (два байта). Это займет 2 цикла инструкций на цикл. При 4 тактах на цикл инструкций вы получаете 8 тактов. PIC18 имеет 31 уровень стека, поэтому после 32-го цикла он переполняет стек за 256 тактов. На 64 МГц вы переполните стек за 4 микросекунды и 2 байта .

PIC16F5x (еще меньше и быстрее)

Тем не менее, серия PIC16F5x использует 12-битные инструкции:

CALL $
1001 0000 0000

Опять же, два цикла команд на цикл, 4 такта на инструкцию, поэтому 8 тактов на цикл.

Однако PIC16F5x имеет двухуровневый стек, поэтому в третьем цикле он будет переполнен в 24 инструкциях. При 20 МГц он будет переполнен за 1,2 микросекунды и 1,5 байта .

Intel 4004

Intel 4004 имеет 8 разрядную команду вызова подпрограммы:

CALL $
0101 0000

Для любопытных, которые соответствуют ascii 'P'. С 3-уровневым стеком, который занимает 24 такта в общей сложности 32,4 микросекунды и один байт . (Если вы не разгоните свой 4004 - давай, ты знаешь, что хочешь.)

Это так же мало, как ответ befunge, но намного, намного быстрее, чем код befunge, работающий в современных интерпретаторах.

Адам Дэвис
источник
57

Гудок переполнен!

//              v___v
let rec f o = f(o);(o)
//             ['---']
//             -"---"-
Джульетта
источник
55

Каждое задание нуждается в правильном инструменте. Познакомьтесь с языком переполнения SO , оптимизированным для переполнения стека:

so
Конрад Рудольф
источник
7
Если вы создаете специализированный язык для генерации переполнений с минимальным количеством кода, очевидно, что вы захотите (1) пустой ввод, создающий код переполнения стека (возможно, небольшой двоичный файл, который выполняет собственный код, сгенерированный из записи кода сборки) или (2 все входные программы выдают указанный двоичный файл.
Джаред Апдайк
Хм, не тьюринг завершен. Я не знаю, можно ли еще назвать это языком ...
Адам Дэвис,
42

TeX:

\def~{~.}~

Результаты в:

! Превышена емкость TeX, извините [размер входного стека = 5000].
~ -> ~
    ,
~ -> ~
    ,
~ -> ~
    ,
~ -> ~
    ,
~ -> ~
    ,
~ -> ~
    ,
...
<*> \ def ~ {~.} ~

Латекс:

\end\end

Результаты в:

! Превышена емкость TeX, извините [размер входного стека = 5000].
\ end # 1 -> \ csname end # 1
                      \ endcsname \ @checkend {# 1} \ expandafter \ endgroup \ if @ e ...
<*> \ end \ end
Pi.
источник
Поскольку ~активен, его можно использовать вместо \a. И я обнаружил код LaTeX совершенно случайно. :)
Джош Ли
35

Ассемблер Z-80 - в ячейке памяти 0x0000:

rst 00

один байт - 0xC7 - бесконечный цикл переноса текущего ПК в стек и перехода к адресу 0x0000.

Деннис Манси
источник
2
Я помню, что пустым eprom были бы все 0xffs, которые являются первыми 7 (= call 0x0038) инструкциями. Это было бы полезно для отладки вашего оборудования с помощью осциллографа. Шина адреса будет циклически проходить через пространство 64 КБ, так как стек многократно переполняется, чередуя чтение 0xff с 0x0038.
Билл Форстер
29

По-английски:

recursion = n. See recursion.
Винко Врсалович
источник
32
Любой здравомыслящий человеческий мозг тоже оптимизирует интерпретацию этого, а не взорвется. :-P
Крис Шестер-Янг
73
Крис, разумный человеческий мозг в наши дни становится редкостью.
Джейсон Z
20
редкость ... ты имеешь в виду, что они существуют?
Адам Лерман
11
Google рекурсия
CodeFusionMobile
29

Другой пример PHP:

<?
require(__FILE__);
диска
источник
4
Вы могли бы даже быть сокращены, пропуская круглые скобки (но включая место вместо первого).
Алекс
26

Как насчет следующего в бейсике:

10 GOSUB 10

(Боюсь, у меня нет переводчика бейсика, так что это предположение).

stusmith
источник
3
На самом деле не переполнение стека, поскольку BASIC - это язык без стеков. Даже VB (у которого есть стек) не будет переполнен этим, поскольку он просто прыгает, а не создает кадр стека.
Даниэль Спивак
21
Это, а GOSUBне GOTO. Так как он RETURNтуда, откуда он был вызван, наверняка он использует стек?
Том
3
Да я согласен. У меня было много переполнений стека в бейсике в 80-х.
Ник
6
Я запустил этот в yabasic просто для удовольствия, и он чуть не сломал мой компьютер. Слава богу, Маллок в конце концов потерпел неудачу, но я пейджинговал как завтра.
Адам Розенфилд
2
Ой, извините, Адам ... напоминает мне время, когда в университете кто-то случайно написал программу, которая рекурсивно разветвлялась: сломал весь сервер Silicon Graphics.
Стусмит
26

Мне понравилась куча ответов Коди, поэтому вот мой аналогичный вклад в C ++:

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

typedef Overflow<0>::type Kaboom;

Ни в коем случае не кодовая игра в гольф, но все же что-нибудь для переполнения мета стека! :-П

Крис Шут-Янг
источник
21

Вот мой вклад C, весом 18 символов:

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

Это намного сложнее оптимизировать! :-П

Крис Шут-Янг
источник
4
Не компилируется для меня: "неопределенная ссылка на` main '": P
Эндрю Джонсон
1
Я не понимаю: зачем вызывать o () 2x?
Дина
3
@Dinah: Одним из ограничений моего конкурса было то, что оптимизация хвостового вызова не считается рекурсией; это просто итеративный цикл. Если вы только что написали o () один раз, это можно было бы оптимизировать с помощью хвостового вызова примерно так (с помощью компетентного компилятора): "o: jmp o". При 2 вызовах o компилятор должен использовать что-то вроде: «o: call o; jmp o». Это рекурсивная инструкция вызова, которая делает переполнение стека.
Крис Джестер-Янг
Вы правы - я не обращал внимания на эту часть. Спасибо за разъяснение.
Дина
19

Используя пакетный файл окна с именем "s.bat":

call s
Джуд аллред
источник
17

Javascript

Чтобы урезать еще несколько персонажей и выкинуть себя из других магазинов программного обеспечения, давайте перейдем к:

eval(i='eval(i)');
Travis Wilson
источник
15

Groovy:

main()

$ groovy stack.groovy:

Caught: java.lang.StackOverflowError
    at stack.main(stack.groovy)
    at stack.run(stack.groovy:1)
 ...
Крис Бродфут
источник
Проголосовал, потому что это довольно интересно. Тем не менее, выявляется довольно досадная слабость в компиляторе Groovy (такие хвостовые вызовы могут быть встроены во время компиляции).
Даниэль Спивак
ты уверен, что это хвостовой вызов? что падение в конце программы не вызывает оболочки интерпретатора?
Аарон
15

Пожалуйста, скажите мне, что означает аббревиатура " GNU ".

Greg
источник
4
Или Eine (Eine не Emacs), или Zwei (Zwei был Eine изначально). :-P
Крис Шестер-Янг
Или YAML, или WINE, или XNA, или любой другой по адресу en.wikipedia.org/wiki/Recursive_acronym
TM.
Drei (Drei - это действительно Emacs Incognito), Fier (Fier - это Emacs Reinvented) - хорошо, так что я только что придумал это :-)
Ferruccio
14
Person JeffAtwood;
Person JoelSpolsky;
JeffAtwood.TalkTo(JoelSpolsky);

Здесь надеемся на отсутствие хвостовой рекурсии!

Райан Фокс
источник
1
Хе-хе, смешно. Что касается разговоров, то идея «эффекта эхо-камеры» тоже довольно интересна. Не совсем вызывает переполнение стека, но все же.
Крис Джестер-Янг
8
Разве это не исключение нулевого указателя? Извините, я знаю, что это шутка.
Jamesh
12

C - Это не самое короткое, но без рекурсии. Он также не переносим: он падает на Solaris, но некоторые реализации alloca () могут вернуть здесь ошибку (или вызвать malloc ()). Вызов printf () необходим.

#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
источник
Вы также можете просто сделать "ulimit -s16", чтобы установить стек действительно маленьким. Любое число меньше 16, и программа даже не запускается (очевидно, недостаточно аргументов!).
Эндрю Джонсон
11

Perl в 12 символов:

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

bash в 10 символов (пробел в функции важен):

i(){ i;};i
оборота асксол
источник
11

попробуйте положить более 4 пирожков на один бургер. переполнение стека.

user8456
источник
1
Здесь, в Новой Зеландии, у нас есть Burger Wisconsin, где они используют большие, но тонкие пирожки. Я уверен, что вы можете сложить более 4 из них, если хотите; это будет очень дорогой бургер, хотя!
Крис Джестер-Янг
Возможно: alafista.com/2010/05/10/… Возможно, нет: cheaplightning.blogspot.com/2010/06/…
BCS
Ммм ... In-n-Out. en.wikipedia.org/wiki/In-n-out#Menu
cbednarski
11

Python :

so=lambda:so();so()

В качестве альтернативы:

def so():so()
so()

И если Python оптимизировал хвостовые вызовы ...:

o=lambda:map(o,o());o()
Cody Brocious
источник
К счастью для вас, Python не выполняет оптимизацию хвостовых вызовов; в противном случае он был бы дисквалифицирован, как и два других ответа. :-P
Крис Шестер-Янг
10

Я выбираю «лучший ответ» после этого поста. Но сначала я хотел бы отметить некоторые очень оригинальные вклады:

  1. аку. Каждый из них исследует новый и оригинальный способ вызвать переполнение стека. Идея выполнения f (x) ⇒ f (f (x)) будет рассмотрена в моей следующей записи ниже. :-)
  2. Коди, который дал компилятору Nemerle переполнение стека.
  3. И (немного неохотно), GateKiller предлагает исключение переполнения стека. :-П

Как бы мне ни нравилось вышеизложенное, задача состоит в том, чтобы заняться гольф-кодом, и, если честно, респондентам я должен присудить «лучший ответ» за самый короткий код, который является записью Befunge; Я не верю, что кто-нибудь сможет победить это (хотя Конрад определенно пытался), поэтому поздравляю Патрика!

Видя большое количество решений по переполнению стека за рекурсией, я удивляюсь, что никто (на момент написания статьи) не использовал комбинатор Y (см. Эссе Дика Габриэля « Почему Y» для начинающих). У меня есть рекурсивное решение, которое использует комбинатор Y, а также подход аку f (f (x)). :-)

((Y (lambda (f) (lambda (x) (f (f x))))) #f)
Крис Шут-Янг
источник
8

Вот еще один интересный из Схемы:

((лямбда (х) (хх)) (лямбда (х) (хх)))
Адам Розенфилд
источник
Очень хорошо, и в этом тоже есть хорошая симметрия. Кроме того, использовать формулировку (лямбда (х) (хх)): ((Y (лямбда (х) (хх))) #f) тоже очень весело!
Крис Джестер-Янг
О, это мило. Он работает и в Ruby, хотя и не так красиво, как в Scheme: lambda {| x | x.call x} .call lambda {| x | x.call x}
Уэйн Конрад
7

Ява

Немного короче версия решения Java.

class X{public static void main(String[]a){main(a);}}
Миша
источник
5
Или (то же количество символов): public static void main (String ... a) {main ();}
Майкл Майерс
Или для ребят из TDD (такое же количество символов): public class $‹@org.junit.Test public void $ () {$ ();}}
mhaller
Тем не менее, не самый короткий (см. Мой ответ)
Draemon
6
xor esp, esp
ret
a1k0n
источник
это не совсем переполнение стека, но это тоже хорошо: D
botismarius
5

3 байта:

label:
  pusha
  jmp label

Обновить

Согласно (старой?) Документации Intel (?) , Это также 3 байта:

label:
  call label

Андерс Сандвиг
источник
Это 3 байта в 32-битном режиме. Хороший ответ, учитывая, что он заполнит стек намного быстрее, чем мой ответ!
Крис Джестер-Янг
Согласно penguin.cz/~literakl/intel/j.html#JMP , jmp составляет 3 байта с 8, 16 или 32-битным относительным адресом назначения. Пуша также составляет 1 байт, что составляет в общей сложности 4
Андерс Сандвиг
Существует три типа jmp: короткий, ближний и дальний. Короткий jmp (с использованием кода операции 0xEB) составляет два байта. Адресат должен находиться в диапазоне от -128 до 127 байт от следующей инструкции. :-)
Крис Шестер-Янг
Может быть, вы правы. Мне лень выкапывать мой ассемблер и проверять ...;)
Андерс Сандвиг