Малболџ

Из Википедије, слободне енциклопедије
Иди на навигацију Иди на претрагу
Малболџ
Оригинални називMalbolge
Моделезотерични, императивни, скаларни
Појавио се1998.
Аутор(и)Бен Олмстед
Дизајнер(и)Бен Олмстед
УтицајиBrainfuck, INTERCAL (Tri-INTERCAL), Befunge
Утицао наDis

Малболџ (енгл. Malbolge) је јавни домен езотеричног програмског језика ког је изумео Бен Олмстед 1998. године. Назван је по осмом кругу пакла у Дантеовој Божанственој комедији.

Малболџ, је језик који је дизајниран да буде тежак за програмирање (или можда немогуће - до недавно није постојао ни неформални аргумент који показује потпуност Тјуринга). На пример, ефекат било које инструкције зависи од тога где се она налази у меморији (мод 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]

Види још[уреди]

Референце[уреди]

  1. ^ Cooke, Andrew. „malbolge: hello world”. 
  2. ^ Mykhailova, Mariya. „Malbolge - Programming language”. 
  3. ^ „Language Malbolge”. 99 Bottles of Beer. 
  4. ^ Green, Austin. „Malbolge”. Louisiana Tech University. 
  5. ^ Olmstead, Ben. „Malbolge Specification”. www.lscheffer.com. 
  6. ^ Johansen, Ørjan. „An interpreter for the Malbolge Unshackled dialect” (Haskell). oerjan.nvg.org. 
  7. ^ „Leviathan”. Elementary. Сезона 1. Епизода 10. Manhattan. CBS. 

Спољашње везе[уреди]