it.todo("should be a (web)log");

役に立(つ/たない)技術情報やポエム

Docker Buildのトレースを集約してみよう

テクノロジー OpenTelemetry

この記事は Mackerel Advent Calendar 2024 の24日目の記事です。昨日は id:mrasu さんの オブザーバビリティ成熟度の頂点とその先 でした。

Mackerel チームでアルバイトをしている id:tosukee です。近年の Docker Build は BuildKit を使っていることが多いと思います。BuildKit によりステージを並列に実行することが可能になっていますが、実際ステージが意図通りに並列に実行されているのかやどのステージがボトルネックになっているのか*1が気になることもあるでしょう。

*1:つまり並列化に意味があるのか

続きを読む

OpenTelemetry Collectorでコンテナのログをファイルから取る

テクノロジー OpenTelemetry

呑気にOSをアップデートしたら今までjournalに出ていたコンテナのログが出なくなってしまった。 今までコンテナのログもjournaldから取ってOpenTelemetry Collectorで集約していたが、これを機にファイルから取る方法を試すことにした。

続きを読む

Windows on Linux で快適ゲーム生活

これは天久保 Advent Calendar 2023の6日目の記事です(遅刻。

天久保には居住していませんが「天久保」は町域とは関係ありませんので書きます。

Linux Gaming とその方法

Linux 環境でゲームをプレイすることは「どのように Linux 上で Windows のプログラムを動作させるか？」という問題と同じと言ってもよいでしょう *1。 なぜならほとんどの PC 向けのゲームは Windows のみにしかリリースされないからです *2。

この互換性問題を解決するため、大きく分けて2つのアプローチが存在します。

*1:これは Windows ではない環境全て、例えば macOS にも当てはまります

*2:逆に macOS 向けも出る場合なぜか Linux 版が存在する確率も高いような気がしている。作者がマルチプラットフォームに気持ちがあるということ？

続きを読む

3時間半くらいではじめる自作言語

この記事は MIS.W 54代アドカレ の8日目の記事です(まだ12/8だしセーフセーフ)

前回の記事はSEED????さんの「つくってあそぼ（ローグライクのダンジョン生成）+おまけ」でした。

こんにちは。とすけです。最近PCを新調してはしゃいでいます。 今回は3時間くらいでどこまで言語処理系を書けるか試してみたのでコミットログを追いつつ解説をしていきたいと思います。 リポジトリはtosuke-lab/lang_rta、言語はTypeScriptです。ライブラリを使わずに1ファイルに書いていっているので、TypeScript Playgroud で試していきつつ読んでもらえるとうれしかったりします。

パーサってなんだ

言語処理系って結局は「文字列を処理してなんかするやつ」なんですが、文字列っていうのはコンピュータからしたらバイトの並びなわけで、処理系として扱いやすい形にしてやるとうれしいわけです。そこで、パーサというものを導入します。

type Result<A> =
  | { type: "success"; consumed: number; result: A }
  | { type: "failure"; reasons: string[] };

const parseSuccess = <A>(result: A, consumed: number): Result<A> => ({
  type: "success",
  consumed,
  result
});
const parseFailure = <A>(reasons: string[]): Result<A> => ({
  type: "failure",
  reasons
});

type Parser<A> = (src: string) => Result<A>;

一番下のParser<A>が本体です。気持ちとしては「文字列を受け取ってA型の値を返す関数」です。じゃあなんで(src: string) => Aにならないのかというと、

  • 文字列を処理したときにエラーが起きる可能性がある
  • 何文字処理したのか知りたい

みたいな理由があるからです。「エラー処理は例外でやればいいじゃないか!」と思う人もいるかもしれないですが、パーサの処理で起きるエラーはプログラム上で意図していない"例外"ではなく、想定すべき処理なので返り値として表現します。

上で書いたような性質を表現したのがResult<A>です。Union Typeを使って成功/失敗を表現しています。parseSuccessとparseFailureはオブジェクトリテラルを書くのを横着するためのユーティリティです。

パーサ書く

パーサを書いてみる

試しに、「文字列の先頭に"hoge"という文字列があったらそれを切り出す」パーサを書いてみましょう。

// hogeで成功するパーサ
const hogeParser: Parser<string> = src =>
  src.startsWith("hoge")
    ? parseSuccess("hoge", 4)
    : parseFailure([`expect 'hoge', but got '${src.slice(0, 4)}'`]);

startsWithを使ってsrcが"hoge"から始まるかを判定して、始まっていたら切り出した"hoge"と処理した文字数4を、違っていたらエラーを返しています。(特に言うことがない顔)

ここまでの変更はb828b7aです。

パーサを値として扱う

先ほど書いたhogeParserを一般化して、"hoge"だけでなく、「任意の文字列を受け取って、受け取った文字列の先頭から切り出すパーサ」にしてみましょう。これの型を考えてみると、「切り出す文字列に対してパーサができる」ので、(lit: string) => Parser<string> みたいになるはずです。やってみましょう。

const constParser = (lit: string): Parser<string> => src =>
  src.startsWith(lit)
    ? parseSuccess(lit, lit.length)
    : parseFailure([`expect 'hoge', but got '${src.slice(0, lit.length)}'`]);

関数を返す関数????となるかもしれませんが、これでいいのです。 パーサは関数で、関数はTypeScript(ECMAScript)では値なので、パーサも値として扱うことができるわけです。べんり。

これでhogeParserをconstParserを使って定義できます。

const hogeParser = constParser("hoge");

ここまでの変更はe808264です。

数字を処理するパーサ

(10進数の)数字を処理して数にするパーサを書いてみます。ここでは色々横着して正規表現を使ってしまいます。

const numRegex = /^\-?\d+/;
const numParser: Parser<number> = src => {
  const match = numRegex.exec(src);
  if (match) {
    return parseSuccess(parseInt(match[0], 10), match[0].length);
  } else {
    return parseFailure([`expect a number, but got '${src[0]}...'`]);
  }
};

console.log("11")とかで試してみるとうまく動きますが、この実装、「文字列から数字を切り出そうとする」処理と「切り出した文字列を数値に変換する」処理が一緒になってしまっています。なんか気持ち悪いので分解したいですね!(ご都合主義)

ここで、「文字列から数字を切り出す」部分だけを書いてみます。

const numRegex = /^\-?\d+/;
const numStringParser: Parser<string> = src => {
  const match = numRegex.exec(src);
  if (match) {
    return parseSuccess(match[0], match[0].length);
  } else {
    return parseFailure([`expect a number, but got '${src[0]}...'`]);
  }
};

「数字の文字列を数値に変換する処理」はこんな感じに書けるはずです。

const stringToNum = (str: string): number => parseInt(str, 10)

どうにかしてnumStringParserとstringToNumを合成したいわけです。 型で考えると、Parser<string>をParser<number>にしたいということになるので、Parserに対してメソッドを生やしたくなってきます。(なるよね???) ということで、とりあえずParserをclassを使って定義し直します。

class Parser<A> {
  constructor(readonly parse: (src: string) => Result<A>) {}
}

今までの定義がプロパティになっただけですね。

ここまでのソースは73bf623です。変更が細かいのでコピペしてしまうのが吉。

Parserにメソッドを生やします。(x: A) => Bみたいな関数をParser<A>に適用してParser<B>にするみたいなイメージですが、これはArrayのmapとやってることは同じです。ということでこのメソッドの名前もmapにしてしまいましょう。

class Parser<A> {
  constructor(readonly parse: (src: string) => Result<A>) {}
  map<B>(f: (x: A) => B) {
    return new Parser(src => {
      const r = this.parse(src);
      if (r.type === "success") {
        return parseSuccess(f(r.result), r.consumed);
      } else {
        return r;
      }
    });
  }
}

パースをしてみて、成功していたら渡された関数を適用して、失敗していたらエラーをそのまま返します。

これを使ってnumParserをいい感じにしてみましょう。長かった…

const numRegex = /^\-?\d+/;
const numParser = new Parser<string>(src => {
  const match = numRegex.exec(src);
  if (match) {
    return parseSuccess(match[0], match[0].length);
  } else {
    return parseFailure([`expect a number, but got '${src[0]}...'`]);
  }
}).map(x => parseInt(x, 10));

ここまでのソースは32d76f4です。

処理系を書く

足し算を処理してみる

ここまでで素材がそろってきたのでそろそろ言語処理系っぽいことをします。 ということで、"1+1"を受け取って2を返すような処理をするパーサを書いてみます。 数字を処理するパーサと文字列を切り出すパーサがあるので、結果の消費文字数を見ていい感じに適用していけばいいですね。

// 足し算を処理するパーサ
const plusParser = new Parser<number>(src => {
  let consumed = 0;
  const lhs = numParser.parse(src);
  if (lhs.type === "success") {
    consumed += lhs.consumed;
    const plus = constParser("+").parse(src.slice(consumed));
    if (plus.type === "success") {
      consumed += plus.consumed;
      const rhs = numParser.parse(src.slice(consumed));
      if (rhs.type === "success") {
        consumed += rhs.consumed;
        return parseSuccess(lhs.result + rhs.result, consumed);
      } else {
        return rhs;
      }
    } else {
      return plus;
    }
  } else {
    return lhs;
  }
});

こ れ は ひ ど い 同じようなコードがネストして繰り返されています…文法が複雑になるほどネストが増えていくので、ネスト波動拳の足音を感じてしまいます…

f:id:tosukee:20191208194544j:plain
ネスト波動拳

幸いにもネストの単位にはパターンがあるので、いい感じに切り出せそうです。 Parser<A>、Parser<B>、Parser<C>を受け取ってParser<[A,B,C]>にしてくれるような関数があればよさそうです。

// パーサを繋ぐ
function seq<A>(p1: Parser<A>): Parser<[A]>;
function seq<A, B>(p1: Parser<A>, p2: Parser<B>): Parser<[A, B]>;
function seq<A, B, C>(
  p1: Parser<A>,
  p2: Parser<B>,
  p3: Parser<C>
): Parser<[A, B, C]>;
function seq<A, B, C, D>(
  p1: Parser<A>,
  p2: Parser<B>,
  p3: Parser<C>,
  p4: Parser<D>
): Parser<[A, B, C, D]>;
function seq<A, B, C, D, E>(
  p1: Parser<A>,
  p2: Parser<B>,
  p3: Parser<C>,
  p4: Parser<D>,
  p5: Parser<E>
): Parser<[A, B, C, D, E]>;
function seq(...parsers: Parser<unknown>[]): Parser<any[]> {
  return new Parser(src => {
    const result: unknown[] = [];
    let consumed = 0;
    for (const parser of parsers) {
      const r = parser.parse(src.slice(consumed));
      if (r.type === "failure") return r;
      consumed += r.consumed;
      result.push(r.result);
    }
    return parseSuccess(result, consumed);
  });
}

これでパーサがいくつあってもネストを発生させずに繋げることができますね! このseqを使ってplusParserを書き直します。

const plusParser = seq(
  numParser,
  constParser("+"),
  numParser
).map(([lhs, , rhs]) => lhs + rhs);

実はこのplusParser、"1 + 1"のようにスペースが入った文字列を処理することができません。これは仕様だ!と言い張ることもできますが、気持ち悪いので直してしまいましょう。

スペースを処理するパーサを追加して

const spaceRegex = /^\s*/;
const spaceParser = new Parser<string>(src => {
  const match = spaceRegex.exec(src);
  if (match) {
    return parseSuccess(match[0], match[0].length);
  }
  throw "unreachable!";
});

plusParserに追加するだけです。

const plusParser = seq(
  numParser,
  spaceParser,
  constParser("+"),
  spaceParser,
  numParser
).map(([lhs, , , , rhs]) => lhs + rhs);

seqがなければネスト地獄が発生しているところでしたが、seqのおかげで簡潔に書けるようになっていて、いいですね。 ここまでのソースはfdf4deeです。seqの定義がすごく長いのでコピペしてしまうのが吉です。(実は少し複雑な型を使えばseqに正しい型付けをすることができます。本筋から外れちゃうので書きませんが)

引き算も処理する

足し算もできるようになったので、引き算も処理したいですね。plusParserを少しいじればできそうです。 とりあえず、constParser("+")の部分を"+"も"-"も受け取れるようにしてみましょう。

const opParser = new Parser<string>(src => {
  const reasons: string[] = [];
  const plus = constParser("+").parse(src);
  if (plus.type === "failure") {
    reasons.push(...plus.reasons);
    const minus = constParser("-").parse(src);
    if (minus.type === "failure") {
      reasons.push(...minus.reasons);
      return parseFailure(reasons);
    }
    return minus;
  }
  return plus;
});

const plusMinusParser = seq(
  numParser,
  spaceParser,
  opParser,
  spaceParser,
  numParser
).map(([lhs, , op, , rhs]) => (op === "+" ? lhs + rhs : lhs - rhs));

またネストが出現しましたね…これも一般化してしまいましょう。

// パーサを並べて、最初に成功したものを返す
const or = <A>(...parsers: Parser<A>[]) =>
  new Parser<A>(src => {
    const reasons: string[] = [];
    for (const parser of parsers) {
      const r = parser.parse(src);
      if (r.type === "success") return r;
      reasons.push(...r.reasons);
    }
    return parseFailure(reasons);
  });

このorを使ってplusMinusParserは次のように書けます。

const plusMinusParser = seq(
  numParser,
  spaceParser,
  or(constParser("+"), constParser("-")),
  spaceParser,
  numParser
).map(([lhs, , op, , rhs]) => (op === "+" ? lhs + rhs : lhs - rhs));

ここまでのソースはbc6fd6eです。

何回でも足し引きできるようにする

今までのplusMinusParserだと"1+1-2"のような複数の計算ができません。 このような式を眺めると"1" "+1" "-2"のように分けられて、数字の後に演算子と数字のペアが繰り返されることがわかります。つまり「繰り返し」を表現することができればいいわけです。書いてみましょう。

const plusMinus = new Parser<["+" | "-", number][]>(src => {
  const tmp = seq(
    spaceParser,
    or(constParser("+"), constParser("-")),
    spaceParser,
    numParser
  ).map(
    ([, op, , num]) =>
      [op === "+" ? ("+" as const) : ("-" as const), num] as const
  );
  const result: ["+" | "-", number][] = [];
  let consumed = 0;
  while (true) {
    const r = tmp.parse(src.slice(consumed));
    if (r.type === "failure") return parseSuccess(result, consumed);
    const [op, num] = r.result;
    result.push([op, num]);
    consumed += r.consumed;
  }
});
const plusMinusParser = seq(numParser, plusMinus).map(([num, ops]) => {
  for (const op of ops) {
    if (op[0] === "+") num += op[1];
    else num -= op[1];
  }
  return num;
});

plusMinusでtmpの内容を繰り返しています。これでもちゃんと動きますが、「繰り返されるパーサ」と「繰り返し」の処理が同居しているのは少し気持ち悪いので、一般化してみましょう。

// パーサを連続して適用する
const many = <A>(parser: Parser<A>) =>
  new Parser<A[]>(src => {
    const result: A[] = [];
    let consumed = 0;
    while (true) {
      const r = parser.parse(src.slice(consumed));
      if (r.type === "failure") return parseSuccess(result, consumed);
      result.push(r.result);
      consumed += r.consumed;
    }
  });

このmanyを使って、plusMinusParserはこのように書けます。

const plusMinusParser = seq(
  numParser,
  many(
    seq(
      spaceParser,
      or(constParser("+"), constParser("-")),
      spaceParser,
      numParser
    ).map(
      ([, op, , num]) =>
        [op === "+" ? ("+" as const) : ("-" as const), num] as const
    )
  )
).map(([num, ops]) => {
  for (const op of ops) {
    if (op[0] === "+") num += op[1];
    else num -= op[1];
  }
  return num;
});

かなりすっきりしたのがわかると思います。

ここまでのソースは745c93fです。

パースと計算を分ける

今まではパーサが計算も行っていましたが、この方法で変数の名前の管理など、少し複雑なことをしようとすると難しくなります。そこで、パーサでは「計算を行うのに便利な値」を生成するのに留めて、計算はまた別の場所で行うことにします。

抽象構文木(AST)を定義する

よくパーサで作られる値として、抽象構文木と呼ばれるものがあります。これは入力したプログラムの無駄な要素を落として構造化したもので、これを中間の値として生成することで、無理なくパースと計算を分離することができます。定義してみましょう。

class Literal {
  constructor(readonly value: number) {}
}

class Add {
  constructor(readonly lhs: Expr, readonly rhs: Expr) {}
}

class Sub {
  constructor(readonly lhs: Expr, readonly rhs: Expr) {}
}

type Expr = Literal | Add | Sub;

Literalはただの数です。"1"など、計算を含まない入力をパースした結果できます。

AddとSubは計算を表します。"1+1"はnew Add(new Literal(1), new Literal(1))として表現できます。

パーサがASTを返すようにする

numParserは簡単です。今まで返していた値をLiteralでラップするだけです。

const numRegex = /^\-?\d+/;
const numParser = new Parser<string>(src => {
  const match = numRegex.exec(src);
  if (match) {
    return parseSuccess(match[0], match[0].length);
  } else {
    return parseFailure([`expect a number, but got '${src[0]}...'`]);
  }
}).map(x => new Literal(parseInt(x, 10)));

plusMinusParserは少し難しいですが、"1+2+3"が"(1+2)+3"であると考えれば理解できると思います。

const plusMinusParser = seq(
  numParser,
  many(
    seq(
      spaceParser,
      or(constParser("+"), constParser("-")),
      spaceParser,
      numParser
    ).map(
      ([, op, , expr]) =>
        [op === "+" ? ("+" as const) : ("-" as const), expr] as const
    )
  )
).map(([num, ops]) =>
  ops.reduce(
    (pre, op) => (op[0] === "+" ? new Add(pre, op[1]) : new Sub(pre, op[1])),
    num as Expr
  )
);

ASTを評価する

const evaluate = (ast: Expr): number => {
  if (ast instanceof Literal) {
    return ast.value;
  } else if (ast instanceof Add) {
    return evaluate(ast.lhs) + evaluate(ast.rhs);
  } else if (ast instanceof Sub) {
    return evaluate(ast.lhs) - evaluate(ast.rhs);
  } else {
    const _exhaustiveCheck: never = ast;
    throw "unreached";
  }
};

const run = (src: string) => {
  const r = plusMinusParser.parse(src);
  if (r.type === "failure") {
    console.error(r.reasons);
    return;
  }
  const ast = r.result;
  console.log(evaluate(ast));
};

評価は再帰を使って辿っていくだけです。競プロの人とか得意そう。

ここまでのソースはbd77b76です。

掛け算/割り算を実装する

まずASTを追加します。

class Mul {
  constructor(readonly lhs: Expr, readonly rhs: Expr) {}
}

class Div {
  constructor(readonly lhs: Expr, readonly rhs: Expr) {}
}

type Expr = Literal | Add | Sub | Mul | Div;

次にパーサを追加します。

const mulDivParser = seq(
  numParser,
  many(
    seq(
      spaceParser,
      or(constParser("*"), constParser("/")),
      spaceParser,
      numParser
    ).map(([, op, , expr]) => [op, expr] as const)
  )
).map(([expr, ops]) =>
  ops.reduce(
    (pre, op) => (op[0] === "*" ? new Mul(pre, op[1]) : new Div(pre, op[1])),
    expr as Expr
  )
);

足し算/引き算は掛け算/割り算より優先度が低いので、掛け算/割り算のパースの後に処理するようにします。

const plusMinusParser = seq(
  mulDivParser,
  many(
    seq(
      spaceParser,
      or(constParser("+"), constParser("-")),
      spaceParser,
      mulDivParser
    ).map(
      ([, op, , expr]) =>
        [op === "+" ? ("+" as const) : ("-" as const), expr] as const
    )
  )
).map(([num, ops]) =>
  ops.reduce(
    (pre, op) => (op[0] === "+" ? new Add(pre, op[1]) : new Sub(pre, op[1])),
    num as Expr
  )
);

ASTの評価も対応させます。

const evaluate = (ast: Expr): number => {
  if (ast instanceof Literal) {
    return ast.value;
  } else if (ast instanceof Add) {
    return evaluate(ast.lhs) + evaluate(ast.rhs);
  } else if (ast instanceof Sub) {
    return evaluate(ast.lhs) - evaluate(ast.rhs);
  } else if (ast instanceof Mul) {
    return evaluate(ast.lhs) * evaluate(ast.rhs);
  } else if (ast instanceof Div) {
    return evaluate(ast.lhs) / evaluate(ast.rhs);
  } else {
    const _exhaustiveCheck: never = ast;
    throw "unreached";
  }
};

ここまで来ると割とやるだけです。 ソースは921aa1fです。

カッコを実装する

カッコを実装するために、primeParserというパーサを定義します。

const primeParser = or(
    numParser,
    seq(
      constParser("("),
      spaceParser,
      plusMinusParser,
      spaceParser,
      constParser(")")
    ).map(([, , expr]) => expr)
  );

基本的にはmulDivParserのnumParserをprimeParserに置き替えればよいのですが、これをすると相互参照周りの問題が発生します。これを解決するために色々やったのですが、あまりに色々すぎて貼れないのでDiffを見てください。(アホか)

基本的にはパーサを全部functionで定義し直して、相互参照している部分をlazyというユーティリティを使って動くようにしています。

ともあれこれでカッコを含む数式を処理できるようになりました。

ということで最終形態を貼って終わりにします。

type Result<A> =
  | { type: "success"; consumed: number; result: A }
  | { type: "failure"; reasons: string[] };

const parseSuccess = <A>(result: A, consumed: number): Result<A> => ({
  type: "success",
  consumed,
  result
});
const parseFailure = <A>(reasons: string[]): Result<A> => ({
  type: "failure",
  reasons
});

class Parser<A> {
  constructor(readonly parse: (src: string) => Result<A>) {}
  map<B>(f: (x: A) => B) {
    return new Parser(src => {
      const r = this.parse(src);
      if (r.type === "success") {
        return parseSuccess(f(r.result), r.consumed);
      } else {
        return r;
      }
    });
  }
}

// パーサを繋ぐ
function seq<A>(p1: Parser<A>): Parser<[A]>;
function seq<A, B>(p1: Parser<A>, p2: Parser<B>): Parser<[A, B]>;
function seq<A, B, C>(
  p1: Parser<A>,
  p2: Parser<B>,
  p3: Parser<C>
): Parser<[A, B, C]>;
function seq<A, B, C, D>(
  p1: Parser<A>,
  p2: Parser<B>,
  p3: Parser<C>,
  p4: Parser<D>
): Parser<[A, B, C, D]>;
function seq<A, B, C, D, E>(
  p1: Parser<A>,
  p2: Parser<B>,
  p3: Parser<C>,
  p4: Parser<D>,
  p5: Parser<E>
): Parser<[A, B, C, D, E]>;
function seq<A, B, C, D, E, F>(
  p1: Parser<A>,
  p2: Parser<B>,
  p3: Parser<C>,
  p4: Parser<D>,
  p5: Parser<E>,
  p6: Parser<F>
): Parser<[A, B, C, D, E, F]>;
function seq<A, B, C, D, E, F, G>(
  p1: Parser<A>,
  p2: Parser<B>,
  p3: Parser<C>,
  p4: Parser<D>,
  p5: Parser<E>,
  p6: Parser<F>,
  p7: Parser<G>
): Parser<[A, B, C, D, E, F, G]>;
function seq<A, B, C, D, E, F, G, H>(
  p1: Parser<A>,
  p2: Parser<B>,
  p3: Parser<C>,
  p4: Parser<D>,
  p5: Parser<E>,
  p6: Parser<F>,
  p7: Parser<G>,
  p8: Parser<H>
): Parser<[A, B, C, D, E, F, G, H]>;
function seq<A, B, C, D, E, F, G, H, I>(
  p1: Parser<A>,
  p2: Parser<B>,
  p3: Parser<C>,
  p4: Parser<D>,
  p5: Parser<E>,
  p6: Parser<F>,
  p7: Parser<G>,
  p8: Parser<H>,
  p9: Parser<I>
): Parser<[A, B, C, D, E, F, G, H, I]>;
function seq(...parsers: Parser<unknown>[]): Parser<any[]> {
  return new Parser(src => {
    const result: unknown[] = [];
    let consumed = 0;
    for (const parser of parsers) {
      const r = parser.parse(src.slice(consumed));
      if (r.type === "failure") return r;
      consumed += r.consumed;
      result.push(r.result);
    }
    return parseSuccess(result, consumed);
  });
}

// パーサを並べて、最初に成功したものを返す
const or = <A>(...parsers: Parser<A>[]) =>
  new Parser<A>(src => {
    const reasons: string[] = [];
    for (const parser of parsers) {
      const r = parser.parse(src);
      if (r.type === "success") return r;
      reasons.push(...r.reasons);
    }
    return parseFailure(reasons);
  });

// パーサを連続して適用する
const many = <A>(parser: Parser<A>) =>
  new Parser<A[]>(src => {
    const result: A[] = [];
    let consumed = 0;
    while (true) {
      const r = parser.parse(src.slice(consumed));
      if (r.type === "failure") return parseSuccess(result, consumed);
      result.push(r.result);
      consumed += r.consumed;
    }
  });

// 遅延させる
const lazy = <A>(parser: () => Parser<A>) =>
  new Parser<A>(src => parser().parse(src));

class Literal {
  constructor(readonly value: number) {}
}

class Add {
  constructor(readonly lhs: Expr, readonly rhs: Expr) {}
}

class Sub {
  constructor(readonly lhs: Expr, readonly rhs: Expr) {}
}

class Mul {
  constructor(readonly lhs: Expr, readonly rhs: Expr) {}
}

class Div {
  constructor(readonly lhs: Expr, readonly rhs: Expr) {}
}

type Expr = Literal | Add | Sub | Mul | Div;

// 渡された文字列で成功するパーサを返す関数
const constParser = (lit: string): Parser<string> =>
  new Parser(src =>
    src.startsWith(lit)
      ? parseSuccess(lit, lit.length)
      : parseFailure([`expect 'hoge', but got '${src.slice(0, lit.length)}'`])
  );

// 数字のパーサ
const numRegex = /^\-?\d+/;
const numParser = new Parser<string>(src => {
  const match = numRegex.exec(src);
  if (match) {
    return parseSuccess(match[0], match[0].length);
  } else {
    return parseFailure([`expect a number, but got '${src[0]}...'`]);
  }
}).map(x => new Literal(parseInt(x, 10)) as Expr);

// スペースのパーサ
const spaceRegex = /^\s*/;
const spaceParser = new Parser<string>(src => {
  const match = spaceRegex.exec(src);
  if (match) {
    return parseSuccess(match[0], match[0].length);
  }
  throw "unreachable!";
});

// 括弧
function primeParser() {
  return or(
    numParser,
    seq(
      constParser("("),
      spaceParser,
      lazy(exprParser),
      spaceParser,
      constParser(")")
    ).map(([, , expr]) => expr)
  );
}

// かけ算と割り算を処理するパーサ
function mulDivParser() {
  return seq(
    primeParser(),
    many(
      seq(
        spaceParser,
        or(constParser("*"), constParser("/")),
        spaceParser,
        primeParser()
      ).map(([, op, , expr]) => [op, expr] as const)
    )
  ).map(([expr, ops]) =>
    ops.reduce(
      (pre, op) => (op[0] === "*" ? new Mul(pre, op[1]) : new Div(pre, op[1])),
      expr as Expr
    )
  );
}

// 足し算と引き算を処理するパーサ
function plusMinusParser() {
  return seq(
    mulDivParser(),
    many(
      seq(
        spaceParser,
        or(constParser("+"), constParser("-")),
        spaceParser,
        mulDivParser()
      ).map(
        ([, op, , expr]) =>
          [op === "+" ? ("+" as const) : ("-" as const), expr] as const
      )
    )
  ).map(([num, ops]) =>
    ops.reduce(
      (pre, op) => (op[0] === "+" ? new Add(pre, op[1]) : new Sub(pre, op[1])),
      num as Expr
    )
  );
}

function exprParser(): Parser<Expr> {
  return plusMinusParser();
}

const evaluate = (ast: Expr): number => {
  if (ast instanceof Literal) {
    return ast.value;
  } else if (ast instanceof Add) {
    return evaluate(ast.lhs) + evaluate(ast.rhs);
  } else if (ast instanceof Sub) {
    return evaluate(ast.lhs) - evaluate(ast.rhs);
  } else if (ast instanceof Mul) {
    return evaluate(ast.lhs) * evaluate(ast.rhs);
  } else if (ast instanceof Div) {
    return evaluate(ast.lhs) / evaluate(ast.rhs);
  } else {
    const _exhaustiveCheck: never = ast;
    throw "unreached";
  }
};

const run = (src: string) => {
  const r = exprParser().parse(src);
  if (r.type === "failure") {
    console.error(r.reasons);
    return;
  }
  const ast = r.result;
  console.log(evaluate(ast));
};

run("1 + 2 * 3 + 4");
run("(1+2)*(3*4)");

完走した感想と展望

割とよくある数式のサンプルなのに記事が結構な分量になって驚いています。これで下手に変数とかに手を付けていたら失踪していたでしょう。この記事がcompiler bookに大きく影響を受けていることはバレバレかもしれませんが、あちらはカッコの実装のような手戻りを起こすことなく進んでいて、力量の差を感じさせられています。力が欲しい…

それでも、大体1コミットずつの変更を追っていくことで、概念が整理されたり、クソコードが新たな概念によって綺麗にリファクタリングされたりするようなプログラミングの面白さが少しでも伝わっていたら本当にうれしいです。

とはいえ数式だけでは胸を張って言語処理系を名乗れないと思うので、時間を見つけて少しずつ拡張していきたいですね。

次回はLiberalさんの「私がやってる音ゲーを布教したい」です!

Firestoreに追加されるらしいIN/ARRAY_CONTAINS_ANYクエリについて

Firestoreの次のリリースで新しいクエリが追加されるようだ。(ソース: feat: Add IN queries support (blocked) by thebrianchen · Pull Request #715 · googleapis/nodejs-firestore · GitHub)具体的には

  • 指定された値のどれかに一致するドキュメントを選ぶ IN クエリ
  • ARRAY_CONTAINSのIN版であるARRAY_CONTAINS_ANYクエリ

が使えるようになるらしい。

続きを読む