Skip to main content
Department of Information Technology

Lisp Exercises

Simple Stuff

  1. The function reverse is defined in Common Lisp on sequences. Define it yourself and make sure the complexity is linear. Can you make it work on lists, strings and vectors without resorting to calling the built in reverse?
  2. Define a function flatten that given an arbitrary S-expression returns a list of the elements of the structure.

CL-USER 41 > (flatten '(foo . bar))
(FOO BAR)

CL-USER 42 > (flatten '(((lisp) . (erlang . haskell))))
(LISP ERLANG HASKELL)

CL-USER 43 > (flatten '(((lisp (erlang) haskell))))
(LISP ERLANG HASKELL)

CL-USER 44 > (flatten t)
(T)

CL-USER 45 > (flatten nil)
NIL

Please note that different structures can flatten to the same list. A naive implementation will have quadratic complexity. Don't be naive.

Somewhat less simple

  1. With regards to the observation above, write a function that given two arbitrary S-expression determines if they flatten to the same list. If they do, the resulting list should be return. If not, return nil. A naive version (it could actually be worse) would be

(defun samefringe (s1 s2)
  (let ((fringe1 (flatten s1))
        (fringe2 (flatten s2)))
    (if (equal fringe1 fringe2)
        fringe1
      nil)))

Why is this a naive (and thus slow) version? Write a version that is faster.

Higher order

  1. Write a function to sort a list of elements (yes, there is a built in). It should take one mandatory argument, the list to be sorted, and two keywords arguments :order and :key. If :order is given it should be a predicate taking two arguments, returning non NIL if the arguments are in order. If :order is not given, the list should be ordered in increasing order. If :key is given it should be a function of one argument (an element in the list) return the key of the element to be sorted on. With no :key given, the actual elements should be used as keys.

Please note that it is possible to use only :order for sorting complex elements (it would first find the keys and then do the comparison).

Macros

  1. Define a macro SEQUENTIAL that takes a an arbitrary number of expressions, evaluates all of them and returns the value of the last expression.
  2. Define a macro EVAL-NTH that takes one mandatory argument (which should be or evaluate to a number) and a number of optional expressions. It should return the value of the Nth expression. The other expressions should not be evaluated. Take care of the case where the first argument is a numerical literal at expansion time (which makes it next to trivial) as well as the case where the first argument is an expression (value not known at expansion time).
  3. During a lecture, we defined COND as a macro that expands to IF. Take this definition and modify it so it works as the Common Lisp version. This means that each clause consists of one or more expressions. If the first evaluates to non NIL, the rest of the expressions should be evaluated and the value of the last expression should be returned. No expression should be evaluated more than one time. Observe the special case of one expression - if it is true, the value of it should be returned.
  4. Define your own versions of FLET and LABELS using the basic constructs of Common Lisp. The major point of this exercise is to show that it is possible to define FLET and LABELS using LAMBDA and LET (which is just a convenient version of LAMBDA anyway). Use GENSYM where needed. To see the full complexity of this exercise, be sure to test it with general code in the bodies of the local functions, i.e., they should contain expressions with COND, QUOTE and possibly FUNCALL. This should be true for the body of FLET/LABELS as well.
  5. Define a macro DEFCACHEFUN that can be used to define a function in the same was as DEFUN but with the added feature of constructing a cache that is used for subsequent repeated calls. The value of each unique function call should thus only be computed once, even for a recursive function.
  6. Define a macro that mimics the list comprehension construct in Erlang. Devise the "language" in the macro as well as the expansion.

Updated  2012-11-19 19:46:34 by Cons T. Åhs.