Document

Designing Constraint Maintainers
for User Interaction
2005.6.6
東京大学情報理工学系研究科
電子情報学専攻修士１年
高橋慧
1
発表の流れ




s
Maintainerの復習
Biased Selector
Maintainerの合成
ここまでのまとめ
2
Maintainerの実例
 HTMLエディタ
 グラフィカルビューとソースコード
 タグに関する制約(開きタグ、閉じタグ…)
 maintainerの動作
 ビューのtable中でenterを押したとき、ソースコードに挿入
するのは<tr>か<br />か
 ソースで”<t”と入力したとき、補完するのは<td>か
<table>か
 お節介にならないように、制約も満たすように。
 ユーザーの意志を尊重 → least change
 動作の予測ができるように→ left most / predictable
⇒ビュー / ソースの変化に対し、最適な変化を選択
st
3
復習 : maintainer
 制約R:x～yを常に満たしたい
 yが変化したら、制約Rを満たすようxを変化
→maintainer xy
 maintainerの定義
 -EST : [(xy)Ry]
 -SKIP : [xRy → (xy)=x]
(他にもいくつか同値な定義がある)
 maintainerの望ましい動作
 xの候補が複数→今のxからの変化を最小に
 最小な候補が複数→left most (predictable)
sty
4
MaintainerをSelectorとして見ると…
 maintainerはRyに対するselectorと見れる
 Ryという集合から最適(最小)な要素を選択
 xによって変化する (selector自体がxの関数)
 x§ と表すと、maintainer xy の動作は
x’ = x§(Ry)と書ける
→”Biased Selector”と呼ぶ
 Biased Selectorを考えるメリット
 Biased Selector自体はR(制約)に依存しない
 “よい”maintainerの構成手続きが与えられる
styl
5
Biased Selectorの定義
 定義
A) Selectorの条件を満たす
1. x§S ∈ S
2. x§(S∪T) = x§{x§S, x§T}
B) if x ∈ S : x§S = x
 Well-Orderedな集合には必ずx§が存在
 例えば以下のように構成できる
 if x∈S : x§S = x
 else
: x§S = init(S)
style
6
Biased Selectorとmaintainer
 biased selector ⇒ maintainer:[成立]
 -EST : [(xy)Ry]
 (a.1 : x§S ∈ S) で S=Ryとすればよい
 -SKIP : [xRy → (xy)=x]
 (b: if x ∈ S : x§S = x) そのもの
 maintainer ⇒ biased selector:[不成立]
 (a.2:x§(S∪T) = x§{x§S, x§T})が問題
 least changeに関連
styled
7
“良い”Biased Selectorを構成
 maintainerとしての良い性質を持つ
 least change, left most (predictable)
 x§Sを構成 (Sはwell-ordered)
 “xとの近さ”を定義する (編集距離など)
 S中でxに最も近い距離を持つ集合をCx(S)とおく
 x§S =init(Cx(S))とする
(initは元々のwell-orderを構成したmin)
 このx§は、Biased Selectorになっている
styled b
8
x§がBiased Selectorになっている証明

復習



Cx(S):Sのうち、xからの距離が最小の要素の集合
init(S):Sの最小値(みたいなもの)
a.1 : x§S ∈ S

x§の定義: x§S = init(Cx(S))
⇒ {init(A) ⊆ A, Cx(S) ⊆ S} より x§S ∈ S

a.2 : x§(S∪T) = x§{x§S, x§T}



x§の定義: x§(S∪T) = init(Cx(S∪T))
init(Cx(S∪T)) ∈ Cx{x§S,x§T}


Cx(S∪T) ⊆ Cx(S) ∪ Cx(T)
init(Cx(S∪T)) ∈ {init(Cx(S)), init(Cx(T))} = Cx{x§S,x§T}



init(Cx(S)) ⊆ Cx(S), init(Cx(T)) ⊆ Cx(T)
{x§S,x§T} ⊆ Cx(S∪T)
Cx(A) ⊆ AよりCx{x§S,x§T} ⊆ Cx(S∪T)
Cx{x§S,x§T} ⊆ Cx(S∪T)
⇒ {initの性質: A⊆B ∧ init(B)∈A ⇒ init(A)=init(B)}より

init(Cx(S∪T)) = init(Cx(x§S∪x§T)), x§(S∪T) = x§{x§S, x§T}

b : if x ∈ S : x§S = x

styled by
(x∈S) ⇒ (Cx(S) = {x}) ⇒ (init(Cx(S)) = x) ⇒ (x§S = x)
9
maintainerの推移的合成
 制約R:x～y S:y～zを合成 → T:x～z
 x T z は xR (yS z) として構成できる?
 一般にはyを隠すとx～zが構成できない
 例えばx:ある実数 y:実数集合 z:ある実数で、
xがyの項数、zがyの正の項数とする。
maintainer : x～zは、yを考えないと構成できない
 y=f(x)の関係があるとき(#Ry=1)はOK (証明略)
 複雑な制約を分解してmaintainerを構成できる
styled by K
10
maintainerの統合
 R:x～y, S:x～y → T=R∪S:x～y
 TをRとSから合成
 T=x§{xRy, xSy}とすればよい
 証明
 xTy
= x§((R∪S)y)
…x§の定義
= x§(Ry∪Sy)
…自明ではないが省略
= x§{x§(Ry), x§(Sy)} … Selectorの定義
= x§{xRy, xSy)}
…x§の定義
 x§がR,Sに依存しないのがポイント
styled by Ke
11
3,4章のまとめ
 Maintainerの構成




複数の候補から一つを選ぶ→順序の定義が必要
Well-order : 大小関係が一意に定まる順序
Selector :”最小値”の必要十分条件
Biased Selector : xを基準にしたselector
 Maintainerの統合・合成
 T=R;S : Rが関数で表せれば合成できる
 T=R∪S : 常に合成できる
 maintainerの実例に続きます。
styled by Kei
12

Download Report