Czy możliwy jest pełny wariant Lispa z typem statycznym?

Czy możliwy jest pełny wariant Lispa z typem statycznym? Czy w ogóle ma sens, żeby coś takiego istniało? Uważam, że jedną z zalet języka Lisp jest prostota jego definicji. Czy statyczne pisanie zagroziłoby tej podstawowej zasadzie?

Tak, jest to bardzo możliwe, chociaż standardowy system typu w stylu HM jest zwykle złym wyborem dla większości idiomatycznego kodu Lisp / Scheme. Zobacz Typed Racket, aby zapoznać się z najnowszym językiem, który jest „Full Lisp” (bardziej jak Scheme) ze statycznym pisaniem.

Gdyby wszystko, czego chciałeś, to statycznie typowany język, który wyglądałby jak Lisp, mógłbyś to zrobić dość łatwo, definiując abstrakcyjne drzewo składniowe, które reprezentuje twój język, a następnie mapując to AST na wyrażenia S. Jednak nie sądzę, abym nazwał wynik Lisp.

Jeśli chcesz czegoś, co poza składnią ma cechy Lisp-y, możesz to zrobić za pomocą języka statycznego. Jednak Lisp ma wiele cech, z których trudno jest uzyskać przydatne statyczne typowanie. Aby to zilustrować, przyjrzyjmy się samej strukturze listy, zwanej wadami , która stanowi podstawowy blok konstrukcyjny Lispa.

Nazywanie wad listą, choć (1 2 3)wygląda jak jedna, jest trochę mylące. Na przykład nie jest w ogóle porównywalna z listą wpisywaną statycznie, taką jak lista C ++ std::listczy Haskell. Są to jednowymiarowe połączone listy, w których wszystkie komórki są tego samego typu. Lisp szczęśliwie pozwala (1 "abc" #\d 'foo). Dodatkowo, nawet jeśli rozszerzysz swoje listy o typie statycznym, aby obejmowały listy-z-list, typ tych obiektów wymaga, aby każdy element listy był podlistą. Jak byś ((1 2) 3 4)w nich reprezentował ?

Konsy lispowe tworzą drzewo binarne, z liśćmi (atomami) i gałęziami (wady). Co więcej, liście takiego drzewa mogą w ogóle zawierać dowolny atomowy (nie-wad) typ Lispa! Elastyczność tej struktury jest tym, co sprawia, że ​​Lisp tak dobrze radzi sobie z obliczeniami symbolicznymi, funkcjami AST i przekształcaniem samego kodu Lispa!

Jak więc zamodelowałbyś taką strukturę w języku z typami statycznymi? Wypróbujmy to w Haskell, który ma niezwykle potężny i precyzyjny system typów statycznych:

type Symbol = String
data Atom = ASymbol Symbol | AInt Int | AString String | Nil
data Cons = CCons Cons Cons 
            | CAtom Atom

Twoim pierwszym problemem będzie zakres typu Atom. Najwyraźniej nie wybraliśmy typu Atom, który byłby wystarczająco elastyczny, aby objąć wszystkie typy obiektów, które chcemy zawiesić w konsolach. Zamiast próbować rozszerzyć strukturę danych Atom, jak wymieniono powyżej (która, jak widać, jest krucha), powiedzmy, że mamy klasę typu magicznego, Atomicktóra rozróżnia wszystkie typy, które chcieliśmy uczynić atomowymi. Wtedy możemy spróbować:

class Atomic a where ?????
data Atomic a => Cons a = CCons Cons Cons 
                          | CAtom a

Ale to nie zadziała, ponieważ wymaga, aby wszystkie atomy w drzewie były tego samego typu. Chcemy, aby różniły się od liścia do liścia. Lepsze podejście wymaga użycia egzystencjalnych kwantyfikatorów Haskella :

class Atomic a where ?????
data Cons = CCons Cons Cons 
            | forall a. Atomic a => CAtom a 

Ale teraz dochodzisz do sedna sprawy. Co możesz zrobić z atomami w tego rodzaju strukturze? Jaką wspólną strukturę można by modelować Atomic a? Jaki poziom bezpieczeństwa typu gwarantuje taki typ? Zauważ, że nie dodaliśmy żadnych funkcji do naszej klasy typów i jest dobry powód: atomy nie mają ze sobą nic wspólnego w Lisp. Ich nadtyp w Lispie jest po prostu nazywany t(tj. Top).

Aby ich użyć, musiałbyś wymyślić mechanizmy dynamicznego przekształcania wartości atomu w coś, czego faktycznie możesz użyć. W tym momencie w zasadzie zaimplementowałeś podsystem dynamicznie typowany w swoim języku statycznym! (Nie można nie wspomnieć o możliwym następstwie dziesiątej zasady programowania Greenspun ).

Zauważ, że Haskell zapewnia obsługę właśnie takiego dynamicznego podsystemu z Objtypem, używanego w połączeniu z Dynamictypem i klasą Typeable w celu zastąpienia naszej Atomicklasy, które pozwalają na przechowywanie dowolnych wartości z ich typami i jawne wymuszanie z powrotem z tych typów. To jest rodzaj systemu, którego będziesz potrzebować, aby pracować ze strukturami wad Lispa w ich pełnej ogólności.

Możesz także pójść w drugą stronę i osadzić statycznie typowany podsystem w zasadniczo dynamicznie typowanym języku. Pozwala to na skorzystanie ze statycznego sprawdzania typu dla części programu, które mogą korzystać z bardziej rygorystycznych wymagań dotyczących typów. Wydaje się, że jest to podejście przyjęte na przykład w ograniczonej formie dokładnego sprawdzania typu przez CMUCL .

Wreszcie istnieje możliwość posiadania dwóch oddzielnych podsystemów, dynamicznie i statycznie typowanych, które używają programowania w stylu kontraktu, aby ułatwić nawigację w przejściu między nimi. W ten sposób język może dostosować się do zastosowań Lispa, w których statyczne sprawdzanie typów byłoby bardziej przeszkodą niż pomocą, a także używa, w których statyczne sprawdzanie typów byłoby korzystne. Jest to podejście przyjęte przez Typed Racket , jak widać z poniższych komentarzy.

Moja odpowiedź, bez wysokiego stopnia pewności, brzmi prawdopodobnie . Jeśli spojrzysz na przykład na język taki jak SML i porównasz go z Lispem, rdzeń funkcjonalny każdego z nich jest prawie identyczny. W rezultacie nie wydaje się, żebyś miał problemy z zastosowaniem jakiegoś statycznego wpisywania do rdzenia Lispa (zastosowanie funkcji i wartości pierwotne).

Twoje pytanie jest jednak pełne i tam, gdzie widzę, że pojawia się problem, jest podejście kod jako dane. Typy istnieją na bardziej abstrakcyjnym poziomie niż wyrażenia. Lisp nie ma tego rozróżnienia - wszystko ma „płaską” strukturę. Jeśli weźmiemy pod uwagę jakieś wyrażenie E: T (gdzie T jest jakąś reprezentacją swojego typu), a następnie uznamy to wyrażenie za zwykłe dane, to jaki dokładnie jest tutaj typ T? Cóż, to rodzaj! Rodzaj jest wyższym typem zamówienia, więc po prostu powiedzmy coś o tym w naszym kodzie:

E : T :: K

Możesz zobaczyć, dokąd z tym zmierzam. Jestem pewien, że oddzielając informacje o typie od kodu, można by uniknąć tego rodzaju odwoływania się do siebie, ale to sprawiłoby, że typy nie byłyby zbyt „seplenienie” w swoim smaku. Prawdopodobnie jest na to wiele sposobów, chociaż nie jest dla mnie oczywiste, który z nich byłby najlepszy.

EDYCJA: Och, więc przy odrobinie googlowania znalazłem Qi , która wydaje się być bardzo podobna do Lispa, z wyjątkiem tego, że jest wpisywana statycznie. Być może jest to dobre miejsce, aby zacząć sprawdzać, gdzie wprowadzili zmiany, aby wprowadzić tam statyczne wpisywanie.

Dylan: rozszerzenie systemu typów Dylana w celu lepszego wnioskowania o typie i wykrywania błędów