全関数と部分関数

今日から9章。
次のような関数 looking が出てきた。

(use mymodule)

(define pick
  (lambda (n lat)
    (cond
      ((zero? (sub1 n)) (car lat))
      (else (pick (sub1 n) (cdr lat))))))

(define keep-looking
  (lambda (a sorn lat)
    (cond
      ((number? sorn) (keep-looking a (pick sorn lat) lat))
      (else (eq? sorn a)))))

(define looking
  (lambda (a lat)
    (keep-looking a (pick 1 lat) lat)))

(print (looking 'caviar '(6 2 4 caviar 5 7 3)))
(print (looking 'caviar '(6 2 grits caviar 5 7 3)))

この関数 looking は次のように動作する。まず、引数 lat の1番目の要素を見て、それが数 n なら今度はn番目の要素を見る。そしてそれが数ならまた同じように繰り返す。最終的に数でないアトムに行き当たったとき、それが引数 a と eq? なら #t、そうでないなら #f を返す。
実行してみよう。

^o^ > gosh -I. looking.scm
#t
#f

最初の例では、6 → 7 → 3 → 4 → caviar となって無事 caviar が見つかるので #t が返っている。一方、2つ目の例では、6 → 7 → 3 → grits となって caviar が見つからないので #f が返っている。
動作そのもの以外に注目するところがある。今まで出てきた関数はすべて lat の部分に対して再帰してきた。ところが looking は lat そのものに対して再帰している。これを不自然な再帰というらしい。

さて、この looking はどんなときにも答を返すだろうか。上の2つの例ではどちらも答が返っているが、たとえば、(looking 'caviar '(7 1 2 caviar 5 6 3)) がどうやって動くか見てみると、
7 → 3 → 2 → 1 → 7 → 3 → 2 → 1 → 7 → … となって数でないアトムにたどり着かない。言い換えると looking は停止しない。これはプログラムの停止性の問題だ。どうやら9章のテーマはこれらしい。

さて、この looking のような関数を「部分関数」、今まで出てきたような関数を「全関数」というらしい。
次に eternity という関数が出てきた。

(define eternity
  (lambda (x)
    (eternity x)))

この関数はどんな引数が与えられても停止しない。eternity は最も部分的な関数だと書いてある。

うーん、9章にはいって難しげになってきた。