My First Lisp Program
No longer a mere Lisp script kiddie, I’ve written a Lisp program from scratch, and gotten it to work properly. And I think I’m a better programmer for it, even if only marginally. I haven’t had to be this flexible in my coding thought since my very, very first paid programming job sixteen years ago.
My standard project for studying a new language is to implement the Collatz sequence in that language. It provides all the necessary requirements to explore a language: storage, retrieval, testing, branching. Some shortcuts in the sequence are possible, but the computation required to determine if a shortcut can be applied at any given step is greater than simply sticking to the basic definition of the sequence.
There are two main representations of the Collatz computation, iterative and self-referential (recursive). The iterative approach is very common in imperative languages, because it lends itself to an optimal execution model for local scratch variables and iteration counters.
But iterations can be counted by other means. In the case of the recursive representation of the Collatz sequence, the number of stack frames ultimately becomes the Collatz value for a given number. In developing my Lisp representation of the Collatz sequence, I discovered for myself what a Lisp hacker had already said:
Any looping construct found in an imperative language can be represented as a recursive function.
This is one of the core tenets of Turing completeness: any Turing-complete machine can simulate any other Turing-complete machine, independently of the representation and implementation of the machines’ instructions.
So now, I present to you my first Lisp program, implemented in Common Lisp:
(defun collatz(x) (cond ; Ordered by likelihood: ; Even recurses to collatz(x/2) ((= (mod x 2) 0) (+ (collatz (/ x 2)) 1)) ; Odd recurses to collatz(3x+1), ; except for 1 ((> x 1) (+ (collatz (+ (* 3 x) 1)) 1 )) ; 1 terminates (t 0))) (dotimes (i 1000000) (cond ((= i 0) 0) (t (format t "~d ~d~%" i (collatz i)))))