メモ：A New Approach to Optimal Code Formattingを読む（2 Code layout）

これを読む。あんまり理解できる自信はない。

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}) ) \)

となる。