Lua にタプルを実装したと思ったらリストだった。

Lua は素晴らしい言語なのですが、現実の言語である以上、使っていくと色々と不満点が出てきます。

local として宣言してない変数に触ると、暗黙のうちにグローバル変数として扱われる
- strict.lua を使っても、苦し紛れの解決でしかない
  - 実行時チェックなのでチェック漏れが起きる可能性が少なくない
    - 実行時チェックなのでパフォーマンスに若干の不安がある
  - 定義済みのグローバル変数への干渉は検出することが出来ない
  - module(...) 等のコードでモジュールを作った場合は効果がない
- local として宣言した変数と同じ名前のグローバル変数にアクセスしづらい
  - local hoge がある場合、 local G = getfenv(); G.hoge = xxx としなきゃいけない
多値を扱えるが、少しばかり残念なところもある
- 多値を変数に束縛する簡単な手段がない
  - テーブルはオーバースペック
  - クロージャを使うのがベストだが、組み込みで用意してくれない
    - function bind(...) return function() return ... end end って書きたいけど書けない
  - 束縛された多値を結合する簡単な手段がない
    - こんなコードは書きたくないし、見るからに非効率的！
  - C 関数を使えばマシになるが、 C との連携は環境依存性が強い
    - というか言語組み込みか標準ライブラリで用意すべきだろ JK
- 多値をテーブルのキーとして使えない
  - どうしても使いたい場合は、テーブルに入れた上で保存しておいて使い回すしかない
  - 独立に作られたテーブルだと、もうお手上げ状態
val 欲しい
- Java で言う final 、 C++ でいう const 的なアレ。超欲しい
  - ほとんどの変数は再代入なんてしないし
    - コンパイル時のコストは若干上がるかもだけど、無視できる程度だろ
    - 実行時にはコストかからないし、むしろ最適化しやすいだろ
    - というか luac コマンドに最適化を可能なかぎり行うオプションとか欲しい

エトセトラエトセトラ…。

で、今回はその中の一つ、多値の扱いについて、タプルが欲しいよねという話。
Python 分かる人は Python のタプルをイメージしてください。あんなのです。
具体的に、 Lua において僕が欲しいタプルの特徴を挙げると、

複数の値をまとめたもの
- 基本的には数値インデックスでアクセスする
- それ以外にも unpack や select があると良い
格納される値は immutable
- 再代入することが出来ないので安心して使いまわせる
- 再代入っぽいことをしたい場合は、要素を置き換えた新しいタプルを作る
オブジェクトではなく値の論理で動く
- つまり比較するときは中身を比較する
  - テーブルの場合は { 1, 2 } == { 1, 2 } は false だけど、それじゃ嫌
  - メタテーブルを使って == を書き換えたのでは対処できない場合も多い
    - 具体的にはテーブルのキーとして使う場合
全体的に、文字列をイメージすると分かりやすい

といったところでしょうか。

で、これらの特徴を満たすものを言語組み込みで欲しいな、と思うんですが、
Lua のコードをいじって組み込みで新しくタプル型を作ることは、確かに可能ではあるものの、
僕にはそこまでの気力はないし、出来たとしてもそれは純正 Lua とは別物なのでアレです。

というわけで、ライブラリで実装してみることにしました：
http://gist.github.com/708819

使用コード例：

require "tuple"

local t = tuple.new( 1, "a" )
print( t() )     -- 1	a
print( t(1) )    -- 1	a
print( t(2) )    -- a
print( t(3) )    -- 
print( t('#') )  -- 要素数 2

assert( t == tuple.new( 1, "a" ) )  -- もう一度作っても同じ！
local ls = {}
ls[t] = "hoge"
print( ls[tuple.new(1, "a")] )  -- hoge

-- list 風に
local t2 = tuple.cons( 1, tuple.cons( "a", tuple.nil_ ) )
assert( t == t2 )
assert( tuple.car(t) == 1 )
assert( tuple.cdr(t) == tuple.new("a") )

local nil_ = tuple.new()  -- 空 tuple
assert( nil_ == tuple.nil_ )

特徴としては、 Flyweight です。
つまり、同じ値の組から作られたタプルは、全て同じオブジェクトになります。
これにより、独立に作られたタプルでも、安心してテーブルのキーに使えるし、
数百個とか独立にタプルを作っても、実際のメモリ使用量は一個と変わりません。
また、クロージャベースなので、要素数が少ない時にはテーブルよりも高速に動作し、
中身の書き換えも原理的に起こりえないので、非常に安全。
もちろん、 Flyweight であっても、きっちり GC は動作し、
弱参照テーブルを多段に使ってるため、一度の GC サイクルでは全てのオブジェクトを回収できませんが、
繰り返し GC を実行することで、最終的には使われていない全てのタプルを回収できます。

一方で、 Flyweight にする為に、構築時のコストは大きくなっており、

また、これは完全に実装の都合上なのですが、長いタプルを使う場合、
要素数 N に対して Ο( N^2 ) のメモリ使用量を要求してしまいます。

これは勘違いでした。メモリ使用量は要素数 N に対し Ο(N) です。
ただ、普通に共有させた場合に比べ、メモリ効率があまりよくないのは事実。

なので、実用する場合は、せいぜい十数要素程度に押さえておき、
どうしても要素数が増えそうな場合には、タプルのタプルを作るなど、工夫が必要になりそうです。

と、このように問題点もありますが、
テーブルのキーとして自然に使えるタプルは、あると便利なのは間違いないので、
もし気に入ったなら、適当に改良しつつ、使ってみるといいんじゃないでしょうか。

// というかこれ、インターフェイス的にはどう見てもリスト…。
// リストと違って大量のデータは格納できないけどな！