exercism

Exercism - Forth

This post shows you how to get Forth exercise of Exercism.

Stevinator Stevinator
• 9 min read
SHARE
exercism dart flutter forth

Preparation

Before we click on our next exercise, let’s see what concepts of DART we need to consider

Forth Exercise

So we need to use the following concepts.

Lists as Stacks

A stack is a data structure that follows Last-In-First-Out (LIFO) principle. Lists in Dart can be used as stacks with add() for push and removeLast() for pop.

void main() {
  List<int> stack = [];
  
  // Push (add to end)
  stack.add(1);
  stack.add(2);
  stack.add(3);
  print(stack); // [1, 2, 3]
  
  // Pop (remove from end)
  int top = stack.removeLast();
  print(top); // 3
  print(stack); // [1, 2]
  
  // Peek (view top without removing)
  int last = stack.last;
  print(last); // 2
}

Maps for Definitions

Maps can store word definitions, where keys are word names and values are lists of tokens that define the word.

void main() {
  Map<String, List<String>> definitions = {};
  
  // Define a word
  definitions['double'] = ['dup', '+'];
  
  // Look up definition
  List<String>? def = definitions['double'];
  print(def); // [dup, +]
  
  // Check if word exists
  if (definitions.containsKey('double')) {
    print('Word exists');
  }
}

String Parsing and Tokenization

Strings can be split into tokens using split() with regular expressions. This is essential for parsing Forth code.

void main() {
  String input = "1 2 + dup";
  
  // Split by whitespace
  List<String> tokens = input.split(RegExp(r'\s+'));
  print(tokens); // [1, 2, +, dup]
  
  // Convert to lowercase
  String lower = input.toLowerCase();
  print(lower); // "1 2 + dup"
  
  // Combine operations
  List<String> parsed = input.toLowerCase().split(RegExp(r'\s+'));
  print(parsed); // [1, 2, +, dup]
}

Integer Parsing

The int.tryParse() method attempts to parse a string as an integer, returning null if it fails. This is useful for distinguishing numbers from words.

void main() {
  // Successful parse
  int? num1 = int.tryParse('123');
  print(num1); // 123
  
  // Failed parse
  int? num2 = int.tryParse('abc');
  print(num2); // null
  
  // Pattern matching with tryParse
  String token = '42';
  if (int.tryParse(token) case final num?) {
    print('Number: $num'); // Number: 42
  } else {
    print('Not a number');
  }
}

Pattern Matching with Case Expressions

Dart 3.0+ supports pattern matching with case expressions, allowing elegant handling of optional values and switch statements.

void main() {
  Map<String, int> map = {'key': 42};
  
  // Pattern matching in if
  if (map['key'] case final value?) {
    print('Value: $value'); // Value: 42
  }
  
  // Pattern matching in switch
  String token = 'test';
  switch (token) {
    case 'test' when token.length > 3:
      print('Long test');
    case 'test':
      print('Short test');
    default:
      print('Other');
  }
}

List Operations

Lists support various operations like sublist(), indexOf(), addAll(), and accessing elements by index.

void main() {
  List<String> tokens = ['a', 'b', 'c', 'd', 'e'];
  
  // Get sublist
  List<String> sub = tokens.sublist(1, 4);
  print(sub); // [b, c, d]
  
  // Find index
  int index = tokens.indexOf('c');
  print(index); // 2
  
  // Add multiple elements
  List<String> newList = [];
  newList.addAll(['x', 'y']);
  print(newList); // [x, y]
  
  // Access by negative index (from end)
  int len = tokens.length;
  int secondLast = tokens[len - 2];
  print(secondLast); // d
}

Exception Handling

Exceptions are used to signal errors like stack underflow, division by zero, or unknown commands.

void main() {
  // Throwing exceptions
  void checkStack(List<int> stack, int required) {
    if (stack.length < required) {
      throw Exception('Stack empty');
    }
  }
  
  // Catching exceptions
  try {
    checkStack([], 2);
  } catch (e) {
    print('Error: $e'); // Error: Exception: Stack empty
  }
}

Recursive Processing

Functions can call themselves to process nested structures, like expanding user-defined words in Forth.

void main() {
  List<String> process(List<String> tokens) {
    List<String> result = [];
    for (var token in tokens) {
      if (token == 'expand') {
        // Recursive call
        result.addAll(process(['a', 'b']));
      } else {
        result.add(token);
      }
    }
    return result;
  }
  
  List<String> output = process(['x', 'expand', 'y']);
  print(output); // [x, a, b, y]
}

Cascade Operator

The cascade operator (..) allows multiple operations on the same object in sequence.

void main() {
  List<int> stack = [];
  
  // Multiple operations with cascade
  stack..add(1)..add(2)..add(3);
  print(stack); // [1, 2, 3]
  
  // Useful for stack operations
  int a = 1, b = 2;
  stack..add(b)..add(a);
  print(stack); // [1, 2, 3, 2, 1]
}

Introduction

Implement an evaluator for a very simple subset of Forth.

Forth is a stack-based programming language. Implement a very basic evaluator for a small subset of Forth.

Your evaluator has to support the following words:

  • Arithmetic: +, -, *, / (integer arithmetic)
  • Stack manipulation: DUP, DROP, SWAP, OVER
  • Word definitions: : word-name definition ; (defining new words)

To keep things simple the only data type you need to support is signed integers of at least 16 bits size.

You should use the following rules for the syntax: a number is a sequence of one or more (ASCII) digits, a word is a sequence of one or more letters, digits, symbols or punctuation that is not a number. (Forth probably uses slightly different rules, but this is close enough.)

Words are case-insensitive.

What is Forth?

Forth is a stack-based, concatenative programming language and programming environment. It was created by Charles H. Moore in the 1970s. Forth uses a stack to hold arguments and return values, and words (functions) operate on the stack.

In Forth, you write words (functions) that manipulate a stack. Numbers are pushed onto the stack, and operations consume values from the stack and push results back.

— Programming Languages

How does Forth work?

Forth is a stack-based language where:

  1. Numbers are pushed onto the stack
  2. Words (operations) pop values from the stack, perform operations, and push results back
  3. Stack operations manipulate the stack itself (duplicate, swap, etc.)
  4. User definitions allow creating new words from existing ones

For example:

  • 1 2 + pushes 1, pushes 2, then adds them (result: 3 on stack)
  • : double dup + ; defines a word “double” that duplicates the top value and adds them
  • 5 double pushes 5, then executes “double” (result: 10 on stack)

Examples

  • 1 2 + → Stack: [3]
  • 1 2 3 swap → Stack: [1, 3, 2] (swaps top two)
  • 1 2 3 over → Stack: [1, 2, 3, 2] (copies second-to-top)
  • : double dup + ; 5 double → Stack: [10]

Solution

class Forth {
  final List<int> _stack = [];
  final Map<String, List<String>> _definitions = {};
  
  List<int> get stack => List.unmodifiable(_stack);
  
  void evaluate(String input) {
    _processTokens(input.toLowerCase().split(RegExp(r'\s+')));
  }
  
  void _processTokens(List<String> tokens) {
    for (int i = 0; i < tokens.length; i++) {
      final token = tokens[i];
      
      if (token == ':') {
        final end = tokens.indexOf(';', i);
        final name = tokens[i + 1];
        if (int.tryParse(name) != null) throw Exception('Invalid definition');
        
        // Expand the definition by resolving existing words NOW
        final rawDef = tokens.sublist(i + 2, end);
        final expandedDef = _expandDefinition(rawDef);
        _definitions[name] = expandedDef;
        
        i = end;
      } else if (int.tryParse(token) case final num?) {
        _stack.add(num);
      } else {
        _executeToken(token);
      }
    }
  }
  
  // Expand user-defined words in a definition to their current values
  List<String> _expandDefinition(List<String> tokens) {
    final expanded = <String>[];
    for (final token in tokens) {
      if (_definitions.containsKey(token)) {
        // Use the current definition of this word
        expanded.addAll(_definitions[token]!);
      } else {
        expanded.add(token);
      }
    }
    return expanded;
  }
  
  void _executeToken(String token) {
    if (_definitions[token] case final def?) {
      return _processTokens(def);
    }
    
    void require(int n) {
      if (_stack.length < n) throw Exception('Stack empty');
    }
    
    int pop() => _stack.removeLast();
    
    switch (token) {
      case '+': 
        require(2); 
        _stack.add(pop() + pop());
        
      case '-': 
        require(2); 
        final b = pop(), a = pop(); 
        _stack.add(a - b);
        
      case '*': 
        require(2); 
        _stack.add(pop() * pop());
        
      case '/': 
        require(2);
        final b = pop(), a = pop();
        if (b == 0) throw Exception('Division by zero');
        _stack.add(a ~/ b);
        
      case 'dup': 
        require(1); 
        _stack.add(_stack.last);
        
      case 'drop': 
        require(1); 
        pop();
        
      case 'swap': 
        require(2); 
        final b = pop(), a = pop(); 
        _stack..add(b)..add(a);
        
      case 'over': 
        require(2); 
        _stack.add(_stack[_stack.length - 2]);
        
      default: 
        throw Exception('Unknown command');
    }
  }
}

Let’s break down the solution:

  1. _stack and _definitions - Private fields:

    • _stack: List storing integer values (the Forth stack)
    • _definitions: Map storing user-defined words (name → list of tokens)

  2. evaluate(String input) - Entry point:

    • Converts input to lowercase (case-insensitive)
    • Splits by whitespace using RegExp(r'\s+')
    • Processes the tokens

  3. _processTokens(List<String> tokens) - Main processing loop:

    • Iterates through tokens
    • Definition handling (:): When encountering :, finds the matching ;, extracts the word name and definition, expands nested definitions, and stores it
    • Number handling: Uses pattern matching with int.tryParse() to detect numbers and push them onto the stack
    • Word execution: Calls _executeToken() for other tokens

  4. _expandDefinition(List<String> tokens) - Expands user-defined words:

    • Recursively replaces user-defined words with their definitions
    • This happens at definition time, not execution time (immediate expansion)

  5. _executeToken(String token) - Executes a word:

    • User-defined words: If found in _definitions, recursively processes its definition
    • Built-in words: Uses a switch statement:
      • Arithmetic (+, -, *, /): Pops operands, performs operation, pushes result
      • Stack operations:
        • dup: Duplicates top value
        • drop: Removes top value
        • swap: Swaps top two values
        • over: Copies second-to-top value
    • Error handling: require() checks stack has enough elements; division checks for zero

The solution implements a complete Forth evaluator with stack operations, arithmetic, and user-defined words, using recursive processing to handle nested definitions.

A video tutorial for this exercise is coming soon! In the meantime, check out my YouTube channel for more Dart and Flutter tutorials. 😉

Visit My YouTube Channel
Stevinator

Stevinator

Stevinator is a software engineer passionate about clean code and best practices. Loves sharing knowledge with the developer community.