Thursday, 6 May 2010

Lisp Tutorial | More Recursion in Lisp

Our last Lisp Tutorial introduced the idea of recursion in Lisp. Today we're looking at more recursive Lisp functions but first let's look at the answer to yesterday's Lisp challenge. 

Lisp Tutorial Answer
Write a function called INCREASING-P this function returns T if all the numbers in the list are in ascending order and NIL if they are not.

As a reminder, when writing recursive Lisp functions we need to be able to define the following 3 things:
  • When to stop recursing
  • How do we take the next step
  • How to call the recursive function
In the example of our INCREASING-P function we:
  • Stop recursing when we get to the last two elements of the list
  • Compare the first 2 elements of the list to see if the second is greater
  • Call the recursive function with the REST of the list
(defun increasing-p (the-list)
  (cond ((null (rest the-list)) t)
        ((< (first the-list) (second the-list))
         (increasing-p (rest the-list)))
        (t nil)))

Defining Variables
Before we look further at recursion we're going to define a GLOBAL VARIABLE. Global variables can be evaluated by all functions, this contrasts with LET and LET* which defined variables that were only valid inside that function.

To define a global variable we can use DEFVAR function for example:
(defvar *simpsons* '(homer marge lisa bart maggie))

Note, it's not necessary to though it is common practice and recommended to identify global variables with * around them like *this*

Now when we evaluate this variable we can see its contents:
*simpsons*
(HOMER MARGE LISA BART MAGGIE)

More Recursion in Lisp
Let's define a global variable called *planets*, In this variable we'll store a nested list of attributes of the planet

  • planet-name 
  • orbit(AU) 
  • diameter(km) 
  • mass(kg)
;planet-name orbit(AU) diameter(km) mass(kg)
(defvar *planets* '((mercury 0.38 4880 3.30e23)
                      (venus .72 12103.6 4.869e24)
                      (earth 1 12756.3 5.972e24)
                      (mars 1.52 6794 6.4219e23kg)
                      (jupiter 5.2 142984 1.900e27)
                      (saturn 9.54 120536 5.68e26)
                      (uranus 19.218 51118 8.63e25)
                      (neptune 30.06 49532 1.0247e26)
                      (pluto 39.5 2274 1.27e22)))

Copy, paste and evaluate the above in your Lisp environment.

If we want to create a list of the planet names we need to take the first element of each list. As our *planets* variable is a nested list, the FIRST of *planets* evaluates to this:
(first *planets*)
(MERCURY 0.38 4880 3.3E23)

To get the planets name we need to take the FIRST of this list, so the FIRST of the FIRST of *planets*:
(first (first *planets*))
MERCURY

To create a full list of our planets names we can use recursion, firstly we need to answer our three important questions:

  • When to stop recursing?
    • When we reach the end of the list
  • How do we take the next step
    • CONS the FIRST of the FIRST of *planets* 
  • How to call the recursive function
    • With the REST of *planets*
(defun get-names (planet-list)
  (if (null planet-list) nil
    (cons (first (first planet-list))
          (get-names (rest planet-list)))))

(get-names *planets*)
(MERCURY VENUS EARTH MARS JUPITER SATURN URANUS NEPTUNE PLUTO)

Today's Programming Lisp Challenge
Write GET-ORBIT, GET-DIAMETER, GET-MASS functions that creates a list of orbits, diameter and masses.

Subscribe to the RSS feed and check back soon for the answer and more Programming Lisp tutorials.