Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Programming Languages Principles > Types > Flashcards

Types Flashcards

1
Q

What is the purpose of types in a language?

A
  • Provide implicit context for operations
    • Meaning of + depends on type
  • Limits the set of operations that can be performed on a semaantically valid program
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is a type system?

A
  • A mechanism to define types
  • A way to associate types with objects in a language
  • Sets rules for
    • Type equivalence
    • Type compatibility
    • Type inference
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is type checking?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is strongly typed?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is statically typed?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is dynamically typed?

A

Type checking performed at run-time.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Describe denotional types.

A
  • 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.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Describe constructive types.

A

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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Describe abstraction-based type?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is orthogonality?

A

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)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What are primitive types?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What are discrete types?

A

Countable

  • integer
  • boolean
  • char
  • enumeration
  • subrange
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What are scalar types?

A

One-dimensional

  • discrete
  • real
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Describe the contents of a record (structures).

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

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

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Name a language that allows records to be packed.

A

Pascal

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What are some pros/cons to record packing?

A
  • Optimized for space instead of speed
  • Access requires multiple instructions
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What are the most common and important composite data types?

A

Arrays

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What is slicing?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

What are two lifetime options for arrays?

A

Global

Local (extend of subroutine)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

What are two bound options for arrays?

A

Static

Dynamic

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

What are three allocation mechanisms for arrays?

A

Static

Stack

Heap

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

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.

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

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

Explain.

A

Yes. But only if shape is known when declared.

26
Q

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

A

X = new int[size];

Size of array does not change after allocation.

27
Q

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

A

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.

28
Q

What are two memory layouts for arrays?

A
  • Contiguous elements
  • Row-pointer layouts
29
Q

What are two subcategories for contiguous elements?

A

Column Major

Row Major

30
Q

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?

A

Cache misses.

31
Q

What are Row pointers?

A

They are technically array of arrays.

32
Q

What are some advantages of row pointers?

A
  • 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
33
Q

What are some disadvantages of row pointers?

A
  • Requires extra space for the pointers
  • Possible performance penalty for scientific code
34
Q

(T/F) Strings are arrays of characters.

A

True

35
Q

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

A

False. Strings are one-dimensional.

36
Q

When implementing sets, what is the most common implementation?

A

Using bitsets.

37
Q

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

A

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

38
Q

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

A

False.

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

39
Q

What are the two models of variables?

A

Value model

Reference model

40
Q

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

A
  • l-values are expressions that denote locations
  • r-values are expressions that denote values
41
Q

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?

A

No. reference model only supports l-value.

This is supported by ML.

42
Q

What are some operations that can be done with pointers?

A
  • 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)
43
Q

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

A

Pointer arithmetic.

44
Q

What are two mechanisms that catch dangling pointers?

A

Tombstones

Locks and Keys

45
Q

What does a list consist of?

A
  • Head element
  • Reference to rest of list
46
Q

What operations can be performed on a list?

A
  • Get head
  • Get tail
  • Add element to front of list
47
Q

What programming language is built as a list?

A

LISP is a list.

48
Q

What are the two type equivalence concepts?

A
  • Structural equivalence
  • Name equivalence
    • With alias types
      • Strict
      • Loose
49
Q

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

A

True

50
Q

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?

A

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.

51
Q

What are the two types of alias types?

A
  • Loose name equivalence

TYPE elemType = INTEGER;

  • Strict name equivalence

TYPE person is new string;

52
Q

What is another word for type conversions?

A

Casts

53
Q

What do type conversions allow the programmer to do?

A

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

54
Q

What are the 3 cases for type conversions?

A
  • 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.
55
Q

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

A
56
Q

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

A
57
Q

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

A
58
Q

What is a non-converting type cast?

A

It is a cast that does not alter the underlying bits. It just merely reinterprets them.

Example: r = *((float *) &n);

59
Q

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?

A

The type to the left of the assignment has to support a larger range of values.

Example:

int x = …

real y = y + x;

60
Q

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

A

True.

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

61
Q

Type Inference:

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

A

infer

62
Q

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

A

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.

Programming Languages Principles (14 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions