Getting Lisp

I've been using lisp on and off for the past few years. I read some lisp books, went through The Little Schemer and some of SICP. But I could never really think in lisp. When I needed to write some code, I would prefer another language first. I was writing imperative code for 10 years before I saw lisp, and I was used to it.

Recently, I have found myself wanting to use lists (including alists, plists, etc.) as data structures for everything, even when I'm not even writing lisp. I think I finally got lisp and now I want to use lisp for everything.

For example, take this little problem from the other day on f(t). Katie Nowak gives us a math problem,

There is a 75% chance of rain on any given day in the next week. What is the probability that it will rain on at least 5 of the 7 days?

Rain cloud in parenthesis The purpose of the question was to point out a neat coincidence in the problem (explained at the link). I used a program to solve the problem and there are two reasons for this.

First, I wanted to use the program to explore the problem and find the "special" property. With a program, I could quickly try different parameters, which would take longer, and be more error prone, by hand.

Second, which is similar to the first, I hate evaluating a large expression by hand. It's slow and error prone. Writing a program to do the same work is faster and mistakes are easier to catch. Also, I can quickly try different parameters to make sure my program's output is reasonable. In this case, for any reasonable input, the output, a probability, shouldn't be greater than 1.

Well, let's see, this is a Bernoulli experiment: each day is independent, so it is like flipping a coin seven times and counting the heads. That means we need the choose function.

My first thought was Octave, as this is a simple program and Octave already provides nchoosek() for me.

# Rain at least n days
function sum = rain (n)
  sum = 0;
  for i = n:7
    sum += nchoosek(7,i) * 0.75 ^ i * 0.25 ^ (7 - i);

Simple, but I actually made a couple little mistakes working it out, and it took me a little longer than it should have. If you asked someone to write this program in any imperative language, it would probably look a lot like this.

I then made a lisp version (elisp), but I first needed to define the binomial coefficient function since there wasn't one provided.

(defun nck (n k)
  "The binomial coefficient."
  (if (or (= k 0) (= k n)) 1
    (+ (nck (- n 1) (- k 1)) (nck (- n 1) k))))

This is the recursive version, based on Pascal's rule, so it doesn't need factorials.

In lisp, recursion is preferred to iteration, so that's the way I approached the program.

(defun p-rain (n)
  "Probability of rain on exactly n days."
  (* (nck 7 n) (expt 0.75 n) (expt 0.25 (- 7 n))))

(defun rain-at-least (n)
  "Probability it will rain on at least n days."
  (if (> n 7) 0
    (+ (p-rain n) (rain-at-least (+ 1 n)))))

I like the recursive version, and this code, much better. It presents the solution in a more straight forward way. And I got it right the first time, too. Yes, it was written after the Octave version, but I still think it counts for something.

The lisp version is also less complex. The Octave version has to use some temporary variables, i and sum, which is extra conceptual overhead. Sure, it could also be written recursively, but this is not really the way Octave is meant to be written.

Eh, not a great example, really. Lisp has so many powerful features, like macros (the powerful lisp kind), symbols, low-level access into the interpreter, and the REPL, that allow the programmer to do some really cool things. Many of these features are unique to lisps.

I'm really liking lisp.

blog comments powered by Disqus

null program

Chris Wellons