%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% This is a rough approximation to the algorithm presented in:
%
% "An Algorithm for NAND Decomposition Under Network Constraints,"
% IEEE Trans. Comp., vol C-18, no. 12, Dec. 1969, p. 1098
% by E. S. Davidson.
%
% Written by Bruce Holmer
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% I have used the paper's terminology for names used in the program.
%
% The data structure for representing functions and variables is
% function(FunctionNumber, TrueSet, FalseSet,
% ConceivableInputs,
% ImmediatePredecessors, ImmediateSuccessors,
% Predecessors, Successors)
%
%
% Common names used in the program:
%
% NumVars number of variables (signal inputs)
% NumGs current number of variables and functions
% Gs list of variable and function data
% Gi,Gj,Gk,Gl individual variable or function--letter corresponds to
% the subscript in the paper (most of the time)
% Vector,V vector from a function's true set
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
nand(ShowResult) :- nand_main(0, ShowResult).
nand_main(N, ShowResult) :-
init_state(N, NumVars, NumGs, Gs),
add_necessary_functions(NumVars, NumGs, Gs, NumGs2, Gs2),
test_bounds(NumVars, NumGs2, Gs2),
search(NumVars, NumGs2, Gs2, ShowResult).
nand_main(_, ShowResult) :-
( ShowResult = true ->
write('Search completed'), nl
; true).
% Test input
% init_state(circuit(NumInputs, NumOutputs, FunctionList))
init_state(0, 2, 3, [ % 2 input xor
function(2, [1,2], [0,3], [], [], [], [], []),
function(1, [2,3], [0,1], [], [], [], [], []),
function(0, [1,3], [0,2], [], [], [], [], [])
]) :-
update_bounds(_, 100, _).
init_state(1, 3, 4, [ % carry circuit
function(3, [3,5,6,7], [0,1,2,4], [], [], [], [], []),
function(2, [4,5,6,7], [0,1,2,3], [], [], [], [], []),
function(1, [2,3,6,7], [0,1,4,5], [], [], [], [], []),
function(0, [1,3,5,7], [0,2,4,6], [], [], [], [], [])
]) :-
update_bounds(_, 100, _).
init_state(2, 3, 4, [ % example in paper
function(3, [1,2,4,6,7], [0,3,5], [], [], [], [], []),
function(2, [4,5,6,7], [0,1,2,3], [], [], [], [], []),
function(1, [2,3,6,7], [0,1,4,5], [], [], [], [], []),
function(0, [1,3,5,7], [0,2,4,6], [], [], [], [], [])
]) :-
update_bounds(_, 100, _).
init_state(3, 3, 4, [ % sum (3 input xor)
function(3, [1,2,4,7], [0,3,5,6], [], [], [], [], []),
function(2, [4,5,6,7], [0,1,2,3], [], [], [], [], []),
function(1, [2,3,6,7], [0,1,4,5], [], [], [], [], []),
function(0, [1,3,5,7], [0,2,4,6], [], [], [], [], [])
]) :-
update_bounds(_, 100, _).
init_state(4, 3, 5, [ % do sum and carry together
function(4, [3,5,6,7], [0,1,2,4], [], [], [], [], []),
function(3, [1,2,4,7], [0,3,5,6], [], [], [], [], []),
function(2, [4,5,6,7], [0,1,2,3], [], [], [], [], []),
function(1, [2,3,6,7], [0,1,4,5], [], [], [], [], []),
function(0, [1,3,5,7], [0,2,4,6], [], [], [], [], [])
]) :-
update_bounds(_, 100, _).
/* commented for XSB, compiler complexity too high on big lists
init_state(5, 5, 8, [ % 2 bit full adder
function(7, % A2 (output)
[1,3,4,6,9,11,12,14,16,18,21,23,24,26,29,31],
[0,2,5,7,8,10,13,15,17,19,20,22,25,27,28,30],
[], [], [], [], []),
function(6, % B2 (output)
[2,3,5,6,8,9,12,15,17,18,20,21,24,27,30,31],
[0,1,4,7,10,11,13,14,16,19,22,23,25,26,28,29],
[], [], [], [], []),
function(5, % carry-out (output)
[7,10,11,13,14,15,19,22,23,25,26,27,28,29,30,31],
[0,1,2,3,4,5,6,8,9,12,16,17,18,20,21,24],
[], [], [], [], []),
function(4, % carry-in
[16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31],
[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15],
[], [], [], [], []),
function(3, % B1 input
[8,9,10,11,12,13,14,15,24,25,26,27,28,29,30,31],
[0,1,2,3,4,5,6,7,16,17,18,19,20,21,22,23],
[], [], [], [], []),
function(2, % B0 input
[4,5,6,7,12,13,14,15,20,21,22,23,28,29,30,31],
[0,1,2,3,8,9,10,11,16,17,18,19,24,25,26,27],
[], [], [], [], []),
function(1, % A1 input
[2,3,6,7,10,11,14,15,18,19,22,23,26,27,30,31],
[0,1,4,5,8,9,12,13,16,17,20,21,24,25,28,29],
[], [], [], [], []),
function(0, % A0 input
[1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31],
[0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30],
[], [], [], [], [])
]) :-
update_bounds(_, 21, _).
*/
% Iterate over all the TRUE vectors that need to be covered.
% If no vectors remain to be covered (select_vector fails), then
% the circuit is complete (printout results, update bounds, and
% continue search for a lower cost circuit).
search(NumVars, NumGsIn, GsIn, ShowResult) :-
select_vector(NumVars, NumGsIn, GsIn, Gj, Vector), !,
cover_vector(NumVars, NumGsIn, GsIn, Gj, Vector, NumGs, Gs),
add_necessary_functions(NumVars, NumGs, Gs, NumGsOut, GsOut),
test_bounds(NumVars, NumGsOut, GsOut),
search(NumVars, NumGsOut, GsOut, ShowResult).
search(NumVars, NumGs, Gs, ShowResult) :-
( ShowResult = true ->
output_results(NumVars, NumGs, Gs)
; true),
update_bounds(NumVars, NumGs, Gs),
fail.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Given the current solution, pick the best uncovered TRUE vector
% for covering next.
% The selected vector is specified by its vector number and function.
% Select_vector fails if all TRUE vectors are covered.
% Select_vector is determinant (gives only one solution).
select_vector(NumVars, NumGs, Gs, Gj, Vector) :-
select_vector(Gs, NumVars, NumGs, Gs,
dummy, 0, nf, 999, Gj, Vector, Type, _), !,
\+ unif(Type, cov),
\+ unif(Type, nf).
unif(X, X).
% loop over functions
select_vector([Gk|_], NumVars, _, _, Gj, V, Type, N, Gj, V, Type, N) :-
function_number(Gk, K),
K < NumVars.
select_vector([Gk|Gks], NumVars, NumGs, Gs,
GjIn, Vin, TypeIn, Nin, GjOut, Vout, TypeOut, Nout) :-
function_number(Gk, K),
K >= NumVars,
true_set(Gk, Tk),
select_vector(Tk, Gk, NumVars, NumGs, Gs,
GjIn, Vin, TypeIn, Nin, Gj, V, Type, N),
select_vector(Gks, NumVars, NumGs, Gs,
Gj, V, Type, N, GjOut, Vout, TypeOut, Nout).
% loop over vectors
select_vector([], _, _, _, _, Gj, V, Type, N, Gj, V, Type, N).
select_vector([V|Vs], Gk, NumVars, NumGs, Gs,
GjIn, Vin, TypeIn, Nin, GjOut, Vout, TypeOut, Nout) :-
vector_cover_type(NumVars, Gs, Gk, V, Type, N),
best_vector(GjIn, Vin, TypeIn, Nin,
Gk, V, Type, N,
Gj2, V2, Type2, N2),
select_vector(Vs, Gk, NumVars, NumGs, Gs,
Gj2, V2, Type2, N2, GjOut, Vout, TypeOut, Nout).
vector_cover_type(NumVars, Gs, Gj, Vector, Type, NumCovers) :-
immediate_predecessors(Gj, IPs),
conceivable_inputs(Gj, CIs),
false_set(Gj, Fj),
cover_type1(IPs, Gs, Vector, nf, 0, T, N),
cover_type2(CIs, Gs, NumVars, Fj, Vector, T, N, Type, NumCovers).
cover_type1([], _, _, T, N, T, N).
cover_type1([I|IPs], Gs, V, TypeIn, Nin, TypeOut, Nout) :-
function(I, Gs, Gi),
true_set(Gi, Ti),
\+ set_member(V, Ti), !,
false_set(Gi, Fi),
(set_member(V, Fi) ->
max_type(TypeIn, cov, Type);
max_type(TypeIn, exp, Type)),
N is Nin + 1,
cover_type1(IPs, Gs, V, Type, N, TypeOut, Nout).
cover_type1([_|IPs], Gs, V, TypeIn, Nin, TypeOut, Nout) :-
cover_type1(IPs, Gs, V, TypeIn, Nin, TypeOut, Nout).
cover_type2([], _, _, _, _, T, N, T, N).
cover_type2([I|CIs], Gs, NumVars, Fj, V, TypeIn, Nin, TypeOut, Nout) :-
I < NumVars,
function(I, Gs, Gi),
false_set(Gi, Fi),
set_member(V, Fi), !,
max_type(TypeIn, var, Type),
N is Nin + 1,
cover_type2(CIs, Gs, NumVars, Fj, V, Type, N, TypeOut, Nout).
cover_type2([I|CIs], Gs, NumVars, Fj, V, TypeIn, Nin, TypeOut, Nout) :-
I >= NumVars,
function(I, Gs, Gi),
true_set(Gi, Ti),
\+ set_member(V, Ti), !,
false_set(Gi, Fi),
(set_member(V, Fi) ->
(set_subset(Fj, Ti) ->
max_type(TypeIn, fcn, Type);
max_type(TypeIn, mcf, Type));
(set_subset(Fj, Ti) ->
max_type(TypeIn, exf, Type);
max_type(TypeIn, exmcf, Type))),
N is Nin + 1,
cover_type2(CIs, Gs, NumVars, Fj, V, Type, N, TypeOut, Nout).
cover_type2([_|CIs], Gs, NumVars, Fj, V, TypeIn, Nin, TypeOut, Nout) :-
cover_type2(CIs, Gs, NumVars, Fj, V, TypeIn, Nin, TypeOut, Nout).
% The best vector to cover is the one with worst type, or, if types
% are equal, with the least number of possible covers.
best_vector(dummy, _, _, _, Gj2, V2, Type2, N2, Gj2, V2, Type2, N2) :- !.
best_vector(Gj1, V1, Type1, N1, dummy, _, _, _, Gj1, V1, Type1, N1) :- !.
best_vector(Gj1, V1, Type, N1, Gj2, _, Type, N2, Gj1, V1, Type, N1) :-
function_number(Gj1, J), function_number(Gj2, J),
N1 < N2, !.
best_vector(Gj1, _, Type, N1, Gj2, V2, Type, N2, Gj2, V2, Type, N2) :-
function_number(Gj1, J), function_number(Gj2, J),
N1 >= N2, !.
best_vector(Gj1, V1, Type, N1, Gj2, _, Type, _, Gj1, V1, Type, N1) :-
(Type = exp ; Type = var),
function_number(Gj1, J1), function_number(Gj2, J2),
J1 > J2, !.
best_vector(Gj1, _, Type, _, Gj2, V2, Type, N2, Gj2, V2, Type, N2) :-
(Type = exp ; Type = var),
function_number(Gj1, J1), function_number(Gj2, J2),
J1 < J2, !.
best_vector(Gj1, V1, Type, N1, Gj2, _, Type, _, Gj1, V1, Type, N1) :-
\+ unif2(Type, exp, var),
function_number(Gj1, J1), function_number(Gj2, J2),
J1 < J2, !.
best_vector(Gj1, _, Type, _, Gj2, V2, Type, N2, Gj2, V2, Type, N2) :-
\+ unif2(Type, exp, var),
function_number(Gj1, J1), function_number(Gj2, J2),
J1 > J2, !.
best_vector(Gj1, V1, Type1, N1, _, _, Type2, _, Gj1, V1, Type1, N1) :-
type_order(Type2, Type1), !.
best_vector(_, _, Type1, _, Gj2, V2, Type2, N2, Gj2, V2, Type2, N2) :-
type_order(Type1, Type2), !.
unif2(X, X, _).
unif2(X, _, X).
max_type(T1, T2, T1) :- type_order(T1, T2), !.
max_type(T1, T2, T2) :- \+ type_order(T1, T2), !.
% Order of types
type_order(cov, exp).
type_order(cov, var).
type_order(cov, fcn).
type_order(cov, mcf).
type_order(cov, exf).
type_order(cov, exmcf).
type_order(cov, nf).
type_order(exp, var).
type_order(exp, fcn).
type_order(exp, mcf).
type_order(exp, exf).
type_order(exp, exmcf).
type_order(exp, nf).
type_order(var, fcn).
type_order(var, mcf).
type_order(var, exf).
type_order(var, exmcf).
type_order(var, nf).
type_order(fcn, mcf).
type_order(fcn, exf).
type_order(fcn, exmcf).
type_order(fcn, nf).
type_order(mcf, exf).
type_order(mcf, exmcf).
type_order(mcf, nf).
type_order(exf, exmcf).
type_order(exf, nf).
type_order(exmcf, nf).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Cover_vector will cover the specified vector and
% generate new circuit information.
% Using backtracking, all possible coverings are generated.
% The ordering of the possible coverings is approximately that
% given in Davidson's paper, but has been simplified.
cover_vector(NumVars, NumGsIn, GsIn, Gj, Vector, NumGsOut, GsOut) :-
immediate_predecessors(Gj, IPs),
conceivable_inputs(Gj, CIs),
vector_types(Type),
cover_vector(Type, IPs, CIs, Gj, Vector, NumVars, NumGsIn, GsIn,
NumGsOut, GsOut).
vector_types(var).
vector_types(exp).
vector_types(fcn).
vector_types(mcf).
vector_types(exf).
vector_types(exmcf).
vector_types(nf).
cover_vector(exp, [I|_], _, Gj, V, _, NumGs, GsIn, NumGs, GsOut) :-
function(I, GsIn, Gi),
true_set(Gi, Ti),
\+ set_member(V, Ti),
update_circuit(GsIn, Gi, Gj, V, GsIn, GsOut).
cover_vector(exp, [_|IPs], _, Gj, V, NumVars, NumGs, GsIn, NumGs, GsOut) :-
cover_vector(exp, IPs, _, Gj, V, NumVars, NumGs, GsIn, NumGs, GsOut).
cover_vector(var, _, [I|_], Gj, V, NumVars, NumGs, GsIn, NumGs, GsOut) :-
I < NumVars,
function(I, GsIn, Gi),
false_set(Gi, Fi),
set_member(V, Fi),
update_circuit(GsIn, Gi, Gj, V, GsIn, GsOut).
cover_vector(var, _, [_|CIs], Gj, V, NumVars, NumGs, GsIn, NumGs, GsOut) :-
cover_vector(var, _, CIs, Gj, V, NumVars, NumGs, GsIn, NumGs, GsOut).
cover_vector(fcn, _, [I|_], Gj, V, NumVars, NumGs, GsIn, NumGs, GsOut) :-
I >= NumVars,
function(I, GsIn, Gi),
false_set(Gi, Fi),
set_member(V, Fi),
true_set(Gi, Ti),
false_set(Gj, Fj),
set_subset(Fj, Ti),
update_circuit(GsIn, Gi, Gj, V, GsIn, GsOut).
cover_vector(fcn, _, [_|CIs], Gj, V, NumVars, NumGs, GsIn, NumGs, GsOut) :-
cover_vector(fcn, _, CIs, Gj, V, NumVars, NumGs, GsIn, NumGs, GsOut).
cover_vector(mcf, _, [I|_], Gj, V, NumVars, NumGs, GsIn, NumGs, GsOut) :-
I >= NumVars,
function(I, GsIn, Gi),
false_set(Gi, Fi),
set_member(V, Fi),
true_set(Gi, Ti),
false_set(Gj, Fj),
\+ set_subset(Fj, Ti),
update_circuit(GsIn, Gi, Gj, V, GsIn, GsOut).
cover_vector(mcf, _, [_|CIs], Gj, V, NumVars, NumGs, GsIn, NumGs, GsOut) :-
cover_vector(mcf, _, CIs, Gj, V, NumVars, NumGs, GsIn, NumGs, GsOut).
cover_vector(exf, _, [I|_], Gj, V, NumVars, NumGs, GsIn, NumGs, GsOut) :-
I >= NumVars,
function(I, GsIn, Gi),
false_set(Gi, Fi),
\+ set_member(V, Fi),
true_set(Gi, Ti),
\+ set_member(V, Ti),
false_set(Gj, Fj),
set_subset(Fj, Ti),
update_circuit(GsIn, Gi, Gj, V, GsIn, GsOut).
cover_vector(exf, _, [_|CIs], Gj, V, NumVars, NumGs, GsIn, NumGs, GsOut) :-
cover_vector(exf, _, CIs, Gj, V, NumVars, NumGs, GsIn, NumGs, GsOut).
cover_vector(exmcf, _, [I|_], Gj, V, NumVars, NumGs, GsIn, NumGs, GsOut) :-
I >= NumVars,
function(I, GsIn, Gi),
false_set(Gi, Fi),
\+ set_member(V, Fi),
true_set(Gi, Ti),
\+ set_member(V, Ti),
false_set(Gj, Fj),
\+ set_subset(Fj, Ti),
update_circuit(GsIn, Gi, Gj, V, GsIn, GsOut).
cover_vector(exmcf, _, [_|CIs], Gj, V, NumVars, NumGs, GsIn, NumGs, GsOut) :-
cover_vector(exmcf, _, CIs, Gj, V, NumVars, NumGs, GsIn, NumGs, GsOut).
cover_vector(nf, _, _, Gj, V, NumVars, NumGsIn, GsIn, NumGsOut, GsOut) :-
NumGsOut is NumGsIn + 1,
false_set(Gj, Fj),
new_function_CIs(GsIn,
function(NumGsIn,Fj,[V],[],[],[],[],[]),
NumVars, Gs, Gi),
update_circuit(Gs, Gi, Gj, V, Gs, GsOut).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
update_circuit([], _, _, _, _, []).
update_circuit([function(K,Tk,Fk,CIk,IPk,ISk,Pk,Sk)|GsIn],
Gi, Gj, V, Gs,
[function(K,Tko,Fko,CIko,IPko,ISko,Pko,Sko)|GsOut]) :-
Gi = function(I,_,Fi,_,IPi,ISi,Pi,_),
Gj = function(J,_,Fj,_,_,_,_,Sj),
set_union([I], Pi, PiI),
set_union([J], Sj, SjJ),
(K = J ->
set_union(Tk, Fi, Tk2);
Tk2 = Tk),
(K = I ->
set_union(Tk2, Fj, Tk3);
Tk3 = Tk2),
((set_member(K, IPi); set_member(K, ISi)) ->
set_union(Tk3, [V], Tko);
Tko = Tk3),
(K = I ->
set_union(Fk, [V], Fko);
Fko = Fk),
((set_member(K, Pi); K = I) ->
set_difference(CIk, SjJ, CIk2);
CIk2 = CIk),
((set_member(I, CIk), set_member(V, Fk)) ->
set_difference(CIk2, [I], CIk3);
CIk3 = CIk2),
(K = I ->
exclude_if_vector_in_false_set(CIk3, Gs, V, CIk4);
CIk4 = CIk3),
(K = J ->
set_difference(CIk4, [I], CIko);
CIko = CIk4),
(K = J ->
set_union(IPk, [I], IPko);
IPko = IPk),
(K = I ->
set_union(ISk, [J], ISko);
ISko = ISk),
(set_member(K, SjJ) ->
set_union(Pk, PiI, Pko);
Pko = Pk),
(set_member(K, PiI) ->
set_union(Sk, SjJ, Sko);
Sko = Sk),
update_circuit(GsIn, Gi, Gj, V, Gs, GsOut).
exclude_if_vector_in_false_set([], _, _, []).
exclude_if_vector_in_false_set([K|CIsIn], Gs, V, CIsOut) :-
function(K, Gs, Gk),
false_set(Gk, Fk),
set_member(V, Fk), !,
exclude_if_vector_in_false_set(CIsIn, Gs, V, CIsOut).
exclude_if_vector_in_false_set([K|CIsIn], Gs, V, [K|CIsOut]) :-
exclude_if_vector_in_false_set(CIsIn, Gs, V, CIsOut).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
add_necessary_functions(NumVars, NumGsIn, GsIn, NumGsOut, GsOut) :-
add_necessary_functions(NumVars, NumVars, NumGsIn, GsIn,
NumGsOut, GsOut).
add_necessary_functions(NumGs, _, NumGs, Gs, NumGs, Gs) :- !.
add_necessary_functions(K, NumVars, NumGsIn, GsIn, NumGsOut, GsOut) :-
function(K, GsIn, Gk),
function_type(NumVars, NumGsIn, GsIn, Gk, nf, V), !,
false_set(Gk, Fk),
new_function_CIs(GsIn,
function(NumGsIn,Fk,[V],[],[],[],[],[]),
NumVars, Gs, Gl),
function(K, Gs, Gk1),
update_circuit(Gs, Gl, Gk1, V, Gs, Gs1),
NumGs1 is NumGsIn + 1,
K1 is K + 1,
add_necessary_functions(K1, NumVars, NumGs1, Gs1, NumGsOut, GsOut).
add_necessary_functions(K, NumVars, NumGsIn, GsIn, NumGsOut, GsOut) :-
K1 is K + 1,
add_necessary_functions(K1, NumVars, NumGsIn, GsIn, NumGsOut, GsOut).
new_function_CIs(GsIn, function(L,Tl,Fl,_,IPl,ISl,Pl,Sl), NumVars,
[GlOut|GsOut], GlOut) :-
new_function_CIs(GsIn, L, Fl, NumVars, GsOut, [], CIlo),
GlOut = function(L,Tl,Fl,CIlo,IPl,ISl,Pl,Sl).
new_function_CIs([], _, _, _, [], CIl, CIl).
new_function_CIs([function(K,Tk,Fk,CIk,IPk,ISk,Pk,Sk)|GsIn], L, Fl, NumVars,
[function(K,Tk,Fk,CIko,IPk,ISk,Pk,Sk)|GsOut], CIlIn, CIlOut) :-
set_intersection(Fl, Fk, []), !,
(K >= NumVars ->
set_union(CIk, [L], CIko);
CIko = CIk),
new_function_CIs(GsIn, L, Fl, NumVars, GsOut, [K|CIlIn], CIlOut).
new_function_CIs([Gk|GsIn], L, Fl, NumVars, [Gk|GsOut], CIlIn, CIlOut) :-
new_function_CIs(GsIn, L, Fl, NumVars, GsOut, CIlIn, CIlOut).
function_type(NumVars, NumGs, Gs, Gk, Type, Vector) :-
true_set(Gk, Tk),
select_vector(Tk, Gk, NumVars, NumGs, Gs,
dummy, 0, nf, 999, _, Vector, Type, _).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Cost and constraint predicates:
% very simple bound for now
test_bounds(_, NumGs, _) :-
access(bound, Bound),
NumGs < Bound.
update_bounds(_, NumGs, _) :-
set(bound, NumGs).
% set and access for systems that don't support them
/* Original source
set(N, A) :-
(recorded(N, _, Ref) -> erase(Ref) ; true),
recorda(N, A, _).
access(N, A) :-
recorded(N, A, _).
*/
/* bet for GNU Prolog
set(N, A) :-
g_assign(N, A).
access(N, A) :-
g_read(N, A).
*/
/* ISO version */
set(N, A) :-
( access(N, _) ->
retract(store_value(N, _))
; true),
asserta(store_value(N, A)).
access(N, A) :-
clause(store_value(N, A), _).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Output predicates:
% for now just dump everything
output_results(NumVars, NumGs, Gs) :-
NumGates is NumGs - NumVars,
write(NumGates), write(' gates'), nl,
write_gates(Gs), nl,
write('searching for a better solution...'), nl, nl.
write_gates([]).
write_gates([Gi|Gs]) :-
function_number(Gi, I),
write('gate #'), write(I), write(' inputs: '),
immediate_predecessors(Gi, IPi),
write(IPi), nl,
write_gates(Gs).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Retrieve the specified function from the function list.
% function(FunctionNumber, FunctionList, Function).
function(I, [Gi|_], Gi) :- function_number(Gi, I), !.
function(I, [_|Gs], Gi) :- function(I, Gs, Gi).
function_number( function(I,_,_,_,_,_,_,_), I).
true_set( function(_,T,_,_,_,_,_,_), T).
false_set( function(_,_,F,_,_,_,_,_), F).
conceivable_inputs( function(_,_,_,CI,_,_,_,_), CI).
immediate_predecessors( function(_,_,_,_,IP,_,_,_), IP).
immediate_successors( function(_,_,_,_,_,IS,_,_), IS).
predecessors( function(_,_,_,_,_,_,P,_), P).
successors( function(_,_,_,_,_,_,_,S), S).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Set operations assume that the sets are represented by an ordered list
% of integers.
set_union([], [], []).
set_union([], [X|L2], [X|L2]).
set_union([X|L1], [], [X|L1]).
set_union([X|L1], [X|L2], [X|L3]) :- set_union(L1, L2, L3).
set_union([X|L1], [Y|L2], [X|L3]) :- X < Y, set_union(L1, [Y|L2], L3).
set_union([X|L1], [Y|L2], [Y|L3]) :- X > Y, set_union([X|L1], L2, L3).
set_intersection([], [], []).
set_intersection([], [_|_], []).
set_intersection([_|_], [], []).
set_intersection([X|L1], [X|L2], [X|L3]) :- set_intersection(L1, L2, L3).
set_intersection([X|L1], [Y|L2], L3) :- X < Y, set_intersection(L1, [Y|L2], L3).
set_intersection([X|L1], [Y|L2], L3) :- X > Y, set_intersection([X|L1], L2, L3).
set_difference([], [], []).
set_difference([], [_|_], []).
set_difference([X|L1], [], [X|L1]).
set_difference([X|L1], [X|L2], L3) :- set_difference(L1, L2, L3).
set_difference([X|L1], [Y|L2], [X|L3]) :- X < Y, set_difference(L1, [Y|L2], L3).
set_difference([X|L1], [Y|L2], L3) :- X > Y, set_difference([X|L1], L2, L3).
set_subset([], _).
set_subset([X|L1], [X|L2]) :- set_subset(L1, L2).
set_subset([X|L1], [Y|L2]) :- X > Y, set_subset([X|L1], L2).
set_member(X, [X|_]).
set_member(X, [Y|T]) :- X > Y, set_member(X, T).
% benchmark interface
benchmark(ShowResult) :-
nand(ShowResult).
:- include(common).
