=chapter Declarative Programming =note need discussion of declarative programming. Why do you have to specify the algorithm? You should just be able to specify the constraints, and have it figure out how to calculate them. Beginning programmers often wish for a way to just tell the computer what they want, and have the computer figure out how to do it. Declarative programming is an attempt to do that. The idea is that the programmer will put in the specifications for the value to be computed, and the computer will use the appropriate algorithm. Nobody knows how to do this in general, and it may turn out to be impossible. But there are some interesting results one can get in specific problem domains. Regular expressions are a highly successful example of declarative programming. You write a pattern which represents the form of the text you are looking for, and then sit back and let the regex engine figure out the best way of locating the matching text. Searching in general lends itself to declarative methods: the programmer specifies what they are searching for, and then lets a generic heuristic searching algorithm look for it. Database query languages are highly visible examples of this; consider X, or the query language of R. The programming language X is an extension of this idea to allow general computations. We've seen searching in some detail already, so in this chapter we'll look at some other techniques and applications of declarative programming. =Section Constraint Systems Suppose you wrote a program to translate Fahrenheit temperatures into Celsius: sub f2c { my \$f = shift; return (\$f - 32) * 5/9; } Now you'd like to have a program to perform the opposite conversion, from Celsius to Fahrenheit. Although this calculation is in some sense the same, we have to write completely new code, from scratch: sub c2f { my \$c = shift; return 9/5 * \$c + 32; } The idea of constraint systems is to permit the computer to be able to run this sort of calculation in either direction. =section Local Propagation Networks One approach that seems promising is to distribute the logic for the calculation amongst several objects in a X like this: =picture constraint-network-F-to-C +---+ i | f +---. +---+ `---+---+ k | - +---. m +---+ ,---+---+ `---+---+ +---+ | 32+---' | * +---+ c | +---+ j +---+ ,---+---+ +---+ |5/9+---' +---+ l =endpicture constraint-network-F-to-C There is a node in the network for each constant, variable, and operator. Lines between the nodes communicate numeric values between nodes, and are called X. A node can set the value on one of its wires; this sends a notification to the node at the other end of the wire that the value has changed. Because values are propagated only from nodes to their adjacent wires to the nodes attached at the other end of the wire, the network is called a X. A constant node has one incident wire, and when the network is started up, the constant node immediately tries to set its wire to the appropriate constant value. In the network above, wire I initially has the value 32, and wire I initially has the value 5/9. The nodes marked with variable names, C and C in this example, are input-output nodes. Initially, they do nothing, but the user of the program has the option to tell them to set their incident wires to certain values; that is how the user sends input into the network. If an input-output node notices that its incident wire has changed value, it announces that fact to the user; that's how output is emitted from the network. We'll use the network above to calculate the Celsius equivalent for 212 Fahrenheit. We start by informing the C node that we want V to have the value 212. The C node obliges by setting the value of wire I to 212. The change on wire I wakes up the attached C<-> node, which notices that both of its input wires now have values: wire I has the value 212 and wire I has the value 32. The C<-> node performs subtraction; it subtracts 32 from 212 and sets its output wire I to the difference, 180. The change on wire I wakes up the attached C<*> node, which notices that both of I input wires now have values: wire I has the value 180 and wire I has the value 5/9. The C<*> node performs multiplication; it multiplies 180 from 5/9 and sets its output wire I to the product, 100. The change on wire I wakes up the attached input-output node C, which notices that its input wire now has the value 100. It announces this fact to the user, saying something like c = 100 which is in fact the Celsius equivalent of 212 Fahrenheit. What makes this interesting is that the components are so simple and so easily reversible. There's nothing about this process that requires that the calculation proceed from left to right. Let's suppose that instead of calculating the Celsius equivalent of 212 Fahrenheit, we wanted the Fahrenheit equivalent of 37 Celsius. We begin by informing the C input-output node that we want the value of V to be 37. The C node will set wire I to value 37. This will wake up the C<*> node, which will notice that two of its three incoming wires have values: I has value 5/9 and I has value 37. It will then conclude that wire I must have the value M<37/(5/9)> = 66.6, and set wire I accordingly. The change in the value of wire I will wake up the attached C<-> node, which will notice that the subtrahend I is 32 and the difference I is 66.6, and conclude that the minuend, I, must have the value 98.6. It will then set I to 98.6. This will wake up the attached C node, which will announce something like f = 98.6 which is indeed the Fahrenheit equivalent of 37 Celsius. It's no trouble to attach more input-output nodes to the network to have it calculate several things at once. For example, we might extend the network like this: =picture constraint-network-F-to-C-to-K +---+ i | f +---. +---+ `---+---+ k | - +---. +---+ ,---+---+ `---+---+ +---+ | 32+---' | * +-+-+ c | +---+ j +---+ ,---+---+ | +---+ |5/9+---' | +---+ +---------. p m '---+---+ +---+ | - +---+ k | +------+ ,---+---+ +---+ |273.15+---' +------+ n =endpicture constraint-network-F-to-C-to-K Now setting C to 37 causes values to propagate in two directions. The 37 will propagate left along wire I as before, eventually causing node C to announce the value 98.6. But wire I now has three ends, and the 37 will also propagate rightward, causing the C<-> node to set wire I