fml

Mały język z rodziny ML zaimplementowany od zera w F#. Lexer, parser, system typów i ewaluator - kompletny łańcuch od kodu źródłowego do wyniku.

TL;DR

Mały język z rodziny ML zbudowany od zera w F#: lexer, parser, system typów i ewaluator - pełna droga od tekstu źródłowego aż do wyniku. Najtrudniejsza część to system typów.

Wprowadzenie

fml to mały język programowania z rodziny ML, zbudowany od zera w F#. Ma cztery ogniwa, które razem prowadzą od tekstu źródłowego do wyniku: lexer, parser, system typów i ewaluator. Każde z nich robi jedną rzecz, ale najciekawszym i najtrudniejszym jest system typów.

Własny język to projekt, który uczy pokory. Nie jest jednym problemem, tylko całą sekwencją, w której wyjście jednego etapu jest wejściem następnego, a błąd na wczesnym etapie wraca ze zdwojoną siłą trzy kroki później. Właśnie dlatego jest tak dobrym ćwiczeniem z myślenia o systemach.

Tekst źródłowy trzeba pociąć na tokeny, tokeny ułożyć w drzewo, drzewo sprawdzić pod kątem typów, a na końcu wykonać. To łańcuch, w którym nie można oszukać na żadnym etapie, bo następny natychmiast to wychwyci - albo, co gorsza, nie wychwyci, i błąd ujawni się dopiero na końcu jako niezrozumiały wynik.

Ta zależność etapów jest zarazem trudnością i urodą projektu. Każde ogniwo można zrozumieć osobno, ale dopiero razem tworzą coś, co realnie wykonuje program. Zaprojektowanie granic między nimi tak, żeby były czyste, jest połową sukcesu.

Typy, których nie trzeba pisać

W języku z rodziny ML najciekawszy jest system typów. Nie musisz pisać typów ręcznie - kompilator sam je wnioskuje z tego, jak używasz wartości. Piszesz zwykłą funkcję, a język sam dochodzi do tego, jaki ma typ, i pilnuje, żebyś nie użył jej niezgodnie z nim.

example.fml · fsharp

let rec map f xs =
  match xs with
  | [] -> []
  | x :: rest -> f x :: map f rest

map (fun n -> n + 1) [1; 2; 3]

Informacja

Nigdzie w tym kodzie nie napisaliśmy ani jednego typu, a mimo to język wie, że map ma typ (a -> b) -> lista a -> lista b. To wnioskowanie typów - jedna z najpiękniejszych rzeczy, jakie można napisać własnoręcznie, i zarazem jedna z najbardziej wymagających.

Cztery etapy od tekstu do wyniku

Cała droga rozkłada się na cztery kroki o jasno podzielonych rolach. Tekst staje się tokenami, tokeny drzewem, drzewo dostaje typy, a na końcu zostaje policzone. Niezgodności typów wychodzą na trzecim etapie, jeszcze przed uruchomieniem, a nie w trakcie działania.

Lexer

tekst źródłowy staje się strumieniem tokenów.

Parser

tokeny układają się w drzewo składniowe.

System typów

każde wyrażenie dostaje typ, a niezgodności wychodzą tu, a nie w trakcie działania.

Ewaluator

drzewo zostaje policzone do wyniku.

Łańcuch kompilatora

Etap	Wejście	Wyjście
Lexer	tekst źródłowy	tokeny
Parser	tokeny	drzewo składniowe
System typów	drzewo	drzewo z typami
Ewaluator	drzewo	wynik

Efekt: język ML pisany w języku ML

Na wyjściu jest mały, ale kompletny język, który realnie wykonuje program - od pierwszego znaku w pliku aż po policzony wynik. F# był tu naturalnym wyborem, bo sam należy do rodziny ML, a pisanie języka ML w języku ML ma w sobie coś przyjemnie rekurencyjnego. To projekt, po którym słowo "kompilator" przestaje być abstrakcją.

Więcej projektów

Inne realizacje z tej samej kategorii - zobacz, jak podchodzimy do podobnych wyzwań.

Masz podobny projekt?

Napisz do nas - wycena jest bezpłatna i wraca w godzinę.