2019年2月11日月曜日

循環リストの応用例その2(Luhnアルゴリズム)

Luhnアルゴリズム(Luhn algorithm)は、
様々な識別番号の認証に使われている単純なチェックサム方式。
たとえば、クレジットカード番号にもこの方式が使われている。
詳細は wikipeida参照。

このLuhnアルゴリズムのさまざな言語での実装が、
Implementation in 88 languages on the Rosetta Code project
に載っているので、そちらを見ていただいても構わない。

で、先日ISBNのコードを書いている途中、
たまたまLuhnアルゴリズムに出くわしたので、
「関数の循環リスト」を使った、schemeでの実装を書いてみた。
なお、入力は文字列として受け取る。
(define (check-luhn num-string)
  (define luhn-digit
    (circular-list (lambda (x) x)
                   (lambda (x) (vector-ref #(0 2 4 6 8 1 3 5 7 9) x))))
  (zero? (remainder (fold + 0 (map (lambda (f x) (f x))
                                   luhn-digit
                                   (reverse (map digit->integer (string->list num-string)))))
                    10)))
;; (check-luhn "1234567812345678")

なんというか、schemeならではの素敵なコードになったと思うので、
ここに記録しておく。

以上

2019年2月2日土曜日

ISBNチェッカー(循環リストの応用例)

循環リストの応用例

最近、ISBNの入力ミスを発見するためのスクリプトを書いた。
循環リストを使った美しいコードだと思う。

だけど、「循環リスト(Circular list)なんて観念で、
(理論の)完全性のために存在しているだけ」と言われることがある。
また、Googleで「循環リスト」を検索すると
関連検索として「循環リスト 応用例」を提案してくる。

でも、循環リストを使わないと実現しにくいアルゴリズムもあるし、
循環リストはSchemeの楽しさを高めている思っている。
そして私はこよなくschemeを愛している。
だから、ここに実用的な「循環リストの応用例」として
ISBNチェッカーを公開する。

ISBNチェッカー

ISBNは書籍を一意に示すための番号である。
ISBN-13の最後の1桁はチェックデジットであり、以下のように計算される。
----- -----
現行規格のISBN (ISBN-13) のチェックディジットは、JANコードと同じく、「モジュラス10 ウェイト3・1(モジュラス10 ウェイト3)」という計算法にて算出される。(チェックディジットを除いた一番左側の桁から順に1、3、1、3…を掛けてそれらの和を取る。和を10で割って出た余りを10から引く。ただし、10で割って出た余りの下1桁が0の場合はチェック数字を0とする。)
----- -----
「ISBN」(2018年12月21日 (金) 08:59UTCの版)『ウィキペディア日本語版』より引用[注1]

これを実装すると以下のようになる。ただし、入力は文字列として受け取る。
(use srfi-1)
(define (check-isbn13 num)
  (define weight (circular-list 1 3))
  (zero? (remainder (fold + 0 (map (lambda (x y) (* x y))
                   weight
                   (map digit->integer (string->list num))))
            10)))
「一番左側の桁から順に1、3、1、3…を掛け」るところに循環リストを使っている ((circular-list 1 3)は'(1 3 1 3 ...)となる循環リストを返す。)。
左から1桁ずつループして拾っているのだけど、
掛ける数が1と3で交互なので、
(1 3 1 3 ...)となっている循環リストに対して、
carで先頭を拾って使い、cdrして残りを次のiterationに渡している。
場合分けとかフラグとかを使っていないところが美しいでしょう?

うさぎとかめのアルゴリズム

ところで、あるリストを与えられた時、それが循環リストになっているかをチェックする コードが以下にある。
大変美しく、ぜひご覧いただきたいので、ここで勝手に紹介する。

以上

2019年1月26日土曜日

ふわっとした情報から一次ソースまでたどり着く方法(RFC編)

0. 要旨

「メールアドレスのドットの連続はRFC違反」みたいな ふわっとした情報があって興味をもったとき、 技術屋なら 「どのRFCのどのセクションにどのように記述されているか」 みたいな一次ソースを当然確認したくなるでしょう?
今回、メールアドレスのルールが気になって調べたのでここに記録しておく。

1. 一次ソースまでの道のり

1.1. Wikipedia日本語版「メールアドレス」

ざっと説明を読む。ふむふむ。 RFC 5321とRFC 5322への参照がある。 取り合えずリンクを開く。
(今回は、Wikipedia日本語版に参照先まで書いてあってラッキーなパターン。 日本語版に参照がなくても英語版を眺めると参照先が見つかることもあるし、 さらにインターネットをさすらう場合もある。)

1.2. RFCを眺める

タイトルは
RFC 5321:Simple Mail Transfer Protocol
RFC 5322:Internet Message Format
で、どちらもボリュームがある。
RFC 5321から読むことにする。

1.3. RFC 5321を眺める

まず左上にObsoleted byがないことを確認する。
(もしObsoleteになっているなら、 Obsoleted by: XXXXのXXXXを読むべきだから。)
長いのでさらさらスクロールしてみる。
中程でバッカス・ナウア記法(BNF)的な 表記を見つけて手を止める。その節は 「4.1.2.  Command Argument Syntax」。
読んでみるが、いまいち解決しない。
@の左側はLocal-partと呼び、それはDot-stringであって、、、 と書いてあるが、atext以降が解決していない! そしてこの文書にはatextはこの1個しかない!

1.4. RFC 5322を眺める

気を取り直して、RFC 5322を開き「atext」を検索する。 3個めのatextでBNF的な表記に出くわす。その節は「3.2.3.  Atom」。 atextが定義されている。なんだatextは普通の文字 (アルファベットと数字といくつかの記号)のことか。

1.5. RFC 5321に戻る

ここで、RFC 5321 4.1.2に戻る。
----------------------------------------------
(前略)
   Dot-string     = Atom *("."  Atom)
   Atom           = 1*atext
(後略)
----------------------------------------------
たしかに、Local-partは確かにドットは連続しないわ、と納得する。

<読み方>
読み方は人によるところが大きい。
私はボトムアップが一番理解しやすいので、 最下層(定義に近いもの)から順番に組み立てるように理解する。
「Atomは任意個の普通の文字。
Dot-stringは先頭にAtomあって、その後に任意個の{.(ドット) とAtomの連結}が続く。
ということは.(ドット)は連続で現れないし、先頭にも最後尾(@の直前)にも現れない!」

1.5. RFC 5321とRFC 5322

だけど、RFC 5321の途中からRFC 5322の定義を読むのでよいのか、 と我に返る。
RFC 5321で5322を検索すると 「1.2.  History and Context for This Document」に 「RFC 5322はcompanion documentだよ」と書いてあるので、 よいことにする。

2. おまけ

2.1. ITEFのRFCのページ

ITEFのRFCのページは便利。
https://tools.ietf.org/html/rfc5321
Obsoleteになっているもの、updateがあるものは 最上部で分かるし、 他のRFCへの参照はハイパーテキストリンクになっている。

2.2. バッカス・ナウア記法(Backus-Naur form)

BNFは学部3年のときに情報学科の講義で勉強して、 なるほどすごい、と思った。
でも、いつもギリシャのお酒の好きな神様を思い浮かべてしまう。 (綴りはちょっと違う)

2.3. Request For Comment

RFCに「違反」という言葉は似合わないと思っている。
「法令」ではない、ただの「Standard」なのだから、 「準拠していない」くらいが適切と思う。

以上