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.
programming-languages
type-systems
GregRos
źródło
źródło
void
danych ...void
, a typ jednostki musi mieć jedną wartość. Ponadto, jak wskazałeś, nie możesz nawet zadeklarować wartości typuvoid
, co oznacza, że nie jest to nawet typ, tylko specjalna przypadek narożny w języku.void
w Javie jest prawie tak samo: nie jest tak naprawdę typem i nie może mieć wartości.nil
(aka,()
), który jest typem jednostki.Odpowiedzi:
Podam prosty przykład: C ++ vs Rust.
Oto funkcja używana do zgłaszania wyjątku w C ++ 11:
A oto odpowiednik w Rust:
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:
źródło
void
w twoim przykładzie C ++ definiuje (część) typ funkcji - nie typ zwracany. Ogranicza to wartość, do której dozwolona jest funkcjareturn
; wszystko, co może przekształcić się w pustkę (co jest niczym). Jeśli funkcjareturn
s, po niej nie może następować wartość. Pełny typ funkcji tovoid () (char const*, char const*, int, char const *)
. + 1 za używaniechar const
zamiastconst char
:-)[[noreturn]]
par składni lub dodatek funkcjonalności?Odpowiedź Karla jest dobra. Oto dodatkowe zastosowanie, które, jak sądzę, nikt inny nie wspomniał. Typ
powinien być typem, który zawiera wszystkie wartości w typie
A
i wszystkie wartości w typieB
. Jeśli typemB
jestNothing
, typemif
wyrażenia może być typA
. Często ogłaszam rutynęstwierdzenie, że kod nie zostanie osiągnięty. Ponieważ jest to typ
Nothing
,unreachable(s)
można go teraz używać w dowolnymif
lub (częściej)switch
bez wpływu na rodzaj wyniku. Na przykładScala 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ą,
Nothing
któ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ładerror
funkcja ze standardowego preludium ma schemat typówforall a. [Char] -> a
. Więc możesz pisaća typ wyrażenia będzie taki sam jak typ
A
dowolnego wyrażeniaA
.Pusta lista w Haskell ma schemat typów
forall a. [a]
. JeśliA
jest wyrażeniem, którego typ jest typem listy, tojest wyrażeniem tego samego typu co
A
.źródło
forall a . [a]
a typem[a]
w Haskell? Czy zmienne typu nie są już powszechnie kwantyfikowane w wyrażeniach typu Haskell?forall
w 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, żeforall a . [a]
nie jest to standard, podczas gdy[a]
jest.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”).
Vacuous
) ma zerowe wartości † .()
.(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 izomorficznyBool
.A
iB
zasadniczo ma wszystkie wartościA
plus wszystkie wartościB
, stąd typ sumy . Na przykład,Either () Bool
ma trzy wartości, będę je nazywaćLeft ()
,Right False
iRight True
.Typ dolny jest elementem tożsamości sumy:
Either Vacuous A
ma tylko wartości formularzaRight a
, ponieważLeft ...
nie ma sensu (Vacuous
nie 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. NawetVoid
typ 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.źródło
Void
)”, którego nie należy mylić z wartościąbottom
, która jest członkiem dowolnego typu w Haskell .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ę.źródło
[]
reprezentują wszystkie z nich i zostaną zaimplementowane do konkretny typ w razie potrzeby.[a]
. Podobnie,:t Left 1
dajeNum a => Either a b
. Faktyczna ocena wyrażenia wymusza rodzaja
, ale nieb
:Either Integer b
forall
w swoim rodzaju,forall a. [a]
. Istnieje kilka fajnych sposobów myśleniaforall
, ale naprawdę zajmuje to trochę czasu.*
.[]
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 deklarujeszdata Foo x = Foo | Bar x (Foo x)
; teraz możesz używać goFoo
jako konstruktora typu lub wartości, ale zdarza się, że wybierasz tę samą nazwę dla obu.Przydaje się w analizie statycznej dokumentowanie faktu, że dana ścieżka kodu jest nieosiągalna. Na przykład, jeśli napiszesz w C #:
Kompilator narzeka, że
F
nie zwraca niczego w co najmniej jednej ścieżce kodu. JeśliAssert
miałby zostać oznaczony jako niezwracający, kompilator nie musiałby ostrzegać.źródło
W niektórych językach
null
ma typ dolny, ponieważ podtyp wszystkich typów ładnie definiuje, dla których języków używa się null (pomimo łagodnej sprzecznościnull
bycia zarówno sobą, jak i funkcją, która zwraca się, unikając typowych argumentów na temat tego, dlaczegobot
powinien 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
bot
jako błędu, którego można użyć do dostarczenia niestandardowych błędów kompilatora.źródło
void
popularne języki (choć z nieco inną semantyką dla tego samego zastosowania), nienull
. Chociaż masz również rację, że większość języków nie modeluje wartości null jako najniższego typu.null
, np. Możesz porównać wskaźnik znull
wynikiem 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.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 jednostki
void
; 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.źródło
var foo = someCondition() ? functionReturningBar() : functionThatAlwaysThrows()
może wywnioskować rodzajfoo
asBar
, ponieważ wyrażenie nigdy nie może dać niczego innego?void
w 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 :)functionThatAlwaysThrows()
zostały zastąpione przez wyraźnythrow
, dzięki specjalnej języka w standardzie. Posiadanie takiego typu byłoby poprawą.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).
źródło