doc.tex

% !TeX root = doc.tex
\documentclass[a4paper,12pt]{book} % nie: report!


\usepackage[T1,plmath]{polski}\usepackage{polski} % lepiej to zamiast babel!
\usepackage[utf8]{inputenc} % w razie kłopotów spróbować: \usepackage[utf8x]{inputenc}
\usepackage{fancyhdr} % nagłówki i stopki
\usepackage{indentfirst} % WAŻNE, MA BYĆ!
\usepackage[pdftex]{graphicx} % to do wstawiania rysunków
\usepackage{amsfonts}
\usepackage{amsmath} % to do dodatkowych symboli, przydatne
\usepackage[pdftex,
            left=1in,right=1in,
            top=1in,bottom=1in]{geometry} % marginsy
\usepackage{amssymb} % to też do dodatkowych symboli, też przydatne
\usepackage{amsthm}
\usepackage{float}
\usepackage[font=small,labelfont=bf]{caption}
% jesli potrzeb, można oczywiście wstawić inne pakiety i swoje definicje...

\usepackage{amsmath}
\usepackage{listings}
\usepackage{color} %use color




% definicje nagłówków i stopek
\pagestyle{fancy}
\renewcommand{\chaptermark}[1]{\markboth{#1}{}}
\renewcommand{\sectionmark}[1]{\markright{\thesection\ #1}}
\fancyhf{}
\fancyhead[LE,RO]{\footnotesize\bfseries\thepage}
\fancyhead[LO]{\footnotesize\rightmark}
\fancyhead[RE]{\footnotesize\leftmark}
\renewcommand{\headrulewidth}{0.5pt}
\renewcommand{\footrulewidth}{0pt}
\addtolength{\headheight}{1.5pt}
\fancypagestyle{plain}{\fancyhead{}\cfoot{\footnotesize\bfseries\thepage}\renewcommand{\headrulewidth}{0pt}}

% interlinia
\linespread{1.25}

\definecolor{mygreen}{rgb}{0,0.6,0}
\definecolor{mygray}{rgb}{0.5,0.5,0.5}
\definecolor{mymauve}{rgb}{0.58,0,0.82}
 
%Customize a bit the look
\lstset{ %
backgroundcolor=\color{white}, % choose the background color; you must add \usepackage{color} or \usepackage{xcolor}
basicstyle=\ttfamily\footnotesize, % the size of the fonts that are used for the code
breakatwhitespace=false, % sets if automatic breaks should only happen at whitespace
breaklines=true, % sets automatic line breaking
captionpos=b, % sets the caption-position to bottom
commentstyle=\color{mygreen}, % comment style
extendedchars=true, % lets you use non-ASCII characters; for 8-bits encodings only, does not work with UTF-8
frame=single, % adds a frame around the code
keepspaces=true, % keeps spaces in text, useful for keeping indentation of code (possibly needs columns=flexible)
keywordstyle=\color{blue}, % keyword style
% language=Octave, % the language of the code
morekeywords={*,...}, % if you want to add more keywords to the set
numbers=left, % where to put the line-numbers; possible values are (none, left, right)
numbersep=5pt, % how far the line-numbers are from the code
numberstyle=\tiny\color{mygray}, % the style that is used for the line-numbers
rulecolor=\color{black}, % if not set, the frame-color may be changed on line-breaks within not-black text (e.g. comments (green here))
showspaces=false, % show spaces everywhere adding particular underscores; it overrides 'showstringspaces'
showstringspaces=false, % underline spaces within strings only
showtabs=false, % show tabs within strings adding particular underscores
stepnumber=1, % the step between two line-numbers. If it's 1, each line will be numbered
stringstyle=\color{mymauve}, % string literal style
tabsize=2, % sets default tabsize to 2 spaces,
title=\lstname % show the filename of files included with \lstinputlisting; also try caption instead of title
}
%END of listing package%



\lstset{
  language=Python
  }



\begin{document}
\begin{titlepage}
  ~

  \begin{tabular}{c@{\hspace{21mm}}|@{\hspace{5mm}}l}
    \vspace{-20mm} &                                                                   \\
    \multicolumn{2}{l}{\hspace{-12.5mm} \includegraphics[width=8cm]{LogoUMCS.jpg}}     \\
    \multicolumn{2}{@{\hspace{20mm}}l}{\vspace{-4mm}}                                  \\
    \multicolumn{2}{@{\hspace{28mm}}l}{\Large \sf UNIWERSYTET MARII
    CURIE-SKŁODOWSKIEJ}                                                                \\
    \multicolumn{2}{@{\hspace{28mm}}l}{\vspace{-4mm}}                                  \\
    \multicolumn{2}{@{\hspace{28mm}}l}{\Large \sf W LUBLINIE}                          \\
    \multicolumn{2}{@{\hspace{28mm}}l}{\vspace{-4mm}}                                  \\
    \multicolumn{2}{@{\hspace{28mm}}l}{\Large \sf Wydział Matematyki, Fizyki i
    Informatyki}                                                                       \\
    \multicolumn{2}{@{\hspace{28mm}}l}{\vspace{21mm}}                                  \\
                   & {\sf Kierunek: \textbf{informatyka} }                             \\
    %& {\sf Specjalność: \textbf{informatyczna}} \\ % wpisujemy tylko jeśli jest!!!
                   &                                                                   \\\\\\
                   & {\sf \large \bfseries Patryk Wałach}                              \\
                   & {\sf nr albumu: 296597}                                           \\
                   &                                                                   \\\\\\
                   & \Large \sf \bfseries Opracowanie prostego języka programowania    \\
                   & \Large \sf \bfseries z inferencją typów i jego kompilatora        \\
                   & \Large \sf \bfseries do języka JavaScript                         \\\\[-10pt]
                   & {\large \sf Development of a simple programming language}         \\
                   & {\large \sf with the type inference and its compiler}                \\
                   & {\large \sf to JavaScript}                               \\
                   &                                                                   \\
                   &                                                                   \\
                   &                                                                   \\
                   & {\sf Praca licencjacka}                                           \\
                   & \vspace{-7mm}                                                     \\
                   & {\sf napisana w Katedrze Oprogramowania Systemów Informatycznych} \\
                   & {\sf Instytutu Informatyki UMCS}                                  \\
                   & \vspace{-7mm}                                                     \\
                   & {\sf pod kierunkiem \bfseries dr hab. Jarosława Byliny}           \\
    \multicolumn{2}{@{\hspace{28mm}}l}{\vspace{15mm}}                                  \\
    \multicolumn{2}{@{\hspace{28mm}}l}{\textbf{\textsf{Lublin 2022}}}
  \end{tabular}
\end{titlepage}





\sloppy



\thispagestyle{empty}


\newpage{}

\thispagestyle{empty}

\newpage{}



\tableofcontents{}




\chapter*{Wstęp}
\addcontentsline{toc}{chapter}{Wstęp} % ...ale w spisie treści ma być
Język JavaScript uznawany jest za wysoko podatny na błędy. Jeden nieobsłużony wyjątek jest w stanie przerwać działanie całego programu. Z tego powodu deweloperzy sięgają po narzędzia wykrywające błędy na etapie kompilacji. Często jednak tego typu narzędzia wymagają dodatkowych adnotacji typów co zwiększa ilość pracy i zmniejsza czytelność kodu oraz nie radzą sobie z przesadnie dynamicznym kodem. Dlatego w niniejszej pracy sprawdzimy czy istnieje możliwość stworzenia kompilatora generującego kod w języku JavaScript. Kompilator zbudujemy w języku Python.

W pierwszych trzech rozdziałach przedstawiamy poszczególne elementy kompilatora z teoretycznego punktu widzenia (lekser, parser, inferencja typów, dopasowanie do wzorca). W rozdziale czwartym spoglądamy na język ReScript realizujący podobne zadania. W rozdziale piątym opisujemy założenia naszego kompilatora oraz prezentujemy opis formalny składni języka. W kolejnym rozdziale przedstawiamy narzędzia i środowiska użyte do stworzenia kompilatora. W rozdziale siódmy opisujemy wybrane fragmenty kodu stanowiące implementację naszego kompilatora. W ostatnim rozdziale dokonujemy refleksji co do zaimplementowanych i niezaimplementowanych funkcjonalności kompilatora.

\chapter{Ogólne wprowadzenie}
\section{Analiza leksykalna}
Analiza leksykalna w informatyce jest to proces rozbijania sekwencji znaków (np. takich jak kod źródłowy) na jednostki logiczne (zwane leksemami) złożone z jednego lub więcej znaków, które łącznie mają jakieś znaczenie \cite{Hopcroft__Motwani__Ullman__2005}. Przykładami leksemów mogą być słowa kluczowe (np. \lstinline$while$), identyfikator lub liczba składająca się z cyfr. Rozdzielaniem programu źródłowego na leksemy zajmuje się lekser.

Token jest strukturą reprezentującą leksem i wprost go kategoryzującą \cite{ Aho__Sethi__Ullman__1985}, co ułatwia późniejszą pracę parserowi. Tokeny kategoryzuje się na komputerowy odpowiednik tego, co lingwiści określiliby mianem części mowy. Biorąc jako przykład poniższy kod w języku C:
\begin{lstlisting}[language=c]
  x = a + b * 2;
\end{lstlisting}
analiza leksykalna, zwraca tokeny:
\begin{lstlisting}
  [(identifier, x), (operator, =), (identifier, a), (operator, +), (identifier, b), (operator, *), (literal, 2), (separator, ;)]
\end{lstlisting}
Dwoma ważnymi przypadkami znaków są znaki białe i komentarze. One również muszą być uwzględnione w gramatyce i przeanalizowane przez lekser, lecz mogą być odrzucone (nie produkować żadnych tokenów). Spełniają one wtedy zadanie, rozdzielenia dwóch tokenów (np. w \lstinline{if x} zamiast \lstinline{ifx}).

\section{Parser}
Analizator składniowy, parser – program dokonujący analizy składniowej danych wejściowych w celu określenia ich struktury gramatycznej w związku z określoną gramatyką formalną. Analizator składniowy umożliwia przetworzenie tekstu czytelnego dla człowieka w strukturę danych przydatną dla oprogramowania komputera. Wynikiem analizy składni, dokonywanej przez parser, najczęściej jest drzewo składniowe nazywane czasami drzewem wyprowadzenia \cite{Aho__Sethi__Ullman__1985}.



Zadanie parsera sprowadza się do sprawdzenia czy i jak dane wejściowe mogą zostać wyprowadzone z symbolu startowego. To zadanie można zrealizować na dwa sposoby:


\begin{itemize}
  \item Analiza zstępująca (ang. \emph{top-down parsing}) to strategia znajdowania powiązań między danymi przez stawianie hipotez dotyczących drzewa rozbioru składniowego i sprawdzanie, czy zależności między danymi są zgodne z tymi hipotezami.
  \item Analiza wstępująca (ang. \emph{bottom-up parsing}) – ogólna metoda analizy składniowej, w której zaczyna się od słowa wejściowego i próbuje się zredukować je do symbolu startowego. Drzewo wyprowadzenia jest konstruowane od liści do korzenia (stąd nazwa). W każdym momencie w trakcie tego procesu mamy formę zdaniową, która zawiera segment, powstały w ostatnim kroku wyprowadzenia. Segment ten nazywany uchwytem (ang. \emph{handle}) jest prawą stroną produkcji i powinien zostać w tym kroku zredukowany do jej lewej strony, w wyniku czego powstanie poprzednia forma zdaniowa z wyprowadzenia. Główna trudność w analizie wstępującej polega właśnie na odpowiednim znajdywaniu uchwytów.
        Analiza wstępująca może przebiegać w określonym kierunku (np. od lewej do prawej), lub w sposób bezkierunkowy, wtedy analizowane jest całe słowo naraz. Jednym z bardziej znanych przedstawicieli metody bezkierunkowej jest algorytm CYK. Do metod kierunkowych zalicza się między innymi parsery shift-reduce czyli LR, LALR, SLR, BC, pierwszeństwa.
\end{itemize}



\section{System typów}
System typów jest to system klasyfikacji wyrażeń w zależności od rodzajów wartości, jakie one generują \cite{Pierce__Benjamin__C__2002}. Każdej obliczonej wartości przypisywany jest pewien typ, który jednoznacznie definiuje, jakie operacje można na niej wykonać. Śledząc przepływ wartości, system typów stara się udowodnić, że w programie występuje poprawne typowanie, tzn. nie dochodzi do sytuacji, w której na wartości określonego typu próbujemy wykonać niedozwoloną operację.
\section{System typów ML} System typów ML jest to silny system typów stosowany w językach rodziny ML (Ocaml, Standard ML) oparty na inferencji.

Podstawowy system typów jest następujący: istnieją typy proste, takie jak \lstinline$string$, \lstinline$int$, \lstinline$bool$, \lstinline$unit$ (typ pusty) itd. Z dowolnych typów można też generować typy złożone –-- przez krotki (\lstinline$typ1 * typ2$, \lstinline$typ1 * typ2 * typ3$ itd.), konstruktory typów (typ \lstinline$list$, typ \lstinline$tree$ itd.) i funkcje (\lstinline$typ1 -> typ2$).

System próbuje nadać typy każdemu wyrażeniu języka i nie licząc kilku rzadkich przypadków, udaje mu się to całkiem dobrze.

Generalnie system taki wyklucza polimorfizm, jednak w Standard ML stworzono specjalne reguły umożliwiające polimorfizm dla wyrażeń arytmetycznych.

System typów w języku Standard ML jest interesujący z teoretycznego punktu widzenia – wiele problemów ma bardzo wysoką złożoność, jednak w praktyce inferencja zachodzi bardzo szybko – typy, które są rzeczywiście używane, są zwykle bardzo proste – rzadko używa się funkcji rzędów wyższych niż trzeci-czwarty oraz liczby argumentów większej niż kilkanaście.

W rzeczywistych implementacjach dochodzą do tego bardziej złożone problemy typizacji obiektów, modułów itd.

\section{Rekord z wariantami} Rekord z wariantami jest to rodzaj rekordu, posiadającego tę właściwość, że zbiór rekordów posiada wspólny typ, lecz różną postać, określoną aktualną wartością specjalnego pola znacznikowego.

Na przykład, zakładając, że chcemy stworzyć drzewo binarne typu \lstinline$int$. W języku Standard ML zrobilibyśmy to tworząc nowy typ danych w ten sposób:
\begin{lstlisting}[language=ML]
datatype tree = Leaf
  | Node of (int * tree * tree)
\end{lstlisting}
\lstinline{Leaf} i \lstinline{Node} są konstruktorami, które pozwalają nam na stworzenie konkretnego drzewa, np.
\begin{lstlisting}[language=ML]
  Node(5, Node(1, Leaf, Leaf), Node(3, Leaf, Node(4, Leaf, Leaf)))
\end{lstlisting}
\chapter{Inferencja typów w teorii}
\section{Problem inferencji typów}
Język ML przyjmuje wiele form, najpopularniejszymi wariantami są język Standard ML, język OCaml
i język F\#. Na potrzeby przykładu będziemy wzorować się na \cite{Damas__Milner__1982} i posługiwać się ML-the-calculus, drastycznie uproszczoną wersją języka ML co pozwoli na dojście do sedna w problemie rekonstrukcji typów.

Termy w języku ML-the-calculus są następujące:
\begin{equation}
  \begin{split}
    e\ ::&=x\qquad(\text{identyfikatory})\\
    &|\ \ \ c\qquad(\text{stałe})\\
    &|\ \ \ \lambda x.e\\
    &|\ \ \ e\ e\\
    &|\ \ \ \text{let }x=e\text{ in }e
  \end{split}
\end{equation}
Typy które będziemy przypisywali do termów są następujące:
\begin{equation}
  \begin{split}
    \tau\ ::&=\alpha\qquad(\text{typ zmienny})\\
    &|\ \ \ B\qquad(\text{typ podstawowy})\\
    &|\ \ \ \tau\rightarrow\tau
  \end{split}
\end{equation}
\section{Udowadnianie typów dla ML-the-calculus}

\begin{gather*}
  % \begin{split}
  \frac{}{\Gamma\vdash c:B} \\
  \\
  \frac{\Gamma,x:\tau'\vdash e:\tau}{\Gamma\vdash\lambda x.e:\tau'\rightarrow\tau} \\
  \\
  \frac{\Gamma\vdash e_1:\tau_2\rightarrow\tau\qquad\Gamma\vdash e_2:\tau_2}{\Gamma\vdash e_1\ e_2:\tau} \\
  \\
  \frac{\Gamma(x)=\bigwedge\alpha_1,...,\alpha_n.\tau'\qquad\tau=[\beta_i/\alpha_i]\tau'}{\Gamma\vdash x:\tau}(\beta_1\text{ fresh}) \\
  \\
  \frac{\Gamma\vdash e_1:\tau'\qquad\Gamma,x:(\bigwedge\alpha_1,...,\alpha_n.\tau')\vdash e_2:\tau}{\Gamma\vdash \text{let }x=e_1\text{ in }e_2:\tau:B}(\{\alpha_1,...,\alpha_n\}=ftv(\tau')\backslash ftv(\Gamma)) \\
  % \end{split}
\end{gather*}
Funkcja $ftv(\tau)$ oblicza zbiór zmiennych typów występujących w $\tau$.

Powyższe dowody nie mogą jednak być w prosty sposób przedstawione jako algorytm. Fakt, że typ $\tau'$ jest dowolnie wybierany w dowodzie dla $\lambda$ prowadzi do nieskończonej ilość dowodów, nawet dla prostego wyrażenia $\lambda x.x$.
\section{Inferencja typów bazująca na ograniczeniach}
Algorytmy inferencji typów bazujące na ograniczeniach generują dużą liczbę zmiennych typów oraz zbiór ograniczeń dla tych zmiennych. W drugim kroku algorytm dla każdej zmiennej, szuka typu, który spełnia wszystkie ograniczenia.
\section{Algorytm W}
Algorytm W inferencji typów przedstawiony w \cite{Milner__1978} oraz innych wcześniejszych publikacjach, opiera się na generowaniu ograniczeń i rozwiązywaniu ich w trakcie wykonywania rekursywnego przechodzenia przez termy.

Warto zauważyć, że w ten sposób: dostajemy, prostą strukturalnie rekursywną definicję rekonstrukcji typów, ale tracimy modularność algorytmu: rozszerzenie algorytmu W o dodatkowe funkcje jest o wiele trudniejsze niż algorytmu, który oddziela kroki generowania ograniczeń i ich rozwiązywania.

\begin{equation}
  \begin{split}
    W :&\ \Gamma\times e \rightarrow S\times\tau \\
    \\
    W(\Gamma,x) =&\  ([],[\beta_i/\alpha_i]\tau') \\
    &\ \text{where } \Gamma(x) = \bigwedge\alpha_i,...,\alpha_n.\tau' \\
    &\ \text{and } \beta_i \text{ are fresh} \\
    \\
    W(\Gamma,e_1\ e_2) =&\  (V\circ S_2\circ S_1,V\beta) \\
    &\ \text{where } (S_1,\tau_1) = W(\Gamma,e_1) \\
    &\ \text{and } (S_2,\tau_2)=J(S_1,\Gamma,e_2) \\
    &\ \text{and } V = unify(\{S_2\tau_1=\tau_2\rightarrow\beta\}) \\
    &\ \text{and } \beta \text{ is fresh} \\
    \\
    W(\Gamma,\lambda x.e) =&\  (S,S\beta\rightarrow\tau) \\
    &\ \text{where } (S,\tau)=W((\Gamma,x:\beta),e) \\
    &\ \text{and } \beta \text{ is fresh} \\
    \\
    W(\Gamma,\text{let }x=e_1\text{ in }e_2) =&\  (S_2\circ S_1,\tau_2) \\
    &\ \text{where } (S_1,\tau_1)=W(\Gamma,e_1) \\
    &\ \text{and } (S_2,\tau_2)=W((S_1\Gamma,x:(\bigwedge\alpha_1,...,\alpha_n.\tau_1)),e_2) \\
    &\ \text{and } \{\alpha_1,...,\alpha_n\}=ftv(\tau_1)\backslash ftv(S_1\Gamma) \\
  \end{split}
\end{equation}

\section{Algorytm J}
Algorytm W nie ma żadnych efektów ubocznych i świetnie zajmuje się aplikowaniem i komponowaniem substytucji w odpowiedniej kolejności. Częste aplikacje substytucji na wyrażeniach mogą znacznie zmniejszyć wydajność algorytmu rekonstruującego, dlatego też Milner zaprezentował bardziej efektywną imperatywną wariację algorytmu W nazwaną algorytmem J w \cite{Milner__1978}.

Algorytm J jest funkcją, która dla dokonanych do tej pory substytucji $S$, środowiska $\Gamma$ (ang. \emph{context}) (zbioru przechowywującego pary identyfikator wraz z typem) i wyrażenia $e$, zwraca kolejne substytucje $S$oraz typ wyrażenia $\tau$.
\begin{equation}
  \begin{split}
    J :& S\times\Gamma\times e \rightarrow S\times\tau \\
    \\
    J(S,\Gamma,x) =& (S,[\beta_i/\alpha_i]\tau') \\
    &\text{where } \Gamma(x) = \bigwedge\alpha_i,...,\alpha_n.\tau' \\
    &\text{and } \beta_i \text{ are fresh} \\
    \\
    J(S,\Gamma,e_1\ e_2) =& (V,\beta) \\
    &\text{where } (S_1,\tau_1) = J(S,\Gamma,e_1) \\
    &\text{and } (S_2,\tau_2)=J(S_1,\Gamma,e_2) \\
    &\text{and } V = unify'(\tau_1,\tau_2\rightarrow\beta,S_2) \\
    &\text{and } \beta \text{ is fresh} \\
    \\
    J(S,\Gamma,\lambda x.e) =& (S_1,\beta\rightarrow\tau) \\
    &\text{where } (S_1,\tau)=J(S,(\Gamma,x:\beta),e) \\
    &\text{and } \beta \text{ is fresh} \\
    \\
    J(S,\Gamma,\text{let }x=e_1\text{ in }e_2) =& (S_2,\tau_2) \\
    &\text{where } (S_1,\tau_1)=J(S,\Gamma,e_1) \\
    &\text{and } (S_2,\tau_2)=J(S_1,(\Gamma,x:(\bigwedge\alpha_1,...,\alpha_n.\tau_1)),e_2) \\
    &\text{and } \{\alpha_1,...,\alpha_n\}=ftv(S_2\tau_1)\backslash ftv(S_2\Gamma) \\
  \end{split}
\end{equation}
Funkcja pomocnicza $unify'(\tau,\tau',S)$ rozszerza zbiór substytucji S o substytucje wynikające z unifikacji $\tau$ z $\tau'$ pod kontekstem $S$. Np. $unify'(\alpha_1\rightarrow\alpha_2,B\rightarrow\alpha_3,S) = \{(\alpha_1,B), (\alpha_2,\alpha_3)\}$

\chapter{Kompilacja dopasowania do wzorca (ang. \emph{pattern matching})}
\section{Motywacja}
Wykorzystywany algorytm jest odrobinę inny od algorytmów opisanych w literaturze. Bierzemy pod uwagę następujące obserwacje:
\begin{itemize}
  \item Część algorytmów w literaturze w celu uniknięcia wykładniczego wzrostu ilości wygenerowanego kodu, generuje zbędne testy \cite{Augustsson__1985}.
  \item Wykładniczy wzrost jednak nie występuje w praktyce \cite{Scott__Ramsey__2000}.
  \item Najlepszą praktyką więc wydało nam się by nigdy nie generować niepotrzebnych sprawdzeń i spróbować uniknąć duplikacji kodu używając heurystyki tak jak \cite{Maranget__2008}.
  \item Literatura udowadnia, że w przypadku kodu napisanego w praktyce, różne algorytmy generują prawie identyczny kod \cite{Scott__Ramsey__2000, Maranget__2008}.
\end{itemize}
Naszą metodą więc jest, aby: (1) zawsze skupiać się na przypasowaniu pierwszego przypadku, by uniknąć niepotrzebnych testów i (2) zachłannie spróbować zminimalizować duplikację przy użyciu heurystyki.

\section{Kompilacja na przykładzie}
Naszym celem jest kompilacja poniższego dopasowania do wzorca w języku ML na drzewo decyzyjne.

\begin{align*}
   & \ \text{match}\ \alpha\ \text{with}                       \\
   & |\ \text{Add}(\text{Zero}, \text{Zero}) & \rightarrow e_1 \\
   & |\ \text{Mul}(\text{Zero}, x)           & \rightarrow e_2 \\
   & |\ \text{Add}(\text{Succ}(x), y)        & \rightarrow e_3 \\
   & |\ \text{Mul}(x, \text{Zero})           & \rightarrow e_4 \\
   & |\ \text{Mul}(\text{Add}(x,y), z)       & \rightarrow e_5 \\
   & |\ \text{Add}(x,\text{Zero})            & \rightarrow e_6 \\
   & |\ x                                    & \rightarrow e_7
\end{align*}
Powyższe wyrażenie możemy przedstawić jako listę równań.
\begin{align*}
   & |\ \alpha = \text{Add}(\text{Zero}, \text{Zero}) & \rightarrow e_1 \\
   & |\ \alpha = \text{Mul}(\text{Zero}, x)           & \rightarrow e_2 \\
   & |\ \alpha = \text{Add}(\text{Succ}(x), y)        & \rightarrow e_3 \\
   & |\ \alpha = \text{Mul}(x, \text{Zero})           & \rightarrow e_4 \\
   & |\ \alpha = \text{Mul}(\text{Add}(x,y), z)       & \rightarrow e_5 \\
   & |\ \alpha = \text{Add}(x,\text{Zero})            & \rightarrow e_6 \\
   & |\ \alpha = x                                    & \rightarrow e_7
\end{align*}
Nasz algorytm będzie otrzymywał taką listę równań i zwracał drzewo w którym każdy wierzchołek będzie dopasowaniem do jednego konstruktora.
\begin{align*}
   & \ \text{match}\ \alpha\ \text{with}                 \\
   & |\  \text{C}(a_1,..., a_n)          & \rightarrow A \\
   & |\ \_                               & \rightarrow B \\
\end{align*}
Zaczniemy od pierwszego równania i porównania z konstruktorem \lstinline$Add$.
\begin{align*}
   & \ \text{match}\ \alpha\ \text{with}                 \\
   & |\  \text{Add}(a_1, a_2)            & \rightarrow A \\
   & |\ \_                               & \rightarrow B \\
\end{align*}
Porównanie to rozbija cały problem na pod problemy:

Następujący pod problemem dla A:
\begin{align*}
   & |\ \alpha_1 = \text{Zero}, \alpha_2 = \text{Zero} & \rightarrow e_1 \\
   & |\ \alpha_1 = \text{Succ}(x), \alpha_2 = y        & \rightarrow e_3 \\
   & |\ \alpha_1 = x, \alpha_2 = \text{Zero}           & \rightarrow e_6 \\
   & |\ \alpha = x                                     & \rightarrow e_7
\end{align*}
Oraz pod problemem dla B:
\begin{align*}
   & |\ \alpha = \text{Mul}(\text{Zero}, x)     & \rightarrow e_2 \\
   & |\ \alpha = \text{Mul}(x, \text{Zero})     & \rightarrow e_4 \\
   & |\ \alpha = \text{Mul}(\text{Add}(x,y), z) & \rightarrow e_5 \\
   & |\ \alpha = x                              & \rightarrow e_7
\end{align*}
Wyrażenia takie jak $\alpha_2=y$ to przypisanie do zmiennej, które odbywa się dopiero po dopasowaniu do wzorca, dlatego, możemy przenieść je na prawą stronę. Pod problem A po tym uproszczeniu wygląda następująco:

\begin{align*}
   & |\ \alpha_1 = \text{Zero}, \alpha_2 = \text{Zero} &  & \rightarrow e_1                                     \\
   & |\ \alpha_1 = \text{Succ}(x)                      &  & \rightarrow\text{let } y = \alpha_2 \text{ in }e_3  \\
   & |\ \alpha_2 = \text{Zero}                         &  & \rightarrow\text{let } x = \alpha_1 \text{ in } e_6 \\
   & |\                                                &  & \rightarrow\text{let } x = \alpha \text{ in } e_7
\end{align*}
Następnie możemy kontynuować algorytm przez sprawdzenie $\alpha_1=\text{Zero}$:
\begin{align*}
   & \ \text{match}\ \alpha_1\ \text{with}                 \\
   & |\  \text{Zero}                       & \rightarrow C \\
   & |\ \_                                 & \rightarrow D \\
\end{align*}
I kontynuować rekursywnie dla C i D.
\section{Generalizacja algorytmu}
Mając listę równań, wykonujemy następującą listę kroków:
\begin{itemize}
  \item Równania $\alpha=y$ przenosimy na prawą stronę, aby pozostać z listą równań testujących konstruktory.
  \item Wybieramy któreś z równań $\alpha=\text{C}(\delta_1,...,\delta_2)$
  \item Generujemy następujące wyrażenie:
        \begin{align*}
           & \ \text{match}\ \alpha\ \text{with}                 \\
           & |\  \text{C}(a_1,..., a_n)          & \rightarrow A \\
           & |\ \_                               & \rightarrow B
        \end{align*}
  \item Tworzymy dwa pod problemy, iterując przez równania w następujący sposób:
        \begin{itemize}
          \item Jeżeli wyrażenie zawiera równanie $\alpha=\text{C}(\delta_1,..., \delta_n),...,\Gamma$.

                Rozszerzamy wyrażenie tworząc nowe zmienne $\alpha_1=\delta_1,...,\alpha_n=\delta_n,...,\Gamma$ i dodajemy je do A.
          \item Jeżeli wyrażenie zawiera równanie $\alpha=\text{D}(a_1,..., a_n),...,\Gamma$ gdzie $\text{D}\ne\text{C}$.

                Dodajemy równanie do B.

          \item Jeżeli wyrażenie zawiera równanie $\alpha$.

                Dodajemy je do A i B.
        \end{itemize}
  \item rekursywnie wywołujemy algorytm dla A i B.
\end{itemize}
Rekursja kończy się kiedy:
\begin{itemize}
  \item lista jest pusta --- generujemy błąd braku pełnego dopasowania,
  \item pierwsze z wyrażeń nie ma żadnych równań (udało nam się dokonać dopasowania) --- po prostu zwracamy $e_1$.
\end{itemize}


\chapter{ReScript --- język realizujący podobne zadania}
OCaml jest funkcyjnym językiem programowania kompilowanym na kod maszynowy.
ReScript jest to fork OCaml generujący kod w języku JavaScript, skupiający się na łatwej możliwości wdrożenia i adaptacji przez deweloperów korzystających z języka JavaScript.
Język ten posiada wiele funkcji, które pojawiają się w naszym języku --- między innymi generyczne typy danych, unie z dyskryminatorem, dopasowania do wzorca.

Przykład kodu w języku ReScript:
\begin{lstlisting}
module Button = {
  @react.component
  let make = (~count: int) => {
    let times = switch count {
    | 1 => "once"
    | 2 => "twice"
    | n => Belt.Int.toString(n) ++ " times"
    }
    let msg = "Click me " ++ times

    <button> {msg->React.string} </button>
  }
}
\end{lstlisting}
\chapter{Założenia i priorytety opracowanej aplikacji}
Tworząc aplikację, chcieliśmy, by kompilator posiadał podstawowe typy danych (liczba, napis, wartość logiczna), kilka typów generycznych (funkcja, tablica), typ \lstinline$Option$ oraz możliwość tworzenia własnych typów.
Dodatkowo nie powinno być potrzeby podawania typów zmiennych w większości przypadków, kompilator sam powinien wykrywać typy zmiennych na podstawie ich użycia.


Język poza zmiennymi, potrzebuje możliwości wykonywania operacji na danych, dlatego ważne było dla nas, by zaimplementować operatory binarne oraz unarne. Operatory te miały też spełniać ważną rolą w trakcie inferencji typów. W języku JavaScript operator `+' może być wykorzystywany do dodawania liczb jak i konkatenacji napisów, ważne więc było by stworzyć dwa oddzielne operatory.



Porównanie prymitywnych typów danych i często wykonywanych operacji z ich odpowiednikami w języku JavaScript pokazane jest w tabeli \ref{tab1}.

\begin{table}[h!]
  \begin{tabular}{c c c}
    Co                    & Przykład                                   & wyjście w języku JavaScript                 \\
    \hline
    Ciąg znaków           & \lstinline$'Hello'$                        & \lstinline$"Hello"$                         \\
    \hline
    Konkatenacja          & \lstinline$'Hello '++ 'World'$             & \lstinline$"Hello " + "World"$              \\
    \hline
    Liczby                & \lstinline$23$, \lstinline$-23.0$          & \lstinline$23$, \lstinline$-23.0$           \\
    \hline
    Dodawanie/Odejmowanie & \lstinline$6 + 2.0 - 4$                    & \lstinline$6 + 2.0 - 4$                     \\
    \hline
    Dzielenie/Mnożenie    & \lstinline$2 / 23 * 1$                     & \lstinline$2 / 23 * 1$                      \\
    \hline
    Modulo                & \lstinline$12 % 3$                         & \lstinline$12 % 3$                          \\
    \hline
    Dzielenie całkowite   & \lstinline$5 // 2$                         & \lstinline$Math.floor(5 / 2)$               \\
    \hline
    Konkatenacja tablic   & \lstinline$[1] | [3, 4]$                   & \lstinline$[1].concat([3, 4]) $             \\

    \hline
    Porównywanie liczb    & \lstinline$>$,\lstinline$<$,\lstinline$<>$ & \lstinline$>$,\lstinline$<$,\lstinline$!==$ \\
    \hline
    Równość/Nierówność    & \lstinline$==$, \lstinline$!=$             & \lstinline$===$, \lstinline$!==$            \\
    \hline
    Zmienne logiczne      & \lstinline$True$, \lstinline$False$        & \lstinline$true$, \lstinline$false$         \\
    \hline
  \end{tabular}
  \caption{Porównanie}
  \label{tab1}
\end{table}


\newpage
Chcieliśmy również, by funkcje wieloargumentowe kompilowane były jako funkcje jednoargumentowe zwracające kolejne funkcje, co pozwala na wywoływanie funkcji z niepełną liczbą argumentów w celu zwrócenia funkcji przyjmującej resztę argumentów (ang. \emph{currying}).


\lstinputlisting[firstline=15]{examples/currying.uwu}
\newpage

\lstinputlisting[firstline=15]{examples/currying.uwu.js}

\newpage
Jednym z ważniejszych elementów każdego języka jest możliwość wykonywania różnego zbioru instrukcji warunkowo. W tym celu język powinien posiadać instrukcję \lstinline$if$ oraz \lstinline$case$. Instrukcja \lstinline$case$ wykonywać ma odpowiedni zbiór instrukcji, zależnie do którego wzorca dopasowane zostaną wprowadzone dane. Kompilator, powinien ostrzegać, jeżeli istnieje możliwość niedopasowania danych do żadnego z wzorców.

\begin{itemize}
  
  \item Przykład --- funkcja łącząca dwie posortowane tablice
        \lstinputlisting[firstline=25]{examples/merge.uwu}\newpage
        \lstinputlisting[firstline=19]{examples/merge.uwu.js}
\end{itemize}

\newpage
Kolejnym dość ważnym elementem języka jest brak wyrażenia `return', które jest wykorzystywane do zwrócenia wartości z funkcji. Zamiast tego każdy blok instrukcji powinien zwracać ostatnie wyrażenie.



\lstinputlisting[firstline=15]{examples/return.uwu}
\lstinputlisting[firstline=15]{examples/return.uwu.js}

\section{Opis formalny składni języka}

\allowdisplaybreaks
\begin{align*}
  S'\ ::                              & = \text{program}                                                                                                                                                                                                          \\
  \text{program}\ ::                  & = \text{NEWLINE\_optional}\ \text{do\_exprs\_optional}                                                                                                                                                                    \\
  \text{NEWLINE\_optional}\ ::        & = \text{NEWLINE}                                                                                                                                                                                                          \\
                                      & |\ \ \ \text{<empty>}                                                                                                                                                                                                     \\
  \text{do\_exprs\_optional}\ ::      & = \text{do\_exprs}                                                                                                                                                                                                        \\
                                      & |\ \ \ \text{<empty>}                                                                                                                                                                                                     \\
  \text{do\_exprs}\ ::                & = \text{expr}\ \text{NEWLINE}\ \text{do\_exprs}                                                                                                                                                                           \\
                                      & |\ \ \ \text{expr}\ \text{NEWLINE\_optional}                                                                                                                                                                              \\
  \text{expr}\ ::                     & = \text{let}                                                                                                                                                                                                              \\
                                      & |\ \ \ (\ \text{expr}\ )\ \ [precedence=left,\ level=7]                                                                                                                                                                   \\
                                      & |\ \ \ \text{enum}                                                                                                                                                                                                        \\
                                      & |\ \ \ \text{variant\_call}                                                                                                                                                                                               \\
                                      & |\ \ \ \text{case\_of}                                                                                                                                                                                                    \\
                                      & |\ \ \ \text{def\_expr}                                                                                                                                                                                                   \\
                                      & |\ \ \ \text{binary\_expr}                                                                                                                                                                                                \\
                                      & |\ \ \ \text{call}                                                                                                                                                                                                        \\
                                      & |\ \ \ \text{literal}                                                                                                                                                                                                     \\
                                      & |\ \ \ \text{do}                                                                                                                                                                                                          \\
                                      & |\ \ \ \text{array}                                                                                                                                                                                                       \\
                                      & |\ \ \ \text{identifier}                                                                                                                                                                                                  \\
                                      & |\ \ \ -\ \text{expr}\ \ [precedence=right,\ level=6]                                                                                                                                                                     \\
                                      & |\ \ \ \text{if\_expr}                                                                                                                                                                                                    \\
                                      & |\ \ \ \text{external}                                                                                                                                                                                                    \\
  \text{external}\ ::                 & = \text{EXTERNAL}                                                                                                                                                                                                         \\
  \text{binary\_expr}\ ::             & = \text{expr}\ >\ \text{expr}\ \ [precedence=left,\ level=3]                                                                                                                                                              \\
                                      & |\ \ \ \text{expr}\ \text{INT\_DIV}\ \text{expr}\ \ [precedence=left,\ level=5]                                                                                                                                           \\
                                      & |\ \ \ \text{expr}\ /\ \text{expr}\ \ [precedence=left,\ level=5]                                                                                                                                                         \\
                                      & |\ \ \ \text{expr}\ \%\ \text{expr}\ \ [precedence=left,\ level=5]                                                                                                                                                        \\
                                      & |\ \ \ \text{expr}\ -\ \text{expr}\ \ [precedence=left,\ level=4]                                                                                                                                                         \\
                                      & |\ \ \ \text{expr}\ \text{EQUAL}\ \text{expr}\ \ [precedence=left,\ level=2]                                                                                                                                              \\
                                      & |\ \ \ \text{expr}\ \text{CONCAT}\ \text{expr}\ \ [precedence=left,\ level=4]                                                                                                                                             \\
                                      & |\ \ \ \text{expr}\ +\ \text{expr}\ \ [precedence=left,\ level=4]                                                                                                                                                         \\
                                      & |\ \ \ \text{expr}\ \text{NOT\_EQUAL}\ \text{expr}\ \ [precedence=left,\ level=2]                                                                                                                                         \\
                                      & |\ \ \ \text{expr}\ <\ \text{expr}\ \ [precedence=left,\ level=3]                                                                                                                                                         \\
                                      & |\ \ \ \text{expr}\ |\ \text{expr}\ \ [precedence=left,\ level=4]                                                                                                                                                         \\
                                      & |\ \ \ \text{expr}\ *\ \text{expr}\ \ [precedence=left,\ level=5]                                                                                                                                                         \\
  \text{do}\ ::                       & = \text{DO}\ \text{type\_optional}\ \text{NEWLINE\_optional}\ \text{do\_exprs\_optional}\ \text{END}                                                                                                                      \\
  \text{type\_optional}\ ::           & = :\ \text{type}                                                                                                                                                                                                          \\
                                      & |\ \ \ \text{<empty>}                                                                                                                                                                                                     \\
  \text{block\_statement}\ ::         & = \text{NEWLINE\_optional}\ \text{do\_exprs\_optional}                                                                                                                                                                    \\
  \text{def\_expr}\ ::                & = \text{DEF}\ \text{identifier}\ <\ \text{type\_identifier}\ \text{type\_identifier\_repeat}\ > \\ & (\ \text{NEWLINE\_optional}\ \text{params\_optional}\ )\ \text{type\_optional}\ \text{do} \\ & [precedence=left,\ level=7] \\
                                      & |\ \ \ \text{DEF}\ \text{identifier}\ (\ \text{NEWLINE\_optional}\ \text{params\_optional}\ ) \\ & \text{type\_optional}\ \text{do}\ \ [precedence=left,\ level=7]                                                            \\
  \text{params\_optional}\ ::         & = \text{<empty>}                                                                                                                                                                                                          \\
                                      & |\ \ \ \text{params}                                                                                                                                                                                                      \\
  \text{type\_identifier\_repeat}\ :: & = \text{type\_identifier\_items}                                                                                                                                                                                          \\
                                      & |\ \ \ \text{<empty>}                                                                                                                                                                                                     \\
  \text{type\_identifier\_items}\ ::  & = \text{type\_identifier\_item}                                                                                                                                                                                           \\
                                      & |\ \ \ \text{type\_identifier\_items}\ \text{type\_identifier\_item}                                                                                                                                                      \\
  \text{type\_identifier\_item}\ ::   & = ,\ \text{type\_identifier}                                                                                                                                                                                              \\
  \text{params}\ ::                   & = \text{params}\ ,\ \text{NEWLINE\_optional}\ \text{param}\ \text{NEWLINE\_optional}                                                                                                                                      \\
                                      & |\ \ \ \text{param}\ \text{NEWLINE\_optional}                                                                                                                                                                             \\
  \text{type}\ ::                     & = \text{type\_identifier}                                                                                                                                                                                                 \\
                                      & |\ \ \ \text{type\_identifier}\ <\ \text{type}\ \text{type\_repeat}\ >\ \ [precedence=left,\ level=3]                                                                                                                     \\
  \text{type\_repeat}\ ::             & = \text{type\_items}                                                                                                                                                                                                      \\
                                      & |\ \ \ \text{<empty>}                                                                                                                                                                                                     \\
  \text{type\_items}\ ::              & = \text{type\_items}\ \text{type\_item}                                                                                                                                                                                   \\
                                      & |\ \ \ \text{type\_item}                                                                                                                                                                                                  \\
  \text{type\_item}\ ::               & = ,\ \text{type}                                                                                                                                                                                                          \\
  \text{enum}\ ::                     & = \text{ENUM}\ \text{type\_identifier}\ <\ \text{type\_identifier}\ \text{type\_identifier\_repeat}\ > \\ &  {\ \text{NEWLINE\_optional}\ \text{variants\_optional}\ }                                                         \\
                                      & |\ \ \ \text{ENUM}\ \text{type\_identifier}\ {\ \text{NEWLINE\_optional}\ \text{variants\_optional}\ }                                                                                                                    \\
  \text{variants\_optional}\ ::       & = \text{variants}                                                                                                                                                                                                         \\
                                      & |\ \ \ \text{<empty>}                                                                                                                                                                                                     \\
  \text{variants}\ ::                 & = \text{variant}\ \text{NEWLINE\_optional}                                                                                                                                                                                \\
                                      & |\ \ \ \text{variants}\ \text{variant}\ \text{NEWLINE\_optional}                                                                                                                                                          \\
  \text{variant}\ ::                  & = \text{type\_identifier}                                                                                                                                                                                                 \\
                                      & |\ \ \ \text{type\_identifier}\ (\ \text{type}\ \text{type\_repeat}\ )\ \ [precedence=left,\ level=7]                                                                                                                     \\
  \text{param}\ ::                    & = \text{identifier}\ \text{type\_optional}                                                                                                                                                                                \\
  \text{if\_expr}\ ::                 & = \text{IF}\ \text{expr}\ \text{THEN}\ \text{type\_optional}\ \text{block\_statement}\ \text{or\_else\_optional}\ \text{END}                                                                                              \\
  \text{or\_else\_optional}\ ::       & = \text{or\_else}                                                                                                                                                                                                         \\
                                      & |\ \ \ \text{<empty>}                                                                                                                                                                                                     \\
  \text{or\_else}\ ::                 & = \text{ELSE}\ \text{block\_statement}                                                                                                                                                                                    \\
                                      & |\ \ \ \text{ELIF}\ \text{expr}\ \text{THEN}\ \text{block\_statement}\ \text{or\_else\_optional}                                                                                                                          \\
  \text{case\_of}\ ::                 & = \text{CASE}\ \text{expr}\ \text{OF}\ \text{NEWLINE\_optional}\ \text{cases\_optional}\ \text{END}                                                                                                                       \\
  \text{cases\_optional}\ ::          & = \text{cases}                                                                                                                                                                                                            \\
                                      & |\ \ \ \text{<empty>}                                                                                                                                                                                                     \\
  \text{cases}\ ::                    & = \text{pattern}\ \text{do}\ \text{NEWLINE\_optional}                                                                                                                                                                     \\
                                      & |\ \ \ \text{cases}\ \text{pattern}\ \text{do}\ \text{NEWLINE\_optional}                                                                                                                                                  \\
  \text{pattern}\ ::                  & = \text{match\_as}                                                                                                                                                                                                        \\
                                      & |\ \ \ \text{match\_variant}                                                                                                                                                                                              \\
  \text{match\_as}\ ::                & = \text{identifier}                                                                                                                                                                                                       \\
  \text{match\_variant}\ ::           & = \text{type\_identifier}                                                                                                                                                                                                 \\
                                      & |\ \ \ \text{type\_identifier}\ (\ \text{NEWLINE\_optional}\ \text{patterns\_optional}\ ) \\ & [precedence=left,\ level=7]                                                                                                  \\
  \text{patterns\_optional}\ ::       & = \text{<empty>}                                                                                                                                                                                                          \\
                                      & |\ \ \ \text{patterns}                                                                                                                                                                                                    \\
  \text{patterns}\ ::                 & = \text{patterns}\ ,\ \text{NEWLINE\_optional}\ \text{pattern}\ \text{NEWLINE\_optional}                                                                                                                                  \\
                                      & |\ \ \ \text{pattern}\ \text{NEWLINE\_optional}                                                                                                                                                                           \\
  \text{array}\ ::                    & = [\ \text{NEWLINE\_optional}\ \text{exprs\_optional}\ ]                                                                                                                                                                  \\
  \text{exprs\_optional}\ ::          & = \text{exprs}                                                                                                                                                                                                            \\
                                      & |\ \ \ \text{<empty>}                                                                                                                                                                                                     \\
  \text{call}\ ::                     & = \text{expr}\ (\ \text{NEWLINE\_optional}\ \text{exprs\_optional}\ )\\ & [precedence=left,\ level=7]                                                                                                                      \\
  \text{variant\_call}\ ::            & = \text{type\_identifier}\ (\ \text{NEWLINE\_optional}\ \text{exprs\_optional}\ ) \\ & [precedence=left,\ level=7]                                                                                                          \\
  \text{exprs}\ ::                    & = \text{exprs}\ ,\ \text{NEWLINE\_optional}\ \text{expr}\ \text{NEWLINE\_optional}                                                                                                                                        \\
                                      & |\ \ \ \text{expr}\ \text{NEWLINE\_optional}                                                                                                                                                                              \\
  \text{identifier}\ ::               & = \text{IDENTIFIER}                                                                                                                                                                                                       \\
  \text{type\_identifier}\ ::         & = \text{TYPE\_IDENTIFIER}                                                                                                                                                                                                 \\
  \text{let}\ ::                      & = \text{identifier}\ \text{type\_optional}\ =\ \text{expr}\ \ [precedence=left,\ level=1]                                                                                                                                 \\
  \text{literal}\ ::                  & = \text{NUMBER}                                                                                                                                                                                                           \\
                                      & |\ \ \ \text{STRING}
\end{align*}
\chapter{Narzędzia}
\section{Język Python}
Do implementacji naszego kompilatora postanowiliśmy wykorzystać język Python w wersji 3.10, ze względu na jego dynamiczność.
W tej wersji języka pojawił się również pattern matching, który znacząco ułatwia pracę z drzewem syntaktycznym.
\section{Parsowanie i tokenizowanie przy użyciu biblioteki sly}
Biblioteka sly, jest implementacją narzędzi lex i yacc w języku Python, wykorzystywanych do tworzenia parserów i kompilatorów. Tworzenie leksera i parsera jest bardzo proste.
W naszym języku korzystaliśmy z wersji 0.4.

\subsection{Lekser}
Tokeny są tworzone przy pomocy wyrażeń regularnych.
\begin{lstlisting}
import sly
class Lex(sly.Lexer):
  ID = r"\w+"
  NUM = r"\d+"
\end{lstlisting}
Biblioteka udostępnia specjalną składnie do tworzenia tokenów, w przypadku gdy są już one opisane przez inny token.
\begin{lstlisting}
  ID["and"] = AND
\end{lstlisting}
Pojedyncze znaki można ignorować, poprzez ustawienie pola `ignore'.
Dodatkowo ignorowane są też tokeny zaczynające się od `ignore'.
\begin{lstlisting}
  ignore = " \t"
  ignore_comm = r"\#.*"
\end{lstlisting}
Możemy też stworzyć tokeny o typie równym ich wartości, o ile składają się tylko z jednego znaku.
\begin{lstlisting}
  literals = {"(", ")"}
\end{lstlisting}

\subsection{Parser}
W przypadku parsera każda reguła jest implementowana jako metoda, pod której argumentem mamy dostęp do tokenów i wartości zwróconych z innych metod występujących w składni danej reguły.
\begin{lstlisting}
  import sly
  class Parser(sly.Parser):
  tokens = Lex.tokens
  
  @_("NUM")
  def expr(self, p):
  return p[0] # Lub p.ID
  
  @_("'(' expr AND expr ')'")
  def expr(self, p):
  return p.expr0 and p.expr1
\end{lstlisting}
Powyższy parser pozwala na opisanie wyrażeń logicznych typu: \lstinline{(1 and 0) and 4}.
\section{Środowisko nodejs do uruchomienia skompilowanego kodu}
JavaScript jest językiem programowania wykorzystywanym w przeglądarkach internetowych. Do uruchomienia skompilowanego kodu używali będziemy jednak środowiska nodejs. Pozwoli to na szybkie i wygodne testowanie wygenerowanego kodu. Po zainstalowaniu środowiska i skompilowaniu pliku `index.uwu' otrzymamy plik `index.uwu.js', który możemy uruchomić w terminalu komendą `node index.uwu.js'.

\chapter{Implementacja}
\section{Lekser}
Nasz lekser implementował będzie poniższy zbiór tokenów, warto zauważyć, że identyfikatory zaczynające się z dużej litery są identyfikatorami typów.
\lstinputlisting[firstline=75, lastline=94]{parser.py}
\newpage
Nasz lekser zajmował się również będzie zwracaniem tokena dla znaku nowej linii

\lstinputlisting[firstline=99, lastline=102]{parser.py}
Lekser ignorował będzie tokeny komentarza, które zaczynają się od znaku `\#'. Oraz znaki tabulacji i spacji.
\lstinputlisting[firstline=96, lastline=97]{parser.py}

Poza tym nasz lekser zwracał będzie poniższy zbiór tokenów
\lstinputlisting[firstline=55, lastline=74]{parser.py}
\newpage
\section{Parser}
Implementacja parsera jest bardzo prosta, każda z metod zajmuje jedynie linijkę, gdzie zwracane jest odpowiedne wyrażenie drzewa syntaktycznego.

\lstinputlisting[firstline=188, lastline=195]{parser.py}
W przypadku zbiorów wyrażeń zwracane są listy.
\lstinputlisting[firstline=369, lastline=375]{parser.py}

\section{Drzewo decyzyjne}



Dopasowanie do wzorca zamieniane jest w drzewo decyzyjne przy pomocy rekurencyjnej funkcji.
Rekursja ma dwa podstawowe przypadki:
\begin{itemize}
  \item lista przypadków jest pusta, więc generujemy pustą gałąź końcową\newpage
  \item pierwszy przypadek, nie ma już więcej wzorów, więc zwracamy gałąź końcową z blokiem.
\end{itemize}
\lstinputlisting[firstline=72, lastline=80]{case_tree.py}
W innym przypadku wybieramy wzorzec przy pomocy heurystyki
\lstinputlisting[firstline=81, lastline=88]{case_tree.py}

Następnie tworzymy dwa pod problemy \lstinline{yes} i \lstinline{no} iterując przez wszystkie przypadki. Dla każdego z nich robimy jedną z trzech rzeczy:
\begin{itemize}
  \item Przypadek nie zawiera wzorca, więc dodajemy go do \lstinline{yes} i \lstinline{no}
        \lstinputlisting[firstline=90, lastline=95]{case_tree.py}\newpage
  \item Przypadek zawiera szukany wzorzec, więc dodajemy go do \lstinline{yes}
        \lstinputlisting[firstline=97, lastline=108]{case_tree.py}
  \item Przypadek zawiera wzorzec, więc dodajemy go do \lstinline{no}
        \lstinputlisting[firstline=110, lastline=111]{case_tree.py}
\end{itemize}

Rekursywnie generujemy kod dla \lstinline{yes} i \lstinline{no} i zwracamy gałąź decyzyjną
\lstinputlisting[firstline=116, lastline=118]{case_tree.py}\newpage
\section{Inferencja typów}
\subsection{Reprezentacja środowiska}
Implementację inferencji typów zaczynamy przez stworzenie zmiennego typu, który będzie reprezentowany przez unikalny identyfikator.
\lstinputlisting[firstline=28, lastline=34]{algorithm_j.py}
Substytucje to pary zmiennych i typów
\lstinputlisting[firstline=25, lastline=25]{algorithm_j.py}
Jednym z argumentów algorytmu J jest środowisko, w naszej implementacji reprezentowane jest one przez zmienną \lstinline$Context$, będący słownikiem identyfikatorów i schematów,
\lstinputlisting[firstline=26, lastline=26]{algorithm_j.py}
gdzie schemat zawiera informację o typie oraz listę występujących w nim zmiennych typów

\lstinputlisting[firstline=12, lastline=16]{algorithm_j.py}
\newpage
\subsection{Aplikowanie substytucji}
Tworzymy funkcję aplikującą substytucje na typie.

Przykład: dla $subt=\{a:Num\}$ i $ty=a\rightarrow b$ funkcja zwraca $Num\rightarrow b$
\lstinputlisting[firstline=37, lastline=46]{algorithm_j.py}

Tworzymy funkcję, unifikującą dwa typy

\lstinputlisting[firstline=95, lastline=112]{algorithm_j.py}\newpage
wraz z funkcją generującą substytucje w przypadku unifikacji zmiennego typu
\lstinputlisting[firstline=115, lastline=124]{algorithm_j.py}
Teraz zaczynamy implementację algorytmu J.

\subsection{Literały}
W przypadku literałów typ jest oczywisty.

\lstinputlisting[firstline=164, lastline=171]{algorithm_j.py}
\subsection{Identyfikatory}
W przypadku identyfikatorów musimy zastąpić występujące w nich zmienne typy nowymi zmiennymi typami.
\lstinputlisting[firstline=172, lastline=173]{algorithm_j.py}\newpage
\subsection{Bloki wyrażeń}
W przypadku bloku wyrażeń inferujemy typ każdego z nich i zwracamy ostatni typ.
\lstinputlisting[firstline=185, lastline=192]{algorithm_j.py}

\subsection{Operatory binarne}
Implementacje operatorów binarnych są bardzo podobne.

Na przykład operator \lstinline{|} służący do konkatenacji dwóch list, oczekuje by wyrażenie z lewej i prawej strony były listami tego samego typu i zwraca nową listę tego właśnie typu.
\lstinputlisting[firstline=257, lastline=263]{algorithm_j.py}
\subsection{Wywołania funkcji}
W przypadku wywołania funkcji musimy zaimplementować currying.

Przykład: $J(fn)=Num\rightarrow Str\rightarrow Unit\rightarrow Arr<Str>\\ J(args)=[Num,Str]$
\begin{itemize}
  \item typy argumentów zbieramy w odwrotnej kolejności \lstinline{ty_args=[Str,Num]}
  \item Tworzymy nowy zmienny typ $ty=\alpha$
  \item Następnie przy użyciu funkcji \lstinline{reduce_args} aplikujemy \lstinline{ty_args} na typie $\alpha$ co tworzy typ $tmp=Num\rightarrow Str\rightarrow \alpha$
  \item Unifikujemy typy $tmp$ i $J(fn)$ co tworzy substytucję $\{\alpha: Unit\rightarrow Arr<Str>\}$
  \item I zwracamy $\alpha$
\end{itemize}
\lstinputlisting[firstline=323, lastline=335]{algorithm_j.py}

\subsection{Wyrażenia warunkowe}
W przypadku wyrażeń warunkowych musimy, sprawdzić, czy warunek jest typu \lstinline{Bool} i czy, typy zwracane z każdej gałęzi są takie same, po czym zwracamy ten typ.
\lstinputlisting[firstline=361, lastline=373]{algorithm_j.py}
\newpage
\subsection{Definicje funkcji}
W przypadku definicji funkcji musimy upewnić się że typy generyczne, są przypisywane do środowiska. Musimy sprawdzić, czy typ zwracany z funkcji jest przypisywalny do zadeklarowanego typu oraz zapisać funkcję do środowiska.

\lstinputlisting[firstline=336, lastline=360]{algorithm_j.py}

\section{Dopasowanie do wzorca}
W trakcie dopasowania do wzorca, musimy upewnić się, że konstruktory, posiadają odpowiednią liczbę argumentów. Dodatkowo przeprowadzać będziemy sprawdzanie czy wyrażenie \lstinline$case$ jest wyczerpujące --- czy przewiduje wszystkie przypadki. W tym celu funkcja przyjmuje argument \lstinline$o_alts$ będący bazą zmiennych i ich konstruktorów.
\newpage
W przypadku pustej gałęzi końcowej, sprawdzamy, czy każda z list jest pusta i wyrzucamy błąd, jeżeli jest.

\lstinputlisting[firstline=508, lastline=520]{algorithm_j.py}

W przypadku gałęzi decyzyjnej inferujemy typ zmiennej i sprawdzanego konstruktora
\lstinputlisting[firstline=521, lastline=527]{algorithm_j.py}
Następne dwa kroki dopełniają nasze sprawdzenie czy wyrażenie jest wyczerpujące. Wpierw uzupełniamy naszą bazę konstruktorów przy użyciu funkcji \lstinline{alternatives} zwracającej listę wszystkich konstruktorów dla danego typu.
Następnie usuwamy z bazy konstruktorów konstruktor do którego odnosi się nasza gałąź decyzyjna.
\lstinputlisting[firstline=530, lastline=534]{algorithm_j.py}
\newpage
Kolejna część inferuje typy zmiennych dla każdego z argumentów konstruktora.
Oraz tworzy dla nich zmienne w środowisku.
\lstinputlisting[firstline=536, lastline=561]{algorithm_j.py}
\newpage
Reszta funkcji to sprawdzenie, czy typy zwracane z bloków są takie same.
\lstinputlisting[firstline=564, lastline=578]{algorithm_j.py}


\section{Windowanie (ang. \emph{Hoisting})}
Ze względu, na to, że deklaracje zmiennych w języku JavaScript, np. \lstinline{const x = 1} w przeciwieństwie do naszego języka nie zwracają przypisywanej do identyfikatora wartości, wyrażenia typu \lstinline{f(a = b = c)} muszą być przekonwertowane do
\begin{lstlisting}
  b=c
  a=b
  f(a)
\end{lstlisting}
W tym celu zaimplementowaliśmy funkcję, która przyjmuje wyrażenie i zwraca, listę wyrażeń do przeniesienia wyżej oraz zmodyfikowane wyrażenie.

\newpage
W przypadku bloków wyrażeń, listy z wyrażeniami do windowania są łączone z listą wyrażeń danego bloku.
\lstinputlisting[firstline=46, lastline=56]{compile.py}
\lstinputlisting[firstline=13, lastline=21]{compile.py}

W przypadku deklaracji zmiennych i funkcji, dodajemy elementy do listy wyrażeń do windowania.
\lstinputlisting[firstline=62, lastline=72]{compile.py}
W każdym innym przypadku lista wyrażeń do windowania jest po prostu przepuszczana dalej.
\lstinputlisting[firstline=81, lastline=89]{compile.py}


\section{Kompilacja}
Kompilacja opiera się na jednej funkcji zamieniającej drzewo syntaktyczne na kod języka JavaScript w postaci napis.

\section{Literały}
Jak widać, dla literałów jest to dość trywialne.
\lstinputlisting[firstline=145, lastline=152]{compile.py}
\newpage
\subsection{Wyrażenia warunkowe}
Wyrażenia warunkowe wymagają kompilacji do postaci funkcji, gdyż w odróżnieniu od języka JavaScript, w naszym języku zwracają one wartość.
\lstinputlisting[firstline=170, lastline=171]{compile.py}

\subsection{Warianty}
Warianty przyjmują postać obiektów z dyskryminatorem
\lstinputlisting[firstline=187, lastline=190]{compile.py}

\subsection{Dopasowanie do wzorca}
W przypadku pustej gałęzi z blokiem kompilujemy blok.
W przypadku pustej gałęzi końcowej generujemy wyjątek.
\lstinputlisting[firstline=262, lastline=267]{compile.py}
\newpage
W przypadku gałęzi decyzyjnej generowany jest blok if sprawdzający zawartość zmiennej. Można też uniknąć generowania bloku else, w przypadku, gdy wygenerowany byłby wyjątek.
\lstinputlisting[firstline=268, lastline=284]{compile.py}

\chapter{Opis działania}
Po uruchomieniu komendą \lstinline{python3 main.py **/*.uwu} programu, program skompiluje wszystkie pliki kończące się rozszerzeniem `.uwu' i wygeneruje dla każdego z nich odpowiedni plik z rozszerzeniem `.js'.

\section{Co działa}
W programie udało się zaimplementować dużą część funkcjonalności potrzebnych do pisania faktycznych programów. Zabrakło jednak kilku początkowo planowanych funkcji: między innymi: rekursji, krotek, rekordów.
\section{Uwagi do działania}
\subsection{Obsługa błędów}
Błędy zwracane przez program nie są optymalne, nie zaimplementowaliśmy żadnej obsługi błędów w parserze. Błędy wynikające z inferencji typów, zwracają jedynie informacje o błędnych typach, nie o miejscu wystąpienia błędu. Wynika to z braku propagacji numerów linii i kolumn z parsera do drzewa syntaktycznego.
\subsection{Dopasowanie do wzorca}
W przypadku dopasowania do wzorca, kompilator powinien wyświetlić ostrzeżenie w momencie, gdy jedna ze ścieżek jest nieosiągalna.
\chapter*{Podsumowanie}
\addcontentsline{toc}{chapter}{Podsumowanie}
Udało nam się stworzyć kompilator generujący kod języka JavaScript. Zbadaliśmy problemy inferencji typów i dopasowania do wzorca. Zwróciliśmy uwagę na podobne rozwiązania. Zaimplementowaliśmy lekser oraz parser. Zaimplementowaliśmy typy podstawowe (liczby, ciągi znaków), oraz generyczne (funkcje, tablice) wraz z inferencją typów. Zaimplementowaliśmy również dopasowywanie danych do wzorca. Nasz kompilator cechuje się prostotą implementacji która daje możliwość szybkiego rozszerzania jego funkcjonalności w przyszłości.

\bibliographystyle{abbrv}

\bibliography{doc}
\addcontentsline{toc}{chapter}{Bibliografia}

\end{document}