[S-8] 関数プログラミング

• 筑波大学 情報科学類 3年次実験（ソフトウェアサイエンス実験）
• 担当教員: 亀山幸義(kam[at]cs.tsukuba.ac.jp),
• 担当TA: 夏井，李 (jikken.fp[at]gmail.com)
• 時期と場所: 秋ABC, 座学・質問対応はMS Teamsのオンライン会議, 実作業を行う場所は自由
• 科目情報: 実験ホームページ

関数プログラミングの世界へようこそ!

「関数型プログラム言語」という言葉を聞いたことがありますか？ 「聞いたことがあるけど何だかわからない」、 「興味はあるけど難しそう」という印象の人はいませんか？

関数型プログラム言語を使えば、 C言語を使うよりもずっと、 美しく、 簡潔で、 わかりやすい プログラムを書くことができます。

実験S-8 は、一番広く使われている関数型言語である OCaml (オーキャムル, もともとは Objective Caml の省略だった)の入門講座です。 予備知識ゼロの状態から始めて、 プログラムを処理するプログラムである「インタープリタ」を、いとも簡単に書けるようになります。 実験後半では，「型検査器・型推論器」や「コンパイラ」などの 簡単なものも作成し，「プログラム言語の処理系」の作り方を修得します． これにより，将来，「自分の言語」を設計したときに， その処理系を比較的容易に作ることができるようになります．

C や Java 以外のプログラム言語，また，言語処理系に興味がある人は、 是非この実験にチャレンジしてください。

連絡事項

• テキストを更新して 2024年度版にしました。(2024/10/01)
• このページを設定しました。(2013/03/15)

実験の資料

• 実験概要
• 今年のスケジュールなどの情報
• 実験TA のページは、MS Teams内のExcelファイルに 引越しました。
• テキスト 以下に実験のテキストを示します。 間違いやわかりにくい点があれば、遠慮なく質問・指摘してください。
  (Credit) この実験のテキスト(以下のリンク先)は最初は亀山が作成したのですが、 その後、 海野広志先生 (2023年度まで筑波大学在籍)がコンパイラの部分などを大幅に改訂して くださったものです。また、 歴代のTeaching Assistantの人たちがテキスト改善に貢献してくれています。
  • 1. 準備
    • 1-1. 関数プログラミングとは
    • 1-2. OCaml を使うための準備
    • 1-3. OCamlでの関数プログラミング
  • 2. インタープリタの基礎
    • 2-1. ミニOCaml言語
    • 2-2. 内部データ構造と構文解析
    • 2-3. 数式の処理
    • 2-4. 真理値とif の処理
    • 2-5. 入れ子になった関数定義と高階関数
  • 3. 環境と束縛の処理
    • 3-1. 変数と let の前に: 環境の話
    • 3-2. 変数と let の処理の続き
  • 4. 構文解析器の利用
    • 4-1. 構文解析の話
  • 5. 関数の処理
    • 5-1. 束縛の話
    • 5-2. 関数の処理とクロージャ
    • 5-3. 再帰関数の処理
  • 6. インタープリタの拡張 (必須ではありません。)
    • 6-1. 様々な工夫と拡張
    • 6-2. リスト処理
    • 6-3. 継続渡し方式
  • 7. 型検査と型推論
    • 7-1. 型検査と型推論の概要
    • 7-2. 単純な式に対する型検査
    • 7-3. 変数の型付け含む型検査
    • 7-4. 関数に対する型検査
    • 7-5. 単純な式に対する型推論
    • 7-6. 単一化
    • 7-7. 一般的な型推論
  • 8. 簡単なコンパイラの作成
    • 8-1. 高級言語と抽象機械の話
    • 8-2. カテゴリカル抽象機械 (CAM)
    • 8-3. ミニOCamlからCAMへのコンパイル
    • 8-4. ZINC抽象機械 (ZAM)とZAMへのコンパイル
  • まとめ;
    • まとめと最終課題