読者です 読者をやめる 読者になる 読者になる

きくらげ観察日記

好きなことを、適当に。

OCamlのFunctorという概念を知らずに自分で再発明していた話

最近わけあってOCamlの勉強をしているのですが、OCamlは多相的な関数を定義する方法として、Functorというものを持っています。

(* 要素の型と、その比較方法を定義するモジュール *)
module type Cmp =
  sig
    type elt
    val le : elt -> elt -> bool (* <= *)
  end

(* Cmp の int による実装 *)
module IntCmp : Cmp with type elt = int =
  struct
    type elt = int
    let le = (<=)
  end

module type Max =
  sig
    type elt
    val max : elt -> elt -> elt
    val min : elt -> elt -> elt
  end

(* モジュール Cmp を受け取って、 max と min が定義されたモジュールを返す Functor *)
module Max (C : Cmp) : Max with type elt = C.elt =
  struct
    type elt = C.elt
    let max (x : elt) (y : elt) : elt =
      if C.le x y
      then y
      else x
    let min (x : elt) (y : elt) : elt =
      if C.le x y
      then x
      else y
  end

module IntMax : Max with type elt = int = Max(IntCmp)

let main : unit =
  Printf.printf "max 2 3 = %d\n" (IntMax.max 2 3);
  Printf.printf "min 5 0 = %d\n" (IntMax.min 5 0)

まだOCaml初心者なので拙い書き方になっているかもしれませんが、なんとなく雰囲気は伝わったと思います。
要するに、OCamlのFunctorとは「モジュールを引数にとってモジュールを返す関数」のようなものです。


しかし、このFunctorという概念について、自分は思い当たるものがありました。
これは紛れもなく、自分が以前JAKLDに実装した、モジュールを利用した多相性を扱う手段でした。


話は数年前に遡ります。
まだ自分が京都大学情報学科の1回生の頃の話でした。
当時の京大の情報学科では、新入生が最初に学ぶ言語はJAKLDという言語でした。

JAKLDはSchemeの一種の方言であり、学生がどんな環境のPCでもSICPの勉強ができるようにと、その昔京大の教授がJavaで開発した処理系でした。
確かに、JAKLDはSICPに登場する関数や図形言語の(たぶん)全てを扱うことができます。
しかし、この処理系はR5RSのサブセット+α程度のものでしかなく、実用的なプログラミング言語とは程遠いものでした。

JAKLDにはモジュールシステムすら無く(モジュールがSchemeに導入されたのはR7RS以降なので、当たり前といえば当たり前ですが)、その環境で複雑なコードを書くのは苦痛以外の何者でもありませんでした。

そこで自分がまず開発したのは、Angularを参考にしたDIによるモジュール管理システムでした。
実際のコードは紛失してしまったのですが、大体以下のような雰囲気でモジュールを定義することができるようなライブラリです。

(define my-module
  (make-module '(mod-a mod-b) ; インポートするモジュールのリスト
   (lambda (mod-a mod-b) ; モジュール自体は引数で受け取る
     (define (my-func foo)
       ;; モジュール内の関数 a は (mod 'a) で受け取る
       ((mod-a 'some-func) foo))
     (define my-value 3)

     (export `((my-func . ,my-func)
               (my-value . ,my-value)))
     )))

その後、Haskellのようなアドホックな多相性が欲しくなり、それを実現するために試行錯誤することとなりました。
まず最初に試してみたのは通常のLispのように、多相性が欲しくなる部分を引数として受け取る方法です。

(define (my-sort lst my-comperator)
  ;; comperator を使って要素を比較し、ソートする
  ...)

しかし、例えばHaskellでいう

someFunc1 :: (Eq a, Ord a, Show a) => a -> b
someFunc2 :: (Eq a, Ord a, Show a) => a -> c
someFunc2 = somehow $ someFunc1 a

のような関数を定義したい場合、Schemeでは以下のような非常にわかりにくいコードになってしまいます。

(define (some-func1 a a-eq? a-compare a-show)
  ...)
(define (some-func2 a a-eq? a-compare a-show)
  (somehow (some-func1 a a-eq? a-compare a-show)))

多相性が必要な関数は、その型に関するすべての動作を引数で受け取らなければなりません。
そのため、多相性が必要な型に関する制約が複雑になれば、それだけ引数の長さも増えていきます。
また、多相性が必要なすべての関数に操作を引数として与えなければならないので、非常にコードが長くなります。

複数の関数を1つのデータ構造にしてまとめたりしてみましたが、根本的な解決にはなりません。


そこで思いついたのは、型aに関する複数の定義をまとめたモジュールを引数に受け取って、そのモジュール用に具体化されたモジュールを返すといった方法でした。
例えば、以下の例では<という関数を定義しているモジュールを引数にとって、その比較方法でソートを行うモジュールを返す関数のようなものを定義しています。

(define my-module2
  (make-module
   '(comparable) ;; 引数モジュール
   '(mod-a mod-b) ;; インポートリスト
   (lambda (comparable)
     (lambda (mod-a mod-b)
       ;; 引数で受け取ったモジュール内の < を利用して
       ;; ソートを行う関数
       (define (my-sort lst)
         (sort-by lst (comparable '<)))

       (export `((my-sort . ,my-sort)))
     ))))

この「モジュール」を引数モジュール付きでインポートする構文は、確か次のようなものだったと思います。

(define main-module
  (make-module
   '()
   '((my-module2 int-cmp))
   (lambda ()
     ;; my-mod2-int には、 my-module2 を int 用に特殊化したものが入る
     (lambda (my-mod2-int)
       ...
       ))))

このようなモジュールシステムを作ることによって複雑な多相性を持つ関数を簡単に定義できるようになった僕は、これは大発明だと喜びながらその上でモナドやら何やらをせっせと構築していきましたとさ。めでたしめでたし。



今改めて考えてみると、この「モジュールを引数に取るモジュール」はOCamlのFunctorに他なりません。
当時の自分は他のどの言語にもない大発明だと思っていたので、少しショックですね……。