Interpreter パターンで独自の言語を作る：簡易計算機の実装

## はじめに

Interpreterパターンは、特定のドメイン固有言語（DSL）を解釈し実行するためのデザインパターンです。このパターンを使用することで、独自の言語や文法を定義し、それを解釈して実行するシステムを構築することができます。

本記事では、Interpreterパターンを使って簡単な計算機を実装し、このパターンの使い方、メリット、デメリットについて解説します。さらに、基本的な実装から始めて、より複雑な機能を持つ拡張版の実装まで段階的に説明していきます。

## なぜInterpreterパターンを使うのか

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2648069/a0bb1af4-f439-9c66-8760-ec55e8654586.png)

Interpreterパターンは以下のような状況で有用です：

1. 特定のドメインに特化した言語を作成する必要がある場合
2. 複雑な文法や表現を解釈する必要がある場合
3. 柔軟性が高く、拡張可能なシステムが必要な場合

## Interpreterパターンの使い所

- ビジネスルールエンジン
- 数式パーサー
- 設定ファイルの解析
- クエリ言語の実装
- スクリプト言語の開発

## メリット

1. 柔軟性：新しい文法規則や演算子を追加しやすい
2. 拡張性：既存のコードを変更せずに新しい機能を追加できる
3. 分離性：文法規則とその解釈を明確に分離できる
4. 再利用性：パターン化されているため、他のプロジェクトでも再利用しやすい

## デメリット

1. 複雑性：大規模な言語では、クラス階層が複雑になる可能性がある
2. パフォーマンス：インタープリタ方式のため、コンパイル方式と比べて実行速度が遅くなる可能性がある
3. デバッグの難しさ：エラーの追跡が難しくなる場合がある
4. オーバーエンジニアリング：単純な問題に対して過剰に複雑な設計になる可能性がある

## 基本的な実装：簡易計算機

まずは、Interpreterパターンを使用して基本的な計算機を実装してみましょう。この計算機は、整数の加算と減算を行うことができます。

```plantuml
@startuml
skinparam classAttributeIconSize 0
skinparam noteBackgroundColor LightYellow
skinparam noteBorderColor Gray

abstract class Expression {
    +interpret(): int
}

class Number {
    -value: int
    +interpret(): int
}

class Add {
    -left: Expression
    -right: Expression
    +interpret(): int
}

class Subtract {
    -left: Expression
    -right: Expression
    +interpret(): int
}

class Parser {
    +parse(tokens: list): Expression
}

class Calculator {
    -parser: Parser
    +calculate(expression: string): int
}

Expression <|-- Number
Expression <|-- Add
Expression <|-- Subtract
Add --> Expression : left, right
Subtract --> Expression : left, right
Parser ..> Expression : creates
Calculator --> Parser : uses
Calculator ..> Expression : uses

note right of Expression
    抽象構文木の要素を表す抽象クラス
    全ての式はこのクラスを継承する
end note

note right of Number
    終端となる数値を表現する
    具体的な値を保持
end note

note right of Add
    加算を表現する非終端記号
    左右の式を組み合わせる
end note

note right of Subtract
    減算を表現する非終端記号
    左右の式を組み合わせる
end note

note right of Parser
    入力をトークンに分解し
    抽象構文木を構築する
end note

note right of Calculator
    全体の制御を行う
    Parserを使用して式を解析し
    結果を計算する
end note

note as PatternNote
Interpreterパターン
- 文法規則をクラスで表現
- 再帰的な構造を持つ
- 新しい式の追加が容易
- 文法の解釈と実行を分離
end note

Calculator .. PatternNote

@enduml
```

```plantuml
@startuml
skinparam sequenceArrowThickness 2
skinparam roundcorner 5
skinparam maxMessageSize 100
skinparam noteBackgroundColor LightYellow
skinparam noteBorderColor Gray

actor ユーザー as User
participant 計算機 as Calculator
participant パーサー as Parser
participant "加算: 式" as Add
participant "減算: 式" as Subtract
participant "数値: 式" as Number

User -> Calculator : calculate("5 + 3 - 2")
activate Calculator
note right of User : 計算式を入力

Calculator -> Parser : parse(["5", "+", "3", "-", "2"])
activate Parser
note right of Calculator : トークンに分割された式を解析

Parser -> Number : new Number(5)
Parser -> Number : new Number(3)
Parser -> Add : new Add(Number(5), Number(3))
Parser -> Number : new Number(2)
Parser -> Subtract : new Subtract(Add, Number(2))
note right of Parser : 抽象構文木を構築\n各式オブジェクトを生成

Parser --> Calculator : Subtract式を返す
deactivate Parser

Calculator -> Subtract : interpret()
activate Subtract
note right of Calculator : 構文木の解釈を開始

Subtract -> Add : interpret()
activate Add
note right of Subtract : 左側の式（加算）を解釈

Add -> Number : interpret() // 5
activate Number
Number --> Add : 5を返す
deactivate Number

Add -> Number : interpret() // 3
activate Number
Number --> Add : 3を返す
deactivate Number

Add --> Subtract : 8を返す
deactivate Add
note right of Add : 5 + 3 = 8 を計算

Subtract -> Number : interpret() // 2
activate Number
Number --> Subtract : 2を返す
deactivate Number

Subtract --> Calculator : 6を返す
deactivate Subtract
note right of Subtract : 8 - 2 = 6 を計算

Calculator --> User : 6を返す
deactivate Calculator
note right of Calculator : 最終結果をユーザーに返す

@enduml
```
```python
from abc import ABC, abstractmethod

# 抽象構文木のノードを表す抽象基底クラス
class Expression(ABC):
    @abstractmethod
    def interpret(self) -> int:
        pass

# 数値を表現するクラス
class Number(Expression):
    def __init__(self, value: int):
        self.value = value

    def interpret(self) -> int:
        return self.value

# 加算を表現するクラス
class Add(Expression):
    def __init__(self, left: Expression, right: Expression):
        self.left = left
        self.right = right

    def interpret(self) -> int:
        return self.left.interpret() + self.right.interpret()

# 減算を表現するクラス
class Subtract(Expression):
    def __init__(self, left: Expression, right: Expression):
        self.left = left
        self.right = right

    def interpret(self) -> int:
        return self.left.interpret() - self.right.interpret()

# 構文解析を行うクラス
class Parser:
    def parse(self, tokens: list) -> Expression:
        stack = []
        for token in tokens:
            if token == '+':
                right = stack.pop()
                left = stack.pop()
                stack.append(Add(left, right))
            elif token == '-':
                right = stack.pop()
                left = stack.pop()
                stack.append(Subtract(left, right))
            else:
                stack.append(Number(int(token)))
        return stack[0]

# 計算機クラス
class Calculator:
    def __init__(self):
        self.parser = Parser()

    def calculate(self, expression: str) -> int:
        tokens = expression.split()
        ast = self.parser.parse(tokens)
        return ast.interpret()

# 使用例
if __name__ == "__main__":
    calc = Calculator()
    print(calc.calculate("5 3 +"))  # 出力: 8
    print(calc.calculate("10 5 - 3 +"))  # 出力: 8
    print(calc.calculate("7 3 - 2 -"))  # 出力: 2
```

この実装では、逆ポーランド記法（後置記法）を使用しています。例えば、`5 + 3`は`5 3 +`と表現します。

### 基本実装の解説

1. `Expression`クラス：すべての式の基底クラスです。`interpret`メソッドを持ちます。

2. `Number`クラス：数値を表現します。`interpret`メソッドは単に値を返します。

3. `Add`クラス：加算を表現します。左右の式を持ち、それぞれを解釈した結果を加算します。

4. `Subtract`クラス：減算を表現します。左右の式を持ち、それぞれを解釈した結果を減算します。

5. `Parser`クラス：トークンのリストを受け取り、抽象構文木を構築します。

6. `Calculator`クラス：文字列の式を受け取り、計算結果を返します。

## 拡張版実装：複雑な計算機

次に、基本実装を拡張して、より複雑な計算とエラーハンドリングを追加しましょう。この新しいバージョンでは、以下の機能を追加します：

1. 乗算と除算の追加
2. 括弧のサポート
3. エラーハンドリング

```python
from abc import ABC, abstractmethod

class Expression(ABC):
    @abstractmethod
    def interpret(self) -> float:
        pass

class Number(Expression):
    def __init__(self, value: float):
        self.value = value

    def interpret(self) -> float:
        return self.value

class Add(Expression):
    def __init__(self, left: Expression, right: Expression):
        self.left = left
        self.right = right

    def interpret(self) -> float:
        return self.left.interpret() + self.right.interpret()

class Subtract(Expression):
    def __init__(self, left: Expression, right: Expression):
        self.left = left
        self.right = right

    def interpret(self) -> float:
        return self.left.interpret() - self.right.interpret()

class Multiply(Expression):
    def __init__(self, left: Expression, right: Expression):
        self.left = left
        self.right = right

    def interpret(self) -> float:
        return self.left.interpret() * self.right.interpret()

class Divide(Expression):
    def __init__(self, left: Expression, right: Expression):
        self.left = left
        self.right = right

    def interpret(self) -> float:
        right = self.right.interpret()
        if right == 0:
            raise ValueError("Division by zero")
        return self.left.interpret() / right

class Parser:
    def __init__(self):
        self.operators = {'+': Add, '-': Subtract, '*': Multiply, '/': Divide}
        self.precedence = {'+': 1, '-': 1, '*': 2, '/': 2}

    def parse(self, expression: str) -> Expression:
        tokens = self.tokenize(expression)
        return self.parse_expression(tokens)

    def tokenize(self, expression: str) -> list:
        return expression.replace('(', ' ( ').replace(')', ' ) ').split()

    def parse_expression(self, tokens: list) -> Expression:
        output_queue = []
        operator_stack = []

        for token in tokens:
            if self.is_number(token):
                output_queue.append(Number(float(token)))
            elif token in self.operators:
                while (operator_stack and operator_stack[-1] != '(' and
                       self.precedence[operator_stack[-1]] >= self.precedence[token]):
                    self.apply_operator(output_queue, operator_stack.pop())
                operator_stack.append(token)
            elif token == '(':
                operator_stack.append(token)
            elif token == ')':
                while operator_stack and operator_stack[-1] != '(':
                    self.apply_operator(output_queue, operator_stack.pop())
                if operator_stack and operator_stack[-1] == '(':
                    operator_stack.pop()
                else:
                    raise ValueError("Mismatched parentheses")

        while operator_stack:
            if operator_stack[-1] == '(':
                raise ValueError("Mismatched parentheses")
            self.apply_operator(output_queue, operator_stack.pop())

        if len(output_queue) != 1:
            raise ValueError("Invalid expression")

        return output_queue[0]

    def is_number(self, token: str) -> bool:
        try:
            float(token)
            return True
        except ValueError:
            return False

    def apply_operator(self, output_queue: list, operator: str):
        if len(output_queue) < 2:
            raise ValueError(f"Not enough operands for operator {operator}")
        right = output_queue.pop()
        left = output_queue.pop()
        output_queue.append(self.operators[operator](left, right))

class Calculator:
    def __init__(self):
        self.parser = Parser()

    def calculate(self, expression: str) -> float:
        try:
            ast = self.parser.parse(expression)
            return ast.interpret()
        except Exception as e:
            return f"Error: {str(e)}"

# 使用例
if __name__ == "__main__":
    calc = Calculator()
    print(calc.calculate("3 + 4 * 2"))  # 出力: 11.0
    print(calc.calculate("(3 + 4) * 2"))  # 出力: 14.0
    print(calc.calculate("10 / (4 - 2)"))  # 出力: 5.0
    print(calc.calculate("5 + + 3"))  # 出力: Error: Not enough operands for operator +
    print(calc.calculate("10 / 0"))  # 出力: Error: Division by zero
    print(calc.calculate("(3 + 4"))  # 出力: Error: Mismatched parentheses
```

### 拡張版実装の解説

1. **新しい演算子**: `Multiply`と`Divide`クラスを追加し、乗算と除算をサポートしました。

2. **括弧のサポート**: `Parser`クラスを大幅に改良し、シャンティングヤード・アルゴリズムを使用して中置記法の式を解析できるようにしました。これにより、括弧を含む複雑な式を正しく解釈できます。

3. **エラーハンドリング**: 
   - 不正な式（演算子や括弧の不足など）に対してエラーを発生させます。
   - ゼロ除算を検出し、エラーを発生させます。
   - `Calculator`クラスで、すべての例外をキャッチし、ユーザーフレンドリーなエラーメッセージを返します。

4. **柔軟性**: 数値を`float`型で扱うことで、小数点を含む計算もサポートしています。

## まとめ

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2648069/c15d59ce-fe9a-f963-b5b7-714d8434d7ec.png)

Interpreterパターンを使用することで、独自の言語や文法を柔軟に実装できることを示しました。基本的な実装から始まり、より複雑な機能を持つ拡張版の実装まで段階的に解説することで、以下の点を強調しました：

1. Interpreterパターンの基本的な構造と動作
2. パターンの拡張性と柔軟性
3. エラーハンドリングの重要性
4. 実践的な実装の例

この記事で示した実装は、さらに拡張して以下のような機能を追加することも可能です：

- 変数のサポート
- 関数の定義と呼び出し
- 条件分岐や繰り返し構文

Interpreterパターンの強みは、このような拡張性にあります。ただし、言語の複雑さが増すにつれて、実装も複雑になる可能性があります。大規模な言語処理システムを構築する場合は、パーサージェネレータやコンパイラコンストラクションツールの使用を検討することも重要です。

Interpreterパターンは、特定のドメインに特化した言語の実装や、設定ファイルの解析、数式の評価など、様々な場面で活用できる強力なツールです。適切に使用することで、柔軟で拡張性の高いシステムを構築することができます。