Types

Question 1

What is the purpose of types in a language?

Answer 1

• Provide implicit context for operations
  
  • Meaning of + depends on type
• Limits the set of operations that can be performed on a semaantically valid program

Question 2

What is a type system?

Answer 2

• A mechanism to define types
• A way to associate types with objects in a language
• Sets rules for
  
  • Type equivalence
  • Type compatibility
  • Type inference

Question 3

What is type checking?

Answer 3

Process of ensuring that a program satisfies languages type compatibility rules.

Question 4

What is strongly typed?

Answer 4

Language implementation prohibits application of operation to object not intended to support operation.

Question 5

What is statically typed?

Answer 5

Strongly typed + type checking (mostly) performed before run-time.

Question 6

What is dynamically typed?

Answer 6

Type checking performed at run-time.

Question 7

Describe denotional types.

Answer 7

• 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.

Question 8

Describe constructive types.

Answer 8

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

Question 9

Describe abstraction-based type?

Answer 9

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.

Question 10

What is orthogonality?

Answer 10

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)

Question 11

What are primitive types?

Answer 11

Built-in types typically corresponding to those supported by hardware.

Question 12

What are discrete types?

Answer 12

Countable

• integer
• boolean
• char
• enumeration
• subrange

Question 13

What are scalar types?

Answer 13

One-dimensional

• discrete
• real

Question 14

Describe the contents of a record (structures).

Answer 14

Each record is a collection of fields, each of which belongs to a potentially simpler type.

Question 15

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?

Answer 15

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.

Question 16

Name a language that allows records to be packed.

Answer 16

Pascal

Question 17

What are some pros/cons to record packing?

Answer 17

• Optimized for space instead of speed
• Access requires multiple instructions

Question 18

What are the most common and important composite data types?

Answer 18

Arrays

Question 19

What is slicing?

Answer 19

A slice or section is a rectangular portion of an array.

Question 20

What are two lifetime options for arrays?

Answer 20

Global

Local (extend of subroutine)

Question 21

What are two bound options for arrays?

Answer 21

Static

Dynamic

Question 22

What are three allocation mechanisms for arrays?

Answer 22

Static

Stack

Heap

Question 23

When can a compiler allocate space for an array in static global memory?

Answer 23

If the array has a global lifetime and a static shape.

Question 24

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.

Answer 24

Yes. As long as the exists throughout the execution of a subroutine.

Question 25

Can an array be allocated on a stack with a local lifetime and a shape bound at elaboration time? Explain.

Answer 25

Yes. But only if shape is known when declared.

Question 26

Give an example of an array with an arbitrary lifetime, and a shape bound at elaboration time.

Answer 26

X = new int[size]; Size of array does not change after allocation.

Question 27

Arrays with arbitrary lifetimes and dynamic shapes implies that the shape can change during runtime. How can this occur?

Answer 27

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.

Question 28

What are two memory layouts for arrays?

Answer 28

* Contiguous elements * Row-pointer layouts

Question 29

What are two subcategories for contiguous elements?

Answer 29

Column Major Row Major

Question 30

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?

Answer 30

Cache misses.

Question 31

What are Row pointers?

Answer 31

They are technically array of arrays.

Question 32

What are some advantages of row pointers?

Answer 32

* 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

Question 33

What are some disadvantages of row pointers?

Answer 33

* Requires extra space for the pointers * Possible performance penalty for scientific code

Question 34

(T/F) Strings are arrays of characters.

Answer 34

True

Question 35

(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.

Answer 35

False. Strings are one-dimensional.

Question 36

When implementing sets, what is the most common implementation?

Answer 36

Using bitsets.

Question 37

In a bitset a vector is used. What determines the length of the vector?

Answer 37

The vector length will equal the number of distinct values in the base type.

Question 38

(T/F) Bitsets work perfectly with large base types.

Answer 38

False. A bit vector for ints would require 500M on a 32 bit machine

Question 39

What are the two models of variables?

Answer 39

Value model Reference model

Question 40

In value model variable, what is the difference between l-values and r-values?

Answer 40

* l-values are expressions that denote locations * r-values are expressions that denote values

Question 41

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?

Answer 41

No. reference model only supports l-value. This is supported by ML.

Question 42

What are some operations that can be done with pointers?

Answer 42

* 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)

Question 43

In C, what special operation can be done on pointers that is not supported in other languages?

Answer 43

Pointer arithmetic.

Question 44

What are two mechanisms that catch dangling pointers?

Answer 44

Tombstones Locks and Keys

Question 45

What does a list consist of?

Answer 45

* Head element * Reference to rest of list

Question 46

What operations can be performed on a list?

Answer 46

* Get head * Get tail * Add element to front of list

Question 47

What programming language is built as a list?

Answer 47

LISP is a list.

Question 48

What are the two type equivalence concepts?

Answer 48

* Structural equivalence * Name equivalence * With alias types * Strict * Loose

Question 49

(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.

Answer 49

True

Question 50

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?

Answer 50

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.

Question 51

What are the two types of alias types?

Answer 51

* Loose name equivalence TYPE elemType = INTEGER; * Strict name equivalence TYPE person is new string;

Question 52

What is another word for type conversions?

Answer 52

Casts

Question 53

What do type conversions allow the programmer to do?

Answer 53

It allows them to use an object of one type in a context where another type is expected.

Question 54

What are the 3 cases for type conversions?

Answer 54

* 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.

Question 55

Give an example of a conversion for types being structurally equivalent but with name equivalency.

Answer 55

Question 56

Give an example of a type conversion for types that have different sets of values, but the intersection is represented in the same way.

Answer 56

Question 57

Give an example of type conversion for types that have different low-level representations, but that have some sensible correspondence between them.

Answer 57

Question 58

What is a non-converting type cast?

Answer 58

It is a cast that does not alter the underlying bits. It just merely reinterprets them. Example: r = \*((float \*) &n);

Question 59

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?

Answer 59

The type to the left of the assignment has to support a larger range of values. Example: int x = ... real y = y + x;

Question 60

(T/F) In an OO language, an object reference of one type is allowed whenever a reference of any supertype is expected.

Answer 60

True. This works since each instance of a class includes an instance of each superclass.

Question 61

Type Inference: In all strongly typed languages, the compiler must _______ types of expressions.

Answer 61

infer

Question 62

What type checking is used to determine the types of names without explicitly giving the types?

Answer 62

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.