Here we collect a number of small programs that serve to illustrate some interesting programming techniques.
A Crypto-arithmetic Puzzle
Consider one of the standard crypto-arithmetic puzzles. We require an injective assignment of digits to the letters S, E, N, D, M, O, R, Y such that the equation
S E N D + M O R E --------- M O N E Y
holds. The program first imposes certain constraints on the values. Then it tries to assign possible values to the letters. The problem is combinatorially explosive and so a naive generate and test solution would be very inefficient. In contrast, the straightforward program below runs quickly in CLP( ).
The program illustrates how CLP( ) can be used to advantage in solving problems over integer domains. Because the unsolvability of constraints in implies their unsolvability over the integers, CLP( ) can prune the search space significantly without the expense of invoking an integer solver. For CLP programs in general, the key issue is the trade-off between the power and the speed of the constraint-solver: powerful solvers entail smaller search spaces but are costlier to run. For CLP( ) in particular, the use of a real-number-based solver to approximate constraint-solving over a discrete or finite domain is one important realization of this trade-off.
solve([S, E, N, D, M, O, R, Y]) :- constraints([S, E, N, D, M, O, R, Y]), gen_diff_digits([S, E, N, D, M, O, R, Y]). constraints([S, E, N, D, M, O, R, Y]) :- S >= 0, E >= 0, N >= 0, D >= 0, M >= 0, O >= 0, R >= 0, Y >= 0, S <= 9, E <= 9, N <= 9, D <= 9, M <= 9, O <= 9, R <= 9, Y <= 9, S >= 1, M >= 1, C1 >= 0, C2 >= 0, C3 >= 0, C4 >= 0, C1 <= 1, C2 <= 1, C3 <= 1, C4 <= 1, M = C1, C2 + S + M = O + C1 * 10, C3 + E + O = N + 10 * C2, C4 + N + R = E + 10 * C3, D + E = Y + 10*C4, bit(C1), bit(C2), bit(C3), bit(C4). bit(0). bit(1). gen_diff_digits(L) :- gen_diff_digits(L, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]). gen_diff_digits([], _). gen_diff_digits([H | T], L) :- select(H, L, L2), gen_diff_digits(T, L2). select(H, [H | T], T). select(H, [H2 | T], [H2 | T2]) :- select(H, T, T2). ?- solve(S, E, N, D, M, O, R, Y).
Critical Path Analysis
This program uses local propagation to compute start, completion and float times for a project network. Significantly, the constraint paradigm allows the program to compute these values by making only one pass of the project network, as opposed to the three passes that would be needed using a conventional programming language.
Most of the program is basically parsing the input and building an adjacency graph out of the network. Then the latest completion time and earliest starting time for every node is simply the minimum of the time required for the outgoing events and maximum of the time of the incoming events.
cpm(Network, Graph, Latest) :- build(Network, Graph), early_late(Graph, Graph, End, Latest), Latest >= End, analyse(Graph, Graph). cpm(Network, Graph) :- build(Network, Graph), early_late(Graph, Graph, End), analyse(Graph, Graph). % Build adjacency graph out of the network ... build([], Graph) :- ... % Get early start times and latest completion times % early/4 is used when a ending time is given % otherwise early/3 assumes that the early start time % for the end node is equal to the latest completion time early_late([], _, _, _). early_late([ad(I, Es, Lc, To, From) | T], G, End, Latest) :- setearly(From, To, G, End, Es), setlate(To, G, Latest, Lc), early_late(T, G, End, Latest). early_late([], _, _). early_late([ad(I, Es, Lc, To, From) | T], G, End) :- setearly(From, To, G, End, Es), setlate(To, G, End, Lc), early_late(T, G, End). setearly([], _, _, _, 0). setearly([ed(V, C, _, _, _, _) | T],[], G, Es, Es) :- !, getnode(V, G, Es1, _), setmax(T, G, Es1 + C, Es). setearly([ed(V, C, _, _, _, _) | T], _, G, End, Es) :- getnode(V, G, Es1, _), setmax(T, G, Es1+C, Es). setmax([], _, Max, Max). setmax([ed(V, C, _, _, _, _) | T], G, Max0, Max) :- getnode(V, G, Es1, _), setmax(T, G, max(Max0, Es1 + C), Max). setlate([], _, Last, Last). setlate([ed(V, C, _, _, _, _) | T], G, Last, Lc) :- getnode(V, G, _, Lc1), setmin(T, G, Lc1-C, Lc). setmin([], _, Min, Min). setmin([ed(V, C, _, _, _, _) | T], G, Min0, Min) :- getnode(V, G, _, Lc1), setmin(T, G, min(Min0, Lc1 - C), Min). % Search graph for the early & late times for a node getnode(I,[ad(I, Es, Lc, _, _) | T], Es, Lc). getnode(I,[H | T], Es, Lc) :- getnode(I, T, Es, Lc). % Compute the other times: % Ls - latest start time % Ec - earliest completion time % Tf - total float time % Ff - free float time analyse([], G). analyse([ad(I, Es, Lc, To, _) | T], G) :- analyse_times(To, Es, Lc, G), analyse(T, G). analyse_times([], _, _, _). analyse_times([ed(V, C, Ls, Ec, Tf, Ff) | T], Esi, Lci, G) :- getnode(V, G, Esj, Lcj), X = Esi + C, Ls = Lcj - C, Ec = Esi + C, Tf = Lcj - X, Ff = Esj - X, analyse_times(T, Esi, Lci, G). print_analysis(G) :- ...
A goal might be
?- cpm([ [n1, n2, 4], [n1, n3, 3], [n1, n4, 4], [n2, n5, 7], [n2, n3, 1], [n2, n7, 8], [n3, n5, 4], [n4, n6, 2], [n5, n6, 1], [n5, n7, 3], [n6, n7, 4]], G), print_analysis(G).
A Simple Circuit Solver
The following program performs DC analysis on circuits containing resistors, voltage sources and diodes. The circuit analysis is decomposed in a hierarchical fashion. The individual components are modelled directly by constraints such as Ohm's law. Then the components are connected together and the global circuit constraints on the currents and voltages, as specified by Kirchoff's laws, are used to define the whole circuit.
solve_dc(C, L) :- solve(C, [], L), solve_current(L). % solve for every circuit component solve([], L, L). solve([[Comp, Name, Par, Nodes] | T], In, Out) :- connect(Name, Nodes, Volts, Amps, In, Tmp), component(Comp, Par, Volts, Amps), solve(T, Tmp, Out). % sum of currents at each node are zero solve_current([]). solve_current([n(N, V, IList) | T]) :- kcl(IList, 0), solve_current(T). kcl([], 0). kcl([(Name, I) | T], X) :- kcl(T, I + X). % connect the arcs which meet at a node connect(Name, [], [], [], L, L). connect(Name, [N | T], [V | VR], [I | IR], In, Out) :- add_arc(Name, N, V, I, In, Tmp), connecting(Name, T, VR, IR, Tmp, Out). % create the voltage and currents add_arc(Name, N, V, I, [], [n(N, V, [(Name, I)])]). add_arc(Name, N, V, I, [n(N, V, IList) | T], [n(N, V, [(Name, I) | IList]) | T]). add_arc(Name, N, V, I, [X | T], [X | T1]) :- add_arc(Name, N, V, I, T, T1). component(resistor, R, [V1, V2], [I, -I]) :- V1 - V2 = I*R. component(voltage_source, V, [V, 0], [I, -I]). component(diode, in914, [V1, V2], [I, -I]) :- diode(in914, [V1, V2], [I, -I]). diode(in914, [V1, V2], [I1, I2]) :- V = V1 - V2, V < -100, DV = V+100, I1 = 10*DV - 0.1. diode(in914, [V1, V2], [I1, I2]) :- V = V1 - V2, V >= -100, V < 0.6, I1 = 0.001*V. diode(in914, [V1, V2], [I1, I2]) :- V = V1 - V2, V >= 0.6, DV = V - 0.6, I1 = 100*DV - 0.0006.
A sample query which returns the currents and voltages in L
?- R1 = 100, R2 = 50, V = 20, solve_dc([[voltage_source, v1, V, [n1, ground]], [resistor, r1, R1, [n1, n2]], [resistor, r2, R2, [n2, ground]], [diode, d1, in914, [n2, ground]]], L).