Sunday, October 12, 2008

Looping in Common Lisp

I'm currently taking an Artificial Intelligence class, and had my first assignment to be done in Common Lisp. There have been many variations of Lisp over the years, and currently the two major dialects are Common Lisp and Scheme, both of which are commonly used for Artificial Intelligence related applications.
Since I was learning Common Lisp over the course of doing the project, I had a somewhat difficult time getting the syntax for loops correct. For those of you who support the "pure" functional programming paradigm (where side effects and loops are evil): I took the lazy approach of using a loop and some variables rather than figuring out how to do the recursion. Faster? Maybe. Overall better? Varies by opinion. Feel free to disagree.

Anyway, these are the most useful and "safe" ways I found to do loops without causing massive debugging headaches that cause you to want to switch to a lucrative career in ice cream sales.

loop: The simplest loop structure
The "loop" structure is as simple as you can get. It provides no built-in termination, you must provide that yourself with a conditional statement, and the "return" command. Here is a simple example:

(let ((n 5))
(loop
(print "Looping!")
(- n 1)
(if (< n 0) (return "Finished"))
)


do: General Counting Loop
The "do" loop is analogous to the "for" loop structure in many languages. You can specify several variables, rules for how they are to be updated each iteration, and a stopping condition. For me, it took a little while to get used to the syntax, but once you understand the structure, you have a great deal of flexibility at your fingertips. The general syntax is as follows:

(do (([var1] [var1 initial value] [var1 step])
([var2] [var2 initial value] [var2 step])
.
.
)
([stopping-condition-test] [return value])
...commands....
)

A simple example that will loop 10 times, each time printing "Looping..." and
then will print "Finished":

(do ((i 0 (+1 i))
((= i 10) "Finished")
(print "Looping...")
)
dotimes:
"dotimes" is a specialized form of the "do" loop, suited for situations where you know exactly how many times you need to iterate. It basically saves you from having to enter a stopping condition, by counting from 0 until the number you specify. Here is the syntax:

(dotimes ([variable] [final-value])
...commands...
)

An example:

(dotimes (i 10)
(print i)
)


dolist:
"dolist" is another specialized form of "do", perfect for iterating through a list. You need to specify an iteration variable (holds the value of the current item in the list) and a list to iterate through. The basic form is as follows:

(dolist ([variable] [list])
...commands...
)

An example that squares each value of a list of numbers:

(dolist (item '(1 2 3 4 5))
(print (* item item))
)

Note: In this situation you could also use the one of the "map" functions (mapcar or maplist) to apply a function to each successive item in a list (mapcar), or to successive cdr's of a list (maplist). These functions both return another list.

Now, go forth and Lisp.