作成: 2025-11-15 17:48

インターンシップ

北陸先端科学技術大学院大学 計算理論研究室にインターンに行きました。

内容

事前課題

Haskellの種々の構文や概念、各種アルゴリズムやデータ構造の実装方法を学びました。

具体的には、

• 関数に付く型
• 再帰関数
• パターンマッチ
• リストの定義
• リストの結合
• リストを含む関数
• 挿入ソート、クイックソート、マージソート
• ラムダ関数
• 高階関数
  • Map
  • Filter
  • Partition
  • 畳み込み(左右)
• リスト内包表記
• 代数的データ型
  • 二分探索木
• 型クラス
• 型エイリアス
• I/O
• do記法
• Zip
• 順列
• N-queen problem

というような内容です。

実習

インターン1日目は、再帰を含む関数の性質の証明方法を習い、演習問題を解きました。英語で証明を書くのは初めてだったのですが、私程度でもなんとかなりました。

インターン2日目は、文脈、置換等といった項書換え系の概念を学び、演習問題を解きました。その後はこの記事に沿って実際に項書換え系のインタプリタを実装しはじめました。このときはreplace、positions、subtermAtなどといった関数を実装しました。

インターン3日目は、インタプリタの実装の続きを行いました。具体的には、パターンマッチングを行うための関数matchとその補助関数、代入のための関数substituteを実装しました。そして前日に作っていた関数と合わせた単一ステップの項書換えを行うrewrite、正規系まで項書換えを行うnf関数を実装しました。

インターン4日目は、項書換え系のファイル(.trs形式)を読み込み、定数mainの正規系を出力するプログラムを実装しました。そしてクイックソートを表したプログラム(qsort.trs)の実行に完了しました。その後はマージソート、挿入ソートを表したプログラムを実装しました。更に.trs形式ではなくて.fp形式で書き表されたファイルを読むパーサーが与えられたので、.fp形式で各種ソートを移植したほか、list関数を実装しました。

インターン5日目は、プログラム高速化のために、書き換え戦略を見直して、これまでsmall-step semanticsと呼ばれていたものを実装していましたが、big-stem semanticsと呼ばれているものに変更したものを実装しました。これでどれくらい早くなったかを確認するためにfibonacci数列のn項目を計算する関数なども書きました。

感想

やっぱり言語処理系というと大量のコードを書くことになるだろうということでプログラムを書く能力の低さが露呈するのではないかと危惧していましたが(更にOCamlを挫折したくらいしか関数型言語をやったことがなかった)、案外私が書いた行はコメントなどを除くと100行程度で評価器になっていて驚きました。まあパーサーの部分を書かずに配布されたやつを使うという感じだったので、そこを書くとなるともうちょっと書くことになりはしそうでしたが、その部分はそれぞれの制御文字列に対して似たような処理を何回も書く感じだったのでそこまで本質ではないのかもしれないと思いました。いや実際書くと難しいのかもしれませんが。構文解析って結構面白そうなアルゴリズムがあるっぽいので、そのうちちゃんと学びたいですね。

石川県らしくEIZOの4kモニターが与えられて大変作業しやすかったです。キーボードも持っていけばよかったなあ。

廣川教授には大変丁寧な指導を頂きました。ありがとうございました。

また学生募集係の中西様にも大変お世話になりました。ありがとうございました。

最終更新: 2025-11-20 02:07