SICP Exercise 1.3: Sum of squares of two largest numbers out of three, Prolog Version

Question

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

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

My answer is this:

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

My reason for learning Prolog is to understand the logic programming paradigm. So, how can I solve this exercise in good logic programming style?

Answer 1

The problem, as stated, has a completely straight-forward solution, because the problem statement is limited to numbers:

sicp1(X, Y, Z, SumSquares) :-
        msort([X,Y,Z], [_,A,B]),
        SumSquares is A^2 + B^2.

You can use this predicate every time the three numbers are fully specified, for example:

?- sicp1(1, 2, 3, S).
S = 13.

The problem though is that this code is not as general as it could be. It does not work for example if the arguments are variables:

?- sicp1(X, Y, Z, S).
ERROR: is/2: Arguments are not sufficiently instantiated

From a truly declarative solution, we expect valid answers even if arguments are only partially known.

Enter constraints. I show you a solution with CLP(FD) constraints. This means that the arguments are elements of the set of integers. Check out other constraint libraries like CLP(Q) to get solutions over different domains.

Working solution for SICStus, SWI etc.:

:- use_module(library(clpfd)).

sicp2(X, Y, Z, SumSquares) :-
        Max #= max(max(X, Y), Z),
        Median #= max(min(X, Y), min(max(X, Y), Z)),
        SumSquares #= Max^2 + Median^2.

Now, we can use this just like before:

?- sicp2(1, 2, 3, S).
S = 13.

However, we can also use it in other ways. For example:

?- sicp2(X, 3, 5, S).
...
S in 34..sup.

From this answer, you see that the sum of squares will be at least 34, no matter the eventual value of X.

When giving further constraints, you get more precise answers:

?- sicp2(X, 3, 5, S), X #< 4.
S = 34,
... .

This means that, if it is known that X is less than 4, then the result is certainly 34 in this case.

Thus, the solution using constraints is much more general, and it is just what we would expect from a truly declarative solution that can be queried in all directions and gives useful answers in all cases.