Prolog Learnings: FizzBuzz

3-minute read

Elixir builds on Erlang and the first versions of Erlang were implemented in Prolog, so it makes sense that Prolog and Elixir share a number of similarities. For example, Elixir and Prolog support pattern matching with function arguments, but;

  • Elixir evaluates arguments prior to performing pattern matching, while

  • Prolog does not perform argument evaluation, pattern matching is performed on the shape of whatever is passed as the argument.

Here is an example of FizzBuzz as implemented in Elixir (Fizzbuzz in Elixir).

Elixir
1
2
3
4
5
6
7
8
9

def fb(0, 0, _), do: "FizzBuzz"
def fb(0, _, _), do: "Fizz"
def fb(_, 0, _), do: "Buzz"
def fb(_, _, n), do: n
def fb(n), do: fb(rem(n, 3), rem(n, 5), n)

def fizzbuzz(n) do
  Enum.map(0..n, &fb/1)
end

Here is an example of Fizzbuzz as implemented in Prolog. Unlike Elixir, where modulo is evaluated and the result passed as an argument to the fb helper function, in Prolog, the result of the modulo calculations are first unified (Unification) with the Fizz and Buzz variables which are subsequently passed as arguments to the fizzbuzz_ auxilliary (helper) function.

Prolog
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

fizzbuzz(Count) :-
    Count > 0,
    Fizz is Count mod 5,
    Buzz is Count mod 3,
    fizzbuzz_(Fizz, Buzz, Count),
    CC is Count - 1,
    fizzbuzz(CC).

%% Matches when Count is divisible by 15.
%% Both 3 and 5.
fizzbuzz_(0, 0, _) :-
    !,
    write('FizzBuzz'), nl.

%% Matches when Count is divisible by 5.
fizzbuzz_(0, _, _) :-
    !,
    write('Fizz'), nl.

%% Matches when Count is divisible by 3.
fizzbuzz_(_, 0, _) :-
    !,
    write('Buzz'), nl.

% Matches when Count is neither divisible by 3 or 5.
fizzbuzz_(_, _, N) :-
    !,
    write(N), nl.

This example calculates the Greatest Common Denominator (GCD). Again, in Elixir the modulo is evaulated and the result is passed as the second argument in the recursive call to gcd.

Elixir
1
2
3
4

defmodule Gcd do
  def gcd(a, 0), do: a
  def gcd(a, b), do: gcd(b, rem(a, b))
end

However in Prolog, the modulo is first calculated and unified with the variable Rem which is then passed as an argument to gcd.

Prolog
1
2
3
4

gcd(A, 0, A).
gcd(A, B, Result) :-
    Rem is A mod B,
    gcd(B, Rem, Result).

Copying the Elixir syntax produces unexpected results as Prolog will search for a GCD function with a pattern matching the second argument A mod B and fail.

Prolog
1
2
3

gcd(A, 0, A).
gcd(A, B, Result) :-
    gcd(B, A mod B, Result).

We should also disable backtracking using ! (a "cut") when we know that there can only be a single answer, otherwise Prolog will prompt to find alternate solutions when there are none (just as in the Fizzbuzz example earlier.)

Prolog
1
2
3
4
5
6
7

gcd(A, 0, Result) :-
    !,
    Result = A.

gcd(A, B, Result) :-
    Rem is A mod B,
    gcd(B, Rem, Result).