Transcript Data Types

CHAPTER 4
TYPES:
DATA REPRESENTATION
Data Representation
Example:
A day of the year is a data
object in some application. In a program,
a day can be represented by an integer
between 1 and 366.
January 1
1
-
February 5
36
-
May 6
126 | 127 ? Depend on number
of days of February
chapter 4
2
Values and Their Types

Basic Types





Integers
Characters
Reals
Booleans
Structure Types



Array
Records
pointers
chapter 4
3
Type Expressions
How a data representation is built up
Example array [0..99] of char
 To represent data objects
 To lay out values in the underlying
machine
 To check that operator are applied
properly within expressions

chapter 4
4
Preview of Type Name

Basic Types:
Data Type
Pascal
C
boolean
boolean
bool
char
integer
real
char
integer
real
char
int
double
chapter 4
5
Layout
A:array[0..2] of T
R: record
a:Ta;b:Tb;c:Tc
end
A[0]
T
R.a
Ta
A[1]
T
A[2]
T
R.b
R.c
Tb
Tc
p
P:^T
T
A
A: Set of [1..5]
01101
chapter 4
6
Preview of Arrays


consists of a sequence of element of the
same type
Supports random access to its elements
ARRAY [begin-label..end-label] OF data-type
Let A is an array variable ; A[i] is the syntax for the ith element
of array A, and i is called the index of the ith element.
**Meaning of Random Access is the time to access A[i] is
independent of the value of i
chapter 4
7
Preview of Records



Consists of a set of components, each
with its own type.
The components of a record have
names and are called fields.
Field names are referred to variously
as selectors, field identifiers, or
member names.
chapter 4
8
Preview of Records (cont’d)
Example A Entry of the index in a book
can be represented using a combination
of basic types. An entry consists of an
index term and a page number.
An integer term : character string
A page number
: integer
TYPE
termrep
: RECORD
spell :array[0..99] of char;
length:integer;
END;
index_entry : RECORD
term : termrep;
page : integer;
END; chapter 4
9
Enumerations

A finite sequence of names written
between parentheses.
TYPE day = (Mon,Tue,Wed,Thu,Fri,Sat,Sun)
TYPE boolean = (true,false)
**Name like Mon are treated as constants
Operation apply to enumberation
Ordinal: Function ord(x) maps name x to its integer position.
Successor: Function succ(x) maps name x to next name .
Predecessor: Function pred(x) maps name x to previous name.
chapter 4
10
Integer and Reals

Largest and smallest numbers
determined primarily by the number of
bits in machine word.
Operation in Pascal
< <= = <> >= > in
+ - or
/ div mod and
not
chapter 4
Operation in C
||
&&
== !=
< > <= >=
+/ %
!
11
Subranges


A special case of basic types
They restrict the range of values of an
existing type.
The syntax of a subrange in Pascal is
<constant1>..<constant2>
chapter 4
12
ARRAY:
SEQUENCES OF ELEMENTs

An array type has the form
array [<simple>] of <type>
An array type specifies the index of the first and last
elements of the array and the type of all elements.
• Index of the first element, called the lower bound
• Index of the last element, called the upper bound
array [1996..2000] of real
array [(Mon,Tue,Wed,Thu,Fri)] of char
array [char] of token
chapter 4
13
LEXICAL ANALYZER



Uses an array to map characters to tokens
Read input characters in expression
Groups them into tokens





Arithmetic operators
Parentheses
Semicolon
numbers
Numbers are made up digits – 100 ; 3 digits
chapter 4
14
LEXICAL ANALYZER
TYPE token = (plus,minus,times,divide,number,lparen,rparen,semi);
VAR optoken = array [char] of token;
:
Optoken[‘+’] := plus;
Optoken[‘-’] := minus;
...
:
CASE ch OF
‘+’, ‘-’, ‘*’, ‘/’, ‘(’, ‘)’, ‘;’
:
begin
lookahead:=optoken[ch];
ch := ‘’;
end;
‘0’..‘9’ :begin
...
lookahead := number
chapter 4
end;
END; {end of case}
15
Array Layout
VAR A:array[low..high] of T

The machine address of an element
A[i] relative to the address of the first
element.
w
A[low]
base
A[low+1] A[low+2]
base+w
base+2w
…
A[i]
A[high]
base+i*w
Formula for address of A[i] is best expressed as
i*w + (base – low*w)
chapter 4
16
Layout of 2D Array
VAR M : array [lowi..highi] OF [lowj..highj] OF T
VAR M : array [1..3] OF [1..2] OF integer
 m11 m12 
m

 21 m22 
 m31 m32 
Formula for the Address of A[i][j]
i*w + j*w + (base – lowi*wi – lowj*wj)
M[1]
M[2]
M[3]
M[1,1] M[1,2] M[2,1] M[2,2] M[3,1] M[3,2]
chapter 4
17
Storage Allocation

Storage Allocation for the values and
variables in a procedure or function is
done when the function is called.
Function getnum: integer;
Var value : integer;
Begin
value := 0;
repeat
value := value*10 + ord(ch) – ord(‘0’)
getch;
until(ch<‘0’) or (ch>‘9’);
getnum := value;
End;
chapter 4
18
Layout from Allocation



Array layout in C is done statically at
compile time.
Storage allocation is usually done
upon procedure entry.
Static variable if both layout and
allocation are done statically.
chapter 4
19
Static & Dynamic Array Bounds



Static evaluation : Array bounds are
computed at compiled at compile time.
Pascal allow bounds like [xmin..xmax]
Evaluation upon procedure entry : In Algol
60, array bounds were computed when
control entered a procedure.
Dynamic evaluation : In C++, a expression
of the form new char[size] can be evaluated
at any time.
chapter 4
20
Array values Initialization
EXAMPLE Array Initialization in C.
An array initializer is a sequence of values for
array elements.
int coin[] = { 1, 5, 10, 25, 50, 100}
chapter 4
21
RECORD




Record type specifies fields
Variable declaration Allocates Storage
Operations on Records
Comparison of Arrays and Records
chapter 4
22
Record & Field

Record type with k fields can have the
following
<Record-type> ::= Record [<name1> : <type1>] end
IEEE single format 32 bit
1
s
8
exponent
23
fraction
Example
Type scform = record
fraction:real;
exponent:integer;
end;
chapter 4
23
Allocates Storage
Type complex = record
re:real;
im:real;
end;
Var x,y,z:complex;

struct complex{
double re;
double im;
};
struct complex x,y,z;
Storage is allocated


when the template is applied in a variable
declaration
Not when the template is described.
chapter 4
24
Operations on Records

We have to access data in Record by
denote record with its field-name.
<record-variable>.<record-field-name>
Example
z.Re := x.re + y.re;
z.Im := x.im + y.im;
L
:= z.re*z.re + z.im*z.im;
chapter 4
25
Comparison of Array & Record


A[i] can change at run time, depending
on the value of i, but the record field
fixed <var>.<field> at compile time
A Record’s Fileds have different types,
but all array elements have the same
arrays
Component types
homogeneous
Expressions evaluated
Component selectors
Atchapter
run4 time
records
heterogeneous
Name known
At compile time
26
UNIONS & VARIANT RECORD


A union is special case of a variant
record, with an empty common part
variant records have a part common to
all record of that type, and a variant
part, specific to some subset of the
record.
chapter 4
27
Type kind = (leaf, unary, binary);
mode = record
c1: T1;
c2: T2;
case k:kind of
leaf: ();
unary: (child:T3);
binary: (lchild,rchild:T4);
end;
c1
c2
k
c1
c2
k
c1
c2
k
child
chapter 4
lchild
rchild
28
SETS


Set can be implemented efficiently using
bits in the underlying machine.
Operations of sets turn into bit operations
Example
Var A: set of [1..3]
Can denote one of following sets:
[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]
The set [1,3] can be encoded by the bit vector 101
chapter 4
29
Operations on Sets

Bit vectors allow the following operations
on set




(+) Union
(-) Difference
(*) Intersection
(/) Symmetric difference (A-B)U(B-A)
chapter 4
30
Pointers


Can provides indirect to elements of a
known type.
Used as:




Efficiency: to move or copy
Dynamic data: grow and shrink during
execution
Fixed size, a single machine
independent of what they point to
chapter 4
31
Pointer Types

A pointer type has form
^<type-name>
Example
Var X,Y: Integer;
P :^Integer;
begin
X := 17;
P := @X;
Y := P^;
end;
// X &Y are Integer variables
// P points to an Integer
// assign a value to X
// assign the address of X to P
// dereference P; assign result to Y
chapter 4
32
Operations on Pointers





Dynamic allocation on the heap
Dereferencing
Assignment
Equality testing
Deallocation
chapter 4
33
Operations on Pointers(cont’d)

Storage for the new structure is taken
from a special area of memory called a
heap
new(p) {where p is of type pointer to T,}
P :^T {p pointer to T}
P^
{the object pointed to by p}

Storage exists until it is explicitly
deallocated by executing
Dispose(p)
chapter 4
34
Serve as links
Static Layout principle.
The size and layout of the storage for each type are known
statically, before a program runs

Records and pointers use for data
structure (grow and shrink)
TYPE link = ^cell;
cell = record
info : integer;
next : link;
end;
chapter 4
35
Memory Leaks


Storage that is allocated but is
inaccessible is called garbage.
Programs that create garbage are said
to have memory leaks
p
p
q
q
chapter 4
36
Dangling Pointers

Dangling Pointers is a pointer to
storage that is being used for another
purpose; the storage has been
deallocated.
Dispose(p)
p
p
q
q
chapter 4
37
Dangling Pointers & Memory Leaks


Dangling Pointers are unsafe because
the result of dereferencing a dangling
pointer is unpredictable.
Memory leaks can degrad the
performance of a running program
chapter 4
38
Pascal

Pascal prevents dangling pointers
except through dispose by using the
following approach
Confine pointers to the heap. Pointers cannot be used to
access storage for variables
The operations on pointers in Pascal stress safety over flexibility.
C stresses flexibility, trusting the programmer to use it safety.
chapter 4
39
Assignment Pointer
e := f
e
B
a
c
12 11
f
B
a
b
b
16 23
e
B
a
b
b
16 23
f
B
a
b
b
16 23
e^:= f^
chapter 4
40
TYPE & ERROR CHECKING

Type of an expression can be inferred
at compile time.
Type system for a language is a set of rules for associating
a type with expressions in the language.
Example : type system for Fortran
• Variable name ‘I’..’N’ have type int, othername have type real
• A number has type real if it contains a decimal point
• operands in expression have the same type.
chapter 4
41
Basic rule of type checking

Arithmetic Operators
If E and F have type int, then
E+F also has type int

Overloading
If E has type int and F has type int, then
E+F also has type int
If E has type real and F has type real, then
E+F also has type real
chapter 4
42
Basic rule of type checking

Type Conversion
Int * real
2*3.142 --> 2.0*3.142 real

Polymorphism
Polymorphic types allow such a data structure
to be defined once and then applied later to
any desired type such as stacks of integers,
stacks of grammar symbols, and so on.
chapter 4
43
CLASS TEMPLATEs
Template <class List_entry>
Class List{
Public:
List();
int size() const;
Private:
int count;
List_entry entry[max_list]
}
chapter 4
44
Type Names & Type Equivalence

What does it mean for two types to be
equal?
Example 4.9 Look at the following two types.
var x,y : array [0..9] of integer;
var z
: array [0..9] of integer;
In Pascal, x and y have the same type, because they are
declared together, but z does not.
In the corresponding C fragments, x,y, and z all have the
same type
chapter 4
45
Structural Equivalence

Two type expressions are structurally
equivalent if an only if they are equivalent
under the following three rules:
SE1. A type name is structurally equivalent to itself
SE2. Two types are structurally equivalent if they are
formed by applying the same type constructore to
structurally equivalent types.
SE3. After a type declaration, type n = T, the type name
n is structurally equivalent to T
chapter 4
46
Forms of Name Equivalence


Pure name equivalence. A type name is
equivalent to itself, but no constructed type
is equal to any other constructed types.
Transitive name equivalence. A type name is
equivalent to itself and can be declared
equivalent to other type names
Type S = integer; T = S; U = integer;

Type expression equivalence. A type name is
equivalent only to itself.
chapter 4
47
Type Equivalence in
Pascal/Modula-2

Type equivalence was left amgiguous
in Pascal. Its successor, Modula-2,
avoided ambiguity by defining two
types to be compatible if
C1. They are the same name, or
C2. They are s and t, where s = t is a type declaration, or
C3. One is a subrange of the other, or
C4. Both are subranges of the same basic type.
chapter 4
48
Type Equivalence in C/C++


C uses structural equivalence for all
types except records or structures in C
This constraint saves C from having to
deal with circular types.
chapter 4
49
Circular Types


can arise when structures and pointers
are used to implement linked data
structures
Linked data structures give rise to
recursive or circular types
chapter 4
50
Circular Types
Type link=^cell;
Type cell = record
info : integer;
next : link;
end;
Expression :
P :
P^:
P^.next :
P^.next^:
chapter 4
Type
link
cell
link
cell
51