Skip to content
February 7, 2010 / gus3

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)
  ; 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)
  ((= i 0) 0)
  (t (format t "~d ~d~%" i (collatz i)))))


Leave a Comment
  1. Zach Beane / Feb 12 2010 8:35 am might be helpful. Also, you shouldn’t use EQ on numbers – it need not return true for numerically equal values. = is preferable.
    (Thanks, fixed. — gus3)

  2. foo / Feb 13 2010 4:35 pm
    (defun collatz (x)
    (cond ((evenp x) (1+ (collatz (/ x 2))))
    ((plusp x) (1+ (collatz (1+ (* 3 x)))))
    (t 0)))
  3. gus3 / Feb 13 2010 4:57 pm

    That fails when x is 1; the second condition applies, rather than the third.
    So, (plusp x) should instead be (> x 1) or (plusp (- x 1)).

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: