6c6c6c6c プログラミング言語処理系論 (2022年度)

プログラミング言語処理系論 (2022年度)

(東京大学大学院工学系研究科講義)

by 佐藤周行

この授業の目的

アルゴリズムを表現するためのプログラミング言語でかかれたプログラムを具体的なアーキテクチャに向けて最適なコードに変換することは、従来からコンピュータサイエンスの中心的な話題であったが、プログラミング言語の抽象度とアーキテクチャの複雑度の両方が飛躍的に増している現在、その重要度と問題の複雑度は飛躍的に増加している。

本講義では、プログラミング言語をどう設計するか、そこで表現する概念をどう実装するか、その時に処理効率をあげるにはどうしたらよいかを理解することを目標とする。

ごく簡単な（スクリプト）プログラミング言語の設計、実装、実行用VMの構築をスクラッチから行い、それを通しての説明を行うことをふくむ。

今年度の教材と具体的な目標は次のとおりとする。

Pythonのソースツリーを目の前にして迷子にならず、ソースコードの重要な部分を読む「あたり」をつけられるようにする
PyPyやRPythonをみて、VMの作りかたについての理解を深める
TypeScript等で使われている現代的な型システムとその生産性への貢献についての理解を深める

今回、大規模なプログラミング言語の実際とその標準化に関して、特別講義（1回）を予定する。

4/20 岩下英俊氏（JIS Fortran委員会委員長）

授業予定

授業導入とプログラミング言語概説(2回)4/6, 4/13
- 授業導入
- プログラミング言語概説
特別講義（岩下英俊 JIS Fotran委員会委員長）(1回) 4/20
プログラミング言語の定義の手法(3.5回) 4/27, 5/11, 5/18, 5/27
- プログラミング言語の定義の手法(1)
  1. プログラミング減とを定義するとは
  2. 文法の定義とその表現
  - ODC.pdf
  - サンプル言語処理系キット ODC
- プログラミング言語の定義の手法(2)
  1. シンボル解析
    - CPython
  2. Abstract Syntax TreeからSource Tree Traversalによる実行まで
  3. Type Check/型システム
  - TypeScriptの型システム (PDF)
- プログラミング言語の定義の手法(3)
  - 関数コールの実現と関係するさまざまな話題
    - GCC
    - Java
    - Python
- プログラミング言語の定義の手法(4)
  - コード生成
    - コンパイルの概念 (準同型、Futamura Projection)
    - コード生成の実際
    - PyPy
  - VM
    - ターゲットVM
VMと実行環境（2.5回）5/27, 6/8, 6/15
- VMの考え方とアーキテクチャ (JVM and CPython)
  - Stack machine (ISA)
  - Java VMの構成
- VMの考え方と具体的な設計 -- CPython, RPython, JIT Compiler
  - VMの生成
  - Internals of CPython
  - PyPy
    - RPython
    - JIT Compiler -- Metainterpreter
プログラム解析とプログラム最適化(3回) 6/22, 6/29, 7/6
- 最適化の考え方・ピープホール最適化
  - 最適化の考え方
  - 中間表現
  - Peephole最適化
  - Pythonのpeephole最適化ルーチンの解析
- 局所的な最適化、大域的な最適化
  - 局所的な最適化：Value Numbering
  - 大域的な最適化
    1. フローグラフとDominator
- データフロー方程式を用いた大域最適化とSSA
  - データフロー方程式とそれを用いた大域最適化
  - SSAとそれを用いた大域最適化
(進んだ話題(1回) 7/13)
- 正しさの保証
  - Secure Coding
  - Verified Computation/Validation
  - Practical Correctness

場所、日時

Zoom を使ったオンライン講義になります。 Zoomの情報は ITC-LMS に載っています。

毎週水曜日(2020/4/6 -- ) 10:25--

評価

提出したレポートによって評価します。

問題はここです。問題

問題集

全体講評

全体講評をここにおいておきます。