Scala でプログラミング言語を自作する
Let’s make a programming language by Scala
無線部開発班
平成 28 年 7 月 5 日
無線部
Scala でプログラミング言語を自作する
開発班
目次
第 1 章 言語処理系入門
1.1
1.2
3
形式言語 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
構文解析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
第 2 章 言語仕様の策定
2.1
2.2
識別子 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3
2.4
基本型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.5
2.6
2.7
構文規則 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.8
2.9
参照透明 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
予約語 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
型変換 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
関数閉包 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
評価戦略 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
無名再帰 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
第 3 章 ラムダ計算入門
3.1
関数定義 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2
3.3
3.4
関数適用 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.5
3.6
論理演算 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
変換規則 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
無名再帰 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
整数演算 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
第 4 章 仮想機械の実装
4.1
仮想機械と命令 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2
4.3
4.4
二項演算の実現 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
条件分岐の実現 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
関数適用の実現 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
第 5 章 構文解析の実装
5.1
5.2
3
4
5
5
5
5
5
6
6
6
6
6
7
7
7
7
8
8
8
9
9
9
11
11
13
抽象構文木の実装 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
言語処理系の完成 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
15
第 6 章 遅延評価の実装
16
第 7 章 記憶領域の管理
17
7.1
7.2
計数型の実装 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
走査型の実装 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
17
18
無線部
Scala でプログラミング言語を自作する
開発班
第 1 章 言語処理系入門
本稿は、Scala のパーサーコンビネータを利用し、ラムダ計算を基礎とするプログラミング言語を自作する。
1.1
形式言語
英字や数字など終端記号の有限集合 Σ を字母と呼び、Σ に属する記号 σ を並べた文の集合 L を言語と呼ぶ。
L ⊂ Σ∗ = {σ1 σ2 ...|σk ∈ Σ} .
(1.1)
形式的な文法を持つ言語を形式言語と呼び、正規言語・文脈自由言語・文脈依存言語・帰納可算言語がある。
正規言語は有限状態機械、文脈自由言語はプッシュダウン機械、文脈依存言語は線形拘束機械で受理できる。
最上位の帰納可算言語はチューリング機械で受理できる。通常、プログラミング言語は文脈自由言語である。
P を生成規則の集合、N を非終端記号の集合、S を開始記号とすると、形式文法 G は式 (1.2) で与えられる。
G = (N, Σ, P, S), P : N → (N ∪ Σ)∗ , S ∈ N.
(1.2)
文脈自由言語では、生成規則は、非終端記号を非終端記号と終端記号の列に置換する。四則演算の例を示す。
数式
expr := add | mul | num
加算
add
mul
num
乗算
整数
:= num (’+’ | ’-’) num
:= num (’*’ | ’/’) num
:= [0-9]+
上記は BNF、即ちバッカスナウア記法の例でもあり、プログラミング言語の文法を定義する際に多用する。
A|B
A B
A+
選択
A*
A?
0 回以上の出現
1 回以下の出現
連続
1 回以上の出現
前掲の四則演算の定義では、任意個の項を扱えず、演算の優先順位も未定義なので、下記のように修正する。
数式
expr ::= add
加算
乗算
add
mul
::= mul ((’+’ | ’-’) mul)*
::= num ((’*’ | ’/’) num)*
整数
num
:= [0-9]+
数式をプッシュダウン機械で読み取る手順は、トップダウン構文解析とボトムアップ構文解析の 2 種類ある。
前者では、開始記号 S = expr を起点に設定し、P から適切な生成規則を選びながら、終端記号に到達する。
後者では、終端記号を起点に設定し、P から適切な生成規則を選びながら、開始記号 S = expr に到達する。
構文解析は探索問題であり、バックトラックが必要なら、記号をプッシュダウン機械のスタックに退避する。
3
無線部
1.2
Scala でプログラミング言語を自作する
開発班
構文解析
第 1.2 節で紹介する再帰下降構文解析は、第 1.1 節に示した生成規則のうち、開始記号から探索を開始する。
そして、文字列に適合する規則を探索しながら構造を把握する。下記は、四則演算の構文解析の実装である。
RecursiveDescentParser.scala
class RecursiveDescentParser(expr: String) {
def parse() = parseAdd(new Lex(expr))
def parseAdd(lex: Lex): Int = {
var left = parseMul(lex)
while(true) lex.next() match {
case "+" => left += parseMul(lex)
case "-" => left -= parseMul(lex)
case _ => lex.back(); return left;
}
return left
}
def parseMul(lex: Lex): Int = {
var left = parseNum(lex)
while(true) lex.next() match {
case "*" => left *= parseNum(lex)
case "/" => left /= parseNum(lex)
case _ => lex.back(); return left;
}
return left
}
def parseNum(lex: Lex) = lex.next().toInt
}
上記で、Lex は、正規言語を利用し、数式を終端記号の列、即ち演算子と整数に分解する字句解析器である。
Lex.scala
class
val
var
def
def
}
Lex(expr: String) {
tokens = "[0-9]+|\\+|-|\\*|/".r.findAllIn(expr).toSeq
cursor = Stream.from(0).iterator
next() = tokens.lift(cursor.next).getOrElse(null)
back() = cursor = Stream.from(cursor.next -1).iterator
関数 parseAdd・parseMul・parseNum は、それぞれ下記の生成規則 add・mul・num に沿った解析器である。
加算
乗算
add ::= mul ((’+’ | ’-’) mul)*
mul ::= num ((’*’ | ’/’) num)*
整数
num ::= [0-9]+
このように、再帰下降構文解析では、生成規則に対応する関数を組み合わせることで、構文解析を実現する。
RecursiveDescentParser.scala
val result = ((new RecursiveDescentParser("12*34+56-78/9")).parse())
第 5 章で述べるパーサーコンビネータがあれば、複雑な文法も容易に実装できるが、左再帰に注意を要する。
加算
add ::= add ’+’ mul | mul
上記の生成規則は左再帰の例であり、再帰下降構文解析などトップダウン構文解析では、無限ループに陥る。
4
無線部
Scala でプログラミング言語を自作する
開発班
第 2 章 言語仕様の策定
本稿で設計する fava は、無名関数が特徴の動的型付け言語だが、不動点を利用して再帰関数も記述できる。
fava$
1
fava$
2
fava$
3
fava$
5
((f)=>((x)=>f((y)=>x(x)(y)))((x)=>f((y)=>x(x)(y))))((f)=>(n)=>(n<2)?n:f(n-1)+f(n-2))(2)
((f)=>((x)=>f((y)=>x(x)(y)))((x)=>f((y)=>x(x)(y))))((f)=>(n)=>(n<2)?n:f(n-1)+f(n-2))(3)
((f)=>((x)=>f((y)=>x(x)(y)))((x)=>f((y)=>x(x)(y))))((f)=>(n)=>(n<2)?n:f(n-1)+f(n-2))(4)
((f)=>((x)=>f((y)=>x(x)(y)))((x)=>f((y)=>x(x)(y))))((f)=>(n)=>(n<2)?n:f(n-1)+f(n-2))(5)
2.1
識別子
fava では、$もしくは_もしくは英字で始まり、$もしくは_もしくは英数字が続く文字列を識別子にできる。
識別子
id ::= [$A-Z_a-z] [$0-9A-Z_a-z]*
fava の識別子は、当該箇所を包含し、同名の引数を有する、最も内側の関数の引数として静的に解決する。
2.2
予約語
fava では、識別子 true と false は引数の名前として利用できず、真偽値を参照する予約語として扱われる。
2.3
基本型
fava は強い動的型付けを行う言語である。データ型は整数型、実数型、論理型、文字列型、関数型がある。
整数型
int
実数型
文字列
real ::= [0-9]* ([0-9] ’.’ | ’.’ [0-9]) [0-9]*
bool ::= ’true’ | ’false’
str ::= ’"’ char* ’"’
関数型
func ::= ’(’ (id (’,’ id)*)? ’)’ ’=>’ expr
論理型
::= [0-9]+
整数型は符号付き 32bit 整数値、実数型は IEEE 754 2 進倍精度小数である。文字列は UTF-16 で表現する。
fava の関数は無名関数だが、first-class function でもある。例えば、関数の引数や返り値として指定できる。
2.4
型変換
fava は明示的な型変換を行う機能を持たないが、整数と実数との四則演算は、暗黙的に実数に変換される。
fava$ 0.1 + 234
234.1
5
無線部
2.5
Scala でプログラミング言語を自作する
開発班
構文規則
fava のプログラムは単独のラムダ式である。繰り返し文や変数宣言、変数の再代入などの概念は排除する。
ラムダ式
条件分岐
論理積
論理和
等値比較
順序比較
加減算
乗除算
単項演算
関数適用
式の要素
リテラル
expr
cond
or
::= cond | or
::= or ’?’ expr ’:’ expr
::= and (’|’ and )*
and
::= equal (’&’ equal)*
equal ::= rel ((’==’ | ’!=’) rel)*
rel
add
mul
::= add ((’<’ | ’>’ | ’<=’ | ’=>’) add)*
::= mul ((’+’ | ’-’) mul)*
::= unary ((’*’ | ’/’ | ’%’) unary)*
unary ::= (’+’ | ’-’ | ’!’) unary | call
call ::= fact (’(’ (expr (’,’ expr)*)? ’)’)*
fact
atom
::= func | atom | ’(’ expr ’)’
::= int | real | bool | str | id
fava では、半角空白 (0x20) とタブ (0x09) と改行 (0x0A) は、字句と字句を切り離す区切り文字として扱う。
2.6
関数閉包
fava の束縛変数は、それを引数とする関数への参照が生存する限り保存され、値を取り出すことができる。
fava$ ((x)=>((y)=>x*y))(2)(3)
6
2.7
評価戦略
fava では、式は作用的順序で評価され、演算子は called by value である。部分評価や部分適用は禁止する。
2.8
参照透明
fava では、式の意味と式の値は同義であり、部分式を同値な他の式に置換しても、式の意味は不変である。
2.9
無名再帰
自作言語処理系で無名関数を嗜むことは、言語処理系を自作する醍醐味である。詳細は第 3.4 節で述べるが、
式 (3.12) の Y コンビネータを fava で実装し、無名関数を引数に与えれば、無名関数を再帰的に呼び出せる。
fava$ ((f)=>((x)=>f(x(x)))((x)=>f(x(x))))
以下はフィボナッチ数の例である。ただし、第 3.4 節に述べる通り、call by value では、無限ループに陥る。
fava$ ((f)=>((x)=>f(x(x)))((x)=>f(x(x))))((f)=>(n)=>(n==0)?1:n*f(n-1))(10)
対策としては、第 6 章で実装する遅延評価が有効であるが、当面は、式 (3.14) の Z コンビネータで代用する。
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
6
無線部
Scala でプログラミング言語を自作する
開発班
第 3 章 ラムダ計算入門
ラムダ計算は多くのプログラミング言語の理論的基礎であり、チューリング機械と等価な計算モデルである。
3.1
関数定義
式 (3.1) はラムダ式で、関数 f (x) = 7x3 − 5x2 + 3x を表す。関数 f (x) を定義する作業をラムダ抽象と呼ぶ。
λx.(7x3 − 5x2 + 3x).
(3.1)
記号 λ は、ラムダ抽象の合図であり、ラムダ計算の名前の由来でもある。多変数関数 f (x, y) も定義できる。
λxy.(x3 + x2 − y 2 + y) = λx.λy.(x3 + x2 − y 2 + y).
(3.2)
式 (3.2) の左辺は、右辺の高階関数と等価である。このように単変数関数で書き直す操作をカリー化と呼ぶ。
3.2
関数適用
関数 f (x) に引数 x を与える操作を関数適用と呼ぶ。式 (3.3) は、式 (3.2) の関数 f (x, y) の値 f (2, 3) である。
(λx.λy.(x3 + x2 − y 2 + y)) 2 3.
(3.3)
関数適用は左結合であり、引数 y は放置して、引数 x を値 2 で束縛する。結果、式 (3.3) は式 (3.4) になる。
(λy.(23 + 22 − y 2 + y)) 3.
(3.4)
式 (3.3) から式 (3.4) への変換をベータ簡約と呼ぶ。残りの引数 y を値 3 で束縛すると、f (2, 3) = 6 を得る。
3.3
変換規則
変数 y が自由変数として出現しない式 E と変数 x に対し、式 (3.5) に示す置換の操作をアルファ変換と呼ぶ。
λx.E −
→ λy.E|x:=y .
α
(3.5)
式 E1 , E2 と変数 x に対し、式 (3.6) の操作が E2 内の自由変数を束縛しない場合、操作をベータ簡約と呼ぶ。
(λx.E1 )E2 −
→ E1 |x:=E2 .
β
(3.6)
変数 x が自由変数として出現しない式 E と変数 x に対し、x を消去する式 (3.7) の操作をイータ変換と呼ぶ。
λx.Ex −
→ E.
(3.7)
η
式 (3.7) の操作が許容される場合、任意の引数 x に対し同値関係にある関数 f と g は外延的に同値と言える。
f x = gx → λx.f x = λx.gx −
→ f = g.
η
7
(3.8)
無線部
3.4
Scala でプログラミング言語を自作する
開発班
無名再帰
ラムダ計算には再帰関数を定義する規則はないが、不動点コンビネータを利用すれば再帰関数を表現できる。
関数 f (x) に対し p = f (p) となる点 p を不動点と呼び、p を求める高階関数 g を不動点コンビネータと呼ぶ。
g(f ) = f (g(f )).
(3.9)
関数 h(x) を、関数 f が変数として出現する式 E と不動点コンビネータ g により、式 (3.10) の通り定義する。
h(x) = gλf.λx.E.
(3.10)
式 (3.9) より式 (3.11) が導出される。式 E の中の変数 f は、関数 h(x) により束縛される。
h(x) = (λf.λx.E)(gλf.λx.E) = (λf.λx.E)(h(x)) = λx.E|f :=h(x) .
(3.11)
式 (3.11) は、関数 h(x) が引数 f を通じて関数 h(x) を参照することを意味し、関数 h(x) は再帰関数となる。
関数 g の候補は星の数ほど存在するが、特に有名な例として、Haskell Curry の Y コンビネータを紹介する。
y = λf.(λx.f (xx))(λx.f (xx)).
(3.12)
関数 h に対し、式 (3.12) の Y コンビネータが式 (3.9) の性質を満たすことは、式 (3.13) により明らかである。
yh −
→ (λx.h(xx))(λx.h(xx)) −
→ h((λx.h(xx))(λx.h(xx))) = h(yh).
β
β
(3.13)
本稿の言語も該当するが、call by value を原則とする多くの言語では、式 (3.13) の実行は無限ループに陥る。
式 (3.13) を無限に展開するためである。そこで、式 (3.12) を部分的に変換した Z コンビネータで代用する。
z = λf.(λx.f (λy.xxy))(λx.f (λy.xxy)).
3.5
(3.14)
論理演算
純粋なラムダ計算では、論理演算の機能を計算規則に導入せずとも、関数定義だけで論理演算を再現できる。
T = λxy.x,
(3.15)
F = λxy.y.
(3.16)
式 (3.15)(3.16) は真と偽の定義例である。論理演算子は、式 (3.17)(3.18) で定義する。ぜひ証明してみよう。
3.6
and = λxy.xyF,
(3.17)
or = λxy.xT y.
(3.18)
整数演算
純粋なラムダ計算では、論理演算と同様に整数演算も、関数定義で再現できる。Church の整数と呼ばれる。
0 = λf x.x,
(3.19)
1 = λf x.(f x),
(3.20)
2 = λf x.f (f x).
(3.21)
例えば、整数と整数の足し算と掛け算は、式 (3.22)(3.23) で定義する。
add = λab.λf x.af (bf x),
(3.22)
mul = λab.λf x.a(bf )x.
(3.23)
第 2 章の言語仕様では、第 3.5 節や第 3.6 節に示す狂気に満ちた定義は採用せず、実用的な言語を志向した。
8
無線部
Scala でプログラミング言語を自作する
開発班
第 4 章 仮想機械の実装
第 4 章では、ラムダ計算は忘却の彼方に放逐し、ソフトウェアで仮想的な計算機を再現する技術を紹介する。
実行環境としてスタック機械と呼ばれる仮想機械を設計し、それを動かす機械語と併せて Scala で実装する。
4.1
仮想機械と命令
下記の仮想機械 VM は、プログラムカウンタ pc とスタックを有し、pc が示す位置の命令を順番に実行する。
VM.scala
object VM {
def exec(codes: Seq[fava.code.Code]): Any = {
val stack = new Stack()
var pc = 0
while(pc < codes.size) pc = codes(pc).exec(stack , pc)
stack.pop
}
}
命令は下記の Code トレイトを継承し、スタックと pc を引数に演算を行い、次に実行する命令の位置を返す。
Code.scala
trait Code {def exec(stack: Stack , pc: Int): Int}
第 4 章では、Scala の Any 型を A、Int 型を I、Double 型を D、Boolean 型を B、String 型を S と表記する。
Code.scala
import scala.{Any=>A,Int=>I,Double=>D,Boolean=>B}
4.2
二項演算の実現
Fig. 4.1: generating byte codes from a syntax tree.
第 5 章で実装する構文解析器を用いて式 (1+2)*3 を構文解析すると、Fig. 4.1 に示す抽象構文木が得られる。
構文木は中間言語命令に変換され、スタックマシンで Fig. 4.2 に示す通りに実行され、計算結果の 9 を得る。
9
無線部
Scala でプログラミング言語を自作する
開発班
Fig. 4.2: calculation of (1+2)*3 on a stack machine.
まず、命令 push 1 により、スタックに即値 1 が積まれる。次に、命令 push 2 により、即値 2 が積まれる。
Code.scala
case class Push(value: Any) extends Code {
def exec(stack: Stack , pc: Int): Int = {
stack.push(value)
pc + 1
}
}
続く add 命令は、式 1+2 を計算する。スタックの上端の値を 2 個取り去って加算し、結果をスタックに積む。
Code.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
}
}
この時点で、スタックには整数 3 が積まれている。命令 push 3 を実行し、mul 命令により 3 × 3 を求める。
Code.scala
case class Mul() 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) => throw error(a, b)
}
}
最後に残った整数 9 が計算結果である。なお、二項演算の命令は、下記の Bin クラスを継承するものとする。
Code.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}")
}
10
無線部
4.3
Scala でプログラミング言語を自作する
開発班
条件分岐の実現
条件分岐は、下記の Jmp 命令と Jmpf 命令で実現する。Jmp 命令は、pc を操作して、指定の位置に移動する。
Code.scala
case class Jmp(offset: Int) extends Code {
def exec(stack: Stack , pc: Int) = pc + offset
}
Jmpf 命令は条件分岐命令で、スタックの上端の値を取り去り、その値が false なら指定の位置に移動する。
Code.scala
case class Jmpf(offset: Int) extends Code {
def exec(stack: Stack , pc: Int) = pc + (if(stack.popAs[B]) 1 else offset)
}
4.4
関数適用の実現
関数適用は、関数の定義位置へのジャンプにより実現するが、引数へのアクセス手段も提供する必要がある。
Fig. 4.3: function call with arguments 3 and 4.
Fig. 4.3 に示す通り、関数の引数は関数適用の直前にスタックに積まれ、関数適用と同時に環境に格納する。
環境 Env とは、仮引数と実引数の対応表であり、引数は番号で管理する。環境 Env は、再帰的な構造を持つ。
環境は関数定義の入れ子構造と対応しており、enclosure は、外側に定義された関数の環境への参照である。
Env.scala
case class Env(args: Seq[Any] = null, enclosure: Env = null) {
def get(nest: Int, id: Int): Any = nest match {
case nest if nest >= 1 => enclosure.get(nest - 1, id)
case nest if nest == 0 => args(id)
}
}
fava のラムダ式が変数を参照したら、Load 命令により、指定された番号の引数を複製し、スタックに積む。
Code.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 をスタックに積む。
11
無線部
Scala でプログラミング言語を自作する
開発班
Code.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(Env(args, func.enclosure))
func.from
}
}
Closure は fava の関数型の実装であり、from が関数の定義位置である。enclosure については、後述する。
Type.scala
case class Closure(from: Int, enclosure: Env)
関数の実行が終わると、以前の場所に戻り、後続の命令を実行する必要がある。これは Ret 命令で実現する。
Fig. 4.3 のように、戻り先 ret はスタックに待避してある。Ret 命令は、環境を廃棄して以前の場所に戻る。
Code.scala
case class Ret() extends Code {
def exec(stack: Stack , pc: Int): Int = {
val (ret, _) = (stack.pop, stack.ret)
val jmp = stack.popAs[Int]
stack.push(ret)
jmp
}
}
fava の関数に出現する自由変数は、関数定義が評価された時点での値を記憶する。これを関数閉包と呼ぶ。
クロージャとも呼ばれ、fava がカリー化に対応する根拠となる。関数閉包は、Func 命令により生成される。
Code.scala
case class Func(length: Int) extends Code {
def exec(stack: Stack , pc: Int): Int = {
stack.push(Closure(pc + 1, stack.env))
pc + length
}
}
最後に、スタックを実装する。環境の操作を効率化するため、環境のスタックと演算のスタックを分離した。
Stack.scala
class Stack {
import collection.mutable.{Stack => ScalaStack}
val envStack = ScalaStack[Env](new Env)
val valStack = ScalaStack[Any]()
def push(frame: Env) = envStack.push(frame)
def push(value: Any) = valStack.push(value)
def popN(n: Int) = 1.to(n).map(_=>pop).reverse
def popAs[Type]: Type = pop.asInstanceOf[Type]
def pop = valStack.pop
def ret = envStack.pop
def env = envStack.head
}
12
無線部
Scala でプログラミング言語を自作する
開発班
第 5 章 構文解析の実装
第 1.2 節では、再帰下降構文解析を手書きで実装したが、パーサーコンビネータがあれば簡単に実装できる。
生成規則を表現する関数を、パーサーコンビネータと呼ばれる高階関数で結合して、構文解析器を構築する。
Parser.scala
object Parser extends util.parsing.combinator.JavaTokenParsers {
def parse(str: String): AST = parseAll(expr, str) match {
case Success(result , _) => result
case fail: NoSuccess => throw new ScriptException(fail.msg)
}
def expr: Parser[Expr] = cond|or
def cond = or~"?"~expr~":"~expr^^{
case c~_~yes~_~no => If(c, yes, no)
}
def or = chainl1(and,
"|"^^(op => (l: Expr, r: Expr) => Or(l, r)))
def and = chainl1(eq,
"&"^^(op => (l: Expr, r: Expr) => And(l, r)))
def eq = chainl1(rel,
"=="^^(op => (l: Expr, r: Expr) => Eq(l, r))|
"!="^^(op => (l: Expr, r: Expr) => Ne(l, r)))
def rel = chainl1(add,
">="^^(op => (l: Expr, r: Expr) => Ge(l, r))|
"<="^^(op => (l: Expr, r: Expr) => Le(l, r))|
">" ^^(op => (l: Expr, r: Expr) => Gt(l, r))|
"<" ^^(op => (l: Expr, r: Expr) => Lt(l, r)))
def add = chainl1(mul,
"+"^^(op => (l: Expr, r: Expr) => Add(l, r))|
"-"^^(op => (l: Expr, r: Expr) => Sub(l, r)))
def mul = chainl1(unary ,
"*"^^(op => (l: Expr, r: Expr) => Mul(l, r))|
"/"^^(op => (l: Expr, r: Expr) => Div(l, r))|
"%"^^(op => (l: Expr, r: Expr) => Mod(l, r)))
def unary: Parser[Expr] = ("+"|"-"|"!")~unary^^{
case "+"~u => Add(Lit(0), u)
case "-"~u => Sub(Lit(0), u)
case "!"~u => Ne (Lit(true), u)
}|call
def call = fact~rep("("~>repsep(expr, ",")<~")")^^{
case p~Nil => p
case p~apps => apps.foldLeft(p)(Call(_,_))
}
def fact = func|bool|num|str|id|"("~>expr <~")"
def func = ("("~>repsep(id, ",")<~")")~"=>"~expr^^{
case p~_~e => Func(p.map(_.name), e)
}
def bool = ("true"|"false")^^(Bool(_))
def num = decimalNumber^^(Num(_))
def str = stringLiteral^^(Str(_))
def id = ident^^(Id(_))
}
13
無線部
5.1
Scala でプログラミング言語を自作する
開発班
抽象構文木の実装
第 5 章の構文解析器が構築する構文木を実装する。コード生成器を兼ねており、第 4 章の命令列を生成する。
AST.scala
trait AST {def code(implicit env: Func): List[Code]}
trait Expr extends AST
命令列の生成は、code メソッドに実装する。暗黙の引数 env は、その構文木を包む環境となる関数である。
下記の Lit は、リテラルを表す構文木である。code メソッドは、value を即値として Push 命令を発行する。
AST.scala
case class Lit(value: Any) extends Expr {
def code(implicit env: Func): List[Code] = {
List(fava.code.Push(value))
}
}
下記の Add は、二項演算の構文木の例である。先に被演算子の命令列を展開し、直後に演算命令を挿入する。
AST.scala
case class Add(expr1: AST, expr2: AST) extends Expr {
def code(implicit env: Func): List[Code] = {
expr1.code ++ expr2.code :+ fava.code.Add()
}
}
下記の If は、条件分岐を表す構文木である。第 4.3 節で実装した Jmp 命令と Jmpf 命令は、ここで使用する。
AST.scala
case class If(cond: AST, yes: AST, no: AST) extends Expr {
def code(implicit env: Func): List[Code] = {
val (c,y,n) = (cond.code, yes.code, no.code)
(c :+ fava.code.Jmpf(2 + y.size)) ++
(y :+ fava.code.Jmp (1 + n.size)) ++ n
}
}
命令列は、条件式・Jmpf 命令・真の場合の式・Jmp 命令・偽の場合の式と並び、不要な式の評価を回避する。
下記の Id は、識別子を表現する。環境を辿り、該当する仮引数を探索し、発見すれば Load 命令を発行する。
AST.scala
case class Id(name: String) extends Expr {
def find(implicit env: Func): Load = {
val idx = env.pars.indexOf(name)
if(idx >= 0) return Load(0, idx)
if(env.enclosure != null) {
val out = find(env.enclosure)
return Load(out.nest + 1, out.id)
}
import javax.script.ScriptException
throw new ScriptException(s"${name}:?")
}
def code(implicit env: Func) = List(find)
}
14
無線部
Scala でプログラミング言語を自作する
開発班
下記の Call は、関数適用を表現する構文木である。関数と引数を順に評価してから、Call 命令を実行する。
AST.scala
case class Call(func: AST, args: Seq[Expr]) extends Expr {
def code(implicit env: Func): List[Code] = {
func.code ++
args.map(_.code).fold(List())(_++_) :+
fava.code.Call(args.size)
}
}
下記の Func は、関数定義を表現する。関数を命令列に変換すると、まず Func 命令、次に関数の内容が続き、
最後に Ret 命令を挿入する。Func 命令は、関数閉包を生成し、関数が実行されないように直後に移動する。
AST.scala
case class Func(pars: Seq[String], body: Expr) extends Expr {
var enclosure: Func = null
def code(implicit env: Func): List[Code] = {
this.enclosure = env
val contents = body.code(this)
fava.code.Func(1 + contents.size + 1) +:
contents :+
fava.code.Ret()
}
}
enclosure は、外側の関数への参照である。code メソッドの引数 env を記憶し、識別子の解決に役立てる。
5.2
言語処理系の完成
第 4 章で仮想機械が、第 5 章で構文解析器とコード生成器が完成し、後は対話環境の準備を残すのみである。
対話環境は read-eval-print-loop とも呼ばれ、コマンドライン入力を読み取って解釈し、実行結果を表示する。
Repl.scala
object Repl {
def main(args: Array[String]) {
while(true) try {
print(Console.BLUE + "fava$ " + Console.RESET)
val ast = Parser.parse(io.StdIn.readLine)
println(VM.exec(ast.code(null)))
} catch {
case ex: Exception => println(Console.RED + ex)
}
}
}
蛇足だが、青文字と赤文字による色分け機能を盛り込んだ。構文エラーや実行時エラーは、赤字で表示する。
fava$ ((x, y) => a * y)(2, 3)
a:?
本稿の処理系は、リポジトリで頒布している。紙面の都合で省略した部分は、リポジトリを参照してほしい。
$ git clone http://git.pafelog.net/fava
$ java -jar fava/build/libs/fava.jar
15
無線部
Scala でプログラミング言語を自作する
開発班
第 6 章 遅延評価の実装
第 6 章で設計する bean は fava の仕様を変更し、call by name に対応させた軽量な動的型付け言語である。
次式を call by value で評価すると、関数適用の直前に、式 1+2 の値 3 と式 3+4 の値 7 がスタックに積まれる。
fava$ ((x,y)=>x*y)(1+2,3+4)
上記の式を call by name で評価すると、式 1+2 と式 3+4 の値は、関数内で参照した際に初めて計算される。
これは非正格評価とも呼ばれる。call by value でも、高階関数を利用することで、同等の挙動を再現できる。
fava$ ((x,y)=>x()*y())(()=>1+2,()=>3+4)
実引数の評価を遅延する目的で利用される関数閉包をサンクと呼び、引数の値を計算する操作を強制と呼ぶ。
第 5.1 節で、関数適用の構文木 Call を実装したが、実引数を関数定義の構文木 Func で包む動作を追加する。
AST.scala
case class LazyCall(func: AST, args: Seq[Expr]) extends Expr {
def code(implicit env: Func): List[Code] = {
Call(func, args.map(Func(List(), _))).code
}
}
第 4.4 節で、引数を参照する命令 Load を実装したが、構文木 Id を改修して、直後に Call 命令を挿入する。
Code.scala
case class LazyId(name: String) extends Expr {
def code(implicit env: Func): List[Code] = {
List(Id(name).find, fava.code.Call(0))
}
}
第 5 章の構文解析器を改修して、Call 命令を LazyCall 命令に、構文木 Id を構文木 LazyId に置き換える。
Parser.scala
def call = fact~rep("("~>repsep(expr, ",")<~")")^^{
case p~Nil => p
case p~apps => apps.foldLeft(p)(LazyCall(_,_))
}
def id = ident^^(LazyId(_))
僅かな改修で bean の評価戦略は call by name に移行した。式 (3.12) の Y コンビネータの評価も停止する。
fava$ ((f)=>((x)=>f(x(x)))((x)=>f(x(x))))((f)=>(n)=>(n==0)?1:n*f(n-1))(10)
3628800
引数を参照する度に実引数を評価する上記の実装は、同じ引数を何度も参照する場合には、非効率的である。
fava$ ((x)=>x*x)(3+3)
実引数を評価した際に、その値を環境に登録して、評価の回数を抑制する非正格評価を call by need と呼ぶ。
16
無線部
Scala でプログラミング言語を自作する
開発班
第 7 章 記憶領域の管理
関数適用は、引数の数だけ多くのメモリ領域を消費する。関数適用が終了すれば、メモリ領域は解放できる。
だが、下記の高階関数では、外側の関数が終了しても、内側の関数は束縛変数 x = 2 を参照する必要がある。
fava$ ((x)=>((y)=>x*y))(2)(3)
第 7 章で実装するガベージコレクタは、変数のメモリを解放しても良いか、自動的に判断する仕組みである。
自作せずとも Java の高性能なガベージコレクタの恩恵に与れるが、折角なので C++で簡単に再現してみる。
7.1
計数型の実装
C++11 の shared_ptr<>は reference count と呼ばれるガベージコレクタの実装である。Fig. 7.1 に図示する。
Fig. 7.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 は、オブジェクトが不要になると迅速に解放できるが、循環参照を解放できない難点がある。
17
無線部
7.2
Scala でプログラミング言語を自作する
開発班
走査型の実装
Fig. 7.2 の mark and sweep は、第 7.1 節の reference count と並び、主要なガベージコレクタの手法である。
Fig. 7.2: mark-and-sweep garbage collector.
まず、スタックを起点に参照を辿り、巡回したオブジェクトに生存の印を付ける。この操作をマークと呼ぶ。
次に、ヒープ領域を走査し、生存の印が付いていないオブジェクトを削除する。この操作をスイープと呼ぶ。
第 7.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;
}
18
無線部
Scala でプログラミング言語を自作する
開発班
いよいよ、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);
}
};
19
無線部
Scala でプログラミング言語を自作する
開発班
ところで、スタックに積まれる値はポインタとは限らず、数値や真偽値の場合、起点にしても無駄であるが、
データ型の判別は困難である。そこで、保守的なガベージコレクタでは、全てがポインタであると仮定する。
以上で、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));
cons *cons2 = (cons*) noah::alloc(sizeof(cons));
cons *cons3 = (cons*) noah::alloc(sizeof(cons));
cons *cons4 = (cons*) noah::alloc(sizeof(cons));
root[0] = cons1;
root[1] = cons2;
cons1 ->car = cons2;
cons3 ->car = cons5;
cons4 ->car = cons5;
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. 7.3 の stop and copy を紹介する。
Fig. 7.3: stop-and-copy garbage collector.
まず、スタックを起点に参照を辿り、巡回したオブジェクトを新しい領域に移す。この操作をコピーと呼ぶ。
転写に漏れたオブジェクトは、古いヒープ領域と共に破棄する。mark and sweep に比べ、軽快に動作する。
転写の際に、参照・被参照の関係にあるオブジェクトを近傍に配置すれば、キャッシュヒット率が改善する。
20
© Copyright 2024 ExpyDoc
