Chapter 6 - Data Types Flashcards
Definition of Data Type
defines a collection of data values and a set of pre-defined operations on those values
Definition of descriptor
the collection of the attributes of a variable
Definition of primitive data type
data types that are not defined in terms of other types
Why do primitive data types need very little non-hardware support for implementation?
These types are merely reflections of the hardware itself
What does it mean to be “a reflection of the hardware”?
that the entity is represented by some physical hardware mechanism
The 4 types of integer sizes in Java
byte
short = 2 bytes
int = 4 bytes
long = 8 bytes
(all integers in Java are signed)
Why are integers a reflection of the hardware?
The maximum value that can be represented, depends on the number of physical mechanisms used to define each bit
3 Different hardware implementations for signed integers
Dumb way = the most significant bit (the left-most one) determines the sign of the number. 1 implies a negative number and 0 implies a positive number
One’s Complement = The negation of a given number is obtained by flipping all the bits of that number.
Two’s Complement = the negation of a number is obtained by flipping all the bits and then adding one
Definition of Floating-point number data type
a primitive data type modeling real numbers (not just integers)
What is the size of a regular floating point number? How are the bits distributed?
4 bytes or 32 bits
sign bit = 1 bit
exponent = 8 bits
fraction or mantissa = 23 bits
Definition of double data type
A double precision floating point number
What is the size of a double data type? how are the bits distributed?
8 bytes or 64 bits
sign bit = 1 bit
exponent = 8 bits
fraction or mantissa = 53 bits
What is the floating point number exponent value and how is it represented?
The exponent refers to the exponent value of the floating point number in scientific notation
Simply add 127 to the value of the exponent and express that result in binary (doesn’t change for negative exponents).
ex) exponent = 5, result = 5 + 127 = 132, bin(132) = 1000010 (27 + 22 = 132)
exponent of 5 = 1000010
What is the floating point number fraction value and how is it represented?
Each digit after the decimal point represents a negative power of 2. Decimal values are approximated by combining these negative powers of 2
- 1 = 2**-1 = 0.5 (in decimal)
- 001 = 2**-2 = 0.25
- 0001 = 2**-3 = 0.125
The number in front of the decimal point is expressed normally in binary
How to express the sign of a floating point number
The sign bit represents the sign of the mantissa!
1 = negative 0 = positive
Definition of decimal data type
store a fixed number of decimal digits with the decimal point at a fixed position in the value
What common PLs have decimal data types?
COBOL
C#
F#
What is the main advantage of using decimal numbers instead of floating point numbers?
Decimal numbers are able to store decimal values exactly within a limited range
Floating point numbers can only approximate decimal values (remember that they approximate decimal values by using combinations of negative powers of 2, which makes it impossible to precisely store certain values)
What are the disadvantages of using decimal numbers instead of floating point numbers?
for decimal numbers:
- the range of values that can be expressed is limited
- their representation in memory is slightly wasteful
Definition of a nibble
4 bits or half of a byte
What does BCD stand for? What does it mean?
binary coded decimal
Meaning that each digit (0-9) and the sign(+/-), is represented by a nibble (4 bits)
How are the digits of a decimal number represented in binary?
The leftmost digit of the decimal number is the leftmost nibble in the binary representation
The digits 0-9 are represented by their normal 4-bit binary values (ex. 9 = 1001)
How is the sign of a decimal number represented in binary?
The sign is the rightmost nibble
+ sign represented by: 1100
- sign represented by: 1101
Definition of boolean data type
a data type with 2 allowed values true or false
What is the size of a normal boolean data type?
1 byte
It can theoretically be represented by 1 bit, however, this data type is typically stored in the smallest efficiently addressable cell of memory (typically 1 byte)
Which PL was first to include the boolean data type?
ALGOL 60
How is character data represented in memory?
with some numeric coding
ASCII vs Unicode
ASCII - an 8-bit numeric coding for characters. Can represent 128 characters (0-127)
Unicode - a 16-bit numeric coding for characters. The first 128 characters are identical to ASCII
Definition of character string type
a data type consisting of sequences of characters
Two most prominent representations of Strings
implemented as a (hardware) primitive type or as an array of single characters
2 main design issues pertaining to Strings
1) should it be implemented as some kind of character array or as a primitive type?
2) should they have static or dynamic length
Definition of Static length string
the length is set when the string is created.
The length can only be adjusted by creating a new string variable (or reference)
5 PLs that use static length strings
python java C++ Ruby C#
Definition of Limited dynamic length string
allows the string to be of varying length up to a declared and fixed maximum set by the variables definition
2 PLs with limited dynamic length strings
C
C++ (using C-style strings)
Definition of dynamic length strings
allows strings to be of varying length with NO maximum
3 PLs with dynamic length strings
Javascript
Perl
C++ STL
What 3 attributes need to be maintained in a static length string descriptor
name of the type
length of the type in characters
address of the first character
What 2 additional attributes need to be maintained for limited dynamic length strings? Are there alternatives to these attributes?
a run-time descriptor needs:
1) fixed max length
2) the current length
C doesn’t use a run-time descriptor but instead has a null character as the last character of every string denoting the end of it
3 storage schemes for dynamic length strings
- stored as a linked list
- stored as an array of pointers of individual characters
- store all strings in adjacent memory (dedicated area of memory to strings)
1 pro and 1 con for storing dynamic length strings as a linked list
Pro = highly growable
Con = complicated operations
1 pro and 1 con for storing dynamic length strings as an array of pointers to characters
pro = fast
con = bulky
1 pro and 1 con for storing dynamic length strings in adjacent memory
pro = string ops are faster
con = allocation is slower
Definition of ordinal type
a data type in which variables take one of a finite number of values (these possible values are typically represented by a set of positive integers)
int, char boolean, array subscripts are all ordinal types
What are the 2 user-defined ordinal types commonly supported by PLs
enumeration
subrange
Definition of enumeration type
a type that defines a collection of named constants called enumeration constants
3 Design issues for enumeration types
- can a given enumeration constant appear in more than one type?
- are the constants coerced to int?
- are other types coerced to the enumerated type
Definition of array data type
an aggregate of homogeneous data elements in which an individual element is identified by its position in the aggregate relative to the first element
7 design issues pertaining to arrays
1) what types are legal for subscripts
2) are subscripting expressions in element references range checked? (is it in the range of the array)
3) when are subscript ranges bound
4) when does allocation take place
5) what is the maximum number of subscripts
6) can array objects be initialized
7) are slices allowed
PLs that enforce subscript range checking
Ada
Java
C#
5 categories of arrays
Static Fixed stack dynamic Stack dynamic Fixed heap dynamic heap dynamic
What 2 characteristics define the 5 different categories of arrays
subscript binding
binding to storage
(remember binding is the association of some attribute to some variable)
Definition of a static array and its main advantage
the range of subscripts and storage bindings are static
Adv: execution efficiency (no allocation or deallocation)
Definition of a fixed stack dynamic array and its main advantage
the range of subscripts bound statically but storage bound at declaration elaboration time
Adv: space efficiency
Definition of a stack dynamic array and its main advantage
range and storage are dynamic (at declaration elaboration time), but then are fixed for the remaining lifetime of the variable
Adv: flexibility bc size need not be known until use
Definition of a fixed heap dynamic array and its main advantage
similar to stack dynamic arrays except for the subscript ranges and storage bindings are not done until the program makes use of them (not declaration elaboration time)
Adv: flexibility
Definition of a heap dynamic array and its main advantage
subscript ranges and storages bindings are dynamic and not fixed
Adv: flexibility, especially in that arrays can shrink and grow
Definition of array operation
an operation that operates on the array as a unit
Common PLs that support array operations
Ada
FORTRAN 95+
APL (Array Processing Language)
How are arrays represented in memory?
a sequence of adjacent memory cells
How to calculate the address of the kth element of an array?
address_first_element + (k - lower_bound_subscript) * sizeof_element
Calculate address of element in the ith column and jth row in 2D array
address_first_element + (j - row_lower_bound)sizeof_row + (i - column_lower_bound)sizeof_element
Definition of associative array
an unordered collection of data elements that are indexed by an equal number of values called keys
AKA a hash table
definition of a record type
a possibly heterogeneous aggregate of data elements which the individual elements are defined by names
3 design issues with records
how are they referenced
what operations are defined
are elliptical references allowed
Definition of elliptical reference
the ability to reference a data member or method without an explicit reference the record/class (don’t need to use the dot operator)
PLs allowing elliptical references
COBOL
Ada
Pascal
How are records organized in memory?
All record data stored as contiguous block in memory
individual fields are accessible through an offset value (this is because the different members/methods have different sizes)
definition of union type
a data type that allows for the storage of different data types in the same memory location
each of the data types is members and only one may have a value at a time
Discriminated vs Free unions
discriminated = includes a tag for type checking free = no type checking at all
Definition of pointer type
a type which value is a memory address to some location holding data
2 primary uses for pointers
indirect addressing
access to dynamic storage
5 design issues with pointers
what is the scope and lifetime of them
what is the lifetime of heap dynamic variables
are they restricted to point to a particular type
are pointers used one or both of the two primary uses
should a language support both pointer types and reference types?
What are the 2 pointer operations
assignment ( int* p = new int, p = &x)
dereference (x = *ptr, p -> age)
definition of a dangling pointer
a pointer that points to a heap dynamic variable that has been deallocated
definition of a memory leak
the existence of a heap dynamic variable that is no longer referenced by any program pointer
5 characteristics of pointers in C/C++
used for dynamic storage and addressing
explicit dereferencing
can do address arithmetic
void* = can point to any type but cannot be dereferenced
can use void* to pass functions as parameters to other functions
definition of reference type
similar in nature to a pointer except that it refers to an object or value in memory instead of an address
AKA no address arithmetic
