Малболџ
Малболџ (енгл. Malbolge) је јавни домен езотеричног програмског језика ког је изумео Бен Олмстед 1998. године. Назван је по осмом кругу пакла у Дантеовој Божанственој комедији.
| Малболџ | |
|---|---|
| Оригинални назив | Malbolge |
| Модел | езотерични, императивни, скаларни |
| Појавио се | 1998. |
| Аутор(и) | Бен Олмстед |
| Дизајнер(и) | Бен Олмстед |
| Утицаји | Brainfuck, INTERCAL (Tri-INTERCAL), Befunge |
| Утицао на | Dis |
Малболџ, је језик који је дизајниран да буде тежак за програмирање (или можда немогуће - донедавно није постојао ни неформални аргумент који показује потпуност Тјуринга). На пример, ефекат било које инструкције зависи од тога где се она налази у меморији (мод 94), сва упутства се самомодификују (према таблици пермутације), а оба показивача кода и података се увећавају након сваке инструкције, што отежава поновно коришћење било ког кода или податка. Заснива се на потешкоћама ранијих езотеричних језика као што су Брејнфак (Brainfuck) и Бефунг (Befunge), иако је веома тешко, могуће је писати корисне програме у њему.
Програмирање у Малболџу уреди
Програмирање у Малболџу је било веома тешко за разумевање. О томе сведочи и чињеница да је први програм у Малболџу направљен тек 2 године након његовог оснивања. Сам аутор никада није написао ни један програм. Први програм није написало људско биће, већ је био генерисан алгоритмом за претраживање снопа за чији је дизајн заслужан Ендру Кук (Andrew Cooke) који је комплементиран у ЛИСП-у.[1]
Касније је Лу Шифер поставио криптоанализу Малболџа и обезбедио програм за копирање његовог уноса у свој производ. Такође је спасио оригинални тумач и спецификације након што је оригинална локација престала да функционише и понудио генерелну стратегију писања програма у Малболџу као и неке идеје за Тјурингову коначност програма. [2]
Олмстед је веровао да ће Малболџ бити линеарно ограничен робот. Постоји дискусија о томе да ли се могу применити разумне петље у Малболџу - требало је много година пре него што је уведен први који није завршен. Прави програм "99 Bottles of Beer" , који се бави не-тривијалним петљaма и условима, није објављен седам година; први исправан је био Хисасхи Иизава 2005.[3]
Примери програма уреди
Hello, World! уреди
Ендру Кук је имплементирао први програм у Малболџу. Програм "Hello World!" је написао 2000. године, 2 године након што је Бен Олмстед измислио језик.
(=<`#9]~6ZY32Vx/4Rs+0No-&Jk)"Fh}|Bcy?`=*z]Kw%oG4UUS0/@-ejc(:'8dc
Друга варијанта
('&%:9]!~}|z2Vxwv-,POqponl$Hjig%eB@@>}=<M:9wv6WsU2T|nm-,jcL(I&%$#"`CB]V?Tx<uVtT`Rpo3NlF.Jh++FdbCBA@?]!~|4XzyTT43Qsqq(Lnmkj"Fhg${z@>
Не брините ако не разумете ништа. То је само намера творца језика. Заправо, изгледа језиво само зато што је шифровано; зато Kук предлаже "нормализован Малболџ", што значи да остане после фазе дешифровања. То не значи да је језик много лакши након тога, међутим,могуће је написати програм у нормализованом Малболџу и касније применити завршну фазу шифрирања.Нормализован Малболџ програм је уклонио иницијално мапирање.
Пример "Hello, World!" програма у нормализованом Малболџ језику
jpp<jp<pop<<jo*<popp<o*p<pp<pop<pop<jijoj/o<vvjpopoopo<ojo/o vooooooooooooooooooooooooooooooooooooooooooooooooooo*p<v*<*
Чак и ако изгледа лакше за читање него раније, и даље је компликовано разумети без описа онога шта сваки симбол значи, па чак и са њим. Дистрибуција Малболџа долази са пуним описом језика. Надаље, у нормализованом Малболџу значење података је измењено тако да нормализација није ни потребна.
- CAT
Лу Шифер је користио другачији приступ од Кука. Његова идеја је да осмисли Малболџ
као криптосистем, то јест, комплексан алгоритам
претварајући улаз у излаз. Овај програм чита низ карактера и штампа тај низ.
(=BA#9"=<;:3y7x54-21q/p-,+*)"!h%B0/.
~P<
<:(8&
66#"!~}|{zyxwvu
gJ%
Дизајн уреди
Малболџ је машински језик направљен за виртуелну машину која користи тернарни бројчани систем. Не долази до савршеног преклапања стандардног интерпретатора и јавне спецификације.[4] Једна од разлика је у томе што компајлер завршава егзекуцију са подацима од 33-126. Иако се ово сматрало багом у компајлеру, Бен Олмстед је изјавио да је то с намером тако и да је у ствари баг у спецификацији. Како би се лакше користиле команде овог програмског језика, потребно је разумети његово радно окружење.
Регистри уреди
Малболџ располаже са три регистра a, c и d која се користе за манипулацију подацима. Када програм почне с радом, почетна вредност сва три регистра је 0.
a означава акумулатор подешен на вредност задану од стране свих записаних операција у меморији
c показивач кода (code pointer) приказује тренутну инструкцију. Регистар се аутоматски повећава након сваке од
инструкција и указује на њено извршавање.[5]
d показивач података (data pointer) Такође се аутоматски повећава након сваке од инструкција, али локација коју он упућује се користи за податке команде манипулације.
Означавање уреди
d може да садржи адресу у меморији; [d] је вредност која се чува на тој адреси. Исто важи и за [c].
Меморија уреди
Виртуелна машина има 59,049 меморијских локација.
Језик користи исти меморијски простор за податке и инструкције. На то је утицао начин на који функционише хардвер x86 архитектуре.
Пре него што започне програм Малболџ, први део меморије се попуњава програмом. Када интерпретер очита програм, сви празни простори у програму се игноришу. Ако интерпретер наиђе на било шта што није инструкција или простор, исписује грешку, у супротном, учитава датотеку. Како би се програмирање отежало, све остало у програму мора почети као једно од доле наведених упутстава.
Остатак меморије се попуњава коришћењем лудих операција на претходне две адресе ([m] = crz [m - 2], [m - 1]). Меморија испуњена на овај начин ће поновити сваких дванаест наслова (појединачне тернарне цифре ће поновити сваку трећу или четврту адресу, тако да загарантована група тернарних цифара понавља сваку дванаесту).
У 2007. години, Øрјан Јохансен је створио Малболџ Аншаклд (енгл. Malbolge Unshackled), верзију Малболџа која нема произвољно ограничење меморије. Нада је била стварање Тјуринг- потпуног језика, уз задржавање духа Малболџа. Ниједна друга правила се не мењају, а сви Малболџ програми који не досегну границу меморије су потпуно функционални.[6]
Инструкције уреди
У Малболџу се користи осам инструкција. Када преводилац покушава да изврши програм, прво проверава да ли је тренутна инструкција ASCII знак, тачније, ако [с] није између 33 и 126, укључујући обе вредности, инструкција није валидна и програм се ту завршава. Узимањем вредности [c], Малболџ одлучује коју инструкцију ће извршити додајући му вредност c и узимајући остатак при дељењу са 94. Коначни резултат говори тумачу шта треба да уради.
| Вредност израза ([c] + c) % 94 |
Инструкција represented |
Објашњење |
|---|---|---|
| 4 | jmp [d] | Вредност [d] говори где ће Малболџ скочити и започети извршавање инструкција. |
| 5 | out a | На екрану штампа вредност a у виду ASCII карактера |
| 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] |
Извршава луде операције (види испод) са вредностима из [d] и a. Чува резултат у [d] и a. |
| 68 | nop | Не ради ништа. |
| 81 | end | Завршава Малболџ програм. |
| Било која друга вредност | исто што важи и за 68: ништа. Остале вредности нису дозвољене у програму док се учитавају, али су дозвољене накнадно. | |
Ако неки резултат није један од осам знакова, датотека ће бити одбијена.
Након извршења инструкције, 33 се одузима од инструкције
у с, а резултат се користи као индекс. Нови
знак се затим смешта у с, а затим се с повећава.
Још један начин за представљање инструкција.
Нормализација програма уреди
Предност, коју је донела нормализација програма, је то што команде(карактери) не мењају вредност у зависности од позиције на којој се налазе, што омогућава лакше генерисање. Сада, програм садржи само командне знакове (j, i, *, p, <, v, o).
- j d = [d] Подешава показивач података на вредност у ћелији на коју указује тренутна вредност.
- i c = [c] Подешава показивач инструкције на вредност у ћелији на коју указује његова тренутна вредност.
- [d] = ROTATE([d]) Ротира вредност у ћелији на коју указује Д за једну тернарну цифру удесно. Као споредни ефекат, ова вредност се чува у А.
- p [d] = CRAZY(a, [d]) Примењује луду операцију вредности А на ћелију на коју указује Д.
- / a = INPUT Чита један карактер из улаза и чува ASCII у А.
- < PRINT a Штампа карактер са ASCII добијен као остатак при дељењу a са 256.
- v STOP Зауставља извршење програма.
- o NOP Једини важећи програм који не ради ништа.
"Луда" операција уреди
За сваку цифру тернарног система, користи следећу табелу. Пример: crz 0001112220, 0120120120 даје резултат 1001022211
| crz | Унос 2 | |||
|---|---|---|---|---|
| 0 | 1 | 2 | ||
| Унос 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 2 | |
| 2 | 2 | 2 | 1 | |
Кодирање уреди
Након извршења инструкције, вредност на [c] (без икаквог додавања) биће замењена са остатком при дељењу са 94 (mod 94). Затим, резултат је шифрован једним од следећих два еквивалентна метода.
Метод 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 уреди
Нађите резултат испод. Чувати шифровану верзију на '[с]' .
| Резултат | Шифровано | Резултат | Шифровано | Резултат | Шифровано | Резултат | Шифровано | Резултат | Шифровано |
|---|---|---|---|---|---|---|---|---|---|
| 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 ...
Ови циклуси се могу користити за креирање петљи које сваки пут врше различите ствари и које се на крају понављају. Лу Шифер је ову идеју искористио за креирање програма Малболџ која понавља све што корисник уноси.
Популарна култура уреди
У десетој епизоди прве сезоне серије "Елементарно", кључни докази у решавању злочина били су део папира,на којима је програмски код штампан на Малболџу (што је непрецизна копија програма Хелло Ворлд горе), а на другој је забележен ред кафе.[7]
Види још уреди
Референце уреди
- ^ Cooke, Andrew. „malbolge: hello world”. Архивирано из оригинала 02. 07. 2017. г. Приступљено 29. 10. 2018.
- ^ Mykhailova, Mariya. „Malbolge - Programming language”.
- ^ „Language Malbolge”. 99 Bottles of Beer.
- ^ Green, Austin. „Malbolge”. Louisiana Tech University.
- ^ Olmstead, Ben. „Malbolge Specification”. www.lscheffer.com.
- ^ Johansen, Ørjan. „An interpreter for the Malbolge Unshackled dialect” (Haskell). oerjan.nvg.org.
- ^ „Leviathan”. Elementary. Сезона 1. Епизода 10. Manhattan. CBS.
Спољашње везе уреди
- Бен Олмстед- О Малболџу
- Малболџ интерпретер (C source code)
- Malbolge interpreter, debugger, assembler and example Malbolge Assembly code (Java source code)
- Опис Куковог алгоритма за креирање првог Малболџ програма Архивирано на сајту Wayback Machine (18. октобар 2010)
- Расправа о писању програма Малболге
- "99 bottles" у Малболџу (real loop version)
- Малболџ СДК – Збирка програма која олакшава кодирање у Малболге (Португалски)
- Малболџ онлајн интерпретер у JavaScript са сакупљањем програма