Transcript Difference Lists

Programming Techniques
[email protected]
http://www.knoesis.org/tkprasad/
cs774 (Prasad)
L17ProgTech
1
Generalization/Abstraction
Analogy:
[a,b,c]  [f(a),f(b),f(c)]
maplist(_,[],[]).
maplist(P,[X|T],[NX|NT]) :G =.. [P,X,NX],
call(G),
maplist(P,T,NT).
(G  p(N,NX))
cs774 (Prasad)
L17ProgTech
2
Application
transpose([],[]).
transpose([[]|_],[]) :- !.
transpose([R|Rs],[C|Cs]) :maplist(first,[R|Rs],C),
maplist(rest,[R|Rs],RC),
transpose(RC,Cs).
first([H|T],H).
rest([H|T],T).
/* Built-in maplist exists*/
cs774 (Prasad)
L17ProgTech
3
Enhancing Efficiency
• Interpreted vs Compiled code (order of
magnitude improvement observed)
• Improving data structures and algorithm
• 8-Queens problem, Heuristic Search, Quicksort, etc
• Tail-recursive optimization
• Memoization
• storing partial results / caching intermediate results
• Difference lists
• DCGs
cs774 (Prasad)
L17ProgTech
4
(cont’d)
• Prolog implementations that index on the
first argument of a predicate improve
determinism.
• Cuts and other meta-programming
primitives can be used to program in new
search strategies for controlled
backtracking.
cs774 (Prasad)
L17ProgTech
5
Optimizing Fibonacci Number Computation
fib(0,0) :- !.
fib(1,1) :- !.
fib(N,F) :N1 is N - 1, N2 is N1 -1,
fib(N1,F1), fib(N2,F2),
F is F1 + F2.
?-fib(5,F).
Complexity: Exponential time algorithm
cs774 (Prasad)
L17ProgTech
6
Fibonacci Call Tree
with Parameter Value
cs774 (Prasad)
L17ProgTech
7
(cont’d)
f(0,F,_,F).
f(1,_,F,F).
f(N,Fpp,Fp,F) :- N >= 2,
N1 is N – 1, F0 is Fp + Fpp,
f(N1,Fp,F0,F).
fib(N,F) :- f(N,0,1,F).
?-fib(5,F).
Complexity: Linear time algorithm
(tail-recursive version)
cs774 (Prasad)
L17ProgTech
8
Last call optimization
• Activation record normally stores a
continuation and a backtrack point, to be
used when the goal succeeds or fails
respectively.
p :- q, r.
p :- s.
– LCO avoids allocating a new activation record
for s, but rather reuses one for p.
cs774 (Prasad)
L17ProgTech
9
Caching intermediate results
• Instead of explicitly modifying the code to
improve performance, XSB uses tabling to
store intermediate results and avoids
recomputing earlier goals.
• Ironically, double-recursive (exponentialtime) Fibonacci Number definition serves as
a benchmark for testing efficiency of
implementation of recursion!
cs774 (Prasad)
L17ProgTech
10
Different Lists : Motivation
STACK
push
pop
Array-Impl.
O(1)
O(1)
Linked-list Impl.
O(1)
O(1)
QUEUE
enqueue
dequeue
Circular Buffer or
Linked List Impl.
(front& rear
pointer)
O(1)
O(1)
Linked-List Impl.
(front but no rear
pointer)
O(1)
O(n)
cs774 (Prasad)
L17ProgTech
11
(cont’d)
• In Prolog, pointers implementing list structures are
not available for inspection/manipulation. Hence,
complexity of enqueue (resp. dequeue) is O(1) and
that of dequeue (resp. enqueue) is O(n).
enqueue(Q,E,[E|Q]).
dequeue([E],E).
dequeue([_|F|T],E) :dequeue([F|T],E).
• Difference list is a techqniue to get O(1)
complexity for both the operations.
cs774 (Prasad)
L17ProgTech
12
Difference Lists : Details
• Represent list L as a difference of two lists
L1 and L2
– E.g., consider L = [a,b,c] and various L1-L2
combinations given below.
cs774 (Prasad)
L1
L2
[a,b,c]
[]
[a,b,c,d,e]
[d,e]
[a,b,c|T]
T
[a,b,c,d|T]
[d|T]
L17ProgTech
13
Benefit
L = L1 – L2
• Both enqueue and dequeue are O(1)
operations obtained by cons-ing an element
to L1 and L2 respectively.
enqueue(L1-L2, E, [E|L1] – L2).
dequeue(L1-L2, E, L1 – [E|L2]).
E.g.,
enqueue([a]-[], b, [b,a] – []).
dequeue([a]-[], a, [a]–[a]).
cs774 (Prasad)
L17ProgTech
14
Append using Difference Lists
append(X-Y, Y-Z, X-Z).
• Ordinary append complexity = O(length of first list)
• Difference list append complexity = O(1)
X-Z
X
X-Y
Y
Y
Y-Z
Z
Z
cs774 (Prasad)
L17ProgTech
Z
15
(cont’d)
append(X-Y, Y-Z, X-Z).
?-append([a,b,c|L]-L, [1,2|M]-M, N).
X=[a,b,c|L]
Y = L
Y = [1,2|M]
Z = M
X – Z = N
N= [a,b,c|[1,2|Z]]-Z
N= [a,b,c,1,2|Z]]-Z
cs774 (Prasad)
L17ProgTech
16
Restriction
append(X-Y, Y-Z, X-Z).
?-append([a,b,c|[d]]-[d], [1,2]-[], N).
• Fails because the second lists must be a variable.
Incomplete data structure is a necessity.
cs774 (Prasad)
L17ProgTech
17
Interpreter-based Semantics vs
Declarative Semantics
• IS is an over-specification but may provide
an efficient implementation.
• DS specifies correctness criteria and may
permit further optimization.
• Overall research goal: Characterize classes
of programs for which the declarative and
the procedural semantics coincide.
cs774 (Prasad)
L17ProgTech
18
Relational Algebra
(Operations on Relations)
• Select, Project, Join, Union, Intersection,
difference
– Transitive closure cannot be expressed in terms
of these operations.
• A query language is relationally complete if
it can perform the above operations.
cs774 (Prasad)
L17ProgTech
19
Deductive Databases : Datalog
(Function-free/Finite Domain Prolog)
• Datalog + Negation is relationally complete.
• What effects query evaluation efficiency?
– Characteristics of data (cyclic vs acyclic)
– Ordering of rules and body literals
– Search strategy (top-down vs bottom-up)
• Tuple-at-a-time vs Set-at-a-time
cs774 (Prasad)
L17ProgTech
20
Middle Ground:
Top-down vs Bottom-up
• Improve efficiency by
caching. (cf. tabling)
• Remove
Incompleteness by
loop detection.
• Focused search.
• Propagate bindings in
the query. (cf. Magic
sets)
In general, the efficiency of query evaluation can be
improved by sequencing goals on the basis of
their bindings and dependencies among rule literals.
cs774 (Prasad)
L17ProgTech
21
Heuristics for rearranging rules and
body literals for efficiency
• Order body literals by decreasing values of
failure probability
• Order rules by decreasing values of success
probability
• Order body literals to maximize
dependencies among adjacent literals.
• Metric for comparison – e.g., extent of base
relation graphs inspected
cs774 (Prasad)
L17ProgTech
22
Backtracking
• Chronological
• Dependency directed
– focus on the reason for backtracking
ans(X,Y) :- p(X), q(Y), r(X).
p(1). p(2). p(3).
q(1). q(2). q(3).
r(3).
cs774 (Prasad)
L17ProgTech
23
Data Dependency Graph
p(X), r(X),
ans(X,Y) :-
q(Y),
If r(X) fails,
then backtrack to p(X)
rather than q(Y).
cs774 (Prasad)
L17ProgTech
24
Indexing
• Prolog indexes on
– predicate symbol and arity
– principal functor of first argument (cf. constant
-> hash)
• Randomly accessed rule groups
p(a) :- …
p(22) :- …
p(f(X)) :- …
p([]) :- …, p([a]) :- …,
cs774 (Prasad)
L17ProgTech
…
25
Robert Kowalski
• Algorithm = Logic + Control
Niklaus Wirth
• Programs = Data Structures + Algorithms
cs774 (Prasad)
L17ProgTech
26