Scheme R7RSの形式意味論を読んでいく3
続きです
前回の続きとなります。
Scheme R7RSの形式意味論を読んでいく2 - nptclのブログ
7.2.3. Semantic functions
意味関数はSchemeの中核です。
式を受け取りどのように実行するかを表します。
意味関数は次のような型になります。
簡単に説明します。
は、1つの引数を受け取り、を返却する関数です。
目的は定数をに変換することです。
は、4つの引数を受け取り、
を返却する関数です。
この関数がSchemeの本体と言ってもいいほど重要なものです。
は、4つの引数を受け取り、
を返却する関数です。
目的は関数呼び出し時の全要素を評価するときに使われます。
は、4つの引数を受け取り、
を返却する関数です。
この関数は、返却値が無視できる式の評価を行う時に使用します。
具体的に言うと、lambda式のbody部の最後以外の式です。
この4つの関数は特殊であり、例えば次のような定義がされます。
他にも
のような定義がたくさんあります。
ここに現れる関数は、引数の数が4つではなく3つであることに注意して下さい。
もし
のように実行された場合は、
のように関数が呼び出されたかのようにふるまい、
さらに第一引数のの形式によって呼ばれる関数が分岐します。
例えばがであった場合は、
で宣言された関数が呼び出されることになります。
とは、を評価するという意味です。
評価とは、eval
のことです。
評価の例を見てみましょう。
引数の100は定数なので、が呼ばれます。
次の例を見てみます。
引数はlambda式なので、 が呼ばれます。
ではの定義を全部見て行きましょう。
定義を示します。
は定数なので、で定数を評価したときの振る舞いになります。
例えばこんな感じです。
では内容を見て行きます。
まずですが、
仕様書にの定義は面倒なので省略しますと書かれています。
難しいものではなく、受け取った定数を、
何とかしてにして返却するというものです。
処理系を作る人が適当に作ってくださいね、ということなのでしょう。
仮にの値がだとしたとき、
になります。
この関数の引数はの3つあるのですが、
今はしか使っていません。
の引数の形式が決まっているため、自由に変更できないのです。
sendの定義は前に説明しましたが再掲します。
内容のというのは、 を列 にして、継続を呼び出すということです。
例えばの場合を考えます。
の結果をとした場合、
の実行は
になります。
つまりは継続を引数で
呼び出すということになります。
Schemeで考えれば分かりますが、100
と書かれたら
継続に100
を渡すということです。
そのままですね。
sendの存在意義は、たった1つの値を継続に渡すことです。
継続の関数であるは、引数に列を受け取る関数です。
つまり
みたいな呼び出し方ができます。
もしたった1つだけ値を継続に渡したいなら、
つまりみたいになるのですが、
それをsendという関数で実現したということです。
定義を示します。
は
変数が評価されたときの処理です。
は型なので、つまりは変数です。
いろいろと説明されてない関数があります。
lookup, single, wrong, holdくらいでしょうか。
ちゃんと説明して行きます。
lookup関数は、変数の表から位置を取得します。
第1引数が変数表、第2引数が変数である、返却値が位置です。
引数とを受け取り、
実行がだと何の意味があるんだという話になりますが、
lookup関数を使うことで、索引からアドレスを引いているんですよ、
分かりやすくするためなのかもしれません。
実行部のは、
関数を引数で呼び出すという処理です。
さて問題はsingleです。
定義は下記の通り。
何が問題なのかはすでに説明しました。
「暗黙のlambda式」に該当するので、次のように書き換えられます。
変更点は「」の部分を 「」にしただけです。
single関数は1つの引数を関数として受け取ります。
受け取る関数は、ひとつの引数を列として受け取ります。
この列は継続の値そのものの列であるvalues
だと思います。
もしの長さが1だったら、その要素を引数に関数を呼び出して返却しますが、
もしの長さが1では無かったらwrongでエラーになります。
型から考えるなら、関数の戻り値は継続のようです。
holdは非常に問題がある関数です。
まずは定義から。
引数の数が一致してないので、暗黙のlambda式になっています。
つまり次のように書き直します。
send関数の引数の個数は2つということを考慮すると、 次のようになります。
邪魔なのでを消してしまいましょう。
ここで気にして欲しいのは、が残るということです。
は位置なので、値を取り出すには、
メモリが必要です。
何らかの形で、どうしてもは必要になるのです。
hold関数は全体的におかしかったため、
暗黙のlambda式でを消してしまいましたが、
本来であればは引数に必要です。
しかしhold関数に引数を追加した所で、
全体的に作りがを渡せるように設計されていないのです。
引数にが無いと、
後から説明するの
ローカル変数の値を取り出せません。
どうしようもないので、
処理系実装者は適切なをどうにかして持ってきて下さい。
単純にグローバル変数にしてもダメです。
仕様書を全体で見ると、の扱いはいつもなんかおかしいです。
実装する人はちゃんと考えて下さい。
そうじゃない人は適当に注意して下さい。
関数holdを改めて解説しますが、
まずは位置と継続を受け取ります。
位置というのはポインタです。
メモリを位置で呼び出すと、
その位置にある情報が次のような列になって取得できます。
第1要素の「value」が欲しいので、により
「value」を取得します。
send関数は「value」と継続を引数の実行されますので、
単純に継続が「value」という値で呼び出されます。
まとめますと「位置にある値を継続に渡す」。
定義を示します。
この関数の内容は、関数をただ呼んでいるだけです。
しかしの第1引数と第4引数には色々手を加えているのが分かります。
まず注目したいのは、とは、
それぞれ要素と列を表していることです。
さらに、実行内容を見ると、であったり、
, の記号があります。
前に少し余談として出しましたが、
(car ε*)
は、
(cdr ε*)
は、
(cons E0 E*)
は、
とみなすことができるます。
Lispの考え方が出来るのであれば、
たぶん列を再帰処理していくんだろうなあ、と予想することができます。
まだ説明していない関数は下記の通り。
- permute
- unpermute
- applicate
それでは、それぞれを見て行きましょう。
これらの関数は並べ替えをするためのものです。
処理系実装者であるあなたが自由に作成する関数です。
よくわかんなかったら、引数をそのまま返却してください。
Schemeの関数が呼び出されるとき、各要素の評価順は決まっていません。
これはCommon Lispとは違っている部分です。
その評価順を変更するための関数が、
permuteとunpermuteになります。
Common Lispであれば、(aaa 10 20 30)
という
関数呼び出しがあったとしたら、
10
が評価され、20
, 30
と順番に評価した後に
関数aaa
が呼び出されるのですが、
Schemeでは順番は未定です。
最初に20
が評価されるかもしれませんし、そうじゃないかもしれません。
それを分かってもらおうとしてpermuteとunpermuteが制定されたとのこと。
面倒なら引数をそのまま返却するという実装でいいと思います。
この関数は、関数を表すを実行するという処理です。
まず引数が4つもあります。
とはいってもは実行に必要なものなので
ただのたらいまわしです。
第1引数のはであり、第2引数のは引数の列です。
はいわゆる関数オブジェクトですが、
形式意味論でそのまま使える関数ではなく、
内容はの列です。
処理の内容を見て行きましょう。
まずはで、第1引数がかどうかの確認を行います。
もしじゃなかったらエラーが出て終わりです。
はどういう意味かというと、
はの列であるため、
その第2要素である関数を取り出すということです。
取り出した関数は、引数を引数にして呼び出されます。
の説明に戻ります。
第1引数で実行されるpermuteは、要素の順番を変えるだけです。
面倒なら無視していいと思います。
4つ目の引数である
は少し複雑に見えます。
lambda式が2つあることに注意してください。
あと、どちらのlambda式の引数もになっているので分かりづらいです。
こんな感じに変えてしまうことができます。
Schemeっぽく書き換えると次のようになります。
(lambda (e1) (let ((e2 (unpermute e1))) (applicate (↓ e2 1) († e2 1) ω κ)))
2つ目のlambdaをletにしてしまいました。
第一引数はこっちの計算の都合でpermuteを使って並び替えをしたのだから、
第四引数の継続内ではunpermuteを使ってちゃんと元の並び順に戻しましょうね、
という意味です。
参考までにpermuteを使用しない定義を示します。
それでは、を見て行きましょう。
呼び出される関数はとは別物なので、
ちゃんと定義を見て行かなければなりません。
は何をするのかというと、
関数呼び出しのカッコの中を再帰呼出で評価するというものです。
例えば
(list 10 20 30)
という関数呼び出しのリストがあった場合は、
それを先頭から順番に評価していきます。
でもSchemeは関数の呼び出し順序は不定なんじゃ?
というときのためのpermuteであって、
(30 20 10 list)
とか
(list 30 20 10)
みたいに好きに並び順を変えればいいのです。
もうめちゃくちゃに変えたっていいですけど、
ちゃんとunpermuteで元に戻せるようにして下さい。
は、列の全ての要素を、単純に評価していくだけです。
それでは定義を見て行きましょう。
この定義は再帰呼出の最後に使われるものです。
何もない場合は、継続に長さ0の列を渡します。
どんどん行きたい所ですが、lambda式が3つもありますね。
この関数は、つまりはを評価するために、
を実行しているだけです。
は3つの引数を取る関数なので、
引数にとと、そして関数である継続を渡しています。
継続は次の文で作られます。
singleは、継続からひとつの値をとりだす関数です。
その値はに渡されます。
返却値もまた継続になります。
singleの引数である
は何なのかというと、 残りの列であるを再帰処理に渡して、 すでに評価したの値を、 継続内で結合して返却するというものです。
もっと分かりやすく言うとmap関数です。
とは、再帰処理を使ってmap関数をやっています。
例えば入力の値が
であった場合、は次のようになります。
ただそれだけです。
よくある再帰関数なので、まあまあ理解しやすいと思います。
この辺りまで見ると、評価には常に継続があり、
変数の返却は当たり前のように継続に渡されていることが分かりました。
そりゃSchemeなんだからそんなもんだろうと思ってはいましたが、
ここまでちゃんと書かれていると作る方は楽だと思います。
続きます
次の投稿に続きます。
Scheme R7RSの形式意味論を読んでいく4 - nptclのブログ