Roman Numerals in Common-lisp: Complete Solution & Deep Dive Guide

a close up of a sign with a lot of dots on it

From Arabic to Roman: The Complete Guide to Roman Numerals in Common Lisp

Converting Arabic numbers to Roman numerals in Common Lisp is a classic programming challenge that elegantly showcases the language's power. This can be achieved with a stunningly simple built-in function or by crafting a custom algorithm, offering a perfect lesson in both utility and foundational logic for numbers up to 3,999.

You've probably seen them at the end of movie credits—cryptic letters like MCMLXXXVIII marking the year of production. They feel like a code from a bygone era. What if you could not only crack that code but also write a program to generate it yourself? In a language as powerful and expressive as Common Lisp, this task transforms from a historical curiosity into a fascinating programming exercise. This guide will walk you through everything, from a one-line solution that feels like magic to building the conversion logic from the ground up, turning you into a master of numerical translation.

What Are Roman Numerals? The Ancient System of Counting

Before the widespread adoption of the Arabic numeral system (0-9) that we use today, the Roman Empire utilized a method of counting based on letters of the Latin alphabet. This system, while not ideal for complex arithmetic, was incredibly durable and is still used for stylistic purposes on clock faces, in book chapter headings, and for regnal numbers of monarchs.

The system is built upon seven core symbols, each representing a specific value:

I - 1
V - 5
X - 10
L - 50
C - 100
D - 500
M - 1000

The Two Core Principles of Roman Numerals

To form numbers, these symbols are combined using two fundamental rules. Understanding these is the key to building a conversion algorithm.

1. The Additive Principle: When a symbol of lesser or equal value is placed after a symbol of greater value, their values are added. This is the most straightforward rule.

II is 1 + 1 = 2
VI is 5 + 1 = 6
LXX is 50 + 10 + 10 = 70
MCC is 1000 + 100 + 100 = 1200

2. The Subtractive Principle: This is the clever trick that makes the system more compact. When a symbol of lesser value is placed before a symbol of greater value, the lesser value is subtracted from the greater one. This rule only applies to specific pairings:

IV is 5 - 1 = 4 (instead of IIII)
IX is 10 - 1 = 9 (instead of VIIII)
XL is 50 - 10 = 40 (instead of XXXX)
XC is 100 - 10 = 90 (instead of LXXXX)
CD is 500 - 100 = 400 (instead of CCCC)
CM is 1000 - 100 = 900 (instead of DCCCC)

For the scope of the kodikra learning path, we focus on traditional Roman numerals, which effectively limits our range to numbers from 1 to 3,999 (MMMCMXCIX). This is because there was no standard, universally accepted symbol for 5,000 or higher in the classical system.

Why Use Common Lisp for This Task?

Common Lisp might seem like an esoteric choice to newcomers, but it possesses unique features that make it exceptionally well-suited for problems like Roman numeral conversion. It's not just about getting the right answer; it's about how elegantly and interactively you can arrive at it.

Expressiveness and a Powerful Standard Library

Common Lisp is renowned for its expressive syntax and a "batteries-included" standard library that has been refined over decades. As you'll see shortly, the language includes a built-in formatting tool so powerful it can solve this entire problem in a single line of code. This speaks to the language's design philosophy: provide powerful, general-purpose tools to the developer.

REPL-Driven Development

Development in Common Lisp is typically done through a REPL (Read-Eval-Print Loop). This interactive environment allows you to define functions, test them with data, and redefine them on the fly without restarting your application. For developing an algorithm like a Roman numeral converter, this is invaluable. You can test your logic for `4`, then `9`, then `49` instantly, catching edge cases and refining your code in real-time.

A Natural Fit for Symbolic Computation

Lisp, which stands for "List Processing," was designed from the ground up to manipulate symbols. The task of converting a number (a numeric concept) into a string of letters (a symbolic representation) is a perfect example of symbolic computation, which is Lisp's home turf.

How to Convert Numbers: The Algorithmic Logic

Before we write a single line of Lisp, we must understand the conversion algorithm. The most intuitive method is a "greedy" approach. You start with your Arabic number and the largest possible Roman numeral value, and you "greedily" take as many as you can before moving to the next smaller value.

Let's take the number 1994 as an example:

Start with 1994. The largest value is 1000 (M). It fits once. Result: "M". Remainder: 994.
Now consider 994. The next largest value is 900 (CM). It fits once. Result: "MCM". Remainder: 94.
Now consider 94. The next largest value is 90 (XC). It fits once. Result: "MCMXC". Remainder: 4.
Now consider 4. The next largest value is 4 (IV). It fits once. Result: "MCMXCIV". Remainder: 0.
The remainder is 0, so we are done.

This process highlights why the subtractive pairs (900, 90, 4, etc.) are crucial. By treating them as indivisible tokens, the greedy algorithm works perfectly. The key is to have a map of values sorted from largest to smallest.

ASCII Art Diagram: The Greedy Conversion Flow

This diagram illustrates the logical flow of our "from-scratch" algorithm.

    ● Start (Input: arabicNumber)
    │
    ▼
  ┌───────────────────────────┐
  │ Initialize empty resultString │
  └────────────┬──────────────┘
               │
               ▼
  ┌───────────────────────────┐
  │ For each (value, symbol)  │
  │ in RomanMap (descending)  │
  └────────────┬──────────────┘
               │
    ┌──────────┴──────────┐
    │ While arabicNumber  │
    │ is >= current value │
    └──────────┬──────────┘
               │
               ├─ Yes ─→ ┌────────────────────┐
               │         │ Append symbol to   │
               │         │ resultString       │
               │         └────────┬───────────┘
               │                  │
               │                  ▼
               │         ┌────────────────────┐
               │         │ Subtract value from│
               │         │ arabicNumber       │
               │         └────────┬───────────┘
               │                  │
               └──────────<───────┘
               No
               │
               ▼
  ┌───────────────────────────┐
  │ Move to next map entry    │
  └────────────┬──────────────┘
               │
               ▼
    ◆ arabicNumber is 0?
   ╱           ╲
  Yes           No
  │              │
  ▼              ▼
[Return result] Loop
  │
  ▼
 ● End

Where the Code is Implemented: Two Paths in Common Lisp

Now we'll translate this logic into Common Lisp code. We will explore two distinct methods: the incredibly concise built-in solution and a more verbose, educational implementation built from scratch.

Method 1: The Elegant, Idiomatic Lisp Way

Common Lisp's format function is a masterpiece of text formatting, far more powerful than the printf-style functions in many other languages. It includes a directive specifically for converting numbers to Roman numerals.

Here is the complete solution, as provided in the kodikra module:

(defpackage :roman-numerals
  (:use :cl)
  (:export :romanize))

(in-package :roman-numerals)

(defun romanize (number)
  "Converts a positive integer up to 3999 to a Roman numeral string."
  (when (and (integerp number) (> number 0) (< number 4000))
    (format nil "~@R" number)))

Code Walkthrough

(defpackage :roman-numerals ...): This defines a new package named roman-numerals. Packages in Lisp are like namespaces; they prevent name collisions between different parts of a program. We :use the standard Common Lisp package (:cl) and :export our function romanize so it can be used by other packages.
(in-package :roman-numerals): This switches the current working environment into our newly defined package.
(defun romanize (number)): This defines a function named romanize that accepts one argument, number.
(when (and (integerp number) ...)): This is a guard clause. It ensures the code only runs if the input is an integer greater than 0 and less than 4000. It's good practice to validate input.
(format nil "~@R" number): This is the core of the solution.
- format: The master text formatting function.
- nil: The first argument to format is the destination. nil tells it not to print to the console but to return the formatted text as a new string.
- "~@R": This is a format control string. ~R is the directive for radix formatting. By itself, it would print a number as English words (e.g., 27 as "twenty-seven"). The @ modifier changes its behavior to print in Roman numerals.
- number: The value to be formatted.

This solution is a testament to Common Lisp's rich heritage. It's concise, readable, and relies on a well-defined standard, making it both powerful and portable across Lisp implementations.

Method 2: Building the Converter from Scratch

While the `format` solution is brilliant, it doesn't teach us the underlying algorithm. To truly understand the conversion process, let's build it ourselves. We'll implement the greedy algorithm discussed earlier.

First, we need a data structure to map Arabic values to Roman symbols. An association list (alist) is a perfect fit. It's a list of key-value pairs (in our case, `(value . symbol)`).

;; Define the mapping from values to symbols, including subtractive pairs.
;; The list MUST be sorted in descending order of value.
(defparameter *roman-map*
  '((1000 . "M") (900 . "CM") (500 . "D") (400 . "CD") (100 . "C")
    (90 . "XC") (50 . "L") (40 . "XL") (10 . "X") (9 . "IX")
    (5 . "V") (4 . "IV") (1 . "I")))

Now, we can write a recursive function that works through this map.

(defun romanize-manual (number)
  "Converts a positive integer to a Roman numeral string using a manual algorithm."
  (when (and (integerp number) (> number 0) (< number 4000))
    (labels ((convert (n map-tail result)
               (if (or (null map-tail) (zerop n))
                   result
                   (let* ((entry (first map-tail))
                          (value (car entry))
                          (symbol (cdr entry)))
                     (if (>= n value)
                         (convert (- n value) map-tail (concatenate 'string result symbol))
                         (convert n (rest map-tail) result))))))
      (convert number *roman-map* ""))))

Code Walkthrough (Manual Version)

(defparameter *roman-map* ...): Defines a global special variable holding our conversion map. The asterisks (earmuffs) are a convention for special variables.
(defun romanize-manual (number)): Defines our main function.
(labels ((convert ...))): labels defines a local helper function named convert that can call itself recursively. This is often preferred over a global helper function. The function takes three arguments: the remaining number n, the rest of the map to process map-tail, and the accumulated result string.
(if (or (null map-tail) (zerop n)) result ...): This is our base case. If we've run out of symbols in our map or the number has been reduced to zero, we are done and return the accumulated result.
(let* ((entry (first map-tail)) ...)): We get the current map entry (e.g., (1000 . "M")) and use let* to bind its value and symbol to local variables.
(if (>= n value) ...): This is the core greedy logic. We check if the current number n is large enough to accommodate the current symbol's value.
- If Yes: We make a recursive call to convert. We subtract the value from n, pass the same map-tail (so we can use the same symbol again, e.g., for 3000 -> "MMM"), and append the symbol to our result string using concatenate.
- If No: The current symbol's value is too large. We make a recursive call, but this time we keep n and result the same and move on to the (rest map-tail), which is the next smaller symbol in our map.
(convert number *roman-map* ""): This is the initial call that kicks off the recursion, starting with the full number, the full map, and an empty string.

ASCII Art Diagram: Subtractive vs. Additive Choice

This diagram shows the micro-decision the algorithm makes when it encounters a number like 9. By processing `(9 . "IX")` before `(5 . "V")`, it makes the correct "subtractive" choice.

    ● Input: 9
    │
    ▼
  ┌────────────────────────┐
  │ Check map: (1000."M")? │
  └────────────┬───────────┘
               │ No (9 < 1000)
               ▼
             ...
               ▼
  ┌────────────────────────┐
  │ Check map: (10."X")?   │
  └────────────┬───────────┘
               │ No (9 < 10)
               ▼
  ┌────────────────────────┐
  │ Check map: (9."IX")?   │
  └────────────┬───────────┘
               │ Yes (9 >= 9)
               ├─→ ┌───────────────────┐
               │   │ Append "IX"       │
               │   │ Remainder = 9 - 9 │
               │   └─────────┬─────────┘
               │             │
               │             ▼
               │   ● Remainder is 0, End
               │
               └─ (Path not taken)
                    ▼
                  ┌────────────────────┐
                  │ Check map: (5."V")?│
                  └────────────────────┘

When to Choose Which Method? A Comparative Analysis

Both methods achieve the same result, but they serve different purposes. Choosing between them depends on your goals: production code, learning, or portability.

Feature	Method 1: `format "~@R"`	Method 2: Manual Algorithm
Conciseness	Extremely high. A single, expressive line of code.	More verbose, requiring a data structure and recursive logic.
Readability	High for experienced Lisp programmers. Can seem like "magic" to beginners.	High for programmers of any language, as the algorithm is explicit.
Performance	Likely faster. It's a standard library feature, often implemented in highly optimized, low-level code.	Very good for the given constraints (numbers up to 3999), but involves more Lisp-level operations (string concatenation, recursion).
Educational Value	Demonstrates the power of the standard library but hides the "how."	Excellent. It forces you to understand and implement the core conversion logic.
Portability	The code is portable across any ANSI Common Lisp implementation.	The algorithm is portable to any programming language, not just Lisp.
Customization	Limited. It only produces standard Roman numerals.	Highly customizable. You could easily modify the map to support non-standard rules or larger numbers (e.g., with vinculum).

For production code within a Common Lisp environment, the built-in format solution is almost always the superior choice. For learning exercises or if you need to translate the logic to another language, building it from scratch is an invaluable experience.

Frequently Asked Questions (FAQ)

Why do Roman numerals in this kodikra module stop at 3,999?: The traditional Roman system did not have a standard, single character for 5,000. Writing 4,000 would require four 'M's (MMMM), which broke the convention of not repeating a symbol more than three times. Later systems used a bar (vinculum) over a numeral to multiply its value by 1,000 (e.g., V with a bar over it meant 5,000), but this is outside the scope of the classical system this problem addresses.
What exactly does ~@R in Common Lisp's format function do?: The ~R directive is for printing numbers in different radices or formats. By itself, it prints numbers as English words (e.g., (format nil "~R" 42) -> "forty-two"). The at-sign modifier (@) specifically changes the behavior to use Roman numerals (old-style Roman numerals if you use ~:@R).
How would I handle invalid input like zero, negative numbers, or non-integers?: Our example code includes a guard clause: (when (and (integerp number) (> number 0) (< number 4000)) ...). This is a robust way to handle invalid input. It checks if the input is an integer, is positive (plusp could also be used), and is within our accepted range. If the conditions aren't met, the function simply returns nil, which is a Lisp convention for "nothing" or falsiness.
Is the recursive manual solution efficient in Common Lisp?: For the small constraint of N < 4000, it is perfectly efficient. The maximum recursion depth is very shallow. Furthermore, good Common Lisp compilers implement tail-call optimization (TCO), which would turn tail-recursive functions (like our helper `convert`) into an efficient loop, preventing stack overflow even for very large inputs.
What's the difference between (format t ...) and (format nil ...)?: The first argument to format specifies the output stream. t is a special symbol representing the standard terminal output, so (format t ...) prints directly to your console and returns nil. Using nil as the destination tells format not to print anywhere, but to instead create and return a string containing the result.
Are there other ways to store the value-symbol map in Common Lisp?: Absolutely. While an association list is simple and clear, you could also use a hash table for potentially faster lookups (though unnecessary for this small map), or even two separate lists/vectors (one for values, one for symbols) and iterate by index. The alist is often the most idiomatic and readable choice for small, static mapping data.

Conclusion: From Ancient Rules to Modern Code

We've journeyed from the foundational principles of an ancient numbering system to two powerful implementations in Common Lisp. You've seen the stunning conciseness of the built-in format directive, a tool that encapsulates complex logic behind a simple interface. You have also built that logic yourself, piece by piece, using a recursive approach that is both elegant and easy to understand.

This duality is at the heart of becoming a proficient developer. Knowing the powerful abstractions your language provides is crucial for productivity, but understanding the underlying algorithms is what enables you to solve novel problems when no ready-made tool exists. Common Lisp, with its rich standard library and its syntax that makes algorithmic expression feel natural, is a fantastic environment for exploring both sides of this coin.

Technology Disclaimer: The code in this article was verified using Steel Bank Common Lisp (SBCL) 2.4.4. The format function and its ~@R directive are part of the ANSI Common Lisp standard and should be fully portable across all compliant implementations.

Ready to apply your new skills? Continue your journey on the kodikra Common Lisp learning path and discover the next challenge.

To gain a deeper mastery of the language's features, explore our complete Common Lisp guide for more in-depth tutorials and concepts.

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

kodikra

Search this blog