Prolog - gregorymorrison/euler1 GitHub Wiki

Prolog, introduced in 1972, is a different beast that involves writing a bunch of true statements about a problem domain and then letting its fact engine distill some solution from it. Here is my Euler1. Notice that my assertions mostly take the form of canonical Functional programming operations:

#!/usr/bin/pl -q -t euler -f

range(N, N, [N]).
range(Start, End, Result) :-
	Start < End,
	Next is Start + 1,
	range(Next, End, Partial),
	Result = [Start | Partial].

filter([], []).
filter([H|T], Result) :-
	test(H),
	filter(T, Partial),
	Result = [H | Partial].
filter([H|T], Result) :-
	not(test(H)),
	filter(T, Result).

sum([], 0).
sum([H|T], Total) :-
	sum(T, SemiTotal),
	Total is H + SemiTotal.

test(N) :- N mod 3 =:= 0.
test(N) :- N mod 5 =:= 0.

euler :-
	range(1, 999, MyRange),
	filter(MyRange, MyFilteredRange),
	sum(MyFilteredRange, MyAnswer),
	format('~w~n', [MyAnswer]).

Notice also that there are two versions of test() here. These two function declarations have identical signatures and would be illegal in imperative languages. Even in functional languages that allow multiple identical signatures and use guards for differentiation, this is illegal. That's because as stated earlier, test() is not a function - it's an assertion. Here I declare that my integer must be divisible by 3. Also, it must be divisible be 5. Like I said, the whole program is simply a compendium of true statements.

Like every other Turing-complete language that strives for ideologically purity, Prolog has to make compromises in its design. Prolog's seem to take the shape of including side-effects in with the assertions. Instead of an assertion being a simple true-false declaration, it's actually a collection of Turing-complete statements. Witness this more compact, more Prolog idiomatic version of Euler1:

#!/usr/bin/pl -q -t euler -f

solve(Start, End, Total) :-
	write('Entering solve')
	(Start mod 3 =:= 0; Start mod 5 =:= 0),
	Start < End,
	Next is Start + 1,
	solve(Next, End, SemiTotal),
	Total is SemiTotal + Start.
solve(Start, End, Total) :-
	Start < End,
	Next is Start + 1,
	solve(Next, End, Total).
solve(N, N, N).

euler :-
	solve(1, 999, MyAnswer),
	format('~w~n', [MyAnswer]).

Here each version of solve() is a collection of operations. The first one reads:

A blatant side effect - output something to the console.
Start must be divisible by 3 and 5.
Start must be less than End.
Define a local variable NEXT equal to Start + 1.
Recursively call solve().
Assign the result to our Pass-By-Reference variable, Total.

As you can see, points 2 and 3 above serve as guards for pattern matching. The runtime will execute the first version of solve() in which all initial conditions are true.

Also note that Prolog uses Pass-By-Reference to return values. You must include a return variable in your ~~method signature~~ assertion to get anything back from it. Returning values from an assertion sounds like a side-effect to me, as does the I/O operation at the end that prints out the final answer.

I must say, it took me a long time to wrap my head around this language. On paper it doesn't look that complicated, but I struggled for a couple of days to write this simple problem, and even then I had to give up and Google a solution. It's a very different environment - I spent an entire day just trying to figure out how to print a variable's value to the console! Even after all this, I still lack fundamental knowledge of how this runtime works.

Normally, Prolog is executed as statements in an interactive REPL. But SWI-Prolog allows for sessions to be compiled into an executable script. Just make sure that you include the same arguments that I did in the shebang. To install SWI-Prolog on Fedora, yum install pl and yum install pl-devel.

$ ./euler1.prlg
233168