Success is a Journey, not a Destination: 9月 2011

[The Economistの "Greek banks - Playing against type" の翻訳です。]

銀行は悪者だという見方は、ヨーロッパでもアメリカでも受け入れられている。これに関しては、これだけではないが、ギリシャは仲間外れだ。ギリシャの銀行の人と話すと、哀れみを覚えずにはいられない。

ギリシャの銀行は、2007-2008の金融危機の真っ最中もとても上手くやってきた。国の救済 (そんなものがあったら、の話だが) に頼ることなく、お金を逆方向に流していた。つまり、銀行が国債を買うことが、ギリシャ政府にとっての最も確実な収入源だった。ある銀行関係者によれば、国債の購入は今や強制されているようなもので、政府は「国債を購入しないなら、公営企業の預金を引き上げるぞ」と脅しているそうだ。

きっかけはどうあれ、国債のデフォルトリスクのせいで、銀行のバランスシートは炎上しやすくなっている。PSI (財政危機の対策のために民間企業の協力を求めること) のため、ギリシャが破綻しないための負担の一部は民間の債権者にも求められていて、すでに銀行は評価損を計上している。でも、更なるリストラのリスクは未だに高まっている。

財源は、関連する大きな問題だ。預金は金融システムの外へと流れ出ている。クレディ・スイスは、民間部門の預金額は 1 月から 7 月にかけて 10% 減少した、と見積もっている。人々は預金を引き出し、破綻のリスクに怯えている。ある銀行員は、人々が預金を引き出してタンス預金しないように説得している銀行の努力について、「私たちは預金者のサイコセラピストなんです」と語る。

ECB (ヨーロッパ中央銀行) は銀行を破綻させないはずだが、同時に、銀行が差し出した担保を定期的に再評価し、酸素供給 (銀行への資金供給) を絞っている。担保価値が下がりつづけ、貸出期間が短くなっている状況では、銀行はお金を中期の貸し出しにはまわしたくないだろう。しかし、それこそが経済が成長するために必要なのだが。

そのため、経済は停滞し、不良債権問題は増え続けている。おなじみの Blackrock Solutions から派遣されたチームは、銀行の貸出帳簿の検査に関して起訴された。今年中に銀行は更に資本が必要になるだろう。[訳注: よく分からない・・・]

銀行家たち自身は、(PSIによる一定の評価損以上の) ギリシャのデフォルトは望んでいない。そうなったら、彼らの資本は当然なくなってしまう。取締役会も、デフォルト危機の状態にあることが、ギリシャに更なる改革をすすめるための最良の方策だと言っている。憂慮すべきモラルハザードは、民間部門の債務が軽くなることではなく、ギリシャ政府が改革をやめてしまうことだ、とある銀行家はいう。

彼らの願いが叶ったとしても、銀行の未来は依然として窮屈なものだろう。2 つの銀行 (Eurobank と Alpha) は、資産の拡大とコストカットのために合併した。海外の資産は買い叩かれている。業務部門は、損失を補えるだけの引き当てを積むというつまらない目標を掲げている。同情を誘うには十分だ。

きのう参加した Start Haskell ではパフォーマンスの話題、とくに末尾再帰の話が多かった。遅延評価が関わると (?)、ある関数が末尾再帰になっているかを判断することさえそれほど単純ではないようだ。コンパイル後のアセンブラを読むのはさすがにやりたくないので、もう少し手軽な方法はないかと思っていたら、GHCが生成する中間形式を見る、という方法があるそうだ。昨日の演習問題だったsplitAtを例としてまとめてみる。

splitAtは、整数とリストを受け取って、リストを整数が示すインデックスで2つに分ける関数。splitAt 2 "abcd" -> ("ab", "cd") という感じ。Haskellのコードはこう。

sp1 :: Int -> [a] -> ([a], [a])
sp1 = sp1' ([],[])
  where
    sp1' (l1,l2) _ []    = (reverse l1, reverse l2)
    sp1' (l1,l2) m (l:ls)
      | m > 0        = sp1' (l:l1,l2) (m-1) ls
      | otherwise    = sp1' (l1,l:l2) (m-1) ls

これが末尾再帰になってなかったら死ねる、というコード。

このコードに対して、「reverse使うのは反則では?」という意見があった (出題は「リストを一回だけ走査する実装」だった)。まぁあと、ヘルパー関数を無くしたいとは思った。

sp2      :: Int -> [a] -> ([a], [a])
sp2 _ [] = ([], [])
sp2 n (x:xs)
    | n > 0     = (x:ys, zs)
    | otherwise = ([], x:xs)
  where
    (ys, zs) = sp2 (n-1) xs

この方が美しいとは思うが、再帰呼び出しのあとxをconsしているから、末尾再帰になってないと思った。が、「いや末尾再帰になっている」という声もあったので、調べてみた。ちなみに、ghcは "The Glorious Glasgow Haskell Compilation System, version 7.2.1"を使った。

% ghc -c -O2 -ddump-simpl [ソースファイル名]

とやると中間形式が標準出力に表示される。出力はかなり長いので、このエントリの最後にペーストした。

sp1の再帰部分に対応するコードを見ると、

case GHC.Prim.># sc2_syd 0 of _ {
  GHC.Types.False ->
    SplitAt.sp1_$s$wsp1'
      @ a_am8
      sc_syb
      (GHC.Types.: @ a_am8 l_ajZ sc1_syc)
      (GHC.Prim.-# sc2_syd 1)
      ls_ak0;
  GHC.Types.True ->
    SplitAt.sp1_$s$wsp1'
      @ a_am8
      (GHC.Types.: @ a_am8 l_ajZ sc_syb)
      sc1_syc
      (GHC.Prim.-# sc2_syd 1)
      ls_ak0

となっているので、(これがチェックするべき中間言語であって、私が中間形式をただしく読めていて、ソースコードとの対応を間違っていなくて、GHCがこのあと更に最適化しなければ) 末尾再帰になっているといえるだろう。

一方、sp2の再帰部分に対応するコードは、

Case GHC.Prim.># sc_syz 0 of _ {
  GHC.Types.False -> (# GHC.Types.[] @ a_abq, wild_X9 #);
  GHC.Types.True ->
    let {
      ds_swT [Dmd=Just D(SS)] :: ([a_abq], [a_abq])
      [LclId, Str=DmdType]
      ds_swT =
        case SplitAt.sp2_$s$wsp2 @ a_abq (GHC.Prim.-# sc_syz 1) xs_abt
        of _ { (# ww1_sxN, ww2_sxO #) ->
        (ww1_sxN, ww2_sxO)
        } } in
    (# GHC.Types.:
         @ a_abq x_abs (case ds_swT of _ { (ys_adK, zs_adL) -> ys_adK }),
       case ds_swT of _ { (ys_adK, zs_adL) -> zs_adL } #)
}

となっている。再帰呼び出しはletの中に入っていて、そのあとinの中で "GHC.Types.:" つまりconsを呼んでいる。なので、末尾再帰になっていないと考えられる。

ちなみに、-Oでも-O3でも結果は変わらなかった。

と、ここまで書いてきてなんだけど、ある関数を末尾再帰にするというのは局所的な最適化なので、重要性は低いと思っている。初心者が知る必要はないし、ソフトウェアの開発初期に、部品となる関数一つ一つに対して、「これは末尾再帰にするべきか、末尾再帰になっているか」と考えるのは premature optimization というものだろう。

なのに、どうして多くの関数型言語の本もかなり序盤に末尾再帰の話を持ってくるのか疑問だ。そもそも関数型言語のような高レベル言語を使ってるのに、スタックを消費する・しない、とか考えたくない。と思うのは間違っているのだろうか? まぁ、パズルみたい (しかもたいてい簡単) なので、面白いけどね。

dump-simplの全出力は以下のとおり。"@"とか"(#"とか"#)"とか謎のシンボルがある。トップレベルの関数と再帰用(Rec { ... } で定義されている)と2つの関数定義ができるみたい。

==================== Tidy Core ====================
Result size = 250

Rec {
SplitAt.sp1_$s$wsp1' [Occ=LoopBreaker]
  :: forall a_am8.
     [a_am8]
     -> [a_am8] -> GHC.Prim.Int# -> [a_am8] -> (# [a_am8], [a_am8] #)
[GblId, Arity=4, Caf=NoCafRefs, Str=DmdType LLLS]
SplitAt.sp1_$s$wsp1' =
  \ (@ a_am8)
    (sc_syb :: [a_am8])
    (sc1_syc :: [a_am8])
    (sc2_syd :: GHC.Prim.Int#)
    (sc3_sye :: [a_am8]) ->
    case sc3_sye of _ {
      [] ->
        (# GHC.List.reverse @ a_am8 sc_syb,
           GHC.List.reverse @ a_am8 sc1_syc #);
      : l_ajZ ls_ak0 ->
        case GHC.Prim.># sc2_syd 0 of _ {
          GHC.Types.False ->
            SplitAt.sp1_$s$wsp1'
              @ a_am8
              sc_syb
              (GHC.Types.: @ a_am8 l_ajZ sc1_syc)
              (GHC.Prim.-# sc2_syd 1)
              ls_ak0;
          GHC.Types.True ->
            SplitAt.sp1_$s$wsp1'
              @ a_am8
              (GHC.Types.: @ a_am8 l_ajZ sc_syb)
              sc1_syc
              (GHC.Prim.-# sc2_syd 1)
              ls_ak0
        }
    }
End Rec }

SplitAt.sp1
  :: forall a_abp. GHC.Types.Int -> [a_abp] -> ([a_abp], [a_abp])
[GblId,
 Arity=2,
 Caf=NoCafRefs,
 Str=DmdType,
 Unf=Unf{Src=, TopLvl=True, Arity=2, Value=True,
         ConLike=True, Cheap=True, Expandable=True,
         Guidance=IF_ARGS [20 100] 283 360}]
SplitAt.sp1 =
  \ (@ a_am8) (w_sxu :: GHC.Types.Int) (w1_sxv :: [a_am8]) ->
    case w1_sxv of _ {
      [] ->
        (GHC.List.reverse1
           @ a_am8 (GHC.Types.[] @ a_am8) (GHC.Types.[] @ a_am8),
         GHC.List.reverse1
           @ a_am8 (GHC.Types.[] @ a_am8) (GHC.Types.[] @ a_am8));
      : l_ajZ ls_ak0 ->
        case w_sxu of _ { GHC.Types.I# x_awt ->
        case GHC.Prim.># x_awt 0 of _ {
          GHC.Types.False ->
            case SplitAt.sp1_$s$wsp1'
                   @ a_am8
                   (GHC.Types.[] @ a_am8)
                   (GHC.Types.: @ a_am8 l_ajZ (GHC.Types.[] @ a_am8))
                   (GHC.Prim.-# x_awt 1)
                   ls_ak0
            of _ { (# ww1_sxH, ww2_sxI #) ->
            (ww1_sxH, ww2_sxI)
            };
          GHC.Types.True ->
            case SplitAt.sp1_$s$wsp1'
                   @ a_am8
                   (GHC.Types.: @ a_am8 l_ajZ (GHC.Types.[] @ a_am8))
                   (GHC.Types.[] @ a_am8)
                   (GHC.Prim.-# x_awt 1)
                   ls_ak0
            of _ { (# ww1_sxH, ww2_sxI #) ->
            (ww1_sxH, ww2_sxI)
            }
        }
        }
    }

Rec {
SplitAt.sp2_$s$wsp2 [Occ=LoopBreaker]
  :: forall a_abq. GHC.Prim.Int# -> [a_abq] -> (# [a_abq], [a_abq] #)
[GblId, Arity=2, Caf=NoCafRefs, Str=DmdType LS]
SplitAt.sp2_$s$wsp2 =
  \ (@ a_abq) (sc_syz :: GHC.Prim.Int#) (sc1_syA :: [a_abq]) ->
    case sc1_syA of wild_X9 {
      [] -> (# GHC.Types.[] @ a_abq, GHC.Types.[] @ a_abq #);
      : x_abs xs_abt ->
        case GHC.Prim.># sc_syz 0 of _ {
          GHC.Types.False -> (# GHC.Types.[] @ a_abq, wild_X9 #);
          GHC.Types.True ->
            let {
              ds_swT [Dmd=Just D(SS)] :: ([a_abq], [a_abq])
              [LclId, Str=DmdType]
              ds_swT =
                case SplitAt.sp2_$s$wsp2 @ a_abq (GHC.Prim.-# sc_syz 1) xs_abt
                of _ { (# ww1_sxN, ww2_sxO #) ->
                (ww1_sxN, ww2_sxO)
                } } in
            (# GHC.Types.:
                 @ a_abq x_abs (case ds_swT of _ { (ys_adK, zs_adL) -> ys_adK }),
               case ds_swT of _ { (ys_adK, zs_adL) -> zs_adL } #)
        }
    }
end Rec }

SplitAt.sp2 [InlPrag=INLINE[0]]
  :: forall a_abq. GHC.Types.Int -> [a_abq] -> ([a_abq], [a_abq])
[GblId,
 Arity=2,
 Caf=NoCafRefs,
 Str=DmdType LSm,
 Unf=Unf{Src=InlineStable, TopLvl=True, Arity=2, Value=True,
         ConLike=True, Cheap=True, Expandable=True,
         Guidance=ALWAYS_IF(unsat_ok=True,boring_ok=False)
         Tmpl= \ (@ a_abq)
                 (w_sxA [Occ=Once!] :: GHC.Types.Int)
                 (w1_sxB [Occ=Once!] :: [a_abq]) ->
                 case w1_sxB of wild_X9 {
                   [] -> (GHC.Types.[] @ a_abq, GHC.Types.[] @ a_abq);
                   : x_abs [Occ=Once] xs_abt [Occ=Once] ->
                     case w_sxA of _ { GHC.Types.I# x1_awt ->
                     case GHC.Prim.># x1_awt 0 of _ {
                       GHC.Types.False -> (GHC.Types.[] @ a_abq, wild_X9);
                       GHC.Types.True ->
                         let {
                           ds_swT [Dmd=Just D(SS)] :: ([a_abq], [a_abq])
                           [LclId, Str=DmdType]
                           ds_swT =
                             case SplitAt.sp2_$s$wsp2 @ a_abq (GHC.Prim.-# x1_awt 1) xs_abt
                             of _ { (# ww1_sxN [Occ=Once], ww2_sxO [Occ=Once] #) ->
                             (ww1_sxN, ww2_sxO)
                             } } in
                         (GHC.Types.:
                            @ a_abq
                            x_abs
                            (case ds_swT of _ { (ys_adK [Occ=Once], _) -> ys_adK }),
                          case ds_swT of _ { (_, zs_adL [Occ=Once]) -> zs_adL })
                     }
                     }
                 }}]
SplitAt.sp2 =
  \ (@ a_abq) (w_sxA :: GHC.Types.Int) (w1_sxB :: [a_abq]) ->
    case w1_sxB of wild_X9 {
      [] -> (GHC.Types.[] @ a_abq, GHC.Types.[] @ a_abq);
      : x_abs xs_abt ->
        case w_sxA of _ { GHC.Types.I# x1_awt ->
        case GHC.Prim.># x1_awt 0 of _ {
          GHC.Types.False -> (GHC.Types.[] @ a_abq, wild_X9);
          GHC.Types.True ->
            let {
              ds_swT [Dmd=Just D(SS)] :: ([a_abq], [a_abq])
              [LclId, Str=DmdType]
              ds_swT =
                case SplitAt.sp2_$s$wsp2 @ a_abq (GHC.Prim.-# x1_awt 1) xs_abt
                of _ { (# ww1_sxN, ww2_sxO #) ->
                (ww1_sxN, ww2_sxO)
                } } in
            (GHC.Types.:
               @ a_abq x_abs (case ds_swT of _ { (ys_adK, zs_adL) -> ys_adK }),
             case ds_swT of _ { (ys_adK, zs_adL) -> zs_adL })
        }
        }
    }

Success is a Journey, not a Destination

2011年9月24日土曜日

ステレオタイプとは真逆のギリシャの銀行

2011年9月11日日曜日

Haskellの中間形式を見て関数が末尾再帰かどうか調べる