これを読む。あんまり理解できる自信はない。
https://research.google.com/pubs/pub44667.html
2.1 Layouts and Combinators
2つの記号を導入している。
\( l_1 \updownarrow l_2 \)
\( l_1 \) と \( l_2 \) の順に垂直に積み重ねる
l1l1l1l1l1 l2l2l2l2l2
\( l_1 \leftrightarrow l_2 \):
\( l_1 \) と \( l_2 \) の順に水平に並べる。
l1l1l1l1 l2l2l2l2l2
ただし、両方とも複数行になる可能性があって、その場合は
placing the first character of \( l_2 \) on the same line as and immediately to the right of the last character of \( l_1 \), translating \( l_2 \) bodily rightwards
らしい。\( l_1 \) の最後の文字の横に \( l_2 \) の行頭をそろえる。
l1l1l1l1 l2l2l2
l2l2l2l2l2
例えば、例として、
('if (voltage[t] < LOW_THRESHOLD)' \( \updownarrow \) ' ') \( \leftrightarrow \) 'LogLowVoltage(voltage[t])'
が
if (voltage[t] < LOW_THRESHOLD)
LogLowVoltage(voltage[t])
と解釈される。' 'が明示されていることからわかるように、インデントの付け方はまだ扱えない。
2.2 Choosing layouts
先ほど挙げた例のコードは、
('if (voltage[t] < LOW_THRESHOLD)' \( \leftrightarrow \) ' ') \( \leftrightarrow \) 'LogLowVoltage(voltage[t])'
とも書ける。つまり、
if (voltage[t] < LOW_THRESHOLD) LogLowVoltage(voltage[t])
ということ。これはどちらも文法的にも意味的にも等価なコードになる。どちらを選ぶかは行数や行幅の制限や好みによる。
To capture the trade-off in quantitative terms, we associate a cost with a code layout: When code is output according to the layout, we incur a cost of \( \beta \) units for each character beyond the right margin, and a cost \( \alpha \) for each line break output.
そこにはトレードオフがある。右のマージンを超える文字ひとつにつきコスト \( \beta \) が、改行ひとつにつきコスト \( \alpha \) がかかるとする。このコストが小さいものが「よい」フォーマットだとみなす、ということらしい。
ここで、さらに新たな記法?を導入して、上の2つの表現式は次のようにまとめられる。
\( [ \) ('if (voltage[t] < LOW_THRESHOLD)' \( \updownarrow \) ' ') ? ('if (voltage[t] < LOW_THRESHOLD)' \( \leftrightarrow \) ' ') \( ] \)
\( \leftrightarrow \) 'LogLowVoltage(voltage[t])'
一般的にコードの表現式は以下のように表すことができる。
\( (l_{11} ? l_{12}) \leftrightarrow (l_{21} ? l_{22}) \leftrightarrow \cdots \leftrightarrow (l_{n1} ? l_{n2}) \)
つまり、\( 2^n \) 通りの可能性がある。それを計算するのは大変すぎるけど、効率的なやり方を考えましたよ、というのがこの論文の主旨っぽい。
2.3 Dynamic programming and optimal layouts
\( l_{i1} ? l_{i2} \) を \( l_i \) と置く。ここで、\( l_i \) の項は明らかに \( l_{i+1} \) のレイアウトに影響を与える（\( i = n \) を除く）。\( i = n, \cdots, 1 \) に対してコストを比較するためにはまず、
we need to know the horizontal extents or spans of the two component expressions in \( l_i = l_{i1} ? l_{i2} \)
らしい。このhorizontal extentsを仮に定数として \( s_{i1}, s_{i2} \) と置く。
（このあたりよくわからない…）
これを、目的関数 \( f_i \) の最小化問題として考える。
もし \( l_i \leftrightarrow l_{i+1} \leftrightarrow \cdots \leftrightarrow l_n \) の結果のインデントを \( x \) 文字とおくと、 選択肢1を選んだ場合の \( l_{i+1} \leftrightarrow \cdots \leftrightarrow l_n \) の結果のインデントは \( x + s_{i1} \) となる。
目的関数 \( f_i \)は、
\( x \mapsto \min( c_{i1} + f_{i+1}(x + s_{i1}) + f_{i+1}(x + s_{i2}) ) \)
となる。