% Unary arithmetics in Prolog, as a warm-up. % % Representation of numbers: lists of atoms 'u' % generators for unary numerals. genu([]). genu([u|X]) :- genu(X). % The illustration of the failure of the solution set monotonicity % for the infinite solution set and SLD mf([],Y) :- genu(Y). mf([u|X],Y) :- mf([u|X],Y). % successor: only one clause. NB: succ is an internal predicate. succs(X,[u|X]). % ?- succs([u,u],X). % X = [u, u, u] % ?- succs(X,[u,u]). % X = [u] % ?- succs(X,[]). % finite failure % ?- succs(X,X). % With the occurs check, finite failure % Unbound variables % ?- succs(X,Y). %% X = _G183 %% Y = [u|_G183] ; %% succeeds with only one solution: finite representation of %% the infinite number of solutions. % addition/subtraction. Just the regular append... add([],X,X). add([u|X],Y,[u|Z]) :- add(X,Y,Z). % Forward % ?- add([u],[u,u],X). %X = [u, u, u] % backward % ?- add(X,[u],[u,u,u]). % X = [u, u] % ?- add([u],X,[u,u,u]). % X = [u, u] % ?- add(X,[u,u,u],[u]). % finite failure % All summands % ?- bagof((X,Y), add(X,Y,[u,u,u]), R). % R = [ ([], [u, u, u]), ([u], [u, u]), ([u, u], [u]), ([u, u, u], [])] % all unbound: enumeration % ?- add(X,Y,Z). % X = [] % Y = _G184 % Z = _G184 ; % X = [u] % Y = _G184 % Z = [u|_G184] % ?- call_with_depth_limit((add(X,Y,Z), print([X,Y,Z]), nl, fail),5,_). % [[], _G184, _G184] % [[u], _G184, [u|_G184]] % [[u, u], _G184, [u, u|_G184]] % [[u, u, u], _G184, [u, u, u|_G184]] % could have added a clause add(X,[],X). But would lead to duplication % in the above enumeration. % multiplication/division % First attempt mul1([],_,[]). mul1([u|X],Y,Z) :- mul1(X,Y,Z1), add(Z1,Y,Z). % ?- mul1([u,u],[u],X). % ?- mul1([u,u,u],[u,u],X). % X = [u, u, u, u, u, u] ; % ?- mul1(X,[u,u],[u, u, u, u, u, u]). % X = [u, u, u] ; % but diverges further down... % ?- mul1(X,[u,u],[u, u, u, u, u]). % diverges % actually, % ?- mul1(X,Y,Z). % gives % X = [] Y = _G184 Z = [] ; % X = [u] Y = _G184 Z = _G184 ; % X = [u, u] Y = [] Z = [] ; % X = [u, u] Y = [u] Z = [u, u] ; % X = [u, u] Y = [u, u] Z = [u, u, u, u] ; % X = [u, u] Y = [u, u, u] Z = [u, u, u, u, u, u] ; % etc. X gets stuck at two. % Or, more clearly % % ?- mul1(X,Y,[u,u,u,u,u,u]). % X = [u] Y = [u, u, u, u, u, u] ; % X = [u, u] Y = [u, u, u] ; % X = [u, u, u] Y = [u, u] ; % ERROR: Out of global stack % One may think the problem can be fixed merely by swapping add and mul: mul2([],_,[]). mul2([u|X],Y,Z) :- add(Z1,Y,Z), mul2(X,Y,Z1). % ?- mul2(X,[u,u],[u, u, u, u, u, u]). % singleton: X = [u, u, u] ; % ?- mul2(X,[u,u],[u, u, u, u, u]). % finite failure % ?- mul2([u,u,u],[u,u],X). % X = [u, u, u, u, u, u] ; % and then diverges when trying to find the second solution. % ?- mul2(X,Y,[u, u, u, u, u, u]). % after yielding 4 solutions, gives `ERROR: Out of local stack' mul3([],_,[]). mul3([u|X],Y,Z) :- add(Y,Z1,Z), mul3(X,Y,Z1). % ?- mul3(X,[u,u],[u, u, u, u, u, u]). % singleton: X = [u, u, u] ; % ?- mul3(X,[u,u],[u, u, u, u, u]). % finite failure % ?- mul3([u,u,u],[u,u],X). % singleton X = [u, u, u, u, u, u] ; % ?- mul3(X,Y,[u, u, u, u, u, u]). % ERROR: Out of global stack % A terminating mul % X+Y <= Z1 < Z less3([],[],_,[u|_]). less3([],[u|Y],[u|Z1],[u|Z]) :- less3([],Y,Z1,Z). less3([u|X],Y,[u|Z1],[u|Z]) :- less3(X,Y,Z1,Z). % We can derive that for x >= 1 and y >= 1, % xy + 1 >= x + y % Equality is achieved for y=1. For y>1, we have y-1 >= y-1 and positive. % multiplying by the inequality x > 1 gives the result. % mul([],_,[]). % mul([u],Y,Y). % mul([u,u|_],[],[]). % mul([u,u|X],[u|Y],Z) :- % less3([u|X],[u|Y],[u|Z1],[u|Z]), % mul([u|X],[u|Y],Z1), % add([u|Y],Z1,Z). mul([],_,[]). mul([u|_],[],[]). mul([u|X],[u|Y],Z) :- add([u|Y],Z1,Z), mul(X,[u|Y],Z1). %---------------------------------------------------------------------- % Tests % Auxiliary predicate to build and show binary numerals. % The following predicate is not the part of the system, strictly speaking. % It is also `impure'. None of the other predicates need +/- annotations % because they can be used in any mode whatsoever, and none of the % other predicates use cut. % The auxiliary predicate is "input-output", to input and output numerals % from/into more convenient representation. I must say that % the binary notation is not too bad per se. ?- op(700,xfx,isb). % +PrologNum isb -OurNum % -PrologNum isb +OurNum 0 isb []. N isb L :- number(N), N > 0, !, N1 is N-1, L = [u|L1], N1 isb L1. N isb [u|L1] :- !, N1 isb L1, N is N1 + 1. sh1(L,LR) :- maplist((isb),LR,L). sh2(L,LR) :- maplist(sh1,L,LR). okn(B,N) :- N1 isb B, N1 =:= N *-> (print('as expected: '),print(N),nl); throw(mismatch(B,N)). okt(T1,T2) :- T1 = T2 *-> (print('as expected: '),print(T1),nl); throw(mismatch(T1,T2)). should_fail(G) :- G, !, throw(should_have_failed(G)). should_fail(_). ?- nl, print('Multiplication tests'), nl. ?- mul([u,u],[u],X), okn(X,2). ?- 12 isb A12, 3 isb A3, mul(A3,X,A12), okn(X,4). ?- 12 isb A12, 3 isb A3, mul(X,A3,A12), okn(X,4). ?- 12 isb A12, 5 isb A5, should_fail(mul(_,A5,A12)). % ?- mul([u,u],[u,u,u],X). % X = [u, u, u, u, u, u] ; % ?- mul([u,u,u],[u,u],X). % X = [u, u, u, u, u, u] ; % ?- mul(X,[u,u],[u, u, u, u, u, u]). % X = [u, u, u], only one % ?- mul(X,[u,u],[u, u, u, u, u]). % finite failure % ?- bagof((X,Y),mul(X,Y,[u,u,u]),R). % R = [ ([u], [u, u, u]), ([u, u, u], [u])] % ?- bagof((X,Y),mul(X,Y,[u,u,u,u]),R). % R = [ ([u], [u, u, u, u]), ([u, u], [u, u]), ([u, u, u, u], [u])] % ?- call_with_depth_limit((mul(X,Y,Z), print([X,Y,Z]), nl, fail),7,_). ?- print('All factors of 24'), nl. ?- 24 isb A24, findall([X,Y],mul(X,Y,A24),R), sh2(R,LR), okt(LR, [[24, 1], [12, 2], [8, 3], [6, 4], [4, 6], [3, 8], [2, 12], [1, 24]]). ?- print('2 * 3 must produce only one answer'), nl. ?- 2 isb A2, 3 isb A3, findall(Z,mul(A2,A3,Z),R), sh1(R,LR), okt(LR,[6]), nl. ?- nl, print('a few numbers such as 3*X = Y'), nl. ?- call_with_depth_limit((mul([u,u,u],X,Y),print([X,Y]), nl, fail),9,_). ?- nl, print('a few numbers such as X*3 = Y'), nl. ?- call_with_depth_limit((mul(X,[u,u,u],Y),print([X,Y]), nl, fail),7,_). ?- nl, print('a few numbers such as X*Y = Z'), nl. ?- call_with_depth_limit((mul(X,Y,Z),print([X,Y,Z]), nl, fail),7,_). % however, if we check mul(X,Y,Z), we see that we get stuck on Y=[u]. % test of recursive enumerability % mul(X,Y,Z), [X,Y,Z]=[[u,u], [u,u,u], [u,u,u,u,u,u]]. % mul(X,Y,Z), [Y,X,Z]=[[u,u], [u,u,u], [u,u,u,u,u,u]]. % diverges %---------------------------------------------------------------------- % Terminating and recursively enumerating (for the half of the domain) % mul. % less(X,Y) holds if X is less than Y. less([],[_|_]). less([u|X],[u|Y]) :- less(X,Y). % We can derive that for x >= 1 and y >= 1, % xy + 1 >= x + y % Equality is achieved for y=1. For y>1, we have y-1 >= y-1 and positive. % multiplying by the inequality x > 1 gives the result. semimul([],_,[]). semimul([u|_],[],[]). semimul([u|X],[u|Y],Z) :- less(X,Z), less(Y,[u|X]), mul([u|X],[u|Y],Z). semimul([u|Y],[u|X],Z) :- less(X,Z), less(Y,X), mul([u|X],[u|Y],Z). ?- nl, print('Multiplication tests, for semimul now'), nl. ?- semimul([u,u],[u],X), okn(X,2). ?- 12 isb A12, 3 isb A3, semimul(A3,X,A12), okn(X,4). ?- 12 isb A12, 3 isb A3, semimul(X,A3,A12), okn(X,4). ?- 12 isb A12, 5 isb A5, should_fail(semimul(_,A5,A12)). % ?- semimul([u,u],[u,u,u],X). % X = [u, u, u, u, u, u] ; % ?- semimul([u,u,u],[u,u],X). % X = [u, u, u, u, u, u] ; % ?- semimul(X,[u,u],[u, u, u, u, u, u]). % X = [u, u, u], only one % ?- semimul(X,[u,u],[u, u, u, u, u]). % finite failure % ?- bagof((X,Y),semimul(X,Y,[u,u,u]),R). % R = [ ([u], [u, u, u]), ([u, u, u], [u])] % ?- bagof((X,Y),semimul(X,Y,[u,u,u,u]),R). % R = [ ([u], [u, u, u, u]), ([u, u], [u, u]), ([u, u, u, u], [u])] % ?- call_with_depth_limit((semimul(X,Y,Z), print([X,Y,Z]), nl, fail),7,_). ?- print('All factors of 24'), nl. ?- 24 isb A24, findall([X,Y],semimul(X,Y,A24),R), sh2(R,LR), okt(LR, [[6, 4], [8, 3], [12, 2], [24, 1], [4, 6], [3, 8], [2, 12], [1, 24]]). ?- print('2 * 3 must produce only one answer'), nl. ?- 2 isb A2, 3 isb A3, findall(Z,semimul(A2,A3,Z),R), sh1(R,LR), okt(LR,[6]), nl. ?- nl, print('a few numbers such as 3*X = Y'), nl. ?- call_with_depth_limit((semimul([u,u,u],X,Y),print([X,Y]), nl, fail),9,_). ?- nl, print('a few numbers such as X*3 = Y'), nl. ?- call_with_depth_limit((semimul(X,[u,u,u],Y),print([X,Y]), nl, fail),7,_). ?- nl, print('a few numbers such as X*Y = Z'), nl. ?- call_with_depth_limit((semimul(X,Y,Z),print([X,Y,Z]), nl, fail),7,_). ?- nl, print('Recursive enumerability of multiplication'), nl. ?- semimul(X,[u,u,u],Y),3 isb X, okn(Y,9). ?- semimul(X,[u,u,u],Y),9 isb Y, okn(X,3). ?- 3 isb X, semimul(X,[u,u,u],Y), okn(Y,9). ?- semimul(N,M,P), ((N=[u,u,u,u,u], M=[u,u,u,u]); (N=[u,u,u,u], M=[u,u,u,u,u])), okn(P,20). ?- print('Test to see that semimul(X,Y,Z) contains all numbers '), print('such as X*Y=Z, Y<=X'), nl. et(I,J,P) :- semimul(X,Y,Z), (X = I, Y = J; X = J, Y = I), Z = P, sh1([X,Y,Z],R), print(R), nl, !. et(L) :- less(I,L), less(J,L), et(I,J,_), fail. et(_). ?- 8 isb L, et(L).