Memoizer 4a – Lisp for Mortals

Now that this is getting to be a series, I ought to provide links to the previous entries, in case anyone is actually reading this thing:

• Memoizer 1 – C++
• Memoizer 2 – Python
• Memoizer 3 – Lua

Other than the C++ example, this series has been part of an experiment to bootstrap my experience in dynamically typed programming languages — and what sort of experiment would it be if I overlooked Lisp.  So here it goes.

All those parenthesis!

I can already hear the cries of some programmers, those who were brought up being told Lisp is interesting, but full of all those inscrutable (((parenthesis))) that make it so hard to read.  I know because I feel the same way — like many others, I come from C and initially fear the parenthesis.

So, to get that out of the way, Lisp parenthesis 101!

In Python, you might write:

  1:     # python, step 0
  2:     def fib(n):
  3:       if n < 2:
  4:         return 1
  5:       else:
  6:         return fib(n-1) + fib(n-2)
Or better yet, In C and C++ you might write:
  1:     // C++, step 0
  2:     int fib(int n){
  3:       if(n < 2) {
  4:          return 1;
  5:       } else {
  6:         return fib(n-1) + fib(n-2);
  7:       }
  8:     }
Lets start translating it to Lisp.
Step One: remove those types in the function signature in C, and replace the Python ‘def’ with ‘defun’:
    # python, step 1
    defun fib (n):
      if n < 2:
        return 1
      else:
        return fib(n-1) + fib(n-2)
    // C++, step 1
    defun fib (n) {
      if(n < 2) {
         return 1;
      } else {
        return fib(n-1) + fib(n-2);
      }
    }
Step Two: Lisp takes away operators, and gives you back consicely named functions.  Pretend that “+” and “<” are simple functions, so “x < y” can be reworded “<(x, y)” and so forth.
    # python, step 2
    defun fib (n):
      if <(n, 2):
        return 1
      else:
        return +(fib(-(n,1)), fib(-(n,2)))
    // C++, step 2
    defun fib (n) {
      if( <(n, 2) ) {
         return 1;
      } else {
        return +(fib(-(n,1)), fib(-(n,2)));
      }
    }
Step Three: Lets replace curly braces {} and indenting with parenthesis. And for good measure, lets put those function names inside the parenthesis so we can always tell which thing is getting which arguments:
    # python, step 3
    (defun fib (n):
      (if (< n 2):
        (return 1)
      else
        (return (+ (fib (- n 1)) (fib (- n 2))))))
    // C++? step 3
    (defun fib (n)
      (if (< n 2)
        (return 1);
      else
        (return (+ (fib (- n 1)) (fib (- n 2))));
      )
    )
Step Four: Now we’re in the home stretch. Those semicolons are just getting in the way now, and I’ve already ripped out the commas from underneath you.  The keywords ‘else’ and ‘return’ are superfluous now.  A little more cleanup, and:
    ; Python-y Lisp! step 4
    (defun fib (n)
      (if (< n 2)
          1
        (+ (fib (- n 1)) (fib (- n 2)))))
    ; C++-y Lisp! step 4
    (defun fib (n)
      (if (< n 2)
          1
        (+ (fib (- n 1)) (fib (- n 2)))
      )
    )
Now the only difference we’re left with is indentation.  C++-y Lispers may want to keep with the closing-brace style above, but Scheme Style would suggest the whitespace/Python-like approach.
Until next time…
I only picked up Practical Common Lisp just today, and this post is long enough as it is, so I’ll save the memoizer for the next post.
Whether you love Lisp or hate it, I hope this post can help you see past all those (((parenthesis))).