4
\$\begingroup\$

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?

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Wow, that's what I'm talking about! Just one thing: why does it say Warning: Test is always true: var(Max); Test is always true: var(Median) when I load the file? \$\endgroup\$ – Marcus Vinícius Monteiro Apr 13 '15 at 22:19
  • 1
    \$\begingroup\$ Because you are not using a very recent version of SWI-Prolog. This superfluous warning has been fixed for more than 6 months already in the most recent development releases. Try 7.1.36, released today, for a more recent version. \$\endgroup\$ – mat Apr 13 '15 at 22:23
  • \$\begingroup\$ @mat. The goal sort([1,1,1],[_,_,_]) fails, because it eliminates duplicates. You can use msort/2 to keep the duplicates. \$\endgroup\$ – repeat Apr 21 '15 at 14:16
  • \$\begingroup\$ [1,1,1] cannot be considered valid input because which two numbers are then "the two larger numbers"? ;-) \$\endgroup\$ – mat Apr 21 '15 at 14:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.