プログラミング言語処理系論 (4) Design and Implementation of Programming Language Processors

(1)

プログラミング言語処理系論

(5)

Design and Implementation of

Programming Language Processors

佐藤周行

（情報基盤センター/電気系専攻融合情報学コース）

(2)

今日やること

 Parse Tree vs. Abstract Syntax Tree

 Perlの吐き出すコードの観察

 Source Tree Traversalによる実行

(eval)

 オブジェクトに関係するさまざまな話題

 抽象実行（Abstract Interpretation）

 Type/Class Check (Static/Dynamic)

 アクセスの許認可

(3)

文法要素以降の作業

High Level Concept

Syntax Design Semantics Design Parsing Ｓｅｍａｎｔｉｃ Analysis（Type/Class Check) Code Generation Execution Optimization Optimization Interpreter Compiler VM

(4)

Parse Treeの観察

 以下のコードと、パースに関するルールを考える while (i < 10) {r=r*i; i=i+1}

expr: … | WH '(' expr ')' expr {$$ = push(WHILE, $3, $5);} | condexpr | '{' compound '}’ {int x; x = $2; $$=push(LENV, x, 0);} condexpr: | expr LE expr

{$$ = push(LESS, $1, $3);} ...

compound: compound ';' expr

{$$ = push(COMPOUND, $1, $3);} | expr

(5)

Parseの生成するParse Tree

while (i < 10) {r=r*i; i=i+1}

LT VAR LIT VAR LIT expr expr LT condexpr LESS xxx xxx LENV xxx 0 COMPOUND xxx xxx WH expr expr expr WHILE xxx xxx

(6)

Parse Tree vs. Abstract Syntax Tree

 Parse Treeは一意に生成される必要がある（そうでないと、意味が一意に定まらない）

 …が、Parse Treeから生成される実行、またはコード生成のためのTree (Abstract Syntax

Tree)は自由に設計してよい

 前回話したASDLは、このAbstract Syntax Treeの記述言語です

 では、Perl5では、どのようなASTが生成されているのでしょうか

(7)

Perlの生成するコードを観察する。

sub factorial { $r = 1; while ($i>0) { $r = $r * $i; $i = $i-1; } return $r; } $i = 7; print factorial();

(8)

$ perl -MO=Concise,factorial,-src fact.pl main::factorial:

t <1> leavesub[1 ref] K/REFC,1 ->(end) - <@> lineseq KP ->t # 3: $r = 1; 1 <;> nextstate(main 1 fact.pl:3) v:{ ->2 4 <2> sassign vKS/2 ->5 2 <$> const[IV 1] s ->3 - <1> ex-rv2sv sKRM*/1 ->4 3 <#> gvsv[*r] s ->4 # 5: while ($i>0) { 5 <;> nextstate(main 3 fact.pl:5) v:{ ->6

(9)

o <2> leaveloop vKP/2 ->p

6 <{> enterloop(next->j last->o redo->7) v ->k - <1> null vK/1 ->o n <|> and(other->7) vK/1 ->o m <2> gt sK/2 ->n - <1> ex-rv2sv sK/1 ->l k <#> gvsv[*i] s ->l l <$> const[IV 0] s ->m - <@> lineseq vKP ->- # 6: $r = $r * $i; 7 <;> nextstate(main 1 fact.pl:6) v:{ ->8 c <2> sassign vKS/2 ->d

(10)

a <2> multiply[t6] sK/2 ->b - <1> ex-rv2sv sK/1 ->9 8 <#> gvsv[*r] s ->9 - <1> ex-rv2sv sK/1 ->a 9 <#> gvsv[*i] s ->a - <1> ex-rv2sv sKRM*/1 ->c b <#> gvsv[*r] s ->c # 7: $i = $i-1;

d <;> nextstate(main 1 fact.pl:7) v:{ ->e i <2> sassign vKS/2 ->j

g <2> subtract[t9] sK/2 ->h - <1> ex-rv2sv sK/1 ->f

(11)

e <#> gvsv[*i] s ->f f <$> const[IV 1] s ->g - <1> ex-rv2sv sKRM*/1 ->i h <#> gvsv[*i] s ->i j <0> unstack v ->k # 9: return $r; p <;> nextstate(main 3 fact.pl:9) v:{ ->q s <@> return K ->t q <0> pushmark s ->r - <1> ex-rv2sv sK/1 ->s r <#> gvsv[*r] s ->s

(12)

PerlのAbstract Syntax Tree

 Perlは、コードセグメントはほぼAST

 実行のための最小限のヒープ、スタックが用意されている

(13)

 Perlの実行について（課題５） PerlのB::Conciseモジュールを利用して、以下についてレポートせよ (1) 適当なプログラムに対してのソースとパース木の対応（-src）の観察 (2) 実行に際して必要となるデータ構造（スタック、フレーム、ヒープ）の特定(myによるローカル変数の扱いを観察すること) (3) ループ構造を必ず含むこと

(14)

その他大切なこと：パス

 Def. Pass  ソースプログラム(および中間生成物)を処理する一単位。  Def. One-Pass  パス一つ（パースを終了させるまで）でコード生成まで済ませる  Def. Multi-Pass  複数のパスから構成されるもの。一般的にはパースをした後で、解析（最適化等）をするパスを追加する

(15)

複数パスの表現

 ソースファイル中での表現

main(int ac, char **av) { if (ac >= 2){ if (!strcmp(*++av, "-d")) debug = 1; } code = yyparse(); if (!code) exit(1); nextPass(Entry); } Node *Entry; Top: … {Entry = …}; /* 最初か最後に、後々の処理のエントリーポイントを設定しておく */

(16)

パスの考え方

 近年の考え方では、パースまでと、パース以後の最適化をわけています。  パースまででできることは高が知れていると認識が一般的になりました。  最適化ルーチン  インタラクティブな言語では、パースまでの処理と、それ以後の処理（最適化等）のバランスが問題になっています。

(17)

プログラムの実行

 Source Tree Traversalによる実行

 Perl5はこの方式を取っています。

 直感的でわかりやすい

 簡単なものについてeval関数を書くことは straightforwardにできる。

 e.g. [ WHILE e st] = while [e] [st]  e.g. [x := e] = [x] := [e]

 [f(e1,e2, …, en)] = [f]([e1],[e2],…[en])

(18)

Source Tree Traversal

 ASTをそのまま実行  evalの構造を見てみる  構造を保ったまま変換することを一般的に homomorphism （準同型）と言う  式の評価については、準同型

 assignment, function call等、少数のものにつ

(19)

Source tree traversalに向けてさまざまな準備  コードの配置  関数定義の実体  データオブジェクトの配置  データセグメントを定義する  変数のハンドリング

 symbol table + (code/data segment)

 関数コールの設計

(20)

alternative

 コンパイラシステムの構築

 仮想マシンの設計（ISA決めないといけない）

 stack machine vs. register machine

 仮想マシン上のコンパイラ設計、コード生成

 仮想マシン上での実行

 変数の評価

 By name (スクリプト言語では特に)

(21)

Type Check and Class Check

 Typeとは何か？

 基本型（primitive types）と派生型（derived type）（導来型）

 int, float, double, bool as primitive types  As derived types,  Function type  Pointer type  Array type  Structure type  Union type

(22)

Type導入の目的

 Type導入の目的は2つ  プログラムが正しく動作するための情報  e.g. ポインタどうしの足し算をしてはいけない  プログラムが効率的に動作するための情報  プログラム内で＋が出てきたときに、int対象の＋か double対象の+かがわかると、効率的なコードが生成できる  特に関数呼び出しの時の静的型チェックが歴史的に重要視されてきた

(23)

Type Check

 変数、関数は型とともに宣言する

 型に関するルールを推論規則の形で書く e.g. a: point(int)  *a: int

f: (int, double)(int), i:int, d: double  f(i, d) : int

 プログラム中、推論規則を適用して、データ（式）の型を決めていく

(24)

図式として

 下の図式はCommuteするか？

Program

Type

Value

Compute (dynamic) Typing (static)

(25)

すすんだ話題

 式が、複数の型を持つと考えられることがある e.g. (lambda (x) x)  Polymorphic Typesにより、複数の型を持つことを表現することができる  現在、実用になっている（C++, Java, 多くの関数型言語）polymorphic type system

 ad hoc polymorphism

(26)

抽象実行

(Abstract Interpretation)

 Type checkのためのコードは、evalの簡略版として書くことができる  最初に変数宣言を強制するところでは、あらかじめ与えられた型との整合性をチェック  そうでなければ、一番「一般的な型」を想定してtype check 開始  CSでは、プログラム実行（動的）の前にプログラムの性質を解析することが重要なテーマの一つになっていた  Static Analysis

 Type Checkは、Static Analysisの重要な分野の

(27)

例えば

 eval([PLUS, e1, e2]) = [e1]+[e2]

に並行させて

 tychk([PLUS, e1, e2]) =

if (tychk(e1) == INT && tychk(e2)== INT)

INT;

(28)

Polymorphicな場合

 一番一般的な型（クラス）を最初に割り当て

 情報が増えるごとに具体化

 Milnerのアルゴリズム for predicative p-types

Robin Milner. A theory of type

polymorphism in programming. Journal of Computer and System Sciences,

17(3):348–375, 1978.

(世間の評判：本人、何やっていたか、当時絶対わか

っていなかった→この論文は読んでも無駄です)

 後々、unificationを援用したすっきりしたアルゴリズムにまとめられた

(29)

スクリプト言語では

 柔軟な表現を求める  1+2.0 くらいは書けるようにしてよ  “1.0” + 3.0 = 4.0 くらい書けるようにしてよ  動的にしか決まらない型は、動的にしかチェックできない  PerlのPMCや、PythonのNumberなど、計算時の型計算を許すものが

(30)

Objectとクラス

 クラスはオブジェクト指向での型に相当する  Structure type + access qualifier

 サブクラスを許すものが多い  Extends  サブクラスは、型の階層に自明でない構造を持ち込んだ重要な概念  抽象クラスを許すものがある  abstract  implements  methodの実体を後から定義する

(31)

Access Qualifier

 Private  Protected  Public  なんだかんだ言って、オブジェクトを導入しようとすると、GCその他、実行環境のサポートが大変なんだ…  「この言語にオブジェクトを導入しました」というブログの記事を簡単に信じてはいけません

(32)

環境と変数のバインディング

定義として  環境＝変数と値の結合の世界  変数が大域、局所とスコープが切られている場合変数の参照が何を指しているかを正しく表現することが必要

(33)

def fac(n) { my(r); r = 1; while (n>0) { r=r*n; n=n-1; } r = 10; n = 3; fac(5); r; n; X X

(34)

関数の出現

 Homomorphicな考えをサポートするため  この他には変数（シンボル）管理  関数の出現につれて考えなければならない問題  コードセグメントの管理  フレームの管理  ローカル変数、グローバル変数  スコープの管理  引数の渡し方

(35)

変数のバインディング

 関数コールについて考えるべきこと (a) 関数には引数をどう渡すのか？ (b) 引数が渡されると、変数名とデータの対応がどのように変更されるか。また、関数からリターンするとき、どのような処理が必要か？

(36)

フレーム

 関数実行の時に必要な局所的な情報を格納しておく場所を一般にフレーム (frame) といいます  フレームを一つ作ると、環境が変化します  関数呼び出しが終了したら、環境を復帰させなければなりません  Frameに含まれる情報には以下があります  Return address  引数のバインディング情報（特に実引数と仮引数の対応関係）  関数内のローカル変数のための領域

(37)

 局所的な環境は、任意の場所に現れるというのが現代的なプログラミング言語の常識  考え方はフレームと同じ  局所的な環境を定義するときに、変数と値の結合の仕方を改めて定義する  局所的な環境が「終了」したら、変数と値の結合を元にもどす

 source tree traversalでのやり方をまず見

(38)

バインディングの余談：

Call by **

 Call by Value  値を実引数として渡す (C)  ほとんどの現代的言語で実装される  JavaのreferenceやCのポインタをわたすのも実はCall by Value  Call by Reference  変数のアドレスを引数として渡す（Fortran, C++の一部機能）  Call by Name  変数が含まれる式を、呼び出しごとに評価する（現在ではごく少数）  Call by Keyword  パラメタに「名前」が付いている (Fortran)  実は、変数の評価についても同じことが言える  特にスクリプト言語では、Referenceが実行時にしか決まらないことがある（by Nameの必要性）  局所変数等、Referenceが静的にわかる場合はby Referenceを採用すべきである