VulCode

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.

TypInterpreter języka Scheme
JęzykSwift
BudowanieSwift Package Manager
TestyXCTest
kite

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

ZapisPrzykład
Listy, także w nawiasach kwadratowych(a b c), [a b]
Pary z kropką(a . b)
Liczby całkowite, ułamki i zmiennoprzecinkowe42, 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.

Interpreter.swift · swift
private func run(_ initial: MachineState) throws -> Value {
    var state = initial
    while true {
        switch state {
        case .returning(let value, let kont):
            if case .done = kont { return value }
            state = try applyKont(value, kont)
        case .evaluating(let expr, let env, let kont):
            state = try step(expr, env, kont)
        case .applying(let proc, let args, let kont):
            state = try apply(proc, args, kont)
        }
    }
}

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.

tailloop.scm · scheme
(define (even-loop n)
  (if (= n 0) #t (odd-loop (- n 1))))
(define (odd-loop n)
  (if (= n 0) #f (even-loop (- n 1))))

(display (even-loop 1000000))

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:

callcc.scm · scheme
(define (list-product items)
  (call/cc
    (lambda (break)
      (let loop ((xs items) (acc 1))
        (cond ((null? xs) acc)
              ((= (car xs) 0) (break 0))
              (else (loop (cdr xs) (* acc (car xs)))))))))

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.

macros.scm · scheme
(define-syntax swap!
  (syntax-rules ()
    ((_ a b)
     (let ((tmp a))
       (set! a b)
       (set! b tmp)))))

(define tmp 10)
(define other 20)
(swap! tmp other)

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

FormaPostać po przepisaniu
letwywołanie lambdy
nazwany letletrec 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ą
caselet i cond z porównaniem memv
and, orzagnieżdżone if, w or ze zmienną tymczasową
quasiquotecons 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żenieWynik
(/ 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

GrupaProcedury
Arytmetyka+, -, *, /, quotient, modulo, gcd, expt, min, max
Porównania=, <, >, <=, >= z dowolną liczbą argumentów
Listycons, car, cdr, append, reverse, list-ref, list-tail, length
Funkcje wyższego rzędumap na wielu listach, for-each, filter, fold-left, fold-right, apply
Wyszukiwaniemember, memq, memv, assoc, assq, assv
Równość i predykatyeq?, eqv?, equal?, null?, pair?, list?, procedure?
Łańcuchy i znakistring-append, substring, string->number, symbol->string, char->integer
Wyjście i błędydisplay, 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

ProgramCo sprawdza
fib.scmrekurencja drzewiasta
factorial.scmnazwany let z akumulatorem
maps.scmmap, filter, fold-left i for-each
callcc.scmwczesne wyjście i ponowne wejście w kontynuację
macros.scmswap!, 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ę.