Neunomizuの日記

俺だけが俺だけじゃない

アドベントカレンダー24日目 EEICコンパイラ部への予習

情報

advent_function.md

アドベントカレンダー24日目 EEICコンパイラ部への予習

eeic （東京大学工学部電気電子・電子情報工学科） Advent Calendar 2018 その2の24日の記事を書かせていただきます．

記事を書いた動機

基本的に強い人についていけば同じ程度には成長できるだろうという高度経済成長期の日本と同じ発想をEEIC生活をしているのですが，自分も貢献しないとそろそろEEIXTさせられそうなので記事を書こうと思いました．しかし実力がないのでポエムとなっています．

自己紹介という名の自分語り

EEIC2019のものです．推敲していたら期末試験2週間前という状況で単位がやばいです．どの言語も第2外国語(なんなら第3外国語)よりも長い期間触ったことがないという感じなので大体察してほしいです．

EEICに入った当時，私は

「プログラミングなんてOSSライブラリにある関数に引数打ち込めばおしまいでしょ(笑)」

というくらいの頭ハッピーセットwould-beハッカーやろうでした．

しかしEEICの授業を通して(...というかガチプロ学科民の影響？)で脱EEICの阿蒙を目指してぷろぐらみんぐを自分なりに頑張っているという感じです．

ですからこれからする話には多少どころでなく間違いが散見される可能性がありますがその際は是非ご報告ください．訂正します．

EEICコンパイラ部(仮称)

EEIC2019ではなにやら春休みにコンパイラを作るらしいです．

学科Slackにチャンネルは出来ていませんが心にはあるっぽいってことで勝手に「EEICコンパイラ部」と読んでいます．

最初コンパイラを作ると聞いたときは

「コンパイルってC言語でgccを書くと.cファイルを実行できる形にするやつよね．」

くらいの知識でしたが，みんなで何かを作るって面白そう！くらいのノリで参加を決意しました．

しかし，流石に何も知識がないままコンパイラ作りに参加しようとしてもお互い損だと思うのでコンパイラとかそこらへんについてした自分の予習みたいなのを今回は記事にします．

コンパイラとは

コンパイラ（英:compiler）とは、コンピュータ・プログラミング言語の処理系（言語処理系）の一種で、高水準言語によるソースコードから、機械語に（あるいは、元のプログラムよりも低い水準のコードに）変換するプログラムである。^1

らしいです．人間が読める形のコードを，機械が読める形あるいはその橋渡しをする形のコードに変換するプログラムのことです．

しかし，上の動作をただ「コンパイル」と呼ぶと多少語弊があり，実際はビルドと呼んでその中の作業の一つをコンパイルと言ったほうが正しい(はず)です．

ビルドには順序があります．

f:id:sosodemonai:20181225024719p:plain
ビルドの様子

それぞれの役割は大体以下のようになっています

  • プリプロセス...ソースコードに前処理を施し，インクルードやマクロの処理をしたりコメントを取り除いたりする
  • コンパイル...文法チェックをして機械語にマシン語に変換してオブジェクトファイルを作成する
  • リンク...オブジェクトファイルを統合して実行可能ファイル(~.outや~.exeみたいなの)を作る

ですから実際にコンパイラを作ろうとするしたら色々な処理のソースコードを書かないといけないのですね．大変そうです(小並感)．

より厳密に言うと字句解析，構文解析，意味解析...などなどあるのですがそこらへんも書くと長文失礼します君になってしまうので端折りました.

インタプリタとは

ちなみに言語を実行するためにはコンパイラ以外にインタプリタを通すという方法もあります．

インタプリタとは

インタプリタは、およそ次のいずれかの動作をするプログラムである。

らしいです．

例えば，EEICだと授業で使っているPythonがインタプリタ言語ですね．インタプリタの長所はコンパイラに比べるといちいちビルドをしなくて良い分内容の修正が楽なことです．

授業だとそんなに大きなファイルをビルドしませんがおそらく将来でかいファイルをビルドするときに実感するんでしょうね．

しかし，反面実行速度は遅いです．これに関しては競技プログラミングをやっている方などはご存知のはず(？)．

上の2つじゃあコンパイラ，インタプリタの説明物足りないよ！って人はこの落合陽一大学のプログラミング言語処理の授業用ページがおすすめです．

じゃゔぁはいやじゃ

こんな感じで調べてると中々こういうの作るのも面白そうだなとか思ったので実際にコンパイラ部発案者(？)のおすすめするドラゴンブックのAmazonページを見ると

コンパイラ解説書として国際的に高い評価を得ている“ドラゴンブック”が、コンパイル技術に関する最新の研究成果と話題を盛り込み全面改訂。コンパイラ設計への徹底した入門的な解説からスタートし、ソフトウェアの設計と開発における諸問題へのコンパイル技術の応用へ至るまで、広範囲に及ぶ話題をカバー。本書の前半は学部レベルでのコンパイラの授業用に、後半はコード最適化に重点を置いて大学院レベルでの授業用に構成。

→→→→→→後半はコード最適化に重点を置いて大学院レベルでの授業用に構成←←←←←←

は？(まだ半年もプログラミングしてねぇぞ…？？？)

となりました．しかもソースコードが一部Javaだし...

まあ別に今更Javaを始めてもいいんですけど，オブジェクト指向言語ならPythonやってるしどうせなら他にないかなということで探したところ...

SICPについて

どの本も良さそうですが，それを差し置いて私はStructure and Interpretation of Computer Programs(通称:SICP，シクピー)をやりたいなと思いました．

SICPの内容を簡単に説明するとプログラミング初心者もインタプリタ，コンパイラを作っちゃおうという本です(ただしCコンパイラのように低レイヤーもやるのかは不明)．

その際にSchemeというLispの方言の関数型言語を使います．

この本はMITのelectrical engineeringとcomputer scienceを専攻する学生の必修科目の教科書でした(しかし今はもう扱っていないようです←)．

個人的にこの本をやりたいなぁと思ったのは以下の理由からです．

  1. 関数型言語がいじれる
  2. electrical engineeringとcomputer scienceを専攻する学生って実質EEICじゃない...？と思った
  3. コンパイラだけじゃなくてインタプリタ(インタプリタだけじゃなくてコンパイラ？)まで一冊で作れる
  4. ネットでただで公開されている(金がかからない)

Schemeという言語に関して

SICPでのソースコードはSchemeという言語です．

もはや説明を放棄しているように思われますが，wikiを見れば大体どんな言語か分かると思います．

簡単にまとまった動画もあるのでこちらも見るといいと思います．

()とλをやたら使う陰キャ言語ということですね(オタクじゃん)．この陰キャ，文法は簡単です．現実の陰キャも紋切り型の会話しかしていない静的型付け言語を話しているので似たようなのですね(Schemeは動的型付け言語です)(静的スコープではありますが)

処理系

1975年から登場した言語なのでもちろん色々処理系があります．

私はGaucheを使っていますが，SICPのために環境構築をしているブログは色々あるので他の処理系を試してみたいという方はどうぞ．

文法

これからは基本的な文法に関する解説をしたいと思いますが，完全な初心者向けです．多分Lisp系の言語をいじった人から見ると退屈だと思うので読み飛ばして頂いて結構です．

最初に出入力をやりたいのですが，その前にこの言語は少し触れましたがデータ構造が基本的にリストです．

(<手続き> <データ1> <データ2> ...)となっています．

それをそれを頭に入れて以降の説明を読んでいただきたいです．

ではHello Worldから行きましょう．

入力がreadで出力がdisplayです．

    (display "Hello World\n")

これは他のプログラミング言語をやっていれば読むだけで何を言いたいかはわかるでしょう．

次は四則演算です．+ - * /がそれぞれ足し算，引き算，掛け算，割り算の手続きです．

  • 問題2「太郎君は100円のりんごを2個，花子さんは200円のみかんを3つ買いました．一人あたり何円支払いましたか？」

  • 解答2

    ((100 * 2 + 200 * 3) / 2)  ; 400

これも簡単ですね．ちなみにコメントアウトは;で行います．

次は関数の定義と真偽値に関してやろうと思います．

Schemeのデータ構造はリストです．そのため関数を定義するときは入れ子構造のリストを書きます．例えば足し算をする関数addを定義するときは以下のように書きます．

    (define (add a b) (+ a b))

これは(add a b)を(+ a b)だと定義していると直感的にわかりやすいと思います．

真偽値は手続きの部分に= < > <= >=が入り，左右の値を比較して真か偽を判定します．

例えば(< 2 1)は2と1を比較して2より1の方が小さいので偽だと判定します．

一応Schemeでは真偽は#t，#fと書きます．しかし，SICPではtrue，falseと書いてあります(紛らわしい．．．)．

ifも使えば分岐が出来ます．真偽を判断する手続きを述語といい，

    (if <述語> <真のときの値> <偽のときの値>)

と書きます．では問題に行きましょう．

  • 問題3「引数xが5より大きい時10，それ以外のときは0を返す関数を定義せよ」
  • 解答3
    (define (round x) (if (> x 5) 10 0))

どうですか？少し()が増えてきてこんがらがってきたと思います．

このようにリストが増えた際に中のリストの一部だけを使いたいという時があると思います．

そのようなときはcarとcdrという手続きを使います．

carは(car <リスト>)という風に使い，リストの先頭(一番左)の値だけを取り出します．逆にcdrはリストの先頭(一番左)以外の値を取り出します．

今まで出てきた文法知識を使って関数型言語最大の特徴と言っていい再帰関数を書いてみましょう．一応Schemeにも繰り返し文はありますが普通は書きません．そしてここまでくれば大体の基礎の基礎はつかめていると思います(要出典)．

では最後の問題です．

  • 問題4「nの階乗を返す関数を定義せよ(nは0以上の整数)」
  • 解答4
    (define (factorial n)
        (if (= n 0)
        1
        (* n (factorial (- n 1)))))

こんな感じになります．もうここまで書ければSchemeにも慣れたことでしょう．SICPは一応プログラミング経験のない受講者に向けて書かれているので最初はSchemeの文法の説明があります．

ですからここまで読んでいただいた方ならネットで調べながらやれると思います．

文法をかなり雑に紹介しました(間違いも書いたかも？)が，詳しく知りたい方はもうひとつのScheme入門というHPが詳しいのでよかったら御覧ください.

勝負の春

このようにめっちゃSICPを推していますが，もしコンパイラ部の総意がドラゴンブックやることな場合は自分の意思を一般意思だと思いこんでやります(実際のところ発案者は最終的にドラゴンブックをやりたいと言っていただけで最初は初心者もできる本からやると言っていました．誤解を生んだら誤ります)．

集まって何かを作るというだけで面白そうですし，詳しい人が選んだものなら納得出来るというのが本音です．

というか自分で作る経験もしたいからSICPは自分でやってみたい(この記事はなんだったのか...)．

受験シーズンの受験生は今頑張っていると思います．しかし私の周りの学科民は努力家で受験生に負けず劣らず勉強していてそういう環境楽しいです．

卍期末試験と春休みは圧倒的成長の機会ですね卍

...と媚を売ったのでもし本当に春やるなら誰か誘ってくれるでしょ...

この記事で出てきた本が読みたい人

これをSlackでも言った気がしますが，洋書が読みたい人は「英語版タイトル pdf」で検索すると幸せになれるかもしれません．ちなみにSICPは2nd editionの方が綺麗です．

引用した本

別にアフィリエイトはもらってないので安心(？)

スッキリわかるC言語入門

スッキリわかるC言語入門