Line 1: Error: Invalid Blog('by Esehara' )

または私は如何にして心配するのを止めてバグを愛するようになったか

>> Zanmemo

あと何かあれは 「esehara あっと じーめーる」 か @esehara まで

FizzBuzzによるTyped Racket入門 ーー静的に型を付けるLispに向けて

今日の看板

f:id:nisemono_san:20160707102555j:plain

概要

Lispにも静的型付けをおこなおうとする試みはされてきた。現在、その静的型付けLispを触るのにうってつけの環境は、恐らくTyped Racketだろう。そこで、FizzBuzzを通じて、Typed Racketがどういう型付け戦略を取っているのかを一通り試してみることにする。

はじめに

最近では、動的型付けを採用しているプログラミング言語でも、その言語を使った開発規模が大きくなるにつれて、なんらかの型チェックを行ないたいという需要が出てきている。

いくつかの言語、例えばPHPPython、既にType Hintingと呼ばれる、何らかの関数やメソッドに対して、引数の型と返り値の型を指定できるようになっている。これらが喜ばしいのは、その関数を利用するためのインターフェイスに関するドキュメントを、実行不可能なコメントによって注意を喚起するのではなく、型を利用して、実行可能な形でチェックすることができることがポイントとなっている。

さて、動的型付け言語と言えば、当然のことながら、Lispもその中に入ってくる。とはいえ、Lispに対して静的な型付けをおこなおうとする試みは無かったわけではない。例えば、Typed Schemeや、Shen、直近だとTyped Clojureなどがそれに当る。ただ、これらの環境は手軽に試せるものではない。そこで、手軽に試せる環境として、今回、Typed Racketに焦点を当てる。

今回語らないこと

静的型付け言語といっても、その型付け戦略に関しては様々な方法がある。Typed Racketの場合、Occurence Typingという方法を採用している。ただ、これに関しては、まだ理解が浅いことがあるので、今回は觝れないが、しかし論文自体はそこそこ見つかるので、興味ある方は参照するといいかもしれない。また、これらに関しても、理解を深めたのちに、このブログで書ければと思っている。

Typed RacketでFizzBuzz

大抵、新しいことをするときには、FizzBuzzを実装するようにしている。例えば、Typed Racketで普通にFizzBuzzを実装すると、次のようになる:

(: integer->fizzbuzz-helper : (-> Integer String))
;; これは Integer -> String でも良い
(define (integer->fizzbuzz-helper x)
  (cond [(= (modulo x 15) 0) "FizzBuzz"]
        [(= (modulo x 3) 0) "Fizz"]
        [(= (modulo x 5) 0) "Buzz"]
        [else ""]))

例えば、Haskellなんかを知っている人ならばわかりやすい記法かもしれない。最後がその関数の返り値となり、それ以外の最初の部分は引数の型となる。FizzBuzzのルールに関しては、慧眼な読者であるならば、既に知っているものであるし、他のブログでも散々語られていることなので、そのルールについては省略する。FizzBuzzは整数を取るため、型としてIntegerを指定することにする。そして、IntegerStringにするように指定する。

さて、これで困ったことがある。このようなFizzBuzzは型として冗長になる傾向にある。例えば上の関数を利用して、FizzBuzzをおこなう際、次のような感じになるだろう(なので、integer->fizzbuzz-helperという名前にした)。

(: integer->fizzbuzz : (-> Integer Void))
(define (integer->fizzbuzz x)
  (for ([i (range 0 x)])
     (let ([result (integer->fizzbuzz-helper (+ 1 i))])
        (display (if (string=? result "") x result))
        (display "\n"))))

さて、ここで一つ気になることがある。まず最初に、displayという関数は、基本的にAnyの型を取る。

> display
- : (->* (Any) (Output-Port) Void)

とするならば、関数の返り値は必ずしもStringに限定することではない。この実装の無理がある点は、Stringに限定しているため、FizzBuzzのロジックがinteger->fizzbuzz-helperから漏れ出てしまっている点にある。なので、StringIntegerも取りうるような型として、FizzBuzzという型を定義する。

(define-type FizzBuzz (U Integer String))

(: integer->fizzbuzz-helper : (-> Integer FizzBuzz))
(define (integer->fizzbuzz-helper x)
  (cond [(= (modulo x 15) 0) "FizzBuzz"]
        [(= (modulo x 3) 0) "Fizz"]
        [(= (modulo x 5) 0) "Buzz"]
        [else x]))

(: integer->fizzbuzz : (-> Integer Void))
(define (integer->fizzbuzz x)
  (for ([i (range 0 x)])
    (display (integer->fizzbuzz-helper (+ i 1)))
    (display "\n")))

define-typeの先頭に付いているUだけれども、これはUnion Typesと呼ばれていて、型同士の和を取るようにする。これ自体はさほど珍しいことではない。とりあえず、これでStringIntegerの両方の返り値を取れるようになったので、返り値に対して、StringおよびIntegerを返すことができるようになった。

しかし、わざわざこの程度のプログラムに対して、型を宣言することは冗長ではないだろうか。言ってしまえば、無名の型が指定できれば便利ではないだろうか。そこで、Racketの場合、直接Union型を指定することができる。

(: integer->fizzbuzz-helper : (-> Integer (U String Integer)))
(define (integer->fizzbuzz-helper x)
  (cond [(= (modulo x 15) 0) "FizzBuzz"]
        [(= (modulo x 3) 0) "Fizz"]
        [(= (modulo x 5) 0) "Buzz"]
        [else x]))

もっと考える

さて、FizzBuzzに関して無視していた事実が一つある。それは、FizzBuzzは正の整数に対して行なう対象であるということだ。なので、型で正の整数のみを対象とすることが保証できれば、そちらのほうが望ましいだろう。実際に、RacketにはPositive-Integerという型が用意されている。なので、これを利用する。

(: integer->fizzbuzz-helper : (-> Positive-Integer (U String Integer)))
(define (integer->fizzbuzz-helper x)
  (cond [(= (modulo x 15) 0) "FizzBuzz"]
        [(= (modulo x 3) 0) "Fizz"]
        [(= (modulo x 5) 0) "Buzz"]
        [else x]))

(: integer->fizzbuzz : (-> Positive-Integer Void))
(define (integer->fizzbuzz x)
  (for ([i (range 0 x)])
    (display (integer->fizzbuzz-helper (+ i 1)))
    (display "\n")))

しかし、これはエラーが起きる。具体的には下の通りだ。

Type Checker: type mismatch
  expected: Positive-Integer
  given: Integer in: (+ i 1)

これはコードを見る限り、とてもマイナスになりそうにもないのだが、しかしこの段階では、また(+ i 1)の型はIntegerなのだ。同様のことは、Racketのドキュメントにも書いてある:

> (: a : Positive-Integer)
> (define a 10)
> (: b : Positive-Integer)
> (define b 20)
> (: c : Positive-Integer)
> (define c (- b a))
. Type Checker: type mismatch
  expected: Positive-Integer
  given: Integer in: (- b a)

推論がどのように行なわれているか、現状ではちょっとわからないところがあるけれども、自分の仮説としてはこう。

型からすれば、Positive-IntegerPositive-Integerを引算した結果として、必ずしもその結果はPositive-Integerにならない可能性は十分にある。この例は直ぐに挙げることができる( 10 - 20ならマイナスになる)。つまり、型は、その型を組み合わせたときに何になるのか、にしか興味がなく、「実際にそれがどのような値になった結果、どの型になるのか」ということに関しては興味がないし、またそのような型としてはまだ表せていない。

とはいえ、何らかの型の変換方法が無ければ、Positive-Integerを指定した意味というのが無い。そこで、次のように指定する。

(define c (let ([result (- b a)])
              (if (positive? result) result
                  (error "Type Check Missing."))))

このように、positive?という判定を行なうことによって、必ずPositive-Integerが保証されるようになり、ちゃんとcに対して代入することが可能になるようだ。これを短縮した関数(というか、中身はマクロなのだが)としてassertが用意されている。上の式は、下のように書き直すことが可能だ。

(define c (assert (- b a) positive?))

assertは2番目の引数でチェックしたのちに、もしtrueであるならば、値を返し、falseならばエラーが起きるマクロである。このようにして、Racketでは、ある関数に入ってくる型がそうであるということを保証することになる。

さて、概要が分かったところで、早速FizzBuzzに対して手を入れよう:

(: integer->fizzbuzz-helper : (-> Positive-Integer (U String Integer)))
(define (integer->fizzbuzz-helper x)
  (cond [(= (modulo x 15) 0) "FizzBuzz"]
        [(= (modulo x 3) 0) "Fizz"]
        [(= (modulo x 5) 0) "Buzz"]
        [else x]))

(: integer->fizzbuzz : (-> Positive-Integer Void))
(define (integer->fizzbuzz x)
  (for ([i (range 0 x)])
    (display (integer->fizzbuzz-helper (assert (+ i 1) positive?)))
    (display "\n")))

というわけで、これで無事FizzBuzzが型付きでできるようになる。

雑感

知人と、この型について話をしたところ、このRacketが採用しているoccurence typingという方法が特殊なのではないかという示唆を貰った。確かに、関数の引数を渡す段階で型をチェックし、もしそのチェックが成功すれば、それはまたある型である、とする方法はちょっと不思議な感じもしなくはない。このあたりに関しては、論文が出ているので、それらを参考にもうすこし理解を深めようと思ったりもした。