Vaporware

These are some ideas of softwares that I haven't implemented (yet).

Ipomoea

A dot-file manager using Git (or any other VCS's) as its version control backend. I already have one, but want to redesign it and make it publicly available.

Celaenito

An implementation of the Web Archive mainly for private use, but it'd be cool if it optionally forms a P2P web-archiving network.

Many years ago I already implemented it in Perl, but it has bitrotted now, doesn't work anymore. So I want to reimplement it in Haskell.

HyperEstraier works. It actually works. It's even used in this very site. But... its DB backend QDBM is way too fragile to live with. So I want to reimplement it in a more robust way in Haskell.

(Unnamed) Natural language translator using Lojban as an intermediate language

Lojban is very promising language to build a translator on it. I think I might start from English→Japanese translation but can be extended to any other pairs of language.

(Unnamed) GStreamer-like multimedia streaming framework implemented in Haskell

Wouldn't it be cool if we have a multimedia streaming framework implemented in Haskell, especially if it's purely functional and based on FRP?

I also want it to gain benefits from parallelism, instead of explicit concurrency (i.e. threads).

(Unnamed) Virtual filesystem with file attributes and version control, similar to Subversion FS

Subversion FS works well for this domain. It's actually used in this site. But... it doesn't play nice with Haskell, and its documentation is... well... abysmal.

So I need my own Haskell implementation of it.

Cocoli: Write-ahead transactional key-value data storage

I'd like to someday implement this in Haskell.

Brief summary

  1. キーも値も任意のバイナリ。
  2. レコードの挿入と削除(上書きも含む)はその情報を追記する事のみによって行う。
  3. レコードを参照するには、まずファイルの後ろの方から辿ってキーを探して行き、最初に見付けた情報を採用する。

Order of operations

レコード新規挿入
O(1)
レコード上書き
O(1)
レコード削除
O(1)
レコード検索
DB 履歴件数 n に対して O(n)。但しキーからレコードの最新位置(もし存在しないならその事実)への写像をキャッシュする事は可能で、その場合キーはバイナリであって順序比較可能なので lrucache を用いて O(log n) 程度まで下げる事ができる。

Transaction

  1. transaction (tx) を開始する時は、開始時のファイル末尾のオフセットを覚えておく。
  2. tx 中に DB がどのように書き変わろうとも、問題のトランザクションは開始時オフセットより前の情報しか見ないので、read-committed となる。
  3. tx 中に観測したレコード位置は全て記憶しておく。tx 中でのレコード追記/削除はまだファイルには書かないでおく。
  4. commit の際、もし観測していたレコードのいずれかが最新のものではなくなっていたら、commit は失敗する。そうでなければ書換内容を一気にファイルに追記する。これにより serializable となる。(その最中に crash しても問題が起きないように工夫せよ。)
  5. 最適化の案として、ファイルにレコードを追記する際には、そのレコードを観測している全てのトランザクションを即座に失敗させるという手がある。

Compactification

これが難しい。おそらくこれをやってる最中は stop-the-world が必要だろう。

  1. ファイルの先頭にあるレコードを見る。それが生きているかどうかを調べて、もし生きていたら次のレコードへ行く。死んでいたら、そのチャンクの領域を dead area として覚えておく。もし見付けたのがレコードの削除を表す情報だったら、それは無条件で dead area に加えて良い。
  2. 最初に見付けた living record について、もしその record を最初の dead area にそのまま移す事ができるなら、つまり最初の dead area の方が問題の living record よりも広いならば、dead area にコピーした上で living record が元々あった場所を dead area とする。この時、その dead area がファイルの末尾にあれば、ファイルを truncate する。
  3. 最初の living record の方が最初の dead area よりも大きかった場合は、まずその living record をファイルの末尾にコピーし、元あった場所を dead area にする。このとき拡大された dead area は常に今移動した living record よりも広いので、移動したばかりの living record を dead area にコピーして、ファイルの末尾を truncate する。
  4. レコードを移動した時は、その時に存在する全ての tx の観測レコード一覧の中から該当するレコードのオフセットを書換えておく。なぜならここではレコードを移動しただけで内容を変更したわけではないから。
  5. この操作をファイルの末尾まで続ける。

(Unnamed) 2-dimensional cellular automaton with the concept of mass and energy

空間の広さは有限であり、上下と左右は繋がってゐる(1次元トーラス、レゲー的空間)。

各セルは次の情報を持つ。

  • quark が有るか無いか (0 または 1)
  • エネルギー値 (0.0 から 1.0)

quark を持たない各セルは eGen + eGen' を越えない範圍でエネルギー値を持つ。eGen + eGen' を越えた瞬間に quark が生成され、餘剩エネルギー eGen' が周圍に均等に發散する。既に quark を持つセルはeGen + eGen' よりも大きなエネルギーを持つ事が出來る(そのエネルギーが移動や結合等を起さない場合)。一つのセルが持てるエネルギーの最大量は 1.0 であり、それよりも大きなエネルギーを與へようとすると周圍に漏れる。

quark に エネルギー eCol を與へると quark が崩壊し、エネルギーeGen + eCol が周圍に均等に發散する。

quark はエネルギー ePush を受けると、そのエネルギーが來たのとは逆の方向に移動し、それまで自分が占めてゐたセルにエネルギー ePush を殘す。(ここで殘ったエネルギーが eGen + eGen' を越えてゐたら次のターンで eGen' が發散する。)

隣接する二つの quark の片方にエネルギー eJoin + eJoin' を與へると、その二つの quark を結合させる事が出來て、餘剩エネルギー eJoin' が發生する。結合された quark が移動される時には常に「引き摺られて」移動する。

結合してゐる二つの quark の片方にエネルギー eSplit を與へると、その結合を解く事が出來る。結合が解かれるとエネルギー eJoin + eSplit が發散する。

quark を移動させる際には、それを移動させる事で同時に動く(結合されてゐるか、若しくはその quark の移動によって押される)quark の數 n に對して ePush * n のエネルギーが必要になる。

quark の移動よりも quark の結合の方が起こり易い。つまり ePush > eJoin が成り立つ。

quark の分離よりも quark の移動の方が起こり易い。つまり eSplit > ePush が成り立つ。

quark の崩壊よりも quark の分離の方が起こり易い。つまり eCol > ePush が成り立つ。

eGen > eGen' であり、eJoin > eJoin' である。

まとめると、eJoin' < eJoin < ePush < eSplit < eCol となる。eGen と eGen' は獨立。

閉ぢた系である以上はエントロピーが長期的に増大して行くに決まってゐるので、初期状態のエントロピーは小さくなければ意味が無い。つまり充分に少ない點に高いエネルギーが集中してゐなければならない。

畫面上では、1セルが1ピクセル(またはその整数倍の長さの邊を持つ正方形)として表される。セルの持つエネルギー量は明度として表され、エネルギーゼロの時に濃灰色、エネルギー最大の時に明灰色になる。quark が存在する場合は RGB 値に決まった色が加算される。