kite
Interpreter języka Scheme w Swifcie. Kontynuacje call/cc, rekurencja ogonowa w stałej pamięci, higieniczne makra syntax-rules, liczby dowolnej wielkości i dokładne ułamki, do tego REPL.
Wprowadzenie
kite to interpreter języka Scheme napisany w Swifcie. Czyta kod źródłowy, zamienia go w S-wyrażenia i wykonuje je na maszynie abstrakcyjnej, w której cały przebieg programu jest zwykłą daną, a nie stosem wywołań Swifta. Z tej jednej decyzji wynika to, co w Scheme najtrudniejsze: kontynuacje pierwszej klasy i rekurencja ogonowa bez limitu głębokości.
Cały język mieszka w bibliotece KiteCore, a program kite jest nad nią cienką warstwą: REPL do pracy interaktywnej i uruchamianie plików .scm. Ten sam interpreter da się wpiąć w dowolną aplikację w Swifcie.
Czytnik: od tekstu do danych
W Scheme kod i dane mają tę samą postać. Czytnik nie buduje więc osobnego drzewa składniowego, tylko zwraca listy, symbole, liczby i łańcuchy, czyli dokładnie te wartości, na których później pracują program i makra.
Co rozpoznaje czytnik
| Zapis | Przykład |
|---|---|
| Listy, także w nawiasach kwadratowych | (a b c), [a b] |
| Pary z kropką | (a . b) |
| Liczby całkowite, ułamki i zmiennoprzecinkowe | 42, 3/4, 1.5 |
| Łańcuchy i znaki | "tekst", #\space, #\newline |
| Wartości logiczne | #t, #f |
Apostrof, odwrotny apostrof, przecinek i ,@ czytnik od razu rozwija do quote, quasiquote, unquote i unquote-splicing. Pomija komentarze liniowe, zagnieżdżone komentarze blokowe i komentarz #;, który wyłącza całe następne wyrażenie.
Maszyna CEK: sterowanie jako dane
Naiwny interpreter liczy podwyrażenie, wywołując sam siebie, więc każdy poziom programu w Scheme to kolejna ramka na stosie Swifta. kite działa inaczej. Ewaluacja jest pętlą, która przechodzi między trzema stanami: liczy wyrażenie w środowisku, zwraca wartość do kontynuacji albo wywołuje procedurę z argumentami.
Kontynuacja, czyli to, co zrobić z wartością dalej, jest zwykłym łańcuchem ramek: wybierz gałąź if, dopisz argument i licz następny, przypisz wynik do zmiennej, przejdź do kolejnego wyrażenia w begin. Stos Swifta nie rośnie razem z programem, bo cała historia obliczeń leży w tej strukturze.
Zmienne żyją w środowiskach leksykalnych. Każde wywołanie procedury tworzy nową ramkę wskazującą na środowisko z miejsca definicji, więc lambda zamyka w sobie zmienne z otoczenia, a set! zmienia je tam, gdzie zostały zdefiniowane. Procedura przyjmuje stałą liczbę argumentów, resztę jako listę w zapisie (a . rest) albo wszystkie naraz jako jedną listę, a apply rozkłada listę z powrotem na argumenty.
Rekurencja ogonowa w stałej pamięci
Scheme nie ma pętli w zwykłym sensie, pętla to procedura, która wywołuje samą siebie. Żeby taki kod mógł kręcić się bez końca, wywołanie w pozycji ogonowej nie może zajmować pamięci. W kite ciało procedury liczy się z tą samą kontynuacją, z którą przyszło wywołanie, więc ostatnie wyrażenie w if, cond czy begin niczego nie odkłada na później.
Pętla nazwanym let do miliona kroków i wzajemna rekurencja dwóch procedur działają w stałej pamięci, bez przepełnienia stosu.
call/cc: kontynuacje pierwszej klasy
Skoro kontynuacja jest daną, call/cc jest prosty: opakowuje bieżącą kontynuację w wartość i podaje ją procedurze. Wywołanie tej wartości porzuca to, co program akurat robił, i wraca w zapamiętane miejsce z nowym wynikiem. Tak wygląda wczesne wyjście z pętli, gdy na liście trafi się zero:
Kontynuację można wywołać także po tym, jak jej wyrażenie już zwróciło wynik, i to wiele razy. Da się na tym zbudować pętlę, generator albo powrót do wcześniejszego punktu obliczeń. Na tych samych ramkach stoją dynamic-wind, który przy skoku kontynuacją uruchamia po drodze kod wyjścia i wejścia, obsługa wyjątków przez with-exception-handler i wiele wartości zwracanych naraz przez call-with-values.
Makra higieniczne
define-syntax z syntax-rules dopisuje do języka nowe formy. Wzorce dopasowują wywołanie makra z literałami, symbolem _ i wielokropkiem, także zagnieżdżonym w szablonie, a makro może rozwijać się rekurencyjnie do samego siebie. let-syntax i letrec-syntax dają makra o zasięgu lokalnym, a when i unless są zwykłymi makrami z preludium interpretera.
Każde rozwinięcie dostaje własny znacznik, którym oznacza symbole wprowadzone przez szablon. tmp z wnętrza swap! nie myli się więc ze zmienną użytkownika o tej samej nazwie i zamiana daje (20 10), zamiast zostawić obie wartości bez zmian.
Formy pochodne
Rdzeń ewaluatora zna tylko kilka form: quote, if, define, set!, lambda i begin. Pozostałe przed obliczeniem są przepisywane na te podstawowe, więc maszyna zostaje mała, a każda forma pochodna dziedziczy po rdzeniu rekurencję ogonową i kontynuacje.
Na co przepisywane są formy pochodne
| Forma | Postać po przepisaniu |
|---|---|
let | wywołanie lambdy |
nazwany let | letrec z lambdą i pierwszym wywołaniem |
let* | zagnieżdżone let |
letrec, letrec* | lambda, która ustawia zmienne przez set! |
cond, także z => | łańcuch if, przy => ze zmienną tymczasową |
case | let i cond z porównaniem memv |
and, or | zagnieżdżone if, w or ze zmienną tymczasową |
quasiquote | cons i append |
Zmienne tymczasowe dostają świeże nazwy, więc or ani cond z => nie przesłaniają zmiennych z kodu użytkownika. quasiquote obsługuje zagnieżdżenie i wklejanie list przez ,@.
Wieża liczbowa
Liczby całkowite liczą się na typie maszynowym, a gdy dodawanie, odejmowanie albo mnożenie przekroczy jego zakres, wynik przechodzi na własną implementację liczb dowolnej wielkości. BigInt ma dzielenie z resztą, NWD, potęgowanie, pierwiastek całkowity i zamianę między systemami liczbowymi, więc silnia ze stu wychodzi co do cyfry.
Dzielenie liczb całkowitych daje dokładny ułamek skrócony przez NWD, a liczby zmiennoprzecinkowe pojawiają się dopiero wtedy, gdy same wejdą do obliczeń. modulo i remainder różnią się znakiem wyniku dokładnie tak, jak wymaga Scheme.
Arytmetyka w kite
| Wyrażenie | Wynik |
|---|---|
(/ 3 2) | 3/2 |
(/ 6 2) | 3 |
(+ 1/2 1/3) | 5/6 |
(* 2 1.5) | 3.0 |
(modulo -7 3) | 2 |
(remainder -7 3) | -1 |
REPL i biblioteka standardowa
Uruchomiony bez argumentów kite otwiera REPL z podpowiedzią kite>. Wyrażenie rozpisane na kilka linii czeka, aż zostanie domknięte, a kolejne linie dostają podpowiedź .... Wynik wypisuje się w postaci, którą da się wkleić z powrotem jako kod, a błąd kończy tylko bieżące wyrażenie, nie całą sesję.
Z nazwą pliku kite wykonuje program .scm, błąd wypisuje na standardowe wyjście błędów i kończy pracę z kodem 1, więc nadaje się do skryptów. Interpreter jest też zwykłą klasą biblioteki KiteCore: aplikacja w Swifcie tworzy go, podaje mu kod źródłowy, dostaje wynik, a wyjście display przechwytuje własną funkcją.
Biblioteka standardowa
| Grupa | Procedury |
|---|---|
| Arytmetyka | +, -, *, /, quotient, modulo, gcd, expt, min, max |
| Porównania | =, <, >, <=, >= z dowolną liczbą argumentów |
| Listy | cons, car, cdr, append, reverse, list-ref, list-tail, length |
| Funkcje wyższego rzędu | map na wielu listach, for-each, filter, fold-left, fold-right, apply |
| Wyszukiwanie | member, memq, memv, assoc, assq, assv |
| Równość i predykaty | eq?, eqv?, equal?, null?, pair?, list?, procedure? |
| Łańcuchy i znaki | string-append, substring, string->number, symbol->string, char->integer |
| Wyjście i błędy | display, write, newline, error |
Testy na każdej warstwie
Każda warstwa ma własny zestaw testów XCTest: czytnik, ewaluator z formami specjalnymi, rekurencja ogonowa, call/cc z wielokrotnym wejściem, makra i arytmetyka BigInt. Na końcu przykładowe programy uruchamiają się w całości, a test porównuje ich wyjście znak w znak.
Przykładowe programy w testach
| Program | Co sprawdza |
|---|---|
| fib.scm | rekurencja drzewiasta |
| factorial.scm | nazwany let z akumulatorem |
| maps.scm | map, filter, fold-left i for-each |
| callcc.scm | wczesne wyjście i ponowne wejście w kontynuację |
| macros.scm | swap!, higiena, wielokropek i makro rekurencyjne |
Pytania o kite
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ę.

