These exercises are in addition to those in Graham. They cover various basic Lisp concepts. Some are just for fun, some are useful tools. Several come from Wilensky's Common LispCraft.

## Lisp #1: HAS-NUMBER-P (Wilensky 8.7)

Define `(has-number-p s-exp)` to return
true if the s-expression is or contains a number.

> (has-number-p 1) T > (has-number-p 'a) NIL > (has-number-p '(a (b (c d) ((3))))) T

Implement this using a simple conditional, recursion, and SOME. Letting SOME do some of the work is more efficient than a pure CAR-CDR recursive solution.

## Lisp #2: KEY-IF (Wilensky 13.2)

Define the macro `key-if` to have the form

(KEY-IF test :THEN exp1 exp2 ... :ELSE exp3 exp4 ...)

This does about the same thing as:

(COND (test exp exp ...) (T else-exp else-exp ...))

Both clauses are optional and can come in either order, but only once. Here are some legal forms and their results:

> (key-if (> 3 1) :then 'ok) OK > (key-if (< 5 3) :else 'ok) OK > (key-if (> 3 1) :else 'oops) NIL > (key-if (> 3 1) :then) NIL > (key-if (> 3 1) :else 'oops :then 'ok) OK > (key-if (> 3 1) :else 'oops :then (print 'hi) 'ok) HI OK

## Lisp #3: MAKE-BALANCE (Wilensky, 12)

Define `(make-balance initial-balance)` to
return a function that takes 0 or 1 arguments. If that function is
called with 0 arguments, it returns the current balance. If called
with 1 argument, which should be a number, it adds that number to the
current balance, and returns the new balance.

> (setq bal (make-balance 100)) <a closure object> > (funcall bal 10) 110 > (funcall bal -50) 60 > (funcall bal) 60

## Lisp #4: DELETE-CAR (Wilensky, 15)

Define `(delete-car list)` to modify and
return

*list*with the first element of list deleted.

> (setq l (list 'a 'b 'c)) (A B C) > (delete-car l) (B C) > L (B C)

Note: it's impossible to destructively delete the only item in a
list and turn it into NIL, but `delete-car` should at least
return NIL in that case.

## Lisp #5: COLLECT-NUMBERS (Wilensky, 15)

Define `(collect-numbers s-exp)` to return
a list of all the numbers in the s-expression

*s-exp*.

*s-exp*may be an atom, a list, or a list of s-expressions.

> (collect-numbers 1) (1) > (collect-numbers 'a) NIL > (collect-numbers '(1 (b (2 c) ((3))))) (1 2 3)

Implement this using a simple conditional, recursion, and MAPCAN. Letting MAPCAN do some of the work is more efficient than a pure CAR-CDR recursive solution. Don't worry about duplicate numbers in the result.

## Lisp #6: TCONC (Wilensky, 15.7)

Adding elements to the end of a list is usually inefficient in Lisp:

`(append`is the worst possible approach, because*list*(list*item*))*list*gets copied every time a new item is added. If you use this form to build a list N long, you'll have done N squared`cons`'s. Imagine doing that for a simple 100-element list!`(nconc`doesn't*list*(list*item*))`cons`, but still gets very slow as the list gets long, because Lisp has to`cdr`all the way to the end of the list in order to find the last`cons`cell to modify.

A classic solution is to create a data structure called a
`tconc` structure (for "tail concatenate"), which holds two
pointers to the same list:

- a
*head pointer*to the whole list, and - a
*tail pointer*to the last`cons`cell of that list.

With this data structure, you can add new elements to the end of the list with just a few quick operations, no matter how long the list is, and you can still get the whole list whenever you need it.

Therefore, your job is to:

- Define
`(make-tconc [`to return a*list*])`tconc`structure pointing to*list*. Ifis a non-NIL list, subsequent calls to*list*`tconc`or`tconc-list`modify. If*list*is empty, or none is given, a*list*`tconc`structure for an empty list is returned. - Define
`(tconc`to add the items, if any, to the end of the list pointed to by*tconc-structure*[*item item ...*])*tconc-structure*, update*tconc-strcture*appropriately, and return the new value of the internal list.*Watch out! It's easy to write this to cause the argument list to be destructively modified.* - Define
`(tconc-list`to add the items in*tconc-structure list*)*list*to the end of the internal list. Neither this nor subsequent calls to`tconc`or`tconc-list`affect.*list*

Note that you can get the internal list at any time with
`(tconc tconc-structure)`.

> (setq tc (make-tconc)) <tconc structure> > (tconc tc 1) (1) > (tconc tc 2 3) (1 2 3) > (tconc tc) (1 2 3) > (setq nums '(1 2 3 4)) (1 2 3 4) > (setq nums2 '(5 6 7)) (5 6 7) > (setq nums3 '(8 9 10)) (8 9 10) > (setq tc2 (make-tconc nums)) <tconc structure> > (tconc-list tc2 nums2) (1 2 3 4 5 6 7) > (tconc-list tc2 nums3) (1 2 3 4 5 6 7 8 9 10) > nums (1 2 3 4 5 6 7 8 9 10) > nums2 (5 6 7)

Each successive call to `tconc` should be efficient, no
matter how long the internal list has grown. One test of your
`tconc` structure is that it *always *obeys the following
rule:

(eq (lasthead-pointer)tail-pointer)

## Lisp #7: LIST-OF

[ Inspired by Guy Lapalme's article in *Lisp Pointers*,
Apr-Jun 91 ]

`list-of` is a macro that simplifies collecting lists of
values of expressions. Though this description is long, and the macro
is powerful, it's actually quite simple and can be implemented with
relatively little code.

The general syntax is

(LIST-OFexp generator-or-filter generator-or-filter ...)

It's easiest to explain by starting with simple examples.

> (list-of (1+ x) (x :in '(1 2 3))) (2 3 4)

*exp* is `(1+ x)` and `(x :in '(1 2 3))` is a
generator. A generator is anything that has the form
`( variable :in list)`. This
generator generates three values for

`x`, namely

`1`,

`2`, and

`3`.

`list-of`returns a list of the value of

`(1+ x)`for those three values of

`x`.

> (list-of (1+ x) (x :in '(1 2 3)) (oddp x)) (2 4)

The *exp* and generator are
as before, but now I've added the filter `(oddp x)`. A filter is any
expression that doesn't look like a generator. The filter says "keep
only those values of `x` that are odd." Hence,
`list-of` only collects values for `(1+ x)` equal to
`1` and `3`.

That's it. Any number of generators and filters can be given. They are applied from left to right. If there are two generators, the second repeats itself for every value created by the first, e.g.,

> (setq l '(a b)) (A B) > (list-of (list x y) (x :in l) (y :in )) ((A A) (A B) (B A) (B B))

Likewise, the filters apply in order.

> (setq l '(1 2 3 4)) (1 2 3 4) > (list-of (list x y) (x :in l) (oddp x) (y :in l) (evenp y)) ((1 2) (1 4) (3 2) (3 4))

This collects `(list x y)` for every `x` in
`l` that is odd and every `y` in `l` that is
even. Notice that

> (list-of (list x y) (x :in l) (y :in l) (oddp x) (evenp y)) ((1 2) (1 4) (3 2) (3 4))

returns the same answer, but does more work. Trace `oddp`
to see the difference.

One special case that follows naturally:

`(list-of`simply returns a list of*exp*)*exp*.

**Note**:
It'd be more direct to write "the list of x in l that are odd" as

(list-of (x :in l) (oddp x))

rather than

(list-of x (x :in l) (oddp x))

Define `list-of`

so that
if no initial expression to collect is given, it uses the variable
of the first generator.

Our final examples are primarily for hard-core computer science
types. You can skip them if you wish. Neither are particularly
efficient, but they show the power of `list-of`.

To define a function that gets all the permutations of a list:

(defun perms (l) (if (endp l) (list nil) (list-of (cons a p) (a :in l) (p :in (perms (remove a l :count 1))))))

The `list-of` collects "`(cons a p)` for every
`a` in `l` and every `p` in the permutations of
`l` with `a` removed."

To define a simple unoptimized version of Quicksort:

(defun qsort (l) (if (endp l) nil (let ((a (car l)) (r (cdr l))) (append (qsort (list-of (x :in r) (< x a))) (list a) (qsort (list-of (x :in r) (>= x a)))))))

This splits `l` into those elements that are less than the
`car` of `l`, and those that are greater, sorts each
sublist recursively, and joins the results.

## Lisp #8: MULTIPLE-VALUE-SETF

This exercise has been retired.

## Lisp #9: WITH-COLLECTOR

Common Lisp has a nice special form for building strings, called
`with-output-to-string`. The `with-collector` macro
adds similar functionality to list building.

(with-collector (fn-name[accumulator])expression expression...)

This evaluates the expressions with * fn-name* bound

*temporarily*to a function that, given zero or more arguments, adds them to the end of the list in

*.*

`accumulator`*returns the new value of the list. The value of the last*

`fn-name`*is returned.*

`expression`As with * with-output-to-string*, in the common case
where you are collecting a fresh list, you can eliminate the accumulator
variable. Then

- an internal initially empty list will be created
will add its arguments to that list`fn-name`- the final value of that list will be returned from
`with-collector`rather than the value of the last expression - you can just write
instead of`fn-name``(`.*fn-name*)

Here are two examples:

> (with-collector collect (dolist (x '(1 2 3 4)) (when (oddp x) (print (collect x))))) (1) (1 3) (1 3) > (let ((odds (list 'odds))) (with-collector (collect odds) (dolist (x '(1 2 3 4)) (when (oddp x) (collect x)))) odds) (ODDS 1 3)

To be efficient, * with-collector* should expand
into code that uses tconc.

Your macro should not define any global functions. Check out flet for how to define local ones.

## Lisp #10: Tokenizer

Some of the clumsiest code written is code to process strings, for example, to look for certain patterns, or even just to split a string up using some character or string as a delimiter. The clumsiness is caused by the need to manage several variables in parallel, such as the starting and end points for matching.

One solution is to use a regular expression library. This is the right way to go if you're doing repeated and/or complicated string processing. But a regular expression library is a big hammer if all you want to do is something simple, like split a string up into parts.

Some people, when confronted with a problem, think "I know, I'll use regular expressions." Now they have two problems. [source: it's complicated].

For example, assume we want to implement
a `split-string` function so that

> (split-string " Now is the time ") ("Now" "is" "the" "time") > (split-string "12,132,abc" #\,) ("12" "132" "abc")

For tasks like this, the easiest thing is to create a "string tokenizer." This is an object that you initialize with some string and delimiter that provides two methods:

`(next-token-p`returns true if there's at least one more token (substring) left in the tokenizer*tokenizer*)`(next-token`returns that token and updates internal variables to point to the next one, if any*tokenizer*)

With a tokenizer you can collect the substrings you want with any simple loop form, e.g.,

(defun split-string (str &optional (delim #\space)) (let ((tr (make-tokenizer str delim))) (do ((l nil (cons (next-token tr) l))) ((not (next-token-p tr)) (nreverse l)))))

There's one special consideration. When splitting strings,
programmers normally expect something like
`" ab cd ef"`

to return 3 strings if split
on spaces, namely `("ab" "cd" "ef")`

, i.e., only
the "real" tokens. But if
the delimiter is not a space, e.g., a comma or tab, then they
want to see any empty tokens,e.g., `",ab,cd,,ef"`

should yield `("" "ab" "cd" "" "ef")`

.

Define the function `(make-tokenizer string [delim])` to
create an instance of the class

`tokenizer`

with the given string and delimiter. The delimiter
should default to `#\SPACE`.

Here are some test cases, using the `split-string`

function defined above. Note particularly the intended behavior
in the boundary cases involving empty strings and different delimiters.

(define-test tokenizer (assert-equal '("now" "is" "the" "time") (split-string " now is the time ")) (assert-equal '("12" "132" "abc") (split-string "12,132,abc" #\,)) (assert-equal '("" "12" "132" "" "abc") (split-string ",12,132,,abc" #\,)) (assert-equal '("" "") (split-string "," #\,)) (assert-equal () (split-string " ")) (assert-equal '("") (split-string "" #\,)) (assert-equal '(" ") (split-string " " #\,)) )

## Lisp #11: MAP-RANGE, EVERY-RANGE, FIND-RANGE, REDUCE-RANGE

Lisp has many functions to operate on sequences, such as `mapcar`

and `some`

, but very few to operate on numeric ranges. So your
job is to define some.

Define the functions `map-range`

, `every-range`

, `find-range`

,
and `reduce-range`

to be simple versions of their list counterparts
The first three take a function and two numbers, *start*
and *end*, and apply the function to every integer from *start*, up or down to, but not including,
*end*. The iteration goes up or down,
depending on whether *end* is greater or lesser than *start*.

`reduce-range`

works similarly but takes an optional
fourth argument, the initial value to pass to the reduction.

> (map-range 'identity 1 10) (1 2 3 4 5 6 7 8 9) > (map-range 'identity 10 1) (10 9 8 7 6 5 4 3 2) > (map-range (lambda (n) (* n n)) 0 5) (0 1 4 9 16) > (map-range (lambda (n) (* n n)) 5 5) NIL > (find-range (lambda (n) (= (mod 35 n) 0)) 2 10) 5 > (find-range (lambda (n) (= (mod 35 n) 0)) 10 2) 7 > (every-range (lambda (n) (> (mod 37 n) 0)) 2 36) T > (every-range (lambda (n) (> (mod 35 n) 0)) 2 36) NIL > (every-range (lambda (n) nil) 5 5) T > (reduce-range (lambda (v x) (cons x v)) 1 5) (4 3 2 1) > (reduce-range '+ 1 5 0) 10

## Lisp #12: REDUCE-TREE

`REDUCE`

is a useful function for accumulating values
returned as a function is applied to every element of a list. Accumulating
can mean anything -- summing, building a list, picking a best value, etc.

Sometimes you want to do that for every atomic element of a tree, where a tree is an atom, or a list of trees (note the recursiveness of this definition.

Define `(reduce-tree `

to apply *function tree initial-value*)*function* to every atom element of *tree*, as defined above.
*function* takes two arguments: the current value so far, and the next
atom in *tree*, going left to right. The current value is *initial-value*
for the first atom in the tree. *initial-value* is optional and defaults to
`NIL`

. See the tests
for what happens with `nil`

and non-null
atomic trees.

> (reduce-tree '+ '((1 (2 3) (((4)))) 6) 0) 16 > (reduce-tree (lambda (x y) (cons y x)) '(a (b (c d) e) f)) (F E D C B A)

Don't worry about defining keyword parameters such as `:from-end`

.

## Lisp #13: TEST-EXP

Generalize the `test-exp`

macro in
the macro reading
to take any number of expressions. Each should be evaluated
and printed in order, using the "=>" format, with semicolons
separating pairs. The return value doesn't matter.

< (let ((x 1) (y 2)) (test-exp (+ x y) x y)) (+ X Y) => 3;X => 1;Y => 2

This is a simple macro exercise but also an exercise in
how to use `FORMAT`

. Use only one `FORMAT`

call. Note that there is no semicolon at the end.