Introduction to programming. Data types

1. Introduction to Programming I Fall 2019

Types (Data types)
Lecture 2 – Alexey Kanatov
1

2. Agenda

• What is type and typification, type equivalence, entity
• Evolution of type system
• Type conversions
• CPU memory and type
• Array, structure, range and enumeration types
• Pointer type and memory management
• User Types
• Static and dynamic type checking
High-level and quick intro!
• Compilation unit
• Summary
2

3. What types were in fact presented at Lecture 1?

• Von Neumann architecture: CPU + RAM + I/O devices
• RAM may contain program code and data
• RAM contains set of cells, each cell has an address, the cell is called …
Main memory - RAM
Program code and data together
• Bit, byte and word. These are in fact 3 data types!
• What operations can be done with memory? Is memory a type?
• What operations can be performed on bit, byte and word?
3

4. Why do we need types?

• As soon as we have data it belongs to some class of data – this data
class is the type -> data types just exist!
• Types can be checked by the compiler or runtime system to prevent
or detect errors in programs.
• Types are used to model the real world by programmers.
• Temperature -> how to deal with it?
• Weight, color, sex, age, passport #, …. Student at the university
4

5. Type – what is it? Abstract concept. Data type!

Type has a name!
Definition1. What is a data type – it can be described by combining two notions:
• Values: a type is, in essence, a set of values.
• Operations: not every operation can be applied on every data type.
Definition 2.
A. Region of computer memory (size)
B. Set of operations (code)
C. Set of constraints on the content of the memory region (invariant) (predicate)
type T
data
d1: T1
d2: T2
operation
op1 ….
op2 …
end type T
When type T1 is equivalent to type T2?
When T1.A = T2.A and T1.B = T2.B and T1.C = T2.C then T1 and T2 are the same types!
Let’s consider Integer and Cardinal: same size, set of operations?, set of constraints?
5

6. Data type -> entity

Data type -> entity
• Low-level => word, that is how Asm works, key thing is address
• High-level => entity, it has a name and all work with an entity is being done using a name
not an address. (Name => Identifier)
• Approaches:
• Explicit
• a: A (Pascal style)
• A a; (C style)
• Implicit
• I = 100, all identifiers starting with I, J, K are of type Integer (Fortran, PL-I)
• Inference (deduction) with Java and Eiffel examples
• var b = 1; // Type of expression becomes the type of the left part
• abs (x: INTEGER): INTEGER then
if x < 0 then -x else x end
end
6

7. Evolution of types in programming languages

1. Fixed set of types (Asm, Fortran IV, PL-I, …)
2. Standard types (compiler knows them by name) + user defined types
a) C, C#, Java, …. Very long list
b) Set of operations for standard types is to learnt by heart
c) Can we extend set of operations for standard types? How?
3. Uniform type system (every type is described in uniform way)
a) Eiffel, ?
Speed?
Usability?
7

8. Type conversions

Distinguish
• Interpret one region of memory as entity of another type
• Do some calculation to fill another region of memory with new value
Approaches
Implicit (compiler may support some, built-in algorithms)
Integer -> Real i = r
Real -> Integer r = i
String -> Integer i = “1234”
Integer -> String s = 1234
a = (Type) Expression; // C-style cast
Explicit
Integer => real
T1 -> T2 via conversion function
Integer.toReal ()
Real.toInteger ()
x := y -- If there is a conversion function from y type into x type it will be called
8

9. Types – approach for construction

• Bit -> 1 bit Integer, Boolean
• Byte -> 8 bit Integer, 8 but unsigned Integer, Boolean, Character
• 0 – False, 1 – True, 5 -?
• Word -> 16/32 bit Integer, pointer (address), UNICODE Character
• Double word -> Real, Extended Real
• String – tricky
Bit
Byte
Word
9

10. Important built-in types - Array

• Array is so close to math. 1 dimensional array is vector. 2 or greater dimensional array is a matrix. To
work with array we need an index to deal with its elements
• Fixed number of elements (static array), each element has the same size (data type!), address of the
1st element is the address of an array
• Why square brackets???? Math uses () – FORTARN used them too!
• intArray: ARRAY [1..5] of INTEGER {Pascal-style array}
• int intArray [5] // C-style array
• How to calculate address of an element?
• Multi-dimensional arrays a[1,4,6] – how many dimension we have here? How many elements are in
the array?
• How static arrays are stored in memory?
• Dynamic arrays a bit later be patient!
• Is String an Array?
10

11. Important built-in types – struct (Record)

• Named group of data entities of different size (type). Each element of the group is
called member(field). Each member has a name and type!
• C-style
struct tag_name {
type1 member1;
type2 member2;
/* declare as many members as desired, but the entire
structure size must be known to the compiler. */
};
• How to calculate address of the member?
• How structures are stored in memory?
11

12. Important built-in types – range and enumeration

• Range - [1..100] – kind of constraint to the base type
• Integer will be a base here and [1..100] will be the constraint
• Allows to do more checks at compile time and at run-time (less bugs)
• Enum
• (Red, Green, Blue) – all possible values are explicitly named
• Raises design abstraction to higher level (less bugs)
• Typically Integer is used to model enumerations
12

13. Value and pointer to the value

• So, far we have atomic data entities (bit, byte, word, etc), we have arrays
and structures. All of them are static. All of them are well identified at
compile time.
• One more entity of this kind is pointer. Address in memory. Size of pointer
is typically 1 word.
Pointer
Other memory region
• No pointers (references) all the program in memory layout is known.
• Pointers (references) in place. Memory management is required.
13

14. Memory management

2 key operations
• malloc (NEW) – allocate (reserve) fixed size chuck of memory
• free (DISPOSE) – make a chunk free again
If there is no ‘free’ in the programming language we need to clean up
what is no longer required – garbage collector (GC)
Static memory
(offsets)
Heap
Stack
(push-pop) (pointers)
Value data goes to static memory or stack
Data referenced by pointers goes to heap
Dynamic arrays and strings – easy !
14

15. User types

• Unlimited number of different types!
• They all are based on bit, byte and word
• Aggregation of
Basic values (bit, byte, word, …)
Pointers
Structures
Arrays
Array of Array of Structure
List
Queue
Hash table
Remember – region of memory occupied, set of operations, set of constraints
15

16. Static and dynamic type checking

• JavaScript, Python, … dynamic type
checking.
• “easy” to code
• Harder to debug
• Slower code execution speed
Source code
Static type
checking
Check
• Java, C#, C, C++,Eiffel , … static type
checking
“harder” to code and compiler
Less runtime errors
No extra checks at runtime
More abilities to optimize the output
code
Compiler
Object code
Linker
Run &
Check!
Computer
Executable
code
16

17. Compilation unit – to proceed at labs

• It is the programming language construction which can be stored 1 object file (with native
or byte code)
• Java example
public class HelloWorldApp {
public static void main(String[] args) {
System.out.println("Hello World!"); // Prints the string to the console.
}
}
• Eiffel example
class HELLOWORLDAPP
create main
feature
main do
print ("Hello World!%N") -- Prints the string to the console.
end
end
17

18. Summary

• Data type is named memory region (size) with set of operations and constraints
• 2 types are the when they have the same size, set of operations and constraints
• Types allow to minimize the number of errors and provide additional
opportunities for optimizations
• All types are based on bit, byte, word computer types
• There are basic aggregation concepts – array and structure
• Pointers allow to model dynamic data structures
• User types allow to model real life entities raising the level of abstraction
• Static type checking is in general better than dynamic one
• Now you can start trying both Java and Eiffel at labs
18