list?と手続きの停止性

nmosh

追記: predicateは常に値を返すとなっているので停止すると言ってよさそうですね。。(いや、"停止する場合に値を返す"とも言えなくもない気もするけど)

  • R7RS

1.3.5. Naming conventions
By convention, ? is the final character of the names of procedures that always return a boolean value. Such procedures are called predicates. Predicates are generally understood to be side-effect free, except that they may raise an exception when passed the wrong type of argument.

以前の内容

前回のコメント( http://d.hatena.ne.jp/mjt/20150329/p1#c )を読んで考えたのは、そもそもlist?ってどの処理系でも停止するのかというポイント。たとえば、vanilla-moshのlist?は停止する。

    static bool isList(Object p)
    {
        Object obj = p;
        Object seen = obj;
        for (;;) {
            if (obj.isNil()) return true;
            if (!obj.isPair()) return false; // dot pair
            obj = obj.cdr();
            if (obj.isNil()) return true;
            if (!obj.isPair()) return false; // dot pair
            obj = obj.cdr();
            seen = seen.cdr();
            if (obj == seen) return false; // circular ← ★ 半分の速度で進めているポインタと衝突したらどこかでループしている
        }
        return false;
    }

これは、chibi-schemeでも同様のアルゴリズムになっている:

sexp sexp_listp_op (sexp ctx, sexp self, sexp_sint_t n, sexp hare) {
  sexp turtle;
  if (! sexp_pairp(hare))
    return sexp_make_boolean(sexp_nullp(hare));
  turtle = hare;
  hare = sexp_cdr(hare);
  for ( ; sexp_pairp(hare); turtle=sexp_cdr(turtle)) {
    if (hare == turtle) return SEXP_FALSE;
    hare = sexp_cdr(hare);
    if (sexp_pairp(hare)) hare = sexp_cdr(hare);
  }
  return sexp_make_boolean(sexp_nullp(hare));
}

(HareとTurtleは、いわゆる"ウサギとカメ"に由来すると考えられる - 英語圏ではrabbitとhareを区別する。)
というわけで多分規格としてもlist?は停止することが求められている気がするが、特に明記されてはいないように読める(see 追記)。ただし、例ではこれを要求している

(let ((x (list 'a)))
  (set-cdr! x x)
  (list? x)) ;; => #f

R7RSのこの例は、set-cdr!で生成される循環リストに対しても、list?は停止して#fを返さないといけないと読める。たぶんSchemeにおいてはlist?が循環リストに対して停止するのは一種の常識ということになっているのだろう。
個人的にはlist?はほぼ使わない。どうせ循環リストを処理できない手続きはどこかで遭遇するので、循環リストを作る可能性のあるポイントは他と区別するようにしている。多くの場合はpair?とかnull?で十分。
CDR codingのようなエンコード下ではlist?は定数時間で完了するはずだが、そこまでするかどうかは。。というかCDR codingってAI研の特許技術なの。。?

It was developed and patented by the MIT Artificial Intelligence Laboratory, and implemented in computer hardware in a number of Lisp machines derived from the MIT CADR

停止性の仕様

R7RSにおいても、いくつかの手続きは循環リストでも停止することが明確に要求されている。

  • equal?

Even if its arguments are circular data structures, equal? must always terminate.

  • display

However, display must not loop forever on self-referencing pairs, vectors, or records.

  • write

If obj contains cycles which would cause an infinite loop using the normal written representation, then at least the objects that form part of the cycle must be represented using datum labels as described in section 2.4. Datum labels must not be used if there are no cycles.

writeの場合は、停止しなくても良いバリアントとしてwrite-simpleも規定されている:

  • write-simple

This can cause write-simple not to terminate if obj contains circular structure.

C APIだけでなくScheme手続きについてもAPIメタデータを収集しておいた方が良いのかもしれない。例えば、停止しない可能性のある手続きの呼び出しチェックを自動化する等。