ECM2418 Computer Languages and Representation Flashcards
Haskell inbuilt functions to use
filter
foldr
map
even
odd
(++)
sel
not
polymorphic type of conditional functor (even, odd) haskell
(a -> Bool)
polymorphism syntax haskell
function :: a..
list split haskell
(x:xs)
list split Prolog
([A|AS])
Prolog predicates to remember
reverse
between
findall
permutations
(EXAMPLE) what’s stopping this predicate from working
alpha(XS).
it’s missing base cases:
alpha([]).
alpha([_]).
Functional programming
- Programs are represented by expressions
- Computation is implemented by reduction
- The foundation is the lambda calculus
- Functions akin to mathematics functions
Logic Programming
- Programs are represented by clauses
- Computation is represented by proof
- The foundation is the first-order logic
Finite State Machines
Simple idea occurring throughout computer science
- Programs are represented by state machines
- Computation is represented by transitions
tuples in haskell
(a1,a2,a3)
can have different types in one tuple
Recursive definitions in haskell
Contains a base case that can act as a halt for the function to return a value
Guards in Haskell
|
a boolean expression that must be true for the equation to apply
acts similarly to if and else
guard keywords
where
otherwise
generate-and-select design pattern
the generator constructs a large number of values that might be solutions to a problem
the selector filters out those values that are solutions to the problem
explanations of the productivity paradox
1) Uneven/concentrated gains
2) Implementation lags
3) Mismeasurements
uneven/concentrated gains
One explanation of the productivity paradox is an uneven/concentrated distribution of gains - the gains are in few productive firms and sectors with limited weight int the overall economy
Implementation lags
Another explanation of the productivity paradox is implementation lags - it takes considerable time for new technologies to achieve critical mass, or for necessary complementary ones appear. There are gains, but it takes a long time time
Mismeasurement
adopting new technologies can lead workers to move from more productive adopting sectors to less productive ones, and so to negligible aggregate productivity growth
Behind the scenes, Artificial Neural Networks (ANNs) work as follows:
1) The core ANN is trained on text from the Internet to respond to a prompt with a list of most probable next words after the prompt
2) The core ANN is tweaked by scoring its responses to sample queries. A second ANN is trained on these scores to predict the most likely one to be assigned to a prompt
3) The second ANN is used in reinforcement learning to adjust the weights in the core ANN so that its outputs are even more likely to satisfy humans
4) Sometimes, data from user responses to LLM responses is fed back to fine-tune for still better results
Among the concerns when using Large Language Models are:
- copyright
- education
- code quality
- code security
- not an expert
Copyright and LLMs
although the code produced is the melding of that form many sources, there may still be some licensing problems
Education and LLMs
good solutions to many assignments can be completed directly, reducing their challenge and worth
code quality and LLMs
There is no guarantee of code quality when using a large language model, and a code review will need to be conducted before code is deployed
Code security and LLMs
There is no guarantee of code security when using a LLM, and a security audit will need to be conducted before code is deployed
LLMs are not experts
it does not know that it does not know, able to confabulate is necessary, mixing high-quality text with low-quality rubbish
List comprehensions
[ | ]
used to test and transform a list
conditionals in haskell
case _ of _ ->
or
if _ then _ else
cody copying is
error-prone
inefficient
Backtracking in Prolog
If any goal fails, the Prolog system tries to find another way of satisfying the most recently satisfied previous goal
Alternative proofs are requested with NEXT, forcing backtracking
Successive permutations of a clause can be achieved via backtracking
atoms in Prolog
An atom is a constant that does not have a numerical value. It begins with a lowercase letter, or is quoted
It is possible to split atoms into lists of ASCII codes, and to make atoms from lists of ASCII codes
This makes Prolog and other logical languages a great fit for Natural Language Processing
Prolog’s Closed World Assumption (CWA)
Anything that cannot be proven to be true based on the facts and rules in the program is assumed to be false
For example, if a fact likes(mary, pizza) exists but likes(mary, sushi) does not, Prolog assumes likes(mary, sushi) is false.
Declarative Semantics in Prolog
Logic programs describe what is true, not necessarily how to compute it.
Example: Writing
ascending([X, Y | XYS]) :-
X =< Y,
ascending([Y | XYS]).
specifies the property of an ascending list, not how to iterate through the list procedurally.
Horn Clauses Prolog
Programs are expressed as a set of Horn clauses, which are a type of logical implication:
Facts: Unconditionally true statements, e.g., parent(john, mary). Rules: Conditional statements, e.g., ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).
Resolution Prolog
The main inference mechanism, where Prolog tries to resolve goals by matching them against facts or rules.
Unification Prolog
Prolog matches variables with constants or other variables to make clauses work. It ensures terms are syntactically compatible.
Why might one discourage the use of the assert and retract predicates in prolog
Assert adds a predicate to the running program, and the retract predicate removes.
They make reasoning about the program harder
The program being run changes over time
Perhaps less efficient
code gets created and destroyed on program run-time
Unlike Haskell programs, Prolog programs are not strongly typed. What does this mean, and why might it cause problems?
This means that due to programmer misunderstandings or errors, predicates may be applied to arguments of unexpected types, predicate calls may fail due to unification errors, incorrect results. This failure will be silent and hard to debug
X // Y vs X / Y
X // Y represents the integer quotient of X and Y, while X / Y can compute a floating point result
arithmetic functions
abs(N, X)
sin(N, X)
cos(N, X)
log(N, X)
sqrt(N, X)
absolute value of N
sine of N in radians
cosine of N in radians
natural logarithm of N
square root of N
Relational operators
X =:= Y
X == Y
X > Y
X >= Y
X < Y
X =< Y
X and Y are same value
X and Y are not same value
X is greater than Y
X is greater than or equal to Y
X is less than Y
X is less than or equal to Y
Unification operators
X = Y
X = Y
X and Y can be unified
X and Y cannot be unified
Which of these terms unifies:
* 42 and [42];
* anna and X;
* woman(anna) and woman(X);
* [’A’,’B’,’C’] and [P, Q, R];
* loves(X, jo) and loves(jim, X)
- anna and X;
- woman(anna) and woman(X)
- [’A’, ’B’, ’C’] and [P, Q, R]
- loves(X, jo) and loves(jim, X)
logical negation operator
+ X means Not X
Note the closed-word assumption — what is stated is true; what is not stated is false.
Also note negation as failure — anything that cannot be proved true is false
The Cut Predicate, ‘!’, in Prolog
prevents backtracking
Although backtracking is a fundamental part of the process by
which goals are satisfied, it can sometimes be too powerful.
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;
examples of classical expert system
Dendral
MYCIN
PROSPECTOR
SHRDLU
Dendral, 1965
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.
MYCIN, 1972
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
PROSPECTOR, 1976
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.
Static Predicates
cannot be modified as the program runs —
by default, predicates are static ones.
Dynamic Predicates
can be modified as the program runs —
predicates may be declared as dynamic ones.
dynamic(droid/1).
Adding clauses to the database
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.
Deleting clauses from the database
retract(X) — remove clause X from the database;
retractall(X) — remove all facts/clauses that unify with X from the database
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,
Logic programming was chosen for the Fifth Generation Project because it unifies innovations in:
1 software engineering;
2 databases;
3 artificial intelligence;
4 computer architecture.
Software Engineering and Logic programming
In the field of software engineering, logic programs can serve as executable specifications, that can be made more efficient by program transformation
databases and 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
Artificial Intelligence and Logic programming
In the field of artificial intelligence, logic programs naturally implement rules of the form
A if B1 and . . . and Bn
Computer Architecture and Logic Programming
Logic programs provide a way to overcome the Von Neumann Bottleneck through single assignment
Inference Machines
Several hundred Personal Sequential Inference Machine (PSI) workstations were built and installed.
The largest Parallel Inference Machine (PIM), PIM/p had 64 × 8 processing elements
Three “classical forms of parallelism in Prolog”
unification-parallelism
or-parallelism
and-parallelism
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.
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
regular expression algebra uses 3 different operations
closure
concatenation
union
Closure, L∗
represents the set of those strings that can be formed by taking any number of strings from L, and concatenating them
has the highest precedence, applying to the smallest sequence of symbols to its left
Concatenation, LM
the set of strings that can be formed by taking any string in L and appending any string in M
second highest priority - expressions that are juxtaposed are grouped together
Union, L + M
set of strings either in L or M or both
lowest priority - expressions may be grouped by unions in any order.
0* + 1
any number of 0s or a 1
101*
10 and any number of 1s
10 + 01
10 or 01
0(10)*
0 and any number of 10s
Five advantages that the Japanese Fifth Generation Project saw in using
Prolog programs as specifications were:
(i) specifications are naturally described by logical relation-
ships [1 mark];
(ii) logical relationships are naturally described by Prolog pro-
grams [1 mark];
(iii) specifications and Prolog programs are therefore always consis-
tent [1 mark];
(iv) Prolog specifications/programs are executable, albeit rather ineffi-
ciently [1 mark].
(v) Prolog specifications/programs can be transformed into more
efficient ones with machine assistance [1 mark].
