Skip to content

Instantly share code, notes, and snippets.

@long-long-float
Created December 12, 2017 03:15
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save long-long-float/3247474261787d6bb974d8f4a88de172 to your computer and use it in GitHub Desktop.
Save long-long-float/3247474261787d6bb974d8f4a88de172 to your computer and use it in GitHub Desktop.
seccomp2017 AdC

これはseccamp2017 Advent Calendar 12日目の記事です。

進捗どうですか?

進捗、あるにはあるのですが(コンパイラ関係のバイトを始めることができた)記事にできるほどのものではないので自分がセキュリティキャンプに応募した時の文章を晒します。自分は集中コースX「言語やOSを自作しよう」の言語自作ゼミを受講しました。

来年応募しようと思っている人は受講対象に対する想いをぶつければ行けると思います(適当)。進捗があればチューター業をやりたいと思っているのでその時はよろしくお願いします。

共通問題

共-1(1).

あなたが今まで作ってきたものにはどのようなものがありますか? いくつでもいいので、ありったけ自慢してください。

共-1(2).

それをどのように作りましたか? ソフトウェアの場合には、どんな言語で作ったのか、どんなライブラリを使ったのかなども教えてください。追加したい機能や改善の案があれば、それも教えてください。

  • FunctionQuest
    • ゲーム部分、プログラミング言語部分共にCoffeeScriptで実装した。
    • ゲーム部分はエディタにace、MarkdownをHTMLに変換するのにmarked、REPLのUI部分にjquery.console、DOM操作にjquery, コレクション操作を楽にするためにunderscoreを利用した。
    • プログラミング言語部分(以下AOScript)とゲーム部分はそれぞれ独立しており、プログラミング言語部分だけでもライブラリとして利用することができるようにした。具体的にはAOScriptに自由に型や関数を追加できるようにして、ゲーム関係の型(Goなどの命令やUpなどの方向)をAOScriptを使う側(ゲーム部分)で追加することでAOScriptにはゲーム関係のコードは入れないようにした。
    • AOScriptは関数型言語ではあるが、正格評価で(残念ながら)事前に型チェックを行わないので、手続き型言語とあまり変わらず、ソースコードをASTに変換してからそれを再帰的に評価することで値を得る。代数的データ構造は型のクラスを作ってそれを入れ子にすることで実現している。型チェックをするときは再帰的に等しいかどうかを比較すれば良い。パターンマッチはその延長で、変数が展開可能かを判定するメソッドと実際に展開するメソッドを型のクラスに実装して、展開される変数(例えば match(list){ Cons(x, xs) -> ... } のx, xs)があった場合のみ展開するようにしている。
    • 改善案は、第一に型チェックが甘い所を修正したい。AOScriptは型による束縛ができ、これにより型チェックを行うことができるが現時点ではそれができているのは一部だけである。例えば、変数宣言や演算子は型チェックを行っていない。第二に、代数的データ型辺りの機能も充実させたい。現時点で代数的データ型を定義する方法はAOScriptをエンジンとして使うプログラムから定義する以外にはない。つまり、AOScriptのソースコード内から代数的データ型を定義できないので使えるように対応したい。他にはジェネリクス(多相)関数の機能も欲しいがこれはChinoScriptで実現した。
  • Lispインタプリタ
    • JavaScript(CoffeeScript), C++, Goで実装した
    • 各言語版共にパーサから自作したので特に利用したライブラリはない(JavaScript版のみエディタ部分にaceを使用)
    • 処理の流れはまず、テキストをトークン列に変換してからそれをAST(この実装ではLispの内部構造そのまま)に変換する。トークン列に変換する処理はソースの先頭からパターンに合致するトークンに順次変換していく。ASTに変換する処理は再帰的にトークンをASTに変換していく、再帰下降構文解析で実装している。あとは再帰的に式を評価していけば実行できる。LispはLL(1)なので特に工夫をせずにパーサを実装できる(LL(k)のkが大きいと先読みしないといけないトークンが増えバックトラックが生じてしまう)。
    • Go版はスレッド機能(スレッドを生成する関数と生成したスレッドが終わるのを待つ関数)が付いているおり、これはgoroutineとchannelを用いて実装している。これは結構便利でジョブキューやセマフォなど様々な用途に使用できる。スレッドを走らせる命令が呼ばれたら中の処理を動かすgoroutineと、その処理が終わるのを待ちエラーを出力するgoroutineを走らせ、処理の結果を返すchannelを含んだスレッドを返す。スレッドの終了を待つ関数はスレッドのchannelから同期的に結果が返ってくるのを待つ。
    • C++版はGCが付いているおり、これはマーク・アンド・スイープで実装した。これはその時存在している(現在の環境から辿れる)変数、関数から辿れるオブジェクトをマークしてから、そのマークしていないオブジェクトを開放するスイープという処理で不要なオブジェクトを開放していく。
  • Lispコンパイラ
    • C++で実装した
    • 機械語を生成するのにLLVMを用いた。これはLLVM IRという中間言語の命令列をこちらで作成することでそれをx86やARM向けの機械語を生成できるフレームワークである。これを用いることでコンパイラを作成する敷居が下がる。
    • 構文解析する処理はLispインタプリタの処理を流用した。ASTを生成したらそれを再帰的に辿っていき各ノードに対応する命令(列)を生成する。LLVM IRを生成したら後はそれをターゲットアーキテクチャ(例えばx86)向けの機械語を生成すれば実行ファイルが生成される。
    • 改善案として、第一に型に関する機能を強化させたい。例えば現状だと変数を定義するときに型を書く必要があるが、型推論の機構を導入することで型を省略できるところは省略できるようにしたい。第二に、print関数などの型チェックが甘いところがあるので型チェックができるようにしたい。第三に、Consを作成する時にヒープから領域を確保するが、これで確保した領域を解放していないのでメモリリークが生じてしまうのでGCを導入したい。
  • ChinoScript
    • JavaScriptで実装した
    • この言語のインタプリタの処理の流れも上の他の処理系と同じで、パースしてからそれを再帰的に評価している。ただ、この言語には変数に型を付けるので型チェックも行っている。型の内部構造はAOScriptと同じで型の中に型を入れられるようにすることで配列型などに対応している。また、この言語はジェネリック関数に対応しており、これは型チェックをするときにある型aの宣言時には未定の型のリストを再帰的に型チェックをするメソッドに渡す。チェックするときに自分の型が先ほどのリストにあったら比較対象のその時の名前と比較対象の型を対応付けさせる。例えばArray<a>を要求している関数があってそれにArray<int>の値を渡す時、まずArrayの型チェックが行われるがこれらの名前は等しいので次に入れ子になっている型(inta)同士の比較が行われる。このときaは未定の方のリストに入っているので比較対象のintaが対応付けられる。後は引数や返り値にある未定の型を確定している型に置き換えれば良い。
    • 複数の値を束ねることができる、構造体を扱えるようにしたい。現状でも値を束ねることができるタプルがあるが、構造体はそれとは違い、中の値に名前を付けることができる。また、yieldの機能も実装したい。これについては、実装のアイディアがあり実際に実装してみたのだが思いの外、規模が大きくなり提出までに間に合わなかった。アイディアはまず、プログラムを専用のVM(スタックマシン)で実行できるコード向けにコンパイルする。これによりif文などの入れ子になっている構造を無くす。つまり状態(行数や変数、スタック)が与えられればあたかもその状態で直前まで実行していたかのように振る舞うことができる。後はコンパイルしたコードをVMで実行して、yieldが呼ばれた時に状態を保存しておいて、再び対象の関数が呼ばれた時には保存した状態から復帰すれば実現できる。コンパイルする部分まではできたのだが、コードを実行するところで間に合わなかった。型が無いJavaScriptで実装したため変更途中でコードの正確性が保証できなくなりつつあるので、作りなおすときはTypeScriptで実装したい。
  • llfOS
    • C言語とアセンブリ(NASK)で実装した
    • 基本的には「30日でできる! OS自作入門」に沿って作成しているが、自分のスタイルとは異なるところ(struct宣言時にはtypedefを付ける、変数名等)は自分なりに変更したが、本質的なところは変わらない。
    • 自作のシェルを実装して、llfOSに載せたい。シェルはコマンド実行、パイプ、リダイレクトの機能を備えたものを実装したい。また、ifコマンド等を使用できるようにしてシェルスクリプトとして実行できるようにもしたい。
  • ratex
    • Rubyで実装した
    • Rubyには演算子の動作を上書きする機能があるのでそれを使用してコードの見た目と実際に評価した結果を近づけることで、Ruby上でtexの数式が書けるようになっている。それに加えてRubyには未定義のメソッドに対してのコールバック(method_missing)があるのでそれを利用して、変数を宣言すること無くその変数名を利用することができるようにした(例えば f(x, y) == x * y と書けるがf, x, yでmethod_missingが呼ばれる)。なぜ変数なのに"method"_missingなのかというと、ratexで式を実行するときはinstance_evalという対象のインスタンスのコンテキストで実行できるメソッドを利用していて、これによりレシーバ(dog.runのdog)は省略できるので、実は変数ではなくメソッド呼び出しであるからだ。
    • f(x) = y と書けるように、=を使えるようにしたい。ただし、現状Ruby(というかほとんどの言語)では関数呼び出しを左辺に置くことが出来ないので実現は恐らく出来ない。関数呼び出しでなければいいので x = y なら対応可能(Rubyでは代入もメソッド(.x=)となる)。

共-1(3).

開発記のブログ、スライドなどの資料があれば、それも教えてください。コンテストなどに出品したことがあれば、それも教えてください。

共-1(4).

Twitterアカウント、Github、ブログをお持ちでしたら、アカウント名、URL等を記載してください。

Twitter: @long_long_float Github: @long-long-float ホームページ: http://llfloat.net/ Qiita: http://qiita.com/long_long_float

共-2(1).

あなたが経験した中で印象に残っている技術的な壁はなんでしょうか? (例えば、C言語プログラムを複数ファイルに分割する方法など)

  • プログラムを始めたばかりの頃、ディレクトリを再帰的に扱う方法がわからなかった。
  • 簡易的なオンラインジャッジのシステムを作ったときにプログラムを安全に実行する方法がわからなかった。
  • インタプリタを作っている時にyieldの実装に悩んだ。
  • COMET II向けのCコンパイラを作成しようとして失敗した。

共-2(2).

また、その壁を乗り越えるためにとった解決法を具体的に教えてください。 (例えば、知人に勧められた「○○」という書籍を読んだなど)

  • プログラムを始めたばかりの頃、ディレクトリを再帰的に扱う方法がわからなかった。
    • C言語の入門書を読んだ
  • 簡易的なオンラインジャッジのシステムを作ったときにプログラムを安全に実行する方法がわからなかった。
  • インタプリタを作っている時にyieldの実装に悩んだ
    • プログラミング関係の雑誌(日経ソフトウエア)のLisp処理系の実装記事のcall-ccの実装を読んでいる時にアイディアが思い浮かんだ。 詳細は共-1(2)で書いた。
  • COMET II向けのCコンパイラを作成しようとして失敗した。(未実装)
    • LLVMを使用してLispコンパイラを作成した後で改めて考えなおしたらアイディアが思い浮かんだ。失敗の原因は、C言語のソースコードから直接アセンブリに落としこもうとしてレジスタを割り当てる処理(例えば足し算をするのに何番のレジスタを使うか)が上手く書けず、ソースコードが訳が解らなくなってしまった。 なので直接アセンブリに落としこむのではなく、一旦中間言語に落とし込んでからそれをアセンブリに変換するようにすると実装がある程度楽になると思う。中間言語はスタックベース(命令の引数の受け渡しをスタック経由で行う)や命令に返り値を持たせるようにしてレジスタが不要になるようにする。

共-2(3).

その壁を今経験しているであろう初心者にアドバイスをするとしたら、あなたはどんなアドバイスをしますか?

考えても調べても、わからなければとりあえず放置して良いと思う。しかし、その疑問を忘れてはダメでどこかにメモするなりして記憶に留めておくと後で知識が増えた時に、そのことについて調べることができ、恐らくその時には理解できると思う。 知識を増やすためには当然勉強をするしかないが、自分の場合は何か作りたいものが出てきたら、事前に勉強をほとんどせずにそれを作っている。勉強していない状態で試行錯誤して作ると、自分でいろいろ考えることになるので、後で勉強するときにいきなり勉強をするよりも頭に入って来やすいと考えている。 あとは余り興味がない分野もアンテナを張ったり少しは勉強しておくと、意外なところで自分の興味と繋がったりするかもしれない。

共-3(1).

あなたが今年のセキュリティ・キャンプで受講したいと思っている講義は何ですか?(複数可) そこで、どのようなことを学びたいですか?なぜそれを学びたいのですか?

受講したいと思っている講義は、「集中コースX 言語自作ゼミ」 そこでは、

  • プログラミング言語処理系の実装のテクニックを学びたい。
    • 川合さんのEssenのwikiを見ていると内部処理、構造についてのテクニックが書かれているが、自分が処理系を作るときはそういうことは全くと言っていいほど考えていないので、言語自作ゼミでは自分の実装について助言を受けながら身に着けていきたい。
  • 新規のプログラミング言語のアイディアを得たい。
    • 自分で、新しくプログラミング言語を作ろうと思っていてもアイディアが思い浮かばない。言語自作ゼミではプログラミング言語自体に興味がある人が集まると思われるので、その参加者たちや講師と交流をすることでなにか新しいプログラミング言語のアイディアを得られると考えた。現に、Essenの「変数がファイルとして永続化される」というのは斬新だなと思った。

共-3(2).

あなたがセキュリティ・キャンプでやりたいことは何ですか? 身につけたいものは何ですか?(複数可) 自由に答えてください。

  • プログラミング言語に興味がある仲間を増やしたい
    • 同年代のプログラミング言語処理系に興味がある人や、他分野(特に自作OSに興味がある人)と交流して刺激を得たい。同じ興味の人からは、恐らく自分より技術力がある人が来ると思うので、そういう人たちからいろいろ吸収したり、自分が若干傲慢になっているところがあるので刺激を受けてさらなる高みを目指したい。他の分野の人からは普段自分が触れていない技術についての話を聞いたりして知見を深めていきたい。また、自作OSにも少し興味がある(OS自作本を見ながらOSを作っている)ので、そのあたりの話も聞いてみたいと思った。
  • 技術力を高めたい
    • 自分の技術力が独学では頭打ちになってきているような気がするのでセキュリティ・キャンプに参加して刺激を受けることでそれをブレークスルーさせたいと考えている。

選-X-言(1).

あなたの得意なプログラミング言語とそれぞれのプログラミング歴を教えてください。どのくらい書けるのかが知りたいです。たくさんできる人は上位5つくらいで十分です。過去にどんなものを作ったのかも教えてください。共通問題「共-1(1)~(3)」で十分に説明した場合は、ここは未回答で構いません。

  • Ruby
    • 3年
    • 内部構造を少し把握している
      • 処理の流れ(字句解析ー>構文解析ー>RubyVM用のバイトコードにコンパイル->実行)
      • Rubyは数値もクラスのインスタンスだが内部的にはただの値(インスタンスへのポインタに直接数値を入れる)
    • 作成したもの(共通問題で紹介したものは除く): アルバイトで作成した業務向けシステム(Rails使用)、競技プログラミングの回答に使用
  • JavaScript(TypeScript, CoffeeScript)
    • 3年
    • 作成したもの(共通問題で紹介したものは除く): COMET-IIのエミュレータ、ゲーム(ローグライク)、任意のページにニコニコ動画風のコメントを流せるスクリプト、述語論理が正しいか判定するスクリプト、アルバイトで作成したSNS(Vue.js使用)
  • C++/C
    • 4年弱
    • 作成したもの(共通問題で紹介したものは除く): Brainf*ckのGUI拡張、Brainf*ckコンパイラ(LLVM使用)、ゲーム(全方位シューティング、マインスイーパー)、競技プログラミングの回答に使用

選-X-言(2).

このゼミでどんなことをやるか具体的に説明しています。 http://khfdpl.osask.jp/wiki/?seccamp2017 をよく読んで、もしプログラミング言語にこういう機能があればいいのにと思うことがあればぜひ提案してください。既に何らかの言語で実現されてしまっている機能であっても構いません。もし複数のアイデアがあるのなら遠慮しないでたくさん書いてください。

  • 変数の型について、宣言時のみ代入の型チェックが行われると書いてあるが、それ以外の最初に変数に代入された時も宣言した時と同じように代入する値の型にすると良いかなと思った。同じ変数に違う値を代入することは滅多になく、型を固定することによる、プログラムミスの検出や最適化がしやすくなるというメリットを上回ることはないと考えるからだ。それでも違う型を代入したいということが起きた時(例えばリストを実装したくなった時)はany型という特別な型を用意して、any型の変数については型チェックを行わないようにすれば安全性は失われるが整合性は取れる(実際TypeScriptという言語は静的型付けだがany型も存在している)。
  • 上の型に関連して、すでに実装されているかもしれないが、配列など入れ子になっている構造の型もかけると良いと思った。Javaなどの言語ではジェネリックと呼ばれている。型の表記は Array が自然だと思う。
  • 関数の引数にはコンマは欲しいかなと思った。なぜなら、例にもある通り c = func(-1, -2 4) では付けないと曖昧になってしまい、それをコーディング中に意識しないといけないのは煩わしいと思ったからだ。コンマは必ず必要ということにすればタイプ量は増えるがこういったことを考えずに済む。また、見た目的にもコンマがあったほうが引数の区切りがわかりやすくなって読みやすいように考える。

以下は自分だったらこういう仕様にするだろうなという想像です

  • インライン***について
    • スクリプトのソース中に他の言語のソースをインラインで書くという機能で懸念されるのがデータのやり取りだ。インラインで書くのであればなるべくデータはシームレスにやりとりしたい。そこで、このEssenの特徴である「変数が永続化される」ことを利用する。変数がファイルに保存されるのであればそれ経由でやり取りすれば良くなる。例えばRubyであれば、動的にメソッドが定義でき、また未定義のメソッドに対してフック処理(method_missing)を挟むことができるので、変数のアクセス(=メソッドへのアクセス)時に読み込み、保存(またはスクリプト終了時にまとめて保存しても良い)するようにすればスムースにやり取りできる。これらの処理をインラインで書かれたスクリプトにつなげて実行すればほぼ違和感はなくなる。
  • 変数がファイルとして永続化される点について
    • 保存される時のフォーマットは他の言語からの再利用性も考えるとJSONやMessagePackを使うのが良さそうだと思った。wikiを見る限りだと型はJSON等にある型で間に合いそうである。関数のみJSON等にはないが構文解析時に生成したASTをkey-valueの構造に落とし込めば保存可能である(少し手間はかかるが)。

選-X-言(3).

その他に自己アピールしたいことがあれば自由に書いてください。なおこのゼミでは加点評価で採点します。つまりまずいことを書いてしまっても減点はしません。書いておきたいことはなんでも書いてください。なお、図や写真などを使いたい場合はどこかにアップロードして、文章内にURLを書いておいてください。

自分はプログラミングが好きで、プログラムを始めてから6年の間で色々なものを作ってきた。自分は飽き性だが、なぜプログラミングは6年も続けられたかというと、自分にとってプログラミングは楽しいことだからだ。 プログラミングのどこが楽しいかというと、気軽に自分の想像しているものが具現化できる事である。これがしたいなぁ、できるかなぁと思ったらすぐにキーボードを叩いて作り始めることができる。これはソフトウェアにしかできないことだと思う。作ったものはあっさり動くこともあれば、思い通りに動かないこともある(自分はこっちの方が好きだ)。思い通りに動かないときは試行錯誤して、やっと動いたときの感動もプログラミングの楽しさだと思う。 6年プログラミングをして、自分は言語処理系などの比較的低いレイヤーに興味があるということに気がついた。プログラミング言語を作る楽しさは自分で1つの世界を作ることができることだと思っている。ライブラリやフレームワークだとそれを実装する言語の範囲内に収まってしまうが、プログラミング言語はより広い範囲の、いわば世界を作ることが出来ると思っている。手続き型言語しか知らない状態でHaskellを勉強した時は様々なところで衝撃を受けた。例えばHaskellは純粋関数型言語で副作用(例えば変数を上書きすること)が無いが、ではどうやって入出力をするかというと"入出力をする命令"を返すとその通りに処理系が実行してくれる。Haskellでは上手く構文が作られているのであたかも手続き型言語を書いているかのように入出力処理を書くことができる。これがすごいと思ったのは入出力をする関数、つまり返り値の型が"入出力をする命令"の型になっているので、ついうっかり出力の処理を書いてしまうことがない。そういう処理は通常言語仕様として組み込むと思うが、Haskellはそれを基本的な型の仕組みで実現しているところがすごいと思った。そういうわけでセキュリティ・キャンプではそのような、自分の想像を超える事柄を得たいと思っている。 また、将来も言語処理系あたりの分野でやっていこうかと考えており、そのような分野でも通用するような技術力を身に着けていきたい。

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment