Rubyで新しいプログラミング言語を作る：インタプリタ編

GitHubで完全なソースコードを公開中

Stoffleプログラミング言語の完全な実装はGitHubで公開しています。バグを見つけたり、疑問点がある場合は、ぜひIssueを立ててください。

この記事では、Rubyだけで作られたおもちゃのプログラミング言語「Stoffle」のインタプリタ実装を始めます。このプロジェクトについては、シリーズ第1回目の記事で詳しく紹介しているので、まだ読んでいない方はそちらもチェックしてみてください。

今回構築するのは、いわゆる「ツリーを辿るインタプリタ（tree-walk interpreter）」と呼ばれるものです。前回の記事では、フラットなトークンの列を木構造（抽象構文木、略してAST）に変換するパーサーを作りました。お察しのとおり、今回のインタプリタの役割は、パーサーが生成したASTをたどりながら、Stoffleプログラムに命を吹き込むことです。個人的には、この最後のステップこそが言語実装の旅の中で最もワクワクする部分だと感じています。インタプリタを組み上げると、すべてのピースがついにかみ合い、Stoffleのプログラムが実際に動く姿を目撃できるのです！

インタプリタの実装は2回に分けて解説します。この第1部では、基本となる機能——変数、条件分岐、単項演算子・二項演算子、データ型、コンソールへの出力——を動くようにします。より濃い内容（関数定義、関数呼び出し、ループなど）は、インタプリタ編の最終回である次回に取っておきます。

レキサーとパーサーの復習

インタプリタの実装に取りかかる前に、これまでの記事で何をしてきたのかを簡単におさらいしましょう。まず、生のソースコードをトークンに変換するレキサーを作りました。次に、トークンを木構造（AST）へと変形させるパーサーを実装しました。まとめると、ここまでで観察してきた変換の流れは以下のとおりです。

状態0：ソースコード

my_var = 1

状態1：レキサーがソースコードをトークン列に変換

[:identifier, :'=', :number]

状態2：パーサーがトークンを抽象構文木（AST）に変換

鍵は「木を歩くこと」

ASTが手に入ったので、次の仕事はこの構造を歩き回るコードを書くことです。ASTの各ノードが記述している内容に命を与えるRubyのコードを書かなければなりません。たとえば変数束縛を表すノードがあるなら、代入式の右辺の評価結果をどこかに保存し、その保存領域を変数名と関連付けて（名前を通じてアクセスできるようにして）おくRubyコードが必要になります。

これまでのシリーズと同様に、サンプルプログラムを処理する際に関わる重要なコード行を一つひとつ追いかけながら、実装を掘り下げていきます。今回解釈対象とするStoffleコードはこちらです。

num = -2
if num > 0
  println("The number is greater than zero.")
else
  println("The number is less than or equal to zero.")
end

そして、同じプログラムから生成されたASTがこちらです。

歩き出しの一歩目

前回の記事を覚えている方なら、StoffleのASTは必ずAST::Programノードをルートとすることをご存じでしょう。このルートには通常、複数の子ノードがあります。浅いノードもあれば（単純な変数代入のASTを思い浮かべてください）、かなり深い部分木のルートになるノードもあります（本体に多数の行を含むループなどを思い浮かべてください）。インタプリタに渡されたASTを歩き始めるために必要なRubyコードがこちらです。

module Stoffle
  class Interpreter
    attr_reader :program, :output, :env

    def initialize
      @output = []
      @env = {}
    end

    def interpret(ast)
      @program = ast

      interpret_nodes(program.expressions)
    end

    private

    def interpret_nodes(nodes)
      last_value = nil

      nodes.each do |node|
        last_value = interpret_node(node)
      end

      last_value
    end

    def interpret_node(node)
      interpreter_method = "interpret_#{node.type}"
      send(interpreter_method, node)
    end

    #...

  end
end

Interpreterがインスタンス化されると、すぐに2つのインスタンス変数@outputと@envを作成します。前者の役割は、プログラムが出力した内容を時系列順に記録することです。この情報があると、自動テストを書いたりデバッグしたりするときに非常に便利です。@envの役割は少し異なります。これは「environment（環境）」への言及としてこう名付けました。名前が示唆するとおり、その機能は実行中のプログラムの状態を保持することです。その一つとして、識別子（たとえば変数名）と現在の値との束縛を実現します。

#interpret_nodesメソッドは、ルートノード（AST::Program）のすべての子をループ処理し、個々のノードに対して#interpret_nodeを呼び出します。

#interpret_nodeはシンプルですが、興味深いメソッドです。ここではRubyのメタプログラミングを少し使って、現在扱っているノードの種類に応じた適切なメソッドを呼び出します。たとえばAST::VarBindingノードの場合は、#interpret_var_bindingメソッドが呼ばれる仕組みです。

避けて通れない変数の話

サンプルプログラムのASTで最初に解釈すべきノードはAST::VarBindingです。その@leftはAST::Identifier、@rightはAST::UnaryOperatorになっています。変数束縛を解釈するメソッドを見てみましょう。

def interpret_var_binding(var_binding)
  env[var_binding.var_name_as_str] = interpret_node(var_binding.right)
end

ご覧のとおり、非常に単純です。@envハッシュにキーと値のペアを追加（または上書き）しているだけです。

キーは変数名です（#var_name_as_strはvar_binding.left.nameと等価なヘルパーメソッドです）。現時点では、すべての変数はグローバルです。スコープの処理は次回の記事で扱います。

値は、代入式の右辺にある式を解釈した結果です。そのために、ここでも#interpret_nodeを使います。右辺はAST::UnaryOperatorなので、次に呼ばれるのは#interpret_unary_operatorメソッドです。

def interpret_unary_operator(unary_op)
  case unary_op.operator
  when :'-'
    -(interpret_node(unary_op.operand))
  else # :'!'
    !(interpret_node(unary_op.operand))
  end
end

Stoffleがサポートする単項演算子（-と!）のセマンティクスはRubyと同じです。そのため、実装はこれ以上ないほどシンプルです。オペランドを解釈した結果に、Rubyの-演算子を適用するだけです。お馴染みの#interpret_nodeがまた登場しますね。プログラムのASTを思い出せば、-のオペランドはAST::Number（数値の2）だったはずです。というわけで、次の立ち寄り先は#interpret_numberです。

def interpret_number(number)
  number.value
end

#interpret_numberの実装は朝飯前です。数値リテラルの内部表現としてRubyのFloatを採用した判断（これはレキサーの段階での話です！）が、ここで報われます。AST::Numberノードの@valueには、望んでいた数値の内部表現がすでに格納されているので、それを取り出すだけです。

これで、AST::Programの最初の直接の子の解釈が完了しました。プログラム全体の解釈を終えるには、もう少し手強いもう一方の子——AST::Conditional型のノード——を処理しなければなりません。

条件分岐を解釈する

#interpret_nodesに戻ると、頼れる相棒の#interpret_nodeが再び呼び出され、AST::Programの次の直接の子を解釈します。

def interpret_nodes(nodes)
  last_value = nil

  nodes.each do |node|
    last_value = interpret_node(node)
  end

  last_value
end

AST::Conditionalを解釈する担当メソッドは#interpret_conditionalです。その前に、AST::Conditional自体の実装をおさらいしておきましょう。

class Stoffle::AST::Conditional < Stoffle::AST::Expression
  attr_accessor :condition, :when_true, :when_false

  def initialize(cond_expr = nil, true_block = nil, false_block = nil)
    @condition = cond_expr
    @when_true = true_block
    @when_false = false_block
  end

  def ==(other)
    children == other&.children
  end

  def children
    [condition, when_true, when_false]
  end
end

整理すると、@conditionは真または偽と評価される式を保持し、@when_trueは条件が真だった場合に実行される1つ以上の式からなるブロック、@when_false（ELSE節）は条件が偽だった場合に実行されるブロックを保持します。

それでは、#interpret_conditionalを見てみましょう。

def interpret_conditional(conditional)
  evaluated_cond = interpret_node(conditional.condition)

  # We could implement the line below in a shorter way, but better to be explicit about truthiness in Stoffle.
  if evaluated_cond == nil || evaluated_cond == false
    return nil if conditional.when_false.nil?

    interpret_nodes(conditional.when_false.expressions)
  else
    interpret_nodes(conditional.when_true.expressions)
  end
end

Stoffleにおける真偽性（truthiness）はRubyと同じです。つまり、Stoffleではnilとfalseだけが偽であり、条件に渡されたその他のあらゆる値は真とみなされます。

まず、conditional.conditionが保持する式を解釈して条件を評価します。どんなノードを扱っているのか、もう一度プログラムのASTを見て確認してみましょう。

どうやらAST::BinaryOperator（num > 0で使われている>）のようです。よし、いつもの道筋ですね。まず#interpret_nodeが呼ばれ、今度は#interpret_binary_operatorが呼ばれます。

def interpret_binary_operator(binary_op)
  case binary_op.operator
  when :and
    interpret_node(binary_op.left) && interpret_node(binary_op.right)
  when :or
    interpret_node(binary_op.left) || interpret_node(binary_op.right)
  else
    interpret_node(binary_op.left).send(binary_op.operator, interpret_node(binary_op.right))
  end
end

論理演算子（andとor）も二項演算子とみなせるので、ここで一緒に処理します。セマンティクスがRubyの&&や||と同等なので、上記のとおり実装は非常に簡単です。

次が、このメソッドの中で最も注目すべき部分です。ここではその他すべての二項演算子（>を含む）を処理します。ここでは、Rubyの動的な性質を味方につけて、とても簡潔なソリューションを実現できます。Rubyでは、二項演算子は演算に参加するオブジェクトのメソッドとして利用できるのです。

-2 > 0           # is equivalent to
-2.send(:'>', 0) # this
# and the following line would be a general solution,
# very similar to what we have in the interpreter
operand_1.send(binary_operator, operand_2)

二項演算子を冗長に実装する場合

ご覧のとおり、二項演算子の実装は非常に簡潔です。しかし、Rubyほど動的な言語でなかったり、演算子のセマンティクスがRubyとStoffleで異なったりする場合は、このような書き方はできません。

もし言語設計者・実装者としてそんな状況に陥ったら、シンプルながら（あまりエレガントではない）代替策に頼ることができます。それはswitch文を使う方法です。今回のケースなら、実装は次のようになるでしょう。

# ... inside #interpret_binary_operator ...

case binary_op.operator
when :'+'
  interpret_node(binary_op.left) + interpret_node(binary_op.right)
# ... other operators
end

#interpret_conditionalに戻る前に、見落としがないかちょっと寄り道しておきましょう。解釈中のプログラムを覚えていますか？　直前に見た比較（二項演算子>を使う箇所）では、num変数が使われていました。あの比較の左オペランド、つまりnum変数に格納された値は、どうやって取得していたのでしょうか？　それを担うのが#interpret_identifierメソッドで、その実装は至ってシンプルです。

def interpret_identifier(identifier)
  if env.has_key?(identifier.name)
    env[identifier.name]
  else
    # Undefined variable.
    raise Stoffle::Error::Runtime::UndefinedVariable.new(identifier.name)
  end
end

さて、#interpret_conditionalに戻りましょう。今回の小さなプログラムでは、条件はRubyのfalseと評価されました。この値を使って、条件分岐のIF側とELSE側のどちらを実行すべきかを決めます。今回はELSE側を解釈することになり、対応するコードブロックはconditional.when_falseに格納されています。ここにあるのはAST::Blockで、ASTのルートノード（AST::Program)によく似ています。ブロックも同様に、解釈すべき式を多数持っている可能性があります。そのため、ここでも#interpret_nodesを使うのです。

def interpret_conditional(conditional)
  evaluated_cond = interpret_node(conditional.condition)

  # We could implement the line below in a shorter way, but better to be explicit about truthiness in Stoffle.
  if evaluated_cond == nil || evaluated_cond == false
    return nil if conditional.when_false.nil?

    interpret_nodes(conditional.when_false.expressions)
  else
    interpret_nodes(conditional.when_true.expressions)
  end
end

次に処理すべきASTノードはAST::FunctionCallです。関数呼び出しを解釈する担当メソッドは#interpret_function_callです。

def interpret_function_call(fn_call)
  return if println(fn_call)
end

冒頭で述べたとおり、関数定義と関数呼び出しは次回の記事で扱います。そのため、ここでは関数呼び出しの特殊なケースだけを実装します。私たちの小さなおもちゃの言語では、printlnをランタイムの一部として提供し、インタプリタ内に直接実装しています。このプロジェクトの目的と範囲を考えれば、十分に妥当なソリューションです。

def println(fn_call)
  return false if fn_call.function_name_as_str != 'println'

  result = interpret_node(fn_call.args.first).to_s
  output << result
  puts result
  true
end

AST::FunctionCallの最初の（そして唯一の）引数はAST::Stringで、これは#interpret_stringによって処理されます。

def interpret_string(string)
  string.value
end

#interpret_stringは、#interpret_numberとまったく同じパターンです。AST::Stringにはすぐに使える状態のRuby文字列がすでに格納されているので、取り出すだけです。

さて、#printlnに戻りましょう。

def println(fn_call)
  return false if fn_call.function_name_as_str != 'println'

  result = interpret_node(fn_call.args.first).to_s
  output << result
  puts result
  true
end

関数の引数（Ruby文字列に変換済み）をresultに格納した後、あと2つのステップが残っています。まず、コンソールに出力しようとしている内容を@outputに保存します。前述のとおり、これは何が（どんな順序で）出力されたのかを簡単に確認できるようにするためです。これがあると、インタプリタのデバッグやテストがぐっと楽になります。最後に、コンソールへの出力自体はRubyのputsを使って実装します。

いざ、実行

Stoffleの骨格を実装するのに必要な要素はすべて見てきたので、簡単な実行ファイルを作って、インタプリタの動作を確かめてみましょう。

#!/usr/bin/env ruby

require_relative '../lib/stoffle'

path = ARGV[0]
source = File.read(path)
lexer = Stoffle::Lexer.new(source)
parser = Stoffle::Parser.new(lexer.start_tokenization)
interpreter = Stoffle::Interpreter.new

interpreter.interpret(parser.parse)

exit(0)

TIP： どこからでもStoffleのインタプリタを使えるようにするには、この実行ファイルをPATHに追加しておくことを忘れないでください。

ついにプログラムを実行する瞬間がやってきました。すべてが正しく動いていれば、「The number is less than or equal to zero」という文字列がコンソールに表示されるはずです。インタプリタを実行すると、まさにそのとおりになりました。

TIP： インタプリタをインストール済みの方は、サンプルプログラムのnum変数をゼロより大きい数値に変更してみてください。期待どおり、今度はIF側の分岐が実行され、「The number is greater than zero」という文字列が出力されます。

まとめ

この記事では、Stoffleインタプリタの第一歩を踏み出しました。変数、条件分岐、単項・二項演算子、データ型、コンソール出力といった言語の基本を処理できるだけのインタプリタを実装しました。次回のインタプリタ編最終回では、おもちゃの言語を設計どおりに動かすために残された要素——変数のスコープ、関数定義、関数呼び出し、そしてループ——に取り組みます。記事を読んで楽しんでいただけたなら嬉しいです（書いた私自身、とても楽しかったです！）。それでは、シリーズ次回の記事でお会いしましょう！