Community hub
0 subscribers7 pages, 0 posts
Recent from talks
Be the first to start a discussion here.
Be the first to start a discussion here.
Be the first to start a discussion here.
Be the first to start a discussion here.
Contribute something
Welcome to the community hub built to collect knowledge and have discussions related to Bottom type.
Nothing was collected or created yet.
Bottom type
View on Wikipediafrom Wikipedia
In type theory, a theory within mathematical logic, the bottom type of a type system is the type that is a subtype of all other types.[1]
Where such a type exists, it is often represented with the up tack (⊥) symbol.
Relation with the empty type
[edit]When the bottom type is uninhabited, a function whose return type is bottom cannot return any value, not even the lone value of a unit type. In such a language, the bottom type may therefore be known as the zero, never or empty type which, in the Curry–Howard correspondence, corresponds to falsity.
However, when the bottom type is inhabited, it is then different from the empty type.
If a type system is sound, the bottom type is uninhabited and a term of bottom type represents a logical contradiction. In such systems, typically no distinction is drawn between the bottom type and the empty type, and the terms may be used interchangeably.
Computer science applications
[edit]In subtyping systems, the bottom type is a subtype of all types.[1] It is dual to the top type, which spans all possible values in a system.
If the bottom type is inhabited, its term(s) typically correspond to error conditions such as undefined behavior, infinite recursion, or unrecoverable errors.
In Bounded Quantification with Bottom,[1] Pierce says that "Bot" has many uses:
- In a language with exceptions, a natural type for the raise construct is raise ∈ exception -> Bot, and similarly for other control structures. Intuitively, Bot here is the type of computations that do not return an answer.
- Bot is useful in typing the "leaf nodes" of polymorphic data structures. For example, List(Bot) is a good type for nil.
- Bot is a natural type for the "null pointer" value (a pointer which does not point to any object) of languages like Java: in Java, the null type is the universal subtype of reference types.
nullis the only value of the null type; and it can be cast to any reference type.[2] However, the null type is not a bottom type as described above, it is not a subtype ofintand other primitive types. - A type system including both Top and Bot seems to be a natural target for type inference, allowing the constraints on an omitted type parameter to be captured by a pair of bounds: we write S<:X<:T to mean "the value of X must lie somewhere between S and T." In such a scheme, a completely unconstrained parameter is bounded below by Bot and above by Top.
In programming languages
[edit]Most commonly used languages don't have a way to denote the bottom type. There are a few notable exceptions.
In Haskell, the bottom type is called Void.[3]
In Common Lisp the type NIL, contains no values and is a subtype of every type.[4] The type named NIL is sometimes confused with the type named NULL, which has one value, namely the symbol NIL itself.
In Scala, the bottom type is denoted as Nothing. Besides its use for functions that just throw exceptions or otherwise don't return normally, it's also used for covariant parameterized types. For example, Scala's List is a covariant type constructor, so List[Nothing] is a subtype of List[A] for all types A. So Scala's Nil, the object for marking the end of a list of any type, belongs to the type List[Nothing].
In Rust, the bottom type is called the never type and is denoted by !. It is present in the type signature of functions guaranteed to never return, for example by calling panic!() or looping forever. It is also the type of certain control-flow keywords, such as break and return, which do not produce a value but are nonetheless usable as expressions.[5]
In Ceylon, the bottom type is Nothing.[6] It is comparable to Nothing in Scala and represents the intersection of all other types as well as an empty set.
In Julia, the bottom type is Union{}.[7]
In TypeScript, the bottom type is never.[8][9]
In JavaScript with Closure Compiler annotations, the bottom type is !Null (literally, a non-null member of the Null unit type).
In PHP, the bottom type is never.
In Python's optional static type annotations, the general bottom type is typing.Never (introduced in version 3.11),[10] while typing.NoReturn (introduced in version 3.5) can be used as the return type of non-returning functions specifically (and doubled as the general bottom type prior to the introduction of Never).[11]
In Kotlin, the bottom type is Nothing.[12]
In D, the bottom type is noreturn.[13]
In Dart, since version 2.12 with the sound null safety update, the Never type was introduced as the bottom type. Before that, the bottom type used to be Null.[14][15]
See also
[edit]References
[edit]- ^ a b c Pierce, Benjamin C. (1997). "Bounded Quantification with Bottom". Indiana University CSCI Technical Report (492): 1.
- ^ "Section 4.1: The Kinds of Types and Values". Java Language Specification (3rd ed.).
- ^ "Data.Void". Hackage. Retrieved 2023-09-20.
- ^ "Type NIL". Common Lisp HyperSpec. Retrieved 25 October 2022.
- ^ "Primitive Type never". The Rust Standard Library Documentation. Retrieved 2020-09-24.
- ^ "Chapter 3. Type system — 3.2.5. The bottom type". The Ceylon Language. Red Hat, Inc. Retrieved 2017-02-19.
- ^ "Essentials - The Julia Language", The Julia Programming Language Documentation, retrieved 2021-08-13
- ^ The never type, TypeScript 2.0 release notes, Microsoft, 2016-10-06, retrieved 2019-11-01
- ^ The never type, TypeScript 2.0 release notes, source code, Microsoft, 2016-10-06, retrieved 2019-11-01
- ^ "typing — Support for type hints — Python 3.12.0a0 documentation". docs.python.org. Retrieved 2024-03-02.
- ^ typing.NoReturn, typing — Support for type hints, Python documentation, Python Software Foundation, retrieved 2024-03-02
- ^ Nothing, retrieved 2020-05-15
- ^ "Types - D Programming Language". dlang.org. Retrieved 2022-10-20.
- ^ Understanding null safety - top and bottom, retrieved 2022-04-13
- ^ Understanding null safety - never for unreachable code, retrieved 2022-04-13
Further reading
[edit]Bottom type
View on Grokipediafrom Grokipedia
In type theory, the bottom type—also known as the empty type or zero type—is the type that contains no values and serves as a subtype of every other type in a given type system, representing the least element in the subtype relation.[1][2] This property ensures that values of the bottom type can be safely used wherever any other type is expected, though no such values exist, making it uninhabited and useful for modeling impossibility or contradictions.[1]
The bottom type corresponds to the initial object in the category of types under subtyping, analogous to the empty set in set theory or the falsity constant in logic, where it inhabits no terms but allows type systems to remain closed under operations like intersections or products.[2] In formal semantics, it often denotes divergent computations or non-terminating programs, distinguishing it from the unit type (which has exactly one value) by its complete lack of inhabitants.[1]
In programming languages with advanced type systems, the bottom type facilitates features like exhaustive pattern matching, dead code elimination, and modeling functions that never return, such as error handlers or infinite loops.[3] For instance, TypeScript's
This approach, supported by GHC extensions like PatternGuards (introduced around 2003), allows flexible matching while relying on ⊥ to model unreachable cases without altering the function's type.[25]
never type represents values that never occur, acting as a subtype of all types to refine control flow analysis and prevent unreachable code.[4] Similarly, Rust's ! (never) type denotes computations that do not produce a value, coercible to any type for use in error propagation or panics.[3] These implementations highlight the bottom type's role in enhancing type safety and expressiveness without introducing runtime overhead.
Definition and Properties
Formal Definition
In type theory, the bottom type, often denoted as , is defined as the least element in the lattice of types under the subtyping relation, making it a subtype of every other type in the system.[2] It is represented as an uninhabited type, meaning it contains no values or terms, in contrast to inhabited types that admit at least one inhabitant.[5] Logically, under the Curry-Howard correspondence, the bottom type aligns with falsehood, such that the implication holds for any type , as there are no terms of type to falsify the implication (ex falso quodlibet).[6] This notion traces its origins to denotational semantics in domain theory, developed by Dana Scott in the 1970s to model recursion and fixed points, where the bottom element denotes undefined or non-terminating behavior.[7]Key Properties
The bottom type, often denoted ⊥, embodies the absurdity principle in type theory: assuming the existence of a term inhabiting ⊥ leads to a logical contradiction, enabling the derivation of any proposition or type through the ex falso quodlibet rule, which is foundational for proof by contradiction in constructive settings.[8] This property arises because ⊥ has no introduction rules or constructors, making any purported inhabitant impossible to construct without violating the type system's consistency.[2] A key structural property of the bottom type is its universality in subtyping relations: as the least element in the subtype lattice, ⊥ is a subtype of every other type in the system, allowing values (or rather, the absence thereof) of bottom to be safely coerced to any expected type without runtime errors.[2] This universality facilitates flexible type checking and inference, particularly in polymorphic contexts where bottom serves as a "catch-all" subtype, though its uninhabited nature ensures it never introduces actual values.[2] The non-constructibility of the bottom type underscores its emptiness: unlike inhabited types, ⊥ admits no terms, constructors, or values, rendering it computationally irrelevant and preventing any meaningful computation from proceeding on its instances.[2] This property distinguishes bottom from other empty-like constructs and ensures that functions expecting bottom inputs are total, as they need not handle any cases.[2] In domain theory, which provides denotational semantics for typed lambda calculi, the bottom type corresponds to the least element ⊥ of a domain, representing undefined or partial computations and serving as the initial element in the least fixed-point construction for recursive type definitions.[7] This role is essential for modeling recursive functions and data types, where iterations begin from bottom and approximate towards fixed points through directed complete partial orders (dcpos).[7]Relations to Other Types
Empty Type
In many type systems, the bottom type coincides with the empty type, often denoted ∅ or ⊥, as both represent uninhabited types containing no values.[9] This equivalence arises because the bottom type serves as the least element in the type lattice, mirroring the empty set's role as the initial object in categorical models of type theory.[10] Consequently, expressions typed as bottom or empty can be safely coerced to any other type via subtyping, as no actual values exist to violate type invariants. In more advanced systems, particularly those with non-strict evaluation semantics, distinctions emerge: the bottom type may model divergence or non-termination (e.g., infinite loops), while the empty type strictly captures impossible or absent values.[10] For instance, in call-by-need languages, assigning the bottom type to diverging computations prevents unsound subtyping equivalences, such as treating a pair of a diverging expression and an integer as interchangeable with a pair involving a boolean, whereas the empty type maintains a pure interpretation as the empty set without incorporating computational effects like non-termination.[10] In logical contexts, such as intuitionistic logic under the Curry-Howard correspondence, the empty type embodies falsehood (⊥), where the absence of terms proves a contradiction, directly paralleling the bottom type's uninhabited nature in type theory.[8] A term inhabiting the empty type would derive any proposition via ex falso quodlibet, reinforcing its foundational role in constructive proofs. This overlap supports type safety by enabling the empty or bottom type to statically model errors or unreachable states, allowing functions that "never return" (due to impossibility or divergence) to integrate seamlessly without requiring runtime exception handling or checks.[9] By leveraging the bottom type's universality as a subtype of all types, systems can eliminate dynamic error propagation in these cases, ensuring compile-time guarantees of correctness.Top Type
The top type, denoted , serves as the universal supertype in type theory, meaning that every type is a subtype of . Unlike the bottom type , which is uninhabited and thus contains no values, the top type is inhabited by any possible value, allowing it to act as a catch-all or most general type in hierarchical structures. This positions as the greatest element in the partial order of types under subtyping. Note that the top type should not be confused with the unit type, which is a distinct singleton type often corresponding to the terminal object in categorical semantics.[12] In the context of bounded lattices formed by types ordered by subtyping, the top type exhibits a clear duality with the bottom type: while functions as the infimum or least element (subtype of all types), acts as the supremum or greatest element (supertype of all types). This symmetry underscores their complementary roles in type hierarchies, where the lattice is bounded above by and below by . Such duality ensures that type systems can model complete partial orders effectively, facilitating proofs and constructions in theoretical foundations.[2][12] During type unification processes, the top type often plays the role of a wildcard or universal type, representing a placeholder that can match any specific type in inference algorithms, thereby enabling flexible generalization without overconstraining solutions. This usage highlights 's utility in deriving principal types or most general unifiers. In category theory, the bottom type aligns with the initial object, from which there is exactly one morphism to any other object. Dually, the unit type corresponds to the terminal object, an object such that there is exactly one morphism from any object to . The top type in subtyping lattices, while the greatest element, does not directly correspond to the terminal object but complements the bottom in the subtype poset, emphasizing their symmetric extremes in categorical semantics of types.[2]Theoretical Applications
Subtyping and Lattices
In type theory, the bottom type functions as the minimal element in the subtyping relation, serving as a subtype of every other type in the system. This is formalized by the rule , which guarantees that can safely substitute for any type without violating type safety, thereby enabling covariant subtyping in constructs like function types where the argument position requires a supertype.[13] Such positioning of as the least element ensures that subtyping forms a partial order with a bottom, preventing inconsistencies in type hierarchies and supporting the propagation of type information downward in the lattice.[14] The types in a system equipped with a bottom type form a complete lattice under subtyping, where represents the infimum (greatest lower bound) of the entire type set, and the top type serves as the supremum (least upper bound). In this structure, the meet operation (glb) computes the greatest lower bound between two types, akin to intersection, while the join operation (lub) computes the least upper bound, akin to union; for instance, in algebraic subtyping systems, the meet of two function types and is .[14] This lattice framework, often distributive to facilitate algorithmic subtyping decisions, allows for the existence of meets and joins for arbitrary subsets of types, ensuring totality in the sense that every pair of types has a well-defined glb and lub relative to .[15] The bottom type's role as the meet of the empty set further solidifies the lattice's completeness, enabling proofs of properties like transitivity and reflexivity in subtyping derivations.[13] In certain models of non-structural subtyping with both and , the subtyping relation is total, as all types lie between and , ensuring comparability within those lattices.[13] This property simplifies type checking and inference by avoiding incomparable types, as demonstrated in logics where encodes the empty type to resolve undecidability in structural variants.[15] In applications to bounded quantification, is employed as the implicit lower bound for generics and wildcards, permitting the widest possible instantiation without restricting to a specific supertype. For example, in wildcard-based systems, an unbounded wildcard like Java's? is modeled with as the lower bound, equivalent to , which allows substitution with any type while preserving covariance in producer positions.[16] This usage in lower-bounded type variables, such as , facilitates flexible polymorphism by treating as the neutral element for lower constraints, enhancing expressiveness in languages supporting impredicative instantiation.[17]
Polymorphism and Inference
In parametric polymorphism, the bottom type enables polymorphic functions to operate uniformly across type instances, including the uninhabited bottom type, without necessitating specialized implementations. As the least element in the type lattice, the bottom type is a subtype of every other type, allowing a universally quantified function like ∀α. α → α to accept a bottom value as an argument of any type α while preserving the function's parametric generality. This integration avoids representational overhead, as the type system can simplify quantified types involving monotonic positions of the bottom type, replacing them with equivalent forms that maintain semantic equivalence. For instance, a type such as ∀α:∀β:α → β simplifies to top → bottom under subtyping constraints, reflecting the bottom type's role in bounding polymorphic outputs to uninhabitable cases.[18] The bottom type enhances type inference in systems supporting polymorphism, such as the Hindley-Milner framework, by resolving ambiguities during unification. In unification algorithms, type variables facing conflicting constraints—such as needing to subtype multiple incompatible types—can be bound to the bottom type, which unifies seamlessly with any type due to its universal subtyping. This mechanism yields the most general unifier without over-specializing, facilitating efficient inference for expressions involving potential non-values. By treating the bottom type as a canonical solution for underconstrained variables, inference algorithms maintain completeness and decidability, avoiding unification failures in polymorphic contexts.[19] The bottom type models non-terminating or divergent computations within polymorphic settings, representing the domain-theoretic least element that inhabits no values yet subtypes all types. A non-terminating function can thus be assigned the bottom type, enabling its use in polymorphic positions—such as arguments to higher-order functions—without requiring the caller to specialize for termination guarantees. This approach leverages polymorphism's uniformity to handle divergence generically; for example, inferred types from polymorphic programs can detect non-termination by propagating bottom constraints through recursive or higher-order calls, ensuring type safety without explicit termination checks. Such modeling aligns with subtyping lattices where the bottom type anchors incomplete computations, briefly relating to totality proofs by excluding divergent paths from well-typed behaviors.[20] In advanced dependent type systems, the bottom type supports proofs of totality by explicitly excluding impossible or contradictory cases during type checking. When index constraints in dependent types derive an unsatisfiable proposition equivalent to the bottom type (denoted ⊥), it signals that no closed value can inhabit the type, allowing the system to prune unreachable branches and verify exhaustive coverage. For pattern matching, if constraints entail ⊥ for a clause, the matcher confirms no input can reach it, aiding totality by ensuring functions handle all valid cases without gaps or runtime errors. This use of the bottom type integrates with dependent quantification to enforce invariants, proving program correctness in contexts like recursive definitions or effectful computations.[21]Practical Implementations
In Functional Languages
In functional programming languages like Haskell, the bottom type, denoted as ⊥, represents computations that fail to produce a value, encompassing both non-termination (such as infinite loops) and explicit errors.[22] This concept is integral to Haskell's semantics, where ⊥ is included in every type, allowing any expression to potentially diverge without violating type safety. The Prelude module providesundefined :: a as a canonical inhabitant of ⊥ for any type a, enabling programmers to stub out incomplete implementations that raise a runtime error when evaluated.[23]
Haskell's lazy evaluation strategy leverages ⊥ through unevaluated thunks, which are suspensions of computations that delay execution until their results are demanded. If a thunk's computation yields ⊥, the bottom value propagates without forcing immediate evaluation, preserving referential transparency in pure functions. This mechanism facilitates short-circuiting in control structures; for instance, the logical operators && and || avoid evaluating the second argument if the first determines the outcome, as the remaining thunk remains unevaluated and ⊥-infused if applicable.[24]
Semantically, ⊥ is included in every type due to Haskell's non-strict evaluation, and polymorphic functions like undefined have the type forall a. a, allowing their use in any context to represent impossible or erroneous cases. This supports error handling and modeling without subtyping in Haskell's Hindley-Milner type system.
In practice, Haskell's pattern matching exhaustiveness checks, implemented in GHC since the early 2000s, utilize bottom for handling impossible branches to avoid runtime failures. When patterns are non-exhaustive, GHC issues warnings, and developers often complete matches with a catch-all clause returning undefined or error, ensuring the function is total while signaling impossibility at runtime. For example, in a function processing a sum type like data Color = Red | Green | Blue, an exhaustive match might include:
processColor Red = "red"
processColor Green = "green"
processColor Blue = "blue"
processColor _ = undefined -- Bottom for any impossible extension
processColor Red = "red"
processColor Green = "green"
processColor Blue = "blue"
processColor _ = undefined -- Bottom for any impossible extension
In Object-Oriented Languages
In object-oriented languages, the bottom type is typically adapted to handle scenarios where no valid value can be produced, such as in exception propagation or interface implementations that cannot be fulfilled. This adaptation contrasts with functional paradigms by emphasizing mutable state and runtime errors over pure non-termination, enabling polymorphic dispatch in inheritance-based systems. Java lacks an explicit bottom type but approximates it throughvoid for non-returning methods and null for absent references. Unchecked exceptions, subclasses of RuntimeException, model bottom-like behavior by allowing abrupt termination without compile-time declaration, effectively permitting a method to "return" no value while remaining type-compatible with any caller expectation. For instance, a method declared to return String but always throwing a RuntimeException behaves as if it has a bottom subtype, avoiding type errors in polymorphic contexts.
Scala, as a hybrid object-oriented and functional language, provides an explicit bottom type called Nothing, which is a subtype of every other type and has no instances. Nothing is commonly used for empty collections, such as List.empty, which has type List[Nothing] and can be safely upcast to List[T] for any T due to subtyping. It also serves as the return type for methods that never complete normally, like those throwing exceptions: def fail(msg: String): Nothing = throw new RuntimeException(msg). This enables polymorphic usage, such as returning Nothing from case statements to satisfy exhaustiveness without providing a value.[26][27]
In object-oriented inheritance hierarchies, the bottom type integrates with exception classes to support polymorphic handling. Exception hierarchies typically root at a top type like Throwable in Java or Exception in other languages, but the bottom type represents the uninhabited intersection of all exception subtypes, allowing catch blocks to polymorphically handle any possible error as a supertype. This design ensures that functions returning bottom (e.g., via guaranteed exceptions) are subtypes of all function types, facilitating safe substitution in overridden methods or interface implementations.
C++ templates exhibit bottom-like behavior through SFINAE (Substitution Failure Is Not an Error), introduced prominently in C++11, which discards invalid template specializations at compile time without error. This simulates an uninhabited type when substitution fails, enabling conditional compilation akin to selecting from a bottom type in a type lattice. For example, trait detection using std::enable_if relies on SFINAE to provide a valid overload only if a type satisfies criteria, otherwise falling back to no implementation—mirroring the absence of values in a bottom type.References
- https://arxiv.org/pdf/1810.05555