soukouki’s diary

誰かの役に立つ記事をかけたらいいなあ

トップ > セキュリティキャンプ2024 Cコンパイラゼミ 応募課題晒し

セキュリティキャンプ2024 Cコンパイラゼミ 応募課題晒し

セキュリティキャンプ2024のCコンパイラゼミについて、選考に通過したので応募課題を公開したいと思います。

セキュリティキャンプに応募するのは今回が2回目です。前回はエントリーだけして、応募課題を前にして諦めてしまった記憶があります。今年の春になり、去年参加した友人の勧めで今年も応募しました。今は浪人・留年のない学部4年生なので、今年が応募できる最後のチャンスということになります。今年受かって本当に良かったです。

応募したのは開発コースの「Rust プログラム検証ゼミ」と「Cコンパイラゼミ」です。一応第3希望として他のゼミも応募したのですが、第2希望までの応募課題で力尽きてしまったので、この2つのコースに応募することになりました。

結果として、Rustプログラム検証ゼミは通過できず、Cコンパイラゼミに参加する運びとなりました。個人的には、Rustプログラム検証ゼミの方が今一番扱っているCoq言語との相性も良かったので少し残念です。ともかく、なんとか選考を通過することが出来たので、楽しんできたいと思います。

応募課題はRustプログラム検証ゼミは6000字、Cコンパイラゼミは13000字でした(コード込み)。今となっては、第1希望の方はもっと沢山書いた方が良かったのかなと思います。

今年の春休みに、Rui Ueyamaさんの「低レイヤを知りたい人のためのCコンパイラ作成入門」を読み、本文中に書かれているステップ28を超え、プリプロセッサの直前あたりまでCコンパイラの作成を進めました。この応募課題には、そこで得られた経験を元に書いているものが多いです。

前置きはこのくらいにして、以下が応募課題となります。

問 1: コンパイラを一つ選び、そのコンパイラがどのような過程でソースコードから実行バイナリを生成しているかを、現在知っている範囲で説明し、実際にコンパイラがその過程を経ているということを自分なりに検証してみてください。どのように検証したか、そして、その検証結果から何が言えるかを教えて下さい。どの言語をコンパイルするコンパイラかは、好きなものでかまいません。

gccをもとに説明します。gccのコンパイルフェイズは以下になってると考えます。

  1. 字句解析
  2. プリプロセス
  3. 構文解析
  4. 意味解析
  5. アセンブリの生成
  6. オブジェクトファイルの生成
  7. リンク

字句解析とプリプロセスの順番について

gccの-Eオプションを使うことで、プリプロセス後のコードを確認できます。ここで、字句解析ではエラーになるがプリプロセスは許容されるなコードを書くことで、どちらが先に行われるかを確かめられます。以下がそのコードとエラー内容です。

#define CONSTANT_VALUE 42
int main() {
  return CONSTANT_VALUE;
}
/*

$ gcc -E test1.c
# 0 "test1.c"
# 0 "<built-in>"
# 0 "<command-line>"
# 1 "/usr/include/stdc-predef.h" 1 3 4
# 0 "<command-line>" 2
# 1 "test1.c"

int main() {
  return 42;
test1.c:5:1: error: unterminated comment
    5 | /*
      | ^
}

このコードでは/* ... */形式のコメントの前半分を使い、コメントを終了しないようにしました。これをプリプロセスまで行うコンパイルオプション-Eとともにgccを実行すると、終了していないコメントというエラーが出ました。このエラーは字句解析で発生するエラーのため、字句解析はプリプロセスよりも前に行われていることがわかります。

(追記)

出力をよく見ると、returnの部分のCONSTANCE_VALUEが42に置き換わっているのがわかります。なので、このサンプルコードではどちらが先に行われているかを確認することはできません。代わりに、次のコードと、それを-Eオプションを使って実行した結果を見てみます。

/*
#define CONSTANT_VALUE 42
*/
int main() {
  return CONSTANT_VALUE;
}

$ gcc -E test11.c
# 0 "test11.c"
# 0 "<built-in>"
# 0 "<command-line>"
# 1 "/usr/include/stdc-predef.h" 1 3 4
# 0 "<command-line>" 2
# 1 "test11.c"

int main() {
  return CONSTANT_VALUE;
}

このコードでは、#define CONSTANT_VALUE 42のプリプロセス部分をコメントアウトしています。もしも字句解析より前にプリプロセスが動くなら、このコメントの処理よりも前にプリプロセスが働き、CONSTANT_VALUEは42に置き換えられるはずです。しかし実際はそうではなく、CONSTANT_VALUEは置き換えられずそのままになっています。このことから、プリプロセスより前に字句解析が行われ、コメントの除去が行われていることがわかります。

プリプロセスと構文解析の順番について

これについても-Eオプションを使い、プリプロセスでは許容されるが構文解析ではエラーになるコードを書くことで、どちらが先に行われるかを確かめます。以下がそのコードとエラー内容です。

#define CONSTANT_VALUE 42

int main() {
  return CONSTANT_VALUE + ;
}

$ gcc -E test2.c
# 0 "test2.c"
# 0 "<built-in>"
# 0 "<command-line>"
# 1 "/usr/include/stdc-predef.h" 1 3 4
# 0 "<command-line>" 2
# 1 "test2.c"


int main() {
  return 42 + ;
}

このコードにはreturn <定数> + ;という誤った構文のコードが含まれています。これをプリプロセスまでを行うコンパイルオプション-Eとともにgccを実行すると、プリプロセスによる式の置き換えが行われます。そして構文の誤りによるエラーは無く、プリプロセスは構文解析よりも前に行われていることがわかります。

構文解析と意味解析の順番について

一般的には構文解析が先、意味解析が後になります。gccではエラーリカバリがよく行われていて、きっぱりと順番の説明がつくコードを作れませんでした。代わりに構文解析と意味解析の役割分担が現れるコードとそのコンパイルエラーについて説明します。

int main() {
  int void a;
  register auto int b;
}

$ gcc test3.c
test3.c: In function ‘main’:
test3.c:2:7: error: two or more data types in declaration specifiers
    2 |   int void a;
      |       ^~~~
test3.c:3:3: error: multiple storage classes in declaration specifiers
    3 |   register auto int b;
      |   ^~~~~~~~

C言語の構文解析レベルにおいては、宣言指定子列(JIS X3010:2003 「プログラム言語C」での用語に合わせます。以下同様)には、記憶域クラス指定子、型指定子、型修飾子、関数指定子を好きな順番でいくつも並べられます。しかし、int void a;やregister auto int b;のように、矛盾した宣言指定子が来ることがあります。これについて、構文解析レベルでは好きな順番で受け入れ、意味解析レベルでそれらが矛盾していないかをチェックする、という2段階の解析が行われます。このソースコードでは矛盾した宣言指定子を指定したため、意味解析でエラーが出ています。

アセンブリの生成

gccでは、-Sオプションを使うことでアセンブリを生成できます。意味解析が先で、アセンブリの生成はその後になります。

// test5.c
int func();
int main() {
  return func();
}

gcc -S test5.cとすると、test5.sというアセンブリファイルが生成されます。このファイルを見ると、func関数の呼び出しを行うcall命令が含まれていることがわかります。

 .file "test5.c"
    .text
    .globl    main
    .type main, @function
main:
.LFB0:
    .cfi_startproc
    pushq    %rbp
    .cfi_def_cfa_offset 16
    .cfi_offset 6, -16
    movq %rsp, %rbp
    .cfi_def_cfa_register 6
    movl $0, %eax
    call func@PLT // ここでfunc関数を呼び出しています。
    popq %rbp
    .cfi_def_cfa 7, 8
    ret
    .cfi_endproc
.LFE0:
    .size main, .-main
    .ident    "GCC: (GNU) 13.2.1 20230801"
    .section  .note.GNU-stack,"",@progbits

このアセンブリにはfunc関数の定義は含まれておらず、リンクがまだ行われていないこともわかります。

オブジェクトファイルの生成

gccでは、-cオプションを使うことでオブジェクトファイルを生成できます。アセンブリの生成が先で、オブジェクトファイルの生成はその後になります。

gcc -c test5.sとすると、test5.oというオブジェクトファイルが生成されます。このオブジェクトファイルは、アセンブリファイルをリンクすることで実行可能ファイルが生成されます。

生成されたtest5.oと、比較用に次のコードを入力したtest6.oを見てみます。無理やりテキストファイルとして開いてみてみると、test5.oにはmainとfuncという文字列が、test6.oにはfuncという文字列が含まれていることがわかります。ここから、オブジェクトファイルにはリンクするために必要な関数名などが含まれていることが推察できます。

// test6.c
int func() {
  return 42;
}

リンク

gcc test5.o test6.oとすると、実行可能ファイルa.outが生成されます。

試しにgcc test5.oやgcc test6.oとすると、次のようなエラーが出ます。gcc test5.oではfunc関数が見つからないというエラーが、gcc test6.oではmain関数が見つからないというエラーが出ます。これらから、リンクはプログラムを合わせることで、異なるファイルにある関数呼び出しやグローバル変数などを統合する処理だということがわかります。

$ gcc test5.o
/usr/bin/ld: test5.o: in function `main':
test5.c:(.text+0xa): undefined reference to `func'
collect2: error: ld returned 1 exit status

$ gcc test6.o
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/13.2.1/../../../../lib/Scrt1.o: in function `_start':
(.text+0x1b): undefined reference to `main'
collect2: error: ld returned 1 exit status

gccのコンパイルフェイズは、上記のような順番で行われると考えられます。

問 2: C言語のコンパイラを書く際に、最も難しいポイントはどこだと思いますか？考えたことや、これまでのプログラミング経験をもとに、具体的に教えてください。

普通の言語では字句解析->構文解析->意味解析の流れで独立して処理できますが、C言語では例外がいくつかあり、その点が難しいと思います。

プリプロセッシングと字句解析・構文解析の関係

問1ではプリプロセッシングは字句解析と構文解析の間に行われると書きましたが、単純に1方向にデータを流すだけでは上手く行かない例が考えられます。

// test7.c
#include /* */ <stdio.h>
int main() {
  printf("Hello, World!\n");
}

// test8.c
#include
<stdio.h>
int main() {
  printf("Hello, World!\n");
}

test8.c:1:9: error: #include expects "FILENAME" or <FILENAME>
    1 | #include
      |         ^
test8.c:2:1: error: expected identifier or ‘(’ before ‘<’ token
    2 | <stdio.h>
      | ^

test7.cは#includeと<stdio.h>の間にコメントがありますが、コンパイル可能です。しかし、test8.cは同じように#includeと<stdio.h>の間に改行がありますが、コンパイルエラーとなります。C言語の他の部分ではコメントや改行、空白はすべて字句解析で処理され、無視されます。しかし、前処理においてのみ、改行が意味のあるトークンとして扱われます。

これの回避策として思いつくのは、改行をトークンとする字句解析と、改行を読み飛ばす処理の2段階に分けて行うことです。1段階目の字句解析では、コメントや空白は除去しますが、改行はトークンとして残します。その後にプリプロセッシングを行います。更にその後に改行を読み飛ばす処理を行い、構文解析に移ります。このようにすることで、プリプロセッシングや構文解析をシンプルにしたまま、C言語の特殊な仕様に対応できると考えます。

構文解析と意味解析の関係

問1では構文解析の後に意味解析が行われるとかきましたが、これも単純に1方向にデータを流すだけでは上手く行かない例が考えられます。

typedef int A;
int f1() {
  int A;
  A++;
  A a; // Aは変数なので、aの前にセミコロンが必要だという構文解析のエラー
  a++;
}
int f2() {
  A a;
  a++;
  int A;
  A++;
}

$ gcc test4.c
test4.c: In function ‘f1’:
test4.c:5:4: error: expected ‘;’ before ‘a’
    5 |   A a; // Aは変数なので、aの前にセミコロンが必要だという構文解析のエラー
      |    ^~
      |    ;
test4.c:6:3: error: ‘a’ undeclared (first use in this function)
    6 |   a++;
      |   ^
test4.c:6:3: note: each undeclared identifier is reported only once for each function it appears in

関数f1ではint Aと変数を定義したことで、A aは変数Aと解釈され、構文解析のコンパイルエラーが発生します。しかし、関数f2ではA aはA型の変数aを定義すると解釈され、コンパイルは成功します。typedefを使ったコードでは、このように変数を定義したかどうかで構文が変わる自体が発生します。

これの回避策として思いつくのは、構文解析中において、変数を定義した箇所で変数名を記録するようにし、以後その変数名と同じ文字列を持った識別子が来たときに処理を変えるというものです。教科書通りの構文解析からは外れてしまいますが、この方法はコードに落とし込むとかなり簡便になり、実装方法として有効だと考えます。

このような仕様について、この課題を解く中で調べたところ、Ruby言語にも同じようなポイントがあることがわかりました。以下はirbでのRubyプログラムの実行結果です。a -bという形の構文では、aがローカル変数であればa - bという形の構文として、aが関数であればa(-b)という形の構文として解釈されます。

irb(main):001:0> a = 1
=> 1
irb(main):002:0> b = 2
=> 2
irb(main):003:0> a -b
=> -1
irb(main):004:0> def f(x) return x; end
=> :f
irb(main):005:0> f -b
=> -2

この構文の実装はおそらく、構文解析中にローカル変数を保存しておき、その変数名と同じ識別子が来たときに構文解析の処理を変えることで実現されていると考えられます。その根拠として、Rubyのローカル変数を動的に変更するメソッドの制約があります。Bindingクラスのlocal_variable_setというメソッドを見てみます( https://docs.ruby-lang.org/ja/latest/method/Binding/i/local_variable_set.html )。このメソッドは動的にローカル変数を定義しますが、これを実行した後にそのローカル変数を使おうとすると、NameErrorが出て使用できません。この仕様は、ローカル変数か関数かを構文解析時に決定していることから来ているものと考えられます。構文解析時に決定しているため、動的なローカル変数の定義に対応できず、NameErrorを出すようになっていると考えられます。

これらの教科書通りの言語処理系では上手く行かない箇所がC言語の難しいポイントだと考えます。

問 3: C言語のどこが不便だと思いますか？どのような機能があったらそれを便利にできますか？その機能はどうやったら実装できると思いますか？一つ選んで説明してください。

リストやハッシュマップなどを利用する際に、voidポインターを扱う点が不便だと思います。voidポインターを扱うことで型チェックが効かず、動的型付け言語以下の型付けになっており、バグの原因になりやすいです。改善策として、2つ思いつきました。

1つ目は、C++で採用されているように、テンプレートを導入することです。テンプレートを使うことで、これまでvoidポインターを扱うしかなかった部分を型チェックできるようになります。しかし、この方法はこの不便な点を解決するためには少しやりすぎとも考えます。テンプレートは型によって実装を分ける必要があり、影響範囲が大きくなってしまいます。テンプレートを導入した場合、ある関数にテンプレートを使うとなるとその関数をすべて再実装するような大掛かりなことになります。

2つ目は、テンプレートのような構文を使いますが、関数の戻り値の型を補足するに留めるものです。テンプレートのある関数を定義する際にはvoidポインターとして扱い、使用する際に型チェックを走らせます。これにより、既存のコードをそのままに、関数プロトタイプのみ書き換えることで型チェックを行います。アイデアとしてコードを下にかきました。

struct list<T>;
typedef struct list<T> list<T>;
list<T>* list_new<T>();
T*       list_pop<T>(list<T>*);
void     list_push<T>(list<T>*, T*);

int main() {
  list<double>* l = list_new()
  double* a = 12.3, b = 45.6;
  list_push(l, &a);
  list_push(l, &b);
  double *d = list_pop(l) // 成功
  int    *i = list_pop(l) // コンパイルエラーを出す
}

テンプレート型を持っておく必要のあるlist構造体と、そのテンプレート型をやり取りする必要のあるリストの各関数には、<T>というテンプレート(に似たもの)を指定しています。各関数でT型を扱う際には、全てポインターで扱う必要があります。もともとはvoidポインターだった部分を、T型のポインターに変更しているためです。また、ポインタとして扱うことで、テンプレートのように関数を型違いで複数定義する必要がなくなります。この方法であれば、既存のコードをそのままに、型チェックを行うことができます。

問 4: 今までで一番苦労したデバッグの話を教えてください。それがどのようなバグで、どのようなアプローチを取った結果解決したのか、そして結局なにがバグの原因だったのかを書いてください。

Rui UeyamaさんのCコンパイラ作成入門のテキストを読みながらCコンパイラを作っている際に遭遇したバグです。最初発見した際は、(ローカル)変数定義と条件分岐を組み合わせたやや複雑なコードをコンパイルすると、思っていたとおりの出力が得られないというものでした。最初の対処法として、条件分岐を減らし、対象のプログラムを簡単にしていきました。すると、変数2つと条件分岐が残りました。この段階では、①push/pop周りのアセンブリの生成で失敗しているか、②ローカル変数のスタック周りのアセンブリの生成で失敗しているか、③条件分岐あたりの構文解析で失敗しているか、この3つを中心にして疑っていました。

次に、生成されたアセンブリを読み込み、実際にどのような経緯で意図しない動作が発生しているのかを突き止めようとしました。この作成中のコンパイラでは、生成したアセンブリの中に過剰にpush/popが含まれています。なので、生成されたアセンブリの中から余計なpush/popを一つづつ手で取り除く作業を行いました。すると、1回目は取り除くのに失敗して動作が変わり、2回目で見た感じ問題のないアセンブリが生成されていることがわかりました。この時点で、もうコンピュータが壊れたのではないかと思い、一旦落ち着くために散歩に出かけました。

散歩から帰ってきて、バグが起きてるコードと、すでに成功しているテストを見比べてみました。すると、バグが起きているコードはローカル変数を2つ定義していることに加え、初めてそれらの変数に代入していることに気づきました。バグの起きているコードはローカル変数aとbを定義し、aに値を代入した後にbに値を代入した後、aとbの値を使用していました。ここで、さらにプログラムを簡単にしていくと、bに値を代入した後にaの値が0になっていることに気づきました。このことから、条件分岐は関係なく、ローカル変数の代入周りでバグが発生しているのではないかという結論になりました。

ここで当時のローカル変数の仕様を整理すると、ローカル変数はすべてint型で、スタックに1変数あたり4バイトの空間を確保するようにしていました。そして、値に代入する命令はmov [rax] rdiとしていました。Cコンパイラ作成入門のテキストを読み返したところ、この命令は8バイトの空間に値を代入する命令であることがわかりました。

つまり、変数aに4バイト、変数bに4バイトの空間を確保していたのに対し、変数bに対して8バイトの空間の代入命令を使っていました。そのため、変数bに値を代入する際に変数aの値が破壊され、変数aの値が0になっていたのです。そして、変数に代入する命令をmov [rax] rdiからmov [rax] ediに変更し、バグを解決しました。

問 5: 既存のプログラミング言語（マークアップ言語なども可）の仕様のうち、理不尽だと思うものを一つ選んでください。どうしてそのような仕様になってしまったのでしょうか？その理不尽さが発生しないようにするにはどのようにしておけばよかったのでしょうか、それとも本質的に解決不能なのでしょうか？歴史的経緯も含め、自分なりに調べて教えてください。

#include <stdio.h>
int main() {
  int a = 1;
  printf("%d %d %d\n", a++, a++, a++);
}

上記のコードをコンパイルした際に、gccでは3 2 1と表示されます。これは、C言語の関数呼び出しの仕様について、関数本体と関数の引数について、どの順番で処理するのかが定められていないことによります。この仕様は直感的ではなく、また他の言語でもこのような仕様は採用されていません。プログラムは前から実行していく流れが基本であり、関数呼び出しの仕様としても前から順番に評価されるのが自然だと考えます。

他の言語の関数呼び出しの副作用の例として、次のRubyのコードを考えます。このコードを実行すると1 2 3と出力されます。実際にRubyの規格書(JISX3017:2013「プログラム言語Ruby」)を読むと次のように書かれていて、関数呼び出しの引数は前から順番に評価されることが規定されています。

def func(a, b, c) puts "#{a} #{b} #{c}" end

a = 0
func((a += 1), (a += 1), (a += 1))

(《添字実引数リスト》について) プログラムテキストに現れる順に，《コマンド》，《演算子式リスト》の《演算子式》又は《連想リスト》を評価し，評価結果の値をLの末尾に追加する。 (JISX3017:2013「プログラム言語Ruby」p. 50)

C言語の規格書(JISX3010:2003「プログラム言語C」)を読むと、仕様として次のように書かれています。この仕様は、関数呼び出しの引数は評価順序が未規定であるとし、このような挙動が許容されていることを示しています。

関数指示子，実引数及び実引数内の部分式の評価順序は未規定とするが，実際に呼出しが行われる前に副作用完了点がある。 (JISX3010:2003「プログラム言語C」p. 52)

なぜこの仕様になっているのかを色々調べてみたのですが、その経緯は見つけられませんでした。ですが、探している際に見つけた仮説として、「関数の呼び出し時にスタックに積むときに有利」というものがありました。実際にSystem V ABI - Intel386 Architecture Processor Supplemenを読んでみると、引数はレジスタに加え、スタックフレームに積んでいることがわかりました。スタックフレームはHigh addressからLow addressの方向へ伸びていきますが、スタックフレームの引数は左側からLow addressからHigh addressの方向へ積まれています。これらを考えると、たしかに「関数の呼び出し時にスタックに積むときに有利」という仮説はある程度考えられると思います。

(追記)

この「関数の呼び出し時にスタックに積むときに有利」というのは、この課題について調べているときにTwitterで見つけた意見です。ABIを読んで関数呼び出しのスタックの作り方をみると、確かにそういう呼び出し順にすることで実装がやや簡単になりそうなのは分かったのですが、実際に何が原因でこうなっているのかまでは探し切れませんでした。ただ、調べてる中でSystem V ABIが読めるサイトを知り、コンパイラ作成に重要な説明がたくさん書いてあることに気づけたのは良い収穫でした。

問 6: 既存のプログラミング言語（マークアップ言語なども可）の仕様のうち、「世間一般で流布している説明には、厳密にいうと誤りが含まれている」というものを一つ選んで、それについてしっかりと丁寧に説明してください。ただし、「誤った説明が世間に流布している」という主張を支えるためには、互いに無関係な 4 種類以上の文献や教材においてその誤った説明がされていることを示してください（書籍・Web サイト・動画など幅広く OK としますが、講師が検証しやすいように、public なインターネットからアクセス可能なものの方がありがたいです）。そして、「厳密にいうと誤っている」という主張を支えるためには、「流布している説明に基づいたときに期待される挙動」と「実際に動かしてみて得られた挙動」の差を示すだけではなく、仕様を規定するドキュメントを読み込んだり、実装のソースコードを確認するなどして、「世間一般で流布している説明はこうであるが、この挙動を規定する仕様書や実装はこうであり、このような点で異なる」ということを丁寧に論証してください。

一方の「インタプリタ」はいわば「同時通訳者」、話し言葉を1文ずつリアルタイムに翻訳していくイメージです。プログラムを実行しながら、下図の赤枠部分のようにソースコードを1行ずつ機械語に変換します。

https://www.sejuku.net/blog/124720 「コンパイラとは？基礎知識やインタプリタとの違いをわかりやすく解説」侍エンジニア編集部

インタプリタ言語は、コードを実行する際に1行ずつ機械語に翻訳していく言語です。

https://qiita.com/tomokichi_ruby/items/73b0e7924a9f83fe45c6 「インタプリタ言語とコンパイラ言語」@tomokichi_ruby

インタプリター型言語のソースコードを、1行ずつオブジェクトコードに変換しながら実行するソフトウェア。 出典　ASCII.jpデジタル用語辞典

https://kotobank.jp/word/%E3%82%A4%E3%83%B3%E3%82%BF%E3%83%97%E3%83%AA%E3%82%BF%E3%83%BC-12389 コトバンク「インタプリタ」

インタプリタ（interpreter）は、コンピュータでプログラムを処理する方法の一つです。プログラムの実行時にソースコードを1行ずつ機械語プログラムに変換するプログラムのことでもあり、コードを読み込みながらその場で処理・実行していきます。

https://www.ntt-west.co.jp/business/glossary/words-00246.html NTT西日本 ICT用語集「インタプリタ」

これら4つの記事では、インタプリタの説明として、「ソースコードを1行づつ読み込み、機械語に変換しながら実行する」と説明されています。しかし、これは誤りです。

この説明を否定するためにいくつか仕様書を読んでみたのですが、はっきりと否定している箇所を見つけられませんでした。

(追記)

インタプリタを作ったことがあれば明らかに誤りだとわかるこれらの説明ですが、明確に誤りだとわかる仕様書は見つかりませんでした。この誤りを選んだ時にはRubyの仕様書を読めば書いてあるだろ！と意気込んでいたのですが、一通り読んでみた所インタプリタの仕組みについては全く書いてありませんでした。それも当然で、Rubyの仕様書はRubyの言語の仕様書であって、それをどう実行させるかについては書いてありません。

この問題を残したまま応募締め切りの日になってしまったため、この問題には明確に答えられないままとなりました。アフェリエイトブログの「調べてみましたが、分かりませんでした！」ってやつと同じですね。

(さらに追記)

JavaScript(ECMAScript)の企画書にはこれを否定する内容が書いてあるそうです。

また、実際のインタプリタ言語の実装を例にとって説明する手もあるそうです。ただ、インタプリタの実装を挙げるにしてもコードベースが膨大で、そこからコードを引用して説明するのもなかなか骨が折れそうです。

問 7: どのプログラミング言語を使って C 言語のコンパイラを実装する予定ですか？講師が予習するためにも、具体的に教えてください。

C言語で作成する予定です。セルフホストに挑戦したいです。

(追記)

自分はこの2年間Coq言語を中心に書いているので、Coq言語で書いてみたいと思ったのですが、流石に無理だと判断してC言語と答えました。C言語だとセルフホストという明確な目標が出来るので、その点でも良いのかなと思います。

問 8: これまでのプログラミング歴について好きなだけ語ってください。何か作ったものがあれば、それについても教えてください。また、何か他にアピールしたいことがあれば、それも自由に書いてください。

高校生の頃からプログラミング言語に興味があり、C言語やRuby、Schemeなどを触り、特にRubyについては標準ライブラリのドキュメントを何周もするなどしていました。

大学生になり、プログラミング言語を作る側に回ってみようと思い立ち、「Go言語でつくるインタプリタ」という本を読み、Go言語でyokan( https://github.com/soukouki/yokan )という言語を作ってみました。この言語は、四則演算や数値の大小比較、変数の代入と使用、関数定義と呼び出しをサポートしています。ループは再帰を、条件分岐はif関数(then節とelse節をラムダ式で渡す)を使うという、仕様を減らしてコード側で頑張るようなインタプリタを作成しました。実際にその言語上でfizzbuzzを書き、実行することができました。

学部1年の冬頃、Go言語でつくるインタプリタで得た知識をもとに、インタプリタを作成する勉強会を開催しました。baby-interpreter( https://github.com/soukouki/baby-interpreter )という、機能を意図的に削ったインタプリタを作成し、参加者に足りない機能を追加してもらう形式にしました。また、この勉強会の資料をもとに、技術書典に合同誌の1章として寄稿しました。

学部2年になり、大学の講義でCoq言語に出会いました。Coq言語はカリー・ハワード同型対応を利用した定理証明支援系であり、プログラムを書くことで数学の証明を書くことができ、型チェックをすることでその証明を検証することができます。私はこのCoq言語にドハマりし、Coqを書くことに没頭しました。2年の夏ごろに、クイックソートがソートできることの証明を書きました( https://github.com/soukouki/coq-quick_sort )。その後はCoqの勉強もかねて、松坂先生の「集合・位相入門」という数学書をもとに、Coqに集合論を形式化する取り組みを始めました( https://github.com/soukouki/mathlib のEnsemble以下)。3年になってからは毎日Coqに取り組むようになり、3年の夏にはCoqの標準ライブラリの証明を短くし、コントリビュートをしました( https://github.com/coq/coq/pull/17940 )。

3年の春休みには、今まで避けてきたCコンパイラの自作に挑戦しました。Rui Ueyamaさんの「低レイヤを知りたい人のためのCコンパイラ作成入門」をもとに、C言語でCコンパイラを作成しました( https://github.com/soukouki/10cc )。四則演算やif・while・forといった制御構文、関数定義に関数呼び出し、グローバル変数に文字列リテラル、構造体・列挙型にtypedefなどを実装しました。セルフホストを目標にしていたのですが、プリプロセッサの実装がなかなか思いつかず、途中で放置してしまいました。この課題をやる中で、字句解析・構文解析とプリプロセッサの関係がつかめてきたので、この後実装してみようと思っています。また、関数呼び出しで7つ以上の引数を渡したり、可変長引数の関数へもまだ対応していないので、これらについても挑戦していきたいと思っています。

セキュリティ・キャンプでCコンパイラ自作のコースに参加できたら、今度こそセルフホストを達成したいと思っています。前回のCコンパイラ自作でできたコードを書き直すなり、今回また新しくコードを作るなりして、前回の自作コンパイラの状況を超えたいと思っています。