Does Prolog do Dynamic Programming automatically?
wht
en.wikipedia.org/wiki/Dynamic_programming), I am almost convinced that
Prolog does at least some of this automatically. The fact that it
keeps track of bound variables as it searches for solutions while not
redoing the calculations that depend on those variables indicates that
a sort-of Dynamic Programming algorithm is in place.
I know that the Memo/Tabling Prolog patterns are also easy to
implement but they could actually take longer in certain cases, since
much of the search space reduction is taken care automatically. Any
thoughts?
fodor
> Looking at the definition of Dynamic Programming (http://
> en.wikipedia.org/wiki/Dynamic_programming), I am almost convinced that
> Prolog does at least some of this automatically.
Depends on how you implement your programs. I wouldn't say that in
basic prolog you get any advantage than in any other programming
language. I guess you are referring to the fact that you can keep and
the list of intermediate results and compute them in such an order so
you can always increase the level of the program.
In one of this year's posts on this list (comp.lang.prolog) Bart
Demoen showed a program called "the poor man's tabling" which might be
considered an example of dynamic programming in Prolog.
With tabling you get dynamic programming for free. I see that you know
that from your post below.
Chip Eastham
> en.wikipedia.org/wiki/Dynamic_programming), I am almost
> convinced that
> Prolog does at least some of this automatically.
I don't see clearly what you are getting at.
A hallmark of "dynamic programming" is embedding
a given problem into a larger setting, often with
the twin advantages that:
(1) the larger problem, although bigger in size,
is a simpler kind of problem, and
(2) the larger problem does not need to be solved
in its entirety in order to settle the original
problem,
leading to an overall savings in complexity in
comparison with naive algorithms for the original
problem. Richard Bellman is considered "the
father" of dynamic programming, at least in the
context of continuous optimization problems.
In a discrete context Dijkstra's shortest path
algorithm can be viewed as a dynamic programming
solution.
But does Prolog "automatically" do this? You
wrote:
> The fact that it keeps track of bound variables
> as it searches for solutions while not redoing
> the calculations that depend on those variables
> indicates that a sort-of Dynamic Programming
> algorithm is in place.
Hmm. While dynamic programming algorithms are
recursive in nature, and Prolog's depth-first
search strategy can be so, some ingenuity is
typically required of the Prolog programmer to
achieve the "bottom-up" efficiency of dynamic
programming methods.
> I know that the Memo/Tabling Prolog patterns
> are also easy to implement but they could
> actually take longer in certain cases, since
> much of the search space reduction is taken care
> automatically. Any thoughts?
Memoization can help in computing lower "rungs"
of the computations once and reusing them. It's
certainly worth playing around with for the sake
of learning/experience.
However I think functional languages (Haskell,
ML, etc.) may come a lot closer to your idea
of "automatic" dynamic programming.
regards, chip
wht
> Memoization can help in computing lower "rungs"
> of the computations once and reusing them. It's
> certainly worth playing around with for the sake
> of learning/experience.
>
I have run across people who embed a Boolean flag into their
procedural language structure saying that "this value has already been
calculated, do not calculate this again". This is in the context of
some optimization sweep algorithm. When I suggest that Prolog does
this for free with bound/unbound variables, they don't seem to
comprehend it.
I guess this is just a result of having a depth-first, backtracking
algorithm for free. I am trying to get justification that some
problems require less work to get done.
I tried the "memoization" Dynamic Programming algorithm that is on the
Prolog Wikipedia page in the context of one of my own programs, and it
actually made the execution run slower. http://en.wikipedia.org/wiki/Prolog,
see under the Dynamic programming header
:- dynamic(stored/1).
memo(Goal) :- ( stored(Goal) -> true ; Goal, assertz(stored(Goal)) ).
lcs([], _, []) :- !.
lcs(_, [], []) :- !.
lcs([X|Xs], [X|Ys], [X|Ls]) :- !, memo(lcs(Xs, Ys, Ls)).
lcs([X|Xs], [Y|Ys], Ls) :-
memo(lcs([X|Xs], Ys, Ls1)), memo(lcs(Xs, [Y|Ys], Ls2)),
length(Ls1, L1), length(Ls2, L2),
( L1 >= L2 -> Ls = Ls1 ; Ls = Ls2 ).
I can understand this to a degree since you need to have a computation
that is somewhat intensive to compensate for the extra lookup.
Chip Eastham
> On Oct 28, 11:34 am, Chip Eastham <hardm...@gmail.com> wrote:> Memoization can help in computing lower "rungs"
> > of the computations once and reusing them. It's
> > certainly worth playing around with for the sake
> > of learning/experience.
>
> Thank you.
>
> I have run across people who embed a Boolean flag into their
> procedural language structure saying that "this value has already been
> calculated, do not calculate this again". This is in the context of
> some optimization sweep algorithm. When I suggest that Prolog does
> this for free with bound/unbound variables, they don't seem to
> comprehend it.
>
> I guess this is just a result of having a depth-first, backtracking
> algorithm for free. I am trying to get justification that some
> problems require less work to get done.
>
> I tried the "memoization" Dynamic Programming algorithm that is on the
> Prolog Wikipedia page in the context of one of my own programs, and it
> see under the Dynamic programming header
>
> :- dynamic(stored/1).
>
> memo(Goal) :- ( stored(Goal) -> true ; Goal, assertz(stored(Goal)) ).
>
> lcs([], _, []) :- !.
> lcs(_, [], []) :- !.
> lcs([X|Xs], [X|Ys], [X|Ls]) :- !, memo(lcs(Xs, Ys, Ls)).
> lcs([X|Xs], [Y|Ys], Ls) :-
> memo(lcs([X|Xs], Ys, Ls1)), memo(lcs(Xs, [Y|Ys], Ls2)),
> length(Ls1, L1), length(Ls2, L2),
> ( L1 >= L2 -> Ls = Ls1 ; Ls = Ls2 ).
>
> I can understand this to a degree since you need to have a computation
> that is somewhat intensive to compensate for the extra lookup.
I'm not sure your code is doing what
you expect it to.
Consider lcs([a,b],[b,a],Z). The 1st
three clauses don't apply, so we have
the two subgoals lcs([b],[b,a],Ls1) and
lcs([a,b],[a],Ls2), each of which returns
a list of length 1: Ls1 = [b], Ls2 = [a].
So Z = [b], but if the first two arguments
had been reversed you'd have Z = [a].
Others can probably give you more feedback
about making memoization efficient. I do
not use it, but here you must rely on the
indexing of dynamic predicates to provide
results quickly. Since the length of lists
is required by the code above, one approach
to improving performance would be to add
the length into the memo'ed results.
regards, chip
wht
> I'm not sure your code is doing what
> you expect it to.
>
> Consider lcs([a,b],[b,a],Z). The 1st
> three clauses don't apply, so we have
> the two subgoals lcs([b],[b,a],Ls1) and
> lcs([a,b],[a],Ls2), each of which returns
> a list of length 1: Ls1 = [b], Ls2 = [a].
>
> So Z = [b], but if the first two arguments
> had been reversed you'd have Z = [a].
>
I'm sorry but the specific list processing wasn't the code I was
evaluating. That was just the context of how memoization was applied
on that particular Wikipedia page.
I just reused the memoization part in another program and noticed no
real speedup.
memo(Goal) :- ( stored(Goal) -> true ; Goal, assertz(stored(Goal)) ).
This is the part that didn't improve efficiency much. This would
happen if evaluating "Goal" by itself was faster than doing a lookup
for stored(Goal). I guess this is pretty obvious, yet the way that
bound/unbound variables work in Prolog is that you get a bit of "mini-
memoization" for free. Say that the variable Goal was bound, then upon
backtracking, Goal would not have to be recalculated. That is what I
meant by getting Dynamic Programming for free. A regular procedural
program would have to know not to re-evaluate that value if some
optimality criteria was not met for a set of parameters. And the only
way it would know would be via a "test and set" step that the
programmer would have to code in place.
The other moral of the story is that Wikipedia is free and you get
what you pay for.
Chip Eastham
It could also happen that looking up stored(Goal) beats
deriving Goal from scratch but memoization doesn't help
because of the order in which (sub)goals are attempted
isn't advantageously ordered. The design of a clever
bottom-up dynamic programming "embedding" remains one
the programmmer's to-do list.
regards, chip
wht
> It could also happen that looking up stored(Goal) beats
> deriving Goal from scratch but memoization doesn't help
> because of the order in which (sub)goals are attempted
> isn't advantageously ordered. The design of a clever
> bottom-up dynamic programming "embedding" remains one
> the programmmer's to-do list.
>
Thank You. One thing I have reinforced in my mind is the importance of
structuring a Prolog program to take advantage of efficient search
path ordering.
I know that this goes against declarative programming in the abstract,
but that is the way things go if you want to speed up a solution.
afa
> :- dynamic(stored/1).
>
> memo(Goal) :- ( stored(Goal) -> true ; Goal, assertz(stored(Goal)) ).
>
> lcs([], _, []) :- !.
> lcs(_, [], []) :- !.
> lcs([X|Xs], [X|Ys], [X|Ls]) :- !, memo(lcs(Xs, Ys, Ls)).
> lcs([X|Xs], [Y|Ys], Ls) :-
> memo(lcs([X|Xs], Ys, Ls1)), memo(lcs(Xs, [Y|Ys], Ls2)),
> length(Ls1, L1), length(Ls2, L2),
> ( L1 >= L2 -> Ls = Ls1 ; Ls = Ls2 ).
Please find below a program taken from "Simplifying Dynamic
Programming via Mode-directed Tabling" by Guo and Gupta (I adapted it
to B-Prolog).
Cheers,
Neng-Fa
% longest common subsequence
:- table lcs(+,+,-,max).
lcs([], _, [],0).
lcs(_, [], [],0).
lcs([F|L1], [F|L2],[F|L],N) :-
lcs(L1, L2, L, N1),
N is N1 + 1.
lcs([F1|L1], [F2|L2],L, N) :-
F1 =\= F2,
lcs(L1, [F2|L2],L,N).
lcs([F1|L1], [F2|L2],L, N) :-
F1 =\= F2,
lcs([F1|L1], L2, L, N).
go :-
statistics(_, _),
lcs([50, 10, 400, 30, 30, 20, 10, 5, 30, 20,
6, 20, 20, 30, 9, 30, 20, 500, 20, 40,
30, 8, 3, 5, 9, 200, 10, 400, 20, 30,
50, 10, 400, 30, 30, 20, 10, 5, 30, 20,
7, 3, 60, 38, 20, 39, 83, 92, 30, 19,
6, 20, 20, 30, 9, 30, 20, 20, 30, 9,
30, 20, 500, 20, 40, 4, 92, 30, 92, 20,
6, 20, 20, 30, 9, 30, 20, 500, 20, 40,
30, 8, 3, 5, 9, 200, 10, 400, 20, 30,
30, 20, 500, 20, 40, 4, 92, 30, 92, 20,
50, 10, 400, 30, 30, 20, 10, 5, 30, 20,
6, 20, 20, 30, 9, 30, 20, 500, 20, 40,
30, 8, 3, 5, 9, 200, 10, 400, 20, 30],
[ 7, 20, 25, 30, 9, 35, 20, 500, 20, 40,
30, 8, 3, 5, 9, 200, 10, 400, 20, 30,
50, 10, 405, 30, 35, 20, 10, 5, 30, 20,
30, 8, 3, 5, 9, 200, 10, 400, 20, 30,
50, 10, 405, 30, 35, 20, 10, 5, 30, 20,
30, 8, 3, 5, 9, 200, 10, 400, 20, 30,
30, 8, 3, 5, 9, 200, 10, 400, 20, 30,
50, 10, 403, 30, 30, 20, 10, 5, 30, 20,
6, 20, 20, 30, 9, 37, 20, 500, 20, 40,
50, 10, 400, 30, 30, 20, 10, 5, 30, 20,
6, 20, 20, 30, 9, 39, 20, 500, 20, 40,
6, 20, 20, 30, 19, 30, 20, 500, 20, 40,
30, 8, 3, 5, 9, 210, 10, 400, 22, 30
], L, V),
writeln(L),
statistics(_, [_, B]),
write('The length of the longest common subsequence is '), write
(V), nl,
write('execution time = '), write(B), write(' ms'), nl.