Code review, advantages and disadvantages of these two ways of writing a predicate

Help!
1

I’m working my way through “Prolog For Artificial Intelligence” by Ivan Bratko, and exercise 3.17 is to write a maxlist(L, M) that succeeds when M is the largest number in the list L.

My attempt at this was:

maxlist([H|T], Max) :-
  maxlist(T, H, Max).
maxlist([], Max, Max).
maxlist([H|T], CurrentMax, Max) :-
  (
    CurrentMax > H
    -> maxlist(T, CurrentMax, Max)
    ;
    maxlist(T, H, Max)
  ).

The author’s solution was:

  maxlist([N], N).
  maxlist([N1,N2|T], Max) :-
    maxlist([N2|T], MaxTail),
    max(N1, MaxTail, Max).

My code is longer, and not as easy to read, but his code gave a choice point.

Anyone have any comments on either piece of code? In particular, is there anything to choose his over mine or vice versa?

Thanks

1 Like
2

I assume that max/3 is defined:

max(X, Y, Z), X >= Y => Z = X.
max(_, Y, Z)         => Z = Y.

Your code is “accumulator” style, which has two advantages over the textbook code: it doesn’t leave a choicepoint and it’s tail recursive (the last call in the 2nd clause of maxlist/3 is to maxlist/3, so the compiler can change the recursion into iteration).

Some implementations might not leave a choicepoint for the textbook code - but they’d need to do a deeper inspection of the first argument ([N] vs [N1,N2|T]). However, this wouldn’t make the textbook code tail-recursive.

It’s hard to say which is more difficult to read.

  • The textbook code can be read as:
    • the maximum of a single-element list is the element.
    • otherwise, it’s the maximum of the first element and the maximum of the rest of the list.
  • Your code can be read as:
    • select the first element as the maximum-so far.
    • iterate through the rest of the list, for each element keeping the larger of the maximum-so-far and the first element.

When you have an accumulator-style predicate, you can use the foldl/4 predicate, which is more concise and doesn’t leave a choicepoint if max/3 doesn’t:

maxlist([L1|Ls], Max) :-
    foldl(max, Ls, L1, Max).

It took me a while to get used to this style of programming … this style is very common in some functional programming languages such as Haskell, Ocaml, and Lisp; but works just as well in Prolog (and sometimes a bit better) – see also maplist/3, and similar meta-predicates in library(apply).

3 Likes
3

@peter.ludemann Thanks for the comments. His code for max/3 was actually…

max(X, Y, X) :-
  X >= Y.
max(X, Y, Y) :-
  X < Y.

This works, but left a choicepoint. It was while I was working on this, and an exercise for the GCD of two numbers that you posted some code that helped me write it using if.

I wrote my code based on the excellent help I’ve had here. I’m trying hard to avoid choicepoints where there is only one solution to a question (eg there’s only one maximum of two integers, only one GCD of two integers, etc), and what I learned about argument indexing led me to the code I wrote.

Thanks also for the pointer toward foldl/4. I’ve come across this before, and have seen similar ideas in other languages, but haven’t yet become familiar enough with it (or most of the built-in predicates) to be confident in using it. Your example will help me explore it more.

Thanks again.

4

To my mind, performing the check twice is inelegant, when we have ->/2 and *->/2 for if…then…else.

max/3 can be:

max(X, Y, Max) :-
    (   X @< Y
    ->  Max = Y
    ;   Max = X
    ).

For iterating through a list, use an accumulator properly:

max_list([H|T], Max) :-
    max_list_(T, H, Max).

max_list_([], Max, Max).
max_list_([H|T], U, Max) :-
    (   U @< H
    ->  M = H
    ;   M = U
    ),
    max_list_(T, M, Max).

This is much faster than maxlist, and uses less memory due to tail-end recursion not needing to remember the state of the variables.

Can test with e.g.:

?- numlist(1, 5_000_000, NL), time(maxlist(NL, Max)).
% 6,615,659 inferences, 2.636 CPU in 2.639 seconds (100% CPU, 2510201 Lips)
ERROR: Stack limit (1.0Gb) exceeded

vs

?- numlist(1, 5_000_000, NL), time(max_list(NL, Max)).
% 10,000,000 inferences, 0.248 CPU in 0.249 seconds (100% CPU, 40268784 Lips)

Non-tail-end recursion can be convenient, but it comes with performance and memory-usage penalties.

2 Likes
5

Bratko is a classic that I know only via other people’s quotations. It looks like you’re working a lot for your bedtime exercises :sweat_smile: :clap:
I have a general question: is the if-then-else construct typical of the SWI-Prolog implementation of the language or is it a standard thing, so to say? Thanks

6

@brebs Thanks for that, very useful.

7

I picked up a copy of the 3rd edition really cheaply, and am working through it. It’s very good, although judging by some of the comments I’ve had here, I think some of my answers to the exercises are better than his!

8

(If->Then;Else) is ISO standard. Also discussed => and *-> are SWI-Prolog specific. We find (If*->Then;Else) as if(If,Them,Else) in several Prolog systems and => in Picat

1 Like
9

Is there a simple explanation of the difference between these two, as I can’t get my head round the info in the docs. Prolly makes lots of sense to those who understand Prolog properly, but for beginners like me, it’s really not clear.

Thanks

10

Cond -> Then ; Else is the same as once(Cond) *-> Then ; Else.
The difference is in what happens if there are more than one way for Cond to succeed; (*->)/2 will try those alternatives but (->)/2 won’t.

As a contrived example:

num(one, 1).
num(two, 2).
num(three, 3).

p(Num, Value) :-
    (   num(Num, Value)
    *-> true
    ;   Value = '-none-'
    ).

?- p(N,V).
N = one,
V = 1 ;
N = two,
V = 2 ;
N = three,
V = 3.

If p/2 had been written with (->)/2, there would have been only one solution: N=one,V=1.

However, the behaviour if the N argument is instantiated would be the same for both (->)/2 and (*->)/2, which is why (->)/2 is usually used – it’s relatively uncommon to have a condition that also binds a value.
Similarly, it’s relatively uncommon to only use the “if-then” part; it’s usually of the form “if-then-else”. Also note that (;)/2 is “or” and can be defined like this:

(A ; _) :- call(A).
(_ ; B) :- call(B).
1 Like
11

Brilliant!

Thanks very much for the clear explanation.

12

One other thing: the if-then-else parses as follows (due to operator precedence) – the -> binds tighter than ;, so Cond -> Then ; Else can be read "(if Cond, then (cut) Then); else Else`.

?- write_canonical((a->b;c)).
;(->(a,b),c)
true.

?- forall((member(Op,[';','->','*->']), current_op(P,F,Op)), writeln(op(P,F,Op))).
op(1100,xfy,;)
op(1050,xfy,->)
op(1050,xfy,*->)
1 Like
13

Hi,
To add to this discussion, I bring to your attention a recent paper of ours (actually a book chapter) that discusses over 9 different implementations of min_list/2 (all implementations could be easily mirrored for max_list/2).

https://www.researchgate.net/publication/371661553_Demonstrating_Multiple_Prolog_Programming_Techniques_Through_a_Single_Operation

My favorite one concerning elegance and efficiency is the “functional” one (implementation no. 6 in the paper) that exploits the first element of the list to deliver the temporary minimum/maximum to the rest of the “iterations” of the list. In the case of maxlist the solution looks like this:

maxlist([N],N).
maxlist([N1,N2|T], Max) :-
    max(N1,N2,TmpMax),
    maxlist([TmpMax|T], Max).

In this solution there is no choice point left (if max/3 does not leave one), it is as compact as the Bratko’s solution, but it is also efficient since it is tail-recursive. At the bottom line, it is similar to the solution that uses foldl that Peter suggested, but it is easier for a Prolog programmer that has no exposure to functional programming to understand.

Hope I have helped.
Nick

14

I would consider this an anti-pattern. Specifically, you are reusing the input list to keep the state. [1] And at least on my computer and SWI-Prolog this does in fact leave a choice point.

This is conventionally refactored to (appears as list_min3 in your paper):

maxlist([X|Xs], Max) :- maxlist_(Xs, X, Max).

maxlist_([], Max, Max).
maxlist_([X|Xs], Max0, Max) :-
    max(Max0, X, Max1),
    maxlist_(Xs, Max1, Max).

… and this solution appeared higher in the thread; and it is also the manual rewriting that foldl/4 would do, in case we defined it as:

maxlist([X|Xs], Max) :- foldl(max, Xs, X, Max).

Neither of those leaves a choice point.

Note that if you are in fact doing this for numbers, you might as well use Max is max(A, B) instead of a hand-rolled max/3 predicate. At the very least you avoid one unnecessary conditional.

EDIT: one more thing. SWI-Prolog provides library(apply_macros) that does compile-time re-writing for some meta-predicates, for example maplist. But it does not currently include foldl, so while this mechanical rewriting at compile time is possible, it does not happen.

  1. There is an attempt to resolve this on the syntactic level by using “semi-context notation” with a DCG rule, not sure how successful it is. ↩︎

1 Like
15

I would strongly suggest any programmer to get exposure to both Prolog and functional programming :smiley: we can adjust our tools to a limited set of skills, but we could also grow our skills together with our tools.

16

Why not

  • the third argument is the maximum of the second argument and all the elements of the first one.
    This is declarative (and leads to a quick correctness proof of the program). The quoted description is operational.
1 Like
17

PS: There is, in fact, a difference between using arithmetic comparison operators to implement max/3, and the arithmetic function max().

?- [user].
|: max(X,Y,M) :- ( X >= Y -> M = X ; M = Y ).
|: ^D% user://1 compiled 0.02 sec, 1 clauses
true.

?- max(1, 2+3, Max).
Max = 2+3.

?- X is max(1, 2+3).
X = 5.

I guess either behaviour could be the “right” one depending on the use case.

18

The reason that it gives a choice point is that it doesn’t trigger
deep indexing. The functor of both first arguments does not differ,
its in both cases ('[|]')/2 i.e. the SWI-Prolog specific list consing functor.

Deep indexing would see that the functor of the tail of the first argument
differs, that it is ([])/0 in the first clause and it is ('[|]')/2 in the second clause.
But deep indexing somehow doesn’t kick in, not sure bug or feature?

If deep indexing is not triggered you need to place a cut, to make it
deterministic nevertheless. You might loose declarativity, but you will
gain more determinism, namely you will eradicate a spurious choice point:

maxlist([N], N) :- !.
maxlist([N1,N2|T], Max) :-
    maxlist([N2|T], MaxTail),
    max(N1, MaxTail, Max).

It works, doesn’t give a spurious choice point anymore:

?- maxlist([2,1,3], X).
X = 3.

Adding cuts always works where the automatic indexing of SWI-Prolog fails.
I am not sure whether this is a bug or feature, that deep indexing fails to be
deployed by the Prolog system. What is deep indexing, see also here:

2.18.1 Deep indexing
https://www.swi-prolog.org/pldoc/man?section=deep-indexing