Scheme演習 第7回

品川 嘉久, 浅井 健一, 萩谷 昌己, 西澤 弘毅, 原 謙治

quasiquote と unquote

(quasiquote obj)の省略形。アンクォートされた部分は評価し、それ以外は'と同様、評価せずにそのまま返す。

(unquote obj)の省略形。quasiquoteのなかで使われ、部分的にアンクォートする。

> (+ (* 1 2) (* 3 4))
14
> `(+ (* 1 2) (* 3 4))
(+ (* 1 2) (* 3 4))
> `(+ (* 1 2) ,(* 3 4))
(+ (* 1 2) 12)
> (define x 1)
> `(x ,x x)
(x 1 x)
> `(x 'x ',x)
(x 'x '1)

eval

これは、引数をプログラムだと思って評価する、という関数である。この関数は、実行時にプログラムを作り上げて実行してしまう、という意味でなかなか激しい命令である。

> '(+ 3 4)
(+ 3 4)
> (eval '(+ 3 4))
7
> (eval ''(+ 3 4))
(+ 3 4)
> (define (f g) `(',g 3 4))
> (f +)
('#<procedure +> 3 4)
> (f -)
('#<procedure -> 3 4)
> (eval (f +))
7
> (eval (f -))
-1

ここで単に `(,g 3 4) としてしまうと、λclosure(インタプリタにおける(*lambda* params body env))が直接リストの先頭に来てしまう。

これは値であり式ではないので、eval することはできない。

> (define (f g) `(,g 3 4))
> (f +)
(#<procedure +> 3 4)
> (eval (f +))
*** ERROR -- Ill-formed expression
#<procedure +>

停止性問題の解決不可能性

任意のプログラムの停止性を判定できる関数 eval-halt?を作れると仮定し、矛盾することを示してみる。下のような矛盾の導き方を対角線論法と言う。

このturingという関数は、一引数関数 xを受け取り、「(x x)を実行せよ」というプログラムをeval-halt?で判定する。

それが停止すると判定されたらループに入り、停止しないと判定されたら停止する。

(define (loop) (loop))
(define (turing x)
  (if (eval-halt? `(',x ',x))
      (loop)
      "done"))

このtという式は、「(turing turing)を実行せよ」というプログラムになっている。

(define t `(',turing ',turing))

ここで、eval-halt?を部分的に定義してみる。

eval-halt?が任意のプログラムの停止性を判定できると仮定すると、上のプログラム tに対しても停止性を判定し、#t か #fを返すはずである。

そこで、tに対して#t を返す場合と#fを返す場合の両方の可能性について考えてみる。

t以外に対しては何を返すか定義しない。それでも以下の議論はうまくいく。

(eval-halt? t) で #f と判定された場合、実際には (eval t) は停止してしまう。これは矛盾である。

(define (eval-halt? x)
  (if (equal? x t)
      #f
      "undefined"))
> (eval-halt? t)
#f
> (eval t)
"done"

そこで、(eval-halt? t) で #t と判定されるように修正すると、今度は (eval t) はループしてしまう。これも矛盾である。

(define (eval-halt? x)
  (if (equal? x t)
      #t
      "undefined"))
> (eval-halt? t)
#t
> (eval t)
*** INTERRUPTED IN loop, (stdin)@55.19
1> ,d

結局、undefined の部分をどのように実装しても、この事態は避けられないので、任意のプログラムの停止性を判定する eval-halt? なるプログラムは作れないことがわかった。

継続とcall/cc

継続とは、一言で言うと「その後にやる苓の仕事」である。

たとえば、(+ 3 (* 1 2))を入力すると Scheme はまず+を評価する。

この時点での継続は、「3を評価し、(* 1 2)を評価した後、その結果を+に適用する」である。

+を評価したら、Scheme は次に 3を評価し、* を評価する。

*を評価する時点での継続は「1を評価し、2を評価し、その結果に3を加えて返す」となる。

このように Scheme の式の評価中には常にその時点での継続というものを考えることができる。

この継続を評価の途中で登録しておく命令がcall/ccである。

ただし、処理系によっては下の宣言が必要なものもある。

(define call/cc call-with-current-continuation)

たとえば、下のような式の中で、式 (* 1 2)を評価する時点での継続を登録するには、式をさらに下のように変更する。

(+ 3 (* 1 2))
(+ 3 (call/cc (lambda (cont) (* 1 2))))

(* 1 2)の内部では変数contを使うことができる。contは一引数関数で、たとえば下のように使うことができる。

(+ 3 (call/cc (lambda (cont) (* (cont 1) 2))))

この contは (* 1 2)の実行時の継続を聞く。すなわち、「結果に3を加えて返す」である。

これを関数として内部で使うと、その引数に与えたものの本来の継続を忘れ、contを継続として適用する。

つまり、*を評価したあと、(cont 1)を評価しようとするが、ここで1を「結果に3を加えて返す」に適用し、式全体の結果を求める。

> (+ 3 (call/cc (lambda (cont) (* (cont 1) 2))))
4

継続の効果的な使い方の一つが、例外処理である。たとえば、下の関数を考える。

これは数値のリストを受け取って、その積を求める関数である。

(define (multiply-list1 lst)
  (define (multiply lst2)
    (cond ((null? lst2) 1)
          (else (* (car lst2) (multiply (cdr lst2))))))
  (multiply lst))
> (multiply-list1 '(1 2 3 4))
24

しかし、リスト中に一つでも0があれば、結果は必ず0なので残りを見る必要もないし、0が出てくるまでの掛け算をする必要もない。

そこでcall/ccを使って次のように書き換える。

(define (multiply-list2 lst)
  (call/cc (lambda (cont) ; 抜ける先を cont にとっておいて
    (define (multiply lst2)
      (cond ((null? lst2) 1)
            ((= 0 (car lst2)) (cont 0)) ; 0 だったら、いきなり0を返す
            (else (* (car lst2) (multiply (cdr lst2))))))
    (trace multiply) ; trace で観察
    (multiply lst))))

確かに、0が出てきた時点で計算を中断している。

> (multiply-list2 '(1 2 0 3 4))
| > (#<procedure #x1B6772> '(1 2 0 3 4))
| | > (#<procedure #x1B6772> '(2 0 3 4))
| | | > (#<procedure #x1B6772> '(0 3 4))
0
>

レポート課題7

問1(成績に考慮しない)

問2(成績に考慮しない)