Prolog: How can I implement the sum of squares of two largest numbers out of three?

Question

Exercise 1.3 of the book Structure and Interpretation of Computer Programs asks the following:

Define a procedure that takes three numbers as arguments and returns the sum of the squares of the two larger numbers.

I'm learning Prolog. Here's the function I tried to implement:

square(X, Y) :- Y is X * X.
squareTwoLargest(X, Y, Z, R) :- 
    R is square(L1) + square(L2), L1 = max(X, Y), L2 = max(min(X, Y), Z).

However, when I run it, it gives the following error: ERROR: is/2: Arguments are not sufficiently instantiated. I think I'm not only not getting Prolog's syntax, but I'm also not getting the logic programming paradigm yet. So, how could I implement this function in good logic programming style?

Answer 1

To get the two largest numbers out of three (V1, V2, and V3) you can proceed as follows: Sort the list [V1,V2,V3] and take the last two list items [_,X,Y], square and sum them.

:- use_module(library(lists)).
:- use_module(library(clpfd)).

squareTwoLargest(V1,V2,V3, R) :- 
    Zs = [_,X,Y],
    chain(Zs, #=<),
    permutation([V1,V2,V3],Zs),
    R #= X*X + Y*Y.

Sample query:

?- squareTwoLargest(20,30,10, R).
R = 1300 

---

Better implementation

Above code is based on "permutation sort", which makes it inefficient in more than one way.

The goal squareTwoLargest(X,Y,Z, R) succeeds multiple times and gives redundant answers, if two or more of X, Y, and Z are equal. This is shown by the following two queries:

?- squareTwoLargest(0,10,10, R).
R = 200 ;
R = 200 ;
false.

?- squareTwoLargest(10,10,10, R).
R = 200 ;
R = 200 ;
R = 200 ;
R = 200 ;
R = 200 ;
R = 200 ;
false.

We can eliminate the redundant answers by using a sorting network of size 3. For details, look at this answer to the question ordering lists with constraint logic programming.

list_sorted__SN3([A0,A1,A2], [D0,D1,C2]) :-
    B1 #= min(A1,A2),   B2 #= max(A1,A2),
    C0 #= min(A0,B2),   C2 #= max(A0,B2),
    D0 #= min(C0,B1),   D1 #= max(C0,B1).

squareTwoLargest__SN(V1,V2,V3, R) :-
    list_sorted__SN3([V1,V2,V3],[_,X,Y]),
    R #= X*X + Y*Y.

Consider the following queries:

?- squareTwoLargest__SN(20,30,10, R).
R = 1300.                              % works like it did before

?- squareTwoLargest__SN(20,20,10, R).
R = 800.                               % succeeds deterministically

?- squareTwoLargest__SN(20,20,20, R).
R = 800.                               % succeeds deterministically 

Note that all redundant answers of the corner cases shown above have been eliminated.

Answer 2

Unfortunately, max function you are using, is built-in arithmetic function and does not behave as a predicate, this may trick you into thinking that you will write your predicates in the same way.

In Prolog, what you will be writing is predicates. Predicate does not return any value, it just holds or does not hold (you can think of it as if it returned true or false). Your predicate square is a good example, what it square(X,Y) really means is 'Y is square of X'. If you ask Prolog console square(4, 16)., it will tell you true. If you ask square(4, 44), it will tell you false. So how do you find out square root of some number? You ask Prolog a question with free (unknown) variable square(4,R)., then Prolog will tell you that R=16. That is the important part of logical programming, you do not explain Prolog, how to calculate square, you only tell Prolog what square is in terms of logic and then you ask Prolog question and it will find answer by itself.

Soo what if you try instead of

R is square(L1) + square(L2)

something like

square(L2, L2SQUARED), square(L1, L1SQUARED), ...

which will give you square of L1 in L1SQUARED

However, L1 must not be free variable, Prolog must be able to deduce some value for it based on some other predicates (...), so that it can answer to square(L1, L1SQUARED). Imagine question square(SOMETHING1, SOMETHING2), where both arguments are unknown, what will the answer be? There is infinite number of correct answers, for example [2, 4] or [3, 9] etc.

Note: yes, it can be onliner with arithmetics, but if you want to learn logical programming, try more 'logical programming' like approach. In some flavours of Prolog, you do not get arithmetics and they are still useful...

Answer 3

my bet, using the 'if-then-else' construct.

squareTwoLargest(X, Y, Z, R) :- 
    ( X > Y -> A = X, B = Y ; A = Y, B = X ),
    R is A + max(B, Z).

Two temp variables are needed.