# 代数的データ型とBNFで妄想するプログラミング言語2
代数的データ型とBNFで妄想するプログラミング言語2
はじめに
昨日はザーッとBNFを書いていく方法を書いてみました。 しかし成果物をみるとちゃんとした仕様書とは言えないものができてしまったように思います。 今日は昨日の成果をもとに仕様のみを抜き出して書いていこうと思います。 言語仕様は全体的な構文と機能ごとの追加構文、例、説明で構成することにします。
1. 整数
構文:
e ::= 式
i 整数
1. 整数
構文:
e ::= 式
i 整数
例:
0 123 456789
整数は0から9までの文字の連続です。
2. 足し算
構文:
e ::= 式
i 整数
e+e 足し算
2. 足し算
構文:
e+e 足し算
整数は0から9までの文字の連続です。
例:
1+2 123+456+789
足し算は２項演算子 + で結合された式で、いくつも連続して書くことができます。
3. その他の四則演算
足し算とその他の四則演算を１つにまとめてしまいます。
構文:
e ::= 式
i 整数
e+e 足し算
e-e 引き算
e*e 掛け算
e/e 割り算
2. 四則演算
構文:
e ::= 式
:
e+e 足し算
e-e 引き算
e*e 掛け算
e/e 割り算
例:
1+2 1-2 1*2 1/2
足し算は２項演算子 + で結合された式で、いくつも連続して書くことができます。
引き算は二項演算子 -、掛け算は二項演算子 *、割り算は二項演算子/を使って結合された式として表せます。
4. Bool
構文:
b ::= bool
true 真
false 儀
e ::= 式
i 整数
b bool
e+e 足し算
e-e 引き算
e*e 掛け算
e/e 割り算
3. Bool
構文:
b ::= bool
true 真
false 儀
e ::= 式
:
b bool
例:
true false
bool は trueとfalseからなります。
5. if式
構文:
b ::= bool
true 真
false 儀
e ::= 式
i 整数
b bool
e+e 足し算
e-e 引き算
e*e 掛け算
e/e 割り算
if e then e else e if式
4. if式
構文:
e ::= 式
:
if e then e else e if式
例:
if true then 1 else 2 (if true then 1 else 2) + 3
if は式なので結果を返し他の式の中に書くことができます。
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式
5. 比較演算子
構文:
e ::= 式
:
e<e 比較演算子
例:
1 < 2 2 < 3
比較式は比較演算子< で結合された式です。
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 関数適用
6. 変数、関数、関数適用
構文:
e ::= 式
:
x 変数
λ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)
変数はアルファベットで始まる識別子で表されます。 関数はラムダ抽象を使って書き引数は１つしか使えませんが、関数を連続して書くことで複数の引数がある処理も行うことができます。 関数呼び出しは式を２つ並べた形になります。
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式
7. let式、let rec式
構文:
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式と同様に用いることができます。再帰呼び出しをする関数を定義するような場合に用います。
9. 仕様のまとめ
最後に、全体をまとめて１つの仕様としましょう。
言語仕様
構文:
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式
1. 整数
構文:
e ::= 式
i 整数
例:
0 123 456789
整数は0から9までの文字の連続です。
2. 四則演算
構文:
e ::= 式
:
e+e 足し算
e-e 引き算
e*e 掛け算
e/e 割り算
例:
1+2 1-2 1*2 1/2
足し算は２項演算子 + で結合された式で、いくつも連続して書くことができます。
引き算は二項演算子 -、掛け算は二項演算子 *、割り算は二項演算子/を使って結合された式として表せます。
3. Bool
構文:
b ::= bool
true 真
false 儀
e ::= 式
:
b bool
例:
true false
bool は trueとfalseからなります。
4. if式
構文:
e ::= 式
:
if e then e else e if式
例:
if true then 1 else 2 (if true then 1 else 2) + 3
if は式なので結果を返し他の式の中に書くことができます。
5. 比較演算子
構文:
e ::= 式
:
e<e 比較演算子
例:
1 < 2 2 < 3
比較式は比較演算子< で結合された式です。
6. 変数、関数、関数適用
構文:
e ::= 式
:
x 変数
λ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)
変数はアルファベットで始まる識別子で表されます。 関数はラムダ抽象を使って書き引数は１つしか使えませんが、関数を連続して書くことで複数の引数がある処理も行うことができます。 関数呼び出しは式を２つ並べた形になります。
7. let式、let rec式
構文:
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式と同様に用いることができます。再帰呼び出しをする関数を定義するような場合に用います。
10. まとめ
ここでは、fib関数を書ける言語を妄想してみたものを元に、言語仕様飲みに集中して順番に書いてみました。 最初は順番に１つの機能ごとに書いて最後にまとめて１つの仕様としました。 いきなり大きな仕様を書くのではなく徐々に大きく育てていく楽しさがあります。 慣れてしまえば、Rustのような処理系を使わずとも仕様を簡単に素早く書けるようになるはずです。
