FizzBuzz (Lisp)

From LiteratePrograms
Jump to: navigation, search

FizzBuzz is a common exercise program, such as Hello, world! or 99 Bottles of Beer. It is based on a common game of the same name. The program prints a series of natural numbers, substituting those divisible by 3 with "Fizz", those divisible by 5 with "Buzz" and those divisible by both 3 and 5 with "FizzBuzz".

The fizzbuzz challenge is a simple introduction to output and control structures for the implementation language. (The sort of problem ideally suited to rosetta code.) The three possible tags become the conditions of several branches. These are tested and printed for each number in the sequence. We proceed through the sequence either through recursion or an iterative loop.

We begin functions with the defun keyword and follow with the list of arguments. While most fizzbuzz implementations hardcode the limits 0 & 100, we will permit the caller to specify the length of the output. This way we can keep the output succinct as we develop and test the function.


[edit] Recursive

The algorithm involves printing the output and then moving to the next value in the sequence. We will begin with recursion at this time and print from the provided value to zero. We accomplish this by calling fbzz with a decremented argument. Note that we write lisp expressions in preorder. The operation is the first element of the list, followed by the arguments. Were 1 & left in the reverse order, it would evaluate to "1 - left" Common lisp also has a shorter convention for subtracting a number by one, (1- left).

(defun fbzz (left)
  determine output
  ( fbzz (- left 1) )

Common Lisp outputs strings via (format MODE "string perhaps with flags" any_arguments_to_flags). MODE is an argument that specifies the fate of the assembled string. T will send the string to standard output. (We discuss other flags below.) Using ~S in our string directs format to insert left into the string independent of type. We print the rest of the line, based on which case applies, and finish by setting the cursor on the next line. The ~% directive becomes the end line character.

<<determine output>>=
(format t "~S " left)
base case
printing cases
(format t "~%")

As in all recursion, we concern ourselves first with the base case. Fbzz will count down, so zero is the last value. The predicate zerop replies whether left is zero. In that case, we need to end the recursion. As we are generating a side effect rather than returning anything, we accomplish this with return-from. This demands some care, as return-from allows us to return even higher in the call stack if we tell it to. Otherwise, we return nil, as it is irrelevant.

<<base case>>=
 ( if (zerop left)
   ( return-from fbzz nil ) nil )

Failing the base case, we proceed to the meat of the exercise: print fizz and/or buzz. (mod candidate base) reports the modulus - difference from the next multiple - of base and candidate. So, (mod 10 5) is 0 and (mod 5 10) is 5. The task specifies fizz for multiples of 3 and buzz for multiples of 5. As we didn't break to the next line, the interpreter will check and execute both conditions for multiples of 15. This results in fizzbuzz, which takes care of the recursive version. It is worth noting that these ifs are not if/else chains. We do so, below, in the iterative version. We won't here, as the cases are independent.

<<printing cases>>=
( if (zerop (mod left 3))
   (format t "fizz") nil)
( if (zerop (mod left 5))
   (format t "buzz") nil)

[edit] Iterative

To highlight our alternatives, we now examine an iterative version of fizzbuzz called fzzb. We can accomplish this using the dotimes function. It demands expressions of the form (dotimes (start finish) (body) ). It is similar to the for loop of most imperative languages. Its iteration will increment line by 1 until it reaches limit. We initialized line using the let binding. Here, it locally binds 0 to line. If line were defined outside the let expression, it would return to its initial value.

(defun fzzb (limit)
  (let (line '1)
  (dotimes (line limit)
    print line
choose output

Then, we define the body of the dotimes loop. Format will print it for us, as before, when sent the t flag. However, we will extract the fizzbuzz logic into another function. It will provide us the whole line rather than print it piecewise.

<<print line>>=
(format t ( fb_str line ))

Most implementations simply include the % 15 = 0 rather than build up the fizzbuzz output. This is more elegantly done with cond. and evaluate as Nil. We supply nil when we want format to evaluate as the string.

As noted in the recursive version, fizz and buzz are independent portions of the final string. So, as with most published implementations, we will handle the multiple_of_15 case separately. Facing three separate, but dependent cases, we use the cond form. This is the typical if/elseif/else form seen in other languages. As we produce the whole string, we can also send format the nil argument, unlike above. Now, format will evaluate to the string built with the rest of its arguments. (In our case, the line, maybe the output, and a new line.) There are other format flags, but they are well outside of our scope.

<<choose output>>=
(defun fb_str (at)
    ( (zerop (mod at 15))
      ( format nil "~S fizzbuzz~%" at ) )
    ( (zerop (mod at 3))
      ( format nil "~S fizz~%" at ) )
    ( (zerop (mod at 5))
      ( format nil "~S buzz~%" at ) )
    ( t ( format nil "~S ~%" at ) )

[edit] Execution

With common lisp, we may choose to use the interpreter or compile the script and run the binary. Assuming we use the interpreter, it is still best to save and load your functions in a file.

This portion doesn't go in the file. It is entered in the interpreter. Typically, fizzbuzz is called with 100, but this isn't essential to the problem. Numbers below 20 capture all the cases we are concerned with during testing. The following output is excerpted for fbzz.

; (fbzz 21)
21 fizz
20 buzz
18 fizz
15 fizzbuzz
12 fizz

; (fzzb 15)
3 fizz
5 buzz
6 fizz
9 fizz
10 buzz
12 fizz
15 fizzbuzz
Download code