Hatena::ブログ(Diary)

あどけない話

2013-04-17

GHC の STG に関するまとめ

理解が深まれば、適宜更新します。

G-machine

Spineless G-machine

  • Spineless: 引数が充足している関数は、一気に呼び出す
    • このころまでに標準の G-machine も spineless だったらしい
  • サンクは共有されているときだけ更新 (これが重要)
  • G コードに対して 5 つの新しいコードを追加
  • push/enter 方式

Spineless Tagless G-machine

  • Tagless: 統一された書式になって、先頭の tag がなくなった。先頭は info へのポインタ
  • T コード
  • case 文での分岐は、評価する式が vectorized returns を返すので、直接分岐へ飛べる
  • push/enter 方式

Spineless Tagless G-machine Version 2.5

  • 低レベルなコードをやめ、拡張ラムダ式をそのまま使う高水準な language になった
  • セマンティクスが明確になった
    • 関数の適用は末尾呼び出し(jump)
    • let 式はヒープの割り当て
    • case 式は評価
    • コンストラクタの適用は継続への復帰 (case of の間を評価したあとに分岐という継続に戻る)
  • case 文での分岐は、評価する式が vectorized returns を返すので、直接分岐へ飛べる
  • push/enter 方式

STG(Shared Term Graph) language and STG(Spineless Tagless G) machine

疑問

  • update しなくていいサンクって、どうやって値を保持するんだろう？

Permalink | コメント(0) | トラックバック(0) | 15:12

0582504716
Book VERY HUNGRY CATERPILLAR STG BIG BK (Storytim...
Longman Eric Carle
B000BWURLY
CE ELECOM ヘッドホン延長コード EHP-CT23G/10WH
エレコム
購入: 6人 クリック: 6回

2013-04-04

書評「型システム入門」

端的に説明するなら「正しく型付けされた項はおかしくなることがない」ことを学ぶための壮大な本。型に関する圧倒的な知識を持ち、説明がうまく、根気づよい人にのみ記すことができた英語の良書が、型システムを愛する訳者と監訳者、および(書中に名前が出てくる方も含む)豪華なレビュアの情熱によって翻訳された記念すべき書籍。税抜きで6,800円と高いが、それ以上の価値がある本である。

型システム入門 −プログラミング言語と型の理論−

型システム入門 −プログラミング言語と型の理論−

動的言語のプログラマと静的型付き言語のプログラマの間で、型についての議論が定期的に沸き上がる。今後、型について議論するなら、少なくともこの本の1章を読んでからにすべきだと思う。幸いにも、オーム社のページから1章のPDFがダウロードできる。第1章を読むためだけにも買う価値がある本なのに、なんという大盤振る舞いだろう。

できるかぎり多くのプログラマに本書の第1章が読まれることを願う。

この本では、ラムダ式を使ってプログラマが普段使っている機能を実装し、型を付けていく。ラムダ式と聞いて関数型言語を対象にしていると勘違いしてはいけない。たくさんのページがオブジェクト指向にも費やされている。

本書の内容は包括的である。読み進めていくと、僕の中でふわふわ漂っていた知識の断片が、有機的につながっていく感じなのだ。たとえば、Topという型があるのは知っていたが、これが Java の Object 型に対応するのだとはじめて知った。

本書の説明は明瞭である。これまで僕は、ダウンキャストがあるのに「Javaは型安全である」という主張がよく分からなかった。この本には、型検査が実行時でも型安全と言い、Java でダウンキャストが使われたときは、実行時検査のコードが追加されるという意味で型安全であると書いてあった。

本書の説明は丁寧である。たとえばラムダ式の説明に現れる変数が、他の書籍では何を意味するのが分からなくなるのだが、本書の41ページには以下のような注意書きがある。

任意の項を表すために、メタ変数tを使い続けることにする。同様にxは任意の変数を表す。ここで、xは変数上を動くメタ変数であることに注意されたい。さらに悪いことに、短い名前は数が限られるので、対象言語の変数としても、x や y を使いたい。...

僕は、ジュンク堂池袋店『型システム入門 プログラミング言語と型の理論』トークイベントに参加した。そのときの説明によると、第11章まで読めば読んだことになるそうだ。頭からすべてを読む必要はなく、特に読みたいところがあれば、ix ページに載っている章の依存関係から、必要な章を見つけて読んでもいいとのこと。

話はそれるが、僕がイベントに参加した理由は、Ruby 2.0 のリリースマネージャである遠藤さんの話を聞きたかったからである。型システムをよく知っている人が、どういう感覚で Ruby を使っているのか知りたかったのだ。遠藤さんが Ruby を使う理由は、楽しいから、そして言語を拡張するときに型推論を壊してしまわないか心配しなくていいから、ということであった。後者の理由を聞けただけでも、イベントに参加した価値はあった。

本書は、僕には抜群に面白いが、(第2章以降が)すべてのプログラマ向けではないことは確かだろう。どういう人にお勧めできるか考えてみた。

なお、本書に対する Q&A はサポートページにまとめられている。

Permalink | コメント(2) | トラックバック(0) | 16:14

2013-04-02

Git に関する良記事

適宜追加します。

Pro Git

僕が読んだ Git の書籍の中では、一番分かりやすいと思いました。日本語版の書籍はありませんが、オンライン版が翻訳されています。

図解 Git

Git の初心者が動作を理解するのにおススメ。

こわくない git

ブランチとマージの考え方がよく分かるスライド(@methaneさんから教えて頂きました)。

あなたの知らないGit Tips

書籍には載ってない Tips の解説。知らないと損するかも。

ワークフロー、あるいはブランチング

チームでブランチを使う際の取り決め。自分のチームで一から議論するより、すでにあるものを参考にしましょう。

Github Enterprise

Github Enterprise は、企業内に設置して使うことができる Github サーバです。秘密のコードを Github に置きたくなかったり、Github が落ちて業務が遂行できなくなるのが嫌なら、Github Enterprise の導入を検討してみるのもいいかもしれません。(僕は使ったことがありません。すいません。) 導入に関する Tips は、以下の勉強会のスライドを参考にするといいでしょう。

Permalink | コメント(2) | トラックバック(0) | 16:18

2013-03-31

再帰ドリル(2)：数値に対する末尾再帰

注意：github に移動しました。

再帰ドリル(1)を読んでいない人は、先に読むこと。

等差数列の和

差が1の等差数列の和を素朴な再帰で実現すると以下のようになった。

soap 0 = 0
soap n = soap (n-1) + n

プログラミング言語の内部をよく知っている人は、何度も関数を呼び出すのでスタックが溢れてしまわないか心配だろう。実際、この手の関数はスタックが溢れてしまう可能性がある。

そもそも、この程度の計算はループで実現できるはずで、スタックは溢れて欲しくはない。幸いにも、素朴な再帰を「末尾再帰」(tail recursion)という形に直すと、スタックが溢れなくなる。

末尾再帰の形をした関数とは、分岐の末端の最後で自分自身を呼び出す関数のことである。上記の関数は末尾再帰ではない。(注意：この説明は正格評価を仮定している。) 以下のように二項演算子を関数に直して前に出すと、よく分かる。

soap 0 = 0
soap n = (+) (soap (n-1)) n

soap が最後に呼び出すのは、(+) であるから末尾再帰ではない。幸い、ループできることを実装している再帰関数は、「引数を増やすことで末尾再帰に直せる」。

soap n = soap' n 0

soap' 0 acc = acc
soap' n acc = soap' (n-1) (acc + n)

増やされた引数は「蓄積変数」(accumulator)と呼ばれる。蓄積変数に結果を蓄えていき、最後にそれを返す訳だ。

関数型言語を名乗るプログラミング言語であれば、再帰の末尾呼び出しは、単なるジャンプ(goto)に置き換えられるので、スタックは溢れない。(まぁ、この辺りが微妙な関数型言語もあるけれど。) これを「末尾呼び出しの最適化」(TCO: tail call optimization)と言う。

階乗

階乗を素朴な再帰で実現した

fact 1 = 1
fact n = fact (n - 1) * n

は、以下のように変形できる。

fact n = fact' n 1

fact' 1 acc = acc
fact' n acc = fact' (n - 1) (acc * n)

掛け算

階乗を素朴な再帰で実現した

mul m 1 = m
mul m n = mul m (n - 1) + m

は、以下のように変形できる。

mul m n = mul' m n m

mul' m 1 acc = acc
mul' m n acc = mul' m (n - 1) (acc + m)

蓄積変数の初期値に注意。

演習

様式が分かったところで、演習に移ろう。以下の素朴な再帰関数を末尾再帰の形に直しなさい。

plus m 0 = m
plus m n = plus m (n - 1) + 1

minus m 0 = m
minus m n = plus m (n - 1) - 1

power m 1 = m
power m n = power m (n - 1) * m

Permalink | コメント(0) | トラックバック(0) | 17:12

2013-03-30

再帰ドリル(1)：数値に対する素朴な再帰

注意：github に移動しました。

再帰を学ぶためのドリル。使用するプログラミング言語は Haskell。このシリーズは続くかもしれないし、途中で挫折するかもしれない。乞うご期待！

等差数列の和

差が1の等差数列の和を計算する関数 soap(sum of arithmetic progression) を考える。

soap 0 = 0
soap 1 = 0 + 1
soap 2 = 0 + 1 + 2
soap 3 = 0 + 1 + 2 + 3
soap 4 = 0 + 1 + 2 + 3 + 4

一歩手前を使うとどうなる？

soap 0 = 0
soap 1 = soap 0 + 1
soap 2 = soap 1 + 2
soap 3 = soap 2 + 3
soap 4 = soap 3 + 4

再帰部を一般化するとどうなる？

soap 0 = 0              -- 基底部
soap n = soap (n-1) + n -- 再帰部

階乗

階乗を計算する関数 fact を考える。

fact 1 = 1
fact 2 = 1 * 2
fact 3 = 1 * 2 * 3
fact 4 = 1 * 2 * 3 * 4
fact 5 = 1 * 2 * 3 * 4 * 5

一歩手前を使うとどうなる？

fact 1 = 1
fact 2 = fact 1 * 2
fact 3 = fact 2 * 3
fact 4 = fact 3 * 4
fact 5 = fact 4 * 5

再帰部を一般化するとどうなる？

fact 1 = 1
fact n = fact (n - 1) * n

掛け算

掛け算する関数 mul を考える。

mul m 1 = m 
mul m 2 = m + m
mul m 3 = m + m + m 
mul m 4 = m + m + m + m
mul m 5 = m + m + m + m + m

一歩手前を使うとどうなる？

mul m 1 = m
mul m 2 = mul m 1 + m
mul m 3 = mul m 2 + m 
mul m 4 = mul m 3 + m
mul m 5 = mul m 4 + m

再帰部を一般化するとどうなる？

mul m 1 = m
mul m n = mul m (n - 1) + m

演習

以下の関数に対して、再帰の定義を考えなさい。

plus m 0 = m
plus m 1 = m + 1
plus m 2 = m + 1 + 1
plus m 3 = m + 1 + 1 + 1
plus m 4 = m + 1 + 1 + 1 + 1

minus m 0 = m
minus m 1 = m - 1
minus m 2 = m - 1 - 1
minus m 3 = m - 1 - 1 - 1
minus m 4 = m - 1 - 1 - 1 - 1

power m 1 = m
power m 2 = m * m
power m 3 = m * m * m
power m 4 = m * m * m * m
power m 5 = m * m * m * m * m

Permalink | コメント(0) | トラックバック(1) | 11:25

プロフィール

kazu-yamamoto はてなダイアリープラス利用中

子育て真っ最中の Haskeller

カテゴリー
最新タイトル
最近のコメント
最近のトラックバック