Czy istnieje powód, aby mieć typ dna w języku programowania?

Typ dolny to konstrukcja występująca głównie w matematycznej teorii typów. Jest również nazywany pustym typem. Jest to typ, który nie ma wartości, ale jest podtypem wszystkich typów.

Jeśli typ zwracany przez funkcję jest typem dolnym, oznacza to, że nie zwraca. Kropka. Może zapętla się na zawsze, a może rzuca wyjątek.

Po co mieć ten dziwny typ w języku programowania? To nie jest tak powszechne, ale jest obecne w niektórych, takich jak Scala i Lisp.

Podam prosty przykład: C ++ vs Rust.

Oto funkcja używana do zgłaszania wyjątku w C ++ 11:

[[noreturn]] void ThrowException(char const* message,
                                 char const* file,
                                 int line,
                                 char const* function);

A oto odpowiednik w Rust:

fn formatted_panic(message: &str, file: &str, line: isize, function: &str) -> !;

W kwestii czysto syntaktycznej konstrukcja Rdza jest bardziej rozsądna. Zauważ, że konstrukcja C ++ określa typ zwracany, chociaż określa również, że nie będzie zwracany. To trochę dziwne.

Standardowo, składnia C ++ pojawiła się tylko w C ++ 11 (została dodana na górze), ale różne kompilatory dostarczały różne rozszerzenia przez pewien czas, tak więc narzędzia analityczne innych firm musiały zostać zaprogramowane, aby rozpoznawać różne sposoby ten atrybut można zapisać. Ujednolicenie jest oczywiście wyraźnie lepsze.

A co z korzyścią?

Fakt, że funkcja nie zwraca, może być przydatny do:

• optymalizacja: można przyciąć dowolny kod po nim (nie zwróci się), nie ma potrzeby zapisywania rejestrów (ponieważ nie będzie konieczne ich przywracanie), ...
• analiza statyczna: eliminuje szereg potencjalnych ścieżek wykonania
• łatwość konserwacji: (patrz analiza statyczna, ale przez ludzi)

Odpowiedź Karla jest dobra. Oto dodatkowe zastosowanie, które, jak sądzę, nikt inny nie wspomniał. Typ

if E then A else B

powinien być typem, który zawiera wszystkie wartości w typie Ai wszystkie wartości w typie B. Jeśli typem Bjest Nothing, typem ifwyrażenia może być typ A. Często ogłaszam rutynę

def unreachable( s:String ) : Nothing = throw new AssertionError("Unreachable "+s) 

stwierdzenie, że kod nie zostanie osiągnięty. Ponieważ jest to typ Nothing, unreachable(s)można go teraz używać w dowolnym iflub (częściej) switchbez wpływu na rodzaj wyniku. Na przykład

 val colour : Colour := switch state of
         BLACK_TO_MOVE: BLACK
         WHITE_TO_MOVE: WHITE
         default: unreachable("Bad state")

Scala ma taki typ Nic.

Innym przypadkiem użycia Nothing(jak wspomniano w odpowiedzi Karla) jest Lista [Nic] to typ list, których każdy członek ma typ Nic. Może to być typ pustej listy.

Kluczową właściwością, Nothingktóra sprawia, że ​​te przypadki użycia działają, jest to, że nie ma żadnych wartości - chociaż na przykład w Scali nie ma żadnych wartości - jest to, że jest to podtyp każdego innego typu.

Załóżmy, że masz język, w którym każdy typ zawiera tę samą wartość - nazwijmy go (). W takim języku typ jednostki, który ma ()jako jedyną wartość, może być podtypem każdego typu. Nie oznacza to, że jest to typ dna w tym sensie, że miał na myśli PO; PO było jasne, że typ dna nie zawiera żadnych wartości. Ponieważ jednak jest to typ, który jest podtypem każdego typu, może odgrywać taką samą rolę jak typ dolny.

Haskell robi rzeczy nieco inaczej. W Haskell wyrażenie, które nigdy nie tworzy wartości, może mieć schemat typów forall a.a. Instancja tego typu schematu połączy się z dowolnym innym typem, więc skutecznie działa jako typ dolny, mimo że (standardowy) Haskell nie ma pojęcia podtypu. Na przykład errorfunkcja ze standardowego preludium ma schemat typów forall a. [Char] -> a. Więc możesz pisać

if E then A else error ""

a typ wyrażenia będzie taki sam jak typ Adowolnego wyrażenia A.

Pusta lista w Haskell ma schemat typów forall a. [a]. Jeśli Ajest wyrażeniem, którego typ jest typem listy, to

if E then A else []

jest wyrażeniem tego samego typu co A.

Typy tworzą monoid na dwa sposoby, tworząc razem semiery . To się nazywa algebraiczne typy danych . W przypadku typów skończonych ten semirowanie bezpośrednio odnosi się do semirowania liczb naturalnych (w tym zera), co oznacza, że ​​policzysz, ile możliwych wartości ma typ (z wyłączeniem „wartości nieterminacyjnych”).

• Typ dolny (nazywam to Vacuous) ma zerowe wartości ^† .
• Typ jednostki ma jedną wartość. Wywołam zarówno typ, jak i jego pojedynczą wartość ().
• Skład (który większość języków programowania obsługuje bezpośrednio, poprzez rekordy / struktury / klasy z polami publicznymi) jest operacją produktu . Na przykład, (Bool, Bool)ma cztery możliwe wartości, a mianowicie (False,False), (False,True), (True,False)i (True,True).
  Typ jednostki jest elementem tożsamości operacji kompozycji. Np. ((), False)I ((), True)są jedynymi wartościami typu ((), Bool), więc ten typ jest izomorficzny Bool.
• Alternatywne typy są nieco zaniedbywane w większości języków (języki OO w pewnym sensie wspierają je dziedziczeniem), ale są nie mniej przydatne. Alternatywa między dwoma typami Ai Bzasadniczo ma wszystkie wartości Aplus wszystkie wartości B, stąd typ sumy . Na przykład, Either () Boolma trzy wartości, będę je nazywać Left (), Right Falsei Right True.
  Typ dolny jest elementem tożsamości sumy: Either Vacuous Ama tylko wartości formularza Right a, ponieważ Left ...nie ma sensu ( Vacuousnie ma wartości).

Interesujące w tych monoidach jest to, że kiedy wprowadzasz funkcje do swojego języka, kategoria tych typów z funkcjami morfizmów jest kategorią monoidalną . Pozwala to między innymi na zdefiniowanie funktorów aplikacyjnych i monad , które okazują się doskonałą abstrakcją dla ogólnych obliczeń (być może obejmujących efekty uboczne itp.) W ramach czysto funkcjonalnych terminów.

Teraz właściwie możesz zajść daleko, martwiąc się tylko jedną stroną problemu (monoid kompozycji), wtedy tak naprawdę nie potrzebujesz jawnie typu dna. Na przykład nawet Haskell przez długi czas nie miał standardowego typu dna. Teraz tak się nazywa Void.

Ale jeśli weźmiesz pod uwagę pełny obraz jako dwudzielną kategorię zamkniętą , wówczas system typów jest faktycznie równoważny całemu rachunku lambda, więc w zasadzie masz idealną abstrakcję wszystkiego, co możliwe w języku kompletnym Turinga. Idealne dla osadzonych języków specyficznych dla domeny, na przykład istnieje projekt dotyczący bezpośredniego kodowania obwodów elektronicznych w ten sposób .

Oczywiście można powiedzieć, że jest to ogólny nonsens teoretyczny . Nie musisz wcale wiedzieć o teorii kategorii, aby być dobrym programistą, ale kiedy to zrobisz, daje to potężne i śmiesznie ogólne sposoby rozumowania na temat kodu i udowodnienia niezmienników.

^† _{mb21 przypomina mi, że należy pamiętać, że nie należy tego mylić z dolnymi wartościami . W leniwych językach, takich jak Haskell, każdy typ zawiera oznaczoną dolną „wartość” ⊥. Nie jest to konkretna rzecz, którą można by jawnie przekazać, ale to, co „zwraca”, na przykład, gdy funkcja zapętla się na zawsze. Nawet Voidtyp Haskella „zawiera” dolną wartość, a więc nazwę. W tym świetle typ dna Haskella ma naprawdę jedną wartość, a typ jednostki ma dwie wartości, ale w dyskusji teorii kategorii jest to na ogół ignorowane.}

Może zapętla się na zawsze, a może rzuca wyjątek.

Brzmi jak przydatny typ w takich sytuacjach, choć mogą być rzadkie.

Ponadto, chociaż Nothing(nazwa Scali dla typu dolnego) nie może mieć żadnych wartości, List[Nothing]nie ma tego ograniczenia, co czyni go użytecznym jako typ pustej listy. Większość języków rozwiązuje ten problem, tworząc pustą listę ciągów znaków innego rodzaju niż pustą listę liczb całkowitych, co ma sens, ale sprawia, że ​​pusta lista jest bardziej szczegółowa, co jest dużą wadą w języku zorientowanym na listę.

Przydaje się w analizie statycznej dokumentowanie faktu, że dana ścieżka kodu jest nieosiągalna. Na przykład, jeśli napiszesz w C #:

int F(int arg) {
 if (arg != 0)
  return arg + 1; //some computation
 else
  Assert(false); //this throws but the compiler does not know that
}
void Assert(bool cond) { if (!cond) throw ...; }

Kompilator narzeka, że Fnie zwraca niczego w co najmniej jednej ścieżce kodu. Jeśli Assertmiałby zostać oznaczony jako niezwracający, kompilator nie musiałby ostrzegać.

W niektórych językach nullma typ dolny, ponieważ podtyp wszystkich typów ładnie definiuje, dla których języków używa się null (pomimo łagodnej sprzeczności nullbycia zarówno sobą, jak i funkcją, która zwraca się, unikając typowych argumentów na temat tego, dlaczego botpowinien być niezamieszkany).

Może być również używany jako funkcja typu catch-all w funkcjach ( any -> bot) do obsługi nieudanej wysyłki.

Niektóre języki pozwalają na rozwiązanie problemu botjako błędu, którego można użyć do dostarczenia niestandardowych błędów kompilatora.

Tak, jest to dość użyteczny typ; podczas gdy jego rola byłaby głównie w systemie czcionek, istnieją pewne okazje, w których typ dna pojawiałby się otwarcie.

Rozważmy język o typie statycznym, w którym wyrażenia warunkowe są wyrażeniami (więc konstrukcja if-then-else podwaja się również jako operator trójskładnikowy języka C i znajomych, i może istnieć podobna wielowymiarowa instrukcja case). Funkcjonalny język programowania ma to, ale dzieje się tak również w niektórych imperatywnych językach (od ALGOL 60). Następnie wszystkie wyrażenia rozgałęzione muszą ostatecznie wygenerować typ całego wyrażenia warunkowego. Można po prostu wymagać, aby ich typy były równe (i myślę, że tak jest w przypadku operatora trójskładnikowego w C), ale jest to zbyt restrykcyjne, szczególnie gdy warunek może być również użyty jako instrukcja warunkowa (nie zwraca żadnej użytecznej wartości). Ogólnie rzecz biorąc, chcemy, aby każde wyrażenie gałęzi było (domyślnie) konwertowalne do typowego typu, który będzie typem pełnego wyrażenia (być może z mniej lub bardziej skomplikowanymi ograniczeniami, aby umożliwić temu typowi skuteczne znalezienie kompilatora, por. C ++, ale nie będę tu wchodził w te szczegóły).

Istnieją dwa rodzaje sytuacji, w których ogólny rodzaj konwersji pozwoli na niezbędną elastyczność takich wyrażeń warunkowych. Jeden jest już wspomniany, gdzie typem wyniku jest typ jednostkivoid; jest to oczywiście supertyp wszystkich innych typów, a zezwolenie na (trywialny) konwersję dowolnego typu umożliwia użycie wyrażenia warunkowego jako instrukcji warunkowej. Drugi dotyczy przypadków, w których wyrażenie zwraca użyteczną wartość, ale jedna lub więcej gałęzi nie jest w stanie wygenerować jednej. Zazwyczaj zgłaszają wyjątek lub wymagają przeskoku, a wymaganie od nich (również) wytworzenia wartości typu całego wyrażenia (z nieosiągalnego punktu) byłoby bezcelowe. Jest to tego rodzaju sytuacja, którą można z wdziękiem poradzić, podając klauzule podnoszące wyjątki, skoki i wywołania, które będą miały taki efekt, typ dolny, jeden typ, który można (trywialnie) przekształcić w dowolny inny typ.

Sugerowałbym napisanie takiego dolnego typu, *który sugerowałby jego konwersję na dowolny typ. Może służyć wewnętrznie innym przydatnym celom, na przykład, gdy próbuje się wydedukować typ wyniku dla funkcji rekurencyjnej, która jej nie deklaruje, inferencja typu może przypisać typ *do dowolnego wywołania rekurencyjnego, aby uniknąć sytuacji z kurczakiem i jajkiem; rzeczywisty typ zostanie określony przez gałęzie nierekurencyjne, a te rekurencyjne zostaną przekonwertowane na wspólny typ nierekurencyjnych. Jeśli w ogóle nie ma rozgałęzień nierekurencyjnych, typ pozostanie *i poprawnie wskaże, że funkcja nie ma możliwości powrotu z rekurencji. Oprócz tego i jako wynikowego typu funkcji zgłaszania wyjątku można użyć*jako typ komponentu sekwencji o długości 0, na przykład pustej listy; ponownie, jeśli kiedykolwiek element zostanie wybrany z wyrażenia typu [*](koniecznie pusta lista), wówczas wynikowy typ *poprawnie wskaże, że nie może on nigdy powrócić bez błędu.

W niektórych językach można dodać adnotację do funkcji, aby poinformować zarówno kompilator, jak i programistów, że wywołanie tej funkcji nie zostanie zwrócone (a jeśli funkcja jest napisana w sposób, który może zwrócić, kompilator nie pozwoli na to ). Warto wiedzieć, ale ostatecznie możesz wywołać taką funkcję jak każda inna. Kompilator może wykorzystać te informacje do optymalizacji, aby ostrzec o martwym kodzie i tak dalej. Więc nie ma bardzo ważnego powodu, aby mieć tego typu, ale nie ma też bardzo ważnego powodu, aby tego uniknąć.

W wielu językach funkcja może zwrócić „void”. Co to dokładnie oznacza, zależy od języka. W C oznacza to, że funkcja nic nie zwraca. W Swift oznacza to, że funkcja zwraca obiekt z tylko jedną możliwą wartością, a ponieważ istnieje tylko jedna możliwa wartość, ta wartość przyjmuje zero bitów i nie wymaga żadnego kodu. W obu przypadkach to nie to samo, co „dno”.

„bottom” byłoby typem bez możliwych wartości. Nigdy nie może istnieć. Jeśli funkcja zwraca „dno”, nie może faktycznie zwrócić, ponieważ nie ma wartości typu „dno”, którą mógłby zwrócić.

Jeśli czuje to projektant języka, nie ma powodu, aby nie mieć tego typu. Implementacja nie jest trudna (możesz ją zaimplementować dokładnie tak, jak funkcja zwracająca pustkę i oznaczona jako „nie zwraca”). Nie można mieszać wskaźników do funkcji zwracających dno ze wskaźnikami do funkcji zwracających pustkę, ponieważ nie są tego samego typu).