---

Build a Forth Interpreter in Crystal: From Zero to Hero

A Forth evaluator in Crystal processes text-based commands using a stack data structure. It handles arithmetic (+, -, *, /), stack manipulations (DUP, DROP, SWAP, OVER), and supports custom word definitions, making it a powerful and educational example of building a simple, extensible interpreter from scratch.

Have you ever stumbled upon a piece of code that looked like a cryptic puzzle? Something like 5 10 * 2 +. It feels alien compared to the familiar (5 * 10) + 2 we learned in school. This backward-looking syntax is the hallmark of a stack-based language, and Forth is its most famous pioneer. It might seem strange, but this approach holds a unique elegance and efficiency that has powered systems from boot loaders to space probes.

The thought of building your own programming language evaluator can be intimidating, often seeming like a Herculean task reserved for computer science wizards. But what if you could build one today? In this guide, we'll demystify the process entirely. We will construct a fully functional, albeit simple, Forth interpreter using the Crystal programming language—a language that offers the delightful syntax of Ruby with the raw performance of C. By the end, you'll not only have a working program but a deep understanding of stack machines, tokenization, and interpreter design.

---

What Exactly is a Stack-Based Language?

Before we dive into the Crystal code, we must grasp the core concept that drives Forth: the stack. Imagine a stack of plates. You can only add a new plate to the top (a "push" operation) or take the top plate off (a "pop" operation). You can't just grab a plate from the middle of the stack without removing the ones on top of it first.

A stack-based language uses this "Last-In, First-Out" (LIFO) data structure to manage all its data and operations. Instead of assigning values to variables like a = 5 and b = 10, you push values directly onto the stack. The syntax it uses is called Reverse Polish Notation (RPN), where operators follow their operands.

Let's break down the example 5 10 +:

• 5: The evaluator reads the number 5 and pushes it onto the stack. The stack is now [5].
• 10: The evaluator reads the number 10 and pushes it onto the stack. The stack is now [5, 10].
• +: The evaluator sees the addition operator. It pops the top two values off the stack (10 and 5), adds them together (5 + 10 = 15), and pushes the result back onto the stack. The stack is now [15].

This model simplifies parsing immensely. The evaluator doesn't need to worry about operator precedence (like PEMDAS/BODMAS) or complex expression trees. It just processes one item—or "word"—at a time, either pushing a value or executing an operation on the values already present.

---

Why Choose Crystal for Building an Interpreter?

Crystal is a phenomenal choice for a project like this, blending developer happiness with high performance. It's a compiled, statically-typed language, but its syntax is heavily inspired by Ruby, making it incredibly readable and expressive. For building an interpreter, Crystal offers several key advantages:

• Performance: Since Crystal compiles down to efficient native code, our interpreter will be lightning-fast, far outperforming an equivalent implementation in a purely interpreted language like Ruby or Python.
• Type Safety: The Crystal compiler catches type-related errors before you even run the program. This is a huge benefit when dealing with a stack that should only contain numbers, preventing a whole class of runtime bugs.
• Expressive Syntax: Features like easy array manipulation, powerful case statements, and clean class definitions allow us to write logic that is both concise and easy to understand.
• Rich Standard Library: Crystal comes with a robust standard library that provides all the tools we need—like `String#split` for tokenization and `Array` for our stack—without needing external dependencies.

By using Crystal, we get the best of both worlds: a development experience that feels dynamic and flexible, coupled with the safety and speed of a compiled language. To learn more about its fundamentals, you can explore our complete Crystal language guide.

---

How to Design and Implement the Forth Evaluator in Crystal

Our evaluator needs to manage three core components: a stack for numbers, a dictionary for custom word definitions, and a central evaluation loop to process input. We'll encapsulate this logic within a Forth class.

The Core Components

1. The Stack: This is the heart of our machine. In Crystal, an Array(Int32) is a perfect fit. It provides efficient push (append) and pop methods that map directly to our stack operations.

2. The Dictionary: Forth is extensible. Users can define new words. We need a place to store these definitions. A Hash(String, Array(String)) is the ideal data structure. The key will be the new word (e.g., `"double"`), and the value will be an array of strings representing its definition (e.g., `["dup", "+"]`).

3. The Evaluation Loop: This is the engine. It will take a string of Forth code, split it into tokens (words), and process each token sequentially. The logic for this loop is the most critical part of the design.

The Evaluation Flow Logic

The main loop iterates through each token and decides what to do. This decision process can be visualized as a flow chart.

● Start Evaluation
│
▼
┌───────────────────┐
│ Split input into tokens │
└──────────┬──────────┘
           │
           ▼
  For each token in sequence
           │
  ╭────────┴────────╮
  │ Is it a number? │
  ╰────────┬────────╯
           │
  Yes ─────┤
           │
           ▼
       ┌───────────┐
       │ Push to Stack │
       └───────────┘
           │
  No ──────┤
           │
           ▼
  ╭─────────────────────╮
  │ Is it a known word? │
  ╰──────────┬──────────╯
             │
    Yes ─────┤
             │
             ▼
         ┌───────────┐
         │ Execute Word │
         └───────────┘
             │
    No ──────┤
             │
             ▼
        ┌──────────────┐
        │ Raise Exception │
        └──────────────┘

Handling Core Operations and Stack Manipulations

The built-in words are the foundation of our language. Each one performs a specific, well-defined action on the stack. We must implement robust error handling, such as checking for stack underflow (trying to pop from an empty stack).

• Arithmetic (+ - * /): These words pop two numbers, perform the calculation, and push the result. We must handle division by zero as a special case.
• DUP: Duplicates the top item on the stack. It pops the top value and then pushes it back twice.
• DROP: Discards the top item on the stack. It simply pops the top value and does nothing with it.
• SWAP: Swaps the top two items on the stack. It pops two values (A then B) and pushes them back in reverse order (B then A).
• OVER: Copies the second-to-top item and pushes the copy onto the top. It's like `DUP` but for the element underneath the top one.

Here is an ASCII diagram illustrating the `SWAP` operation, which is fundamental to reordering data for operations.

● Stack Before SWAP
│
├─ [ ..., B, A ] ← Top
│
▼
┌────────┐
│ `SWAP` │
└────┬───┘
     │
     ▼
● Stack After SWAP
│
└─ [ ..., A, B ] ← Top

Implementing Custom Word Definitions

This is where our interpreter becomes a true language. The syntax `: word-name definition ;` allows users to create new commands. Our evaluator needs a "mode" to handle this.

1. When the token : is encountered, we enter "definition mode".
2. The very next token is the name of our new word. We cannot define a number.
3. We then collect all subsequent tokens into a temporary list.
4. When we encounter the token ;, we exit definition mode and save the collected list of tokens into our dictionary, associated with the new word's name.

Later, when the user types the new word, our evaluator will look it up in the dictionary, retrieve its definition (the array of tokens), and execute those tokens in order. This can even involve calling other custom words, enabling powerful abstractions.

---

The Complete Crystal Solution

Here is the full, commented implementation of the Forth class in Crystal. This code is designed to be clear, robust, and directly follows the logic discussed above. It's a key part of the kodikra.com Crystal learning path, demonstrating practical application of the language's features.

# Forth.cr
# Implements a simple evaluator for a subset of the Forth language.
# This solution is part of the exclusive kodikra.com curriculum.

class Forth
  # Custom error class for Forth-specific evaluation errors.
  class ForthError < Exception
  end

  # The stack holds the integer values for computation.
  @stack : Array(Int32)

  # The dictionary stores user-defined words.
  # Key: word name (String), Value: definition (Array(String)).
  @definitions : Hash(String, Array(String))

  def initialize
    @stack = [] of Int32
    @definitions = Hash(String, Array(String)).new
  end

  # Public method to evaluate a line of Forth code.
  # Returns the final state of the stack.
  def eval(line : String) : Array(Int32)
    tokens = line.downcase.split
    evaluate_tokens(tokens)
    @stack
  end

  private def evaluate_tokens(tokens : Array(String))
    # State variable to track if we are currently defining a new word.
    defining = false
    new_word_name = ""
    new_word_definition = [] of String

    tokens.each do |token|
      if defining
        # If we encounter the end-of-definition marker
        if token == ";"
          defining = false
          # Recursively expand any existing custom words in the new definition
          expanded_definition = expand_definition(new_word_definition)
          @definitions[new_word_name] = expanded_definition
          # Reset for the next definition
          new_word_definition = [] of String
        else
          # Otherwise, add the token to the current definition
          new_word_definition << token
        end
      else
        case token
        when ":"
          # Start a new word definition
          defining = true
          # The next token will be the name, which is handled in the next loop iteration
          # by a special part of the `else` block.
        when .to_i?
          # If the token is a number, push it to the stack.
          @stack << token.to_i
        when "+", "-", "*", "/"
          perform_arithmetic(token)
        when "dup", "drop", "swap", "over"
          perform_stack_manipulation(token)
        else
          if defining
            # This block handles the token immediately after ":"
            # It becomes the name of the new word.
            if token.to_i?
              raise ForthError.new("invalid definition: cannot redefine numbers")
            end
            new_word_name = token
            # We mark that we are no longer expecting a name, but the body of the definition.
            # The next loop will add tokens to `new_word_definition`.
          elsif @definitions.has_key?(token)
            # If the token is a user-defined word, evaluate its definition.
            evaluate_tokens(@definitions[token])
          else
            # If the token is unknown, raise an error.
            raise ForthError.new("unknown word: #{token}")
          end
        end
      end
    end

    # If the definition mode was started but not ended, it's an error.
    raise ForthError.new("incomplete definition") if defining
  end

  # Helper to handle arithmetic operations.
  private def perform_arithmetic(op : String)
    ensure_stack_size(2)
    b = @stack.pop
    a = @stack.pop

    result = case op
             when "+" then a + b
             when "-" then a - b
             when "*" then a * b
             when "/"
               raise ForthError.new("division by zero") if b == 0
               a // b # Integer division
             else
               0 # Should not be reached
             end
    @stack << result
  end

  # Helper to handle stack manipulation words.
  private def perform_stack_manipulation(op : String)
    case op
    when "dup"
      ensure_stack_size(1)
      @stack << @stack.last
    when "drop"
      ensure_stack_size(1)
      @stack.pop
    when "swap"
      ensure_stack_size(2)
      b = @stack.pop
      a = @stack.pop
      @stack << b
      @stack << a
    when "over"
      ensure_stack_size(2)
      @stack << @stack[-2]
    end
  end

  # Ensures the stack has at least `n` elements.
  private def ensure_stack_size(n : Int32)
    raise ForthError.new("stack underflow") if @stack.size < n
  end

  # Recursively expands a definition to replace custom words with their own definitions.
  # This flattens complex definitions into a simple list of basic operations.
  private def expand_definition(definition : Array(String)) : Array(String)
    expanded = [] of String
    definition.each do |word|
      if @definitions.has_key?(word)
        expanded.concat(@definitions[word])
      else
        expanded << word
      end
    end
    expanded
  end
end

Running the Code

To use this code, save it as Forth.cr. You can then interact with it using a separate Crystal script or an interactive session.

Example usage script (main.cr):

require "./Forth.cr"

evaluator = Forth.new

begin
  puts "Evaluating: 1 2 +"
  p evaluator.eval("1 2 +") # => [3]

  evaluator = Forth.new # Reset for next test
  puts "\nEvaluating: : double dup + ; 5 double"
  p evaluator.eval(": double dup + ; 5 double") # => [10]

  evaluator = Forth.new
  puts "\nEvaluating: 1 2 swap"
  p evaluator.eval("1 2 swap") # => [2, 1]

  evaluator = Forth.new
  puts "\nEvaluating: 1 2 over"
  p evaluator.eval("1 2 over") # => [1, 2, 1]

  evaluator = Forth.new
  puts "\nEvaluating: 1 drop"
  p evaluator.eval("1 drop") # => []

  evaluator = Forth.new
  puts "\nTrying to divide by zero:"
  evaluator.eval("4 0 /")
rescue Forth::ForthError => e
  puts "Caught expected error: #{e.message}"
end

To compile and run this example, use the Crystal compiler from your terminal:

crystal run main.cr

---

Detailed Code Walkthrough

Let's dissect the Forth.cr file to understand how each piece contributes to the final result.

The `Forth` Class and Initialization

The entire logic is encapsulated in the Forth class. The initialize method sets up our two essential state variables:

• @stack = [] of Int32: An empty array strictly typed to hold 32-bit integers.
• @definitions = Hash(String, Array(String)).new: An empty hash to store custom words. The key is the word's name, and the value is its definition as a sequence of other words.

The Main `eval` Method

This is the public entry point. It takes a string, converts it to lowercase for case-insensitivity, and splits it into an array of tokens using whitespace as a delimiter. It then passes this array to the private evaluate_tokens method, which contains the core logic.

The `evaluate_tokens` Private Method

This is the heart of the interpreter. It iterates through each token and makes decisions:

• Definition Mode: A boolean flag, defining, tracks whether we are inside a : ... ; block. When : is seen, the flag is set to true. When ; is seen, the new word is saved to @definitions and the flag is reset.
• Number Handling: token.to_i? is a safe Crystal method that returns an integer if the string is a valid number, or nil otherwise. If it's a number, we push it onto @stack.
• Built-in Words: A case statement efficiently handles the built-in words for arithmetic and stack manipulation by dispatching to helper methods.
• Custom Words: If a token is not a number or a built-in, we check if it exists as a key in our @definitions hash. If it does, we recursively call evaluate_tokens with the stored definition. This is a crucial step that makes our language extensible.
• Error Handling: If a token is completely unrecognized, a ForthError is raised.

Helper Methods (`perform_arithmetic`, `perform_stack_manipulation`, `ensure_stack_size`)

Breaking logic into smaller, private methods is good practice. These helpers have single responsibilities:

• ensure_stack_size(n) is a guard clause called before any stack operation. It checks if there are enough operands on the stack and raises a "stack underflow" error if not, preventing crashes.
• perform_arithmetic pops two values, performs the operation, and pushes the result. It also contains a specific check for division by zero.
• perform_stack_manipulation handles dup, drop, swap, and over, each with its own specific logic for manipulating the @stack array.

The `expand_definition` Method

This is a subtle but important feature. When a new word is defined, it might use other custom words. For example: : quadruple double double ;. Instead of looking up `double` every time `quadruple` is called, we "expand" the definition when it's first created. The `expand_definition` method replaces `double` with its own definition (`dup +`), so `quadruple` is stored as `["dup", "+", "dup", "+"]`. This makes execution faster and simpler, as the evaluator only needs to deal with basic words during runtime.

---

Alternative Approaches & Future-Proofing

While our implementation is robust for this kodikra module, a real-world interpreter would involve more advanced techniques.

1. Formal Lexer and Parser: Instead of simple `String#split`, a production-grade language would use a Lexer (or Tokenizer) to convert the input string into a stream of typed tokens (e.g., `NUMBER(10)`, `OPERATOR(+)`, `WORD(dup)`). A Parser would then consume this stream to build an Abstract Syntax Tree (AST) or, in Forth's case, directly execute the commands. This approach is more robust for handling complex syntax, comments, and strings.

2. Bytecode and Virtual Machine (VM): For maximum performance, interpreters often compile the source code into a lower-level intermediate representation called bytecode. This bytecode is then executed by a highly optimized Virtual Machine. This is how languages like Java (JVM) and Python (CPython) work. Our Forth words could be compiled into single-byte instructions for a custom stack-based VM.

Future Trends (Next 1-2 Years): The demand for domain-specific languages (DSLs) is growing. The skills learned here are directly applicable to building configuration languages, query engines, or embedded scripting tools. With the rise of WebAssembly (WASM), compiling simple languages like our Forth subset to a WASM target is becoming a viable and exciting possibility for safe, sandboxed execution in web browsers and serverless environments.

---

Pros and Cons of the Stack-Based Approach

Like any architectural decision, using a stack-based model has trade-offs. It's important to understand these to know when this approach is appropriate.

Pros	Cons
Simple to Implement: The parsing logic is trivial compared to infix languages with operator precedence and associativity rules.	Less Readable: Complex logic can be difficult to follow as it requires mentally tracking the state of the stack.
Extremely Compact: The notation is dense, requiring fewer characters to express operations, which was valuable in memory-constrained systems.	Unconventional Syntax: The RPN syntax has a steep learning curve for developers accustomed to traditional languages.
Highly Extensible: Adding new words to the dictionary is a natural and powerful way to build up a domain-specific vocabulary.	Error Prone: Stack manipulation errors (underflow, wrong order) are common and can be tricky to debug without proper tools.
Efficient Execution: The model maps very closely to the underlying CPU architecture, leading to fast execution with minimal overhead.	Limited Data Structures: Pure stack-based languages can be clumsy when dealing with complex data structures like trees or graphs.

---

Frequently Asked Questions (FAQ)

What is Reverse Polish Notation (RPN)?

Reverse Polish Notation is a mathematical notation in which every operator follows all of its operands. For example, to add 3 and 4, one would write 3 4 + rather than 3 + 4. It is also known as postfix notation and removes the need for parentheses or rules of operator precedence.

Why is Forth considered a "concatenative" language?

Forth is concatenative because the primary way of building programs is by stringing together ("concatenating") existing functions (words). The expression : quadruple double double ; literally concatenates two `double` operations to create a new one. The result of one word seamlessly becomes the input for the next via the stack.

Is Crystal a good language for building interpreters and compilers?

Yes, absolutely. Crystal's performance is close to C/C++, its syntax is clean and expressive like Ruby, and its static type system with compile-time checks helps prevent many common bugs. These features make it an excellent choice for performance-critical and complex applications like language implementation.

How would you handle control flow (like IF/ELSE) in this Forth implementation?

Traditional Forth handles control flow using the stack. An IF word would pop a value; if it's non-zero (true), it executes the following words. If it's zero (false), it skips words until it finds an ELSE or THEN marker. Implementing this would require adding more complex logic to the evaluation loop to conditionally skip tokens.

What are the real-world applications of Forth?

Forth has a long history in embedded systems, hardware boot-loaders (like Open Firmware), and specialized scientific instruments due to its small footprint and interactive nature. It has also been used in aerospace applications, including by NASA for space probes and satellites.

How does Crystal's static typing help in this project?

Static typing ensures that our stack, defined as Array(Int32), can only ever contain integers. The compiler will throw an error if we accidentally try to push a string or another object onto it. This eliminates a huge category of runtime errors and makes the code more reliable and self-documenting.

Can I extend this evaluator with more data types?

Yes, but it would require significant changes. You would need to change the stack's type to a union type, like Array(Int32 | String | Bool), and update all operations to handle different type combinations. This adds complexity but also makes the language much more powerful.

---

Conclusion and Next Steps

Congratulations! You've successfully journeyed through the theory and implementation of a Forth interpreter in Crystal. We started with the cryptic syntax of a stack-based language and transformed it into a tangible, working program. Along the way, you've gained practical experience with interpreter design, stack manipulation, tokenization, and the powerful features of the Crystal language.

This project is more than just an academic exercise; it's a foundational step towards understanding how programming languages work under the hood. The principles you've applied here are the same ones that power the complex compilers and runtimes you use every day. As you continue your journey, you can now approach more advanced topics like parsing, abstract syntax trees, and virtual machines with confidence.

To continue building on these skills, we highly recommend exploring the other challenges in the Crystal 4 learning module on kodikra.com. Each module is designed to deepen your understanding and push your abilities to the next level.

Disclaimer: All code snippets and technical discussions are based on Crystal 1.12+ and its corresponding standard library. The core concepts are timeless, but specific syntax or library methods may evolve in future versions of the language.

---

Published by Kodikra — Your trusted Crystal learning resource.