---

The Ultimate Guide to Recursive Song Generation in Common Lisp

Learn to generate the cumulative 'Food Chain' song lyrics algorithmically in Common Lisp. This guide covers data-driven design using association lists, recursive function implementation, and string manipulation to solve this classic programming challenge, moving from basic concepts to a complete, elegant solution.

---

The Challenge: Coding a Song Without Losing Your Mind

Have you ever tried to code something that follows a repetitive, yet slightly changing pattern? You start by copying and pasting, making small tweaks. Soon, your code becomes a tangled mess of duplication, a nightmare to debug and impossible to extend. This is a common trap for new and experienced developers alike.

The classic "I Know an Old Lady Who Swallowed a Fly" song is a perfect example. It's a cumulative song where each new verse builds upon the last. A naive approach would involve writing out every verse by hand, leading to fragile and unmaintainable code. But what if there was a better way? A way to capture the song's logic in a few elegant functions?

This guide will walk you through solving this very problem using Common Lisp. We'll leverage the language's powerful features for handling data and recursion to build a solution that is not only correct but also clean, concise, and deeply instructive. You'll learn how to think algorithmically and turn a complex pattern into simple, reusable code.

---

What Exactly is the Food Chain Song Problem?

The "Food Chain" problem, based on the cumulative song, challenges us to programmatically generate its lyrics. The song's structure is the key. It starts with a simple verse about an old lady swallowing a fly. Each subsequent verse introduces a new, larger animal and then recursively lists all the previous animals it was swallowed to catch.

Let's break down the pattern:

• Verse 1: Introduces the fly. Ends with a standard closing line.
• Verse 2: Introduces the spider. Includes a unique remark about the spider. Then, it explains that the spider was swallowed to catch the fly, and repeats the closing lines from Verse 1.
• Verse 3: Introduces the bird. Includes a unique remark about the bird. Then, it explains the bird was swallowed to catch the spider, which was swallowed to catch the fly, and so on.
• The Final Verse: The song culminates with a horse, which has a terminal, non-recursive ending: "...She's dead, of course!".

The core challenge is managing this "cumulative" and "recursive" logic. We need a system that can, for any given animal, generate its introductory line, its unique remark, and the entire chain of animals it was meant to catch, all the way back to the fly.

I know an old lady who swallowed a fly.
I don't know why she swallowed the fly. Perhaps she'll die.

I know an old lady who swallowed a spider.
It wriggled and jiggled and tickled inside her.
She swallowed the spider to catch the fly.
I don't know why she swallowed the fly. Perhaps she'll die.

... and so on.

This structure is a perfect candidate for an algorithmic solution, especially in a language built for symbolic manipulation and recursion like Common Lisp.

---

Why Common Lisp is the Perfect Tool for This Task

While you could solve this problem in any language, Common Lisp offers a particularly elegant and natural way to model the solution. Its design philosophy aligns perfectly with the problem's requirements.

1. Data as Code (Homoiconicity)

Lisp's syntax is made of lists. This means you can represent your program's data in the same structure as your code. For the Food Chain problem, we can define the entire song's data—animals, remarks, and order—in a simple list structure. This makes the logic incredibly clear and easy to modify.

2. Innate Support for Recursion

Recursion is not just a feature in Lisp; it's a fundamental, idiomatic way of thinking. The song's structure, where each verse contains a smaller version of the previous verse's "chase" sequence, is inherently recursive. Lisp allows us to express this recursive relationship directly and concisely.

3. Powerful String and List Manipulation

Common Lisp comes with a rich standard library for manipulating lists and formatting strings. Functions like format, car, cdr, and assoc are tailor-made for parsing our data structure and assembling the final lyrics with precision and control.

By using Common Lisp, we're not just finding a solution; we're learning a powerful paradigm for problem-solving that separates data from logic, leading to more flexible and maintainable programs. This is a core lesson from the exclusive kodikra.com Common Lisp curriculum.

---

How to Build the Song Generator: A Step-by-Step Implementation

Let's architect our solution from the ground up. Our strategy will be to first define the data, then build the functions that operate on that data to generate the verses and, finally, the complete song.

Step 1: The Data-Driven Foundation

First, we must avoid hardcoding strings. We'll define all the animal-specific information in a single data structure. An association list (alist) is perfect for this. It's a list of key-value pairs, where the key is the animal's name and the value is its unique remark.

Here is our central data definition. Notice how the order of the list itself defines the order of the song.

(defparameter *animals*
  '(("fly" . "")
    ("spider" . "It wriggled and jiggled and tickled inside her.")
    ("bird" . "How absurd to swallow a bird!")
    ("cat" . "Imagine that, to swallow a cat!")
    ("dog" . "What a hog, to swallow a dog!")
    ("goat" . "Just opened her throat and swallowed a goat!")
    ("cow" . "I don't know how she swallowed a cow!")
    ("horse" . "")))

This approach is powerful. If we wanted to add a new animal, say a "whale," we would only need to insert it into this list. The rest of our code, which we'll write next, will adapt automatically.

ASCII Diagram: Data Structure Flow

This diagram illustrates how our program will access the data. We start with the list and retrieve information for each animal in sequence.

    ● Start with *animals* list
    │
    ▼
  ┌───────────────────────────┐
  │ `(("fly" . "")            │
  │  ("spider" . "It wriggled…")│
  │  ("bird" . "How absurd…") │
  │  ...)                      │
  └──────────┬────────────────┘
             │
             ├─→ Get Animal 1 ("fly") ───→ Get Remark ("")
             │
             ├─→ Get Animal 2 ("spider") → Get Remark ("It wriggled…")
             │
             └─→ ... and so on

Step 2: The Recursive Engine for the "Chase"

The most complex part of the song is the repeating chain: "She swallowed the X to catch the Y...". We'll create a recursive helper function, recite-chase, to handle this.

The function will take a list of remaining animals as its argument.

• Base Case: When the list only contains the "fly", we print the final two lines and stop.
• Recursive Step: For any other animal, we print the line connecting it to the previous one, and then call the function again with the rest of the list.

(defun recite-chase (animals)
  "Recursively generates the 'swallowed to catch' part of a verse."
  (let ((current-animal (caar animals))
        (next-animal (caar (cdr animals))))
    (cond
      ((string= next-animal "fly")
       (format nil "She swallowed the ~a to catch the ~a.~%I don't know why she swallowed the fly. Perhaps she'll die."
               current-animal next-animal))
      ((string= next-animal "spider")
       (format nil "She swallowed the ~a to catch the ~a that wriggled and jiggled and tickled inside her.~%~a"
               current-animal next-animal (recite-chase (cdr animals))))
      (t
       (format nil "She swallowed the ~a to catch the ~a.~%~a"
               current-animal next-animal (recite-chase (cdr animals)))))))

Note the special case for the spider, which has a longer line connecting it to the fly. This kind of conditional logic is easy to handle within the recursive function.

Step 3: Assembling a Single Verse

Now we need a function, recite-verse, that constructs a complete verse given its number (e.g., verse 3 for the bird).

This function will:

1. Get the correct animal and its remark from our *animals* list.
2. Print the opening line: "I know an old lady who swallowed a...".
3. Handle the three special cases: fly, horse, and all other animals.
4. For a standard animal, print its unique remark and then call recite-chase with the appropriate sublist of animals.

(defun recite-verse (n)
  "Generates the nth verse of the song."
  (let* ((sub-animals (subseq *animals* 0 n))
         (current-animal-pair (car (last sub-animals)))
         (animal (car current-animal-pair))
         (remark (cdr current-animal-pair)))
    (format nil "I know an old lady who swallowed a ~a.~a"
            animal
            (cond
              ((string= animal "horse")
               "~%She's dead, of course!")
              ((string= animal "fly")
               "~%I don't know why she swallowed the fly. Perhaps she'll die.")
              (t
               (format nil "~%~a~%~a"
                       remark
                       (recite-chase (reverse sub-animals))))))))

ASCII Diagram: Recursive Function Logic

This flow shows how recite-chase would work when called for the "cat" verse. It unwinds the call stack until it hits the base case (the fly).

    ● Call: recite-chase(cat → bird → spider → fly)
    │
    ▼
  ┌──────────────────────────────────┐
  │ Print: "swallowed cat to catch bird" │
  └───────────────┬──────────────────┘
                  │
                  ▼
      ● Call: recite-chase(bird → spider → fly)
      │
      ▼
    ┌──────────────────────────────────────────┐
    │ Print: "swallowed bird to catch spider that wriggled..." │
    └──────────────────┬───────────────────────┘
                       │
                       ▼
          ● Call: recite-chase(spider → fly)
          │
          ▼
        ┌────────────────────────────────────────┐
        │ BASE CASE REACHED: It's the fly!         │
        │ Return: "swallowed spider... I don't know why..." │
        └────────────────────────────────────────┘
                       ▲
                       │
    ● Return value bubbles up the call stack
    ▲
    │
  ● Final string is assembled

Step 4: Generating the Full Song

The final piece is a function, song, that ties everything together. It simply loops from the first verse to the last, calling recite-verse for each one and concatenating the results with blank lines in between.

(defun song ()
  "Generates the entire song from verse 1 to 8."
  (format nil "~{~a~^~%~%~}"
          (loop for i from 1 to (length *animals*)
                collect (recite-verse i))))

The format directive ~{~a~^~%~%} is a concise Lisp idiom. It iterates over a list (collected by the loop), printing each element (~a) and inserting a separator (~%~%, two newlines) between them.

The Complete Solution Code

Here is the final, complete code packaged within a Common Lisp package definition. This is a best practice for organizing code and avoiding symbol conflicts.

(defpackage #:food-chain
  (:use #:cl)
  (:export #:song))

(in-package #:food-chain)

(defparameter *animals*
  '(("fly" . "")
    ("spider" . "It wriggled and jiggled and tickled inside her.")
    ("bird" . "How absurd to swallow a bird!")
    ("cat" . "Imagine that, to swallow a cat!")
    ("dog" . "What a hog, to swallow a dog!")
    ("goat" . "Just opened her throat and swallowed a goat!")
    ("cow" . "I don't know how she swallowed a cow!")
    ("horse" . "")))

(defun recite-chase (animals)
  "Recursively generates the 'swallowed to catch' part of a verse."
  (let ((current-animal (caar animals))
        (next-animal (caar (cdr animals))))
    (cond
      ((string= next-animal "fly")
       (format nil "She swallowed the ~a to catch the ~a.~%I don't know why she swallowed the fly. Perhaps she'll die."
               current-animal next-animal))
      ((string= next-animal "spider")
       (format nil "She swallowed the ~a to catch the ~a that wriggled and jiggled and tickled inside her.~%~a"
               current-animal next-animal (recite-chase (cdr animals))))
      (t
       (format nil "She swallowed the ~a to catch the ~a.~%~a"
               current-animal next-animal (recite-chase (cdr animals)))))))

(defun recite-verse (n)
  "Generates the nth verse of the song."
  (let* ((sub-animals (subseq *animals* 0 n))
         (current-animal-pair (car (last sub-animals)))
         (animal (car current-animal-pair))
         (remark (cdr current-animal-pair)))
    (format nil "I know an old lady who swallowed a ~a.~a"
            animal
            (cond
              ((string= animal "horse")
               "~%She's dead, of course!")
              ((string= animal "fly")
               "~%I don't know why she swallowed the fly. Perhaps she'll die.")
              (t
               (format nil "~%~a~%~a"
                       remark
                       (recite-chase (reverse sub-animals))))))))

(defun song ()
  "Generates the entire song from verse 1 to 8."
  (format nil "~{~a~^~%~%~}"
          (loop for i from 1 to (length *animals*)
                collect (recite-verse i))))

Running the Code

To run this code, save it as a file (e.g., food-chain.lisp). Then, you can load and execute it from a Common Lisp implementation like SBCL (Steel Bank Common Lisp).

$ sbcl
* (load "food-chain.lisp")
T
* (food-chain:song)
"I know an old lady who swallowed a fly.
I don't know why she swallowed the fly. Perhaps she'll die.

I know an old lady who swallowed a spider.
It wriggled and jiggled and tickled inside her.
She swallowed the spider to catch the fly.
I don't know why she swallowed the fly. Perhaps she'll die.
..."

---

Pros and Cons: Data-Driven vs. Hardcoded Approach

To fully appreciate our solution, it's helpful to compare it to the most basic alternative: hardcoding the entire song. This highlights the importance of algorithmic thinking for maintainability and scalability.

Aspect	Data-Driven Recursive Approach (Our Solution)	Hardcoded Approach (Naive Solution)
Maintainability	Excellent. To change a line or add an animal, you only edit the *animals* list. The logic remains untouched.	Poor. Changing a single line (like the fly's closing) requires finding and replacing it in every single verse. Very error-prone.
Scalability	High. Adding 10 more animals is as simple as adding 10 more entries to the data list. The code scales automatically.	None. Each new verse must be written out completely by hand, increasing code size linearly and making it unmanageable.
Readability	Good. The logic is separated from the data. Anyone reading the code can understand the song's structure from the *animals* list and the recursive pattern from the functions.	Poor. The code is a giant wall of text. The underlying pattern is obscured by massive amounts of duplicated string data.
Initial Effort	Higher. It requires upfront thinking about the data structure and the recursive algorithm.	Lower. You can start typing the song immediately by copying and pasting. This is a classic example of a short-term gain for long-term pain.
Risk of Bugs	Low. Once the core logic is correct, it's correct for all verses. Bugs are centralized in the functions.	High. A typo in one of the copied verses can be difficult to spot and can easily be propagated to other verses during copy-paste operations.

---

Frequently Asked Questions (FAQ)

Why is recursion a good fit for the Food Chain problem?

Recursion excels at solving problems that can be broken down into smaller, self-similar subproblems. Each verse of the song contains the "chase" sequence from the previous verse. This "contains a smaller version of itself" pattern is the textbook definition of a problem well-suited for a recursive solution.

What is an association list (alist) in Common Lisp?

An association list, or alist, is a fundamental Lisp data structure used to store key-value pairs. It is simply a list of cons cells, where the car of each cell is the key and the cdr is the value. Functions like assoc are used to efficiently look up a value by its key. It's a simple yet powerful way to implement a dictionary or map.

How does the code handle the special case of the horse?

The recite-verse function uses a cond statement to check the name of the current animal. If the animal is "horse", it returns a specific, hardcoded final line ("She's dead, of course!") and does not proceed to the recursive recite-chase part, effectively terminating the song's pattern.

Is iteration a viable alternative to recursion here?

Absolutely. You could solve the "chase" sequence using an iterative loop that builds the string from the inside out (starting from the fly and working backwards). However, for many Lisp programmers, the recursive solution more directly models the problem's structure, making the code's intent clearer and more declarative.

What does format nil "..." do differently from format t "..."?

The second argument to format specifies the destination stream. t is the standard output stream (your terminal). nil is a special value that tells format not to print anything, but instead to return the formatted text as a new string. We use format nil to build strings that we can then use or combine elsewhere.

How could this code be made more extensible?

To make it even more data-driven, you could move the special spider line ("...that wriggled...") into the data structure itself, perhaps as a third element in each sublist. The recite-chase function could then be generalized to look for this optional "connector" string, removing the special case logic from the function body.

What are common pitfalls when writing recursive functions in Lisp?

The most common pitfall is failing to define a proper base case. Without a condition to stop the recursion, the function will call itself indefinitely, leading to a stack overflow error. Another issue is ensuring that each recursive call makes progress toward the base case (e.g., by passing a smaller list).

---

Conclusion: Beyond the Song

We've successfully built a robust, maintainable, and elegant solution to the Food Chain song problem using Common Lisp. More importantly, we've explored a powerful programming paradigm: separating data from logic. By defining the song's content in a clean data structure (the alist) and creating generic functions (recite-verse, recite-chase) to process it, we've created a system that is easy to understand, debug, and extend.

The concepts of recursion and data-driven design are not just for academic exercises. They are fundamental tools used in building complex software, from compilers and interpreters to web servers and AI systems. Mastering them is a crucial step in your journey as a developer.

This challenge is a fantastic part of the kodikra.com Common Lisp 5 learning roadmap, designed to solidify your understanding of these core principles. Keep practicing, keep building, and continue to explore the expressive power of Lisp.

Disclaimer: The code in this article is written for modern Common Lisp implementations (like SBCL 2.4.x) and adheres to standard language features. It should be compatible with any ANSI Common Lisp compliant system.

---

Published by Kodikra — Your trusted Common-lisp learning resource.