2015-07-04-01-CL-OVERLOADとCL-OPERATORとCL-STL - project-enigma

2015-07-04-01-CL-OVERLOADとCL-OPERATORとCL-STL

>> Site top >> weblog >> 月別アーカイブ >> 2015年07月のlog >> 2015-07-04-01-CL-OVERLOADとCL-OPERATORとCL-STL

最終更新日付:2015/07/04 23:50:00


CL-OVERLOADとCL-OPERATORとCL-STL

2015 年 07 月 04 日

Common Lisp をやり始めてからわりとすぐだったと思うけれど、C++ 標準ライブラリの STL を Common Lisp に移植する、という作業をやっていた。というか、やっている。Let Over Lambda の影響もあって、最初はコンテナやら何やらのクラスを全てクロージャで作成していたが、結局全てを捨てて CLOS と総称関数を土台にした設計でやりなおした。それが CL-STL と呼んでいる、もう何年イジっているかもわからないライブラリだ。

前回前々回書いていたのは、そこから基盤になるような機能を抽出したライブラリで、CL-OVERLOAD と CL-OPERATOR という。今回は、このあたりのことについて少し。

STL は、当たり前だけど C++ の言語機能を使っている。CL-STL を作るにあたって、Common Lisp でできなくて困ったなー、と思ったのは主に以下の2つだった。

  1. パラメータの数や型でもって関数などをオーバーロードする。
  2. 演算子のオーバーロード。

総称関数を使用すればパラメータとして異なる型を取る同名のメソッドを複数定義することはできる。しかし、パラメータの数を変えたければ &optional や &rest を使用せざるをえず、そのような可変部分ではパラメータの型を特定化することはできない。そのために作成したのが CL-OVERLOAD であり、これは総称関数の上に被せるマクロのラッパーだった。正確にはコンパイラマクロを使用しているので、それがちゃんと機能してくれればパラメータ数による解決はコンパイル時点で終わる。まずこれが1つ。

次に演算子のオーバーロード。Common Lisp では、たとえば + は関数であって総称関数ではない。また、様々なオブジェクトは基本的に参照が渡される。(setf a b) としたとき、そこで行なわれているのはおおむね( C/C++ で言えば)ポインタのコピーだ。しかし、STL(というか C/C++ )では値がコピーされる。イテレータ a と b に対して a = b と代入した後に ++a とすれば、a と b はもはや別の場所を指している。また、STL のイテレータは C/C++ のポインタのメタファーとして機能するから、ポインタにかけられる演算子は使い易くしておきたい。当初 CL-STL の中に無理矢理作り込んだそれらの機能を抽出したのが、CL-OPERATOR であり、その際に致し方なくポインタクラスも CL-OPERATOR に移動した。

で、CL-OPERATOR とはどんなものかといえば、やはりポインタのクラスを使って説明するのが一番早い。総称関数呼び出しをベタに使って書くと、以下のような口数の多いコードになる。

(let ((arr (make-array 10)))
  (do ((idx 0 (1+ idx))
       (p1 (operator_& arr  0) (operator_++ p1))
       (p2 (operator_& arr 10)))
      ((operator_== p1 p2) arr)
    (setf (operator_* p1) idx)))

=> #(0 1 2 3 4 5 6 7 8 9)

 

やっていることは配列に対してインデックスを指定して operator_& を呼び出すことでポインタクラスのオブジェクトを作成している。そして operator_++ でインクリメントするループ。まぁこれ以上は説明の必要はないだろう。で、operator と毎回タイプせずに済ませるためのマクロを使えば以下のようになる。まぁ美しくはないよね。

(let ((arr (make-array 10)))
  (do ((idx 0 (1+ idx))
       (p1 (_& arr  0) (_++ p1))
       (p2 (_& arr 10)))
      ((_== p1 p2) arr)
    (setf (_* p1) idx)))

=> #(0 1 2 3 4 5 6 7 8 9)

 

で、CL-OPERATOR が提供する with-operators マクロを使うと、いわゆる単項演算子をそれっぽく書くことができるようになる。以下のように。

(let ((arr (make-array 10)))
  (with-operators
      (do ((idx 0 (1+ idx))
           (p1 &arr[0] ++p1)
           (p2 &arr[10]))
          ((_== p1 p2) arr)
        (setf *p1 idx))))

=> #(0 1 2 3 4 5 6 7 8 9)

 

CL-STL では、STL の std::vector にあたる stl:vector などでは内部的に使用する配列を simple-vector にしていた。そして STL アルゴリズムを移植した部分でも、配列のための最適化実装では simple-vector としていた。しかし、CL-OPERATOR を分離する際、これを全て cl:vector として declare type するようにした。そして CL-STL 側のアルゴリズムでも simple-vector でなく cl:vector を扱うように変更。これにより、cl:character の配列である cl:string (の要素を指すポインタ)をアルゴリズムにかけることができるようになった。例を示そう。文字列に対して、登場する文字から重複を除去した文字の並びを返すには以下のようにする。

(let* ((str "abracadabra")
       (len (length str)))
  (with-operators
      (let ((p1 &str[0])
            (p2 &str[len]))
        (stl:sort p1 p2 #'char<)
        (let ((p (stl:unique p1 p2 #'char=)))
          (setf str (subseq str 0 (_- p p1))))))
  str)

=> "abcdr"

 

使っているのは文字列の要素を指すポインタの組みと、アルゴリズム stl:sort および stl:unique だ。文字の比較や等値検査には Common Lisp 標準の関数をそのまま与えている。STL 同様、CL-STL の stl:unique はシーケンスの長さ自体は変更しないで重複を除去したシーケンスを先頭部分に作って末尾を指すイテレータを返すから、最後に subseq を使って文字列を切り詰めている。

そもそも、CL-STL から CL-OPERATOR を分離したのは use-package してしまいたいからでもあった。STL が使う名前には、CL パッケージがエクスポートしているシンボルとカブるものが非常にたくさんある。vector とか list とか sort とか、本当にたくさんだ。だから CL-STL は stl:vector のように常にパッケージ名で修飾する前提にしていた。そうなると、operator_* なども全て stl: でもって修飾しなければならなくなる。それが我慢ならなかったんだな。

 

なんだか散漫な文章になってしまったけれども、大体こんなところだ。CL-STL と、そこから独立させた CL-OVERLOAD と CL-OPERATOR。今回は CL-OVERLOAD についてはほとんど何も書いていないけれど、もし自分が書いた Common Lisp のコードを公開するとしたら、おそらくこれらの3つが最初になると思う。問題は、ドキュメントが中途半端(あるいは皆無)ということだ。でもそこに満足がいくまで公開しなかったら、おそらく永久に未完成ということになると思う。中途半端な状態でも動作するなら公開してしまって、使ってくれる方がいるならそれを励みにしてドキュメントを頑張る、というのがいいのかもしれない。

 

コメント

このページにコメントする

 

このページのタグ

Page tag : Common Lisp

 

 


Copyright(C) 2005-2017 project-enigma.
Generated by CL-PREFAB.