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

107

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?

Lambda Przedostatnia
źródło
10
Podoba mi się dowolne makra Lispa, ale podoba mi się solidność systemu typów Haskella. Chciałbym zobaczyć, jak wygląda Lisp wpisany statycznie.
mcandre
4
Dobre pytanie! Uważam, że shenlanguage.org to robi. Chciałbym, żeby stało się bardziej mainstreamowe.
Hamish Grubijan
Jak wykonujesz symboliczne obliczenia z Haskellem? (rozwiąż 'x' (= (+ xy) (* xy))). Jeśli umieścisz go w łańcuchu, nie ma sprawdzania (w przeciwieństwie do Lispa, który może używać makr, aby dodać sprawdzanie). Jeśli używasz algebraicznych typów danych lub list ... Będzie to bardzo rozwlekłe: rozwiąż (Sym "x") (Eq (Plus (Sym "x") (Sym "y")) (Mult (Sym "x") (Sym "y")))
aoeu256

Odpowiedzi:

57

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.

Eli Barzilay
źródło
1
Problem polega na tym, jaki jest typ listy, która składa się na cały kod źródłowy programu rakietowego.
Zorf
18
Zwykle tak by było Sexpr.
Eli Barzilay
Ale wtedy mogę pisać coerce :: a->bw kategoriach eval. Gdzie jest typ bezpieczeństwa?
raz
2
@ssice: kiedy używasz funkcji bez typu, na przykład evalmusisz przetestować wynik, aby zobaczyć, co się pojawi, co nie jest niczym nowym w Typed Racked (taka sama umowa, jak funkcja, która przyjmuje typ unii Stringi Number). Niejawnym sposobem sprawdzenia, czy można to zrobić, jest fakt, że można pisać i używać dynamicznie typowanego języka w języku HM-statycznie typowanym.
Eli Barzilay
37

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.

Owen S.
źródło
16
Ta odpowiedź ma fundamentalny problem: zakładasz, że statyczne systemy typów muszą być typu HM. Podstawową koncepcją, której nie można tam wyrazić i która jest ważną cechą kodu Lispa, jest podtytuł. Jeśli spojrzysz na rakietę pisaną na maszynie, zobaczysz, że może ona łatwo wyrazić dowolną listę - w tym takie jak (Listof Integer)i (Listof Any). Oczywiście podejrzewasz, że ta ostatnia jest bezużyteczna, ponieważ nic nie wiesz o typie, ale w TR możesz później użyć, (if (integer? x) ...)a system będzie wiedział, że xjest to liczba całkowita w pierwszej gałęzi.
Eli Barzilay,
5
Aha, i jest to zła charakterystyka rakiety maszynowej (która różni się od niesprawnych systemów typów, które można znaleźć w niektórych miejscach). Wpisane Rakieta jest statycznie wpisane język, bez narzutu wykonawczego dla kodu pisanego. Rakieta nadal umożliwia pisanie kodu w TR, a innych w zwykłym języku bez typu - iw takich przypadkach kontrakty (kontrole dynamiczne) są używane do ochrony wpisanego kodu przed potencjalnie niewłaściwym nietypowym kodem.
Eli Barzilay,
1
@Eli Barzilay: Kłamałem, są cztery części: 4. Interesujące jest dla mnie to, jak przyjęty w branży styl kodowania C ++ stopniowo odchodzi od podtypów w kierunku generycznych. Wadą jest to, że język nie zapewnia pomocy w deklarowaniu interfejsu, z którego będzie korzystać funkcja ogólna, w czym z pewnością mogą pomóc klasy typów. Ponadto C ++ 0x może dodawać wnioskowanie o typie. Przypuszczam, że nie HM, ale pełzasz w tym kierunku?
Owen S.,
1
Owen: (1) głównym punktem jest to, że potrzebujesz podtypów, aby wyrazić rodzaj kodu, który piszą lispers - a nie możesz tego mieć z systemami HM, więc jesteś zmuszony do niestandardowych typów i konstruktorów dla każdego użycia, co sprawia, że ​​całość jest znacznie bardziej niewygodna w użyciu. W rakietach maszynowych użycie systemu z podtypami było konsekwencją celowej decyzji projektowej: aby wynik był w stanie wyrazić typy takiego kodu bez zmiany kodu lub tworzenia niestandardowych typów.
Eli Barzilay,
1
(2) Tak, dynamictypy stają się popularne w językach statycznych jako rodzaj obejścia, aby uzyskać niektóre korzyści z języków dynamicznie wpisywanych, przy czym zwykłe kompromisy tych wartości są opakowane w sposób, który umożliwia identyfikację typów. Ale także tutaj rakieta pisana na maszynie radzi sobie bardzo dobrze, czyniąc ją wygodną w obrębie języka - narzędzie do sprawdzania typów wykorzystuje wystąpienia predykatów, aby dowiedzieć się więcej o typach. Na przykład, zobacz wpisany przykład na stronie rakiety i zobacz, jak string?„redukuje” listę strun i numerów do listy strun.
Eli Barzilay,
10

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.

Gian
źródło
Wydaje się, że następna iteracja po Qi to Shen , opracowana przez tę samą osobę.
Diagon
4

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

Rainer Joswig
źródło
Link nie działa. Ale w każdym razie Dylan nie jest wpisywany statycznie.
Björn Lindqvist
@ BjörnLindqvist: ten odsyłacz prowadził do pracy magisterskiej o dodawaniu stopniowego pisania do Dylana.
Rainer Joswig
1
@ BjörnLindqvist: Podałem link do artykułu przeglądowego.
Rainer Joswig
Ale stopniowe pisanie nie liczy się jako wpisywanie statyczne. Gdyby tak było, to Pypy byłby Pythonem statycznym typem, ponieważ używa również typowania stopniowego.
Björn Lindqvist
2
@ BjörnLindqvist: jeśli dodamy typy statyczne poprzez stopniowe wpisywanie i są one sprawdzane podczas kompilacji, to jest to typowanie statyczne. Po prostu nie chodzi o to, że cały program jest zapisywany statycznie, ale części / regiony. homes.sice.indiana.edu/jsiek/what-is-gradual-typing 'Stopniowe typowanie to system typów, który opracowałem wraz z Walidem Tahą w 2006 roku, który umożliwia dynamiczne wpisywanie części programu i statyczne wpisywanie innych części.'
Rainer Joswig