Malbolge
 Ett ekoprogram i Malbolge
| |
| Paradigm | Esoterisk, imperativ, skalär, värdenivå |
|---|---|
| Designad av | Ben Olmstead |
| Utvecklare | Ben Olmstead |
| Dök först upp | 1998 |
| Maskinskrivningsdisciplin | Oskrivet |
| Filnamnstillägg | .mal, .mb |
| Influerad av | |
| Brainfuck , INTERCAL (Tri-INTERCAL), Befunge | |
| Influenced | |
| Dis, Malbolge Unshackled | |
Malbolge ( / m æ l ˈ b oʊ l dʒ / ) är ett esoteriskt programmeringsspråk för offentlig egendom som uppfanns av Ben Olmstead 1998, uppkallat efter den åttonde helvetescirkeln i Dantes Inferno , Malebolge . Det var specifikt designat för att vara nästan omöjligt att använda, via en kontraintuitiv "galen operation", bas-tre aritmetik och självförändrande kod. Den bygger vidare på svårigheten med tidigare utmanande esoteriska språk (som Brainfuck och Befunge ), men tar denna aspekt till det yttersta och spelar på datavetenskapens och krypteringens intrasslade historia . Trots denna design är det möjligt att skriva användbara Malbolge-program.
Programmering i Malbolge
Malbolge var väldigt svår att förstå när den kom. Det tog två år för det första Malbolge-programmet att dyka upp. Författaren själv har aldrig skrivit något Malbolge-program. Det första programmet skrevs inte av en människa; den genererades av en strålsökningsalgoritm designad av Andrew Cooke och implementerad i Lisp .
Senare publicerade Lou Scheffer en kryptoanalys av Malbolge och tillhandahöll ett program för att kopiera dess input till dess output. Han sparade också den ursprungliga tolken och specifikationen efter att den ursprungliga webbplatsen slutade fungera, och erbjöd en allmän strategi för att skriva program i Malbolge samt några tankar om dess Turing-fullständighet .
Olmstead trodde att Malbolge var en linjär avgränsad automat . Det finns en diskussion om huruvida man kan implementera vettiga loopar i Malbolge — det tog många år innan den första icke-avslutande infördes. Ett korrekt 99 Bottles of Beer-program , som handlar om icke-triviala loopar och villkor, tillkännagavs inte på sju år; den första korrekta var av Hisashi Iizawa 2005. Hisashi Iizawa et al. föreslog också en guide för programmering i Malbolge i syfte att fördunkla för mjukvaruskydd.
2020 gjorde GitHub- användaren kspalaiologos en fungerande Lisp- tolk i Malbolge Unshackled.
Exempel på program
Hej världen!
Det här programmet visar " Hello, World ".
(=<`#9]~6ZY327Uv4-QsqpMn&+Ij"'E%e{Ab~w=_:]Kw%o44Uqp0/Q?xNvL:`H%c#DD2^WV>gY;dts76qKJImZkj
ekoprogram _
Det här programmet läser en sträng från en användare och skriver ut den strängen, liknande Unix echo .
(=BA#9"=<;:3y7x54-21q/p-,+*)"!h%B0/. ~P< <:(8& 66#"!~}|{zyxwvu gJ%
Design
Malbolge är maskinspråk för en ternär virtuell maskin , Malbolge- tolken .
Standardtolken och den officiella specifikationen matchar inte perfekt. En skillnad är att kompilatorn stoppar exekvering med data utanför intervallet 33–126. Även om detta från början ansågs vara en bugg i kompilatorn, sa Ben Olmstead att det var avsett och att det faktiskt fanns "en bugg i specifikationen".
Register
Malbolge har tre register , a , c och d . När ett program startar är värdet på alla tre registren noll.
a står för 'ackumulator', inställt på det värde som skrivs av alla skrivoperationer på minnet och används för standard I/O . c , kodpekaren, är speciell: den pekar på den aktuella instruktionen . d är datapekaren. Den ökas automatiskt efter varje instruktion, men platsen den pekar på används för datamanipuleringskommandon.
Pekarnotation
d kan hålla en minnesadress; [d] är register indirekt ; värdet lagrat på den adressen. [c] är liknande.
Minne
Den virtuella maskinen har 59 049 (3 10 ) minnesplatser som var och en kan innehålla ett tio-trits ternärt nummer . Varje minnesplats har en adress från 0 till 59048 och kan innehålla ett värde från 0 till 59048. Om du ökar förbi denna gräns går det tillbaka till noll.
Språket använder samma minnesutrymme för både data och instruktioner . Detta påverkades av hur hårdvara som x86-arkitektur fungerade.
Innan ett Malbolge-program startar är den första delen av minnet fylld med programmet. Allt blanksteg i programmet ignoreras och för att försvåra programmeringen måste allt annat i programmet börja som en av instruktionerna nedan.
Resten av minnet fylls genom att använda den galna operationen (se nedan) på de två föregående adresserna ( [m] = crz [m - 2], [m - 1] ) . Minnet fyllt på detta sätt kommer att upprepas var tolfte adresser (de individuella ternära siffrorna kommer att upprepas var tredje eller var fjärde adress, så en grupp av ternära siffror kommer garanterat att upprepas var tolfte).
År 2007 skapade Ørjan Johansen Malbolge Unshackled, en version av Malbolge som inte har den godtyckliga minnesgränsen. Förhoppningen var att skapa ett Turing-komplett språk och samtidigt hålla så mycket i Malbolges anda som möjligt. Inga andra regler ändras, och alla Malbolge-program som inte når minnesgränsen är helt funktionella.
Instruktioner
Malbolge har åtta instruktioner . Malbolge räknar ut vilken instruktion som ska utföras genom att ta värdet [c] , lägga till värdet av c till det och ta resten när detta divideras med 94. Slutresultatet talar om för tolken vad den ska göra:
|
Värde på ([c] + c) % 94 |
Instruktion representerad |
Förklaring |
|---|---|---|
| 4 | jmp [d] | Kopierar värdet vid [d] till c . Observera att c fortfarande kommer att ökas efter exekvering av denna instruktion, så nästa instruktion som ska exekveras kommer att vara den vid [d] + 1 (modulo 59049) . |
| 5 | ut a | Skriver ut värdet på ett , som ett ASCII -tecken, på skärmen. |
| 23 | i en | Matar in ett tecken, som en ASCII-kod, i en . Nya rader eller radmatningar är båda kod 10 . Ett filslutvillkor är kod 59048 . |
| 39 |
rotr [d] mov a, [d] |
Roterar värdet vid [d] med en ternär siffra åt höger (000211111 2 blir 2 000211111). Lagrar resultatet både vid [d] och i en . |
| 40 | mov d, [d] | Kopierar värdet vid [d] till d . |
| 62 |
crz [d], a mov a, [d] |
Gör den galna operationen (se nedan) med värdet vid [d] och värdet av en . Lagrar resultatet både vid [d] och i en . |
| 68 | nej | Gör ingenting. |
| 81 | slutet | Avslutar Malbolge-programmet. |
| Något annat värde | gör samma sak som 68 : ingenting. Dessa andra värden är inte tillåtna i ett program medan det laddas, men är tillåtna i efterhand. | |
Efter att varje instruktion har utförts, krypteras den skyldiga instruktionen (se nedan) så att den inte kommer att göra samma sak nästa gång, om inte ett hopp precis har hänt. Direkt efter ett hopp kommer Malbolge att kryptera den oskyldiga instruktionen precis före den den hoppade till istället. ökas värdena för både c och d med en och nästa instruktion exekveras.
Galen operation
För varje ternär siffra för båda ingångarna, använd följande tabell för att få en ternär siffra av resultatet. Till exempel, crz 0001112220, 0120120120 ger 1001022211.
| crz | Ingång 2 | |||
|---|---|---|---|---|
| 0 | 1 | 2 | ||
| Ingång 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 2 | |
| 2 | 2 | 2 | 1 | |
Kryptering
Efter att en instruktion har körts kommer värdet vid [c] (utan att något tilläggs till det) ersättas med sig själv mod 94. Sedan krypteras resultatet med en av följande två ekvivalenta metoder .
- Metod 1
- Hitta resultatet nedan. Lagra ASCII-koden för tecknet under den vid [c] .
0000000000111111111112222222222333333333333444444444444455555555556666666666677777777778888888888892995 36777777778888888888892995 36777777788888888888929951 67890123456789012345678901234567890123456789012345678901234567890123 -------------------------------------------- ---------------------------------------------------- 9m<.TVac `uY*MK'X~xDl}REokN:#?G"i@5z]&gqtyfr$(we4{WP)H-Zn,[%\3dL+Q;>U!pJS72FhOA1CB6v^=I_0/8|jsb- Metod 2
- Hitta resultatet nedan. Lagra den krypterade versionen på [c] .
| Resultat | Krypterad | Resultat | Krypterad | Resultat | Krypterad | Resultat | Krypterad | Resultat | Krypterad |
|---|---|---|---|---|---|---|---|---|---|
| 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 |
Lou Scheffers kryptoanalys av Malbolge nämner sex olika cykler i permutationen . De är listade här:
- 33 ⇒ 53 ⇒ 45 ⇒ 119 ⇒ 78 ⇒ 49 ⇒ 87 ⇒ 48 ⇒ 123 ⇒ 71 ⇒ 83 ⇒ 94 ⇒ 57 ⇒ 91 ⇒ 57 ⇒ 91 59 ⇒ 92 ⇒ 115 ⇒ 82 ⇒ 118 ⇒ 107 ⇒ 75 ⇒ 104 ⇒ 89 ⇒ 56 ⇒ 44 ⇒ 40 ⇒ 121 ⇒ 35 ⇒ 93 ⇒ 98 ⇒ 84 ⇒ 61 ⇒ 100 ⇒ 97 ⇒ 46 ⇒ 9 ⇒ 9 ⇒ 9 ⇒ 9 ⇒ 9 109 ⇒ 88 ⇒ 47 ⇒ 52 ⇒ 72 ⇒ 55 ⇒ 110 ⇒ 126 ⇒ 64 ⇒ 81 ⇒ 54 ⇒ 90 ⇒ 124 ⇒ 34 ⇒ 122 ⇒ 63 ⇒ 43 ⇒ 36 ⇒ 38 ⇒ 113 ⇒ 108 ⇒ 1 108 ⇒ 1 ⇒ 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 ...
Dessa cykler kan användas för att skapa loopar som gör olika saker varje gång och som så småningom blir repetitiva. Lou Scheffer använde denna idé för att skapa ett Malbolge-program (ingår i hans kryptoanalys länkad nedan) som upprepar allt som användaren matar in.
Varianter
Malbolge är inte Turing-komplett på grund av dess minnesbegränsningar. I övrigt har den sekventiell exekvering, upprepning och villkorlig exekvering. Flera försök har gjorts för att skapa Turing-kompletta versioner av Malbolge:
- Malbolge20 är en version av Malbolge med en utökad ordstorlek på 20 trits, vilket gör att man kan skriva ett program med en storlek på upp till ~3,4 gigabyte.
- Malbolge-T är en teoretisk version av Malbolge som återställer in-/utgångsströmmen när den når slutet, vilket möjliggör obundna program. Malbolge-T skulle vara bakåtkompatibel med Malbolge.
- Malbolge Unshackled är en förhoppningsvis Turing-komplett variant som tillåter program av vilken längd som helst. Men på grund av kommandovariationer för att tillåta värden över 257, kommer giltiga Malbolge-program inte nödvändigtvis att köras korrekt i Malbolge Unshackled.
Populärkultur
I tv-serien Elementary , under avsnittet "The Leviathan" (säsong 1, avsnitt 10), beskrivs en ledtråd skriven på en kaffebeställning som skriven i Malbolge. Det verkar vara en liten modifiering av det mer utförliga "Hello World"-exemplet som visas ovan.
I Leverage: Redemption -avsnittet "The Golf Job" (säsong 1, avsnitt 12) lyder ett automatiskt SMS-svar "Breanna är inte tillgänglig torsdag till söndag eller tills hon behärskar Malbolge-koden."
I Billions -avsnittet "The Limitless Shit" (säsong 5, avsnitt 7) förklarar en programmeringsanalytiker på Axe Capital att han "... brukade busa med Malbolge, men bara för skojs skull."
