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

49

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.

GregRos
źródło
2
@SargeBorsch: jesteś tego pewien? Oczywiście nie można w C jednoznacznie zdefiniować voiddanych ...
Basile Starynkevitch
3
@BasileStarynkevitch nie ma wartości typu void, a typ jednostki musi mieć jedną wartość. Ponadto, jak wskazałeś, nie możesz nawet zadeklarować wartości typu void, co oznacza, że ​​nie jest to nawet typ, tylko specjalna przypadek narożny w języku.
Sarge Barszcz
2
Tak, C jest w tym dziwny, szczególnie w sposobie pisania wskaźnika i typów wskaźników funkcji. Ale voidw Javie jest prawie tak samo: nie jest tak naprawdę typem i nie może mieć wartości.
Sarge Barszcz
3
W semantyce języków z typem dolnym nie uważa się, że typ dolny nie ma żadnych wartości, ale raczej ma jedną wartość, dolną wartość, reprezentującą obliczenie, które nigdy się nie kończy (normalnie). Ponieważ dolna wartość jest wartością każdego typu, dolny typ może być podtypem każdego typu.
Theodore Norvell
4
@BasileStarynkevitch Common Lisp ma typ zerowy, który nie ma żadnych wartości. Ma również typ zerowy, który ma tylko jedną wartość, symbol nil(aka, ()), który jest typem jednostki.
Joshua Taylor

Odpowiedzi:

33

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)
Matthieu M.
źródło
6
voidw twoim przykładzie C ++ definiuje (część) typ funkcji - nie typ zwracany. Ogranicza to wartość, do której dozwolona jest funkcja return; wszystko, co może przekształcić się w pustkę (co jest niczym). Jeśli funkcja returns, po niej nie może następować wartość. Pełny typ funkcji to void () (char const*, char const*, int, char const *). + 1 za używanie char constzamiast const char:-)
Jaśniejsze
4
Nie oznacza to jednak, że bardziej sensowne jest posiadanie typu bottom, tylko że sensowne jest dodawanie adnotacji do funkcji, czy zwracają się czy nie jako część języka. W rzeczywistości, ponieważ funkcje mogą nie zostać zwrócone z różnych powodów, wydaje się, że lepiej jest w jakiś sposób zakodować przyczynę, zamiast używać terminu catch-all, podobnie jak stosunkowo nowa koncepcja opisywania funkcji na podstawie ich skutków ubocznych.
GregRos
2
W rzeczywistości istnieje powód, aby „nie zwracać” i „ma niezależny typ zwracany X”: Kompatybilność wsteczna dla własnego kodu, ponieważ konwencja wywoływania może zależeć od typu zwracanego.
Deduplicator
jest [[noreturn]] par składni lub dodatek funkcjonalności?
Zaibis,
1
[cd.] Ogólnie rzecz biorąc, chciałbym tylko powiedzieć, że dyskusja na temat zalet ⊥ musi określać, co kwalifikuje się jako wdrożenie ⊥; i nie sądzę, aby system typów, który nie ma ( a → ⊥) ≤ ( ab ), jest użyteczną implementacją ⊥. W tym sensie SysV x86-64 C ABI (między innymi) po prostu nie pozwala na implementację ⊥.
Alex Shpilkin
26

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.

Theodore Norvell
źródło
Jaka jest różnica między typem forall a . [a]a typem [a]w Haskell? Czy zmienne typu nie są już powszechnie kwantyfikowane w wyrażeniach typu Haskell?
Giorgio
@Giorgio W Haskell uniwersalna kwantyfikacja jest domyślna, jeśli jest jasne, że patrzysz na schemat typów. Nie możesz nawet pisać forallw standardowym Haskell 2010. Kwantyfikację napisałem wprost, ponieważ nie jest to forum Haskell i niektórzy ludzie mogą nie znać konwencji Haskell. Więc nie ma różnicy, z wyjątkiem tego, że forall a . [a]nie jest to standard, podczas gdy [a]jest.
Theodore Norvell,
19

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.

po lewej stronie
źródło
„Typ dolny (nazywam to Void)”, którego nie należy mylić z wartością bottom , która jest członkiem dowolnego typu w Haskell .
mb21
18

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ę.

Karl Bielefeldt
źródło
12
„Pusta lista Haskella jest konstruktorem typów”: z pewnością istotną kwestią w tym przypadku jest to, że jest polimorficzna lub przeciążona - to znaczy, że puste listy z różnych typów są odrębnymi wartościami, ale []reprezentują wszystkie z nich i zostaną zaimplementowane do konkretny typ w razie potrzeby.
Peter LeFanu Lumsdaine
Co ciekawe: Jeśli próbujesz utworzyć pustą tablicę w interpreter Haskell, można uzyskać bardzo określoną wartość z typem bardzo nieokreślony: [a]. Podobnie, :t Left 1daje Num a => Either a b. Faktyczna ocena wyrażenia wymusza rodzaj a, ale nie b:Either Integer b
John Dvorak
5
Pusta lista jest konstruktorem wartości . Trochę myląco, zaangażowany konstruktor typu ma tę samą nazwę, ale sama pusta lista jest wartością, a nie typem (no cóż, istnieją również listy poziomów typów, ale to zupełnie inny temat). Część, która sprawia, że pusta lista pracy w dowolnym rodzaju lista jest implikowana forallw swoim rodzaju, forall a. [a]. Istnieje kilka fajnych sposobów myślenia forall, ale naprawdę zajmuje to trochę czasu.
David
@PeterLeFanuLumsdaine To właśnie oznacza konstruktor typów. Oznacza to po prostu, że jest to rodzaj innego rodzaju *.
GregRos
2
W Haskell []jest konstruktorem typów i []jest wyrażeniem reprezentującym pustą listę. Ale to nie znaczy, że „pusta lista Haskella jest konstruktorem typów”. Kontekst wyjaśnia, czy []jest używany jako typ, czy jako wyrażenie. Załóżmy, że deklarujesz data Foo x = Foo | Bar x (Foo x); teraz możesz używać go Foojako konstruktora typu lub wartości, ale zdarza się, że wybierasz tę samą nazwę dla obu.
Theodore Norvell,
3

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ć.

usr
źródło
2

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.

Telastyn
źródło
11
Nie, typ dolny nie jest typem jednostki. Typ dna nie ma żadnej wartości, więc funkcja zwracająca typ dna nie powinna zwracać (tzn.
Generować
@BasileStarynkevitch - Nie mówię o typie jednostki. Typ jednostki odwzorowuje na voidpopularne języki (choć z nieco inną semantyką dla tego samego zastosowania), nie null. Chociaż masz również rację, że większość języków nie modeluje wartości null jako najniższego typu.
Telastyn
3
@TheodoreNorvell - wczesne wersje Tangent to zrobiły - chociaż jestem jego autorem, więc może to oszustwo. Nie mam zapisanych linków dla innych i minęło trochę czasu, odkąd przeprowadziłem te badania.
Telastyn
1
@Martijn Ale możesz użyć null, np. Możesz porównać wskaźnik z nullwynikiem logicznym. Myślę, że odpowiedzi pokazują, że istnieją dwa różne rodzaje rodzajów dna. (a) Języki (np. Scala), w których typ będący podtypem każdego typu reprezentuje obliczenia, które nie dostarczają żadnych wyników. Zasadniczo jest to pusty typ, choć technicznie często zapełniany przez bezużyteczną dolną wartość reprezentującą nieterminację. (b) Języki takie jak Tangent, w których typ dolny jest podzbiorem każdego innego typu, ponieważ zawiera użyteczną wartość, która występuje również w każdym innym typie - null.
Theodore Norvell
4
Interesujące jest to, że jeden język ma wartość o typie, którego nie można zadeklarować (wspólny dla literału zerowego), a inny ma typ, który można zadeklarować, ale nie ma wartości (tradycyjny typ dna), i że wypełniają one nieco porównywalne role .
Martijn
1

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.

Marc van Leeuwen
źródło
Czy więc pomysł var foo = someCondition() ? functionReturningBar() : functionThatAlwaysThrows()może wywnioskować rodzaj fooas Bar, ponieważ wyrażenie nigdy nie może dać niczego innego?
supercat
1
Właśnie opisałeś typ jednostki - przynajmniej w pierwszej części odpowiedzi. Funkcja, która zwraca typ jednostki, jest taka sama jak funkcja zadeklarowana jako zwracana voidw C. Druga część twojej odpowiedzi, w której mówisz o typie funkcji, która nigdy nie zwraca, lub liście bez elementów - to jest rzeczywiście typ dolny! (Często jest napisane _|_raczej niż *. Nie jestem pewien, dlaczego. Być może dlatego, że wygląda jak (ludzkie) dno :)
andrewf
2
W celu uniknięcia wątpliwości: „nie zwraca niczego przydatnego” różni się od „nie zwraca”; pierwszy jest reprezentowany przez typ jednostki; drugi według rodzaju Dna.
andrewf
@andrewf: Tak, rozumiem to rozróżnienie. Moja odpowiedź jest nieco długa, ale chciałem powiedzieć, że zarówno typ jednostki, jak i typ dna odgrywają (różne, ale) porównywalne role, umożliwiając bardziej elastyczne (ale nadal bezpieczne) używanie niektórych wyrażeń.
Marc van Leeuwen,
@ superupat: Tak, to jest pomysł. Obecnie w C ++, który jest nielegalne, chociaż byłoby to ważne, jeżeli functionThatAlwaysThrows()zostały zastąpione przez wyraźny throw, dzięki specjalnej języka w standardzie. Posiadanie takiego typu byłoby poprawą.
Marc van Leeuwen,
0

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).

gnasher729
źródło