450 exam 3 Flashcards
(182 cards)
1
Q
unary operator
A
has one operand; e.g., ++, –
2
Q
binary operator
A
has two operands; e.g., +, -, *, /
3
Q
ternary operator
A
has three operands; e.g., ? : conditional expression syntax (ex: average = (count == 0) ? 0 : sum / count;)
4
Q
operator precedence rules for expression evaluation define
A
the order in which “adjacent” operators of different precedence levels are evaluated
5
Q
typical precedence levels (highest to lowest precedence)
A
parentheses unary operators ** (if the language supports it) *, / \+, -
6
Q
operator associativity rules for expression evaluation define
A
the order in which adjacent operators with the same precedence level are evaluated
7
Q
associativity for operators is typically ? except for ?
A
left to right; ** is right to left
8
Q
what does 2 ** 3 ** 4 evaluate to using typical associativity rules?
A
2 ** 81
9
Q
associativity for assignment is ?
A
right to left
10
Q
what are the values of a=1, b=2, c=3 after executing a = b += c ?
A
a=5, b=5, c=3
11
Q
functional side effects
A
occur when a function changes either one of its parameters or a global variable (declared outside the function but is accessible in the function)
12
Q
functions in mathematics (do/do not) have side effects - why?
A
do not b/c there is no notion of variables in mathematics
13
Q
functional programming languages have no variables, so do they have functional side effects?
A
no
14
Q
a program has referential transparency if
A
any two expressions in the program that have the same value can be substituted for one another anywhere in the program, without affecting the action of the program
15
Q
advantage of referential transparency
A
semantics easier to understand
16
Q
programs in pure functional languages (are/are not) referentially transparent - why?
A
are; b/c they do not have variables (so, if a function uses an outside value, it must be a constant)
17
Q
narrowing conversion
A
converts a value to a type that cannot include all of the value of the original type (ex: float to int)
18
Q
widening conversion
A
a value is converted to a type that can include all of the value of the original type (ex: int to float)
19
Q
coercion
A
implicit type conversion
20
Q
casting
A
explicit type conversion
21
Q
relational expressions
A
use relational operators/operands of various types; evaluate to true or false; operators !=, >=, <=, etc.
22
Q
boolean expressions
A
operands are boolean and the result is boolean; operators &&, ||, !
23
Q
short-circuit evaluation
A
the result is determined without evaluating all of the operands and/or operators
24
Q
when would the following be an example of short-circuit evaluation?
(13 * a) * (b / 13 - 1)
A
if a=0, there is no need to evaluate (b / 13 -1) because the result will be 0
25
assignment statements general syntax
[target_var] [assign_operator] [expression]
26
compound assignment operator
a shorthand method of specifying a commonly needed form of assignment (e.g., +=)
27
unary assignment operators
in C-based languages; combine increment and decrement operations with assignment (e.g., sum = count++;)
28
multiple assignments
allowed by Perl, Python, and Ruby; e.g., ($first, $second, $third) = (20, 30, 40);
29
example of multiple assignment in Python
interchange: (a, b) = (b, a)
30
mixed-mode assignment in Fortran, C, Perl, and C++
any numeric type value can be assigned to any numeric type variable
31
mixed-mode assignment in Java and C#
only widening assignment coercions are done (e.g., int x = 3.5;) is valid in C++ but not in Java
32
control structure
a control statement and the statements whose execution it controls
33
selection statement
provides the means of choosing between two or more paths of execution
34
two general categories of selection statements
two-way selectors & multiple-way selectors
35
general form of two-way selection statements
if control_expression then
clause
else
clause
36
if the then reserved word (or some other syntactic marker) is not used to introduce the then clause, the control expression is placed in
parentheses
37
in what languages can the control expression be arithmetic? what is the type of a control expression in most other languages?
C/C++ and Python; Boolean
38
Python uses ? to define clauses and nest selectors
indentation
39
Java's static semantics rule: else matches with which if? to force it to match with something else, use ?
the nearest previous if; braces
40
Ruby uses the keyword ? for nesting selectors
end
41
in ML, F#, and Lisp, the selector is
an expression
42
multiple-way selection statements
allow the selection of any number of statements or statement groups
43
C/C++, Java, and JavaScript use ? for multiple-way selection
switch statements
44
Ruby uses ? for multiple-way selection
case expression
45
Python uses ? for multiple-way selection
else-if clauses
46
iterative statement
one that causes a statement or collection of statements to be executed zero, one, or more times
47
iteration/recursion
the repeated execution of a statement or compound statement
48
an iterative statement is often called a
loop
49
counter-controlled loops: a counting iterative statement has
a loop variable, and a means of specifying the initial and terminal, and stepsize values
50
counter-controlled loops example
for loop
51
if the (first/second/third) expression is absent in a for loop, it is an infinite loop
second
52
counter-controlled loop syntax in C-based languages
for([expr1]; [expr2]; [expr3]) {
statement(s)
}
53
counter-controlled loop syntax in Python
for loop_variable in object:
| loop body
54
the object in a Python counter-controlled loop is often a
range, which is either a list of values in brackets or a call to the range function
55
logically-controlled loops are also called
event-controlled (or condition-controlled) loops
56
repetition control in logically-controlled loops is based on
a Boolean expression
57
logically-controlled loops in C-based languages
while or do-while loops
58
C and C++ allow the control expression to be
arithmetic
59
Java is like C and C++ in regards to logically-controlled loops, except
the control expression must be Boolean and Java has no goto
60
unconditional branch statement
transfers execution control to a specified place in the program (e.g., goto statement)
61
major concerns of unconditional branching
readability and reliability
62
what represented one of the most heated debates in the 1960's and 1970's?
unconditional branching (e.g., goto statements)
63
do all languages support goto?
no; for instance, Java
64
guarded command language (GCL)
language defined by Dijkstra in 1975
65
purpose of guarded command language
to support a new programming methodology that supported verification (correctness) during program development
66
basic idea of guarded command language
if the order of evaluation is not important, the program should not specify one
67
guarded command
each line in the selection statement, consisting of a Boolean expression (a guard) and a statement or statement sequence
68
semantics of guarded command: when construct is reached,
evaluate all Boolean expressions
if more than one is true, choose one non-deterministically
if none of the conditions are true, error
69
subprogram definition
describes the interface to and the actions of the subprogram abstraction
70
subprogram call (or invocation)
an explicit request that the subprogram be executed
71
subprogram header
the first part of the definition, including the name, the kind of subprogram, and the formal parameters
72
subprogram profile/signature
the name of the subprogram and the parameter list (number, order, and types of its parameters)
73
subprogram protocol
a subprogram’s profile and its return type
74
formal parameter
a dummy variable listed in the subprogram
| header and used in the subprogram
75
actual parameter
represents a value used in the subprogram call statement (aka argument)
76
the parameters in the method declaration max(int num1, int num2) are (actual/formal)
formal
77
the parameters in the method call max(x, y) are (actual/formal)
actual
78
actual/formal parameter correspondence: positional
the binding of actual parameters to formal parameters is by position: the first actual parameter is bound to the first formal parameter etc.
safe and effective
79
actual/formal parameter correspondence: keyword
the name of the formal parameter to which an actual parameter is to be bound is
specified with the actual parameter
parameters can appear in any order, but user must know formal parameter names
80
keyword correspondence is supported by
Python, Ruby, R, Visual Basic, etc.
81
example of calling a method with keyword correspondence for the following method definition:
def show_interest(principle, rate, periods):
show_interest(rate=0.01, periods=10, principle=10000.0)
82
in certain languages (e.g., Python, C++, Ruby, PHP), formal parameters can have ? if no actual parameter is passed
default values
83
example of a method using default values
void greet(string name, string msg="Good morning!")
if no msg is passed, the "Good morning!" value is used
84
languages that support variable number of parameters
Java, C/C++, C#, Python, Ruby, etc.
85
example of a method header using variable number of parameters
public static void print(int... numbers)
vararg parameters are treated as arrays
86
two categories of subprograms
procedures & functions
87
procedures
collections of statements that define computations; do not return values
88
functions
semantically modeled on mathematical functions; return values
89
functions are expected to ?
produce no side effects (but in practice, they do)
90
models of parameter passing: in mode
passes info from caller to callee
caller --> callee
91
models of parameter passing: out mode
callee writes values in caller
caller
92
models of parameter passing: inout mode
caller tells callee value of variable, which may be updated by callee
caller callee
93
pass-by-value is (in/out/inout) mode
in
94
pass-by-value
changes made to the formal parameter do not get transmitted back to the caller; any modifications to the parameter variable inside the called function will not be reflected
95
pass-by-reference is (in/out/inout) mode
inout
96
pass-by-reference (aka pass-by-sharing)
changes made to formal parameter get transmitted back to the caller through parameter passing; any changes to the formal parameter are reflected in the parameter in the calling environment b/c the formal parameter receives a reference to the actual data.
97
pass-by-result is (in/out/inout) mode
out
98
pass-by-result
no value is transmitted to the subprogram; the corresponding formal parameter acts as a local variable and its value is transmitted to the caller’s actual parameter
99
pass-by-value-result is (in/out/inout) mode
inout
100
pass-by-value-result
a combination of pass-by- value and pass-by-result
101
pass-by-name is (in/out/inout) mode
inout
102
pass-by-name
symbolic name of a variable is passed, which allows it both to be accessed and updated; used in Algol
103
in some languages (e.g., Python, JavaScript, Haskell), subprograms can be passed as ?
parameters
104
three choices of the referencing environment for executing a subprogram passed as a parameter
deep binding, shallow binding, ad-hoc binding
105
deep binding
the environment of the definition of the passed subprogram; most natural for static-scoping
106
shallow binding
the environment of the call statement that enacts the passed subprogram; most natural for dynamic-scoping
107
overloaded subprogram
one that has the same name as another subprogram in the same referencing environment
108
every version of an overloaded subprogram has
a unique protocol (essentially same name, but return type/parameters may vary)
109
generic (or polymorphic) subprogram
takes parameters of different types on different activations
110
generic functions in C++ are named
template functions
111
example of a template function (C++ generic function)
```
template
Type max(Type first, Type second) {
//method body
}
```
112
subprogram linkage
the subprogram call and return operations of a language
113
activation record
the format (or layout) of the non-code part of an executing subprogram
114
activation record instance
a concrete example of an activation record (the collection of data for a particular subprogram activation)
115
an activation record includes
local variables, parameters, and the return address
116
activation record instances reside on the ? and are dynamically created when ?
run-time stack; a subprogram is called
117
dynamic link of a subprogram
always points to the caller, which immediately precedes it on the stack; used to reset top-of-stack when a subprogram exits
118
dynamic chain (or call chain)
the collection of dynamic links in the stack at a given time
119
typical activation record for a language with stack-dynamic local variables
local variables, parameters, dynamic link, return address
120
environment pointer (EP)
always points at the base of the activation record instance of the currently executing program unit
121
local offset
local variables can be accessed by their local offset from the beginning of the activation record, whose address is in the environment pointer
122
the local_offset of a local variable (can/cannot) be determined easily at compile time
can
123
the first local variable in a subprogram would be allocated where?
in the AR two position (for return address and dynamic link) plus the number of parameters from the bottom
124
static link in an activation record instance for subprogram A
points to the activation record instance of A's static parent
125
static chain
a chain of static links that connects certain activation record instances
126
the static chain from an activation record instance connects it to
all of its static ancestors
127
static_depth
an integer associated with a static scope whose value is the depth of nesting of that scope
128
chain_offset (or nesting_depth) of a nonlocal reference
the difference between the static_depth of the reference and that of the scope where it is declared
129
a reference to a variable can be represented by the pair
(chain_offset, local_offset), where local_offset is the offset in the activation record of the variable being referenced
130
the design of the imperative languages is based directly on
the von Neumann architecture
131
the design of the functional languages is based on
mathematical functions
132
primary concern of imperative languages
efficiency
133
lambda expression
specifies the parameter(s) and the mapping of a function; describe nameless functions; applied to parameter(s) by placing the parameter(s) after the expression
134
functional form
a higher-order function that either takes functions as parameters or yields a function as its result, or both
135
function composition
a functional form that takes two functions as parameters and yields a function whose value is the first actual parameter function applied to the application of the second
136
form of function composition
h ≡ f * g means h(x) ≡ f(g(x))
137
apply-to-all
a functional form that takes a single function as a parameter and yields a list of values obtained by applying the given function to each element of a list of parameters
138
form of apply-to-all
α
example for h(x) = x* x
α(h, (2, 3, 4) yields (4, 9, 16)
139
objective of functional programming languages
to mimic mathematic functions to the greatest extent possible
140
referential transparency
in a functional programming language, the evaluation of a function always produces the same result given the same parameters
141
if in Scheme
if predicate then_exp else_exp
| ex:
if <= n 1
1 //return one if true
0 //else zero
142
cond in Scheme
```
(cond
((zero? (modulo year 400)) #t)
((zero? (modulo year 100)) #f)
(else (zero? (modulo year 4))) //default case
)
```
143
list function
returns a new list of its parameters
144
car function
returns first element of its list parameter
145
cdr function
returns the remainder of its list parameter after the first element has been removed
146
cons function
puts its first parameter into its second parameter, a list, to make a new list
147
what does (list 'A 'B '(C D)) return?
(A B (C D))
148
what does (car '(A B C)) return?
A
149
what does (cdr '(A B C)) return?
(B C)
150
what does (cons 'A '(B C)) return?
(A B C)
151
list? function returns #t if
parameter is a list
152
null? function returns #t if
the parameter is the empty list
153
member takes an atom and a simple list; returns #t if
atom is in the list
154
append takes two lists as parameters; returns
the first parameter list with the elements of the second parameter list appended at the end
155
a function is tail recursive if
its recursive call is the last operation in the function
156
functional programming features in Python
lambda expressions, map
157
imperative languages pros/cons
complex syntax & semantics, efficient execution
158
functional languages pros/cons
simple syntax & semantics, less efficient execution
159
logic programming languages
AKA declarative languages; use a logical inferencing process to produce results (only specification of results are stated)
160
compound term
one element of a mathematical relation, written like a mathematical function (a mapping)
161
compound term is composed of two parts
functor (function symbol that names the relationship) and an ordered list of parameters
e.g., student(jon)
student - functor
jon - parameter
162
clausal form has two parts
antecedent (right side - if) and consequent (left side - then)
163
resolution
an inference rule that allows inferred propositions to be computed from given propositions
essentially cutting out the middle man
164
unification
finding values for variables in propositions that allows matching process to succeed
165
instantiation
assigning temporary values to variables to allow unification to succeed
166
backtracking
with a goal of multiple subgoals, if it fails to show truth of one of the subgoals, reconsider another subgoal to find an alternative solution; begin search where previous search left off
167
Horn clauses have two forms
headed and headless
168
headed Horn clause
single atomic proposition on left side
e.g., likes(bob, trout) ⊂ likes(bob, fish) ∩ fish(trout)
169
headless Horn clause
empty left side (used to state facts or queries)
e.g., father(bob, jake)
170
fact statements
headless Horn clauses
171
rule statements
headed Horn clauses
e.g., ancestor(mary, shelley) :- mother(mary, shelley).
172
conjunction
multiple terms separated by logical AND operations (use a comma)
173
goal statements (or queries)
in form of a proposition that we want the system to prove or disprove; same as a headless Horn
e.g., man(fred).
e.g., father(X, mike).
X is a variable that will yield the result, if one is found
174
process of proving a subgoal is called
matching or satisfying
175
forward chaining
begin with facts and rules of database and attempt to find a sequence of matches that lead to goal
176
backward chaining
begin with goal and attempt to find a sequence of matching propositions that lead to some set of original facts in the database
177
Prolog implementations use (forward/backward) chaining
backward
178
when goal has more than one subgoal, can use either
depth-first search or breadth-first search
179
depth-first search
find a complete proof for the first subgoal before working on others
180
breadth-first search
work on all subgoals in parallel
181
Prolog uses (breadth-first/depth-first) search
depth-first
182
applications of logic programming
relational DB management systems, expert systems, natural language processing
