型付きRubyでパーサを書く（前編）

K-Ruby という鹿児島のRubyコミュニティの忘年LT大会でRBSを使ってみた話をします。オンラインですが、九州盛り上げていきましょう！

k-ruby.connpass.com

それはそれとしてRBSというものに今回ちゃんと触れるので、触れた記録を雑にでも残していこうと思い、ブログを書きます。どれくらい後学のためになるのかならないのかわかりませんが、触ってみたライブな感想をなるべく残しておくのは意味があるでしょう、と。

@yoshikouki さんには「RailsにRBSを入れる方法を教えてください！」って言われてて、俺にRailsの話を聞くのか... って思ったんですけど、 まあその辺の面白そうなトピックは @yoshikouki さんのために取っておこうと思うので、僕はもうちょっと簡単なプログラム、そう、 プログラミング言語のパーサ をRubyで、型付きで書こうと思いました。

最初に諸注意

このエントリはただの作業メモで、この通りに実装を進めたら動くような書き方をしていません。前半で残したコードや型が後半で細かく変わってるということがふつうにあるし、全ての修正を記録していません。

一応というか、最終的な実装は以下のリポジトリに残してあります。それを見比べながら読み解く風になるでしょう。

github.com

あくまで「型付けRubyの雰囲気」を感じ取り、皆様が実際に型をドライブしながら書き進めていく際のシャドーイングに役立てばと思います（本当に？）*1。

また、「Rubyの型ってどうなの？」というところだけ知りたければ、後編をいきなり読んでもいいと思います。いずれにせよ個人の感想ですのでご留意ください。

udzura.hatenablog.jp

言語の文法

実装しようとする言語の文法です。

Luaをベースに、実装量を抑えるためにめちゃくちゃ簡素な文法にしました。そうですね、軽量なLua、 Klua (ｹｰﾙｱ) とでも名付けますか...。

トークン

Kluaは以下のトークンを持ちます。トークンってどういう記法で書くもんなんでしょうか。まあ...雰囲気で...正規表現風に。

// Tokens
tName -> [a-zA-Z_][a-zA-Z0-9_]*
tNumber -> [0-9]*
tLiteralString -> ".*"
tReserved -> local | if | then | else | end |
             and | or | not
tPunct -> + | - | \* | / |
         < | > | == | ~= |
         = | , | ; | ( | )

このトークンを使って以下の文法を持ちます。{ ... } は0回以上の繰り返し、 [ ... ] は0または1回繰り返しです。

// eBNF
block ::= {stat}
stat ::= varstat | assignstat | funcallstat | ifstat
varstat ::= local var [‘=’ exp] ‘;’
assignstat ::= var ‘=’ exp ‘;’
funcallstat ::= functioncall ‘;’
ifstat ::= if exp then block [else block] end ‘;’

exp ::= binary
binary ::= unary {binop unary}
unary ::= unop unary | functioncall | primary
functioncall ::=  primary args
primary ::= nil | false | true | tNumeral | tLiteralString |
            ‘(’ exp ‘)’ | var
var ::= tName

args ::=  ‘(’ [exp] ‘)’
binop ::=
         ‘+’ | ‘-’ | ‘*’ | ‘/’ |
         ‘<’ | ‘>’ | ‘==’ | ‘~=’ |
         and | or
unop ::= ‘-’ | not

見ての通り演算子の優先順位がない。関数は呼べるけど定義できないのでプリセットされたものしか使えない。

早速書き始める

Rubyは3.0.2で、まず klua というgemのプロジェクトを作ります。

$ bundle gem klua # rubocopは一旦なしで。
Creating gem 'klua'...
....
Initializing git repo in /usr/local/ghq/github.com/udzura/klua
      create  klua/Gemfile
      create  klua/lib/klua.rb
      create  klua/lib/klua/version.rb
      create  klua/klua.gemspec
      create  klua/Rakefile
      create  klua/README.md
      create  klua/bin/console
      create  klua/bin/setup
      create  klua/.gitignore
      create  klua/.github/workflows/main.yml
Gem 'klua' was successfully created. For more information on making a RubyGem visit https://bundler.io/guides/creating_gem.html

$ cd klua
$ emacs lib/klua.rb

最初に、 klua.rb を以下のように書く。

module Klua
  class Token
    def initialize(type, value)
      @type = type
      @value = value
    end
    attr_reader :type, :value
  end

  class Node
    def initialize(type, nodes, term)
      @type = type
      @nodes = nodes
      @term = term
    end
    attr_reader :type, :nodes, :term
  end

  class Root < Node
    def initialize(root)
      @root = root
      @type = :root
      @nodes = []
      @term = nil
    end

    attr_reader :root
  end

  class Scanner
    def initialize
    end

    def scan(source)
      [Token.new(:dummy, "")]
    end
  end

  class Parser
    def initialize
    end

    def parse(tokens)
      Root.new(
        Node.new(:dummy, [], nil)
      )
    end
  end
end

typeprof を使いRBSの雛形っぽいものを作ります。

$ mkdir sig
$ typeprof lib/klua.rb -o sig/klua.rbs

こういうのができる。

module Klua
  VERSION: String

  class Token
    def initialize: (:dummy type_, String value) -> String
    attr_reader type: :dummy
    attr_reader value: String
  end

  class Node
    def initialize: (:dummy type_, Array[bot] nodes, nil term) -> nil
    attr_reader type: :dummy
    attr_reader nodes: Array[bot]
    attr_reader term: nil
  end

  class Root < Node
    @type: :root
    @nodes: Array[bot]
    @term: nil

    def initialize: (Node root) -> nil
    attr_reader root: Node
  end

  class Scanner
    def initialize: -> nil
    def scan: (untyped source) -> [Token]
  end

  class Parser
    def initialize: -> nil
    def parse: (untyped tokens) -> Root
  end
end

これを眺めて、雰囲気で最初の型定義を書きます。いったんこの時点での最終形。

# TypeProf 0.12.0

# Classes
module Klua
  VERSION: String

  type token_type = :identifier | :number | :literal_str |
                    :local | :if | :then | :else | :end |
                    :and | :or | :not |
                    :+ | :- | :* | :/ | :< | :> | :== | :noteq |
                    :assign | :comma | :semicolon | :lbrace | :rbrace |
                    :eof |
                    :dummy

  class Token
    def initialize: (token_type type_, String value) -> untyped
    attr_reader type: token_type
    attr_reader value: String
  end

  type node_type = :block | :stat | :varstat | :assignstat | :funcallstat | :ifstat |
                   :exp | :binary | :unary | :functioncall | :primary | :var |
                   :args | :binop | :unop | :term |
                   :dummy |
                   :root

  class Node
    def initialize: (node_type type_, Array[Node] nodes, Token? term) -> untyped
    attr_reader type: node_type
    attr_reader nodes: Array[Node]
    attr_reader term: Token?
  end

  class Root < Node
    @type: node_type
    @nodes: Array[Node]
    @term: Token?

    def initialize: (Node root) -> untyped
    attr_reader root: Node
  end

  class Scanner
    def initialize: -> untyped
    def scan: (String source) -> Array[Token]
  end

  class Parser
    def initialize: -> untyped
    def parse: (Array[Token] tokens) -> Root
  end
end

以下は作業途中のログですが、 Gemfile に gem "steep" を書いて bundle install するとsteepコマンドが使えますが、途中結構怒られつつ直していく感じ。

bundle install
bundle exec steep init
emacs Steepfile # steep のドキュメントを見て更新する

bundle exec steep check
# \ で複数行にはしないらしい
sig/klua.rbs:7:7: [error] Syntax error caused by token `tUIDENT` (TokenType)
│ Diagnostic ID: RBS::SyntaxError
│
└   type TokenType = :identifier | :number | :literal_str | \
         ~~~~~~~~~

Detected 1 problem from 1 file
...
sig/klua.rbs:7:59: [error] Unexpected string: \
│         ...
│
│ Diagnostic ID: RBS::SyntaxError
│
└   type token_type = :identifier | :number | :literal_str | \
                                                             ~

# :"~~~" というSymbolリテラルは使えないらしい
sig/klua.rbs:10:55: [error] Syntax error caused by token `kCOLON` (:)
│ Diagnostic ID: RBS::SyntaxError
│
└                    :+ | :- | :* | :/ | :< | :> | :== | :"~=" | 
                                                         ~

$ bundle exec steep check
# Type checking files:

..............F..............................................F

# 親子でインスタンス変数の型を変えると怒られる...？
sig/klua.rbs:33:11: [error] Instance variable cannot have different type with parents: :root <=> ::Klua::node_type
│ Diagnostic ID: RBS::InstanceVariableTypeError
│
└     @type: :root
             ~~~~~

sig/klua.rbs:35:11: [error] Instance variable cannot have different type with parents: nil <=> (::Klua::Token | nil)
│ Diagnostic ID: RBS::InstanceVariableTypeError
│
└     @term: nil
             ~~~

# initializeの返り型は検査する必要がない、untypedにするべき
lib/klua.rb:15:8: [error] Cannot allow method body have type `(::Klua::Token | nil)` because declared as type `nil`
│   (::Klua::Token | nil) <: nil
│     ::Klua::Token <: nil
│
│ Diagnostic ID: Ruby::MethodBodyTypeMismatch
│
└     def initialize(type, nodes, term)
          ~~~~~~~~~~

Detected 3 problems from 2 files

最終的にsteep checkが通るんですが、やっぱり 気持ちいい ですね。型を決めると気持ちいいんですよ。Rubyでも。

$ bundle exec steep check
# Type checking files:

..............................................................

No type error detected.

ここからスキャナを実装してみます。

実装の方針自体は、Crafting Interpretersの実装を大きく参考しています、というかそれを Rustに移植したやつ が手元にあるので眺めて書いた。

  class Scanner
# ...
    private
    def succ
      char = @source[@current]
      # unless char
      #   raise "Overgone"
      # end
      @current += 1
      char
    end

    def match(expected)
      return false if at_end?

      char = @source[@current]
      return false if char != expected

      @current += 1
      true
    end

    def peek
      if at_end?
        0
      else
        @source[@current]
      end
    end

    def peek_next
      if @current + 1 >= @source.size
        0
      else
        @source[@current + 1]
      end
    end

    def digit?(char)
      char >= '0'.ord && char <= '9'.ord
    end

    def alpha?(char)
      (char >= 'a'.ord && char <= 'z'.ord) ||
      (char >= 'A'.ord && char <= 'Z'.ord) ||
      char == '_'.ord
    end

    def alphanumeric?(char)
      digit?(char) || alpha?(char)
    end

    def at_end?
      @current >= @source.size
    end
# ...

こういう感じでもりもり書いて、いったん steep check 。

$ bundle exec steep check
# Type checking files:

.............................................................F

lib/klua.rb:58:22: [error] Type `::Klua::Scanner` does not have method `at_end?`
│ Diagnostic ID: Ruby::NoMethod
│
└       return false if at_end?
                        ~~~~~~~

lib/klua.rb:68:9: [error] Type `::Klua::Scanner` does not have method `at_end?`
│ Diagnostic ID: Ruby::NoMethod
│
└       if at_end?
           ~~~~~~~

lib/klua.rb:94:6: [error] Type `::Klua::Scanner` does not have method `digit?`
│ Diagnostic ID: Ruby::NoMethod
│
└       digit?(char) || alpha?(char)
        ~~~~~~

lib/klua.rb:94:22: [error] Type `::Klua::Scanner` does not have method `alpha?`
│ Diagnostic ID: Ruby::NoMethod
│
└       digit?(char) || alpha?(char)
                        ~~~~~~

Detected 4 problems from 1 file

ここで怒られないようにRBSを更新。typeprofの結果を参考にして、

$ typeprof lib/klua.rb
...
  class Scanner
    @source: untyped
    @start: Integer
    @current: Integer
    @tokens: Array[bot]

    def initialize: -> nil
    def scan: (untyped source) -> Array[bot]

    private
    def succ: -> untyped
    def match: (untyped expected) -> bool
    def peek: -> Integer
    def peek_next: -> Integer
    def digit?: (untyped char) -> untyped
    def alpha?: (untyped char) -> untyped
    def alphanumeric?: (untyped char) -> untyped
    def at_end?: -> bool
  end

Scanner のメソッドの型定義を埋めます。

  class Scanner
    @source: Array[Integer]
    @start: Integer
    @current: Integer
    @tokens: Array[Token]

    def initialize: -> untyped
    def scan: (String source) -> Array[Token]

    private
    def succ: -> Integer
    def match: (Integer expected) -> bool
    def peek: -> Integer
    def peek_next: -> Integer
    def digit?: (Integer char) -> bool
    def alpha?: (Integer char) -> bool
    def alphanumeric?: (Integer char) -> bool
    def at_end?: -> bool
  end

$ bundle exec steep check
# Type checking files:

..............................................................

No type error detected. 

型を決めると気持ちいい！

ヘルパーメソッドは終わったので本体処理を書いていきます。

class Scanner
    def scan(source)
      @source = source.bytes
      @start = 0
      @current = 0
      @tokens = []

      while !at_end? do
        @start = @current
        scan_token
      end

      @tokens << Token.new(:eof, "")

      @tokens
    end

    private
    def scan_token
    end

RBSにも追記。

  private
    def scan_token: -> untyped

ここで一旦チェック。

$ bundle exec steep check
# Type checking files:

..............................................................

No type error detected. 

えっ...気持ちいい...。

単一のトークンのスキャン処理。

private
    def scan_token
      char = succ
      case char
      when '+'.ord
        add_token(:+)
      when '-'.ord
        add_token(:-)
      when '*'.ord
        add_token(:*)
      when '/'.ord
        add_token(:/)
      when '<'.ord
        add_token(:<)
      when '>'.ord
        add_token(:>)
      when '='.ord
      when '~'.ord
      when ','.ord
      when ';'.ord
      when '('.ord
      when ')'.ord
      when ' '.ord, "\r".ord, "\n".ord, "\t".ord
      when '"'.ord
      else
      end
    end

    def add_token(type)
      value = @source[@start..@current].map{|v| v.chr }.join
      @tokens << Token.new(type, value)
    end

# ---
private
    def scan_token: -> untyped
    def add_token: (token_type type_) -> untyped

途中までで一度確認する。

lib/klua.rb:83:40: [error] Type `(::Array[::Integer] | nil)` does not have method `map`
│ Diagnostic ID: Ruby::NoMethod
│
└       value = @source[@start..@current].map{|v| v.chr }.join
                                          ~~~

Detected 1 problem from 1 file

オッ

    def add_token(type)
      value = @source[@start..@current]&.map{|v| v.chr }.join
      raise "Invalid token range" unless value
      @tokens << Token.new(type, value)
    end

raise して、あってはいけない型を返しそうな分岐を潰します。

$ bundle exec steep check
# Type checking files:

..............................................................

No type error detected. 

OK。続々実装を進める。

    def scan_token
      char = succ
      case char
      when '+'.ord
        add_token(:+)
      when '-'.ord
        add_token(:-)
      when '*'.ord
        add_token(:*)
      when '/'.ord
        add_token(:/)
      when '<'.ord
        add_token(:<)
      when '>'.ord
        add_token(:>)
      when '='.ord
        if match('='.ord)
          add_token(:==)
        else
          add_token(:assign)
        end
      when '~'.ord
        if match('='.ord)
          add_token(:noteq)
        else
          raise "Unexpected character"
        end
      when ','.ord
        add_token(:comma)
      when ';'.ord
        add_token(:semicolon)
      when '('.ord
        add_token(:lbrace)
      when ')'.ord
        add_token(:rbrace)
      when ' '.ord, "\r".ord, "\n".ord, "\t".ord
        # Skip!
      when '"'.ord
        as_string
      else
        if digit?(char)
          as_number
        elsif alpha?(char)
          as_identifier
        else
          raise "Unexpected character"
        end
      end
    end

  class Scanner
    #...
    private
    def as_string: -> untyped
    def as_number: -> untyped
    def as_identifier: -> untyped

ここで $ bundle exec steep check ! no error!!

こういう感じで、メソッドの中身を埋める、型をつける、確認するを回して行っています。

メソッドの中身を埋めるごとにsteep checkで、静的にエラーが出そうな箇所がわかるというわけです。ここまで一回もコードは実際には実行していない。静的解析だけでたくさんのエラーがわかる。

$ bundle exec steep check
# Type checking files:

.............................................................F

lib/klua.rb:113:8: [error] Type `::Klua::Scanner` does not have method `advance`
│ Diagnostic ID: Ruby::NoMethod
│
└         advance()
          ~~~~~~~

lib/klua.rb:120:6: [error] Type `::Klua::Scanner` does not have method `advance`
│ Diagnostic ID: Ruby::NoMethod
│
└       advance()
        ~~~~~~~

lib/klua.rb:130:6: [error] Type `::Klua::Scanner` does not have method `advance`
│ Diagnostic ID: Ruby::NoMethod
│
└       advance() while digit?(peek)
        ~~~~~~~

一点引っ掛かったのが、こういうパターンで。

    def as_identifier
      succ() while alphanumeric?(peek)
      lit = @source[@start..@current]&.map{|v| v.chr }.join
      raise "Invalid number range" unless lit

      if %w(local if then else end and or not).include? lit
        @tokens << Token.new(lit.to_sym, lit)
      else
        @tokens << Token.new(:identifier, lit)
      end
    end

lib/klua.rb:144:29: [error] Cannot pass a value of type `::Symbol` as an argument of type `::Klua::token_type`
│   ::Symbol <: ::Klua::token_type
│     ::Symbol <: (:identifier | :number | :literal_str | :local | :if | :then | :else | :end | :and | :or | :not | :+ | :- | :* | :/ | :< | :> | :== | :noteq | :assign | :comma | :semicolon | :lbrace | :rbrace | :eof | :dummy)
│       ::Symbol <: :identifier
│
│ Diagnostic ID: Ruby::ArgumentTypeMismatch
│
└         @tokens << Token.new(lit.to_sym, lit)
                               ~~~~~~~~~~

こうした。多分もっといい方法があるでしょう（型が人間の目に明らかな場合、何かしらのアノテーションで強制できそう）。

def get_reserved_sym: (String lit) -> token_type?

    def as_identifier
      succ() while alphanumeric?(peek)
      lit = @source[@start..@current]&.map{|v| v.chr }.join
      raise "Invalid number range" unless lit

      if sym = get_reserved_sym(lit)
        @tokens << Token.new(sym, lit)
      else
        @tokens << Token.new(:identifier, lit)
      end
    end

    def get_reserved_sym(lit)
      case lit
      when "local"
        :local
      when "if"
        :if
      when "then"
        :then
      when "else"
        :else
      when "end"
        :end
      when "and"
        :and
      when "or"
        :or
      when "not"
        :not
      else
        nil
      end
    end

そうこうしていたら、一応トークナイザーができた。まずはおわりです。

$ bundle exec irb -rklua
irb(main):001:0> pp Klua::Scanner.new.scan 'if x == true then 1 + 1; else print("Whoa"); end'; nil
[#<Klua::Token:0x00007fe7ab88e8a8 @type=:if, @value="if">,
 #<Klua::Token:0x00007fe7ab88e6f0 @type=:identifier, @value="x">,
 #<Klua::Token:0x00007fe7ab88e4e8 @type=:==, @value="==">,
 #<Klua::Token:0x00007fe7ab88e268 @type=:identifier, @value="true">,
 #<Klua::Token:0x00007fe7ab88def8 @type=:then, @value="then">,
 #<Klua::Token:0x00007fe7ab88dcf0 @type=:number, @value="1">,
 #<Klua::Token:0x00007fe7ab88db10 @type=:+, @value="+">,
 #<Klua::Token:0x00007fe7ab88d660 @type=:number, @value="1">,
 #<Klua::Token:0x00007fe7ab88d390 @type=:semicolon, @value=";">,
 #<Klua::Token:0x00007fe7ab88d138 @type=:else, @value="else">,
 #<Klua::Token:0x00007fe7ab88ce68 @type=:identifier, @value="print">,
 #<Klua::Token:0x00007fe7ab88cc10 @type=:lbrace, @value="(">,
 #<Klua::Token:0x00007fe7ab887ee0 @type=:literal_str, @value="Whoa">,
 #<Klua::Token:0x00007fe7ab8875a8 @type=:rbrace, @value=")">,
 #<Klua::Token:0x00007fe7ab887300 @type=:semicolon, @value=";">,
 #<Klua::Token:0x00007fe7ab886fb8 @type=:end, @value="end">,
 #<Klua::Token:0x00007fe7ab886dd8 @type=:eof, @value="">]
=> nil

次回はちゃんとエディタの支援機能を入れてみます（入れてなかったのかい！）。そしてパーサの実装へ入る。

中編へ:

udzura.hatenablog.jp

*1:本来なら、ライブコーディングの動画でも残すのがいいんでしょうね