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)

This exercise has been retired.


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)

This exercise has been retired.


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:

A classic solution is to create a data structure called a tconc structure (for "tail concatenate"), which holds two pointers to the same 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:

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 (last head-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-OF exp 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:

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, TCONC

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-name1 fn-name2 ...)
  expression expression ...)

This evaluates the expressions with the fn-name's bound temporarily to functions that, given zero or more arguments, adds them to an internal list, and return the new list. The value of the last expression is returned.

with-collector comes in handy when you have an API that implements the visitor pattern. For example, Alain Picard's CSV parser provides the function (map-csv-file file fn) that passes fn a list of the data on each line in a CSV file. To collect and return two lists, one for odd values and one for even values:

(with-collector (collect-odd collect-even)
  (map-csv-file "data.csv"
   (lambda (row)
     (if (oddp (cadr row)) (collect-odd row)
       (collect-even row))))
  (list (collect-even) (collect-odd)))

Since most often we want to collect and return a single list, there is a shorthand form.

(with-collector fn-name)
  expression expression ...)

is equivalent to

(with-collector (fn-name)
  expression expression ... (fn-name))

To collect just the rows where the 2nd column is an odd value:

(with-collector collect-odd
  (map-csv-file "data.csv"
   (lambda (row)
     (when (oddp (cadr row)) (collect-odd row)))))

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

To be efficient in building a list as it goes, define with-collector to expand into code that uses the function tconc. Define and include tconc with your macro code. Be sure to test your tconc with the unit tests provided.


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:

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.

Common Lisp's reduce has many special cases. reduce-range is simpler and more like reduce in other languages. (reduce fn start end [init]) always passes the accumulated value in the first argument to fn, and always starts with the initial value (default nil).

> (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 function tree initial-value) to apply 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

Note that there is no semicolon at the end.

This is a simple macro exercise but also an exercise in how to use FORMAT. The code generated by the macro should need only one FORMAT call, no looping form, no list building.


Faculty: Chris Riesbeck
Time: Monday, Wednesday, Friday: 11am - 11:50am
Location: Tech LR5

Contents

Important Links