2

Values and Types

Part 2
▪ Types of values.
▪ Primitive, composite, recursive types.
▪ Type systems: static vs dynamic typing, type completeness.
▪ Expressions.
▪ Implementation notes.
2-1
 Mappings (1)

▪ We write m : S → T to state that m is a mapping from set

S to set T. In other words, m maps every value in S to
some value in T.
▪ If m maps value x to value y, we write y = m(x). The value
y is called the image of x under m.
▪ Some of the mappings in {u, v} → {a, b, c}:
m1 = {u → a, v → c}
m2 = {u → c, v → c}
m3 = {u → c, v → b} image of u is c,
image of v is b

2-2
 Mappings (2)

▪ Let S → T stand for the set of all mappings from S to T:

S → T = { m | x  S m(x)  T }

▪ What is the cardinality of S → T?

There are #S values in S.
Each value in S has #T possible images under a mapping in S → T.
So there are #T  #T  …  #T possible mappings. Thus:
#(S → T) = (#T)#S #S copies of #T multiplied together

▪ For example, in {u, v} → {a, b, c}

there are 32 = 9 possible mappings.

2-3
 Arrays (1)

▪ Arrays (found in all imperative and OO PLs) can be

understood as mappings.
▪ If an array’s components are of type T and its index values
are of type S, the array has one component of type T for
each value in type S. Thus the array’s type is S → T.
▪ An array’s length is the number of components, #S.
▪ Basic operations on arrays:
• construction of an array from its components
• indexing – using a computed index value to select a component.
so we can select the ith component
2-4
 Arrays (2)

▪ An array of type S → T is a finite mapping.

▪ Here S is nearly always a finite range of consecutive
values
+1, …,
{l, llower u}. This
bound is bound
upper called the array’s index range.

▪ In C and Java, the index range must be {0, 1, …, n–1}.

In Ada, the index range may be any primitive (sub)type
other than Float.
▪ We can generalise to n-dimensional arrays. If an array has
index ranges of types S1, …, Sn, the array’s type is
S1  …  Sn → T.
2-5
 Example: Ada arrays (1)

▪ Type declarations:
type Color is (red, green, blue);
type Pixel is array (Color) of Boolean;

▪ Application code:
p: Pixel := (true, false, true);
c: Color;
array construction
…
p(c) := not p(c);

indexing indexing

2-6
 Example: Ada arrays (2)

▪ Set of values:
Pixel = Color → Boolean = {red, green, blue} → {false, true}
viz: {red → false, green → false, blue → false}
{red → false, green → false, blue → true}
{red → false, green → true, blue → false}
{red → false, green → true, blue → true}
{red → true, green → false, blue → false}
{red → true, green → false, blue → true}
{red → true, green → true, blue → false}
{red → true, green → true, blue → true}

▪ Cardinality:
#Pixel = (#Boolean)#Color = 23 = 8

2-7
 Example: Ada 2-dimensional arrays

▪ Type declarations:
type Xrange is range 0 .. 511;
type Yrange is range 0 .. 255;
type Window is
array (YRange, XRange) of Pixel;

▪ Set of values:
Window = Yrange  Xrange → Pixel
= {0, 1, …, 255}  {0, 1, …, 511} → Pixel

▪ Cardinality:
#Window = (#Pixel)#Yrange  #Xrange = 8256  512

2-8
 Functions as mappings

▪ Functions (found in all PLs) can also be understood as

mappings. A function maps its argument(s) to its result.
▪ If a function has a single argument of type S and its result
is of type T, the function’s type is S → T.
▪ Basic operations on functions:
• construction (or definition) of a function
• application – calling the function with a computed argument.

▪ We can generalise to functions with n arguments. If a

function has arguments of types S1, …, Sn and its result
type is T, the function’s type is S1  …  Sn → T.
2-9
 Example: Ada functions

▪ Definition:
function is_even (n: Integer)
return Boolean is
begin or any other code
return (n mod 2 = 0); that achieves the
end; same effect
▪ Type:
Integer → Boolean

▪ Value:
{…, 0 → true, 1 → false, 2 → true, 3 → false, …}

▪ Other functions of same type: is_odd, is_prime, etc.

2-10
 Disjoint unions (1)

▪ In a disjoint union, a value is chosen from one of several

different types.
▪ Let S + T stand for a set of disjoint-union values, each of
which consists of a tag together with a variant chosen
from either type S or type T. The tag indicates the type of
the variant:
S + T = { left x | x  S } { right y | y  T }
• left x is a value with tag left and variant x chosen from S
• right x is a value with tag right and variant y chosen from T.

▪ Let us write left S + right T (instead of S + T) when we

want to make the tags explicit.

2-11
 Disjoint unions (2)

▪ Cardinality:
#(S + T) = #S + #T hence the “+” notation

▪ Basic operations on disjoint-union values in S + T:

• construction of a disjoint-union value from its tag and variant
• tag test, to determine whether the variant was chosen from S or T
• projection, to recover either the variant in S or the variant in T.

▪ Algebraic data types (Haskell), discriminated records

(Ada), and objects (Java) can all be understood in terms of
disjoint unions.
▪ We can generalise to multiple variants: S1 + S2 +  + Sn.
2-12
 Example: Java objects (1)

▪ Type declarations:
class Point {
private float x, y;
… // methods
}
class Circle extends Point {
private float r; inherits x and y
… // methods from Point
}
class Rectangle extends Point {
private float w, h; inherits x and y
… // methods from Point
}

2-13
 Example: Java objects (2)

▪ Set of objects in this program:

Point(Float  Float)
+ Circle(Float  Float  Float)
+ Rectangle(Float  Float  Float  Float)
+…

▪ The set of objects is open-ended. It is augmented by any

further class declarations.

2-14
 Example: Java objects (3)

▪ Methods:
class Point {
…
public float area()
{ return 0.0; }
}
class Circle extends Point {
…
public float area() overrides Point’s
{ return 3.1416 * r * r; } area() method
}
class Rectangle extends Point {
… overrides Point’s
public float area() area() method
{ return w * h; } 2-15
}
 Example: Java objects (4)

▪ Application code:
Rectangle box =
new Rectangle(1.5, 2.0, 3.0, 4.0);
float a1 = box.area();
it can refer to a
Point it = …; Point, Circle, or
float a2 = it.area(); Rectangle object
calls the appropriate
area() method

2-16
Example: Haskell algebraic data types (1)

▪ Type declaration:
data Number = Exact Int | Inexact Float
Each Number value consists of a tag, together
with either an Integer variant (if the tag is
Exact) or a Float variant (if the tag is Inexact).

▪ Set of values:
Number = Exact Integer + Inexact Float
viz: … Exact(–2) Exact(–1) Exact 0 Exact 1 Exact 2 …
… Inexact(–1.0) … Inexact 0.0 … Inexact 1.0 …

▪ Cardinality:
#Number = #Integer + #Float
2-17
Example: Haskell algebraic data types (2)

▪ Application code:
pi = Inexact 3.1416 disjoint-union
construction
rounded :: Number -> Integer
rounded num =
case num of
Exact i -> i
projection
Inexact r -> round r tag test
(by pattern
matching)

2-18
Example: Ada discriminated records (1)

▪ Type declarations:
type Accuracy is (exact, inexact);
type Number (acc: Accuracy := exact) is
record
case acc of
when exact => ival: Integer;
when inexact => rval: Float;
end case;
end record;

Each Number value consists of a tag field named acc, together

with either an Integer variant field named ival (if the tag is
exact) or a Float variant field named rval (if the tag is inexact).

2-19
Example: Ada discriminated records (2)

▪ Set of values:
Number = exact Integer + inexact Float
viz: … exact(–2) exact(–1) exact 0 exact 1 exact 2 …
… inexact(–1.0) … inexact 0.0 … inexact 1.0 …

▪ Cardinality:
#Number = #Integer + #Float

2-20
Example: Ada discriminated records (3)

▪ Type declarations:
type Form is
(pointy, circular, rectangular);
type Figure (f: Form := pointy) is record
x, y: Float;
case f is
when pointy => null;
when circular => r: Float;
when rectangular => w, h: Float;
end case;
end record;
Each Figure value consists of a tag field named f, together with a pair
of Float fields named x and y, together with either an empty variant or a
Float variant field named r or a pair of Float variant fields named w and h.
2-21
Example: Ada discriminated records (4)

▪ Set of values:
Figure = pointy(Float  Float)
+ circular(Float  Float  Float)
+ rectangular(Float  Float  Float  Float)
e.g.: pointy(1.0, 2.0) represents the point (1, 2)
circular(0.0, 0.0, 5.0)
rectangular(1.5, 2.0, 3.0, 4.0) represents a circle of
… radius 5 centered at (0, 0)
represents a 34 rectang-
le centered at (1.5, 2)

2-22
Example: Ada discriminated records (5)

▪ Application code: discriminated-record

box: Figure := construction
(rectangular, 1.5, 2.0, 3.0, 4.0);
function area (fig: Figure) return Float is
begin
case fig.f is
when pointy =>
return 0.0; tag test
when circular =>
return 3.1416 * fig.r**2;
when rectangular =>
return fig.w * fig.h;
end case;
end; projection
2-23