Implementacja Języków Programowania

Jak Wytresować Smoka, czyli Warsztat z Podstaw Implementacji Języków Programowania

Rys. 1 Programista obłaskawiający kompilator.

Jako rzecze wielki mędrzec Piotr Fronczewski, aby wyruszyć w drużynę, należy zebrać drogę… czy jakoś tak.  
Nie inaczej jest z programowaniem — każdy aspirujący adept technik komputerowych wie, że aby stworzyć program komputerowy należy pierwej poznać jakiś język programowania. Nie każdy jednak wie, skąd te „magiczne” programistyczne narzędzia się biorą.

W zamierzchłej przeszłości, przez współczesnych zwanych Latami Pięćdziesiątymi, czarodziej McCarthy wykradł z Macierzy Zero — siedziby Cyfrowych Bogów — pierwszy język programowania, który nazwał LISP…

Oczywiście, jak można się domyślić, prowadzący niniejszy warsztat się zgrywa i kompilatory, maszyny wirtualne czy inne interpretery wcale nie są mistycznymi artefaktami bogów programowania ani nie ciągną się one — niczym żółwie ze znanej anegdotki — do samego spodu, a warsztat ten ma na celu przybliżyć ich historię oraz pozwolić zrozumieć przynajmniej podstawowe techniki ich implementacji.

Warsztaty będą prowadzone w formie wykładu mającego za zadanie przekazać słuchaczowi podstawową wiedzę z zakresu implementacji języków programowania, połączonego z segmentami praktycznymi pozwalającymi uczestnikom spróbować własnych sił w pisaniu prostego języka wykorzystując zdobytą właśnie wiedzę.

Zagadnienia

W części wykładowej prowadzący chciałby poruszyć przynajmniej następujące tematy:

• przedstawienie historii języków programowania od rachunku lambda, maszyny Turinga i kart drukowanych, poprzez Fortrana, LISPa, Cobola oraz Smalltalka aż po SMLa, Haskella i Idris, ze szczególnym uwzględnieniem technik implementacyjnych i nowatorskich rozwiązań które wpłynęły na powstające później języki,
• jak komputery „rozumieją” kod — gramatyki formalne, podział tekstu na leksemy (lekser), analiza składniowa (parsery), kombinatory parserów, maszyny stanów, drzewa składniowe (AST, Abstract Syntax Trees), składnie prefiksowe, infiksowe i postfiksowe, rozszerzalność składni za pomocą przekształceń AST (makra),
• interpretowanie (bądź redukcja) AST jako najprostszy sposób implementacji języka programowania, podstawowe zagadnienia semantyki języków, zakres leksykalny vs. zakres dynamiczny, tablica symboli.

W zależności od pozostałego czasu, chęci słuchaczy oraz wiedzy prowadzącego, będzie można pobieżnie omówić któreś z bardziej zaawansowanych technik implementacyjnych, takie jak — statyczna kompilacja, linkowanie i kompatybilność binarna, alokacja rejestrów i optymalizacje, maszyny wirtualne oparte o bajtkod i kompilatory JIT, automatyczne zarządzanie pamięcią (garbage collection), stos zwykły a stos spaghetti, domknięcia oraz kontynuacje, wykorzystanie typów do zapewnienia poprawności programu i emisji lepszego kodu wynikowego, cukier składniowy, desugaring i reprezentacje pośrednie.

W części praktycznej słuchacze będą mogli wykorzystać poznaną wiedzę aby zaimplementować język programowania będący uproszczoną wersją Scheme/LISPa, co — przy dobrych wiatrach — sprawi że każdy słuchacz będzie mógł pochwalić się własnym, działającym interpreterem i obejmie następujące zagadnienia:

• stworzenie parsera wczytującego formy w notacji prefiksowej i tworzącego drzewo składniowe programu,
• stworzenie interpretera AST pozwalającego na wykonywanie prostych programów,
• rozbudowane interpretera — definiowanie funkcji, instrukcje warunkowe, funkcje anonimowe, funkcje wyższego rzędu, domknięcia z wykorzystaniem stosu spaghetti.

Dodatkowo o ile starczy czasu prowadzący postara się zaprezentować przykłady wykorzystania niektórych z bardziej rozbudowanych technik, takich jak statyczna kompilacja za pomocą LLVM, prosty garbage collector czy prosta maszyna wirtualna, oczywiście zgodnie z tym, co słuchacze uznają za interesujące.

Wymagania

• umiejętność logicznego i algorytmicznego rozumowania (konieczne ze względu na ograniczenia czasowe warsztatu),
• znajomość jakiegoś języka programowania (mniej koniecznie, gdyż język wykładowy i tak pewnie będzie obcy dla większości słuchaczy),
• znajomość języka angielskiego (bo kto chce mówić „analizator składniowy” jak można powiedzieć „parser”),
• laptop lub chęć interakcji z innym uczestnikiem warsztatów, który takowy posiada (Linuks niewymagany, acz mile widziany, bo w razie problemów technicznych typu instalacja bibliotek prowadzący będzie w stanie z tym systemem pomóc).

Są to w zasadzie podstawowe wymagania tych warsztatów, ale są rzeczy które na pewno Ci pomogą wynieść z niego jak najwięcej, drogi uczestniku:

• jeżeli kiedykolwiek próbowałeś napisać program wczytujący jakiś plik i zamieniający go na struktury danych w pamięci albo — jeszcze lepiej — wiesz z czym się je parsery, to punkt dla Ciebie,
• podobnie jeżeli wiesz coś o automatach skończonych, drzewach i grafach, gdyż są to struktury danych bardzo często występujące w implementacji języków programowania,
• znajomość C, działania pamięci w architekturze von Neumanna oraz wskaźników może pomóc zrozumieć pewne bardziej niskopoziomowe koncepcje (na przykład jeżeli zdecydujemy się powiedzieć więcej o automatycznym zarządzaniu pamięcią),
• styczność z którymś z następujących języków — Haskell, F#, Scheme/Clojure/Racket — to masz szansę być jedną z osób dla których język wykładowy nie będzie obcy.

Materiały

Jeżeli wiesz, dlaczego wybrałem taką, a nie inną nazwę warsztatów, to jesteś już o krok do przodu jeżeli chodzi o materiały. Oprócz tej tajemniczej pozycji, prowadzący warsztaty do ich przygotowania będzie korzystał także z (in no particular order):

• „Haskell Programming from First Principles” Christopher Allen, Julie Moronuki,
• „Modern Compiler Implementation” Andrew W. Appel,
• „Types and Programming Languages” Benjamin C. Pierce,
• „Advanced Topics in Types and Programming Languages ” Benjamin C. Pierce,
• „Practical Foundations for Programming Languages” Robert Harper,
• „Programming Language Pragmatics” Michael L. Scott,
• „Essentials of Programming Languages” Daniel P. Friedman, Mitchell Wand,
• „The Implementation of Functional Programming Languages” Simon Peyton Jones,
• „Lisp in Small Pieces” Christian Queinnec,
• materiały do wykładu o rachunku lambda z MIM Uniwersytetu Warszawskiego,
• „Write Yourself a Scheme in 48 Hours”,
• „Write You a Haskell”,
• „Baby's First Garbage Collector” (polecam w ogóle całego bloga, koleś ze swadą pisze o ciekawych rzeczach, w tym np. o parserach Pratta),

choć tak naprawdę jeżeli przeczytasz powyższe materiały od deski do deski, to równie dobrze to Ty mógłbyś poprowadzić te warsztaty, więc podrzucam je raczej w charakterze informacyjnym — tak, abyście wiedzieli gdzie szukać informacji do dalszego pogłębiania wiedzy w tym kierunku, gdyby temat okazał się dla Ciebie interesujący.

Ponieważ materiały są równe i równiejsze i w związku z tym, że nie będę z nich korzystał w jednakowym stopniu — z książki o Haskellu interesuje nas głównie pierwszy rozdział, jako przystępne wyjaśnienie rachunku lambda, TAPL posłuży głównie do zarysowania korzyści płynących z typów, a natomiast materiały o implementacji Scheme zostaną dość wyczerpująco wykorzystane — więc mam cichą nadzieję, że okażecie wyrozumiałość jak nie będę w stanie odpowiedzieć na pytania co na stronie 354, w wierszu 23 powiedział SPJ o Maszynie G :V

Zadania Kwalifikacyjne

Będą.

Pierwsze mogę nawet zdradzić już teraz — jak wspomniałem wyżej nazwa warsztatów jest nieprzypadkowa — jeżeli wiesz i/lub umiesz znaleźć jaka jest proweniencja tej nazwy, to zaliczenie pierwszego pytania masz jak w banku.

EDIT: Nadal będą, ale z lekkim poślizgiem. Jak się — wybaczcie moją korpomowę — czelendżuje fakap na asapie w pracy (która na szczęście korpo nie jest) to się obsuwy mogą zdarzyć. Postaram się jak najszybciej to ogarnąć. Mam nadzieję, że wszyscy potencjalnie zainteresowani mi wybaczą ~~'

EDIT2: To straszne, ile mi to zajęło, ale już są!