Scalaで作るプログラミング言語処理系

(1)

Computation Models & Compiler on Scala

無線部開発班平成 28 年 7 月 28 日

(2)

第 1 章逆ポーランド電卓の実験

通常、数式は1 + 2などと中置記法で記す。演算子を後置して1 2 +と記す流儀を逆ポーランド記法と呼ぶ。

逆ポーランド記法は、プログラミング言語処理系の基礎たるスタック機械に対し、実に素直な命令列となる。

1.1 スタック機械の実装

スタックは、配列やキューと並ぶ代表的なデータ構造であり、要素をfirst-in last-outに管理する配列である。

ScalaではStackクラスで実装されている。pushメソッドで値を追加し、popメソッドで取り出し削除する。

stack.scala

val stack = new scala.collection.mutable.Stack[Int]

stack.push(3) stack.push(7)

assert(stack.pop == 7 && stack.size == 1) assert(stack.pop == 3 && stack.size == 0)

第2章でチューリング機械を実装するが、スタック機械は、テープをスタックに置換した計算模型と言える。

Fig. 1.1に模式図を示す。常にスタックの先頭を被演算子とし、n項演算なら先頭のn個を被演算子とする。

top

init

0

top

1 1

1

top

1 2

2

top

3 add

3

time

Fig. 1.1: addition operation 1 + 2 in a stack machine.

StackMachine.scala object StackMachine {

val stack = new scala.collection.mutable.Stack[Int]

def execStepOnce(code: String) = code match { case "+" => stack.update(0, stack(1) + stack.pop) case "-" => stack.update(0, stack(1) - stack.pop) case "*" => stack.update(0, stack(1) * stack.pop) case "/" => stack.update(0, stack(1) / stack.pop) case num => stack.push(num.toInt)

} }

execStepOnceメソッドで命令を実行する。命令が整数ならスタックに追加し、演算子なら演算を実行する。

StackMachine.scala

for (code <- Seq("1", "2", "+")) StackMachine.execStepOnce(code)

JavaやRubyの仮想機械もスタック機械である。ただし、Lua5やPerl6の仮想機械はレジスタ機械である。

(4)

1.2 中置記法からの翻訳

第1.2節では、中置記法から逆ポーランド記法へのコンパイラを実装する。手始めに字句解析器を実装する。

字句解析とは、数式を分割し、演算子と被演算子の列に変換する工程である。Tokenizerクラスに実装する。

Tokenizer.scala

class Tokenizer(expr: String) {

val tokens = "[0 -9]+|\\p{Punct}".r.findAllIn(expr).toList var cursor = Stream.from (0). iterator

def next() = tokens.lift(cursor.next).getOrElse(null) def back() = cursor = Stream.from(cursor.next -1). iterator }

数式の分割には、正規表現を利用する。字句解析で得られた演算子や被演算子を字句ないしトークンと呼ぶ。

test.scala

println((new Tokenizer("(1+20)*3 -40/5")). tokens.map(t => s"’$t’"))

tokensメソッドを呼び出せば、字句の列を得られる。下記は、(1+20)*3-40/5を字句解析した結果である。

List(’(’, ’1’, ’+’, ’20’, ’)’, ’*’, ’3’, ’-’, ’40’, ’/’, ’5’)

余談だが、有限状態機械が受理する語の集合を正規言語と呼び、正規言語を記述する手段が正規表現である。

次に実装する構文解析器は、字句の列を数式の文法に基づき解釈する。今回は再帰下降構文解析を採用する。

RecursiveDescentParser.scala

class RecursiveDescentParser(expr: String) { def parse = parseAdd(new Tokenizer(expr))

構文解析器では、演算子の優先順位を考慮して、演算子を探す。parseAddメソッドは、加減算を担当する。

def parseAdd(lex: Tokenizer): Seq[String] = { val buf = parseMul(lex).toBuffer

while(true) lex.next() match {

case "+" => buf ++= parseMul(lex) :+ "+"

case "-" => buf ++= parseMul(lex) :+ "-"

case _ => lex.back(); return buf.toList;

}

return buf.toList }

加減算の部分式を発見するたび、逆ポーランド記法に変換する。乗除算は、parseMulメソッドが担当する。

def parseMul(lex: Tokenizer): Seq[String] = { val buf = parseNum(lex).toBuffer

while(true) lex.next() match {

case "*" => buf ++= parseNum(lex) :+ "*"

case "/" => buf ++= parseNum(lex) :+ "/"

case _ => lex.back(); return buf.toList;

}

return buf.toList }

(5)

最後に定義するparseNumメソッドは、乗除算よりも優先順位が高い、括弧ないし数値単体の式を担当する。

def parseNum(lex: Tokenizer) = lex.next() match { case "(" =>

val inner = parseAdd(lex) assert(lex.next() == ")") inner

case num => Seq(num) }

}

parseメソッドを呼び出せば、逆ポーランド記法の命令列が得られるので、順番にスタック機械に投入する。

test.scala

(new RecursiveDescentParser("1+2*3")).parse.foreach(StackMachine.execStepOnce(_))

なお、Fig. 1.2は、スタック機械にベクタ画像を出力する機能を追加し、計算過程を視覚化した結果である。

top

init

0

top

1 1

1

top

1 2

2

top

1 2 10

10

3

top

1 20

mul

4

top

21 add

5

top

21 20

20

6

top

1 sub

7

time (a) 1 + 2×10−20.

top

init

0

top

1 1

1

top

1 2

2

top

3 add

3

top

3 10

10

4

top

3 10 20

20

5

top

3 -10

sub

6

top

-30 mul

7

time (b) (1 + 2)×(10−20).

Fig. 1.2: a visual stack machine.

例えば、視覚的なスタック機械は下記のSVGを出力する。或いは、JavaFXによるアニメ表示も良案である。

timeline.svg

</svg>

第1章の内容を応用すれば、言語処理系の自作も可能である。本格的な言語処理系は、第4章以降に述べる。

(6)

第 2 章チューリング機械の実験

計算可能な任意の問題には、それを計算するチューリング機械が存在する。これは計算模型のひとつであり、

有限状態機械と、無限長のテープと、テープを読み書きするヘッドで構成される。現実の計算機で例えれば、

有限状態機械はプロセッサに、テープはメモリに、ヘッドはメモリ番地に相当する。構成をFig. 2.1に示す。

I

0 0 0 1 1 1

Fig. 2.1: Turing machine.

TuringMachineクラスに実装する。コンストラクタには、有限状態機械の遷移表と、テープの初期値を渡す。

TuringMachine.scala

class TuringMachine(table: Map[(Char , Char), (Char , Char , Int)], init: Seq[Char]) { val tape = scala.collection.mutable.Map[Int , Char](Stream.from (0).zip(init):_*) var (head , state) = (0, ’I’)

while (state != ’F’) {

val (next , back , move) = table(state , tape.getOrElse(head , ’ ’)) tape(head) = back

state = next head += move }

}

状態遷移表は、現状態とテープの値を引数とし、次状態とテープに書き戻す値とヘッドの移動量を指示する。

これはノイマン型の計算機におけるプログラムに相当し、周辺装置との入出力は、テープを通じて実現する。

有限状態機械の初期状態はIに設定する。最終的に状態Fに遷移した時点で、チューリング機械は停止する。

2.1 自然数の後続の計算

現実の計算機とチューリング機械では、理論上の計算能力は同等とされる。自然数の後続を求める例を示す。

test.scala

val tm = new TuringMachine(Map(

(’I’, ’0’) -> (’a’, ’0’, +1), (’I’, ’1’) -> (’a’, ’1’, +1), (’a’, ’0’) -> (’a’, ’0’, +1), (’a’, ’1’) -> (’a’, ’1’, +1), (’a’, ’ ’) -> (’b’, ’ ’, -1), (’b’, ’0’) -> (’c’, ’1’, -1), (’b’, ’1’) -> (’b’, ’0’, -1), (’b’, ’ ’) -> (’F’, ’1’, +0), (’c’, ’0’) -> (’c’, ’0’, -1), (’c’, ’1’) -> (’c’, ’1’, -1), (’c’, ’ ’) -> (’F’, ’ ’, +1) ), Seq(’1’, ’0’, ’1’, ’1’))

(7)

第1章と同様に、ベクタ画像で視覚化を試みた。Fig. 2.2は、2進数11の次の整数100を求める様子である。

I

1 1

a

1 1

a

1 1

b

1 1

b

1 0

b

0 0

F

1 0 0

Fig. 2.2: increment from111to1000in a Turing machine.

状態aでビット列を右方向に走査しつつ終端を探し、終端に達したらビットを反転させて状態bに遷移する。

状態bはビット列を左方向に走査しつつ桁上げを行い、桁上げが終わると状態cに遷移し、左端に到達する。

2.2 ^{文脈自由言語の受理}

下記は、テープ上の記号列を走査して、言語{0ⁿ1ⁿ |n≥1}に適合すると停止するチューリング機械である。

言語{0ⁿ1ⁿ |n≥1}は文脈自由言語の例であり、正規表現では表記不可能である。詳細は第4章で紹介する。

test.scala

val tm2 = new TuringMachine(Map(

(’I’, ’0’) -> (’a’, ’0’, +1), (’I’, ’1’) -> (’I’, ’1’, +0), (’a’, ’0’) -> (’a’, ’0’, +1), (’a’, ’1’) -> (’b’, ’B’, -1), (’a’, ’ ’) -> (’a’, ’ ’, +0), (’b’, ’A’) -> (’b’, ’A’, -1), (’b’, ’B’) -> (’b’, ’B’, -1), (’b’, ’0’) -> (’c’, ’A’, +1), (’b’, ’ ’) -> (’b’, ’ ’, +0), (’c’, ’A’) -> (’c’, ’A’, +1), (’c’, ’B’) -> (’c’, ’B’, +1), (’c’, ’1’) -> (’b’, ’B’, -1), (’c’, ’ ’) -> (’d’, ’ ’, -1), (’d’, ’A’) -> (’d’, ’A’, -1), (’d’, ’B’) -> (’d’, ’B’, -1), (’d’, ’0’) -> (’d’, ’0’, +0), (’d’, ’ ’) -> (’F’, ’ ’, +1) ), Seq(’0’, ’0’, ’1’, ’1’))

状態aで記号列を右方向に走査し、記号1を発見するとBに書き換え、状態bに遷移して左方向に走査する。

以降は、テープ上を往復して、記号0はAに、記号1はBに書き換え、0と1が同数と判明すれば停止する。

(8)

第 3 章セルオートマトンの実験

第3章は、異色の計算模型として、セルオートマトンを紹介する。格子状に並ぶ有限状態機械で構成される。

Fig. 3.1のラングトンのループが著名で、僅か857通りの規則で自己を複製し、個体群を形成し、死滅する。

Fig. 3.1: Langton’s loops.

セルは、ある時刻における近傍セルの状態を観測し、遷移規則に従って、次の時刻における状態を決定する。

状態遷移はセル間で同期する。2次元の場合、各セルはFig. 3.2に示す通り、8個か4個のセルと隣接する。

(a) Moore’s (8 cells). (b) Neumann’s (4 cells).

Fig. 3.2: neighborhood cells.

隣接するセルを8個とする流儀をムーア近傍と呼び、隣接するセルを4個とする流儀をノイマン近傍と呼ぶ。

セルがk通りの状態を持つ場合、遷移規則はムーア近傍ならk⁸通り、ノイマン近傍ならk⁴通り存在しうる。

第3.2節で述べるライフゲームの場合、セルは生か死の状態を有し、近傍の個体密度に応じて状態遷移する。

誕生・生存 近傍に生きたセルが2個もしくは3個あれば、次の世代は生 過疎・過密 近傍に生きたセルが1個以下か4個以上なら、次の世代は死

現実のセルオートマトンでは、格子が有限なので、上下端や左右端を接続して円環面を設定する場合もある。^{トーラス}

(9)

3.1 セル空間の実装

第3.1節で定義するRuleクラスは、第3.2節や第3.3節で実装する各種のセルオートマトンの基本形である。

引数wとhはセル空間の規模を表し、statesは各セルの状態を保持する。updateメソッドで状態遷移する。

Rule.scala

abstract class Rule(val w: Int , val h: Int) { val states = Array.ofDim[Int](w, h)

val buffer = Array.ofDim[Int](w, h) def update() {

for(x <- 0 until w) { for(y <- 0 until h) {

buffer(x)(y) = nextAt(x, y) }

}

for(x <- 0 until w) { for(y <- 0 until h) {

states(x)(y) = buffer(x)(y) }

} }

抽象メソッドとして、nextAtメソッドを定義する。個別のセルの遷移規則は、nextAtメソッドで記述する。

Rule.scala

def nextAt(x: Int , y: Int): Int

本稿に掲載の実行結果は、下記のsvgメソッドで描画した。実装にはscala-xmlライブラリが必要である。

Rule.scala

def svg(u: Int = 8) = <svg xmlns=’http://www.w3.org /2000/ svg’> { for(x <- 0 until w; y <- 0 until h) yield <rect

x={(u * x).toString}

y={(u * y).toString}

width ={(u-1). toString}

height ={(u-1). toString}

fill={"#%06x".format(states(x)(y))}

/>

}</svg >

}

なお、マウスによる初期状態の入力やアニメ表示に対応するには、JavaFXのCanvasクラスが便利である。

Grid.scala

class Grid(rule: Rule , u: Double = 8) extends Canvas { val gc = getGraphicsContext2D ()

for(x <- 0 until rule.w; y <- 0 until rule.h) { val r = rule.states(x)(y) >> 16 & 0xFF

val g = rule.states(x)(y) >> 8 & 0xFF val b = rule.states(x)(y) >> 0 & 0xFF gc.setFill(Color.rgb(r, g, b))

gc.fillRect(u * x, u * y, u - 1, u - 1) }

}

ただし、Ruleクラスの仕様として、セルの状態は、赤と緑と青に8bitずつ割り当てたRGB色空間で表す。

(10)

3.2 生物集団の表現

Conway’s Game of Lifeとは、生物群集の増殖と死滅を簡素な遷移規則で表現したセルオートマトンである。

各セルは生物個体に相当し、ムーア近傍の個体群密度が適度な場合は生存し、過疎や過密の場合は死滅する。

誕生・生存 近傍に生きたセルが2個もしくは3個あれば、次の世代は生 過疎・過密 近傍に生きたセルが1個以下か4個以上なら、次の世代は死

Lifeクラスに実装する。Game of Lifeに限らず、次状態が近傍の値の総和に依存する場合、life-likeと呼ぶ。

Life.scala

class Life(w: Int , h: Int) extends Rule(w, h) { val (l, d) = (0xFFFF00 , 0x000000)

override def nextAt(x: Int , y: Int): Int = { var count = 0

def nx(off: Int) = (x + off + w) % w def ny(off: Int) = (y + off + h) % h count += states(nx(-1))(ny(-1)) / l count += states(nx( 0))(ny(-1)) / l count += states(nx(+1))(ny(-1)) / l count += states(nx(-1))(ny( 0)) / l count += states(nx(+1))(ny( 0)) / l count += states(nx(-1))(ny(+1)) / l count += states(nx( 0))(ny(+1)) / l count += states(nx(+1))(ny(+1)) / l if(count == 2) return states(x)(y) return if(count == 3) l else d }

}

遷移規則の単純さに反し、固定物体や移動物体など、実に多彩な模様を描く。Fig. 3.3は振動子の例である。

(a) pentadecathlon. (b) hertz oscillator.

Fig. 3.3: oscillator patterns.

ただし、各セルの初期状態は、配列statesを編集して設定する。Fig. 3.4は、時計の針に似た挙動を示す。

Fig. 3.4: clock patterns.

何れも周期4の振動子で、時計や回転花火と呼ばれる。Fig. 3.5はパルサーと銀河で、周期は3と8である。

(11)

(a) pulser. (b) galaxy.

Fig. 3.5: astronomical bodies.

固定物体や振動子は、外乱がなければ、永久に現状を維持する。これに対し、繁殖型は、際限なく増殖する。

繁殖型の例として、シュシュポッポ列車をFig. 3.6(a)に示す。煙を棚引かせ、蜂の巣などの固定物体を残す。

(a) puﬀer train. (b) glider gun.

Fig. 3.6: infinite growth pattern.

他にも、Fig. 3.6(b)のグライダー銃は、周期30でグライダーと呼ばれる移動物体を射出する繁殖型である。

3.3 論理回路の表現

第3.3節で紹介するワイヤワールドは、電子回路を模倣したセルオートマトンで、チューリング完全である。

Fig. 3.7(a)は、NAND素子の実装例である。左側に並ぶ発振器から電気信号が伝播し、論理積を出力する。

(a) NAND gate. (b) SR latch.

Fig. 3.7: logic circuit elements

Fig. 3.7(b)は、SRラッチの実装例である。下側の入力がセット端子で、上側の入力がリセット端子である。

黒のセルは絶縁体を、黄のセルは電導体を、赤と青のセルは電子の頭と尾を表す。Wireクラスで実装する。

(12)

Wire.scala

class Wire(w: Int , h: Int) extends Rule(w, h) { val (b, c) = (0x000000 , 0xFFFF00)

val (l, f) = (0xFF0000 , 0x0000FF)

override def nextAt(x: Int , y: Int): Int = { var count = 0

def nx(off: Int) = (x + off + w) % w def ny(off: Int) = (y + off + h) % h if(states(nx(-1))(ny(-1)) == l) count += 1 if(states(nx( 0))(ny(-1)) == l) count += 1 if(states(nx(+1))(ny(-1)) == l) count += 1 if(states(nx(-1))(ny( 0)) == l) count += 1 if(states(nx(+1))(ny( 0)) == l) count += 1 if(states(nx(-1))(ny(+1)) == l) count += 1 if(states(nx( 0))(ny(+1)) == l) count += 1 if(states(nx(+1))(ny(+1)) == l) count += 1 if(states(x)(y) == b) return b

if(states(x)(y) == l) return f if(states(x)(y) == f) return c

return if(count == 1 || count == 2) l else c }

}

絶縁体は、常にその状態を維持する。電導体は1個か2個の電子の頭が近傍にあれば、電子の頭に変化する。

また、電子の頭と尾は、次の時刻で電子の尾と電導体に変化する。これにより、電子は進行方向に移動する。

Schererは、論理回路の実装例を多岐にわたり紹介している¹。例えば、Fig. 3.8は、カウンタの実装である。

Fig. 3.8: binary counter.

Fig. 3.9は、直列加算器である。左側が入力で、右側が出力である。入出力とも最下位ビットを先頭とする。

Fig. 3.9: binary adder.

1http://karlscherer.com/Wireworld.html

(13)

第 4 章文脈自由文法と言語仕様

第4章からは、パーサーコンビネータを利用して、ラムダ計算を基礎とするプログラミング言語を自作する。

4.1 ^{バッカスナウア記法}

英字や数字など終端記号の有限集合Σを字母と呼び、Σに属する記号σを並べた文の集合Lを言語と呼ぶ。

L⊂Σ^∗={σ₁σ₂...|σ_k∈Σ}. (4.1)

形式的な文法を持つ言語を形式言語と呼び、正規言語と文脈自由言語と文脈依存言語と帰納可算言語がある。

第1章や第4章の言語は、文脈自由言語に属す。文脈自由言語を受理する機械をプッシュダウン機械と呼ぶ。

帰納可算言語や文脈依存言語は複雑で、チューリング機械や、その下位互換である線形拘束機械で受理する。

Pを生成規則の集合、Nを非終端記号の集合、Sを開始記号とすると、形式文法Gは式(4.2)で与えられる。

G= (N,Σ, P, S), P :N →(N∪Σ)^∗, S∈N. (4.2) 文脈自由言語では、生成規則は、非終端記号を非終端記号と終端記号の列に置換する。四則演算の例を示す。

数式 expr := add | mul | num 加算 add := num (’+’ | ’-’) num 乗算 mul := num (’*’ | ’/’) num 整数 num := [0-9]+

上記はBNF、即ちバッカスナウア記法の例でもあり、プログラミング言語の文法を定義する際に多用する。

A|B 選択 A B 連続

A+ 1回以上の出現 A* 0回以上の出現 A? 1回以下の出現

前掲の四則演算の定義では、任意個の項を扱えず、演算の優先順位も未定義なので、下記のように修正する。

数式 expr ::= add

加算 add ::= mul ((’+’ | ’-’) mul)*

乗算 mul ::= num ((’*’ | ’/’) num)*

整数 num := [0-9]+

構文解析はトップダウン構文解析とボトムアップ構文解析の2種類があり、再帰下降構文解析は前者に属す。

前者では、開始記号S=exprを起点に設定し、Pから適切な生成規則を選びながら、終端記号に到達する。

後者では、終端記号を起点に設定し、Pから適切な生成規則を選びながら、開始記号S=exprに到達する。

再帰下降構文解析は、生成規則を表す関数の相互再帰で構成され、実装が容易だが、左再帰に注意を要する。

(14)

加算 add ::= add ’+’ mul | mul

上記は左再帰の例で、再帰下降構文解析では無限再帰に陥る。文法から巧妙に左再帰を除去する必要がある。

4.2 自作する言語の仕様

favaは強い動的型付けを行う言語である。データ型は整数型、実数型、論理型、文字列型、関数型がある。

整数型 int ::= [0-9]+

実数型 real ::= [0-9]* ([0-9] ’.’ | ’.’ [0-9]) [0-9]*

論理型 bool ::= ’true’ | ’false’

文字列 str ::= ’"’ char* ’"’

関数型 func ::= ’(’ (id (’,’ id)*)? ’)’ ’=>’ expr

整数型は符号付き32bit整数値、実数型はIEEE 754 2進倍精度小数である。文字列はUTF-16で表現する。

favaの関数は無名関数だが、first-class functionでもある。例えば、関数の引数や返り値として指定できる。

favaは明示的な型変換を行う機能を持たないが、整数と実数との四則演算は、暗黙的に実数に変換される。

fava$ 0.1 + 234 234.1

favaの識別子は、当該箇所を包含し、同名の仮引数を有する、最も内側の関数の仮引数として解決される。

識別子 id ::= [$A-Z_a-z] [$0-9A-Z_a-z]*

favaのプログラムは単独のラムダ式である。繰り返し文や変数宣言、変数の再代入などの構文は排除する。

favaでは、式の意味と式の値は同義であり、部分式を同値な他の式に置換しても、式の意味は不変である。

ラムダ式 expr ::= cond | or

条件分岐 cond ::= or ’?’ expr ’:’ expr 論理積 or ::= and (’|’ and)*

論理和 and ::= eql (’&’ eql)*

等値比較 eql ::= rel ((’==’ | ’!=’) rel)*

順序比較 rel ::= add ((’<’ | ’>’ | ’<=’ | ’=>’) add)*

加減算 add ::= mul ((’+’ | ’-’) mul)*

乗除算 mul ::= unr ((’*’ | ’/’ | ’%’) unr)*

単項演算 unr ::= (’+’ | ’-’ | ’!’)* call

関数適用 call ::= fact (’(’ (expr (’,’ expr)*)? ’)’)*

式の要素 fact ::= func | atom | ’(’ expr ’)’

リテラル atom ::= int | real | bool | str | id

favaでは、式は作用的順序で評価され、演算子はcalled by valueである。部分評価や部分適用は禁止する。

favaの束縛変数は、それを引数とする関数への参照が生存する限り保存され、値を取り出すことができる。

fava$ ((x)=>((y)=>x*y))(2)(3) 6

自作言語で無名関数の再帰を嗜むことは、言語処理系を自作する醍醐味である。詳細は第5.2節で述べるが、

式(5.19)のZコンビネータをfavaで実装し、無名関数を引数に与えれば、無名関数を再帰的に呼び出せる。

(15)

第 5 章型なしラムダ計算の基礎

ラムダ計算はチューリング機械と等価な計算模型で、LISPやMLを始め、数多の言語の理論的基礎である。

式(5.1)はラムダ式で、関数f(x) = 7x³−5x²+ 3xを表す。関数f(x)を定義する作業をラムダ抽象と呼ぶ。

λx.7x³−5x²+ 3x. (5.1)

記号λはラムダ抽象の合図で、式λx.Eは、式E内の変数xを束縛する。多変数関数f(x, y)も定義できる。

式(5.2)の左辺は、右辺の高階関数と等価である。このように単変数関数で書き直す操作をカリー化と呼ぶ。

f =λxy.3x+ 7y=λx.λy.3x+ 7y. (5.2)

また、式(5.3)は、式(5.2)の関数fの値f(2,3)を与える。関数に引数の値を与える操作を関数適用と呼ぶ。

f(2,3) =λx.λy.3x+ 7y 2 3 = (((λx.λy.3x+ 7y) 2) 3) = ((λy.6 + 7y) 3) = 27. (5.3) 関数適用は左結合であり、引数xを2で置き換え、関数f(2, y)を得てから引数yを3で置換し、27を得る。

形式的には、式(5.4)の操作をベータ簡約と呼び、その左辺を、引数E₂に対する関数λx.E₁の適用と呼ぶ。

(λx.E1)E2−→

β E1|x:=E2. (5.4)

第4章で仕様を定義したfava言語は、ラムダ計算を実装する。下記のプログラムは、式(5.3)と等価である。

fava$ ((x)=>(y)=>3*x+7*y)(2)(3) 27

5.1 ^{チャーチ符号化}

ラムダ計算は、計算可能な任意の関数を表現する能力を持ち、論理演算をラムダ式で定義することもできる。

T =λxy.x, (5.5)

F =λxy.y, (5.6)

x∧y=λxy.xyF, (5.7)

x∨y=λxy.xT y. (5.8)

式(5.5)(5.6)は真と偽の定義例である。演算子は、式(5.7)(5.8)で定義する。正当性はfavaでも確認できる。

fava$ ((x)=>(y)=>x(y)((x)=>(y)=>y))((x)=>(y)=>x)((x)=>(y)=>y)(1)(0) 0

fava$ ((x)=>(y)=>x((x)=>(y)=>x)(y))((x)=>(y)=>x)((x)=>(y)=>y)(1)(0) 1

以上の表現をチャーチ論理値と呼ぶ。同様に、自然数の体系もペアノの公理に基づきチャーチ数で表現する。

0 =λf x.x, (5.9)

1 =λf x.(f x), (5.10)

2 =λf x.f(f x). (5.11)

(16)

例えば、自然数と自然数の加算と乗算は、式(5.12)(5.13)で定義する。これも正当性はfavaで確認できる。

a+b=λab.λf x.af(bf x), (5.12)

a×b=λab.λf x.a(bf)x. (5.13)

fava$ ((a)=>(b)=>(f)=>(x)=>a(f)(b(f)(x)))((f)=>(x)=>f(x))((f)=>(x)=>f(f(x)))((x)=>x+1)(0) 3

fava$ ((a)=>(b)=>(f)=>(x)=>a(b(f))(x))((f)=>(x)=>f(f(x)))((f)=>(x)=>f(f(x)))((x)=>x+1)(0) 4

5.2 無名関数の再帰

ラムダ計算には再帰関数を定義する規則はないが、不動点コンビネータを利用すれば再帰関数を表現できる。

関数f(x)に対しp=f(p)となる点pを不動点と呼び、pを求める高階関数gを不動点コンビネータと呼ぶ。

g(f) =f(g(f)). (5.14)

関数h(x)を、関数fが変数として出現する式Eと不動点コンビネータgにより、式(5.15)の通り定義する。

h(x) =gλf.λx.E. (5.15)

式(5.14)より式(5.16)が導出される。式Eの中の変数fは、関数h(x)により束縛される。

h(x) = (λf.λx.E)(gλf.λx.E) = (λf.λx.E)(h(x)) =λx.E|f:=h(x). (5.16)

式(5.16)は、関数h(x)が引数f を通じて関数h(x)を参照することを意味し、関数h(x)は再帰関数となる。

関数gの候補は星の数ほど存在するが、特に有名な例として、Haskell CurryのYコンビネータを紹介する。

y=λf.(λx.f(xx))(λx.f(xx)). (5.17)

関数hに対し、式(5.17)のYコンビネータが式(5.14)の性質を満たすことは、式(5.18)により明らかである。

yh−→

β (λx.h(xx))(λx.h(xx))−→

β h((λx.h(xx))(λx.h(xx))) =h(yh). (5.18) 下記は、favaによるYコンビネータの利用例だが、call by valueを原則とする言語では、無限再帰に陥る。

fava$ ((f)=>((x)=>f(x(x)))((x)=>f(x(x))))((f)=>(n)=>(n==0)?1:n*f(n-1))(10)

call by valueでは、式(5.18)のyhを無限にh(yh)に展開する。式(5.17)にイータ変換を施せば回避できる。

z=λf.(λx.f(λy.xxy))(λx.f(λy.xxy)). (5.19)

なお、式(5.20)で、式Eに変数xが未束縛で出現しない場合、ラムダ抽象を外す操作をイータ変換と呼ぶ。

λx.Ex−→

η E. (5.20)

式(5.20)の操作を許容する場合、任意の引数xに対し同値関係にある関数fとgは外延的に同値と言える。

f x=gx→λx.f x=λx.gx−→

η f =g. (5.21)

下記は、favaによるZコンビネータの利用例である。再帰的アルゴリズムで10の階乗を計算し、停止する。

fava$ ((f)=>((x)=>f((y)=>x(x)(y)))((x)=>f((y)=>x(x)(y))))((f)=>(n)=>(n==0)?1:n*f(n-1))(10) 3628800

(17)

第 6 章仮想的な実行環境の設計

第6章では、ラムダ計算は忘却の彼方に放逐し、自作言語favaの実行環境となるスタック機械を設計する。

VirtualMachineは、スタックとプログラムカウンタpcを持ち、pcが示す位置の命令を逐次的に実行する。

fava.scala

object VirtualMachine {

def exec(codes: Seq[Code]) = { val stack = new Stack() var pc = 0

while(pc < codes.size) {

pc = codes(pc).exec(stack , pc) }

stack.pop }

}

基本的な仕組みは第1.1節のスタック機械と同じだが、条件分岐や関数適用に対応するための命令を備える。

命令は下記のCodeトレイトを継承し、スタックとpcを引数に演算を行い、次に実行する命令の位置を返す。

fava.scala trait Code {

def exec(stack: Stack , pc: Int): Int }

第6章では、ScalaのAny型をA、Int型をI、Double型をD、Boolean型をB、String型をSと表記する。

fava.scala

import scala.{Any=>A,Int=>I,Double=>D,Boolean=>B}

6.1 演算命令と定数

favaのスタック機械では、命令の種類を可能な限り削減するため、算術演算や論理演算は、2項演算に限る。

例えば、-1や!aなどの単項演算は、0-1やa^trueに変換される。2項演算の命令はBinクラスを継承する。

fava.scala

abstract class Bin(op: String) extends Code { def exec(stack: Stack , pc: Int): Int = {

val val2 = stack.pop val val1 = stack.pop

stack.push(apply(val1 , val2)) pc + 1

}

def apply(a: Any , b: Any): Any

def error(a: Any , b: Any) = new ScriptException(s"$a ${op} $b") }

(18)

2項演算命令は、スタックの上端の2値を取り出し、演算結果をスタックに戻す。加算命令の実装例を示す。

fava.scala

case class Add() extends Bin("+") {

def apply(a: Any , b: Any): Any = (a, b) match { case (val1: I, val2: I) => val1 + val2

case (val1: I, val2: D) => val1 + val2 case (val1: D, val2: I) => val1 + val2 case (val1: D, val2: D) => val1 + val2 case (val1: A, val2: A) => "" + val1 + val2 }

}

他の算術論理演算命令も、例えば減算と乗算と除算と剰余も、同様に実装する。論理積と論理和も実装する。

fava.scala

case class And() extends Bin("&") {

def apply(a: Any , b: Any): Any = (a, b) match { case (val1: B, val2: B) => val1 && val2 case (val1: A, val2: A) => throw error(a, b) }

}

また、算術比較命令を実装する必要がある。算術比較命令は不等号に相当し、左辺と右辺の大小を比較する。

fava.scala

case class Gt() extends Bin(">") {

def apply(a: Any , b: Any): Any = (a, b) match { case (val1: I, val2: I) => val1 > val2

case (val1: I, val2: D) => val1 > val2 case (val1: D, val2: I) => val1 > val2 case (val1: D, val2: D) => val1 > val2 case (val1: S, val2: S) => val1 > val2 case (val1: A, val2: A) => throw error(a, b) }

}

最後に、等値比較命令を実装する。等値比較は、関数型を除き等値性を比較し、関数型のみ参照を比較する。

fava.scala

case class Eq() extends Bin("==") { def apply(a: Any , b: Any): Any = a == b }

なお、演算子を伴わない定数式は、即値をスタックに積む命令に翻訳する。下記のPushクラスに実装する。

fava.scala

case class Push(value: Any) extends Code { def exec(stack: Stack , pc: Int): Int = {

stack.push(value) pc + 1

} }

第1.1節で実装したスタック機械で言えば、単なる数値がこれに該当し、広くロード命令として分類される。

(19)

6.2 条件分岐と関数

制御構造は、下記のJmp命令とJmpf命令で実現する。Jmp命令は、pcを操作して、指定の位置に移動する。

fava.scala

case class Jmp(offset: Int) extends Code { def exec(stack: Stack , pc: Int) = pc + offset }

Jmpf命令は条件分岐命令で、スタックの上端の値を取り去り、その値がfalseなら指定の位置に移動する。

fava.scala

case class Jmpf(offset: Int) extends Code {

def exec(stack: Stack , pc: Int) = pc + (if(stack.popAs[B]) 1 else offset) }

関数適用は、関数の定義位置へのジャンプにより実現するが、引数へのアクセス手段も提供する必要がある。

call data stack

1

^st

argument 2

^nd

argument

closure

call stack

environment

push a closure and arguments

data stack

return to

call stack

environment environment

create a new environment

Fig. 6.1: function call with arguments 3 and 4.

Fig. 6.1に示す通り、関数の引数は関数適用の直前にスタックに積まれ、関数適用と同時に環境に格納する。

環境Envとは、仮引数と実引数の対応表であり、引数は番号で管理する。環境Envは、再帰的な構造を持つ。

環境は関数定義の入れ子構造と対応しており、enclosureは、外側に定義された関数の環境への参照である。

fava.scala

class Env(args: Seq[Any], enclosure: Env = null) { def get(nest: Int , id: Int): Any = nest match {

case n if n >= 1 => enclosure.get(n - 1, id) case n if n == 0 => args(id)

} }

favaのラムダ式が変数を参照したら、Load命令により、指定された番号の引数を複製し、スタックに積む。

fava.scala

case class Load(nest: Int , id: Int) extends Code { def exec(stack: Stack , pc: Int): Int = {

stack.push(stack.env.get(nest , id)) pc + 1

} }

では、関数適用の命令Callを実装する。指定の個数の値をスタックから取り去り、Envをスタックに積む。

(20)

fava.scala

case class Call(argc: Int) extends Code { def exec(stack: Stack , pc: Int): Int = {

val args = stack.popN(argc) val func = stack.popAs[Closure]

stack.push(pc + 1)

stack.push(new Env(args , func.enclosure)) func.from

} }

Closureはfavaの関数型の実装であり、fromが関数の定義位置である。enclosureについては、後述する。

fava.scala

case class Closure(from: Int , enclosure: Env)

関数の実行が終わると、以前の場所に戻り、後続の命令を実行する必要がある。これはRet命令で実現する。

Fig. 6.1のように、戻り先retはスタックに待避してある。Ret命令は、環境を廃棄して以前の場所に戻る。

fava.scala

case class Ret() extends Code {

def exec(stack: Stack , pc: Int): Int = { stack.swap

stack.ret

stack.popAs[Int]

} }

favaの関数に出現する自由変数は、関数定義が評価された時点での値を記憶する。これを関数閉包と呼ぶ。

クロージャとも呼ばれ、favaがカリー化に対応する根拠となる。関数閉包は、Func命令により生成される。

fava.scala

case class Func(length: Int) extends Code { def exec(stack: Stack , pc: Int): Int = {

stack.push(Closure(pc + 1, stack.env)) pc + length

} }

Func命令はJmp命令を兼ねる。その位置を起点に関数閉包を生成すると、関数定義の直後にジャンプする。

最後に、スタックを実装する。環境の操作を効率化するため、環境のスタックと演算のスタックを分離した。

fava.scala class Stack {

val callStack = collection.mutable.Stack[Env]() val dataStack = collection.mutable.Stack[Any]() def push(frame: Env) = callStack.push(frame) def push(value: Any) = dataStack.push(value) def popN(n: Int) = 1.to(n).map(_=>pop).reverse def popAs[Type]: Type = pop.asInstanceOf[Type]

def swap = Seq(1,2).map(_=>pop).foreach(push(_)) def env = callStack.applyOrElse(0,(_:Int)=>null) def pop = dataStack.pop

def ret = callStack.pop }

(21)

第 7 章言語処理系の完成と拡張

第7章では、構文解析器と抽象構文木とコード生成器を実装してコンパイラを構成し、対話環境に連接する。

対話環境はread-eval-print-loopとも呼ばれ、対話的にコマンドを読み取り、実行する。以下に実装例を示す。

fava.scala

def main(args: Array[String]) {

val console = new scala.tools.jline.console.ConsoleReader console.setExpandEvents(false)

console.setPrompt(s"${Console.BLUE}fava$$ ${Console.RESET}") while(true) try {

val code = Parser.parse(console.readLine).code(Func(null)) println(s"${Console.CYAN}${VirtualMachine.exec(code)}") } catch {

case ex: Exception => println(Console.RED + ex.getMessage) }

}

完成した処理系は、LGPLのもとGitリポジトリで頒布している。紙面の都合で省略した部分も閲覧できる。

$ git clone http://git.pafelog.net/fava

$ java -jar fava/build/libs/fava.jar fava$

読み取りにはJLineを利用し、履歴機能を持たせた。また、構文ミスや実行時エラーは、赤文字で警告する。

7.1 ^{抽象構文木の実装}

抽象構文木とは、構文解析の結果を書き下した木構造である。下記は、(1+2)*(10-20)の抽象構文木である。

Mul(*,Add(+,Lit(1),Lit(2)),Add(-,Lit(10),Lit(20)))

抽象構文木はコード生成器を兼ね、下記の命令列に変換される。識別子の解決は、抽象構文木の段階で行う。

List(Push(1), Push(2), Add(), Push(10), Push(20), Sub(), Mul())

全ての抽象構文木は、必ず下記のExprトレイトを継承する。命令列への変換は、codeメソッドに実装する。

fava.scala trait Expr {

def code(implicit env: Func): Seq[Code]

}

暗黙の引数envには、その式を包む最も内側の関数を渡す。まずは、定数に対応するLitクラスを実装する。

fava.scala

case class Lit(value: Any) extends Expr {

def code(implicit env: Func) = Seq(is.Push(value)) }

(22)

下記のAddは、2項演算の抽象構文木の例である。被演算子の命令列を展開し、直後に演算命令を挿入する。

fava.scala

case class Add(op: String , e1: Expr , e2: Expr) extends Expr { def code(implicit env: Func): Seq[Code] = op match {

case "+" => e1.code ++ e2.code :+ is.Add() case "-" => e1.code ++ e2.code :+ is.Sub() }

}

下記のUnaryは、単項演算の抽象構文木である。被演算子を補足して、2項演算に変換する点が特徴である。

fava.scala

case class Unary(op: String , expr: Expr) extends Expr { def code(implicit env: Func): Seq[Code] = op match {

case "+" => is.Push(0) +: expr.code :+ is.Add() case "-" => is.Push(0) +: expr.code :+ is.Sub() case "!" => expr.code :+ is.Push(true) :+ is.Xor() }

}

例えば、式-123を読み込むと、下記の命令列を生成する。論理否定も、排他的論理和を利用して実装する。

List(Push(0), Push(123), Sub())

下記のIfは、条件分岐の抽象構文木である。第6.1節で実装したJmp命令とJmpf命令は、ここで使用する。

fava.scala

case class If(cond: Expr , val1: Expr , val2: Expr) extends Expr { def code(implicit env: Func): Seq[Code] = {

val code1 = val1.code val code2 = val2.code

val jump1 = is.Jmpf(2 + code1.size) +: code1 val jump2 = is.Jmp (1 + code2.size) +: code2 cond.code ++ jump1 ++ jump2

} }

例えば、式3.14>3?"big":"small"は、下記の命令列に展開する。分岐命令が、不要な式の評価を防止する。

List(Push(3.14), Push(3), Gt(), Jmpf(3), Push(big), Jmp(2), Push(small))

下記のIdは、識別子を表現する。環境を辿り、該当する仮引数を探索し、発見すればLoad命令を発行する。

最外部の環境まで遡っても該当の仮引数が存在しない場合は、例外を発生して、対話環境に警告を表示する。

fava.scala

case class Id(ident: String) extends Expr { def find(implicit env: Func): is.Load = {

val idx = env.pars.indexOf(ident) if(idx >= 0) return is.Load(0, idx) if(env.enclosure != null) return {

val out = find(env.enclosure) is.Load(out.nest + 1, out.id) }

throw new ScriptException(s"$ident?") }

def code(implicit env: Func) = Seq(find) }

(23)

下記のCallは、関数適用を表す抽象構文木である。関数と実引数を命令列に変換し、Call命令を挿入する。

fava.scala

case class Call(func: Expr , args: Seq[Expr]) extends Expr { def code(implicit env: Func): Seq[Code] = {

val vals = args.map(_.code).fold(Seq())(_++_) func.code ++ vals :+ is.Call(args.size) }

}

下記のFuncは、関数定義を表現する。Func命令を先頭に、関数の内容を挟み、最後にRet命令を挿入する。

fava.scala

case class Func(body: Expr , pars: Seq[String] = Seq()) extends Expr { var enclosure: Func = null

def code(implicit env: Func): Seq[Code] = { this.enclosure = env

val contents = body.code(this)

is.Func(1 + contents.size + 1) +: contents :+ is.Ret() }

}

enclosureは、外側の関数への参照である。codeメソッドの引数envを記憶し、識別子の解決に役立てる。

7.2 構文解析器の実装

第1.2節では、再帰下降構文解析を手書きで実装したが、パーサーコンビネータがあれば簡単に実装できる。

生成規則を表現する関数を高階関数で結合し、構文解析器とする。式を与えると、抽象構文木が生成される。

fava.scala

object Parser extends scala.util.parsing.combinator.JavaTokenParsers { def parse(str: String): Expr = parseAll(expr , str) match {

case Success(ast , _) => ast

case Failure(msg , _) => throw new ScriptException(s"error: $msg") case Error (msg , _) => throw new ScriptException(s"fatal: $msg") }

def expr: Parser[Expr] = cond|or

def cond = (or <~"?")~expr~(":"~>expr )^^{case c~y~n => If(c, y, n)}

def or = chainl1(and , "|"^^(op => (Or (_: Expr , _: Expr )))) def and = chainl1(eql , "&"^^(op => (And(_: Expr , _: Expr ))))

def eql = chainl1(rel , ("=="|"!=") ^^(op => (Eql(op, _: Expr , _: Expr )))) def rel = chainl1(add , (">="|"<="|">"|"<")^^(op => (Rel(op, _: Expr , _: Expr )))) def add = chainl1(mul , ("+"|"-") ^^(op => (Add(op, _: Expr , _: Expr )))) def mul = chainl1(unr , ("*"|"/"|"%") ^^(op => (Mul(op, _: Expr , _: Expr )))) def unr = rep("+"|"-"|"!")~call^^{case ops~e => ops.foldRight(e)(Unary(_,_))}

def call = fact~rep(args )^^{case f~a => a.foldLeft(f)(Call(_,_))}

def args = "("~>repsep(expr , ",")<~")"

def func = pars~"=>"~expr^^{case p~_~e => Func(e, p)}

def pars = "("~>repsep(name , ",")<~")"^^(_.map(_.ident)) def bool = ("true"|"false")^^(b => Lit(b.toBoolean))

def real = """(\d+\.\d*|\d*\.\d+)""".r^^(d => Lit(d.toDouble)) def int = """\d+""".r^^(i => Lit(i.toInt))

def str = stringLiteral ^^(s => Lit(s.tail.init)) def name = ident^^(Id(_))

}

(24)

利用方法は、Scala公式のAPI仕様書に詳しい。終端記号を正規表現で記述でき、字句解析器は不要である。

7.3 ^{遅延評価への変更}

次式をcall by valueで評価すると、関数適用の直前に、式1+2の値3と式3+4の値7がスタックに積まれる。

fava$ ((x,y)=>x*y)(1+2,3+4) 21

上記の式をcall by nameで評価すると、式1+2と式3+4の値は、関数内で参照した際に初めて計算される。

これは非正格評価とも呼ばれる。call by valueでも、高階関数を利用することで、同等の挙動を再現できる。

fava$ ((x,y)=>x()*y())(()=>1+2,()=>3+4) 21

実引数の評価を遅延する目的で利用される関数閉包をサンクと呼び、引数の値を計算する操作を強制と呼ぶ。

ただし、引数を参照する度に評価する上記の実装は、同じ引数を何度も参照する場合には、非効率的である。

fava$ ((x)=>x()*x())(()=>3+3) 36

実引数を評価した際に、その値を環境に登録して、評価の回数を抑制する非正格評価をcall by needと呼ぶ。

第7.3節ではcall by nameを実装する。まずIdクラスを改修し、Load命令の直後にCall命令を挿入する。

fava.scala

case class LazyId(ident: String) extends Expr { def code(implicit env: Func): Seq[Code] = {

Seq(Id(ident).find , is.Call (0)) }

}

同様に、関数適用のCallクラスも改修する。関数定義のFuncクラスを利用して、実引数を関数定義で包む。

fava.scala

case class LazyCall(func: Expr , args: Seq[Expr]) extends Expr { def code(implicit env: Func): Seq[Code] = {

Call(func , args.map(Func(_))). code }

}

第7章の構文解析器を改修して、Call命令をLazyCall命令に、構文木Idを構文木LazyIdに置き換える。

fava.scala

def call = fact~rep(args )^^{case f~a => a.foldLeft(f)(LazyCall(_,_))}

def name = ident^^( LazyId(_))

実行環境に手を加える必要はない。試しに、式((x)=>x)(3.14)をコンパイルすると、下記の命令列を得る。

List(Func(4), Load(0,0), Call(0), Ret(), Func(3), Push(3.14), Ret(), Call(1))

僅かな改修でfavaの評価戦略はcall by nameに移行する。式(5.17)のYコンビネータの評価も停止する。

fava$ ((f)=>((x)=>f(x(x)))((x)=>f(x(x))))((f)=>(n)=>(n==0)?1:n*f(n-1))(10) 3628800

(25)

第 8 章ガベージコレクタの実験

関数適用は、引数の数だけ多くのメモリ領域を消費する。関数適用が終了すれば、メモリ領域は解放できる。

だが、下記の高階関数では、外側の関数が終了しても、内側の関数は束縛変数x= 2を参照する必要がある。

fava$ ((x)=>((y)=>x*y))(2)(3)

第8章で実装するガベージコレクタは、変数のメモリを解放しても良いか、自動的に判断する仕組みである。

自作せずともJavaの高性能なガベージコレクタの恩恵に与れるが、折角なのでC⁺⁺で簡単に再現してみる。

8.1 計数型の実装

C⁺⁺11のshared_ptr<>はreference countと呼ばれるガベージコレクタの実装である。Fig. 8.1に図示する。

Fig. 8.1: reference-counting garbage collector.

オブジェクトは個別に参照カウンタを持ち、被参照数が増減した際に、直ちに参照カウンタの値に反映する。

参照の増減を監視する機構が必要だが、C⁺⁺の場合は、コンストラクタやデストラクタを用いて実現できる。

count.cpp

template<typename T>

shared_ptr <T>:: shared_ptr(T *ptr): ptr(ptr) { count[ptr]++;

}

template<typename T>

shared_ptr <T>::~ shared_ptr() { if(!--count[ptr]) delete ptr;

}

countは大域的な配列であり、shared_ptrの生成と破棄により、指定のポインタに対応する値が増減する。

使用例を以下に示す。1行目で確保したメモリはptr1とptr2で共有されるが、6行目でptr2が脱落する。

count.cpp

shared_ptr <int> ptr1(new int);

{

shared_ptr <int> ptr2 = ptr1;

*ptr2 = 114514;

}

std::cout << *ptr1 << std::endl;

reference countは、オブジェクトが不要になると迅速に解放できるが、循環参照を解放できない難点がある。

(26)

8.2 走査型の実装

Fig. 8.2のmark and sweepは、第8.1節のreference countと並び、主要なガベージコレクタの手法である。

Fig. 8.2: mark-and-sweep garbage collector.

まず、スタックを起点に参照を辿り、巡回したオブジェクトに生存の印を付ける。この操作をマークと呼ぶ。

次に、ヒープ領域を走査し、生存の印が付いていないオブジェクトを削除する。この操作をスイープと呼ぶ。

第8.1節のreference countと比べ、停止時間が長くなるが、循環参照を回収できる。では、実装してみよう。

noah.hpp

#include <cstdlib >

#include <vector >

namespace noah {

void* alloc(size_t size);

void clean(void *from , void *last);

};

上記のnoah::alloc関数はstdlibのmallocに相当し、noah::clean関数はmark and sweepを実行する。

次に、noah::alloc関数で割り当てたポインタの範囲と生存の印を管理するための構造体Headを定義する。

noah.cpp

namespace noah { struct Head {

bool marked;

void *from;

void *last;

};

構造体Headはnoah::alloc関数を呼び出す度にベクタに追加する。include宣言は紙面の都合で省略する。

noah.cpp

std::vector <Head*> heads;

noah::alloc関数は、指定されたバイト数のメモリをヒープ領域に確保し、headsベクタの末尾に登録する。

noah.cpp

void* alloc(size_t bytes) { Head *head = new Head;

heads.push_back(head);

void *p = malloc(bytes);

size_t a1 = (size_t) p;

size_t a2 = a1 + bytes;

head ->from = (void*) a1;

head ->last = (void*) a2;

head ->marked = false;

return p;

}

(27)

以降はmark and sweepを実装する。下記のnoah::owner関数は、指定されたポインタのHeadを検索する。

noah.cpp

static Head* owner(void *ptr) { for(Head* &head : heads) {

void *from = head ->from;

void *last = head ->last;

if(ptr < from) continue;

if(ptr > last) continue;

return head;

}

return NULL;

}

noah::mark関数は、指定されたポインタをメンバに持つオブジェクトに印を付け、その参照先を巡回する。

noah.cpp

static void mark(void *ptr) { Head *head = owner(ptr);

if(head == NULL) return; if(head ->marked) return; head ->marked = true;

void *from = head ->from;

void *last = head ->last;

size_t s = (size_t) from;

size_t e = (size_t) last;

for(size_t i=s; i<e; i++) { mark(*(void**)i);

} }

noah::sweep関数は、指定されたHeadを確認し、無印ならばメモリを回収し、headsベクタから削除する。

noah.cpp

static void sweep(size_t idx) { Head *head = heads[idx];

auto it = heads.begin();

if(!head ->marked) { heads.erase(it + idx);

free(head ->from);

delete head;

} else head ->marked = false;

}

noah::clean関数は、指定された範囲に所在の全てのポインタを起点として、mark and sweepを実行する。

noah.cpp

void clean(void *from , void *last) { size_t s = (size_t) from;

size_t e = (size_t) last;

for(size_t i=s; i<e; i++) { mark(*(void**)i);

}

size_t i = heads.size();

while(i-- > 0) sweep(i);

} };

(28)

上記は、スタックに積まれた値が全てポインタであると仮定する保守的なガベージコレクタの実装例である。

数値の場合、mark and sweepをしても無駄であるが、言語処理系の協力がなければ、判別は不可能である。

以上で、mark and sweep方式のガベージコレクタが完成した。sharedオプションを付けてコンパイルする。

$ g++ -shared -fPIC -o libnoah.so noah.cpp

共有ライブラリlibnoah.soが生成される。動作確認を兼ねて、サンプルアプリケーションを実装してみる。

test.cpp

#include "noah.hpp"

struct cons { cons *car;

cons *cdr;

};

int main(void) {

void **root = new void*[2];

cons *cons1 = (cons*) noah::alloc(sizeof(cons));

root[0] = cons1;

root[1] = cons2;

cons3 ->car = cons4;

noah::clean(root , &root [2]);

}

libnoah.soを言語処理系に組み込む場合は、定期的にnoah::clean関数を実行するように実装すると良い。

test.cppは下記のコマンドで実行する。環境変数LD_LIBRARY_PATHを設定し、libnoah.soをリンクする。

$ g++ -L. -lnoah -o test test.cpp

$ export LD_LIBRARY_PATH=.

$ ./test

最後に、mark and sweepと並ぶ主要な走査型のアルゴリズムとして、Fig. 8.3のstop and copyを紹介する。

Fig. 8.3: stop-and-copy garbage collector.

まず、スタックを起点に参照を辿り、巡回したオブジェクトを新しい領域に移す。この操作をコピーと呼ぶ。

転写に漏れたオブジェクトは、古いヒープ領域と共に破棄する。mark and sweepに比べ、軽快に動作する。

転写の際に、オブジェクトの参照関係に応じて位置を調整すれば、キャッシュヒット率の改善も期待できる。

(29)

第 9 章リスト指向言語の処理系

第9章では、これまでとは趣向を変えて、構文を自在に拡張できるプログラミング言語の処理系を実装する。

elva$ (+ 1 2 3) 6

これは独自のLISPであり、elvaと名付ける。elvaはLisp-1であり、関数と変数は共通の名前空間に属す。

elva$ (set ’function-in-variable list)

elva$ (function-in-variable 1 2 3 4 5) (1 2 3 4 5)

Schemeと同様に、静的スコープであり、関数閉包にも対応する。関数は、define-lambdaにより定義する。

elva$ (define-lambda fact (x) (if (eq x 1) x (* x (fact (- x 1))))) (lambda (x) (if (eq x 1) x (* x (fact (- x 1)))))

elvaではマクロを定義して、構文を自在に拡張できる。例えば、変数宣言に利用するsetqもマクロである。

elva$ setq

(syntax (name value) (list (quote set) (list (quote quote) name) value))

syntax関数はマクロを生成する。関数閉包はlambda関数で生成する。名前はsetqを利用して与えている。

elva$ define-lambda

(syntax (name pars body) (list (quote setq) name (list (quote lambda) pars body))) elva$ define-syntax

(syntax (name pars body) (list (quote setq) name (list (quote syntax) pars body)))

ドット対は、Common LispやSchemeと異なり、隠蔽される。代わりに、リストを基本型として提供する。

9.1 式の構文解析

構文解析器は、S式を読み取って、LISPの構文木たるリスト構造を構築する。マクロ文字には未対応である。

elva.scala

object Parser extends util.parsing.combinator.JavaTokenParsers { def parse(str: String): Any = parseAll(sexp , str) match {

case Success(exp , _) => exp

case Failure(msg , _) => sys.error(s"error: $msg") case Error (msg , _) => sys.error(s"fatal: $msg") }

def sexp: Parser[Any] = quot|text|real|list|name def quot = "’"~>sexp^^(Seq(’quote , _))

def text = stringLiteral ^^(_.tail.init)

def real = """\d+\.?\d*(?=$|\s|$|$)""".r^^( BigDecimal(_)) def list = "("~>rep(sexp)<~")"

def name = """[^\s]+""".r^^( Symbol(_)) }

識別子には、空白や()以外の任意の印字可能なASCII文字を利用でき、数字で始まる識別子も許容される。

実数値との区別のため、正規表現に位置指定子(?=)を指定し、実数値の直後に空白文字か()を必須とした。

(30)

9.2 環境と評価器

Bindクラスは環境の実装で、識別子とその値を管理する。静的スコープを備え、外の環境への参照を持つ。

elva.scala

case class Bind(out: Eval , params: Seq[(Symbol , Any)]) { val table = scala.collection.mutable.Map(params: _*) def apply(s: Symbol): Any = {

if(table.isDefinedAt(s)) table(s) else if(out != null) out.binds(s) else sys.error(s"$s not defined") }

def update(s: Symbol , v: Any): Any = {table(s) = v; v}

}

第6.2節とは異なり、変数の値を更新するupdateメソッドを備える。続くEvalクラスは評価器を実装する。

評価器は、LISPの構文木を受け取り、その値を求める。識別子なら値を取得し、関数なら関数適用を行う。

elva.scala

case class Eval(binds: Bind = Bind(null, Seq())) { def apply(sexp: Any): Any = sexp match {

case s: Symbol => binds(s) case s: Seq[_] if s.isEmpty => s case s: Seq[_] => this(s.head) match {

case f: Lambda => f(s.tail , this) case f: Syntax => f(s.tail , this) case f: System => f(s.tail , this) case _ => sys.error(s"raw list: $s") }

case _ => sexp }

}

構文木はAny型である。例えば、リストはSeqで、識別子はSymbolで、実数値はBigDecimalで表現する。

9.3 関数とマクロ

elvaのシステム関数は、Systemクラスで実装する。関数は、実引数のリストと環境を受け取り、値を返す。

elva.scala

case class System(func: (Seq[Any], Eval) => Any) {

def apply(args: Seq[Any], eval: Eval) = func(args , eval) }

Lambdaクラスは関数閉包を表す。実引数を評価して新たな環境に登録し、新たな環境でvalueを評価する。

elva.scala

class Lambda(val params: Seq[Any], val value: Any , scope: Eval) { def apply(args: Seq[Any], eval: Eval) = {

Eval(Bind(scope , params.zip(args).map { case (p: Symbol , a) => p -> eval(a) case (p, a) => sys.error(s"$p=$a?") }))( value)

} }

(31)

Syntaxクラスはマクロを表す。実引数を評価せずに新たな環境に登録し、新たな環境でvalueを評価する。

elva.scala

class Syntax(val params: Seq[Any], val value: Any , scope: Eval) { def apply(args: Seq[Any], eval: Eval) = eval(

Eval(Bind(scope , params zip args map { case (p: Symbol , a) => p -> a

case (p, a) => sys.error(s"$p=$a?") }))( value)

) }

これで、実引数を式のままマクロの内部に展開できる。その後、展開されたマクロを以前の環境で評価する。

9.4 ^{システム関数}

Scalaでquoteやlistなどのシステム関数を実装し、対話環境のトップレベルを示す環境rootに登録する。

elva.scala

val root = Bind(null, Seq())

quoteは、引数を評価せずに値として返す。これは、引数を評価しない構文である特殊形式の代表例である。

elva.scala

root(’quote) = System((args , eval) => args.head)

listは、引数を評価して、値を順番に並べたリストを返す。特に、S式を生成する際に重要な役割を果たす。

elva.scala

root(’list) = System((args , eval) => args.map(eval(_)))

他にも、carやcdrなど、リストを操作する関数を定義すると良い。算術演算子も定義する。+の例を示す。

elva.scala

root(’+) = System((args , eval) => args.map(eval(_) match { case real: BigDecimal => real

case sexp => sys.error(s"non -number $sexp in $args") }). reduce((a, b) => a + b))

Scalaならば、mapやreduceなどのメソッドを駆使して、手軽に実装できる。続いて、eq関数を実装する。

elva.scala

root(’eq) = System((args , eval) => eval(args (0)) == eval(args (1)))

ifは、第1引数を評価してtrueならば第2引数を、falseならば第3引数を評価して返す特殊形式である。

elva.scala

root(’if) = System((args , eval) => eval(args (0)) match { case true => eval(args (1))

case false => eval(args (2))

case sexp => sys.error(s"not boolean: $sexp") })

(32)

lambdaは、関数閉包を生成する特殊形式である。第1引数が仮引数になり、第2引数が関数の本体となる。

elva.scala

root(’lambda) = System((args , eval) => new Lambda(args.head match { case pars: Seq[_] if pars.forall(_.isInstanceOf[Symbol]) => pars case sexp => sys.error(s"not symbol list: $sexp")

}, args(1), eval))

syntaxは、マクロを生成する特殊形式である。第1引数が仮引数になり、第2引数がマクロの本体になる。

elva.scala

root(’syntax) = System((args , eval) => new Syntax(args.head match { case pars: Seq[_] if pars.forall(_.isInstanceOf[Symbol]) => pars case sexp => sys.error(s"not symbol list: $sexp")

}, args(1), eval))

setは、識別子を値で束縛する。変数の宣言だけでなく、関数閉包やマクロに名前を与える際にも利用する。

elva.scala

root(’set) = System((args , eval) => eval(args.head) match { case name: Symbol => eval.binds(name) = eval(args (1)) case sexp => sys.error("not symbol: $sexp")

})

9.5 処理系の完成

暗黙の型変換を利用して、任意の型のS式を文字列に変換する機構を用意すると良い。以下に実装例を示す。

elva.scala

implicit class PrettyPrintableRawValueWrapper(rawValue: Any) { def p: String = rawValue match {

case v: Symbol => v.name

case v: String => ’"’ + v + ’"’

case v: System => s"<function >"

case v: Seq[_] => s"(${v.map(_.p).mkString(" ")})"

case v: Lambda => s"(lambda ${v.params.p} ${v.value.p})"

case v: Syntax => s"(syntax ${v.params.p} ${v.value.p})"

case v: Any => v.toString }

}

最後に、対話環境を実装する。プロンプトを表示して、S式を読み取り、評価した結果を文字列で表示する。

elva.scala

def main(args: Array[String]) {

val console = new scala.tools.jline.console.ConsoleReader console.setExpandEvents(false)

console.setPrompt(s"${Console.BLUE}elva$$ ${Console.RESET}") while(true) try {

println(Eval(root)(Parser.parse(console.readLine )).p) } catch {

case ex: Exception => println(Console.RED + ex.getMessage) }

}

Scalaで作るプログラミング言語処理系

Computation Models & Compiler on Scala

無線部開発班 平成 28 年 7 月 28 日

目次

第 1 章 逆ポーランド電卓の実験

1.1 スタック機械の実装

1.2 中置記法からの翻訳

第 2 章 チューリング機械の実験

2.1 自然数の後続の計算

2.2 文脈自由言語の受理

第 3 章 セルオートマトンの実験

3.1 セル空間の実装

3.2 生物集団の表現

3.3 論理回路の表現

第 4 章 文脈自由文法と言語仕様

4.1 バッカスナウア記法

4.2 自作する言語の仕様

第 5 章 型なしラムダ計算の基礎

5.1 チャーチ符号化

5.2 無名関数の再帰

第 6 章 仮想的な実行環境の設計

6.1 演算命令と定数

6.2 条件分岐と関数

call data stack

1

argument 2

argument

closure

call stack

environment

push a closure and arguments

data stack

return to

call stack

environment environment

create a new environment

第 7 章 言語処理系の完成と拡張

7.1 抽象構文木の実装

7.2 構文解析器の実装

7.3 遅延評価への変更

第 8 章 ガベージコレクタの実験

8.1 計数型の実装

8.2 走査型の実装

第 9 章 リスト指向言語の処理系

9.1 式の構文解析

9.2 環境と評価器

9.3 関数とマクロ

9.4 システム関数

9.5 処理系の完成

無線部開発班平成 28 年 7 月 28 日

第 1 章逆ポーランド電卓の実験

第 2 章チューリング機械の実験

2.2 ^{文脈自由言語の受理}

第 3 章セルオートマトンの実験

第 4 章文脈自由文法と言語仕様

4.1 ^{バッカスナウア記法}

第 5 章型なしラムダ計算の基礎

5.1 ^{チャーチ符号化}

第 6 章仮想的な実行環境の設計

第 7 章言語処理系の完成と拡張

7.1 ^{抽象構文木の実装}

7.3 ^{遅延評価への変更}

第 8 章ガベージコレクタの実験

第 9 章リスト指向言語の処理系

9.4 ^{システム関数}