mad日記

■[Erlang] erlangのアセンブリを読んでみる． 04:36

Erlangが末尾再帰最適化をしてるか調べようとした - みずぴー日記

に興味が湧いたので，erlangのアセンブリコードを見てみた．beamのバイトコードにほぼ一対一対応していると考えていいと思う．

まず単純な定義の場合

fact(0) -> 1;
fact(N) -> N * fact(N-1).

以下のようになる．アセンブリコードの各行はそのままerlangのタプルとなっている．ここで，

• {x, N}: はx registerという．Nはレジスタ番号．
• {y, N}: はy registerという．レジスタという名前だが，スタック上に置かれる．
• {f, N}: は{label, N}に対応している．{f, 0}はプログラム終了コードのラベル．

{function, fact, 1, 2}.   % 引数1個, {label,2}がエントリーポイントという意味．
  {label,1}.
    {func_info,{atom,fact},{atom,fact},1}.
  {label,2}.
    % 引数は{x, 0}に入っている．
    {test,is_eq_exact,{f,3},[{x,0},{integer,0}]}. % N!=0なら{label, 3}に飛ぶ
    {move,{integer,1},{x,0}}. % 戻り値は{x, 0}に入れる
    return.
  {label,3}.
    {allocate_zero,1,1}. % スタックフレームを1ワード分確保．
    {gc_bif,'-',{f,0},1,[{x,0},{integer,1}],{x,1}}.
    {move,{x,0},{y,0}}.  % もとのNをスタックに退避
    {move,{x,1},{x,0}}.
    {call,1,{f,2}}.       % 再帰呼び出し．1は引数の数を表す．
    {gc_bif,'*',{f,0},1,[{y,0},{x,0}],{x,0}}. 
    {'%live',1}.
    {deallocate,1}.
    return.

見ての通りerlangだからといって何も特殊な点はなく，いたって普通のコードだった．

スタックも通常どおり消費されているので，Erlangが末尾再帰最適化をしてるか調べようとした - みずぴー日記でスタックオーバーフローしないというのは単にスタックを大きく取れているからなのだと思う．

続いて末尾再帰バージョンを見てみる。

fact(N) -> fact_iter(N, 1).

fact_iter(0, R) -> R;
fact_iter(N, R) -> fact_iter(N-1, N*R).

{function, fact, 1, 2}.
  {label,1}.
    {func_info,{atom,fact},{atom,fact},1}.
  {label,2}.
    {move,{integer,1},{x,1}}.
    {'%live',2}.
    {call_only,2,{f,4}}.

{function, fact_iter, 2, 4}.
  {label,3}.
    {func_info,{atom,fact},{atom,fact_iter},2}.
  {label,4}.
    {test,is_eq_exact,{f,5},[{x,0},{integer,0}]}.
    {move,{x,1},{x,0}}.
    return.
  {label,5}.
    {gc_bif,'-',{f,0},2,[{x,0},{integer,1}],{x,2}}.
    {gc_bif,'*',{f,0},3,[{x,0},{x,1}],{x,1}}.
    {move,{x,2},{x,0}}.
    {call_only,2,{f,4}}.

末尾呼び出しの部分がcall_onlyとなっているので，確かに末尾再帰の最適化が行われている事が分かる．y registerが使われていない事からもスタックが消費されていないことが見て取れる．

ところでこれらのコードをみる限り，スケジューラとレジスタ割り当てがあまり賢くないようだ．

コンパイル時間を優先して簡略化しているのかな．[追記]コンパイラを見てみたら、そもそも命令スケジューリングを行っていないように見えた．もしかしたらアセンブリ -> バイトコードのフェーズか，beam側で何かやっているかも知れない．

■ [C/C++][コンパイラ] オペランド評価の実際 16:22

こことか

• http://code.nanigac.com/forum/view/342

こことか

• http://www.st.rim.or.jp/~phinloda/cqa/cqa7.html

で話されているオペランドの評価に関してだけれども, もちろん処理系依存なので一般的な議論はできないが,実際のところコンパイラの実装がどうなっているかは興味がある所ではないかと思う。

例えばC Q&Aの例の

int i = 7;
printf("%d", i++ * i++);

が49になるのは, まぁ納得できる人は多いと思うけれども,

int i = 7;
printf("%d", ++i * ++i);

が81になると言ったら(つまり2つの++iがどちらも9になる), 驚く人は結構いるのではないかと思う。

実はこれは何も奇妙な話ではなく,コンパイラを素直に実装するとこうなってしまう。多くのコンパイラで同じになっているのではないだろうか。

説明

プログラムは何でも機械語まで落ちるわけなので, コンパイルの途中で直列化を行う必要がある。例えば

op(e1, e2, ..., en)

というオペランドがn個ある命令を直列化する場合には

e1を直列化したもの
e2を直列化したもの
...
enを直列化したもの
op(e1の評価値, e2の評価値, ..., enの評価値)

という風になる。(並べ方は自由だけれども, 第1オペランドから並べるのがまぁ自然でしょう)

具体例をあげると

x = y++;

は

t = y;
y = y + 1;
x = t;  /* tがy++の評価値 */

とか

x = y;
y = y + 1;

とかになる。(実装は前者が楽だが,後者の方が効率が良く,例えばgccは主に後者を使う.)

++yの場合は「yそのものを評価値として使用」して

x = ++y;

を

y = y + 1;
x = y;

としてしまう事が多い。

以上を踏まえて冒頭の例を考えて見ると,

i = 7;
x = ++i * ++i;

は

i = 7;
i = i + 1; /* 左の++i (iが評価値) */
i = i + 1; /* 右の++i (iが評価値) */
x = i * i;

となるので++i*++iが81になるわけである。

次に

• http://code.nanigac.com/forum/view/342

の

#include <stdio.h>
void f(int x;int y;int z){
        printf(“%d %d %d\n”,x,y,z);
}
int main(){
        int n=10;
        f(n++, --n, ++n);
        return 0;
}

の出力がなぜ

10 11 11

となるかだけれども,

n = 10;
f(n++, --n, ++n);

を直列化すると

n = 10;
t = n;      /* tがn++の評価値 */
n = n + 1;
n = n - 1; /* このnが--nの評価値 */
n = n + 1; /* このnが++nの評価値 */
f(t, n, n);

となるので,f(10, 11, 11)という呼び出しになると説明できる。

以上の話は, もちろん規格で何も定められていない話なのでさまざまな実装がありえるし, 同一の実装でも最適化などの具合によっていくらでも変わりうる話であるという事に注意。

ただ, 未定義だからとそれですませるのではなく，実際の所どうなっているのかに興味を持ってみるのも面白いのでは無いかと思う。

■[コンパイラ] 形骸化している代入演算子の優先順位 13:53

true ? 1 : x = 2

のようなソースがパースエラーにならないかどうか。

ちょっと調べた限りでは、

• 書ける：
  • Ruby
  • C#
• 書けない：
  • C
  • Java

のように分かれております。

Javaと文法が似てると思ってたC#ですが、こんなところに違いがあったんですねぇ。

http://mono.kmc.gr.jp/~yhara/d/?date=20090108

を読んで思ったこと。

> こんなところに違いがあったんですねぇ

演算子の優先順位という観点でみると, 4言語とも(代入) < (条件)と同じなので, もしこの式が

true ? 1 : (x = 2)

とパースされるならそれはある意味でバグです.

ただ, Rubyに関して言えば代入式が括弧無しで右辺に来れるので,代入演算子の優先順位が崩れてしまうのは仕方がないことなんですよね。

例えば

x = 1 + x = 2

が

x = (1 + (x = 2))

になるなど、代入演算子の優先順位はもはや形だけになってしまっています。(この例だと左の=と右の=で使われている文法規則が違うのでこういうことになる)

私はこういった点をちゃんとドキュメントに明示しなければならない(代入演算子とひとくくりにしないで, 「〜にある代入演算子」と種別分けするとか)と思いますが,多分暗黙の了解があるんでしょうね。

ところで,C#はどうなんだろうか。

■ [コンパイラ][Haskell][OCaml] Haskellのinfixの仕組み 12:11

OCamlでは ＜ や | で始まる中置演算子は左結合になるため、|> はO.K.ですが、<| 演算子をつなげたときにカッコが必要になってしまいます。

http://d.hatena.ne.jp/mzp/20090105#c1231290114

なんだそれと思ったが,ほんとだった。

  | ['=' '<' '>' '|' '&' '$'] symbolchar *
            { INFIXOP0(Lexing.lexeme lexbuf) }
(* 略 *)
  | ['*' '/' '%'] symbolchar *
            { INFIXOP3(Lexing.lexeme lexbuf) }

とレキサの中で先頭文字だけ('**'のみ2文字)を見て演算子の種別分けをしている。

なんでこんな設計になっているんだろうか。(手抜き? 高速化の為?)

ところで,演算子の結合性を指定できる言語にSMLやHaskellがある。例えばHaskellでは

infixr 5 <+>   -- 右結合性で優先順位は5

などと指定できる。しかし, yaccなどのコンパイラコンパイラには動的に定義される演算子を扱う方法がないので一体どうやっているのかが気になった。

そこでghcを読んでみたところ,以下のようになっていた。

1. パース時には全て同一の結合性(全部左結合)としてパースする
2. 型検査時のα変換(異なる値の変数には違う名前を割り振る)のフェーズで, 結合性をチェックして組み換える

組み替えは,(e1 op1 e2) op2 e3 となっている部分で op1とop2の結合性を比較して,必要ならe1 op1 (e2 op2 e3)に直すというようにする.

以下が組み替え処理の一部。

-- (e11 `op1` e12) `op2` e2
mkOpAppRn e1@(L _ (OpApp e11 op1 fix1 e12)) op2 fix2 e2
  | nofix_error = do
    addErr (precParseErr (ppr_op op1,fix1) (ppr_op op2,fix2))
    return (OpApp e1 op2 fix2 e2)

    -- op2の方が結合性が高い
  | associate_right = do
    -- 新しく組み直した e12 `op2` e2 の再組み替え
    new_e <- mkOpAppRn e12 op2 fix2 e2
    return (OpApp e11 op1 fix1 (L loc' new_e))
  where
    loc'= combineLocs e12 e2
                                           -- 結合性のチェック
    (nofix_error, associate_right) = compareFixity fix1 fix2

-- nofix_error = False, associate_right = Falseの時は何もしない

何か面白いことをやっているかと思ったら想像通りでおもしろくなかった。もっと工夫したやり方はないだろうか。

ところで,Haskellでは型検査が終わるまで構文木は正しくない状態という事になるけれども,これは一年以上放置していたなぜ型検査は脱糖の前か?という疑問の解答の一つになった。

■ [日記] あけましておめでとうございます 00:33

しばらく卒論関係のコーディングに追われているので, 2008-12-11 - mad日記の続きがなかなかできないでいます。そのうち時間を見つけて何とか。

ところで,2008年もいろいろあったのにブログを読み返したらなんかコンパイラの話ばかりで悲しかったので,もうちょっと日記を書こうかと思った。

最近の主だった出来事。

12/24

塾の高3クラス最終授業日なので授業後に壮行会をした。今年は教え子に企画をさせてみたが,生徒持参のガチャピンの着ぐるみを着ながら若干後悔。

でも,ケーキを作って持ってきてくれる子がいたり,ロシアンルーレット饅頭(見事私が当たりを引いた)とかジェンガを用意してたりとなかなか盛り上がったので良かったかもしれない。

皆様受験がんばって下さい。

12/31〜1/3

久しぶりに故郷の岩手で年越し。寒かった。

年を越しながら, ひたすら自作コンパイラのバグと戦っていた。

1/2

高校の吹奏楽部の同級会に参加したが,想定外の男1女8というハーレム状態で一人おどおどしてきた。

久しぶりの飲み会+カラオケ+ボーリングでだいぶストレス発散をする事ができた。

飲み会では会社の友達が派遣切りにあったとか,転職するだとかいった話題がやはり多かったように思う。

1/3

小学校以来の友達に第一子(女の子)ができたという連絡をもらったのを思い出し会いに行った。やはり赤ん坊は可愛い。さらにその後, 町をぶらついていたら中高時代の同級生の夫婦に遭遇。そいつは既に2児の親になっていた。

もうそんな歳かとしみじみ。田舎だから早いだけかもしれないけれども。