Midterm Review Flashcards
(205 cards)
1
Q
Defines a collection of data objects and a set of predefined operations on those objects
A
Data type
2
Q
The collection of the attributes of a variable
A
Descriptor
3
Q
Represents an instance of a user-defined (abstract data) type
A
Object
4
Q
Only design issue for all data types:
A
What operations are defined and how are they specified?
5
Q
Those not defined in terms of other data types
A
Primitive data types
6
Q
Uses of type system of a programming language
A
- Error detection
- Assistance it provides for program modularization
- Documentation
7
Q
Defines how a type is associated with each expression in the language and includes its rules for type equivalence and type compatibility.
A
Type system
8
Q
How do user-defined types improve readability and modifiability?
A
User-defined types provide improved readability through the use of meaningful names for types. They allow type checking of the variables of a special category of use, which would otherwise not be possible.
User-defined types also aid modifiability: A programmer can change the type of a category of variables in a program by changing a type definition statement only.
9
Q
Most common structured (nonscalar) data types in the imperative languages are:
A
Arrays and records
10
Q
What are the primitive data types?
A
- Integer
- Floating point
- Complex
- Decimal
- Boolean types
- Character types
11
Q
Two floating point types
A
Float and double
12
Q
The accuracy of the fractional part of a value, measured as the number of bits.
A
Precision
13
Q
A combination
of the range of fractions and, more important, the range of exponents.
A
Range
14
Q
The most common primitive data type
A
Integer
15
Q
Java four signed integer sizes:
A
byte, short, int, long
16
Q
A negative integer could be stored in….
A
sign-magnitude notation
17
Q
Two types of notation
A
Twos complement and ones complement
18
Q
The representation of a negative number is formed by taking the logical complement of the positive version of the number and adding one.
A
Twos complement notation
19
Q
The negative of an integer is stored as the logical complement of its absolute value.
A
Ones complement notation
20
Q
Floating-point values are represented as ___ and ____
A
fractions and exponents
21
Q
Floating-point values use a form that is borrowed from ______________
A
scientific notation
22
Q
Complex values are representes as____________
A
ordered pairs of floating-point values
23
Q
Advantage of decimal types
A
Accuracy. Being able to precisely store decimal values, at least those within a restricted range.
24
Q
Disadvantage of decimal types
A
- Range of values is restricted because no exponents are allowed.
- Wastes memory
25
Simplest of all types
Boolean types
26
Boolean types range of values:
one for "true" and one for "false"
27
Boolean types advantage:
Readability
28
Stored as numeric coding
Character types
29
Most commonly used coding of character types
ASCII
30
Values consist of sequences of characters
Character string types
31
Character string types design issues:
- Should strings be simply a special kind of character array or primitive type?
- Should strings have static or dynamic length?
32
Most common string operations:
- Assignment
- Catenation
- Substring reference
- Comparison
- Pattern matching
33
A reference to a substring of a given string
Substring reference
34
Substring references are called
slices
35
Character string length options
1. Static length string
2. Limited dynamic length string
3. Dynamic length string
36
The length can be static and set when the string is created
Static length strings
37
Allow strings to have varying length up to a declared and fixed maximum set by the variable's definition.
Limited dynamic length strings
38
Allow strings to have varying length with no maximum.
Dynamic length strings
39
Three fields of a descriptor:
Name of the type
Type's length (in characters)
Address of the first character
40
Three approaches to supporting the dynamic allocation and deallocation that is required for dynamic length strings.
1. Strings can be stored in a linked list.
2. Store strings as arrays of pointers to individual characters allocated in the heap.
3. Store complete strings in adjacent storage cells.
41
the range of possible values can be easily associated with the set of positive integers
Ordinal type
42
Primitive ordinal types in Java
integer, char, boolean
43
All possible values, which are named constants, are provided in the definition
Enumeration type
44
Enumeration type design issues:
1. Is an enumeration constant allowed to appear in more than one type definition, and if so, how is the type of an occurrence of that constant in the program checked?
2. Are enumeration values coerced to integer?
3. Are any other types coerced to an enumeration type?
45
Enumeration literals are allowed to appear in more than one declaration in the same referencing environment.
Overloaded literals
46
Advantages of enumeration types
Aid to readability: Named values are easily recognized, whereas coded values are not.
Aid to reliability: (1) No arithmetic operations are legal on enumeration types. (2) No enumeration variable can be assigned a value outside its defined range.
47
A contiguous subsequence of an ordinal type
subrange type
48
Advantages of subrange types
Aid to readability: Make it clear to the readers that variables of subrange can store only certain range of values.
Aid to reliability: Assigning a value to a subrange variable that is outside the specified range is detected as an error.
49
Enumeration types are implemented as:
Integers
50
A homogeneous aggregate of data elements in which an individual element is identified by its position in the aggregate, relative to the first element
Array
51
Array design issues
1. What types are legal for subscripts?
2. Are subscripting expressions in element references range checked?
3. When are subscript ranges bound?
4. When do array allocation take place?
5. Are ragged or rectangular multidimensioned arrays allowed, or both?
6. Can arrays be initialized when they have their storage allocated?
7. What kinds of slices are allowed, if any?
52
Arrays are sometimes called
finite mappings
53
Array categories:
1. Static array
2. Fixed stack-dynamic array
3. Stack-dynamic array
4. Fixed heap-dynamic array
5. Heap-dynamic array
54
Subscript ranges are statically bound and storage allocation is static (before run-time)
Static array
55
Subscript ranges are statically bound, but the allocation is done at declaration time
Fixed static-dynamic array
56
Subscript ranges are dynamically bound and storage allocation is dynamic (done at run-time)
Stack-dynamic array
57
Similar to fixed stack-dynamic: Storage binding is dynamic but fixed after allocation
Fixed heap-dynamic array
58
Binding of subscript ranges and storage allocation is dynamic and can change any number of times
Heap-dynamic array
59
Python's arrays are called:
Lists
60
A multi-dimensioned array in which all of the rows have the same number of elements and all columns have the same number of elements
Rectangular array
61
Has rows with varying number of elements
Jagged matrix
62
A ___ of an array is some substructure of that array.
slice
63
Two ways in which multidimensional arrays can be mapped to one dimension:
Row major order and column major order
64
The elements of the array that have as their first subscript the lower bound value of the subscript are stored first, followed by the elements of the second value of the first subscript, and so forth.
Row major order
65
The elements of the array that have as their last subscript the lower bound value of the subscript are stored first, followed by the elements of the second value of the last subscript, and so forth.
Column major order
66
Unordered collection of data elements that are indexed by an equal number of values called keys
Associative array
67
In Perl, associative arrays are called:
hashes
68
Python's associative arrays are called:
dictionaries
69
An aggregate of data elements in which the individual elements are identified by names and accessed through offsets from the beginning of the structure
record
70
All intermediate record names, from the largest enclosing record to the spcefic field, are named in the reference
fully qualified reference
71
The field is named, but any or all of the enclosing record names can be omitted, as long as the resulting reference is unambiguous in the referencing environment.
elliptical references
72
Data type that is similar to a record, except that the elements are not named
tuple type
73
Python includes a powerful mechanism for creating arrays called____
list comprehensions
74
A type whose variables are allowed to store different type values at different times during execution
union
75
Union design issues:
1. Should type checking be required?
2. Should unions be embedded in records?
76
A union with a discriminant
discriminant union
77
The variables have a range of values that consists of memory addresses and a special value, nil.
Pointer type
78
Uses of pointers
1. Provides some of the power of indirect addressing
2. Provides a way to manage dynamic storage.
79
A pointer that can be used to access a location in an area where storage is dynamically allocated is called a ___
heap
80
Variables that are dynamically allocated from the heap are called
heap-dynamic variables
81
variables without names
anonymous variables
82
two categories of variables
reference types and value types
83
Design issues particular to pointers:
1. What are the scope and lifetime of a pointer variable?
2. What is the lifetime of a heap-dynamic variable?
3. Are pointers restricted as to the type of value to which they can point?
4. Are pointers used for dynamic storage
management, indirect addressing, or both?
5. Should the language support pointer types, reference types, or both?
84
Fundamental pointer operations:
assignment and dereferencing
85
Used to set a pointer variable's value to some useful address
Assignment
86
Yields the value stored at the location represented by the pointer's value
Dereferencing
87
Pointer problems:
1. Dangling pointers
2. Lost heap-dynamic variable
88
A pointer that contains the address of a heap-dynamic variable that has been deallocated..
Dangling pointer or dangling reference
89
An allocated heap-dynamic variable that is no longer accessible to the user program (often called garbage)
Lost heap-dynamic variable
90
Lost heap-dynamic variables are most often created by the following sequence of operations:
1. Pointer p1 is set to point to a newly created heap-dynamic variable.
2. p1 is later set to point to another newly created heap-dynamic variable.
91
Ada's pointers are called
access types
92
Solutions to the dangling-pointer problem
1. Tombstones
2. Lock-and-keys approach
93
Extra heap cell taht is a pointer to the heap-dynamic variable
Tombstone
94
Pointer values are represented as [key,address] pairs
Lock-and-keys
95
Two approaches to reclaim garbage
1. Reference counters (eager approach)
2. Mark-sweep (lazy approach)
96
Reclamation is gradual
Reference counters
97
Reclamation occurs when the list of variable space becomes empty
Mark-sweep
98
Some of the inefficiency of reference counters can be eliminated by an approach named________, which avoids reference counters for some pointers.
deferred reference counting
99
Advantage or reference counter approach
It is intrinsically inremental. Its actions are interleaved with those of the application, so it never causes significant delays in the execution of the application.
100
The activity of ensuring that the operands of an operator are of compatible types
type checking
101
one that is either legal for the operator or is allowed under language rules to be implicitly covered by compiler-generated code to a legal type
compatible type
102
the application of an operator to an operand of an inappropriate type
type error
103
dynamic type binding requires type checking at run time, which is called __________
dynamic type checking
104
a programming language is ______ if type errors are always detected
strongly typed
105
advantage of strong typing
allows the detection of the misuses of variables that result in type errors
106
when are two types equivalent?
if an operand of one type in an expression is substituted for one of the other type, without coercion
107
two approaches to defining type equivalence:
1. name type equivalence
2. structure type equivalence
108
means that two variables have equivalent types if they are defined either in the same declaration or in declarations that use the same type name
name type equivalence
109
means that two variables have equivalent types if their types have identical structures
structure type equivalence
110
a new type that is based on some previosuly defined type with which is not equivalent, although it may have identical structure
derived type
111
in computer science, there are two branches of type theory:
practical and abstract
112
arithemetic expressions consists of:
1. operators
2. operands
3. parentheses
4. function calls
113
operator with a single operand
unary
114
operator with two operand
binary
115
operator with three operand
ternary
116
unary addition is called ___ because it usually has no associated operation and thus has no effect on its operand
identity operator
117
typical precedence levels:
- parentheses
- unary operators
- ** (if the language supports it)
- *, /
- +, -
118
define the order in which adjacent operators with the same precedence level are evaluated
operator associativity rules
119
define the order in which adjacent operators of different precedence levels are evaluated
operator precedence rules
120
occurs when the function changes either one of its parameters or a global variable
side effect
121
a program has the property of _________ if any two expressions in the program that have the same values can be substitued for one another anywhere in the program, without affecting the action of the program
referential transparency
122
use of an operator for more than one purpose is called
operator overloading
123
type conversions are either:
narrowing or widening
124
converts an object to a type that cannot include all of the values of the original type
narrowing conversion
125
an object is converted to a type that can include at least approximations to all of the values of the original type
widening conversion
126
one that has operands of different types
mixed-mode expression
127
a coercion is an ___ type conversion
implicit
128
in c-based languages, explicit type conversions are caled:
casts
129
an operator that compares the values of its two operands
relational operator
130
an expression in which the result is determined without evaluating all the operands and/or operators.
short-circuit evaluation
131
a shorthand method of specifying a commonly needed form of assignment
compound assignment operator
132
provides the means of choosing betwen two or more paths of execution
selection statement
133
selection statement categories:
1. two-way selection
2. multiple-way selection
134
allow the selection of one of any number of statements or statement groups
multiple-way selection
135
one that causes a statement or collection of statements to be executed zero, one, or more times
iterative statement (often called a loop)
136
the ___ of an iterative statement is the collection of statements whose execution is controlled by the iteration statement
body
137
means that the test for loop completion occurs before the loop body is executed
pretest
138
means that the test for loop completion occurs after the loop body is executed
posttest
139
the iteration statement and the associated loop body together form an:
iteration stament
140
transfers execution control to a specified location in the program
unconditional branch statement
141
who designed guarded commands
Dijkstra
142
purpose of dijkstra on making guarded commands
to support a new programming methodology that suported verification (correctness) during development
143
two fundamental abstarction facilities can be included in a programming language:
1. process abstraction
2. data abstraction
144
describes the interface to and the actions of the subprogram abstraction
subprogram definition
145
an explicit request that the subprogram be executed
subprogram call
146
the first part of the definition, including the name, the kind of subprogram, and the formal parameters
subprogram header
147
_____ of a subprogram is the number, order, and types of its parameters
parameter profile
148
a subprogram's parameter profile and, if it is a function, its return type
protocol
149
function declarations in C and C++ are often called:
prototypes
150
provides the protocol, but no the body of the subprogram
subprogram declaration
151
a dummy variable listed in the subprogram header and used in the subprogram
formal parameter
152
represents a value or address used in a subprogram call
actual parameter
153
two ways that a non-method subprogram can gain access to the data that it is to process:
through:
1. direct access to nonlocal variables
2. parameter passing
154
two distinct categories of subprograms:
procedures and functions
155
the parameters in the subprogram header
formal parameters
156
the first actual parameter is bound to the first formal parameter and so forth
positional parameters
157
the name of the formal parameter to which an actual parameter is to be bound is specified with the actual parameter
keyword parameters
158
advantage of positional parameters
safe and effective
159
advantage and disadvantage of keyword parameters
advantage: parameters can appear in any order
disadvantage: the user of the subprogram must know the names of formal parameters
160
one that has the same name as another subprogram in the same referencing environment
overloaded subprogram
161
one whose computation can be done on data of different types in different calls
generic subprogram
162
a nested subprogram and its referencing environment, which together allow the subprogram to be called from anywhere in a program
closure
163
variables that are defined inside subprograms are called
local variables
164
local variables can be either:
static or stack dynamic
165
local variables that are bound to storage when the subprogram begins execution and are unbound from storage when the execution terminates
stack-dynamic local variables
166
advantages and disadvantages of stack-dynamic local variables
advantages:
- support for recursion
- storage for locals is shared among some subprograms
disadvantages:
- allocation/deallocation, initialization time
- indirect addressing
-subprograms cannot be history sensitive
167
examples of subprograms that need to be history sensitive
- generating pseudorandom numbers
- coroutines
- subprograms used in the iterator loop constructs
168
advantages and disadvantage of static local variables
advantage:
- slightly more efficient (doesn't require run-time over-head for allocation/deallocation)
- subprograms can be history sensitive
disadvantage:
- doesn't support recursion
- storage cannot be shared with the local variables of other inactive subprograms
169
three distinct sematic models:
1. in mode
2. out mode
3. inout mode
170
they can receive data from the corresponding actual parameter
in mode
171
they can transmit data to the actual parameter
out mode
172
they can do both: receiving and transmitting data to actual parameter
inout mode
173
parameter passing methods
1. pass-by-value
2. pass-by-result
3. pass-by-value-result
4. pass-by-reference
5. pass-by-name
174
the value of the actual parameter is used to initialize the corresponding formal parameter, which then acts as a local variable in the subprogram
pass-by-value (in-mode)
175
advantage and disadvantage of pass-by-value
advantage:
- for scalars, it is fast, in both linkage cost and access time
disadvantage:
- additional storage is reqquired for the formal parameter (either in the called subprogram or in some area outside)
176
no value is transmitted to the subprogram; the corresponding formal parameter acts as a local variable; its value is transmitted to caller's actual parameter when control is returned to the caller
pass-by-result (out mode)
177
advantage and disadvantage of pass-by-result
advantage:
- for scalars, it is fast, in both linkage cost and access time
disadvantage:
- additional storage is reqquired for the formal parameter (either in the called subprogram or in some area outside)
- needs to ensure that the initial value of the actual parameter is not used in the called subprogram
- actual parameter collision
178
a combination of pass-by-value and pass-by-result
pass-by-value-result (inout mode)
179
pass-by-value-result is sometimes called:
pass-by-copy
180
the actual parameter is copied to the formal parameter at subprogram entry and then copied back at subprogram termination
pass-by-value-result
181
pass an access path
pass-by-reference (inout mode)
182
pass by reference is also called
pass by sharing
183
advantage and disadvantage of pass-by-reference
advantage:
- passing process is effecient (no copying and duplicated storage)
disadvantage:
- slower accesses to formal parameters
- potentials for unwanted side effects
- unwanted aliases
184
the actual parameter is textually substituted for the corresponding formal parameter in all its occurrences in the subprogram
pass-by-name (inout mode)
185
bound to an access method at the time of the subprogram call, but the actual binding to a value or an address is delayed until the formal parameter is assigned or referenced
pass-by-name (inout mode)
186
simplest parameter passing method to implement
pass-by-reference
187
two important design considerations for parameter passing
1. efficiency
2. one way or two way data transfer
188
three choices fow what referencing envirsonment for executing the passed subprogram should be used:
1. shallow binding
2. deep binding
3. ad hoc binding
189
the environment of the call statement that enacts the passed subprogram
shallow binding
190
the environment of the definition of the passed subprogram
deep binding
191
the environment of the call statement that passed the subprogram as an actual parameter
ad hoc binding
192
a subprogram that has the same name as another subprogram in the same referencing environment
overloaded subprogram
193
takes parameters of a different types on different activations
generic or polymorphic subprogram
194
particular kind of polymorphism provided by overloaded subprograms
ad hoc polymorphism
195
means that a variable of type T can access any object of type T or any type derived from T
subtype polymorphism
196
is provided by a subprogram that takes generic parameters that are used in type expressions that describe the types of the parameters of the subprogram
parametic polymorphism
197
a subprogram and the referencing environment where it was defined
closure
198
a variable whose lifetime is that of the whole program is said to have:
unlimited extent
199
a subprogram that has multiple entries and controls them itself
coroutine
200
a coroutine call is named a:
resume
201
language categories:
1. imperative
2. functional
3. logic
4. object-oriented
5. markup
202
language design trade-offs:
1. reliability vs. cost of execution
2. readability vs. writability
3. writability vs. reliability
203
programming language implementation methods:
1. compilation
2. pure interpretation
3. hybrid implementation systems
204
three primary methods of semantics description:
1. operational
2. axiomantic
3. denotational
205
