0x19fの日報

なるべく毎日書きます

ICPC 2018国内予選に参加してきました

M1の@reminさん、B4の自分、B3の@9071tomatoくんの3人で、チームMohuhu UniversityとしてICPC 2018国内予選に参加しました。 なんとかA〜D問題を解いて全体で31位になることができたので、おそらく国内予選を突破できたはずです。

f:id:mizu0x19f:20180707193343p:plain

一応、問題一覧と順位表のリンクを貼っておきます。
問題一覧: All Problems
順位表: LiveSite

A問題:
n個の値が与えられるので、その平均以下の値の数を答える問題。 @reminが考察・実装。 最近の国内予選のA問題だと解きやすい方に入るのかなぁと。

B問題:
紙を横方向または縦方向に折る指示がいくつか与えられて、折った後に特定の場所に何枚紙が重なっているか答える問題。 自分が考察・実装。 パッと見ですごく解きたくない問題だったんですが、実際に解いてみるとものすごく解きたくない気持ちになりました。 少し手間取ったもののなんとか通せてよかったです。

C問題:
連続する正の整数の和がbになるような範囲のうち、範囲に含まれる数の個数が最大のものを答える問題。 @9071tomatoが最初読んでわからないようだったので一旦飛ばしてDを読んでもらいました。 自分もBを解き終えて問題を読んだのですが、なるほど確かにわからない。 昨年のC問題とかもっとずっと簡単だったのに......なんて思いつつ考察してました。 bが109程度であること、範囲の和が2乗で大きくなっていくことを考えると、何かしらがsqrt(109)に収まるんだろうなぁと話していたら、@reminが範囲の幅がsqrt(109)で抑えられることを見つけてくれました。 というわけで、Cは@reminに実装してもらいました。

D問題:
総当たり戦の対戦結果が途中まで埋められた表が与えられて、全チームの勝敗数が等しくなるような対戦結果は何通りあるかを答える問題。 チーム数が最大で9なので試合の数が9C2で36通り、全探索をしても236なので時間をかければ解けそうだし、適当に枝刈りすれば十分な速さで解けそうだなぁと思いました。 実際のところ最大ケースでも236通り試す必要はなくて、たぶん8C4 * 6C3 * 4C2 * 2C1 = 16800ぐらいになるのかな? @9071tomatoがいけそうだと言ってくれたので実装してもらいました。 @9701tomatoくんにnext_combination(next_permutationの組み合わせ版)を持ってないかと聞かれたのですが、奇跡的に持っていたので写経してもらいました。 何がいつどこで役に立つかわからないものですね。

E問題:
簡易版の浮動小数点を用いて加算をn回繰り返すプログラムの結果をシミュレーションしてくださいという問題。 nが最大で1018なのでダブリングだと思ったんですが、違いました。 実装してからダブリングだとn回加算で起きる誤差が再現できないことに気づきました。 実装する前に@reminから指摘があったとの説もありますが......。 実はサンプルの最後のケースが最大ケースになっているらしく、指数部が増えるタイミングがたかだか50回程度であることがわかるみたいです。 あとは指数が増えるところまでまとめて足すというのを50回ぐらい繰り返せばいいみたいです。 (まだ実装できてないですが......)

F〜Hは一応問題には目を通したもののどうしたらいいのかさっぱりだったので諦めました。

ちなみに、学内1位のWAsedACが選抜チーム内で14位、Mohuhu Universityが学内2位で選抜チーム内で20位、学内3位のWAsita Universityが選抜チーム内で25位なので、学内から3チームアジア地区大会に出場も夢じゃなくなってきてますね。 (学内から3チーム出場するには20位以内に入る必要があるので。)

とまぁ、なんとかアジア地区大会に出場できそうです。 国内予選を通過されたチームのみなさん、横浜でお会いできるのを楽しみにしています。

ちなみに、これは予選終了後に学内の参加者で集まって寿司を食べている様子です。 寿司が食べたいみなさん、来年はぜひICPCに参加しましょう。

(ところでなぜ僕らはコンテストが始まる前にフビライ・ハンとエビフライゴハンの話をしていたんですかね?)

Cコンパイラ自作チャレンジ(その2・プリプロセッサ編)

字句解析に続いてプリプロセッサ

前回は字句解析器を作るところまでの話でした。

0x19f.hatenablog.com

今回はプリプロセッサのお話です。

先に言い訳をしておくと、WG14/N1570 Committee Draftを読みながらザクザクと実装を進めてそれっぽいマクロ展開などはできるようになってきましたが、まだ完全に作りきれてはいないです。 加えてだんだん自分でも何を書いているのかよくわからなくなってきたので、少し整理しながら書き直したいと思っています。 というわけで、まだ具体的な実装はGitHubリポジトリにpushしてないです。

そんな感じなので、一度プリプロセッサの挙動を書き起こして整理したいと思います。 僕の備忘録的な色が強いです。

プリプロセッサの概要

プリプロセッサというと、#include#defineなどがパッと思い浮かぶんじゃないかと思います。 これらはプリプロセッシング・ディレクティブと呼ばれます。

ディレクティブとマクロの展開は字句解析で得られたトークン列に対して行われます。 プリプロセッシングによって得られたトークン列は型の特定や文字列の結合などの処理が行われて構文解析されていきます。

ディレクティブの一覧は以下の通りです。

  • Conditional inclusion: #if, #ifdef, #ifndef, #elif, #else, #endif
  • Source file inclusion: #include
  • Macro replacement: #define, #undef
  • Line control: #line
  • Error directive: #error
  • Pragma directive: #pragma

#line__LINE__マクロとか__FILE__マクロとかを制御するためのものっぽい。 #errorはこのディレクティブを読むと後ろに指定されたエラーメッセージを出してくれるようです。 #pragmaコンパイラ固有・環境固有の機能とかを追加するのに使われるディレクティブという認識だけど、よくわからない。

規格に書かれているディレクティブはこれで全てなので、この他は各コンパイラ拡張機能ということになるんですかね。

ここからはプリプロセッシングの中心的な機能となるMacro replacementとSource file inclusion, Conditional inclusionについて書いていこうと思います。

Macro replacement

マクロの定義

#defineディレクティブでマクロを定義できます。

マクロの定義には2種類あって、オブジェクト型のマクロ(object-like macro)と関数型のマクロ(function-like macro)のようなものがあります。 関数型のマクロは可変長引数みたいなものを受け取ることもできて、その場合は#define function(a, b, ...)のような宣言の仕方になります。

#define identifier replacement-list
#define identifier( identifier-list ) replacement-list
#define identifier( ... ) replacement-list
#define identifier( identifier-list , ... ) replacement-list

なお、混乱を避けるために以下ではパラメータと引数を明確に区別して使います。 パラメータと言った場合は、マクロ宣言の()の間に含まれる識別子のことを指します。 引数と言った場合には、マクロ呼び出しの()の間に含まれるトークン列のことを指します。 要するにパラメータは宣言側のこと、引数は呼び出し側のことと思ってください。

マクロの置換

テキスト中にオブジェクト型のマクロの名前が出てきた場合には、対応するreplacement-listでそれを置き換えます。 置き換えが終わったら、置き換えられた部分を再度スキャンしてマクロを再帰的に展開していきます。

テキスト中に後ろに(が続く関数型のマクロの名前が出てきた場合には、対応する括弧を除いた次の)までを以下の手順で置き換えます。

  1. 1番外側の()の内側のトークン列を,で区切って関数型マクロの引数とする
    ただし、対応する括弧の中にある,を除く
  2. replacement-list中に現れるパラメータを引数で置換します
    ただし、パラメータの前に#トークンがある場合と前後に##トークンがある場合を除きます
    また、置き換えを行う前に引数に含まれるすべてのマクロを展開します
  3. #トークンの後ろに続くパラメータは文字列化されます
    ##トークンの前後のトークンは連結されます
  4. 置き換えられた部分を再スキャンしてマクロを再帰的に展開していきます

パラメータに...を持つ関数型マクロの呼び出しの際はパラメータの数以上の引数を渡すことができます。 その場合、余分な引数の部分は,を含めて__VA_ARGS__というパラメータに対応付けられたように振舞います。

# 演算子について

#は後ろに続くパラメータを引数を文字列化したもので置き換えるという演算子です。

引数の先頭と末尾の空白文字は取り除かれます。 それ以外は元のトークン列のスペリングが維持されたままひとつの文字列に変換されます。 例外として、トークン列中に現れる"\のみエスケープされます。

## 演算子について

##は前後のトークン列を連結するという演算子です。 関数型マクロだけでなくオブジェクト型のマクロでも使うことができます。

引数が空のトークン列である場合は、placemarkerという特殊なトークンで置き換えます。 トークンを連結する際、片方がplacemarkerである場合は、その結果はもう片方のトークンになります。 両方がplacemarkerの場合は、結果もplacemarkerとなります。 placemarkerは再スキャンの前に全て取り除かれます。

マクロの再帰的な展開

一通り上記の手順でマクロを展開し終えたら、置換された部分を再度スキャンして再帰的にマクロを展開します。 再帰的な展開の途中ですでに展開済みのマクロ名に出会った場合は、展開を行いません。

実装する上では、マクロ展開を終えた後に展開したマクロにフラグを立てておいて、フラグが立っているマクロを無視しながら再スキャンを行い、再スキャンが終わったらフラグを折るという感じで問題ないと思います。

この再帰的な展開を図にしてみたんですが、あんまりわかりやすくはなさそうですね...

f:id:mizu0x19f:20180528072317p:plain

Source file inclusion

#includeディレクティブでソースファイルのインクルードができます。

#include <h-char-sequence>
#include "q-char-sequence"

厄介なのが#includeの後ろに続くのが上記の2つ以外のトークン列の場合です。 この場合、トークン列を通常のテキストと同様にマクロ展開し、ひとつのヘッダー名に変換し、それが上記の2パターンに当てはまればインクルードを行います。

Conditional inclusion

#ifディレクティブなどから次の#endif#elif#elseまでが出てくるまでのことをグループ(group)と規格では呼んでいたので、以下でもそれに習ってグループという言葉を使っていきます。

#ifdef, #ifndefはマクロの定義状態によってどのグループを読むかを決めるディレクティブです。 これはおそらく実装するのも難しくないです。

#if, #elsifがやばいです。 なぜやばいのかというと、実は#ifの後に続く条件は整数定数式として評価されるからです。 この時点で結構重めの構文解析が必要です。

さらにただの整数定数式ではなく、defined演算子という後に続く識別子がマクロとして定義されているかいないかによって1/0に置き換えられる演算子があったり、マクロの展開も行われます。 なので、defined(macro) + 3 >= 4のようなトークン列を処理する必要が出てきます。

具体的には、#if#elifの後ろに続くトークン列は以下のようにして真か偽か評価されます。

  1. defined演算子がついている識別子を除いて、マクロを展開する
  2. defined演算子を0/1に置き換える
  3. 残っている識別子を全てpp-numberの0で置き換え、トークン列をtoken(pp-tokenではなく)に変換する
  4. 整数定数式として評価する
  5. 得られた結果が0でなければ真、0なら偽

else, endifはあんまりちゃんと読んでないけれど、見たとおりだと思います。

一応、読み込まれなかったグループはマクロの展開とかディレクティブの評価とかをせずに読み飛ばすっぽい?

次こそプリプロセッサ

だいたいの挙動は理解できたし実装のイメージもつかめたので、もう少しいい感じにプリプロセッサを作り直します。 空白を読み飛ばす処理が面倒でつらいなぁという気持ちになったので、そこはうまくやりたいなぁと。

Cコンパイラ自作チャレンジ(その1・字句解析編)

2018/06/05追記

続き書きました。

0x19f.hatenablog.com

Cコンパイラの自作に挑戦してみる

C言語のプログラムを書き始めたのはたしか僕が中学生か高校生の頃でした。 あの頃からなんとな〜く「プログラミング言語というのはどうやってできているんだろう」と思っていました。 どう考えてもあんな複雑なルールを持ったプログラムの構文を解釈するなんて無理やろ、既存のコンパイラはどうしているんだと思わずにいられませんでした。

そんな疑問が解決されたのは、大学に入って言語処理系の講義を受けた時でした。 字句解析や構文解析について教わりとても感動しました。 最適化の話はあんまり理解できませんでしたが。

というわけで、今ならそれなりにコンパイラの自作ができそうな気がするのでCコンパイラの自作に挑戦してみたいと思います。 最近は言語処理系の自作が流行っているみたい(?)ですし。

作るにあたって名前があったほうがいいなと思ったのですが、だいたいCコンパイラって「なんとかcc」みたいな名前がついているイメージがあるので、僕のイニシャルをとってskccという名前をつけることにします。

github.com

C言語の規格

C言語の正式な規格はANSIやISOから購入する必要があるみたいなのですが、Committee Draftであれば自由に閲覧することができます。 Committee Draftは最終決定された規格と違う部分もあるかもしれないのですが、どれくらい違うものなんですかね?

今回はC11のCommittee Draftに沿ってコンパイラを作っていこうと思います。

コンパイルの処理の流れ

規格の5.1.1.2 Translation phasesに処理の流れが8つのフェーズに分かれて記述されています。 ざっくり要約してまとめると以下のような感じになります。

  1. トライグラフを置換する。
  2. 改行の直前にあるバックスラッシュを削除して前後の行を1つにつなげる。
  3. 字句解析をしてソースファイルをpreprocessing-tokenに分解する。
  4. プリプロセッサの実行、マクロを展開、_Pragmaの実行を行う。
  5. 文字定数と文字列リテラルの文字を対応する実行環境用に変換する。
  6. 隣接する文字列リテラルを連結する。
  7. preprocessing-tokentokenに変換、構文解析をする。
  8. あんまり読んでないですが、リンクの話をしているっぽそう(?)。

フェーズ2で行われる処理は、複数行にわたる#defineなどの行末に置かれるバックスラッシュの処理ですね。

preprocessing-tokenはフェーズ3〜6で使われる字句要素、tokenはフェーズ7の構文解析で使われる字句要素です。 ふたつは若干内容が異なっている点に注意です。 イメージとしては、preprocessing-tokenはざっくりとしたトークン分けで、プリプロセッシングが行われた後により細くtokenに分けるという感じです。 例えば、数値は整数と浮動小数点をすべて含むpp-numberという字句要素に分解され、プリプロセッシングの後で整数と浮動小数点に分けられて値と型が解析されます。 余談ですが、pp-number0xe-8のようなinteger-constantでもfloating-constantでもないトークンを含んでおり、これらは値と型を解析するタイミングでエラーとすればよさそうです。

preprocessing-tokenの字句解析器

まずはフェーズ3の処理をする字句解析器を作っていきます。

6.4 Lexical elementsにpreprocessing-tokenの構文が書かれています。 トークンの種類はheader-name, identifier, pp-number, character-constant, string-literal, punctuator, これらのいずれにもマッチしない1文字です。

入力文字列のうちで構文に一致する最長の箇所までがひとつのトークンとなります。 例えば、x+++++yx, ++, +, ++, yと区切ると正しいプログラムになりますが、この規則に則って字句解析が行われるのでx, ++, ++, +, yと区切られます。

字句解析器を作る際にはflexなどのツールを利用することが多いと思うのですが、今回はそういった便利なものを使わずに頑張ります。 というわけで、基本的にはpreprocessing-tokenの構文を手でオートマトンに変換し、1文字ずつ読み取りながらどのトークンにマッチするのか調べていきます。

このオートマトンを作る部分が結構大変で苦労しました。 例えば、文字定数を受理するオートマトンは以下のような感じになるんですが、初めて見るプレフィックスやエスケープシーケンスが意外と多くその辺で手こずりました。

f:id:mizu0x19f:20180506204036p:plain
文字定数を受理するオートマトン

その他の種類のトークンを受理するオートマトンGitHubに置いておくので気になる方はどうぞ。 間違いがあれば指摘していただけると助かります。

skcc/diagrams at c85779b7150b75f8aef604f56dc7a7950633c479 · ShinyaKato/skcc · GitHub

あとはこの図を見ながらひたすらif文を書いていきます。 こんな感じ。

skcc/lex.c at 6a7ed86c64717b31517f5a5633fa7fbc5b784a43 · ShinyaKato/skcc · GitHub

また、これは自分の解釈があってるか自信がないのですが、最長の一致箇所を見るので途中でどこにも遷移できない場合は最後に通った受理状態まで戻ることになると思われます。 例えば、...(可変引数のアレ)を受理する途中にドットふたつという状態があるのですが、この状態は受理状態になりません。 なので仮に..というドットがふたつ連続した入力が与えられた場合は、最後に通った受理状態であるドットひとつまで戻って..という形に分割されます。 もし途中でひとつも受理状態を通っていなければ、先頭の1文字をどのトークンにもマッチしない文字としてトークンにします。 規格をよく読むと、"'がこのような1文字のトークンとして切り出された場合の挙動は未定義とされています。 このような"'が現れるのはクォーテーションの間に改行が入る場合やエスケープシーケンスが不正な場合ぐらいだと思いますが。

もう一点忘れないように書いておくと、header-nameは行頭の#, defineの後に続く場合にのみ認識されます。 すなわち、字句解析器は文脈に依存します。 正直かなり衝撃的だったのですが、規格にもそう書いてあるので仕方ないですね。

次はプリプロセッサ

次はプリプロセッサを作っていきたいと思います。 といってもある程度サボって構文解析に進んでいくつもりではありますが。 字句解析とかプリプロセッサとかあんまりTwitter映えしないし。

大学1年から大学3年までの時間割をまとめておく

ちょくちょく「3年の時間割ってどんな感じですか?」みたいなことを後輩に聞かれるので、この際全部まとめて残しておくことにした。

一応説明しておくと、早大理工は基幹理工学部先進理工学部創造理工学部の3つの学部に分かれている。 僕が所属しているのは基幹理工学部なので、1年の時はその時間割になる(細かいことをいうと、学系2だった)。 さらに、基幹理工学部は2年から数学科・応用数理学科・機械航空学科・電子物理システム学科・情報理工学科・情報通信学科・表現工学科に分かれる。 僕は情報理工学科なので、2年以降はその時間割になる。 なお、僕が大学に入学したのは2015年度だった。

まとめると、こういうことになる。

  • 1年: 2015年度の基幹理工学部(学系2)の時間割
  • 2年: 2016年度の情報理工学科の時間割
  • 3年: 2017年度の情報理工学科の時間割

後輩たちの参考になればよいけれど、僕の頃とカリキュラムが異なるかもしれないのでその辺りは注意していただけると。

1年

f:id:mizu0x19f:20180228001612p:plainf:id:mizu0x19f:20180228001643p:plain
1年春学期 / 1年秋学期

1年の時はほとんど理系の基礎みたいな科目。 この辺は全部必修な上に、時間割の選択権もないので言及することはなし。

ピンク色は教養科目みたいなやつ。 おもしろかったけれど、成績は微妙だった。

2年

f:id:mizu0x19f:20180228001701p:plainf:id:mizu0x19f:20180228001718p:plain
2年春学期 / 2年秋学期

春学期の方が色ついてなくて見辛いですがお許しを。

2年から情報理工の専門必修が入ってくる。 前期だと回ロリA・プロA・ロリ回路・実験A・情報数学A・アルゴリAが、後期だとアーキA・電子回路・情報数学B・実験B・アルゴリBが必修。 他はだいたい専門の選択か基幹理工共通の数学科目。 時間割の中に1年生の必修のCプロが入っているが、これは再履修とかではなくTAをしてただけ。

前期がかなりしんどかった記憶があるが、後期は人によってはそんなにしんどそうにしてなかった印象。 しんどいけれど、2年のうちに選択の単位を稼ぐと3年以降が楽になる。 やっぱり、実験のレポートがつらかった(共振回路とか共振回路とか共振回路とか)。

3年

f:id:mizu0x19f:20180228001753p:plainf:id:mizu0x19f:20180228001740p:plain
3年春学期 / 3年秋学期

3年になるとほとんど専門必修や専門選択になる。 前期だとプロB・OSA・情ネツA・ソフ工A・実験B・言語処理系、後期だとDB・プロ言・プロC・アーキB・実験Cが必修。 他は選択だった。 必修の数自体は少ないので選択の単位数さえ取れば結構講義は少なめ。

僕は必修以外も無意味にたくさん講義を取ったけれど、講義の難易度も上がり、成績を落とす要因になりかねないので個人的にはあまりオススメしない。 もちろん、興味があれば構わずに取れば良いと思うけれど。

あと、春学期の火曜日が1〜6限までだったけれど、正直かなりしんどかった。 1〜5でもしんどいんだから当然だとは思う。

ちなみに、3年の必修は個人的にはおもしろいものが多かった。 なんていうか「こういうのが勉強したくて大学に来たんだよなぁ」という感じ。 講義以外で勉強したことの方が多いような気もするけれど、興味を持つきっかけとしては非常にありがたかった。

まとめ

こんな感じで3年分の時間割をまとめてみたけれど、誰かの役に立ったらいいなぁと。

山本一成さんの「エレファントな解法」に対抗して動的計画法による「エレガントな解法」を考えてみた

エレファントな解法(?)

先日Ponanza開発者の山本一成さんがブログでこのような記事を書いておられました.

note.mu

この記事の中では以下の問いが投げかけられています.

問. コインを100回投げて表か裏が10回連続で出る確率は?

山本さんのブログでは「エレファントな解法」としてモンテカルロ法を用いた力任せの解法が紹介されています. つまりは, 乱数を使って100回コインを投げるというシミュレーションを何度も繰り返して条件を満たす確率を近似的に求めるというわけです. この方法ならきちんと確率を求めることができなくても, それなりに確率を正しく求められます. 困った時の最終手段としては非常に便利だと思います.

ちなみに, こういった方法が「エレファントな解法」と呼ばれているのは初めて知りました.

エレガントな解法

「エレファントな解法」のことは一旦置いておいて, 山本さんがエレガントな解法について「私は正直解ける気がしません」と言っておられたのが少し気になりました. 競プロerならぱっと見で「動的計画法で解けそう?」と感じた人も多いんじゃないでしょうか, 僕もそう感じました.

というわけで, この問題を動的計画法(DP)で解いてみたいと思います.

DPで解いてみる

先に断っておくと, 解いてみてから気づいたのですがちょっと冗長なDPをしています. あと, 答えはあったものの, 若干怪しいところがあります(おい).

基本的な考え方

DPそのものの説明はいろいろと調べてもらうのが早いと思うのですが, 僕は「コインの投げ方って2N通りあるけれど, 実はそんなに場合分けしなくても"何回コインを投げて何回連続で同じ面が出てるか"で場合分けすれば十分じゃない?」というものだと思ってます.

例えば, 10回コインを投げて最後に表が3回連続で出るような投げ方って26通りありますが, 今回の問題では最初の6回までに表裏どっちが出たかって知らなくても答えは出せます.

というわけで, これらをまとめて計算して, さらに上手に前の計算結果を利用していくことで計算量を落とすことができます.

解法

まず, コインを投げる回数をN, 求めたい確率の連続回数をMとします. そして, 以下のようなDPを考えます.

dp[i][j][k][l]:
i回コインを投げた時に, 最後にj回連続で(k = 0: 表, 1: 裏)が出て, 条件を(l = 0: 満たしていない, 1: 満たしている)確率

遷移に関しては, (k, l)の4パターンについてそれぞれ表が出た場合と裏が出た場合を考えます. 表が連続している場合に限って説明します.

まだ条件を満たしていいない場合は, 表が出たら連続回数を1増やし裏が出た場合は連続回数を1に戻してあげます. このとき, 表がM回以上連続していたらl = 1, つまり条件をすでに満たした状態に遷移してあげます.

すでに条件を満たしている場合も, 表が出たら連続回数を1増やし裏が出た場合は連続回数を1に戻してあげます.

裏が連続している場合もほぼ同様です.

最終的な答えは, N回コインを投げて最後の連続数とコインの裏表に関係なく条件を満たしている確率です. つまり, dp[N][j][k][1] (0 <= j < N, k = 0, 1)の和が答えです.

というわけで, O(N2)の時間計算量で答えが出せます.

実装

これをC++で書いてみると以下のようになります.

#include <cstdio>

int main(void) {
  const int N = 100, M = 10; // コインを投げる回数, 連続する回数
  const double P = 0.5;      // 表が出る確率

  // dp[i][j][k][l]:
  //   i回コインを投げて,
  //   最後のj回連続して(k = 0: 表, 1: 裏)が出て,
  //   (l = 0 : まだ条件を満たしていない, 1: すでに条件を満たしている)確率
  double dp[N + 1][N + 1][2][2];
  for(int i = 0; i < N + 1; i++) {
    for(int j = 0; j < N + 1; j++) {
      dp[i][j][0][0] = 0;
      dp[i][j][0][1] = 0;
      dp[i][j][1][0] = 0;
      dp[i][j][1][1] = 0;
    }
  }
  dp[0][0][0][0] = P;
  dp[0][0][1][0] = (1 - P);

  for(int i = 0; i < N; i++) {
    for(int j = 0; j < i + 1; j++) {

      // (k, l) = (0, 0): 表が連続, 条件を満たしてない
      dp[i + 1][j + 1][0][j + 1 >= M] += dp[i][j][0][0] * P;
      dp[i + 1][1][1][0] += dp[i][j][0][0] * (1 - P);

      // (k, l) = (0, 1): 表が連続, 条件を満たした
      dp[i + 1][j + 1][0][1] += dp[i][j][0][1] * P;
      dp[i + 1][1][1][1] += dp[i][j][0][1] * (1 - P);

      // (k, l) = (1, 0): 裏が連続, 条件を満たしてない
      dp[i + 1][1][0][0] += dp[i][j][1][0] * P;
      dp[i + 1][j + 1][1][j + 1 >= M] += dp[i][j][1][0] * (1 - P);

      // (k, l) = (1, 1): 裏が連続, 条件を満たした
      dp[i + 1][1][0][1] += dp[i][j][1][1] * P;
      dp[i + 1][j + 1][1][1] += dp[i][j][1][1] * (1 - P);
    }
  }

  // 最終的な答えは, dp[N][j][k][1] (0 <= j < N, k = 0, 1)の和
  double ans = 0;
  for(int j = 0; j < N + 1; j++) {
    ans += dp[N][j][0][1];
    ans += dp[N][j][1][1];
  }
  printf("%.15lf\n", ans);
}

実行した結果「コインを100回投げて表か裏が10回連続で出る確率」は0.086659044348362となりました. 山本さんがブログの中で知人の数学者の方に「エレガントな解法」で計算してもらったという値と一致してます, やったね.

まとめ

というわけで, こんな感じでこの問題は答えが出せます. これぐらいならまだなんとか確率求められますが, 難しくなると圧倒的にエレファントな解法に分がありそうですね(無理やりまとめた).

ちなみに, 頑張るとO(NM)で答え出せるはずです. この解法はchokudaiさんが書いておられますね......プログラムみじかw

【メモ】UNIX V6コードリーディング(メモリ周りの整理/まとめ)

今回の内容

前回まではトラップハンドラについて読み進めていました.

0x19f.hatenablog.com

前回とは大きく内容が変わってメモリ周りの話を整理していきたいと思います(先にシグナルを読んでもよかったかも). 実は先々週あたりの勉強会を思い出して書いているので内容が確かじゃないかもしれないです. 書籍のページ数が結構飛び飛びになるので, 適宜どのあたりの話をしているか書いていきたいと思います.

アドレス変換(p52〜p55)

仮想アドレスから物理アドレスへの変換はp52に書かれていますが, 1点だけ補足を. APRが8つあるということは, 逆に言うと仮想アドレス空間は8Kバイト(= 213)毎に違うAPRを参照して物理アドレスへの変換を行うことになります. p50に書かれている「データ領域はテキストセグメントの後ろの8Kバイト刻みのアドレスに割り当てられます」の理由はここにあります. テキストセグメントとデータセグメントは物理アドレス上では連続していません. つまり, 同じAPRに割り当てられません. このあたりはアドレス変換の仕方についてよく考えると確かにそうなるなぁという感じになります.

仮想アドレス空間(p48〜p52)

細かいメモリの操作をする箇所を読むにあたって, 仮想アドレス空間物理アドレス空間がどのようにマッピングされているかを理解しておくと非常に理解が進みます. 意識しておいたほうが良さそうなポイントをいくつか.

  1. テキストセグメントとデータセグメントは物理メモリ上では別々の連続した領域.
  2. テキストセグメントはプロセス間で共有される.
  3. データセグメントはPPDA, データ領域(ヒープ領域を含む), スタック領域からなる.
  4. PPDAにはuser構造体とカーネルスタック領域が置かれる.
  5. PPDAはユーザープロセスの仮想アドレス空間マッピングされない(ユーザー空間からはアクセスできない).
  6. データ領域とスタック領域は物理アドレス空間では連続している.
  7. ヒープ領域はアドレスが大きくなる方向に, スタック領域は小さくなる方向に伸びていく.
  8. スタック領域は仮想アドレス空間の一番上位(0xffff)に割り当てられている.
  9. 物理アドレス上でヒープとスタックがぶつかった場合は拡張が行われる(expand関数).

仮想アドレス空間の操作

仮想アドレス空間に対する操作を行っている(と思われる箇所)をピックアップしてみました.

仮想アドレス空間マッピングの変更はestabur, suregあたりで行われるようです(p103〜). 細かいところは読めてないですが, estaburでuser構造体にAPRにセットする情報を格納, suregでuser構造体の情報に従ってAPRの値を操作するようです.

データ領域の拡張はbreakシステムコールで実現されます(p118). Cライブラリのmallocなどの内部で使用されるようです. 長年疑問だったmallocした時のメモリはどこから出てくるのかに対する答え(?)が少し得られたようで, 個人的には結構面白いと感じました. 実際にはOS側はデータ領域を拡張/縮小しているだけで, その他の諸々はCライブラリのmallocがやってくれているという感じなんでしょうか?

スタック領域の拡張はトラップハンドラの中で行われます(p176, grow).

ちなみに, 実行プロセスのPPDAはカーネル用のAPR6から参照できるようになっており, プログラム中ではuという変数で参照できます(p54一番下). この切り替えはコンテキストスイッチの際にしれっと行われています(p78). 当然ですが, このときにユーザー空間のマッピングが変更されます. おそらく, estabursuregが分かれている理由はこの辺にあって, コンテキストスイッチの際はuser構造体に格納された情報からマッピングし直すだけなのでsuregだけが呼び出されてます. (細かく中を読めていないので間違ってるかもしれないですが...)

まとめ

メモリ周りをいろいろと整理してみましたが, これを一発で理解するのは無理ですね(). ただ, いろいろと考えながら読んでみると本当によくできているなぁと思わされることばかりです.

次回の予定

スワッピングあたり?

【メモ】UNIX V6コードリーディング(トラップハンドラ/システムコール, p171〜184)

今回の内容

前回は, 主にタイマー割り込みに関連する箇所を読んでいました.

0x19f.hatenablog.com

今回は, トラップハンドラでの処理を見ていきます. システムコールについてもこの辺りに書かれています.

トラップハンドラtrap

トラップハンドラも割り込みハンドラ同様に呼び出しが行われcsvが実行された後のスタックの状態は以下のようになります.

引数 備考
sp pc csvから戻るのに使用されるだけ(あまり関係ない)
退避されたr2
退避されたr3
退避されたr4
r5 退避されたr5
pc(割り込みハンドラから返る先)
マスクされたPSW dev
割り込まれたプロセスのsp sp
古いr1 r1
PSW nps
古いr0 r0
割り込まれたプロセスのpc pc
割り込まれたプロセスのPSW ps

trap関数の9行目でu.u_ar0に引数r0のアドレスを格納していますが, これはスタック上のアドレスになります. 実際にスタック上の値を操作する際はu.u_ar0[R0]のようにして操作するのですが, R0はただの定数でスタック上のr0が格納されている位置からのオフセットです. 同様にしてR0R7RPS(PSWの操作に用いる)を使ってスタック上の値を書き換えています. トラップハンドラ内ではあまりこの操作は行われませんが, システムコールハンドラ内で行われるのでしょうか?

その後のswitch分でdev(トラップ種別)の値によって処理が分岐していきますが, 基本的にはシグナルを送って処理は終わりです. 例外はillegal instruction, floating exception(カーネルプロセス), segmentation exception, システムコールの時です.

illegal instructionの時はSETDなる謎の命令か否かをチェックしているようですが, 正直なんのためのものなのかあまりわかってないです.

カーネルプロセスでは浮動小数点演算を行わないらしいのですが, PDP11の特性上ユーザープロセスが行った浮動小数点演算によるfloating exceptionがトラップ発生後に引き起こされることがあるらしく, その場合はそのユーザープロセスにシグナルを送って関数から抜けます.

segmentation exceptionの場合, スタックを拡張します. それでもexceptionを回避できない場合は, プロセスにシグナルを送ります. このスタックの拡張はgrowという関数の中で行われるのですが, 仮想メモリ空間の話とかをあまりちゃんと理解していないので一旦飛ばします. ちなみに, growの前にbackupという関数が実行されているのですが, この関数はUNIX V6の中で最難関らしいです. exceptionが起きた時の状態を再現する関数らしいのですが, すべてアセンブリで書かれておりおまけに中でPDP11にはないレジスタの挙動をエミュレートしているようです. 実際にソースコードを読むと/ hard partというコメントが見つけられます. 最難関なのでは仕方ないので飛ばします.

システムコールの場合の処理の前にシステムコールの処理の流れをまとめたいと思います.

システムコールの処理の流れ

システムコールハンドラはsysent構造体によって管理されます. この構造体にはシステムコールの引数の数とハンドラのアドレスが格納されます.

sysent構造体の配列sysentに各システムコールの引数の数とハンドラのアドレスが格納されています. この配列は要素数が64で, 添字はsys命令のオペランド(6 bit)と対応しています.

システムコールの0番は間接呼び出しに割り当てられています. 間接呼び出しというものを自分は初めて知ったのですが, どうやら普通の呼び出しと異なるのは引数の渡し方のようです. 通常の呼び出しは, sys命令の後に引数が埋め込まれます. 一方で, 間接呼び出しの場合は, sys命令の後に引数のアドレスが埋め込まれます. これは推測なのですが, 直接命令の場合は引数が埋め込まれる場所がテキストセグメントになるため, 動的にシステムコールの引数が変わる場合に困ってしまうのでこのような仕組みが用意されているのではないかと考えています. sys命令の次にデータ領域のアドレスを埋め込んでおけば, 複数のプロセスでテキストセグメントを共有しつつ個別に引数を扱うことができます. あるいは, 引数の数が動的に変わる場合などでしょうか.

システムコールの引数は上述のようなsys命令の後に埋め込むものと, r0を経由するものがあります.

トラップハンドラ内でのシステムコールの処理

話はトラップハンドラのswitch文に戻ってくるのですが, システムコールの場合の処理を見ていきます. 基本的にはエラーフラグを初期化, 間接呼び出し/直接呼び出しそれぞれの場合で引数とシステムコールの番号を取得, trap1を呼び出してシステムコールハンドラを実行, エラーフラグの処理という流れです.

特筆すべきなのがtrap1を用いてハンドラを呼び出している点です. trap1の中を見てみるとわかるのですが, フラグを立ててからsavuしてシステムコールハンドラを呼び出しています. これが意味するところなのですが, これはシステムコール中にシグナルを受け取った場合にエラーを起こすためのものらしいです. 詳しくはシグナル処理のあたりで書かれています. このsavuに対応するaretusleep関数の末尾にあります. このエラーはシステムコールハンドラがsleepを実行して処理を中断している間にシグナルを受け取った場合に起こるものらしいです. シグナルを受け取った場合は, trap1が返る場所から処理が継続されます. この場合は, フラグが立ったまま処理が続行されるため, その後のtrapでの処理でユーザープロセスにはエラーが返ります. このエラーを見てユーザープロセスは再度システムコールを実行することができるようになっています.

まとめ

ということで割り込みとトラップを見てきましたが, なかなか複雑だなぁという感想です. もう一度プロセス管理あたりも読み直してみると納得感が増すのかなぁと思います.

次回の予定

シグナル?メモリ管理? 未定です