Logic Programming + Finite State Machines Flashcards
1
Q
What are the 5 data objects/terms
A
-Numbers
-Atoms
-Variables
-Compound terms
-Lists
2
Q
What is a number
A
A number may be either an integer or a floating point
quantity (e.g 42 or -816.22)
3
Q
What is an atom
A
An atom is a constant that does not have a numerical value. It
begins with a lowercase letter, or is quoted (e.g buffalo or ‘The X Files’)
4
Q
What is a variable
A
A variable stands for a term that is to be determined. It begins
with an uppercase letter or ‘_’ (e.g X or Person_A)
5
Q
What is a compound term
A
A compound term consists of a functor followed by a
sequence argument terms in brackets (e.g dog(rover))
6
Q
What is a list
A
A list is a structured data type made up of a sequence of terms
enclosed in square brackets and separated by commas (e.g [dog, X, 220, 500])
7
Q
What could a clause be
A
A clause may be
-a fact
-a rule
8
Q
What is a fact
A
A fact is taken to be true. It must be an atom or a compound term and end in a full stop (e.g christmas. or dog(fido).)
9
Q
What is a rule
A
A rule may be either true or false — only computation will
show. It must be an atom or a compound term, followed by a
“:-” followed by further atoms or a compound terms,
separated by commas (e.g grandfather(X, Y) :- father(X, Z), parent(Z, Y).)
10
Q
What is the declarative reading of h :- t1, t2, … tk
A
h is true if t1, t2, … tk are all true
11
Q
What is the procedural reading of h :- t1, t2, … tk
A
To compute h, compute t1, t2, … tk
12
Q
What is a predicate
A
A predicate is defined by several clauses
13
Q
What is a list
A
A list is made up of elements (possibly of different type)
enclosed in square brackets and separated by commas
14
Q
What is the Cons Notation
A
The “cons” (or “|”) notation allows one to represent a list as
being constructed from some leading elements and a list (e.g [1, 2, 3 | [4, 5]] = [1, 2, 3, 4, 5])
15
Q
sum_list( [], 0 ).
sum_list( [H|T], R )
:- sum_list( T, W ),
R is H + W.
In this predicate, what does H and T stand for
A
H is the head of the list, and T is the Tail
16
Q
What is the member predicate
A
The member predicate is true when an element is a member of a list
member_list( E, [E|] ).
member_list( E, [|T] )
:- member_list( E, T ).
17
Q
What is the append predicate
A
An append predicate appends two lists
append_list( [], Y, Y ).
append_list( [H|T], Y, [H|W] )
:- append_list( T, Y, W ).
18
Q
What is the reverse predicate
A
A reverse predicate reverses a list
reverse_list( [], [] ).
reverse_list( [H|T], R )
:- reverse_list( T, W ),
append( W, [H], R ).
19
Q
How can an atom be viewed as a list of ASCII codes
A
The “name” predicate allows one to convert from an atom to a list of integers
name( ace, X ).
X = [ 97, 99, 101 ]
20
Q
Not really anything but just an example of making characters uppercase idk it might be useful
A
make_upper( [], [] ).
make_upper( [H|T], [V|W] )
:- to_upper( H, V ),
make_upper( T, W ).
to_upper( A, B )
:- B is A - 32.
21
Q
What is the infix operator to carry out arithmetic
A
The operator ‘is’
22
Q
What happens if the left argument of the arithmetic is an unbound variable
A
Bind it to the result of evaluating evaluating the right argument, and succeed
23
Q
What happens if the left argument is a number, or a bound variable with a numerical values
A
Succeed if the right argument has the same numerical value
24
Q
What are the arithmetic operators
A
X + Y: sum of X and Y
X - Y: difference of X and Y
X * Y: product of X and Y
X / Y: quotient of X and Y
X // Y: integer quotient of X and Y
X mod Y: remainder when X is divided by Y
X ^ Y: value of X to the power Y
25
What are the arithmetic functions
abs( N, X ): absolute value of N
sin( N, X ): sine of N (in radians)
cos( N, X ): cosine of N (in radians)
log( N, X ): natural logarithm of N
sqrt( N, X ): square root of X
26
What are the relational operators
X =:= Y: X and Y are same value
X =\= Y: X and Y are not same value
X > Y: X greater than Y
X >= Y: X greater than or equal to Y
X < Y: X less than Y
X =< Y: X less than or equal to Y
27
What are the unification operators
X = Y: X and Y can be unified
X \= Y: X and Y cannot be unified
(ok so its supposed to be a backslash for the bottom one but its not appearing)
28
What is the only logical negation operator
\+ X not X
(backslash isnt working here either)
29
What is the closed-word assumption
What is stated is true; what is not stated is false
30
What does 'negation as failure' mean
Anything that cannot be
proved true is false.
31
How do you construct 'if-then-else'
By using -> ; (e.g maxof( X, Y, Z )
:- ( X =< Y
-> Z = Y
; Z = X
). )
32
How does Prolog attempt to satisfy a sequence of goals
It system attempts to
satisfy each goal in turn, working from left to right. If all the goals succeed in turn, the sequence of goals succeeds
as a whole.
33
A goal must be a call term, what is a call term
Either an atom, a compound
term, or an “is”, but not a number.
34
How does the Prolog system work to satisfy a single goal
It works through the
clauses in the database from top to bottom, examining those
clauses that have a functor and arity that unify with the goal.
(A functor is the atom part of a compound term and arity is the number of arguments)
35
What is unification
The matching algorithm used to choose a particular clause
36
How do two numbers unify
Two numbers unify if and only if they are the same
37
How do two atoms unify
Two atoms unify if and only if they are the same
38
How do variables unify
Two unbound variables, say A and T, always unify, with the
two variables bound to each other.
An unbound variable and a term that is not a variable always
unify, with the variable bound to the term.
39
How do two compound terms unify
Two compound terms unify if and only if they have the same
functor and the same arity, and their arguments can be unified
pairwise, working from left to right.
40
How do two lists unify
Two lists unify if and only if they have the same number of
elements and their elements can be unified pairwise, working
from left to right.
41
How do substitutions work
In general, the result of unification is a substitution
σ = X1/t1, X2/t2, . . . Xn/tn
where ti is a term to be substituted for variable Xi.
This substitution is carried forward to further unifications
42
What is backtracking
If any goal fails, the Prolog system tries to find another way of satisfying the most recently satisfied previous goal.
h :- t1, t2, ... tk.
43
How does a logic program generate permutations
It will generate one permutation at a time, on demand from the tester, backtracking to consider
further permutations.
44
Why do purists not like the modification of the database
They see as being against the spirit of logic programming. Like other advanced features, they need to be used with care
45
What is a classical expert system
-A database of elementary facts about the domain;
-Some domain rules for knowledge acquisition;
-Some inference rules for reasoning from data;
-A facility for generating explanations.
46
What are the 4 examples of classical expert systems
-Dendral;
-MYCIN;
-PROSPECTOR;
-SHRDLU.
47
What is Dendral
The 1965 Dendral system (a contraction of DENDRitic ALgorithm) generates all possible arrangements of a set of atoms, and searches through it for likely ones, consistent with
the rules of chemical valence.
The heuristics employed are based on judgment and chemical knowledge — experience and intuition.
48
What is MYCIN
The 1972 MYCIN system (many antibiotics have the suffix “-mycin”) is designed to assist physicians in the diagnosis of bacterial infections.
Knowledge is encoded as 350 decision rules which embody the clinical decision criteria of infectious disease experts.
49
What is PROSPECTOR
The 1976 PROSPECTOR system was designed for decision-making problems in mineral exploration. It aids geologists in evaluating exploration sites or regions for occurrences of ore deposits of particular types.
50
What is SHRDLU
The 1968 SHRDLU system allowed the user to communicate with the computer in natural language, moving objects and querying the state of a simplified “blocks world.”
51
What is blackboard architecture
In expert systems, a blackboard architecture is one where a shared “blackboard” is iteratively updated by a diverse group of knowledge sources, starting with a problem specification and ending with a solution.
The Prolog database readily supports this architecture.
52
What is the difference between static and dynamic predicates
A static predicate cannot be modified as the program runs — by default, predicates are static ones.
A dynamic predicate can be modified as the program runs — predicates may be declared as dynamic ones.
53
How do you add clauses to a database
A clause can be added to the database with:
* asserta( X ) — add a clause X at the beginning of the database;
* assertz( X ) — add a clause X at the end of the database;
* assert( X ) — add a clause X at the beginning of the database.
54
How do you delete clauses from the database
A clause can be removed from the database with:
* retract( X ) — remove a clause X from the database;
* retractall( X ) — remove all facts or clauses that unify with X from the database.
55
What issues can arise from having all functions at the top level?
Name space pollution can occur, clashes caused by reuse of the same name
56
In Haskell what does a where definition do?
A where definition allows one to name a value, and to use it in
an expression.
e.g
sumList :: [ Int ] -> Int
sumList []
= 0
sumList (x:xs)
= x + sxs
where
sxs = sumList xs
57
In Haskell what does a let definition do?
A let definition allows one to name a value, and to use it in an
expression
e.g.
lengthList :: [Int] -> Int
lengthList []
= 0
lengthList (x:xs)
= let
lxs = length xs
in
1 + lxs
58
Define Partial Application in Haskell
Partial application in Haskell refers to the process of supplying a function with fewer arguments than it expects, resulting in a new function that takes the remaining arguments. This allows you to create specialized versions of functions and promotes code reuse and composability.
e.g
-- Original function
add :: Int -> Int -> Int
add x y = x + y
-- Partial application
addThree :: Int -> Int
addThree = add 3
-- Example usage
result :: Int
result = addThree 4
59
Define Curried functions(Indian haha)
A function that takes multiple arguments may be converted into
a succession of functions that each take a single argument.
e.g.
add2 :: Int -> Int -> Int
60
Define uncurried form(not indian haha)
Functions of two or more arguments may also be defined in
uncurried form, this looks like:
multiply2 :: (Int, Int) -> Int
61
Define the pointfree style
The pointfree style means that the arguments of a function
are not explicitly named.
e.g.
minList :: [Int] -> Int
minList xs =
head (sort xs)
would be :
minList2 :: [Int] -> Int
minList2 =
head . sort
62
Note: Haskell functions can be defined using Lambda abstractions
idk what that is it doesnt say - comes later
63
What are the Standard type classes in Haskell
1. Eq;
2 Ord;
3 Show;
4 Read.
64
Define the EQ class
The Eq class provides (==) and (/=) methods.
All basic datatypes except for functions and IO are instances of
this class.
65
Define the Ord Class
The Ord class provides (<=), (<), (>) and (>=) methods.
All basic datatypes except for functions and IO are instances of
this class
66
Define the Show Class
The Show class provides the method
show :: a -> String
All basic datatypes except for functions and IO are instances of
this class
It's typically used for "unparsers" that output values
e.g.
digits :: Int -> String
digits n
| otherwise = digits d ++ [ chr (ord ’0’ + m) ]
where
(d, m) = n ‘divMod‘ 10
can be written as
digits2 :: Int -> String
digits2 n =
show n
| n < 10 = [ chr (ord ’0’ + n) ]
67
Define the read class
The Read class provides the method
read :: String -> a
All basic datatypes except for functions and IO are instances of
this class.
Is typically used for "parsers" that input values
e.g.
number2 :: String -> Int
number2 xs =
read xs
68
Define higher order functions and the three that we need to know
A higher-order function is one that takes a function as an
argument or returns a function as a result.
Three important examples are:
1 map
2 filter
3 foldr
69
Define the map function
The map function applies a function to list elements
70
Define the filter function
The filter function applies a predicate to pick list elements.
71
Define the foldr Function
The foldr function folds a function into list elements.
^idk what that means but coolio
72
Define a list comprehension
A list comprehension expresses one list in terms of the
elements of another. From the first list we generate elements,
which we test and transform to form elements of the result.
[ 2 * n | n <- [5,6,7] ]
73
What is Lazy Evaluation
A lazy functional programming language evaluates the
arguments of functions and of constructors only when
necessary to give a result and then only as far as necessary
to give a result.
74
Define a generator tester structure
The generator/tester structure has a generator component
that generates all values that might be solutions, and tester
component that filters out the values that actually are solutions.
75
What is meant by this statement?
Functional programs must not change the state of the world
when they do calculation
This refers to a key principle in functional programming known as referential transparency or immutability.
In functional programming, functions are expected to be referentially transparent, meaning that their output is solely determined by their input and they have no side effects. This principle extends to the idea that functions should not modify external state or have observable interactions with the outside world during their execution.
Bottom line: there must be no side-effects
76
What is an Action in Haskell
An action is a value of type IO a that, when performed, may do
some input/output, before delivering a value of type a.
77
What does the Then operator do in Haskell
The then operator, (>>), performs a first action, discards the result, and performs a second action.
e.g.
putStr2 :: String -> IO ()
putStr2 s
= putStr s >> putStr s
78
What does the Bind Operator do Haskell?
The bind operator, (>>=), passes the result of performing a
first action to a (parameterised) second action.
e.g.
snooper :: IO ()
snooper
= readFile "/etc/passwd" >>=
putStrLn
(>>=) :: IO a -> (a -> IO b) -> IO b
79
What does the do notation do in Haskell?
The do notation provides a more convenient notation.
test :: String -> String -> IO String
test fn s
= do writeFile fn s
readFile fn
main :: IO ()
main
= do s <- test "a.txt" "a"
putStrLn s
80
Define the Lambda calculus
The lambda calculus (or λ-calculus) is a formal system for
expressing computation through abstraction and application,
using variable binding and substitution.
81
In the Lambda calculus what are constants
The constants are things like integers, characters, booleans
and operators.
Strictly, speaking, constants are unnecessary.
82
In Lambda calculus what are variables
A variable is a name
^all it says
83
In Lambda calculus what are Applications
An application of a function to an argument is written by
juxtaposition.
Parentheses disambiguate.
looks like (fa)
84
In Lambda calculus what are Functions
A function is described by a λ-abstraction.
A λ-abstraction binds a variable; if there is no λ-abstraction,
then the variable is free
85
What are the three conversion rules in the Lambda calculus
1 alpha conversion;
2 beta conversion;
3 eta conversion
86
What is Alpha conversion
Alpha conversion (α-conversion) allows one to rename bound
variables.
e.g.
(λx.x + 2) ⇒ (λw.w + 2)
87
What is Beta conversion
Beta conversion (β-conversion) allows one to apply a lambda
abstraction to an argument.
(λx.x + 2) 9 ⇒ 9 + 2
88
What is Eta Conversion
Eta conversion (η-conversion) allows one to drop a
λ-abstraction over a function.
(λx.f x) ⇒ f
89
What are some properties(4) of Parallel functional programming
1 concurrency is implicit, not explicit;
2 any shared data needs no protection;
3 reasoning remains easy;
4 results remain determinate
90
What does the statement "Functional programs are blessed with an abundance of parallelism" mean?
Because expressions lack side-effects, they can be evaluated
in any order, or in parallel.
91
What does this statement mean?
Functional programs are cursed by an embarrassment of
parallelism.
Just because an expression could be evaluated in parallel, it
does not mean that it should be evaluated in parallel
92
What are three things that should be considered before creating a task to evaluate an expression
1 is the result going to be useful?
2 is the computation large enough?
3 is there spare processing capacity?
93
What does the Par annotation do?
The pseudo-function par evaluates its arguments in parallel: x
on another processor (if possible), and y on the current
processor.
e.g.
par :: a -> b -> b
par x y = y
94
What does the Seq annotation do?
The pseudo-function seq evaluates its arguments in sequence:
x then y
e.g
seq :: a -> b -> b
seq ⊥ y = ⊥
seq x y = y
95
How is output done in Prolog
With the "write" predicate which displays a term structure, "nl" displays a new line and "writeln" combines the two
96
How is input done in Prolog
With the “read” predicate, which reads a term
97
What are the three classical forms of parallelism in Prolog
-“unification parallelism”;
-“or-parallelism”;
-“and-parallelism”
98
What is unification parallelism
Unification parallelism arises during the unification of the
arguments of a goal with the arguments of a clause head with
the same name and arity. Unification parallelism unifies the arguments of complex structures in parallel.
(e.g [1, f(4)] = [1, R] as R is bound to f(4) i think)
99
Why might it be hard to implement unification parallelism
It might be hard to implement unification parallelism because a substitution must be read/written by multiple processors.
100
What is or-parallelism
Or-Parallelism arises when a goal may be unified with more than one clause in parallel. Or-Parallelism explores the search space generated by the presence of multiple clauses in parallel.
(e.g
f(a).
f(b).
f(c).
^that is three separate functions happening)
101
Why might it be hard to implement or-parallelism
It might be hard to implement or-parallelism because the
parallel implementation must still have sequential behaviour.
102
What is and-parallelism
And-Parallelism arises when more than one subgoal may be
satisfied in parallel. And-Parallelism exploits the presence of more than one
subgoal that may be satisfied in parallel.
(e.g f(a) :- e(1), f(b).)
103
Why might it be hard to implement and-parallelism
It might be hard to implement and-parallelism because the
parallel implementation must account for data dependencies
between subgoals
104
What happened on 2nd September 1945
General Douglas MacArthur invited the
representatives of Japan and the Allies to sign a surrender
document ending World War 2.
(not relevant but its in the lecture notes and made me laugh)
105
What did the Ministry of International Trade and Industry (MITI) do
MITI excelled in working with the private sector
closely but neutrally, knowing different plans and problems of
individual firms, and coordinating and guiding them. They were repsonsible for the Fifth Generation Project
106
What is the Fifth Generation Project
The Fifth Generation Project was intended to:
* make Japan a leader in the computer industry by
developing knowledge information processing systems
built using logic programming.
* stimulate original research, making the results widely
available, so refuting accusations that Japan exploits
knowledge from abroad without contributing any of its own
107
Why was logic programming chose for the Fifth Generation Project
Logic programming was chosen because it unifies innovations in:
-software engineering;
-databases;
-artificial intelligence;
-computer architecture.
108
Explain software engineering in terms of logic programming
In the field of software engineering, logic programs can serve as executable specifications, that can be made more efficient by program transformation
109
Explain databases in terms of logic programming
In the field of databases, logic programs have been shown to
be adequate both as a query language, and for describing
integrity constraints
110
Explain artificial intelligence in terms of logic programming
In the field of artificial intelligence, logic programs naturally implement rules of the form A if B1 and . . . and Bn
111
Explain computer architecture in terms of logic programming
In the field of computer architecture, logic programs provide a way to overcome the von Neumann bottleneck through single assignment.
112
What is a finite state automaton
A Finite State Automaton (FSA), is a model of computation based on the idea of a system changing state due to inputs supplied to it, until a final or acceptor state is reached.
113
Why a finite automata useful
They are a useful model for many important kinds of
hardware and software (e.g representing process states on a processor)
114
What are the central concepts of automata theory
-alphabets;
-strings;
-languages.
115
What is an alphabet in terms of FSA
An alphabet, Σ, is a finite, nonempty set of symbols.
Example:
Σ = a, b, . . . z
116
What is a string in terms of FSA
A string is a finite sequence of symbols chosen from some
alphabet. The set of all possible strings over an alphabet Σ is Σ∗.
Example:
bccd is a string drawn from Σ = a, b, . . . z.
117
What is a language in terms of FSA
If Σ is an alphabet, and L ⊆ Σ∗, then L is a language over Σ.
Example:
{abc, def, ghi} is a language drawn from Σ∗, where
Σ = a, b, . . . z.
118
What does a deterministic finite automata (DFA) consist of
-a finite set of states;
-a finite set of input symbols;
-a transition function;
-a start state;
-a set of accepting or final states.
119
How are states represented in DFA
The finite set of states is often denoted Q.
Each state may be drawn as a circle.
120
How are input symbols represented in DFA
The finite set of input symbols is often denoted Σ.
Each symbol may be drawn as a label of a transition arrow (so just either numbers or letters labelling the arrows)
121
How are transition functions represented in DFA
The transition function may be described by a number of cases,
δ(p, a) = q.
Each case, δ(p, a) = q, may be drawn as an arrow from the
circle for p to the circle for q, labelled a.
122
How is the start state represented in DFA
The start state, q0, is one of the states in Q.
The arrow drawn into the start state q0 is labelled Start.
123
How is the accepting/final state represented in DFA
The accepting or final states are a subset of Q. The machine
may halt in accepting states provided it has no input left.
All other states become rejecting states if there is no input left.
Final or accepting states are marked by double circles.
124
What is the difference between deterministic and non-deterministic automata
* on each input, a deterministic automaton can transition
from its current state to another state;
* on each input (or on no input), a nondeterministic
automata can transition form its current state to several
states.
125
What is regular expression
A regular expression provides an algebraic (and so
declarative) description of a deterministic or nondeterministic
finite state automaton.
126
What are the three operations for regular expressions
The algebra of regular expressions combines constants and variables denoting languages using three operations:
-closure;
-concatenation;
-union.
127
What is the closure operation
The closure of a language L is denoted L∗.
It represents the set of those strings that can be formed by
taking any number of strings from L, and concatenating them.
The “*” operator has the highest precedence — it applies to the
smallest sequence of symbols to its left.
128
What is the concatenation operation
The concatenation of languages L and M is denoted LM.
It is the set of strings that can be formed by taking any string in
L and appending any string in M.
Concatenation has the next highest priority — expressions that
are juxtaposed are grouped together.
129
What is the union operation
The union of two languages L and M is denoted L + M.
It is the set of strings that are either in L or M, or both.
The “+” operator has the lowest priority — expressions may be
grouped by unions in any order.
130
Just some examples of regular expression
0* + 1 means any number of 0s or a 1
101* means 10 and any number of 1s
10 + 01 means 10 or 01
0(10)* means 0 and any number of 10s
