Zenn
nextbeat Tech BlogPublicationへの投稿
👻

JavaScriptで作る！ミニ言語のインタプリタ（８）〜静的型検査を実装する（２）〜

kmizu
2024/12/18に公開
JavaScript
language
tech

はじめに

前回の記事では、リテラルや制御構文、変数の代入/参照を含む基本的な式に対する静的型検査の実装を紹介しました。今回はその続きとして、関数定義と関数呼び出しにおける型検査を追加し、型安全性をさらに向上させます。

必要なクラスの定義

前回の記事では関数定義・呼び出しを含まないプログラムを対象に型検査をしていたため、プログラム全体が一つの式でした。しかし、今回は任意個の関数定義が並んだあとに式の並びが出てくるような形式であるため、クラス定義の追加・修正が必要になります。

Programクラス

前々回の記事のように、再び以下のクラスProgramを対象として型検査を行うものとします。defsは任意個の関数定義を、　expressionsはプログラム本体の列を表します。

//プログラム全体
class Program {
  constructor(defs, ...expressions){
    this.defs = defs;
    this.expressions = expressions;
  }
}

前々回の記事のProgramクラスとまったく同じです。

FuncionTypeクラス

関数の型チェックを行うのですから、関数を表す型を作る必要があります。この記事ではそのためのクラスFunctionTypeを次のように定義します：

class FunctionType {
  constructor(argTypes, returnType) {
    this.argTypes = argTypes;
    this.returnType = returnType;
  }
  equals(other) {
    return (
      other instanceof FunctionType &&
      arrayEquals(this.argTypes, other.argTypes) &&
      this.returnType.equals(other.returnType)
    );
  }
  toString() {
    return `FunctionType(${this.argTypes} -> ${this.returnType})`;
  }
}

このクラスは、型の等価性を確認するequalsメソッドと、デバッグ用のtoStringメソッドを持っています。このクラスを使って以降で関数定義・呼び出しの型検査を実装していきます。

FunDefクラス

前々回の記事でもでてきたFunDefクラスですが、以下のように拡張します。

//関数定義を表すクラス
class FunDef {
  constructor(name, args, returnType, body) {
    this.name = name;
    this.args = args;
    this.returnType = returnType;
    this.body = body;
  }
}

argsは[["x", "int"],["y", "int"]]のように引数名と型名のペアの配列であることを想定しています。また、returnTypeは返り値の型をあらわします。

プログラム全体の型検査

前回はプログラムに現れる式を単純に型検査すればよかったのですが、関数定義と呼び出しが出てくると少し複雑になります。具体的には、

  • 関数定義の本体が型検査を通ること
  • 関数本体の型が関数定義の返り値の型と一致すること

を追加で検査する必要があります。これを実現するためにtypeCheckProgram関数を実装します：

function evalJsonProgram(jsonString) {
  const jsonProgram = JSON.parse(jsonString);
  const program = translateProgram(jsonProgram);
  typeCheckProgram(program); // typeCheck(program, {}) から差し替え
  return evalProgram(program);
}

function typeCheckProgram(program) {
  // 組み込み関数の型を定義
  const typeEnv = {
    'print': new FunctionType([STRING_TYPE], STRING_TYPE),
    'input': new FunctionType([STRING_TYPE], STRING_TYPE),
    'concat': new FunctionType([STRING_TYPE, STRING_TYPE], STRING_TYPE),
    'parseInt': new FunctionType([STRING_TYPE], INT_TYPE),
    'add': new FunctionType([INT_TYPE, INT_TYPE], INT_TYPE),
    'mul': new FunctionType([INT_TYPE, INT_TYPE], INT_TYPE),
    'length': new FunctionType([STRING_TYPE], INT_TYPE),
    'charAt': new FunctionType([STRING_TYPE, INT_TYPE], STRING_TYPE),
    'slice': new FunctionType([STRING_TYPE, INT_TYPE, INT_TYPE], STRING_TYPE),
    'intToString': new FunctionType([INT_TYPE], STRING_TYPE),
  };

  // 関数型の環境への登録
  program.defs.forEach((def) => {
    typeEnv[def.name] = new FunctionType(
      def.args.map((arg) => typeFromName(arg[1])),
      typeFromName(def.returnType)
    );
  });

  // 関数本体の型検査
  program.defs.forEach((def) => {
    const localEnv = { ...typeEnv };
    def.args.forEach((arg) => {
      localEnv[arg[0]] = typeFromName(arg[1]);
    });

    const bodyType = typeCheck(def.body, localEnv);
    const expectedType = typeFromName(def.returnType);

    if (!bodyType.equals(expectedType)) {
      throw `Function ${def.name} expected return type ${expectedType}, but got ${bodyType}`;
    }
  });

  // プログラム本体の型検査
  let result = null;
  program.expressions.forEach((e) => {
    result = typeCheck(e, typeEnv);
  });
  return result;
}

関数の実装は大きく4つのパートに分かれていますので、それぞれ説明します。

組み込み関数の型を定義

当然ながら、組み込み関数がどのような型を持つかは事前にわかりませんから、言語作成者が定義してあげる必要があります。それが以下の部分です:

const typeEnv = {
  'print': new FunctionType([STRING_TYPE], STRING_TYPE),
  'input': new FunctionType([STRING_TYPE], STRING_TYPE),
  ...
};

print関数はstring型を受け取って、それを出力してその値自身を返すのでFunctionType([String_TYPE], STRING_TYPE)となります。input関数はプロンプトとして表示するための文字列を受け取って、入力された文字列を返すので同様にFunctionType([STRING_TYPE], STRING_TYPE)となります。

他の関数についても同様にして「望ましい関数の型」を定義していきます。

関数型の環境への登録

トップレベルの関数すべてについて、それが表すFunctionTypeを作って環境に登録します。後ほどトップレベル関数の呼び出しが出てきたときに型検査を行うために必要な作業です。

  program.defs.forEach((def) => {
    typeEnv[def.name] = new FunctionType(
      def.args.map((arg) => typeFromName(arg[1])),
      typeFromName(def.returnType)
    );
  });

ここでは関数名def.nameをキーにして都度都度FunctionTypeを生成して割り当てています。typeFromName関数は前回でてきましたが以下のようになっています。

function typeFromName(name) {
  switch(name) {
    case "int":
      return INT_TYPE;
    case "boolean":
      return BOOLEAN_TYPE;
    case "string":
      return STRING_TYPE;
  }
}

関数本体の型検査

プログラム本体の型検査に入る前にそれぞれの関数定義の中で型検査を行って、エラーが出ていないことを確認します。最初の行でlocalEnv = { ...typeEnv }としているのは、関数定義の型検査ごとに新しい環境を作って既存の環境を汚染しないためです。

localEnvに引数名と型の対を登録した後で、関数本体の型検査を行い、型検査を通ることと、その型と返り値の型が一致することを検査しています。

  program.defs.forEach((def) => {
    const localEnv = { ...typeEnv };
    def.args.forEach((arg) => {
      localEnv[arg[0]] = typeFromName(arg[1]);
    });

    const bodyType = typeCheck(def.body, localEnv);
    const expectedType = typeFromName(def.returnType);

    if (!bodyType.equals(expectedType)) {
      throw `Function ${def.name} expected return type ${expectedType}, but got ${bodyType}`;
    }
  });

プログラム本体の型検査

プログラム本体を構成するそれぞれの式について型検査を順番に実行します。

  let result = null;
  program.expressions.forEach((e) => {
    result = typeCheck(e, typeEnv);
  });
  return result;

関数呼び出しの型検査

関数呼び出しの型検査では、次の点を検査します：

  • 関数が型環境に存在すること
  • 実引数と仮引数の個数が一致すること
  • 実引数の型が仮引数の型と一致すること

この3点を検査するためにtypeCheck関数を以下のように拡張します：

function typeCheck(expr, typeEnv) {
  // ...
  if (expr instanceof FunCall) {
    // 関数が存在することを確認
    const targetType = typeEnv[expr.name]
    if(!(targetType instanceof FunctionType)) {
      throw `Type error. Type ${expr.name} is required to function.  Actual: ${targetType}`;
    }

    // 仮引数と実引数の個数が一致することを確認
    const argTypes = expr.args.map((a) => typeCheck(a, typeEnv));
    if(targetType.argTypes.length !== argTypes.length) {
      throw `Type error. Required: ${targetType.argTypes.length} arguments, actual: ${argTypes.length} arguments`;
    }

    // 引数それぞれについて、仮引数の型と実引数の型が一致することを確認
    for(let i = 0; i < targetType.argTypes.length; i++) {
      if(!targetType.argTypes[i].equals(argTypes[i])) {
        throw `Type error. Required: ${targetType.argTypes[i]}, actual: ${argTypes[i]}`;
      }
    }

    // 返り値の型を返す
    return targetType.returnType;
  }
  // ...
}

テストケース

以下に、型検査を通るプログラムと型エラーが起こるプログラムの例を示します：

型検査を通る例

関数addは2つのintを受け取ってintを返す関数です。呼び出し側もその制約を満たすように引数1, 2を渡しているので型検査を通るはずです。

{
  "functions": [
    ["add", [["x", "int"], ["y", "int"]], "int",
      ["+", ["ref", "x"], ["ref", "y"]]
    ]
  ],
  "body": ["call", "print", ["call", "intToString", ["call", "add", 1, 2]]]
}

実行すると型検査を通り、予想通り3が出力されます。

型エラーの例

関数addは2つのintを受け取るはずなのに呼び出し側では2番目の引数にtrueが渡されています。そのため、このプログラムは型検査を通らないはずです。

{
  "functions": [
    ["add", [["x", "int"], ["y", "int"]], "int",
      ["+", ["ref", "x"], ["ref", "y"]]
    ]
  ],
  "body": ["call", "print", ["call", "intToString", ["call", "add", 1, true]]]
}

このプログラムを実行すると、次のようなエラーメッセージが表示されます：

Type error. Required: Type(int), actual: Type(boolean)

コードの全体像

コードの修正が多岐にわたったので、再び型検査器を含むインタプリタの全体像を示します。535行とだいぶ長くなってきたので、gistからご覧ください。

まとめ

今回の記事では、以下を実装しました：

  • 関数定義の型検査
  • 関数呼び出しの型検査

これにより、関数を含むプログラムの型安全性を保証できるようになりました。だいぶプログラミング言語としての機能が揃ってきたので次回からはいよいよ具象構文および構文解析について解説していきます。

お楽しみに！

nextbeat Tech Blog
nextbeat Tech BlogPublication

株式会社ネクストビート所属のエンジニアが運営するテックブログです。ネクストビートは、テクノロジーと推進力、そして熱いベンチャーマインドで、ライフイベント・地方創生・グローバルの各事業に取り組んでいます。 なお、投稿内容は社員個人の見解であり、所属する組織を代表するものではありません。

Discussion