PROGRAMMING LANGAUGES
STUDY GUIDE
MODULE 6
DATA TYPES
SUBTOPIC 1: COMMON TYPES OF DATA
Data Types
To developed an intuitive notion of what types are; what's behind the intuition?
✓ collection of values from a "domain" (denotational approach)
✓ internal structure of a bunch of data, described down to the level of a small set
of fundamental types (structural approach)
✓ equivalence class of objects (implementer's approach)
✓ collection of well-defined operations that can be applied to objects of that type
(abstraction approach)
Example for Denotational approach:
• the phrase n*m produces a denotation when provided with an environment that has
binding for its two free variables: n and m.
• If in the environment n has the value 3 and m
has the value 5, then the denotation is 15.
denotational semantics is concerned with finding mathematical objects called domains that
represent what programs do.
Example of Structural approach:
• Structured data refers to any data that resides in a fixed field within a record or file.
• This includes data contained in relational databases and spreadsheets.
• This includes defining what fields of data will be stored and how that data will be
stored: data type (numeric, currency, alphabetic, name, date, address)
• Any restrictions on the data input (number of characters; restricted to certain terms
such as Mr., Ms. or Dr.; M or F).
Example of Implementer’s approach:
Create a set of equivalence classes of declaration elements and expression that must have
exactly the same type
• Computers are naturally untyped.
• Encoding by a type is necessary to store data:
• as integer: -1, -396, 2, 51, 539
• as float: -3.168, 384.0, 1.234e5
• as Strings: “FEU"
• So how do we know what it means?
* We associate types with:
• Expressions
• Objects (anything that can have a name)
• Type checking can also be done with user-defined types:
• speed = 100 mile/hour
• time = 2 hour
• distance = speed * time (mile)
What has a type?
* things that have values:
constants,
variables,
fields,
parameters,
subroutines.
objects.
Data Types
• What are types good for?
• understood context for operator (“+” is concatenation for Strings vs. integer
summation for integers, etc.)
– Type checking – is to make sure that certain meaningless operations do not
occur
• type checking cannot prevent all meaningless operations
• It catches enough of them to be useful
STRONG TYPING
- means that the language prevents you from applying an operation to data on
which it is not appropriate:
- unlike types cause type errors.
» informally, it means that the language prevents you from applying an operation to data on
which it is not appropriate
» more formally, it means that the language does not allow variables to be used in a way
inconsistent with their types (no loopholes)
STATIC TYPING
• means that the compiler can do all the checking at compile time types are
computed and checked at compile time.
» variables have types
» compiler can do all the checking of type rules at compile time
» ADA, PASCAL, ML
Type Systems
Examples
• Common Lisp is strongly typed, but not statically typed
• Ada is statically typed
• Pascal is almost statically typed
• Java is strongly typed, with a non-trivial mix of things that can be checked statically
and things that have to be checked dynamically (for instance, for dynamic binding):
String a = 1; compile-time error.
double d = 10.0;
int i = d; compile-time error.
• Python is strong dynamic typed:
int a = 1
b = "2"
a+b run-time error
COMMON TERMS:
DISCRETE TYPES – countable
• integer
• boolean
• char
• enumeration
• subrange
SCALAR TYPES - one-dimensional
• discrete
• real
COMPOSITE TYPES:
– records (unions)
– arrays
• strings
– sets
– pointers
– lists
– files
❖ Discrete types
• » Countable
• » One-dimensional
• • integer
• • boolean
• • character
❖ floating-point types, real
• typically 64 bit (double in C); sometimes 32 bit as well (float in C)
❖ rational types
• used to represent exact fractions (Scheme, Lisp)
• integer types
• » often several sizes (e.g., 16 bit, 32 bit, 64 bit)
• » sometimes have signed and unsigned variants
• boolean
• character
• enumeration types
Type Checking
• A TYPE SYSTEM has rules for
– type equivalence (when are the types of two values the same?) (when do two
objects have the same type?)
– type compatibility (when can a value of type A be used in a context that expects
type B?) (where can objects of a given type be used?)
• type inference (what is the type of an expression, given the types of the operands?)
(how do you determine the
• type of an expression from the types of its
• parts)
• Certainly format does not matter:
struct { int a, b; }
is the same as
struct {
int a, b;
}
CERTAINLY WANT THEM TO BE THE SAME AS
struct {
int a;
int b; }
Type checking is the process of ensuring that a program obeys the type system’s type
compatibility rules.
• » A violation of the rules is called a type clash.
Two major approaches: structural equivalence and name equivalence
• Name equivalence is based on declarations
• Structural equivalence is based on some notion of meaning behind those
declarations
• Name equivalence is more fashionable these days
COERCION
– conversion of a value into another of a different data type
Example:
int x = 10;
float y;
y = (float) x;
C has lots of coercion, too, but with simpler rules:
• all floats in expressions become doubles
• short int and char become int in expressions
In effect, coercion rules
are a relaxation of type checking
• Languages such as Modula-2 and Ada do not permit coercions
• one of the hardest parts of the language to understand
Records(Structures) and Variants(Unions)
RECORDS
• A record consists of a number of fields:
– Each has its own type:
struct my_example
{
int label;
char letter;
char name[20];
} mystruct ;
UNIONS (VARIANT RECORDS)
• A union is a special data type that allows to store different data types in the same
memory location.
• You can define a union with many members,
but only one member can contain a value at any
given time.
❖ Variant records (a and b take up the same memory, saves memory, but usually unsafe,
tagging can make safe again.
union {
int a;
float b;
}
SUBTOPIC 2: IMPORTANT TYPES OF DATA
Arrays
Arrays are the most common and important composite data types.
Unlike records, which group related fields of disparate types, arrays are usually homogeneous
Semantically, they can be thought of as a mapping from an index type to a component or
element type
A slice or section is a rectangular portion of an array
Dimensions, Bounds, and Allocation
global lifetime, static shape — If the shape of an array is known at compile time, and if the
array can exist throughout the execution of the program, then the compiler can allocate space
for the array in static global memory.
local lifetime, static shape — If the shape of the array is known at compile time, but the array
should not exist throughout the execution of the program, then space can be allocated in the
subroutine’s stack frame at run time.
local lifetime, shape bound at elaboration time
• Contiguous elements
– column major - only in Fortran
– row major
• used by everybody else
• makes array [a..b, c..d] the same as array [a..b] of array [c..d]
TWO LAYOUT STRATEGIES FOR ARRAYS
– Contiguous elements
– Row pointers
ROW POINTERS
– an option in C
– allows rows to be put anywhere - nice for big arrays on machines with
segmentation problems
– avoids multiplication
– nice for matrices whose rows are of different lengths
• e.g. an array of strings
– requires extra space for the pointers
Example: Suppose
A : array [L1..U1] of array [L2..U2] of array [L3..U3] of elem;
D1 = U1-L1+1
D2 = U2-L2+1
D3 = U3-L3+1
Let
S3 = size of elem
S2 = D3 * S3
S1 = D2 * S2
Strings
• Strings are really just arrays of characters
• They are often special-cased, to give them flexibility (like polymorphism or dynamic
sizing) that is not available for arrays in general
– It's easier to provide these things for strings than for arrays in general because
strings are one-dimensional and (more important) non-circular
Pointers and Recursive Types
• Pointers serve two purposes:
– efficient (and sometimes intuitive) access to elaborated objects (as in C)
– dynamic creation of linked data structures, in conjunction with a heap storage
manager
• Several languages (e.g. Pascal) restrict pointers to accessing things in the heap
• Pointers are used with a value model of variables
– They aren't needed with a reference model
Pointers and Recursive Types
Pointers and Recursive Types
• C pointers and arrays
int *a == int a[]
int **a == int *a[]
• BUT equivalences don't always hold
– Specifically, a declaration allocates an array if it specifies a size for the first
dimension
– otherwise it allocates a pointer
int **a, int *a[] pointer to pointer to int
int *a[n], n-element array of row pointers
int a[n][m], 2-d array
Pointers and Recursive Types
• Problems with dangling pointers are due to
– explicit deallocation of heap objects
• only in languages that have explicit deallocation
– implicit deallocation of elaborated objects
• Two implementation mechanisms to catch dangling pointers
– Tombstones
– Locks and Keys
• Problems with garbage collection
– many languages leave it up to the programmer to design without garbage
creation - this is VERY hard
– others arrange for automatic garbage collection
– reference counting
• does not work for circular structures
• works great for strings
• should also work to collect unneeded tombstones
• Garbage collection with reference counts
MARK-AND-SWEEP
– commonplace in Lisp dialects
– complicated in languages with rich type structure, but possible if language is
strongly typed
– achieved successfully in Cedar, Ada, Java, Modula-3, ML
– complete solution impossible in languages that are not strongly typed
– conservative approximation possible in almost any language (Xerox Portable
Common Runtime approach)
Lists
• A list is defined recursively as either the empty list or a pair consisting of an object
(which may be either a list or an atom) and another (shorter) list
– Lists are ideally suited to programming in functional and logic languages
• In Lisp, in fact, a program is a list, and can extend itself at run time by
constructing a list and executing it
– Lists can also be used in imperative programs
Files and Input/Output
• Input/output (I/O) facilities allow a program to communicate with the outside world
– interactive I/O and I/O with files
• Interactive I/O generally implies communication with human users or physical devices
• Files generally refer to off-line storage implemented by the operating system
• Files may be further categorized into
– temporary
– persistent
