Constraint Logic Programming

CLP(D) is a language framework, where D is the domain of the constraints.

Example CLP languages:

In contrast to Prolog, the function symbols for constraints over the domain D are interpreted.

CLP(R) can solve arbitrary collections of linear equality and inequality constraints. It can also solve other kinds of constraints over the reals if it can find the answer using one-step deductions (first find this variable using one constraint, then find another variable using another constraint, etc -- but no simultaneous equations).

Examples

Sample rule: 
cf(C,F) :-
  F = 1.8*C + 32.
Sample Goals: 
?- 2*A+B=7, 3*A+B=9.
  A=2, B=3

?- cf(100,A).
  A=212.0

?- cf(X,X).
  X=-40.0

?- X*X*X + X = 10.
  maybe
("maybe" answer when the constraints are too hard for CLP(R))
For example programs see ~borning/clpr/myprogs/* and ~borning/clpr/progs/* on orcas.

Ordinary prolog examples (no use of constraints on the reals):

Examples illustrating use of constraints:

Some Small CLP(R) Examples


/* LENGTH OF LIST */

length([],0).
length([H|T],N) :- 
  N > 0,
  length(T,N-1).


/* SUM OF THE ELEMENTS IN A LIST */

sum([],0).
sum([X|Xs],X+S) :- sum(Xs,S).


/* FACTORIAL */
factorial(0, 1).
factorial(N, N * F) :-
        N > 0 ,
        fact(N - 1, F).


/* GREATEST COMMON DIVISOR (USING EUCLID'S ALGORITHM) */

gcd(A,B,G) :- 
   A < B,
   gcd(A,B-A,G).

gcd(A,B,G) :- 
   A > B,
   gcd(A-B,B,G).

gcd(A,A,A).



/* QUICKSORT */

quicksort([],[]).
quicksort([X|Xs],Sorted) :-
  partition(X,Xs,Smalls,Bigs),
  quicksort(Smalls,SortedSmalls),
  quicksort(Bigs,SortedBigs),
  append(SortedSmalls,[X|SortedBigs],Sorted).

partition(Pivot,[],[],[]).
partition(Pivot,[X|Xs],[X|Ys],Zs) :-
   X <= Pivot,
   partition(Pivot,Xs,Ys,Zs).
partition(Pivot,[X|Xs],Ys,[X|Zs]) :-
   X > Pivot,
   partition(Pivot,Xs,Ys,Zs).


append([],X,X).
append([X|Xs],Ys,[X|Zs]) :- append(Xs,Ys,Zs).

Electrical Circuits Example

Here is a longer example that includes rules to represent resistors, batteries, meters, and wires. 
/* RULES FOR SIMPLE ELECTRICAL CIRCUITS */

/* the term lead(I,V) represents a lead of an electrical component, with 
   a current I flowing out of the lead and a voltage of V at the connecting
   node
*/


/* The goal resistor(L1,L2,Ohms) creates an Ohm's Law constraint.  Also
   (as with any two-leaded object) the current flowing into one lead must
   equal the current flowing out of the other */
resistor(lead(I1,V1),lead(I2,V2),Ohms) :-
   I1+I2=0,
   V2-V1=I1*Ohms.

/* The goal battery(L1,L2,Volts) creates a battery with internal voltage
   Volts */
battery(lead(I1,V1),lead(I2,V2),Volts) :-
   V1 = V2+Volts,
   I1+I2=0.

/* an electrical ground has a voltage of 0 (and no current flowing ... we
   are assuming only one ground per circuit)  */
electrical_ground(lead(0,0)).

/* a perfect ammeter - has zero resistance */
ammeter(lead(I1,V),lead(I2,V),I1) :-
   I1+I2=0.

/* a perfect voltmeter - doesn't draw any current */
voltmeter(lead(0,V1),lead(0,V2),Volts) :-
   V1-V2=Volts.

/* rule to connect a list of leads together (makes all the voltages the
   same, and the sum of the currents be 0 */
connect(Leads) :-
  same_voltages(Leads),
  currents_sum(Leads,0).

same_voltages([]).
same_voltages([L]).
same_voltages([lead(I1,V),lead(I2,V)|More]) :- 
   same_voltages([lead(I2,V)|More]).

currents_sum([],0).
currents_sum([lead(I1,V1)|More],I1+Sum) :-
   currents_sum(More,Sum).


/* RULES TO BUILD THE SAMPLE CIRCUITS */

/* simple battery-resistor circuit */
one_resistor(Volts,Ohms,Amps) :-
   battery(B1,B2,Volts),
   resistor(R1,R2,Ohms),
   ammeter(A1,A2,Amps),
   electrical_ground(G),
   connect([B2,A1]), connect([A2,R1]), connect([R2,B1,G]).

/* same circuit, but no ground */
one_noground(Volts,Ohms,Amps) :-
   battery(B1,B2,Volts),
   resistor(R1,R2,Ohms),
   ammeter(A1,A2,Amps),
   connect([B2,A1]), connect([A2,R1]), connect([R2,B1]).

/* voltage divider */
divider(Volts,Ohms1,Ohms2,Amps,VCenter) :-
   battery(B1,B2,Volts),
   resistor(R1,R2,Ohms1),
   resistor(S1,S2,Ohms2),
   ammeter(A1,A2,Amps),
   voltmeter(V1,V2,VCenter),
   electrical_ground(G),
   connect([B2,A1]), connect([A2,R1]), connect([R2,S1,V1]),
   connect([S2,V2,B1,G]).


divider_noground(Volts,Ohms1,Ohms2,Amps,VCenter) :-
   battery(B1,B2,Volts),
   resistor(R1,R2,Ohms1),
   resistor(S1,S2,Ohms2),
   ammeter(A1,A2,Amps),
   voltmeter(V1,V2,VCenter),
   connect([B2,A1]), connect([A2,R1]), connect([R2,S1,V1]),
   connect([S2,V2,B1]).

/* Wheatstone bridge */
wheat(Volts,WOhms,XOhms,YOhms,ZOhms,Amps) :-
   battery(B1,B2,Volts),
   resistor(W1,W2,WOhms),
   resistor(X1,X2,XOhms),
   resistor(Y1,Y2,YOhms),
   resistor(Z1,Z2,ZOhms),
   ammeter(A1,A2,Amps),
   electrical_ground(G),
   connect([B2,W1,X1]), connect([B1,Y2,Z2,G]), 
   connect([W2,Y1,A1]), connect([X2,Z1,A2]).

wheat_noground(Volts,WOhms,XOhms,YOhms,ZOhms,Amps) :-
   battery(B1,B2,Volts),
   resistor(W1,W2,WOhms),
   resistor(X1,X2,XOhms),
   resistor(Y1,Y2,YOhms),
   resistor(Z1,Z2,ZOhms),
   ammeter(A1,A2,Amps),
   connect([B2,W1,X1]), connect([B1,Y2,Z2]), 
   connect([W2,Y1,A1]), connect([X2,Z1,A2]).

ladder(T1,T2,Ohms,1) :-
   /* one rung */
   resistor(T1,A,Ohms),
   resistor(T2,B,Ohms),
   resistor(R1,R2,Ohms),
   connect([A,R1]), connect([B,R2]).

ladder(T1,T2,Ohms,N) :-
   N > 1,
   ladder(X1,X2,Ohms,N-1),
   resistor(T1,A,Ohms),
   resistor(T2,B,Ohms),
   resistor(R1,R2,Ohms),
   connect([A,R1,X1]), connect([B,R2,X2]).


/* SAMPLE GOALS */

go1 :- one_resistor(100,50,A), dump([A]).
go2 :- one_noground(100,50,A), dump([A]).
go3 :- divider(100,30,20,Amps,VCenter), dump([Amps,VCenter]).
go4 :- divider_noground(100,30,20,Amps,VCenter), dump([Amps,VCenter]).
go5(XOhms) :- wheat(100,100,XOhms,50,30,Amps), dump([XOhms,Amps]).
go6(XOhms) :- wheat_noground(100,100,XOhms,50,30,Amps), dump([XOhms,Amps]).

go7(N) :- 
  ladder(T1,T2,10,N),
   battery(B1,B2,100),
   ammeter(A1,A2,Amps),
   electrical_ground(G),
   connect([B2,A1]), connect([A2,T1]), connect([T2,B1,G]),
   dump([Amps]).