こんにちは。とすけです。最近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さんの「私がやってる音ゲーを布教したい」です!

2019-10-17

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クエリ

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

2017-07-17

プチコン3号乱数解析の話

なお、この解析結果はプチコン3号限定です。(プチコンBIGはまた別の乱数生成アルゴリズムを採用しているらしい)

乱数の内部実装を予測する

なぜ？

SmileBasicにおいて乱数を取得する方法は、 0からK-1までの乱数を生成するRND(K)と、0から1までの乱数を生成するRNDF()があります。つまり、プチコン内から直接これらの関数の内部で使用されている"生"の乱数を取得する方法はありません。そのため、乱数生成アルゴリズムを知るには、これらの関数の実装を予測し、"生"の乱数を計算する必要があります。

予想

とりあえず、実装が簡単そうなRNDF()について予想してみましょう。

double RNDF() {
  return raw_rand() / RND_MAX;
}

ここではraw_rand()は0からRND_MAXまでの整数の乱数を返す関数とします。 RNDF()の仕様から考えて、これ以外の実装はあまり考えられないでしょう。

次はRND(K)です。これは、複数の実装が考えられます。 1つ目はRNDF()を内部で利用する方法です。

int RND(int K) {
  return (int)( RNDF() * K );
}

RNDF()の範囲を拡大する方法ですね。

2つ目はraw_rand()の余りを取る方法です。

int RND(int K) {
  return raw_rand() % K
}

raw_rand()のアルゴリズムが線形合同法だとプログラマー格付けチェックに引っかかるあれですね。

実験

次のコードを使います。

RANDOMIZE 0,1
?"RNDF",RNDF()

RANDOMIZE 0,1
?"RND ",RND(&H7FFFFFFF)/&H7FFFFFFF

RANDOMIZE命令を使って乱数のシード値を1に固定しています。もしRND(K)の実装が内部でRNDF()を利用する実装の場合、RND(K)の値をKで割ることによってRNDF()に近い値が得られると考えられます。では実行してみましょう！

RNDF 0.59263361
RND 0.18526723

2つの値が大きく異なっています。

結果

この結果からRND(K)とRNDF()の実装を予測することができます。

int RND(int K) {
  return raw_rand() % K
} 

double RNDF() {
  return raw_rand() / RND_MAX;
}

"生"の乱数値を計算する

乱数関数の実装を知ることができたので、"生"の乱数値を計算できます。次のコードを使います。

DEF R(K)
 RANDOMIZE 0,1
 return RND(K)
END

?R(&H7FFFFFFF)
?R(&H7FFFFFFE)
?R(&H7FFFFFFD)
?R(&H7FFFFFFC)

結果は

R(K)に渡す値を1減らすたびに結果が1増えていて、規則性を感じますね。 R(K)は"生"の乱数の値をKで割った余りなので、この時の"生"の乱数をXとすると、

${ \displaystyle X=K\times n+R(K) }$ (nは整数)

と表すことができます。これに実際の数字を代入してみましょう。(nは変化しないと仮定します。)

${\displaystyle \left\{ \begin{array}{@{}1} X=0x7FFFFFFF\times n+397858342 \\ X=0x7FFFFFFE\times n+397858343 \end{array} \right. }$

これを解くと、 ${ \displaystyle X=2545341989,\,n=1 }$ より、シード値が1のときの"生"の乱数は2545341989であると考えられます。

乱数生成アルゴリズムを推測する

一口に乱数生成アルゴリズムといっても様々な種類があります。それらについてより深く知るためにGoogle先生の力を借りましょう。 f:id:tosukee:20170717151506j:plain 一瞬で答えが出てしまいました。このことから、プチコン3号の乱数生成アルゴリズムはTiny Mersenne Twisterであるということがわかります！

あとがき

最初にも書きましたが、プチコンBIGの乱数生成アルゴリズムはプチコン3号とは違います。また、SmileBasicはPasocomMiniにも搭載される予定ですが、これの乱数生成アルゴリズムも他とは異なる可能性があります。いつかこれらの解析もしたいですね。(投げやり)

2017-07-16

はじめまして

~~全然はじめましてではない~~

自己紹介

名前

Tosuke

本名を魔改造してできた文字列です。特に意味はありません。(どうやらとすけは輪投げという意味らしい)

生息場所

主にTwitterに生息しています。 Miiverseにもたまに出没しています。某限界SNSでも姿を確認できると思います。

できること

D言語を書いていましたが、色々あって最近はJavaScriptやTypeScriptやC#を書いています。 D言語を書いていた流れでC言語やC++(ほんの少し、読める程度)、Rustもできます。 Pythonも一応経験あります。(文法やった程度)

特殊なところではSmileBasicを書きます。

職業

宮城県の某高校の学生です。(2017年現在)

ブログを始めた理由

上で書いた通り、私はTwitterによく出没しています。その中で、その時々に感じたことや知見をTwitterに書くことで流れてしまい、書いた本人ですらそれを再び見ることがないということがかなり多くありました。ブログという形で書きとめておくことはそのような問題に対する有効な解決手段だと思っています。

とはいうものの、私はブログを立ちあげることを長らく面倒くさがっていました。しかし、私はHexoを使えば簡単にブログを立ち上げることができることを知り、ブログを立ち上げましたが、放置してたらぶっ壊れたのではてなブログにしました(markdownで書けて数式も使えてよさそうだったので)

書こうと思っていること

技術的な知見
ポエム
ただのメモ

要はチラシの裏案件です。おそらく半分くらいは全く役に立たない内容になると思いますが、つらつら書いていこうと思います。