Scheme:初心者の質問箱

Scheme:初心者の質問箱

メーリングリストで質問したり、WiLiKiに自分のページを作ったりするのはちょっと… というシャイなあなたのためのスペースです。

あたらしい質問は、項目の先頭に追加していって下さい。

書き方を間違えても小人さんが直してくれるので、 こわがらなくてもだいじょうぶ。

長くなってきたので過去ログ:



while 内の唐突な代入について

累積関数 factorial

(define (factorial n)
  (if (<= n 1)
      1
      (* n (factorial (- n 1)))))

を while で書き直すことを考えると

(define (w-fac n)
  (let ((b 1))
    (while
     [> n 1]
     (set!-values (n b) (values (- n 1) (* n b))))
    b))

こんな感じになると思います。(末尾再帰化と似ている) これを、段階を細分化し

0: b に1を代入し

1: n が1か否かで処理を分け

2: n=1 でない場合は b:=n*b n:=n-1 として処理を続け

3: n=1 の場合は b を返す

という while でさらに書き換えます。 (u の値がおよそ上記の番号に当たる)

(define (w-fac2 n)
  (let ((u 0) (b 0))
    (while
     [< u 3]
     (cond ((= u 0)
            (set!-values (u n b) (values 1 n 1)))
           ((= u 1)
            (set!-values (u n b) (values (if (= n 1) 3 2) n b)))
           ((= u 2)
            (set!-values (u n b) (values 1 (- n 1) (* n b))))))
    b))

そしてこれからが本題なのですが、while に入る前に u だけでなく b の値も決めておかなければ実行時に「bが未定義シンボルだ」とエラーが出ます。(当たり前といえば当たり前ですが) while 前に代入(ではなく束縛ですが)するのは状態を判断して処理を振り分ける u だけで出来ないかと色々試してみました。

しかし、例えば u=0 の場合に

(define b 0)

としてみると「トップレベル以外で define は無理」とエラーになります。また、関数の引数も最初のもの(factorial)が1つなので、b をあらかじめ与えられるようにすると「同じ関数を while で書き換える」とは違うように思います。

Python などで

def w_fac2 (n) :
    u = 0
    while u < 3 :
        if u == 0 :
            u, n, b = 1, n, 1
        elif u == 1 :
            u, n, b = (lambda a: 3 if a == 1 else 2)(n), n, b
        else :
            u, n, b = 1, n -1, n * b
    return b

と、いきなり b に代入するようなことは、Scheme(Gauche) では無理なのでしょうか。 何となく出来たら出来たで恐ろしい気もしますが(バグが紛れ込みそう)、出来ないことを明確に知りたいと思います。 よろしくお願いします。

Gauche の、Racket との違いと評価順序について

一つ前の質問をした者です。齊藤さん、hamayamaさん、Shiroさん、丁寧なお答えを頂きありがとうございました。

call/cc について調べているとこの様なページを見つけました。 https://stackoverflow.com/questions/52807955/infinite-loop-while-using-call-with-current-continuation-in-scheme[

ちょっといじって

(define (f n)
  (let ((p (call/cc identity)))
    (sleep 1) ; 無限ループで分からなくならないように
    (display n)
    p))

((f #\newline) (f "*"))

とすると call/cc パズルhttps://practical-scheme.net/wiliki/wiliki.cgi?Scheme%3A%E4%BD%BF%E3%81%84%E3%81%9F%E3%81%84%E4%BA%BA%E3%81%AE%E3%81%9F%E3%82%81%E3%81%AE%E7%B6%99%E7%B6%9A%E5%85%A5%E9%96%80#H-2x6wuk[ と同じように、DrRacket では動きました。 が、Gauche で

(define (f n)
  (let ((p (call/cc identity)))
    (sys-sleep 1) ; 無限ループで分からなくならないように
    (display n)
    p))

((f #\newline) (f "*"))

とすると * -> 改行 -> 改行 -> * 改行 -> 改行 -> * …… となります。 何故かを考えますと、まず Racket ではおそらく

簡略のため、並列された上から順序で評価される式を -> で書いています

([let ((p (call/cc identity))) 改行->p] [let ((p (call/cc identity))) *->p]) ; ①
([let ((p k1)) 改行->p] [let ((p (call/cc identity))) *->p]) ; ② 継続 k1 が生成される(identity を引数に取っているため call/cc が返す値は継続そのもの)
改行 & (k1 [let ((p (call/cc identity))) *->p] ;③ k2 が生成される
(k1 [let ((p k2)) *->p]) ; ④
* & (k1 k2) ; ⑤
([let ((p k2)) 改行->p] [let ((p (call/cc identity))) *->p]) ; ⑥ k1 が生成された時点の ② の k1 に k2 が当て嵌められる
改行 & (k2 [let ((p k3)) *->p]) ; ⑦ k3 が生成される
* & (k2 k3) ; ⑧
(k1 [let ((p k3)) *->p]) ; ⑧
* & (k1 k3) ; ⑨
...

と、② 式(ただし kn の n の値は変わっていく)に戻る度に遡るためのステップが一つずつ増えていくことで * が改行前に一つずつ増えて表示されるのだと思います。 対して Gauche では最初に * が表示されることから被適用される前の式より、適用する後ろの式から評価されるのだと推測しました。すると

([let ((p (call/cc identity))) 改行->p] [let ((p (call/cc identity))) *->p]) ; ①
([let ((p (call/cc identity))) 改行->p] [let ((p k1)) *->p]) ; ② k1 が生成される
* & ([let ((p (call/cc identity))) 改行->p] k1) ; ③ 
([let ((p k2)) 改行->p] k1) ; ④ k2 が生成される
改行 & (k2 k1) ; ⑤ 
([let ((p k1)) 改行->p] k1) ; ⑥ k2 が生成された時点の④式の k2 に k1 が当て嵌められる
改行 & (k1 k1) ; ⑦ 
([let ((p (call/cc identity))) 改行->p] [let ((p k1)) *->p]) ; ⑧ k1 が生成された時点の②式の k1 に k1 が当て嵌められる
* & ([let ((p k3)) 改行->p] k1) ; ⑨ k3 が生成される
(k3 k1) ; ⑩ 
([let ((p k1)) 改行->p] k1) ; ⑪ ⑨式の k3 に k1 が当て嵌められる
改行 & (k1 k1) ; ⑫  k1 が生成された時点の②式の k1 に k1 が当て嵌められる

...

と、②式に戻りそこからの流れが繰り返され(ただし k2 -> k3 -> ...) 改行 -> 改行 -> * ... が繰り返されるのだと推測しました。 しかしこれには間違いがあります。

(define (f n) ...

と f を定義せずに

([let ((p (call/cc identity))) 改行->p] [let ((p (call/cc identity))) *->p])

と直接 let 式で行うと  * -> 改行 * -> 改行 * -> 改行 * -> 改行 ... となってしまうのです。おかしい、何が違うんだ。同じことをやってるんじゃないのかよ……と紙に書いて色々考えた結果、一つの仮定にたどり着きました。

([let ((p (call/cc identity))) 改行->p] [let ((p (call/cc identity))) *->p]) ; ①
([let ((p (call/cc identity))) 改行->p] [let ((p k1)) *->p]) ; ② k1 が生成される
([let ((p k2)) 改行->p] [let ((p k1)) *->p]) ; ③ そしてここで適用する let 式が評価されてしまう前に、被適用の let 式の評価が行われる
* & ([let ((p k2)) 改行->p] k1) ; ④ 
改行 & (k2 k1) ; ⑤ 
([let ((p k1)) 改行->p] [let ((p k1)) *->p]) ; ⑥ ③式に k1 が当て嵌められる
* & ([let ((p k1)) 改行->p] k1) ; ⑦ 
改行 & (k1 k1) ; ⑧ 
([let ((p (call/cc identity))) 改行->p] [let ((p k1)) *->p]) ; ⑨ ②式に k1 が当て嵌められる

...

と、③式から * と改行の出力が行われて②式へ戻ることを繰り返しているのではないかという仮定です。

何故

(define (f n) ...

とすると適用する側の評価が行われる前に被適用側の評価が行われないか考えてみると、おそらく適用側の (f 引数) が明確に値を返すまで評価されるからだと思います。

これらが正しいとすると

・Gauche では適用側(引数)の方から評価が行われる

・let 式は let が束縛する変数が分かると評価は割と後回しにされる

・定義された関数(変数)に束縛された式は値を返すまで評価される

だと思います。しかし call/cc パズルの解説と同じページの「評価順序と継続」 https://practical-scheme.net/wiliki/wiliki.cgi?Scheme%3A%E4%BD%BF%E3%81%84%E3%81%9F%E3%81%84%E4%BA%BA%E3%81%AE%E3%81%9F%E3%82%81%E3%81%AE%E7%B6%99%E7%B6%9A%E5%85%A5%E9%96%80#H-1wby0gx[ によると

「つまり、Gaucheでは左から順に引数を評価するために、」 とあって大前提の

・適用側(引数)の方から評価が行われる

は、間違いのようです。 と、すると Gauche と Racket でこの違いは一体何によるものでしょうか。

ブロック内で call/cc とその他を並列にしたときの継続の中身

begin 内で call/cc 式と他の式を並べてみました。

(define aaa/cc)
(begin
  (call/cc (lambda (k) (set! aaa/cc k)))
  (print "aaa"))

この begin 式を評価すると

gosh> aaa
#<undef>

となります。また

gosh> (aaa/cc)
aaa
#<undef>

というのも(一体どういう仕組みでこれが可能になっているのかはともかく)おそらく call/cc 式の次の (print 'aaa) が aaa/cc に set! で代入されているのだろうというのは推測できます。どういう仕組みでそうなるのかはともかく。 しかし

gosh> (aaa/cc 1)
aaa
#<undef>

gosh> (aaa/cc 'a 'b 'c)
aaa
#<undef>

と、aaa/cc に引数を(幾らでも)渡しても同じように同じ結果を返します。継続は結局はクロージャ、あるいはクロージャの連鎖だと理解しているのですが、aaa/cc に代入された継続は一体どのようなものなのでしょうか。

よろしくお願いします。

;; (A)
(define k1 #f)
(begin
  (call/cc (lambda (k) (set! k1 k)))
  (print "aaa"))
(k1 1)
;; (B)
(define k1 #f)
(print (call/cc (lambda (k) (set! k1 k) 0)))
(k1 1)
;; (C)
(define k1 #f)
(list 100 (call/cc (lambda (k) (set! k1 k) 0)) 200 300)
(k1 1)
;; (D)
(define k1 #f)
(call-with-values (lambda () (call/cc (lambda (k) (set! k1 k) 0))) list)
(k1 1 2 3)

Shiro(2022/10/23 21:03:51 UTC): aaa/cc に渡した値は、(call/cc (lambda (k)... の戻り値になります。デバッグスタブ #?= を使って表示させてみましょう。

(define aaa/cc #f)
(define (foo)
  #?=(call/cc (lambda (k) (set! aaa/cc k)))
  (print "aaa"))

最初の呼び出し:

gosh> (foo)
#?=(call/cc (lambda (k) (set! aaa/cc k)))
#?-    #<subr "continuation">
aaa
#<undef>

ここで表示されているのは、(set! aaa/cc k) の戻り値 (kの値、つまり継続手続き) がそのまま出てきています。

gosh> (aaa/cc 1)
#?-    1
aaa
#<undef>

継続に1を渡してみました。すると、(call/cc ... から1が返ってきて、foo の残りが再び実行されます。

gosh> (aaa/cc 'a 'b 'c)
#?-    a
#?+    b
#?+    c
aaa
#<undef>

三つの値を渡すと、それが多値として(call/cc ... から返ってきます。

なお、トップレベル式で捕まえる継続はR7RSでは明確に定義されておらず、処理系によって振る舞いが分かれるので、私の例のように関数の中で捕まえる方がわかりやすいです。

More ...