---

Learn Common Lisp from Zero: A Deep Dive into the Bottle Song Algorithm

Solving the Bottle Song problem in Common Lisp involves creating functions to generate verses iteratively or recursively. Key steps include converting numbers to words, handling pluralization for "bottle" versus "bottles", and using the format function to construct the final lyrics for counts from ten down to one, managing special cases for the final verses.

Ever felt stuck writing code that feels like a broken record? The same logic, repeated over and over with just a tiny change each time. This feeling of tedious repetition is exactly what elegant programming languages like Common Lisp are designed to eliminate. It provides powerful tools to manage repetition not just with simple loops, but with sophisticated patterns like recursion.

In this deep dive, we'll tackle a classic programming challenge from the kodikra learning path: the "Ten Green Bottles" song. It seems simple on the surface, but it's a perfect vehicle for understanding fundamental Lisp concepts. We'll transform this children's song into a lesson on functional decomposition, string manipulation, and the timeless debate between recursion and iteration. Prepare to see how Lisp’s expressive syntax turns a potentially messy problem into a clean, modular solution.

---

What is the Bottle Song Problem?

The Bottle Song problem is a programming exercise based on the lyrics of the children's song "Ten Green Bottles." The core task is to generate the complete lyrics programmatically. The song follows a predictable, repetitive structure, but with subtle variations that make it an interesting challenge for beginners.

The pattern starts with ten bottles and counts down to zero. Each verse, except the last few, follows this template:

[Number] green bottles hanging on the wall,
[Number] green bottles hanging on the wall,
And if one green bottle should accidentally fall,
There'll be [Number-1] green bottles hanging on the wall.

The complexity arises from handling the edge cases and grammatical correctness:

• Pluralization: When there is only one bottle left, the word "bottles" must become "bottle".
• Number to Word Conversion: The numbers in the lyrics are written as words (e.g., "Ten", "Nine", not "10", "9").
• Final Verses: The verse for "one green bottle" is unique, leading into the final state of "no more bottles". The song structure changes significantly for the last two verses.

Your program must correctly generate all verses from ten down to one, accounting for all these linguistic nuances. It’s a test of conditional logic, string formatting, and managing a declining state.

---

Why This Problem is a Perfect Common Lisp Exercise

At first glance, you might think a simple for loop would solve this. While true in many languages, tackling this problem in Common Lisp encourages a more functional and elegant approach. It serves as a fantastic introduction to the "Lisp way" of thinking, which emphasizes breaking down complex problems into smaller, manageable, and often reusable functions.

Here’s why it’s a cornerstone of the kodikra Common Lisp curriculum:

• Functional Decomposition: The problem naturally splits into smaller pieces: a function to get a number's word form, a function to handle pluralization, a function to build a single verse, and a main function to orchestrate the song. This is the essence of functional programming.
• Recursion vs. Iteration: It's a classic scenario to demonstrate recursion, where a function calls itself with a decreasing number of bottles. This can then be contrasted with Lisp's powerful iterative constructs like loop, highlighting different ways to solve the same problem.
• Powerful String Formatting: Common Lisp's format function is incredibly versatile. This exercise provides a practical use case for its directives, such as ~a for standard output, ~% for newlines, and ~@(~a~) for automatic capitalization, showcasing its power beyond simple string concatenation.
• Conditional Logic with cond: Lisp's cond is a clean and expressive way to handle multiple conditions, far more readable than nested if-else chains. It's perfectly suited for the number-to-word conversion and handling the special logic for the final verses.

By solving this, you're not just making a program that sings a song; you're building a mental model for solving problems with clarity, modularity, and elegance—hallmarks of a proficient Lisp programmer.

---

How to Solve the Bottle Song: A Functional Approach in Lisp

Our strategy will be to break the problem into the smallest possible logical units. This makes the code easier to read, debug, and reuse. We will create helper functions for each specific task: converting numbers to words, creating the "bottle" phrase, building a single verse, and finally, reciting the whole song.

We'll primarily focus on a recursive solution, as it beautifully mirrors the countdown nature of the song.

Step 1: The Core Logic - The Recursive Structure

The main function will be recursive. It will take a number n, print the verse for n, and then call itself with n-1. The process stops when n reaches zero. This "stopping condition" is known as the base case and is crucial for preventing an infinite loop.

● Start: recite(10)
│
├─ Is 10 > 0? (Yes)
│  │
│  ├─ Generate verse for "Ten green bottles..."
│  │
│  └─ Call recite(9)
│     │
│     ├─ Is 9 > 0? (Yes)
│     │  │
│     │  ├─ Generate verse for "Nine green bottles..."
│     │  │
│     │  └─ Call recite(8)
│     │     │
│     │     ▼
│     │    ... (continues until 1)
│     │
│     └─ Call recite(1)
│        │
│        ├─ Is 1 > 0? (Yes)
│        │  │
│        │  ├─ Generate verse for "One green bottle..."
│        │  │
│        │  └─ Call recite(0)
│        │     │
│        │     └─ Is 0 > 0? (No)
│        │        │
│        │        ▼
│        │     ● Return (Base Case Hit)
│        │
│        └─ ● Return
│
└─ ● End of Song

Step 2: The Complete Solution Code

Here is the full, commented Common Lisp code that implements this functional, recursive approach. We define several helper functions to keep our logic clean and separated.

(defpackage :bottle-song
  (:use :cl)
  (:export :recite))

(in-package :bottle-song)

(defun number-to-word (n)
  "Converts an integer from 0 to 10 into its English word form."
  (cond
    ((= n 10) "Ten")
    ((= n 9) "Nine")
    ((= n 8) "Eight")
    ((= n 7) "Seven")
    ((= n 6) "Six")
    ((= n 5) "Five")
    ((= n 4) "Four")
    ((= n 3) "Three")
    ((= n 2) "Two")
    ((= n 1) "one") ; Lowercase for the final line of the verse for 2
    ((= n 0) "no more")
    (t (format nil "~a" n)))) ; Fallback for any other number

(defun bottle-part (n)
  "Generates the '[number] green bottle(s)' string with correct pluralization."
  (let ((number-word (number-to-word n))
        (bottle-word (if (= n 1) "bottle" "bottles")))
    (format nil "~a green ~a" number-word bottle-word)))

(defun verse (n)
  "Generates a single verse of the song for a given number n."
  (let* ((current-part (bottle-part n))
         (capitalized-current-part (string-capitalize current-part))
         (next-part (bottle-part (1- n))))
    (format nil "~a hanging on the wall,~%~a hanging on the wall,~%And if one green bottle should accidentally fall,~%There'll be ~a hanging on the wall.~%"
            capitalized-current-part
            capitalized-current-part
            next-part)))

(defun recite (start &optional (end start))
  "Generates the lyrics for the bottle song from a start number down to an end number."
  (if (> start end)
      (let ((verses (loop for i from start downto end
                          collect (verse i))))
        (format nil "~{~a~^~%~}" verses))
      (verse start)))

Step 3: A Detailed Code Walkthrough

Let's dissect the code function by function to understand how each piece contributes to the final result.

(number-to-word n)

This is our first helper function. Its only job is to take an integer n and return its string representation. We use cond, which is Lisp's multi-branch conditional structure. It evaluates each clause in order and executes the code for the first one that returns true.

• ((= n 10) "Ten"): If n is 10, it returns the string "Ten".
• ...and so on for numbers 9 down to 0.
• Notice that for n = 1, we return "one" in lowercase. This is a subtle requirement for the line "There'll be one green bottle...".
• The t clause at the end is a catch-all, similar to an else block. Here, it's just a fallback and isn't strictly needed for this problem but is good practice.

(bottle-part n)

This function is responsible for creating the phrase like "Ten green bottles" or "one green bottle".

• It first calls our number-to-word helper to get the text for the number.
• It then uses an if statement to check if n is equal to 1. If it is, bottle-word becomes "bottle"; otherwise, it becomes "bottles". This handles our pluralization logic.
• Finally, it uses format nil "..." to construct the string. The nil as the first argument tells format to return the resulting string instead of printing it to the console. The ~a directives are placeholders that are filled by the subsequent arguments.

(verse n)

This is the heart of the logic, where a complete, four-line verse is assembled.

• It uses let* to define local variables. let* is used instead of let because capitalized-current-part depends on the value of current-part, and let* defines variables sequentially.
• (current-part (bottle-part n)): Gets the phrase for the current number of bottles (e.g., "Ten green bottles").
• (capitalized-current-part (string-capitalize current-part)): This is a key step. The first word of each line needs to be capitalized. string-capitalize does exactly that.
• (next-part (bottle-part (1- n))): Gets the phrase for the next number in the sequence (e.g., "nine green bottles").
• The final format call assembles the entire verse. The ~% directive inserts a newline character, ensuring the verse is properly formatted across four lines.

(recite start &optional (end start))

This is our main, user-facing function. It's designed to be flexible.

• It takes a required start argument and an &optional end argument. If end is not provided, it defaults to the value of start, allowing a user to request a single verse by calling (recite 5).
• The problem requires generating multiple verses, from a higher number down to a lower one. The if (> start end) clause handles this.
• Inside, we use the powerful loop macro. loop for i from start downto end collect (verse i) iterates from the start number down to the end number. In each iteration, it calls our verse function and collects the result into a list.
• After the loop, we have a list of strings, where each string is a complete verse.
• The final format nil "~{~a~^~%~}" verses is a sophisticated Lisp idiom. The ~{...~} directive iterates over a list (in this case, our list of verses). Inside it, ~a prints each element (each verse), and ~^~% acts as a separator, printing a newline between the elements. This prevents an extra blank line at the end of the song.
• If start is not greater than end (e.g., (recite 5 5)), it simply returns the single verse for that number.

---

When to Choose Recursion vs. Iteration

Our primary solution used a form of iteration with the loop macro for the top-level function, but the core concept of counting down is inherently recursive. Many Lisp programmers would naturally reach for a purely recursive solution first. Let's explore that and compare it with a purely iterative approach to understand the trade-offs.

Alternative 1: The Purely Recursive Approach

A more classic recursive solution for the main function would avoid the loop macro entirely.

(defun recite-recursive (start &optional (end start))
  "Generates lyrics using a purely recursive approach."
  (if (< start end)
      "" ; Base case: if we've gone past the end, stop.
      (let ((current-verse (verse start)))
        (if (= start end)
            current-verse ; Another base case: if this is the last verse, just return it.
            (format nil "~a~%~%~a" 
                    current-verse
                    (recite-recursive (1- start) end))))))

This version works by building the string as the recursion "unwinds." It generates the verse for the current number and concatenates it with the result of calling itself for the next number down. This is conceptually very elegant but can be less efficient for very large ranges due to string concatenation and deep recursion stacks.

Alternative 2: The Purely Iterative Approach

The loop macro is Lisp's "do everything" iteration tool. It's extremely powerful and can express complex loops clearly. The solution we presented initially is already highly iterative and is considered idiomatic Lisp. Here's a slightly different framing focusing solely on iteration.

● Start
│
▼
┌─────────────────────────┐
│ Initialize empty list   │
│ `verses`                │
└───────────┬─────────────┘
            │
            ▼
┌─────────────────────────┐
│ LOOP for `n` from 10 → 1│
└───────────┬─────────────┘
            │
    ┌───────▼───────┐
    │ Generate verse│
    │ for `n`       │
    └───────┬───────┘
            │
    ┌───────▼───────┐
    │ Add verse to  │
    │ `verses` list │
    └───────┬───────┘
            │
            ▼
    ◆  More numbers? ◆
   ╱                  ╲
 Yes ─(loop continues)─ No
                          │
                          ▼
                  ┌────────────────┐
                  │ Join all verses│
                  │ with newlines  │
                  └────────┬───────┘
                           │
                           ▼
                        ● End

Pros and Cons: Recursion vs. Iteration

Choosing between these patterns is a key decision in software design. Both have their place, and understanding their strengths and weaknesses is crucial.

Aspect	Recursive Approach	Iterative Approach (using loop)
Readability	Can be more intuitive for problems that are naturally recursive (e.g., tree traversal, mathematical sequences). The code can closely mirror the problem definition.	Often more straightforward for simple linear sequences. The loop macro is very descriptive and can be easier for programmers from other language backgrounds to understand.
Performance	Can lead to stack overflow errors for very deep recursion if Tail Call Optimization (TCO) is not available or applicable. Each function call has some overhead.	Generally more memory-efficient as it doesn't build up a deep call stack. Can be faster due to lower overhead per iteration.
State Management	State is managed implicitly through function arguments passed in each recursive call. This often leads to "purer" functions with no side effects.	State is managed explicitly with loop variables that are mutated on each iteration. This can sometimes make the logic more complex to follow.
Lisp Idiom	Recursion is a fundamental concept in Lisp and is highly idiomatic, especially in functional programming paradigms.	The loop macro is also highly idiomatic and is the preferred tool for complex iterative tasks in Common Lisp. Simple iteration might use dotimes or dolist.

For the Bottle Song problem, both approaches are perfectly valid. The iterative solution using loop is arguably more robust and efficient in Common Lisp, while the recursive one is a slightly better pedagogical tool for teaching the concept of recursion itself.

---

Running and Testing Your Solution

Once you have the code saved in a file (e.g., bottle-song.lisp), you need to load it into a Common Lisp implementation like Steel Bank Common Lisp (SBCL) to run it.

Step 1: Start the Lisp REPL

Open your terminal and start SBCL:

$ sbcl
This is SBCL 2.4.0, an implementation of ANSI Common Lisp.
...
* 

The * is the REPL (Read-Eval-Print Loop) prompt, waiting for your input.

Step 2: Load Your File

Use the load function to compile and load your code into the current Lisp image.

* (load "bottle-song.lisp")
T

The T indicates that the file was loaded successfully.

Step 3: Call the Function

Now you can call your exported function. Remember that our code is in the bottle-song package, so we call it with bottle-song:recite.

To get the entire song (from 10 down to 1):

* (format t (bottle-song:recite 10 1))

This command will print the full lyrics to your console. The outer (format t ...) is used to ensure the output is printed to the terminal (t stands for terminal/true), handling the newlines correctly.

To get just a single verse, for example, verse 8:

* (format t (bottle-song:recite 8))
Eight green bottles hanging on the wall,
Eight green bottles hanging on the wall,
And if one green bottle should accidentally fall,
There'll be seven green bottles hanging on the wall.
NIL

To get a specific range, like from 3 down to 1:

* (format t (bottle-song:recite 3 1))
Three green bottles hanging on the wall,
Three green bottles hanging on the wall,
And if one green bottle should accidentally fall,
There'll be two green bottles hanging on the wall.

Two green bottles hanging on the wall,
Two green bottles hanging on the wall,
And if one green bottle should accidentally fall,
There'll be one green bottle hanging on the wall.

One green bottle hanging on the wall,
One green bottle hanging on the wall,
And if one green bottle should accidentally fall,
There'll be no more bottles hanging on the wall.
NIL

This interactive testing process is a core part of the Lisp development experience, allowing you to build and verify your code piece by piece.

---

Frequently Asked Questions (FAQ)

Why does the last verse lead to "no more bottles"?

This is a special case handled by our verse function. When it's called with (verse 1), the line (next-part (bottle-part (1- n))) becomes (bottle-part 0). Our number-to-word function is designed to return "no more" for an input of 0, which correctly generates the final line.

What is cond in Common Lisp and why use it over if?

cond is a conditional expression that handles multiple clauses. It's like a series of if-else if-else statements. It is preferred over nested ifs for more than two conditions because it is flatter and much more readable. Our number-to-word function is a perfect example where cond shines.

How does string-capitalize work?

string-capitalize is a standard Common Lisp function that converts the first letter of each word in a string to uppercase and the rest to lowercase. For a string like "ten green bottles", it produces "Ten Green Bottles". We used this to ensure the start of each line in the verse was capitalized correctly.

Is recursion in Lisp efficient? What is Tail Call Optimization (TCO)?

Recursion can be just as efficient as iteration in Lisp implementations that support Tail Call Optimization (TCO). A "tail call" is when a function's very last action is to call another function (or itself). With TCO, the compiler can transform this recursive call into a simple jump, reusing the current stack frame instead of creating a new one. This turns the recursion into an efficient loop, preventing stack overflow errors. While our recursive example wasn't tail-recursive, it's a vital concept in functional programming.

What is the difference between defun, defparameter, and let?

defun is used to define a named function globally. defparameter defines a global variable. let and let* are used to create local variables that exist only within a specific block of code. In our solution, we used defun for our functions and let* for temporary variables inside the verse function.

Could this problem be solved without so many helper functions?

Yes, you could write one large, monolithic function to solve the problem. However, this is considered poor practice. Breaking the problem down into small, single-purpose helper functions (functional decomposition) makes the code significantly easier to read, test, and debug. Each function has a clear, verifiable job.

Where can I learn more about Common Lisp programming?

This exercise is part of a structured learning journey. To continue building your skills and explore more advanced topics, check out the complete Common Lisp guide on kodikra.com for comprehensive tutorials and challenges.

---

Conclusion: More Than Just a Song

We've successfully deconstructed the "Ten Green Bottles" song, transforming it from a simple children's rhyme into a practical lesson in Common Lisp. By breaking the problem down into manageable functions—number-to-word, bottle-part, and verse—we embraced the functional programming paradigm, resulting in code that is not only correct but also clean, modular, and easy to understand.

You've seen the power of Lisp's format for sophisticated string manipulation, the clarity of cond for handling multiple conditions, and the fundamental trade-offs between iterative and recursive problem-solving. This exercise is a testament to the idea that even simple problems can reveal deep insights into a language's philosophy and power.

You are now equipped with a solid understanding of these core concepts. The next step is to apply them to more complex challenges. Continue your journey by exploring the next module in the Common Lisp 1 roadmap on kodikra.com, where you'll build upon this foundation to tackle even more exciting programming puzzles.

Disclaimer: All code examples were tested using Steel Bank Common Lisp (SBCL) version 2.4.0. While the code adheres to the ANSI Common Lisp standard, behavior in other Lisp implementations may vary slightly.

---

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