
2022 年頭初の目標:

-   院試突破: ヨシ
-   絵描くのを続ける: 夏くらいで飽きた
-   ジム行ってみる: 1mm も行ってない
-   TL に張り付く時間を減らす: 2021 年よりは減った気がする．TweetDeck は悪だった
-   イ: 行った
-   装いをやる: まぁやった
    https://twitter.com/ikanag0/status/1477636154300452864

## 1 月

-   [フォントワークスのサブスク](https://lets.fontworks.co.jp/)に入った．メイドラのロゴで使われてるフォントとかを使える．あんまり使ってない．
-   ウマ娘にハマってたっぽい．Pixiv を徘徊したり絵を描いたりしてた．
-   簿記 3 級の勉強を始めて，貸借対照表の書き方とか仕訳を覚えた．詰めるのがダルくて 3 日で飽きたので試験は受けてない．

## 2 月

-   ニューラルネットワーク書くかとなったので[ガッと書いた](https://github.com/ikanago/ami)．Back propagation をがんばって書き，iris の分類ができたので飽きてやめた．
-   有馬温泉行ってきた 1
-   逆張りやめたほうが楽しいみたいなツイートをよくしていた．それはそうなんだよな
    -   と思ったら[去年の夏くらい](https://twitter.com/ikanag0/status/1415226426781954051)からっぽい

## 3 月

-   友達と劇ス上映会をした．あれは 3 回め以降は人と騒ぎながらみたほうがおもしろい．
-   電子ピアノを物色してた(伏線)

## 4 月

-   [長崎に旅行に行った](https://twitter.com/ikanag0/status/1510597869614497796)けど途中で体調悪くなって離脱する羽目になって最悪だった．体調管理には気をつけよう!
-   研究室に配属された．ほとんど研究室の雰囲気で選んだ．期待通りで居心地もよく，成功だった．
-   [CLI で 𝙈𝙮 𝙣𝙚𝙬 𝙜𝙚𝙖𝙧... するやつ](https://github.com/ikanago/omekasy)書いたらそこそこ Star をもらえてよかった

## 5 月

-   きんに君の YouTube にある動画で筋トレを始めた．サボるときもあるけどいまもやってる．
-   iPad 買った．定期的に使わない時期が来てただの板になるのでもうちょい活用したいが，手段の目的化っぽいのでむずかしい．

## 6 月

-   院試勉強はじめた
-   「ゼロからの OS 自作入門」をやり始めた．もう年末だけどまだ終わってない．USB マウスの検出ができない(USB マウスを持ってないため)かなにかで詰まってた気がする．
-   大昔に僕が書いた C コンパイラがきっかけの一つになってセキュキャンに行きました，みたいな言及があってかなりうれしかった．いろいろあるけど書いたソフトウェアはできるだけ公開していきたい．
-   なんか馬の動画を見るのにハマってた．馬かわいいからね...
-   SPY×FAMILY とまちカドまぞく 2 期が終わってしまって悲しがっていた
-   [いい colorscheme](https://github.com/rebelot/kanagawa.nvim)を見つけた．いまも使ってる．

## 7 月

-   kaito さんとチーズケーキ食べに行った．チーズケーキのためにシュッと移動してきたのかなりウケて，よかった．
-   kaito さんに劇スは映画館で見た方がいいと推しまくったら見てきてくれて，限界オタクにすることに成功した．最高〜!
-   高校生にパソコンカタカタを教えた．Google Apps Script でちょっとしたツールを作ってもらった．僕が見る限り楽しそうにカタカタしてたので続けてくれたらうれしい．

## 8 月

-   [さかな〜🐟](https://twitter.com/ikanag0/status/1559482654155685889
-   オタクと劇ス同時視聴をした 2
-   [4K モニタ](https://www.philips.co.jp/c-p/279P1_11/brilliance-lcd-monitor-with-usb-c)を買った．もう Full HD には戻れない．
-   PureScript 触ってみた．Better Haskell な面もあるし Node.js でシュッと動くのでいいんだけど，とにかく情報が少ない．Haskell の情報が役に立つことも多いんだけど，`Eff` とかはそうでもなくてつらい．
-   [フェルメール展](https://twitter.com/ikanag0/status/1557722611810832386)よかった
-   GeoGuessr にハマった．日本マップで 1 回だけ満点とれてうれしかった．
-   [尾道](https://twitter.com/ikanag0/status/1564071487338061824)行ってきた．景色がきれいだしいい感じのカフェもあるしねこもいるしよかった．

## 9 月

-   イに行った．研究職のやつだったんだけど，やっぱり開発がいいかな〜となった．
    -   関東に行ったのでしいさんと会ったり劇ス聖地巡礼をしたりした．
-   いきなりワンピースを読み始めた．12 月の半ばまでかかってようやく最近の話に追いついた．
-   [韓国ドラマ](<https://ja.wikipedia.org/wiki/%E3%83%B4%E3%82%A3%E3%83%B3%E3%83%81%E3%82%A7%E3%83%B3%E3%83%84%E3%82%A9_(%E3%83%86%E3%83%AC%E3%83%93%E3%83%89%E3%83%A9%E3%83%9E)>)も見始めた．テンポがよく，ギャグもありおもしろかった．
    -   ついでにハングルの読み方も覚えた．韓国語はわからないので，明らかに漢字語とわかる語と人名しか読んでもピンとこない...
-   リコリコ終わって悲しがっていた．「心゛臓゛が゛逃゛げ゛る゛ッ゛!」すきです

## 10 月

-   ぼざろ始まったので見たら 1 話からテンポがよすぎて一瞬で視聴確定した．
-   研究をまじめにやり始めた．
-   有馬温泉に行った 2．kaito さんが温泉入りたい欲に呪われていた(これ盛ってるかもしれないです)ので解放できてよかった．

## 11 月

-   ぼざろにハマりまくり
    -   MAD も見まくり
-   春から買うか迷ってたピアノをとうとう買った．ほぼ毎日弾いてる．かなり楽しい．
-   やっぱりセルフホストコンパイラ書きたいよな〜となったので [Go で Go のコンパイラ](https://github.com/ikanago/indigo)書き始めた

## 12 月

-   ぼざろ終わってしまった... :sob:
    -   「星座になれたら」を一生聴いてる
    -   ギターかベースもやりたくなってしまった
-   ピアノ弾くのが完全に習慣になった

## 2023 年にやりたいこと

-   読んだ本やマンガ，見た映画やアニメの感想を文字にして残すようにする
-   ピアノで弾ける曲を増やす
-   ディスプレイを見なくていい趣味をもう 1 つくらい見つける


2022年の振り返り


情報系学部での生活が折り返しを迎えようとしています．ここで自分がコンピュータ科学/工学について何を知っていて何を知らないのか確認してみることにします．

## 数学

線形代数・微積・確率統計・群論はやりました．フーリエ変換とラプラス変換もやりましたが，適当にやっていたのですらすら計算できません．そもそも入試の数学の成績がかなり悪く，人並みにはできるが決して得意とは言えません．

## CPU

単一サイクルパスとパイプラインプロセッサの命令実行の流れはざっくり分かります．キャッシュや投機的実行，レジスタリネーミングなどの高速化はよく知りません．

## OS

メモリ管理・プロセス管理をしていることやそれらの概念的な仕組みは分かります．実装はよく分かりません．

## 処理系

### コンパイラ

書いたことがあるので基本的なことは分かります．型推論も簡単なものなら分かります．レジスタを頑張って使うとか定数畳み込みとかの最適化があることは知っていますが、詳しいことはコンパイラ様のみぞ知るという感じです．

### アセンブラ

アセンブリとバイナリを 1 対 1 に変換していることは分かりますが、static とか extern な変数の扱いなどは即答できません．

### リンカ

オブジェクトファイルをくっつけたり別のファイルにある関数の位置を特定したりすることは知っていますが、どんなデータ構造を使っているかなどは知りません．ハッシュテーブルを頑張っていじるとできそうな気はします．

## データベース

関数従属性とか SQL とか B 木は知っていますが、状況に応じたテーブル設計はやったことがありません．

### 同時実行制御

よく分かりません．トランザクションとか ACID 特性とか直列可能とかは軽く習いましたが具体例は知りません．このへんは [key-value store](https://github.com/ikanago/horreum) を作ったときにやればよかったんですが放置しています．

## ネットワーク

OSI 参照モデルの各層の役割は知っています．

### IP

BGP と OSPF は概要を調べたことはあります．概念的なことは分かりますが，ネットワークを自分で構成したことがないので自分のものにはなっていません．

### TCP と HTTP

TCP の再送制御とか輻輳制御とかは勉強しました．TCP のライブラリを使って HTTP サーバを作ったことはあって，そのときに HTTP 1.1 の仕様を眺めたことはあります．HTTP 2 と 3 については新しい機能を把握していますが、そんなに活かしたことはないです．

## インフラ

Docker は使えますが，Kubernetes はデカすぎてまだ触れる気になりません．Ansible は localhost に作用するものだけは自分で書いたことがあります．　　
前述の通りネットワークを組んだことがないのでやってみたいんですが題材や機会がないので放置しています．

## アルゴリズムとデータ構造

学部のこういう授業でやるようなやつはだいたい知っていますが、実装したことのないやつもあります．またアルゴリズムやデータ構造の処理の時間計算量をフォーマルに解析するのもあまりやったことがないです．

## 暗号

RSA と準同型暗号しか知りません．準同型暗号は「準同型性があると暗号化したまま計算できてうれしいね!」．ということしか知りません．あと証明書の仕組みとか何も知らないのでそろそろ勉強しようなというところです．

## 分散システム

CAP 定理だけ知っています．よく分かってないので「A と P 被ってない?」みたいなことを思っています．分散システムはあまりにカオスそうなので興味があります．

## ソフトウェア開発

### テスト

単体テストは書けます．どう設計するとテストが書きやすいかなどの方法論はまだ知らないです．CI/CD は簡単なものなら生やせますが，あまり複雑なことはできません．

### 開発手法

アジャイルとウォーターフォールの違いは分かります．それ以外のことは分かりませんが，いまのところ学習の優先度は低いです．

## おわりに

基本的なことは踏破しつつあるので，ガッツリ深めていく分野を見つけたいところです．今はネットワークやデータベースなどカバー範囲の広い分散システムが面白そうだなと思っています．とはいえまた気が変わる(ひどいときは寝て起きたら興味を失っていたりする)と思うので，もうしばらくは興味の向いたものを気ままに勉強しようと思います．


コンピュータについて知っていること・知らないこと


## 2020 年の振り返り

2020 年ももう終わってしまいます．早いですね．今年はいつにもまして時間の過ぎるのが早かったように思います．
一方で今年は家にいる時間が長かったので自分のやりたいことをやる時間を多くとることができました．
そんな 2020 年を振り返っていこうと思います．

### 1 ~ 4 月

この時期は C コンパイラを書いていました． Rust が徐々に分かってきたので少し大きめのものを作りたくなったのがきっかけだったと思います．
IR を介してコード生成をするように実装していたのでテストがしやすかったように記憶しています．

### 5 月

Twitter かなにかで見つけた京大の講義資料に沿って OCaml のインタプリタを作りました．

[IoPLMaterials | Materials for the class “Implementation of Programming Languages” in Kyoto University.](https://kuis-isle3sw.github.io/IoPLMaterials/)

メインの目標は小さな型推論器を作ることでした． 型推論のしくみはほぼ知らなかったのですが，気合を入れて講義資料を読むことでだんだんと理解することができました．
最終的には以下のようなパターンマッチの型推論まで実装できました．

```ocaml
let rec max l = match l with
  | x :: [] -> x
  | x :: y :: z -> if x < y then max (y :: z) else max (x :: z) in
max [1; 2; 4; 2; 5; 9; 3;];;
let rec len l = match l with
  | [] -> 0
  | x ::y -> 1 + len y in
len (3 :: 0 :: 2 :: 4 :: 8 :: []);;
```

さらに，ふと思い立っておじさん風の絵文字を命令列として解釈する Brainfuck インタプリタを書きました．

[ikanago/ojisan_f-ck](https://github.com/ikanago/ojisan_f-ck)

たとえば

Rust ちゃん，おっは~ 😘😘😘😘😘😘😘😘😘✋😅
今日はもう寝ちゃったのかな 😘😘😘😘😘😘😘😘😅😘😘😘😘😘😘😘😘😘😘😘
今日も 2 時までお仕事かナ ❓🤔🤩😅😘😘😘😅😘😭😭😭😭😚🤟😅💦
金曜日，会社がお休みになったよ 😅（笑）😘😘💦😘😘😘😘😘😘😘💦💦😘😘😘💦😅😘😘😘😘😘
カラオケ 🎤 どう！💦😭😭😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘💦😅💦
お返事待ってるヨ！😘😘😘💦😚😚😚😚😚😚💦😚😚😚😚😚😚😚😚💦😅😘💦😅😘💦

というメッセージがおじさんから送られてくることがあると思いますが，これを `ojisan_fuck` に食わせると `Hello, World!` が出力されます．
おじさん風のメッセージを装ってプログラミングの素養をアピールできるのはなかなかクールではないでしょうか．
`cargo install ojisan_fuck` で簡単にインストールできるのでよければ使ってください．

### 6,7 月

もともとこのブログははてなでホストしていたのですが，静的サイトジェネレータで生成した Web ページを netlify でホストする方式に変更しました．
静的サイトジェネレータとしては Gatsby.js を使用しています． React をこのとき初めて触ったのですが，関数型言語みたいに宣言的に書くと Web ページが出来ていくのはおもしろかったです．

### 8 ~ 10 月

確か 8 月ごろにセキュリティキャンプ(セキュキャン)の応募があった気がします． セキュキャンには去年から出たいと思っていたのでエントリーしました．
今回はデータベースゼミに応募しました． データベースにそこまで深い思い入れはなかったのですが，データベースシステムを自作するという内容になんとなく惹かれて応募することにしました．

ところが頑張って応募課題をこなしエントリーしたものの落選してしまいました． そこでこのまま終わるのも後味が悪いと思ったのでひとりでデータベースシステムを作ることにしました．

データベースといえばまず RDB を思い浮かべる人が多いと思います．
しかし調べていくうちに RDB は実装がかなり大変そうであることに気づいて，代わりに key-value store を実装することにしました．
今回は LSM-Tree というデータ構造で key-value store を実装しています．簡単な説明でも紙幅を取るので興味のある人はググってみてください．

### 11,12 月

Twitter を眺めていると僕の大学の量子コンピュータを研究している研究室がプログラミングのバイトを募集していることを知りました． もともとやっていた塾のバイトにも飽きていたので応募してみるとすんなり通ってしまいました．

僕は量子コンピュータはおろか量子力学もあまり勉強したことはなかったためついていくのは大変ですが，いまのところ楽しくやっています
(なんで量子力学もやったことないのに応募したのかというと，応募要項で要求されていたスキルが C++ プログラミングと線形代数だけだったからです)．

また，12 月にはイラストの練習をいきなり始めました．前々からやろうとは思っていたのですが，この記事を読んで急にモチベーションが湧いてきたのでやってみることにしました．

[【練習内容公開】イラストを 100 日練習しました｜都路 燕禅｜ note](https://note.com/enzen3852/n/na1fecd0ac10b)

まだまだ全然うまくはないですが，当初想定していたよりは描けていてびっくりしています(もっとぐにゃぐにゃしたような絵しか描けないと思っていた)．
よければ [@ikanag0_art](https://twitter.com/ikanag0_art) のフォローもお願いします．

## 2021 年の目標

さて来る 2021 年の目標です．

-   自作言語処理系 on 自作 OS on 自作 CPU エミュ
-   興味のある研究分野を見つける
-   新たなインターン/バイトを見つける
-   イラスト環境をデジタルに移行する

一つ目はシステムアプリケーションを自作して全部統合するというプロジェクトです． ロマンがありますよね．
さすがにひとりでやっていると寿命を迎えそうなので Twitter で呼びかけてオタクを集めたいと思っています．

二つ目はなかなか大事で，2022 年からおそらく 3 年にわたって研究をすることになるので興味のある分野をぼちぼち見つけなければなりません．
僕は興味がコロコロ変わりがちなのですが，一つくらいは年単位で取り組めるほどに興味を持てる分野があると思う(あってほしい)のでそれを見つけたいです．

三つ目の目標です． 今のバイトは塾のバイトをやめるために始めたようなところがあり，量子コンピュータに特段深い興味があるわけではありません．
もっと条件がよくて自分の興味のあることに取り組めるインターンやバイトがあればチャレンジしていきたいです．

2020 年はここには書いていないことも含めていろんなものを作れたと思っています．
しかしもっとうまい時間の使い方ができると思うので(Twitter を見すぎない!)，その反省を生かして 2021 年はさらに大きな進捗を出したいです．


2020年の振り返りと2021年の目標


[NITIC CTF](https://wakuwakuclub.connpass.com/event/182469/) に参加しました．CTF の経験は cpaw_ctf を 8 割がた埋めたことと
リアルタイムのコンテストで椅子温め係をやったことがあるくらいです．  
そんなぼくでも想定以上に解けたので Writeup を書いてみようと思います．以下解いた順です．

## prime factorization (PPC)

素因数分解してほしそうな数が与えられるので適当に素因数分解をします．フォーマットを整えて投げると通ります．

## anim (Forensic)

よく分からない `flag` というファイルが降ってきます．こういうときはまず `file` コマンドで素性を調べてみます．

```
$ file flag
flag: Microsoft PowerPoint 2007+
```

PowerPoint らしいです．無理矢理開きます．すると青い背景に何も書かれていないテキストボックスが配置されています．

![Powerpoint](20200719133633.jpg)

背景色をいじったりしてもなにも見えなかったので詰まってしまいましたが，ふとサイドバーを見ると星マークがついています．  
これはこのスライドがアニメーションを含むということなのでアニメーションを再生してみました．  
するとテキストボックスがシュッと動いてフラグが出てきました． `file` コマンド使えますか問題っぽいですね．

## shift only (Crypto)

暗号化に使ったとみられる Python スクリプトと暗号文が降ってきます．

```python
from os import environ
flag = environ["FLAG"]
format = environ["FORMAT"]


encrypted = "6}bceijnob9h9303h6yg896h0g896h0g896h01b40g896hz"
shift_table = "abcdefghijklmnopqrstuvwxyz0123456789{}_"
def encrypt(text: str, shift: int) -> str:
    assert  0 <= shift <= 9
    res = ""
    for c in text:
        res += shift_table[(shift_table.index(c)+shift)%len(shift_table)]
    return str(shift) + res
for shift in format:
    flag = encrypt(flag, int(shift))
with open("encrypted.flag", "w") as f:
    f.write(flag)
```

これが暗号化のスクリプトです．あんまりよく読んでいなかったので `encrypt` でシフトしてそのシフト幅を暗号の先頭に付加しているだけの簡単な問題だと思いました．  
逆シフトする関数を書いて復号しようとしましたが，フラグっぽいものは得られません．

ここでスクリプトをよく読むと，シフト幅を `format` から一文字ずつ取ってきて，順番に複数回シフトしていることが読み取れました．つまり `format = "123"` のときは
シフト幅 1, 2, 3 で順にシフトするということです．

最後に暗号化したときのシフト幅は暗号の一文字目を見れば分かるので，それを読みながら順に逆シフトしていけばよいです．フラグの形式から，暗号の一文字目が数字でなければそれがフラグです．
実装は以下の通りになりました．

```python
encrypted = "6}bceijnob9h9303h6yg896h0g896h0g896h01b40g896hz"
def decrypt(text: str, shift: int) -> str:
    res = ""
    for c in text:
        res += shift_table[(shift_table.index(c) - shift + len(shift_table)) % len(shift_table)]
    return res

while True:
    try:
        # シフト幅
        shift = int(encrypted[0])
        encrypted = decrypt(encrypted[1:], int(shift))
    except ValueError as e:
        # 一文字目が数字でなければフラグ
        print(encrypted)
        break
```

## 8^2 (Web)

`data:image/jpeg;base64,` で始まるフラグが与えられます．ググるとこれは `img` タグに JPEG を base64 でエンコードして埋め込むときの書式らしいです．
ブラウザのアドレスバーにコピペして見るとフラグが書かれた画像が表示されました．

## Dangerous Twitter (Recon)

運営のフレキシブル基盤さんの Twitter プロフィールのリンクが提示されて，そこからパスワードを探します．  
かなり難しそうだと思って投稿を眺めていたらパスワードが書かれた紙の写っている画像が投稿されていたので，これを入力してみると通りました．
今回はたまたま開いた画像にフラグが書いてあってラッキーでしたが，最悪ツイートを全探索すればいいので運がなくても解けます．

## cha1n (Misc)

いくつかのシェルスクリプトとバッチファイルが降ってきます．とりあえずバッチファイルは無視します．  
シェルスクリプトを見ると `str=${str//()/h}` のように文字列の置換を行っています．また `c.sh` には `njtjxpxtfwx()s1Kpx()s1Kpx()s1Kpx()s1Kpx()s1Kp5x8mb83` という
いい感じに置換するとフラグになりそうな文字列があり，これに置換を施して `echo` しています．  
問題名もヒントになっていて，順に置換を施して(チェインして)やればよさそうなことに気づきます．置換をすべて書き出していい感じにつながるような順でチェインしてやるとフラグを得られました．  
実行は以下のようにしました．

```bash
$ bash c.sh | bash h.sh | bash a.sh | bash 1.sh | bash n.sh
```

## Fortran (Reversing)

一番苦戦しました．Fortran からコンパイルされたと思しき ELF と EXE が降ってきます．ELF のほうを実行すると `nitictf{Fortran}` というフラグらしきものがテキストファイルに書き込まれますがこれはフラグではありません．  
次に EXE のほうを実行しようとしますが DLL が見つからないというエラーが出ます．  
ELF に適当な入力を食わせたらなにか吐かないかなと思っていろいろ試してみますが同じ出力しか得られません．しかたないので `objdump -d -M intel` してグッとにらんでみるとどうやら入力を受け取っているわけではなさそうでした． `strings`を試してもそれっぽいものは得られず，ここで諦めてしまいました．  
ところが夜ご飯を食べてから EXE のほうを `strings` にかけていないことに気づいて試してみるとなんとフラグがありました! なぜこれを最初に試さなかったのか......

## 完走した感想

完走はできませんでしたが......  
Pwn が最後まで解けなかったのが残念ですがそれ以外は楽しく解けたので良かったです．Pwn は CTF の花形みたいなイメージがあって自力で解けるようになりたいのですが
根本的なことが分かっていない気がしています．そのうちやる気が出てくると思うのでそのときには基本的なことからやっていこうと思います．


NICIT CTF Writeup


![rate graph](20191028001138.png)

<b>このエントリは 6/16 までに下書きの大部分が書かれています．なんでや!!!</b>

## TL;DR

競プロをはじめて，ついに AtCoder で緑になりました!🎉 というわけで恒例の変色エントリです．緑になるまでの道のりを書こうと思いますが，「緑になるにはこれをして…」とかは少ないかもしれません．「はぁ，この人はここしばらくこんなことをして過ごしてきたんだな」とか思いながら気楽に読んでください．

## 2 月後半～ 3 月(競プロ開始)

時間は飛んでこの春．やりたいことの一覧を見てみると競プロが入っていたので，国公立前期試験が終わるやいなや C++環境を整えておもむろに競プロを始めました(あのとき前期は落ちた気でいたのに競プロを始めたのは謎)．

そして無事阪大に合格し，春休みは遊びと競プロでいっぱいになりました．この頃は阪大競プロ界隈が急に盛り上がるなんて思いもよりませんでした(たぶん．いつから勢いづいてきたのか正直覚えていない)．

## 4 月

キラキラ?大学生生活が始まり，精進量は目に見えて落ちました．

このころになるとさすがに AB 問題は 99％通せていたので C 問題を少しずつやっていこうと決めたわけですが，これが B 問題との差が大きく，なかなかはかどりません．いまだにはかどっていません．(このころは C の壁が大きかったのになぁ…?)

### ICPC

ICPC という大学対抗のプロコンがあるということなので「おもしろそう～」といいながら 4 月の終わりに参加の意思表明をしました．初出場なので不安もありますが心配してもしょうがないので~~楽しんでいきたいと思います．~~楽しかったです．

## 5 月

GW に はにーまさん主催の競プロ合宿・CPSCO があったので参加しました．普段 Twitter でしか見ない人たちが実体を持っていることに驚いたり(コラ)，初めてのチーム戦(チーム戦だいすき)をしたりとても充実した体験ができました．

この 4 完を皮切りにだんだん C 問題や，ときには D 問題まで通せるようになりました．

ただまぁ 4 完するとさすがに調子にも乗るのでこんな目標を立てました．

<blockquote class="twitter-tweet" data-lang="ja"><p lang="ja" dir="ltr">えーー年明けまでに水色目標ということでやっていきます</p>&mdash; いかなご (@ikanago987) <a href="https://twitter.com/ikanago987/status/1132666863719051266?ref_src=twsrc%5Etfw">2019年5月26日</a></blockquote>
<script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

~~このときは緑になるのは 8 月くらいだと思っていたので想定以上に順調に進んでいて，もしかすると本当に達成できるかもしれません．~~な～～にが 8 月だ，やっと緑になりました．目標を年度内水色に変更しました 😠．

### 空前のユーフォブーム

この春からアニメ「響け! ユーフォニアム」の劇場版が公開されており，阪大ではほとんどじゅぴろさんの影響で阪大界隈にユーフォが漂い始めました(ほんとに教祖です)．今回の映画の先行作品「リズと青い鳥」の上映会が開かれたりして，もはや競プロ界隈なのかユーフォ界隈なのか分からなくなっていました．ぼくも映画を観て涙を流し，また頑張ろうという気持ちになりました(ほんまか?)．

## 6 月

新 ABC が易化したからかはたまたユーフォを見に行ったからかコンテスト中に D まで通せることが多くなりました．ただこの月は精進が虚無で，他のプログラムを書いたりしていました．

## 7 月～ 9 月

**な ん も し て な い  
大 不 作  
空 前 の 虚 無**  
なんかテスト勉強と競プロ以外のコーディングをしてたら夏休みが終わってました．しょうがないね．

### 10 月

9 月の終わりに急に競プロに目覚めました．なんで? KUPC が近づいてたからですかね．  
1 人でばちゃを立てたりして C とか D を埋める日々を続けました．

## 覚えたこと

### アルゴリズム

-   にぶたん(まだまだ使いこなせてない)
-   累積和
-   imos 法
-   DFS(たまにバグらせる)
-   BFS(ちょっと怪しい スラスラとは書けない)
-   bit 全探索
-   gcd, lcm
-   素因数分解
-   約数列挙

bit 全探索とかはほとんど書いたことないですね．整数系の初等的なアルゴリズムは結構使えます．

### データ構造

-   C++の STL

そんなに特別なデータ構造は使ってません．`priority_queue`がかなり有用ですね．

## おわりに

緑になるまで半年くらいかかってしまいました(まぁ精進してなかったのでそれはそう)．

嬉しいんですが，今年度中の目標が水色なのでやっとスタートラインに立てた感じです．

まだやってない C/D 問題を埋めつつ，DP とかも覚えていきたいです． 標準ライブラリにないデータ構造(Union-Find 木とか)の勉強はそのうち，興味が出たらやります．


AtCoderで緑になりました


## お久しぶりです

前に 1 つ目の自作コンパイラの記事を出したのが 6 月下旬だったのでそこから 4 ヶ月経ったことになります．えっ，もうそんなに経ったんですか

[C コンパイラを自作する その 2](https://ikanago-blog.netlify.app/blog/c-compiler1.md)

以前は関数定義がうまくいったあたりで終わっていた気がします．そしてこの 4 ヶ月でファイル入力，`for`, `while`ループ，型，ポインタ，配列，そして文字列リテラルの実装をしました．こうして書き並べてみるとよくやった気もしますが道のりはまだまだ長く続いています．

それでは前回同様 commit をした日を 1 日としてカウントしながら振り返りたいと思います．リポジトリはこちら:

[ikanago/ycc](https://github.com/ikanago/ycc)

## 日記

### 23 日目(7/4)

この日は`while` ループを実装しました．gcc の吐くアセンブリと [低レイヤを知りたい人のための C コンパイラ作成入門](https://www.sigbus.info/compilerbook) をにらんで書くだけなので比較的実装しやすい機能です．繰り返し処理ができると一気にプログラミング言語っぽくなりました．

### 25 日目(7/15)

外部ファイルに記述したソースコードをコンパイルできるようになりました．C 言語でファイル IO を扱うのは初めてだったんですが結構ややこしいかった気がします．実はこの時の実装にはバグがあって，この 2 ヶ月後に修正されることになっています．

### 28 日目(7/19)

`for` ループを実装しました．`while` だけでも問題ないけどやっぱり欲しいので…

### 31 日目(8/2)

`&&`と`||`を実装しました．これ実はそれぞれがひとつの`if`ステートメントと似たようなアセンブリを吐くんですよね おもしろい

### 32 日目(8/3)

アドレス演算子`&`とポインタのデリファレンス演算子`*`を実装しました．ポインタの実装難しそう><ってなっていましたが意外と簡単でした．
まず`int`型の変数へのアクセス(スタックトップに積む)は

```asm
# int aに対してaを返す:
lea rax [rbp-4]             # raxにaのあるアドレスをロード
mov eax, DWORD PTR [rax]    # raxの値をアドレスとして見てeaxにそのアドレスにある値(a)をロード
```

一方`int*`型の変数は

```asm
# int a, int *b = &aに対して*bを返す:
lea rax [rbp-12]    # raxにbのアドレスをロード
mov rax [rax]       # raxの値をアドレスとして見てraxにそのアドレスにある値(b == &a)をロード
mov rax [rax]       # raxの値をアドレスとして見てraxにそのアドレスにある値(a)をロード
```

ポインタ変数 b には指し示している a のアドレスが入っているだけなので，一度 a のアドレスを引っ張ってきて，そのアドレスから値を引っ張ってくると終わりです．
ポインタのポインタに対しても`mov rax [rax]`をもう一度やるとうまくいくことが分かりますね．

### 36 日目(8/23)

今まで`int`型のサイズが 8byte だったので`int`は 4byte，`int*`は 8byte になるようにしました．サイズによってレジスタを指定する名前が変わるので逐一場合分けする必要があります．

ただし今回の実装では負数をうまく扱えていません．おそらく符号 bit とかの話が全く理解できていないのでこれは今後の課題です．

### 38 日目(8/25)

`int *a, *b`に対して`*a +*b`をするときに型のサイズの情報が AST の各ノード(演算子なども含む)に乗っていると嬉しかったので，AST を駆け回って各ノードに対して型をつける処理を書きました．ここで不正な計算(現時点ではポインタ変数同士をそのまま足すことくらい)を弾けるようにもなりました．

そして`sizeof`演算子を導入しました．ただし`sizeof(a)`で変数`a`のサイズは分かりますが`sizeof(int)`のようにしてある型のサイズを知ることはまだできません(実装を忘れていたのか…?)．これもそのうち実装すべき機能です．

### 39 日目(9/7)

いよいよ配列を実装しました．C 言語においては，「sizeof か単項&のオペランドとして使われるとき以外，配列は，その配列の先頭要素を指すポインタに暗黙のうちに変換される」(出典: [低レイヤを知りたい人のための C コンパイラ作成入門#配列からポインタへの暗黙の型変換を実装する](https://www.sigbus.info/compilerbook#%E9%85%8D%E5%88%97%E3%81%8B%E3%82%89%E3%83%9D%E3%82%A4%E3%83%B3%E3%82%BF%E3%81%B8%E3%81%AE%E6%9A%97%E9%BB%99%E3%81%AE%E5%9E%8B%E5%A4%89%E6%8F%9B%E3%82%92%E5%AE%9F%E8%A3%85%E3%81%99%E3%82%8B)ようです．

配列はメモリ上に連続したデータの集合ですから，先頭の要素から`i`進んだところに`i`番目の要素があります．配列`a`に対して，0 番目の要素のポインタは`a`，1 番目の要素のポインタは`a+1`，`i`番目の要素のポインタは`a+i`という調子で，それぞれの要素の値を取り出すには`*a`，`*(a+1)`，`*(a+i)`とすればよいです．実は`a[i]`は`*(a+i)`と等価であるとして定義されています．(この定義から a[i] == _ (a+i) == _ (i+a) == i[a]が成立します．実際 2[a] というコードはコンパイルも実行も問題なくできます．)

というわけで，`a[i]`を読んだら`*(a+i)`のノードを生やしていくことになります．機械的にこの変換を施しているだけなのでそりゃあ配列外参照も検知できない…のか…?(配列のサイズ超えてるかどうかはわかる気もするけど)．

### 40 日目(9/11)

みんなだいすきグローバル変数の時間です．現時点で構文的にトップレベルにあるのは関数定義とグローバル変数の 2 種類です．この 2 つは型名と識別子を読んだだけではまだ区別できず，関数の仮引数の `()` の有無を確認して初めて判別できます．(構文解析の場合分けが少なくなるので後発の言語が変数定義に let とかを使う気持ちがちょっと分かりました)

グローバル変数はローカル変数とは別で管理します．そしてアセンブリを出力するときも，データの保管場所や参照方法は互いに異なります．ここは gcc の出力をにらむとすぐに実装できました．

### 41 日目(9/12)

`char`型を実装しました．`'a'`のような文字リテラルをパースできるわけではありません．(本記事執筆時点でもまだできていません) 単に文字列を`char`型の配列として扱うためです．

### 42 日目(9/13)

前置の`++`と`--`や`+=`，`-=`を実装しました．`for`文でわざわざ`i=i+1`と書かなくてもよくなりました．

### 44 日目(9/17)

前々から気になっていた`GitHub Actions`という機能を使うことにしました．これは GitHub 上で提供されている CI ツールで，yaml で設定ファイルを書くと`push`や`pull request`ごとにテストが走って，コードがちゃんとテストをパスしたかを GitHub のページ上で確認できます．

手元と同じテストスクリプトを走らせているだけですが，いつでも正常性を確認出来たり，自分以外の人にコンパイラのレベルを示しやすくなると思って導入しました(単に使ってみたかったというのもある)．

![GitHub Actions](20191023233444.jpg)

そして 9/14 に文字列のパースを実装し終えていたので，コード生成をしました．今回もアセンブリをにらみながら実装しました．これでめでたく`printf("Hello, world!");`を出力できます!(では今までどうやって計算結果を出力していたかというと，結果をプログラムの終了コードをとして吐いて， echo \$? で確認していました．) Hello world を出力するのになかなか長い時間がかかりました…

### 46 日目(9/23)

今までは一度に 1 つか 2 つの機能を確認する単体テストしかありませんでしたが，複数の機能を詰め込んだ結合テストを書きました．次の日にはコンパイラの実装で使った C の組み込み関数の動作を確認するコードも入れて，コンパイラのコードがカバーされつつあることを実感しました．`strncmp()`とか`malloc()`とかが動いているのを見たときはかなり嬉しかったです．特に`malloc()`なんかは絶対バグると思い込んでいたので．

### 49 日目(10/6)

9/24 に行/ブロックコメントを導入したのですが，コンパイル対象のソースコードを文字列として読み込んだ時に末尾に`\001`のようなゴミが紛れ込んでくるというバグ(?)が発生しました．

以前まではファイルの入力を 1 行ごとにバッファに読み出して，自作の可変長文字列の構造体に`append`していました．このときにバッファをクリアせずに次の行を読み出しており，それが原因だろうと思って`memset()`で毎回バッファを初期化したのですがそれでも直りません．読み出している途中のバッファには`\001`のような異物はないのに，読み出し終えた文字列を見ると末尾に`\001`がいたのです．

さすがに意味が分からずキレかけたのですが，事前にファイルサイズを取得してそのサイズ分だけバッファを確保して(file_stat 構造体を使いました) 一気に読み込むことにしました．そうすれば異物の入る余地はないだろうと考えたのです．結果としてこれはうまくいって，バグを潰すことができました．めでたしめでたし．

## おわりに

これを書いた感想ですが，自分のやったことでもある程度時間が経つと細部を忘れてしまうことを実感しました．もっとコミットメッセージに動機とか解決策を詳細に書くべきですね．その時の自分は分かってもしばらく後の自分は理解できないことが多いです．(多いどころではないし，未来の自分はほぼ他人)

そしてコンパイラの方ですが，まだまだセルフホストに向けて実装すべき機能はたくさんあります．(少なくともコンパイラを書くために使った機能は実装しないといけません) 大きなところでは`struct`，`enum`，`switch`，キャストなどが残っています．現時点で「低レイヤを～」の記事に記載された機能は実装しつくしたはずなので，ここから先は自力でどうにかする必要がありますが，ここからが本番のような気もします．とは言ってもあまり気負わずに，じっくりやっていきたいと思っています．


Cコンパイラを自作する その2


## はじめに

先日 7 月 13 日(金)に，ICPC2019 国内予選に出場しました．結果は 127 位でした．

特に活躍をしたわけではないのですが，来年また出場したときに一年間で何がどう変わったのかを見れると楽しそうなのでちょろっと書いておこうと思います．

## ほんばん

今回は jupiro さんと cider さんと一緒に Euphonium として出場しました．二人とも水色です．ひえー．

本番の数日前に jupiro さんに「ぼくはエンジョイでいきます笑」と言われてびっくりしました(ちょっと前までの精進を見て ICPC ガチだと思っていたので)．これのおかげで気負わずにできたので良かったかもしれません．

16 時 30 分になると本番が始まりました．問題を印刷して僕が A を考えて，2 人が B と C を考えていました．さすがに A はｴｲｯと書くと通ったので，jupiro さんに B を実装してもらう間に cider さんと C を考えました．3^m に気づいて先に量れる質量を DFS で列挙しようというところまでは順調でした．これを考察している間に jupiro さんが発狂しながら B を通しました．

さて C ですが，`vector` の積集合を求める必要が出てきました．僕は「STL にそんなのがあったよな～」とか言いながら C++リファレンスを走査して`set_intersection`という関数を提案したのですがこれが罠でした．返り値もよく分からないし引数は二つのコンテナの`begin` と `end` だからループをいちいち回さないといけないしバグの温床でした．これを提案したのはマジでおつむてんてんで申し訳ないです．

結局それをやめて二分探索でやると(これも未解決の闇をはらんではいますが)なんとか AC しました．のこり 30 分，D は解けそうになかったので撤退して順位表を眺めていました．終了 10 分前くらいに Trumpet(阪大)が E を通したり，残り数分で Heno_world(京大)が 6 問目を通して 3 位に躍り出たりと最後まで熱い展開で楽しかったです．

## おわりに

エンジョイで行こうと言って臨みましたがコンテストがいざ始まると 3 人とも真剣だったので競プロ er だなぁと思いました．来年はアジア進出も視野に入れて練習しようと思っています．来年の阪大競プロ界隈はどうなっているのでしょうか．これからが楽しみです(なんでこんな外野みたいな締め方なんですか)．

## らいねんのじぶんへ

今回は去年の ICPC の様子を紹介しました． いかがでしたか? 去年のことなんてどうせ忘れてるだろうから書いておきました．去年の様子を思い出していただければ最高です． ここまで読んでいただきありがとうございました!😊 よければ SNS でのシェアよろしくお願いします 🙇‍♀️


ICPC2019国内予選に参加しました


## TL;DR

今回は最近書いている C コンパイラの ycc('y'は自分の名前に由来しています)についてについて書きます．

僕が C コンパイラなどというものを書こうと思ったのはある日，Rui Ueyama さんのこのページを見つけたからです．

[低レイヤを知りたい人のための C コンパイラ作成入門](https://www.sigbus.info/compilerbook)

あとは最近言語処理系の実装に燃える人を Twitter でよく観測するようになったからでしょうか．マジであの界隈はガチプロしかいない…

この Web ページでは C のソースを渡すとアセンブリを吐くコンパイラの作り方が紹介されています．電卓レベルから初めて徐々に機能を増やしながらコンパイラを開発するので，初心者でも取り組みやすくなっています．最高ですね．

## しくみとか

このコンパイラは標準ライブラリしか使っていないのでトークナイザからすべてスクラッチで書かないといけません．まぁ言語処理系の動きを勉強したいのでそれはそうなんですが

現時点の機能です:

-   扱えるのは整数だけ
-   四則演算とカッコの優先順位つき計算
-   if-else
-   外部ソースに定義した関数の呼び出し

では簡単にしくみを見てみましょう．

### tokenizer

空白を無視しながら意味のある単位(トークン)で切り分けて配列に詰めていきます．すべて読み終わるまで `while` で回すだけなのでまだ簡単ですが，識別すべき単位が増えてくるとしんどくなりそうですね…

### parser

トークナイズした配列を順に読んで，生成文法に従って再帰下降構文解析で構文木を組んでいきます．生成文法をうまく定めてやると演算子の優先順位を表現できるのですが，初めに見たときは感動と困惑が入り混じっていました．本当によくできているなぁと思います．

ここではポインタ使いまくりなのでちょっとだけポインタに慣れたかもしれません(ほんまか?)．

### code generator

構文木を根から再帰的にたどって，それぞれのノードに対応するアセンブリを出力します．関数呼び出しの実装のあたりから上記のサイトには出力すべきアセンブリが載っていないので現時点だとここが一番しんどいです．

## 日記

さて，ここからは僕が何日目にどんな機能を実装したのかを順に見ていきます．さすがに毎日開発しているわけではないので `git push` をした日を一日としてカウントします．

リポジトリはこちら:
[ikanago/ycc](https://github.com/ikanago/ycc/)

### 1 日目 (4/11)

大学入学早々こんなことをしていたんですね…先が思いやられます．

記念すべき first commit は数字リテラルを読んでそれを返すだけでした．

それから入力を解析して加減法ができるようになりました．これだけでも割とひとりで盛り上がっていました．

### 3 日目 (4/15)

この時点で構文木を構築してカッコ，乗除を含めた優先順位付きの計算ができるようになり，やっと電卓レベルのことができるようになりました．このときは木の構築を指示通りに書いていただけで，どんなふうに動作しているのかを理解しきれていませんでした．

### 7 日目 (5/20)

トークンを配列に格納していて任意長のプログラムに対応できなかったので，C++の `std::vector` のような構造体を実装しました．構造体のメンバに配列のポインタを持っていて，いっぱいになったら `realloc` するようになっています．これで任意の長さのプログラムを処理できるようになりました．

C の標準ライブラリには便利なデータ構造がほぼないので自前で実装しなければなりません． `vector` を実装したときは `void*` が分からなくて無限に悩んだ覚えがあります(これ未だにちゃんと理解してなさそう)．

### 11 日目 (5/26)

この日までにまず比較演算子を実装しました．

そして一文字の変数と `return` が使えるようになりました．変数の実装ですが，これは初めにアルファベット 26 文字分の変数領域をスタックに確保しているだけです．しかしこれでプログラムらしいものがコンパイルできるようになってグッと楽しくなってきました．

そこで任意の文字数の変数を実装するために `std::map` のような `Map` という構造体を作りました．

このころになってやっと構文木の構築が理解できるようになってきました．たぶんデバッグで鬼のようにステップ実行して木の上を走り回ったからでしょう．

### 14 日目 (6/1)

任意の文字数の変数を実装しました． `Map` に変数名と「スタックにおける RBP からのオフセット」を一組にして管理しました．変数を呼び出すときはオフセットが分かっていれば RBP の値から変数の値が入っているスタックのアドレスを特定できます．このへんからアセンブリ(というかスタック)の理解がしんどくなってきました．スタックのお絵描きをして遷移をなんとか理解していた気がします．

そろそろ意識的にコードをきれいに書かないとつらくなるくらいにコードが多くなってきました．

### 18 日目 (6/9)

`if` 文を実装しました( `else` はまだ)．そしてブロックを実装して， `if` のあとに複数の式を実行できるようにしました．だんだん様になってきましたがまだまだ道のりは長い…

いちいちデバッグするのがしんどいので，トークナイザの結果だけをダンプできるように `dump_token` 関数を作りました．これで「バグってるけどトークナイザは正常だ」ということを手軽に確認出来て便利です．

![dump token](20190627105905.jpg)

### 21 日目 (6/25)

外部の C ソースと一緒にコンパイルして，そこで定義されている関数を呼び出せるようにしました．まずは引数なし，そして引数ありでも呼び出せるようになりました．まだ関数定義はできません．

パーサはトークナイザよりデバッグが面倒(再帰だらけなので遷移を追うのにエネルギーを使う)ので， `dump_node` 関数を実装しました．根から順に再帰的に子を見やすく出力するだけです( `tree` コマンドみたいなやつ)．競プロのおかげでこういう処理をそこまで消耗せずに書けるようになっているかもしれません((木構造の問題はそんなに解いてませんが実装力の意味で))．デバッグ時に `dump_node` までうまくいっていればデバッグするのはコードジェネレータとアセンブリだけ，みたいにできてこれから少し楽になりそうです．我ながらいいツールができたなぁとか言っています．

![dump node](20190627105946.jpg)

### 22 日目 (6/27)

関数呼び出しができるようになったので関数定義を実装したのですが，定義した引数ありの関数をアセンブリで呼ぶとせぐふぉが出るのでうんうん唸っていました．デバッグをして変数を格納している `Map` がバグっていそうだなぁとはなったのですがよく分かりません．ところがヤケクソになって引数なしで関数定義をしたコードをコンパイルしてみると正常に動作しました．どうやら関数定義における引数の処理がうまくいっていないはずです．

これから ICPC と期末試験が控えているのでしばらく開発を中断したほうが良さそう…?

## まとめ

この記事は関数定義の実装がうまくいかなかったので息抜きに書きました．この開発の目標としてセルフホスト(作ったコンパイラでそれ自身をコンパイルする)を掲げているのですが，こうして振り返るとまだまだ道のりは遠いです．正直ゴールが全然見えてきません．頑張って来年の 4 月までに完成させたいですね．

このコンパイラ開発がうまくいったらアセンブラとかも組んでみたいです．コンパイラを作ったところでそれ以外の部分は結局 GCC に頼っているので… C 言語の処理系を完全に自作できたらいいですね(野望)．

これからも進捗がまとまったら記事にしようと思います．では…

## 追記

このブログを上げた次の日である 6/28 に，欠陥に気づいてちょっとソースコードをいじると引数ありの関数定義がうまく動くようになりました．再帰呼び出しも原理的にはうまくいくことが分かってはいたのですがいざフィボナッチ数列を食わせて正常に動作するのを見ると感動しました．

![](20190628151344.png)

なんとか関数定義が完成して一安心です…! 一旦開発を中断する前にテスト方法の見直しとファイル入力による実行ができるようにしたいと思います．

それではまた!


ごきげんまっすぐ

2022年の振り返り

コンピュータについて知っていること・知らないこと

2020年の振り返りと2021年の目標

NICIT CTF Writeup

AtCoderで緑になりました

Cコンパイラを自作するその2

ICPC2019国内予選に参加しました

Cコンパイラを自作するその1

ごきげんまっすぐ

2022年の振り返り

コンピュータについて知っていること・知らないこと

2020年の振り返りと2021年の目標

NICIT CTF Writeup

AtCoderで緑になりました

Cコンパイラを自作する その2

ICPC2019国内予選に参加しました

Cコンパイラを自作する その1

Cコンパイラを自作するその2

Cコンパイラを自作するその1