Мальболге - Malbolge
Парадигма | Эзотерический, императивный, скалярный, ценностный уровень |
---|---|
Разработано | Бен Олмстед |
Впервые появился | 1998 |
Печатная дисциплина | Нетипизированный |
Расширения имени файла | .mal, .mb |
Под влиянием | |
Brainfuck, ИНТЕРКАЛ (Tri-INTERCAL), Befunge | |
Под влиянием | |
Дис, Мальболге Освобожденный |
Мальболге (/мæлˈбoʊлdʒ/) это всеобщее достояние эзотерический язык программирования изобретен Беном Олмстедом в 1998 году, назван в честь восьмого круга ада в Данте с Inferno, то Malebolge. Он был специально разработан для того, чтобы его было почти невозможно использовать с помощью нелогичной «сумасшедшей операции», арифметики с основанием три и самоизменяющегося кода.[1] Он основан на сложности более ранних сложных эзотерических языков (таких как Brainfuck и Befunge ), но доводит этот аспект до крайности, играя на запутанных историях Информатика и шифрование. Несмотря на такую конструкцию, можно писать полезные программы на Malbolge.
Программирование в Мальболге
Когда он появился, понять Мальболге было так сложно, что на появление первой программы Мальболге ушло два года. Действительно, сам автор никогда не писал ни одной программы Malbolge.[1] Первую программу написал не человек: она была создана поиск луча алгоритм разработан Эндрю Куком и реализован в Лисп.[2]
Позже Лу Шеффер опубликовал криптоанализ of Malbolge и предоставил программу для копирования входных данных в выходные данные.[3] Он также сохранил исходный интерпретатор и спецификацию после того, как исходный сайт перестал работать, и предложил общую стратегию написания программ на Malbolge, а также некоторые мысли о его полноте по Тьюрингу.[4]
Олмстед считал Мальболджа линейно ограниченный автомат. Существует дискуссия о том, можно ли реализовать разумные циклы в Malbolge - потребовалось много лет, прежде чем был введен первый неограничивающий цикл. Правильный Программа 99 бутылок пива, который имеет дело с нетривиальными циклами и условиями, не анонсировался в течение семи лет; первый правильный был Хисаши Иидзава в 2005 году.[5] Hisashi Iizawa et al. также предложил руководство по программированию на Malbolge с целью обфускации для защиты программного обеспечения.[6]
Примеры программ
Эта секция возможно содержит оригинальные исследования.Апрель 2020 г.) (Узнайте, как и когда удалить этот шаблон сообщения) ( |
Привет, мир!
Эта программа Malbolge отображает "Привет, мир! ", с заглавными буквами и восклицательным знаком в конце.
(= <`# 9] ~ 6ZY32Vx / 4Rs + 0No- & Jk)" Fh} | Bcy? `= * Z] Kw% oG4UUS0 / @ - ejc (: '8dc
Кот программа
Эта программа считывает строку от пользователя и печатает эту строку, как в Unix. Кот.
(= BA # 9 "= <;: 3y7x54-21q / p -, + *)"! H% B0 /. ~ P << :( 8 & 66 # "! ~} | {ZyxwvugJk
Дизайн
Мальболге машинный язык для тройной виртуальная машина, Мальболге устный переводчик.
Стандартный интерпретатор и официальная спецификация несовместимы.[7] Одно отличие состоит в том, что компилятор останавливает выполнение с данными за пределами диапазона 33–126. Хотя изначально это считалось ошибкой в компиляторе, Бен Олмстед заявил, что это было задумано и что на самом деле это «ошибка в спецификации».[1]
Регистры
У Мальболге три регистры, а, c, и d. Когда программа запускается, значение всех трех регистров равно нулю.
а обозначает «аккумулятор», устанавливается в значение, записываемое всеми операциями записи в память и используемое для стандартный ввод / вывод. c, указатель кода особенный: он указывает на текущую инструкцию.[8] d - указатель данных. Он автоматически увеличивается после каждой инструкции, но место, на которое он указывает, используется для команд манипулирования данными.
Обозначение указателя
d может содержать адрес памяти; [d] является регистрировать косвенный; значение, хранящееся по этому адресу. [c] похож.
объем памяти
На виртуальной машине 59049 (310) объем памяти места, каждое из которых может вместить десять тритов троичное число. Каждая ячейка памяти имеет адрес от 0 до 59048 и может содержать значение от 0 до 59048. При превышении этого предела происходит возврат к нулю.
Язык использует одинаковое пространство памяти для данных и инструкций. На это повлияло то, как работает оборудование, такое как архитектура x86.[1]
Перед запуском программы Malbolge первая часть памяти заполняется программой. Все пробелы в программе игнорируются, и, чтобы усложнить программирование, все остальное в программе должно начинаться в соответствии с одной из приведенных ниже инструкций.
Остальная память заполняется с помощью псих операции (см. ниже) на двух предыдущих адресах ([m] = crz [m - 2], [m - 1]). Заполненная таким образом память будет повторяться каждые двенадцать адресов (отдельные троичные цифры будут повторяться каждые три или четыре адреса, поэтому группа троичных цифр гарантированно повторяется каждые двенадцать).
В 2007 году Эрджан Йохансен создал Malbolge Unshackled, версию Malbolge, не имеющую произвольного ограничения памяти. Была надежда на создание полного по Тьюрингу языка, сохраняя при этом дух Мальболге. Никакие другие правила не меняются, и все программы Malbolge, которые не достигают предела памяти, полностью функциональны.[9]
инструкции
У Мальболге восемь инструкции. Мальболге определяет, какую инструкцию выполнить, взяв значение [c], добавляя значение c к нему и взяв остаток от деления на 94. Окончательный результат сообщает интерпретатору, что делать:
Значение ([c] + c)% 94 | Инструкция представлен | Объяснение |
---|---|---|
4 | jmp [d] | Копирует значение в [d] к c. Обратите внимание, что c будет по-прежнему увеличиваться после выполнения этой инструкции, поэтому следующая инструкция, которая будет выполнена, будет той, которая находится в [d] + 1 (по модулю 59049). |
5 | из | Печатает значение а, как ASCII персонаж, на экран. |
23 | в | Вводит символ в виде кода ASCII в а. Новые строки или перевод строки - это код 10. Условие конца файла - это код 59048. |
39 | ротр [д] mov a, [d] | Поворачивает значение на [d] одной троичной цифрой (0002111112 становится 2000211111). Сохраняет результат как в [d] И в а. |
40 | mov d, [d] | Копирует значение в [d] к d. |
62 | crz [d], a mov a, [d] | Есть ли псих операции (см. ниже) со значением на [d] и ценность а. Сохраняет результат как в [d] И в а. |
68 | нет | Ничего не делает. |
81 | конец | Завершает программу Мальболге. |
Любое другое значение | делает то же самое, что и 68: ничего. Эти другие значения не разрешены в программе, пока она загружается, но разрешены впоследствии. |
После выполнения каждой инструкции виновная инструкция шифруется (см. Ниже), поэтому в следующий раз она не сделает то же самое, если только не произошел скачок. Сразу после прыжка Мальболге зашифрует невинную инструкцию непосредственно перед той, к которой он перешел. Тогда значения обоих c и d увеличиваются на единицу и выполняется следующая инструкция.
Псих операция
Для каждой троичной цифры обоих входных значений используйте следующую таблицу, чтобы получить троичную цифру результата. Например, crz 0001112220, 0120120120 дает 1001022211.
crz | Вход 2 | |||
---|---|---|---|---|
0 | 1 | 2 | ||
Вход 1 | 0 | 1 | 0 | 0 |
1 | 1 | 0 | 2 | |
2 | 2 | 2 | 1 |
Шифрование
После выполнения инструкции значение в [c] (без добавления чего-либо) будет заменен собой мод 94. Тогда результат зашифрованный с одним из следующих двух эквивалентных методы.
- Способ 1
- Найдите результат ниже. Сохраните ASCII-код символа под ним в [c].
00000000001111111111222222222233333333334444444444555555555566666666777777777777888888999901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012 --------------------------------------------- 9 мес. <.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 |
Криптоанализ Мальболджа Лу Шеффером упоминает шесть различных циклов в перестановка. Они перечислены здесь:
- 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-T - это теоретическая версия Malbolge, которая сбрасывает поток ввода / вывода по достижении конца, что позволяет использовать неограниченные программы. Мальболге-Т будет обратная совместимость с Мальболге.[3]
- Malbolge Unshackled - это, надеюсь, полная по Тьюрингу вариация, допускающая программы любой длины. Однако из-за различий в командах, допускающих значения выше 257, допустимые программы Malbolge не обязательно будут правильно работать в Malbolge Unshackled.[10]
Популярная культура
В телесериале Элементарный во время эпизода «Левиафан» (сезон 1, эпизод 10) подсказка, написанная на заказе на кофе, описывается как написанная на языке Мальболге. Похоже, это небольшая модификация более подробного примера «Hello World», показанного выше.[1][11]
Смотрите также
Рекомендации
- ^ а б c d е ж Темкин, Даниил (03.11.2014). «Интервью с Беном Олмстедом». esoteric.codes. Получено 2017-06-09.
- ^ Кук, Эндрю (2016-06-06). "malbolge: привет, мир". Получено 2017-06-09.
- ^ а б Схеффер, Лу (2015-04-17). «Введение в Мальболге». Получено 2017-06-09.
- ^ Михайлова, Мария (11.05.2012). «Мальболге - язык программирования». Прогопедия. Получено 2017-06-09.
- ^ "Language Malbolge". 99 бутылок пива. 2005-12-29. Архивировано из оригинал на 2020-05-14. Получено 2020-11-19.
- ^ а б ИДЗАВА, Хисаси. "Метод программирования на обфусцированном языке Malbolge" (PDF) (на японском языке). Нагойский университет. Получено 2017-06-09.
- ^ Грин, Остин (2000-12-01). "Мальболге". Технологический университет Луизианы. Получено 2017-06-09.
- ^ Олмстед, Бен (1998). «Спецификация Мальболге». www.lscheffer.com. Получено 2017-06-09.
- ^ Йохансен, Эрьян (2013-10-25). «Переводчик диалекта Мальболге без сковок» (Haskell). oerjan.nvg.org. Получено 2017-06-09.
- ^ "Мальболге без кандалов". esolangs.org. 2017-04-14. Получено 2017-06-09.
- ^ «Левиафан». Элементарный. Сезон 1. Эпизод 10. Манхэттен. 2012-12-14. CBS.