Re: question about last call optimization


"blindsearch" <dpatte3@xxxxxxxxxxx> wrote in message
news:1122418036.807489.196470@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
>I have a question about last call optimization using euclids algorithm
> as an example. Okay the prolog literature gives the procedure as:
>
> gcd(A,0,A).
> gcd(A,B,GCD) :- B > 0, C is A mod B, gcd(B,C,GCD).
>
> Now will prolog "last call optimize" this. It is easy to see that when
> prolog gets to the goal gcd(B,C,GCD) in the last clause that there are
> no alternative clauses. I am assuming then that this procedure is "last
> call optimized". Is this true?

It is true in most Prolog systems.

> What about if we switch the order of the clauses as such:
>
> gcd(A,B,GCD) :- B > 0, C is A mod B, gcd(B,C,GCD).
> gcd(A,0,A).
>
> Now upon reaching the last goal in the first clause, prolog can not
> determine that there are no alternative clauses. Right?

Because of the existence of a choice point, the last call cannot reuse the
frame of the caller in this predicate. But if you rewrite it into the
following:

gcd(A,B,GCD) :- B > 0, C is A mod B, gcd(B,C,GCD).
gcd(A,B,GCD):-B=:=0,GCD=A.

then you still have last-call optimization in some Prolog systems (e.g.,
B-Prolog).

> Okay finally, say we write:
>
> gcd(A,0,GCD) :- !, GCD = A.
> gcd(A,B,GCD) :- T is A mod B, gcd(B,T,GCD).
>
> Now, this should be "last call optimized" right? So in terms of speed
> of execution would this last example execute equivalently to the first?
> What about to the second?
>
> One more question. There is no big difference between the three
> versions of gcd. The first two do leave behind some choicepoints
> whereas the last does not leave any behind. So is there any point in
> writing it the last way? We're not supposed to use cuts all the time
> right? or is it a good habit to get into in the event that we run into
> procedures that have the potential of leaving behind a lot of choice
> points?

The difference should be very big. The version that is deterministic and
tail-recursive is the fastest and takes the least amount of memory.

You may want to add a version that uses if-then-else into your collectition.

--nf


.

Relevant Pages

  • question about last call optimization
    ... I have a question about last call optimization using euclids algorithm ... Okay the prolog literature gives the procedure as: ... Now will prolog "last call optimize" this. ... What about if we switch the order of the clauses as such: ...
    (comp.lang.prolog)
  • Re: An even more basic question...
    ... Prolog is a pretty decent platform for some "knowledge ... extending logic programming in various ways, ... thing about SQL that is interesting is that behind the scenes, ... search optimization seems to exist. ...
    (comp.lang.prolog)
  • Re: optimization
    ... Is there any documentation available ... for the optimization in the prolog? ... What is "optimziation IN Prolog"?... ...
    (comp.lang.prolog)
  • Re: newbie question: repeat search
    ... The Prolog system here is applying an optimization that is only valid ... for pure programs. ...
    (comp.lang.prolog)
  • Re: Out of local stack? (SWI)
    ... that your clauses go from the most spécific case to the most général ... all the lines 'Ontimer" and see wich one is always choosen..... ... >>and standard Prolog is pretty simple minded. ...
    (comp.lang.prolog)