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

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

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.


fizzbuzz(Num, Res) :- 
  isFizzbuzz(Num) -> Res = 'fizzbuzz';
    isFizz(Num) -> Res = 'fizz';
    isBuzz(Num) -> Res = 'buzz';
    Res = Num.

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

fizzbuzzes(TopNum, TopNum, List) :-
  List = [],!.
fizzbuzzes(TopNum, CurrentNum, [Head | Tail]) :- 
  CurrentNum > TopNum -> throw('the CurrentNum is greater than TopNum'); 
  TopNum < 1 -> throw('the TopNum is less than 1'); 
  (NextNum is CurrentNum + 1,
  fizzbuzz(CurrentNum, Head),
  fizzbuzzes(TopNum, NextNum, Tail)).

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

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

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.


printFizzbuzzes(TopNum) :-
  fizzbuzzes(TopNum, FizzbuzzList),
  forall(member(X, FizzbuzzList), (print(X), nl)). 

main :- 

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

:- begin_tests(fizzbuzz).

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

test(isFizz_isnot) :-

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

test(fizzbuzz_fizz) :-
  fizzbuzz(3, 'fizz').

test(fizzbuzzes_empty) :-
  fizzbuzzes(0, []).

test(fizzbuzzes_5) :-
  fizzbuzzes(5, [1, 2, fizz, 4, buzz]).

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

:- end_tests(fizzbuzz).

end_tests closes out the test suite.

Running Your Tests

To execute the unit tests, run swipl from the directory that contains 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.


Scala 2/4: Loops, Decisions and Tests

This is the second article in a series, to read the whole series go here.

This week I’ve worked on learning Scala’s basic syntactic structures and how to write unit tests. To accomplish this I’ve implemented a solution to the fizzbuzz problem and written a couple of unit tests to demonstrate that it works.

For an overview of the fizzbuzz problem, go to wikipedia’s page.

Conditionals, Loops and Other Constructs


Defining Methods

object Fizzbuzz {
  // Returns true if the given number is divisible by 3
  def isfizz(num : Int) : Boolean = { num % 3 == 0 }

  // Returns true if the given number is divisible by 5
  def isbuzz(num : Int) : Boolean = { num % 5 == 0 }

The method definition syntax is in the format: def <method name>(<arg name> : <arg type>) : <result type> = <body>. You can see here that there is no ‘return’ statement in Scala. The value of any given block is the last statement executed in that block. This can lead to some confusion if you have very large methods with a lot of complex branching. The obvious solution is not to have very large methods. I generally start breaking up my methods if they start getting to be more than 12 lines long.

Scala is a statically typed language, which means that all of the variable/argument types are set at compile time. Fortunately it also uses Hindley-Milner type inference which will often guess the intended type of an argument/variable. Because of this the above code can be simplified as:

object Fizzbuzz {
  // Returns true if the given number is divisible by 3
  def isfizz(num : Int) = num % 3 == 0

  // Returns true if the given number is divisible by 5
  def isbuzz(num : Int) = num % 5 == 0

As far as I’m able to tell, unlike in some systems that use Hindley-Milner, types are required when defining the arguments for a method. I don’t really view this as a disadvantage, when I’m coding I get hopelessly confused if I don’t have the intended type of my variables noted somewhere, there’s no reason not to have it in a way that the compiler can catch my mistakes.

You can also see that when there’s only one statement in the method there’s no need for the curly braces around it. This can lead to significantly cleaner looking code when you just have a one liner.

If Statements and Exploring Your Options

   def fizzbuzzSingle(num : Int) : Option[String] = { 
    if(num < = 0) None
    else if(isfizz(num) && isbuzz(num)) Some("fizzbuzz")
    else if(isfizz(num)) Some("fizz")
    else if(isbuzz(num)) Some("buzz")
    else Some(num.toString())

If Statements

One of the ways the Scala team tried to make their language more accessible is to keep the syntax similar to Java where they didn't either simplify it or add functionality which needed new syntax. So anyone who is familiar with any of the Algol type programming languages will recognize the format of the conditional statements above.

Algebraic Data Types

What is less common is Scala's use of an algebraic type system. In short this means that there are types that wrap other types. In the above case the Option type can wrap an arbitrary types. I've used it to wrap a string, bit it could just as easily wrap an Int or a Window object. There are a myriad of reasons for using an algebraic type system. Here it allows me to indicate that an input is invalid (values less than 1) without throwing an exception.

When you are using a package that communicates failure through exceptions, it's often hard to know what exceptions to expect. By using the type system, if you know the type signature of your function/method, you can be sure what to expect as output from your function. When an invalid value is handed to a function using the Option type, it returns None. When it receives a valid value then it returns Some(<response>).

Strictly speaking Scala doesn't have Algebraic types, here for example None and Some are subclasses of the abstract class Option. But for practical purposes it's hard to tell the difference.

Comprehensions and Match

   def fizzbuzzList(end : Int) : List[String] = {
    for (num < - List.range(1, end + 1)) yield fizzbuzzSingle(num) match {
      case Some(n) => n
      case None => ""

For Comprehensions

For comprehensions are similar to list comprehensions in other languages with the syntax: for <value> <- <list> if <boolean statement> yield <result>. This will go through each of the values in <list> and if the <boolean statement> returns true then yields the given <result>. The if <boolean statement> part is optional as in the above code.

Match/Case Statements

Scala's match/case statements are a generalization of the more common switch statement. The difference between them are that checking isn't just at a value level, but at a type level also. Here I'm using it to distinguish between the Some and None type, then I can extract the variable value in Some(n) and make use of it.


   def fizzbuzzString(end : Int) : String = fizzbuzzList(end).mkString(" ")

  def main(args : Array[String]) = println(fizzbuzzString(20))

When a file contains an object with a main method, it will execute that method when it's associated class is called from Java.

Testing in Scala


There are a number of unit test frameworks available for Scala. The one that comes with the system, SUnit, has been deprecated. While there isn't a replacement in the standard libraries, the most common recommendations are:

  • ScalaTest: A standard unit testing framework.
  • scalacheck: A test generation framework in the same style as Haskell's quickcheck.
  • specs: A Behavior-Driven-Design style of test framework.

For my purposes I chose scalacheck because it is well suited to testing the fizzbuzz problem, and I'm rather fond of quickcheck. In scalacheck you write assertions about the function that is tested instead of writing explicit test cases. Scalacheck then generates random data to verify those assertions.

Installing the Library

To install scalacheck, download the jar file (scalacheck-..-.*.jar) from scalacheck's download page and save it to Scala's lib directory, c:\scala\lib if you're continuing from last week. 

Importing Libraries

import org.scalacheck._
import Fizzbuzz._

Import in Scala looks very similar to Import in Java except instead of using *, you use _ to indicate a wildcard.

Subclassing and Local Imports

object TestFizzbuzz extends Properties("fizzbuzzSingle") {
  import Prop._

Scala's subclassing and trait system is extraordinarily complex, but just subclassing from one other class is simple: object <object name> extends <super class>

If you only need to use an import in context to a single class or object, then you can import it inside that class or object.

A scalacheck Properties

property("fizzbuzzSingle: < 1 is None") = forAll 
  { (num: Int) => (num < 1) ==> (Fizzbuzz.fizzbuzzSingle(num) == None) }

  property("fizzbuzzSingle: >= 1 is not None") = forAll 
  { (num: Int) => (num >= 1) ==> (Fizzbuzz.fizzbuzzSingle(num) != None) }

  property("fizzbuzzSingle: (mod 3) and not (mod 5) is Some(\"fizz\")") = 
    forAll (Gen.posNum[Int]) 
      { (num: Int) => ((num % 3 == 0) && (num % 5 != 0)) ==> 
        (Fizzbuzz.fizzbuzzSingle(num) == Some("fizz")) }

Scalacheck has a lot of depth to it, but getting started is simple. A simple template is:

property("<property description>") = forAll { (<argument> : <type>) => (<limiting condition>) ==> (<assertion>) }

Working backwards, the assertion is a boolean statement that should be true so long as the limiting condition is true. The argument/type combination are the values that you want the system to generate randomly. As in a normal function definition, you can have as many argument/type pairs as you like, separated by commas.

My Experience

Overall I've found working out the fizzbuzz problem in Scala to be interesting and, the language didn't spend much time getting in the way. The two major caveates to that are:

  1. The state of flux of the unit test system, it'd be nice if they'd pick one to include in the package.
  2. When the code is compiled, there are an unusually large number of class files because of the anonymous functions that tend to crop up in functional code (14 if you include the test code).


Python 2/4: Loops, Decisions, and Tests

This is the second article in a series, to read the entire series go here.

Conditionals and Loops

Now that Python’s installed and we know how to run a program, the next step is to look more closely at Python’s conditional structures. The lens we’ll use for this is the fizzbuzz problem.


The fizzbuzz problem is derived from a game in which the players sit in a circle and count, one after the other. If the number is divisible by 3 or 5, they say either ‘fizz’ or ‘buzz’ insteady of the number. If the number is divisible by both 3 and 5 they say ‘fizzbuzz.’ A fairly common test of basic programming skill is to write a program that will iterate through a sequence of numbers assigning them the appropriate value from the fizzbuzz game.

I’ll be using two different solutions to the fizzbuzz problem to take a look at how Python handles conditionals and loops. One solution will use a for loop, the other will use list comprehension.

Function Formatting

The first point to examine is function definition. In the previous post I skimmed over how blocks are delimited in Python. Here you can see that python uses the off-side rule to indicate the start and end of a block and new lines to indicate the end of a statement. This is wonderful because it makes for a very clean looking syntax, and it eliminates two entire classes of bugs: the ‘you forgot a semicolon here’ bug and the ‘remember to close your braces’ bug. It also creates its own problems.

Python interprets both a tab and a space as a single unit of whitespace. It reads 1 tab’s worth of spaces and an actual tab as being two different things. This can lead to a lot of frustration for new programmers because these look exactly the same to someone reading the code. To help avoid this kind of problem it’s considered standard in the Python community to set your editor to use only spaces and never insert a tab character. How to go about this varies from editor to editor. In IDLE, Python’s IDE, tabs are treated as spaces by default.

Most frequently in the line preceding a new block there is a line such as a function declaration, an if statement, a looping statement, those lines will have colon’s at their ends indicating the end of the statement/start of the block.

def isfizz(num):
  """Returns true if the given number is divisble by 3"""
  return num % 3 == 0

def isbuzz(num):
  """Returns true if the given number is divisble by 5"""
  return num % 5 == 0

The other point of interest in the above code is the first line of each of the functions after the declaration. When you write a python function if you start it with a triple quoted string documention generated by pydoc will automatically be incorporated in the function.

If I Were More Assertive

def fizzbuzzSingle(num):
  """This follows the fairly simple pattern of generating
     a single instance of fizz buzz depending on the number
     value given."""
  assert num > 0, "The given number " + str(num) + " is not a natural number."

  if isfizz(num) and isbuzz(num):
    return "fizzbuzz"
  elif isfizz(num):
    return "fizz"
  elif isbuzz(num):
    return "buzz"
    return str(num)

A few interesting pythonisms show up here. On line 5 there’s an assertion statement with the format “assert <a boolean statement>, <The string to throw if it fails>“. This is just syntactic sugar for:

    if not num > 0:
      raise AssertionException("The given number " + str(num) + "is not a natural number."

Lines 7-13 contain the standard setup for Python if/elif/else statements. Although Python usually uses parentheses to delimit arguments in a function, they are unnecessary in python conditionals/loops where the colon indicates the end of the statement. Of course that leads to the question, why they are necessary in function definitions. Anyone who can answer this feel free to let me know.

On line 14, there’s an explicit type conversion from an integer to a string. This is necessary in Python because implicit type casting isn’t allowed. The basic types all have an equivalent to this converstion, this means the programmer only has to learn one function per type, instead of “intToStr”, “floatToStr” etc.

Ranges and Method Calls

def fizzbuzzComprehension(topNum):
  """In this example I've used list comprehension to generate the list of
     fizzbuzz strings, then combined them afterwards."""
  fizzbuzzList = [fizzbuzzSingle(num) for num in range(1, topNum + 1)]
  return " ".join(fizzbuzzList)

I’ve used the range function several times, but haven’t gotten around to explaining how it works. It shows a few of the nice features in python. At its base, range generates an ordered list of numbers. What that list is depends on the number of arguments.

range(5) # 1 Argument Generates [1, 2, 3, 4]
range(3, 7) # 2 Arguments Generates [3, 4, 5, 6]
range(0, 30, 5) # 3 Arguments Generates [0, 5, 10, 15, 20, 25]

The important idea here is that Python allows variable numbers of arguments in its functions, we’ll get to more detail on how this works in a later article.

The last line in fizzbuzzComprehension introduces Python’s method call notation. The syntax is fairly common in object oriented languages <object>.<method>(<arguments>). Here the object is a string with one space, the method is “join.” Join takes a list of strings and intersperses its object between them.

For Loops, Iterables and Slices

def fizzbuzzFor(topNum):
  """Here I've used the more common for loop to generate the fizzbuzz string,
     It's less concise than the list comprehension version, but is also less
     suprising to those who aren't as familiar with the syntax."""
  fizzbuzzString = ""
  for num in range(1, topNum + 1):
    fizzbuzzString += fizzbuzzSingle(num) + " "

  # Return the total string, dropping the last space.
  return fizzbuzzString[:-1]

On line 6 we introduce Python’s version of the for loop. Unlike most languages I’ve encountered where the format is “for(<start value>, <end condition>, <value change>)“, Python’s format is “for <new variable> in <iterable>“. An iterable, broadly described, is any value that you could perceive as a list of something. Lists, lines in a file, the output of a generator and a sets are a few examples of iterables.

The last line will look especially unusual to those who are used to conventional array index notation. Python uses a rather power syntax called slice notation to refer to subsets of an iterable value where 0 is the first value. You can refer to sub-lists with the syntax “<a list>[<first value>:<value after the last value>]“. If you leave out either the start or end value then Python will take from the beginning or the end respectively. Finally, as can be seen in fizzbuzzFor, you can use negative numbers to refer to start from the end of the iterable rather than the beginning. To make the functionality more clear, read a few examples:

"spam"[0:1] == "s"
"spam"[:3] == "spa"
"spam"[-2:] == "am"
"spam"[:-1] == "spa"

Making it Run

if __name__ == "__main__":
  print fizzbuzzComprehension(20)

As I mentioned in the last article, Python doesn’t have a ‘main’ function, but there are times when you want to load a module without having it execute all of its code. If you want code that is only executed when the file is executed on its own you check if the the __name__ variable’s value is "__main__".

Testing…. Testing

Python comes with its unit test framework built in, among many other libraries. There are a number of others available, but pyunit (called unittest in the python 2.7 release) is more than adequate.

Importing Modules/Libraries

import unittest
from fizzbuzz import *

Both of the above commands import the named libraries. The two differ in how much information you need to reference the contents of their modules. The functions on fizzbuzz can be referenced as though they were declared in the same file. To refer to an element in the unittest module you must indicate that you are referring to a member of that module with dot notation like “<module>.<element>“. Unfortunately this notation is confusingly similar to the notation used to reference the methods in objects.

The notation “from <module> import <something>” can either be general and import all of the elements in the module as above, or import specific elements as in:

from fizzbuzz import fizzbuzzSingle, fizzbuzzComprehension


class FizzBuzz(unittest.TestCase):
  def setUp(self):
    """Setup is run every time a given test is executed."""
    self.justBy3 = [num for num in range(1, 101) if isfizz(num) and not isbuzz(num)]
    self.justBy5 = [num for num in range(1, 101) if isbuzz(num) and not isfizz(num)]
    self.by3and5 = [num for num in range(1, 101) if isfizz(num) and isbuzz(num)]
    self.notBy3and5 = [num for num in range(1, 101) if not (isfizz(num) or isbuzz(num))]

Class syntax in Python isn’t especially suprising, “class <name of class> (<superclasses>)“. It’s worth noting that Python allows for multiple inheritance and that methods are declared in a similar fashion to functions.

All methods have ‘self’ as their first argument, this allows you to refer to the object that contains the method without any extra keywords. This can cause some confusion because while all methods have ‘self’ as their first argument when declared, when the method is called ‘self’ is left off.

  def testFizzBy3(self):
    """Verifies that if a number is divisble by 3, it returns fizz"""
    for num in self.justBy3:
      result = fizzbuzzSingle(num)
      self.assertEqual(result, "fizz")

Pyunit makes use of the exception handling system for its tests. In this case, should the assertion in line 5 fail then the test fails. Also note in line 3, the use of the list generated in the setUp method.

  def testMustBePositive(self):
    """fizzbuzzSingle should throw an error when given a non-positive value"""
    except AssertionError:
      fail("Expected an assertion error, non-positive should fail.")

In cases where an error is the expected behavior, using the try/except/else syntax demonstrated that the error was thrown. Here Python is actually using a pun on pass/fail. Fail is a legitimate part of the unittest library. Pass is a python keyword indicating that it should do nothing. It’s similar to NOP in assembler code.

if __name__ == "__main__":

The main() method in unittest uses reflection to extract and run all of the methods in the object that start with “test” and executes them as the unit test suite.

PyUnit / Python’s Unittest Docs
Python Cheat Sheet
The first article in this sequence