condの値式に潜む
「判定の陰」

by

関連記事

1. 「判定の陰」ができていた

AtCoderの問題を解いていたら、興味深いバグで不正解が出ていました。

マスに数値が置かれるたびに呼ばれる関数で、行・列・対角線ごとにカウントを更新し、どれかがNに達したらビンゴと判定します。

(defun mark-bingo-count-p (N A col-dp row-dp diagonal-dp)
  (let* ((val (1- A))
         (row (floor val N))
         (col (mod val N)))
    (cond ((= N (incf (aref row-dp row))))
          ((= N (incf (aref col-dp col))))
          ((= row col)
           (= N (incf (aref diagonal-dp 0))))
          ((= (- N row 1) col)
           (= N (incf (aref diagonal-dp 1)))))))Code language: Lisp (lisp)

問題は、1つずれることがあることです。
コードを見ても何が問題かわからなかったのですが、主対角線と副対角線が同時に成立するマスで、片方の対角線しか処理されない、そういうバグがありました。

1.1. 両方の条件が交差するところ

この原因は、condの値式を「条件」として扱っていたことです。

(cond ((= N (incf (aref row-dp row))))
      ((= N (incf (aref col-dp col))))
      ((= row col)
       (= N (incf (aref diagonal-dp 0))))
      ((= (- N row 1) col)
       (= N (incf (aref diagonal-dp 1)))))Code language: Lisp (lisp)

並んだ条件式を見ると、行・列・主対角線・副対角線のどれかがビンゴになったかを順番に調べているように見えます。

しかし、実は主対角線の条件(= row col)と副対角線の条件(= (- N row 1) col)は、同時に成り立つケースがあります1。
奇数サイズのビンゴ盤の中央マスです。

ところが、condは最初に真になった節で止まります2。
すると、主対角線の節が選ばれた時点で、副対角線の節は評価されません。
そこで、(aref diagonal-dp 1)が更新されず、不正解（WA）になってしまったのです3。

1.2. 真偽値を返す値式が紛らわしかった

コードでは、3つ目の条件式は、(= row col)で、その値式が(= N (incf (aref diagonal-dp 0)))という真偽値を返す式になっています4。

この値式が上の条件式と似ているため、「主対角線がまだビンゴでないなら、次の節を試す」という動きを期待してしまっていました。

しかし、実際には、条件式(= row col)が真になった時点で節は確定しています。
diagonal-dp 0がまだNに達していなくても、diagonal-dp 1の更新には進みません。

値式で真偽値を返していたことで、「判定の陰」ができていました。
条件判定の真偽値を返しているつもりが、結果を返して終わっていたのです。

2. 条件分岐と論理演算

2.1. cond + and

まず思いついたのは、condの節の中でandを使う形でした。

(cond ((= N (incf (aref row-dp row))))
      ((= N (incf (aref col-dp col))))
      ((and (= row col)
            (= N (incf (aref diagonal-dp 0)))))
      ((and (= (- N row 1) col)
            (= N (incf (aref diagonal-dp 1))))))Code language: Lisp (lisp)

条件式を(and 位置チェック カウント更新+判定)の形にすることで、判定が偽なら次に進みます。

2.2. or + and

ただ、condで書くと、すべての条件節が二重の括弧で囲んでいることになります。
すると、orとandで書き直せることに気づきました。

(or (= N (incf (aref row-dp row)))
    (= N (incf (aref col-dp col)))
    (and (= row col)
         (= N (incf (aref diagonal-dp 0))))
    (and (= (- N row 1) col)
         (= N (incf (aref diagonal-dp 1)))))Code language: Lisp (lisp)

orが「どれかがビンゴになったか」を組み立て、各andの前半が位置チェック、後半が更新と判定を兼ねています。
condの節選択と値式という非対称な構造がなく、式全体が判定になりました。

2.3. 更新と判定を分ける

ここで、更新と判定を同じ式にしない方がスッキリするかも、と考えました。

C言語では「代入しつつ比較」という書き方が使われることもあり、一箇所で完結する簡潔さがあります。
ただ、更新と判定が同じことで、更新が「判定の陰」に入るか慎重に読む必要が出てしまいました。

この条件分岐は、そこまで計算コストがかかるわけではないので、関数を分けることにしました。

(defun mark-bingo (N A col-dp row-dp diagonal-dp)
  (let* ((val (1- A))
         (row (floor val N))
         (col (mod val N)))
    (incf (aref row-dp row))
    (incf (aref col-dp col))
    (when (= row col)
      (incf (aref diagonal-dp 0)))
    (when (= (- N row 1) col)
      (incf (aref diagonal-dp 1)))))

(defun bingo-p (N row col row-dp col-dp diagonal-dp)
  (or (= N (aref row-dp row))
      (= N (aref col-dp col))
      (= N (aref diagonal-dp 0))
      (= N (aref diagonal-dp 1))))Code language: Lisp (lisp)

mark-bingoは状態を更新するだけで、判定はbingo-pが担います。
bingo-pは副作用を持たないので、任意のタイミングで何度でも呼べます。
同じターンに複数回判定したいときや、デバッグで状態だけ確認したいときに扱いやすくなります。
更新と判定を分けると、このような柔軟性が生まれます。

3. condとor/andの似ているところ

このバグを修正しながら、条件分岐のcondと論理演算のorが近いことに気が付きました。

値式のないcondは、かなりorに近いです。

(cond (a)
      (b)
      (c))

;; ほぼ同じ
(or a b c)Code language: Lisp (lisp)

どちらも「真の値が現れるまで順番に評価する」という動きをします5。

また、condは、andやwhenにも似ています。

condの条件式と値式の1節を見ると、andやwhenにも似ています。

(cond (a b))

;; 感覚的に近い
(and a b)
(when a b)Code language: Lisp (lisp)

aが真のときだけbが評価される、という点です6。
whenについても同様で、CLHSでは(when test {form}+)は(cond (test {form}+))と等価と明記されています7。

3.1. 似ているからこそ生まれる誤読

バグの原因は、この2つの類似点を結びつけた思い違いでした。

(cond (a b)
      (c d))

;; これと同じだと思い込む
(or (and a b)
    (and c d))Code language: Lisp (lisp)

しかし、これが違ったのです。

orとandの組み合わせでは、bがnilを返すと(and a b)全体がnilになり、(and c d)の評価に進みます。

(or (and t nil)
    :next)
;; => :NEXTCode language: Lisp (lisp)

しかし、condでは進みません。

(cond (t nil)
      (t :next))
;; => NILCode language: Lisp (lisp)

最初の節の条件式tが真になった時点で、その節が選ばれます。
値式がnilを返しても、次の節には進みません。

  • orは「真の値が返るまで進む」。
  • condは「真の条件式に出会うまで進む」。

condにおいて、節を選ぶのは条件式だけです。
値式は、節が選ばれたあとで評価される「結果」であり、次に進むかどうかの判定には参加しません8。

図式で書くとこうなります。

(cond (a b)        ;; a が判定、b は結果
      (c d))       ;; c が判定、d は結果

(or (and a b)      ;; a も b も判定に参加する
    (and c d))

3.2. 振分け関数、論理関数、述語関数

条件に関わる関数は、定義域と値域で3種類に分類できます。

分類定義域値域例
述語関数オブジェクト真偽値=, null, char=
論理関数真偽値真偽値not, and, or
振り分け関数（ディスパッチ）真偽値オブジェクトif, cond, when

ただし、Common Lispでは真偽値とオブジェクトの境界は曖昧です。
nilが偽で、それ以外のあらゆる値が真として機能します。
これが generalized Boolean です9。

つまり、条件式の定義域も値域も、nilと非nilの全域に広がります10。

この曖昧さから、同じ構文が複数の役割を兼ねます。
orは論理関数として設計されていますが、値域がオブジェクト全域に広がるので「振り分け関数」としても機能します。

orは、unlessとも似ています。

(unless x y)       ;; nil のときだけ y を評価する
(or x y)           ;; 論理関数として：どちらかが真か
                   ;; 振り分けとして：x が真なら x を返す、nil なら y に渡すCode language: Lisp (lisp)

unlessはbodyが1つならorと同じ動きをするからです11。
これは、orで「デフォルト値」と返す構文や、andでオブジェクトの有効性を確認してから処理する構文などで使われます。

本来、異なる目的で設計された構文が、特定の引数数でたまたま同じ動作をする。
condとorが似て見えるのも、generalized Boolean の定義域と値域の広さが、こういう構造上の重なりを生むからです12。

  1. この問題は AtCoder Beginner Contest 355 の C 問題です。N×Nのビンゴ盤で、ターンごとに宣言された数字を印付けし、行・列・対角線のいずれかが埋まったターン数を出力します。 – C – Bingo 2
  2. CLHS の仕様では「Once one test-form has yielded true, no additional test-forms are evaluated」と明記されています。 – CLHS: Macro COND
  3. WAはWrong Answerの略で、提出したコードの出力が期待された答えと異なる場合にジャッジシステムが返すステータスです。 – 用語集 – AtCoder
  4. incfは指定した場所の値をインクリメントし、更新後の値を返すマクロです。(= N (incf ...)) はインクリメントしつつNとの比較結果を返します。 – CLHS: Macro INCF, DECF
  5. orはショートサーキット評価を行い、真の一次値が返った時点で残りの式を評価せず、その値を返します。 – CLHS: Macro OR
  6. andは左から順に評価し、nilが返った時点で残りを評価せずnilを返します。すべて真の場合は最後の式の値を返します。 – CLHS: Macro AND
  7. CLHSのノートには (when test {form}+) == (cond (test {form}+)) と等価形が記載されています。 – CLHS: Macro WHEN, UNLESS
  8. CLHSの記述では「the forms associated with this test-form are evaluated in order, left to right, as an implicit progn, and the values returned by the last form are returned by the cond form」とあり、値式（forms）はあくまで選ばれた節の返り値を構成するものです。 – CLHS: Macro COND
  9. CLHSの用語集では predicate を「a function that returns a generalized boolean as its first value」と定義しています。述語関数は generalized boolean を返す関数全般を指します。 – CLHS: Glossary – predicate
  10. CLHSの用語集では generalized boolean を「an object used as a truth value, where the symbol nil represents false and all other objects represent true」と定義しています。 – CLHS: Glossary – generalized boolean
  11. CLHSでは (unless test {form}+) == (cond ((not test) {form}+)) と等価形が記載されています。body が複数の場合、cond の implicit progn として評価されますが、or にはその仕組みがありません。 – CLHS: Macro WHEN, UNLESS
  12. notはCLHSで「is intended to be used to invert the ‘truth value’ of a boolean (or generalized boolean)」と説明されています。nullと同じ動作をしますが、用途の意味的な違いで使い分けます。 – CLHS: Function NOT