I know very little Scheme, but am trying to demonstrate to some of
my colleagues a few of the features that Scheme has,
compared to Common Lisp. (CL is my language of choice)
I am using a CL book titled On Lisp by Paul Graham - - even though
it is a CL book, the author uses Scheme code to make some points.
Here is the Scheme function I am trying to get working, page 303 of 'On Lisp'
(define (path node1 node2)
(cond ((null? (neighbors node1)) (fail))
((memq node2 (neighbors node1)) (list node2))
(else (let ((n (choose (neighbors node1) )))
(cons n (path n node2))) )))
The problem is, the author left out the definition of the NEIGHBORS function,
also he does not specify how to make the arguments for PATH.
Here is the diagram, the aim of the PATH function is to return the
shortest path from node A to node E
C
/ \
/ \
/ \
/ \
A---------B
\
\
\
\
D------E
I derived the input node arguments for PATH with the following code.
This code may be in error, the author did not specify how to make
the arguments for PATH.
(define node-a)
(define node-e)
(set! node-a '(a b (c) (d . e)))
(set! node-e (cdr (cadddr node-a)))
(begin (set-cdr! (caddr node-a) node-a) 'done)
Be careful, node-a now contains of a circular list, if you try to evaluate it by itself you will get trapped in an endless loop.
node-a ===> (a b (c a b (c a b (c a b etc. etc.
Using these arguments, 'path' will be ran this way:
(path node-a node-e)
hopefully returning either (a d e) or (a d . e)
The definition of CHOOSE and FAIL are below, from page 304 of 'On Lisp'
******************************************************
(define *paths* '() )
(define failsym ยท@) ;; non-special usage, therefore no asterisks
(define call/cc call-with-current-continuation) ;; alias for convenience
(define (choose choices)
(call/cc
(lambda (cc)
(set! *paths* (append *paths*
(map (lambda (choice)
(lambda () (cc choice)))
choices)))
(fail) )))
;; the variable 'fail' starts life as a non-special global variable,
;; will be 'captured' and actually used as a function.
(define fail)
;; the code below _is_ the continuation. Scheme will automatically
;; use it wherever cc appears in the CHOOSE function. (i think)
(call/cc
(lambda (cc)
(set! fail
(lambda ()
(if (null? *paths*)
(cc failsym)
(let ((p1 (car *paths*)))
(set! *paths* (cdr *paths*))
(p1) ))) )))
***************************************************
End of definitions of CHOOSE and FAIL
If any one has worked their way though this particular PATH function
in Paul Graham's Common Lisp book "On Lisp" and actually got it
to work, I would be very interested in knowing how.
Gerald
Erann,
First, let me apologize for not making the problem clear, hopefully I
will remedy that with this post.
The PATH function should accept any path-like argument, say for
example an ordinary tree, or a circular list, or an inter-connected
network.
Assume for the moment that you intend to feed PATH a circular list
that looks like this:
----E----F----G----H----A----B----C----D----
| |
| |
--------------------------------------------
First, to even construct this circular list, you have to go through
gyrations. There is no simple way to construct a circular list
directly that I am aware of. Perhaps you know of a way.
To construct the above circular list I would do this:
(define circ-list)
(set! circ-list '(e f g h a b c d) )
(begin (set-cdr! (cdddr (cddddr circ-list)) circ-list) 'done)
To prove that circ-list was now indeed a circular list, I could
try evaluating it.
In the MacScheme that I am using, the prompt is >>>
>>> circ-list
(e f g h a b c d e f g h a b c d e f g h a b c d e f g h a b c.........
which results in an endless printout unless I reset Scheme,
so obviously I have a circular list.
Now the author of 'On Lisp', Paul Graham, claims that his PATH
function can find the shortest path from say node H to node B
even on a circular list.
Something like this, I would imagine:
>>> (path node-h node-b)
(h a b)
He does not detail how to make the node arguments for PATH.
He does not furnish a definition of the NEIGHBORS function.
To me, it makes no sense to manipulate the nodes of circ-list
directly. After all, the whole idea of the PATH function is to take
an _unknown_ path structure and return a list of the shortest
path between any two nodes which might be in the structure.
If I know the structure well enough to identify all the nodes
by sight, there is no point in using the 'path' function.
Gerald
Erann,
First, let me apologize for not making the problem clear, hopefully I
will remedy that with this post.
The PATH function should accept any path-like argument, say for
example an ordinary tree, or a circular list, or an inter-connected
network.
Assume for the moment that you intend to feed PATH a circular list
that looks like this:
----E----F----G----H----A----B----C----D----
| |
| |
--------------------------------------------
First, to even construct this circular list, you have to go through
gyrations. There is no simple way to construct a circular list
directly that I am aware of. Perhaps you know of a way.
To construct the above circular list I would do this:
(define circ-list)
(set! circ-list '(e f g h a b c d) )
(begin (set-cdr! (cdddr (cddddr circ-list)) circ-list) 'done)
To prove that circ-list was now indeed a circular list, I could
try evaluating it.
In the MacScheme that I am using, the prompt is >>>
>>> circ-list
(e f g h a b c d e f g h a b c d e f g h a b c d e f g h a b c.........
which results in an endless printout unless I reset Scheme,
so obviously I have a circular list.
Now the author of 'On Lisp', Paul Graham, claims that his PATH
function can find the shortest path from say node H to node B
even on a circular list.
Something like this, I would imagine:
>>> (path node-h node-b)
(h a b)
He does not detail how to make the node arguments for PATH.
He does not furnish a definition of the NEIGHBORS function.
To me, it makes no sense to manipulate the nodes of circ-list
directly. After all, the whole idea of the PATH function is to take
an _unknown_ path structure and return a list of the shortest
path between any two nodes which might be in the structure.
If I know the structure well enough to identify all the nodes
by sight, there is no point in using the 'path' function.
Gerald