Re: Some advice for a lisp newb

From: a (abc_at_def.gh)
Date: 03/13/04 

Date: Sat, 13 Mar 2004 18:28:31 GMT

In Figure 3.12, the code states that the shortest path from a start node to
an end node in a network of nodes is found by performing a breadth-first
search (bfs) for the end node.

A bfs needs to know the end node for which it is searching, a queue
containing the current starting node, and the network which is being
searched. If the queue is empty, there is no current starting node because
the search has exhausted all paths. There is no path from the start node to
the end node. Bfs returns nil. Otherwise, there is a starting node. Bfs
attemps to build a path to the end node. The starting point for this path is
the first entry in the queue.

I need to digress and explain the structure of the queue. The queue is a
list of lists. The first entry, and every entry, in the queue is a list. Bfs
readies itself to search a path, which is the first entry in the queue. This
path is a list of nodes. The first entry in the path is a node. Bfs now has
a current path and a current node in that path.

If the current node is the goal, or end, node, bfs returns the path as the
solution to the search. Because the path was built up in reverse order, a
common idiom, used for efficiency, which can be explained separately, the
path is reversed before it is returned so that the returned path is in
start-to-end sequence.

If the current node is not the goal, or end, node, then another bfs search
will be performed. This new bfs search uses the same end node as the current
bfs search and the same network of nodes to be searched as the current bfs
search. The middle parameter, the queue of nodes searched so far, is
different for the new bfs search than the queue used in the current bfs
search.

The new queue for the new bfs search is constructed by appending the "rest"
of the current queue to the result of the function "new-paths" called with
the current path, current node, and current network of nodes. I will explain
new-paths separately from the rest of bfs.

As I said before, bfs is reinvoked with the same end goal node and the same
network but with a new queue. The new queue is "almost" the same as the old
queue but not quite the same. The new queue is missing the first entry of
the old queue, which we just searched, and the new queue includes any
new-paths that can be found when examining the current node. At some point,
either the end node will be found or the search will exhaust any possible
new-paths. There will be no more new-paths yet each recursion, or repeated
execution, through bfs will shorten the queue because only the rest of the
queue -- (cdr queue) -- is passed on each subsequent call to bfs. Therefore,
bfs eventually will either find the end node or terminate after determining
that there is no path to the end node.

How are new-paths found? The new-paths function accepts the current path,
the current node, and the network of nodes being searched. New-paths uses
mapcar, which maps a function over a list. The function is called once for
each member of the list. The results of each function call are collected
into a list, which is returned as the result of the mapcar. The mapcar's
result is returned as the result of new-paths.

The broad structure, then, is that a function will be called for every
member of a list and the results of the function will be put into a list
which will be returned as the result of new-paths. We need to understand the
function called for each member of the list and we need to understand what
is in the list whose members are passed to the function.

The function called for each member of the list accepts "n" and returns
(cons n path). Path is a list which was given to new-paths as a parameter.
The form "(cons X list)", in general, returns a list with X as the first
member of the list and the old list as all the other members. (Look on page
356 for information on append and cons. Decide what the differences are
between (append X list) and (cons X list), if there are any differences, and
when one or the other should be used.) We already know that, in this
example, a path is a list of nodes, so it is reasonable to guess that n is a
node. The lambda function used in the mapcar returns (cons n path) and the
mapcar accepts that returned result, saving it in a list, which will be
returned as the result of new-paths.

We have mapcar mapping a function over a list. What is the list? The code
gives it as (cdr (assoc node net)). On page 51 see that "(N)etworks are
represented as assoc-lists with elements of the form (node . neighbors)".
Assoc returns the entire (node . neighbors) form for the first entry in the
assoc list for which the node in the call to assoc matches the car of the
assoc-list entry. Assoc returned a (node . neighbors) structure in which the
node tests as equal to the node specified in the call to assoc. Assoc
returned (node . neighbors) but all we want is the neighbors, so we use (cdr
(assoc node net)).

New-paths simply returns a list of all the neighbors of a given node.

To summarize: The shortest-path from a start node to an end node in a
network of nodes is found via breadth-first search (bfs), which is given the
end, or goal, node, a list containing a list containing the start node, and
the network of nodes to be searched. Bfs returns nil if there is no path
from the start node to the end node. If there is at least one node remaining
to search, bfs examines the first path in the current queue of paths. Each
path is a list of nodes. Bfs looks at the first node in the current path. If
that node is the end node, bfs returns the current path because the current
path led bfs to the end node. If that node is not the end node, bfs is
called again using the paths not yet searched followed by a new path
consisting of the neighbors of the current node.

"Brett Kelly" <inkedmn@inkedmn.com> wrote in message
news:pan.2004.03.13.09.55.24.64934@inkedmn.com...
> I'm a C#/SQL programmer by trade, and I've recently acquired ANSI Common
> Lisp by Paul Graham intending to learn Lisp as a hobby. I've read through
> the first couple of chapters and I have to say that, by and large, I'm
> lost.
>
> Now, I consider myself to be a fairly intelligent guy, and I'm able to
> pick up other (imperative) languages fairly quickly, but Lisp is just
> giving my brain a serious run for its money. Is this normal? Am I reading
> the wrong book? Am I going about this the wrong way? I know that
> reading/writing code in a language is the best way to learn it, but (for
> example) I've spent about 3 hours total staring at one example from the
> book (3.12, page 52 for those who are interested), and it seriously has me
> baffled.
>
> I've been told (and read on several different sites) that learning Lisp
> will change the way you look at programming. I'm excited about this
> "enlightenment", but frustrated at the fact that it's not coming very
> easily to me...
>
> Any suggestions?
>
> Thanks in advance!!

Relevant Pages

  • Re: ACL shortest-path example
    ... A network is an association list. ... BFS stands for breadth-first search. ... (defun bfs (end queue net) ... To turn tail recursion into a loop, we have to re-assign the argument variables ...
    (comp.lang.lisp)
  • Re: Well always have Munich
    ... limits are arbitrary and if you'd rather use Tables instead of Select Lists ... you'll still need the best middleware to open up your VMS servers and your ... Java Applets enabled ... If things are still going well, enter an asterix "*" for the Queue Name ...
    (comp.os.vms)
  • Re: Tree Help
    ... Push the root of the tree onto a list ... Push the right child of root onto a list ... Put the ending node in the queue. ... level's nodes and the push the lists to a stack, ...
    (comp.programming)
  • [PATCH 4/15] cfq-iosched: rework the whole round-robin list concept
    ... Kill those lists and maintain an rbtree of cfq_queue's, ... struct list_head idle_rr; ... unsigned int dispatch_slice; ... * if a queue is marked sync and has sync io queued. ...
    (Linux-Kernel)
  • Re: Hutch, give it up.
    ... NOT by spinning in a polling loop. ... run and ready lists, which are OS maintained structures used for ... interrupt occurs. ... messages in the msg queue, it does not return to the calling task. ...
    (alt.lang.asm)