Hatena::ブログ(Diary)

純粋関数型雑記帳 このページをアンテナに追加 RSSフィード Twitter

このページはHaskellを愛でるページです。
日刊形式でHaskellなどについての記事をだらだらと掲載しとります。
2004 | 07 | 08 | 09 | 10 | 11 | 12 |
2005 | 01 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2006 | 01 | 02 | 03 | 04 | 06 | 07 | 08 | 09 | 11 |
2007 | 03 | 04 | 05 | 07 | 08 | 09 | 12 |
2008 | 02 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 03 | 05 | 06 | 09 | 10 | 11 | 12 |
2010 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 12 |
2011 | 01 | 02 | 05 |
本体サイト

2004年12月27日(月) Tempale meta-programing for Haskell

久しぶりにHaskell勉強した。

せっかくなのでだらだらと。

[]Template Haskell Template Haskellを含むブックマーク Template Haskellのブックマークコメント

  • はじめに

Template Haskell というものを勉強してみた。

そういうわけで、資料を探してみたのだが、

日本語の資料は見事なまでに皆無だったので、

(Haskellで、しかも試験的な機能だから止む無しか)

英語論文を読むことになった。

10ページほど読むのに3日かかったけど…。


大雑把に言うとコンパイル時にプログラムを生成するためのもののようである。

  • 概要

コンパイル時に指定した式を実行させ、その値をコードの中に展開させることが出来る。

展開できる式の値は"プログラム式"等の型をもつ。

要するに、任意の方法で構文木を組み立てて、それを実行することが出来ると。

構文木はExpQという型を持つ。

Template Haskell においてはこのExpQ型の何かを扱えば良い。

ExpQというのは実際にはQ Expのシノニムであり、

Expは単にHaskellのデータ型、

QはQuotationモナドというように説明されている。

Quotationモナドであるが、これはほぼIOモナドと同じだろう。

実際のところQモナドとIOモナドは相互変換可能である。

IOに加え、コンパイラの内部状態にアクセスするためにこのように

なっていると思われる。

構文木の構築においてExpQという型を持ち出すのは

構築の際に任意のIOを行わせるためだろう。

Exp型には VarE :: String -> Exp や

AppE :: Exp -> Exp -> Exp などのコンストラクタがあり、

これらはそれぞれ変数参照、関数適用を表している。

全容はLanguage.Haskell.THSyntaxに定義されている。

これとモナド演算だけを用いてプログラムを構築することも出来るのだが、

それはあまりにも冗長で煩雑であるので、利便性のために

もっと別な方法で記述できるようになっている。


Template Haskellの記述方法には3つのやり方がある。

それぞれ順番に記述力が下がり、利便性が上がる。

まず、最初は、先に書いたExp型等をそのまま扱う方法。

次に、それのモナディック版を使う方法。

VarEに対してvarE、AppEに対して、appEなど、先頭が小文字

関数バージョンが定義されており、

これらはいずれもExpQ上の関数として定義されている。

これらを用いることにより、明示的なモナド操作が減少する。

最後に、quasi-quote記法というものを用いる方法。

これはSchemeにあるquasi-quoteに大体で似ている。

[| |] で囲った部分の式をExpQな型として扱える。

途中に$(式)と書くことにより、その中の式を実行したものを

埋め込むことが出来る。

tfact :: Int -> ExpQ
tfact 0 = [| 1 |]
tfact n = [| $(lift n) * $(tfact $ n-1) |]

適当な例として階乗を。

tfact 5 が 5 * 4 * 3 * 2 * 1 * 1 に展開される。

なお、quasi-quote記法では色々と記述しきれない部分があるので

これら3つの手法を組み合わせて目的のコードを作成することになる。

これらの手法はシームレスに混合可能である。

作成したものをコンパイル時に実行させるには(unquoteと同様に)

$を頭につければよい。

> $(tfact 10)
3628800

式として書かれるべき場所トップレベルな展開が発生した場合、

その計算したものの型がExpQであった場合、そこにコードが

挿入されるような感じであろうか。

定義を書くべき場所であれば、DecQ型を返せばそこに宣言を挿入することも出来る。

  • 例1 printf

普通なHaskellではprintfのような関数を定義しようと思っても

型を付けることが出来ない。

というのも、

printf "%s : %d" "hello" 123

等のようなコードで、printf の型は引数文字列によって変わるからなのである。

上の例では String -> String -> Int -> IO () になるだろうか。

しかし、Template Haskellなら可能である。

コンパイル時に文字列を解析して

printf "%s : %d" を \s n -> s ++ " : " ++ show n なる式に

してしまうことが出来るからである。

(以下、都合上 printfでは無くてsprintfを作る)

{-# OPTIONS -fglasgow-exts #-}

module Printf(
  sprintf
) where

import Language.Haskell.THSyntax

data Format = D | S | L String deriving (Eq,Show)

sprintf :: String -> ExpQ
sprintf = flip toExp [| "" |] . parse

parse :: String -> [Format]
parse [] = []
parse ('%':x:xs)
  | x=='d'    = D : parse xs
  | x=='s'    = S : parse xs
  | otherwise = error "invalid input"
parse xs = L l : parse rest
  where (l,rest) = span (/='%') xs

toExp :: [Format] -> ExpQ -> ExpQ
toExp []         x = x
toExp (D   : xs) x = [| \n -> $(toExp xs [| $x ++ show n |]) |]
toExp (S   : xs) x = [| \s -> $(toExp xs [| $x ++ s|]) |]
toExp (L s : xs) x = toExp xs [| $x ++ $(lift s) |]

まず、StringをFormatのリストに変換し、

それをExpQに構築する。

なお、GHCではなぜかtop-levelなspliceはローカルな定義ではなくて

importしたものじゃないと駄目だといわれるので、Printfモジュールを作成している。

{-# OPTIONS -fglasgow-exts #-}

module Main where

import Printf

main = putStr $ $(sprintf "error %s on line %d.\n") "Hoge.hs" 123

このように使用することが出来る。

sprintfは左記の通り変換されるので、型チェックも

問題なく行えるようだ。

pairからの要素選択はfst、sndという関数が用意されているが、

triple以上のものから選択しようと思うと、

case x of (a,b,c) -> b

のようなものを書かなければならない。

Template Haskellを用いると、

$(sel 1 3) (1,'a',[]) => 1
$(sel 2 3) (1,'a',[]) => 'a'

のような、自動的にそのような式を生成するものを

記述することが出来る。

{-# OPTIONS -fglasgow-exts #-}

module Select(
  sel
) where

import Language.Haskell.THSyntax

sel :: Int -> Int -> ExpQ
sel a b = lamE [varP "x"] (caseE (varE "x") [alt])
  where alt = match pat (normalB rhs) []
        pat = tupP (map varP xs)
        rhs = varE (xs !! (a-1))
        xs  = ["x"++show i | i <- [1..b]]

上記、sel関数は、quasi-quoteだけでは書けない。

sel a b = [| \x -> case x of ...

と、ここでb要素のタプルが書けないのである。

上のように必要に応じてモナディックな関数で構成すれば

定義できる。

  • 例3 任意個のzip

タプルは帰納的な型でないためか

Template Haskellの格好の題材のようであるが、次はzipである。

zipにはzip,zip3,zip4,... と個数に応じたバージョンzipが定義されているが

zip3 = $(zipN 3)

と書ければ嬉しいという話。

{-# OPTIONS -fglasgow-exts #-}

module Zips(
  zipN ,tfact
) where

import Language.Haskell.THSyntax

zipN :: Int -> ExpQ
zipN n = [| let zp = $(mkzip n [| zp |]) in zp |]

mkzip n f = lamE pys (caseE (tupE eys) [m1,m2])
  where
    (pxs ,exs)  = genPE "x"  $ toInteger n
    (pys ,eys)  = genPE "y"  $ toInteger n
    (pxss,exss) = genPE "xs" $ toInteger n
    pcons x xs  = conP "GHC.Base::" [x,xs]
    b = [| $(tupE exs) : $(appsE (f:exss)) |]
    m1 = match (tupP (zipWith pcons pxs pxss)) (normalB b) []
    m2 = match (tupP (replicate n wildP)) (normalB [| [] |]) []

lexical scopingのためにzpという名前の扱いが

ややトリッキー(…でもないか)になっているが、

まぁ、こんな感じで。

conP "GHC.BASE::" という部分があるが、これは

(x:xs) なるパターンを生成したかった。

論文中では [p| $x : $xs |] というようにパターン用クオート表記が

使われていたのだが、これがなんだか使えなかったので、

上のような感じになってしまった。

GHC.Baseのようなものを直接書くのは正直忍びないが、

他にやり方がわからなかった。

  • まとめ?

参考文献 http://www.haskell.org/th/papers/meta-haskell.ps

率直な感想…構文木を作るコード書くのめんどくさすぎ…

自分で書こうと思っても全然書けない。

慣れの問題なのだろうか…?

http://www.haskell.org/ghc/docs/latest/html/libraries/haskell-src/Language.Haskell.THSyntax.html

ここにもほとんど説明が付いていないし、

いろいろ大変だ。

yaneuraoyaneurao 2004/12/28 07:25 なるほろ。Template Haskellは一種のmeta programmingなんですナ..。Lisp時代から、この手のmeta programming手法って、いろいろありますけど、ライブラリのためのライブラリを作るときぐらいしか役に立たないですネ..。それも可読性が著しく低下するので保守しにくくなって..。

JavaEPPとかも似たようなアプローチなんですけど、なかなか現場で導入するのは難しいです..。

tanakhtanakh 2004/12/29 03:43 Lispに関してはS式のおかげでマクロが極めて自然な形で統合されてますね。なんせプログラム自体が構文木ですし。Lispに於いてはメタプログラミングは盛んに利用されていて、現実に(ある程度の規模の)とあるプログラムでは実に2割程度がマクロで構成されているという話もあるようです。そのようなものの突き詰めたところに何があるのかというと、極端にまで積極的な言語のカスタマイズで、それを考えるとLisp以外の言語でメタプログラミングをうまく使うのは難しいのかもしれません。
Template Haskellは構文木をHaskellのデータ型で扱うせいか、なんだか読みにいような感じですし、使いどころも確かに難しいような感じですね。C++でのTemplate Meta-programmingもちょっと見ただけでは何に使えば有効なのか分かりかねます。
Lispでのメタプログラミングを一つの理想形とするなら、他の言語にまでそれが降りてきて、一般的に使われだすのはまだまだ先なのかなぁ、とか思ったりします…。

h_sakuraih_sakurai 2004/12/29 14:50 今、[](){}の括弧でブロックをあらわして、’;’ ’,’ ’ ’をセパレータとして分解するC言語ライクなデータ定義言語を定義して、その言語上でプログラミング言語を作り、メタプログラミングできるようなものを考えています。(作ってはいません。)データ定義言語のデータ操作プログラムのサンプルを2chに置いたら変な人扱いされたのでぶち切れてしまいました(wおかげで第一印象がめちゃめちゃ悪い言語になってしまった(;-;)構文追加の方法として、見た目が簡単な構文定義、構文木を直接いじる構文定義、の2つは必要かと考えていたのですがHaskellは3つあるんですね。lispだとdefmacroとschemeの名前ぶつからない新しい奴とあるのは知ってますが、ほかにあるのかな?プログラム自体が構文木って言語はlisp,xml,forth,yaml(これはマイナー)以外あるのか知りたいところです?サンプルだけだと、おかしな人扱いされるからちゃんと文章にしないといけないと思うのですが、それがなかなか、はかどらない今日この頃です。switch文をloopとifで定義するようなメタプログラミングはどう書いたら簡潔になるのかとあとはパターンマッチングしてどうこうするといいのかな?わからーん。

yaneuraoyaneurao 2004/12/29 16:45 そんな幼稚くさい方法で実装するんでなくて、少しはまじめにコンパイラ本とEPPを勉強しなチャイ!(`ω´)

http://staff.aist.go.jp/y-ichisugi/epp/j-index.html

h_sakuraih_sakurai 2004/12/29 18:34 はい。コンパイラ本は読みます。EPPはどの変を勉強したらよいでしょうか?使い方はある程度、分かっているつもりなので、ソースを読んだり、仕組みをもっとよく理解したりってことだと思いますが。もっと素晴らしい使い方とかあるのだろうか、、、。

以下愚痴
ミックスジュースが個人的に嫌なんだよなぁ。追い辛い。
幼稚だからいいと思ったんだけどなぁ。
オートマトンするとプログラムから構造が見えなくなるんだよなぁ。再帰下降で書くとやたら長々と書かなきゃいけないし。EPPをもっと広めることこそ重要なのかなぁ。S式つかうんだったら最初からLISPでいいじゃんって気がするしなぁ。LISPは団子虫言われて敬遠されるし。Treeいじる以外の方法があるのかなぁ。ぶつぶつ。

tanakhtanakh 2005/01/02 05:14 どうも忙しくて書くのが遅くなって申し訳ないです…。
C様なデータ定義言語でメタプログラミングですか、具体的にどうなるんだろ…。Haskellは3つの方法がある、といっても、そのうち二つは構文木をいじる方法なので、実質は二つかもしれません。Schemeのdefine-syntaxはメタプログラミングといえるんでしょうかね。パターンマッチが出来るぐらいなので、昔ながらのマクロに比べて自由度はかなり低いと思います。もっとも、r5rsによるとこれで十分という判断なんでしょうか。switch文をifとloop…?これはよく分かりません。
EPPというのは有名ななのでしょうか。私は恥ずかしながら知りませんでした…。

h_sakuraih_sakurai 2005/01/02 13:12 携帯Javaの開発をしてますと関数をインライン展開してバイト数稼いだり関数呼び出しのオーバーヘッドを無くしたりしたくなったりするわけです。ところが、インライン展開できるような方法を探すとEPPのマクロで解決するくらいしかなかったのですよ。EPPのマクロはCommonLispのマクロ同様のマクロ内で使用している変数名とマクロの引数の名前がぶつかる問題があって、schemeのマクロ的なことをするようにしたりするプログラムを組んであげないといけなかったりするのですが。yaneuraoさんも私も携帯Java開発してるので、知っているということだと思います。

switch文をifとloopでって話は、yaneuraoさんの考えたfiberのプログラムを構文木をいじって、FMSとかいうモデルに書き換えるプログラム

http://d.hatena.ne.jp/yaneurao/20040524
http://d.hatena.ne.jp/yaneurao/20040525
をEPPを使って書いてみたのですが、構文が沢山あると、書き換えプログラムが多岐にわたって効率的でないことがわかりました。なので、現状ある構文を構造化プログラミングに最小限必要な制御文に書き換えてあげれば変換プログラム書くのが楽になってバグも減っていいんじゃないかなということを考えていたわけです。ミニマムな言語の制御構文って何かなと。

C様なデータ定義言語(CLDDL?)の具体的利用方法で考えられることは、S式で出来ること全てです。LISPのような言語を作ってその中でLISPのマクロと同じ機構を作る。EPPのJavaをS式に置き換えて構文木をいじるように、JavaをC様データ定義言語に置き換えて構文木をいじる。ということが出来ます。S式より処理は重いけど、見やすいという利点が得られるかなと。
あとはS式に絡まないメタプログラミングの概念を持ち込むことと、
S式に絡まないメタプログラミングの概念とS式の概念の融合、
現状あるメタプログラミングの考え以外の発想を追加することです。

トラックバック - http://d.hatena.ne.jp/tanakh/20041227

2004年12月21日(火) 超賢いポインタ (後編) このエントリーを含むブックマーク このエントリーのブックマークコメント

  • 本題

循環参照を解決できるポインタを作るには

どのようにすればよいのか。

一般的なGCで残すべきオブジェクトを決めるとき、

ルートからポインタをたどっていって、到達できるものを残すというようにする。

逆に考えると、

削除すべきオブジェクトとは、それをポイントするすべてのオブジェクト

削除すべきオブジェクトである場合である。

上からも分かるように、どこからもポイントされていないオブジェクト

削除可能である(参照カウント方式だと、これがカウンタが0になった状態か)。

残すべきオブジェクトからポイントされていればこれまた

自明に削除してはいけないオブジェクトなのである。


そういうわけで、アルゴリズムとしてはこれだけなのだが、

これを実現するにはとあるオブジェクトポイントしている

オブジェクトを知っている必要がある。

つまり、オブジェクトポイントしているスマートポインタ

所有するオブジェクト、がわかる必要がある。

オブジェクトポイントしているスマートポインタは簡単に管理することが出来る。

しかし、それがどのオブジェクトに所有されているかは、

個々のデータ構造によるものなので一般的には解決不可能である。


ではどうするか。ここでは非常に強引にメモリスキャンして

スマートポインタを検索することにした。

(半ば反則技か…他の環境で動くかどうかわからんし)

スマートポインタは(高確率で…)識別できるようにシグニチャを持つことにした。

これで、"とあるオブジェクトが所有するスマートポインタの列挙"が可能である。

スマートポインタがどのオブジェクトに所有されているかであるが、

これはオブジェクトが所有するスマートポインタをたどってとあるノードから

到達可能なオブジェクトを集めて、それを用いて算出できる。

到達不能なオブジェクトが所有するスマートポインタからポイントされている

ケースもあるが、この場合は、そのオブジェクトは削除してはいけない

ノード扱いなので、特に問題になるわけではない。


これで一応実装できるような感じである。

実装は以下の通り。

class base_gptr;

template <class T>
class genius_ptr;

class base_gobj{
public:
	virtual ~base_gobj() {}
	set<base_gptr*> parent;
};

template <class T>
class gobj : public base_gobj {
public:
	gobj(T *p) :p(p) {}
	~gobj() { delete p; }
	void incr(base_gptr *bp) { parent.insert(bp); }
	void decr(base_gptr *bp){
		parent.erase(bp);
		if (p!=NULL&&can_erase())
			erase();
		if (parent.empty())
			delete this;
	}
	void erase(){
		T *q=p;
		p=NULL;
		delete q; // これが死んだら、pが持ってるスマートポインタもデストラクトされるはず…
	}
	bool can_erase(){
		if (parent.empty())
			return true;

		// 準備。スマートポインタ→gobjなマップを作成する。
		set<base_gptr*> ptrs;
		collect_ptrs(*parent.begin(),ptrs);

		// map<base_gptr*,base_gobj*> ...
		map<void*,void*> tbl;
		for (set<base_gptr*>::iterator p=ptrs.begin();p!=ptrs.end();p++){
			vector<base_gptr*> c=(*p)->children();
			for (int i=0;i<(int)c.size();i++)
				tbl[c[i]]=(*p)->get_gobj();
		}

		// 消しても良いものか、探索を行う。
		// 自分が指されているノード全てが削除可能ノードな場合は削除してよい、
		// ということを再帰的に計算する
		set<void*> hist;
		return search(this,tbl,hist);
	}
	bool search(base_gobj *p,map<void*,void*> &m,set<void*> &hist){
		if (hist.count((void*)p)!=0)
			return true;

		hist.insert((void*)p);
		for (set<base_gptr*>::iterator it=p->parent.begin();it!=p->parent.end();it++){
			if (m.count((void*)*it)==0)
				return false;
			if (!search((base_gobj*)m[(void*)*it],m,hist))
				return false;
		}
		hist.erase((void*)p);
		return true;
	}

	void collect_ptrs(base_gptr *p,set<base_gptr*> &ptrs){
		if (ptrs.count(p)!=0) return;
		ptrs.insert(p);
		vector<base_gptr*> next=p->children();
		for (int i=0;i<(int)next.size();i++)
			collect_ptrs(next[i],ptrs);
	}

	T *get() { return p; }

private:
	T *p;
};

#define GENIUS_CODE 0xabcdfedc

class base_gptr{
public:
	virtual ~base_gptr() {}
	virtual vector<base_gptr*> children()=0;
	bool is_valid() { return code==GENIUS_CODE; }
	int get_code() { return code; }
	void *get_gobj() { return go; }
protected:
	int code;
	void *go;
};

template <class T>
class genius_ptr : public base_gptr {
public:
	genius_ptr(){
		code=GENIUS_CODE;
		g=NULL;
		go=NULL;
	}
	genius_ptr(T *p){
		code=GENIUS_CODE;
		g=new gobj<T>(p);
		go=g;
		g->incr(this);
	}
	~genius_ptr(){
		if (g)
			g->decr(this);
	}
	genius_ptr<T> &operator=(const genius_ptr<T> &r){
		if (g) g->decr(this);
		g=r.g;
		go=g;
		if (g) g->incr(this);
		return *this;
	}

	T &operator *() { if (g==NULL) throw "nullp_exc"; return *g->get(); }
	T *operator->() { if (g==NULL) throw "nullp_exc"; return  g->get(); }

	vector<base_gptr*> children(){
		if (g==NULL) return vector<base_gptr*>();

		char *p=(char*)g->get();
		vector<base_gptr*> ret;
		if (p!=NULL){
			for (int i=0;i<sizeof(T);i++){
				try{
					base_gptr *bp=(base_gptr*)(p+i);
					if (bp->is_valid())
						ret.push_back(bp);
				}catch(...){}
			}
		}
		return ret;
	}
private:
	gobj<T> *g;
};

長い。そのうえ微妙に怪しげな技法が…。

一応、名前は超賢いポインタということでgenius_ptrということに…(つっこみは無しで)。

基本的に参照カウント方式のカウンタを参照しているスマートポインタ

リストを持つことでグラフ構造をたどれるようにしている。

参照関係が変化したとき(要するにスマートポインタがデストラクトされるとき)

そのオブジェクトが破壊可能かを頑張って調べている。

毎回グラフを探索しているのでたぶん規模が大きくなってくると非常に重くなる。

(大きくならなくてもそのコストは参照カウンタの比ではないけども…)

ちなみにこの決定はDPアルゴリズムが存在するが(というか、メモライズするだけか)、

テーブルを用意するのが面倒だったので、上の実装ではNPな感じになっている。

実装も適当なので間違っても実用しないよう…。


以下はテストコード。

class gaa;
class gbb;

class gaa{
public:
	gaa() {}
	~gaa(){ cout<<"gaa死す"<<endl; }
	genius_ptr<gbb> p;
};

class gbb{
public:
	gbb() {}
	~gbb(){ cout<<"gbb死す"<<endl; }
	genius_ptr<gaa> p,q;
};

まずはクラスの定義。

昨日のと大体同じ。

void f4()
{
	genius_ptr<gaa> pa(new gaa());
	genius_ptr<gbb> pb(new gbb());
}

これは単に孤独スマートポインタ

普通にデストラクトされるはず。

void f5()
{
	genius_ptr<gaa> pa(new gaa());
	genius_ptr<gbb> pb(new gbb());

	pa->p=pb;
	pb->p=pa;
}

循環参照。これがちゃんと消えてくれよ。

genius_ptr<gaa> gl_a;

void f6()
{
	genius_ptr<gaa> pa(new gaa());
	genius_ptr<gbb> pb(new gbb());

	pa->p=pb;
	pb->p=pa;

	gl_a=pa;
}

リングごとどっかに保持。消えちゃだめ。

void f7()
{
	genius_ptr<gaa> pa(new gaa());
	pa->p=genius_ptr<gbb>(new gbb());
	pa=genius_ptr<gaa>();
	// ↑ここで死ぬはず
	cout<<"もう死んでますか?"<<endl;
}

途中で死ぬはず、なコード。

int main()
{
	cout<<"** 普通のスマートポインタ。循環参照なし"<<endl;
	f1();
	cout<<"** 普通のスマートポインタ。循環参照あり"<<endl;
	f2();
	cout<<"** 普通のスマートポインタ。循環参照を作った後、循環参照を壊してある"<<endl;
	f3();
	cout<<"** 頑張ってるスマートポインタ。循環参照なし"<<endl;
	f4();
	cout<<"** 頑張ってるスマートポインタ。循環参照あり"<<endl;
	f5();
	cout<<"** 頑張ってるスマートポインタ。循環参照があるけど消したら駄目なケース"<<endl;
	f6();
	cout<<"** 頑張ってるスマートポインタ。循環参照その2"<<endl;
	f7();
	cout<<"** 終わり"<<endl;
	return 0;
}

これで昨日のやつとまとめてテストしてみた。

** 普通のスマートポインタ。循環参照なし
bb死す
aa死す
** 普通のスマートポインタ。循環参照あり
** 普通のスマートポインタ。循環参照を作った後、循環参照を壊してある
bb死す
aa死す
** 頑張ってるスマートポインタ。循環参照なし
gbb死す
gaa死す
** 頑張ってるスマートポインタ。循環参照あり
gaa死す
gbb死す
** 頑張ってるスマートポインタ。循環参照があるけど消したら駄目なケース
** 頑張ってるスマートポインタ。循環参照その2
gaa死す
gbb死す
もう死んでますか?
** 終わり
gaa死す
gbb死す

普通のスマートポインタでは循環参照が削除できていないのと、

ジーニアスポインタでは循環参照を削除できているのと、

消したら駄目なケースではちゃんと消えていないのと、

消したら駄目なやつがプログラムの終わりでちゃんと消されているのに注目。


それではこんなところで。

yaneuraoyaneurao 2004/12/20 07:06 私の考えた方法と、元となるアイデアは同じですネ。

結局、root集合から到達可能かをこのポインタのデストラクトのときに何らかの形で調べなければならないという。まあ、その部分に多少の最適化の余地があるにせよ、実用にならないことは間違いないわけで..。

この問題って、コンパイラ自体を自作すると仮定して、データ構造がりごり変更しても構わないとしてもやはりどうにもならないんですかネ..悔しいナァ..。

tanakhtanakh 2004/12/20 17:49 そうですね。毎度探索を行わないでルートから到達可能かどうかを判断するのはちょっと無理そうですね。
処理系を作る場合は普通にルートから探索するGCを実装したほうがやはり良いとは思いますが…。賢いポインタ方式だと末端からの探索になるわけですけど、毎回ルートからたどるのと同程度のコストがかかるわけでやっぱりちょっと難しそうですね。

トラックバック - http://d.hatena.ne.jp/tanakh/20041221

2004年12月20日(月) 超賢いポインタ (前編)

[]超賢いポインタ 超賢いポインタを含むブックマーク 超賢いポインタのブックマークコメント

  • 前口上

C++ではメモリを自分で管理しなければならない。

オブジェクトのライフタイムが単純に決められない場合、

いつオブジェクトを削除するのかを決めるのが難しく、

結局自前でGCのようなものを作ることになってしまう。

(…まあ、そこまであれなケースはめったに無いけど)

単純に消し忘れの危険性があるという問題もある。


そこで、C++の標準的なライブラリではその辺を解決すべく

いくつかのライブラリがある。

まず、STLのauto_ptr。これは単にスコープの終わりで

デストラクトするだけで、スコープオブジェクトのライフタイム

が一致する場合に消し忘れを防ぐ、程度のものであろう。

次にboostのshared_ptr。これは参照カウンタを用いて

オブジェクトを管理している。

おおむね、shared_ptrはうまく機能するのであるが、

ポインタの参照関係がグラフ状になっている場合はうまく削除できない。


で。そういう場合はどうするのかというと、

weak_ptrなる参照先がこっそり死ぬかもしれないポインタを使ってみたり

そもそも設計を見直してみたり

(…私は循環参照が正当なケースは普通にあると思いますがね)

するわけである。

しかしやはり循環参照の問題を解決できないものかと誰でも一度は(?)

考えるもので、私も2年ほど前から時々考えていた。

で、昨日電車に乗りながらぼーっと考えていたらいけそうな気がしてきて、

やってみたらいけたっぽいような。構想二年、製作二日である。

(あらかじめお断りしておくのだが、あくまでグラフ理論的に

どうこうという話であって、決して実用な物ではないので。)

  • まずは普通のものを

まず、普通のスマートポインタを実装してみる。

これはスマートポインタ間でオブジェクトを共有して、

そこに参照カウンタを持たせて、それを上げ下げしてうんぬん…

というように実装すればよい。

スマートポインタを表すクラスポインタをラップして

カウンタを持たせるクラスの二つを作る。

template <class T>
class obj{
public:
	obj(T *p):p(p),cnt(1) {}
	~obj() { delete p; }

	void incr() { cnt++; }
	void decr(){
		if (--cnt==0)
			delete this;
	}
	T& ref() { return *p; }

private:
	T* p;
	int cnt;
};

template <class T>
class sptr {
public:
	sptr()           { o=NULL; }
	sptr(T *p)       { o=new obj<T>(p); }
	sptr(sptr<T> &r) { o=r.o; if (o) o->incr(); }
	~sptr()          { if (o) o->decr(); }

	sptr<T> &operator=(const sptr<T> &r){
		if (o) o->decr();
		o=r.o;
		if (o) o->incr();
		return *this;
	}

	T &operator *() { if (!o) throw "nullp_exc"; return  o->ref(); }
	T *operator->() { if (!o) throw "nullp_exc"; return &o->ref(); }

private:
	obj<T> *o;
};

非常に単純にこのように実装できる。

objクラスを受け取ったときにカウンタを増やして、

手放すときにカウンタを減らしている。

カウンタが0になれば勝手に削除される。

使用例は以下の通り。

class aa;
class bb;

class aa{
public:
	aa() {}
	~aa(){ cout<<"aa死す"<<endl; }
	sptr<bb> p;
};

class bb{
public:
	bb() {}
	~bb(){ cout<<"bb死す"<<endl; }
	sptr<aa> p,q;
};

まずこのようなクラスを定義。

void f1()
{
	sptr<aa> pa(new aa());
	sptr<bb> pb(new bb());
}

f1()から抜けると二つはデストラクトされる。

void f2()
{
	sptr<aa> pa(new aa());
	sptr<bb> pb(new bb());

	pa->p=pb;
	pb->p=pa;
}

循環参照を作る。f2()から抜けてもカウンタは0にならないので

デストラクトされない。

void f3()
{
	sptr<aa> pa(new aa());
	sptr<bb> pb(new bb());

	pa->p=pb;
	pb->p=pa;

	pa->p=sptr<bb>();
}

片方の参照を切ってみる。

これだと片方の参照カウントが0になるのでそこからデストラクトされる。

は、長くなってきたのでひとまず次回へ、つづく。

yaneuraoyaneurao 2004/12/20 04:27 私も以前に(2年ぐらい前に)超賢いポインタ(?)を実装しました。遅すぎて、ふつうにincremental GCを実装したほうがはるかにマシだという結論に達したので闇に葬りました..(´д`)

参照カウント方式のスマートポインタ + incremental GCとかいう組み合わせは結構現実的だとは思いますけれども。

tanakhtanakh 2004/12/20 05:13 うはぁ、先に言われちゃいました。
そうですね。高速なアルゴリズムは私も思いつきませんでした。
ただ、GCを実装するとなるとデータ構造に若干の制限を受ける
(…はず)のがいやといえばいやで、
使い分けをするのもいやといえばいやですかね。
でも多分、実用的には(というか、全て速度的な要因から)
超賢いポインタはだめですね…

トラックバック - http://d.hatena.ne.jp/tanakh/20041220

2004年12月19日(日) 超賢いポインタ

何なんだろうなぁ… 何なんだろうなぁ…を含むブックマーク 何なんだろうなぁ…のブックマークコメント

ああ。ああ。ああっ。

また書きたいネタを書かずにずるずるとすごしているっ。

というか、何か書きたいことが出てきても、

どうも後から考えるとくだらないことのような気がして

どうにもこうにも…。

[]Fedora Core が超重い… Fedora Core が超重い…を含むブックマーク Fedora Core が超重い…のブックマークコメント

なんだかんだあって、ICPC世界大会にいくことになったので

それなりにちゃんと準備をすることになった。

これまではメディアセンターの貧弱な環境で細々と練習会を

やっておったのであるが、やはり世界となると待遇が違う。

湯浅研の研究室を貸してもらえることになった。

(どうでもいいが、私は4回生なのだが来年修士じゃなくて

学部5回生なので、まだ研究室なるところに立ち入ったことが無いのだ)

コンピュータも一つ使わせてもらえることになった。


とまぁ、ここまではよい。

その使わせてもらえることになったマシンが問題なのである。

CPUはPentiumIIIのなにか。これもまぁ、今となっては極おそだが

そこまで問題になることはなかろう。

メモリが!メモリが64MBしかないのである。

6年ほど前ならこの程度が標準スペックだったし、

このマシンに最初から入っていたWindowsNTはそれなりに動いていた。

しかしそこは本番の環境と同じのFedora Core 2である。

Linuxは軽い、空いたマシンLinuxでもいれとけ。

というのも今は昔。Linuxも進化を重ね極重OSへと変貌を遂げていたのである。

いや、全く。


64MBマシンFedora Coreを入れた人はどれぐらいいるだろうか。

というか、ちゃんと入るんか?とすら思えてくるが。

実際のところインストールは出来た。

しかし、それは我々の想像を遥かに超えた困難の連続なのであった。


まず驚いたのが、インストール中にメモリが足らなくなる。

メモリが足らなくなるのでさっき作ったスワップを使わせろ、

とかいうダイアログが出てくるのである。

どれだけメモリを食うインストーラなのだ。


次に驚いたのがデフォルトスワップ設定ではインストール

途中で止まる。

というか、デフォルトではスワップ領域が実メモリの3倍(…と思う)

取られるのだが、64MBの3倍、つまり192MB用意されるので、

合計ではメモリが256MB使えるということになる。

要するにインストーラがこれ以上のメモリを要求してしまったということか。

スワップを1GBぐらいにすると何とかインストールは終わった。


そんなこんなで色々失敗しながらインストールしていたら

結局4時間ぐらいかかってしまった。

と、ここまででも充分大変だったのだが、

本当の苦労はここからである。

まず。ターミナルを立ち上げようとすると10秒ぐらい固まる。

emacsを起動しようとするとこれまた数十秒固まる。

(めちゃくちゃ小さいソース一つの)コンパイルに1分ぐらいかかる。

ブラウザを立ち上げると1分ほど待たされる。

ブラウザを起動するアイコンクリックしても

全然応答が無いから待ってる間にターミナルを起動して

色々作業しながらさっきやっぱりクリックできてなかったんかなぁ

とか思ってるといきなりブラウザが起動したりとか。

GUIのメニューをクリックするとメニューが降りてくるまでに

5秒ぐらいかかる。

そして。

ブラウザでページを見ようとすると表示されるまでに

10分ぐらいかかる………。


もうねぇ…何の練習してるのか全然分からない。(忍耐か?)

uvaを解こうと思うと、

まず、uvaのトップページが出てくるまでに早けりゃ数分。

たいていは途中間でしか表示されないままDoneとか表示されるので

リロードが必要になる。

リロードするとまた早くても数分かかるわけで。

問題セット選んで問題見るまでに数十分。

問題解いてSubmitすると、これまた応答まで数十分。

何でページ表示するだけなのにHDDごりごりやってるんだとか

本当にイライラがつのる。


システムモニタメモリ使用状況を見てみるとMozilla99MBとか、

もうなんじゃこりゃって感じですな。

メモリ64MBしかつんでないのに。

他のプログラムもことごとく数十MB食いつぶしてるし、

いやはやなんとも。


というわけで、こんな状況では練習時間のほとんどが待ち時間に

なってしまうので早急に何とかしたいものである。

これではメディアセンターで細々とやっていたほうが

遥かにマシ…。まともな計算機環境なだけ。

[]超賢いポインタ 超賢いポインタを含むブックマーク 超賢いポインタのブックマークコメント

愚痴を書いていたら長くなったので、

本題のこちらは明日分にでも書くことにする。

h_sakuraih_sakurai 2004/12/19 21:03 うわ!なんだ!超賢いポインタって!気になる!

tanakhtanakh 2004/12/19 21:08 ああっ。あんまり期待しないでください。多分予想できる内容です。

トラックバック - http://d.hatena.ne.jp/tanakh/20041219

2004年12月08日(水) 歯医者生活3週間目

[]あのころに戻りたい あのころに戻りたいを含むブックマーク あのころに戻りたいのブックマークコメント

今年の夏ごろから放置していた虫歯

ICPCのころから顕著化(お湯でもしみる)していたので

歯医者に行ったら神経を抜かなければならないということで。

ああ、この年ですでに一本失うとは。

確かにあんまりちゃんと歯磨きしてなかったけど、ショックである。


とりあえず、一週目→応急処置、二週目→歯髄を取る、

三週目(いまここ)→さらに取る(?)。殺菌。

なんだかまだまだかかりそうな予感。

今週なんか麻酔なしで取り残しの神経を取るもんだから痛い痛い。

しかし、こんなに時間がかかるとはおもわなんだ。

これまでの経験(とはいっても最後に歯医者に行ったのが

小学生のときだったような)から一回いってささっとけずって

終わりだと思ったのに。


そういうわけで、皆様も歯だけは大切に。

一度失った歯はもう戻りません…。

[][][]汎用オセロサーバ 汎用オセロサーバを含むブックマーク 汎用オセロサーバのブックマークコメント

なぜかここでオセロ

ここ一週間ほど断続的に作っていました。

名目はオセロサーバ

Haskellでのネットワークプログラミング練習など。

結果は思ったより良好です。

  • 概要

ネットワーク越しにオセロの対戦を実現するプロトコルの実装。

実装は、かなり趣味世界だが

TCP越しにS式を転送するプロトコルを実装し、

その上に実装している。

プロトコル仕様は簡便に。

なるべくシンプル。

(現状ではセキュリティーとか何も考えていないので

不正し放題かもしれない)


クライアントとして思考ルーチンを作れば思考ルーチン同士を

戦わせることが出来、その仕様は割りと自由に出来る。

  • 実装

サーバとCUI版クライアントなど。

対戦の仕方は非常に煩雑…。


C#で適当に作ったGUIクライアント。

C#版S式パーザとしても使える…かも。


さらにもうひとつ。

C++で作った思考ルーチンクライアント。

これにもS式パーザが(当たり前ですが…)。

思考ルーチンは深遠な話題なのでまた今度。

  • とりあえず

サーバを立ててGUIクライアントで接続しつつ

思考ルーチンでも走らせてみてください。

この思考ルーチンはそんなに強くないけど…。

めちゃくちゃ強い思考ルーチンで殴りこみ…

とかは大歓迎です。

[]ICPCその後 ICPCその後を含むブックマーク ICPCその後のブックマークコメント

残りの問題を解いた。

F問題は実装がめんどくさいと思ってたのだが、

実装してみると全然めんどくさくなかった。

I問題はM氏が解いた。体積を求めるのはさほど難しくない

(数値積分を使った模様)ので、

立体を微小に膨らませたときの体積を求めることにより

表面積が求まるというもの。

表面の面積を直接求める方法もあるようだが、

難しそうだというのは想像に難くない。

(FとIのソースは本体ページの参加記に追加してあります)


というわけで、これでICPCの復習もひとまず終わった。

順位のほうもいつの間にか1位扱いになってて嬉しい。

トラックバック - http://d.hatena.ne.jp/tanakh/20041208