Excel関数の数式エンジンをTypeScriptで実装したらプログラミング言語の実装みたいで面白かったので解説してみる

アルダグラムでエンジニアをしている @sukechannnn です！

開発に携わっている KANNAレポート は、Excelを取り込んでその見た目のまま帳票を電子化できるサービスで、いくつかのExcel関数にも対応しています。

以前 @watabee が登壇した際にその仕組みについて触れていますが、現状は数式の依存関係（他セルの参照や他セル数式の計算結果を利用して計算するなど）を深さ優先探索（DFS）によるトポロジカルソートで構築した上で、各数式の計算は math.js を利用して行っています。

https://speakerdeck.com/watabee/kanna-android-noji-shu-de-ke-ti-toqu-rizu-mi?slide=18

math.js は簡単に独自の数式を定義し計算できて便利なのですが、その柔軟さの代償として計算の度にパースして評価するため、どうしてもオーバーヘッドが大きくなってしまいます。KANNAレポートでも依存が5000個以上あるような関数はかなり遅くなってしまうという課題がありました。

高速化のためにできることを検討した結果、１回あたりの計算を速くする以外に方法がないという結論に至った^[1]ので、TypeScript で数式を評価する計算エンジンをゼロから実装しました。その結果めっちゃ速くなった（100倍くらい）のですが、実装内容がプログラミング言語の実装みたいで面白かったので、簡易版の実装を用いて解説してみようと思います。

（ちなみに私はプログラミング言語の処理系に特段詳しいわけではなく、概要をふんわり知ってるくらいなので、変なところがあればツッコミ大歓迎です！）
（今回の実装は Claude Code をフル活用してます。自分だけでゼロから実装するより100倍速かったです）

Excel数式の計算エンジンの解説

ここでは、四則演算とIF関数を例に、実装した計算エンジンがどのように動作するのかを解説します。

サンプルコードは以下のリポジトリに置いてあります。
https://github.com/sukechannnn/excel-formula-engine-example

どんな数式が実行可能かはテストコードをご確認ください。

概要

まずは全体像を掴んでみましょう。
今回実装した数式エンジンは、以下のような流れで動作します。

1. 構文解析（ANTLR）: 数式文字列を構文解析木 (Parse Tree) に変換
2. RPN変換: Parse Tree を逆ポーランド記法（RPN）に変換し、中間表現（IR）を生成
3. 実行（Stack VM）: RPNをスタックマシンで評価

ここでは、簡単化のために以下の実装を省いています。

• セルの参照先が数式
  • 例: A1=A2+1、A2=A3+1、A3=1 のような場合
  • 複数の数式の依存関係をトポロジカルソートして正しい順番に並び替える必要がある
  • 上記の例だと、A3: 1 -> A2: A3+1 = 1+1 = 2 -> A1: A2+1 = 2 + 1 = 3
• セルの範囲参照や、他シート参照
  • 例: =SUM(A1:A5) や =Sheet!A1

単一数式の処理フローは以下の通りです。

"=A1+B1*2"（数式文字列）
    ↓
[FormulaEngine.evaluate()]
    ↓
[Lexer (ANTLR4)] → トークン化
    ↓
["=", "A1", "+", "B1", "*", "2"]
    ↓
[Parser (ANTLR4)] → 構文解析
    ↓
      [+] （Parse Tree: 構文解析木）
     /   \
  [A1]   [*]
         / \
      [B1] [2]
    ↓
[FormulaToRPNConverter] → RPN変換 + 依存関係抽出
    ↓
    ├── RPN: ["A1", "B1", "2", "*", "+"] （逆ポーランド記法）
    └── 依存関係: ["A1", "B1"]
    ↓
[StackVM.evaluate()] → 実行
    ↓
    ├── 依存関係の値を取得（A1=10, B1=3）
    └── スタックで計算実行
        └── [10] [3] [2] → [10] [6] → [16]
    ↓
結果: 16

math.js が文字列をパースして AST を直接 Visitor 的に歩きながら評価するインタープリタ方式なのに対して、今回の実装はコンパイラ方式です。数式を事前にコンパイルして中間表現に変換することで、計算処理を高速化することができます。また、事前に依存関係を解決することで、関数の引数が他セル参照だったり、参照先のセルが関数でまた更に参照している...などの場合に対応することができます。

それでは、それぞれの処理について、より詳細に見てみましょう。

1. ANTLRによる構文解析

構文解析には ANTLR（ANother Tool for Language Recognition） というパーサージェネレータを活用しました。

実は、KANNAレポートではExcel数式の一部にしか対応していないため、その判定のためにバックエンドで既に ANTLR を利用していました（そして流用可能な完璧な定義でしたすごい）。今回はそれを利用しています。

ANTLRは文法を定義することで、字句解析器と構文解析器を生成できる非常に便利なツールです。ANTLRの文法の書き方自体は少し慣れが必要ですが、下の方がよりプリミティブな定義なので、下から読んでいくと理解しやすいです。

以下は、「四則演算, SUM, IF, セル参照（範囲参照なし）」に対応する例です。これをビルドすることで、FormulaLexer, FormulaParser, FormulaVisitor が生成されます。

Formula.g4

// 四則演算、SUM、IF、セル参照のみ対応
// SUM(A1,B1) は動くが、SUM(A1:B5) のような範囲参照には対応していない

grammar Formula;

formula
    : EQ? expr EOF
    ;

expr
    : additiveExpr ( (GT | LT | GTEQ | LTEQ | EQ | NEQ) additiveExpr )?
    ;

additiveExpr
    : additiveExpr (PLUS | MINUS) multiplicativeExpr
    | multiplicativeExpr
    ;

multiplicativeExpr
    : multiplicativeExpr (MUL | DIV) unaryExpr
    | unaryExpr
    ;

unaryExpr
    : (PLUS | MINUS)? primaryExpr
    ;

primaryExpr
    : ifFunction
    | sumFunction
    | cellRef
    | numberExpr
    | LPAREN expr RPAREN
    ;

ifFunction
    : IF LPAREN expr COMMA expr (COMMA expr)? RPAREN
    ;

sumFunction
    : SUM LPAREN (expr (COMMA expr)*)? RPAREN
    ;

cellRef
    : CELL_REF
    ;

numberExpr
    : NUMBER
    ;

// ===== Lexer =====
IF  : [Ii] [Ff] ;
SUM : [Ss] [Uu] [Mm] ;

EQ   : '=' ;
NEQ  : '<>' ;
GTEQ : '>=' ;
LTEQ : '<=' ;
GT   : '>' ;
LT   : '<' ;

PLUS : '+' ;
MINUS: '-' ;
MUL  : '*' ;
DIV  : '/' ;

LPAREN : '(' ;
RPAREN : ')' ;
COMMA  : ',' ;

CELL_REF : [A-Z]+ [1-9][0-9]* ;
NUMBER   : [0-9]+ ('.' [0-9]+)? ;

WS : [ \t\r\n]+ -> skip ;

例えば、EQ : '=' ; は「'=' を EQ というトークンとして認識する」という意味です。
ifFunction は IF(式,式,式?) を表します（? は省略可能という意味）。

additiveExpr は + と - を扱うためのルールです。演算子の優先順位を「どの層に置くか」で表現しており、multiplicativeExpr を additiveExpr の“下の層”に置くことで、*, / が +, - より先に計算されるようになります。
additiveExpr (PLUS | MINUS) multiplicativeExpr に着目すると、「自分自身 (additiveExpr) の後ろに + か - が来て、その後ろに掛け算・割り算の式が続く」という意味です。
例: 1 + 2 + 3 * 4 → (1 + 2) + (3 * 4)
| は or を表していて、加減がない場合はそのまま multiplicativeExpr に移譲します。

生成された FormulaLexer, FormulaParser, FormulaVisitor は以下のように利用します。

export function evaluate(
  formula: string,
  cellValues: Map<string, unknown>
): unknown {
  // lexer 用の入力ストリーム (数式文字列 を 1 文字ずつ読み取れるようにしたもの) を用意
  const inputStream = new CharStream(formula)

  // 字句解析: 文字 → 記号（トークン）の並び
  const lexer = new FormulaLexer(inputStream)

  // parser 用のトークンストリーム (Lexer が生成したトークンを順番に並べて保持する) を用意
  const tokenStream = new CommonTokenStream(lexer)

  // 構文解析: トークン列 → 構文解析木
  const parser = new FormulaParser(tokenStream)
  const tree = parser.formula()

  // --------- ここから下は後ほど解説 ---------

  // Parse Tree をRPNに変換
  const converter = new FormulaToRPNConverter()
  const ir = converter.convert(tree)

  // 評価コンテキストを作成
  const context: EvaluationContext = {
    dependencies: cellValues,
  }

  // StackVMで評価
  const vm = new StackVM()
  const result = vm.evaluate(ir.tokens, context)

  return result
}

const tree = parser.formula() で得られた Parse Tree を用いて、逆ポーランド記法（RPN）に変換します。次はそのRPN変換について見ていきます。

2. 逆ポーランド記法（RPN）変換

逆ポーランド記法（RPN、後置記法）とは、数式を記述する際に演算子（+, -, ×, ÷など）をオペランド（数字や変数）の後ろに置く記法のことです（ここからはRPNと書きます）。

例えば 10 + (20 * 30) という数式の場合、RPNに変換すると 10 20 30 * + になります。なぜRPNに変換するのかと言うと、RPNはスタックマシンで簡単に計算することができるからです（最後の方に出てきます）。

RPN変換の具体的な流れは、以下の通りです。

10 20 30 * +:

• 初期化: stack = []
• 1つ目はオペランドなのでpush: stack.push(10) = [10]
• 2つ目はオペランドなのでpush: stack.push(20) = [10, 20]
• 3つ目はオペランドなのでpush: stack.push(30) = [10, 20, 30]
• 4つ目は演算子なので、2つpopして計算してpush: stack.pop() * stack.pop() → 20 * 30 = 600 → stack.push(600) = [10, 600]
• 5つ目は演算子なので、2つpopして計算してpush: stack.pop() + stack.pop() → 10 + 600 = 610 → stack.push(610) = [610]
• stack.length === 1 なので、答えは 610

RPN変換の実装

概要が分かったところで、RPN変換の実装を見てみましょう。ここでは、主要なコードを抜粋しています。
全体のコードは以下をご確認ください。

https://github.com/sukechannnn/excel-formula-engine-example/blob/main/src/FormulaToRPNConverter.ts

types.ts

...

// RPNトークン
export interface RPNToken {
  type: TokenType
  value?: unknown
  argCount?: number // 関数の引数数
  offset?: number // ジャンプ命令のオフセット
}

// 中間表現（IR）
export interface IntermediateRepresentation {
  tokens: RPNToken[]
  dependencies: string[]
}

...

FormulaToRPNConverter.ts

import FormulaVisitor from "./antlr/generated/FormulaVisitor"
import { TokenType, RPNToken, IntermediateRepresentation } from "./types"
... (省略)

export class FormulaToRPNConverter extends FormulaVisitor<void> {
  private tokens: RPNToken[] = []
  private dependencies: Set<string> = new Set()

  // エントリーポイント
  convert(ctx: FormulaContext): IntermediateRepresentation {
    this.tokens = []
    this.dependencies = new Set()

    this.visit(ctx)
    return {
      tokens: this.tokens,
      dependencies: Array.from(this.dependencies),
    }
  }

  // 以下に実装してある visitXxx の処理に委譲する
  visitFormula = (ctx: FormulaContext): void => {
    const expr = ctx.expr()
    if (expr) {
      this.visit(expr)
    }
  }

  // Formula.g4 で定義した文法ルール expr に対応するノードを訪問したときに呼ばれる
  // 引数 ctx にはその expr ノードの情報が入っている
  visitExpr = (ctx: ExprContext): void => {
    const additiveExprs = ctx.additiveExpr_list()

    if (additiveExprs.length === 1) {
      // 比較演算子なし
      this.visit(additiveExprs[0])
    } else if (additiveExprs.length === 2) {
      // 比較演算子ありの場合は左右の式を先に評価
      this.visit(additiveExprs[0])
      this.visit(additiveExprs[1])

      // 比較演算子を push
      if (ctx.GT()) {
        this.tokens.push({ type: TokenType.GREATER_THAN })
      } else if (ctx.LT()) {
        this.tokens.push({ type: TokenType.LESS_THAN })
      } else if (ctx.GTEQ()) {
        this.tokens.push({ type: TokenType.GREATER_EQUAL })
      } else if (ctx.LTEQ()) {
        this.tokens.push({ type: TokenType.LESS_EQUAL })
      } else if (ctx.EQ()) {
        this.tokens.push({ type: TokenType.EQUAL })
      } else if (ctx.NEQ()) {
        this.tokens.push({ type: TokenType.NOT_EQUAL })
      }
    }
  }

  // Formula.g4 で定義した文法ルール additiveExpr に対応するノードを訪問したときに呼ばれる
  // 引数 ctx にはその additiveExpr ノードの情報が入っている（以下同様）
  visitAdditiveExpr = (ctx: AdditiveExprContext): void => {
    // ANTLR4の左再帰処理
    const additiveExpr = ctx.additiveExpr()
    const multiplicativeExpr = ctx.multiplicativeExpr()

    if (additiveExpr && multiplicativeExpr) {
      // 左側の式を先に処理
      this.visit(additiveExpr)
      // 右側の式を処理
      this.visit(multiplicativeExpr)

      // 演算子を追加
      if (ctx.PLUS()) {
        this.tokens.push({ type: TokenType.ADD })
      } else if (ctx.MINUS()) {
        this.tokens.push({ type: TokenType.SUBTRACT })
      }
    } else if (multiplicativeExpr) {
      // 乗除算式のみの場合
      this.visit(multiplicativeExpr)
    }
  }

...

  // セル参照だったら、依存 (dependencies) に追加した上でトークンを push
  visitCellRef = (ctx: CellRefContext): void => {
    const ref = ctx.getText()

    // 通常のセル参照（シート参照なし）
    const cleanRef = ref.replace(/\$/g, "") // $A$1 -> A1 に直してる
    this.dependencies.add(cleanRef)
    this.tokens.push({ type: TokenType.CELL_REF, value: cleanRef })
  }

  // 数値が来たらそのままトークンを push
  visitNumberExpr = (ctx: NumberExprContext): void => {
    const value = parseFloat(ctx.getText())
    this.tokens.push({ type: TokenType.NUMBER, value })
  }

...

  visitIfFunction = (ctx: IfFunctionContext): void => {
    const exprs = ctx.expr_list()
    if (!exprs || exprs.length === 0) return

    // 条件式を評価
    this.visit(exprs[0])

    // 条件がfalseならelseブランチへジャンプ
    const jumpToElseIndex = this.tokens.length
    this.tokens.push({ type: TokenType.JUMP_IF_FALSE, offset: 0 }) // 後で更新

    // thenブランチ
    if (exprs[1]) {
      this.visit(exprs[1])
    }

    // elseブランチをスキップ
    const jumpToEndIndex = this.tokens.length
    this.tokens.push({ type: TokenType.JUMP, offset: 0 }) // 後で更新

    // elseブランチの開始位置
    const elseStartIndex = this.tokens.length

    // elseブランチ（省略可能）
    if (exprs.length > 2 && exprs[2]) {
      this.visit(exprs[2])
    } else {
      this.tokens.push({ type: TokenType.BOOLEAN, value: false })
    }

    // ジャンプオフセットを更新
    this.tokens[jumpToElseIndex].offset = elseStartIndex - jumpToElseIndex - 1
    this.tokens[jumpToEndIndex].offset = this.tokens.length - jumpToEndIndex - 1
  }
}

処理の流れをざっくり説明すると、

• convert メソッドで this.visit(ctx) すると、引数 ctx が FormulaContext なのでまずは visitFormula が呼ばれる
• visitFormula 内の ctx.expr() は ExprContext 型を返すので、this.visit(expr) で visitExpr が呼ばれる
• visitExpr 内では ctx.additiveExpr_list() が AdditiveExprContext を返すので、 this.visit(additiveExprs[0]) で visitAdditiveExpr が呼ばれる
• つづく...

という風に、this.visit() の引数に与える型に応じてどの関数が呼ばれるかが判断されます（Visitor パターン）。

最初の convert() メソッドの引数は ANTLR がパースした Parse Tree で、数式をパースして得られる構文解析木（jsのオブジェクト）です。Parse Tree の各ノードが AdditiveExprContext や NumberExprContext、SumFunctionContext などなどになっているので、Visitor パターンで走査できるのです。

ここからは visitAdditiveExpr について説明します。

visitAdditiveExpr (足し算引き算)

Formula.g4 では additiveExpr は次のように定義されています。
additiveExpr, 演算子, multiplicativeExpr のセットか、multiplicativeExpr のみを返すということが書いてあります。

additiveExpr
    : additiveExpr (PLUS | MINUS) multiplicativeExpr
    | multiplicativeExpr
    ;

additiveExpr と multiplicativeExpr の両方を返す場合を見てみましょう。
この場合、左辺の additiveExpr を visit するため、また visitAdditiveExpr が呼ばれ再帰処理に入ります。

ANTLR は左再帰を自動的に右再帰に変換し、さらに左結合性を保持してくれるため、10 / 2 * 5 は ((10 / 2) * 5) = 25 として正しく評価され、(10 / (2 * 5)) = 1 とはなりません。

例: 1 + 2 - 3 の解析

1.解析木の構造

        additiveExpr (1 + 2 - 3)
        /          |           \
    additiveExpr    '-'    multiplicativeExpr
    (1 + 2)                     (3)
    /    |    \
additiveExpr '+' multiplicativeExpr
    (1)              (2)

2.ビジターメソッドの呼び出し順序

// 1回目: 1 + 2 - 3 全体
visitAdditiveExpr() {
  additiveExpr = (1 + 2)  // 存在する
  multiplicativeExpr = (3) // 存在する

  // 左側を先に処理（再帰呼び出し）
  visit(additiveExpr)  // → 2回目の呼び出しへ

  // 右側を処理
  visit(multiplicativeExpr)  // 3を処理

  // 演算子を追加
  tokens.push({ type: TokenType.SUBTRACT })
}

// 2回目: 1 + 2 の部分
visitAdditiveExpr() {
  additiveExpr = (1)      // 存在する
  multiplicativeExpr = (2) // 存在する

  visit(additiveExpr)  // → 3回目の呼び出しへ
  visit(multiplicativeExpr)  // 2を処理
  tokens.push({ type: TokenType.ADD })
}

// 3回目: 1 の部分
visitAdditiveExpr() {
  additiveExpr = null      // 存在しない
  multiplicativeExpr = (1) // 存在する

  // ベースケース
  visit(multiplicativeExpr)  // 1を処理
}

このように処理することで、以下のような処理の流れが形成され、RPN が得られます。

1. "1"を追加
2. "2"を追加
3. "+"を追加（1 + 2の演算子）
4. "3"を追加
5. "-"を追加（(1+2) - 3の演算子）

得られたトークン:
[
  { type: TokenType.NUMBER, value: 1 },       // 1をスタックに
  { type: TokenType.NUMBER, value: 2 },       // 2をスタックに
  { type: TokenType.ADD },                    // 加算 (1 + 2)
  { type: TokenType.NUMBER, value: 3 },       // 3をスタックに
  { type: TokenType.SUBTRACT }                // 減算 ((1+2) - 3)
]

visitMultiplicativeExpr もまた同じように処理を行い、その先に関数（SUM や IF）の処理があります。
IF関数をRPN変換する処理が面白いので、取り上げてみましょう。

visitIfFunction（IF関数）

visitIfFunction の実装を再掲します。

  visitIfFunction = (ctx: IfFunctionContext): void => {
    const exprs = ctx.expr_list()
    if (!exprs || exprs.length === 0) return

    // 条件式を評価
    this.visit(exprs[0])

    // 条件がfalseならelseブランチへジャンプ
    const jumpToElseIndex = this.tokens.length
    this.tokens.push({ type: TokenType.JUMP_IF_FALSE, offset: 0 }) // 後で更新

    // thenブランチ
    if (exprs[1]) {
      this.visit(exprs[1])
    }

    // elseブランチをスキップ
    const jumpToEndIndex = this.tokens.length
    this.tokens.push({ type: TokenType.JUMP, offset: 0 }) // 後で更新

    // elseブランチの開始位置
    const elseStartIndex = this.tokens.length

    // elseブランチ（省略可能）
    if (exprs.length > 2 && exprs[2]) {
      this.visit(exprs[2])
    } else {
      this.tokens.push({ type: TokenType.BOOLEAN, value: false })
    }

    // ジャンプオフセットを更新
    this.tokens[jumpToElseIndex].offset = elseStartIndex - jumpToElseIndex - 1
    this.tokens[jumpToEndIndex].offset = this.tokens.length - jumpToEndIndex - 1
  }

IF関数は IF(condition, left, right) と３つの引数を取る関数です（right は省略可能）。condition が TRUE なら left を、FALSE なら right を実行します。この時、実行しなくて良い方の関数をスキップできれば高速化できます（何も工夫しないと全部実行しちゃいます）。それを実現するために、condition の結果に応じて、TRUE ならそのまま left を実行、FALSE なら right までジャンプ、right が省略されてたらその次の式にジャンプするように実装しています。

    // 条件がfalseならelseブランチへジャンプ
    const jumpToElseIndex = this.tokens.length
    this.tokens.push({ type: TokenType.JUMP_IF_FALSE, offset: 0 }) // offsetは後で更新
    ...
    // elseブランチをスキップ
    const jumpToEndIndex = this.tokens.length
    this.tokens.push({ type: TokenType.JUMP, offset: 0 }) // offsetは後で更新
    ...
    // elseブランチの開始位置
    const elseStartIndex = this.tokens.length

    // ジャンプオフセットを更新
    this.tokens[jumpToElseIndex].offset = elseStartIndex - jumpToElseIndex - 1
    this.tokens[jumpToEndIndex].offset = this.tokens.length - jumpToEndIndex - 1

上記実装の offset が「どの位置にジャンプするか」を表しています。
elseStartIndex - jumpToElseIndex - 1 は else の先頭、this.tokens.length - jumpToEndIndex - 1 は else を飛ばして次の処理に飛ばすための offset です。
最後に -1 しているのは、「現在の JUMP 命令の次」から数えて何命令先か という相対距離に合わせるためのオフバイワン調整です。

例えば、IF(A1 > 1, 1+1, 2+2) をRPN変換すると、以下のようなトークンが得られます。

[
  // 1. 条件式の評価 (A1 > 1)
  { type: TokenType.CELL_REF, value: "A1" },      // A1の値を取得
  { type: TokenType.NUMBER, value: 1 },           // 1をスタックに
  { type: TokenType.GREATER_THAN },               // 比較演算 (>)

  // 2. IF文の制御フロー
  { type: TokenType.JUMP_IF_FALSE, offset: 4 },   // FALSEならoffset分ジャンプ

  // 3. thenブランチ (1+1)
  { type: TokenType.NUMBER, value: 1 },           // 1をスタックに
  { type: TokenType.NUMBER, value: 1 },           // 1をスタックに
  { type: TokenType.ADD },                        // 加算

  // 4. elseブランチをスキップ
  { type: TokenType.JUMP, offset: 3 },            // elseブランチを飛び越える

  // 5. elseブランチ (2+2)
  { type: TokenType.NUMBER, value: 2 },           // 2をスタックに
  { type: TokenType.NUMBER, value: 2 },           // 2をスタックに
  { type: TokenType.ADD }                         // 加算
]

TokenType.JUMP_IF_FALSE の offset が 4 なのは、その次の { type: TokenType.NUMBER, value: 1 } ~ { type: TokenType.JUMP, offset: 3 } をスキップするように、スキップするトークンの数を数えているからです（TokenType.JUMP も同様）。

さて、ここまでで数式の文字列をRPNに変換できました。最後は生成したRPNトークンを使って、スタックマシンで計算を行います。

3. スタックで計算実行

最後に、生成されたRPNトークンをスタックマシン（Stack VM）で評価します。スタックマシンは、スタックと呼ばれる LIFO（Last In First Out）のデータ構造を使用して計算を行う仮想マシンです。今回は TypeScript の配列を用いて実装します。

スタックマシンは以下の要素で構成されます：

• スタック: 値や計算の中間結果を保持
• プログラムカウンタ（PC）: 現在実行中の命令の位置
• 評価コンテキスト: セル参照の値などの外部データ

StackVMの実装

それでは、実装を見てみましょう。ここでも、主要な部分を抜粋しています。
全体のコードは以下をご確認ください。

https://github.com/sukechannnn/excel-formula-engine-example/blob/main/src/StackVM.ts

StackVM.ts

export class StackVM {
  private stack: unknown[] = []
  private pc = 0 // プログラムカウンタ

  evaluate(tokens: RPNToken[], context: EvaluationContext): unknown {
    this.stack = []
    this.pc = 0

    while (this.pc < tokens.length) {
      const token = tokens[this.pc]
      
      // トークンの種類に応じて処理
      switch (token.type) {
        case TokenType.NUMBER:
          this.stack.push(token.value)
          break
        
        case TokenType.ADD:
          const b = this.popNumber()
          const a = this.popNumber()
          this.stack.push(a + b)
          break
        // ... 他の演算子も同様
      }
      
      this.pc++
    }
    
    return this.stack[0]
  }
}

実装としては比較的シンプルではないでしょうか。
具体的な実行例を見た方がイメージが付きやすいと思うので、見てみましょう。

四則演算

A1 + B1 * 2（A1=10, B1=3）を実行すると、以下のような流れで計算が行われます。

RPNトークン列:

["A1", "B1", "2", "*", "+"]

実行ステップ:

PC	トークン	処理	スタック
0	CELL_REF("A1")	A1の値(10)をプッシュ	[10]
1	CELL_REF("B1")	B1の値(3)をプッシュ	[10, 3]
2	NUMBER(2)	2をプッシュ	[10, 3, 2]
3	MULTIPLY	3と2をポップ、6をプッシュ	[10, 6]
4	ADD	10と6をポップ、16をプッシュ	[16]

結果: 16

セル参照は CELL_REF トークンの場合に依存Mapを参照するだけです。
それ以外は、特に難しい部分はないかなと思います。

IF関数の制御フロー

次は、IF関数を見てみましょう。
IF関数では条件分岐のためにジャンプ命令を使用しますが、そのためにプログラムカウンタ (PC) を利用します。

IF(A1 > 1, 1+1, 2+2)（A1=2）の実行：

RPNトークン列:

[
  CELL_REF("A1"),           // PC=0
  NUMBER(1),                // PC=1
  GREATER_THAN,             // PC=2
  JUMP_IF_FALSE(offset:4),  // PC=3
  NUMBER(1),                // PC=4
  NUMBER(1),                // PC=5
  ADD,                      // PC=6
  JUMP(offset:3),           // PC=7
  NUMBER(2),                // PC=8
  NUMBER(2),                // PC=9
  ADD                       // PC=10
]

実行フローは以下のようになります。

TRUE (A1=2) の場合:

1. PC=0-2: A1(2) > 1 → TRUEをスタックにプッシュ
2. PC=3: JUMP_IF_FALSE → TRUEなのでジャンプしない
3. PC=4-5: 1, 1をスタックにプッシュ
4. PC=6: ADD → 1+1=2をスタックにプッシュ
5. PC=7: JUMP → PC=8-10をスキップして終了
6. 結果: 2

FALSE (A1=0) の場合:

1. PC=0-2: A1(0) > 1 → FALSEをスタックにプッシュ
2. PC=3: JUMP_IF_FALSE → FALSEなのでPC+4ジャンプ（PC=8へ）
3. PC=8-9: 2, 2をスタックにプッシュ
4. PC=10: ADD → 2+2=4をスタックにプッシュ
5. 結果: 4

RPN変換のところで offset について説明しましたが、FALSE の時に利用しているのが分かると思います。このジャンプ処理により、必要のない計算をスキップすることができるのですね。

まとめ

Excelの数式を再現する数式エンジンの実装について解説してみました。特にIF関数は条件分岐を実現していることもあり、プログラミング言語っぽくて面白かったのではないでしょうか。

実際に、IF関数は math.js で実装した時から難しく、math.js の時には上記のジャンプ処理を実装することができませんでした（つまり、ジャンプしない場合よりも1.5倍の計算量が必要だった）。今回の実装でそこが改善できたのは、個人的にとても嬉しかったです。

また、RPNとスタックマシンを用いた計算は、多くのプログラミング言語で利用されています。今回のExcelの計算エンジンの実装を通して、プログラミング言語が動作する原理の一端を体験してもらえたら嬉しいです。

AIコーディング的な話で言うと、今回のように理論が確立されてる機能の開発はめちゃ得意なようで、爆速でコード生成してくれました。それでもAIが書いたものが一発で動くわけではなく、エッジケースの対応や独自仕様の実装などは自分で行う必要がありました。コードを読んで理解し修正する…というのは変わらず必要ですね。

脚注

1. WebWorkerで処理するようにしたり、キャッシュを入れたりという改善は行った上での結論です