Napisz tłumacza języka Haskell w języku Haskell

90

Klasycznym ćwiczeniem programistycznym jest napisanie interpretera Lisp / Scheme w Lisp / Scheme. Możliwości pełnego języka można wykorzystać do stworzenia tłumacza dla podzbioru języka.

Czy jest podobne ćwiczenie dla Haskella? Chciałbym zaimplementować podzbiór Haskell, używając Haskella jako silnika. Oczywiście można to zrobić, ale czy są dostępne do obejrzenia jakieś zasoby online?


Oto historia.

Badam ideę wykorzystania języka Haskell jako języka, aby zgłębić niektóre pojęcia z kursu o Strukturach Dyskretnych, którego prowadzę. W tym semestrze zdecydowałem się na Mirandę , mniejszy język, który zainspirował Haskella. Miranda robi około 90% tego, co bym chciał, ale Haskell około 2000%. :)

Więc moim pomysłem jest stworzenie języka, który ma dokładnie te cechy Haskella, które mi się podobają i nie dopuszcza wszystkiego innego. W miarę postępów uczniów mogę selektywnie „włączać” różne funkcje po opanowaniu podstaw.

Pedagogiczne „poziomy językowe” są z powodzeniem wykorzystywane do nauczania języka Java i Scheme . Ograniczając ich możliwości, możesz uniemożliwić im strzelanie sobie w stopę, podczas gdy nadal opanowują składnię i koncepcje, których próbujesz nauczyć. Możesz zaoferować lepsze komunikaty o błędach.

Barry Brown
źródło
Mam dialekt WIP Haskell zaimplementowany z Typing Haskell w Haskell jako podstawę. Jest tego demo tutaj chrisdone.com/toys/duet-delta Nie jest gotowe do publicznego wydania open source, ale mogę podzielić się z wami źródłem, jeśli jest zainteresowany.
Christopher Sporządzono

Odpowiedzi:

76

Uwielbiam twój cel, ale to wielka praca. Kilka wskazówek:

  • Pracowałem nad GHC i nie chcesz żadnej części źródeł. Uściski to znacznie prostsza, czystsza implementacja, ale niestety jest w C.

  • To mały kawałek układanki, ale Mark Jones napisał piękną pracę zatytułowaną Typing Haskell in Haskell, która byłaby świetnym punktem wyjścia dla twojego front-endu.

Powodzenia! Określenie poziomów językowych dla Haskella, wraz z dodatkowymi dowodami z klasy, byłoby bardzo korzystne dla społeczności i zdecydowanie możliwe do opublikowania!

Norman Ramsey
źródło
2
Zastanawiam się, czy komentarz o GHC jest wciąż aktualny. GHC jest złożony, ale jest dość dobrze udokumentowany. W szczególności wewnętrzne Notessą pomocne w zrozumieniu szczegółów niskiego poziomu, a rozdział poświęcony GHC w Architekturze aplikacji open source zapewnia doskonały przegląd na wysokim poziomie.
sjy
37

Istnieje kompletny parser Haskell: http://hackage.haskell.org/package/haskell-src-exts

Po przeanalizowaniu go pozbycie się lub zablokowanie pewnych rzeczy jest łatwe. Zrobiłem to dla tryhaskell.org, aby nie zezwalać na instrukcje importu, aby obsługiwać definicje najwyższego poziomu itp.

Po prostu przeanalizuj moduł:

parseModule :: String -> ParseResult Module

Następnie masz AST dla modułu:

Module SrcLoc ModuleName [ModulePragma] (Maybe WarningText) (Maybe [ExportSpec]) [ImportDecl] [Decl]    

Typ Decl jest obszerny: http://hackage.haskell.org/packages/archive/haskell-src-exts/1.9.0/doc/html/Language-Haskell-Exts-Syntax.html#t%3ADecl

Wszystko, co musisz zrobić, to zdefiniować białą listę - tego, jakie deklaracje, importy, symbole, składnia są dostępne, a następnie przejść przez AST i wyrzucić „błąd analizy” na wszystko, czego jeszcze nie chcesz, aby byli świadomi. Możesz użyć wartości SrcLoc dołączonej do każdego węzła w AST:

data SrcLoc = SrcLoc
     { srcFilename :: String
     , srcLine :: Int
     , srcColumn :: Int
     }

Nie ma potrzeby ponownego wdrażania Haskell. Jeśli chcesz zapewnić bardziej przyjazne błędy kompilacji, po prostu przeanalizuj kod, przefiltruj go, wyślij do kompilatora i przeanalizuj dane wyjściowe kompilatora. Jeśli jest to „nie można dopasować oczekiwanego typu a do wywnioskowanego a -> b”, oznacza to, że prawdopodobnie funkcja ma za mało argumentów.

O ile naprawdę nie chcesz spędzać czasu na implementowaniu Haskella od zera lub majstrowaniu przy wewnętrznych elementach Hugs, lub jakiejś głupiej implementacji, myślę, że powinieneś po prostu filtrować to, co jest przekazywane do GHC. W ten sposób, jeśli twoi uczniowie chcą wziąć swoją bazę kodu i przejść do następnego kroku i napisać prawdziwy, pełnoprawny kod Haskell, przejście jest przejrzyste.

Christopher Gotowe
źródło
24

Chcesz zbudować swojego tłumacza od podstaw? Zacznij od zaimplementowania łatwiejszego języka funkcjonalnego, takiego jak rachunek lambda lub wariant seplenienia. W tym drugim przypadku jest całkiem fajny wikibook zatytułowany Napisz sobie schemat w 48 godzin, który zawiera fajne i pragmatyczne wprowadzenie do technik parsowania i interpretacji.

Ręczna interpretacja Haskella będzie znacznie bardziej złożona, ponieważ będziesz musiał radzić sobie z wysoce złożonymi funkcjami, takimi jak typeklasy, niezwykle potężny system czcionek (wnioskowanie o typach!) I leniwej oceny (techniki redukcji).

Więc powinieneś zdefiniować całkiem mały podzbiór Haskella, z którym będziesz pracować, a następnie może zacząć od rozszerzania przykładu schematu krok po kroku.

Dodanie:

Zauważ, że w Haskell masz pełny dostęp do API interpreterów (przynajmniej pod GHC), w tym parserów, kompilatorów i oczywiście interpreterów.

Pakiet do użycia to hint (Language.Haskell. *) . Niestety nie znalazłem samouczków online na ten temat ani nie wypróbowałem tego samodzielnie, ale wygląda to całkiem obiecująco.

Dario
źródło
12
Zauważ, że wnioskowanie o typie jest w rzeczywistości bardzo łatwym algorytmem, składającym się z 20-30 linii. jest piękny w swojej prostocie. Leniwa ocena również nie jest tak trudna do zakodowania. Powiedziałbym, że trudność leży w szalonej składni, dopasowywaniu wzorców i po prostu w dużej ilości rzeczy w języku.
Claudiu
Interesujące - Czy możesz publikować linki do algorytmów wnioskowania o typie?
Dario
5
Tak, sprawdź tę bezpłatną książkę - cs.brown.edu/~sk/Publications/Books/ProgLangs/2007-04-26 - jest na stronie 273 (289 pliku PDF). Pseudokod alg znajduje się na P296.
Claudiu
1
Istnieje również implementacja (the?) Algorytmu wnioskowania / sprawdzania typu w " Implementacji języków programowania funkcjonalnego ".
Phil Armstrong,
1
Wnioskowanie o typie z klasami typów nie jest jednak proste.
Christopher Sporządzono
20

stworzyć język, który ma dokładnie te cechy Haskella, które bym chciał i nie zezwala na wszystko inne. W miarę postępów uczniów mogę selektywnie „włączać” różne funkcje po opanowaniu podstaw.

Proponuję prostsze (jak przy mniejszym nakładzie pracy) rozwiązanie tego problemu. Zamiast tworzyć implementację Haskell, w której można wyłączyć funkcje, opakuj kompilator Haskell programem, który najpierw sprawdza, czy kod nie używa żadnej funkcji, której nie zezwalasz, a następnie używa gotowego kompilatora do kompilacji.

Byłoby to podobne do HLint (a także swego przeciwieństwa):

HLint (dawniej Dr. Haskell) czyta programy Haskella i sugeruje zmiany, które, miejmy nadzieję, ułatwią ich czytanie. HLint ułatwia również wyłączanie niechcianych sugestii i dodawanie własnych niestandardowych sugestii.

  • Zaimplementuj własne „sugestie” HLint, aby nie używać funkcji, na które nie zezwalasz
  • Wyłącz wszystkie standardowe sugestie HLint.
  • Spraw, aby Twój wrapper uruchomił zmodyfikowany HLint jako pierwszy krok
  • Traktuj sugestie HLint jako błędy. To znaczy, jeśli HLint "narzekał", to program nie przechodzi do etapu kompilacji
yairchu
źródło
6

Seria kompilatorów EHC jest prawdopodobnie najlepszym rozwiązaniem: jest aktywnie rozwijana i wydaje się być dokładnie tym, czego chcesz - serią małych kompilatorów / interpretatorów obliczeń lambda, których kulminacją był Haskell '98.

Ale możesz również przyjrzeć się różnym językom opracowanym w Pierce's Types and Programming Languages lub interpreterowi helu (okaleczony Haskell przeznaczony dla studentów http://en.wikipedia.org/wiki/Helium_(Haskell) ).

gwern
źródło
6

Jeśli szukasz podzbioru Haskell, który jest łatwy do zaimplementowania, możesz pozbyć się klas typów i sprawdzania typów. Bez klas typów wnioskowanie o typie nie jest potrzebne do oceny kodu Haskella.

Napisałem samokompilujący się kompilator podzbiorów Haskell dla wyzwania Code Golf. Pobiera kod podzbioru Haskell na wejściu i tworzy kod C na wyjściu. Przykro mi, że nie ma bardziej czytelnej wersji; Ręcznie podniosłem zagnieżdżone definicje, przygotowując je do samodzielnej kompilacji.

Studentowi zainteresowanemu wdrożeniem tłumacza dla podzbioru języka Haskell radziłbym zacząć od następujących funkcji:

  • Leniwa ocena. Jeśli tłumacz jest w Haskell, być może nie będziesz musiał nic robić.

  • Definicje funkcji z argumentami dopasowanymi do wzorca i gwarancjami. Martw się tylko o zmienne, wady, zero i _wzorce.

  • Prosta składnia wyrażeń:

    • Literały całkowite

    • Literały znakowe

    • [] (zero)

    • Aplikacja funkcji (lewostronna)

    • Infix :(minusy, prawy asocjacyjny)

    • Nawias

    • Nazwy zmiennych

    • Nazwy funkcji

Mówiąc konkretniej, napisz tłumacza, który może to uruchomić:

-- tail :: [a] -> [a]
tail (_:xs) = xs

-- append :: [a] -> [a] -> [a]
append []     ys = ys
append (x:xs) ys = x : append xs ys

-- zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith f (a:as) (b:bs) = f a b : zipWith f as bs
zipWith _ _      _      = []

-- showList :: (a -> String) -> [a] -> String
showList _    []     = '[' : ']' : []
showList show (x:xs) = '[' : append (show x) (showItems show xs)

-- showItems :: (a -> String) -> [a] -> String
showItems show []     = ']' : []
showItems show (x:xs) = ',' : append (show x) (showItems show xs)

-- fibs :: [Int]
fibs = 0 : 1 : zipWith add fibs (tail fibs)

-- main :: String
main = showList showInt (take 40 fibs)

Sprawdzanie typów jest kluczową cechą Haskella. Jednak przejście od zera do kompilatora Haskella sprawdzającego typy jest bardzo trudne. Jeśli zaczniesz od napisania interpretera dla powyższego, dodanie do niego funkcji sprawdzania typu powinno być mniej zniechęcające.

Joey Adams
źródło
- Leniwa ocena. Jeśli tłumacz jest w Haskell, być może nie będziesz musiał nic robić. To może nie być prawdą. Zobacz artykuł Naylor w haskell.org/wikiupload/0/0a/TMR-Issue10.pdf, aby uzyskać więcej informacji na temat implementacji leniwego interpretera w Haskell.
Jared Updike
3

Możesz spojrzeć na Happy (parser podobny do yacc w Haskell), który ma parser Haskell.

Kathy Van Stone
źródło
3

To może być dobry pomysł - stwórz małą wersję NetLogo w Haskell. Oto malutki tłumacz.

Claudiu
źródło
Linki są martwe. Czy jest jakaś szansa, że ​​ta treść nadal istnieje gdzie indziej? Byłbym ciekawy ...
Nicolas Payette,
hmm to był wpis na blogu i nie mam pojęcia, jakich słów kluczowych użyć, aby go wyszukać. Dobra lekcja, aby podać bardziej istotne informacje podczas podawania linku ...
Claudiu,
1
Pojawia się wyszukiwanie w Google hasła „netlogo haskell” ... to pytanie. W każdym razie nic wielkiego. Dzięki!
Nicolas Payette
2

sprawdź, czy hel byłby lepszą bazą do budowania niż standardowy haskell.

Martin DeMello
źródło
2

Powiedziano mi, że Idris ma dość kompaktowy parser, nie jestem pewien, czy naprawdę nadaje się do zmian, ale jest napisany w języku Haskell.

Jeff Burdges
źródło
2

Zoo języka programowania Andreja Bauera zawiera małą implementację czysto funkcjonalnego języka programowania, nieco bezczelnie nazwanego „minihaskell”. Zawiera około 700 linii OCaml, więc jest bardzo lekkostrawny.

Witryna zawiera również zabawkowe wersje języków programowania w stylu ML, Prologu i OO.

niklas
źródło
1

Czy nie sądzisz, że byłoby łatwiej wziąć źródła GHC i usunąć to, czego nie chcesz, niż napisać własnego interpretera Haskella od zera? Ogólnie rzecz biorąc, usuwanie funkcji powinno wymagać znacznie mniej wysiłku niż tworzenie / dodawanie funkcji.

GHC i tak jest napisane w języku Haskell, więc technicznie rzecz biorąc, pozostaje to przy pytaniu o tłumacza języka Haskell napisanego w Haskell.

Prawdopodobnie nie byłoby zbyt trudne, aby całość była statycznie połączona, a następnie rozprowadzała tylko dostosowane GHCi, aby uczniowie nie mogli załadować innych modułów źródłowych Haskell. Nie mam pojęcia, ile pracy zajęłoby im uniemożliwienie ładowania innych plików obiektów Haskell. Możesz również chcieć wyłączyć FFI, jeśli masz na swoich zajęciach wielu oszustów :)

Mark Rushakoff
źródło
1
Nie jest to takie proste, jak się wydaje, ponieważ wiele funkcji zależy od innych. Ale być może OP po prostu nie chce importować Prelude i zamiast tego zapewniać własne. Większość Haskell, które widzisz, to normalne funkcje, a nie specyficzne cechy środowiska wykonawczego. (Ale oczywiście wiele .)
jrockway
0

Powodem, dla którego jest tak wielu interpreterów LISP, jest to, że LISP jest w zasadzie poprzednikiem JSON: prostym formatem do kodowania danych. To sprawia, że ​​część frontendowa jest dość łatwa w obsłudze. W porównaniu z tym Haskell, zwłaszcza z rozszerzeniami językowymi, nie jest najłatwiejszym językiem do przeanalizowania. Oto kilka konstrukcji składniowych, które wydają się trudne do wykonania:

  • operatory z konfigurowalnym priorytetem, asocjatywnością i stałością,
  • komentarze zagnieżdżone
  • zasada układu
  • składnia wzorca
  • do- bloki i desugering do kodu monadycznego

Każdy z nich, z wyjątkiem być może operatorów, mógłby zostać rozwiązany przez studentów po kursie budowy kompilatora, ale odciągnąłby to uwagę od tego, jak faktycznie działa Haskell. Oprócz tego możesz nie chcieć bezpośrednio implementować wszystkich konstrukcji składniowych Haskella, ale zamiast tego zaimplementować przebiegi, aby się ich pozbyć. Co prowadzi nas do dosłownego sedna problemu, w pełni zamierzonego kalambura.

Proponuję zaimplementować sprawdzanie typów i tłumacza dla Core zamiast pełnego Haskella. Oba te zadania są już same w sobie dość skomplikowane. Ten język, choć nadal jest silnie typowanym językiem funkcjonalnym, jest o wiele mniej skomplikowany w zakresie optymalizacji i generowania kodu. Jednak nadal jest niezależny od maszyny bazowej. Dlatego GHC używa go jako języka pośredniego i tłumaczy na niego większość składniowych konstrukcji Haskella.

Ponadto nie powinieneś unikać korzystania z frontendu GHC (lub innego kompilatora). Nie uważałbym tego za oszustwo, ponieważ niestandardowe LISP-y używają parsera systemu hosta LISP (przynajmniej podczas ładowania początkowego). Czyszczenie Corefragmentów i prezentowanie ich uczniom, wraz z oryginalnym kodem, powinno pozwolić na przedstawienie przeglądu tego, co robi frontend i dlaczego lepiej go nie wdrażać ponownie.

Oto kilka linków do dokumentacji Coreużywanej w GHC:

MauganRa
źródło