Мальболге - Malbolge

Мальболге
ПарадигмаЭзотерический, императивный, скалярный, ценностный уровень
РазработаноБен Олмстед
Впервые появился1998
Печатная дисциплинаНетипизированный
Расширения имени файла.mal, .mb
Под влиянием
Brainfuck, ИНТЕРКАЛ (Tri-INTERCAL), Befunge
Под влиянием
Дис, Мальболге Освобожденный

Мальболге (/мæлˈбл/) это всеобщее достояние эзотерический язык программирования изобретен Беном Олмстедом в 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]

Примеры программ

Привет, мир!

Эта программа 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
Инструкция
представлен
Объяснение
4jmp [d]Копирует значение в [d] к c. Обратите внимание, что c будет по-прежнему увеличиваться после выполнения этой инструкции, поэтому следующая инструкция, которая будет выполнена, будет той, которая находится в [d] + 1 (по модулю 59049).
5изПечатает значение а, как ASCII персонаж, на экран.
23вВводит символ в виде кода ASCII в а. Новые строки или перевод строки - это код 10. Условие конца файла - это код 59048.
39ротр [д]
mov a, [d]
Поворачивает значение на [d] одной троичной цифрой (0002111112 становится 2000211111). Сохраняет результат как в [d] И в а.
40mov d, [d]Копирует значение в [d] к d.
62crz [d], a
mov a, [d]
Есть ли псих операции (см. ниже) со значением на [d] и ценность а. Сохраняет результат как в [d] И в а.
68нетНичего не делает.
81конецЗавершает программу Мальболге.
Любое другое значениеделает то же самое, что и 68: ничего. Эти другие значения не разрешены в программе, пока она загружается, но разрешены впоследствии.

После выполнения каждой инструкции виновная инструкция шифруется (см. Ниже), поэтому в следующий раз она не сделает то же самое, если только не произошел скачок. Сразу после прыжка Мальболге зашифрует невинную инструкцию непосредственно перед той, к которой он перешел. Тогда значения обоих c и d увеличиваются на единицу и выполняется следующая инструкция.

Псих операция

Для каждой троичной цифры обоих входных значений используйте следующую таблицу, чтобы получить троичную цифру результата. Например, crz 0001112220, 0120120120 дает 1001022211.

Псих операция[1][6]
crzВход 2
012
Вход 10100
1102
2221

Шифрование

После выполнения инструкции значение в [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].
Таблица шифрования
РезультатЗашифрованныйРезультатЗашифрованныйРезультатЗашифрованныйРезультатЗашифрованныйРезультатЗашифрованный
057191083811357917679
1109201253911658377765
26021824012159927849
34622694110260517967
4842311142114611008066
58624107433662768154
69725784440634382118
79926584511964818394
89627354610165598461
91172863475266628573
108929714812367858695
11423034498768338748
1277311055080691128847
13753264514170748956
143933535272718390124
1588341225345725591106
1612635935490735092115
1712036385511074709398
186837103564475104

Криптоанализ Мальболджа Лу Шеффером упоминает шесть различных циклов в перестановка. Они перечислены здесь:

  • 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]

Смотрите также

Рекомендации

  1. ^ а б c d е ж Темкин, Даниил (03.11.2014). «Интервью с Беном Олмстедом». esoteric.codes. Получено 2017-06-09.
  2. ^ Кук, Эндрю (2016-06-06). "malbolge: привет, мир". Получено 2017-06-09.
  3. ^ а б Схеффер, Лу (2015-04-17). «Введение в Мальболге». Получено 2017-06-09.
  4. ^ Михайлова, Мария (11.05.2012). «Мальболге - язык программирования». Прогопедия. Получено 2017-06-09.
  5. ^ "Language Malbolge". 99 бутылок пива. 2005-12-29. Архивировано из оригинал на 2020-05-14. Получено 2020-11-19.
  6. ^ а б ИДЗАВА, Хисаси. "Метод программирования на обфусцированном языке Malbolge" (PDF) (на японском языке). Нагойский университет. Получено 2017-06-09.
  7. ^ Грин, Остин (2000-12-01). "Мальболге". Технологический университет Луизианы. Получено 2017-06-09.
  8. ^ Олмстед, Бен (1998). «Спецификация Мальболге». www.lscheffer.com. Получено 2017-06-09.
  9. ^ Йохансен, Эрьян (2013-10-25). «Переводчик диалекта Мальболге без сковок» (Haskell). oerjan.nvg.org. Получено 2017-06-09.
  10. ^ "Мальболге без кандалов". esolangs.org. 2017-04-14. Получено 2017-06-09.
  11. ^ «Левиафан». Элементарный. Сезон 1. Эпизод 10. Манхэттен. 2012-12-14. CBS.

внешняя ссылка