<div class="notebook"> <div class="nb-cell html" name="htm1"> <h1>Programming the Natural Numbers</h1> <small><em>Author: Paul Brown (<a href="https://twitter.com/PaulBrownMagic" target="_blank" title="Twitter">@paulbrownmagic</a>)</em></small> </div> <div class="nb-cell markdown" name="md1"> The Natural Numbers are positive integers, including zero. They can be defined in terms of 0 and the successors of zero (we'll use `s` for short). Programming the Natural Numbers and their typical operators are a fantastic exercise in recursive thinking. Let's start by defining a natural number. </div> <div class="nb-cell program" data-background="true" data-singleline="true" name="p1"> natural_number(0). natural_number(s(N)) :- natural_number(N). </div> <div class="nb-cell query" data-chunk="3" name="q1"> natural_number(N). </div> <div class="nb-cell markdown" name="md2"> So s(0) is equivalent to 1 as it has one successions, s(s(0)) is two and so on. For the sake of our own programming convenience, let's make a translation predicate. </div> <div class="nb-cell program" data-background="true" name="p2"> translate(Succ, Int) :- translate_(Succ, Int), !. translate_(0, 0). translate_(s(N), I) :- translate_(N, X), I is X + 1. </div> <div class="nb-cell query" name="q3"> translate(s(s(0)), I). </div> <div class="nb-cell query" name="q2"> translate(Num, 3), !. </div> <div class="nb-cell markdown" name="md3"> Ok, now we can write some operators. # Comparison Operators There's 5 of these: <, ≤, =, ≥, >, plus their negations (such as ≠). Let's take two approaches to these, we should be able to define just < and = and capture the rest from those. Alternatively we could make a single compare operation and use the information from that to define all 5 more efficiently. </div> <div class="nb-cell program" name="p3"> % Inefficient but interesting version (defined locally) eq(0, 0). eq(s(N), s(M)) :- eq(N, M). less_than(0, s(_)). less_than(s(N), s(M)) :- less_than(N, M). greater_than(N, M) :- \+ eq(N, M), \+ less_than(N, M). less_than_eq(N, M) :- eq(N, M) ; less_than(N, M). greater_than_eq(N, M) :- \+ less_than(N, M). </div> <div class="nb-cell query" name="q4"> translate(N, 4), translate(M, 4), eq(N, M). </div> <div class="nb-cell query" name="q5"> translate(N, 3), translate(M, 4), less_than(N, M). </div> <div class="nb-cell query" name="q6"> translate(N, 5), translate(M, 4), greater_than(N, M). </div> <div class="nb-cell program" data-background="true" name="p4"> % More Efficient version (defined globally) % find the true operator, see which operators hold % for that case (4 = 4 & 4 ≤ 4 & 4 ≥ 4). comparrison(N, M, Op) :- comp(N, M, Case), lt_gt_eq(Case, Op). % comp gets the true comparrison case comp(0, 0, eq). comp(s(_), 0, gt). comp(0, s(_), lt). comp(s(N), s(M), Op) :- comp(N, M, Op). % alternative cases to the true operator. lt_gt_eq(Op, Op). lt_gt_eq(eq, lt_eq). lt_gt_eq(eq, gt_eq). lt_gt_eq(lt, lt_eq). lt_gt_eq(gt, gt_eq). </div> <div class="nb-cell markdown" name="md4"> </div> <div class="nb-cell query" name="q7"> translate(N, 4), translate(M, 4), comparrison(N, M, gt_eq). </div> <div class="nb-cell markdown" name="md5"> # Mathematical Operators We can compare values, now lets add, multiple, subtract and divide them. Due to Prolog working forwards and backwards, we only need to define two of these. Let's do the easier ones to reason about, addition and multiplication. </div> <div class="nb-cell program" data-background="true" name="p5"> % base-cases, only one required for recursion % but the other is required for completeness add(N, 0, N). add(0, N, N). % same logic as append/3, transfer structure across add(s(N), M, s(O)) :- add(N, M, O). </div> <div class="nb-cell query" name="q8"> maplist(translate, [N, M], [2, 3]), add(N, M, O), translate(O, Ans), format("~w + ~w = ~d~n", [N, M, Ans]). </div> <div class="nb-cell program" data-background="true" name="p6"> % base-cases, only one required for recursion % but the other is required for completeness multiply(0, _, 0). multiply(_, 0, 0). % multiply through repeated addition multiply(s(N), M, O) :- multiply(N, M, Oo), add(Oo, M, O). </div> <div class="nb-cell query" name="q9"> maplist(translate, [N, M], [2, 3]), multiply(N, M, O), translate(O, Ans), format("~w x ~w = ~d~n", [N, M, Ans]). </div> <div class="nb-cell program" data-background="true" name="p7"> % N - M = O % N = O + M % O + M = N % Also, we haven't defined negative numbers % so ensure N ≥ M subtract(N, M, O) :- comparrison(N, M, gt_eq), add(O, M, N). </div> <div class="nb-cell query" name="q10"> maplist(translate, [N, M], [4, 3]), subtract(N, M, O), translate(O, Ans), format("~w - ~w = ~d~n", [N, M, Ans]). </div> <div class="nb-cell program" data-background="true" name="p8"> % N ÷ M = O % N = O x M % O x M = N % Haven't defined floating point numbers, will fail % or fail to terminate for these cases. divide(N, M, O) :- comparrison(N, M, gt_eq), multiply(O, M, N). </div> <div class="nb-cell query" name="q11"> maplist(translate, [N, M], [6, 2]), divide(N, M, O), translate(O, Ans), format("~w ÷ ~w = ~d~n", [N, M, Ans]). </div> <div class="nb-cell markdown" name="md6"> # A Fun Application We've got some numbers we can use, so lets put them to use. This number structure is particularly suited to cases of recursion where we need to count down things, this is where you'll often find the clause `NextN is N - 1`, or some such thing. But with these numbers, there's no such need for that. So here's the Towers of Hanoi recursive puzzle solution using our numbers. The A, B, C variables denote the pegs, we're moving discs from A to B with C as an auxillary peg. </div> <div class="nb-cell program" data-background="true" name="p9"> :- op(100, xfx, to). % base case, move the single base disc hanoi(s(0), A, B, _C, [A to B]). hanoi(s(N), A, B, C, Moves) :- % There's some moves from A to C hanoi(N, A, C, B, AtoCmoves), % and some moves from C to B hanoi(N, C, B, A, CtoBmoves), % add those moves with that from A to B to % get all the moves append(AtoCmoves, [A to B|CtoBmoves], Moves). </div> <div class="nb-cell query" name="q12"> hanoi(s(s(s(0))), left, right, middle, Moves). </div> <div class="nb-cell markdown" name="md7"> # Conclusion and Challenge There's more of this, [check out "The Art of Prolog" by Sterling and Shapiro, chapter 3](https://mitpress.mit.edu/books/art-prolog-second-edition), which is Open Access. The Towers of Hanoi solution is from there, many of the predicates here are similar or practically the same as their solutions, there's only so many ways to skin a cat. Fancy a challenge? Why not extend this notebook to include other mathematical operations such as modulus, exponentional, or root. What about even and odd? Or why not close this, ignore it exists, and have a go at writing your own? Have fun! </div> </div>