CS325 Lisp Exercises and Critique

This document outlines a series of Lisp programming exercises for the CS325 course, referencing the textbook 'ANSI Common Lisp' by Paul Graham. It includes instructions on setting up the Lisp environment, running tests, and addressing critiques. The exercises cover various topics, including graph algorithms, list manipulation, and code style. The document also provides links to helpful websites and a list of specific exercises to complete, along with notes on fixing indentation and addressing previous comments on specific functions. The exercises require passing both automated tests and manual code critiques.

The first thing you have to do is set the lisp critique and tests. Follow the
instructions in ‘Lisp Critique and Tests’. To see if you installed correctly, I have
provided the example and output below.
Lisp Critique and Tests
http://www.cs.northwestern.edu/academics/courses/325/admin/lisp-setup.php
Here is what you should get
CS325-USER 2 > (critique (defun foo (x) (setq x (+ x 1))))
----------------------------------------------------------------------
INCF would be simpler to add 1 to X than SETQ
----------------------------------------------------------------------
It's bad style to reassign input parameters like X -- and often
useless.
----------------------------------------------------------------------
Don't use (+ X 1), use (1+ X) for its value or (INCF X) to change X,
whichever is appropriate here.
----------------------------------------------------------------------
CS325-USER 3 > (get-tests)
(3TREE-CLONE 3TREE-MEMBER ?IS-A ABSTS-ABSTP ALIST->HASH-TABLE
BIGGER-ARG BIN-SEARCH BST-ELEMENTS CAR-CIRCULAR-P CDR-
CIRCULAR-P CIRCULAR-MEMBER-P COLLECT-NUMBERS COMMON-ABSTS
COPY-QUEUE DELETE-CAR DIFF-BY-ONE-P DOUBLEF EMPTY-QUEUE-P
ENQUEUE-FRONT EVERY-RANGE EXTRACT-CODE-FROM-STREAM FIND-
RANGE FUNCTIONS-REFERENCED GET-A-COUNT GREATER GREATEST-ARG
HAS-LIST-P HAS-NUMBER-P HASH-TABLE->ALIST HENLEY-P HORNER
INTERSECT INTERSECT-SEGMENTS INTERSPERSE KEY-IF LIST-OF
LONGEST-PATH MAKE-BALANCE MAKE-BEST-CHANGE MAKE-CHANGE
MAKE-QUEUE MAP-RANGE MAP-STREAM MAX-MIN MEMBER-MATCH
MEMOIZE MY-COPY-LIST MY-REMOVE-IF MY-REVERSE N-OF NORMAL
NROTATE-ARRAY NTH-EXPR OCCURRENCES POSITION+ PRECEDERS
PRESERVE PRINT-DOTS REDUCE-TREE REQUEUE-FRONT RING-PACKAGE
ROTATE-ARRAY SHORTEST-PATH SHOW-DOTS SHOW-LIST SOLVE STABLE-
INTERSECTION STABLE-SET-DIFFERENCE STABLE-UNION STREAM-SUBST
SUMMIT TCONC TEST-TAKING-MATCH TOKENIZER TWO-MOST WITH-
COLLECTOR)
This is the textbook for the various exercises.
The Textbook
https://7chan.org/pr/src/ANSI_Common_Lisp_-_Paul_Graham.pdf

Here are helpful websites that contain partially / mostly completed answers.
Helpful Websites
http://www.shido.info/lisp/pacl2_e.html#symbol
https://github.com/pdelong42/ANSI_Common_Lisp-solutions
https://github.com/ffilozov/ANSI-Common-Lisp
https://github.com/ryuk/ansi-common-lisp-exercises
Here is the exercise list. You can see that the exercises have been slightly changed
from the textbook versions.
Exercise list
https://www.cs.northwestern.edu/academics/courses/325/exercises/
exercises.php
Below are the exercises to do in the textbook (make sure to take ‘Exercise list’ into
account). The exercises first need to pass the tests and then the critique. For
example, pretend you have created the read-stream function in 8-5:
(defun read-stream (input
.... )))
First (run-tests read-stream) must be passed
Second (critique
(defun read-stream (input
.... ))) )
Must be passed
Next, the assignment is submitted and the professor usually comes back with a few
comments.
Exercises to do (Graham)
Do Lisp: 10, 11, 12, 13
Do Graham: 7-2, 7-5+6, 8-5, 9-5, 9-6, 10-3+5, 10-8
Fix Graham comments: 3-9, 5-9
Fix Indentation: Graham 4-4 and 10-6
Matcher: 1, 2
Other: Triple query filter, Make Best Change, Insert Segments, camelize & hyphenate
* Fix indentation for 4-4 and 10-6 below.
* I have notes for Graham 3-9 and 5-9 below.
;4-4 – fix indentation
(defun bst-elements (bst)

(labels ((loop (a bst)
(if a
(loop (node-r a)
(cons (node-elt a)
(loop (node-l a) bst)))
bst)))
(loop bst nil)))
;10-6 – fix indentation
(defmacro preserve (vars &body body)
`(let ,(mapcar #'(lambda (name)
`(,name ,name)) vars)
,@body))
;3-9
(defun longest-path (begin stop web)
(if (eql begin stop)
(let ((answer (bfs begin stop web nil)))
(if (null answer)
(list begin)
answer))
(bfs begin stop web (list begin))))
This is more complicated than necessary.
OR is the simplest way to do "use calculated value or ..." It replaces the conditional
and sometimes eliminates a LET.
(defun bfs (begin stop web previous)
Very poor names. previous implies one element. this is a path. web is not a common
name for a graph or network
You're passing an argument you don't need. the start element should not be needed.
it's in the path. you only care about end.
(if (and (eql begin stop) (not (null previous)))
Why worry about this case when you handle it in longest-path?
(list stop)
(do ((i (cdr (assoc begin web))
(cdr i))
This is bad indentation. Nested code should always be indented more than the
surrounding code. Must be fixed
(best nil
(new-trail best (car i) stop web previous)))
((null i)
(if (null best)
nil
(cons begin best))))))

(defun new-trail (best test stop web previous)
(if (member test previous) best
(let ((new-best (bfs test stop web (cons test previous))))
(if (> (length new-best) (length best))
new-best
best))))
One function to a function. The main loop (the DO) should handle
for each node adjacent to end of path
keep the longer of
the best-path-so-far
vs path-thru-node-to-end
Then this function should just get the path through "test" -- possibly NIL
;5-9
(defun shortest-path (begin end net)
(catch 'all-done
(bfs end (list (list begin)) net)))
This is bad indentation. Nested code should always be indented more than the
surrounding code.
(defun bfs (end queue net)
(and queue
(let* ((path (car queue))
(vertex (car path))
(vertex-links (cdr (assoc vertex net))))
This is very bad indentation.
(if (member end vertex-links)
(throw 'all-done (reverse (cons end path)))
(bfs end
(rebuild-line path vertex-links (cdr queue))
net)))))
Keep the simple code Graham. There's another place you can throw that is already
scanning the vertices
(defun rebuild-line (path vertex-links oldies)
(append oldies
(mapcan #'(lambda (n)
(unless (member n path)
(list (cons n path))))
WHEN and UNLESS are not appropriate when the return value is needed. WHEN
and UNLESS are for when you sometimes want to do some actions. Use IF or COND
or AND/OR, as appropriate, when values matter.
vertex-links)))

; No exceptions version
(defun shortest-trail (begin end web)
web is a bad name for a network the world wide web did not lead to CS renaming
basic concepts
(bfs end (list (list begin)) web))
(defun bfs (end waiting_order web)
Underbars are not normally used in Lisp names. You won't see any built-in functions
with them. Use hyphens.
waiting order is a very odd name for a well understood concept -- queue. why
change from what Graham wrote?
(and waiting_order
(let* ((trail (car waiting_order))
trail? You appear to be suffering from thesaurus surrogatisation
https://github.com/Droogans/unmaintainable-code#thesaurus-surrogatisation
(vertex (car trail))
(vertex-links (cdr (assoc vertex web))))
(if (member end vertex-links)
(reverse (cons end trail))
(bfs end
(rebuild-waiting_order trail vertex-links (cdr waiting_order))
why mess up graham's code with bad names and moving things, like the append,
that made much more sense where he put them?
web)))))
(defun rebuild-waiting_order (trail vertex-links visited)
(append visited
(mapcan #'(lambda (n)
(unless (member n trail)
(list (cons n trail))))
WHEN and UNLESS are not appropriate when the return value is needed.
vertex-links)))