Typ systemu - Type system

W językach programowania , o układ typu jest system logiczny zawierający zbiór zasad, które przypisuje właściwość o nazwie typu do różnych konstruktów do programu komputerowego , takich jak zmienne , wyrażenia , funkcje i moduły . Te typy formalizują i wymuszają niejawne kategorie, których programista używa dla algebraicznych typów danych, struktur danych lub innych komponentów (np. "string", "array of float", "funkcja zwracająca wartość logiczną"). Głównym celem systemu typów jest zmniejszenie możliwości występowania błędów w programach komputerowych poprzez zdefiniowanie interfejsów między różnymi częściami programu komputerowego, a następnie sprawdzenie, czy części zostały połączone w spójny sposób. To sprawdzanie może odbywać się statycznie (w czasie kompilacji ), dynamicznie (w czasie wykonywania ) lub jako kombinacja obu. Systemy typu mają również inne cele, takie jak wyrażanie reguł biznesowych, umożliwienie pewnych optymalizacji kompilatora , umożliwienie wielokrotnej wysyłki , udostępnienie formy dokumentacji itp.

System typów kojarzy typ z każdą obliczoną wartością i badając przepływ tych wartości, próbuje zapewnić lub udowodnić, że nie mogą wystąpić żadne błędy typu . Dany system typów, o którym mowa, określa, co stanowi błąd typu, ale generalnie celem jest zapobieganie używaniu operacji oczekujących pewnego rodzaju wartości z wartościami, dla których ta operacja nie ma sensu (błędy ważności). Systemy typów są często określane jako część języków programowania i wbudowane w interpretery i kompilatory, chociaż system typów języka można rozszerzyć za pomocą opcjonalnych narzędzi, które wykonują dodatkowe sprawdzenia przy użyciu oryginalnej składni i gramatyki języka.

Przegląd użytkowania

Przykładem prostego systemu typów jest język C . Części programu w C to definicje funkcji . Jedna funkcja jest wywoływana przez inną funkcję. Interfejs funkcji podaje nazwę funkcji i listę parametrów, które są przekazywane do kodu funkcji. Kod funkcji wywołującej podaje nazwę wywoływanej wraz z nazwami zmiennych, które przechowują wartości, które mają być do niej przekazane. Podczas wykonywania wartości są umieszczane w pamięci tymczasowej, a następnie wykonanie przeskakuje do kodu wywołanej funkcji. Kod wywołanej funkcji uzyskuje dostęp do wartości i korzysta z nich. Jeśli instrukcje wewnątrz funkcji są napisane z założeniem otrzymania wartości całkowitej , ale kod wywołujący przekazał wartość zmiennoprzecinkową , to wywoływana funkcja obliczy błędny wynik. Kompilator języka C sprawdza typy argumentów przekazywanych do funkcji, gdy jest ona wywoływana z typami parametrów zadeklarowanych w definicji funkcji. Jeśli typy nie są zgodne, kompilator zgłasza błąd w czasie kompilacji.

Kompilator może również użyć typu statyczne o wartości do optymalizacji pamięci masowej potrzebuje i wybór algorytmów dla operacji na wartości. W wielu kompilatorach C typ danych float jest na przykład reprezentowany w 32 bitach , zgodnie ze specyfikacją IEEE dla liczb zmiennoprzecinkowych o pojedynczej precyzji . Będą zatem używać operacji mikroprocesorowych specyficznych dla zmiennoprzecinkowych na tych wartościach (dodawanie zmiennoprzecinkowe, mnożenie itp.).

Głębokość ograniczeń typu i sposób ich oceny wpływają na typowanie języka. Język programowania może dodatkowo powiązać operację z różnych rozdzielczościach dla każdego typu, w przypadku polimorfizmu typu . Teoria typów to nauka o systemach typów. Konkretne typy niektórych języków programowania, takie jak liczby całkowite i łańcuchy, zależą od praktycznych zagadnień związanych z architekturą komputera, implementacją kompilatora i projektowaniem języka.

Podstawy

Formalnie teoria typów bada systemy typów. Język programowania musi mieć możliwość sprawdzenia typu za pomocą systemu typów, czy to w czasie kompilacji, czy w czasie wykonywania, ręcznie adnotowanych lub automatycznie wywnioskowanych. Jak zwięźle ujął to Mark Manasse :

Podstawowym problemem, którym zajmuje się teoria typów, jest zapewnienie, że programy mają znaczenie. Podstawowym problemem spowodowanym przez teorię typów jest to, że znaczące programy mogą nie mieć przypisanego im znaczenia. Z tego napięcia wynika poszukiwanie bogatszych typów systemów.

Przypisanie typu danych, określane jako typing , nadaje znaczenie sekwencji bitów, takiej jak wartość w pamięci lub jakiś obiekt, taki jak zmienna . Sprzęt komputera ogólnego przeznaczenia nie jest w stanie odróżnić na przykład adresu pamięci od kodu instrukcji lub znaku , liczby całkowitej lub liczby zmiennoprzecinkowej , ponieważ nie dokonuje samoistnego rozróżnienia między żadną z możliwych wartości, które sekwencja bitów może oznaczać . Skojarzenie sekwencji bitów z typem przekazuje to znaczenie programowalnemu sprzętowi w celu utworzenia systemu symbolicznego złożonego z tego sprzętu i jakiegoś programu.

Program kojarzy każdą wartość z co najmniej jednym określonym typem, ale może się również zdarzyć, że jedna wartość jest powiązana z wieloma podtypami . Inne jednostki, takie jak obiekty , moduły , kanały komunikacyjne i zależności, mogą zostać powiązane z typem. Nawet typ może zostać powiązany z typem. Implementacja systemu typów może teoretycznie kojarzyć identyfikacje zwane typem danych (typ wartości), klasą (typ obiektu) i rodzajem ( typ typu lub metatypem). Są to abstrakcje, przez które może przejść pisanie na hierarchii poziomów zawartych w systemie.

Kiedy język programowania ewoluuje w bardziej skomplikowany system typów, zyskuje bardziej drobnoziarnisty zestaw reguł niż podstawowe sprawdzanie typów, ale ma to swoją cenę, gdy wnioskowanie o typie (i inne właściwości) stają się nierozstrzygalne i kiedy więcej uwagi musi być zwrócone przez programista do adnotacji kodu lub rozważenia operacji i działania związanych z komputerem. Trudno jest znaleźć wystarczająco ekspresyjny system typów, który spełnia wszystkie praktyki programowania w sposób bezpieczny dla typów .

Im więcej ograniczeń typu nałożonych przez kompilator, tym silniejszy jest język programowania. Języki z silną typizacją często wymagają od programisty dokonania jawnej konwersji w kontekstach, w których niejawna konwersja nie spowodowałaby szkody. System typów Pascala został opisany jako „zbyt silny”, ponieważ na przykład rozmiar tablicy lub łańcucha jest częścią jego typu, co utrudnia niektóre zadania programistyczne. Haskell jest również silnie typowany, ale jego typy są automatycznie wywnioskowane, więc jawne konwersje są często niepotrzebne.

Kompilator języka programowania może również zaimplementować typ zależny lub system efektów , który umożliwia weryfikację jeszcze większej liczby specyfikacji programu przez sprawdzanie typu. Poza prostymi parami typu wartość, wirtualny „region” kodu jest powiązany z komponentem „efektu” opisującym, co jest robione z what , i umożliwiającym na przykład „zgłoszenie” raportu o błędzie. Zatem system symboliczny może być systemem typu i efektu , co daje mu więcej kontroli bezpieczeństwa niż samego typu.

Niezależnie od tego, czy jest zautomatyzowany przez kompilator, czy określony przez programistę, system typów sprawia, że ​​zachowanie programu jest nielegalne, jeśli wykracza poza reguły systemu typów. Zalety zapewniane przez systemy typu programistycznego obejmują:

  • Abstrakcja (lub modularność ) – typy umożliwiają programistom myślenie na wyższym poziomie niż bit lub bajt, nie zawracając sobie głowy implementacją niskopoziomową. Na przykład programiści mogą zacząć myśleć o łańcuchu jako o zestawie wartości znakowych, a nie o zwykłej tablicy bajtów. Co więcej, typy umożliwiają programistom myślenie i wyrażanie interfejsów między dwoma podsystemami o dowolnej wielkości. Umożliwia to więcej poziomów lokalizacji, dzięki czemu definicje wymagane do współdziałania podsystemów pozostają spójne, gdy te dwa podsystemy komunikują się.
  • Dokumentacja – w bardziej ekspresyjnych systemach typów typy mogą służyć jako forma dokumentacji wyjaśniającej intencje programisty. Na przykład, jeśli programista deklaruje funkcję jako zwracającą typ datownika, dokumentuje to funkcję, gdy typ datownika może być jawnie zadeklarowany głębiej w kodzie jako typ całkowity.

Zalety zapewniane przez systemy typu określonego przez kompilator obejmują:

  • Optymalizacja — statyczne sprawdzanie typu może dostarczyć przydatnych informacji w czasie kompilacji. Na przykład, jeśli typ wymaga, aby wartość była wyrównana w pamięci do wielokrotności czterech bajtów, kompilator może być w stanie użyć bardziej wydajnych instrukcji maszynowych.
  • Bezpieczeństwo — system typów umożliwia kompilatorowi wykrywanie bezsensownego lub nieprawidłowego kodu. Na przykład możemy zidentyfikować wyrażenie 3 / "Hello, World"jako nieprawidłowe, gdy zasady nie określają, jak podzielić liczbę całkowitą przez łańcuch . Mocne pisanie zapewnia większe bezpieczeństwo, ale nie gwarantuje pełnego bezpieczeństwa pisania .

Wpisz błędy

Błąd typu to niezamierzony stan, który może objawiać się na wielu etapach rozwoju programu. Dlatego w systemie typograficznym potrzebne jest urządzenie do wykrywania błędu. W niektórych językach, takich jak Haskell, dla których wnioskowanie o typie jest zautomatyzowane, kompilator może mieć dostęp do lint , aby pomóc w wykryciu błędu.

Bezpieczeństwo typów przyczynia się do poprawności programu , ale może gwarantować poprawność tylko kosztem uczynienia samego sprawdzania typu problemem nierozstrzygalnym . W systemie typów z automatycznym sprawdzaniem typów program może działać niepoprawnie, ale nie powodować błędów kompilatora. Dzielenie przez zero jest niebezpieczną i niepoprawną operacją, ale program do sprawdzania typu działający w czasie kompilacji nie skanuje tylko w poszukiwaniu dzielenia przez zero w większości języków, a następnie pozostaje jako błąd w czasie wykonywania . Aby udowodnić brak tych wad, powszechnie stosuje się inne rodzaje metod formalnych , określanych zbiorczo jako analizy programowe . Alternatywnie, wystarczająco ekspresyjny system typów, taki jak w językach z typami zależnymi, może zapobiec tego rodzaju błędom (na przykład wyrażanie typu liczb niezerowych ). Ponadto testowanie oprogramowania jest empiryczną metodą wyszukiwania błędów, których nie jest w stanie wykryć kontroler typu.

Sprawdzanie typu

Proces weryfikacji i wymuszania ograniczeń typówsprawdzanie typów — może nastąpić w czasie kompilacji (kontrola statyczna) lub w czasie wykonywania . Jeśli specyfikacja języka wymaga silnych reguł typowania (tj. mniej lub bardziej zezwalających tylko na te automatyczne konwersje typów , które nie tracą informacji), można odnieść się do procesu jako strong typed , jeśli nie, jako poorly typed . Terminy nie są zwykle używane w ścisłym znaczeniu.

Sprawdzanie typu statycznego

Statyczne sprawdzanie typu to proces weryfikacji bezpieczeństwa typu programu oparty na analizie tekstu programu ( kodu źródłowego ). Jeśli program przejdzie pomyślnie sprawdzanie typu statycznego, to gwarantuje, że program spełni pewien zestaw właściwości bezpieczeństwa typu dla wszystkich możliwych danych wejściowych.

Statyczne sprawdzanie typu może być uważane za ograniczoną formę weryfikacji programu (patrz bezpieczeństwo typów ), aw języku bezpiecznym dla typu może być również uważane za optymalizację. Jeśli kompilator może udowodnić, że program jest dobrze napisany, nie musi emitować dynamicznych kontroli bezpieczeństwa, dzięki czemu wynikowy skompilowany plik binarny będzie działał szybciej i jest mniejszy.

Statyczne sprawdzanie typu dla języków z pełnym Turingiem jest z natury konserwatywne. Oznacza to, że jeśli system typ jest zarówno dźwięku (co oznacza, że odrzuca wszystkie niepoprawne programy) i rozstrzygalne (co oznacza, że możliwe jest, aby napisać algorytm, który określa, czy program jest dobrze wpisane), to musi być niekompletne (czyli tam są poprawnymi programami, które również są odrzucane, mimo że nie napotykają błędów w czasie wykonywania). Rozważmy na przykład program zawierający kod:

if <complex test> then <do something> else <signal that there is a type error>

Nawet jeśli wyrażenie <complex test>zawsze ocenia się truew czasie wykonywania, większość programów sprawdzających typ odrzuci program jako źle wpisany, ponieważ statyczne analizatorowi trudno (jeśli nie niemożliwe) jest określenie, że elsegałąź nie zostanie pobrana. W związku z tym statyczny kontroler typu szybko wykryje błędy typu w rzadko używanych ścieżkach kodu. Bez statycznego sprawdzania typu nawet testy pokrycia kodu ze 100% pokryciem mogą nie być w stanie znaleźć takich błędów typu. Testy mogą nie wykryć tego typu błędów, ponieważ należy wziąć pod uwagę kombinację wszystkich miejsc, w których tworzone są wartości i wszystkich miejsc, w których dana wartość jest używana.

Szereg przydatnych i typowych funkcji języka programowania nie może być sprawdzonych statycznie, takich jak downcasting . W związku z tym wiele języków będzie miało zarówno statyczne, jak i dynamiczne sprawdzanie typu; sprawdzanie typu statycznego weryfikuje, co może, a kontrole dynamiczne weryfikują resztę.

Wiele języków ze statycznym sprawdzaniem typu zapewnia sposób na ominięcie sprawdzania typu. Niektóre języki umożliwiają programistom wybór między statycznym a dynamicznym bezpieczeństwem typów. Na przykład C# rozróżnia zmienne typu statycznego i dynamicznego . Zastosowania tych pierwszych sprawdzane są statycznie, podczas gdy drugie są sprawdzane dynamicznie. Inne języki umożliwiają pisanie kodu, który nie jest bezpieczny dla typu; na przykład w C programiści mogą swobodnie rzutować wartość między dowolnymi dwoma typami, które mają ten sam rozmiar, skutecznie obalając koncepcję typu.

Aby zapoznać się z listą języków ze statycznym sprawdzaniem typów, zobacz kategorię dla języków z typami statycznymi .

Dynamiczne sprawdzanie typu i informacje o typie środowiska wykonawczego

Dynamiczne sprawdzanie typu to proces weryfikacji bezpieczeństwa typu programu w czasie wykonywania. Implementacje języków z dynamicznym sprawdzaniem typu zazwyczaj wiążą każdy obiekt środowiska wykonawczego ze znacznikiem typu (tj. odwołaniem do typu) zawierającym informacje o jego typie. Te informacje o typie środowiska uruchomieniowego (RTTI) mogą być również używane do implementowania dynamicznego wysyłania , późnego wiązania , downcastingu , odbicia i podobnych funkcji.

Większość języków bezpiecznych dla typów zawiera pewną formę dynamicznego sprawdzania typów, nawet jeśli mają one również statyczne sprawdzanie typów. Powodem tego jest to, że wiele przydatnych cech lub właściwości jest trudnych lub niemożliwych do zweryfikowania statycznie. Załóżmy na przykład, że program definiuje dwa typy, A i B, gdzie B jest podtypem A. Jeśli program próbuje przekonwertować wartość typu A na typ B, co jest znane jako downcasting , wówczas operacja jest dozwolona tylko jeśli konwertowana wartość jest w rzeczywistości wartością typu B. W związku z tym konieczne jest sprawdzenie dynamiczne, aby sprawdzić, czy operacja jest bezpieczna. Ten wymóg jest jednym z zarzutów obniżania cen.

Z definicji dynamiczne sprawdzanie typu może spowodować awarię programu w czasie wykonywania. W niektórych językach programowania możliwe jest przewidzenie i naprawienie tych awarii. W innych błędy sprawdzania typu są uważane za fatalne.

Języki programowania, które obejmują dynamiczne sprawdzanie typu, ale nie statyczne sprawdzanie typu, są często nazywane „językami programowania z typami dynamicznymi”. Aby zapoznać się z listą takich języków, zobacz kategorię dla dynamicznie wpisanych języków programowania .

Łączenie statycznego i dynamicznego sprawdzania typu

Niektóre języki umożliwiają zarówno statyczne, jak i dynamiczne pisanie. Na przykład Java i niektóre inne języki rzekomo o typach statycznych obsługują rzutowanie typów na ich podtypy , wysyłając zapytania do obiektu w celu wykrycia jego typu dynamicznego i innych operacji na typach, które zależą od informacji o typie środowiska wykonawczego. Innym przykładem jest C++ RTTI . Mówiąc bardziej ogólnie, większość języków programowania zawiera mechanizmy rozsyłania różnych „rodzajów” danych, takich jak rozłączne związki , polimorfizm środowiska uruchomieniowego i typy wariantów . Nawet w przypadku braku interakcji z adnotacjami typu lub sprawdzaniem typu, takie mechanizmy są zasadniczo podobne do implementacji dynamicznego typowania. Zobacz język programowania, aby uzyskać więcej informacji na temat interakcji między typowaniem statycznym i dynamicznym.

Obiekty w językach obiektowych są zwykle dostępne przez odwołanie, którego statyczny typ docelowy (lub typ manifestu) jest równy albo typowi czasu wykonywania obiektu (jego typowi ukrytemu) albo jego nadtypowi. Jest to zgodne z zasadą podstawienia Liskova , która mówi, że wszystkie operacje wykonywane na instancji danego typu mogą być również wykonywane na instancji podtypu. Pojęcie to jest również znane jako polimorfizm subsumpcji lub podtypów . W niektórych językach podtypy mogą również posiadać odpowiednio kowariantne lub kontrawariantne typy zwracane i typy argumentów.

Niektóre języki, na przykład Clojure , Common Lisp lub Cython, są domyślnie sprawdzane dynamicznie, ale pozwalają programom na włączenie statycznego sprawdzania typu poprzez dostarczanie opcjonalnych adnotacji. Jednym z powodów używania takich wskazówek byłaby optymalizacja wydajności krytycznych sekcji programu. Jest to sformalizowane przez stopniowe wpisywanie . Środowisko programistyczne DrRacket , środowisko pedagogiczne oparte na Lispie i prekursor języka Racket, jest również soft-typed.

I odwrotnie, począwszy od wersji 4.0, język C# umożliwia wskazanie, że zmienna nie powinna być sprawdzana statycznie. Zmienna, której typ jest dynamic, nie będzie podlegać statycznemu sprawdzaniu typu. Zamiast tego program opiera się na informacjach o typie środowiska wykonawczego, aby określić, w jaki sposób zmienna może być używana.

W Rust , typ zapewnia dynamiczne typowanie typów. std::any'static

Statyczne i dynamiczne sprawdzanie typu w praktyce

Wybór między typowaniem statycznym a dynamicznym wymaga pewnych kompromisów .

Wpisywanie statyczne może niezawodnie znaleźć błędy typu w czasie kompilacji, co zwiększa niezawodność dostarczanego programu. Jednak programiści nie zgadzają się co do tego, jak często występują błędy typów, co skutkuje dalszymi nieporozumieniami co do proporcji zakodowanych błędów, które zostałyby wychwycone przez odpowiednią reprezentację zaprojektowanych typów w kodzie. Zwolennicy statycznego pisania uważają, że programy są bardziej niezawodne, gdy zostały dobrze sprawdzone, podczas gdy zwolennicy dynamicznego pisania wskazują na rozproszony kod, który okazał się niezawodny, oraz na małe bazy danych błędów. Wartość statycznego typowania wzrasta wraz ze wzrostem siły systemu czcionek. Zwolennicy typowania zależnego zaimplementowanego w językach takich jak Dependent ML i Epigram sugerowali, że prawie wszystkie błędy można uznać za błędy typu, jeśli typy użyte w programie są poprawnie zadeklarowane przez programistę lub poprawnie wywnioskowane przez kompilator.

Wpisywanie statyczne zwykle skutkuje szybszym wykonaniem skompilowanego kodu. Gdy kompilator zna dokładne typy danych, które są w użyciu (co jest niezbędne do weryfikacji statycznej, poprzez deklarację lub wnioskowanie), może wygenerować zoptymalizowany kod maszynowy. Z tego powodu niektóre języki z typami dynamicznymi, takie jak Common Lisp, umożliwiają optymalizację opcjonalnych deklaracji typów.

W przeciwieństwie do tego dynamiczne pisanie może pozwolić kompilatorom działać szybciej, a interpreterom dynamicznie ładować nowy kod, ponieważ zmiany w kodzie źródłowym w dynamicznie pisanych językach mogą skutkować mniejszą liczbą sprawdzania do wykonania i mniejszą ilością kodu do ponownego sprawdzenia. To również może skrócić cykl edycji-kompilacji-testu-debugowania.

Języki o typie statycznym, które nie mają wnioskowania o typie (takie jak C i Java przed wersją 10 ) wymagają, aby programiści deklarowali typy, których musi używać metoda lub funkcja. Może to służyć jako dodana dokumentacja programu, która jest aktywna i dynamiczna, a nie statyczna. Pozwala to kompilatorowi na zapobieganie wychodzeniu z synchronizacji i ignorowaniu przez programistów. Jednak język może być wpisywany statycznie bez konieczności deklaracji typu (przykłady obejmują Haskell , Scala , OCaml , F# i w mniejszym stopniu C# i C++ ), więc jawna deklaracja typu nie jest wymagana dla pisania statycznego we wszystkich językach.

Typowanie dynamiczne umożliwia tworzenie konstrukcji, które niektóre (proste) statyczne sprawdzanie typu odrzuciłyby jako niedozwolone. Możliwe stają się na przykład funkcje eval , które wykonują dowolne dane jako kod. Funkcja eval jest możliwa przy typowaniu statycznym, ale wymaga zaawansowanego użycia algebraicznych typów danych . Co więcej, dynamiczne typowanie lepiej dostosowuje kod przejściowy i prototypowanie, takie jak umożliwienie przejrzystego wykorzystania zastępczej struktury danych ( mock object ) zamiast pełnej struktury danych (zwykle do celów eksperymentowania i testowania).

Pisanie dynamiczne zazwyczaj umożliwia pisanie kaczką (co ułatwia ponowne użycie kodu ). Wiele języków z typowaniem statycznym oferuje również pisanie kaczką lub inne mechanizmy, takie jak programowanie ogólne, które również umożliwiają łatwiejsze ponowne użycie kodu.

Typowanie dynamiczne zazwyczaj ułatwia korzystanie z metaprogramowania . Na przykład szablony C++ są zazwyczaj bardziej kłopotliwe do napisania niż odpowiedniki w Ruby lub Pythonie, ponieważ C++ ma silniejsze reguły dotyczące definicji typów (zarówno dla funkcji, jak i zmiennych). Zmusza to programistę do napisania większej ilości standardowego kodu dla szablonu niż programista w Pythonie. Bardziej zaawansowane konstrukcje uruchomieniowe, takie jak metaklasy i introspekcja, są często trudniejsze w użyciu w językach z typami statycznymi. W niektórych językach takie funkcje mogą być również wykorzystywane np. do generowania nowych typów i zachowań w locie, na podstawie danych run-time. Takie zaawansowane konstrukcje są często dostarczane przez dynamiczne języki programowania ; wiele z nich jest typowanych dynamicznie, chociaż dynamiczne typowanie nie musi być powiązane z dynamicznymi językami programowania .

Systemy typu mocnego i słabego

Języki są często potocznie określane jako silnie typowane lub słabo typowane . W rzeczywistości nie ma powszechnie akceptowanej definicji tego, co oznaczają te terminy. Ogólnie rzecz biorąc, istnieją bardziej precyzyjne terminy reprezentujące różnice między systemami typów, które sprawiają, że ludzie nazywają je „silnymi” lub „słabymi”.

Bezpieczeństwo typu i bezpieczeństwo pamięci

Trzecim sposobem kategoryzacji systemu typów języka programowania jest bezpieczeństwo typowanych operacji i konwersji. Informatycy używają terminu język bezpieczny dla typów do opisania języków, które nie zezwalają na operacje lub konwersje, które naruszają zasady systemu typów.

Informatycy używają terminu język bezpieczny w pamięci (lub po prostu język bezpieczny ) do opisania języków, które nie pozwalają programom na dostęp do pamięci, która nie została przypisana do ich używania. Na przykład język bezpieczny w pamięci sprawdzi granice tablicy lub statycznie gwarantuje (tj. w czasie kompilacji przed wykonaniem), że dostęp do tablicy poza granicami tablicy spowoduje błędy w czasie kompilacji i być może w czasie wykonywania.

Rozważmy następujący program języka, który jest bezpieczny dla typu i pamięci:

var x := 5;   
var y := "37"; 
var z := x + y;

W tym przykładzie zmienna zbędzie miała wartość 42. Chociaż może to nie być to, czego oczekiwał programista, jest to dobrze zdefiniowany wynik. Jeśli ybyłby innym ciągiem, takim, którego nie można przekonwertować na liczbę (np. „Hello World”), wynik również byłby dobrze zdefiniowany. Należy zauważyć, że program może być bezpieczny dla typu lub pamięci i nadal ulegać awarii w przypadku nieprawidłowej operacji. Dotyczy to języków, w których system typów nie jest wystarczająco zaawansowany, aby precyzyjnie określić poprawność operacji na wszystkich możliwych operandach. Ale jeśli program napotka operację, która nie jest bezpieczna dla typu, zakończenie programu jest często jedyną opcją.

Rozważmy teraz podobny przykład w C:

int x = 5;
char y[] = "37";
char* z = x + y;
printf("%c\n", *z);

W tym przykładzie wskaże adres pamięci pięć znaków dalej , co odpowiada trzem znakom po kończącym znaku zero ciągu wskazywanego przez . Jest to pamięć, do której program nie powinien mieć dostępu. Może zawierać dane śmieci i na pewno nie zawiera niczego użytecznego. Jak pokazuje ten przykład, C nie jest językiem bezpiecznym w pamięci ani bezpiecznym dla typu. zyy

Ogólnie rzecz biorąc, bezpieczeństwo typu i bezpieczeństwo pamięci idą w parze. Na przykład język obsługujący arytmetykę wskaźników i konwersje liczb do wskaźników (takich jak C) nie jest ani bezpieczny w pamięci, ani typu, ponieważ umożliwia dostęp do dowolnej pamięci tak, jakby była prawidłową pamięcią dowolnego typu.

Aby uzyskać więcej informacji, zobacz bezpieczeństwo pamięci .

Różne poziomy sprawdzania typu

Niektóre języki umożliwiają zastosowanie różnych poziomów sprawdzania do różnych regionów kodu. Przykłady obejmują:

  • use strictDyrektywa w JavaScript i Perl zastosowanie silniejszej kontroli.
  • declare(strict_types=1)W PHP na zasadzie per-pliku zezwala tylko zmienną dokładnego typu deklaracji typu zostaną zaakceptowane, albo TypeErrorzostanie wyrzucony.
  • Option Strict OnW VB.NET pozwala kompilator do żądania konwersji między obiektami.

Dodatkowe narzędzia, takie jak lint i IBM Rational Purify, mogą również służyć do osiągnięcia wyższego poziomu rygorystyczności.

Opcjonalne systemy typu

Zaproponował, głównie Gilad Bracha , aby wybór systemu typów był niezależny od wyboru języka; że system typów powinien być modułem, który można w razie potrzeby podłączyć do języka. Uważa, że ​​jest to korzystne, ponieważ to, co nazywa obowiązkowymi systemami typów, sprawia, że ​​języki są mniej ekspresyjne, a kod bardziej kruchy. Wymóg, aby system typów nie wpływał na semantykę języka, jest trudny do spełnienia.

Wpisywanie opcjonalne jest związane z wpisywaniem stopniowym , ale różni się od niego . Podczas gdy obie dyscypliny typowania mogą być używane do wykonywania statycznej analizy kodu ( typowanie statyczne ), opcjonalne systemy typów nie wymuszają bezpieczeństwa typów w czasie wykonywania ( typowanie dynamiczne ).

Polimorfizm i typy

Termin polimorfizm odnosi się do zdolności kodu (w szczególności funkcji lub klas) do działania na wartościach wielu typów lub do zdolności różnych wystąpień tej samej struktury danych do zawierania elementów różnych typów. Systemy typów, które pozwalają na polimorfizm, zazwyczaj robią to w celu zwiększenia możliwości ponownego wykorzystania kodu: w języku z polimorfizmem programiści muszą tylko zaimplementować strukturę danych, taką jak lista lub tablica asocjacyjna, raz, a nie raz dla każdego typu element, z którym planują go użyć. Z tego powodu informatycy czasami nazywają użycie pewnych form polimorfizmu programowaniem generycznym . Podstawy teorii typów polimorfizmu są ściśle związane z abstrakcją , modularnością i (w niektórych przypadkach) podtypowaniem .

Systemy typu specjalistycznego

Stworzono wiele systemów typów, które są wyspecjalizowane do użytku w określonych środowiskach z określonymi typami danych lub do statycznej analizy programów poza pasmem . Często są one oparte na pomysłach z teorii typów formalnych i są dostępne tylko jako część prototypowych systemów badawczych.

Poniższa tabela zawiera przegląd koncepcji teorii typów, które są używane w wyspecjalizowanych systemach typów. Nazwy M, N, O obejmują różne terminy, a nazwy różnią się rodzajem. Zapis (odp. ) opisuje typ, który wynika z zastąpienia wszystkich wystąpień zmiennej typu α (odp. zmienna termiczna x ) w τ przez typ σ (odp. term. N ).

Pojęcie typu Notacja Oznaczający
Funkcjonować Jeśli M ma typ , a N ma typ σ , to aplikacja ma typ τ .
Produkt Jeśli M ma typ , to jest para taka, że N ma typ σ , a O ma typ τ .
Suma Jeśli M ma typ , to albo jest pierwszym wtryskiem takim, że N ma typ σ , albo

jest drugim wtryskiem takim, że N ma typ τ .

Skrzyżowanie Jeśli M ma typ , to M ma typ σ , a M ma typ τ .
Unia Jeśli M ma typ , to M ma typ σ lub M ma typ τ .
Nagrywać Jeśli M ma typ , to M ma element x , który ma typ τ .
Polimorficzny Jeśli M ma typ , to M ma typ dla dowolnego typu σ .
Egzystencjalny Jeśli M ma typ , to M ma typ dla pewnego typu σ .
Rekursywny Jeśli M ma typ , to M ma typ .
Funkcja zależna Jeśli M ma typ , a N ma typ σ , to aplikacja ma typ .
Produkt zależny Jeśli M ma typ , to jest para taka , że N ma typ σ , a O ma typ .
Skrzyżowanie zależne Jeśli M ma typ , to M ma typ σ , a M ma typ .
Rodzinne skrzyżowanie Jeśli M ma typ , to M ma typ dla dowolnego terminu N typu σ .
Związek rodzinny Jeśli M ma typ , to M ma typ dla pewnego wyrazu N typu σ .

Typy zależne

Typy zależne opierają się na pomyśle wykorzystania skalarów lub wartości do dokładniejszego opisania typu jakiejś innej wartości. Na przykład może to być typ macierzy. Możemy wtedy zdefiniować reguły typowania, takie jak następująca reguła mnożenia macierzy:

gdzie k , m , n są dowolnymi dodatnimi liczbami całkowitymi. Wariant ML o nazwie Dependent ML został stworzony w oparciu o ten system typów, ale ponieważ sprawdzanie typów dla konwencjonalnych typów zależnych jest nierozstrzygalne , nie wszystkie programy używające ich mogą być sprawdzane bez ograniczeń. Dependent ML ogranicza rodzaj równości, o której może decydować, do arytmetyki Presburgera .

Inne języki, takie jak Epigram, sprawiają, że wartość wszystkich wyrażeń w języku jest rozstrzygalna, dzięki czemu sprawdzanie typu może być rozstrzygalne. Jednak ogólnie rzecz biorąc dowód rozstrzygalności jest nierozstrzygalny , dlatego wiele programów wymaga odręcznych adnotacji, które mogą być bardzo nietrywialne. Ponieważ utrudnia to proces rozwoju, wiele implementacji języka zapewnia łatwe wyjście w postaci opcji wyłączenia tego warunku. Jednak wiąże się to z kosztem uruchomienia sprawdzania typu w nieskończonej pętli, gdy karmione programy nie sprawdzają typu, powodując niepowodzenie kompilacji.

Typy liniowe

Typy liniowe , oparte na teorii logiki liniowej i ściśle związane z typami unikatowości , są typami przypisanymi do wartości, które mają tę właściwość, że mają jedno i tylko jedno odniesienie do nich przez cały czas. Są one cenne przy opisywaniu dużych niezmiennych wartości, takich jak pliki, ciągi itd., ponieważ każda operacja, która jednocześnie niszczy obiekt liniowy i tworzy podobny obiekt (np. „ str= str + "a"”), może zostać zoptymalizowana „pod maską” w miejsce mutacji. Zwykle nie jest to możliwe, ponieważ takie mutacje mogą powodować skutki uboczne w częściach programu zawierających inne odniesienia do obiektu, naruszając przezroczystość odniesienia . Są one również używane w prototypowym systemie operacyjnym Singularity do komunikacji międzyprocesowej, zapewniając statycznie, że procesy nie mogą współdzielić obiektów w pamięci współdzielonej, aby zapobiec sytuacji wyścigu. Język Clean (język podobny do Haskella ) używa tego typu systemu, aby uzyskać dużą szybkość (w porównaniu do wykonywania głębokiej kopii), pozostając jednocześnie bezpiecznym.

Rodzaje skrzyżowań

Typy przecięcia to typy opisujące wartości, które należą do obu dwóch innych podanych typów z nakładającymi się zestawami wartości. Na przykład w większości implementacji języka C znak ze znakiem ma zakres od -128 do 127, a znak bez znaku ma zakres od 0 do 255, więc typ przecięcia tych dwóch typów miałby zakres od 0 do 127. Taki typ przecięcia można bezpiecznie przekazać do funkcji oczekujących albo podpisane lub niepodpisane zwęgla, ponieważ jest on zgodny z obu typów.

Typy przecięcia są przydatne do opisywania przeciążonych typów funkcji: na przykład, jeśli „ → ” jest typem funkcji przyjmujących argument typu integer i zwracających liczbę całkowitą, a „ → ” jest typem funkcji przyjmujących argument float i zwracających liczbę float, to przecięcie tych dwóch typów może być użyte do opisania funkcji, które wykonują jedną lub drugą, w zależności od typu danych wejściowych. Taka funkcja może być przekazana do innej funkcji, która oczekuje bezpiecznie funkcji " → "; po prostu nie używałby funkcji „ → ”. intintfloatfloatintintfloatfloat

W hierarchii podklas przecięcie typu i typu przodka (takiego jak jego rodzic) jest najbardziej pochodnym typem. Przecięcie typów rodzeństwa jest puste.

Język Forsythe zawiera ogólną implementację typów skrzyżowań. Forma zastrzeżona to typy doprecyzowania .

Typy Unii

Typy Unii to typy opisujące wartości, które należą do jednego z dwóch typów. Na przykład w C znak ze znakiem ma zakres od -128 do 127, a znak bez znaku ma zakres od 0 do 255, więc połączenie tych dwóch typów będzie miało ogólny „wirtualny” zakres od -128 do 255, który może być używane częściowo w zależności od tego, do którego członka związku ma dostęp. Każda funkcja obsługująca ten typ unii musiałaby radzić sobie z liczbami całkowitymi w tym pełnym zakresie. Mówiąc bardziej ogólnie, jedynymi prawidłowymi operacjami na typie unii są operacje, które są poprawne na obu typach, które są połączone. Koncepcja „unii” w C jest podobna do typów unii, ale nie jest typesafe, ponieważ zezwala na operacje, które są prawidłowe dla każdego typu, a nie obu . Typy unii są ważne w analizie programu, gdzie są używane do reprezentowania wartości symbolicznych, których dokładna natura (np. wartość lub typ) nie jest znana.

W hierarchii podklas połączenie typu i typu przodka (takiego jak jego rodzic) jest typem przodka. Unia typów rodzeństwa jest podtypem ich wspólnego przodka (to znaczy, że wszystkie operacje dozwolone na ich wspólnym przodku są dozwolone na typie unii, ale mogą również mieć inne prawidłowe operacje wspólne).

Typy egzystencjalne

Typy egzystencjalne są często używane w połączeniu z typami rekordów do reprezentowania modułów i abstrakcyjnych typów danych , ze względu na ich zdolność do oddzielenia implementacji od interfejsu. Na przykład, typ "T = ∃X { a: X; f: (X → int); }" opisuje interfejs modułu, który zawiera element danych o nazwie a typu X oraz funkcję o nazwie f, która pobiera parametr tego samego typu X i zwraca liczbę całkowitą. Można to zrealizować na różne sposoby; na przykład:

  • intT = { a: int; f: (int → wew); }
  • floatT = { a: float; f: (zmiennoprzecinkowa → wewn.); }

Oba typy są podtypami bardziej ogólnego typu egzystencjalnego T i odpowiadają konkretnym typom implementacji, więc każda wartość jednego z tych typów jest wartością typu T. Mając wartość „t” typu „T”, wiemy, że „ TF (TA)”jest dobrze wpisane, niezależnie od tego, co abstrakcyjny typ X jest. Daje to elastyczność wyboru typów dopasowanych do konkretnej implementacji, podczas gdy klienci używający tylko wartości typu interfejsu — typu egzystencjalnego — są odizolowani od tych wyborów.

Ogólnie rzecz biorąc, kontroler typu nie jest w stanie wywnioskować, do jakiego typu egzystencjalnego należy dany moduł. W powyższym przykładzie intT { a: int; f: (int → wew); } może również mieć typ ∃X { a:X; f: (int → wew); }. Najprostszym rozwiązaniem jest opisanie każdego modułu z jego przeznaczeniem, np.:

  • intT = { a: int; f: (int → wew); } jako ∃X { a:X; f: (X → wew); }

Chociaż abstrakcyjne typy danych i moduły były implementowane w językach programowania od dłuższego czasu, to dopiero w 1988 roku John C. Mitchell i Gordon Plotkin ustanowili formalną teorię pod hasłem: „Abstract [data] types have eg egzystencjalny typ”. Teoria ta jest rachunkiem lambda typu drugiego rzędu, podobnym do Systemu F , ale z kwantyfikacją egzystencjalną, a nie uniwersalną.

Stopniowe pisanie

Stopniowe pisanie to system typów, w którym zmienne mogą być przypisane do typu w czasie kompilacji (co jest pisaniem statycznym) lub w czasie wykonywania (co jest pisaniem dynamicznym), umożliwiając programistom wybór odpowiedniego paradygmatu typu, od wewnątrz jeden język. W szczególności stopniowe pisanie używa specjalnego typu o nazwie dynamic do reprezentowania statycznie nieznanych typów, a stopniowe pisanie zastępuje pojęcie równości typów nową relacją o nazwie spójność, która wiąże typ dynamiczny z każdym innym typem. Relacja spójności jest symetryczna, ale nie przechodnia.

Jawna lub niejawna deklaracja i wnioskowanie

Wiele statycznych systemów typów, takich jak C i Java, wymaga deklaracji typu : programista musi jawnie powiązać każdą zmienną z określonym typem. Inne, takie jak Haskell, wykonują wnioskowanie o typie : kompilator wyciąga wnioski na temat typów zmiennych na podstawie tego, jak programiści używają tych zmiennych. Na przykład, biorąc pod uwagę funkcję , która dodaje i razem, kompilator można wywnioskować, że i muszą być liczbami-Since Ponadto jest zdefiniowana tylko dla liczb. W związku z tym każde wywołanie innego miejsca w programie, które jako argument określa typ nienumeryczny (taki jak łańcuch lub lista), zasygnalizuje błąd. f(x, y)xyxyf

Stałe liczbowe i łańcuchowe oraz wyrażenia w kodzie mogą i często implikują typ w określonym kontekście. Na przykład wyrażenie 3.14może sugerować typ zmiennoprzecinkowy , podczas gdy może sugerować listę liczb całkowitych — zwykle tablicę . [1, 2, 3]

Wnioskowanie o typie jest ogólnie możliwe, jeśli jest obliczalne w danym systemie typów. Co więcej, nawet jeśli wnioskowanie nie jest ogólnie obliczalne dla danego systemu typów, wnioskowanie jest często możliwe dla dużego podzbioru programów świata rzeczywistego. System typów Haskella, wersja Hindley-Milner , jest ograniczeniem Systemu Fω do tak zwanych typów polimorficznych rangi-1, w których wnioskowanie o typie jest obliczalne. Większość kompilatorów Haskella dopuszcza polimorfizm dowolnej rangi jako rozszerzenie, ale to sprawia, że ​​wnioskowanie o typie nie jest obliczalne. (Sprawdzanie typu jest jednak rozstrzygalne , a programy rangi 1 nadal mają wnioskowanie o typie; programy polimorficzne o wyższym stopniu są odrzucane, chyba że podano wyraźne adnotacje typu.)

Problemy decyzyjne

System typów, który przypisuje typy do terminów w środowiskach typów przy użyciu reguł typów, jest naturalnie powiązany z problemami decyzyjnymi dotyczącymi sprawdzania typów , typowalności i zamieszkiwania typów .

  • Biorąc pod uwagę typ environment , term i type , zdecyduj, czy terminowi można przypisać typ w środowisku typów.
  • Biorąc pod uwagę termin , zdecyduj, czy istnieje środowisko typu i typ taki, że termin może być przypisany do typu w środowisku typu .
  • Biorąc pod uwagę środowisko typu i type , zdecyduj, czy istnieje termin, do którego można przypisać typ w środowisku typu.

Zunifikowany system typów

Niektóre języki, takie jak C# lub Scala, mają ujednolicony system typów. Oznacza to, że wszystkie typy C#, w tym typy pierwotne, dziedziczą z jednego obiektu głównego. Każdy typ w C# dziedziczy z klasy Object. Niektóre języki, takie jak Java i Raku , mają typ główny, ale mają również typy podstawowe, które nie są obiektami. Java udostępnia opakowujące typy obiektów, które istnieją razem z typami podstawowymi, dzięki czemu programiści mogą używać opakowujących typów obiektów lub prostszych nieobiektowych typów pierwotnych. Raku automatycznie konwertuje typy pierwotne na obiekty, gdy uzyskuje się dostęp do ich metod.

Kompatybilność: równoważność i podtypy

Moduł sprawdzania typu dla języka wpisywanego statycznie musi sprawdzić, czy typ dowolnego wyrażenia jest zgodny z typem oczekiwanym przez kontekst, w którym pojawia się to wyrażenie. Na przykład w instrukcji przypisania formularza wywnioskowany typ wyrażenia musi być zgodny z zadeklarowanym lub wywnioskowanym typem zmiennej . To pojęcie spójności, zwane kompatybilnością , jest specyficzne dla każdego języka programowania. x := eex

Jeśli typ ei typ xsą takie same, a przypisanie jest dozwolone dla tego typu, to jest to prawidłowe wyrażenie. Tak więc w najprostszych systemach typów pytanie, czy dwa typy są kompatybilne, sprowadza się do tego, czy są one równe (lub równoważne ). Jednak różne języki mają różne kryteria, kiedy dwa wyrażenia typu są rozumiane jako oznaczające ten sam typ. Te różne teorie równań typów różnią się znacznie, dwa skrajne przypadki to systemy typów strukturalnych , w których dowolne dwa typy opisujące wartości o tej samej strukturze są równoważne, oraz systemy typów mianownikowych , w których żadne dwa syntaktycznie różne wyrażenia typu nie oznaczają tego samego typu ( tj. typy muszą mieć tę samą „nazwę”, aby były równe).

W językach z podtypowaniem relacja zgodności jest bardziej złożona. W szczególności, jeśli Bjest podtypem A, wartość type Bmoże być używana w kontekście, w którym Aoczekiwany jest jeden z typów ( covariant ), nawet jeśli odwrotność nie jest prawdą. Podobnie jak równoważność, relacja podtypu jest definiowana inaczej dla każdego języka programowania, z wieloma możliwymi odmianami. Obecność polimorfizmu parametrycznego lub ad hoc w języku może również mieć wpływ na zgodność typów.

Zobacz też

Uwagi

Bibliografia

Dalsza lektura

Zewnętrzne linki