eoml0002 のバックアップ(No.1) - khfdpl-wiki

[ トップ ] [ 新規 | 一覧 | 単語検索 | 最終更新 | ヘルプ ]

バックアップ一覧
差分を表示
現在との差分を表示
ソースを表示
eoml0002 へ行く。
- 1 (2017-02-20 (月) 13:52:07)
- 2 (2017-02-20 (月) 16:03:14)

Essen Object Management Library #0002

(by K, 2017.02.20)

レイヤ構造

Essen：言語レイヤ
ObjSys(OS) : オブジェクトの管理をするレイヤ
- 階層構造など
ValSys(VS) : 値の管理をするレイヤ
- 可変長なデータを扱いやすくする＆メモリ管理＆重複管理

基本型

通常データ：
- intとかdoubleとか文字列型とか、まあなんでも。
- サイズが規定できればよい。型のタイプも記述する。
- 可変長でもあってもいい。
メタデータ：
- 通常データと似た扱いを受けるが、多少の追加サポートがある。
- (dir) (memberTable) (namelessDir)

ディレクトリ

Essenにおけるディレクトリは、構造体と配列を融合したようなもの。
たとえば以下のようなデータを考える。
```
(a:1 b:2)
```

このデータをシステムは以下のように管理する。

p0: (dir)[p1 p2 p3] // p1がメンバ名情報, p2とp3は値.

p1: (memberTable)[2 p4 p5] // 2はメンバ総数, p4とp5は名前.
p2: (int)[1]
p3: (int)[2]
p4: (string)["a"]
p5: (string)["b"]

このとき、さらに以下のような記述をしたとする。
```
(a:3 b:1)
```
このデータは次のように管理される。
```
p6: (dir)[p1 p7 p2]

p7: (int)[3]
```
- つまり、データは共有される
  - ただしデフォルトで自動共有されるためには条件がある
  - しかし明示的に共有を指示すれば確実に共有部分は共有される
  - 自動共有がデフォルトではない最大の理由は、重複排除のための比較にそれなりにコストがかかるため。
  - もちろんハッシュ値などを使って高速化するが、それでも何もしないよりはどうしたって遅い。

さらに以下のようなケースを考える。
```
(0:(a:1 b:2) 1:(a:3 b:1))
```

このデータは次のように管理される。

p8: (dir)[p9 p0 p6]

p9: (memberTable)[2 p10 p2]
p10: (int)[0]

ただし、メンバ名が(int)で0,1,2,...の場合に限って簡略表現を用意したい。そうすればメンバーテーブルの氾濫を緩和できる。

メンバ名を持たないディレクトリも作れる。
```
((a:1 b:2) (a:3 b:1)) → (namelessDir) [2 p0 p6]
```
- まあそれぞれの名前をnulにしても同じことはできる。しかし出現頻度を考えると、内部的に(namelessDir)があったほうが有利だと思う。

（註）初期のバージョンのEssenでは双方向リストを使ってこれらを管理していたが、今後のバージョンではこのように双方向リストを使わない実装をメインに据える。

配列

メモリをより節約したいという観点では、ディレクトリのメンバの型がすべて同じときには、それらをまとめられる機能がほしくなる。
- でもそんなことをしても大して節約できないのかもしれない。
- ということでまずは検討してみる。効果が大したことなければ没にする。
p8の内容を書きかえてみる。
```
p11: (array) [p9 p1 p2 p3 p7 p2]
```
- これでどれだけ節約されたのか？
- p0やp6の内容はいらなくなった。それでオブジェクト2つが節約できた。ポインタの数としては差し引き3個得した。
- 微妙だなあ。役に立っていると言えばそうなんだけど、内部タイプを増やすだけの価値があるかというと悩ましい。
よし、悩んだときは作らない！

サイズの省略

(memberTable)でサイズを明示する必要ってあるだろうか？データのサイズは取得できるのだから、そこから分かりそうなものだ。
(namelessDir)にもサイズは不要だろう。

双方向リストのサポート

Essenの式評価アルゴリズムを考えると、要素の挿入や削除がかなり頻繁に繰り返されるので、双方向リスト的なものはやはり必要である。だからそのサポートも必要だ。
双方向リストのノードは、前後が誰であるかという情報を持っているので、そのポインタ情報があだとなって値が同じでも共有はまずできない（＝他と同じ値になることはまずないだろう）。
となれば、値だけを別のオブジェクトに追い出すことによって共有の可能性を高めるという方法は可能ではある。
```
(doublyLinkedList) [p0 p1 p2]
```
- p0がprev, p1はnext, p2がvalueへのポインタ