Virtuous Programmer Adventures of an Autodidact

10Jan/110

Prolog 2/4: Loops, Decisions and Tests

Writing and Testing Fizzbuzz in Prolog

This is the second article in a series, to read it from the beginning go here.

The Plan

This week I've worked my way through solving the Fizzbuzz problem in Prolog. The most difficult part of working on it was learning to deal with Prolog's syntax. Once I got a decent grasp of the syntax, the solution to the fizzbuzz problem fell out quite naturally.

What to Expect

When this article is complete:

  • You will have:
    • An executable that produces fizzbuzz up to 20
    • Unit tests that verify several of predicates
  • You will know:
    • How to write recursive clauses.
    • How to write conditionals.
    • How to write loops.
    • How to trow and catch exceptions.
    • How to write and run unit tests.

Files Used in this Project

The Code

Basic Predicates

  1. isFizz(Num) :- 0 is Num mod 3.
  2. isBuzz(Num) :- 0 is Num mod 5.
  3. isFizzbuzz(Num) :- isFizz(Num), isBuzz(Num).
  4.  

There are two basic ways that information comes out of a predicate. The first is by filling in all of its arguments, then it returns either true or false depending on how they evaluate in the predicate's body.

Conditionals

  1. fizzbuzz(Num, Res) :-
  2.   isFizzbuzz(Num) -> Res = 'fizzbuzz';
  3.     isFizz(Num) -> Res = 'fizz';
  4.     isBuzz(Num) -> Res = 'buzz';
  5.     Res = Num.
  6.  

Prolog's conditional is ->. a -> b is equivalent to if a then b. You can see above that the conditionals are separated out by Prolog's "or" operator is ;. In this context, ; operates as an else. These aren't special cases, but the standard operation of Prolog. For example:

  1. If isFizzbuzz(Num) evaluates to true, then Res = 'fizzbuzz' and the statement evaluates to true and the following 'or' statement is short-circuited.
  2. If isFizzbuzz(Num) evaluates to false, then the whole if statement evaluates to false and then the other side of the 'or' operator is evaluated.

Recursion and Exceptions

  1. fizzbuzzes(TopNum, TopNum, List) :-
  2.   List = [],!.
  3. fizzbuzzes(TopNum, CurrentNum, [Head | Tail]) :-
  4.   CurrentNum > TopNum -> throw('the CurrentNum is greater than TopNum');
  5.   TopNum < 1 -> throw('the TopNum is less than 1');
  6.   (NextNum is CurrentNum + 1,
  7.   fizzbuzz(CurrentNum, Head),
  8.   fizzbuzzes(TopNum, NextNum, Tail)).
  9.  

Here I took advantage of the fact that Prolog evaluates its terms on the left side as well as on the right of :-. For the first clause, if the first two terms have the same value then this clause is the one to fire. List is set to [], then all further evaluation stops because of the !. I'm still a little vague on exactly how it works, but the short version is that if a predicate has multiple possible values, then Prolog will normally try to look for them. The ! tells Prolog that once it reaches it, it shouldn't look any further.

Line 3 is in some ways the oddest one in the set. The first two values passed in aren't unusual. The third value [Head | Tail] is a list which doesn't have a name as a whole, but its head and tail do. For our use this is will be the return value of the predicate, though in Prolog this isn't entirely a meaningful phrase. Later you'll see a case where the "return value" is passed into the predicate to verify if it's valid.

In Line 4 I verify if the CurrentNum is greater than the TopNum, this should never happen since there's a wrapper that's intended to be used that won't let it, but there's no harm in a bit of verification. If it is then an error is thrown with the term: 'the CurrentNum is greater than TopNum'. Normally terms don't have spaces in them, but if you surround a term in single quotes it can have any combination of characters.

Clauses with More Than One Arity

  1. fizzbuzzes(TopNum, List) :-
  2.   OneHigher is TopNum + 1,
  3.   fizzbuzzes(OneHigher, 1, List).
  4.  

This fizzbuzzes is the same clause as the one in the previous section, but with Arity 2 instead of 3. In Prolog these are differentiated as fizzbuzzes\2 and fizzbuzzes\3. In the second line you can see some arithmetic, which is OneHigher = TopNum + 1.

Loops

  1. printFizzbuzzes(TopNum) :-
  2.   fizzbuzzes(TopNum, FizzbuzzList),
  3.   forall(member(X, FizzbuzzList), (print(X), nl)).
  4.  
  5. main :-
  6.   printFizzbuzzes(20),
  7.   halt.
  8.  

I claimed in the last article that Prolog had no looping constructs. This is a half truth. It has no special syntax for loops, but it does allow for the creation of a for loop as a predicate. forall is part of swipl's standard library where the first argument is a generator for terms and the second argument is applied to each of those terms.

Unit Tests

Starting Unit Tests

  1. :- begin_tests(fizzbuzz).
  2.  

A clause that has a body, and not a head is a message to the compiler. A sequence of unit tests always starts with the being_tests clause. The term inside it will mark out what test suite this is.

Test Cases, Negation

  1. test(isFizz_isnot) :-
  2.   not(isFizz(5)).
  3.  

When a predicate named test is defined it will be added to the test suite. not here is a little bit strange, it does not mean that something is false, but that it can't be asserted as true. So if there is no assertion of the truth or falsehood of a statement, it will return true.

Not Really a Return Type

  1. test(fizzbuzz_fizz) :-
  2.   fizzbuzz(3, 'fizz').
  3.  
  4. test(fizzbuzzes_empty) :-
  5.   fizzbuzzes(0, []).
  6.  
  7. test(fizzbuzzes_5) :-
  8.   fizzbuzzes(5, [1, 2, fizz, 4, buzz]).
  9.  

Where previously I used the second argument in fizzbuzz and fizzbuzzes to return a value, here I'm using it to verify the truth of a statement.

Closing the Test Suite

  1. :- end_tests(fizzbuzz).
  2.  

end_tests closes out the test suite.

Running Your Tests

To execute the unit tests, run swipl from the directory that contains fizzbuzz.pl. Load fizzbuzz into the interpreter with [fizzbuzz]., then run the tests with run_tests.

Final Summary

Fizzbuzz comes out well in Prolog. I've spent a lot more time time thinking I was fighting with the syntax when the reality was I don't get the semantics. It's the first time in a few years I've had to remind myself, "The compiler's not broken, you just don't know what you're doing."

Coming Up

Next week we'll put the rubber to the road. Prolog's pretty cool for algoritmic stuff, let's see how it handles networking and XML.

Resources

Posted by Frank Berthold

Comments (0) Trackbacks (0)

No comments yet.


Leave a comment

No trackbacks yet.