Typed RacketでLuhnアルゴリムを実装した
目次
1. はじめに
最近、クレジットカード番号まわりを扱う開発をする機会があり、 クレジットカード番号の入力ミスを検知するのに使用されている Luhn アルゴリズムについて知りました。
これは面白い仕組みだなと思い、 趣味プログラミングの一環として Typed Racket で実装してみました。
その結果、いい感じに実装できたので記事に残します。 Luhn アルゴリズムについての詳細には触れず、 Typed Racket で実装したときの感想や、 最終的な実装に至るまでに考えたことなどについて主に書きます。
2. Luhn アルゴリズムとは
Luhn アルゴリズムは、Hans Peter Luhn 氏が発明したチェックサム方式の誤りを検知する方法です。
番号の右端に誤り検出用の番号(チェックディジット)を一つ追加しておき、 決められた方法で計算した値が10で割り切れるかどうかで判定します。 10で割り切れる場合は誤り未検出で、 割きれない場合は誤りを検出できます。 誤りが検出されない場合に、元の誤りがないことを証明できているわけではないことに注意が必要です。 (0と9の入れ替えなどの簡単な入力間違えであってもすり抜けるケースがあります)
手元に番号が書かれたカードや紙があるときに、 コンピュータに手入力する場合には入力ミスがよく起きるものですが、入力ミスのたびに番号を管理しているシステムまで問い合わせまでしてしまうと無駄が多いです。 番号を入力するユーザー側の体験としても、 システムへの問い合わせを待つことなく、 すぐに入力ミスが分かった方が快適に感じると思うので、 大変有益なアルゴリズムだと思います。
3. Typed Racket 実装のインターフェース
Typed Racket で実装する際に定義した型や手続きについて紹介します。
実際の実装は GitHub の luhn.rkt に置いてあります。
3.1. Digit 型
折角 Typed Racket を使っているので Digit 型を定義することにしました。
手続きに整数のリストを渡すインターフェースにすると、 リストの要素が0から9までの整数になっていない場合には、 入力としては不正なわけです。
ただ、実際プログラム書いていてこういう細かいのをエラーにするのは結構面倒だし費用対効果的に微妙となりがちだと思うのですが、 Typed Racket だと気軽に型で入力の制限が可能です。
入力値を型で制限しておくと、入力された整数が0から9までの範囲にあるという信頼できる前提にでき思考が軽くなってよいと感じます。
以下のように型定義をしました。
(define-type Digit (U 0 1 2 3 4 5 6 7 8 9)) (define-predicate digit? Digit)
かなりごり押し感のある型定義ですが、 Digit は10個しかないのでいいとしましょう。 これで Digit を普通の整数として扱いつつ、0から9までの整数に限定した型が用意できました。
また、 digit?
述語も定義しています。
この述語で分岐することで Digit かどうかを判定できます。
3.2. Luhn アルゴリズムのインターフェース
Luhn アルゴリズムの検証をする際には、
番号の列を一度を Luhn
型の構造体に変換してから扱うことにしました。
3.2.1. Luhn 構造体を作成する
まず、luhn 構造体を作る方法として次の二つの方法を提供しています。
list->luhn: (Listof Digit) -> Luhn
- Digit のリストを Luhn 構造体に変換する手続き
string->luhn: String -> (U Luhn False)
- 文字列を Luhn 構造体に変換する手続き
list->luhn
は確実に Luhn
に変換できます。
しかし、文字列の場合は入力に数字以外が含まれているかもしれないので、数字以外の文字が含まれていた場合には #f
を返すようにしています。
逆に Luhn 構造体から文字列、リストに変換する場合は以下の手続きを使います。 こちらはどちらも失敗する可能性のない手続きです。
luhn->list: Luhn -> (Listof Digit)
- Luhn 構造体をリストに変換する手続き
string->luhn: Luhn -> String
- Luhn 構造体を文字列に変換する手続き
3.2.2. 番号の誤りを検出する
以下の手続きで、番号の誤りを検出するようにしました。
luhn-valid?: Luhn -> Boolean
- 番号の不正を検出し、誤りがが検出されなければ
#t
, 検出された場合は#f
を返す
Luhn 構造体を作成する部分と組合せると次のように使うことで、番号のチェックができます。
;; 誤りなしの場合 (luhn-valid? (list->luhn '(1 4 7 6 3 7))) ; => #t ;; 誤りありの場合 (luhn-valid? (list->luhn '(1 4 7 3 6 7))) ; => #f
3.2.3. 番号にチェックディジットを追加する
以下の手続きで、番号にチェックディジットを追加できるようにしました。
luhn-add-check-digit: Luhn -> Luhn
- チェックディジットを追加
以下のように使用します。
(luhn->list (luhn-add-check-digit (list->luhn '(1 4 7 6 3)))) ;; => '(1 4 7 6 3 7)
ここまでで、Luhn アルゴリムを扱うのに必要なインターフェースを説明しきりました。
3.2.4. 何故 Luhn 構造体を仲介する設計にしたのか
最初の実装ではそもそも設計など考えずに、
(Listof Digit)
を受けとって Boolean
を返す手続きを返そうと思っていました。
ただ、この方針だと次の3点が気になったので色々考えた結果 Luhn 構造体を経由するようにしました。
- チェックサムを計算するとき、リストが反転している方が望ましいため
- チェックディジットを追加するとき、リストが反転している方が望ましいため
- リストだけでなく文字列を扱うインターフェースも欲しくなったため
- 文字列を渡す手続きとリストを渡す手続きの二つを作ると無駄が多い
- 一つの手続きにまとめることも可能だが、文字列を渡す場合は失敗する可能性があり、リストを渡す場合は失敗可能性がないので無理に一つにしようとすると複雑になった
- 中間構造としては、反転したリストの方がアルゴリズムと相性がよく、一度文字列を Digit のリストに変換してから適用するようにすると、無駄に reverse を実行しないといけないので、リストではなくて中間構造に変換するインターフェースの方がよかった
- 文字列を渡す手続きとリストを渡す手続きの二つを作ると無駄が多い
上記のように主な理由としては、Luhn アルゴリズムと相性のよい中間構造が、単純な Digit のリストではなくて、反転させたリストの方がよかったのが主要因となって Luhn 構造体を用意しました。
Luhn に実は反転したリストが入っているというのは隠蔽したかったので、
luhn
モジュールでは Luhn 構造体の中身を外部に公開(provide
)していません。
4. Typed Racket での実装について
では Luhn をどんな感じで実装したのかについて紹介します。
4.1. Luhn
構造体の中身
Luhn 構造体は次のように定義しています。
(struct luhn ([rev-digits : (Listof Digit)]) #:type-name Luhn)
rev-digits
というフィールドのみを持った構造体です。
中間構造としては反転したリストを持った方がやりやすいのでそうしています。
list->luhn
は以下のようになっています。
(: list->luhn (-> (Listof Digit) Luhn)) (define (list->luhn lst) (luhn (reverse lst)))
string->luhn
は、文字列に数字以外が含まれていた場合に対処するため少し複雑になっています。
文字が数字でない場合に #f
を返すようにしているだけではあります。
(: string->luhn (-> String (Option Luhn))) (define (string->luhn str) (call/cc (lambda ([return : (-> False Nothing)]) (luhn (for/fold ([rev : (Listof Digit) '()]) ([c (in-string str)]) (cond [(digit-char->digit c) => (lambda (d) (cons d rev))] [else (return #f)]))))))
(digit-char->digit
の掲載は省略、GitHub で公開している実装の方を参照してください)
4.2. luhn-valid?
の実装
luhn-valid?
は以下の定義になっています。
(: luhn-valid? (-> Luhn Boolean)) (define (luhn-valid? lhn) (zero? (modulo (luhn-sum lhn) 10)))
非公開の手続きである luhn-sum
メソッドでチェックサムを計算して、10 で割り切れるかを確認します。
luhn-sum
は次のような感じです。
(: luhn-sum (->* (Luhn) ((Listof (U 1 2))) Natural)) (define (luhn-sum l [scale-list '(1 2)]) (for/sum : Natural ([d : Digit (luhn-rev-digits l)] [scale : Natural (in-cycle scale-list)]) (sum-of-digits (* d scale))))
luhn アルゴリズムでは、番号の右端から 1, 2, 1, 2 … のサイクルの列を掛け合せた値を使います。
この計算をするのには、事前にリストを反転させておいた方がいいため、 luhn
構造体に入っている反転済みのリストを使っています。
番号の各ディジットと scale-list のサイクルを掛けた後、
2桁になる場合は1桁目と2桁目を加算した値を使います。
この計算は sum-of-digits
手続きで実装しています。
(: sum-of-digits (-> Natural Natural)) (define (sum-of-digits n) (define-values (q r) (quotient/remainder n 10)) (if (< q 10) (+ q r) (+ r (sum-of-digits q))))
この実装では、任意の自然数に対して sum-of-digits
を求められるようにしているのですが、 0
から 19
までの整数に対してであれば、
n
が 9
より大きい場合に 9
を引くという方法でも求められます。
これは、 Wikipedia の Luhn アルゴリズムのページに記載されていた実装でこの事実が使われているのをみて知りました。
たしかにそうなのですが、 sum-of-digits
という名前を付けて抽象化した以上は 0 から 19 までに限定するのはいかがなものかと思ったので任意の自然数に対して動作するように実装しています。
4.3. チェックディジットを番号の右端に追加する処理の実装
luhn-add-check-digit
の実装は以下の通りです。
(: luhn-add-check-digit (-> Luhn Luhn)) (define (luhn-add-check-digit l) (luhn (cons (calculate-check-digit l) (luhn-rev-digits l))))
これをみると、やはり反転したリストを中間構造として使うのがよさそうです。
仮に反転していない場合は (append (luhn-digits l) (list (calculate-check-digit l)))
のようにしないといけないわけで、要素を一つ追加するのにリストを構成する pair を全部更新するのはちょっとなあという気持ちになると思います。
(: calculate-check-digit (-> Luhn Digit)) (define (calculate-check-digit l) (let ([sum (luhn-sum l '(2 1))]) (assert (modulo (- 10 (modulo sum 10)) 10) digit?)))
先程紹介した luhn-sum
を再度使っています。
追加するチェックディジットを計算するには、
チェックディジット部分を飛ばしてチェックサムを計算した際に、
何を足したら10で割り切れるかというのを計算する必要があります。
チェックディジットを飛ばした場合のチェックサムを計算するために luhn-sum
に '(2 1)
を渡しています。
こうすることで、右端から 2, 1, 2, 1… で掛け合わせた場合のチェックサムが手に入ります。
((cons 0 _)
をしてから、 luhn-sum
に渡してもよかったのですが、無駄にpairを作るのが嫌だと思ったのでそうはしていません)
あとは assert
の部分についてなのですが、
これは (modulo _ 10)
の結果が Natural 型に広がってしまうために書いています。
仮に (digit? (modulo _ 10))
が偽の場合は実行時エラーになります。しかし私は (modulo _ 10)
の結果は常に Digit
だと知っているので assert
を書くことにしました。
Typed Racket には実験的機能として Dependent Function Type というのがあり、もしかすると 0<=n<=9
のような n
をうまく扱うことができるのかもしれないのですがよく分かっていないのと、それ以前に実験的機能という問題があるのでこのあたりの可能性については深入りしないことにします。
5. Typed Racket で実装してよかったこと/よくなかったこと
5.1. よかったこと
- 型がつくおかげで細かいエラーの可能性について考慮が不要になってよかった
- 「Digit 以外の整数が渡ってくることがない」など
- Digit 型を定義できること
- 0から9までの整数を表現する型を定義できるのは珍しい
- Racket の for/fold や for/sum などの繰り返し構文が便利で分かりやすい
- 簡単なテストを実装のそばに書けるのが嬉しい
module+
構文を使うと実装を書いた後にすぐテストをかけて楽
- 型が付いているのでインターフェースの変更時に、試しに動かさなくても壊れている部分を型エラーで全て把握できる
- Natural 型が便利、負の整数の可能性を考慮しなくてよいのは最高
5.2. よくなかったこと
- Racket に依存すること
- 当然他の Scheme 処理系との互換性はない
- 型注釈しないといけない部分としなくてよい部分の違いが分かりにくい場合がある
Maybe Boolean
的な構造が欲しい場合に困ると思った- 最終的な実装ではこの型が不要になる設計にしたが、実装中は悩んでいた
- 詳細は次の「Typed Racket での失敗の表現をどうするかについて」で言及する
6. Typed Racket での失敗の表現をどうするかについて
今回の実装で最終的には不要となったため、問題にはならなかったのですが、 Boolean
を返す手続きで失敗を表現する場合はどうすればいいんだろうと思ったのでその件について話します。
Racket では普通失敗を表現するのに (U <結果の型> False)
を使用します。これは結果の型の値か #f
のどちらかという意味で、少なくとも Scheme ではこれが便利といえます。
便利だからか Typed Racket では (U <結果の型> False)
を (Optionl <結果の型>)
とも書けるようになっています。
何故これが便利なのかというと cond
のようにこのパターンをうまく扱う構文が Scheme の仕様に入っているからです。
string->luhn
手続きを再掲します:
(: string->luhn (-> String (Option Luhn))) (define (string->luhn str) (call/cc (lambda ([return : (-> False Nothing)]) (luhn (for/fold ([rev : (Listof Digit) '()]) ([c (in-string str)]) (cond [(digit-char->digit c) => (lambda (d) (cons d rev))] [else (return #f)]))))))
digit-char->digit
は (-> Char (Option Digit))
という型の手続きで、 Digit
の値か #f
のどちらかを返します。
で、 Digit
だった場合は =>
の右にある手続きに結果を渡して呼び出して、そうでなければ次の条件を見るというものです。
Scheme 標準の手続きでも string->number
のような手続きでは、
失敗したら #f
で、成功したら 数が返るようなものがあり、
#f
は Scheme で失敗を表現するよいツールとなっています。
ただ、場合によっては Boolean もしくは失敗の意味ではない #f
を返す手続きが失敗するというケースも考えられるわけです。
この場合は困るということで、今回考えた回避策を紹介します。
6.1. Boolean を返す失敗する手続きの例
文字列を渡して、luhn アルゴリズムで検証する手続きを実装すると考えてみましょう。
この手続きはどういう型にするのがいいでしょうか。 文字列に数字以外がある場合と、 luhn アルゴリズムで検証した結果誤りがあった場合では、 失敗の意味合いが異なってきます。 前者はプログラムが期待していない入力値エラーという意味で、 後者はluhnアルゴリズムの結果として誤りを発見したという意味です。
luhn アルゴリムで検証することが主目的であれば、 文字列に数字以外がある場合はその計算の目的を果たす前に失敗したということなので、計算の失敗を表現しないといけません。
6.2. 例外を使う方法
シンプルに例外を放ってしまうというのも一つの選択肢です。 Racket には Java の throws みたいな機能がなく、 手続きがどの例外を放つ可能性があるのかということを適切に把握できるわけではないためあまり使いたくない気がしています。
例外を使う場合はドキュメント作成の負荷が上がるし、 利用者にドキュメント参照の負荷をかけることになるのでなるべく避けたい気がします。
6.3. Maybe を使う方法
Haskell などで採用されているのと同じ Maybe 型を定義するという方法です。
Racket には代数的データ型はない(と思うの)ですが、次のように構造体を定義すれば Maybe をエミュレートできます。
(struct (A) just ([value : A]) #:type-name Just) (struct none () #:type-name None) (define-type (Maybe A) (U (Just A) None))
これなら (Maybe Boolean)
という構造を作れますし、Maybe をネストすることも可能です。
しかし、前述したような cond
の =>
のような Racket
標準にある便利な構文が使えるわけでもないので、
Racket の標準的な実装方法から大きく外れる問題があります。
これをうまく扱うライブラリが適切に整っていないと別に便利とはいえないですし、揃っていたとしても Typed Racket 標準から大きく外れて特定のライブラリに深く依存する感じになるのが嫌です。
6.4. 失敗継続を使う方法
失敗継続を使うという方法があります。 この方法で実装する場合はこんな感じになります。
(: luhn-string-valid? (All (A) (-> String (-> A) (U A Boolean)))) (define (luhn-string-valid? str fail) (cond [(string->luhn str) => luhn-valid?] [else (fail)]))
失敗した場合に継続する処理を、
ライブラリのユーザー側で決めてから luhn-string-valid?
を使うという方法です。
ちょっと気になるのは、 Boolean
を返すとは限らないのに ?
を使うのっていいのだろうかというところで少し微妙な感じがします。
以下のように型を変更すれば、失敗した場合は (fail)
が値を返さないようにすることを利用者に強要することも可能なのですが、
失敗継続に何を渡すかには好みがある気がしていて、戻り値の型を Boolean
にするためだけにこういった無理強いをするのはどうなのかなと思います。
(: luhn-string-valid? (-> String (-> Nothing) Boolean)) (define (luhn-string-valid? str fail) (cond [(string->luhn str) => luhn-valid?] [else (fail)]))
この場合は失敗継続は値を返してはならないので、
fail
手続きの中で例外を発生させるか、 call/cc
で外に脱出させるかといったことを利用者に強制することが可能です。
しかし、この方法でも値を返さないことがあるのに述語というのはおかしいので、そんな副作用のある変な述語は述語じゃないということでやはり名前から ?
は取った方がいいような気がします。
6.5. 失敗する可能性のある Boolean を返す手続きは定義しない
これは、今回の luhn
モジュールで採用した戦略です。
luhn-string-valid?
のような Boolean を返すが失敗する可能性があるという種類の手続きをそもそも定義しなければ問題は解決したといえます。
結局、失敗する可能性のある Boolean を返す手続きというのは、 なんらかの意味で副作用のある変な述語であり、 そもそも何か設計がおかしいのかもしれません。
計算結果の構造体を定義して、 その結果の構造体に対しての述語手続きを用意する方法の方がうまい設計だといえるのかもしれないです。
いつでもこの方法が取れるかについてはよく分からないのですが、 この方法を採用した結果、設計がより綺麗になるのであれば、基本的にはこれでいいのかなという感じがします。
7. おわりに
私の趣味で実際に Luhn アルゴリズムを使いたいと思うことはあまりなさそうですが、書いてみて設計を検討したのはよい体験でした。 私的な自分の名刺を作成する際に、それぞれの名刺にユニークな番号を振っておいて、渡した相手に ID を振って何かの機会に入力してもらうみたいなことはギリギリありえるかもしれません。
久々に Typed Racket でプログラムを書いてみて、 「やはり Typed Racket はよいな」と思いました。 自分が Lisp を強く好んでいるというバイアスはかかっていますが、 なんというか丁度よく便利な型システムという感じがします。 万能なわけではないですが、今回定義した Digit 型のように Integer の一部分を型にできるのは結構嬉しいです。
今回私が定義した Digit 型は入力を制限することにしか役立たず演算が絡むとすぐに広い型になってしまって面倒なことになりますが、
Typed Racket で定義されている Natural
型は本当に便利です。
Natural
の値を zero?
で分岐すると
Zero
と Exact-Positive-Integer
に分かれ、
Exact-Positive-Integer
から 1 を引くと
Natural
型になることを活用することで、
factorial
や fibonacci
のような再帰手続きも普通に定義できますし、
Natural
型まわりの計算は Typed Racket 側でよくサポートされているので計算が絡んでも Integer
型になりくいのでだいぶ便利です。
負の整数の可能性が邪魔なことってプログラミングをしているとかなりあるので、結構嬉しいのではないかと思います。
とにかく Typed Racket は結構便利だというのが私の感覚なので、使ってみようと思っていただければ幸いです。
一回記事を書いてみて振り返った結果、 「失敗する可能性のある Boolean を返す手続きは定義しない」という方針が今回に限らず設計をよくする大切なヒントっぽいことに気づけてよかったです。 設計・実装時ではなんとなくの思いつきでやっていたことですが、 記事として書くことで言語化し、問題を整理することで気づきを得られたのだと思うので、今後も積極的に記事を書いていこうかなと思います。