FCS2: Lecture 2
Values and Types
Chapter 2: Programming Language
Design Concepts
Values and Types
• A computer program takes input, manipulates
it and produces output.
• The input is some form of data and the output
is some form of data.
• Therefore the study of data is important.
In this lecture..
• Types of values
• Primitive and composite types and their
underlying representation.
Types
• Different programming languages support
different types of values:
• Java: booleans, characters, integers, real
numbers, arrays and objects
• C: integers, real numbers, structures, arrays,
unions and pointers
• Most programming languages group values
into types
What is a type?
• A set of values
• If is a value of type then we mean that
• An expression, E, has type if the result of
evaluating E will be a value of type .
• Is every set of values suitable to be regarded
as a type?
Types
• **Each operation associated with a type
behaves uniformly when applied to all values of
the type.
• is a type because the operations and, or and
not operate uniformly over these values
• is not a type. There are no useful operations
that could be applied uniformly over this set.
• Programming languages have primitive,
composite and recursive types.
Primitive types
• A primitive type: one which cannot be decomposed
into simpler values
• Programming languages have built-in primitive types
• The type of primitive types in different programming
languages reflect the intended application area:
– Cobol (fixed-point numbers) used in commercial data
processing (e.g. banking)
– Fortran (real numbers with a choice of precision) used in
scientific and engineering applications
Primitive Types
• Common Primitive Types
– boolean
– char
– int
– float
• Java provides several integer types: byte, short, int, long
• The cardinality (#) of a Type (in Java):
– #boolean=2
– #char=216 (2 bytes)
– #float=? (4 bytes)
Composite Types
• A composite value (or data structure) is a
value that is composed from simpler values.
• A composite type is a type whose values are
composite.
• Structures, records, arrays, objects, strings,
lists, trees are composite types
Composite types
• Composite types can be understood in terms
of a small number of structuring concepts
including:
– Cartesian product
– Mapping
Cartesian Product
• Consider the pair of values
• is the set of all pairs such that comes from
the set and comes from the set
• Consider some examples of Cartesian
Product
Cartesian Product
• Month = {jan, feb, mar, apr, may, jun, jul, aug, sep, oct, nov, dec}
• Day={1, 2, 3,…,31}
• Month X Day = ?
• #(Month X Day) = ?
• In C programming:
enum Month = {jan, feb, mar, apr, may, jun, jul, aug, sep,
oct, nov, dec};
struct Date{
Month m;
byte d;
}
Mappings
• The concept of mapping underlies two
language features (arrays and
functions/methods)
• What does mean?
– is a mapping from to
– maps every value in to a value in
– What is the cardinality of ?
• Consider some examples
Mappings
• represents the set of all mappings from to
• Consider some examples.
• What is the cardinality of ?
Arrays implementing Mappings
• An array is an indexed sequence of
components
• An array has one component of type for each
value of type
• The length of an array is the number of its
components, which is # .
• The type must be finite
• Consider some examples
Functions implementing Mappings
• Consider the following function/method:
boolean isEven (int n){
return (n%2 ==0);
}
• What mapping does isEven implement? i.e.
What are the pairs of elements?
• What is the type of the mapping? i.e. The
mapping is from set ? to set ?
Functions implementing Mappings
• Consider a function/method with multiple
parameters
float power(float b, int n){
…
}
• What mapping does the method power
implement?
• What is the type of the mapping implemented
by the power function/method?
Summary
• What is a type?
• What distinguishes a type?
• What is a primitive type?
• What is a composite type?
• What are the underlying concepts for each type we
have seen?
– A primitive type
– A composite type such as a struct in C
– An array type
– A function type
Reading
• Chapter 2: Programming Language Design
Concepts
