研究日誌とうめき の変更点
Top / 研究日誌とうめき
- 追加された行はこの色です。
- 削除された行はこの色です。
- 研究日誌とうめき へ行く。
- 研究日誌とうめき の差分を削除
[[TopPage]]
-[[M1研究ページ>研究日誌とぼやき]]
-[[B4研究ページ>研究日誌とつぶやき]]
-[[vista - ubuntu8.04(on VMware)間での共有フォルダ設定]]
-[[Vistaで自動シャットダウン]]
&br();
-[[研究日誌>#report]]
--[[hyperlink仕様まとめ]]
--[[読み物]]
--[[SLIM callback関連 メモ]]
--[[M2,M1顔文字集>#face]]
-[[うめき>#word]]
-[[言語班ローカル/CHR encoding:http://www.ueda.info.waseda.ac.jp/lmntal/local/pukiwiki.php?CHR%20encoding]]
*Contents[#s8e0a853]
#contents
*TODO[#s8e0a853]
-hyperlink関連コードにもっとコメント残す
//-研究環境の整備
//--新しいPC、NIOLO2？
//--デュアルディスプレイにしたい
&aname(report);
*研究日誌 [#s8e0a853]
**2011-03-26 [#t6eada5a]
***KI journal の英訳文 [#ya60ff78]
-申し訳程度のtexファイルがgoudaのhome/seiji/ki2011/にあります
**2011-03-18 [#n7021431]
***JSAI2011執筆時の実験結果 [#e52bffe0]
-&ref(./experiment_LATEST_slim428.zip);
--CHR,LMNtalプログラム入り
**2011-02-19 [#q9971212]
***論文の所属 [#zed0f856]
-基本的に研究した所属を「所属」に書く
--論文発表時に別の所属になってる場合には、脚注に書く人もいる
**2011-02-09 [#n49f731d]
***修論の漢字統一 [#sb7a0ec9]
-分かる
-思う
-できる
-とき
-つながる
-および
-組合せ
-一つ, 1個
-みなす
-こと
-もの
-行う
-全て
-
**2011-02-08 [#ze430023]
***paragraphで改行 [#ta0591a1]
-させたかったら
\paragraph{タイトル \\}
-のように{}の中に\\を書けばよい
**2011-02-05 [#n6e38065]
***eclipseでtex [#z228e7c3]
-[[ここ参照>http://oku.edu.mie-u.ac.jp/~okumura/texwiki/?TeXlipse#m60f5d27]]
***texの使い方 [#s6e148aa]
-\documentstyle[report,12pt]{jsbook}は\documentclass[report,12pt]{jsbook}
-\pagestyle{heading}は\pagestyle{lineheadings}
--だとうまくいったけど、あってんのかな
-documentclassからbegin{document}までがプリアンブル部
**2011-02-04 発表終了！！ [#h30ccea0]
***いただいたコメント [#x97b8ebd]
-膜はいらなくなっちゃったの？(中島先生)
--いります。膜には階層を作って計算の局所化を行う役割があるので、それはハイパーリンクにはない機能です。
-ハイパーリンクによって非効率的なマッチングが減ったのはわかった、それはモデルが単純に記述できるようになったからだよね？(中島先生)
--それが一つの理由で、もう一つはハイパーリンクの接続関係を利用したマッチングがあります。（詳しめに説明）。CHRの最適化もこれと似たような考え方を使っています。
-どういうときに膜、ハイパーリンクを使い分けるの？(中島先生)
--ハイパーリンクには、接続先を計算量１で取得する機能があります、これは論理変数にも無い機能です。今までは集合は膜で囲って、中にアトムを入れるとかしていましたが、その個数を数えるためにはルールを繰り返し適用して数えるしかなかった。
---だから局所化は膜、集合を扱う場合にはハイパーリンクだね。(上田先生)
-マッチング最適化のスライドをもっとちゃんと用意しておけばよかった
***用意していた回答 [#j8fea1ce]
-LMNtal内だけのことでしょ？
-LMNtal以外に利用できる新規性は？
--論理変数+要素数の取得ができる点で、新規性がある（よね？）
--(これが一番？)既存のUnion-Find algorithmを改良した点。特にUFにもともと無い要素削除処理を入れたり、集合全体の要素数を常に保持する処理(要素数を計算量１で取得するため)を追加している
--CHRの実績を持ち上げ、それとLMNtalの関係性について述べる、LMNtalでも実アプリ記述できますよ的な
--非効率的マッチングの防止はLMNtalを含む多重集合書換え言語モデルにとって大事
-他の多重集合書き換え型言語って何？
--う、きつい。マッチングの仕方まで詳しく調べたのはCHRだけなので、他のも話せるようにしましょう。
-今までもCHRをエンコードできていた、っていうのはどうやって示したの？
--まずLMNtalはProlog, CHRに影響を受けている言語で、構文から見ればエンコードに問題は無い。言語仕様決定の段階で、論理プログラミング言語の一対一エンコードのし易さにも言及している。
--ただし、CHRには3種類のルールがあり、この内2つはLMNtalでもサポートされているが、残りのPropagation ruleはLMNtalには無い概念であった。そこでuniq制約を入れた。これで全てのルールも一対一でエンコードできるようになった。
---あたりが示し方かなぁ？
**2011-02-02 [#w26e9a3f]
***現時点での処理系行数（アバウト） [#v8bde261]
-上2つはこの日にwcで計測、コメントアウトも入っている
--Java処理系：38460+19010+2784=60254
--SLIM：27708+29285=56993(ファイルの頭のコメントは計4600行くらい)
--LaViT：30000くらい
--UNYO：15000くらい
**2011-01-28 [#gb52e399]
***文字数の差 [#v688fc95]
-各例題の文字数を数えてみた
|example|atom_cmp|cycle|leq|fibonacci| uf|uf_opt|*ram_simul|h
|lmn | 26| 84|241| 157|357| 537| 766|
|lmn-mem| 31| 184|645| 549|627| 1112| 無理|
|lmn-hl | 18| 60|207| 348|301| 483| 653|
|chr | 20| 51|144| 183|266| 345| 612|
-- memがすごいことに
-- *ルールはadd,sub,cjump0,cjumpN,haltのみ
-- *全部のルールを含めると順に2378, 無理, 2266, 2069.
***ちなみに [#yb981772]
-(ハイパーでない)グラフ <=> 一般グラフ
-ハイパーグラフ <=> 超グラフ
--と呼ぶらしい
**2011-01-27 [#kb0dde60]
-修論一旦提出
-JSAI2011に申込み、発表はたぶん目黒パワーに期待することになりそう
**2011-01-26 [#h2312eee]
***韓国に劇的勝利 [#pedae3cc]
***texの表で破線を使えるように [#ufb10270]
-&ref(arydshln.sty);
cc|ccc:rrr| とかそんな感じで":"いれたとこが破線に
**2011-01-25 [#lf757ba7]
***unary用比較演算子"\==" [#n1de5431]
-を追加してみた
a(X), b(Y) :- X \== Y | .
----------------------------
--guard:L118:
spec [3, 7]
derefatom [3, 1, 0]
isunary [3]
derefatom [4, 2, 0]
isunary [4]
getfunc [5, 3]
getfunc [6, 4]
neqfunc [5, 6]
jump [L103, [0], [1, 2, 3, 4], []]
**2011-01-24 [#tc9f4e02]
***論文で中間命令列の一覧を書きたいとき （修正版） [#p26c1af9]
-幅が半分に設定されていたので直してみた、他にも色々修正
-thesis.texに追加する方ね
\newenvironment{instruction}[2]{%
\vskip-0.5\baselineskip
\vbox{\hbox to 1\textwidth{\hrulefill}}
\nobreak
\vskip-0.7\baselineskip\nobreak
\begin{description}
\item[\texttt{\hspace{10pt}#1 \rlap{[\textit{#2}]}}]\hfill\break
\rightskip0zw}%
{\end{description}\nobreak\vskip-1.0\baselineskip\nobreak
\hbox to 1\textwidth{\hrulefill}}
***論文で中間命令列の一覧を書きたいとき [#l678d191]
-jssst2007から掘り起こしてきた
- メインとなるファイル(thesis.texとか)の\begin{document}よりも前に
\newenvironment{instruction}[2]{%
\vskip-0.2\baselineskip
% \vskip-0.0\baselineskip
\vbox{\hbox to0.48\textwidth{\hrulefill}}\nobreak
\vskip-0.3\baselineskip\nobreak
\begin{description}
\item[\texttt{\hspace{-3pt}#1 \rlap{[\textit{#2}]}}]\hfill\break
\rightskip0zw}%
% {\end{description}\nobreak\vskip-0.7\baselineskip\nobreak
{\end{description}\nobreak\vskip-0.5\baselineskip\nobreak
\hbox to0.48\textwidth{\hrulefill}}
-を入れる(コメントアウトとかいらなそうなのもそのままコピペしてる)
-中間命令を書きたいページで
\begin{instruction}{spec}{formals, locals}
% 命令列の実行中はアトムや膜は変数番号でアクセスするが，
% 本命令は，
［制御命令］
仮引数の数 (本命令列に渡されるアトムや膜の数) を \textit{formals}，
本命令列で保持すべきアトムや膜の総数を \textit{locals} から受け取って，
後者を保持できる大きさの変数ベクタを確保する．
\end{instruction}
-な感じで記述すればおｋ
**2011-01-20 [#b48f85e0]
*** hyperlink : groundチェックでのバグ [#p0a5b31e]
- 昨日直したと思ったけど、直っていなかった
--原因は大体把握したけど、どう直すかはしっかり考えないといけないかも
---修論後？
**2011-01-19その2 [#t6037b49]
-memo for gocho
-before
/* groundはつながったグラフなので1つの根からだけたどればよい */
{
LinkObj l = (LinkObj)vec_get(srcvec, 0);
vec_push(unsearched_link_stack, (LmnWord)LinkObj_make(l->ap, l->pos));
}
-after
/* groundはつながったグラフなので1つの根からだけたどればよい */
{
LinkObj l = (LinkObj)vec_get(srcvec, 0);
if (LMN_ATTR_IS_EX(l->pos)) {
hashset_add(found_ground_symbol_atoms, l->ap);
++count_of_ground_atoms;
}
else vec_push(unsearched_link_stack, (LmnWord)LinkObj_make(l->ap, l->pos));
}
**2011-01-19 [#vadd00c3]
***新仕様の[[ハイパーリンク仕様まとめ>http://www.ueda.info.waseda.ac.jp/lmntal/local/pukiwiki.php?%A5%CF%A5%A4%A5%D1%A1%BC%A5%EA%A5%F3%A5%AF%BB%C5%CD%CD%A4%DE%A4%C8%A4%E1]]（言語班ローカル） [#k43b9e81]
-まとめてみた
***Java処理系公開の手続き [#t4cd1593]
-[[http://www.ueda.info.waseda.ac.jp/lmntal/local/pukiwiki.php?ant]]
**2011-01-16 [#dfaa43f8]
***hyperlink : commit! [#se12695f]
-してしまった。致命的なバグがないことをみんなで祈ろう。
-追加したもの
--hyperlink
--hyperlinkを利用したマッチング最適化機能（findproccxt命令ほか）
--callback関数gettimeと、SLIMモジュールtime.lmn
***slim419でedfs_t*.ilがsegmentation fault [#j11f67de]
-%%gochoが直してるバグってこれかな？%%
--元々--delta-memで動かない例題だった
***修論タイトル [#u3366a25]
-酔った勢いでかっこよさげなの考えてみる
--%%並行プログラミング言語LMNtalにおけるLMNtalグラフのハイパーグラフへの拡張%%
--LMNtal連呼してる感じなので却下
**2011-01-15 [#ta1b22e7]
***[[すっきりCHR>http://www.ueda.info.waseda.ac.jp/~seiji/trychr]] [#j7e43cf4]
-リニューアル。何気にサイト名で検索すると上位に。
**2011-01-15 [#s1081fce]
***hyperlink : ハイパーリンクのIDをインクリメンタルな数値に [#m05e86bd]
- ''hyperlinkに値を代入する話ではない''
- hyperlink木からhyperlinkオブジェクトを削除する際、木の中で削除対象のオブジェクトを葉に向かってスワップしていき、葉に到達した時点で削除するような最適化(子をたくさん持ったまま削除すると色々処理がかかる)を入れたため、集合を代表する(rootの)IDが固定されなくなってしまっていた
- これだとuniq制約で履歴を管理する際に苦しい
-- インクリメンタルな番号をふり、uniqの履歴および標準出力時にはそれをIDとする
-- hyperlinkのuniqへの対応＋出力時のIDの短縮化が可能に
-出力before
tmp.
tmp :- new($x) | a($x), b($x).
*--->
a(!1ab5038). b(!1ab5068). @5.
== HyperLink =============================================================
[hl_ID] [parent] [linked with] [num] [direct children ( inside info )]
1ab5038 root a 2 1ab5068.
1ab5068 1 b 2
================================================ 1 group, 2 elements ====
-出力after
tmp.
tmp :- new($x) | a($x), b($x).
*--->
a(!1). b(!2). @5.
== HyperLink =============================================================
[hl_ID] [parent] [linked with] [num] [direct children ( inside info )]
1 root a 2 2.
2 1 b 2
================================================ 1 group, 2 elements ====
- --show-hlオプションをつけない通常の出力
a(!1). b(!1). @5.
**2011-01-14 [#h20ab9ee]
***hyperlink : コミット作業中 [#jf029420]
- callback関数をモジュールで呼び出せるtime.lmnも追加予定
//**2011-01-11 [#c23827cd]
//*** 再現性のある疑似乱数integer_rand_lcg（とgettime） [#ed001670]
//- 線形合同法によって疑似乱数を生成するcallback関数を書いてみた
// i(20). list = [].
// i(I), list = H :- I>0, I1=I-1 | i(I1), list = [integer.rnd_lcg | H].
// *--> list([8,4,5,2,0,6,7,9,1,3,8,4,5,2,0,6,7,9,1,3]).
//-- 一度関数が呼ばれるごとに、0 から 9 の間での乱数を一つ返す
//-- ソースファイルを見れば分かるが、厳密な線形合同法ではない、けど十分でしょう//-integer_rand_lcgとgettimeをmoduleでも使えるようにした
//--hyperlinkのコミット時に一緒にコミットしちゃおうかな
**2011-01-10 その2 [#p531d49c]
*** hyperlink : 新々仕様での実験 ram_simul_many [#i9dab134]
|N |5k |10k |20k |40k |80k |O |h
|slim int |1.59|3.16|6.33|12.65| 35.71| |
|slim hlink old|0.15|0.28|0.55| 1.10|IDover| |
|slim hlink new|0.18|0.36|0.72| 1.43| 2.83| |
|chr int opt |0.21|0.51|1.26| 3.61| 8.51| |
*** hyperlink : 新々仕様での実験 fibonacci_topdown [#n7f4e368]
|N | 5k| 8k| 10k| 16k| 20k| 32k| 64k|128k|O|h
|slim hlink old|0.08|0.14|0.18|0.28|0.37|0.56|IDover| |N|
|slim hlink new|0.08|0.13|0.16|0.26|0.32|0.51| 1.02|2.06|N|
|chr int opt |0.03|0.04|0.08|0.10|0.17|0.20| 0.46|1.11|N|
//***hyperlink：新々仕様での実験 cycle_backedge3 [#b8d8af39]
//-3頂点からなる閉路を探索する(propagation, uniq無し)
//- mem allはグラフ生成の時間も含めた総実行時間
// edge(X, Y), edge(Y, Z), edge(Z, X) <=> cycle(X, Y, Z).
//|N |100 ||500 |1000 |2k |O |h
//|slim int |243.43|| | | | |
//|slim mem | 0.02|| 0.34|1.43 | | |
//|( mem all) | 0.22||24.65|197.42| | |
//|slim hlink old| 0.04|| 0.73| 2.63| 5.90| |
//|slim hlink new| 0.07|| 1.39| 5.60|13.95| |
//|chr int opt | || 1.25| 2.54| 5.05| |
***hyperlink：新々仕様での実験 atomcmp_x3 [#xc17dd11]
- hlinkは全て--hl-optで測ることにする(./hltest_new/)
- lmntal -O3 --slimcode --hl-opt atomcmp.lmn | slim --hl -
|N |8k*3 |16k*3 |32k*3 |64k*3 |128k*3|256k*3|O |h
|slim int |38.94|156.27|631.03|--- |--- |--- |N^2|
|slim mem | 0.03| 0.06| 0.12| 0.24| 0.48| 0.95|N |
|slim hlink old| 0.02| 0.03| 0.06| 0.12|IDover| |N |
|slim hlink new| 0.06| 0.11| 0.22| 0.44| 0.88| 1.79|N |
|chr opt | 0.11| 0.21| 0.47| 0.96| 1.84| 3.67|N |
**2011-01-10 [#n0abee8a]
*** hyperlink : 中間命令列の並び替え [#j4755ff3]
- コンパイラを若干変更
-- newhlink, makehlinkとuniqの並び替えがうまくいっていなかったのを修正、コミット
-- ついでにコードの整理もちょっとやった
**2011-01-08 [#a4023296]
***計算量が悪い件 [#nb8eb79a]
-原因が把握できた
--なぜ膜内の！アトムを全てさらうようにしていたのか、理解に苦しむ
*** --enable-gprof(と--disable-tcmalloc)でallocs/freesの数が合わない [#x2936051]
lmntal --slimcode -e "a." | valgrind src/slim -
-valgrindで見るとfreesが1足りない
--俺の環境だけかな？
---2つのデバッガを同時に使う俺が悪い 2011-01-14
**2011-01-07 [#s904e67a]
***fibonacciとramを測定 [#ve536dc2]
-オーダーが悪い...
-- --p3でチェック、ルールの適用/試行/バックトラック回数は旧実装より悪いルールは無い
--内部実装の問題、見直し中
-fibonacci_topdown(unify)
|N | 4k| 8k| 16k| 32k||O |h
|slim hlink new|0.13|0.41|1.90|14.60||? |
-ram_simul
|N | 5k| 10k| 20k||O |h
|slim hlink new|0.66|3.84|22.60||? |
**2011-01-04 [#k102ad93]
***hyperlink : 所属膜へのポインタ [#iab55978]
-持たせておけば、hyperlinkからのfindatomをもう少し効率化できる気がする
***hyperlink : ユーザIDの追加検討 [#oc8204c8]
-機能としては用意しておきたい。がバグが取れてから...
-- CHRでは同じ値を束縛された論理変数が生成された場合は、生成された時点で同じ集合に属する
X is 1.
hoge <=> Y is 1, v(Y).
-- （必須ではないが）hyperlinkにもこういう機能がないと、プログラムが煩雑になる
--- 非効率なマッチングを生まないように書くために、色々と苦労しそう
イメージ：
hoge :- make($x, 123) | h($x).
*---> h(!123).
(ID123を持つ他のhyperlinkの集合と併合された状態で生成される)
**2010-12-28 [#vdf04a81]
***hyperlink : ハッシュ表による管理を廃止 [#l3e25c5a]
-新しい属性LMN_HL_ATTRのバグがかなり取れてきた気がするので、ハッシュ表でatom pointer => hyperlink objectの参照関係を管理していたのを廃止
-"!"アトムの第2引数にhyperlink objectへのポインタを直接埋め込む
--適当に測ってみた
|N |8k*3 |16k*3 |32k*3 |64k*3 |128k*3|256k*3|O |h
|slim hlink new(廃止前)| 0.06| 0.12| 0.27| 0.57| 1.16| 2.35|N |
|slim hlink new(廃止後)| 0.04| 0.08| 0.17| 0.36| 0.74| 1.50|N |
**2010-12-22 [#rd3e5b67]
***最短"経路"問題 [#qde1b7c2]
-最短距離を求めるプログラムは色々あるけど、uniq使えばたいがい1,2ルールで書ける
-ただ最短"経路"となると2行で書けるのかちょっと自信無かったけど、なんとか書けた
--&ref(./shortest.lmn,shortest.lmn);
**2010-12-21 [#j4fad4c0]
***hyperlink：新仕様での実験 cycle_backedge5 [#b8d8af39]
-3頂点からなる閉路を探索する(propagation, uniq無し)
edge(X, Y), edge(Y, Z), edge(Z, X) <=> cycle(X, Y, Z).
|N |100 ||500 |1000 |2k |O |h
|slim int |243.43|| | | | |
|slim mem | 0.02|| 0.34|1.43 | | |
|( mem all) | 0.22||24.65|197.42| | |
|slim hlink old| 0.04|| 0.73| 2.63| 5.90| |
|slim hlink new| 0.07|| 1.50| 6.15|13.95| |
|chr int opt | || 1.25| 2.54| 5.05| |
--計測途中
**2010-12-18 [#ice96280]
***hyperlink：新仕様での実験 atomcmp_x3 [#xc17dd11]
- hlinkは全て--hl-optで測ることにする(./hltest_new/)
- lmntal -O3 --slimcode --hl-opt atomcmp.lmn | slim --hl -
|N |8k*3 |16k*3 |32k*3 |64k*3 |128k*3|256k*3|O |h
|slim int |38.94|156.27|631.03|--- |--- |--- |N^2|
|slim mem | 0.03| 0.06| 0.12| 0.24| 0.48| 0.95|N |
|slim hlink old| 0.02| 0.03| 0.06| 0.12|IDover|IDover|N |
|slim hlink new| 0.06| 0.12| 0.27| 0.57| 1.16| 2.35|N |
|chr opt | 0.11| 0.21| 0.47| 0.96| 1.84| 3.67|N |
-- hyperlink のIDの上限が無くなったのが大きい
***カラー大辞典 [#r211acbd]
-[[原色>http://www.colordic.org/]]
-[[パステル>http://www.colordic.org/p/]]
**2010-12-14 [#i31cddb6]
***ubuntu9.10にopenoffice3.2 [#kb30fc40]
-[[ここ>http://user.services.openoffice.org/ja/forum/viewtopic.php?f=6&t=586]]
-エラー
ステータスデータベースエリアが別のプロセスによってロックされています
--synapticが開いていると出る
**2010-12-13 [#n5bf4b7b]
*** 解放忘れ？ [#fff188bd]
-公開版slimで以下のようにデータ型だけのground型比較をするとメモリリークがあると言われる、俺の環境のせい？
a(1), a(1). a(X), a(Y) :- X = Y | ok.
--eqground/neqgroundでのsrcvec, dstvecの解放がrev400以降無くなってる
--復活させるとちゃんと解放されてるみたいだけど、他の処理に作用してないだろうか
---2010-12-14 修正前/修正後で差異が無かった（benchmarksetの例題に対して--nd, --mem-enc実行で状態数を比較）のでコミット
**2010-12-12 [#i2967981]
*** hyperlink 比較系memo [#g60c1cb8]
-isground
-eq/neqground
-eq/neqfunc
-samefunc
--lmn_eq_func
*** memo[#h7942c2c]
-wine : 282MB
-wine-dev : 18MB
-QuickTimeInstaller.exe : 36.4
-iTunesSetup.exe : 78.1
**2010-12-10 [#c73da7ff]
***hyperlink : 新仕様での実行時間 [#g287c412]
-アトム生成&削除
--10000個のatom(hyperlink)をN回生成->削除
--どちらもtime optimized slim
|N | 100| 200| 400| 800|h
|symbol atom|1.91|3.72| 7.40|14.75|
|hyperlink |3.78|7.65|15.31|31.87|
-new_and_delete.lmn
start(10000, 100).
init @@ start(M, I) :- int(M) | s(M, I, M).
return @@ s(0, I, M) :- I > 0, I1 = I-1, int(M) | s(M, I1, M).
/* atom */
new @@ s(I, J, M) :- I > 0, I1 = I-1 | s(I1, J, M), a(b).
delete @@ a($a) :- unary($a) | .
/* hyperlink */
//new @@ s(I, J, M) :- I > 0, I1 = I-1, new($a) | s(I1, J, M), a($a).
//delete @@ a($a) :- hlink($a) | .
-hlink制約
--10000*N回のhlink型検査を行う
|N | 100| 200| 400| 800|h
|old hyperlink|1.17|2.36|4.74| 9.52|
|new hyperlink|1.42|2.82|5.62|11.42|
--旧仕様：hlink型検査はファンクタIDの比較
--新仕様：hyperlink属性を利用して型検査、新仕様より楽だがオブジェクトの削除->生成が毎回行われるために旧仕様より遅いのかも
-ishlink.lmn
i(10000, 800).
init @@ i(I, J) :- uniq, int(I), new($x) | i(I, J, I), a($x).
return @@ i(0, J, M) :- J > 0, J1 = J-1, int(M) | i(M, J1, M).
hlink @@ i(I, J, M), a($x) :- I > 0, I1 = I-1, hlink($x) | i(I1, J, M), a($x).
**2010-12-07 [#z99bc25e]
***リモート設定メモ [#i12ffcaa]
-コンピュータ：localhost:13389
-プロトコル：RDPv5
-ユーザ名とパスワード
-(マシンアドレス：00:22:15:7d:86:dc)
**2010-12-06 [#a0d82910]
***LMN_ATTR_IS_DATA_WITHOUT_EX [#m93aef1f]
-exはextended。extra, expandedでもまぁ意味は通じる？
**2010-12-03 [#kfa39533]
***ハイパーリンク属性 [#l2921ed1]
-ハイパーリンクはファンクタ!/1のアトム
--だけど属性としてはデータアトムの一種
--だけどシンボルアトムとして、膜への登録、削除等々を行う
---callback atomと同じような
---メリットとしては型検査を最適化できる
---デメリットとしては実装が面倒
**2010-11-26 [#ke0483e5]
***hyperlink : アトムポインタをIDとする [#m5f5ba11]
-これまでのハイパーリンクアトム
--ファンクタ：!1, !2, ...(実行中に新たなファンクタを生成していた)
--管理(hlink ID)： 1, 2, ...
--- !1 <-> 1, !2 <-> 2, ...
--通常の（シンボル）アトム
-新しいハイパーリンクアトム
--ファンクタ：予約語'!'で統一 (新たなファンクタ生成は無い)
--管理(hlink ID)：'!'アトムのポインタ
--- atom pointer <-> hlink object, ...
--データアトム扱い（hyperlink属性を追加、hlinkである/ないの判定が楽に）
tmp.
tmp :- new($x) | a($x).
*--->
a(!). (出力は a(!0x1ab5038)か, 適当な値を付けてa(!1)とか)
-INSTR_COPYATOM
--これまでは同じIDを持つhlinkは複数個生成可能
---ポインタにするとIDはユニーク
--複製したらオリジナルと併合する
tmp.
tmp :- new($x) | a($x), b($x).
*--->
a(!0x1ab5038). b(!0x1ab5068). @5.
== HyperLink =============================================
[hl_ID] [parent] [elem] [rank (direct child)]
Name ----------------------------------------------------
0x1ab5038 root --- 1(0x1ab5068)
0x1ab5068 0x1ab5038 --- 0
==========================================================
**2010-11-24 [#ef1cfe00]
***戸川先生のディジタル回路設計(ごてふより) [#v1c49927]
-回路の設計 × ハイパーリンク
--落ち着いたら調べてみる
***hyperlink : 仕様変更 [#g71546e0]
-インクリメンタルなIDで管理するより、アトムのポインタでハイパーリンクを管理する方が何かと都合が良いため
**2010-11-23 [#wf54aa25]
***boolean.lmnのコンパイル [#b488c708]
-修正版を一昨日コミットしたが、どうやらちゃんと動いているみたい
-俺がよく見ていたboolean.lmnのコンパイルエラーは、単にノーパソで間違ったパスをLMNTAL_HOMEに指定していたから出てきていたものだった、迂闊なんてレベルじゃない
**2010-11-22 [#p68a4296]
***デフォルトセッションの変更 [#xad3b9a7]
- netbook editionを入れると、ログイン時にdesktop版も選択できるけど、デフォルトセッションを変更したければ、システム管理→ログイン画面の設定
***日本語入力が出来ない [#y5cc350c]
-システム→設定→キーボード・インプットメソッドからAuthyを追加
**2010-11-20 [#af04f1ac]
*** Xp - ubuntuデュアルブート関連 [#y14fdd3c]
-wubiでインストール失敗
--permission denied となってlogを参照するように言われる
--isoファイルのダウンロードで終了していたら、[[ここ:http://www.ubuntulinux.jp/News/ubuntu1004-desktop-ja-remix-20100512]]からisoをダウンロード
--Deamon tools liteでisoをマウントして一旦ubuntuをアンインストール
--再びisoからインストール開始
-既定の起動OSを変更する
--Xp -> コンパネ -> システム -> 詳細設定 -> 起動と回復 から変更
*** boolean.lmnがコンパイルできなかったバグ [#cc5791de]
-俺でした...修正版をコミットしましたが、チェックできてないのでちゃんと直ってるかどうか
**2010-11-19 [#le08f0fe]
***ubuntuでSLIMが動かなくなった件解決 [#i6e01716]
-iwatasoが解決法をなんとか思い出してくれたおかげで復活！
-make install で /usr/local/share/に出来るslimが悪かった？
--''slimという名前を変更すれば''正常に動くようになった
--原因は何なんだろう？
***Windows XP:余計なスタートアッププログラムを解除 [#d168e7a2]
-[[参考:http://www.atmarkit.co.jp/fwin2k/win2ktips/180disabl_autorun/disabl_autorun.html]]
**2010-11-18 [#b7bc1261]
***ubuntuでSLIMが急に動かなくなった件 [#xd1399bd]
-以下を色々試した
***wubi [#bc3ba012]
-追加でubuntuをインストールすることは出来なそう、アンインストールが必要と言われる
***もう一台のPCにubuntuをインストールして比較してみた [#ya73af4a]
-configureの内容を互いに比較してみた
--mawkとgawkというソフトの違いがあり、その辺をそろえてみたけど結局変わらず
***ubuntu : eclipse install memo [#x5161a1c]
-eclipse
--配布元からバイナリインストール
-SVN
--Subversive SVN Connectors Site - http://community.polarion.com/projects/subversive/download/eclipse/2.0/update-site/
---Subversive SVN Connectors
---Subversive SVN Team Provider (Incubation)
---SVNKit 1.3.x Implementation (Optional)
-SLIM compile
--flexのインストールだけは気づきにくい
**2010-11-17 [#s18bab59]
***kernelの再構築 [#sd2a64f9]
$ sudo -s
/*** カーネル再構築に必要なパッケージをインストール ***/
# apt-get install build-essential
# apt-get install kernel-package libncurses5-dev libqt3-mt-dev
/*** カーネルソースをインストールして展開 ***/
# apt-get install linux-source-2.6.28
# cd /usr/src
# tar xvjf linux-source-2.6.28.tar.bz2
/*** .config ファイルの作成 ***/
# cd linux-source-2.6.28
# cp /boot/config-2.6.28-xx-generic .config
# make oldconfig
/*** CPU関連のパラメータを環境に合わせて修正 ***/
# make menuconfig
例えば...
Processor type and features >
Processor family => Core 2/newer Xeon
Timer frequency => 1000 HZ
/*** カーネルのリビルド ***/
# make-kpkg clean
# make-kpkg --initrd --revision=20090618 kernel_image kernel_headers
/*** .deb ができるので dpkg でインストール ***/
# cd ..
# dpkg -i linux-image-2.6.28.xx_20090618_x86.deb
**2010-11-17 [#h7e9af0d]
-memo
--lmntal.cupにごみが入っていたのを修正、そのうちコミット
**2010-11-09 [#sf2cb5ab]
-中間発表メモ
--IDの使用数を測ってみる
--グラフだけでなく、例題の内容、同実装したか、結果の考察は必要
--インクリメンタルなIDではなく、アドレスをIDに
---でも結局ファンクタのID数は決まっているのでよく考えたほうがよさそう
-アンビエントを書いてみたい
--ラムダ計算も
-今後の方向性、非決定実行の評価
**2010-11-03 [#w26aafeb]
-ハイパーリンクへの値の束縛の必要性？
--集合が持つ値をn(!1, 1).とかで表すと、例えば
a($x), n($x,N1), b($y), n($y,N2) :- N=N1+N2 |...
--のように値を足すルールで、N1,N2が同じ値である場合があるなら、その分nの個数を増やさなければならない、書くのがちょっと面倒かな
**2010-10-29 その2 [#y53bee55]
***fibonacciのオーダーが悪かった原因（残りの半分） [#a9a3e3d0]
--addにて'+'からfindatomしていたのが原因、値を持っているvからfindatomすれば適用失敗がかなり抑えられる
unify @@ fib($n, N1, M1) \ fib2($n, N2, M2) :- hlink(M1), int(N2) | M1 >< M2.
fib1 @@ fib2(N,0,M) :- hlink(N) | v(M, 1).
fib2 @@ fib(N,1,M) :- hlink(N) | v(M, 1).
fib3 @@
fib($n, N, M) :-
N > 1, N1 = N-1, N2 = N-2,
make(N, $a), make(N1, $b), new($x), new($y), hlink($n) |
fib($a, N1, $x), fib2($b, N2, $y), M = $x + $y.
add @@ v($x, X), v($y, Y), H = $x + $y :- Z = X+Y | v(H, Z) ,v($x, X).
|N番目 |5000 |8000 |10000|16000|20000|32000|O |h
|slim hlink opt| 0.08| 0.14| 0.18| 0.28| 0.37| 0.56| |
|chr int opt | 0.03| 0.04| 0.08| 0.10| 0.17| 0.25| |
***fibonacciのオーダーが悪かった原因（半分） [#t806dd09]
-unifyするより前にfib3が適用されてしまい、余計な手間がかかっていた
-併合する側fibと併合される側fib2に分けることで、unify>fib3、という優先度で実行できる
--だいぶ早くなったが、これでも計算量はN^2〜3、まだもう一段階原因があるのか
unify @@ fib($n, N1, M1) \ fib2($n, N2, M2) :-
hlink(M1), int(N2) | M1 >< M2.
fib1 @@ fib2(N,0,M) :- hlink(N) | v(M, 1).
fib2 @@ fib(N,1,M) :- hlink(N) | v(M, 1).
fib3 @@
fib($n, N, M) :- /* hlinkidとN,N1は1ずつずらしている */
N > 1, N1 = N-1, N2 = N-2,
make(N, $a), make(N1, $b), new($x), new($y), hlink($n) |
fib($a, N1, $x), fib2($b, N2, $y), M = $x + $y.
add @@
H = $x + $y, v($x, X), v($y, Y) :- Z = X+Y | v(H, Z), v($x, X), v($y, Y).
|N番目 |1000 |2000 |4000 |8000 |16000|O |h
|slim int hlink| 0.28| 1.18| 7.23|38.30| | |
--memo
16000 :
8000 : 23999
4000 : 11999
2000 : 5999
1000 : 2999
**2010-10-29 [#uca7298f]
-班ゼミメモ
--CHRで書くことに意味のある例題を選ぶ
--fibonacci, leqの解析
**2010-10-28 [#d7658fd6]
-grub : ×グルーブ、○グラブまたはジーラブ
**2010-10-27 [#r4503471]
***fibonacci [#lbef4d44]
-注)フィボナッチ数は、下記のbottomup, topdownのようなやり方をしなくても、リストを使えば数万番目くらいまでは一瞬で求めることができる
fib(N,[X,Y|L]) :- N > 0, N1 = N-1, Z = X+Y |
fib(N1,[Z,X,Y|L]).
--あくまで性能測定のための例題ということで...
***fibonacci (bottomup) [#x3bf3139]
-hyperlinkを使う意味はあまり無いが、下のtopdownとの比較のために測ってみた
|N番目 |100 |200 |400 |800 |O |h
|slim int |0.14|0.92 |6.92 |52.85| |
|slim hlink opt| | | | | |
|chr int opt |0.05|0.19 |0.72 |2.87 | |
***fibonacci (topdown) [#x621ef5b]
-論理変数を効果的に使っている例題
fibonacci(N,M1) # ID \ fibonacci(N,M2) <=> M1 = M2 pragma passive(ID).
|N番目 |10 |15 |20 |25 ||100 |200 |400 ||10000|20000|O |h
|slim int | 0.01| 0.03| 2.00|241.64|| | | || | | |
|slim mem | 0.04|38.70| over| || | | || | | |
|slim hlink opt| | | | ||0.51|12.34|267.82|| | | |
|chr int | | | | || | | ||20.64| | |
|chr int opt | | | | || | | 0.00|| 0.08| 0.15| |
--膜による擬似論理変数を使っても、結局同じ値を持つ集合を併合する操作のオーダが悪いために時間がかかっている
--hyperlinkも変数が持つ値同士を加算するルールが余分にある分chr-optよりオーダーが悪い
--91番目7540113804746346429以降はslimでは正しく出力されない
&ref(fib.png);
**2010-10-25 [#kf170c6a]
***ram_simulator [#w712d1ce]
-memory num = 10, program_counter = N
prog(L,L1,add(B),A), mem(B,Y) \ mem(A,X), prog_counter(L) <=>
Z is X+Y, mem(A,Z), prog_counter(L1).
|N |5k |10k |20k |40k |O |h
|slim int |0.17|0.33|0.64|1.27| |
|slim hlink | | | | | |
|slim hlink opt| | | | | |
|chr int | | | | | |
|chr int opt |0.23|0.51|1.33|3.76| |
-memory num = 30, program_counter = N
|N |5k |10k |20k |40k |O |h
|slim int |1.59|3.16|6.33|12.65| |
|slim hlink | | | | | |
|slim hlink opt|0.15|0.28|0.55| 1.10| |
|chr int |1.54|2.99|5.96|12.35| |
|chr int opt |0.21|0.51|1.26| 3.61| |
--(chrのオーダーが悪いのは、同じ値を持つ変数が多いために、dense_intが逆効果になっているからだろうか？)
**2010-10-24 [#z219609f]
***union-find [#o9f60cff]
-
|N |100 |200 |400 |800 |160O |3200 |O |h
|slim int |0.03|0.13|0.71|4.89|36.52|290.04|N^3|
|slim hlink | | | | | | | |
|slim hlink opt|0.03|0.11|0.41|1.54| 6.27| 24.95|N^2|
|chr int | | | | | | | |
|chr int opt |0.02|0.05|0.15|0.55| 2.18| 9.29|N^2|
***union-find opt [#s385f1ac]
-pass compression for find, union-by-rank
|N |100 |200 |400 |800 |160O |3200 |O |h
|slim int |0.03|0.41|3.26|25.87|206.28| |N^3|
|slim hlink | | | | | | | |
|slim hlink opt|0.03|0.05|0.21| 0.73| 3.12|11.58|N^2|
|chr int | | | | | | | |
|chr int opt |0.02|0.05|0.17| 0.64| 2.51| 9.99|N^2|
-slim内部に実装したunion-find
|N |8000|16k |32k |64k |O |h
|slim hyperlink|0.01|0.02|0.04|0.08|N |
***cycle [#w712d1ce]
-3頂点からなる閉路を探索する(propagation, uniq無し)
edge(X, Y), edge(Y, Z), edge(Z, X) <=> cycle(X, Y, Z).
|N |8k |16k |32k |64k |O |h
|slim int | | | | | |
|slim hlink | | | | | |
|slim hlink opt|0.33|0.67|1.34| 2.69| |
|chr int | | | | | |
|chr int opt |1.25|2.54|5.05|10.18| |
***lexicographic [#w712d1ce]
-辞書順比較(5〜10の長さのリストをN回比較)
l4 @ lex([X|L1],[Y|L2]) <=> X==Y | lex(L1,L2).
|N |2500| 5000|10k |20k |O |h
|slim int |0.18| 0.75|3.17|20.58| |
|slim hlink |2.53|13.88| | | |
|slim hlink opt|0.45| 2.00|8.82|46.85| |
|chr int |0.65| 1.25|2.58| 5.13| |
|chr int opt |0.03| 0.06|0.12| 0.23| |
--findatomではなくderefでhyperlinkに到達するようなルールの最適化は考慮していないため、オーダーが悪い
--そもそもhlinkを使うメリットはあまりない
**2010-10-22 [#v1492a89]
***leq [#q67e9865]
-クエリ：leq(1,2), leq(2,3), ... leq(N, 1).
reflexivity @ leq(X,X) <=> true.
antisymmetry @ leq(X,Y), leq(Y,X) <=> X = Y.
idempotence @ leq(X,Y) \ leq(X,Y) <=> true.
transitivity @ leq(X,Y), leq(Y,Z) ==> leq(X,Z).
|N |20 |40 |60 |80 |O |h
|slim int |0.32|16.06|929.34| | |
|slim hlink ||||||
|slim hlink opt|0.03|0.79|6.42|28.79| |
|chr int ||||||
|chr int opt |0.06|0.29|1.31| 5.45| |
--uniqはpropagationより時間がかかるため、こういう結果
//***変数への値の束縛が欲しい例題 [#q6bbc099]
//-fib_topdown.pl
//--トップダウンでフィボナッチ数を求める
// fib(N,M) ==> N > 1 | N1 is N-1, fib(N1,M1), N2 is N-2, fib(N2,M2), M is M1 + M2.
**2010-10-22 [#z1d8f4ce]
***CHR bencnmark [#af25fb11]
-また見失わない様にメモ
--[[本家？:http://people.cs.kuleuven.be/~tom.schrijvers/CHR/]]
--[[indexing用:http://people.cs.kuleuven.be/~tom.schrijvers/CHR/Indexing/]]
**2010-10-21 [#h4690d57]
***整数比較改めアトム比較の再々試 [#n3b8367e]
-条件をより同じにして再々試
- slimhl395/101109/vartest.lmn
- lmntal -O3 --slimcode --hl-opt atomcmp.lmn | slim --hl -
|N |8k |16k |32k |64k |O |h
|slim int |0.64| 2.52| 10.08| 41.87|N^2|
|slim hlink |4.49|27.58|120.20|607.76|N^2|
|slim hlink opt|0.02| 0.03| 0.06| 0.12|N |
|chr int |3.41|15.50| 70.15|288.34|N^2|
|chr int opt |0.06| 0.15| 0.28| 0.59|N |
***コンパイラをコミット [#j3d6c504]
-hyperlinkをjava版コンパイラにコミットした
***hyperlinkの出力 [#ie20402f]
-併合されたhyperlinkを標準出力時にrootのファンクタで出力するようにした
**2010-10-20 [#h4690d57]
***hyperlinkからのfindatom 改良版 [#v88402db]
-併合した異なる名前のhyperlink同士も比較できるように
-複数引数がある場合のバグを修正
leq($x, $y), leq($y, $x).
-同一アトム内で分離が起こっている場合に対応
leq($x, $x)
-その他、いろいろ最適化
&br;
-整数比較を追試
|N|10k|20k|40k|h
|hlink(追試)|15.87|78.59||
|hlink opt(前回の)|0.02|0.04|0.09|
|hlink opt(今回の)|0.03|0.05|0.10|
|chr opt|0.08|0.20|0.39|
--探索にかかる操作や条件分岐が増えて遅くなるはずだったが、その分最適化もしたので、大きくスピードが落ちることはなかった
**2010-10-12 その3 [#wba7e196]
***leq.pl(CHR)をhyperlinkで書いてみる [#ed77cb0f]
-leq.pl
ref @ leq(X,X) <=> true.
ant @ leq(X,Y), leq(Y,X) <=> X = Y.
ide @ leq(X,Y) \ leq(X,Y) <=> true.
tra @ leq(X,Y), leq(Y,Z) ==> leq(X,Z).
-leq_hl.lmn
ref @@ leq($x, $x) :- .
ant @@ leq($x, $y), leq($y, $x) :- hlink($x), $x \= $y | $x >< $y.
ide @@ leq($x, $y), leq($x, $y) :- leq($x, $y).
tra @@ leq($x, $y), leq($y, $z) :-
uniq($x, $z) | leq($x, $y), leq($y, $z), leq($x, $z).
-SLIMでの実行結果
leq('!1', '!2'), leq('!2', '!1'), a('!1'), b('!2').
*--ant@@-->
'!1'(a). '!2'(b). @5
== HyperLink ===============================================
[func] [parent] [elem] [rank (direct child)]
Name ----------------------------------------------------
!1 !1 2 1 (2)
!2 !1 --- 0
============================================================
--a, bは変数名に相当、表から!1と!2が同じ集合に属していることが分かる
**2010-10-12 その2 [#a70e8b7b]
***hyperlinkの使い方ページを少し整備 [#x424455c]
-[[hyperlink仕様まとめ]]
***hyperlink SLIM側をbranchにコミット [#w45de2da]
-使い方は[[ここ>hyperlink仕様まとめ#pf1ceb9f]]
**2010-10-12 [#mfa8bf06]
***subversionでエラー [#z1f59234]
-Let'sNoteの方からコミットしようとしたら、エラーが出て出来なかった。
--眠いから明日調べる
commit -m "hyperlink branch (α-version)..." (19 paths specified)
Failed to execute WebDAV PROPPATCH
svn: Commit failed (details follow):
svn: At least one property change failed; repository is unchanged
RA layer request failed
svn: Error setting property 'log':
Could not execute PROPPATCH.
**2010-10-10 [#hc2310bd]
*** hyperlink compiler側をコミット [#wb13cfbb]
-devel/sample/seiji/hyperlink_*.zip
--使い方は[[ここ>hyperlink仕様まとめ#pf1ceb9f]]
**2010-10-08 [#s4229dfd]
-班ゼミ
--ファンクタの数が足りなくなるのはどうしよう→とりあえず棚上げ
--コミットしなきゃ
---slimのリーク取り→コンパイラのコミット→slimのコミットの順にやるか
-hyperlink branch
--"branches"を右クリ、フォルダ新規生成
--"trunk"内の"slim"をコピー、"branch"内の"新規生成したフォルダ"を右クリ、貼り付け
**2010-10-07 [#h7a7d450]
***hyperlinkを利用したfindatomの最適化 [#ya5f947d]
-動くようになったので、一旦測ってみた
--unaryアトム比較
---hlink opt : 今回の実装
|N|10k|20k|40k|80k|h
|hlink|10.10||||
|hlink opt|0.09|0.17|0.36|※|
|chr opt|0.08|0.20|0.39|0.80|
---(※hyperlinkの数が足りない)
---微妙に勝ってる？いやどっこいどっこいか
---もっとちゃんと実装すれば、もう少し早くできる気がする
---追試：ガードにhlink(unaryでも可)チェックを入れた場合
|N|10k|20k|40k|80k|h
|hlink opt|0.02|0.04|0.09|※|
|chr opt|0.08|0.20|0.39|0.80|
---かなり早い
-TODO:膜を貫くリンクに接続している場合のhyperlinkアトムの処理の整備
**2010-10-04 [#e5d85fd2]
*** findproccxt[#k42188cb]
-特定のアトム引数(型付きプロセス文脈)同士が同じ構造を持つことを示す中間命令
--生成時は適当に挿入、最後にcompile/Optimizer.javaにてfindatomよりも前に並び替えてる
a($x), a($x) :- ok.
-------------------------------------------------
--memmatch:
spec [1, 3]
findproccxt [1, 0, 2, 0]
findatom [1, 0, 'a'_1]
findatom [2, 0, 'a'_1]
neqatom [2, 1]
jump [L118, [0], [1, 2], []]
-ソースコード中に書いた説明書き
/** findproccxt [atom1, length1, arg1, atom2, length2, arg2]
* アトム番号atom1(価数=lenght1)の第arg1引数の型付きプロセス文脈が、
* アトム番号atom2(価数=lenght2)の第arg2引数の型付きプロセス文脈と同名であることを示す
* 必ず(atom1,arg1)がオリジナル、(atom2,arg2)が新たに生成された名前になるよう配置されている
*/
**2010-09-29 [#fb32f670]
***同名型付きプロセス文脈の分離 [#r3fa6a93]
- --hl系オプションでのみ使用できるように変更 (2010-10-10)
-- さらに--hl-optオプションを付けることで、ガードに自動的にhlink型チェックを挿入し、ground対groundの構造比較をファンクタ対ファンクタで済ますようしている
-ヘッドに膜がある場合の操作が抜けていたので修正（2010-09-30)
&br;
-これまでは一つのルール内で同名の型付きプロセス文脈は記述できなかったが、以下の様に変更した
a($p), a($p) :- ... → a($p), a($p0) :- $p = $p0 | ...
--シンタックスシュガー的なもの
---コンパイル時に自動的に右側に変換してくれる
--元の名前の後ろに数字をつけて新しい名前にしている
--もちろん、以下の場合も考慮してある
a($p), a($p), a($p0) :- ... → a($p), a($p1), a($p0) :- $p = $p1 | ...
**2010-09-25 [#w78abbbb]
***hlinkのコピーと削除 [#c9840d33]
-アトム(hlinkアトム)を10000*N回ずつコピー＆削除する
--atom : a(b)
--hlink : a('!1')
|N|100|200|400|800|O|h
|atom|1.193|2.337|4.640|9.240|O(N)|
|hlink|1.757|3.477|6.947|13.803|O(N)|
---オーダーは変わらない
---hlinkアトムの生成・削除には要素数の増減処理が伴うため若干時間がかかる
---他にも原因があるかな？
-copy_and_delete.lmn
{
i(10000, 800). a(b).
//new @@ i(I, M), a($x) :- I > 0, I1 = I-1, unary($x) | i(I1, M), a($x), a($x).
//del @@ a($x), a($y) :- unary($x), unary($y) | a($x).
hlinit @@ a(b) :- new($x) | a($x).
newhl @@ i(I, M), a($x) :- I > 0, I1 = I-1, hlink($x) | i(I1, M), a($x), a($x).
delhl @@ a($x), a($y) :- hlink($x), hlink($y) | a($x).
}.
{i(0, I), $p, @p}/ :- I > 0, I1 = I-1 | {i(10000, I1), $p, @p}.
**2010-09-24 [#d3c955b0]
***集合の要素を数えるのにかかる時間 [#ra4a62a3]
-(10000個の要素を持つ)集合の要素数をN回数えた時間を計測[sec]
--mem:膜を一つの集合、内部のアトムを集合に属する要素とみなす
--hlink:hyperlinkによって集合を表す
|N|1000|2000|4000|8000|16000|32000|64000|h
|mem|3.84|7.74|15.51|31.11||||
|hlink|0.003|0.01|0.02|0.03|0.05|0.10|0.21|
---hlinkは自身につながる要素数を常に保持しているので、まぁ当然の結果
-num_mem.lmn
{
i(10000). num(0).
i(I) :- I > 0, I1 = I-1 | i(I1), a(I).
}.
a2b{i(1000). num(N), a(X) :- N1 = N+1 | num(N1), b(X).}.
b2a{i(1000). num(N), b(X) :- N1 = N+1 | num(N1), a(X).}.
{i(0), $p, @p}/, a2b{i(I), @q} :- I1 = I-1 |
count{$p, @q}, a2b{i(I1)}, '$callback'(gettime, start).
count{num(N), $p, @p}/, a2b{$q}, b2a{i(I), @r} :- int(N), I > 0, I1 = I-1 |
count{num(0), $p, @r}, a2b{$q, @p}, b2a{i(I1)}.
count{num(N), $p, @p}/, b2a{$q}, a2b{i(I), @r} :- int(N), I > 0, I1 = I-1 |
count{num(0), $p, @r}, b2a{$q, @p}, a2b{i(I1)}.
a2b{i(0), @p}, b2a{i(0)} :- '$callback'(gettime, end).
end(E), start(S) :- R = E-.S | time(R).
-num_hl.lmn
{
i(10000).
i(I) :- I > 0, I1 = I-1, new($h) | i(I1), e($h), a($h).
e($x), e($y) :- $x \= $y | e($x), $x >< $y.
}.
i(10000).
{i(0), e($h), $p, @p}/ :- hlink($h) | count{$p}, '$callback'(gettime, start).
count{a($x), $p}, i(I) :- I > 0, I1 = I-1, $n = num($x) |
count{a($x), $p}, i(I1), num($n).
i(0) :- '$callback'(gettime, end).
end(E), start(S) :- R = E-.S | time(R).
end(E), start(S) :- R = E-.S | time(R).
***--showhl [#b13024de]
-hyperlink詳細出力用オプションをこっそり追加
--出力フォーマットも一新
***その他 [#g50b1ada]
-conameは現状では要素数に含めるようにしている
-hyperlinkと9/14の変更をローカルのslimにマージ
**2010-09-22 [#s0e16d8d]
-集合内の「要素数」の定義
--!1〜!5までのname(各1個)からなる集合に、coname !-1を与えたとき、この集合の要素数はどうなるんだろうか
---5個なのか5+1個なのか
--conameは要素として数えるべきかどうか、ちょっと考えた方がいいかも
-memo
--add
---alloc.c/lmn_new_atom(lmn_copy_satomなども含)
--sub
---alloc.c/lmn_delete_atom
**2010-09-18 [#y9606ad3]
- 9/14の変更をコミットした
--状態数も正常みたいだし、多分大丈夫だろう
**2010-09-17 [#x11b74df]
*** --showrule [#jcbd8492]
-ruleset idの後ろに、ruleの中身を続けて出力するオプションを忍び込ませた
--一度も反応しなかったルールは何も表示されない(何らかのruleがあるということは分かる)
--StateViewerでもオプション指定すれば使える
a(b(c)), a(d(e)).
rule @@ a(X) :- uniq(X) | ok(X).
ok(X) :- uniq(X) | .
aaaa :- bbbb.
--->
@5/[rule"b(c,a):""d(e,a):"][_okXu"b(c,ok):""d(e,ok):"][]
**2010-09-14 [#mf063b27]
***久しぶりにuniq [#l004cd49]
-膜のダンプでrulesetsのポインタではなく、ruleが持つ履歴の内容を全て突っ込む方式に変更
--したつもり。チェックは明日以降。
**2010-09-10 [#w2567dde]
-hyperlink等価性判定のバグを修正
--「conameを持つname」と「coname」との比較など
--memo : hyperlink等価判定に関わる命令列
---samefunc
---eq/neqfunc
---eq/neqground
**2010-09-06 [#fa7c5130]
-よくよく考えたら、rankはnameの子数であって、要素数とは違う
--任意の集合に属するhyperlinkの本数(非hyperlinkアトムへの接続箇所)を数えられるようにした
-予約語用のファンクタが20個くらいあるので、使用できるhlink idは65536個より若干少ない
**2010-08-31 [#n98c31a5]
-TODO：reverseを一時コメントアウトしておく
**2010-08-30 [#jd35234c]
-lmn_eq_funcにLMN_FUNCTOR_ATTRの場合分けを追加
--他にも場合分け追加しなきゃいけない所がたくさんある
-初期化関数で全て初期化してしまっていたのを最適化した
**2010-08-20 [#a1f6e011]
-coname-coname, name-coname間の併合処理を実装
--比較演算の修正はまだ
-そろそろhyperlink手動のfindatomと、parserを変更して同じプロセス文脈名が3回以上出現を許す、辺りの検討を
**2010-08-19 [#y5736fa4]
-coname管理方法を変更
-st_get_entry関数を若干修正
--レコードではなくキーを取得するようになっていた
**2010-08-18 [#o4b1ca55]
-細かな所でバグが...
--ランクの再計算を修正
--conameの管理方法の変更を検討中、配列よりハッシュ表の方がいいかも
**2010-08-13 [#r252930e]
-反転処理：リンクの繋ぎ換えでおかしかったところを修正
**2010-08-12 [#c3c1532a]
***LMN_FUNCTOR_ATTRと型検査の兼ね合い [#b26e6a05]
-newとintなどを組み合わせるとおかしくなる
-そのうちやる
**2010-08-10 [#w559c845]
-リファクタリング
**2010-08-06 [#xcef2f39]
***要素数の取得 [#zcd1698d]
-任意のhlinkが所属する集合の要素を取得する
a($h) :- $n = num($h) | n($n).
***new制約 [#d5b8b5e8]
-0入力制約関連のバグを自己解決
***name-conameの反転 [#m15217fe]
-"-"をつけることでボディで反転できるように
--nameからconameへの反転は、conameを持つ場合のみ可能
a(!1). a($h) :- name($h) | a(-$h).
---> a(!-1).
**2010-08-05 [#xcef2f39]
***hyperlink生成 [#d5b8b5e8]
-ガードではシンボルアトムを生成しないというSLIMの作りに則っていたが、それだと次のようなガードが書けない
... :- new(X), Y = setconame(X) | ...
--ガードでアトム生成できるようにするなり、ちょっと見直しが必要
**2010-08-03 [#qb678b4b]
***ボディで併合できるようにした [#za11a7d0]
-演算子："><"
--name-name, coname-coname用
--bow tieっぽく見える
a($x), b($y) :- $x \= $y | a($x), b($y), $x >< $y.
---name-coname用には">>","<<"あるいは"<-","->"かな
**2010-07-30 [#t7e56c54]
***論理変数の状態 [#sc17ebec]
-値や属性を持たない
--これを初期状態とし、下のどちらかの状態に移行可能
+値や属性を持つ
+他の変数と併合される
--値や属性の代わりに相手変数への参照を持つ
***Attribute variable [#p1d13d13]
-属性の実装はどうやっているのか、ちょっと調べてみる
**2010-07-29 [#x9501758]
***conameのunify [#t8c987ce]
-異なる値を持つ変数同士の併合は失敗
-conameのみで存在することは無い、とするとconameの生成はnameありきの構文にしたほうがいいのか
**2010-07-23 [#x9501758]
***hyperlink [#t8c987ce]
-name<->name関連機能は大体実装した...か？
--木で集合を管理
--rankやパス圧縮を用いて多少は効率良いようにしてみた
-次はco-name<->name関連をぼちぼちと
***co-name [#c06c9830]
-必要そうな操作と、構文妄想
--co-nameの生成
---co-nameを生成する=対応するnameがすでに生成されているはず？
+++(name型である&&co-nameを持たない)=>co-name生成？
+++name型である=>co-name生成=>(co-name2つ以上持つ=>co-nameの併合)？
--nameがco-nameを持つかどうかの検査
--- a($h) :- hasconame($h) | ...
--- $hがname(hlink)である=>$hがco-nameを持つかどうか
--nameからco-nameを呼び出す
--- a($h) :- getconame($h) | ...
--- $hがname(hlink)である=>$hがco-nameを持つ=>$hにco-nameを結びつける
--co-name型検査
--- a($h) :- coname($h) | ...
--name->co-nameの併合 (=co-nameの無いnameにco-nameを結びつける)
--- a($x), b($y') :- $h = $x >> $y' | a($h), b($h). ('付きはco-name)
***co-nameの属性を扱う構文 [#obdc1c82]
- (!-1 > 3), (!-2 < 5)というco-name!-1,!-2を併合する
--andとorの区別をつけられるようにする必要はあるか？
&br;
-memo
--before
1: func !1 200, parent 1, rank 7
children >> 2 3 5
2: func !2 202, parent 1, rank 0
3: func !3 204, parent 1, rank 1
children >> 4
4: func !4 23, parent 3, rank 0
5: func !5 207, parent 1, rank 3
children >> 6 7
6: func !6 209, parent 5, rank 0
7: func !7 211, parent 5, rank 1
children >> 8
8: func !8 25, parent 7, rank 0
9: func !9 214, parent 9, rank 1
children >> 10
10: func !10 216, parent 9, rank 0
--after 4,8からrootを探索
1: func !1 200, parent 1, rank 7
children >> 2 3 4 5 7 8
2: func !2 202, parent 1, rank 0
3: func !3 204, parent 1, rank 0
4: func !4 23, parent 1, rank 0
5: func !5 207, parent 1, rank 2
children >> 6
6: func !6 209, parent 5, rank 0
7: func !7 211, parent 1, rank 0
8: func !8 25, parent 1, rank 0
9: func !9 214, parent 9, rank 1
children >> 10
10: func !10 216, parent 9, rank 0
**2010-07-16 [#x9501758]
***[[hyperlink仕様まとめ]] [#udc2bbbf]
**2010-07-15 [#x9501758]
-班ゼミ用現状メモ
-hlink用演算子が決まらない
***name, coname [#q04d9db5]
-名前の決め方
--name : "!" + 0,1,2,...
--coname : "!!" + (nameから求めたファンクタid)
-実装方法案
--どちらも基本的に今までのファンクタ
---属性付き変数を導入するなら、
-対応関係
--ハッシュテーブルで関係を保持（親-->子、子-->親）
-記法案
-- name-->coname取得
a($h) :- coname($h) | a(
***hlink生成 [#yce62560]
-本命：bodyで生成
--コンパイラ読み+改造中
-次善策のnew制約
hoge, hoge.
hoge :- new($h) | a($h), b($h).
*--> a('!0'), b('!0'), a('!1'), b('!1').
***併合 [#v7bef253]
-merge用演算子
a($x), b($y) :- $h = $x =$= $y | a($h), b($h).
--#なのはいかがなものか
***memo [#fd6bc3d9]
-hlinkの実装方法
--SLIMではガードでsymbolアトムを生成出来るようになっていなかった
--通常の(symbol)アトムとして名前をつけるか
--データアトムの一種とする(単なる数値)か
---Attrにhlink用の属性を新たに用意するか
**2010-07-09 [#x9501758]
*** JFlex.jarとjava_cup.jar [#b8365df3]
-java_cup.jarの方はsrc/compiler/parser/に移動して実行しないと、parser.javaが正しいディレクトリに生成されないみたい
***"=="演算子 [#m8288f9b]
-'=='をunary型同士の比較演算子にしようという話(cf.先生wiki)
--'=','\='はground、'=:=','=\='はint
--unaryのnot equalに関して(src/compile/GuardCompiler.java, l.363)
// .. :- unary(A),A\=B | ..
//の場合、Bがgroundで構わない。Aがunaryで、かつBが異なる構造の時に反応する。
//この点は、==とは違う。==の場合、そもそも同じ型でなければマッチしないため。
//Bがunaryの時に限定したければ、unary(B)を書き加えればよい。
//(何も考えずに実装したらそうなったのだが、結果的に一番柔軟で直感的な形だと思う。)
-実装変更後の中間命令列
a($x), b($y) :- $x == $y | ...
-------------------------------------------------------------
--guard:L118:
spec [3, 5]
derefatom [3, 1, 0]
isunary [3]
derefatom [4, 2, 0]
isunary [4]
samefunc [3, 4]
jump [L103, [0], [1, 2, 3, 4], []]
***hlinkのmerge [#f1b7a60c]
-併合はどういう状況で使うだろうか
--$x,$yが異なる集合に属していれば併合する、というルールは割と書きそう
-merge版と'=='/3演算子版で書いてみる
a($h1), b($h2) :- merge($h1, $h2) | a($h1), b($h2).
a($x), b($y) :- $x \= $y, $h = $x == $y | a($h), b($h).
-'=='版の方がLMNtalっぽい気はする
--ただ、'=='版だとこういうルールも書けることになる
a($x), b($y) :- $h = $x == $y | a($h), b($h).
-この場合、$x,$yが既に併合されていようが構わず併合するルールになる
-''既に同じ集合に属しているhlink同士を併合しようとした場合はどうなるのか？''
-merge制約は「既に併合されているhlink同士を引数に持つとFALSE」という、制約の様な役割を持たせるようにしてある
--%%ただ、データ構造上はグラフの書換えが起こらないのに、併合操作で余計な状態遷移が生じるのはあまりうれしくないかも%%間違い、hlinkの併合前と併合後は別の状態だから1ステップかかってもいいのか、まぁそれがmerge制約を推す決め手にはならないが
-同じ集合に属するhlink同士の併合の意味を決めて'=='にした方がいいかもしれない
**2010-07-08 [#x9501758]
***hlink型 [#f1b7a60c]
-基本的には(プログラム上は)unary型
--ファンクタの最初の3文字が"$hl"である（かつ親ファンクタへのアドレスを持つ）
---rootファンクタは親ファンクタ=自身のアドレス
---他の通常ファンクタは親ファンクタ=NULL
---あるいは単純にroot(非hlink型含)ファンクタはNULLでもいいのかも
-他の型との関係はこんな感じ？
hlink ⊂ unary ⊂ ground
hlink ≠ data(int, double, ...)
-ガード制約、一応作ってみた
hlink(X) : hlink型検査
newhl(X) : hlink atom生成、中間命令列は昨日のhlinkと一緒
hlink型だと適用しない(not_hlink検査)の役割も持つ
***併合 [#jc2fc545]
-システムルールセットで行なう方法、演算子"=="
--ルール適用のタイミングで、ユーザの思い通りにいかないことがある、却下
-ボディで行なう方法、演算子は"=="にしようかな
a($h1), b($h2) :-
hlink($h1), hlink($h2) | a($h1), b($h2), $h1==$h2.
--unify("=")のように、中間命令列を変えるか、実装が少し面倒
--加えて、分子'=='($h1,$h2)が自動的に消去される、ちょっと不自然？
---さらに問題、上のルールは無限ループする
-ガードで行なう方法、例えばmerge制約とか
a($h1), b($h2) :- merge($h1, $h2) | a($h1), b($h2).
--併合操作は、併合するファンクタの名前だけ取得できればよい
--ボディで分子を不自然に消さなくて済む上に、実装も楽
---既に併合されている集合に属するhlink同士は結合できない、とかにすれば無限ループも防げる
--ただガード制約が増え過ぎな気もする
***等価判定(naive) [#ea1cd4b3]
/* $h1, $h2どちらか一方にhlink(unary)チェックを施す */
a($h1), b($h2) :-
hlink($h1), $h1==$h2 | a($h1), b($h2).
-等価判定(optimize)は中間命令列を変更しないでSLIM側だけで可能かな？うーんよく考えないと
***hyper link for nd [#g112f39b]
-とりあえず放置したい、やるなら状態ごとにファンクタの親子関係管理をさせないといけないかな
**2010-07-07 その２[#ua4377c7]
-hlink型制約は必要かな
hlink atom生成 : newhl($h) に変更
hlink型チェック : hlink($h) とか?
--unary型チェックの中で無理やりhlinkを識別することはできる
-現在、BODYでの"="と"=="は共にeqground
--"=="をhlアトム専用にする？
... :- unary(X), unary(Y), X==Y | ...
-------------------------------------
derefatom [5, 3, 0]
isunary [5]
derefatom [4, 2, 0]
isunary [4]
samefunc [5, 4]
**2010-07-07 [#ua4377c7]
-以下、未コミット
***hyper link atom 生成[#r585d88f]
-コンパイラ側
--hlink制約
--- hyper link atom (hlアトム) : アトム名($hl + ID)を持つ1引数アトム
a($h) :- hlink($h) | b($h).
------------------------------------------
if ($h == hlアトム) {
ルール適用失敗
} else {
$hから求めたIDをもつhlアトムを生成
}
---hyperlink用中間命令
/** hyperlink [atom, mem]
* $memに所属する$atomをhyperlink atomに置き換える
*/
-SLIM側
--ゆくゆくはhlアトムをdataアトム(のspecialアトム?)にして処理を簡単にしたいところ
--ファンクタをUnionFindのように親子関係を持たせるようにした
---試しにsamefunc命令の中でhlアトムの比較だけ別の処理をさせるように変更
---親子関係を反映した等価判定ができた
a(X), b(Y) :- unary(X), unary(Y), X==Y | .
-memo
--Instruction.java
--GuardCompiler.java
**2010-07-05 [#ua4377c7]
-memo
--hylink atomはint型じゃないから==の両引数に指定しても大丈夫
**2010-07-01 その2[#ua4377c7]
***班ゼミ [#g07cbc9e]
-hylinkの生成はガードで
--一度考えて、おかしいと思ってたけど、確かに+や-をガードでしてるか
**2010-07-01 [#ua4377c7]
***hyper link [#b198ff41]
-(再掲)
++hylinkを新規生成
++2つのhylinkの等価性判定
++指定したhylinkの出現の列挙
++指定されたhylinkに繋がるアトムの(効率的)探索
++hylink同士の併合
-金曜から進んだところまで
--1、5をシステムルールセットで
-1. ハイパーリンクアトム(仮)の生成
a(hL(abc)), b(hL(1)).
<==> a('$hL62'). b('$hL236').
--%%今のところcallback関数使用%%システムルールセットにて
--62, 233はhL(N)のNをlmn_internに投げて得られる値
-5. ハイパーリンクの併合
// '$hL'(HYLINK1, HYLINK2) : HYLINK1と2が併合される
a('$hL61'). b('$hL236'), '$hL'('$hL61', '$hL236').
{b('$hL236')}.
<==> a('$hL61'). b('$hL61'), {b('$hL61')}.
--システムルールセット
---hylink_unify : $hL_2に繋がったアトムのファンクタを記憶
---hylink_unify2: 記憶したペアの併合を現在膜+子孫膜全てに対して行なう
-もろもろの記法をそろそろ決めていきたいところ
--新規生成：hLでいいのか、引数は取るか
---リンク名ならぬハイパーリンク名は代表要素でいいとする(引数を取らない)と、代表要素の無いhylink(つまり無向)は名無しのハイパーリンク(内部的には一意のidなりが付く)になる
a(hL) <==> a('$hL0') とか?
--併合：hylink同士を接続するわけだから、=が自然？
---unifylinks命令
$hL = $hL
--hylinkの比較
a($p), b($q) :- $p = $q | ...
a($p), b($p) :- ...
---上の方を採用して、マッチング最適化については内部で頑張らせる方がいいのかも
--ゆくゆくは属性付き変数を表現する(したい)
---属性の情報は階層に属するものではないと思う
---属性を表すアトムをハイパーリンクアトム(仮)に直接繋げるやり方はちょっと無理があるかな
**2010-06-28 [#ua4377c7]
-体調悪い
***ハイパーリンク [#gd97d977]
-5.全ての膜に作用するシステムルールセットを書いてみた
--hylinkのunionを表現できる
**2010-06-25 [#ua4377c7]
***ハイパーリンク [#gd97d977]
-上田先生との個別ゼミを個人的に整理してみる
--hylink(かっこいいから「ハイパー」って言いたい気もする)
-実装方法より先にどういう機能を持つのか
--(拡張)unaryアトムで表現するとしてまとめる
---アトムが目に見えない(抽象的な)形で互いに接続し合っている
---つまり、今までの様に膜で表すと
a($h), b($h) :- ... .
<==> a(H1), b(H2), h{+H1, +H2} :- ... .
-機能
++hylinkを新規生成
a(newhl), b(newhl)
--(内部的に)--> a(hyperlink0), b(hyperlink0). とか
++2つのhylinkの等価性判定
a($p), b($q) :- $p = $q | a($p), b($p). とか
++指定したhylinkの出現の列挙
++指定されたhylinkに繋がるアトムの(効率的)探索
---unary方式そのままではマッチング効率化は実現できない
---適切な索引(index)構造なんかがあるとよい
++指定されたhylink同士の併合(merge, union)
---システムルールセット的なもので併合元のアトムを併合先のアトムに書き換える
-最短の実装を考えたとき、まずどれをやるか
--1. 5.
**2010-06-24 [#ua4377c7]
***hylink、SLIM側のみでやる場合 [#sb68811e]
-実現方法がいくつかある(1-3は膜を使う)
++システムルールセット、モジュールで済ませる
a(!p) :- a(HL), {name(p), +HL}.
---!を付けるのはアトムなのかリンクなのか
++中間命令列の変換
findatom [1, 0, 'a'_1]
deref [2, 1, 0, 0]
func [2, '!p'_1]
---func命令を、膜を使った構造を探してくる命令列に変換するとか
++新中間命令
---2は現状の命令列を活用、3はhylink用の命令列としてまとめてしまう
++新データ構造の追加
---様子を見ながら
***その他 [#gb15805e]
-気が早いが、!記法を入れるなら参考に
--Flex[[これ:http://www.geocities.co.jp/SiliconValley-Oakland/3432/man/flex/flex-ja_3.html#SEC14]]と[[これ:http://guppy.eng.kagawa-u.ac.jp/2007/ProgLang/flex.html]]
LinkName [A-Z_][a-zA-Z_0-9] ==> "!"?[A-Z_][a-zA-Z_0-9]
-中間命令列眺める
-- link @@ a(X), b(X) :- c(X), d(X).
--memmatch:
spec [1, 3]
findatom [1, 0, 'a'_1]
deref [2, 1, 0, 0]
func [2, 'b'_1]
jump [L103, [0], [1, 2], []]
--hlink @@ a(X), b(Y), {+X, +Y, $p} :- c(X), d(Y), {+X, +Y, $p}.
--memmatch:
spec [1, 10]
findatom [1, 0, 'a'_1]
deref [2, 1, 0, 1]
func [2, $out_2]
deref [3, 2, 0, 0]
func [3, $in_2]
deref [5, 3, 1, 0]
func [5, '+'_1]
lockmem [4, 3, null]
norules [4]
findatom [6, 4, '+'_1]
neqatom [6, 5]
deref [7, 6, 0, 1]
func [7, $in_2]
deref [8, 7, 0, 0]
func [8, $out_2]
deref [9, 8, 1, 0]
func [9, 'b'_1]
jump [L136, [0, 4], [1, 9, 8, 2, 5, 6, 7, 3], []]
-hlink、単なる妄想
a(!P), b(!P), c(!P), !-P = 3.
--"!P"はなんか某エレキバンを思い出させる
//-- a(!P), b(!P). の中間命令
// --memmatch:
// spec [1, 3]
// findatom [1, 0, 'a'_1]
// hlderef [2, 1, 0, 0]
// func [2, 'b'_1]
// jump [L103, [0], [1, 2], []]
//
&br;
-uniq for nd
--いくつかの例を動かしてみたが、おかしなところはなさそう
--ただ他に漏れが無いか不安
&br;
-ルール文脈
--ヘッドにルール文脈2個書くとルールセット集合に2重にマッチングする事になるのか、知らなかった
{rule1 @@ a:-b.}. {rule2 @@ c:-d.}.
{@p}, {@q} :- r{@p, @q}. //2つの膜を結合
r{@p, @q} :- @p, @q.
*---> @5,@5,@6,@6,@7
**2010-06-23 [#ua4377c7]
***時間計測用callback関数 [#na5be7b1]
-&ref(timer.c);
-追加の仕方：[[SLIM callback関連 メモ]]
-中身
/* get_time function */
# include <time.h>
# include "../lmntal_ext.h"
void gettime(ReactCxt rc,
LmnMembrane *mem,
LmnAtom a0, LmnLinkAttr t0)
{
double *t = LMN_MALLOC(double);
*t = (double)clock() / CLOCKS_PER_SEC;
lmn_mem_newlink(mem,
a0, LMN_ATTR_MAKE_LINK(0), LMN_ATTR_GET_VALUE(t0),
(LmnWord)t, LMN_DBL_ATTR, 0);
lmn_mem_push_atom(mem, (LmnWord)t, LMN_DBL_ATTR);
}
void init_timer(void)
{
lmn_register_c_fun("gettime", gettime, 1);
}
-実行例(bへの加算にかかる時間のみ測る)
a(0).
a(A) :- A<500000, A1=A+1 | a(A1).
a(500000) :- b(0), '$callback'(gettime, start).
b(B) :- B<500000, B1=B+1 | b(B1).
b(500000) :- '$callback'(gettime, end).
end(X), start(Y) :- Z=X-.Y | time(Z).
**2010-06-22 [#ua4377c7]
***uniq for nd [#l9939c62]
-膜のダンプ(--nd)に対応した、気がする
--膜が持つルールセット配列をバイナリストリングに書き込んでいる
--- membrane.hにゴミが入ってるよ!(gocho)
atomlist_gelmn_mem_get_rulesett_record
--- 本当に、申し(略)
--mem-encに対応させるなら履歴表の中身を全部書き込まないといけないかも
-発表資料
--概要のあとに発表の流れを置くのも中々いいかも
**2010-06-21 [#ua4377c7]
-臨時班ゼミ
--hyper link、flatLMNtalを対象にする方向で
**2010-06-20 [#ia80b02d]
-callback関数開発メモ
--rev349_2をテスト用に
**2010-06-16 [#ia80b02d]
-SWI-Prologメモ
-L0 : local stack no limit
-G0 : global stack ...
-循環グラフを生成して一周辿る、もうちょっと細かく
|N|1000|2000|4000|5000|6000|7000|8000|h
|atom|0.02|0.02|0.05||||0.08|
|mem|0.06|0.14|0.47|0.92|1.65|2.84|4.89|
**2010-06-15 [#ia80b02d]
***ゼミ発表終了 [#o678b52e]
-ありがとうございました。
-膜をhlinkとすると、どこかの階層に属さなければならないのでは
--どこの階層にも属さない、かつ自由に参照できるような何かがあるといい
--ホントはint型とかもどこかに属していることは望ましくない
-"-"の無いハイパーリンクはあんまいらないんじゃ?
--ノード番号があるグラフは本質的にうれしくない
--抽象化のためにはいいかもしれない
-最適化、という側面からならもっと処理系内部をいじったほうが効果出る
--ハイパーリンクやる意義をもうちょっと広く深く考えなければ
**2010-06-11 [#y0d8265f]
***昨日の班ゼミメモ [#gdbd6f02]
-多対多、という表現はなんかおかしい
-+の方をデフォルトにして文字数減らすとか
-階層無視で作用するルールが無い
-ルートからのプロキシアトムのツリーを作るとか
-集合演算の機能があんまりない、膜内のアトム数が分かるとか
**2010-06-10[#q8663905]
***hyperlink : 妄想 [#z4cb9acd]
-同じリンク名の3回以上の出現を許す、とする
--=内部的には軽い膜でhyperlinkを表現している、とする
-この二つの表現を分けたほうがいいのでは
--a.多数と多数の接続関係(多対多)
--b.多数が一つの共通データを参照している(多対一)
---bはどちらかというと共有変数的な感じ、とりあえずデータの変更方法は後回し
-まずは現状の(flatな)LMNtalでできそうなことだけ
-a.
1.
%大文字膜名は無理だけど
a(!+P), b(!+P), c(!+P). %% a(!P+), a(+!P).
<==>
a(L1), b(L2), c(L3), P{+L1, +L2, +L3}.
2.
a(!+P), b(!+P), c.
a(!+X), b(!+X), c :- a(!+X), b(!+X), c(!+X).
<==>
a(L1), b(L2), P{+L1, +L2}, c.
a(L1), b(L2), P{+L1, +L2, $p}, c
:- a(L1), b(L2), c(L3), P{+L1, +L2, +L3, $p}.
3.
%a,bとcが同じ集合に属するかを調べる
a(!+P), b(!+P), c(!+Q).
a(!+X), b(!+X), c(!+Y)
:- !+X \= !+Y | a(!+X), b(!+X), ok(!+Y).
<==>
%_A, _Bは膜名変数みたいなものとする
a(L1), b(L2), P{+L1, +L2}, c(L3), Q{+L3}.
a(L1), b(L2), _A{+L1, +L2, $p}, c(L3), _B{+L3, $q}
:- _A \= _B |
a(L1), b(L2), _A{+L1, +L2, $p}, ok(L3), _B{+L3, $q}.
%%比較の効率を良くできないか
9. %膜内の+の個数をガード条件にする
%javaには膜内アトム数を数えるガードがある?
a(!*P) :- !*P > 3 | ok(!*P).
<==>
a(X), _A{+X, $p}
:- \+($p=("-", $pp)), atomnum? > 3 | ok(X), _A{+X, $p}
-b. -:[0,1]個, +:[1,inf]個とする ( -L は "-"(L) )
4.
%共有変数への値の代入、のような
a(!+P), b(!+P), !-P = 3.
<==>
a(L1), b(L2), data(3, D), P{+L1, +L2, -D}.
5.
a(!-X) :- !-X =:= 3 | ok(!-X).
<==>
a(X), data(V, Y), _A{+X, -Y, $p}
:- V=:=3 | ok(X), data(V, Y), _A{+X, -Y, $p}.
%これはどうなるんだろう...
a(!+X) :- ground(!+X) | ok(!+X).
6.1.
%「この共有変数に値が束縛されていないなら5を代入する」
a(!-X) :- nonvar(!-X), !-X = 5 | a(!-X).
<==>
a(L), _A{+L, $p} :-
\+($p=("-"(A), $pp)) | a(L), data(5, D), _A{+L, -D, $p}.
6.2.
%「この共有変数に値が束縛されていないなら5を代入する」
a(!-X) :- nonvar(!-X), !-X = 5 | a(!-X).
<==>
a(L), _A{+L, $p} :-
\+($p=("-"(A), $pp)) | a(L), data(5, D), _A{+L, -D, $p}.
-これらを階層構造がある中でやるするとこれを考える必要がある
--c.任意階層から等しく参照できる(ルールで操作できる)
---一番やっかいかな
-c.
7.
a(!+P), {b(!+P)}, !-P = 3.
<==>
a(L1), {b(L2)}, data(3, D), P{+L1, +L2, -D}.
%bがある膜内で
b(!-X) :- int(!-X) | ok(!-X).
<==>
b(X) ... %% 無理
-(b-3と)cが現状のLMNtalではうまくいかない、かな
--そもそも階層クラスタグラフ(だっけ?)にhyperlinkがあるというのは、どうなるんだろう
--プロキシアトムをうまく入れることでどうにかならないかなぁ
--dataにデータアトムが結びついているときは配列で管理とか
**2010-06-09[#q8663905]
-軽い膜を入れるとすると
--+/-アトムのみ持てる
--子膜、ルールは持てない
---この辺りはずっと言われてること
--多階層から(等しく)参照できる
---グローバル変数的な、プロキシアトムを調節することでうまくいかないか
--(なんらかの形でdataを持ってるとして)同じdata持つもの同士をどう扱うのか
---同じなら結合させるのか、
---軽い膜自体の管理方法に大きく関わってくる
--参照カウント(+アトムの数)を利用
--パラメタ付けによる入出力、共有/非共有の表現
---上田先生の論文([[これ:http://link.springer.de/link/service/series/0558/tocs/t2237.htm]]の19番64枚目あたり)にあるけども
-膜 → 軽い膜(内部構造、単純に)
親膜への*p
兄弟膜への*p
代表子膜への*p → 廃止
ｱﾄﾑﾘｽﾄ管理ﾊｯｼｭﾃｰﾌﾞﾙ → -/+管理のみで済む
ｱﾄﾑ数
ﾙｰﾙｾｯﾄ配列 → 廃止
**2010-06-08[#q8663905]
-ゼミ発表資料作成を試みる
**2010-06-04[#q8663905]
*** [#hbd900b0]
-無かった理由として、膜を使えば書けちゃうから必要ないでしょ、がある
-今の膜のままじゃいけない理由をはっきりさせておく
--リンク同士の節点に使うには重い
--どの階層からも等しく参照できるような(グローバルな)ことは出来ない(やりにくい？やろうと思えば出来そうかな..)
---最初はフラットな場合を想定した方がいいんだろうけど、
--(LMNルールで)同じ要素を持つ膜を結合する時にO(膜の数^2)になるんじゃ？
***ubuntu : 起動できない [#i88c9a6a]
-更新したらboot時にgrub画面になって起動しなくなった
01,grub>ls
02,grub>ls (hdX,Y) #find ubuntu partition
03,grub>insmod ntfs #load ntfs module
04,grub>set root=(hdX,Y)
05,grub>ls $Boot #find BOOT partition's UUID
06,grub>search --no-floppy --fs-uuid --set xxxxx # 05で出たUUIDの後ろの文字列
07,grub>loopback loop0 /ubuntu/disks/root.disk
08,grub>set root=(loop0) #reset loop to loop0
09,grub>linux /boot/vmlinuzxxxxxxxxx root=/dev/sda1 loop=/ubuntu/disks/root.disk ro #load kernel
10,grub>initrd /boot/initrd.imgxxxxxxxxxxxx
11,grub>boot
-で無事復活
-あとはubuntu上で前回と同じようにカーネルのバージョン2.6.31-20より新しいやつをコメントアウト
**2010-06-03 2[#q8663905]
***班ゼミにて [#qfb65142]
-やっぱり膜をユニオンする、あるいはそれに相当する何かがあったほうがいいのではないか
--普通の膜よりも軽い膜、あるいはハイパーリンクがほしいかもしれない
--どういうルールになったらエレガントなのか、ちょっと書いてみるといいかも
--見た目は変数3つ許すけど、実は軽い膜を介しているようなシンタックスシュガーはあるとうれしいかも
**2010-06-03 [#q8663905]
***CHR : dijkstra(optimize) 測りなおし [#i96a534e]
-クエリはRand4 (edge=node*4)
|node|128|256|512|1024|2048|4096|h
|normal||0.23|0.66|2.16|8.42|out of stack|
|type/mode_array||0.13|0.31|1.22|3.86|out of stack|
|lmn(素直にencode)|7.95|47.21|320.72|2719.33|||
***膜による擬似共有変数について(昨日の続き) [#r5469161]
-昨日は初期グラフを生成する時に、既に変数(膜)とアトムが結びついた状態で生成していた。が、実際のlmnプログラムで使おうと思うと、(単純に考えてだけど)例えば1を持つアトムを
a(1) :- a(A), {value(1), +A}.
-という感じで変換した後に、value(1)を持つ膜が複数あれば結合する＝共有変数化するという作業が入ってくる。
{value(X), $p}, {value(Y), $q} :- X=:=Y | {value(X), $p, $q}.
-これじゃ結局、昨日の'lmn'ルールみたいにガードで整数を比較する作業を全ての値に対して行う必要が出てくる訳で、計算量的には何も改善されないんじゃなかろうか。
--ちなみにvar moduleを使うと、(最悪の場合で)n=10000で155.21[sec]だった。
-で、まぁそれがデータ(膜)のunionの話に繋がりそうななさそうな。
***CHRのエンコードでどうしても膜を使ってしまう例 [#e919309a]
-aを全て消した後にflagを消す。
-chr
a, a, a, flag.
flag \ a <=> true.
flag <=> true.
-lmn
{
a, a, a, flag.
flag, a :- flag.
}.
{flag, @p}/ :- .
**2010-06-02 [#q8663905]
***実験 : LMNtal vs CHR (整数の比較) [#c69b2962]
-同じ値を持つアトムの組を見つけて消す
-lmn(SLIM rev354) -O3
% A,Bの値をガードで比較
lmn @@ a(A), b(B) :- A=:=B | .
% A,Bが等しいことがヘッドで分かっている
lmnV @@ a(A), b(B), {value(N), +A, +B} :- int(N) | .
-chr(SWI-prolog 5.8.3)
% 制約の宣言はmode/type無し、mode/type有り、mode/type(dense_int)の三種類
chr @ a(X), b(X) <=> true.
-クエリ(計算量最悪になるように)
%lmnとchr3種類用
a(1), a(2), ..., a(N).
b(N), b(N-1), ..., b(1).
%lmnV用
a(A1), b(B1), {value(1), +A1, +B1}, ...(N番目まで)
-実行時間(sec.)
|N|10000|20000|40000|80000||h
|lmn|1.02|3.98|16.09|66.76|O(N^2)|
|lmnV|0.09|0.15|0.30|0.57|O(N)|
|chr|5.40|25.57|105.49|out of stack|O(N^2)|
|chr(mode/type)|0.12|0.25|0.52|1.28|O(N)|
|chr(mode/type_array)|0.08|0.20|0.39|0.80|O(N)|
--この例題に関しては、膜を使って擬似的な共有変数を表現したSLIMの方が若干早い
--ただ膜で変数を表すと、複数の階層間で共有させることは難しいんじゃなかろうか
--また今回はlmnVはO(1)で同じ値を見つけてこれるが、より多くのアトム(制約)が共通の変数を持っている場合にはその限りではない
***CHR : option [#z48e0f3a]
:- chr_option(Option, Value).
- Option = check_guard_bindings, Value = on/off
--off : default
--on : ルールのガードで変数へのillegalな束縛があった場合に実行中断
--例えば次のルールにquery1, query2をそれぞれ与えると以下の様
-
start(X) <=> X=1 | end(X).
% query1 : 正常 (Xの値と1を'比較'している)
start(1), start(2).
*---> end(1), start(2).
% query2 : 中断 (Xという変数に1を'束縛'してしまっている)
start(X).
*--->
start(_G25417)
X = _G25417{user = ...} ;
No
- Option = optimize, Value = ''full''/off
--off : default
--full : all available optimizations
--↓のdebugモードと一緒には使えない
---offとfullの中間は無いんだろうか？
- Option = debug, Value = on/off
on : default
off : optimizeを使うときは自動的にこれ？
*** CHR : その他 [#s9db9d63]
- ERROR: =</2: Arguments are not sufficiently instantiated
-- =< の両側の変数に値が束縛されていない
- findall_constraint/3 (shceduling.pl)
--謎。
**2010-06-01 [#q8663905]
***CHR : optimize option [#e2d84380]
-type/modeが使えるようになった！
--実行オプションつけなきゃいけなかった、書いとけよそういうの！
:- chr_option(optimize, full)
--onやoffでもなく、fullなのがよけい分かりにくくしている
--ちょっと測っただけだが、整数を扱うプログラムが相当に速くなっている様子、明日測ろう
***ヒープ [#b818c2d8]
-orderは次数と訳すのが自然？
**2010-05-28 [#q8663905]
***CHR : Union-Find algorithm [#c69b2962]
-とりあえず問題の内容をもう一度理解
-単純なもの、最適化されたものをlmnにエンコード
--集合を膜で表すことは可能なんだろうか？
***memo [#u83e7b4c]
-参照カウント、マークアンドスイープ
**2010-05-27 [#q8663905]
***CHR : dijkstraのtype/mode [#kb505e2f]
-論文の方ではtype/modeの有無で計算量が変化しているが、手元のSWIprologでは動いているのかよく分からない
--dense_intを使うと実行時間が変わる（逆に遅くなったけど）結果があったから、何らかの影響は出ているようだ、でも謎
-他にはUnion-findでもIndexが使われているようだ
***CHR : partner(passive)constraintの探索 [#l219f1ac]
-共有の変数をうまく利用してパートナーの探索を早くしてほしい、誰かに
**2010-05-26 [#q8663905]
***OpenOffice:対数グラフ [#u5819d25]
-書式→軸→Y軸→スケールタブ
**2010-05-24 [#q8663905]
-いろいろ整理
***dense_int [#maaaf4e7]
-ハッシュベースの制約ストアとは別に、配列形式の制約ストアを用意し、そこにdense_int型でインデックス付けして格納する
--ハッシュの計算回数を減らせる、衝突を避けることができる
--インデックスに使われる整数の個数が[0,n]間である程度多い(濃い=dense)場合に効果を発揮する、らしい
-Indexing tequnicとの関係をもう少し見たい
--chapter 9 join orderingも参考程度に
-dijkstra_fheapの計測
***ほか [#q8c3f6dc]
-prologのマッチングはどうなってる？
-edge(X,Y)形式だと計算量はどうしても多くなる
--アトムの引数の数をルールの条件にできたら...
**2010-05-19 [#z74307c0]
***callback : graph_gen_nocycle_uniq [#m6bd5f6d]
-dijkstraのプログラムは与えるグラフに色々注文が多い
-閉路無しかつ同じedgeが2つ以上存在しないグラフを生成
--関数名がおもいつかない
void graph_gen_nocycle_uniq(ReactCxt rc,
LmnMembrane *mem,
LmnAtom a0, LmnLinkAttr t0,
LmnAtom a1, LmnLinkAttr t1,
LmnAtom a2, LmnLinkAttr t2,
LmnAtom a3, LmnLinkAttr t3)
{
int n = (int)a1, m = (int)a2, r = (int)a3;
LmnSAtom sa;
const char *s;
if (LMN_ATTR_IS_DATA(t0)) {
switch (t0) {
case LMN_INT_ATTR:
break;
case LMN_DBL_ATTR:
break;
default:
break;
}
} else { /* symbol atom */
s = (const char *)LMN_SATOM_STR(a0);
}
int a[m], b[m];
int i, j, k, flag = 0;
srand(time(NULL));
for (i = 0; i < m; i++) {
a[i] = rand() % n + 1;
if (a[i] == 100) a[i]--;
b[i] = a[i] + rand() % (n - (a[i] - 1));
if (a[i] == b[i]) a[i]--;
}
while(!flag){
flag = 1;
for (i = 0; i < m; i++) {
for (j = 0; j < m; j++) {
if (i != j && a[j] == a[i] && b[j] == b[i]) {
a[j] = a[j] / 2;
b[j] = a[j] + rand() % (n - a[j]) + 1;
flag = 0;
}
}
}
}
for (i = 0; i < m; i++){
sa = lmn_mem_newatom(mem, lmn_functor_intern(ANONYMOUS,
lmn_intern(s),
3)
);
k = rand() % r + 1;
lmn_mem_newlink(mem,
sa, LMN_ATTR_MAKE_LINK(0), 0,
(LmnWord)a[i], LMN_INT_ATTR, 0);
lmn_mem_push_atom(mem, a[i], LMN_INT_ATTR);
lmn_mem_newlink(mem,
sa, LMN_ATTR_MAKE_LINK(0), 1,
(LmnWord)b[i], LMN_INT_ATTR, 1);
lmn_mem_push_atom(mem, b[i], LMN_INT_ATTR);
lmn_mem_newlink(mem,
sa, LMN_ATTR_MAKE_LINK(0), 2,
(LmnWord)k, LMN_INT_ATTR, 2);
lmn_mem_push_atom(mem, k, LMN_INT_ATTR);
}
lmn_mem_delete_atom(mem, a0, t0);
lmn_mem_delete_atom(mem, a1, t1);
lmn_mem_delete_atom(mem, a2, t2);
lmn_mem_delete_atom(mem, a3, t3);
}
**2010-05-18 [#z74307c0]
-25.
**2010-05-17 [#z74307c0]
***prolog : setof [#z3bb4037]
-listdom.plでの集合要素の加算
...
all_addition(L1,L2,L3) :- setof(Z, X^Y^(member(X,L1), member(Y,L2), Z is X + Y), L3).
...
--実装がどうなっているのか調べたけどよくわからなかった
--ただ長さNのリストに対してO(N^2)だったので、特別変わった実装じゃなさそう？
---LMNtalでもやっぱりN^2が最速だろうか
**2010-05-14 [#z74307c0]
***CHRのlistdom.pl [#z3bb4037]
-X lt Y って単にmax(X)<max(Y)なんだろうか、少なくとも実行結果はそうみえる
-だとしてもなんだかちゃんと書かれてない気がするな
***UNYOのバグ？（既に報告されていた） [#z3bb4037]
-''(追記)Javaコンパイラのバグだったみたい''
--[[言語班バグ報告:http://www.ueda.info.waseda.ac.jp/lmntal/local/pukiwiki.php?%A5%D0%A5%B0%CA%F3%B9%F0]]
&br;
-LE1.3.5に同封されているUNYO3Gでの現象
-「要素が一つ以上入っている(空( [] )じゃない)リスト」にマッチするようなルールを書きたくてrule1の様にした
list(x, [1,2,3]), list(x, [4,5,6]).
rule1 @@ %空じゃないリストにマッチするルール
list(X1, [Y1 | L1]), list(X2, [Y2 | L2]) :- X1 = X2 |
merge(X1, [Y1 | L1], [Y2 | L2]).
rule2 @@ %rule1を適用後、適用されるルール
merge(X, L1, L2) :- ground(L1), ground(L2) | end(X).
-Java、SLIMで実行すると正常だが、これをUNYOで動かすとなんかリンクがおかしくなった
#ref(unyo_bug.png)
[Step: 0]
list(x,[1,2,3]), list(x,[4,5,6])
[Step: 1]
merge(x,[1,2,3],[L1|L10]), '.'(6,[],L23), '.'(5,L23,L10), 4=[L1|L10]
-このあとrule2が適用されると落ちる
--groundチェック中にグラフが途中で途切れてるから？
-2Gでも落ちた！
-rule1のガード（X1=X2）が関係しているのかも、unary(X1), unary(X2)とかにすると大丈夫
--listを1価(list = [1,2,3]とか)にして、X1=X2を行わないようにしたら大丈夫だった、やっぱりX1=X2がいけない？
--mergeの第一引数にX1を入れないようにすると大丈夫、アトムの再利用が関係しているのか？
-rule1をこうすれば大丈夫だけど、リンクの先がリスト構造ならばマッチするようなルールのきれいな書き方はないものか
list(X1, L1), list(X2, L2) :- X1 = X2 | merge(X1, L1, L2).
**2010-05-13 [#b773aa72]
***callback関数 : integer_int2float [#x3e70a0e]
void integer_int2float(ReactCxt rc,
LmnMembrane *mem,
LmnAtom a0, LmnLinkAttr t0,
LmnAtom a1, LmnLinkAttr t1)
{
int i = a0;
double *d = LMN_MALLOC(double);
*d = i * 1.0;
lmn_mem_newlink(mem,
a1, LMN_ATTR_MAKE_LINK(0), LMN_ATTR_GET_VALUE(t1),
(LmnWord)d, LMN_DBL_ATTR, 0);
lmn_mem_push_atom(mem, (LmnWord)d, LMN_DBL_ATTR);
lmn_mem_delete_atom(mem, a0, t0);
}
***Prolog : delete [#xf5264c2]
delete([1,3,2,3],3,X) ----> X = [1,2].
***班ゼミ [#ma2efd4a]
-一つの例題をもう少し細かく見てみよう
--データ表現やルールの工夫なんかでこれ以上改善できないというところまでもっていく
**2010-05-12 [#v8b22e83]
***[[New CHR website:http://dtai.cs.kuleuven.be/projects/CHR/index.shtml]] [#d611aeec]
-リニューアルされててびっくり
**2010-05-11 [#ad793772]
**2010-05-11 [#geafcdc0]
*** CHR : \+ : andの否定? [#qb484449]
- A=B∨C=Dの否定なので、A\=B∧C\=Dかな、実行してみるとそうなっている様だ
... <=> \+ (A=B, C=D) | ...
**2010-05-09 [#k1072db1]
***listdom.pl : エンコード完了？[#x88b5a48]
-エンコードできたと思う、かー疲れた
**2010-05-08 [#ad793772]
**2010-05-08 [#u021c55c]
***listdom.pl [#x88b5a48]
lt : less than
le : less than or equal
ne : X ne Y, Y::[*]で*からXを取り出す?
**2010-05-07 [#ad793772]
**2010-05-07 [#r6d43f00]
***callback関数 : graph_gen [#ef895289]
-(Name, M, N, R)で1-R間の乱数を引数に持つM価のNameアトムをN個生成
/*
* (Name, M, N, R):
*
* Name = symbol atome
* M, N, R = integer
*
* Create random integer sets.
*
* <------------- M --------------------->
* 1) 'Name'(rand()%R+1, rand()%R+1, ..., rand()%R+1),
* 2) 'Name'(rand()%R+1, rand()%R+1, ..., rand()%R+1),
* ...
* N) 'Name'(rand()%R+1, rand()%R+1, ..., rand()%R+1).
*
*/
void graph_gen(ReactCxt rc,
LmnMembrane *mem,
LmnAtom a0, LmnLinkAttr t0,
LmnAtom a1, LmnLinkAttr t1,
LmnAtom a2, LmnLinkAttr t2,
LmnAtom a3, LmnLinkAttr t3)
{
int m = (int)a1, n = (int)a2, r = (int)a3;
int i, j, v;
LmnSAtom sa;
const char *s;
if (LMN_ATTR_IS_DATA(t0)) {
switch (t0) {
case LMN_INT_ATTR:
break;
case LMN_DBL_ATTR:
break;
default:
break;
}
} else { /* symbol atom */
s = (const char *)LMN_SATOM_STR(a0);
}
for (i = 0; i < n; i++){
sa = lmn_mem_newatom(mem, lmn_functor_intern(ANONYMOUS,
lmn_intern(s),
m)
);
for (j = 0; j < m; j++) {
v = rand() % r + 1;
lmn_mem_newlink(mem,
sa, LMN_ATTR_MAKE_LINK(0), j,
v, LMN_INT_ATTR, j);
lmn_mem_push_atom(mem, v, LMN_INT_ATTR);
}
}
lmn_mem_delete_atom(mem, a0, t0);
lmn_mem_delete_atom(mem, a1, t1);
lmn_mem_delete_atom(mem, a2, t2);
lmn_mem_delete_atom(mem, a3, t3);
}
-こんな感じ
'$callback'('graph_gen', edge, 3, 4, 10).
---->
edge(7,1,4). edge(4,8,6). edge(2,6,10). edge(1,5,10).
***prolog : cut(!) [#b25eb2f7]
-バックトラックを制御するcutについて
1) ticket(Age, Money) :- Age < 13, Money is 500.
2) ticket(Age, Money) :- Money is 1000.
--rule1が再試行したときに、Ageに関係無くrule2が評価されちゃう
1) ticket(Age, Money) :- Age < 13, Money is 500, !.
2) ticket(Age, Money) :- Money is 1000.
--感嘆符でバックトラックを制御しなければならない
**2010-05-07 [#ad793772]
**2010-05-07 [#u6025650]
***callback関数を触ってみた [#na78e819]
-[[SLIM callback関連 メモ]]
&br;
***こんなのがあったのか、コロン記法？ [#vf356b38]
x :: [1,2,3],
y : [4.5.6].
---->
<Java処理系> '::'(x,[1,2,3]). y:[4,5,6].
<SLIM> '.'(1,[2,3],'::'(x)). '.'(4,[5,6],':'(y)).
-これはerror
[4.5.6] : y.
-チルダとか_とかも試してみたけど、こういう風に特別扱いされているものは見当たらなかった
&br;
-eclipse 行番号の表示
++「ウィンドウ」>「設定」>「一般」>「エディタ」>「テキスト・エディタ」
++「行番号の表示」にチェック
**2010-05-06 [#ad793772]
**2010-05-06 [#i6803b6f]
***CHR encoding [#abc74552]
-制約プログラミング的な例題をencodeページに貼っ付ける
--貼っ付けて少し整形してみた
-やりかけ
--TM, RAM, Floyd-Warshall
**2010-05-03 [#ad793772]
**2010-05-03 [#ya3df301]
***Floyd-Warshall法の解説を読んでみた [#h38b6bc4]
-あのアルゴリズムをそのままLMNtalで書けるのか
--書けそうかも？ちょっと書いてみる
-CHR文献内のベンチマークにたまに"FLOYD-WARSH(N)"てのがある、よく調べる
**2010-05-02 [#ad793772]
**2010-05-02 [#o824d9ad]
***ubuntu kernel panic! [#g4982e04]
-ubuntuをupdateして再起動したらkernel panic!
--検索するとLinux 2.6.31-21-genericでは割と多く起こっているみたい
--GW早々ざけんな、というわけで
/boot/grub/grub.cfg の
Linux 2.6.31-21-generic の部分をコメントアウト
--してとりあえず回避
-ubuntuの日本語変換パニクっている
りようしやすいかたちで
理想 : 利用し易い形で
現実 : 理容師やスイカたちで
-輪読の担当部分を読んでみた
--なんかプロセスって言葉の定義と、Javaではどうやって使うかみたいな話ばっかりだった
--例題をさらっと流してしまったが、後町分の内容が薄いならここもちゃんとスライドに盛り込んだほうがいいかと
**2010-04-27 [#ad793772]
**2010-04-27 [#df9764f6]
***CHR encoding [#q314b718]
-CHR encodingのページを整形してみたが、ううむ
-CHRの文献をあさっていたら、いくつか新しい例題を見つけたのでちょっと書いてみる
-輪読を忘れないようにしないと
&br;
-キヤノンのメーリス作った
**2010-04-26 [#ad793772]
**2010-04-26 [#y059c76f]
***[[言語班ローカル/CHR encoding:http://www.ueda.info.waseda.ac.jp/lmntal/local/pukiwiki.php?CHR%20encoding]] [#j4ccfc88]
-とりあえず作ってみたものの、どういうレイアウトにしたらいいのか悩む
***[[SLIM時間計測]] [#db7d2000]
-まだまだ少ないが、突貫でまとめてみた
-CHRプログラムに与えるクエリをどうするかでいつも悩むのはなんとかならないものか
&br;
***ほか [#wc9fbf9c]
-dijkstraは重みが非負数の場合のみ使える、O(V^2)
-Bellman-Fordは非負数でもok、O(V^3)
-Warshall-Floydは非負数ok、でもサイクルに非負数があるとダメ、O(V^3)
**2010-04-25 [#ad793772]
**2010-04-25 [#nde74527]
***SLIM他言語インタフェースドキュメント [#g363450b]
-slim/doc/foreign.txt
***system_rulesetとcallback [#h40a307f]
-こんな風に組み合わせるとおかしくなる、あたりまえか
'$callback'(integer_rand, N+1, H).
**2010-04-24 [#ad793772]
**2010-04-24 [#af62a907]
***graph_generator.c [#w715752b]
-作ってみた、後悔はしていない
--地味に重み付け有り無しや、出力先を選べたりする
--なぜLMNtalで書かないのか、と言われても特に理由はないよ
$ ./graph_generator
name of edge (string) : edge
node num (integer) : 5
edge num (integer) : 5
edges have weights? (yes:1 or no:0) : 1
max edge weights (integer) : 3
at random? (yes:1 or no:0) : 1
---------------------------------
edge(3, 2, 2). edge(1, 4, 2). edge(5, 3, 2). edge(3, 3, 2). edge(4, 5, 3).
***UNIX [#i96144f1]
-scriptコマンド
**2010-04-23 [#ad793772]
**2010-04-23 [#i36266fa]
***Canon事業所見学会 [#wd4e470e]
-開発職でも要素技術研究的な仕事もある、というのはどこの事業所も同じらしい
-Canon合格者のメーリス担当になった。笑
**2010-04-22 [#ad793772]
**2010-04-22 [#kd7c0982]
***Union Find [#ic10d66a]
-エンコードしてみた、クエリとして変数は与えられないけど
***最短経路問題 [#fbe7bb00]
-グラフ上の1点から他の全ての点への最短距離を求める
--chr_sssp : 先週の全対用のプログラムを少し変えてノード1からの最短経路のみを求める
---たったの2ルール
---O(N^7)のプログラムを、N個のノードからではなくノード1からの探索のみにしたのでO(N^6)
|node|10|20|30|40|50|
|time|0.02|1.15|14.47|83.96|330.00|
|t/(n/10)^6|0.023|0.018|0.019|0.020|0.021|
--chr_dijkstra_Fheap : ダイクストラ法＋優先度付きキュー(フィボナッチヒープで表現)
---O(M+NlogN)で最も速いとされている方法、Mはエッジ数
---CHRで書いたらO(N*I+M*D+N*E)、IやらDはルール適用回数
---dijkstra＋Fheapモジュールで26ルールくらいある
---今回のクエリ（有向完全グラフ）ではO(N^4)より若干低いくらいになるはず
&br;
---なってた
|node|10|20|30|40|50|60|
|time|0.01|0.05|0.17|0.45|1.03|1.95|
|t/(n/10)^4|0.01|0.00312|0.00213|0.00175|0.00164|0.00150|
***CHRプログラミング、気になること [#wc70dd00]
-CHRの例題には「処理系の実装方法的にルールの適用順序はこうなるはず」を考慮してプログラミングしているものが多い気がする(というか文献とかで明示している)
--例えば、次の2つのルールは上から順に評価される
---itemがたくさんある中にfindminを生成するとfindmin@が一通り実行され、最後にfoundmin@が実行される
--なんかずるくないか、別にitemがあってもfoundmin@が実行されてもいいはずでは
--それともLMNtalでそういう書き方しないのは馬鹿正直すぎるのだろうか
findmin @ findmin, item(I,K,_,0,_) ==> min(I,K).
foundmin @ findmin <=> true.
**2010-04-21 [#ad793772]
**2010-04-21 [#d1f2e80c]
***dijkstra のエンコード終わった [#hfa7d37e]
***その他 [#k09b3c28]
-[[2011卒 主な企業の採用人数:http://www.nikkei.com/tech/news/article/g=96958A9C93819696E3EBE290868DE0E3E2E6E0E2E3E28698E3E2E2E2;da=96958A88889DE2E0E2E5EAE5E5E2E3E7E3E0E0E2E2EBE2E2E2E2E2E2]]
-村岡・後町を慰める(?)会
--生 * 21杯 / 3人 = 7 [杯/人]
--酔いって指数関数的にくるよね
**2010-04-20 [#ad793772]
**2010-04-20 [#i46c8317]
***dijkstra's algorithm with F-heap [#xe3774f5]
-LMNtalにエンコード中
-膜を使えばうまくできそうな気がしなくもなくもない
-memo
- : 常に未束縛の変数
+ : 常に値を束縛された変数
? : default. どっちにもなりうる。
int : integer number
dense_int : array indexとして使用できる
number : number
float : float
any : any
**2010-04-19 [#ad793772]
**2010-04-19 [#gb03c205]
***chr_path_N [#z8a82d70]
-All Pairs Shortest Path(APSP) problem：全対最短経路問題
-EPSON(Quad, 2.6GHz, RAM4GB)で実験してみた
--クエリは有向完全グラフ
--node:edge = n:(n^2-n)/2
|node|10|20|30|40|50|60|
|time|0.04|3.34|56.94|430.48|2075.18|7498.03|
|t/(n/10)^7|0.04|0.2611|0.2603|0.2627|0.2656|0.2678|
--O(n^7)になってた
e(I,J1,A),e(J2,K,B) :- uniq(I,J1,K,A,B), ... | ... .
n n n n n n n
--今回は重みは全て1なので、A,Bには1しかこない(2以上になると1本目のルールで消される)
***例題増やし [#nfd53792]
-ダイクストラ
--フィボナッチヒープを用いた最適化の論文、読んでみてる
-あとはUnion findとかがいいかな
**2010-04-18 [#ad793772]
**2010-04-18 [#qbeaf19a]
***CHR book [#ybcdcab0]
-パス整合、アーク整合辺りを読んだ
**2010-04-17 [#ad793772]
**2010-04-17 [#kd995be2]
***Propagationとuniqの違い [#k2da0ebc]
-CHRでよくある経路関係の推移閉包を求める例
p1 @ e(X,Y) ==> p(X,Y).
pn @ e(X,Y), p(Y,Z) ==> p(X,Z).
-propagation ruleは同一の''制約''(eやp)に対して高々一回適用が許されるため、この例にe(1,1)を与えると止まらない
-uniqは変数X,Yの組を見ているので、e(1,1)を与えても止まる
-だから例題によっては、LMNtalの方が計算回数が少ない書き方できる、気がする
**2010-04-16 [#ad793772]
***ubuntuでchrを動かせた [#wfab9b91]
-library下にchrディレクトリとchr.plが無かったのが原因
-ただ単純に他のswi-prologから持ってきてもうまく動かないことが多い
-とりあえず、以下の組み合わせなら動いた
+http://www.swi-prolog.org/download/stableから次の2つを落としてくる
--リストの上の方にあるLinux用のバイナリ
--下の方にあるSources
+Sourcesの方をインストールする
% tar zxvf pl-<version>.tar.gz
% cd pl-<version>/src
% ./configure
% make
% [su root]
% make install
--ここでとりえあずSWI-prologが動くか確認
% pl
Welcome to SWI-Prolog ...(略)
?-
--chrライブラリを読み込んでみる
?- [library(chr)].
--次のようなエラーが出たらchrライブラリが無い
ERROR: source_sink `library(chr)' does not exist
+バイナリの方からchrフォルダ,chr.plを持ってくる
--pl-<version>.rpmを適当な場所に解凍
--usrフォルダが出来るので、
解凍した場所/usr/lib/pl-<version>/library/下のchrフォルダとchr.pl
--を、
/usr/local/lib/pl-5.8.3/library/
--にコピーする
+Sourcesに対して再度の1.の./configure以降を実行
--prologを起動し、
?- [library(chr)].
% library(chr) compiled into chr 0.27 sec, 3,866,648 bytes
true.s
--となったらめでたしめでたし
**2010-04-15班ゼミ後 [#ad793772]
**2010-04-15班ゼミ後 [#i09df131]
***次週までに [#m614fe25]
--chr_path.lmnの測定、オーダー計算などもろもろ
---warahall's algorithm
--benchmark setの用意
**2010-04-15 [#ad793772]
**2010-04-15 [#t489fe6c]
***-班ゼミ用：どんな例題を早くしたいのか [#af00bbda]
--ロックフリーで実装
---STMベース？
--最初は0or1価のアトムやリストを扱う例題（膜無しで）
--CHR的な何か
---最短経路、
--NESLの例題はどうか
---quicksort：入れ子データ並列
&br;
***ubuntuでlibrary(chr)が呼び出せていない [#hc7d5e97]
-調べる
**2010-04-14 [#ad793772]
**2010-04-14 [#bc9ae2ef]
***ubuntu [#b57d74f1]
$ uname -a で32or64ビット版か見分けられる
***Let's Noteが直った [#rc79df66]
-パナソニック修理工房、インバータの故障(有料)だったけど、液晶パネルまで交換(無料)してくれた、出来る
**2010-04-13 [#rc509ece]
***SLIMのrule trialにかかる時間(通常実行) [#u0816253]
-time_optimized_slim
-手持ちの例題でざっと取ってみた、編集中
-あっているんだろうか
**2010-04-09 [#rc509ece]
-先生からKLICやらCHRを使える環境をどこかに用意しようとのお話
--paveにはKLICが入っていた、でもうまく動かなかった
-NIOLOに入れてみようとした
--選択肢選んでいったら、途中で無限ループしたので今日は放置
--でもgochoのubuntuではインストールまではうまくいってた、パッチ当てればうまくいく？
-NESLの論文の読み飛ばしてたところを思い出した、明日読む
--やっぱりクイックソート的な例題をやってみたいとは思う
**2010-04-08 [#rc509ece]
-M2ページ作ってみた [#f6ca3e7f]
-ubuntuを新しいPCにインストールしてみた [#e4d9ba88]
-KL1を動かしてみる [#hbc9ed25]
--KLICの実装について
---Inside KLIC（KLICのHPから）日本語
&aname(word);
*うめき [#u845d424]
**2010-08-05 [#d449558d]
&aname(face);
-2010-08-05更新
-ueda先生?
u: :-) or 鋭意製作中
-M2
i: (¬ 。¬)
s: (~ω~ )
a: (・∠・^)
o: (｀〜｀)
g: (´^д^)
m: (｀∀´)
-M1
y: ＜(・ω・ )＞／
y: (｀口´ ) or (｀。´ )
k: (o-ω-o )
s: (＠∇＠ )
s: (≡ω≡ )
q: (^皿^ )
n: (´＠_＠｀ ) → (´ _ ｀ ) → (´_｀ ) → (No Image ) → (´●_●｀ )v
t: (｀ε´ ) or ( ｀з´)
//-b4
// m: (∵)
// n: (^(●●)^ )
// m: (・ш・ )
// x: (○￣ー￣○ ) or (o￣_￣o )
// others: (@_@)
**2010-04-09 [#pecf95bc]
-春だ
-馬場駅周辺が色々変わっててびっくり
-就職活動終了、研究がんばらないと
--山名先生は優しかった、文面がhiroshiと同じだったが、でも優しかった
**2010-04-08 [#pecf95bc]
-がんばりたい。