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.
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
> (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.
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 4 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?