ゼミ: Design Concepts in Programming Languages (Kickoff)
久野靖∗

2012.9.6□ Franklyn Turbak, David Gifford, Mark A. Sheldon, De-1.1

sign Concepts in Programming Languages, MIT Press,Programming Languages□ プログラミングは楽しい --- が、それは簡潔で明快な2008.

とき。ぐちゃぐちゃなコードで読みづらいと確信が持てず、楽しくない0□ プログラミング言語の設計はメタなプログラミング活動

Prefaceであり、普通のプログラムと同じくらい楽しい□ 6.821 Programming Languages (MIT の院における*• 言語の設計においては簡潔さと明快さが一層重要

入門レベル*の科目 (1 セメスター)• 今日では何百もの言語が使われている• プログラミングができ、数学ができることは前提• よいアプリケーション設計は新しい言語や既存言語の拡張とコミだったりする ← 柔軟かつ拡張可能な• 演習問題は実際に授業/試験で使用しているものが大半□ 目標:

アプリケーションは何らかのプログラミング機能を簡潔かつ厳密なフレームワークを学びそれに基提供する必要づいてプログラミング言語の設計と実装を理解□ 言語設計の要素は、通常のプログラミングにも存在• 実際の言語をあれこれ見るツーアはやらない• 例:• 代わりに構文的には類似した簡潔な教育用言語を題材にする• コレクションに対するイテレーションはどのようにカプセル化する?

• 今日は safety/security 重視 → それに関連する• これはプログラミング言語にどういうループ構造を概念を多く取り上げる入れるかということに類似した問題• それらの概念の現実のプログラミング言語への適用□ 本書の目標:についても機会があれば取り上げる

プログラミング言語における偉大なアイデア群を、簡潔なフレームワークの元で (複雑さをそぎ□ 構文は S 式を用いる ← 解析が容易で操作しやすい落として) 学ぶこと

• すべてを明示的にという我々の方針に合致• プログラミング言語の意味を規定する手法を複数学ぶ□ 「プログラミング言語は柔軟で表現力の高いメディアで• 規定が少し変わっただけでプログラムのふるまいが大きく変わることもあるある。コンピュータ科学の土台となるこのコンピューテションのキャンバスについて情熱を持って語りたい」

1

コレクションデータ構造のインタフェース設計• プログラミング言語設計空間の多くの次元について見て行く• 各次元にどのような選択肢があるかについてもIntroduction• それらの次元の選択肢どうしがどのように干渉し合□ 「整理と簡単化は対象理解の第 1 歩 --- 本当の的は未うかについても知。」(トーマス・マン、「魔の山」)• プログラミング言語に関するうまいやり方/拡張方法←とり消し可能な状態遷移、ループ脱出、パターンマッチなど• 我々のアプローチ:

言語のふるまいがより複雑になっている今日、そのふるまいの記述方法はより簡潔であるべきという信念∗ 筑波大学ビジネスサイエンス系

1

1.2

• 奇数が真、偶数が偽、+と*は∨と∧なら (T ∨ T) ∧F = F

Syntax, Semantics, and Pragmatics□ 伝統的にプログラミング言語は 3 つの側面から考えられ• 何の計算も表していなくて、ただそのような形だけて来たなのかも• Syntax (構文) --- 言語の形式• 何かのものをエンコードしているのかも• Semantics (意味) --- 言語の意味□ つまり、1 つのプログラムの句が多くの意味に対応させ• Pragmatics (実践) --- 言語の実装

1.2.1

得るSyntax

1.2.3□ 構文は言語のフレーズの具体的な記法を定める。

□ 意味は句が「何を」意味するかを定めるが、実装は「どうやって」その意味の計算をするかを定める• 例: v と w の積と、y を z で割ったものとの、和が欲しいとする。
• 伝統的な数式:• とくに関心事:

vw + y/z(+ (* v w) (/ y• 逆ドー

資源 (時間、空間、共有デバイスなど) の有効活用• Lisp のかっこつき前置記法:z))ポPragmatics

ラ• 例:

次の式木の評価/ン

電卓:[v][↑][w][↑][×][y][↑][z][↑][÷][＋]-+• スプレッドシートのフォーム• ツリーの図+*ab+a*/vwy23• a や b が何らかの数値を表すとすると、(+ a b) が2 回現れるので、素朴な方法だと同じ加算を 2 回やzることに• 別の方法として、加算は 1 回で、次に必要な時は前の値を参照• これらの記法は構文は違うが同じ句構造を表現□ プログラミング言語の構文:b「どのような文字の並び• 意味は変わらないが、資源の利用は変わっている (加算は減るが記憶場所が必要に)が正しく、正しい文字の並びがどのような句構造を表現しているか」を定める• どちらがよいかは時間や領域の貴重さによる• (* 2 3) が常に 6 になるので、何回もこれを評価す

1.2.2

Semantics

るなら最初から 6 にしておくのがいいかも□ 意味は句構造にその句構造がどのような意味を持つかを対応づける

1.3• どのような句にも「本来の」意味などない

Goals□ 本書の目標はプログラミング言語デザインのイディオム• 例:の包括的な集合についてその意味を探究すること*• さらにそれらをどう組み合わせて自立したプログラ+

ミング言語とできるか

10• さらに意味と実装の関連
111□ 構文については標準的なコンパイラの教科書が十分カ• 1、10 などが十進数値で+や*が和や積なら (1+11)・
10 = 120バー• →本書では最低限の本書で使うコンベンションだけ• *が指数なら 12 の 10 乗
• 数値が 2 進なら (1+3)・2 = 82□ 意味についてはその記述ツールを複数紹介し、それに基• 整数。例:

づいてさままなプログラミング言語の機能やそのバリ

17, 0, -3• 特別なコマンドトークン。add, div, eq, exec,gt, lt, mul, nget, pop, rem, sel, sub,エーションを理解

swap□ 実装については高レベルの部分だけ• 実行シーケンス。かっこで囲んだコマンド列。例:(2 (5 mul) exec add)。これで 1 つのコマンド。

• いくつかの基本的な実装手法やプログラム改良手法
程度まで□ 「(postfix 整数 コマンド…)」がプログラム。

□ プログラミング言語の機能を議論するに当たり、ミニ言語 (群) を対象• すべてのかっこは必要であり省略しない (本書の他の言語でも)• これらはそれぞれ既存の言語の特定側面を反映• とても小さい言語なので実用には向かないかも• しかし基本的な考え方は同じ。余分な複雑さがない 1.4.2 Semantics
ので検討が楽□ コマンドを左から右の順で実行• これらのミニ言語の機能を組み合わせることで現実• 各コマンドはスタック (最初は入力の整数を保持) をの言語に近くできる操作□ 意味と実装の問題はプログラミング言語の特性とその上• スタック中の値は (1) 整数、(2) 実行列のいずれかでの特定のプログラムについて考えるときに重要• 実行が終った時のスタックトップの値が出力値• エラーは (1) 最終スタックが空、(2) 最終スタックトップが整数でない、(3) コマンド実行時にスタック• さらに 2 つの基本的な実装戦略: 解釈実行と変換
実行の値が不適切、のいずれか• 解釈実行: ソース言語の表現 S を S のインタプリタが直接実行□ 各コマンドのふるまいは図 1.1• 変換実行: S をトランスレータでターゲット言語 Tに変換し、T のインタプリタで実行• P → v で P を実行した結果が v であることを表す• インタプリタ、トランスレータ (コンパイラ) は実装• P → error で P を実行した結果エラーになる〃

args
args

言語で書かれている• コマンドのエラーはスタック不足かスタックの値が不適切な場合• ソース言語、ターゲット言語には上述のようにミニ言語を使用• 以下ではコード中の { } はコメント• 実装言語については付録 A のメタ言語で記述□ 引数とプログラムの受け取る値の数が一致しないのも• でも、実際に動く実装も作ってみることをおすすめするエラー• 数値演算は後置記法で表現することになる□ メタプログラミング (プログラムを操作するプログラム• 比較演算子は 1(true)/0(false) を返すを書くこと) こそ最も魅惑的なプログラミングである!

□ スタック中の値を 2 回以上使うためには nget が利用で

1.4

きる

PostFix: A Simple Stack Language• index 値は 1 オリジンで、スタックが積まれると変□ 構文/意味/実装の例に PostFix という言語を使う

わる• 簡 単 な ス タック ベ ー ス の 言 語 ← PostScript,□ 実行列は 1 つの値としてスタックに積まれる

Forth• 実行列は exec によって呼び出され、サブルーチンのように動作• 以下はインフォーマルな説明 (厳密な話は後で各種ツールとともに)□ sel は真偽値 (1/0) に応じて 2 つの値から片方を選ぶ

1.4.1

Syntax□ PostFix の基本構文単位は「コマンド」。コマンドは以下の 3 種3

インフォーマルな記述の弱点• 11 章:型、well-typed□ ここまでのような英語と実例による記述は典型的なもの• 12 章:種別型のより進んだ機能:• まず構文が示され、それぞれの構成の意味が説明さ• 13 章:型 の 明 示 的 な 記 述 を 減 ら す (type1.4.3

れるreconstruction)

• 利点:
いる

多くのプログラマがこの方法で現に学んで• 14 章〜15 章:• 16 章:□ しかしインフォーマルな記述が不適切な場面も多くある• 例:

サブタイプ、多相、静的/動的セマンティクスの活用

effect system□ Paret IV: 実装

プログラム変換→変換によって意味が変わらな• 17 章:い保証?

コンパイラの例、18 章:

GC

言語がもつ性質を示したい (PostFix コード □ 形式的ツールを前面に出しているが、形式的ツールがすべてよいとは言わないは無限ループしない等)• 例:• ↑自然言語記述では厳密さが不足しているので証明の土台にならない• インフォーマルな説明が分かりやすいことも多い• 例:• 形式手法の土台にある概念は現実のプログラミング
言語を理解する上で貴重な道具だということは示し• 形式手法だと手におえなく面倒になることもある

機能を拡張したい→機能どうしの関係を把握• 例: 複数実装→それらが同じ言語を実装していることを保証したいたい□ インフォーマルな記述は厳密さが欠けていて、また長々しくなりがち• また、仕様不足 (すべてのケースをカバーし損なう)も起きやすい• また、仕様過多 (仕様に含まれているべきでないことまで記述) も• 例: PostFix はスタックで説明されるからといって、実装にスタックが無ければならないということはない• ↑より抽象的な定義方法により、実装の自由度があるのがよい

1.5

Overfiew of the Book

□ Part I の残りは上記のインフォーマルな記述の問題を克服するツール• 2 章:s-expression grammer ←文法は必要• 3 章:

操作的意味論 (operational semantics)• 4 章:

表示意味論 (denotational semantics)• 5 章:

再帰的な仕様の意味を決める方法• 使用するメタ言語 → 付録 A
□ Part II: 動的セマンティクス• 6 章:FL (ミニ言語) → 名前 (7 章)、状態 (8 章)、

制御 (9 章)、データ (10 章)、+プログラミングパラ
ダイム□ Part III: 静的セマンティクス

4