Types Flashcards
What is the purpose of types in a language?
- Provide implicit context for operations
- Meaning of + depends on type
- Limits the set of operations that can be performed on a semaantically valid program
What is a type system?
- A mechanism to define types
- A way to associate types with objects in a language
- Sets rules for
- Type equivalence
- Type compatibility
- Type inference
What is type checking?
Process of ensuring that a program satisfies languages type compatibility rules.
What is strongly typed?
Language implementation prohibits application of operation to object not intended to support operation.
What is statically typed?
Strongly typed + type checking (mostly) performed before run-time.
What is dynamically typed?
Type checking performed at run-time.
Describe denotional types.
- Focuses on the value of the type.
- A type is a set of values called a domain.
- A value has a type if it belongs to the set
- An object has a type if its value is guaranteed to be in the set.
Describe constructive types.
Focuses on the construction.
A type is either
- A primitive (built-in) type
- int,
- char,
- boolean,
- etc.
- Or a composite formed by applying a type constructor to simpler types
Describe abstraction-based type?
Focuses on the operations that can be performed on the type.
A type is an interface consisting of a set of operations with well-defined semantics.
What is orthogonality?
There are no restrictions on the way features can be combined in a programming language.
For example
- Pascal is more orthogonal than Fortran, (because it allows arrays of anything, for instance)
- Pascal is not completely orthogonal because it does not permit variant records as arbitrary fields of other records (for instance)
What are primitive types?
Built-in types typically corresponding to those supported by hardware.
What are discrete types?
Countable
- integer
- boolean
- char
- enumeration
- subrange
What are scalar types?
One-dimensional
- discrete
- real
Describe the contents of a record (structures).
Each record is a collection of fields, each of which belongs to a potentially simpler type.
Records are usually laid out contiguously in memory. However, there may be possible holes for alignment reasons. Smart compilers may re-arrange fields to minimize holes. Why could this be an issue?
A programmer may want to arrange fields to keep certain values in the same cache line. Elimminating gaps may cause multiple memory reads for certain full values.
Name a language that allows records to be packed.
Pascal
What are some pros/cons to record packing?
- Optimized for space instead of speed
- Access requires multiple instructions
What are the most common and important composite data types?
Arrays
What is slicing?
A slice or section is a rectangular portion of an array.
What are two lifetime options for arrays?
Global
Local (extend of subroutine)
What are two bound options for arrays?
Static
Dynamic
What are three allocation mechanisms for arrays?
Static
Stack
Heap
When can a compiler allocate space for an array in static global memory?
If the array has a global lifetime and a static shape.
If an array has a local lifetime and a static shape, can its space be allocated in the subroutine’s stack frame at run time?
Explain.
Yes. As long as the exists throughout the execution of a subroutine.
Can an array be allocated on a stack with a local lifetime and a shape bound at elaboration time?
Explain.
Yes. But only if shape is known when declared.
Give an example of an array with an arbitrary lifetime, and a shape bound at elaboration time.
X = new int[size];
Size of array does not change after allocation.
Arrays with arbitrary lifetimes and dynamic shapes implies that the shape can change during runtime. How can this occur?
When the size is increased, a new array may be allocated and contents of the old array are copied over. Then the old array is deallocated.
What are two memory layouts for arrays?
- Contiguous elements
- Row-pointer layouts
What are two subcategories for contiguous elements?
Column Major
Row Major
Row major vs. column major is important for programs that iterate over all elements in multidimensional array.
What can happen if a row major memory layout is iterated in a nested loops in a column major fashion?
Cache misses.
What are Row pointers?
They are technically array of arrays.
What are some advantages of row pointers?
- Allows rows to be put anywhere - nice for big arrays on machines with segmentation problems
- Avoids multiplication (figuring addresses)
- Nice for matrices whose rows are of different lengths
- e.g. an array of strings
- Allows a program to construct an array from existing rows without copying
- Fits better with OO paradigm
What are some disadvantages of row pointers?
- Requires extra space for the pointers
- Possible performance penalty for scientific code
(T/F) Strings are arrays of characters.
True
(T/F) It is easier to provide for strings than for arrays in general because strings are two-dimensional and don’t contain references to anything else.
False. Strings are one-dimensional.
When implementing sets, what is the most common implementation?
Using bitsets.
In a bitset a vector is used. What determines the length of the vector?
The vector length will equal the number of distinct values in the base type.
(T/F) Bitsets work perfectly with large base types.
False.
A bit vector for ints would require 500M on a 32 bit machine
What are the two models of variables?
Value model
Reference model
In value model variable, what is the difference between l-values and r-values?
- l-values are expressions that denote locations
- r-values are expressions that denote values
In a reference model, a variable is a named reference to a value. Can this variable be an r-value type?
Also, what language supports this model?
No. reference model only supports l-value.
This is supported by ML.
What are some operations that can be done with pointers?
- Assignment
- Sets pointer’s value to refer to a valid object
- Dereference
- Get the value of the object referred to by the pointer
- Dereferencing can be explicit or implicit.
- In C it is explicit (use * operator)
In C, what special operation can be done on pointers that is not supported in other languages?
Pointer arithmetic.
What are two mechanisms that catch dangling pointers?
Tombstones
Locks and Keys
What does a list consist of?
- Head element
- Reference to rest of list
What operations can be performed on a list?
- Get head
- Get tail
- Add element to front of list
What programming language is built as a list?
LISP is a list.
What are the two type equivalence concepts?
- Structural equivalence
- Name equivalence
- With alias types
- Strict
- Loose
- With alias types
(T/F) In a language with structural equivalence, two types are equivalent if they consist of the same components put together in the same way.
True
Name equivalence is based on lexical occurance. Each definition introduces a new type. If two types have the same structural equivalence, are they always name equivalent?
If the names of the objects are different, no.
Example:
TYPE t1 = INTEGER;
TYPE t2 = INTEGER;
t1 x = 0;
t2 y = 0;
x = y; is not allowed - even thought the structure is the same, the types have different names.
What are the two types of alias types?
- Loose name equivalence
TYPE elemType = INTEGER;
- Strict name equivalence
TYPE person is new string;
What is another word for type conversions?
Casts
What do type conversions allow the programmer to do?
It allows them to use an object of one type in a context where another type is expected.
What are the 3 cases for type conversions?
- Types are structurally equivalent but language is name equivalent.
- Types have different sets of values, but intersection is represented in the same way.
- Types have different low-level representations, but there is some sensible correspondence between them.
Give an example of a conversion for types being structurally equivalent but with name equivalency.
Give an example of a type conversion for types that have different sets of values, but the intersection is represented in the same way.
Give an example of type conversion for types that have different low-level representations, but that have some sensible correspondence between them.
What is a non-converting type cast?
It is a cast that does not alter the underlying bits. It just merely reinterprets them.
Example: r = *((float *) &n);
Coercion is an example of an implicit type conversion; conversion that is done automatically. What is required of the type before an implicit type conversion is made?
The type to the left of the assignment has to support a larger range of values.
Example:
int x = …
real y = y + x;
(T/F) In an OO language, an object reference of one type is allowed whenever a reference of any supertype is expected.
True.
This works since each instance of a class includes an instance of each superclass.
Type Inference:
In all strongly typed languages, the compiler must _______ types of expressions.
infer
What type checking is used to determine the types of names without explicitly giving the types?
Hindley-Milner type checking.
Example:
a[i] + i;
The type can be inferred by looking at the index i and inferring that i is an integer. So a must be an array of ints since int i is being added to it.
