関数定義・適用を追加しよう

構文解析

関数定義の文法も言語によって様々ですが、一例として次のような文法とします。

def add(a,b)=a+b;

そして関数適用は次のような文法です。

add(2,3)

それでは、この文法をpeg.jsで書いてみましょう。関数定義は、変数定義と、足し算を参考にすれば書けるでしょう。

ASTは、関数名、引数名の配列、関数内で処理する式、関数定義後の式(変数定義のASTを参照)を持つようにすると良いでしょう。

関数適用は、Factorに追加すると良いでしょう。この時、変数の使用の文法の影響に注意して実装しましょう。

関数定義、関数適用の評価について、まず色々な場合を見てどのように実装するのが良いか考えていきましょう。

let a=1;
a+1

これは変数定義・変数使用の場合です。let a=1;が評価されると、envが空の状態から{a: 1}となるのでした。

def add(a,b)=a+b;
add(2,3)

これは関数定義・関数適用の場合です。関数定義の場合にもenvにaddと関連する｢何か」を追加しなくてはなりませんが、何を追加するべきでしょう？

関数適用した時に正しく評価できるよう、関数の引数名のリストと関数本体をenvに持っておく必要があります。つまり、def add(a,b)=a+b;が実行された時のenvは、{add: {args: ["a", "b"], body: (a+bのAST)}}のようにすれば良いです。

関数適用のときは、変数の使用と同じように環境から関数名の変数を取り出した後、関数本体を評価するために、引数名と引数の対応を環境に追加しておかなくてはなりません。上のadd(2,3)の場合であれば、環境に{a: 2, b: 3}の対応関係を追加した後、関数本体を評価すればいいでしょう。

...本当にそれで大丈夫でしょうか？上の素朴な実装で上手くいかない例を考えてみましょう。

上手く行かない例

let n=1;
def succ(n)=n+1;
succ(3)+n

私達の予想に反して、このプログラムは7と評価されます。

これは、succによってnが書き換えられてしまっているためです。つまり、関数適用の評価が終わった後に、関数適用前の環境を復元する必要があります。

envをコピーするには次のようにすると良いでしょう。

const copyenv = JSON.parse(JSON.stringify(env))

少々技巧的ですが、これはenvをディープコピーするためです。

上手く行かない例を参考に、より正しい実装をしてみましょう。

実装をし終えたら、次のプログラムを動かしてみましょう。(文法を自分好みに変えている人は適宜変更してください！)

def fib(n)=if n==1 then 1 else if n==2 then 1 else fib(n-1)+fib(n-2);
fib(10)

55と表示されましたか？表示されれば成功です。お疲れ様でした。自分好みに機能をさらに追加してみましょう！