/*
* Ruminations on recursive data types in Prolog
* (in a manner similar to ML)
*/
/* Some service predicates */
for(1).
for(I) :- for(I1), I is I1+1.
/*
* Declaration of a recursive class nat and an operation plus
* nat = {zero} + nat
*/
nat(zero).
nat(succ(X)) :- nat(X).
/* Several consecutive natural numbers */
?- asserta(count(1)), nat(X), write(X), nl, retract(count(I)), I1 is I+1,
asserta(count(I1)), I > 5.
/* operation plus */
/* plus(addendum1, addendum2, sum) */
plus(zero,X,X).
plus(succ(X),Y,succ(Z)) :- plus(X,Y,Z).
/* Example */
?- plus(succ(succ(succ(zero))),succ(succ(zero)),X).
/*
* Declaration of recursive types
* btree = {integer} + (btree * btree)
* Note that it declares a truly recursive type without using pointers
* (not even mentioning them).
*
*/
btree(leaf(X)) :- var(X), X = 0.
btree(leaf(X)) :- nonvar(X), integer(X).
btree(node(X,Y)) :- btree(X), btree(Y).
/* Generating a couple of btrees */
?- asserta(count(1)), btree(X), write(X), nl, retract(count(I)), I1 is I+1,
asserta(count(I1)), I > 5.
/* Dynamic type checking */
?- btree(leaf(0)).
?- btree(leaf(5)).
?- btree(leaf(atom)).
?- btree(X), btree(X). /* Check out what we've just created */
?- btree(node(leaf(1),leaf(2))).
?- X = node(node(leaf(1),leaf(3)),node(leaf(5),leaf(6))), btree(X).
?- X = node(node(leaf(1),leaf(3)),node(leaf(6))), btree(X).
/* Declaration of the selector */
get_value(leaf(I),I).
get_value(node(X,Y),I) :- get_value(X,I).
get_value(node(X,Y),I) :- get_value(Y,I).
?- get_value(leaf(0),X).
?- get_value(node(leaf(0),leaf(1)),X), display(X), nl, fail.
/*
* An assignment turns out pretty easy (theoretically). If
* X is bound to a, say, btree, and Y is free, then Y = X binds
* Y to the same btree. This is example of sharing. This may lead
* to a problem however:if X and Y are bound (point to) the same
* object then changing X has a side effect of automatically changing Y.
* But it is not the case here where changing of object is simply forbidden.
* If we need Y to be a btree with slightly different contents
* that X is, we must create a new btree (and fill it with some
* info extracted from X). Then this is a copy semantics.
* Thus, in the present case (case of PROLOG where recursive
* types are allowed), we use simple sharing semantics when
* it is appropriate, and copying semantics is used when it
* is required.
*
* The example below shows how to create a btree with a different
* contents, namely with the value of each leaf increased by one.
*/
/* incr_value(src,dest) */
/* dest is a copy of btree 'src' with */
/* the value of each leaf increased */
/* by one */
incr_value(leaf(I),leaf(I1)) :- I1 is I+1.
incr_value(node(X,Y),node(X1,Y1)) :- incr_value(X,X1), incr_value(Y,Y1).
?- X = node(leaf(1),node(leaf(5),leaf(6))),
write('Source btree'), nl, printq(X), nl,
incr_value(X,Y),
nl, write('btree with leaf values increased'), nl, display(Y).