1. No category

Scala でプログラミング言語を自作しよう
Let’s create your original programming language with Scala
無線部開発班
2014 年 12 月 17 日
1
はじめに
本稿では Scala のパーサーコンビネータを使ってお手軽にプログラミング言語を自作する。
2
言語仕様
2.1
概説
nano は関数型言語が備える最低限度の機能のみを実装した軽量な動的型付け言語である。
2.2
予約語
下記の字句は予約語とする。
true, false, if, else
2.3
演算子
下記の字句は演算子とする。
+, -, *, /, %, <, >, <=, =>, ==, !=, &, |
2.4
データ型
nano は強い動的型付けを行う。
2.4.1 整数型
nano の整数型は符号付き 32bit 整数である。
2.4.2 実数型
nano の実数型は IEEE754 倍精度浮動小数点数である。
2.4.3 真偽値型
true は真を表し false は偽を表す。
2.4.4 文字列型
nano の文字列型は UTF-16 で表現される。
2.4.5 関数型
nano の関数は第一級で、関数の引数や返り値にできる。
2.5
暗黙の型変換
整数値と実数値との四則二項演算は実数値に変換される。
2
2.6
評価
nano の全ての式は先行評価される。
2.7
構文
nano のプログラムは単一の式である。
expression ::= conditional | or
2.7.1 条件分岐
if は条件分岐を行う演算子である。
conditional ::= ’if’ ’(’ condition ’)’ then ’else’ else
condition ::= expression
then ::= expression
else ::= expression
condition 式が true なら then 節を、false なら else 節を評価する。
2.7.2 論理演算
&は論理積を計算する演算子で、|は論理和を計算する演算子である。
or ::= and { ’|’ and }
and ::= equal { ’&’ equal }
2.7.3 等値比較
==は左右の式の等値性を確認する演算子で、!=はその否定である。
equal ::= relative { (’==’ | ’!=’) relative }
2.7.4 算術比較
< > <= =>は左右の数値の算術比較を行う演算子である。
relative ::= add { (’<’ | ’>’ | ’<=’ | ’=>’) add }
2.7.5 四則演算
+ は加算、-は減算、*は乗算、/は除算、% は剰余を求める演算子である。
add ::= mul { (’+’ | ’-’) mul }
mul ::= unary { (’*’ | ’/’ | ’%’) unary }
2.7.6 単項演算
+ は正の算術単項演算子、-は負の算術単項演算子、!は論理否定演算子である。
unary ::= (’+’ | ’-’ | ’!’) unary | call
3
2.7.7 関数適用
関数適用では引数を順に先行評価してから関数を簡約する。
call ::= factor { ’(’ [ { expression ’,’ } expression ] ’)’ }
2.7.8 式の要素
factor ::= function | integer | decimal | boolean | string | ident | ’(’ expression ’)’
2.7.9 関数定義
function ::= ’(’ [ { ident ’,’ } ident ] ’)’ ’=>’ expression
2.7.10 整数値
integer ::= digit {digit}
2.7.11 実数値
decimal ::= (digit {digit} ’.’ | ’.’ digit) {digit}
2.7.12 真偽値
boolean ::= ’true’ | ’false’
2.7.13 文字列
string
2.8
::= ’"’ {char} ’"’
関数
2.8.1 無名関数
nano の関数は自らの名前を持たない無名関数である。
2.8.2 参照透過
nano の関数は同じ引数を与えれば必ず同じ値を返す。
2.9
スコープ
nano は静的スコープであり、識別子は構文上の包含関係によって解決される。
3
実行環境の実装
3.1
概要
実行環境としてスタックマシンを実装する。使用したプログラミング言語は Scala である。
4
3.2
特徴
nano は関数が第一級であると同時に、全ての名前がコンパイル時に解決される。従って、関数が引数
や返り値として外部に持ち出される場合でも、その関数が定義された環境への参照は失われない。
((a) => (b) => a + b)(1)(2)
関数の呼び出しが終了すると同時にスタック上から環境が除去される通常の実装では、定義時の環境は
永久に失われる。高階関数に対応するためには、環境の本体はヒープで保管し、スタックには環境への
参照のみを配置することにより環境の永続性を保証する必要がある。関数は、自身が評価された時点で
最も内側にある環境、すなわちスタックのトップから参照されている環境を記憶する。関数を適用する
際には、関数が記憶している環境を親に持つ環境を生成してスタックに積むことで、環境の包含関係を
構築する。これにより、名前はコンパイル時に解決しつつ、環境を動的に持ち出せる関数を実現する。
3.3
環境
環境は関数を呼び出す際に、その関数が生まれた時点での環境を親にして生成される。
class Env ( val args : Seq [ Any ] = null , val 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 )
}
}
3.4
第一級関数
第一級関数は、関数定義の開始部分への参照と、その関数が生成された時点での環境を持つ。
case class Closure ( from : Int , enclosure : Env )
3.5
スタック
環境の操作を容易にする都合上、環境と演算のスタックを分けて実装する。
class Stack {
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 pop = valStack . pop
def ret = envStack . pop
def env = envStack . head
}
5
3.6
本体
スタックマシンの本体は単なる繰り返しであり、その度に命令を呼び出している。
object VM {
def exec ( codes : Seq [ nano . code . Code ]): Any = {
val stack = new Stack ()
var pc = 0
while ( pc < codes . size ) {
pc = codes ( pc ). exec ( stack , pc )
}
stack . pop
}
}
3.7
命令
命令は、スタックと自身の命令アドレスを渡されて演算を行い、次に実行すべき命令アドレスを返す。
package nano . code
trait Code {
def exec ( stack : Stack , pc : Int ): Int
}
3.7.1 二項演算命令
スタックから値を 2 個取り出して演算し、結果をスタックに戻す命令である。
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 Exception ( s " $ { a } $ { op } $ { b } " )
}
この抽象クラスを継承して各命令を実装する。加算命令の例を示す。
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 ) = > throw error (a , b )
}
}
動的型付けに基づく型チェックはこの apply メソッド内部で行われる。
6
3.7.2 スタック操作命令
Push 命令は即値をスタックに積む命令である。
case class Push ( value : Any ) extends Code {
def exec ( stack : Stack , pc : Int ): Int = {
stack . push ( value )
pc + 1
}
}
Load 命令は環境に保管されている値を取り出してスタックに積む命令である。
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
}
}
nest は環境のネスト回数で、id は環境内での識別番号である。
3.7.3 関数適用
直前に計算してスタックに格納した実引数を回収し、第一級関数もスタックから回収して、その関数が
生成された時点での環境を親に持つ環境を生成してスタックに格納する。関数の適用が完了した際には
元の地点に復帰する必要があるため直後の命令アドレスもスタックに退避しておく。最後に関数定義の
開始位置にジャンプする。当然ではあるが、スタックに積まれた実引数を順に取り出すと評価順と逆に
なるため、環境に格納する際に順番を並べ直している。
case class Call ( argc : Int ) extends Code {
def exec ( stack : Stack , pc : Int ): Int = {
val args = new Array [ Any ]( argc )
for ( i <- 1 to n ) ret ( argc - i ) = stack . pop
val func = stack . pop . asInstanceOf [ Closure ]
stack . push ( pc + 1)
stack . push ( new Env ( args , func . enclosure ))
func . from
}
}
関数から戻る際には Ret 命令が実行され、スタックに退避されていた命令アドレスにジャンプする。
case class Ret () extends Code {
def exec ( stack : Stack , pc : Int ): Int = {
stack . ret
val value = stack . pop
val jmpto = stack . pop . asInstanceOf [ Int ]
stack . push ( value )
jmpto
}
}
命令アドレスを取り出す際に、返り値も一緒に取り出してしまうので、スタックに積み直している。
7
3.7.4 第一級関数
関数の定義開始位置と現在の環境への参照をコピーした関数をスタックに積む命令である。
case class Func ( offset : Int ) extends Code {
def exec ( stack : Stack , pc : Int ): Int = {
stack . push ( Closure ( pc + offset , stack . env ))
pc + 1
}
}
3.7.5 分岐命令
Jmp 命令は無条件分岐命令で、指定された命令アドレスにジャンプする。
case class Jmp ( offset : Int ) extends Code {
def exec ( stack : Stack , pc : Int ): Int = pc + offset
}
Jmpf 命令は条件分岐命令で、スタックから取り出した値が false ならジャンプする。
case class Jmpf ( offset : Int ) extends Code {
def exec ( stack : Stack , pc : Int ): Int = stack . pop match {
case true = > pc + 1
case false = > pc + offset
case _ = > throw new C las sC as tE xc epti on ( " not boolean " )
}
}
4
コンパイラの実装
4.1
概要
実装したスタックマシンで動作する中間言語へのコンパイラを Scala で実装する。
4.2
型理論
言語の実装ではまず型理論の設計が重視される。今回は動的型付けとすることで詳細な実装を見送った。
4.3
構文木
構文解析器を実装する前に、まず構文木を設計し、併せて中間言語への変換処理も実装する。
trait AST { def gen ( implicit env : Func ): List [ Code ]}
変換処理を記述する gen メソッドに渡される暗黙の引数 env は最も内側の環境を形成する関数である。
4.3.1 式木
プログラムの全ての構成要素が式であるため必須ではないが式木を定義する。
trait Expr extends AST
8
4.3.2 関数
関数を中間言語命令列に変換すると、まず関数の内容の命令列が並び、次に Ret 命令が続く。冒頭の
Jmp 命令は関数の内容の命令列を飛ばして Func 命令までジャンプする命令である。これは関数定義が
評価され、第一級関数に変換される際に、誤って関数の内容が実行されるのを防ぐために挿入される
ヘッダ部である。関数定義はそれ自体がスコープを形成するため、構文木は外側の関数への参照を持つ。
case class Func ( pars : Seq [ Id ] , body : Expr ) extends Expr {
var enclosure : Func = null
def gen ( implicit env : Func ): List [ Code ] = {
this . enclosure = env
val code = body . gen ( this )
nano . code . Jmp (1 + code . size + 1) +:
code :+
nano . code . Ret () :+
nano . code . Func ( -1 - code . size )
}
}
4.3.3 識別子
識別子は自らが参照する引数を探索するため、スコープを下から上まで順繰りに辿る。該当する宣言が
見つかった場合は、スコープのネスト回数とスコープ内での識別番号を指定して Load 命令を発行する。
case class Id ( id : String ) extends Expr {
def gen ( implicit env : Func ): List [ Code ] = {
var nest = 0
var scope = env
while ( scope != null ) {
val i = scope . pars . indexOf ( this )
if ( i >= 0) return List ( Load ( nest , i ))
nest += 1
scope = scope . enclosure
}
throw new Exception ( s " ’$ { id } ’ not found " )
}
}
該当する宣言が見つからなかった場合にはコンパイルエラーを発行する。
4.3.4 二項演算子
二項演算子では先に被演算子を評価してスタックに格納してから、演算を行う。加算演算子の例を示す。
case class Add ( expr1 : AST , expr2 : AST ) extends Expr {
def gen ( implicit env : Func ): List [ Code ] = {
expr1 . gen ++
expr2 . gen :+
nano . code . Add ()
}
}
9
4.3.5 定数
定数の構文木は Push 命令を発行する。
case class Lit ( value : Any ) extends Expr {
def gen ( implicit env : Func ) = List (
nano . code . Push ( value )
)
}
4.3.6 関数適用
引数を順に評価してから Call 命令を実行するような命令列を発行する。
case class Call ( func : AST , args : Seq [ AST ]) extends Expr {
def gen ( implicit env : Func ): List [ Code ] = {
func . gen ++
args . map ( _ . gen ). fold ( List ())( _ ++ _ ) :+
nano . code . Call ( args . size )
}
}
4.3.7 条件分岐
if 式の構文木が生成する中間言語命令列はジャンプ命令を含む。まず条件式を評価し、その結果が
true ならば後続の式を評価してから脱出する。false の場合は else 節までジャンプして評価する。
case class If ( cond : AST , yes : AST , no : AST ) extends Expr {
def gen ( implicit env : Func ): List [ Code ] = {
val (c , y , n ) = ( cond . gen , yes . gen , no . gen )
( c :+ nano . code . Jmpf (2 + y . size )) ++
( y :+ nano . code . Jmp (1 + n . size )) ++ n
}
}
4.4
パーサー
小さな構文規則をパーサーコンビネータで組み合わせてパーサーを実装する。
object Parser extends util . parsing . combinator . JavaTokenParsers {
def parse ( str : String ): AST = parseAll ( expr , str ) match {
case Success ( result , _ ) = > result
case failure : NoSuccess = > throw new Exception ( failure . msg )
}
}
ここに各節に掲載するような構文規則を追加していく。
4.4.1 式
def expr : Parser [ Expr ] = cond | or
10
4.4.2 条件分岐
def cond : Parser [ Expr ] = " if " ~ " ( " ~ > expr ~ " ) " ~ expr ~ " else " ~ expr ^^{
case c ~ _ ~ yes ~ _ ~ no = > If (c , yes , no )
}
4.4.3 論理演算
def or : Parser [ Expr ] = chainl1 ( and ,
" | " ^^( op = > ( l : Expr , r : Expr ) = > Or (l , r )))
def and : Parser [ Expr ] = chainl1 ( eq ,
" & " ^^( op = > ( l : Expr , r : Expr ) = > And (l , r )))
4.4.4 等値比較
Ge (l ,
Le (l ,
Gt (l ,
Lt (l ,
r ))|
r ))|
r ))|
r )))
chainl1 ( unary ,
r : Expr ) = > Mul (l , r ))|
r : Expr ) = > Div (l , r ))|
r : Expr ) = > Mod (l , r )))
4.4.7 単項演算
def add : Parser [ Expr ] = chainl1 ( mul ,
" + " ^^( op = > ( l : Expr , r : Expr ) = > Add (l , r ))|
" -" ^^( op = > ( l : Expr , r : Expr ) = > Sub (l , r )))
def mul : Parser [ Expr ] =
" * " ^^( op = > ( l : Expr ,
" / " ^^( op = > ( l : Expr ,
" % " ^^( op = > ( l : Expr ,
def rel : Parser [ Expr ] = chainl1 ( add ,
" >= " ^^( op = > ( l : Expr , r : Expr ) = >
" <= " ^^( op = > ( l : Expr , r : Expr ) = >
" >" ^^( op = > ( l : Expr , r : Expr ) = >
" <" ^^( op = > ( l : Expr , r : Expr ) = >
4.4.6 四則演算
def eq : Parser [ Expr ] = chainl1 ( rel ,
" == " ^^( op = > ( l : Expr , r : Expr ) = > Eq (l , r ))|
" != " ^^( op = > ( l : Expr , r : Expr ) = > Ne (l , r )))
4.4.5 算術比較
def unary : Parser [ Expr ] = ( " + " | " -" | " ! " )~ unary ^^{
case " + " ~ u = > Add ( Lit (0) , u )
case " -" ~ u = > Sub ( Lit (0) , u )
case " ! " ~ u = > Ne ( Lit ( true ) , u )
}| call
11
4.4.8 関数適用
def call : Parser [ Expr ] = fact ~ rep ( " ( " ~ > args <~ " ) " )^^{
case p ~ Nil = > p
case p ~ apps = > apps . foldLeft ( p )( Call (_ , _ ))
}
def args : Parser [ Seq [ Expr ]] = repsep ( expr , " ," )
4.4.9 式の要素
def fact : Parser [ Expr ] = func | atom | " ( " ~ > expr <~ " ) "
4.4.10 関数定義
def func : Parser [ Expr ] = ( " ( " ~ > pars <~ " ) " )~ " = > " ~ expr ^^{
case p ~ _ ~ e = > Func (p , e )
}
def pars : Parser [ Seq [ Id ]] = repsep ( id , " ," )
4.4.11 リテラル
def atom : Parser [ Expr ] = num | str | bool | id
5
REPL の実装
以上で仮想マシンとコンパイラの実装が完了したが、頒布版では加えて REPL を実装してある。
6
無名再帰
nano の関数は無名なので無名再帰問題に直面するが、Z コンビネータを用いて回避できる。
((f)=>
((f)=>
((f)=>
((f)=>
((f)=>
((f)=>
((f)=>
((f)=>
((x)=>
((x)=>
((x)=>
((x)=>
((x)=>
((x)=>
((x)=>
((x)=>
f((y)=>
f((y)=>
f((y)=>
f((y)=>
f((y)=>
f((y)=>
f((y)=>
f((y)=>
7
おわりに
x(x)(y)))((x)=>
x(x)(y)))((x)=>
x(x)(y)))((x)=>
x(x)(y)))((x)=>
x(x)(y)))((x)=>
x(x)(y)))((x)=>
x(x)(y)))((x)=>
x(x)(y)))((x)=>
f((y)=>
f((y)=>
f((y)=>
f((y)=>
f((y)=>
f((y)=>
f((y)=>
f((y)=>
x(x)(y))))((f)=>
x(x)(y))))((f)=>
x(x)(y))))((f)=>
x(x)(y))))((f)=>
x(x)(y))))((f)=>
x(x)(y))))((f)=>
x(x)(y))))((f)=>
x(x)(y))))((f)=>
(n)=>
(n)=>
(n)=>
(n)=>
(n)=>
(n)=>
(n)=>
(n)=>
if(n
if(n
if(n
if(n
if(n
if(n
if(n
if(n
==
==
==
==
==
==
==
==
nano 処理系のソースコード一式はレポジトリから入手可能である。
$ git clone git://pafelog.net/git/nano
12
0)
0)
0)
0)
0)
0)
0)
0)
1
1
1
1
1
1
1
1
else
else
else
else
else
else
else
else
n
n
n
n
n
n
n
n
*
*
*
*
*
*
*
*
f(n
f(n
f(n
f(n
f(n
f(n
f(n
f(n
-
1))(1)
1))(2)
1))(3)
1))(4)
1))(5)
1))(6)
1))(7)
1))(8)
=
=
=
=
=
=
=
=
1
2
6
24
120
720
5040
40320