This is an overview of the implementation of the search module; hopefully, it will help you understand the actual code. The description is arranged for you to read as you read the corresponding files.

`Search.scm`

First, we define a couple of global variables.

*number-of-search-steps* keeps track of the number of expansions during a search.
*verbose* controls how much printing happens during the search, set it to #f to limit the amount of printing.

Now, we define the key data structure used in the implementation, namely that of a search-node, which has the following components:

cost - this is the f-value of a node, that is, the sum of the actual cost and the estimate.
actual - this is the g-value of a node, that is, the actual length of the path represented by this node.
estimate - this is the h-value of a node, that is, the (under)estimate of the path length to a goal.
state - the state corresponding to the node.
predecessor - the previous state along the path.
id - this is an arbitrary (but unique) number used internally to identify the node.

The key function is SEARCH which accepts the following arguments:

goal - the goal state. Note that it is trivial to generalize this to a list of goal states.
successors - a function that is given a search-node and returns a list of descendant nodes. This usually involves a call to the extend-node function defined below.
pending - this is Q in our slides, implemented by a function that accepts a number of messages that enable adding and removing nodes, finding the best entries, etc. The details are in search-q.scm .
expanded - an "expanded list" implemented by a function that accepts a number of messages that enable adding and removing nodes as well as checking for their presence. The details are in search-q.scm . This can be #f.

visited - a "visited list" implemented similarly to expanded. This can be #f. The SEARCH function is quite simple.

If the pending list is empty, return indicating failure.
Let current be the next element in pending. The implementation of the pending list will determine what node is next, for example, it could be the one with the least cost or simply the most recently added node.
If we have an expanded list and the state of the current node is in the expanded list, then discard it and call search again.
If the node's state is the goal, display the path and return the current node.
Update the pending list by calling SEARCH-UPDATE with the successors of the current node and call search again.

The SEARCH-UPDATE function form updates the pending, expanded and visited lists. In its simplest form, it adds the current node to the expanded list (if present) and then filters out any nodes whose states are in the visited or expanded lists (if present) and adds them to the pending and to the visited list (if present). There is a much more elaborrate version of this function defined in SEARCH-UPDATE.SCM, we will look at that later.