Kategoryzacja systemów typów (mocna / słaba, dynamiczna / statyczna)

23

W skrócie: w jaki sposób kategoryzowane są systemy typów w kontekście akademickim; w szczególności, gdzie mogę znaleźć renomowane źródła, które wyraźnie rozróżniają różne systemy typów?

W pewnym sensie trudność związana z tym pytaniem nie polega na tym, że nie mogę znaleźć odpowiedzi, ale raczej na tym, że mogę znaleźć zbyt wiele i żadne z nich nie wyróżnia się jako poprawne. Tło stanowi próbę ulepszenia artykułu na wiki Haskell o pisaniu na maszynie , który obecnie ma następujące różnice:

  • Bez pisania: w języku nie ma pojęcia typów ani z perspektywy typowania: w języku jest dokładnie jeden typ. Język asemblera ma tylko „wzorzec bitowy”, Rexx i Tk mają tylko „tekst”, rdzeń MatLab ma tylko typ „macierz o złożonej wartości”.
  • Słabe pisanie: Istnieje tylko kilka wyróżnionych typów i być może synonimy typów dla kilku typów. Np. C używa liczb całkowitych dla logicznych, liczb całkowitych, znaków, zestawów bitów i wyliczeń.
  • Mocne pisanie: drobnoziarnisty zestaw typów, takich jak w Adzie, wirthian (Pascal, Modula-2), Eiffel

Jest to całkowicie sprzeczne z moją osobistą percepcją, która bardziej przypominała:

  • Słabe pisanie: Obiekty mają typy, ale są domyślnie konwertowane na inne typy, gdy wymaga tego kontekst. Na przykład Perl, PHP i JavaScript to wszystkie języki, w których "1"można używać mniej więcej w dowolnym kontekście 1.
  • Silne pisanie: Obiekty mają typy i nie ma niejawnych konwersji (chociaż można je symulować przy przeciążeniu), więc użycie obiektu w niewłaściwym kontekście jest błędem. W Pythonie indeksowanie tablicy ciągiem lub liczbą zmiennoprzecinkową powoduje wyjątek TypeError; w Haskell zakończy się niepowodzeniem w czasie kompilacji.

Poprosiłem o opinie na ten temat od innych osób bardziej doświadczonych w tej dziedzinie niż ja, a jedną z tych cech scharakteryzowałem:

  • Słabe pisanie: Wykonywanie nieprawidłowych operacji na danych nie jest kontrolowane ani odrzucane, a jedynie powoduje nieprawidłowe / arbitralne wyniki.
  • Silne pisanie: Operacje na danych są dozwolone tylko wtedy, gdy dane są zgodne z operacją.

Jak rozumiem, pierwsza i ostatnia charakterystyka nazwałaby C słabym typem, druga nazwałaby to silnym typem. Pierwszy i drugi wywoływałyby słaby typ Perla i PHP, a trzeci wywoływałby je silnie napisane. Wszyscy trzej opisaliby Python jako silnie wpisany.

Myślę, że większość ludzi powiedziałaby mi „no cóż, nie ma konsensusu, nie ma akceptowanego znaczenia terminów”. Jeśli osoby te są błędne, byłbym szczęśliwy, aby usłyszeć o tym, ale jeśli mają rację, to jak mają naukowcy CS opisać i porównać systemy typu? Jakiej terminologii mogę użyć, która jest mniej problematyczna?

Jako powiązane pytanie czuję, że dynamiczne / statyczne rozróżnienie jest często podawane w kategoriach „czasu kompilacji” i „czasu wykonywania”, co uważam za niezadowalające, biorąc pod uwagę, że to, czy język jest kompilowany, nie jest jego własnością jako jego implementacje. Uważam, że powinien istnieć czysto semantyczny opis pisania dynamicznego kontra statycznego; coś w stylu „języka statycznego to taki, w którym można wpisać każde podwyrażenie”. Byłbym wdzięczny za wszelkie przemyślenia, szczególnie odniesienia, które nadają temu pojęciu jasności.

Ben Millwood
źródło
6
Myślę, że masz już odpowiedź: nie ma przyjętej definicji słabego i mocnego pisania.
svick,
Nie trudno mi było w to uwierzyć, ale zadaję to pytanie w nadziei, że jest takie, o którym po prostu nie słyszałem :) lub przynajmniej definicja bardziej autorytatywna niż to, co uważa ktoś, kto edytował wiki. .
Ben Millwood,
3
Aby uzyskać więcej dyskusji na ten temat, zobacz to powiązane pytanie dotyczące SO .
svick,
1
Aby wzmocnić punkt Svicka, nie można znaleźć referencji autorytetu w sprawie czegoś, co nie jest akceptowane. Wszystko, co twierdzi, że jest autorytatywne, byłoby po prostu błędne (ponieważ można podać dowolną liczbę kontrprzykładów).
edA-qa mort-ora-y
Cóż, istnieje różnica między kimś, kto pisze artykuł, który mówi „oto jedna prawdziwa definicja, na którą wszyscy się zgadzają”, a kimś, kto pisze artykuł, który mówi „oto definicje, których zamierzam użyć w tym artykule, chociaż wiem, że są inne ”. Nawet ten ostatni byłby lepszy niż to, co do tej pory wiem. Myślę, że możesz mieć rację, choć w tym przypadku, co mają ludzie mają do powiedzenia na temat różnych rodzajów systemu typu? Czy rozróżnienie dynamiczne / statyczne jest przynajmniej konkretne?
Ben Millwood

Odpowiedzi:

18

Historycznie termin „silnie typowany język programowania” pojawił się w latach 70. w reakcji na istniejące powszechnie używane języki programowania, z których większość zawierała dziury. Kilka przykładów:

  • W Fortranie istniały rzeczy zwane obszarami pamięci „WSPÓLNE”, które mogły być współużytkowane przez moduły, ale nie było sprawdzania, czy każdy moduł deklaruje zawartość pamięci WSPÓLNEJ tego samego typu. Tak więc jeden moduł może zadeklarować, że konkretny wspólny blok pamięci ma liczbę całkowitą, a inny liczbę zmiennoprzecinkową, w wyniku czego dane zostaną uszkodzone. Fortran miał także instrukcje „RÓWNOWAŻNOŚĆ”, w których to samym magazynie można było zadeklarować, że zawiera dwa różne obiekty różnych typów.

  • W Algolu 60 typ parametrów procedury został zadeklarowany jako „procedura”, bez określania typów parametrów procedury. Można więc założyć, że parametr procedury był procedurą akceptującą liczby całkowite, ale przekazał jako argument procedurę akceptacji rzeczywistej. Spowodowałoby to ten sam rodzaj korupcji, co oświadczenia WSPÓLNE i RÓWNOWAŻNE. (Jednak Algol 60 wyeliminował starsze problemy).

  • W Pascalu dodano „zapisy wariantów”, które były prawie dokładnie tak, jak stare oświadczenia EQUIVALENCE.

  • W C dodano „rzutowania typu”, dzięki czemu każdy typ danych może być ponownie interpretowany jako dane innego typu. Była to raczej celowa luka przeznaczona dla programistów, którzy podobno wiedzą, co robią.

Silnie napisane języki zaprojektowane w latach 70. miały na celu wyeliminowanie wszystkich takich dziur. Jeśli zagłębisz się w to, co to oznacza, oznacza to zasadniczo, że reprezentacje danych są chronione. Nie można wyświetlić obiektu danych jednego typu jako obiektu innego typu, który ma taki sam wzór bitowy jak jego wewnętrzna reprezentacja. Teoretycy zaczęli używać terminu „niezależność reprezentacji”, aby scharakteryzować tę właściwość, zamiast niejasnego pojęcia „silnego pisania”.

Należy zauważyć, że języki dynamicznie wpisywane, takie jak Lisp, które wykonują pełne sprawdzanie typów w czasie wykonywania, są „mocno wpisywane” w sensie ochrony reprezentacji. Jednocześnie statycznie wpisane języki straciłyby niezależność reprezentacji, chyba że sprawdzą granice tablic. Nie są więc „mocno wpisane” w ścisłym tego słowa znaczeniu. Z powodu tych anomalnych konsekwencji termin „mocno wpisany na maszynie” przestał być używany po latach 70-tych. Kiedy Departament Obrony USA opracował rygorystyczne wymagania dotyczące projektowania Ady, obejmowały one wymóg, aby język był „silnie pisany”. (Wydaje się, że w tamtym czasie uważano, że idea „silnego pisania” była oczywista. Nie podano definicji. ) Wszystkie propozycje językowe przedstawione w odpowiedzi twierdziły, że są „silnie napisane”. Kiedy Dijkstra przeanalizował wszystkie propozycje językowe, stwierdził, że żadna z nich nie została napisana na maszynie i w rzeczywistości nie było nawet jasne, co oznacza ten termin. Zobacz raportEWD663 . Widzę jednak, że termin ten powraca teraz do użytku przez młodsze pokolenie badaczy, którzy nie znają burzliwej historii tego terminu.

Termin „typowanie statyczne” oznacza, że ​​wszystkie sprawdzanie typu odbywa się statycznie i nie wystąpią żadne błędy typu w czasie wykonywania. Jeśli język jest również mocno wpisany, oznacza to, że tak naprawdę nie ma błędów podczas wykonywania. Jeśli z drugiej strony są dziury w systemie typów, brak błędów typu w czasie wykonywania nic nie znaczy. Wyniki mogą być całkowicie zepsute.

Nowa debata na temat „silnego i słabego pisania” wydaje się dotyczyć tego, czy niektóre konwersje typów powinny być dozwolone. Zezwalanie na ciąg, w którym wymagana jest liczba całkowita, jest „słabym typowaniem” według tych ludzi. Ma to pewien sens, ponieważ próba konwersji łańcucha na liczbę całkowitą może się nie powieść, jeśli łańcuch nie reprezentuje liczby całkowitej. Jednak konwersja liczby całkowitej na ciąg nie ma tego problemu. Czy według tych ludzi byłby to przypadek „słabego pisania”? Nie mam pojęcia. Zauważam, że dyskusje Wikipedii na temat „słabego pisania” nie cytują żadnych recenzowanych publikacji. Nie wierzę, że jest to spójny pomysł.

Dodano uwagę : podstawową kwestią jest to, że termin „mocne pisanie na klawiaturze” nie wszedł w życie jako termin techniczny o ścisłej definicji. Było to bardziej jak niektórzy projektanci języków: „nasz system pisma jest silny; wyłapuje wszystkie błędy pisma; nie ma dziur”, a więc, kiedy opublikowali swój projekt języka, twierdzili, że był „mocno wpisany” . To było modne słowo, które brzmiało dobrze i ludzie zaczęli go używać. Artykuł Cardelli-Wegner był pierwszym, który widziałem, w którym przedstawiono analizę tego, co to znaczy. Mój post tutaj należy traktować jako rozwinięcie ich stanowiska.

Uday Reddy
źródło
Czy możesz podać jakieś odniesienia do historycznego rozwoju? „brak błędów typu wykonania nic nie znaczy” - czy masz na myśli czas kompilacji?
Raphael
Oto artykuł na temat Euclid, który pojawił się w Google Scholar. Pamiętam, jak widziałem kilka artykułów z lat 70., w których twierdzono, że języki są mocno pisane na maszynie. Ogólnie uważano, że to sprzedaż.
Uday Reddy,
1
@Raphael. Miałem na myśli „błędy typu czasu wykonywania”. Aby przejść do czasu wykonywania, program musiałby przede wszystkim ominąć sprawdzanie typu statycznego. Chodzi o to, że język silnie typowany, np. Java, będzie dawał błędy typu w czasie wykonywania, gdy nie będzie w stanie ich sprawdzić w czasie kompilacji. Język do wpisywania tekstu, np. C, pozwala produkować śmieci w czasie wykonywania zamiast dawać błędy.
Uday Reddy,
1
@benmachine. Zobacz sekcję „Sprawdzanie typu” w cytowanym przeze mnie dokumencie Euclid. Myślę, że główną kwestią jest to, że słowo „mocno wpisane” to popularne słowo. To nie jest pojęcie techniczne. W najlepszym razie jego zawartość techniczna oznacza, że ​​nie ma żadnych otworów typu.
Uday Reddy,
1
W typowej nowoczesnej implementacji, w której dwa różne typy liczb całkowitych mają tę samą reprezentację (np. Oba inti longmają 32 bity lub oba longi long longmają 64 bity, program, który używa wskaźnika do jednego takiego typu do zapisywania pewnej ilości pamięci i używa wskaźnika innego typu jego odczytanie nie spowoduje na ogół wykrywalnego błędu w czasie wykonywania, ale może dowolnie działać nieprawidłowo w dowolny inny sposób. Współczesny język C traci zatem bezpieczeństwo typowe innych języków, nie uzyskując żadnej semantyki, jaką miały jakościowe implementacje języka Ritchiego dawniej oferowany w zamian
supercat
7

Artykuł, który Uday Reddy znalazł w swojej odpowiedzi, On Understanding Types, Data Abstraction and Polymorphism (1985), daje następujące odpowiedzi:

Mówi się, że języki programowania, w których typ każdego wyrażenia można określić za pomocą statycznej analizy programu, są typowane statycznie. Wpisywanie statyczne jest użyteczną właściwością, ale wymóg, aby wszystkie zmienne i wyrażenia były powiązane z typem w czasie kompilacji, jest czasami zbyt restrykcyjny. Można go zastąpić słabszym wymogiem, że wszystkie wyrażenia mają być zgodne z typem, chociaż sam typ może być statystycznie nieznany; ogólnie można to zrobić, wprowadzając sprawdzanie typu w czasie wykonywania. Języki, w których wszystkie wyrażenia są zgodne z typem, nazywane są językami silnie typowanymi. Jeśli język jest silnie wpisany, jego kompilator może zagwarantować, że programy, które akceptuje, będą działać bez błędów typu. Ogólnie rzecz biorąc, powinniśmy dążyć do silnego pisania i, w miarę możliwości, stosować pisanie statyczne.

benmachine
źródło
opublikowany jako wiki społeczności, ponieważ nie zasługuję na uznanie za to.
Ben Millwood,
Problem, który tu mam, jest związany z pierwszym komentarzem Svicka. Chociaż może być miło, że znalazłeś definicję silnego pisania, z pewnością nie jest to powszechnie akceptowana definicja.
edA-qa mort-ora-y
@ edA-qamort-ora-y: na jakiej podstawie to mówisz? Czy masz coś lepszego niż anegdotyczne dowody na to, co jest i nie jest powszechnie akceptowane? Jakieś cytaty? (Rozumiem, że możesz mieć rację, nawet jeśli nie, ale nadal uważam, że powyższe odpowiedzi odpowiadają na moje pytanie; nawet jeśli nie ma konsensusu, dobrze jest znać przynajmniej jedną z poważnych odpowiedzi akademickich).
Ben Millwood
1
Naprawdę nie mogę udowodnić braku uzgodnionej definicji, prawda? To nie jest logicznie możliwe. Jednak artykuły Wikipedii na temat silnego pisania na klawiaturze zawierają wiele dowodów i odniesień, co do niezgodności i sprzeczności. en.wikipedia.org/wiki/Strong_typing
edA-qa mort-ora-y
@ edA-qamort-ora-y: Cytaty z Wikipedii nie są tak pomocne: niektóre nie są akademickie, inne cytowane z powodów innych niż zdefiniowanie terminów. Artykuł Typious Programming wydaje się obiecujący, ale na marginesie odnosi się tylko do definicji; może i tak warto edytować moją odpowiedź. Jeśli chodzi o dowód nieobecności, uważam, że wystarczą mi dowody kontrowersji / nieporozumień między ludźmi, którzy wiedzą, o czym mówią, co może mi dać (co zresztą może mi dać artykuł na temat programowania typowego).
Ben Millwood
6

Autorytatywne odpowiedzi można znaleźć w artykule z ankiety Cardelli i Wegnera: O typach zrozumienia, abstrakcji danych i polimorfizmie .

Pamiętaj, że chociaż „mocne pisanie” ma przyjęte znaczenie, „słabe pisanie” nie. Każda awaria silnego pisania może być uważana za słabą, a ludzie mogą różnić się co do tego, jaki rodzaj awarii jest dopuszczalny, a co nie.

Uday Reddy
źródło
Alternatywny URL: lucacardelli.name/Papers/OnUnderstanding.A4.pdf
AProgrammer
Doskonale, właśnie tego chciałem. Artykuł wymaga trochę czytania, więc myślę, że powinna istnieć odpowiedź podsumowująca najważniejsze punkty. Czy powinienem edytować je w swojej odpowiedzi, czy opublikować własną odpowiedź na wiki społeczności? Tak czy inaczej, dam mu jeszcze kilka dni na wypadek, gdyby ktokolwiek miał jakikolwiek wkład, a następnie zaakceptuj wszystko, co pozostało :)
Ben Millwood
@benmachine. Warto przeczytać cały artykuł, ale kwestie pojęciowe na wysokim poziomie omówiono tylko w kilku pierwszych sekcjach.
Uday Reddy,
4
Nadal uważam, że należy to streścić na tej stronie. Link może wygasnąć później.
Ben Millwood,
@benmachine. Zapraszamy do opublikowania podsumowania jako własnej odpowiedzi na pytanie.
Uday Reddy