TLDR: Kod źródłowy prostego języka stworzonego w jslang jest tutaj.
Ostatnio, na potrzeby ćwiczeń do tekstu o podstawach programowania, potrzebowałem napisać interpreter języka programowania, którego będę używał do prezentowania różnych zagadnień. Ze względu na czytelność, chciałem rozwiązania możliwie elastycznego, dlatego powstał generator interpreterów i, przy jego pomocy, zaimplementowałem język. W tym tekście chciałbym zaprezentować w jaki sposób to działa.
Repozytorium z kodem jslang i przykładem znajduje się na: https://github.com/BartekLew/jslang.
Do generowania stron używam własnego rozwiązania (home), napisanego w Common Lispie. Dzięki niemu mam dużą swobodę wstawiania treści na stronie. Zawszę mogę zagnieździć w tekście kawałek kodu w Common Lispie. Home zawiera również generator kodu JS, który przede wszystkim pozwala zapisywać kod JS w formie łatwej do przetwarzania w CL, z możliwością definiowania makr. Na przykład:
'(fun reduceshape (fn shape initial)
(if (undef? initial)
((= initial 0)))
(return (shape.reduce (fun nil (acc ln)
(return (ln.reduce fn acc)))
initial)))Mamy tu deklarację funkcji o trzech parametrach. Wygeneruje ona następujący kod (sformatowany ręcznie):
function reduceshape(fn, shape, initial){
if (typeof initial == "undefined") {
initial = 0;
}
return shape.reduce(
function (acc, ln){return ln.reduce(fn,acc);},
initial
);
}Jak widać, tylko makro undef? miało szczególne znaczenie, reszta była tylko uproszczeniem składni. Symbol shape.reduce było tylko odwołaniem do metody, która istnieje w JS. Dzięki temu, że Common Lisp ma szeroki zakres znaków, które mogą być użyte w symbolach, możemy czasem sobie skrócić pisząc np. x[0] zamiast pełnego wywołania makra (@[] x 0). Warto też zwrócić uwagę, że Common Lisp nie rozróżnia wielkich i małych liter. Dlatego wielbłądzie nazwy są zamieniane na separowane myślnikiem (np. parse-int odpowiada parseInt w JS). Ze względu na to nie mogę napisać x[i-1], muszę (@[] x (- i 1)), choć dałoby się to zaimplementować.
Niestety jest to mechanizm bardzo prosty (choć powoli się rozwija), nie zapewnia żadnej walidacji kodu, często zgubienie nawiasu zmienia znaczenie symboli. Tym niemniej lubię go, dobrze mi się z nim pracuje i postaram się uczynić go przyjaźniejszym w użyciu.
Pierwszym krokiem, zrealizowanym na potrzeby wsparcia jslang, jest wzbogacona konstrukcja definicji funkcji, która nakłada ściślejsze wymagania niż JS. Mianowicie, w JS, niezależnie od zdefiniowanych parametrów, możemy podać dowolną liczbę argumentów. Jeśli jakiegoś zabraknie, parametr będzie miał wartość niezdefiniowaną, a jeśli będzie za dużo, możemy je odczytać przez obiekt arguments.
Za pomocą konstrukcji defn możemy zdefiniować funkcję tak, żeby zablokować taką możliwość, a jeśli trzeba, ściśle określić, które parametry mają być opcjonalne albo zdefiniować parametr zawierający resztę argumentów. Daje on również możliwość automatycznego sprawdzania typu. Składnia naśladuje Common Lisp, jednak bez parametrów nazwanych, za to z możliwością typów z parametrem — np. (int-list offset 2) oznacza, że offset to lista liczb o rozmiarze 2.
Przykładowe funkcje zdefiniowane w ten sposób:
(defn przesuń ((list form) (int-list offset 2))
(if (and (== form.length 2)
(not (array? form[0]))
(not (array? form[1])))
((return (list (+ form[0] offset[0])
(+ form[1] offset[1])))))
(return (form.map
(fun nil (x)
(return (builtins.przesuń x offset))))))
(defn lista (&rest args)
(return args))Nazwy typów mogą być definiowane za pomocą kategorii js-typetest, na wzór tych w js.lisp. Więcej przykładów takich składni, możemy zobaczyć w sekcji builtin w przykładzie.
Gdybyście chcieli użyć tego niezależnie od całego generatora stron, możecie użyć funkcji (js-eval kod). Wówczas potrzebujecie tylko plików js.lisp, lang.lisp i util.lisp.
Standardowo, zaczynam od leksera i parsera. Lekser to funkcja, która dzieli tekst na symbole. Potem lekser interpretuje symbole, zgodnie z gramatyką. Zdecydowałem, że najlepiej będzie reprezentować gramatykę jako listę definicji symboli o formie: (symbol reguła-leksera akcja-parsera). symbol to nazwa (w Lispie jest typ zmiennych symbol) której będę mógł używać w akcjach parsera, żeby sprawdzać typy symboli. Reguła leksera opisuje jaki warunek musi spełniać ciąg znaków, żeby był zakwalifikowany jako dany symbol (zwykle zakresy znaków lub konkretne ciągi). Niestety obecnie, reguły leksera są uporządkowane tak samo jak podano na liście, więc == będzie odróżnione od = tylko jeśli ten pierwszy ma wyższy priorytet wykonywania. Jednak już niebawem będę implementował porównania i naprawię to.
Akcja parsera to sposób obsługi danego symbolu. Akcje parsera ułożone są potem w stos akcji. Z założenia akcja parsera przyjmuje trzy parametry: listę symboli, stos akcji i wartości zmiennych (jednak nic nie stoi na przeszkodzie, żeby to zmienić). Z zewnątrz wywołuje się pierwszą akcję, ona wykonuje swoje zadanie, przeważnie posiłkując się kolejnymi akcjami. Ze względu na elastyczność i łatwość zmiany kolejności (ona odzwierciedla priorytet rozpatrywania symboli), akcja wedle uznania, dowolnie przetwarza listę symboli. Jeśli jednak jest chęć, można zaimplementować jakieś głębsze zależności pomiędzy akcjami kolejnych symboli.
Przytoczę kod opisujący gramatykę wzoru funkcji rysowanej w tym przykładzie:
`((space ,(js-in-set? '_ " " "\\t" "\\n") ,(langignore))
(brack-opn (== _ "(") ,(langskip))
(brack-cls (== _ ")") ,(langbrack 'brack-opn))
(plus (== _ "+") ,(langop '((return (+ before after)))))
(minus (== _ "-") ,(langop '((if (undef? before)
((return (- after)))
((return (- before after)))))
:optional-before T))
(mul-div ,(js-in-set? '_ "*" "/")
,(langop '((return (eval (+ before toks[i][1] after))))))
(pow (== _ "^")
,(langop '((return (^ before after)))))
(number ,(js-range '_ "0" "9") ,(jslangnumber))
(word ,(js-range '_ "a" "z") ,(jslangvar))
(literal (undef? _) ,(jslangliteral)))Znak ` oznacza, że dalszy ciąg ma być brany dosłownie, czyli jego zawartość nie jest interpretowana, z wyjątkiem wartości lub wyrażeń poprzedzonych przecinkiem. Więc, np. ,(langbrack 'brack-opn) wywoła funkcję langbrack i wynik wstawi w tym miejscu.
Znak ' działa tak samo, tylko bez możliwości użycia przecinka. W związku z tym mamy listę list trójelementowych (opisów kolejnych klas symboli). Przyjrzyjmy się tym opisom. I tak, gdyby brack-opn nie było poprzedzone tym znakiem, interpreter próbowałby znaleźć zmienną o takiej nazwie.
Pierwszy element to nazwa symbolu. Powyżej wdzieliśmy przykład takiego wywołania (langbrack 'brack-opn) — funkcja generująca akcję dla zamknięcia nawiasu. Podany jest tylko symbol otwierający nawias. Można podać również specjalną akcję, a tak znacznie nawiasu ogranicza się do zmiany kolejności wykonywania działań.
Drugi element to reguła dla leksera. Może to być konkretny ciąg znaków, jak (== _ "+"), albo zbiór znów jaki może być użyty, jak ,(js-range '_ "a" "z"). Symbol _ oznacza rozpatrywany znak lub ciąg znaków (w przypadku dokładnego dopasowania).
Trzeci element to akcja symbolu. Rozpatrzmy dwa z prostszych przypadków:
(defun langignore ()
`(fun nil (toks opstack vars)
(return (opstack[1][1]
(toks.filter (fun nil (x)
(return (!= x[0] opstack[0][0]))))
(opstack.slice 1)
vars))))
(defun langnumber ()
`(fun nil (toks opstack vars)
(if (== toks[0][0] opstack[0][0])
((if (!= toks.length 1)
((throw (+ "Niepoprawna wartość: "
(print-toks toks)))))
(return (parse-int toks[0][1]))))
(return (opstack[1][1] toks (opstack.slice 1) vars))))Pierwsza jest używana w przypadku białych znaków, które są ignorowane (ale wykrywane przez lekser, bo jego konstrukcja nie przewiduje pomijania znaków nieznaczących). Konstrukcja tej funkcji dobrze pokazuje jak działa stos akcji. Wywoływana jest kolejna akcja (opstack[1][1]). Z listy symboli usuwane są (toks.filter) elementy o typie związanym z akcją — (!= x[0] opstack[0][0]). Zmienne są przekazywane bez zmian.
Druga funkcja, używana do interpretowania liczb (lekser podaje je jako łańcuch znaków). Na początku sprawdzamy czy pierwszy element listy symboli zgadza się typem z symbolem przyporządkowanym do funkcji — (== toks[0][0] opstack[0][0]). Jeśli tak, sprawdzamy czy to jedyny element, jeśli nie to mamy błąd, jeśli tak, po prostu zmieniamy typ zmiennej (parse-int). Jeśli jest to element innego typu, po prostu przekazujemy sprawę do następnej akcji.
Za pomocą specjalnej funkcji, (interpreter nazwa tablica-symboli), możemy wygenerować funkcję tworzącą wszystko czego potrzeba. Obiekt ma następujące pola i metody:
Funkcja ma dodatkowo dwa parametry nazwane:
Bardziej złożony język jest zdefiniowany tak:
(interpreter 'lndn
`((space ,(js-in-set? '_ " " "\\t" "\\n") ,(langignore))
(block-opn (== _ "{") ,(langskip))
(block-cls (== _ "}") ,(langbrack 'block-opn))
(stop (== _ ";") ,(langgenop '((pass before)
(return (self after)))))
(eql (== _ "=")
,(langgenop
'((if (or (!= before.length 1)
(!= before[0][0] word))
((throw (+ "Oczekiwano nazwy, jest: "
(print-toks before)))))
(if (not (undef? vars[before[0][1]]))
((throw (+ "Próba nadpisania zmiennej: "
(print-toks toks)))))
(= (@[] vars before[0][1]) (pass after))
(return after))))
(lambda (== _ "->")
,(langgenop
'((before.map (fun nil (x)
(if (!= x[0] word)
((throw (+ "Zła lista argumentów: "
(print-toks before)))))))
(return (fun nil ()
(let args {})
(foreach (i before)
(= args[before[i][0]] arguments[i]))
(return (opstack[1][1] after (opstack.slice 1)
(hashcat vars args))))))))
(brack-opn (== _ "(") ,(langskip))
(brack-cls (== _ ")") ,(langbrack 'brack-opn
'((let ans (pass bracket))
;each additional parenthesis pair
;creates list, so that we can
;denote list of list like ((1,1))
(if (and (== bracket.length 1)
(== bracket[0][0] literal))
((= ans (list ans))))
(return (self (merge ans))))))
(cons (== _ ",") ,(langop '(;if first element is embedded list
;i.e. put in parenthesis
(if (and (== i 1)
(== toks[0][0] literal))
((return (list before after))))
;else, simple work
(if (array? before)
((before.push after)
(return before))
((return (list before after)))))))
(plus (== _ "+") ,(langop `((let atyp (array? before))
(let btyp (array? after))
(if (and atyp btyp)
((return (before.concat after))))
(if (not (or atyp btyp))
((return (+ before after))))
(throw (+ "Niezgodność typów w wyrażeniu: "
(print-toks toks))))))
(o1 (== _ "-") ,(langop `((if (undef? before)
((return (- after)))
((return (- before after)))))
:optional-before T))
(o2 ,(js-in-set? '_ "*" "/")
,(langop `((return (eval (+ before toks[i][1] after))))))
(o3 (== _ "^")
,(langop `((return (^ before after)))))
(word (!= (_.to-upper-case) (_.to-lower-case)) ,(langcall))
(number ,(js-range '_ "0" "9") ,(langnum))
(literal (undef? _) ,(langliteral)))
:tok-printer '((arr)
(let lastp 0)
(return
(call ((arr.map (fun nil (x)
(if (== x[0] literal)
((return (ser x[1]))))
(if (or (and (> lastp cons) (> x[0] cons))
(and (> lastp cons) (== x[0] brack-opn))
(and (== lastp brack-cls) (> x[0] cons)))
((= lastp x[0])
(return (+ " " x[1])))
((= lastp x[0])
(return x[1])))))
join) "")))
:builtins
'((przesuń ((list form) (int-list offset 2))
(if (and (== form.length 2)
(not (array? form[0]))
(not (array? form[1])))
((return (list (+ form[0] offset[0])
(+ form[1] offset[1])))))
(return (form.map
(fun nil (x)
(return (builtins.przesuń x offset))))))
(obróć ((list form) (number angle-deg)
&optional (int-list base 2))
(let angle (div (* (_pi) angle-deg) 180))
(if (== form.length 2)
((if (undef? base)
((throw (+ "Parametr 3. jest wymagany przy "
"obracaniu punków"))))
(if (not (and (number? form[0])
(number? form[1])))
((throw (+ "Zły argument dla funkcji obróć: "
(print-toks form)))))
(let x (- form[0] base[0]))
(let y (- form[1] base[1]))
(return (list (+ (- (* x (cos angle))
(* y (sin angle)))
base[0])
(+ (* x (sin angle))
(* y (cos angle))
base[1])))))
(if (undef? base)
((= base (reduceshape
(fun nil (a v)
(return (list (+ a[0] v[0])
(+ a[1] v[1]))))
form
(list 0 0)))
(let total (form.reduce (fun nil (a v)
(return (+ a v.length)))
0))
(= base[0] (div base[0] total))
(= base[1] (div base[1] total))))
(return (mapshape
(fun nil (p)
(let x (- p[0] base[0]))
(let y (- p[1] base[1]))
(return (list (+ (- (* x (cos angle))
(* y (sin angle)))
base[0])
(+ (* x (sin angle))
(* y (cos angle))
base[1]))))
form)))
(lista (&rest args)
(return args))
(mapuj ((function fn) (list lst))
(return (lst.map fn)))
(odlicz ((number n))
(let ans [])
(for (i=0 (< i n) i++)
(ans.push i))
(return ans))))Trochę kodu jest, ale myślę, że pełen interpreter prostego języka programowania w 154 linijkach to wcale dobry wynik. Wówczas pozostaje go użyć…
(let lndn (lndn))
;[…]
(let ans (lndn.eval x.src.value))Pozostałe metody mogą być czasem przydatne. Choćby w powyższym przykładzie, rysowanie myszką, powoduje zmianę kodu. Jest to znacznie łatwiejsze, jeśli będziemy działać na liście symboli, więc to działanie używa metody lex, żeby uzyskać taką formę, oraz print-toks, aby zamienić ją z powrotem na formę tekstu.
Jak zostało pokazane powyżej, stworzyłem kilka podstawowych generatorów akcji, dla różnych przypadków rodzajów symboli.
Są dwa przypadki, w których nie chcemy by symbol miał akcję. Po pierwsze, gdy symbol nie ma żadnego znaczenia, jak białe znaki i komentarze. W takim przypadku używamy (langignore), ta akcja odfiltrowuje symbole danego typu i przechodzi do następnej.
W drugim przypadku, mamy symbole, które są częścią większych konstrukcji. Na przykład, gdy mamy nawiasy, wygodnie jest zrobić zamknięcie i otwarcie odrębnymi typami symboli, ale wykonać akcję tylko dla jednego z nich (znacznie wygodniej jest dla zamknięcia), a drugie pominąć bez usuwania z listy symboli — takie działanie zapewnia (jslangskip).
Najbardziej ogólnym generatorem akcji operatora (używany również dla nawiasów) jest (langgenop akcja). Przyjmuje ona kod akcji, który ma być wykonywany dla znalezionego symbolu. W definicji dostępne są następujące symbole:
Oprócz akcji, możemy zdefiniować opcjonalne argumenty nazwane:
Poza typami pochodnymi (operator zwyczajny, nawiasy — o nich za chwilę), używam tej funkcji do implementacji akcji operatorów deklaracji zmiennej = i funkcji ->.
Dla większości operatorów jednak chcemy, żeby kierunek był odwrócony (:reverse T), wtedy działania będą wykonywane tak jak operacje arytmetyczne. Dodatkowo, chcemy, żeby before i after zawierały już gotowe wartości. Dla takich działań stosujemy (langop akcja). Funkcja dodatkowo pozwala zdefiniować nazwane parametry :optional-before i optional-after, żeby uzyskać operator unarny (jak minus poprzedzający liczbę).
Przeważnie chcemy, żeby w naszym języku istniały nawiasy o różnych znaczeniach. Jak już pisałem wyżej, w mojej implementacji, otwarcie i zamknięcie nawiasu są odrębnymi typami symboli. Otwarcia nie mają swojej akcji, są tylko dopasowywane przez akcję zamknięcia. Taki wybór dlatego, że zamykający nawias zawsze odnosi się do poprzedniego otwierającego. Jeśli chcemy wspierać zagnieżdżone nawiasy, zależność nie zachodzi w drugą stronę. Zaczynając od otwarcia nawiasu, musimy szukać następnego otwarcia i następnego zamknięcia i sprawdzać, który jest wcześniej. Bardzo uciążliwe w implementacji.
Akcję zamknięcia nawiasu generuje (langbrack symbol-otwarcia akcja). Funkcja ta bazuje na langgenop, jednak after oznacza listę symboli przed otwarciem nawiasu. Lista symboli wewnątrz nawiasu to bracket. W akcji jest też dostępna funkcja (merge wartość), która wstawia podaną wartość między before i after. Parametr akcji może być pominięty — wówczas nawias będzie tylko i wyłącznie grupował wyrażenia.
W moim przypadku, domyślną akcję stosuje tylko nawias klamrowy (grupujący całe instrukcje), zwykły nawias niewiele ponadto, bo sam przecinek tworzy listy. Tylko na wypadek wyrażenia takiego jak ((1,2)), potrzebne jest małe zastrzeżenie w obsłudze nawiasu, inaczej byłaby to lista, a nie drzewo. Wydało mi się ciekawe, że pomimo tak różnego znaczenia, tych dwóch rodzajów nawiasu, implementowane są prawie tak samo, różnią się zaś priorytetem rozpatrywania.
Na sam koniec, symbole wartości — w mojej dotychczasowej implementacji :
W przyszłości spodziewam się rozszerzenia langnum o liczby zmiennoprzecinkowe i, być może szesnastkowe, postać wykładniczą i ułamkową. Ponadto, prawie na pewno pojawią się literały tekstowe.
Rozwiązanie jest bardzo proste i eksperymentalne, wymaga kilka usprawnień. Przede wszystkim raportowanie błędów woła o pomstę do nieba (choć pierwszy krok został zrobiony — już nie pokazuje pełnego stosu wywołań w razie wyjątku). Mam tu na myśli zarówno na poziomie kompilacji i działania w przeglądarce. W obecnym kształcie, debugowanie nie należy do przyjemności.
Moduł generujący JS też mógłby działać lepiej, robić jakąś walidację. Myślę, że statyczne typowanie byłoby dobre. Nie wiem jednak na ile poczuję się do tego zmotywowany (z trudnością przychodzi mi robienie rzeczy niepotrzebnych).
Nie jestem pewny co do implementowania akcji. Czy ich działanie może być niejasne dla kogoś, kto nie zna wewnętrznych mechanizmów programu (może jak wrócę po przerwie do tego kodu to się przekonam, a może wy mi powiecie).
Z mniejszych rzeczy, potrzebne jest sortowanie symboli w lekserze, żeby uniknąć sytuacji z == i =, jak opisane wcześniej. Raczej nie będzie to bardzo trudne, jednak wstrzymuję się do czasu, kiedy będzie to konieczne.
Mimo, że jest jeszcze trochę do zrobienia, jestem zadowolony z efektu i cieszę się że mogę kontynuować cykl nie martwiąc się, że został mi ten interpreter do zrobienia. Jestem też zadowolony, że kodu jest stosunkowo niewiele (204 linijki generatora i 154 linijki samego języka) i używanie go jest całkiem przyjemne. Bardzo mnie cieszy, że udało mi się w miarę zgrabnie połączyć opis leksera i parsera, unikając niepotrzebnej nadmiarowości i przestrzeni na błędy.
Zasadniczo, chyba ten przykład był najprzyjemniejszym w implementacji językiem programowania jaki zdarzyło mi się stworzyć (a kilka ich było) i zdecydowanie jest to najładniejszy z nich.