Types are the most important abstraction in programming.
Types are the central organising principle of the theory of programming languages. Language features are manifestations of type structure. The syntax of a language is governed by the constructs that define its types, and its semantics is determined by the interactions among those constructs. The soundess of a language design — the absence of ill-defined programs — follows naturally.
— Robert Harper, Practical Foundations for Programming Languages
A type is simply a collection of values. Recall that in set theory, a set is a collection of values.
Set
instead of Type
.You have seen previously many methods to construct sets:
That list of methods for constructing sets contains a lot, not all of which are necessarily practical in the context of types in programming languages.
We will see that most languages include some primitive, (also called atomic or basic) types, along with these ways to combine types to form new types:
What is the difference between
Why would we want both types in our language?
Before we discuss types themselves further, lets discuss various classifications of languages based on types.
These are comparative terms.
“Strongly typed”
“Weakly typed” simply means not strongly typed.
Try for yourself: pick a language “X”, and search for
“is X strongly typed?”
Try to
Languages may require annotations on variables and functions (explicit typing) or allow them to be omitted (implicit typing).
Some languages make type annotations a part of the name, or annotate names with sigils to indicate type details.
i
, j
or k
were for integer variables,
and all variables were of floating point.$
have scalar type,@
have array type,%
have hash type, and&
have subroutine type.Are types checked before or at runtime?
“Dynamically typed” is a misnomer.
Being strict about types (preventing type clashes) introduces a (solveable) problem; it prohibits code reuse!
Subtyping and polymorphism provide solutions to this.
One notion of polymorphism is ad hoc polymorphism, also called overloading.
With parametric polymorphism, subroutines have a most general type, based on the shape or form of their arguments.
More formally called row polymorphism.
Most languages include some subset of these primitive, (atomic, basic) types.
int
void
.()
.nil
, null
or none
), there is nothing in the empty type.A few languages include these basic types.
Many languages include a means of defining other finite types. Instances include
Recall from set theory that
There are multiple ways sequence types are represented in programming languages.
One design decision for any sequence (or more generally, any collection) type is whether it is homogeneous or heterogeneous.
Arrays are an abstraction of finite sequences of adjacent memory cells.
O(1)
access time for any element.Lists are simply an abstract notion of sequences.
O(1)
access time.Lazily (non-strictly) constructed lists may even be “infinite”. For instance, the infinite list of 1's in Haskell:
ones = 1 :: ones
Associative arrays, also called hashes, maps or sometimes tables, are sets of key/value pairs.
A quick side note about sets and bags
Consider:
Strings are simply sequences of characters.
A heterogeneous collection of a fixed number of elements.
struct
'sConsider two types A and B.
Consider:
Whereas an element of a product type contains
a union type contains
Unions can be tagged or untagged.
Tagged unions are also known as
Note that union types are unnecessary in a dynamically typed language.
Pointer and reference types capture the notion of a memory address.