LoginSignup
2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@sonota88

自作言語に簡単な型検査器を追加した

Last updated at Posted at 2025-04-29

簡単な型検査器を作ってみました。実際に作っていたのは 2023年の6月です。せっかくだし備忘記事も書いておきたいな〜と思っているうちに2年経ってしまいました。

以下、2年前に作ったときのことを思い出したりしつつ書いた雑なメモです。

経緯

当時はまだ『TypeScriptではじめる型システム』が載っているn月刊ラムダノート Vol.4, No.3(2024) が発売されておらず、筑波大学の実験資料を参考にしていました。

こちらを読みながら一通り Ruby で写経した後、簡単な型チェックだけなら自作言語 Mini Ruccola にもすぐ組み込めそうだったので実際にやってみた、という流れです。

Mini Ruccola 言語について

私がコンパイラ実装に入門するために作ったシンプルな自作言語です。ML系ではなく Algol系のオーソドックスなもの。私でも作れる簡単なコンパイラ。

リポジトリはこちら:

今回作ったもの

type_check.rb とコンパイル処理の概観

型チェックを行う type_check.rb というスクリプトを追加しました。170行弱の小さなものです。

パースして AST（抽象構文木）が作られたタイミングで実行します。このとき入力として AST を渡します。

# run.sh の一部

set -o errexit

# ...

ruby mrcl_lexer.rb $file > $tokensfile      # 字句解析
ruby mrcl_parser.rb $tokensfile > $treefile # 構文解析
ruby type_check.rb $treefile                # ここに差し込む
ruby mrcl_codegen.rb $treefile > $asmfile   # コード生成

型の不正が検出された場合はコード生成には進まず、コンパイル処理全体を失敗させます。

型注釈を導入

もともと型がない（整数しかない）言語なので、まずは構文を変更して型注釈（型アノテーション）を書けるようにしました。

以下の通り、型注釈を書けるのは関数の引数、関数の返り値、変数宣言の位置です。

// 変更前
func add(a, b) {
  var c;
  set c = a + b;
  return c;
}

// 変更後
func add(a: int, b: int): int {
  var c: int;
  set c = a + b;
  return c;
}

見た目は TypeScript とか Scala っぽい感じですね。

パースすると以下のように型の情報を持つ AST が得られます。

[
  "func", "add",
  "int", // 関数の返り値
  [
    ["a", "int"], // 関数の引数
    ["b", "int"]  // 関数の引数
  ],
  [
    ["var", ["c", "int"]], // 変数宣言
    ["set", "c", ["+", "a", "b"]],
    ["return", "c"]
  ]
]

ここはレキサとパーサをちょろっといじってできあがり。

int だけだと型チェックの意味がないので bool も扱います。今回扱う型はこの2つだけ。

式の型の導出

ここから型チェックについてのメモ。

式を渡すと型を返すメソッドを用意しました。この中身を書いていきます。

def check_expr(expr)
  # ...
end

check_expr(123) #=> "int"

たとえば「123 という式の型は何ですか？」と聞かれて「int です」と答えるとき、人間なら 123 という値を見て「これは int だな」と判断できます。 これを機械にやらせたい。

整数

def check_expr(expr)
  case expr
  when Integer
    "int"
  else
    # ...
  end
end

check_expr(123)  #=> "int"
check_expr(-456) #=> "int"

整数だったら int 型を返す、これだけ。

変数

ただ単に「変数 a の型は何ですか？」とだけ聞かれても分かりません。情報がないから。

ないなら与えてあげればいいじゃない、ということで「変数 a の型は○○○だよ」という情報（型環境）を外から与えてあげます。

def check_expr(type_env, expr)
  case expr
  when String
    if type_env.key?(expr)
      type_env[expr]
    else
      raise "変数 #{expr} は未定義です"
    end
  else
    # ...
  end
end

check_expr({"a" => "int"}, "a")  #=> "int"
check_expr({"b" => "int"}, "b")  #=> "int"
check_expr({"a" => "bool"}, "a") #=> "bool"
check_expr({"a" => "int"}, "c")  #=> エラー: 変数が未定義

副次的にというか未定義変数のチェックもできるようになります。

型環境はどこから持ってくるのか？ という話は後述。

整数同士の加算

加算の場合は「左項・右項の型がどちらも int であること」という条件を課します。たとえば

  • 1 + true
  • false + 2
  • true + false

のような式はこの条件を満たしていないためエラー（型が不正）とします。

true, false というリテラルは今回は導入していないのですが、見た目の煩雑さを避けるために使っています。
ちなみにリテラルを書けるようにするのは割と簡単で、ブランチを分けて別途履修しています。

一方で

  • 1 + 2
  • -123 + 456

のように前提条件を満たしている場合は全体の型が int であると判断します。

def check_expr(expr)
  case expr
  when Integer
    "int"
  when Array
    case expr
    in ["+", lhs, rhs]
      raise "左項が型エラー" unless check_expr(lhs) == "int"
      raise "右項が型エラー" unless check_expr(rhs) == "int"
      "int"
    else
      raise "..."
  else
    raise "..."
  end
end

check_expr(["+", 1, 2]) #=> "int"
check_expr(["+", true, 2]) #=> エラー: 型が不正
  • 実際の計算を行っていない（検査対象のプログラムを実際に実行しているわけではない）というのがポイント。実際に計算しなくても型は得られる。
  • 「1 + 2 を計算すると結果が 3 になる。3 の型は int だから 1 + 2 の型も int である」のように判断しているわけではない。
  • 「1, 2, 358706, ... といった具体的な値に関係なく int 型の値同士を加算した結果の型は int になる」というルールを決めておき、そのルールにしたがって導出していく

入れ子になっている式

すでに加算の左項、右項の型を導出するために再帰的に呼び出すようになっていますから、入れ子になっていても対応できます。

# 1 + ((2 + 3) + 4)
check_expr(["+", 1, ["+", ["+", 2, 3], 4]]) #=> "int"

式の構文木の先端（葉）の方から根に向かって型を導出していって、最終的に式全体の型として一つの型が得られるというイメージ。

過程を書き下してみます。

1 + ((2 + 3) + 4)

↓ まず左項を見る。 1 の型は int

int + ((2 + 3) + 4)
       ^^^^^^^^^^^ 次は右項を見る
        ^^^^^ その中の左項を見る
        ^ さらにその中の左項を見る
    ↓ 2 の型は int

    int + ((int + 3) + 4)
                  ^ 次はここ
    ↓ 3 の型は int

    int + ((int + int) + 4)
            ^^^^^^^^^
    ↓ int + int の型は int

  int + (int + 4)

  ↓ 4 の型は int

  int + (int + int)

  ↓ int + int の型は int

int + int

↓ int + int の型は int

int

（※ 実際に構文木の要素を置き換えていくわけではなく、あくまで処理が進む様子を示すためのイメージです）

ここらへんで「こういうのやったことあるな……」という気持ちになってきます。インタプリタで式を評価すると結果の値が一つ得られる、というのと似てますね。

式の型の導出のまとめ

最終的なできあがりはこうなりました。

def check_expr(ctx, expr)
  case expr
  when Integer
    "int"
  when String
    if ctx.type_dict.key?(expr)
      ctx.type_dict[expr]
    else
      raise "no such variable (#{expr.inspect})"
    end
  when Array
    op, lhs, rhs = expr
    case op
    when "+", "*"
      assert_expr(ctx, lhs, "int")
      assert_expr(ctx, rhs, "int")
      "int"
    when "==", "!="
      type_l = check_expr(ctx, lhs)
      type_r = check_expr(ctx, rhs)
      if type_l != type_r
        raise TypeError
      end
      "bool"
    else
      raise "unsupported operator (#{expr.inspect})"
    end
  else
    raise "unsupported (#{expr.inspect})"
  end
end
  • 乗算は加算と同様
  • 比較（==, !=）の場合は左項と右項が同じ型であればよくて（int 同士または bool 同士であればよい）結果の型は bool とする

実行例:

check_expr({}, 123) #=> "int"
check_expr({"a" => "bool"}, "a") #=> "bool"

# 1 + 2
check_expr({}, ["+", 1, 2]) #=> "int"
# 1 * 2
check_expr({}, ["*", 1, 2]) #=> "int"
# 1 * (2 + 3)
check_expr({}, ["*", 1, ["+", 2, 3]]) #=> "int"

check_expr({}, ["==", 1, 2]) #=> "bool"
check_expr({}, ["==", true, false]) #=> "bool"

# true == (1 != 2)
check_expr({}, ["==", true, ["!=", 1, 2]]) #=> "bool"

# ((a + 1) == (2 * 3)) != false （a は int）
check_expr(
  {"a" => "int"}, 
  [
    "!=",
    [
      "==",
      ["+", "a", 1],
      ["*", 2, 3]
    ],
    false
  ]
)
#=> "bool"

check_expr({}, "a") #=> エラー: 変数が未定義
check_expr({}, ["+", 1, true]) #=> エラー: 加算の右項が int ではない

式以外の処理

変数宣言と代入

var a: bool;
set a = 1;

変数の型の導出で後回しにしていた部分の話です。

  • set文 set a = 1; だけ見ても式 a の型が分からない
  • 型環境を作って渡してあげればよい
  • var文を見れば変数名と型の対応が分かるので、それを見て型環境を作り、set文を処理するときに渡してあげればよい
type_env = {}

statements.each do |statement|
  case statement
  in ["var", [var_name, type]]
    type_env[var_name] = type
  in ["set", var_name, expr]
    type_l = check_expr(type_env, var_name)
    type_r = check_expr(type_env, expr)
    if type_l != type_r
      raise "型が不一致"
    end
  else
    # ...
  end
end

大枠としては「型の情報をどこかから得る」「その情報を使って型チェックを行う」という流れになっています。次に見ていく関数まわりも基本的には同じです。

↓ここらへんの「変数と何か」のマッピングは似てますね。

  • インタプリタでは「変数名 → 値」のマッピングを使う
  • コンパイラでは「変数名 → メモリ上の位置」のマッピングを使う
  • 型検査器では「変数名 → 型」のマッピングを使う

関数の仮引数

func f(a: bool): void {
  var b: int;
  set b = a; // ここで a が登場する
}

set文の左辺 b の型は int なので、あとは右辺の a の型が分かれば判定できます。

a の型の情報を得るにはどうすればいいか？

func f(a: bool): void {

ここを見ます。関数の本体（文の並び）を処理する前にここを見て「a の型は bool である」という情報を型環境に登録し、それから関数の本体（文の並び）を見て検査していけばOK。

「型の情報を得る」「それを使ってチェックする」同じです。

関数の実引数

func f(a: bool): void {
  // ...
}

func main(): void {
  call f(123); // bool が期待されている
}

これまでローカル変数や仮引数を扱うために型環境に「変数名と型のマッピング」を登録して使っていましたが、それと同じように「関数名と引数の型のマッピング」を用意してあげれば実引数をチェックできます。

  • あらかじめ全体を走査して「関数名と返り値の型のマッピング」を作っておき、型検査したいときにそれを参照する
  • 現在の Mini Ruccola の仕様上、変数用の型環境とは別に管理する
def check_funcall(ctx, fn_name, args_act)
  args_exp = $fn_sigs[fn_name].args

  if args_act.size != args_exp.size
    raise "引数の数が間違っている"
  end

  args_exp.zip(args_act).each do |arg_exp, arg_act|
    _, type_exp = arg_exp
    assert_expr(ctx, arg_act, type_exp)
  end

  # ...
end

関数の返り値

func f(): int {
  // ...
}

func main(): void {
  var a: bool;
  call_set a = f(); // ここで f() の返り値を使う
}

関数 f の返り値の型は↓ここを見れば分かりますね。

func f(): int {

「関数名と返り値の型のマッピング」を用意すればよくて、あとはだいたい同じ。（説明が雑になってきましたが、まあだいたい同じなので……）

def check_funcall(ctx, fn_name, args_act)
  # ...

  # 式の型の導出と同様に「結果の型」を返す
  $fn_sigs[fn_name].ret
end

関数呼び出しも式として扱えばより統一性のある形にできますが、今回はスコープ外としています。

組み込み関数の型

組み込み関数の型の情報はコンパイル対象のソースコード内には存在しないので型検査器の側であらかじめ登録しておきます。

$fn_sigs["set_vram"] = FuncSig.new( # 関数名と対応付けて登録
  [["vram_addr", "int"], ["value", "int"]], # 引数の型
  "void" # 返り値の型
)

$fn_sigs["get_vram"] = FuncSig.new(
  [["vram_addr", "int"]],
  "int"
)

case文, while文の条件式

case when (a == 1) {
  // ...
}

while (a != 10) {
  // ...
}

特に難しいことはなくて、条件式（上の例でいえば a == 1 や a != 10）の型を導出して、その型が bool であるかをチェックすればOK。

おわりに

こんな感じで自作言語 Mini Ruccola に簡単な型検査器を追加しました。できあがりの全体を見たい場合はリポジトリの方を参照してください。

実装面で特に難しいところはなく（強いていえば再帰呼び出しが出てくるくらい）、初歩的なものであれば型検査は簡単に作れるな、という手応えが得られました。

この記事はゆるふわな「とりあえず手を動かしてやってみた」系のやつなので、ちゃんとした解説が読みたい方は筑波大の実験資料や『型システムのしくみ』、以下の参考資料などをお読みください。

メモ

  • 手元に自作言語があると「ちょっと型検査器作ってみようかな」と思い立ったときにシュッと作れてべんり
  • mini じゃない Ruccola の方にも追加したい
  • 実用を考えると元のソースコード上の位置情報（行番号など）もエラー時の出力に含めたいところ

参考

『型システムのしくみ ― TypeScriptで実装しながら学ぶ型とプログラミング言語』

これから買って読みます！

Ruby + インタプリタ

  • 遠藤侑介『RubyでつくるRuby ゼロから学びなおすプログラミング言語入門』
  • 原悠『Rubyで作る奇妙なプログラミング言語　～ヘンな言語のつくりかた～』
  • 渡辺昌寛『つくって学ぶプログラミング言語 RubyによるScheme処理系の実装』
  • kanaka/mal: mal - Make a Lisp
    • Ruby 版を写経するのもおすすめ（私も以前やりました）

その他

この記事を読んだ人は（ひょっとしたら）こちらも読んでいます

2
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?