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).