A small collection of uLisp challenges – with answers

#1

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?

A pulsating puzzle – with answer
Another collection of uLisp puzzles – with answers
#2

Here are the answers to the uLisp challenges.

Self-reproducing programs

I asked for a shorter self-reproducing program in uLisp that, when run, prints its own source. Here’s the answer:

((lambda (x) (list x x)) (lambda (x) (list x x)))

This takes advantage of the fact that in uLisp, as in Scheme, the value of a function is its own lambda expression.

For a fuller discussion see Self-Reproducing Programs in Common Lisp (PDF) by Peter Norvig.

Primes without numbers

This challenge was to write a function prime? (with any subfunctions it needs) to take a list and return t if the length of that list is a prime number, or nil otherwise, without using any numerical functions.

First we write sub, which recursively subtracts the length of list b from list a and returns the result:

(defun sub (a b)
  (if (null b) a
    (sub (cdr a) (cdr b))))

So, for example:

> (sub '(x x x x x) '(y y y))
(x x)

The contents of the lists are irrelevant. If the second list is the same length or longer than the first list the function returns nil :

> (sub '(x x) '(y y y))
nil

We will use sub for three different purposes in the following routines.

Next we write div, which divides the length of list a by list b:

(defun div (a b)
  (cond
   ((null a) t)
   ((sub b a) nil)
   (t (div (sub a b) b))))

If the length of the second list divides exactly into the length of the first list it returns t:

> (div '(x x x x x x) '(y y y))
t

Otherwise it returns nil:

> (div '(x x x x x x x) '(y y y))
nil

It repeatedly calls (sub a b) to subtract the length of the second list from the first. It also uses (sub b a) to test whether the first list is the same length or shorter than the second list.

Finally pri takes a list of length n, and a starting divisor list of length d. It checks all divisors from d up to n and returns t if the length of n is prime:

(defun pri (n d)
  (cond
   ((null (sub n d)) t)
   ((div n d) nil)
   (t (pri n (cons 'x d)))))

The starting value of d should be '(x x). It calls itself recursively with progressively longer lists until either (div n d) succeeds, in which case the number is composite, or (sub n d) returns nil, in which case it’s prime.

Finally, for tidyness, we can wrap up the function with the starting value of d and call it prime?:

(defun prime? (n)
  (pri n '(x x)))

So, for example, if n has length 9, a composite:

> (prime? '(x x x x x x x x x))
nil

If n has length 11, a prime:

> (prime? '(x x x x x x x x x x x))
t

Speedup

The third question was to explain how the function speedup makes a recursive uLisp function such as fib, the Fibonacci sequence, or q, the Hofstadter Q sequence, execute faster.

The function speedup works by returning a new version of its argument as a closure that caches the results of previous numbers it was called with on a list c.

We can reveal how it works by inserting a print statement as follows:

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

If we now define fib, the Fibonacci sequence:

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

and call speedup on it:

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

then running

(fib 10)

gives:

((2 . 1)) 
((1 . 1) (2 . 1)) 
((3 . 2) (1 . 1) (2 . 1)) 
((4 . 3) (3 . 2) (1 . 1) (2 . 1)) 
((5 . 5) (4 . 3) (3 . 2) (1 . 1) (2 . 1)) 
((6 . 8) (5 . 5) (4 . 3) (3 . 2) (1 . 1) (2 . 1)) 
((7 . 13) (6 . 8) (5 . 5) (4 . 3) (3 . 2) (1 . 1) (2 . 1)) 
((8 . 21) (7 . 13) (6 . 8) (5 . 5) (4 . 3) (3 . 2) (1 . 1) (2 . 1)) 
((9 . 34) (8 . 21) (7 . 13) (6 . 8) (5 . 5) (4 . 3) (3 . 2) (1 . 1) (2 . 1)) 
((10 . 55) (9 . 34) (8 . 21) (7 . 13) (6 . 8) (5 . 5) (4 . 3) (3 . 2) (1 . 1) (2 . 1))

as successive values are added to the cache. For each new n the fib function is only called once, and subsequently the value of (fib n) is simply returned from the cache without evaluating fib.

#3

Hi David,
I’m very impressed by this challenges. Sadly my lisp knowledge is too small to solve them myself, but I try to learn as much as possible from them.
Thank you very much,
regards,
Kaef

#4

You’re welcome! Now I’ve just got to start thinking of some more for next year!

#5

[speedup]
What I had missed before is that you re-define the function (setq fib (speedup fib)),
I played with this on my ulisp board – very impressive! I think something like this can’t be done in many other programming languages (ie. C, C++) in such generic form…