代数的データ型とBNFで妄想するプログラミング言語
代数的データ型とBNFで妄想するプログラミング言語
はじめに
BNFってなんだか難しそうって思う方もおられると思いますがそんなに気構えずに楽しく書く気持ちを説明したいと思います。 BNFは狭義の意味ではバッカスナウア記法を用いた構文解析器を表す記法になりますが、ここで用いるBNFは木構造データに対するBNF記法です。 通常は抽象構文用いて定義する代数的データ型を、具象構文をつかって定義するようなものと考えることもできます。
これ以降の章では例とRustのenum、BNFによる構文を書き説明する形で言語の仕様を拡張していきます。 最終目標はλ計算でfib関数を書ける言語を作ることです。
1. 整数
例:
0 123 456789
整数は0から9までの文字の連続です。
Rust:
enum E { // 式 I(i32), // 整数 }
Rustで式に整数だけ使える言語を考えるとenumを使って上記のように書くことができます。
構文:
e ::= 式
i 整数
BNFライクに書くと上記のように書くことができます。
2. 足し算
例:
1+2 123+456+789
足し算は２項演算子 + で結合された式で、いくつも連続して書くことができます。
Rust:
type e = Box<E>; enum E { // 式 I(i32), // 整数 Add(e,e) // 足し算 }
Rustで再帰的に型を使いたい場合にデータサイズがわからなくなるので困ります。そういった場合はBoxなどで再帰的な型を使うことができます。
Box<E> のように書くのは長くなるので小文字のeを Box<E> として使うことにしました。
構文:
e ::= 式
i 整数
e+e 足し算
BNF で書く場合は型のサイズなどを気にせずに以上のように書くことができます。
3. その他の四則演算
例:
1+2 1-2 1*2 1/2
引き算は二項演算子 -、掛け算は二項演算子 *、割り算は二項演算子/を使って結合された式として表せます。
Rust:
type e = Box<E>; enum E { // 式 I(i32), // 整数 Add(e,e), // 足し算 Sub(e,e), // 引き算 Mul(e,e), // 掛け算 Div(e,e), // 割り算 }
Rustならコンパイルしておかしな定義になっていないことが確認できます。
構文:
e ::= 式
i 整数
e+e 足し算
e-e 引き算
e*e 掛け算
e/e 割り算
BNF で書くとASTというよりも唯の構文のイメージになるので簡単です。
4. Bool
例:
true false
Rust:
type e = Box<E>; enum E { // 式 I(i32), // 整数 B(bool), // Bool Add(e,e), // 足し算 Sub(e,e), // 引き算 Mul(e,e), // 掛け算 Div(e,e), // 割り算 }
構文:
b ::= bool
true 真
false 儀
e ::= 式
i 整数
b bool
e+e 足し算
e-e 引き算
e*e 掛け算
e/e 割り算
bはboolだと書けば分かる話ではありますが、BNFで書く場合はbがboolでありtrueとfalseからなると明示すると良いかもしれません。
RustでBoolを明示するなら以下のように書くことができます:
type e = Box<E>; enum B { // Bool True, // 真 False, // 儀 } enum E { // 式 I(i32), // 整数 B(B), // Bool Add(e,e), // 足し算 Sub(e,e), // 引き算 Mul(e,e), // 掛け算 Div(e,e), // 割り算 }
5. if式
ここからは順番を構文、例、Rustにしていきます。
構文:
b ::= bool
true 真
false 儀
e ::= 式
i 整数
b bool
e+e 足し算
e-e 引き算
e*e 掛け算
e/e 割り算
if e then e else e if式
if式 は if e1 then e2 else e3 のような式でe1がtrueならばe2が評価されそうでなければe2が評価される式です。
例:
if true then 1 else 2 (if true then 1 else 2) + 3
if は式なので結果を返し他の式の中に書くことができます。
Rust:
type e = Box<E>; enum B { // Bool True, // 真 False, // 儀 } enum E { // 式 I(i32), // 整数 B(B), // Bool Add(e,e), // 足し算 Sub(e,e), // 引き算 Mul(e,e), // 掛け算 Div(e,e), // 割り算 If(e,e,e), // if式 }
RustだとthenやelseはないASTになります。
6. 比較演算子
構文:
b ::= bool
true 真
false 儀
e ::= 式
i 整数
b bool
e+e 足し算
e-e 引き算
e*e 掛け算
e/e 割り算
e<e 比較演算子
if e then e else e if式
例:
1 < 2 2 < 3
比較式は比較演算子< で結合された式です。
Rust:
type e = Box<E>; enum B { // Bool True, // 真 False, // 儀 } enum E { // 式 I(i32), // 整数 B(B), // Bool Add(e,e), // 足し算 Sub(e,e), // 引き算 Mul(e,e), // 掛け算 Div(e,e), // 割り算 Le(e,e), // 比較演算子 If(e,e,e), // if式 }
7. 変数、関数、関数適用
構文:
b ::= bool
true 真
false 儀
e ::= 式
i 整数
b bool
x 変数
e+e 足し算
e-e 引き算
e*e 掛け算
e/e 割り算
e<e 比較演算子
if e then e else e if式
λx.e 関数
e e 関数適用
例:
a abc123 x λa.a+1 λa.λb.a+b (λa.a+1) 10 (λa.λb.a+b) (1+2) (3+4)
変数はアルファベットで始まる識別子で表されます。 関数はラムダ抽象を使って書き引数は１つしか使えませんが、関数を連続して書くことで複数の引数がある処理も行うことができます。 関数呼び出しは式を２つ並べた形になります。
Rust:
type e = Box<E>; type x = String;//文字列 enum B { // Bool True, // 真 False, // 儀 } enum E { // 式 I(i32), // 整数 B(B), // Bool X(x), // 変数 Add(e,e), // 足し算 Sub(e,e), // 引き算 Mul(e,e), // 掛け算 Div(e,e), // 割り算 Le(e,e), // 比較演算子 If(e,e,e), // if式 Fun(x,e), // 関数 App(e,e), // 関数適用 }
そろそろ Rust 実装書かなくてもわかるだろう、、、と思いますが一応。
8. let式、let rec式
構文:
b ::= bool
true 真
false 儀
e ::= 式
i 整数
b bool
x 変数
e+e 足し算
e-e 引き算
e*e 掛け算
e/e 割り算
e<e 比較演算子
if e then e else e if式
λx.e 関数
e e 関数適用
let x = e in e let式
let rec x = e in e let rec式
例:
let a = 1+2 in let b = 2+3 in a+b let a = let a = 1+2 in let b = 2+3 in a+b in a+3 let rec fib = λx. if x<2 then x else fib (x-2) (x-1) in fib 10
let式は指揮を複数に分けて書くことができるようにできる式です。プログラムを分けて書けるようになるため便利です。 let式により変数に値を束縛できます。変数はin以降で使えるようになります。inより手前ではそれ以前に定義された変数が使われます。 同じ変数名で別な値を束縛するとそれ以降で見えなくなり、シャドウィングと言います。 let rec 式はinの手前でも変数を参照ができる点以外はlet式と同様に用いることができます。再帰呼び出しをする関数を定義するような場合に用います。
Rust:
type e = Box<E>; type x = String; // 文字列 enum B { // Bool True, // 真 False, // 儀 } enum E { // 式 I(i32), // 整数 B(B), // Bool X(x), // 変数 Add(e,e), // 足し算 Sub(e,e), // 引き算 Mul(e,e), // 掛け算 Div(e,e), // 割り算 Le(e,e), // 比較演算子 If(e,e,e), // if式 Fun(x,e), // 関数 App(e,e), // 関数適用 Let(x,e,e), // let式 LetRec(x,e,e), // let rec式 }
9. まとめ
ここでは、ゼロからラムダ計算でfib関数を書ける言語を妄想してみました。補助言語としてRustのenumを代数的データ型として使い確認もしました。 特にパーサや評価器は作っていませんが、このように妄想することでプログラミング言語の仕様を形式的な感じに書くことができます。 ラムダ計算の形式化は様々な書き方で定義されていますが、書いたことがない方は書いてみましょう。 慣れてくるとプログラミング言語の仕様を書くのが楽しくなるはずです。 最初は難しい、あるいは面倒に感じるかも知れませんが慣れれば楽しく言語を設計できるようになるので是非チャレンジしてみましょう。
