Starting with Lisp

Just for some fun and relaxation, I decided to start doing some Lisp. I had set up SLIME a few months backs while I was starting some book but I had not done much. I decided to use SBCL because I had read that is usually fast. The reason I was using SLIME is that the back arrow key does not work when I use the SBCL REPL and that is very annoying to me because I type both opening and closing parentheses together and type the rest of the code in between. To setup SLIME, a lot of documentation is available online so I wont re-iterate. Just for reference, the SLIME section of the .emacs file is as follows:

(setq inferior-lisp-program "/usr/bin/sbcl")
(add-to-list 'load-path "/usr/share/emacs/site-lisp/slime/")
(require 'slime)
(slime-setup)

Once I was in SLIME REPL, I started writing a few s-expression to get a hang of it.

(+ 1 2)

(print 'hello)

(format t "hello world")

After that, I started writing a simple function that returns the nth number in the Fibonacci sequence. I came up with the following.

(defun foo (n)
    (cond
     ((= n 1) 0)
     ((= n 2) (+ 1 (foo (- n 1))))
     (+ (foo (- n 1)) (foo (- n 2)))))

And I started testing it.

(foo 1)

(foo 2)

(foo 3)

The result for n = 3 was wrong. The reason lay in the last section of cond. I intended it to be default but I had not specified the condition for it. So, I corrected it as follows.

(defun foo (n)
    (cond
     ((= n 1) 0)
     ((= n 2) (+ 1 (foo (- n 1))))
     (t (+ (foo (- n 1)) (foo (- n 2))))))

Now, the method was returning correct values. Clearly, it is a bad implementation. So, I thought the calls to foo should be memoized. I could go ahead and try writing my own memoization but I wanted to see what Common Lisp had to offer. However, before doing that I wanted to know whether memoization will be beneficial. So, I wanted to benchmark the memoized and the plain versions. Our good friend Google helped me out. I was able to start profiling using SBCL's built-in package sb-prof.

(in-package :cl-user)

(require :sb-sprof)

(declaim (optimize speed))

(sb-sprof:with-profiling (:max-samples 1000
                          :report :flat
                          :loop nil)
  (foo 100))

I was a little doubtful that I should not be trying for the 100th Fibonacci number but still I went ahead with it and even after some minutes, it was going on. So, I now I decided to kill the profiling. Ctrl+C Ctrl+C came in handy. I started low this time. From 10, 15, 25, I reached up to 40 at which value it took around 6 seconds.

(sb-sprof:with-profiling (:max-samples 1000
                          :report :flat
                          :loop nil)
  (foo 40))

Now, I was ready to test a memoized version of the function and see how much benefit I can get. I remembered reading some code by Peter Norvig in Python which used a decorator to achieve generic memoization. So, I thought Lisp ought to have something similar. I found a nice memoization API. However, I had to install the package and I did not want to delve into that because I did not find any packages for Arch. So, I decided to settle for a less robust implementation.

(defun Basic-Memo (Function)
  "Takes a normal function object and returns an `equivalent' memoized one"
  (let ((Hash-Table (make-hash-table)))
    #'(lambda (Arg)
    (multiple-value-bind (Value Foundp)
        (gethash Arg Hash-Table)
      (if
        Foundp
        Value
        (setf (gethash Arg Hash-Table) (funcall Function Arg))))) ))

(defun Basic-Memoize (Function-Name)
  "Memoize function associated with Function-Name. Simplified version"
  (setf (symbol-function Function-Name)
    (Basic-Memo (symbol-function Function-Name))))

(Basic-Memoize 'foo)
Now, the 1000th Fibonacci number was also easily calculated. When I tried to the above profiling code for (foo 1000), I was getting error for the run being too short. Trying for 10000th Fibonacci number, I got 0.01 seconds.