6Functions as RepresentationGenerally, data structures are used to represent. An array could represent ageometric transformation; a tree could represent a hierarchy of command; a graphcould represent a rail network. In Lisp we can sometimes use closures as arepresentation. Within a closure, variable bindings can store information, and canalso play the role that pointers play in constructing complex data structures. Bymaking a group of closures which share bindings, or can refer to one another, wecan create hybrid objects which combine the advantages of data structures andprograms.Beneath the surface, shared bindings are pointers. Closures just bring us theconvenience ofdealingwiththemat ahigherlevelofabstraction. Byusing closuresto represent something we would otherwise represent with static data structures,we can often expect substantial improvements in elegance and efficiency.6.1 NetworksClosures have three useful properties: they are active, they have local state, andwe can make multiple instances of them. Where could we use multiple copiesof active objects with local state? In applications involving networks, amongothers. In many cases we can represent nodes in a network as closures. As well ashaving its own local state, a closure can refer to another closure. Thus a closurerepresenting a node in a network can know of several other nodes (closures) towhich it must send its output. This means that we may be able to translate somenetworks straight into code.766.1 NETWORKS 77> (run-node ’people)Is the person a man?>> yesIs he living?>> noWas he American?>> yesIs he on a coin?>> yesIs the coin a penny?>> yesLINCOLNFigure 6.1: Session of twenty questions.In this section and the next we will look at two ways to traverse a network.First we will follow the traditional approach,with nodes defined as structures, andseparate code to traverse the network. Then in the next section we’ll show how tobuild the same program from a single abstraction.As an example, we will use about the simplest application possible: one ofthose programs that play twenty questions. Our network will be a binary tree.Each non-leaf node will contain a yes/no question, and depending on the answerto the question, the traversal will continue down the left or right subtree. Leafnodes will contain return values. When the traversal reaches a leaf node, its valuewill be returned as the value of the traversal. A session with this program mightlook as in Figure 6.1.The traditional way to begin would be to define some sort of data structure torepresent nodes. A node is going to have to know several things: whether it is aleaf; if so, which value to return, and if not, which question to ask; and where togo depending on the answer. A sufficient data structure is defined in Figure 6.2.It is designed for minimal size. The contents field will contain either a questionor a return value. If the node is not a leaf, the yes and no fields will tell where togo depending on the answer to the question; if the node is a leaf, we will know itbecause these fields are empty. The global *nodes* will be a hash-table in whichnodes are indexed by name. Finally, defnode makes a new node (of either type)and stores it in *nodes*. Using these materials we could define the first node ofour tree:(defnode ’people "Is the person a man?"’male ’female)78 FUNCTIONS AS REPRESENTATION(defstruct node contents yes no)(defvar *nodes* (make-hash-table))(defun defnode (name conts &optional yes no)(setf (gethash name *nodes*)(make-node :contents conts:yes yes:no no)))Figure 6.2: Representation and definition of nodes.(defnode ’people "Is the person a man?" ’male ’female)(defnode ’male "Is he living?" ’liveman ’deadman)(defnode ’deadman "Was he American?" ’us ’them)(defnode ’us "Is he on a coin?" ’coin ’cidence)(defnode ’coin "Is the coin a penny?" ’penny ’coins)(defnode ’penny ’lincoln)Figure 6.3: Sample network.Figure 6.3 shows as much of the network as we need to produce the transcript inFigure 6.1.Now all we need to do is write a function to traverse this network, printingout the questions and following the indicated path. This function, run-node,isshown in Figure 6.4. Given a name, we look up the corresponding node. If it isnot a leaf, the contents are asked as a question, and depending on the answer,we continue traversing at one of two possible destinations. If the node is a leaf,run-node just returns its contents. With the network defined in Figure 6.3, thisfunction produces the output shown in Figure 6.1.6.2 COMPILING NETWORKS 79(defun run-node (name)(let ((n (gethash name *nodes*)))(cond ((node-yes n)(format t "~A~%>> " (node-contents n))(case (read)(yes (run-node (node-yes n)))(t (run-node (node-no n)))))(t (node-contents n)))))Figure 6.4: Function for traversing networks.(defvar *nodes* (make-hash-table))(defun defnode (name conts &optional yes no)(setf (gethash name *nodes*)(if yes#’(lambda ()(format t "~A~%>> " conts)(case (read)(yes (funcall (gethash yes *nodes*)))(t (funcall (gethash no *nodes*)))))#’(lambda () conts))))Figure 6.5: A network compiled into closures.6.2 Compiling NetworksIn the precedingsection we wrote a network programas it might havebeen writtenin any language. Indeed, the program is so simple that it seems odd to think thatwe could write it any other way. But we can—in fact, we can write it much moresimply.The code in Figure 6.5 illustrates this point. It’s all we really need to run ournetwork. Instead of having nodes as data structures and a separate function totraverse them, we represent the nodes as closures. The data formerly contained inthe structures gets stored in variable bindings within the closures. Now there is noneed for run-node; it is implicit in the nodes themselves. To start the traversal,80 FUNCTIONS AS REPRESENTATION(defvar *nodes* nil)(defun defnode (&rest args)(push args *nodes*)args)(defun compile-net (root)(let ((node (assoc root *nodes*)))(if (null node)nil(let ((conts (second node))(yes (third node))(no (fourth node)))(if yes(let ((yes-fn (compile-net yes))(no-fn (compile-net no)))#’(lambda ()(format t "~A~%>> " conts)(funcall (if (eq (read) ’yes)yes-fnno-fn))))#’(lambda () conts))))))Figure 6.6: Compilation with static references.we just funcall the node at which we want to begin:(funcall (gethash ’people *nodes*))Is the person a man?>>Fromthen on,the transcriptwill bejust as it waswith thepreviousimplementation.By representing the nodes as