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

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

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

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

Linux Gaming とその方法

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

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

ICTトラブルシューティングコンテスト(以下 ICTSC)が開催されたので参加してきました。結果としては 2855 点の満点を最初に達成し、優勝でした。

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

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

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

パーサってなんだ

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

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

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

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

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

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

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

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

パーサ書く

パーサを書いてみる

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

const hogeParser: Parser = 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 => 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進数の)数字を処理して数にするパーサを書いてみます。ここでは色々横着して正規表現を使ってしまいます。

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

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

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

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

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

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

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

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

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

class Parser { constructor(readonly parse: (src: string) => Result ) {} map(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をいい感じにしてみましょう。長かった…

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

処理系を書く

足し算を処理してみる

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

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

f:id:tosukee:20191208194544j:plain

ネスト波動拳

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

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

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

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

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

const spaceRegex = /^\s*/; const spaceParser = new Parser(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 plusMinusParser = seq( numParser, spaceParser, opParser, spaceParser, numParser ).map(([lhs, , op, , rhs]) => (op === "+" ? lhs + rhs : lhs - rhs));

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

const or = (...parsers: Parser []) => new Parser (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"のように分けられて、数字の後に演算子と数字のペアが繰り返されることがわかります。つまり「繰り返し」を表現することができればいいわけです。書いてみましょう。

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

const many = (parser: Parser ) => 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でラップするだけです。

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 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の評価も対応させます。

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

カッコを実装する

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

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

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

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

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

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

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

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

const lazy = (parser: () => Parser ) => new Parser (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 => new Parser(src => src.startsWith(lit) ? parseSuccess(lit, lit.length) : parseFailure([expect 'hoge', but got '${src.slice(0, lit.length)}']) );

const spaceRegex = /^\s*/; const spaceParser = new Parser(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 { return plusMinusParser(); }

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)(34)");

完走した感想と展望

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

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

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

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

なお、この解析結果はプチコン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)

結果は

397858342 397858343 397858344 397858345

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にも搭載される予定ですが、これの乱数生成アルゴリズムも他とは異なる可能性があります。いつかこれらの解析もしたいですね。(投げやり)