---

All Your Base: The Complete Guide to Number System Conversion in Common Lisp

To convert a number from an input base to an output base in Common Lisp, the most robust method involves a two-step process. First, convert the source number (represented as a list of digits) into its universal base-10 (decimal) equivalent. Then, convert that decimal number into the target base.

---

The Universal Translator for Numbers

Imagine you're a mathematics professor. Your first week on the job was a breeze, but suddenly, in the second week, every student's answer on their assignments is wrong. Frustration mounts until you have a flash of insight: the logic is sound, the calculations are perfect, but the answers are all in base-2 (binary)!

You realize with a mix of horror and amusement that each week, your students might be using a different number base. To save your sanity and grade their work efficiently, you need a universal translator—a tool that can take a number in any base and convert it to any other base. This isn't just an academic puzzle; it's a foundational concept in computer science.

This guide will walk you through building that very tool in Common Lisp. We'll deconstruct the logic of positional notation and implement an elegant, functional solution from zero to hero, transforming you into a master of numerical systems. You'll learn not just the "how," but the critical "why" behind number base conversion.

---

What Is Number Base Conversion?

At its heart, number base conversion is the process of representing the same quantity using a different set of symbols and positional rules. The system we use daily is base-10 (decimal), which utilizes ten digits (0-9). The position of a digit determines its value, which is a power of 10.

For example, the number 42 in base-10 really means:

(4 * 10¹) + (2 * 10⁰) = 40 + 2 = 42

Computers, however, operate on a much simpler system: base-2 (binary). They only use two digits: 0 and 1. The same quantity, 42, would be represented in binary as 101010, which means:

(1 * 2⁵) + (0 * 2⁴) + (1 * 2³) + (0 * 2²) + (1 * 2¹) + (0 * 2⁰)

= 32 + 0 + 8 + 0 + 2 + 0 = 42

Our task is to create a function, rebase, that can take a sequence of digits like (1 0 1 0 1 0), its input base (2), and a desired output base (say, 10), and produce the new sequence of digits: (4 2).

---

Why Is This a Cornerstone of Programming?

Understanding base conversion isn't just for mathematicians. It's a fundamental skill for any serious programmer, especially in systems programming, data science, and web development. Different bases are used in specific contexts for efficiency and readability.

• Binary (Base-2): The native language of all digital computers. It represents the on/off states of transistors.
• Octal (Base-8): An older system sometimes used in file permissions on Unix-like systems (e.g., chmod 755).
• Decimal (Base-10): The human-readable system we use every day.
• Hexadecimal (Base-16): Uses digits 0-9 and letters A-F. It's a compact way to represent binary data. A single hex digit represents four binary digits (a nibble). You see it everywhere:
  • CSS color codes (e.g., #FF5733)
  • Memory addresses (e.g., 0x7FFF...)
  • Character encodings (e.g., U+0041 for 'A')

Building a converter yourself, as required by the kodikra.com learning path, forces you to grasp the underlying mechanics of how data is represented, a skill that pays dividends throughout your programming career.

---

How to Implement the Conversion Logic: The Two-Step Pivot

The most reliable way to convert from any base A to any base B is to use base-10 as a universal intermediate format. The process is broken into two distinct, manageable steps:

1. Step 1: Convert from the Input Base to Base-10 (Decimal).
2. Step 2: Convert from Base-10 (Decimal) to the Target Output Base.

This pivot strategy simplifies the problem immensely. Instead of writing complex logic for every possible base-to-base combination (binary to hex, base-3 to base-7, etc.), we only need two algorithms.

Step 1: From Any Base to Decimal (list->num)

To convert a number represented by a list of digits into its decimal value, we use the polynomial expansion formula. We iterate through the digits from left to right, continuously multiplying our accumulated total by the base and adding the next digit.

Consider the list (1 0 1) in base-2:

• Start with an accumulator of 0.
• Process first digit 1: (0 * 2) + 1 = 1. Accumulator is now 1.
• Process second digit 0: (1 * 2) + 0 = 2. Accumulator is now 2.
• Process third digit 1: (2 * 2) + 1 = 5. Accumulator is now 5.

The final decimal value is 5. This iterative process is a perfect use case for the reduce function in functional programming.

● Start with list [1, 0, 1] and base 2
│
▼
┌──────────────────┐
│ Accumulator = 0  │
└─────────┬────────┘
          │
          ▼
┌───────────────────────────────┐
│ Process '1': acc = (0 * 2) + 1 │
│ Result: acc = 1               │
└─────────┬─────────────────────┘
          │
          ▼
┌───────────────────────────────┐
│ Process '0': acc = (1 * 2) + 0 │
│ Result: acc = 2               │
└─────────┬─────────────────────┘
          │
          ▼
┌───────────────────────────────┐
│ Process '1': acc = (2 * 2) + 1 │
│ Result: acc = 5               │
└─────────┬─────────────────────┘
          │
          ▼
● End with decimal value 5

Step 2: From Decimal to Any Base (num->list)

To convert a decimal number to another base, we use repeated division and modulo arithmetic. We repeatedly divide the number by the target base and record the remainder. The sequence of remainders, when read in reverse, gives us the digits in the new base.

Let's convert the decimal number 42 to base-2:

• 42 / 2 = 21 with a remainder of 0.
• 21 / 2 = 10 with a remainder of 1.
• 10 / 2 = 5 with a remainder of 0.
• 5 / 2 = 2 with a remainder of 1.
• 2 / 2 = 1 with a remainder of 0.
• 1 / 2 = 0 with a remainder of 1.

The division stops when the quotient becomes 0. We collect the remainders (0 1 0 1 0 1) and reverse them to get the final result: (1 0 1 0 1 0).

● Start with decimal 42 and target base 2
│
▼
┌─────────────────────────┐
│ 42 mod 2 = 0 │ Remainder: [0]
│ 42 / 2 = 21  │
└───────────┬─────────────┘
            │
            ▼
┌─────────────────────────┐
│ 21 mod 2 = 1 │ Remainder: [0, 1]
│ 21 / 2 = 10  │
└───────────┬─────────────┘
            │
            ▼
┌─────────────────────────┐
│ 10 mod 2 = 0 │ Remainder: [0, 1, 0]
│ 10 / 2 = 5   │
└───────────┬─────────────┘
            │
            ▼
┌─────────────────────────┐
│  5 mod 2 = 1 │ Remainder: [0, 1, 0, 1]
│  5 / 2 = 2   │
└───────────┬─────────────┘
            │
            ▼
┌─────────────────────────┐
│  2 mod 2 = 0 │ Remainder: [0, 1, 0, 1, 0]
│  2 / 2 = 1   │
└───────────┬─────────────┘
            │
            ▼
┌─────────────────────────┐
│  1 mod 2 = 1 │ Remainder: [0, 1, 0, 1, 0, 1]
│  1 / 2 = 0   │
└───────────┬─────────────┘
            │
            ▼
┌──────────────────────────────────┐
│ Reverse remainders: [1, 0, 1, 0, 1, 0] │
└─────────────────┬────────────────┘
                  │
                  ▼
● End with list (1 0 1 0 1 0)

---

Where This is Implemented: A Common Lisp Code Walkthrough

Now, let's analyze the complete Common Lisp solution provided in the kodikra.com module. We'll break it down function by function to understand how it masterfully implements the two-step pivot strategy.

The Complete Code

(in-package :cl-user)
(defpackage :all-your-base
  (:use :common-lisp)
  (:export :rebase))
(in-package :all-your-base)

(defun rebase (list-digits in-base out-base)
  "Converts a number, represented as a list of digits, from in-base to out-base."
  (when (and (< 1 in-base)
             (< 1 out-base)
             (every (lambda (x) (< -1 x in-base)) list-digits))
    (if (or (null list-digits) (every #'zerop list-digits))
        '(0)
        (num->list (list->num list-digits in-base) out-base))))

(defun list->num (lst base)
  "Converts a list of digits in a given base to its decimal (base-10) representation."
  (reduce (lambda (acc digit) (+ (* acc base) digit))
          lst
          :initial-value 0))

(defun num->list (num base)
  "Converts a decimal (base-10) number to a list of digits in a given base."
  (if (zerop num)
      nil
      (let ((result (loop for n = num then (floor n base)
                          until (zerop n)
                          collect (mod n base))))
        (if (null result) '(0) (nreverse result)))))

Package and Namespace Setup

The code begins with standard Common Lisp boilerplate for package management.

• (in-package :cl-user): Ensures we start in the default user package.
• (defpackage :all-your-base ...): Defines a new package named all-your-base. This prevents our function names from clashing with other code.
• (:export :rebase): This makes the rebase function public, so it can be called from outside this package.
• (in-package :all-your-base): Switches the current working environment into our newly created package.

The Main Function: rebase

This is the public-facing function that orchestrates the entire conversion process.

(defun rebase (list-digits in-base out-base)
  ...)

It accepts three arguments: list-digits (the number as a list), in-base (the input base), and out-base (the target base).

Input Validation with when

The first thing a robust function does is validate its inputs. The when macro is used here as a conditional guard. The code inside the when block only executes if all conditions are true.

(when (and (< 1 in-base)
             (< 1 out-base)
             (every (lambda (x) (< -1 x in-base)) list-digits))
  ...)

• (< 1 in-base) and (< 1 out-base): Both the input and output bases must be greater than 1. A base of 1 or 0 is mathematically meaningless for positional notation.
• (every (lambda (x) (< -1 x in-base)) list-digits): This is a crucial check. The every function tests if a predicate is true for every element in a list.
  • The lambda function checks if a digit x is valid for the given in-base.
  • A digit must be non-negative (< -1 x is a clever way to say x >= 0) and strictly less than its base (x < in-base). For example, in base-10, digits can only be 0-9.

If any of these conditions fail, the when block is skipped, and the function implicitly returns NIL, which is the Lisp way of indicating failure or falsehood.

Handling Edge Cases and Orchestration

(if (or (null list-digits) (every #'zerop list-digits))
    '(0)
    (num->list (list->num list-digits in-base) out-base))

Inside the validation block, an if statement handles edge cases:

• (null list-digits): Checks if the input list is empty.
• (every #'zerop list-digits): Checks if the input list contains only zeros, like (0) or (0 0 0).

In either of these cases, the number is effectively zero, so the function correctly returns a list containing a single zero: '(0).

If the input is valid and non-zero, the magic happens: (num->list (list->num list-digits in-base) out-base). This is a beautiful example of functional composition. The output of the inner function list->num becomes the input for the outer function num->list, perfectly executing our two-step pivot strategy.

Helper Function: list->num

This function implements Step 1: converting a list of digits to its decimal representation.

(defun list->num (lst base)
  (reduce (lambda (acc digit) (+ (* acc base) digit))
          lst
          :initial-value 0))

The reduce function is the star here. It iterates over a list, applying a function to accumulate a single result.

• (lambda (acc digit) (+ (* acc base) digit)): This is the core logic, as explained in our algorithm breakdown. acc is the accumulated value so far, and digit is the current element from the list.
• lst: The list of digits to process.
• :initial-value 0: We tell reduce to start the accumulator acc at 0.

Helper Function: num->list

This function implements Step 2: converting a decimal number to a list of digits in the target base.

(defun num->list (num base)
  (if (zerop num)
      nil
      (let ((result (loop for n = num then (floor n base)
                          until (zerop n)
                          collect (mod n base))))
        (if (null result) '(0) (nreverse result)))))

This function uses the powerful loop macro, one of Common Lisp's most flexible features.

• (if (zerop num) nil ...): A guard clause. If the number is already zero, it returns NIL initially, which is handled later.
• (let ((result ...))): We define a local variable result to store the list of digits.
• loop for n = num then (floor n base): This sets up the loop variable n. It starts with the value of num. In each subsequent iteration (then), n becomes the result of integer division (floor) by the base.
• until (zerop n): The loop continues until n becomes 0.
• collect (mod n base): In each iteration, this calculates the remainder (mod) of n divided by the base and collects it into a list.

The list collected by loop will have the digits in reverse order. Therefore, (nreverse result) is called to put them in the correct order. nreverse is a destructive version of reverse, which is slightly more efficient as it reuses the existing list structure.

---

Who Needs to Master This? (And Potential Pitfalls)

Mastering number representation is non-negotiable for developers working close to the hardware or dealing with raw data formats. This includes embedded systems engineers, game engine developers, compiler designers, and anyone working on network protocols.

However, even high-level developers benefit from this knowledge. It demystifies common data types and encodings, leading to a more profound understanding of the tools you use daily. While the implementation seems straightforward, there are common risks and considerations.

Pros of This Approach	Cons / Risks
Universality: The base-10 pivot method works for any valid base conversion without needing special case logic.	Intermediate Value Overflow: For very large numbers in high input bases, the intermediate decimal value could exceed the maximum integer size of the system.
Clarity & Maintainability: Separating the logic into two distinct functions (list->num and num->list) makes the code easier to read, test, and debug.	Input Validation is Critical: Failing to validate inputs (bases < 2, digits >= base) will lead to incorrect results or errors. The provided solution handles this well.
Efficiency: The use of idiomatic Lisp features like reduce and loop results in efficient, compiled code.	Off-by-One Errors: Logic involving loops, especially with division and modulo, can be prone to off-by-one errors if the termination condition (e.g., `until (zerop n)`) isn't perfect.
Educational Value: Implementing this from scratch solidifies your understanding of positional notation far better than just using a built-in library function.	Handling of Zero: The number zero is an edge case that requires explicit handling (e.g., an input of `(0)` or `(0 0)` should result in `(0)`).

Running the Code from the Terminal

To test this code, you can save it as a file (e.g., base-converter.lisp) and load it into a Common Lisp implementation like SBCL (Steel Bank Common Lisp).

# Start the SBCL REPL
$ sbcl

# Load the file
* (load "base-converter.lisp")

# Call the function from the correct package
* (all-your-base:rebase '(1 0 1 0 1 0) 2 10)
(4 2)

* (all-your-base:rebase '(4 2) 10 2)
(1 0 1 0 1 0)

* (all-your-base:rebase '(1 1 2 0) 3 10)
(4 2)

# Example of invalid input returning NIL
* (all-your-base:rebase '(1 2 3) 3 10)
NIL

---

Frequently Asked Questions (FAQ)

1. Why is pivoting through base-10 necessary? Can't I convert directly?

While direct conversion algorithms exist for specific pairs (like base-2 to base-16), they are specialized. The base-10 pivot method is a universal algorithm that works for converting from any base X to any base Y. It simplifies the problem into two well-understood, general-purpose steps, making the code more robust and easier to reason about.

2. How does the solution handle invalid inputs, like a digit being too large for its base?

The main rebase function has a comprehensive validation block using when and and. The condition (every (lambda (x) (< -1 x in-base)) list-digits) is key. It iterates through every digit and ensures it is both non-negative and strictly less than the input base. If any digit fails this test, the entire when block is skipped, and the function returns NIL.

3. What's the purpose of `defpackage` and `in-package`?

In Common Lisp, packages are used for namespace management. defpackage creates a new namespace to hold your functions and variables, preventing name collisions with other libraries or Lisp's built-in functions. :export specifies which symbols (functions, etc.) from your package should be publicly accessible. in-package switches the current working context into that package so you can define your functions within it.

4. Could the `list->num` function be written with `loop` instead of `reduce`?

Absolutely. While reduce is arguably more concise and functional, a loop-based version is equally valid and might be more readable for those less familiar with functional programming constructs. It would look something like this:

(defun list->num-loop (lst base)
  (loop for digit in lst
        with acc = 0
        do (setf acc (+ (* acc base) digit))
        finally (return acc)))

5. Can this implementation handle bases larger than 10?

Yes. The code works with numbers, not characters. So for hexadecimal (base-16), you would represent the number as a list of its integer digit values. For example, the hex number "1A" would be passed as the list (1 10). The function would correctly process this and convert it to its decimal equivalent, 26.

6. Why does the code return `'(0)` for an empty or all-zero input list?

This is a convention for representing the number zero. An empty list of digits, or a list containing one or more zeros, both represent the quantity 0. The standard representation for this in the problem's context is a list containing a single zero, (0). The code explicitly checks for these cases to ensure the output is consistent.

---

Conclusion: More Than Just Numbers

You've now dissected the logic and implementation of a universal number base converter in Common Lisp. This journey through positional notation, from binary to decimal and beyond, is more than just a mathematical exercise. It's a fundamental lesson in data representation and algorithmic thinking.

By building this tool from first principles, you've implemented a two-step pivot strategy that is both elegant and robust. You've seen how powerful functional constructs like reduce and the imperative flexibility of the loop macro can be used to solve complex problems cleanly. This foundational knowledge will serve you well as you tackle more advanced topics in computer science.

To continue your journey, explore the other challenges in the kodikra.com Common Lisp learning path or dive deeper into the language with our complete Common Lisp guide.

Disclaimer: The code in this article is based on modern Common Lisp standards. The behavior of specific functions may vary slightly between different implementations like SBCL, CCL, or ABCL. Always consult your implementation's documentation for specifics.

---

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