Exam 2 Flashcards
1
Q
What is logic programming?
A
A collection of facts and rules. Facts are logical statements assumed to be true (axioms), and rules are logical statements that derive new facts from existing facts that support the premise.
2
Q
What is forward-chaining?
A
Start with the facts and work forwards towards the query (the goal).
3
Q
What is backward-chaining?
A
Start with the query (the goal) and move backwards saving any facts that supports the goal
4
Q
Data-Driven vs. Goal-Driven Search
A
Data-driven is best for automatic processing such as object recognition, routine decisions; may do lots of work that is irrelevant to the goal. Goal driven is more appropriate for problem solving such as where are my keys? How do I get into a PhD program? Goal driven is often used in expert systems that are designed for medical diagnosis or other types of diagnostic systems
5
Q
What is first-order predicate logic?
A
Boolean logic assumes the world contains facts that are either true or false, predicate logic assumes the world contains objects and relationships.
6
Q
What are some symbols in predicate calculus?
A
A constant, a variable, a function, or a predicate. Constants being with lowercase letters, variables being with an uppercase letter, the arity of a function is the number of arguments of the functor, and a predicate names a relationship between objects in the world.
7
Q
Everyone likes ice cream.
A
There does not exist someone who doesn’t like icecream.
8
Q
There exists a person that likes broccoli is the same as?
A
It is not true that no one likes broccoli
9
Q
“If it doesn’t rain on Monday, Tom will go to the mountains.”
A
not(weather(rain, monday) → go(tom, mountains))
10
Q
Emma is a Doberman pinscher and a good dog.
A
is_a(emma, doberman) good_dog(emma)
11
Q
“All basketball players are tall.”
A
X (basketball_player(X) → tall(X))
12
Q
“Nobody likes taxes.”
A
not( X likes(X, taxes))
13
Q
What are prolog statements constructed from?
A
Terms. A term is a constant, a variable, or a structure. A constant is an atom or an integer. An an atom is a string of letters, digits, or underscores that begins with a lowercase letter.
14
Q
What is a variable in ProLog?
A
A variable is any string of letters, digits, or underscores that begins with an uppercase letter or an underscore
Variables are not bound to types by declarations
The binding of a value to a variable (hence its type) is called an instantiation
Instantiation occurs as a result of resolution
Instantiations last only as long as it takes to satisfy one complete goal, which involves the proof or disproof of one proposition
15
Q
What is a headless horn clause?
A
The headless Horn clause is an unconditional assertion (a fact, or a proposition that is assumed to be true). For example,
male(bill).
16
Q
What is a headed horn clause?
A
Represents a rule, such that a conclusion can be drawn if a given set of conditions is satisfied
consequence :- antecedent_expression
i.e. ancestor(mary, shelley) :- mother(mary, shelley)
17
Q
When are variables in prolog assumed to universally quantified vs existentially quantified?
A
Variables in the consequence are assumed to be universally quantified
Variables in the antecedent expressions are assumed to be existentially quantified
18
Q
What is the syntax of a goal statement?
A
Headless Horn statement.
19
Q
Prolog to append a list to another list to produce a third list:
A
append( [ ], B, B).
append( [H | T], A, [H | L] ) :- append(T,A,L).
20
Q
What is the “is” operator in prolog?
A
It takes an arithmetic expression as its right operand and a variable as its left operand. X is 1+2.
X = 3.
21
Q
Will 1+2 is 4-1 work?
A
No, because first argument 1+2 is already instantiated.
22
Q
Will X is Y work?
A
No, Y must already be instantiated.
23
Q
Will Y is 1+2, X is Y. work?
A
Yes, if y is instantiated by the time it is needed. Y =3, X =3
24
Q
What is the prolog tracing model?
A
The prolog tracing model of execution has four events: - call (beginning of attempt to satisfy goal), Exit (when a goal has been satisfied), Fail (when goal fails), Redo (when backtracking occurs).
25
Explain backtracking in Prolog.
Prolog searches the database in the order that the statements are listed for each attempt to satisfy a goal. Attempts to satisfy sub-goals left to right after matching a goal to a fact/rule in database. Failure to satisfy a sub-goal undoes unification (uninstantiates variables) and the database search is resumed.
The search for a proof (resolution) in prolog proceeds in a depth-first manner. Can take lots of time and space because may find all possible proofs to every subgoal.
26
How can we make prolog more efficient?
Allows the user to control the ordering of pattern matching during backtracking for resolution. If a user knows that certain rules are much more likely to succeed than the others, then place those rules before the others.
27
What is the cut operator?
A goal that is always satisfied immediately, it cannot be resatisified through backtracking. Side effect is that sub-goals that come after it in a compound goal cannot be re-satisfied through backtracking.
28
What is the closed-world assumption?
Prolog can prove that a given goal is true, but it can never provate that a goal is false. When the system receives a query and the database does not have information to prove it is true, the query is assumed to be false.
29
What is the negation problem?
The prolog operator not is not the same as the logical "not". Consider not(X = Y), if this statement succeeds it does not necessarily mean that X is not equal to Y, it means that resolution cannot prove from the database that X is the same as Y.
30
Resolution requires that the problem be expressed in what?
Conjunctive normal form.
31
What is the conjunctive normal form?
```
It is a conjunction of disjunctions.
X1 Λ X2 Λ X3 Λ … Λ Xn
where each clause, Xi, is of the form:
Y1 v Y2 v Y3 v … v Yn
The Ys are literals
For example, A Λ (B v C) Λ (¬A v ¬B v ¬C v D) is in conjunctive normal form
```
32
Convert A -> B to CNF
not A v B
33
Convert not(A ^ B) to CNF
not A v not B
34
What is a horn clause?
A disjunctive clause that has at most one positive literal: ¬B v ¬C v ¬D v ¬E v A …
This can also be written as an implication:
B Λ C Λ D Λ E → A
In PROLOG, this is written:
A :- B, C, D, E
35
Know the resolution rule
Let us resolve: {(¬A,B), (¬A,¬B,C), A, ¬C}
We begin by resolving the first clause with the second clause, thus eliminating B and ¬B:
{(¬A,C), A, ¬ C}
{C, ¬C}
Now we can resolve both remaining literals, which gives falsum (a contradiction):
^
If we reach falsum, we have proved that our initial set of clauses were inconsistent
This is written:
{(¬A,B),(¬A,¬B,C),A,¬C} ╞ ^
36
Proof by contradiction
Negate its conclusion, convert it to clause form, and then derive falsum using resolution. If we derive falsum, then our clauses were inconsistent, meaning the original argument was valid, since we negative its conclusion.
37
Prove the following 3 statements using proof by contradiction:
(A Λ ¬B) → C
A Λ ¬ B
C
Negate the conclusion and convert to clauses:
{(¬A,B,C), A, ¬B, ¬C}
Now resolve:
{(B,C), ¬B, ¬C}
{C, ¬C}
^
We have reached falsum, so our original argument was valid
38
Prove or disprove the following:
A → B, B → C, C → D, D → E F
A→F
First, we negate the conclusion to give (A→F)
Next we convert to clause form:
D → E F ≡ D (E F) and (A → F) ≡ (A F) ≡ A F
So our clauses are: {(A,B), (B,C), (C,D), (D,E,F), A, F}
This will resolve to {E}; we cannot reach falsum. Hence, we can conclude that our original conclusion was not valid. (You can prove this for yourself by using a truth table.)
39
Where does Unification come in to Resolution?
To complete the resolution of clauses, we often need to make substitutions. For example:
{ (p(W, X)), (¬p(Y, Z)) }
To resolve, we need to substitute Y for W, and Z for X, in other words, {Y/W, Z/X}, giving:
{ (p(Y, Z)), (¬p(Y, Z)) }
These resolve to give falsum (a contradiction
40
What are some issues with unification?
A constant is considered a “ground instance” and cannot be replaced
A variable cannot be unified with a term containing the variable
For example, X cannot be replaced with p(X) as this creates an infinite expression: p(p(p(p(…X)))
Unifying substitutions must be made consistently across all occurrences within the scope of the variable in both expressions being matched
Once a variable is bound to a constant, that variable may not be given a new binding in a future unification
41
Why have a methodology or notation for language semantics?
Programmers need to know what statements mean
Compiler writers must know exactly what language constructs do
Correctness proofs would be possible
Compiler generators would be possible
Designers could detect ambiguities and inconsistencies
42
What are some reasonable semantic rules that cannot be checked at reasonable cost, either statically, or by compiler-generated code at runtime?
All loops should terminate. Termination is undecidable.
Concurrent programs should be free from race conditions. Also undecidable.
Improper use of variants. Decidable but difficult.
Use of un-initialized variables. Decidable but difficult.
Deadlock freedom. Decidable but difficult.
The requirement that a program be unable to tell the difference between reference and value-result parameters. Decidable but difficult.
43
What is a predicate?
A souped up boolean since it can indicate relationships.
44
Why doesn't sum = sum + number work?
1. If sum is already instantiated, it cannot be reinstantiated. 2.If it is not instantiated, we cannot do unification on it.
45
What is call by value?
Copy going in
46
What is call by result?
copy going out
47
What is value result?
copy going in and copy going out.
48
What is call by reference?
pass a pointer
49
What is call by name?
re-evaluate actual parameter on every use. For simple variables, this is the same as call by reference. For actual parameters that are expressions, the expression is evaluated on each access.
50
What are erroneous programs?
Programs that rely on one implementation choice or the other.
51
What types of errors can compilers detect and not detect?
Compliers can detect static semantic errors, not dynamic semantic errors.
52
What is a synthesized attribute?
From children
53
What is a inherited attribute?
From parent.
54
What is referential transparency?
There are no side effects? Pros: Much easier to understand, no variables, they cannot change. Function cannot have state, thus only relies on values of parameters. "If 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.
55
What are some issues with overloading operator?
One symbol for two operations. Problem for maintainability and readability. Loss at complier error detection (omission of an operand should be a detectable issue)
56
What is a narrowing conversion?
Float to int; Converts an object to a type that cannot include all of the values of the original type.
57
What is a widening conversion?
int to float, object is converted to a type that can include at least approximations to all of the values of the original type.
58
What is coercion?
An implicit type conversion.
59
Do you think elimination of overloaded operators in your fav. language would be beneficial?
Yes or no, w/e. Benefits include enchance and increase readability, and minimize the compiler overhead (choosing the correct operator meaning).
60
Would it be a good idea to eliminate all operator precedence rules and require parentheses to show the desired precedence in expressions?
No, because it affects the flexibility provided by the language since only one way is used to show the precedence in expressions. Moreover, using parentheses will future more affects writability and in some cases readability.
61
What are the pros and cons of using unique closing reserved words on compound statements?
Using reserved word on compound statements will slightly affect writability, but in the other hand, it will enhance and increase language readability and flexibility and those two issues are significant.
62
What are the two phases of the compiler after parsing?
Semantic analysis and intermediate code generation
63
What is the principle job of the static semantic analyzer?
To enforce static semantic rules. Construct a syntax tree and gather info needed by the code generator.
64
What are BNF and context free grammers called?
Meta-languages, as they are well-suited for describing the syntax but not the semantics of a programming language.
65
What is the "decoration" of a parse tree?
Semantic analysis and intermediate code generation
66
What is an attribute grammer?
descriptive formalism that can describe both the syntax and the static semantics of a language. A context free grammer with the following rules: For each grammar symbol X there is a set A(X) of attribute values
Each rule has a set of functions that define certain attributes of the non-terminals in the rule
Each rule has a (possibly empty) set of predicates to check for attribute consistency
67
What are the three primary methods of describing dynamic semantics?
Operational, denotational, and axiomatic.
68
What is operational semantics?
Describe the meaning of a program by executing statements on a machine, either simulated or actual
The change in the state of the machine (memory, registers, etc.) defines the meaning of the statement. To use operational semantics for a high-level language, a virtual machine is usually used
69
What are the operational semantics of
for (count1 = 0, count2 = 1.0;
count1 <= 100.0;
sum = ++count1 + count2, count2 *= 2.5);?
```
count1 = 0
count2 = 1.0
loop:
if count1 > 10 goto out
if count2 > 100.0 goto out
count1 = count1 + 1
sum = count1 + count2
count2 = count2 * 2.5
goto loop
out: . . .
```
70
What are the use of operational semantics?
Language manuals, textbooks, teaching programming languages.
71
What is denotational semantics?
Most abstract semantics description method. Based on recursive function theory: define a mathematical object for each language entity, define a function that maps instances of the language entities onto instances of the corresponding mathematical objects.
72
What are the uses of denotational semantics?
Prove the correctness of programs, provide a rigorous way to think about the programs, aid with language design, create compiler generation systems. Because of complexity, little use to language users.
73
Operational vs Denotational?
In operational semantics, the state changes are defined by coded algorithms. In denotational semantics, the state changes are defined by rigorous mathematical functions.
74
What is Axiomatic Semantics?
Based on formal logic (predicate calculus). Original purpose: formal program verification. Axioms or interference rules are defined for each statement type in the language to allow transformations of logical expressions into more formal logical expressions. The logical expressions are called assertions.
75
What is a pre-condition?
An assertion that comes before a statement.
76
What is a post-condition?
An assertion following a statement.
77
What is the weakest pre-condition?
The least restrictive pre-condition that will guarantee the post condition.
78
What is the use of axiomatic semantics?
Proof of program correctness. The post condition for the entire program should be the desired result. Work backwards through the program to the first statement. If the precondition of the first statement is the same as the program specification, the program is correct.
79
What are some design issues with arithmetic expressions?
Operator precedence rules, operator associativity rules, order of operand eval, operand eval side effects, operator overloading, type mixing in expressions
80
What is the operator precedence rules?
define the order in which “adjacent” operators of different precedence levels are evaluated
81
What are some typical precedence levels of C-based language?
```
Parentheses (highest)
Unary operators (+ not necessary, -)
** (exponentiation – if the language supports it)
*, /
+, - (binary)
Equality testing
Assignment (lowest)
```
82
What are operator associativity rules?
define the order in which adjacent operators with the same precedence level are evaluated
Typically left-to-right, except **, which is right to left. Precedence and associativity rules can be overridden with parentheses.
83
In optimising operand evaluation, which is assumed safe and which is known as dangerous?
Communitative is assumed to be save, associativity is known to be dangerous. (a+b+c+d).
84
What is the operand evaluation order?
Variables: fetch the value from memory
Constants: sometimes a fetch from memory; sometimes the constant is in the machine language instruction
Parenthesized expressions: evaluate all operands and operators first
The most interesting case is when an operand is a function call
85
What is a functional side effect?
When a function changes a two-way parameter or a global variable.
86
What are some problems with functional side effects?
When a function referenced in an expression alters another operand of the expression, the result is unpredictable.
86
What are some problems with functional side effects?
When a function referenced in an expression alters another operand of the expression, the result is unpredictable.
87
What is imperative semantics?
The meaning of a statement is determine by its context - by examining local decelerations, scope, and the runtime environment of the program. (How)
87
What is imperative semantics?
The meaning of a statement is determine by its context - by examining local decelerations, scope, and the runtime environment of the program. (How)
88
What is declarative semantics?
The meaning of a statement is determined from the statement itself.(What).
88
What is declarative semantics?
The meaning of a statement is determined from the statement itself.(What).
89
What are some possible solutions to the functional side effects?
Write language definition that doesn't allow functional side effects by not allowing two-way parameters in functions, and no non-local references in functions. Advantage? It works! Disadvantage: Inflexibility of one-way parameters and lack of non-local references
89
What are some possible solutions to the functional side effects?
Write language definition that doesn't allow functional side effects by not allowing two-way parameters in functions, and no non-local references in functions. Advantage? It works! Disadvantage: Inflexibility of one-way parameters and lack of non-local references
90
What are the disadvantages to demand that operand evaluation order is to be fixed?
Limits compiler optimizations
90
What are the disadvantages to demand that operand evaluation order is to be fixed?
Limits compiler optimizations
91
What are some potential trouble with overloaded operators?
Loss of compiler error detection, loss of readability
91
What are some potential trouble with overloaded operators?
Loss of compiler error detection, loss of readability
92
What is a mixed-mode expression?
Has operands of different types.
92
What is a mixed-mode expression?
Has operands of different types.
93
Disadvantage of coercions?
They decrease the type error detection ability of the compiler.
93
Disadvantage of coercions?
They decrease the type error detection ability of the compiler.
94
What is short-circuit evaluation?
It is an expression in which the result is determined without evaluating all of the operands and/or operators.
94
What is short-circuit evaluation?
It is an expression in which the result is determined without evaluating all of the operands and/or operators.
95
What is a selection statement?
Provides the means of choosing between two or more paths of execution. Two-way selectors and multiple-way selectors
95
What is a selection statement?
Provides the means of choosing between two or more paths of execution. Two-way selectors and multiple-way selectors
96
What are multiple-way selection statements?
Allows the selection of one of any number of statements or statement groups
96
What are multiple-way selection statements?
Allows the selection of one of any number of statements or statement groups
97
Design Issues of multiple-way selection statements?
Control expression can only be an integer type
Selectable segments can be statement sequences, blocks, or compound statements
Any number of segments can be executed in one execution of the construct (there is no implicit branch at the end of selectable segments)
default clause is for unrepresented values (if there is no default, the whole statement does nothing)
97
Design Issues of multiple-way selection statements?
Control expression can only be an integer type
Selectable segments can be statement sequences, blocks, or compound statements
Any number of segments can be executed in one execution of the construct (there is no implicit branch at the end of selectable segments)
default clause is for unrepresented values (if there is no default, the whole statement does nothing)
98
What are some approaches to implementing multiple selectors?
Use multiple conditional branches
Store case values in a table and use a linear search of the table
When there are more than ten cases, a hash table of case values can be used
If the number of cases is small and more than half of the whole range of case values are represented, an array whose indices are the case values and whose values are the case labels can be used
98
What are some approaches to implementing multiple selectors?
Use multiple conditional branches
Store case values in a table and use a linear search of the table
When there are more than ten cases, a hash table of case values can be used
If the number of cases is small and more than half of the whole range of case values are represented, an array whose indices are the case values and whose values are the case labels can be used
99
What are some design issues for iteration control statements?
How is iteration controlled?
| 2. Where is the control mechanism in the loop?
99
What are some design issues for iteration control statements?
How is iteration controlled?
| 2. Where is the control mechanism in the loop?
100
What are some design issues with counter-controlled loops?
What is the type and scope of the loop variable?
Should it be legal for the loop variable or loop parameters to be changed in the loop body, and if so, does the change affect loop control?
Should the loop parameters be evaluated only once, or once for every iteration?
100
What are some design issues with counter-controlled loops?
What is the type and scope of the loop variable?
Should it be legal for the loop variable or loop parameters to be changed in the loop body, and if so, does the change affect loop control?
Should the loop parameters be evaluated only once, or once for every iteration?
101
What is unconditional branching?
Goto transfers execution control to a specified place in the program. Major concern is readability.
101
What is unconditional branching?
Goto transfers execution control to a specified place in the program. Major concern is readability.
102
What are guarded commands?
Designed by Dijkstra, to spport a new programming methodology that supported correctness (verification) during development. Basic idea is that if the order of evaluation is not important, the program should not specify one.
102
What are guarded commands?
Designed by Dijkstra, to spport a new programming methodology that supported correctness (verification) during development. Basic idea is that if the order of evaluation is not important, the program should not specify one.
103
What are the semantics of a selection guarded command?
```
Form
if ->
[] ->
...
[] ->
fi
Semantics: when construct is reached,
Evaluate all Boolean expressions “simultaneously”
If more than one is true, choose one non-deterministically
If none are true, it is a runtime error
```
103
What are the semantics of a selection guarded command?
```
Form
if ->
[] ->
...
[] ->
fi
Semantics: when construct is reached,
Evaluate all Boolean expressions “simultaneously”
If more than one is true, choose one non-deterministically
If none are true, it is a runtime error
```
104
What is the rationale for guarded commands?
Connection between control statements and program verification is intimate
Verification is impossible with goto statements
Verification is possible with only selection and logical pretest loops
Verification is relatively simple with only guarded commands
104
What is the rationale for guarded commands?
Connection between control statements and program verification is intimate
Verification is impossible with goto statements
Verification is possible with only selection and logical pretest loops
Verification is relatively simple with only guarded commands
