理学部情報科学科の3S
なんとなくまとめてしまった。簡単な復習です。忘れないうちに。
全体としては、理情の授業は「コンピュータのシステムや"計算"という概念をあらゆるレイヤーで理解する」ことを目的に組まれているような感じで、「何かを作る」とか「何かを解く」というよりも「コンピュータ」とか「計算という概念」そのものが好きという人向けという感じがある（ので僕はとても好き）。まぁコンピュータ・サイエンスっていうのはそういうものなんだろうか。
課題そのもののネタバレは無いはず（多分）。
実験・演習
月：システムプログラミング実験
Operating SystemレイヤーやOperating Systemの一個上のレイヤーレベルの話を実践する実験。
第二回
Linuxのシステムコールを実際に呼び出してみる回。getpidのシステムコールを生で呼び出すと遅いが、libcを介すると速いという話や、簡単なcpを作ったりwcを作ったり、最後はls -lを作る。結構綺麗に作れたりする。
ls自体は、自分がパイプでどこかにつながれているか、出力がすぐにターミナルに吐き出されるかで、色付けをするかどうかを変えているみたいな小話があった（課題とは全く関係ないが）。
それをするには、isattyを使えば分かる ようである。まぁもっともぼくはlsに色をつけなかったが。
https://stackoverflow.com/questions/1061575/detect-in-c-if-outputting-to-a-terminal
第三回
マルチスレッド回。マルチスレッドで遊びます、終わり
第四回
ネットワーク回。tcp/udpで遊びます、終わり。実際ココらへんは際どい話が多くて実際もう一度やれと言われても綺麗にできる感じがしないので、正しい理解にはもう少し精進が必要そう。
正直四回まではあんま真面目にやってなかった気が（ほんまか）。ちょうどこのあたりで僕のPCが壊れた。
第五-六回
シェルを作る。とくにfg, bg, jobsなどのジョブ管理コマンドが正しく動くように実装する必要がある。
シェルは、お互いに壊しあうのが結構楽しいようで、その中で出てきた一つcatをn個パイプでつなげた
cat | cat | cat | .. | cat
その中の右端でも左端でもないようなcatのプロセスをkillしたときの挙動というのが比較的面白かった（かつ課題の大筋とは関係ない）のでメモをしておくと、殺されたcatの左側はwriteしようとしたタイミングでSIGKILLを受け取り、これはデフォルトで終了するので、たかだかn回のenterによってすべての左側のcatプロセスは終了する。一方右側のcatは単純にEOFを受け取ることになり、終了する。
なので、パイプでつながれたcatはどれか一つ死ぬと、連鎖的に死んでいくことになる。かなしい
第八-十回
ベアメタル回。OSに頼らずにコードを書くことが求められる。livaさんが用意してくれた部分が多いのでややまだ理解の至らない部分が多い（なぜ、hoge番地でMMIOできるようになっているか？とか、そもそも例外ハンドラ部分は、「ハンドラ」を書いただけであって、GDTいじったりIDTいじったりみたいなことはしなかったりなど）。
しかし、普通やらないであろう実験であることは確かで楽しいものではあった。個人的には、最初の方の四回半分にしてこっち長くしたほうが理解度的に幸せになれそうな感じがあった（ほんまか）
やることは、簡単なページング、DMAによる時間の計測および画面にデータを出力、TSCとの比較、割り込みとspin lockの実装をする。
spin lock、原理自体は結局CPU潰して待つというだけなんだが、結構奥が深い用で、複数コアで来た順にロックを獲得できるような仕組みというのはいろいろあるようである。
まず本当に愚直に実装する場合は、単に一つのbitでロックの状態を管理し、atomic命令によってTestAndSetをすればよいのだが、これだと順序が保たれない。すなわち「横入り」されてしまうかもしれない。
これを回避するためにticket lockというのがある。これは、銀行とか病院の「番号札」のような仕組みで、自分の番号札になるまで待つ、ロックを解放する際に値を1増やす、のようなアルゴリズムを考えることができる。
これでもう十分な気もするわけだが、複数のCPUが同時に特定のメモリ領域を書き込み・読み込みすることがticket lockでは要求される。これはキャッシュロックの頻発や、キャッシュラインのプロセッサ間での転送(cache line bouncing)が多発することになり、パフォーマンスに影響する。
これを防ぐために、単純に「待っている人の数」だけ待ち時間を増やすbackoffテクニックというのがある。またこのような単純なアプローチではなく、ロックの構造自体をCPU一つ一つに与えて、それぞれのCPUはその構造を監視する。この構造はリンクリスト的になっていて、自分が解放された際には、次にロックを獲得するものがいれば、隣の人のフラグを立てる、というようにする
このようにすることでcache line bouncingを極力抑えることができるようになる。
spin lockといっても非常に低レベルな問題によって工夫の仕様があるんだなあという気持ちになる
参考
https://lwn.net/Articles/531254/
https://lwn.net/Articles/590243/
なんか色々書いてしまった
火：関数論理型実験
名前の通り関数型言語OCamlと論理型言語Prologについて学ぶ実験。驚くべきことにこの実験でRustも勉強してしまった。
ところでこの実験のおかげでTeX力が1あがった（0から）
1-4回
OCaml自体で遊びます。Church数をOCamlで書くと、predに型がつかなくなってしまうので困りますね、という話や、副作用周りの話、Curry Howard isomorphism周りの話、モジュールを使ったGADT、リストモナドの"別実装"など。FLに一貫して言えるが、こういう発展的な"ネタ"は素直にOCamlを学んでいるときには見えにくい話なので、こういうの良いな〜っていう感じである。
5-9回
OCamlのインタプリターを作ります。lex/yaccから始まり、MLの基本機能を実装し、最後はlet多相を実装します。最後rank 2 多相を実装するというのがありましたが、残念ながらできていない。
let多相は、TAPLの22章Type Reconstructionあたりを実装する感じで、22.7のp334にある例
```ocaml
let x = fun x -> (x, x) in
let x = fun y -> x (x y) in
let x = fun y -> x (x y) in
let x = fun y -> x (x y) in
let x = fun y -> x (x y) in
let x = fun y -> x (x y) in
x (fun x -> x);;
```
という式は少なくともOCamlのバージョン4.06.1では、型がつかない。これは型がつかないのではなく、型推論が「終わらない」。これに型がつく（推論が生きている時間で終わる）ように拡張したりする。
unifyの回は、let多相が案外コーナーケースがあるらしく、意外と正しく実装するのは難しいらしい。
10-12回
最初にPrologで遊びます。tic tac toeを完全解析するような述語を作ったりする。
そして、Prologを作ります。なんとなく公開する（まぁprolog処理系はいくらでも書きようがありそうなので）。
https://github.com/moratorium08/pyoyog
基本的に後半はPrologが論理的におかしい挙動をするという話が行われる。Prologがどのように動作するかというのはWikipediaのSLD導出を見たほうが良いが、Prologの実装が必ずしもそれに沿ってないというのが問題となる。
これの最たる問題として
- Prologの探索アルゴリズムが深さ優先であること
- Prologがunifyアルゴリズムを走らせるときに、出現検査をしないこと
- Prologの否定を取る際に、変項を含む場合でもただちに否定をしてしまうこと
のような問題がある。これらを解決したProlog風処理系を作るのが課題になる。
13回
オセロの思考ルーチンを作る課題。これはOCamlでもHaskellでも P r o l o gでも良い。そしてなぜかRustでも良かった（許された）（なぜ？）。なので、Rustで書いたのだが、割とRustの勉強になってよかった。nomはlex/yaccになれた人間がいきなり使うと割としんどかったが。
書き始めるとわかるが、OCamlのint型は63bitで、64bit目はGCのために使われるらしい。しかしこの性質が今回の課題ではやや仇で、オセロのbitboardを実装する際できれば64bitの整数が欲しくなる。もちろんより処理の遅くなった64bit型整数というのがOCamlにも存在するが、bitboard上の演算は、速いほうがうれしそうという理由でRustで書いたほうが良いという話があった
ただ、Rustの場合、サーバーとの通信を行うクライアント側のコードなども自分で書く必要があり少ししんどかった。
あとあんまり強くならなかったので悲しい。評価関数学習はそんなに簡単ではなかった。
木：ハードウェア実験
詳細に書くのがしんどくなってきたので、以降適当にまとめる
ハードウェア実験はVerilogとVivadoに""あいさつ""するような内容。少なくとも理情で学ぶ言語たちに比べてクセが強いのでお気持ちを理解するような感じで、多分秋のCPU実験に備える、ないしコア係にはならんぞの気持ちを高める。
これしばしばVivadoの仕様（バグでは？！）みたいなのものに引っかかってしんどい気持ちになることがあり、よく引っかかったのが、
- 代入時の左右のビット数違い
- 勝手に最適化
の２つである。後者はとくにしんどく、ちゃんと回路がどのようにマッピングされたかを結局のところ見ましょうね〜という話らしい。ひえ〜
具体的な内容は前半4回ほどで、簡単な加算器とかフリップフロップをブレッドボードで作るやつをやった後に、残りでVerilogで回路を書いて、FPGAで動かす、というのをする。内容は、整数の割り算回路、浮動小数点数加算回路、UARTによる通信、AXI4バスのデータ転送回路である。最後のデータ転送あたりは、CPU実験が透けて見える内容になっていて、転送命令のFetch/Decode/Exec/Writeの工程をパイプライン化して速くするような課題をやった。
多分3Sでは一番の低レイヤーだった。
講義
講義は１限が無い、出席をほとんど取らないので期末試験でできれば（基本的に）良いという感じなのがとても良い。
実際演習は（真面目にやると）少し重めなので、授業出ずに課題やっていることもあった（良いことかは知らないが）
月：Operating System
OSの各種仕組みに関して概観する授業。マルチプロセス・マルチスレッドの周りのよくある話（Race Condition, Dead Lockとかそういう話）、CPUスケジューリングの話（FCFSからRate Monotonic, EDFおよびマルチプロセスの際のスケジューリング問題）、仮想記憶の話やPage Fault時のReplacementアルゴリズム周り(LRUやLRUの近似アルゴリズムについて）、IOとファイルシステム・権限周り、最後にバッチシステムや並列分散コンピュータ・メニーコアなどの話が非常にざっくりあった。なんか最後のメニーコア・GPGPUあたりの話が先生的には好きそう。
スライドが包括的で良いが、しかししばしばおかしなところがあったりしてfuga、まぁお気持ちで読めるが。授業にはあまり行かなかった。
火：離散数学
グラフ理論の話。グラフの基本的な話から、フロー、線形計画法・単体法、マトロイドの話が、双対性を軸に進む。
内容が半分競プロで、まぁフロー周りとかは完全に競プロでは。単体法の計算がしんどい。マトロイド周りはどちらかというと、"数学"という感じで、あまり深くやってないのでなんとも言えないが、触りをやった。あと、""予告問題""として、「polymatroidを用いて、Kruscalアルゴリズムの妥当性を証明する問題」を出そっかな〜って言っていたのでオッってなったが出なかった（何）。
あまり真面目に授業に出ていなかったのでなんとも言えない・・・。
水：情報論理
計算可能性、等式論理、命題論理、述語論理と最後にゲーデルの不完全性定理周りについて。教科書が英語。
内容が非常に広いので僕はどれほど理解できているかはわからない。ある意味初習論理 という感じで、多分反復深化が求められている。
計算可能性については、primitive recursive functionから始まり、recursive functionとwhile プログラムの等価性の話や、universal recursive functionとhalting problem周りの話、そしてRecursively Enumerable Predicateの話が続く。
各論理は、syntaxとsemanticsそれぞれについて議論した後に、健全性・完全性の話をする。特に、述語論理の完全性では、Herbrandの定理周りの話を（他の話題に比べて）深くやって、ある程度真面目に議論していた（と思う）。
まどかちゃんコンパクト性ss compact.pdf - Google ドライブ などが面白かった（ほんまか）。
木：言語処理系
コンパイラ周りの理論の授業。字句解析から始まり、LL・LR文法、型周り、中間コード生成と最適化、レジスタ割当などの話。二村射影も。
基本的に
[:タイガー本] は、https://www.amazon.co.jp/Modern-Compiler-Implementation-Andrew-Appel/dp/0521607647に沿った内容ではあるが、スライドが良いし、先生が良い（個人的な感想）。3S講義では一番好きだった。この授業は全部行ったと思う。
まとめ
最後のほう少し書くの疲れてしまった。
