Transcript array type

Chapter 9
Imperative and
object-oriented languages
1
Source language data
representation and handling
• In the source language, a data item has a type,
which may be a basic, built-in type of the
language, or a constructed type, built using one
of the type constructions in the language.
• The target language data types are usually
limited to single bytes, integers of various
sizes, address representations, and floating
point umbers of several sizes.
2
Basic types
• The usual basic types in a source language
are characters, integers of several sizes, and
floating point numbers of several sizes.
• The source language operations on these
typically are arithmetic operations, assignment
and comparison
– The arithmetic operations: addition, subtraction,
multiplication, division, and remainder.
– All these can be mapped directly to the target
language data types and operations.
3
Basic types
• Some source languages also have a void
type, corresponding to no value at all.
• A target language representation for a void
type is not needed.
4
Enumeration types
• An enumeration type defines a set of names to be
the values of the new data type.
• The run-time representation is an integer, with
values usually ranging from 0 to the number of
enumeration values minus 1.
– example:
months ={Jan, Feb, … , Dec}
Jan – 0
Feb – 1
…
Dec – 11 (12-1)
5
Enumeration types
• An enumeration type which is available in many
languages, including some that do not have
explicit enumeration types, is the Boolean type,
with false and true as enumeration literals.
– example:
Boolean type = {false, true}
0
1
6
Pointer type
• Most imperative and object-oriented
languages support a pointer type of some
kind.
• Pointer represent the addresses of source
language data structures.
• Its target type is an unsigned integer of a size
large enough to represent an address.
7
Pointer type
• Operation: copying, assignment, comparison, etc.
• The one operation that is particular to pointers is
dereferencing, which consists of obtaining the
value of the data structure that the pointer refers to.
• If the value is small to fit in a register: a single
machine instruction.
If the value is large: a pointer to a record or array.
8
Pointer type
• For example:
the assignment
q= *p;
in which q is the name of a record variable of
type T and p is a pointer to a record of the
same type, may be translated to a call of a
library routine byte_copy()
byte_copy (&q, p, sizeof(T));
9
Record types
• A record, also called a structure, is a data
item in which a fixed number of members of
possibly different types are grouped together.
• In the target language, these members are
represented consecutively in a memory area
that is large enough to contain all members.
10
Record types
• For example:
struct example {
int member1;
double member2;
};
is represented as follows:
member 1
member 2
11
Record types
• The Scalable Processor ARChitecture
(SPARC) processor requires an int (a 4-byte
quantity) to have an address that is a multiple
of 4 (is 4-byte aligned), and a double (an 8byte quantity) to be 8-byte aligned.
is represented as follows:
member 1
gap
member 2
12
Union type
• A union type is a data type of which the values are of one of a
set of types.
• For example: a variable a of type
union {
int m1;
float m2;
}a,b;
holds either int m1 or float m2
for example
a.m1 b.m2
the program should be aware of which one is present
13
Array type
• An array type describes data structures which consist of
series of items (also called elements) of the same type.
• An array can have one dimension (a vector), two dimensions
(a matrix), or more.
• For example:
A: array [1..3] of integer;
A[1] A[2] A[3]
B: array [1..2, 1..3] of integer
column
row
1.1
1.2
1.3
2.1
2.2
2.3
14
Array type
• The run-time representation of the array
consists of a consecutive sequence of the
representation of the elements; the address of
the first element is called the base address of
the array.
• All languages that support arrays also support
element selection, which is usually called
indexing.
15
Array type
• Assume an n-dimensional array A with base
address base (A), where dimension k has lower
bound LBk and upper bound UBk.
• The number of elements along dimension k is then
LENk= UBk-LBk+1
dimension 1 (row) lower bound LB1 = 1
upper bound UB1 = 2
dimension 2 (column) LB1 = 1
UB2 = 3
number of elements in dimension1.LEN1 = 2
number of elements in dimension2.LEN2 = 3
16
Array type
• How to compute the location (address) of A[1, 3],
i1=1, i2=3.
base (A) + [(i1-LB1)*LEN2 + (i2-LB2)] * element
size
= base (A) + [(1-1) * 3 + (3-1)] * element size
= base (A) +2 * element size
17
Array type
3 dimensions:
base (A) + [(i1-LB1) * LEN2 * LEN3 +(i2-LB2) *
LEN3 + (i3-LB3)] * element size
Example: A: array [1...2, 1…3, 1…4] of integer
assume base (A) = 0000, an integer takes 4
bytes
A[2,2,3] = base (A) + [(2-1) * 3 * 4 + (2-1) * 4 +
(3-1)] * 4
= 0 + 72 =72
18
Array type
K dimensions:
base (A) + [(i1-LB1) * LEN2 * LEN3 * …LENk +
(i2-LB2) *
LEN3 * …LENk +
…
(ik-1 – LBk-1)
* LENk +
(ik – LBk) ] *element size
19
Set type
• If it is a small sub-range of integer, it can be implemented
as bitset.
e.g. The set of integers ranging 0-31
can be represented in a 32-bit word.
01000……….0
2nd element in the set, other elements not.
• Operations:
– Set union is implemented with a bitwise OR
– Set intersection is implemented with a bitwise AND,
– Symmetric set difference is implemented with a bitwise
EXCLUSIVE OR,
– Set difference is implemented with a bitwise NOT.
20
Object type
• An object is a record with built-in methods,
with some additional features. Its type is a
class.
• Operations:
– field selection: o1.i1, o1.f1, o2.i1, o2.f2
– Copying: set o1 to o2
– Method invocation: o1.m1()
21
Object type
• Object also have constructors and destructors, which are
methods that are to be invoked on object creation and object
removal, respectively.
class A {
int a1;
int a2;
method A();
method m1();
method m2();
};
Method of object constructor, destructor.
o1 = A ();
destruct-A(o1);
22
Object type
Target code of o1 is:
a1
a2
Method table for A:
A_A
m1_A
m2_A
23
Object type
Assume: m2_A() has one integer parameter and
returns no value and where Class_A is the C
type name for class A
Target code for m2_A:
void m2_A (class_A *this, int i) {
Body of m2_A,
}
24
Inheritance
• Inheritance allows the programmer to base a class
B on a class A, so that B inherits the methods and
fields of A, in additional to its own fields and
methods.
• This feature is also known as type extension: class
B extends class A with zero or more fields and
methods.
• Class A is the parent class of class B, and class B
is a subclass of class A.
25
Inheritance
class B extends class A {
int b1;
method B;
method m3_B;
}
o2 = B()
o2 looks like:
a1
a2
b1
26
Method overriding
• When a class B extends a class A, it may
redefine one or more of A’s methods; this
feature is called method overriding.
– Method declaration: method m1();
– Method definition: method m1() {a=1;}
– Method re-definition: in subclass, method m1()
{a=2;}
– Abstract class: a class in which at least one
method is declared, but not defined. The actual
methods must then be defined in classes that
extend the abstract class.
27
Method overriding
class A {
…
method m1(); {…}
method m2(); {…}
};
class B extends A {
…
method m2() {…}
method m3() {…}
};
28
Method overriding
Method table for A:
m1_A_A
m2_A_A
Method table for B:
m1_A_A
m2_A_B
m3_B_B
a is an object of A
b is an object of B
a.m2() invokes m2_A_A
b.m2() invokes m2_A_B
29