Malbolge.tex

%&pdfLaTeX
% !TEX encoding = UTF-8 Unicode
\documentclass{article}
\usepackage{ifxetex}
\usepackage{listings}
\ifxetex
\usepackage{fontspec}
\setmainfont[Mapping=tex-text]{STIXGeneral}
\else
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\fi
\usepackage{textcomp}

\usepackage{amssymb}
\usepackage{fancyhdr}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0pt}

\begin{document}

\begin{center}
\baselineskip=13pt
{\LARGE{}\textbf{Wstęp do programowania w Malbolge}}

\textbf{Krzysztof \texttt{"}Palaiologos\texttt{"} Szewczyk}

\textbf{2018}
\end{center}

\baselineskip=13pt
\leftskip=0pt
\parindent=18pt
Język Malbolge to z pewnością jeden z trudniejszych języków programowania 
dla człowieka. Takie \texttt{"}cuda\texttt{"} jak np. Brainfuck/Befunge zaliczę 
będą do najprostszych języków ezoterycznych. Malbolge z drugiej strony to język 
bardzo trudny dla człowieka ze względu na swoje kryptograficzne możliwości. 
Liczba instrukcji wirtualnej maszyny tego języka jest taka sama jak wspomnianego 
wcześniej Brainfucka (którego założeniem było turing completness i jak najmniejszy 
zestaw instrukcji). Każda instrukcja jednak jest specjalnie zakodowana, i znaczenie 
w rozszyfrowaniu jej może zależeć nawet od pozycji instrukcji w kodzie źródłowym!

Malbolge to nie język turing complete, ponieważ nie zezwala na dostęp do nieskończonej 
ilości pamięci (w założeniu; to znaczy że konwencjonalne języki takie jak 
C, ograniczane szerokością magistrali adresowej procesora dalej są turing complete; 
Malbolge spełnia jednak praktyczną definicję turing completness, ponieważ może 
obliczyć rozwiązanie każdego problemu i jest ograniczeniem jest tylko pamięć).

\parindent=36pt
Ekosystem Malbolge nie jest skomplikowany - omawiany język jest kodem maszynowym 
dla trynarnej maszyny wirtualnej. Istnieją asemblery do języka (pozwalające 
ominąć bóle związane z zaszyfrowywaniem instrukcji).

\parindent=18pt
\texttt{"}Standard\texttt{"} języka i jego oficjalna wirtualna maszyna lekko się 
różnią. Tą różnicą jest działanie VM po napotkaniu znaku poza zasięgiem 
(33-126). To na początku zostało uznane błędem, ale sam twórca języka przyznał, 
że błąd leżał faktycznie po stronie \texttt{"}standardu\texttt{"}, a nie jego 
implementacji.

Malbolge posiada trzy rejestry (to aż o 3 więcej niż Brainfuck); A, C, i D. 
Kiedy program w Malbolge jest uruchamiany, wszystkie rejestry mają początkową 
wartość 0. A to akumulator, ustawiony na wartość zapisaną przez wszystkie 
operacje zapisu na pamięci, używany do wejścia i wyjścia. C, wskaźnik kodu 
to specjalny rejestr wskazujący aktualną instrukcję. D to wskaźnik danych który 
jest inkrementowany automatycznie po każdej instrukcji, ale lokacja którą wskazuje 
jest używana do manipulacji danymi. D zawiera adres, notacja [D] to wartość 
zawarta na tym adresie, podobnie z [C].

\parindent=36pt
Maszyna wirtualna może zaadresować do 54 049 bajtów pamięci (3\textasciicircum{}10), 
z których każda może zawierać jedną liczbę trynarną długą na 10 trytów. 
Każda lokacja w pamięci zawiera adres od 0 do 59048 lub wartość w takim samym 
zakresie. Inkrementacja lub dekrementacja poza limitem pozostawi komórkę w pamięci 
na wartości zerowej. Język używa tej samej pamięci dla danych i kodu. Tą samą 
technikę można zauważyć w procesorach x86 Intela. Przed rozpoczęciem działania 
programu obraz pamięci jest ładowanty. Wszystkie spacje, tabulacje, entery, itd. 
są ignorowane i aby sprawić że programowanie jest trudniejsze, program musi 
się zaczynać jedną z instrukcji omówionych później. Reszta pamięci jest 
wypełniona tzw. szaloną operacją na dwóch wcześniejszych adresach \textbf{([c] 
= sz[m-2],[m-1]). }Tak wypełniona pamięć będzie się powtarzać co 12 adresów 
(indywidualne liczby trynarne będą się powtarzać co trzy lub cztery adresy, 
więc grupa cyfr trynarnych z pewnością będzie powtarzać się co dwanaście 
miejsc).

\parindent=18pt
Malbolge ma osiem instrukcji. Aby sprawdzić która instrukcja zostanie wykonana, 
przyjmuje się wartość [c] i dodaje się do tego wartość c, biorąc resztę 
z dzielenia przez 94. Tak więc mając dane osiem instrukcji po wartości \textbf{([c] 
+ c) \% 94 }dane są następujące liczby:

\parindent=0pt
• 4, \textbf{jmp [d] }, wartość [d] to punkt do którego wirtualna maszyna 
skoczy i zacznie wykonywać instrukcje.

\leftskip=36pt
\parindent=-18pt
• 5, \textbf{outb a }, Wyświetla wartość a jako znaku ASCII na ekran.

• 23, \textbf{inb a }, Wczytuje znak jako kod ASCII do a, nowe linie to 10, EOF 
to 59048

• 39, \textbf{rot [d]}; \textbf{mov a, [d] }, odwraca wartość [d] o jeden tryt 
(00212 -\texttt{>} 20021). Nową wartość umieszcza w [d] i a

• 40, \textbf{mov d, [d] },kopiuje [d] do d

• 62, \textbf{sza [d], a}; \textbf{mov a, [d] }, wykonuje szaloną operację 
z wartością [d] i a. Umieszcza wynik i w [d], i w a. 

• 68, \textbf{nop} , nie robi nic.

• 81, \textbf{hlt} , wyłącza wirtualną maszynę.

• Wszystko inne, to samo co 68.

\leftskip=0pt
\parindent=18pt
Po inkrementacji C, winna instrukcja zostaje zaszyfrowana (patrz niżej), więc 
nie zrobi tego samego, chyba że wykonywany był skok. Tuż po skoku, niewinna 
instrukcja zostane zaszyfrowana (ta wcześniejsza od tej, do której skakano). 
Wtedy wartości C i D są zwiększane o jeden, i następna instrukcja jest wykonywana.

Szalona operacja to z definicji funkcja sprawiająca, że dla każdego trytu, dla 
dwóch wejść, używana jest podana tabelka (niżej) do ustalenia finalnej wartości; 
Wszystkie podane wartości są dla wejścia 2 zwiększającego się o 1 (tj. 0, 
1, 2). Dla przykładu, SZA 012210, 210012 = 002200.

\parindent=0pt
• Dla wejścia 1 = 0: 1, 0, 0

\leftskip=36pt
\parindent=-18pt
• Dla wejścia 1 = 1: 1, 0, 2

• Dla wejścia 1 = 2: 2, 2, 1 

\leftskip=0pt
\parindent=18pt
Tuż po wykonaniu instrukcji, wartość na [c] (przed wszystkimi operacjami) jest 
zamieniana z resztą dzielenia jej przez 94. Wtedy reszultat jest szyfrowany; Znajdź rezultat poniżej, zapisz kod ASCII na [c]:

\parindent=0pt
\begin{lstlisting}
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
\end{lstlisting}

\parindent=18pt
Wszystkie powyższe techniki produkują duży i niewydajny kod (czego można było 
się spodziewać; aktualnie nie jest znany mi sposób przygotowywania wydajnych 
i małych programów w Malbolge).

Generalna strategia programowania w Malbolge jest dość prosta, jeśli uda Ci 
się zmieścić cały program do pamięci, można napisać program umożliwiający 
arbitrarny dostęp do pamięci, czego konsekwencją może istnieć konwersja z 
Brainfucka do Malbolge (spokojnie, pracuję już nad tym).

\parindent=36pt
Język i tak jest dość prosty do programowania, ale można byłoby go jeszcze 
utrudnić - usuwanie wszystkich krótkich cykli po ponownym \texttt{"}strawieniu\texttt{"} 
tabeli permutacji instrukcji, modyfikacja instrukcji on-the-fly (co umożliwiałoby 
szyfrowanie nawet skoków). Cała \texttt{"}trudność\texttt{"} języka leży 
w ilości rzeczy, które trzeba brać pod uwagę przy programowaniu.

\vspace{13pt}
\begin{center}
\textbf{Miłego programowania!}
\end{center}

\newpage

\end{document}