Zenn
nextbeat Tech BlogPublicationへの投稿
🐥

JavaScriptで作る！ミニ言語のインタプリタ（６）〜データ型を追加する〜

kmizu
2024/10/24に公開
JavaScript
プログラミング
language
tech

はじめに

前回の記事では、JSONでプログラムを記述し、それを読み込んで実行できるように拡張しました。今回は、インタプリタに新しいデータ型を追加していきます。これまでは数値型のみを扱っていましたが、プログラミング言語として実用的にするために、真偽値型と文字列型を追加します。

データ型の追加

まず、新しいデータ型を表現するためのクラスを追加します。以下が差分です：

+ // 真偽値のためのクラス
+ class Bool extends Expression {
+   constructor(value) {
+     super();
+     this.value = value;
+   }
+ }
+ 
+ // 文字列のためのクラス
+ class Str extends Expression {
+   constructor(value) {
+     super();
+     this.value = value;
+   }
+ }

これらのクラスは既存のNumクラスと同様の構造を持っています。各クラスはExpressionクラスを継承し、値を保持するためのvalueフィールドを持ちます。

演算子の拡張

新しいデータ型を追加したことで、それらに対する演算子も実装する必要があります。特に、論理演算子（and、or、not）を追加します。andとorは以下の既存のクラスで取り扱えます。

 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;
+   }
+ }

JSONからの変換の拡張

次に、JSONからこれらの型への変換を可能にするために、translateExpr関数を拡張します：

 function translateExpr(jsonObject) {
   if(Array.isArray(jsonObject)) {
     const operator = jsonObject[0];
     switch(operator) {
       // ... 既存の演算子 ...
+      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]));
     }
   }
   switch (typeof jsonObject) {
     case "number":
       return new Num(jsonObject);
+    case "string":
+      return new Str(jsonObject);
+    case "boolean":
+      return new Bool(jsonObject);
   }
   throw new Error("Not implemented for: " + JSON.stringify(jsonObject));
 }

評価器の拡張と改善

評価器であるeval関数には、2つの重要な変更を加えました：

  1. 新しい型と演算子のサポート
  2. 比較演算子や制御構文の戻り値の改善

以下が変更の差分です：

 function eval(expr, env, funEnv, builtinFunEnv) {
   if(expr instanceof BinExpr) {
     const resultL = eval(expr.lhs, env, funEnv, builtinFunEnv);
     const resultR = eval(expr.rhs, env, funEnv, builtinFunEnv);
     switch(expr.operator) {
       // ... 既存の演算子 ...
       case "<":
-        return resultL < resultR ? 1 : 0;
+        return resultL < resultR;
       case ">":
-        return resultL > resultR ? 1 : 0;
+        return resultL > resultR;
       case "<=":
-        return resultL <= resultR ? 1 : 0;
+        return resultL <= resultR;
       case ">=":
-        return resultL >= resultR ? 1 : 0;
+        return resultL >= resultR;
       case "==":
-        return resultL === resultR ? 1 : 0;
+        return resultL === resultR;
       case "!=":
-        return resultL !== resultR ? 1 : 0;
+        return resultL !== resultR;
+      case "and":
+        return resultL && resultR;
+      case "or":
+        return resultL || resultR;
     }
+  } else if(expr instanceof UnaryExpr) {
+    const result = eval(expr.expr, env, funEnv, builtinFunEnv);
+    switch(expr.operator) {
+      case "not":
+        return !result;
+    }
   } else if(expr instanceof Bool) {
     return expr.value;
   } else if(expr instanceof Str) {
     return expr.value;
   }
   // ...
   } else if(expr instanceof If) {
-     if(eval(expr.cond, env, funEnv, builtinFunEnv) !== 0) {
+     if(eval(expr.cond, env, funEnv, builtinFunEnv)) {
        return eval(expr.thenExpr, env, funEnv, builtinFunEnv);
      }else {
        return eval(expr.elseExpr, env, funEnv, builtinFunEnv);
      }
   } else if(expr instanceof While) {
-     while(eval(expr.cond, env, funEnv, builtinFunEnv) !== 0) {
+     while(eval(expr.cond, env, funEnv, builtinFunEnv)) {
        eval(expr.body, env, funEnv, builtinFunEnv);
      }
   // ...
 }

注目すべき変更点は、比較演算子およびif,whileの戻り値の扱いです。これまでは1または0を返していましたが、今回の変更でtrueまたはfalseを直接返すようになりました。これには以下のような利点があります：

  1. JavaScriptの標準的な動作との一貫性
  2. 論理演算子（and、or、not）との自然な連携
  3. 条件分岐での直感的な使用

文字列操作のための組み込み関数も追加しました：

 const builtinFunEnv = {
   // ... 既存の関数 ...
+  'length': new BuiltinFun('length', (args) => args[0].length),
+  'charAt': new BuiltinFun('charAt', (args) => args[0].charAt(args[1])),
+  'slice': new BuiltinFun('slice', (args) => args[0].slice(args[1], args[2])),
 };

プログラム例

では、新しい機能を使ったプログラムの例を見てみましょう。以下は古典的なFizzBuzz問題を解くプログラムです：

{
  "functions": [
    ["fizzbuzz", ["n"],
      ["if", ["==", ["%", ["ref", "n"], 15], 0],
        "FizzBuzz",
        ["if", ["==", ["%", ["ref", "n"], 3], 0],
          "Fizz",
          ["if", ["==", ["%", ["ref", "n"], 5], 0],
            "Buzz",
            ["ref", "n"]]]]]
  ],
  "body": ["seq",
    ["<-", "i", 1],
    ["while", ["<=", ["ref", "i"], 100],
      ["seq",
        ["call", "print", ["call", "fizzbuzz", ["ref", "i"]]],
        ["<-", "i", ["+", ["ref", "i"], 1]]]]]
}

このプログラムでは：

  1. 文字列リテラル（"FizzBuzz"、"Fizz"、"Buzz"）を使用
  2. 真偽値を返す比較演算子（==、<=）を使用
  3. 数値演算（+、%）と文字列を組み合わせて使用

しています。比較演算子が直接真偽値を返すようになったことで、if文の条件部分がより自然に書けるようになっていることに注目してください。

処理系のプログラム全体

ここまでだいぶ改修に改修を重ねたため、現在の処理系全体のコードを改めて以下に示します。最初に比べてだいぶ機能が増えましたが、それでも行数にして300行程度です：

//プログラム全体
class Program {
  constructor(defs, ...expressions){
    this.defs = defs;
    this.expressions = expressions;
  }
}
//関数定義を表すクラス
class FunDef {
  constructor(name, args, body) {
    this.name = name;
    this.args = args;
    this.body = body;
  }
}
// 式を表すクラス
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 FunCall extends Expression {
  constructor(name, ...args) {
    super();
    this.name = name;
    this.args = args;
  }
}

// 条件分岐のためのクラス
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 BuiltinFun {
  constructor(name, func) {
    this.name = name;
    this.func = func;
  }
}

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]);
      case "call":
        return new FunCall(jsonObject[1], ...jsonObject.slice(2).map(translateExpr));
    }
  }
  switch (typeof jsonObject) {
    case "number":
      return new Num(jsonObject);
    case "string":
      return new Str(jsonObject);
    case "boolean":
      return new Bool(jsonObject);
  }
  throw new Error("Not implemented for: " + JSON.stringify(jsonObject));
}

/* 
 * {"functions": [
 *    ["add", ["x", "y"] , ["+", x, y]], ...
 *  ], 
 *  "body": ["call", 1, 2]
 * }
 */
function translateProgram(jsonProgram) {
  const defs = jsonProgram['functions'].map(f => 
    new FunDef(f[0], f[1], translateExpr(f[2]))
  );
  const body = translateExpr(jsonProgram['body']);
  return new Program(defs, body);
}

function evalProgram(program) {
  const env = {};
  const funEnv = {};
  const builtinFunEnv = {
    'print': new BuiltinFun('print', (args) => {
      console.log(...args);
      return args[0];
    }),
    'input': new BuiltinFun('input', () => {
      return prompt('Enter input:');
    }),
    'add': new BuiltinFun('add', (args) => args.reduce((a, b) => a + b, 0)),
    'mul': new BuiltinFun('mul', (args) => args.reduce((a, b) => a * b, 1)),
    'length': new BuiltinFun('length', (args) => args[0].length),
    'chatAt': new BuiltinFun('chatAt', (args) => args[0].charAt(args[1])),
    'slice': new BuiltinFun('slice', (args) => args[0].slice(args[1], args[2])),
  };
  let result = null;
  program.defs.forEach((d) => {
    funEnv[d.name] = d;
  });
  program.expressions.forEach((e) => {
    result = eval(e, env, funEnv, builtinFunEnv);
  });
  return result;
}

function evalJsonProgram(jsonString) {
    const jsonProgram = JSON.parse(jsonString);
    const program = translateProgram(jsonProgram);
    return evalProgram(program);
}

function eval(expr, env, funEnv, builtinFunEnv) {
  if(expr instanceof BinExpr) {
    const resultL = eval(expr.lhs, env, funEnv, builtinFunEnv);
    const resultR = eval(expr.rhs, env, funEnv, builtinFunEnv);
    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 = eval(expr.expr, env, funEnv, builtinFunEnv);
    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 new Error(`variable ${expr.name} is not defined`);
     }
     return env[expr.name];
  } else if(expr instanceof Assignment) {
     const result = eval(expr.expr, env, funEnv, builtinFunEnv);
     env[expr.name] = result;
     return result;
  } else if(expr instanceof Seq) {
     let result = null;
     expr.bodies.forEach((e) => {
        result = eval(e, env, funEnv, builtinFunEnv);
     });
     return result;
  } else if(expr instanceof If) {
     if(eval(expr.cond, env, funEnv, builtinFunEnv)) {
       return eval(expr.thenExpr, env, funEnv, builtinFunEnv);
     }else {
       return eval(expr.elseExpr, env, funEnv, builtinFunEnv);
     }
  } else if(expr instanceof While) {
     while(eval(expr.cond, env, funEnv, builtinFunEnv)) {
       eval(expr.body, env, funEnv, builtinFunEnv);
     }
     return 0;
  } else if(expr instanceof FunCall) {
     const def = funEnv[expr.name] || builtinFunEnv[expr.name];
     if(!def) throw `function ${expr.name} is not defined`;

     const args = expr.args.map((a) => eval(a, env, funEnv, builtinFunEnv));

     if (def instanceof BuiltinFun) {
       return def.func(args);
     }

     const newEnv = {}
     for(let i = 0; i < def.args.length; i++) {
       newEnv[def.args[i]] = args[i];
     }
     return eval(def.body, newEnv, funEnv, builtinFunEnv);
  } else {
     console.assert(false, `should not reach here ${expr}`);
  }
}

const fs = require('fs');

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

まとめ

今回の記事では、インタプリタに以下の機能を追加・改善しました：

  1. 真偽値型と文字列型の追加
  2. 論理演算子（and、or、not）の実装
  3. 比較演算子の戻り値を真偽値に変更
  4. 文字列操作のための組み込み関数の追加

これらの変更により、インタプリタはより実用的なプログラムを扱えるようになり、また式の評価がより自然になりました。次回は、静的型システムを導入し、プログラムの型安全性を確保する方法について説明します。

お楽しみに！

nextbeat Tech Blog
nextbeat Tech BlogPublication

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

Discussion