Malbolge

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 20:07, 1 июня 2016.
Malbolge
Парадигма Эзотерическая, Империческая, Скалярная, Многоуровневая
Спроектировано Ben Olmstead
Первый   появившийся 1998
Печать дисциплины Нетипизированный
Расширение файла .mal, .mb
Портал: None
Под влиянием
Brainfuck, INTERCAL ( Tri-INTERCAL), Befunge

Malbolge - эзотерический язык программирования, придуманный Беном Олмстедом в 1998 году. Язык разработан с целью быть максимально сложным для написания программ. Получил своё название от Malebolge, восьмого круга ада Данте.

Malbolge был специально разработан так, чтобы его было практически невозможно использовать из-за нелогичных "Crazy операций" и кода, изменяющегося самостоятельно.[1]. До сих пор практически невозможно написать полезную программу на Malbolge.

Программирование на Malbolge

Код первой программы, выводящей «HEllO WORld», сгенерировала другая программа на языке Lisp, использовавшая поиск в множестве всех возможных программ, через два года после появления самого языка Malbolge.[1] 24 августа 2000 года Энтони Юхас в своём блоге анонсировал 3 работающих программы на языке Malbolge, выводящих фразы «Hello, world.», «Malbolge sucks.» и «antwon.com rules!».[2] Позже Лу Шеффер произвел криптоанализ языка. 17 августа 2004 года Томаш Вегжановски написал генератор программ, выводящих заданные строки. Однако программы, полученные этим путем, длиннее программ Юхаса.[3]

"Hello World!" in Malbolge

Данная программа на языке Malbolge выводит на экран сообщение "Hello World!".

 ('&%:9]!~}|z2Vxwv-,POqponl$Hjig%eB@@>}=<M:9wv6WsU2T|nm-,jcL(I&%$#"
 `CB]V?Tx<uVtT`Rpo3NlF.Jh++FdbCBA@?]!~|4XzyTT43Qsqq(Lnmkj"Fhg${z@>

Значительно сокращённый вариант:

 (=<`#9]~6ZY32Vx/4Rs+0No-&Jk)"Fh}|Bcy?`=*z]Kw%oG4UUS0/@-ejc(:'8dc

Другой вариант программы, которая выводит "Hello, world.":

 (=<`:9876Z4321UT.-Q+*)M'&%$H"!~}|Bzy?=|{z]KwZY44Eq0/{mlk**
 hKs_dG5[m_BA{?-Y;;Vb'rR5431M}/.zHGwEDCBA@98\6543W10/.R,+O<

Ещё один вариант программы которая пишет "HEllO WORld"

 (=<`$9]7<5YXz7wT.3,+O/o'K%$H"'~D|#z@b=`{^Lx8%$Xmrkpohm-kNi;
 gsedcba`_^]\[ZYXWVUTSRQPONMLKJIHGFEDCBA@?>=<;:9876543s+O<oLm

Как работает Malbolge

Malbolge это машинный язык, написанный для виртуальной машины, интерпретатора Malbolge.

Общие правила

  • Стандартный переводчик и официальные спецификации не совпадают идеально.[4]
  • Упрощенное объяснение работы интерпретатора кода: он пропускает ненужные участки шифрования переводит программу на ассемблер.
  • Компилятор прекращает выполнение с данными за пределами диапазона 33-126. Хотя это было изначально ошибкой компилятора, Бен Олмстед заявил, что это было на самом деле "ошибкой в спецификации."[1]

Регистры

В виртуальной машине Malbolge есть три регистра: a, c и d. Регистр c — регистр кода, используемый в качестве указателя на текущую команду. Регистр d — регистр данных, используемый для управления данными. Регистр a — аккумулятор, также используемый некоторыми командами для манипуляции данными. При запуске программы все регистры равны нулю.

Обозначения

d может содержать адрес памяти; [d] это значение, находящееся по данному адресу. [c] работает так же.

Память

Размер памяти виртуальной машины — 59049 (310) ячеек с числами из 10 троичных цифр. Все ячейки с адресами от 0 до 59048 имеют значения от 0 до 59048. Все изменения происходят по модулю 59049 (mod 59049). При запуске программы начало памяти заполняется ASCII-кодами символов её исходного текста. Символы пустого пространства (пробелы, табуляция, переносы строк и пр.) игнорируются, а остальные символы должны быть командами Malbolge (см. ниже). Остаток памяти заполняется с использованием операции crazy (см. ниже): [m] = crz [m-2], [m-1].

Команды

В Malbolge есть 8 команд. Виртуальная машина определяет, какую команду выполнять, следующим образом: к значению ячейки с адресом c ([c]) прибавляется значение c, а в качестве команды выступает остаток от деления этого числа на 94 (поскольку во входном алфавите языка 94 символа, ASCII-коды которых с 33-го по 126-й). Таблица действий интерпретатора:

Команды
Значение ([c] + c) % 94 Инструкция Пояснение
4 mov c, [d] Переход к ячейке с номером [d].
5 out a Вывод значения ASCII-символа с кодом a % 256 на экран.
23 in a Ввод ASCII-символа в a. Разделитель строк имеет код 10. Конец файла — 59048.
39 rotr [d] mov a, [d] Сдвигает значение [d] на одну троичную цифру вправо (0002111112 превращается в 2000211111). Результат сохраняется в [d] и в a.
40 mov d, [d] Копирование значения из [d] в d.
62 crz [d], a mov a, [d] Произвести операцию crazy (см. ниже) со значениями [d] и a. Результат сохраняется в [d] и в a.
68 nop Ничего не делает.
81 end Конец программы.
Любые другие значения ничего не делают. Они не разрешены при загрузке программы, но разрешены после этого.

После выполнения каждой инструкции она шифруется операцией Crazy. После этого значения c и d увеличиваются на 1 и выполнение продолжается со следующей инструкции.

Операция crazy

Операция является аналогом побитовых операций — она применяется к двум соответствующим цифрам.

Операция crazy
crz 2-я цифра
0 1 2
1-я цифра 0 1 0 0
1 1 0 2
2 2 2 1

Шифрование

После того, как очередная инструкция выполнена, инструкция шифруется с помощью следующей таблицы перевода (если она является одним из возможных символов языка):

Метод 1

Найти результат ниже. Храните ASCII в [c].

0000000000111111111122222222223333333333444444444455555555556666666666777777777788888888889999
0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123
----------------------------------------------------------------------------------------------
9m<.TVac`uY*MK'X~xDl}REokN:#?G"i@5z]&gqtyfr$(we4{WP)H-Zn,[%\3dL+Q;>U!pJS72FhOA1CB6v^=I_0/8|jsb

Метод 2

Найти результат ниже. Храните зашифрованную версию на [c].

Таблица расшифровки
Результат Зашифровано Результат Зашифровано Результат Зашифровано Результат Зашифровано Результат Зашифровано
0 57 19 108 38 113 57 91 76 79
1 109 20 125 39 116 58 37 77 65
2 60 21 82 40 121 59 92 78 49
3 46 22 69 41 102 60 51 79 67
4 84 23 111 42 114 61 100 80 66
5 86 24 107 43 36 62 76 81 54
6 97 25 78 44 40 63 43 82 118
7 99 26 58 45 119 64 81 83 94
8 96 27 35 46 101 65 59 84 61
9 117 28 63 47 52 66 62 85 73
10 89 29 71 48 123 67 85 86 95
11 42 30 34 49 87 68 33 87 48
12 77 31 105 50 80 69 112 88 47
13 75 32 64 51 41 70 74 89 56
14 39 33 53 52 72 71 83 90 124
15 88 34 122 53 45 72 55 91 106
16 126 35 93 54 90 73 50 92 115
17 120 36 38 55 110 74 70 93 98
18 68 37 103 56 44 75 104

Циклы расшифровки

Лу Схеффер языка Malbolge вывел шесть различных циклов в шифрования. Они перечислены здесь:

  • 33 ⇒ 53 ⇒ 45 ⇒ 119 ⇒ 78 ⇒ 49 ⇒ 87 ⇒ 48 ⇒ 123 ⇒ 71 ⇒ 83 ⇒ 94 ⇒ 57 ⇒ 91 ⇒ 106 ⇒ 77 ⇒ 65 ⇒ 59 ⇒ 92 ⇒ 115 ⇒ 82 ⇒ 118 ⇒ 107 ⇒ 75 ⇒ 104 ⇒ 89 ⇒ 56 ⇒ 44 ⇒ 40 ⇒ 121 ⇒ 35 ⇒ 93 ⇒ 98 ⇒ 84 ⇒ 61 ⇒ 100 ⇒ 97 ⇒ 46 ⇒ 101 ⇒ 99 ⇒ 86 ⇒ 95 ⇒ 109 ⇒ 88 ⇒ 47 ⇒ 52 ⇒ 72 ⇒ 55 ⇒ 110 ⇒ 126 ⇒ 64 ⇒ 81 ⇒ 54 ⇒ 90 ⇒ 124 ⇒ 34 ⇒ 122 ⇒ 63 ⇒ 43 ⇒ 36 ⇒ 38 ⇒ 113 ⇒ 108 ⇒ 39 ⇒ 116 ⇒ 69 ⇒ 112 ⇒ 68 ⇒ 33 ...
  • 37 ⇒ 103 ⇒ 117 ⇒ 111 ⇒ 120 ⇒ 58 ⇒ 37 ...
  • 41 ⇒ 102 ⇒ 96 ⇒ 60 ⇒ 51 ⇒ 41 ...
  • 42 ⇒ 114 ⇒ 125 ⇒ 105 ⇒ 42 ...
  • 50 ⇒ 80 ⇒ 66 ⇒ 62 ⇒ 76 ⇒ 79 ⇒ 67 ⇒ 85 ⇒ 73 ⇒ 50 ...
  • 70 ⇒ 74 ⇒ 70 ...

Эти циклы могут быть использованы для создания петли, которые делают различные вещи каждый раз и что в конечном счете станет повторным. Лу Схеффер использовал эту идею создать программу Malbolge (входит в его криптоанализа связан ниже), что повторяет все, что входы пользователей.

Варианты

Malbolge не Тьюринг-полной, из-за ее пределов памяти. Тем не менее, в противном случае имеет последовательное выполнение, повторение, и условно-исполнение. Несколько попыток было сделано, чтобы создать Тьюринг-полные версии Malbolge:

  • Malbolge-Т представляет собой теоретическое версия Malbolge, который сбрасывает ввода / вывода потока при достижении конца, что позволяет неограниченных программ. Malbolge-Т будет обратно совместим с Malbolge.</ li>
  • Malbolge Несдерживаемая является, мы надеемся, Тьюринг-полной вариации, что позволяет программам любой длины. Тем не менее, из-за изменения команды, чтобы для значений выше 257, действительные программы Malbolge не обязательно правильно работать в Malbolge Несдерживаемая.

В популярной культуре

В 10-м эпизоде первого сезона сериала «Элементарно» ключевой уликой в разгадке преступления послужил клочок бумаги, на одной из сторон которого был распечатан код программы на malbolge (являющийся неточной копией программы «Hello World» выше), а на другой записан заказ кофе.[1][5]

Примечания

  1. 1,0 1,1 1,2 1,3 Temkin, Daniel (3 November 2014). "Interview with Ben Olmstead".
  2. "andrew cooke: malbolge "hello world""
  3. "Malbolge - Progopedia - Encyclopedia of Programming Languages". progopedia.com.
  4. Green, Austin. "Malbolge". www2.latech.edu.
  5. "Leviathan". Elementary. Season 1. Episode 10.

Список литературы