As is traditional at this festive time of year, here is a collection of amusing uLisp problems to challenge your brain cells. I’ll give the answers in a few days’ time.

### Self-reproducing programs

A traditional programming challenge is to create a self-reproducing program in your favourite programming language: in other words, a program that, when run, prints its own source.

In Lisp the challenge translates to finding an expression that evaluates to itself. Trivial atoms such as **t** or **7** are not permitted.

Here’s one possible answer in uLisp:

```
((lambda (x) (list x (list (quote quote) x)))
(quote (lambda (x) (list x (list (quote quote) x)))))
```

Can you find a shorter one?

### Primes without numbers

This challenge is to write a function **prime?** (and any subfunctions you need) to take a list and return **t** if the length of that list is a prime number, or **nil** otherwise. So, for example:

```
> (prime? '(a b c d e f g h i j k l m))
t
```

but:

```
> (prime? '(a b c d e f g h i j k l))
nil
```

The catch is that you’re not allowed to use any numerical functions, such as the arithmetic operators **+** **-** * **/**, the comparisons **>** **<** **>=** **<=**, **mod**, **length**, **oddp**, **evenp**, or **zerop**.

### Speedup

Here’s a routine that makes any uLisp function run faster:

```
(defun speedup (fn)
(let ((c nil))
(lambda (x)
(or (cdr (assoc x c))
(let ((r (funcall fn x)))
(setq c (cons (cons x r) c))
r)))))
```

It works on any function with one parameter. Let’s test it on a couple of the functions from the Benchmarks page.

First let’s try the **Hofstadter Q sequence**, one of several recursive sequences described in Douglas Hofstadter’s brilliant book “Gödel, Escher, Bach: an Eternal Golden Braid”. It is defined as follows:

```
(defun q (n)
(if (<= n 2) 1
(+
(q (- n (q (- n 1))))
(q (- n (q (- n 2)))))))
```

It is related to the Fibonacci sequence, except that in this case the two preceding terms specify how far to go back in the sequence to find the two terms to be summed.

It’s an interesting sequence because, unlike the Fibonacci sequence, it’s not monotonic. For example:

```
> (q 15)
10
> (q 16)
9
```

Using uLisp running on an ATmega2560 **(q 16)** takes about 4 seconds:

```
> (for-millis () (q 16))
4226
```

To speed it up with **speedup** simply execute:

```
(setq q (speedup q))
```

Now try evaluating (q 16) again:

```
> (for-millis () (q 16))
50
```

This time it only takes 50 msec, nearly a factor of 100 improvement!

We can apply **speedup** to another function; for example, here’s the **Fibonacci sequence**:

```
(defun fib (n)
(if (< n 3) 1
(+ (fib (- n 1)) (fib (- n 2)))))
```

On an ATmega2560 **(fib 20)** takes about 6 seconds:

```
> (for-millis () (fib 20))
6393
```

Speed it up:

```
(setq fib (speedup fib))
```

Now try again:

```
> (for-millis () (fib 20))
45
```

How does **speedup** work its magic?