{% include head.html %}

京都大学工学部専門科目「プログラミング言語処理系」講義資料

講義 Web ページはこちらです．

お知らせ

• 4月1日: 2025年度版ページにしました．

2024年度 講義予定

回	日付 (mm/dd)	内容（予定）	資料	その他
01	4/14	イントロダクション	1章: イントロダクション 2章: 概論的な話
02	04/21	インタプリタ 1	3.1: MiniML1 のシンタックスとセマンティックス 3.2: 各モジュールの機能 (1): Syntax, Eval, Environment, Cui 3.3: 各モジュールの機能 (2): Parser, Lexer
03	04/28	インタプリタ 2	3.4: MiniML2: 定義の導入
04	05/12	インタプリタ 3	3.5: MiniML3: 関数の導入 3.6: MiniML4: 再帰関数
05	05/19	型システム 1	4.1: 静的プログラム検証へのイントロダクション 4.2: MiniML2 のための型推論 (1): MiniML2 の型システム
06	05/26	型システム 2	4.3: MiniML2 のための型推論 (2): 型推論アルゴリズム 4.4: MiniML3,4 のための型推論 (1): Prelude
07	06/02	型システム 3	4.5: MiniML3,4 のための型推論 (2): 型の等式制約と単一化 4.6: MiniML3,4 のための型推論 (3): 型推論アルゴリズムの実装
08	06/09	型システム 4	4.7: 多相的 let の型推論
09	06/16	字句解析		（字句解析と構文解析パートの資料は PandA で配布する）
10	06/23	LL(1)構文解析
11	06/30	LR(0)構文解析
12	07/07	LR(0), SLR(1), LR(1)構文解析
13	07/14	コンパイラ 1	5.1: 能書き 5.2: ソース言語 MiniML4- と中間言語$\mathcal{C}$ 5.3: MiniML4- から$\mathcal{C}$への変換$\mathcal{I}$ 5.6: アセンブリ生成	5.4: MIPS アセンブリ言語入門 を事前に理解しておくこと
14	07/17	MinCaml コンパイラ概説		ソースコードをダウンロードして手元で試しておくとよい

レポート等の課題におけるLLMの使用について（履修者向け）

本科目におけるクイズやレポート等の課題においてLLMを使用する場合は、以下に注意してください。

• LLMを使用することを一律に禁止するものではありません。ただし、答案作成の過程で LLM を使用した場合は、その旨を明記した上で、答案に加えて (1) 使用した目的、(2) 使用したプロンプト、(3) 使用したモデル、(4) LLM からの出力、(5) それを踏まえてどのように自分の答案を作成したか、を明記してください。
• 実装課題において初めからから LLM にソースコードを生成させることは学習の効果を大きく下げてしまいます。LLM で正しいプログラムを作成させるためには、（少なくとも現状で普通にアクセスできる LLM においては）効果的なプロンプトを与え、生成されたプログラムの正しさを判断するために、ある程度の実装スキルが自身に必要です。将来 LLM をプログラム作成により効果的に使いこなすためにも、まずは自分でプログラムを書いてみることをお勧めします。

学習の仕方

以下の記述は履修者でない方々向けです。履修者には課題にとりくむためのリポジトリを作成して、そこで課題に取り組んでもらいますので、授業で指示するまで実装には手をつけないでおいてください。

• OCaml が使えるように環境を設定しましょう．
• 教科書を読みながらもりもり演習問題を解きましょう．
  • 教科書にバグを見つけたら issue で報告しましょう．
  • 講義の履修者は講義用 Slack で質問してもよいですね．
• プログラミング言語強者になりましょう．そのためには．．．
  • なにか自分で言語を作って処理系を作ってみましょう．作った処理系を自慢しましょう．世界中で自作の言語が使われるようになったらいいですね．
  • もしくは，プログラミング言語理論やプログラム検証を勉強してみましょう．たとえば以下の文献が参考になります。
    • Benjamin C. Pierce: Types and Programming Languages
      • 本講義で与えた型システムの理論的背景を学ぶための教科書。プログラミング言語の形式的意味論の導入から関数型言語
      • 和訳: 遠藤 侑介; 住井 英二郎; 酒井 政裕; 今井 敬吾; 黒木 裕介; 今井 宜洋; 才川 隆文; 今井 健男 訳: 型システム入門 : プログラミング言語と型の理論
    • Glynn Winskel: The Formal Semantics of Programming Languages---An Introduction
      • 本講義では自然言語でインフォーマルに与えているプログラミング言語の意味論を数学的に与え、プログラムの性質について厳密に議論する手法に関する教科書。
      • 和訳: 勝股 審也; 中澤 巧爾; 西村 進; 前田 敦司; 末永 幸平 訳: プログラミング言語の形式的意味論入門

目次

• OCaml の環境設定 - (講義スライド)
• OCaml あまり知らない人向け: 前提となる OCaml の知識を身に付ける．
  • OCaml 爆速入門 by 五十嵐淳
  • OCaml で二分探索木を書く by 五十嵐淳
  • この資料の「多相二分木 in OCaml」のところ
  • 高階関数 (OCamlに関するところのみ)
  • 多相性についてもう少し & 例外処理 (OCamlに関するところのみ)
• もう少しちゃんとした OCaml のテキスト: OCaml入門テキスト by 五十嵐淳
  • この PDF は五十嵐淳「プログラミング in OCaml～関数型プログラミングの基礎からGUI構築まで～」の元ネタになっている教材であり、出版社の好意で公開している。内容に古いところがある (OCaml が Objective Caml という古い名前で呼ばれている、五十嵐先生が知能情報学専攻にいる、環境設定が大昔の計算機科学コースシステム用になっている等）があしからず。
  • 1章は古くなっているので，2章から読むこと
• プログラミング言語処理系テキスト by 五十嵐淳，馬谷誠二，末永幸平
  • 1章: イントロダクション
  • 2章: 概論的な話
  • 3章: 型無し MiniML インタプリタの実装
    • 3.1: MiniML1 のシンタックス
    • 3.2: 各モジュールの機能 (1): Syntax, Eval, Environment, Cui
    • 3.3: 各モジュールの機能 (2): Parser, Lexer
    • 3.4: MiniML2: 定義の導入
    • 3.5: MiniML3: 関数の導入
    • 3.6: MiniML4: 再帰関数
    • 3.7: MiniML5 and beyond: やりこみのための演習問題
  • 4章: 型推論機能付き MiniML インタプリタの実装（あるいは，型システムを用いた形式検証の初歩）
    • 4.1: 静的プログラム検証へのイントロダクション
    • 4.2: MiniML2 のための型推論 (1): MiniML2 の型システム
    • 4.3: MiniML2 のための型推論 (2): 型推論アルゴリズム
    • 4.4: MiniML3,4 のための型推論 (1): Prelude
    • 4.5: MiniML3,4 のための型推論 (2): 型の等式制約と単一化
    • 4.6: MiniML3,4 のための型推論 (3): 型推論アルゴリズムの実装
    • 4.7: 多相的 let の型推論
    • 4.8: やりこみのための演習問題
  • 5章: MiniML コンパイラの実装
    • 5.1: 能書き
    • 5.2: ソース言語 MiniML4- と中間言語$\mathcal{C}$
    • 5.3: MiniML4- から$\mathcal{C}$への変換$\mathcal{I}$
    • 5.4: MIPS アセンブリ言語入門
    • 5.5: 仮想マシンコードとその生成
    • 5.6: アセンブリ生成
    • 5.7: $\mathcal{C}$の最適化（まだ）
    • 5.8: $\mathcal{V}$におけるデータフロー解析（まだ）
    • 5.9: レジスタ割り付け（まだ）
    • 5.10: 高階関数（まだ）
    • 5.11: 動的メモリ管理（やるの？）
    • 5.12: オブジェクト指向（やるの？）
    • 5.13: 分割コンパイルとリンカ（やるの？）
  • 6章: 字句解析と構文解析のためのアルゴリズム（まだ）
    • 7.1: 字句解析
    • 7.2: LL(1)アルゴリズム
    • 7.3: LR(0)アルゴリズム
    • 7.4: SLR(1), LR(1)アルゴリズム
  • 7章: さらに学びたい人のための参考文献
  • 8章: 参考文献
  • 付録: 問題リンク集

リンク集

• 実験3ホームページ
• 専門科目「プログラミング言語」ホームページ
  • の中の OCaml のページ（最低このくらいはわかってないとキツイ）
  • の中の OCaml で二分探索木を書くページ（これもわかってないとキツイ）
• OCaml の標準ライブラリの話を教科書に書いてあるので読んでおくととても良い違いない．

(F)AQ

この講義では毎週履修者からの質問やコメントを受け付けており，質問に対しては回答を次週までに書いて公開しているのですが，その中で他の学習者にとっても有用であると思われるものを(F)AQとしてまとめました．誤っている情報や追記すべき情報があれば Issue を立てたり PR を出したりしてもらえればと思います．

講義に関する情報

• 講義をする人: 末永幸平（@ksuenaga, Researchmap）
• 講義が行われる時間: 月曜2限
• 講義が行われる場所: 総合研究7号館講義室1
• Language used in the class: Japanese

ご寄付のお願い

本学学生以外の方で，もしこのページのマテリアルが有用であるとお思いになられたら，是非京都大学基金へのご寄付をいただけると幸いです．運営費交付金が年々削減される中で，大学教員が教育と研究活動を両立させつつ，学外の方々にも有用な情報を発信し続けられるよう，ご支援をいただけると大変ありがたく思います．京都大学へのご寄付に対しましては，法人税法，所得税法による税制上の優遇措置が受けられます．

特に以下の基金へのご寄付をいただけますと大変ありがたいです．

• 京都大学修学支援基金: 意欲と能力のある学生が経済的理由で修学・進学を断念することなく，希望する教育を受けられるようにすることを目的とした基金です．
• 男女共同参画支援たちばな基金: 男女共同参画支援を推進するための基金で，育児等支援の充実，保育施策の充実，男女共同参画推進事業の充実を目的とした基金です．
• 次世代白眉等若手研究者はぐくみ基金: 京都大学における、次世代の若手研究者の活動を支援するための基金です。
• 情報学研究科基金: 情報学研究科における大学院生の学修・研究支援，若手研究者支援，研究支援を目的とした基金です．