📖

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

kmizu

2024/10/31に公開

はじめに

前回の記事では、インタプリタに真偽値型と文字列型を追加し、より実用的なプログラムが書けるようになりました。今回は、プログラムの実行前に型エラーを検出できるように、静的型検査を実装します。

ただし、前回の実装に全て型検査を実装しようとすると説明が膨れ上がるのでいったん以下の単純化した式のみを型検査するようにします。

これは

リテラル（数値、真偽値、文字列）
変数の代入/参照
制御構文（if / while / seq）
各種演算（数値演算、論理演算）

のみをもったものです。

次回以降で、関数の型検査についても説明するのでご安心ください：

// 式を表すクラス
class Expression {}
// 代入を表すクラス
class Assignment extends Expression {
  constructor(name, expr) {
    super();
    this.name = name;
    this.expr = expr;
  }
} 
// 二項演算子（+、-、*、/）のためのクラス
class BinExpr extends Expression {
  constructor(operator, lhs, rhs) {
    super();
    this.operator = operator;
    this.lhs = lhs;
    this.rhs = rhs;
  }
}
// 単項演算子（not）のためのクラス
class UnaryExpr extends Expression {
  constructor(operator, expr) {
    super();
    this.operator = operator;
    this.expr = expr;
  }
}
// 整数値のためのクラス
class Num extends Expression {
  constructor(value) {
    super();
    this.value = value;
  }
}
// 真偽値のためのクラス
class Bool extends Expression {
  constructor(value) {
    super();
    this.value = value;
  }
}
// 文字列のためのクラス
class Str extends Expression {
  constructor(value) {
    super();
    this.value = value;
  }
}
// 変数参照のためのクラス
class VarRef extends Expression {
  constructor(name){
    super();
    this.name = name;
  }
}

// 条件分岐のためのクラス
class If extends Expression {
  constructor(cond, thenExpr, elseExpr) {
    super();
    this.cond = cond;
    this.thenExpr = thenExpr;
    this.elseExpr = elseExpr;
  }
}

// 繰り返しのためのクラス
class While extends Expression {
  constructor(cond, body) {
    super();
    this.cond = cond;
    this.body = body;
  }
}

// 連接のためのクラス
class Seq extends Expression {
  constructor(...bodies) {
    super();
    this.bodies = bodies;
  }
}

型システムの設計

まず、静的型検査を行うために、型を表現するためのクラスを定義します：

class Type {
  constructor(name) {
    this.name = name;
  }
  equals(other) {
    return this.name === other.name;
  }
  toString() {
    return this.name;
  }
}

const INT_TYPE = new Type("int");
const BOOLEAN_TYPE = new Type("boolean");
const STRING_TYPE = new Type("string");

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

Typeクラスは型の名前を保持し、型の等価性を判定するためのequalsメソッドを持ちます。また、エラーメッセージ生成のためにtoStringメソッドもオーバーライドしています。

constな値はそれぞれ以下の役割をになっています。

INT_TYPE: int型を表す定数
BOOLEAN_TYPE: boolean型を表す定数
STRING_TYPE: string型を表す定数

typeFromName()は型名と上記の値を対応づけるための関数です。

型検査器の実装

型検査器は、式の型を推論し、型の整合性をチェックする関数です。

リテラルの型検査

まず、リテラルの型検査の実装は以下のようになります：

  } else if(expr instanceof Num) {
    return INT_TYPE;
  } else if(expr instanceof Bool) {
    return BOOLEAN_TYPE;
  } else if(expr instanceof Str) {
    return STRING_TYPE;

これは

整数リテラルはint型
真偽値リテラルはboolean型
文字列リテラルはstring型

になることを表しています。

演算子の型検査

次は各種演算子の型検査を実装していきます。引数typeEnvは定義済み変数とその型を対応づけるためのもので、次の「変数の型検査」で使います。

function typeCheck(expr, typeEnv) {
  if(expr instanceof BinExpr) {
    const typeL = typeCheck(expr.lhs, typeEnv);
    const typeR = typeCheck(expr.rhs, typeEnv);
    switch(expr.operator) {
      case "+":
      case "-":
      case "*":
      case "/":
      case "%":
        if(!typeL.equals(INT_TYPE) || !typeR.equals(INT_TYPE)) {
          throw `Required: ${INT_TYPE} ${expr.operator} ${INT_TYPE} actual: ${typeL} ${expr.operator} ${typeR}`;
        }
        return INT_TYPE;
      case "<":
      case ">":
      case "<=":
      case ">=":
        if(!typeL.equals(INT_TYPE) || !typeR.equals(INT_TYPE)) {
          throw `Required: ${INT_TYPE} ${expr.operator} ${INT_TYPE}, actual: ${typeL} ${expr.operator} ${typeR}`;
        }
        return BOOLEAN_TYPE;
      case "==":
      case "!=":
        if(!typeL.equals(typeR)) {
          throw `Left and right must be equal. actual: ${typeL} ${expr.operator} ${typeR}`;
        }
        return BOOLEAN_TYPE
      case "and":
      case "or":
        if(!typeL.equals(BOOLEAN_TYPE) || !typeR.equals(BOOLEAN_TYPE)) {
          throw `Required: ${BOOLEAN_TYPE} ${expr.operator} ${BOOLEAN_TYPE}, actual: ${typeL} ${expr.operator} ${typeR}`;
        }
        return BOOLEAN_TYPE;
    }
  }

型検査器は式を再帰的に処理し、以下のようなルールに従って型を推論します：

算術演算子（+、-、*、/、%）
- 両オペランドが整数型であることを要求
- 結果は整数型
比較演算子（<、>、<=、>=）
- 両オペランドが整数型であることを要求
- 結果は真偽値型
等価演算子（==、!=）
- 両オペランドが同じ型であることを要求
- 結果は真偽値型
論理演算子（and、or）
- 両オペランドが真偽値型であることを要求
- 結果は真偽値型

変数の型検査

変数についての型検査も重要です。ポイントは引数typeEnv（型環境）を使って、

変数が定義済みか
定義済みの変数の型は何か

を管理していることです。

function typeCheck(expr, typeEnv) {
  // ... 前述のコード ...
  if(expr instanceof VarRef) {
     if (!(expr.name in typeEnv)) {
       throw `Variable ${expr.name} is not defined`;
     }
     return typeEnv[expr.name];
  } else if(expr instanceof Assignment) {
     const valueType = typeCheck(expr.expr, typeEnv);
     const name = expr.name;
     if(!(name in typeEnv)) {
       typeEnv[name] = valueType;
       return valueType;
     }
     if(!typeEnv[name].equals(valueType)) {
         throw `Since the variable ${name} is declared as ${typeEnv[name]}, ${valueType} cannot be assigned`;
     }
     return valueType;
  }

変数に関する型検査では：

変数参照時に、その変数が定義済みであることを確認
代入時に：
- 未定義の変数なら、代入される値の型で変数を定義
- 定義済みの変数なら、代入される値の型が変数の型と一致することを確認

を実行します。

制御構文の型検査

制御構文の型検査も同様に実装します：

function typeCheck(expr, typeEnv) {
  // ... 前述のコード ...
  } else if(expr instanceof Seq) {
    let result = null;
    expr.bodies.forEach((e) => {
      result = evalExpr(e, env);
    });
    return result;
  } else if(expr instanceof If) {
    const condType = typeCheck(expr.cond, typeEnv);
    if(!condType.equals(BOOLEAN_TYPE)) {
      throw `If expression's condition must be ${BOOLEAN_TYPE}.  Actual: ${condType}`;
    }
    const thenType = typeCheck(expr.thenExpr, typeEnv);
    const elseType = typeCheck(expr.elseExpr, typeEnv);
    if(!thenType.equals(elseType)) {
      throw `If expression's then and else must be equal.  Actual: ${thenType} != ${elseType}`;
    }
    return thenType;
  } else if(expr instanceof While) {
    const condType = typeCheck(expr.cond, typeEnv);
    if(!condType.equals(BOOLEAN_TYPE)) {
      throw `While expression's condition must be ${BOOLEAN_TYPE}.  actual: ${condType}`;
    }
    const bodyType = typeCheck(expr.body, typeEnv);
    return INT_TYPE;
  }

制御構文では以下の制約を満たすように型検査を行います：

if式
- 条件部分が真偽値型であることを要求
- then部分とelse部分の型が一致することを要求
- 結果はthen/else部分の型
while式
- 条件部分が真偽値型であることを要求
- 結果は整数型（便宜上0を返すため）
seq式
- 順番に式の型をチェックし、最後の式の型がseq式の型になる

型検査の実行タイミング

型検査は実行前に行われます。つまり、どのように実行されても型エラーは検出されます。

function evalJsonExpr(jsonString) {
  const jsonProgram = JSON.parse(jsonString);
  const program = translateExpr(jsonProgram);
  typeCheck(program, {});  // 型検査を実行
  return evalExpr(program, {});
}

これはどういうことかというと、たとえば以下のような「絶対に実行されないパス」に型エラーがあってもきちんとエラーとして検出されるということです。

["if", true,
  1,
  ["+", 2, false]]

if式の条件はtrueなので["+", 2, false]の部分は実行されないはずですが、以下のような型エラーになります。

Error in reading the file: Required: int + int actual: int + boolean

このように、あるパスを通るかにかかわらず型の不整合が常に検出されるのが静的型付けの（動的型付けと比べた場合の）利点です。

具体例

以下のプログラムで型検査の動作を確認してみましょう：

// 正しい型のプログラム
["seq",
  ["<-", "x", ["+", 1, 2]],  // xは整数型として定義される
  ["<-", "x", 4]             // xに整数を代入するのでOK
]

このプログラムは型検査をパスします。一方、以下のプログラムは型エラーになります：

// 型エラーになるプログラム
["seq",
  ["<-", "x", ["+", 1, 2]],  // xは整数型として定義される
  ["<-", "x", true]          // エラー：整数型の変数に真偽値を代入しようとしている
]

エラーメッセージは以下のようになります：

Error in reading the file: Since the variable x is declared as int, boolean cannot be assigned

変数xがintとして宣言されたので、booleanを代入できないということが正しく表示されていますね。本当ならJSONの何行目でエラーが出たのかまでわかるといいのですが、標準のJSON.parse()が返すオブジェクトは行番号を保持していないので仕方ありません。

プログラムの全体

今回対象とするプログラムは前回の言語のサブセットなので、改めてプログラム全体を示します。型チェックはインタプリタと同様に構文木を再帰的にたどる処理で、しかもエラーメッセージを作る都合上、やや長くなっています（全体で350行）：

const fs = require('fs');

// 式を表すクラス
class Expression {}
// 代入を表すクラス
class Assignment extends Expression {
  constructor(name, expr) {
    super();
    this.name = name;
    this.expr = expr;
  }
} 
// 二項演算子（+、-、*、/）のためのクラス
class BinExpr extends Expression {
  constructor(operator, lhs, rhs) {
    super();
    this.operator = operator;
    this.lhs = lhs;
    this.rhs = rhs;
  }
}
// 単項演算子（not）のためのクラス
class UnaryExpr extends Expression {
  constructor(operator, expr) {
    super();
    this.operator = operator;
    this.expr = expr;
  }
}
// 整数値のためのクラス
class Num extends Expression {
  constructor(value) {
    super();
    this.value = value;
  }
}
// 真偽値のためのクラス
class Bool extends Expression {
  constructor(value) {
    super();
    this.value = value;
  }
}
// 文字列のためのクラス
class Str extends Expression {
  constructor(value) {
    super();
    this.value = value;
  }
}
// 変数参照のためのクラス
class VarRef extends Expression {
  constructor(name){
    super();
    this.name = name;
  }
}

// 条件分岐のためのクラス
class If extends Expression {
  constructor(cond, thenExpr, elseExpr) {
    super();
    this.cond = cond;
    this.thenExpr = thenExpr;
    this.elseExpr = elseExpr;
  }
}

// 繰り返しのためのクラス
class While extends Expression {
  constructor(cond, body) {
    super();
    this.cond = cond;
    this.body = body;
  }
}

// 連接のためのクラス
class Seq extends Expression {
  constructor(...bodies) {
    super();
    this.bodies = bodies;
  }
}

class Type {
  constructor(name) {
    this.name = name;
  }
  equals(other) {
    return this.name === other.name;
  }
  toString() {
    return this.name;
  }
}
const INT_TYPE = new Type("int");
const BOOLEAN_TYPE = new Type("boolean");
const STRING_TYPE = new Type("string");

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

function translateExpr(jsonObject) {
  if(Array.isArray(jsonObject)) {
    const operator = jsonObject[0];
    switch(operator) {
      case "+":
        return new BinExpr("+", translateExpr(jsonObject[1]), translateExpr(jsonObject[2]));
      case "-":
        return new BinExpr("-", translateExpr(jsonObject[1]), translateExpr(jsonObject[2]));
      case "*":
        return new BinExpr("*", translateExpr(jsonObject[1]), translateExpr(jsonObject[2]));
      case "/":
        return new BinExpr("/", translateExpr(jsonObject[1]), translateExpr(jsonObject[2]));
      case "%":
        return new BinExpr("%", translateExpr(jsonObject[1]), translateExpr(jsonObject[2]));
      case "<":
        return new BinExpr("<", translateExpr(jsonObject[1]), translateExpr(jsonObject[2]));
      case ">":
        return new BinExpr(">", translateExpr(jsonObject[1]), translateExpr(jsonObject[2]));
      case "<=":
        return new BinExpr("<=", translateExpr(jsonObject[1]), translateExpr(jsonObject[2]));
      case ">=":
        return new BinExpr(">=", translateExpr(jsonObject[1]), translateExpr(jsonObject[2]));
      case "==":
        return new BinExpr("==", translateExpr(jsonObject[1]), translateExpr(jsonObject[2]));
      case "!=":
        return new BinExpr("!=", translateExpr(jsonObject[1]), translateExpr(jsonObject[2]));
      case "and":
        return new BinExpr("and", translateExpr(jsonObject[1]), translateExpr(jsonObject[2]));
      case "or":
        return new BinExpr("or", translateExpr(jsonObject[1]), translateExpr(jsonObject[2]));
      case "not":
        return new UnaryExpr("not", translateExpr(jsonObject[1]));
      case "seq":
        return new Seq(...jsonObject.slice(1).map(translateExpr));
      case "if":
        return new If(translateExpr(jsonObject[1]), translateExpr(jsonObject[2]), translateExpr(jsonObject[3]));
      case "while":
        return new While(translateExpr(jsonObject[1]), translateExpr(jsonObject[2]));
      case "<-":
        return new Assignment(jsonObject[1], translateExpr(jsonObject[2]));
      case "ref":
        return new VarRef(jsonObject[1]);
    }
  }
  switch (typeof jsonObject) {
    case "number":
      return new Num(jsonObject);
    case "string":
      return new Str(jsonObject);
    case "boolean":
      return new Bool(jsonObject);
  }
  throw "Not implemented for: " + JSON.stringify(jsonObject);
}

function evalJsonExpr(jsonString) {
    const jsonProgram = JSON.parse(jsonString);
    const program = translateExpr(jsonProgram);
    typeCheck(program, {});
    return evalExpr(program, {});
}

function evalExpr(expr, env) {
  if(expr instanceof BinExpr) {
    const resultL = evalExpr(expr.lhs, env);
    const resultR = evalExpr(expr.rhs, env);
    switch(expr.operator) {
      case "+":
        return resultL + resultR;
      case "-":
        return resultL - resultR;
      case "*":
        return resultL * resultR;
      case "/":
        return resultL / resultR;
      case "%":
        return resultL % resultR;
      case "<":
        return resultL < resultR;
      case ">":
        return resultL > resultR;
      case "<=":
        return resultL <= resultR;
      case ">=":
        return resultL >= resultR;
      case "==":
        return resultL === resultR;
      case "!=":
        return resultL !== resultR;
      case "and":
        return resultL && resultR;
      case "or":
        return resultL || resultR;
    }
  } else if(expr instanceof UnaryExpr) {
    const result = evalExpr(expr.expr, env);
    switch(expr.operator) {
      case "not":
        return !result;
    }
  } else if(expr instanceof Num) {
     return expr.value;
  } else if(expr instanceof Bool) {
     return expr.value;
  } else if(expr instanceof Str) {
     return expr.value;
  } else if(expr instanceof VarRef) {
     if (!(expr.name in env)) {
       throw `Variable ${expr.name} is not defined`;
     }
     return env[expr.name];
  } else if(expr instanceof Assignment) {
     const result = evalExpr(expr.expr, env);
     env[expr.name] = result;
     return result;
  } else if(expr instanceof Seq) {
     let result = null;
     expr.bodies.forEach((e) => {
        result = evalExpr(e, env);
     });
     return result;
  } else if(expr instanceof If) {
     if(evalExpr(expr.cond, env)) {
       return evalExpr(expr.thenExpr, env);
     }else {
       return evalExpr(expr.elseExpr, env);
     }
  } else if(expr instanceof While) {
     while(evalExpr(expr.cond, env)) {
       evalExpr(expr.body, env);
     }
     return 0;
  } else {
     console.assert(false, `should not reach here ${expr}`);
  }
}

function typeCheck(expr, typeEnv) {
  if(expr instanceof BinExpr) {
    const typeL = typeCheck(expr.lhs, typeEnv);
    const typeR = typeCheck(expr.rhs, typeEnv);
    switch(expr.operator) {
      case "+":
      case "-":
      case "*":
      case "/":
      case "%":
        if(!typeL.equals(INT_TYPE) || !typeR.equals(INT_TYPE)) {
          throw `Required: ${INT_TYPE} ${expr.operator} ${INT_TYPE} actual: ${typeL} ${expr.operator} ${typeR}`;
        }
        return INT_TYPE;
      case "<":
      case ">":
      case "<=":
      case ">=":
        if(!typeL.equals(INT_TYPE) || !typeR.equals(INT_TYPE)) {
          throw `Required: ${INT_TYPE} ${expr.operator} ${INT_TYPE}, actual: ${typeL} ${expr.operator} ${typeR}`;
        }
        return BOOLEAN_TYPE;
      case "==":
      case "!=":
        if(!typeL.equals(typeR)) {
          throw `Left and right must be equal. actual: ${typeL} ${expr.operator} ${typeR}`;
        }
        return BOOLEAN_TYPE
      case "and":
      case "or":
        if(!typeL.equals(BOOLEAN_TYPE) || !typeR.equals(BOOLEAN_TYPE)) {
          throw `Required: ${BOOLEAN_TYPE} ${expr.operator} ${BOOLEAN_TYPE}, actual: ${typeL} ${expr.operator} ${typeR}`;
        }
        return BOOLEAN_TYPE;
    }
  } else if(expr instanceof UnaryExpr) {
    const typeL = typeCheck(expr.expr, typeEnv);
    switch(expr.operator) {
      case "not":
        if(!typeL.equals(BOOLEAN_TYPE)) {
          throw `Required: not ${BOOLEAN_TYPE}, actual: not ${typeL}`;
        }
        return BOOLEAN_TYPE;
    }
  } else if(expr instanceof Num) {
    return INT_TYPE;
  } else if(expr instanceof Bool) {
    return BOOLEAN_TYPE;
  } else if(expr instanceof Str) {
    return STRING_TYPE;
  } else if(expr instanceof VarRef) {
     if (!(expr.name in typeEnv)) {
       throw `Variable ${expr.name} is not defined`;
     }
     return typeEnv[expr.name];
  } else if(expr instanceof Assignment) {
     const valueType = typeCheck(expr.expr, typeEnv);
     const name = expr.name;
     if(!(name in typeEnv)) {
       typeEnv[name] = valueType;
       return valueType;
     }
     if(!typeEnv[name].equals(valueType)) {
         throw `Since the variable ${name} is declared as ${typeEnv[name]}, ${valueType} cannot be assigned`;
     }
     return valueType;
  } else if(expr instanceof Seq) {
     let resultType;
     expr.bodies.forEach((e) => {
        resultType = typeCheck(e, typeEnv);
     });
     return resultType;
  } else if(expr instanceof If) {
      const condType = typeCheck(expr.cond, typeEnv);
      if(!condType.equals(BOOLEAN_TYPE)) {
          throw `If expression's condition must be ${BOOLEAN_TYPE}.  Actual: ${condType}`;
      }
      const thenType = typeCheck(expr.thenExpr, typeEnv);
      const elseType = typeCheck(expr.elseExpr, typeEnv);
      if(!thenType.equals(elseType)) {
         throw `If expression's then and else must be equal.  Actual: ${thenType} != ${elseType}`;
      }
      return thenType;
  } else if(expr instanceof While) {
      const condType = typeCheck(expr.cond, typeEnv);
      if(!condType.equals(BOOLEAN_TYPE)) {
          throw `While expression's condition must be ${BOOLEAN_TYPE}.  actual: ${condType}`;
      }
      const bodyType = typeCheck(expr.body, typeEnv);
      return INT_TYPE;
  } else {
     console.assert(false, `should not reach here ${expr}`);
  }
}

try {
  const program = fs.readFileSync(process.argv[2], 'utf8');
  console.log(evalJsonExpr(program));
} catch (err) {
  console.error('Error in reading the file:', err);
}

まとめ

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

基本的な型システムの導入
リテラルの型検査
演算子の型検査
変数宣言/代入の型検査
制御構文の型検査

静的型検査により、プログラムの実行前に型の不整合を検出できるようになりました。次回は、この実装をベースに、関数の定義や関数呼び出しの型チェックを実装していきます。

お楽しみに！

nextbeat Tech BlogPublication

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