Game Life in the language of Mercury

As part of experiments with the Mercury programming language, as well as under the impression that the Life game theme that has been raised several times lately here ( 1 , 2 , 3 ), I wanted to write my own implementation in this interesting programming language.

In a few words about Mercury. This functional-logic programming language was conceived as an improvement to prolog. The improvement consists in introducing static typing into the prologue (as well as declaring the determinism regime). As a result, the compiler has more opportunities to create an effective executable code, greater control at the compilation stage. Lovers of the prologue are probably familiar with the anecdote:

Q: How many Prolog programmers does it take to change a light bulb?
A: False.

In the kingdom of prologues, the Visual Prolog firmly occupies a niche typed. But, it is worth noting that the approaches of Visual Prolog and Mercury are quite different.

VIP hike is more conservative, and Mercury is more radical. For example, all imperative features of classical prologues, such as assert / retract, failure-driven loops, etc., were thrown out of mercury, and methods for working with input-output resemble those of Haskell, namely, every function that uses input-output The output must accept two additional variables: WorldIn and WorldOut, describing the state of the outside world before and after calling this function. These two variables are used to set the parametric dependencies between two consecutive function calls, which prohibits the compiler from rearranging them. In the absence of such a dependency, the compiler is free to shuffle the calls of functions / predicates as he pleases in order to optimize the resulting program. The VIP developers, on the contrary, not only did not remove imperative features, but even added OOP to their Prolog implementation.
')
In general, you can still tell a lot, but let's move on to the code. (For more information on the topic of Mercury, you can, if you wish, find on the official site , or on this Russian-language site ).

The implementation is actually based on the APL solution approach shown in this youtube video:
Game Life in one line APL code .

I'm sure that Prolog and Erlang experts will find the Mercury syntax very familiar.

:- module life. :- interface. :- import_module io. :- pred main(io, io). :- mode main(di, uo) is det. :- implementation. :- import_module int, list, require. :- type row == list(int). :- type grid == list(row). :- type sign ---> sum; mul; or_. :- type lr ---> left; right; no. :- type ud ---> up; down; no. eq([R | RR], N) = [eq_row(R, N) | eq(RR, N)]. eq([], _) = []. eq_row([H|T], N) = [(H=N->1;0) | eq_row(T,N)]. eq_row([],_) = []. sum(M1, M2) = R :- R1 = agg(M1, M2, sum) -> R = R1 ; error("can't sum"). or(M1, M2) = R :- R1 = agg(M1, M2, or_) -> R = R1 ; error("can't or"). mul(M1, M2) = R :- R1 = agg(M1, M2, mul) -> R = R1 ; error("can't mul"). sum_lst(L) = R :- ( L = [M1,M2|MM] -> R = sum_lst([sum(M1,M2)|MM]) ; L=[M] -> R = M ; error("sum_lst") ). :-func agg(grid, grid, sign) = grid is semidet. agg([R1 | RR1], [R2 | RR2], Sign) = [agg_rows(R1, R2, Sign) | agg(RR1, RR2, Sign)]. agg([], [], _) = []. :-func agg_rows(row, row, sign) = row is semidet. agg_rows([E1 | EE1], [E2 | EE2], Sign) = [agg_elts(E1, E2, Sign) | agg_rows(EE1, EE2, Sign)]. agg_rows([], [], _) = []. agg_elts(E1, E2, sum) = E1 + E2. agg_elts(E1, E2, mul) = E1 * E2. agg_elts(E1, E2, or_) = E1 \/ E2. hor([H | T], LR) = [hor_row(H, LR) | hor(T, LR)]. hor([], _) = []. head_det(L) = E :- ( L = [], error("empty list") ; L=[E1|_], E = E1 ). gen(T, N) = R :- ( N=0 -> R = [] ; R = [T|gen(T,N-1)] ). vert(M, up) = [zeros(M) | without_last(M)]. vert(M, down) = without_first(M) ++ [zeros(M)]. vert(M, no) = M. zeros(M) = gen(0, length(head_det(M))). without_first(L) = R :- ( L = [], error("without_first fail") ; L=[_ | T], R=T ). without_last(L) = R :- ( L=[], error("without_last fail") ; L=[_], R=[] ; L=[H,H1|T], R=[H|without_last([H1|T])] ). hor_row(L, left) = [0 | without_last(L)]. hor_row(L, right) = without_first(L) ++ [0]. hor_row(L, no) = L. :- func move(grid, ud, lr) = grid. move(M, UD, LR) = hor(vert(M, UD), LR). neighbours(M) = sum_lst([ move(M, up, left), move(M, up, no), move(M, up, right), move(M, no, left), move(M, no, no), move(M, no, right), move(M, down, left), move(M, down, no), move(M, down, right) ]). %% this is GoL algorithm %% next(M) = or(eq(MN,3), eq(mul(M,MN),4)) :- MN = neighbours(M). %% grid pretty-print %% print_m([H|T]) --> print_r(H), nl, print_m(T). print_m([]) --> []. print_r([H | T]) --> print_el(H), print_r(T). print_r([]) --> []. print_el(H) --> print(H=0->".";"#"). trace(M, N) --> ( {N = 0} -> [] ; print_m(M), nl, trace(next(M), N-1) ). m1 = [ [0,1,0,0,0,0,0,0,0,0], [0,0,1,0,0,0,0,0,0,0], [1,1,1,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,0,0] ]. main --> trace(m1,25). 

In fact, the key line of the entire algorithm is:

 %% this is GoL algorithm %% next(M) = or(eq(MN,3), eq(mul(M,MN),4)) :- MN = neighbours(M). 

which literally means: the cell will be alive in the next step, if its number of neighbors, including itself, is 3, or the number of neighbors, including itself, is 4 and the cell is alive.

Another interesting feature of mercury is the ability to infer types, as well as haskell. To do this, you need to compile with the --infer-all key:

 D:\stuff\test\mercury>mmc.bat --infer-all -s hlc.gc life.m life.m:021: Inferred :- func eq(list.list(list.list(T2)), T2) = life.m:021: list.list(list.list(int)). life.m:024: Inferred :- func eq_row(list.list(T2), T2) = list.list(int). life.m:027: Inferred :- func sum(list.list(list.list(int)), life.m:027: list.list(list.list(int))) = list.list(list.list(int)). life.m:028: Inferred :- func or(list.list(list.list(int)), life.m:028: list.list(list.list(int))) = list.list(list.list(int)). life.m:029: Inferred :- func mul(list.list(list.list(int)), life.m:029: list.list(list.list(int))) = list.list(list.list(int)). life.m:031: Inferred :- func sum_lst(list.list(list.list(list.list(int)))) = life.m:031: list.list(list.list(int)). life.m:047: Inferred :- func agg_elts(int, int, life.sign) = int. life.m:051: Inferred :- func hor(list.list(list.list(int)), life.lr) = life.m:051: list.list(list.list(int)). life.m:054: Inferred :- func head_det(list.list(T)) = T. life.m:060: Inferred :- func gen(T, int) = list.list(T). life.m:066: Inferred :- func vert(list.list(list.list(int)), life.ud) = life.m:066: list.list(list.list(int)). life.m:070: Inferred :- func zeros(list.list(list.list(T))) = list.list(int). life.m:072: Inferred :- func without_first(list.list(T)) = list.list(T). life.m:078: Inferred :- func without_last(list.list(T)) = list.list(T). life.m:086: Inferred :- func hor_row(list.list(int), life.lr) = list.list(int). life.m:093: Inferred :- func neighbours(list.list(list.list(int))) = life.m:093: list.list(list.list(int)). life.m:110: Inferred :- func next(list.list(list.list(int))) = life.m:110: list.list(list.list(int)). life.m:115: Inferred :- pred print_m(list.list(list.list(int)), io.state, life.m:115: io.state). life.m:115: Inferred :- mode print_m(in, di, uo) is det. life.m:118: Inferred :- pred print_r(list.list(int), io.state, io.state). life.m:118: Inferred :- mode print_r(in, di, uo) is det. life.m:121: Inferred :- pred print_el(int, io.state, io.state). life.m:121: Inferred :- mode print_el(in, di, uo) is det. life.m:123: Inferred :- pred trace(list.list(list.list(int)), int, io.state, life.m:123: io.state). life.m:123: Inferred :- mode trace(in, di, di, uo) is det. life.m:131: Inferred :- func m1 = list.list(list.list(int)). 

(Without this key, all signatures must be specified in the code).
Well, actually launch, illustrating the evolution of the glider:

 D:\stuff\test\mercury>life.exe .#........ ..#....... ###....... .......... .......... .......... .......... .......... .......... .......... #.#....... .##....... .#........ .......... .......... .......... .......... .......... .......... ..#....... #.#....... .##....... .......... .......... .......... .......... .......... .......... .#........ ..##...... .##....... .......... .......... .......... .......... .......... .......... ..#....... ...#...... .###...... .......... .......... .......... .......... .......... .......... .......... .#.#...... ..##...... ..#....... .......... .......... .......... .......... .......... .......... ...#...... .#.#...... ..##...... .......... .......... .......... .......... .......... .......... ..#....... ...##..... ..##...... .......... .......... .......... .......... .......... .......... ...#...... ....#..... ..###..... .......... .......... .......... .......... .......... .......... .......... ..#.#..... ...##..... ...#...... .......... .......... .......... .......... .......... .......... ....#..... ..#.#..... ...##..... .......... .......... .......... .......... .......... .......... ...#...... ....##.... ...##..... .......... .......... .......... .......... .......... .......... ....#..... .....#.... ...###.... .......... .......... .......... .......... .......... .......... .......... ...#.#.... ....##.... ....#..... .......... .......... .......... .......... .......... .......... .....#.... ...#.#.... ....##.... .......... .......... .......... .......... .......... .......... ....#..... .....##... ....##.... .......... .......... .......... .......... .......... .......... .....#.... ......#... ....###... .......... .......... .......... .......... .......... .......... .......... ....#.#... .....##... .....#.... .......... .......... .......... .......... .......... .......... ......#... ....#.#... .....##... .......... .......... .......... .......... .......... .......... .....#.... ......##.. .....##... .......... .......... .......... .......... .......... .......... ......#... .......#.. .....###.. .......... .......... .......... .......... .......... .......... .......... .....#.#.. ......##.. ......#... .......... .......... .......... .......... .......... .......... .......#.. .....#.#.. ......##.. .......... .......... .......... .......... .......... .......... ......#... .......##. ......##.. .......... .......... .......... .......... .......... .......... .......#.. ........#. ......###. 

Perhaps that's all for today.

Some more links:

1. The Windows distribution of the language mercury is available here: code.google.com/p/winmercury
2. Just a couple of examples on this YaP : langexplr.blogspot.com/search/label/mercury
3. Refresh view of Prolog: 1 , 2
4. Just a couple of one-liner games of life on k and q (descendants of APL, kx.com ): k , q