Fizz Buzz implemented in Erlang

[Mark44]

TL;DR Summary

Screeners for applicants of programmer jobs have used Fizz Buzz for decades. A typical test would be to ask the applicant to write a program in any language that prints the integers from 1 to 100, with these exceptions. Numbers that are divisible by 3 should be replaced by "Fizz", numbers that are divisible by 5 should be replaced by "Buzz," and numbers that are divisible by 15 should be replaced by "FizzBuzz."

Fizz Buzz has been discussed in many online blogs are articles, in a multitude of programming languages. It has been widely used as a screening device for those aspiring to obtain developer positions. The job candidate is asked to write some code to print the numbers 1 through 100, with "Fizz" replacing numbers that are multiples or 3, "Buzz" replacing numbers that are multiples of 5, and "FizzBuzz" replacing numbers that are multiples of 15.
This has been surprisingly difficult for many applicants of programming positions.

Without further ado, here's my code:

-module(fizz).
-export([fb/1]).

fb(Max) -> fb(1, Max).

fb(Num, Max) ->
  if Num == Max + 1 -> exit("Normal exit");
     Num rem 15 == 0 -> io:format("FizzBuzz~n");
     Num rem 3 == 0 -> io:format("Fizz~n");
     Num rem 5 == 0 -> io:format("Buzz~n");
     true -> io:format("~w~n", [Num])
  end,
  fb(Num + 1, Max).

Some points about the code, which would be invoked from the Erlang interpreter.

• The first two lines 1) identify this as the fizz module, and 2) export a function named fb (short for fizzbuzz) that takes one parameter.
• The fb() function is overloaded, with one version that takes a single parameter and another that takes two parameters. Only the single-parameter variant is exported.
• When fb(Max) is called from the interpreter, it immediately calls the two-parameter version via fb(1, Max).
• Unlike most other programming languages, Erlang doesn't have any syntax for loop constructs. Instead, it usually relies on recursion. The two-parameter version first checks whether the current value of Num is equal to Max + 1. If so, the program exits.
• Erlang if blocks consist of a number of patterns to be matched. In the program above, the patterns to be matched check whether Num is still in range (i.e., from 1 through Max), whether Num is divisible by 15, whether Num is divisible by 3, whether Num is divisible by 5, and finally a catchall if none of the previous patterns has been matched.
• All but the first pattern cause output of one of the strings "Fizz", "Buzz", or "FizzBuzz" to be displayed or the number itself. All are followed by a newline character.
• After the if block is a recursive call to fb(Num + 1, Max). This happens to be tail-call-recursive, which means that the recursive call is at the end of the code. The Erlang interpreter is able to transform tail-call-recursive functions into loops, ameliorating the problem of stack overflow that recursive functions are prone to in other languages.

 

[pbuk]

TL;DR In languages that support it, the ternery operator can be useful in implementing concise algorithms (although Python's implementation was a strange choice).

I can't resist providing what is probably the shortest JavaScript solution:

for(i=0;i<100;)console.log((++i%3?'':'Fizz')+(i%5?'':'Buzz')||i)

Or not very much longer written in accordance with common standards:

for (let i = 0; i < 100; ++i) {
  console.log((i % 3 ? '' : 'Fizz') + (i % 5 ? '' : 'Buzz') || i);
}

C++ is similar, once you have created std::strings that support the + operator. In Python:

for i in range(1,101):
    print(('' if i % 3 else 'Fizz') + ('' if i % 5 else 'Buzz') or i)

 

[Vanadium 50]

I was asked to do this, fairly well-advanced in my career, so with some annoyance, I wrote this:

main() {
    printf("1\n");
    printf("2\n");
    printf("Fizz\n");
    printf("4\n");
    printf("Buzzn");
       ...
}

Then at least we were both annoyed.

So why Erlang?

 

[Ibix]

I was asked to do this, fairly well-advanced in my career, so with some annoyance, I wrote this:

main() {
    printf("1\n");
    printf("2\n");
    printf("Fizz\n");
    printf("4\n");
    printf("Buzzn");
       ...
}

Then at least we were both annoyed.

I think I would have been unable to resist writing a script to generate the printfs. And at that point the script might as well call gcc and execute the binary...

 

[Mark44]

So why Erlang?

Basically, just for the heck of it. After reading a blog post by Joel Spolsky several years ago, I decided to get acquainted with functional programming, and started with Lisp. A couple of years ago, I decided to learn some F#, which I played with awhile. More recently, I wanted to explore some different functional programming languages, such as Eiffel or Haskell, but wound up looking at Erlang. I've posted a couple other examples of some Erlang code I cobbled together. There's a lot about it I don't understand yet...

 

[berkeman]

Unlike most other programming languages, Erlang doesn't have any syntax for loop constructs. Instead, it usually relies on recursion.

Yikes. On the small uCs that I code for often, this would overflow the app stack quickly. How does Erlang handle these demands on the stack with its recursive paradigm?

 

[Vanadium 50]

Unlike most other programming languages, Erlang doesn't have any syntax for loop constructs. Instead, it usually relies on recursion.

I guess if memory is cheap enough...

 

[Vanadium 50]

I think I would have been unable to resist writing a script to generate the printfs.

Or, you could write a script to write the script....

I recall them complaining about how long it would take to enter this (not long - 15 lines, one cut, 7 pastes and some fixups) and I said "Yeah, but look how much I'll save in debugging!"

Then they were even more annoyed.

 

[berkeman]

Then they were even more annoyed.

You could have just said that you were also a big fan of the Kobayashi Maru Scenario challenge...

 

[Filip Larsen]

How does Erlang handle these demands on the stack with its recursive paradigm?

The snippet Mark gave is tail recursive which is handled efficiently by many languages without additional stack usage. And even with body recursion I understand that Erlang has a mechanism to remove references to dead references on recursion which significantly reduces memory consumption and garbage collection performance. Also, as far as I know, Erlang uses message parsing between lightweight processes and not "function calls", so the traditional stack usage on body recursion is not there either.

Edit: The above should be true for single recursive messages. However, I presume multiple recursive messages in Erlang, i.e. a process that send itself two or more new messages on each activation, will result in an extra message on the message queue on next activation, thus it probably still is possible to have a badly designed Erlang process to "run out of memory" in some way.

 

[pbuk]

Implementation using the ternery operator in Julia is a little more verbose due to Julia's strict typing:

for i in 1:100
    s = (i % 3 > 0 ? "" : "Fizz") * (i % 5 > 0 ? "" : "Buzz")
    println(length(s) > 0 ? s : i)
end

This implementation also illustrates Julia's mathematically preferable overloading of the * operator to provide string concatenation rather than + as in many other languages (think about commutativity and inverses in the context of e.g. matrices).

Note that we can achieve a similar result without using the ternery operator due to another interesting feature of Julia, similar to many Lisp dialects:

for i in 1:100
    s = string(if i % 3 > 0 "" else "Fizz" end, if i % 5 > 0 "" else "Buzz" end)
    println(if length(s) > 0 s else i end)
end

 

[Vanadium 50]

Julia's strict typing:

As they say, "strong typing is for people with weak memories."

 

[Vanadium 50]

Kobayashi Maru

Why is this cheating? The problem doesn't specify a loop. Besides, for all I know the compiler is going to unroll it anyway.

What's really the objection? It's that 100 print statements is not very flexible. What if we want to replace 'Fizzz' with 'Phizz', or print in reverse order, or use 7 and 11 instead of 3 and 5. But I would argue:

1. In 30 seconds I got you to state another requirement. I should get credit for that, not blame.
2. Just as it is possible to write code that is not general enough, it is possible to write code that is too general. I can spend days on writing code that takes as input a list of Fizzy and Buzzy words, and another list of factors that may or may not be relatively prime, and write the Ultimate Generalized FizzBuzz. Or you could have bug-free code that meets the requirements after a few minutes. Which do you want?

The "cheating" " is that I treated this not as a coding question but as ananalysis question. "Do the right job" as opposed to "do the job right".

 

[Mark44]

I guess if memory is cheap enough...

If the recursion is tail-recursive, the Erlang interpreter does the recursion as a loop, so there's not the hit on stack memory that many other languages would suffer.

 

[Filip Larsen]

If the recursion is tail-recursive, the Erlang interpreter does the recursion as a loop

I understand send messages, even when to self, to semantically work as if they are appended to the receive queue for the process. One effect of this would be that messages sent from other processes to a process busy in a recursive (tail or body) "loop" will be merged into the messages processed.

Edit: OK, disregard that. I can see I got messages mixed up with functions.

 

[Mark44]

Yikes. On the small uCs that I code for often, this would overflow the app stack quickly. How does Erlang handle these demands on the stack with its recursive paradigm?

Sorry, I missed your earlier comment, Mike. Your question about the demand on stack memory by multiple recursive calls was addressed by me a few posts after yours, as well as the post by @Filip Larsen, partially quoted below.

If the recursive function is tail-recursive, the code that the Erlang interpreter generates essentially converts the chain of calls to a loop. I just ran my code asking it to display the integers from 1 through 20,000. Using the Performance pane of Task Manager, there was hit on memory that I could discern.

The snippet Mark gave is tail recursive which is handled efficiently by many languages without additional stack usage.

Also, as far as I know, Erlang uses message parsing between lightweight processes and not "function calls", so the traditional stack usage on body recursion is not there either.

Right, you can spawn a ton of processes that can communicate with each other via messages. The program I wrote is just a single process, though, with a sequence of recursive function calls. The only communication between successive calls is via the parameter in the call and the value returned by each call.

 

[Vanadium 50]

Right - just because the code is recursive doesn't mean the compiler output is.

A few years ago I found myself looking at the assembler output of the compiler. The optimizers are quite aggressive - it thought nothing of unrolling loops, changing loop order, order of execution, etc.