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

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?

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.

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!

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.

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.

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

Baskell to implementacja nauczania, http://hackage.haskell.org/package/baskell

Możesz zacząć od wybrania, powiedzmy, systemu czcionek do zaimplementowania. To jest tak skomplikowane, jak interpretacja Scheme, http://hackage.haskell.org/package/thih

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) ).

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.

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

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

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

Uhc / Ehc to seria kompilatorów włączających / wyłączających różne funkcje Haskell. http://www.cs.uu.nl/wiki/Ehc/WebHome#What_is_UHC_And_EHC

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

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.

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 :)

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:

• System FC: ograniczenia równości i wymuszenia
• GHC / Jako biblioteka
• Coretyp