How does this Prolog program resolve to H=2? I don't understand the line of execution

1
votes

I have the following chunk of Prolog taken from a YouTube tutorial on Prolog:

change(H, Q, D, N, P) :-
        member(H, [0, 1, 2]),
        member(Q, [0, 1, 2, 3, 4]),
        member(D, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]),
        member(N, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]),

        S is 50*H + 25*Q + 10*D + 5*N,
        S =< 100,
        P is 100-S.

It's a program to make change on a dollar. H is half dollars, Q is quarters, D for dimes, N for nickels, P for pennies.

If I type change(H, 0, 0, 0, 0). as a query, it resolves to H=2. In the video, he mentions this is a program that makes change for $1, so I understand that two half dollars are $1, but I don't understand how it gets that.

My understanding of Prolog is that when I pass change(H, 0, 0, 0, 0)., it looks to find a value for H that will satisfy the conditions, so it goes to the first line and sees that 0 would work, then for the other "member" lines sees that the 0s that were passed also are correct.

It then sets S to a value, which given the above values would be S = 0. The next line makes sure it's less than or equal to 100, which 0 is, then sets P to 100-S (which is 100).

How is it not done there with H = 0? What am I missing?

2
prolog

2 Answers

2
votes

member(H,[0,1,2]) binds H to either 0, 1 or 2. Since Q, D, N and P are all 0, the only value for H that will satisfy the equations at the bottom is 2.

When H=0, S will be 0, 100-S will be 100, and since P is 0, P is 100-S will fail.

When H=1, S will be 50, 100-S will be 50, and since P is 0, P is 100-S will fail.

When H=2, S will be 100, 100-S will be 0, and since P is 0, P is 100-S will succeed.

1
votes

In addition to the operational explanation, I would like to suggest CLP(FD) constraints for such problems, which are easier to understand and more declarative than lower-level arithmetic predicates. For example, in SICStus Prolog, YAP and SWI:

:- use_module(library(clpfd)).

change(H, Q, D, N, P) :-
        H in 0..2,
        Q in 0..4,
        D in 0..10,
        N in 0..20,

        S #= 50*H + 25*Q + 10*D + 5*N,
        S #=< 100,
        P #= 100-S.

Let us now reason declaratively:

If H = 0, as you ask, and the other parameters are 0, as you specified, then what are admissible values of P?

?- change(0, 0, 0, 0, P).
P = 100.

From this, we see that if all other arguments are 0, then the only valid solution for your query is P = 100. Thus, the goal change(0, 0, 0, 0, 0) will certainly fail.