プログラミング言語を作る
プログラミング言語を作る系の授業「情報数理科学」メモ
第1講 関数型言語入門
新しいプログラミグ言語を作る授業
言語学みたいな授業
数学的に難しいことは出てこない
見慣れないだけである
Haskellを使う
GHCを使う
Haskellは圏論を知らないとわからない、や遅延評価なので純粋などは嘘
haskell.orgとsampou.orgが良い
普通は日本語の資料は間違っていると思った方が良い
GHCを使っている場合、ghciがインタプリタ
仮想機械：プログラムはVMの命令列に翻訳され、VM上で解釈実行される
haskellのインタプリタは:から始まるコマンドが隠れコマンド
:l プログラムを読み込み
:r 再読み込み
:q 終了
:!シェルコマンドの読み込み
関数の引数には原則かっこをつけない
if-then-elseを使い、elseは省略できない
ループはないので、再帰関数を使う
とにかく関数呼び出しから先に処理される
かっこを適切につけられる人は関数型言語を書き慣れている人
関数型言語のリストは配列とは全然違う
先頭への要素の追加しかできない
リストの条件分岐ではパターンマッチを使う
リストの要素は変更できない
関数型の = は気持ちとして、代入ではなく等式である
純粋関数型
関数は全て数学的な意味での部分関数、処理手順ではなく入出力関係を定義
値は全て数学的な対象、変更などはナンセンス
参照透明性
同じ計算は常に結果が同じ
関数型言語の厳密な定義はない
純粋関数型プログラミングを基礎とする言語とすれば良い
関数型：a->b
aが入力、bが入力の方
aが要素の型
原則として型が違うものに同じ関数・演算は使えない
複数の型に使える関数がある（多相性）
第2講 関数型言語2
先週の話を別の観点から説明し直す
関数型言語は関数を組み合わせてプログラムを各言語
インタプリタではletとinを省略してもなんとかなるが
普通はlet..inを使う
目標
Haskellの基本部分をちゃんと理解する
プログラミング言語の構成要素を知る(字句規則・構文規則・意味規則)
プログラミング言語の構成要素
・言語としての定義
構文規則 + 意味規則
・ソフトウェア的側面
言語処理系・ライブラリ
・文化的側面
コーディング規則・コミュニティ
構文規則は字句規則と構文規則に大別される
字句構造は単語ごとに分割するイメージ
構文構造はある種の木構造として解釈すること
小文字から始まる→変数名
大文字から始まる→データ構成子（コンストラクタとか）
演算子名か構成子名→演算子名とかデータ構成子
予約語
—から行末まで→コメント
数値や文字列にもルールがある
字句解析は構文解析に比べれば比較的自明である
例えば英語はスペースで切れば良い
この授業では字句構造の解析の話はスキップする
BNFによる算術しきの構文規則
BNFは言語と構文を大雑把に特定するための記法
BNFは構文木を表していると読むことができる
正確な意味は文脈自由文法
Expr
プログラム全体は式Expr
式を二つ並べると関数呼び出しになる
左辺がパターン1つだけなら変数、複数あれば関数の宣言
HaskellやPythonではインデントの深さによって構文構造が決まる（オフサイドルール）
オフサイドルールでは、
具象構文木と抽象構文木
BNFで特定される構文木には本質的でない要素が含まれる
BNFから文字通りに作られたものを具象構文木、本質的な情報のみにしたものを抽象構文木という
正しいプログラムであれば、letの次にinがくるのは当たり前なので消したりする
意味の定義の仕方は色々ある
・表示的意味
・操作的意味
・公理的意味
・翻訳による意味
・簡易意味(reduction semantics)
プログラムの意味を式変形を繰り返して理解する
これの計算は普通に数学の = だと考えれば良い
Haskellのようなプログラミング言語の規則はスライド1枚分ぐらいのもん
easyである
ただし、正確な意味は案外定義が難しいことや、実際のプログラムの挙動とは異なるというデメリットもある
プログラミング言語は字句規則・構文規則・意味規則で理解できる
構文規則の表現はBNF記法を使うと便利
意味の定義方法は色々ある
簡約意味だけでは実用上は問題があるので、これから新しい方法を紹介していく
第3講 高階関数・遅延評価
高階関数と遅延評価について
関数を繰り返して表現するのが関数型言語
C++では関数は一級市民ではない、というのも関数ポインタを使うことで関数を1級市民のように扱う
ポインタが1級市民である
関数でラップするというのが、ポインタなどを使わずに好き放題に関数を使える
関数型言語は高階関数ではないものを見つけるのが難しいぐらい高階関数を使う
多引数関数を1引数関数で表すことをカリー化という
カリー化された関数は部分適用ができる
ラムダ式
あちこちで関数を使うので無名の関数を使う
mapはリストの全要素に関数を適用
zipWith２つのリストをマージ
高階関数は計算パターンの抽象化に使える
foldrとscanlはよく使う
高階関数の意味を簡約で与えるのは簡単
変数捕獲に注意すれば特別な扱いは不要
等式による式変形という考え方は高階関数と相性が良い
高階関数の本質的な意味はあるのか？
→高階関数でプログラミングの様々な要素を表現できる
値は、それの使われ方であると考える
つまり真偽値 = 条件分岐のことであると考える
条件分岐で最初を選ぶのがtrueという定義をする
高階関数のみでチューリング完全
チャーチ・チューリングのテーゼ
関数型言語が高階関数を中心に考えてるのはこれが理由
ラムダ関数のみでチューリング完全ならばそれでプログラムを書けば良いじゃないか！
関数型言語では本質的には関数と変数は同じ
再帰変数をHaskellでは考えることもできる
x = 1:xは無限リスト
Haskellでは無限リストから値を取り出せる
必要ない計算をできれば避ける（遅延評価）
例えば、5個取り出すとしたら無限個生み出す必要がない
簡約の順序には注意が必要
まとめ
関数型言語では高階関数が花型
計算パターンの抽象化や無限リスト、プログラムの構成要素が表現できる
高階関数の意味も簡約なら明白
現実的なコンパイル方針はまた今後
ここまでで関数型言語の基本的な概念はほとんど終わった
第4講 意味論の基礎
ここから4,5回は意味論について
そこから4,5回はコンパイラ についてやる
普通簡約意味は適用しなくて、もっと現実的な意味を考える
Haskellに意味を与えるのは難しいので、今回は簡単な言語の意味を考えてウォームアップする
構文と意味は独立
意味論では自明なことを精密に記述する
意味規則では世界の違いを表すのに閉じかっこを使っている
数学の世界とプログラミングの世界は違う
意味規則の安全性と決定生
計算が有限の時間で停止する
任意の式に対して高々１種類しか存在しない（決定的）
これまでは簡単なプログラミング言語を定義した
次は変数というものを定義する
式を値に対応づけるため環境を用いる
環境に対する操作として定義域と拡張がある
環境を持つ判断ができるようになった
変数のスコープも同時に定義している
遅延評価の意味を真面目にやると論文になってしまうので遅延評価と無限リストは扱わない
意味を求めるときは構文構造がわかっていることが前提となる
いくつかの例題をやって理解を深める
今週は簡単なプログラミング言語を用いて意味を定義した
今週やった意味は自然意味などと呼ばれる
第5講 高階関数型言語の意味
Haskellの意味も前回と同様に与えられることを示す
Pythonなどの意味も同じように与えられる
目標としては、
高階関数の意味をどう与えるか、再帰関数の意味をどう与えるかという問題がある
再帰の意味を与えられるのであればループの意味も当然与えられる
高階関数型言語
条件分岐、無名関数が使用可能に
値の変更
真偽値は何てことないが関数値は真面目に考えないといけない
クロージャ
関数値=ラムダ式？
関数が変数と伴う以上、環境は必須であり、それをクロージャという
関数内で関数ローカルでない変数を許さなければクロージャは不要
ここでは条件分岐の意味規則と、関数の意味規則を導入する
作るルールと使うルールの２つを定義するのが基本である
ラムダ式を評価するとクロージャになる
再帰関数がうまく動作しないことの説明を例で示した
見た目は複雑になっているが、何も複雑なことはやっていない
最後に残ったのは再帰関数である
1 不動点演算子で再帰letを定義する
2 リカーシブクロージャーを導入
の２つがあり、後者の方が実際のプログラムに近いが、今回は1で定義する
fixラムダ式で定義できる
再帰letの導入のために言語拡張は不要である
ラムダ式があればなんでもできる（チューリング完全）
プログラミングオタクがラムダ式を崇拝するのは、最も簡単にチューリング完全な領域にたどり着くからである
ただし、実用上使えるかどうかは別の話である
要するに高階関数はとても強力である！！
今回定義した意味はプログラムの実行に使えるのか？
要するに、クロージャというのはコンパイラに使えるのか？という疑問が湧いてくる
クロージャ変換をすることでコンパイラに使える
関数値は関数本体へのポインタと環境が一緒になったデータ
クロージャ変換の意義
高階の言語を１階の言語で実現することを可能にする
評価規則の性質
今回の評価規則での評価結果は存在すれば１種類である
再帰関数が入ったので止まらない可能性はある
今回の評価規則での評価は簡単にスタック
まとめ
高階関数型言語の意味を与えた
関数はクロージャとして表現する
今回与えた意味には拡張性がある
第6講 型の基本
先週は高階関数型言語の意味を与えた
型を考えれば、前回考えたエラーの多くの部分を解決できる
型：プログラム断片の意味の見積もり
型も意味の一種なので意味と同様に調べる
プログラムの意味を大雑把に見積もったものである
どんなカテゴリーの返り値になるかを見積もるのが一般的
完全性と健全性
健全性：モデルで起こる→対象でも起こる
完全性：対象で起こる→モデルでも起こる
片付けは保守的
怪しいものは許さないという感じになっている
型付き言語の健全性
型エラーのないものはスタックしない（健全性）
片付け規則と評価に対する帰納法で証明する
再帰関数について
現状の型付け規則では不動点演算子fixには型がつかない
型チェックと型推論
型チェック：プログラムが型判定を満たすか調べること
型推論：プログラム断片に、型判定を満たす型を与えること
自動型チェック、自動型推論
第7講 多相型
多相性（ポリモーフィズム）
１つのプログラムが複数の型を扱うことができること
多相性は実用上非常に重要である
というのも、リアルワールドは汎用性があるものを望むからである
しかし、型つけの唯一性が問題となる
代入と単一化
型変数への代入を考える
let多相の限界
2種類の多相
パラメトリック多相
アドホック多相
型クラス
特定の型クラスを要求する関数を定義
型変数に型クラス制約を追加して集約
多相性とPrincipal Type
多相性を持つプログラム断片は複数の型で動作
最も一般的な型がないとその部分は正確な型を持てない
多相型言語の設計
実用的なプログラミング言語には多相性が必須
多相性のためには型の精緻な設計が必須
どう多相性を許すかは重要な言語デザイン
Curry-Howard対応
型付きプログラムと論理体系との対応
証明に対応させるためにはループを使ってはダメ
というのも、fixは証明できてはいけない式なので、再帰を本質的に含むプログラムはダメ
まとめ
今までのやり方はもっと複雑なものも扱える
複雑なものを入れると難しくなる部分もある
現実的な言語では言語機能の強力さ、理論的な取り扱いの良さ、プログラムの書きやすさのバランスが重要
第8講 モナド
モナドについて嘘情報に惑わされなくなる
３つのモナドを区別する
圏論におけるモナド
意味論におけるモナド
Haskellの機能としてのモナド
圏論の定義は意外と簡単
圏は型で、射は関数であると考えれば良い
圏論は様々な数学構造を統一的に扱うためのもの
モナドは群と呼ばれる代数構造の圏論的表現
具体的には半群
プログラミングの観点からは圏論を考えることの直接的な利益は少ない
圏論は、代数学の定理を微分積分額で使ったり、幾何学で使ったりするためのもの
数学の世界のテンプレートみたいなもの
圏論自体には意味がない
例えば、代数学に当てはめると半群になる、みたいに当てはめて使う
つまり、圏論はとある良い性質が成り立つプログラミング言語の性質について述べている
モナド則というものを満たしている
機能拡張を何回しても、出てくるものは１回の機能拡張で得られる程度であるというのが、プログラミングとして読み解いた時の内容である
ベースとなる関数型言語を圏とする
機能追加をファンクタで捉える
多くの機能追加はモナド則を満たす、モナドの性質を調べておけば良い
エラーはモナドに追加できるので大丈夫
意味論におけるモナド
関数型言語の意味は本講義でも議論した
少し機能を追加しても同様に意味は与えられる
→同様に、とは？
Haskellにおけるモナド
モナドは関数型言語への機能追加を統一的に記述できる
→関数型プログラムへの機能追加のための言語機能としてモナドを使える？
IOモナドについて
Haskellでは本質的な副作用にIOモナドを使う
まとめ
数学は知っておくと便利
プログラミング言語理論とプログラミング言語は相互に影響を受けて発展している
理論的な美しさと実用的な便利さはどちらも大事
関数型言語を用いて開発されているソフトウェアはあまり見たことがなくてソフトウェア開発においてはマイナーだと思うのですが、メジャーな言語ではなくHaskellなどの関数型言語はどういったソフトウェアを開発するときに利点があるのでしょうか
それともただ単に好みの問題で不人気ということなのでしょうか
→意外とある, Pythonは関数型言語的なものを取り入れている, 型なしの関数が多言語
型チェックにおいてかなりの部分のバグを減らすことができる
型付き関数型言語で開発できる人がいない
第9講 言語処理系1: 構文解析
ソースコード→構文解析器→抽象構文木→糖衣構文の展開→型推論・型チェック→中間表現→最適化→命令選択→レジスタ割り当て→コード生成→機械語
プログラミング言語の構成要素
-言語として定義
構文規則 + 意味規則
-ソフトウェア的側面
言語処理系・ライブラリ
-文化的側面
コーディング規則・コミュニティ
構文規則は字句規則と狭義構文規則に大別される
今週の目標として、構文解析を理解すること
文脈自由文法の構文解析
CYK法
実はCYK法は実用上使われていない
→実用的な構文解析の条件とは？
文脈自由文法が曖昧化田舎は決定不能である
決定可能：任意の入力に対し、常に正しい解答を有限時間内に返すアルゴリズムが存在する
正規言語ではできるが文脈自由文法では不可能な問題は多い
構文解析
定式化としては文脈自由文法はシンプルで協力
実用上は取り扱いが難しい
まとめ
文脈自由文法は導出木で意味が定まるO(n^3)
文脈自由文法は理論的には比較的シンプルで表現力も高い
文脈自由文法は実用上の取り扱いは難しい
第10講 言語処理系2 コンパイラの概要
木構造をコードまで落とし込むのがコンパイラとインタプリタである
コンパイラはいろんなことをやっている
インタプリタは、ソースコード→構文解析器→抽象構文木→評価→結果
インタプリタは簡単で、1日で実装できる
それに比べるとコンパイラは遥かに難しい
コンパイルはCPUができることへの翻訳
CPUができること
・レジスタ⇔メモリのデータのロード・ストア
・基本的な計算
・プログラムカウンタの操作
糖衣構文
書きやすさのため本質的な不要な構文
コンパイラにとっては冗長なので展開する
型と型チェック
型つけ規則に従って型推論・型チェックを行う
代表的な中間表現
コントロールフローグラフ
コントロールフローグラフは機械語での制御構造に対応
最適化
より効率の良いコードが出力できるように行う様々な処理の総称
命令選択
高レベルの中間表現は機械語では直接表現できない機能を使っている
その処理を実現する適切な機械語っぽい命令を出力すること
再帰関数の実装は簡単じゃない
ループやジャンプだけでは無理で、コールスタックを用いた実装を行う
変数などのメモリへの割付け
変数xを参照→スタックのmバイト目からnバイト読む
レジスタ割付け
実際のCPUのレジスタは有限なので、必要に応じて変数値をメモリに退避・メモリから復旧しなければならない
生存区間
レジスタ割付けには各変数が使われうる範囲を知る必要がある
頂点彩色によるレジスタ割付け
コード生成
最後に機械語を出力
実際にはコード生成に際して命令選択・最適化などを再度行うことが多い
まとめ
インタプリタはプログラムから値を求める
コンパイラはプログラムから機械語を生成する
コンパイラは様々な処理からできている
第11講 コンパイラによる最適化
近代的なコンパイラの主な仕事は最適化である
というのも現代のプログラムは人手で最適化できない
定数たたみ込み
定数伝播
共通部分式除去
部分冗長性除去
デッドコード除去
ループ最適化
演算子強度の低減
ループ展開
ループ融合
関数に関する最適化の重要性
末尾呼び出しの除去
アーキテクチャに依存した最適化
キャッシュメモリ
ブロック単位のアラインメント
アクセス局所性の向上
命令の並び替え
まとめ
コンパイラは様々な最適化を行っている
多くの最適化はトレードオフがある
第12講 メモリ管理とごみ集め
コンパイラはユーザが記述したプログラムに対応するコードのみを生成するわけではない
自動メモリ管理・自動ゴミ集め
目標
基本的なメモリ管理手法について学
手動のメモリ管理手法
完全に自前で管理
メモリ供給は自動、メモリ回収は自己責任
自動メモリ管理
自動メモリ管理の気にすべきこと
典型的なメモリ管理手法
・参照カウント法
・マーク・スイープ法
・コピー法
断片化
コンパクション
Haskell Community
Haskell環境構築
Stackでhello worldするまで
Lispのミニバージョンなら数千行で作られてた気がする
の中のminilispへGO
プログラミング言語作る、１時間で
自作プログラミング言語の集い
プログラミング言語を作る
「bash」