12.5.7 Functions As Network Representation

12.5.7  Functions As Network Representation

  In this section, we will show that functions can be used to represent a network of nodes. We do this by using closures that share binding or refer to one another. Closures allow us to build networks at a higher level of abstraction than usual. Closures have three useful properties: they are active, they have local state, and we can make multiple instances of them. We can use multiple copies of active objects with local state to capture representation of networks. Since a closure can refer to other nodes (i.e., closures), one node can send its output to other nodes or a node can accept outputs of other nodes. In this way, it is possible to "compile" some networks into pure code.

The problem discussed in this section is a toy problem based on Chapter 6 of On Lisp: Advanced Techniques for Lisp [Gra94]. The techniques discussed in this section can be extended and used to build substantial real applications. We first discuss a standard way of building the representation for a network. We then show how the network can also be represented by closures. The application we discuss is a program that plays twenty questions. The network is a binary tree. Each internal node of the network contains a yes/no question. The user is asked this question. Depending on the answer that the user gives, the left or right branch of the binary tree is traversed. Ultimately the player arrives at a leaf node. The leaf node simply contains a value. When the player arrives at a leaf node, the value in the leaf node is returned as the answer to the whole game. The following is a short interaction with the program.

Is the person a man?

>> yes

Is he living?

>> no

Was he American?

>> yes

Is he on a coin?

>> yes

Is the coin a penny?

>> yes

Lincoln

The programs that we write here have bare minimum code to make the example interaction given above work.