TopPage
Contents †
TODO †
研究日誌 †
2011-03-26 †
KI journal の英訳文 †
- 申し訳程度のtexファイルがgoudaのhome/seiji/ki2011/にあります
2011-03-18 †
JSAI2011執筆時の実験結果 †
2011-02-19 †
論文の所属 †
- 基本的に研究した所属を「所属」に書く
- 論文発表時に別の所属になってる場合には、脚注に書く人もいる
2011-02-09 †
修論の漢字統一 †
- 分かる
- 思う
- できる
- とき
- つながる
- および
- 組合せ
- 一つ, 1個
- みなす
- こと
- もの
- 行う
- 全て
2011-02-08 †
paragraphで改行 †
- させたかったら
\paragraph{タイトル \\}
- のように{}の中に\\を書けばよい
2011-02-05 †
eclipseでtex †
texの使い方 †
- \documentstyle[report,12pt]{jsbook}は\documentclass[report,12pt]{jsbook}
- \pagestyle{heading}は\pagestyle{lineheadings}
- documentclassからbegin{document}までがプリアンブル部
2011-02-04 発表終了！！ †
いただいたコメント †
- 膜はいらなくなっちゃったの？(中島先生)
- いります。膜には階層を作って計算の局所化を行う役割があるので、それはハイパーリンクにはない機能です。
- ハイパーリンクによって非効率的なマッチングが減ったのはわかった、それはモデルが単純に記述できるようになったからだよね？(中島先生)
- それが一つの理由で、もう一つはハイパーリンクの接続関係を利用したマッチングがあります。（詳しめに説明）。CHRの最適化もこれと似たような考え方を使っています。
- どういうときに膜、ハイパーリンクを使い分けるの？(中島先生)
- ハイパーリンクには、接続先を計算量１で取得する機能があります、これは論理変数にも無い機能です。今までは集合は膜で囲って、中にアトムを入れるとかしていましたが、その個数を数えるためにはルールを繰り返し適用して数えるしかなかった。
- だから局所化は膜、集合を扱う場合にはハイパーリンクだね。(上田先生)
- マッチング最適化のスライドをもっとちゃんと用意しておけばよかった
用意していた回答 †
- 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 †
現時点での処理系行数（アバウト） †
- 上2つはこの日にwcで計測、コメントアウトも入っている
- Java処理系：38460+19010+2784=60254
- SLIM：27708+29285=56993(ファイルの頭のコメントは計4600行くらい)
- LaViT：30000くらい
- UNYO：15000くらい
2011-01-28 †
文字数の差 †
- 各例題の文字数を数えてみた
| example | atom_cmp | cycle | leq | fibonacci | uf | uf_opt | *ram_simul |
| 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.
ちなみに †
- (ハイパーでない)グラフ <=> 一般グラフ
- ハイパーグラフ <=> 超グラフ
2011-01-27 †
- 修論一旦提出
- JSAI2011に申込み、発表はたぶん目黒パワーに期待することになりそう
2011-01-26 †
韓国に劇的勝利 †
texの表で破線を使えるように †
2011-01-25 †
unary用比較演算子"\==" †
- を追加してみた
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 †
論文で中間命令列の一覧を書きたいとき （修正版） †
論文で中間命令列の一覧を書きたいとき †
- 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 †
hyperlink : groundチェックでのバグ †
- 昨日直したと思ったけど、直っていなかった
- 原因は大体把握したけど、どう直すかはしっかり考えないといけないかも
2011-01-19その2 †
- 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 †
Java処理系公開の手続き †
2011-01-16 †
hyperlink : commit! †
- してしまった。致命的なバグがないことをみんなで祈ろう。
- 追加したもの
- hyperlink
- hyperlinkを利用したマッチング最適化機能（findproccxt命令ほか）
- callback関数gettimeと、SLIMモジュールtime.lmn
slim419でedfs_t*.ilがsegmentation fault †
修論タイトル †
- 酔った勢いでかっこよさげなの考えてみる
並行プログラミング言語LMNtalにおけるLMNtalグラフのハイパーグラフへの拡張- LMNtal連呼してる感じなので却下
2011-01-15 †
2011-01-15 †
hyperlink : ハイパーリンクのIDをインクリメンタルな数値に †
- hyperlinkに値を代入する話ではない
- hyperlink木からhyperlinkオブジェクトを削除する際、木の中で削除対象のオブジェクトを葉に向かってスワップしていき、葉に到達した時点で削除するような最適化(子をたくさん持ったまま削除すると色々処理がかかる)を入れたため、集合を代表する(rootの)IDが固定されなくなってしまっていた
- これだとuniq制約で履歴を管理する際に苦しい
- インクリメンタルな番号をふり、uniqの履歴および標準出力時にはそれをIDとする
- hyperlinkのuniqへの対応＋出力時のIDの短縮化が可能に
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 ====
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 †
hyperlink : コミット作業中 †
- callback関数をモジュールで呼び出せるtime.lmnも追加予定
2011-01-10 その2 †
hyperlink : 新々仕様での実験 ram_simul_many †
| N | 5k | 10k | 20k | 40k | 80k | O |
| 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 †
| N | 5k | 8k | 10k | 16k | 20k | 32k | 64k | 128k | O |
| 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：新々仕様での実験 atomcmp_x3 †
- 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 |
| 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 †
hyperlink : 中間命令列の並び替え †
- コンパイラを若干変更
- newhlink, makehlinkとuniqの並び替えがうまくいっていなかったのを修正、コミット
- ついでにコードの整理もちょっとやった
2011-01-08 †
計算量が悪い件 †
- 原因が把握できた
- なぜ膜内の！アトムを全てさらうようにしていたのか、理解に苦しむ
--enable-gprof(と--disable-tcmalloc)でallocs/freesの数が合わない †
lmntal --slimcode -e "a." | valgrind src/slim -
- valgrindで見るとfreesが1足りない
- 俺の環境だけかな？
- 2つのデバッガを同時に使う俺が悪い 2011-01-14
2011-01-07 †
fibonacciとramを測定 †
- オーダーが悪い...
- --p3でチェック、ルールの適用/試行/バックトラック回数は旧実装より悪いルールは無い
- 内部実装の問題、見直し中
- fibonacci_topdown(unify)
| N | 4k | 8k | 16k | 32k | | O |
| slim hlink new | 0.13 | 0.41 | 1.90 | 14.60 | | ? |
- ram_simul
| N | 5k | 10k | 20k | | O |
| slim hlink new | 0.66 | 3.84 | 22.60 | | ? |
2011-01-04 †
hyperlink : 所属膜へのポインタ †
- 持たせておけば、hyperlinkからのfindatomをもう少し効率化できる気がする
hyperlink : ユーザIDの追加検討 †
- 機能としては用意しておきたい。がバグが取れてから...
- CHRでは同じ値を束縛された論理変数が生成された場合は、生成された時点で同じ集合に属する
X is 1.
hoge <=> Y is 1, v(Y).
- （必須ではないが）hyperlinkにもこういう機能がないと、プログラムが煩雑になる
- 非効率なマッチングを生まないように書くために、色々と苦労しそう
イメージ：
hoge :- make($x, 123) | h($x).
*---> h(!123).
(ID123を持つ他のhyperlinkの集合と併合された状態で生成される)
2010-12-28 †
hyperlink : ハッシュ表による管理を廃止 †
- 新しい属性LMN_HL_ATTRのバグがかなり取れてきた気がするので、ハッシュ表でatom pointer => hyperlink objectの参照関係を管理していたのを廃止
- "!"アトムの第2引数にhyperlink objectへのポインタを直接埋め込む
| N | 8k*3 | 16k*3 | 32k*3 | 64k*3 | 128k*3 | 256k*3 | O |
| 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 †
最短"経路"問題 †
- 最短距離を求めるプログラムは色々あるけど、uniq使えばたいがい1,2ルールで書ける
- ただ最短"経路"となると2行で書けるのかちょっと自信無かったけど、なんとか書けた
- &ref(): File not found: "shortest.lmn" at page "研究日誌とうめき";
2010-12-21 †
hyperlink：新仕様での実験 cycle_backedge5 †
- 3頂点からなる閉路を探索する(propagation, uniq無し)
edge(X, Y), edge(Y, Z), edge(Z, X) <=> cycle(X, Y, Z).
| N | 100 | | 500 | 1000 | 2k | O |
| 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 †
hyperlink：新仕様での実験 atomcmp_x3 †
- 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 |
| 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の上限が無くなったのが大きい
カラー大辞典 †
2010-12-14 †
ubuntu9.10にopenoffice3.2 †
2010-12-13 †
解放忘れ？ †
2010-12-12 †
hyperlink 比較系memo †
- isground
- eq/neqground
- eq/neqfunc
- samefunc
memo †
2010-12-10 †
hyperlink : 新仕様での実行時間 †
- アトム生成&削除
- 10000個のatom(hyperlink)をN回生成->削除
- どちらもtime optimized slim
| N | 100 | 200 | 400 | 800 |
| 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 |
| 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 †
リモート設定メモ †
- コンピュータ：localhost:13389
- プロトコル：RDPv5
- ユーザ名とパスワード
- (マシンアドレス：00:22:15:7d:86:dc)
2010-12-06 †
LMN_ATTR_IS_DATA_WITHOUT_EX †
- exはextended。extra, expandedでもまぁ意味は通じる？
2010-12-03 †
ハイパーリンク属性 †
- ハイパーリンクはファンクタ!/1のアトム
- だけど属性としてはデータアトムの一種
- だけどシンボルアトムとして、膜への登録、削除等々を行う
- callback atomと同じような
- メリットとしては型検査を最適化できる
- デメリットとしては実装が面倒
2010-11-26 †
hyperlink : アトムポインタをIDとする †
- これまでのハイパーリンクアトム
- ファンクタ：!1, !2, ...(実行中に新たなファンクタを生成していた)
- 管理(hlink ID)： 1, 2, ...
- 通常の（シンボル）アトム
- 新しいハイパーリンクアトム
- INSTR_COPYATOM
- これまでは同じIDを持つhlinkは複数個生成可能
- 複製したらオリジナルと併合する
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 †
戸川先生のディジタル回路設計(ごてふより) †
hyperlink : 仕様変更 †
- インクリメンタルなIDで管理するより、アトムのポインタでハイパーリンクを管理する方が何かと都合が良いため
2010-11-23 †
boolean.lmnのコンパイル †
- 修正版を一昨日コミットしたが、どうやらちゃんと動いているみたい
- 俺がよく見ていたboolean.lmnのコンパイルエラーは、単にノーパソで間違ったパスをLMNTAL_HOMEに指定していたから出てきていたものだった、迂闊なんてレベルじゃない
2010-11-22 †
デフォルトセッションの変更 †
- netbook editionを入れると、ログイン時にdesktop版も選択できるけど、デフォルトセッションを変更したければ、システム管理→ログイン画面の設定
日本語入力が出来ない †
- システム→設定→キーボード・インプットメソッドからAuthyを追加
2010-11-20 †
Xp - ubuntuデュアルブート関連 †
- wubiでインストール失敗
- permission denied となってlogを参照するように言われる
- isoファイルのダウンロードで終了していたら、ここからisoをダウンロード
- Deamon tools liteでisoをマウントして一旦ubuntuをアンインストール
- 再びisoからインストール開始
- 既定の起動OSを変更する
- Xp -> コンパネ -> システム -> 詳細設定 -> 起動と回復 から変更
boolean.lmnがコンパイルできなかったバグ †
- 俺でした...修正版をコミットしましたが、チェックできてないのでちゃんと直ってるかどうか
2010-11-19 †
ubuntuでSLIMが動かなくなった件解決 †
- iwatasoが解決法をなんとか思い出してくれたおかげで復活！
- make install で /usr/local/share/に出来るslimが悪かった？
- slimという名前を変更すれば正常に動くようになった
- 原因は何なんだろう？
Windows XP:余計なスタートアッププログラムを解除 †
2010-11-18 †
ubuntuでSLIMが急に動かなくなった件 †
wubi †
- 追加でubuntuをインストールすることは出来なそう、アンインストールが必要と言われる
もう一台のPCにubuntuをインストールして比較してみた †
- configureの内容を互いに比較してみた
- mawkとgawkというソフトの違いがあり、その辺をそろえてみたけど結局変わらず
ubuntu : eclipse install memo †
2010-11-17 †
kernelの再構築 †
$ 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 †
- memo
- lmntal.cupにごみが入っていたのを修正、そのうちコミット
2010-11-09 †
- 中間発表メモ
- IDの使用数を測ってみる
- グラフだけでなく、例題の内容、同実装したか、結果の考察は必要
- インクリメンタルなIDではなく、アドレスをIDに
- でも結局ファンクタのID数は決まっているのでよく考えたほうがよさそう
- アンビエントを書いてみたい
- 今後の方向性、非決定実行の評価
2010-11-03 †
- ハイパーリンクへの値の束縛の必要性？
- 集合が持つ値をn(!1, 1).とかで表すと、例えば
a($x), n($x,N1), b($y), n($y,N2) :- N=N1+N2 |...
- のように値を足すルールで、N1,N2が同じ値である場合があるなら、その分nの個数を増やさなければならない、書くのがちょっと面倒かな
2010-10-29 その2 †
fibonacciのオーダーが悪かった原因（残りの半分） †
- 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 |
| 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のオーダーが悪かった原因（半分） †
- 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 |
| slim int hlink | 0.28 | 1.18 | 7.23 | 38.30 | | |
2010-10-29 †
- 班ゼミメモ
- CHRで書くことに意味のある例題を選ぶ
- fibonacci, leqの解析
2010-10-28 †
2010-10-27 †
fibonacci †
- 注)フィボナッチ数は、下記のbottomup, topdownのようなやり方をしなくても、リストを使えば数万番目くらいまでは一瞬で求めることができる
fib(N,[X,Y|L]) :- N > 0, N1 = N-1, Z = X+Y |
fib(N1,[Z,X,Y|L]).
fibonacci (bottomup) †
- hyperlinkを使う意味はあまり無いが、下のtopdownとの比較のために測ってみた
| N番目 | 100 | 200 | 400 | 800 | O |
| 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) †
2010-10-25 †
ram_simulator †
- 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 |
| 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 |
| 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 †
union-find †
| N | 100 | 200 | 400 | 800 | 160O | 3200 | O |
| 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 †
- pass compression for find, union-by-rank
| N | 100 | 200 | 400 | 800 | 160O | 3200 | O |
| 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 |
| slim hyperlink | 0.01 | 0.02 | 0.04 | 0.08 | N |
cycle †
- 3頂点からなる閉路を探索する(propagation, uniq無し)
edge(X, Y), edge(Y, Z), edge(Z, X) <=> cycle(X, Y, Z).
| N | 8k | 16k | 32k | 64k | O |
| 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 †
2010-10-22 †
leq †
- クエリ：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 |
| 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より時間がかかるため、こういう結果
2010-10-22 †
CHR bencnmark †
2010-10-21 †
整数比較改めアトム比較の再々試 †
- 条件をより同じにして再々試
- slimhl395/101109/vartest.lmn
- lmntal -O3 --slimcode --hl-opt atomcmp.lmn | slim --hl -
| N | 8k | 16k | 32k | 64k | O |
| 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 |
コンパイラをコミット †
- hyperlinkをjava版コンパイラにコミットした
hyperlinkの出力 †
- 併合されたhyperlinkを標準出力時にrootのファンクタで出力するようにした
2010-10-20 †
hyperlinkからのfindatom 改良版 †
- 整数比較を追試
| N | 10k | 20k | 40k |
| 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 †
leq.pl(CHR)をhyperlinkで書いてみる †
- 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 †
hyperlinkの使い方ページを少し整備 †
hyperlink SLIM側をbranchにコミット †
2010-10-12 †
subversionでエラー †
- Let'sNoteの方からコミットしようとしたら、エラーが出て出来なかった。
2010-10-10 †
hyperlink compiler側をコミット †
- devel/sample/seiji/hyperlink_*.zip
2010-10-08 †
- 班ゼミ
- ファンクタの数が足りなくなるのはどうしよう→とりあえず棚上げ
- コミットしなきゃ
- slimのリーク取り→コンパイラのコミット→slimのコミットの順にやるか
- hyperlink branch
- "branches"を右クリ、フォルダ新規生成
- "trunk"内の"slim"をコピー、"branch"内の"新規生成したフォルダ"を右クリ、貼り付け
2010-10-07 †
hyperlinkを利用したfindatomの最適化 †
- 動くようになったので、一旦測ってみた
- unaryアトム比較
- hlink opt : 今回の実装
| N | 10k | 20k | 40k | 80k |
| 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 |
| hlink opt | 0.02 | 0.04 | 0.09 | ※ |
| chr opt | 0.08 | 0.20 | 0.39 | 0.80 |
- かなり早い
- TODO:膜を貫くリンクに接続している場合のhyperlinkアトムの処理の整備
2010-10-04 †
findproccxt †
- 特定のアトム引数(型付きプロセス文脈)同士が同じ構造を持つことを示す中間命令
- 生成時は適当に挿入、最後に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 †
同名型付きプロセス文脈の分離 †
- --hl系オプションでのみ使用できるように変更 (2010-10-10)
- さらに--hl-optオプションを付けることで、ガードに自動的にhlink型チェックを挿入し、ground対groundの構造比較をファンクタ対ファンクタで済ますようしている
- ヘッドに膜がある場合の操作が抜けていたので修正（2010-09-30)
- これまでは一つのルール内で同名の型付きプロセス文脈は記述できなかったが、以下の様に変更した
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 †
hlinkのコピーと削除 †
- アトム(hlinkアトム)を10000*N回ずつコピー＆削除する
- atom : a(b)
- hlink : a('!1')
| N | 100 | 200 | 400 | 800 | O |
| 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 †
集合の要素を数えるのにかかる時間 †
- (10000個の要素を持つ)集合の要素数をN回数えた時間を計測[sec]
- mem:膜を一つの集合、内部のアトムを集合に属する要素とみなす
- hlink:hyperlinkによって集合を表す
| N | 1000 | 2000 | 4000 | 8000 | 16000 | 32000 | 64000 |
| 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 †
- hyperlink詳細出力用オプションをこっそり追加
その他 †
- conameは現状では要素数に含めるようにしている
- hyperlinkと9/14の変更をローカルのslimにマージ
2010-09-22 †
- 集合内の「要素数」の定義
- !1〜!5までのname(各1個)からなる集合に、coname !-1を与えたとき、この集合の要素数はどうなるんだろうか
- conameは要素として数えるべきかどうか、ちょっと考えた方がいいかも
- memo
- add
- alloc.c/lmn_new_atom(lmn_copy_satomなども含)
- sub
2010-09-18 †
2010-09-17 †
--showrule †
- 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 †
久しぶりにuniq †
- 膜のダンプでrulesetsのポインタではなく、ruleが持つ履歴の内容を全て突っ込む方式に変更
2010-09-10 †
- hyperlink等価性判定のバグを修正
- 「conameを持つname」と「coname」との比較など
- memo : hyperlink等価判定に関わる命令列
- samefunc
- eq/neqfunc
- eq/neqground
2010-09-06 †
- よくよく考えたら、rankはnameの子数であって、要素数とは違う
- 任意の集合に属するhyperlinkの本数(非hyperlinkアトムへの接続箇所)を数えられるようにした
- 予約語用のファンクタが20個くらいあるので、使用できるhlink idは65536個より若干少ない
2010-08-31 †
- TODO：reverseを一時コメントアウトしておく
2010-08-30 †
- lmn_eq_funcにLMN_FUNCTOR_ATTRの場合分けを追加
- 他にも場合分け追加しなきゃいけない所がたくさんある
- 初期化関数で全て初期化してしまっていたのを最適化した
2010-08-20 †
- coname-coname, name-coname間の併合処理を実装
- そろそろhyperlink手動のfindatomと、parserを変更して同じプロセス文脈名が3回以上出現を許す、辺りの検討を
2010-08-19 †
- coname管理方法を変更
- st_get_entry関数を若干修正
2010-08-18 †
- 細かな所でバグが...
- ランクの再計算を修正
- conameの管理方法の変更を検討中、配列よりハッシュ表の方がいいかも
2010-08-13 †
- 反転処理：リンクの繋ぎ換えでおかしかったところを修正
2010-08-12 †
LMN_FUNCTOR_ATTRと型検査の兼ね合い †
- newとintなどを組み合わせるとおかしくなる
- そのうちやる
2010-08-10 †
2010-08-06 †
要素数の取得 †
new制約 †
name-conameの反転 †
2010-08-05 †
hyperlink生成 †
2010-08-03 †
ボディで併合できるようにした †
2010-07-30 †
論理変数の状態 †
- 値や属性を持つ
- 他の変数と併合される
Attribute variable †
- 属性の実装はどうやっているのか、ちょっと調べてみる
2010-07-29 †
conameのunify †
- 異なる値を持つ変数同士の併合は失敗
- conameのみで存在することは無い、とするとconameの生成はnameありきの構文にしたほうがいいのか
2010-07-23 †
hyperlink †
- name<->name関連機能は大体実装した...か？
- 木で集合を管理
- rankやパス圧縮を用いて多少は効率良いようにしてみた
- 次はco-name<->name関連をぼちぼちと
co-name †
- 必要そうな操作と、構文妄想
- 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の属性を扱う構文 †
- (!-1 > 3), (!-2 < 5)というco-name!-1,!-2を併合する
- andとorの区別をつけられるようにする必要はあるか？
- 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 †
2010-07-15 †
name, coname †
- 名前の決め方
- name : "!" + 0,1,2,...
- coname : "!!" + (nameから求めたファンクタid)
- 実装方法案
- 対応関係
- ハッシュテーブルで関係を保持（親-->子、子-->親）
- 記法案
- name-->coname取得
a($h) :- coname($h) | a(
hlink生成 †
- 本命：bodyで生成
- 次善策のnew制約
hoge, hoge.
hoge :- new($h) | a($h), b($h).
*--> a('!0'), b('!0'), a('!1'), b('!1').
併合 †
memo †
- hlinkの実装方法
- SLIMではガードでsymbolアトムを生成出来るようになっていなかった
- 通常の(symbol)アトムとして名前をつけるか
- データアトムの一種とする(単なる数値)か
2010-07-09 †
JFlex.jarとjava_cup.jar †
- java_cup.jarの方はsrc/compiler/parser/に移動して実行しないと、parser.javaが正しいディレクトリに生成されないみたい
"=="演算子 †
- '=='を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 †
- 併合はどういう状況で使うだろうか
- $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 †
hlink型 †
- 基本的には(プログラム上は)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検査)の役割も持つ
併合 †
- システムルールセットで行なう方法、演算子"=="
- ルール適用のタイミングで、ユーザの思い通りにいかないことがある、却下
- ボディで行なう方法、演算子は"=="にしようかな
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) †
/* $h1, $h2どちらか一方にhlink(unary)チェックを施す */
a($h1), b($h2) :-
hlink($h1), $h1==$h2 | a($h1), b($h2).
- 等価判定(optimize)は中間命令列を変更しないでSLIM側だけで可能かな？うーんよく考えないと
hyper link for nd †
- とりあえず放置したい、やるなら状態ごとにファンクタの親子関係管理をさせないといけないかな
2010-07-07 その２ †
2010-07-07 †
hyper link atom 生成 †
- コンパイラ側
- 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?のように親子関係を持たせるようにした
- memo
- Instruction.java
- GuardCompiler?.java
2010-07-05 †
- memo
- hylink atomはint型じゃないから==の両引数に指定しても大丈夫
2010-07-01 その2 †
班ゼミ †
- hylinkの生成はガードで
- 一度考えて、おかしいと思ってたけど、確かに+や-をガードでしてるか
2010-07-01 †
hyper link †
- (再掲)
- hylinkを新規生成
- 2つのhylinkの等価性判定
- 指定したhylinkの出現の列挙
- 指定されたhylinkに繋がるアトムの(効率的)探索
- hylink同士の併合
- 金曜から進んだところまで
- 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') とか?
2010-06-28 †
ハイパーリンク †
- 5.全ての膜に作用するシステムルールセットを書いてみた
2010-06-25 †
ハイパーリンク †
- 上田先生との個別ゼミを個人的に整理してみる
- 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)
- システムルールセット的なもので併合元のアトムを併合先のアトムに書き換える
- 最短の実装を考えたとき、まずどれをやるか
2010-06-24 †
hylink、SLIM側のみでやる場合 †
- 実現方法がいくつかある(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用の命令列としてまとめてしまう
- 新データ構造の追加
その他 †
- 気が早いが、!記法を入れるなら参考に
- 中間命令列眺める
- 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], []]
- ルール文脈
- ヘッドにルール文脈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 †
時間計測用callback関数 †
- &ref(): File not found: "timer.c" at page "研究日誌とうめき";
- 追加の仕方：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 †
uniq for nd †
- 膜のダンプ(--nd)に対応した、気がする
- 膜が持つルールセット配列をバイナリストリングに書き込んでいる
- mem-encに対応させるなら履歴表の中身を全部書き込まないといけないかも
2010-06-21 †
- 臨時班ゼミ
- hyper link、flatLMNtalを対象にする方向で
2010-06-20 †
2010-06-16 †
2010-06-15 †
ゼミ発表終了 †
- ありがとうございました。
- 膜をhlinkとすると、どこかの階層に属さなければならないのでは
- どこの階層にも属さない、かつ自由に参照できるような何かがあるといい
- ホントはint型とかもどこかに属していることは望ましくない
- "-"の無いハイパーリンクはあんまいらないんじゃ?
- ノード番号があるグラフは本質的にうれしくない
- 抽象化のためにはいいかもしれない
- 最適化、という側面からならもっと処理系内部をいじったほうが効果出る
- ハイパーリンクやる意義をもうちょっと広く深く考えなければ
2010-06-11 †
昨日の班ゼミメモ †
- 多対多、という表現はなんかおかしい
- +の方をデフォルトにして文字数減らすとか
- 階層無視で作用するルールが無い
- ルートからのプロキシアトムのツリーを作るとか
- 集合演算の機能があんまりない、膜内のアトム数が分かるとか
2010-06-10 †
hyperlink : 妄想 †
- 同じリンク名の3回以上の出現を許す、とする
- =内部的には軽い膜でhyperlinkを表現している、とする
- この二つの表現を分けたほうがいいのでは
- a.多数と多数の接続関係(多対多)
- b.多数が一つの共通データを参照している(多対一)
- bはどちらかというと共有変数的な感じ、とりあえずデータの変更方法は後回し
- まずは現状の(flatな)LMNtalでできそうなことだけ
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 †
- 軽い膜を入れるとすると
- +/-アトムのみ持てる
- 子膜、ルールは持てない
- 多階層から(等しく)参照できる
- グローバル変数的な、プロキシアトムを調節することでうまくいかないか
- (なんらかの形でdataを持ってるとして)同じdata持つもの同士をどう扱うのか
- 同じなら結合させるのか、
- 軽い膜自体の管理方法に大きく関わってくる
- 参照カウント(+アトムの数)を利用
- パラメタ付けによる入出力、共有/非共有の表現
- 上田先生の論文(これの19番64枚目あたり)にあるけども
2010-06-08 †
2010-06-04 †
- 無かった理由として、膜を使えば書けちゃうから必要ないでしょ、がある
- 今の膜のままじゃいけない理由をはっきりさせておく
- リンク同士の節点に使うには重い
- どの階層からも等しく参照できるような(グローバルな)ことは出来ない(やりにくい？やろうと思えば出来そうかな..)
- 最初はフラットな場合を想定した方がいいんだろうけど、
- (LMNルールで)同じ要素を持つ膜を結合する時にO(膜の数^2)になるんじゃ？
ubuntu : 起動できない †
- 更新したら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 †
班ゼミにて †
- やっぱり膜をユニオンする、あるいはそれに相当する何かがあったほうがいいのではないか
- 普通の膜よりも軽い膜、あるいはハイパーリンクがほしいかもしれない
- どういうルールになったらエレガントなのか、ちょっと書いてみるといいかも
- 見た目は変数3つ許すけど、実は軽い膜を介しているようなシンタックスシュガーはあるとうれしいかも
2010-06-03 †
CHR : dijkstra(optimize) 測りなおし †
- クエリはRand4 (edge=node*4)
| node | 128 | 256 | 512 | 1024 | 2048 | 4096 |
| 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 | | |
膜による擬似共有変数について(昨日の続き) †
- 昨日は初期グラフを生成する時に、既に変数(膜)とアトムが結びついた状態で生成していた。が、実際の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のエンコードでどうしても膜を使ってしまう例 †
- 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 †
実験 : LMNtal vs CHR (整数の比較) †
- 同じ値を持つアトムの組を見つけて消す
- 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) | .
- クエリ(計算量最悪になるように)
%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 | |
| 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 †
:- chr_option(Option, Value).
CHR : その他 †
- ERROR: =</2: Arguments are not sufficiently instantiated
- findall_constraint/3 (shceduling.pl)
2010-06-01 †
CHR : optimize option †
ヒープ †
2010-05-28 †
CHR : Union-Find algorithm †
- とりあえず問題の内容をもう一度理解
- 単純なもの、最適化されたものをlmnにエンコード
memo †
2010-05-27 †
CHR : dijkstraのtype/mode †
- 論文の方ではtype/modeの有無で計算量が変化しているが、手元のSWIprologでは動いているのかよく分からない
- dense_intを使うと実行時間が変わる（逆に遅くなったけど）結果があったから、何らかの影響は出ているようだ、でも謎
- 他にはUnion-findでもIndexが使われているようだ
CHR : partner(passive)constraintの探索 †
- 共有の変数をうまく利用してパートナーの探索を早くしてほしい、誰かに
2010-05-26 †
OpenOffice?:対数グラフ †
2010-05-24 †
dense_int †
- ハッシュベースの制約ストアとは別に、配列形式の制約ストアを用意し、そこにdense_int型でインデックス付けして格納する
- ハッシュの計算回数を減らせる、衝突を避けることができる
- インデックスに使われる整数の個数が[0,n]間である程度多い(濃い=dense)場合に効果を発揮する、らしい
- Indexing tequnicとの関係をもう少し見たい
- chapter 9 join orderingも参考程度に
ほか †
- prologのマッチングはどうなってる？
- edge(X,Y)形式だと計算量はどうしても多くなる
2010-05-19 †
callback : graph_gen_nocycle_uniq †
- 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 †
2010-05-17 †
prolog : setof †
- 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)だったので、特別変わった実装じゃなさそう？
2010-05-14 †
CHRのlistdom.pl †
- X lt Y って単にmax(X)<max(Y)なんだろうか、少なくとも実行結果はそうみえる
- だとしてもなんだかちゃんと書かれてない気がするな
UNYOのバグ？（既に報告されていた） †
- 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).
[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 †
callback関数 : integer_int2float †
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 †
delete([1,3,2,3],3,X) ----> X = [1,2].
班ゼミ †
- 一つの例題をもう少し細かく見てみよう
- データ表現やルールの工夫なんかでこれ以上改善できないというところまでもっていく
2010-05-12 †
2010-05-11 †
CHR : \+ : andの否定? †
2010-05-09 †
listdom.pl : エンコード完了？ †
2010-05-08 †
listdom.pl †
lt : less than
le : less than or equal
ne : X ne Y, Y::[*]で*からXを取り出す?
2010-05-07 †
callback関数 : graph_gen †
- (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(!) †
2010-05-07 †
callback関数を触ってみた †
こんなのがあったのか、コロン記法？ †
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)).
- チルダとか_とかも試してみたけど、こういう風に特別扱いされているものは見当たらなかった
- eclipse 行番号の表示
- 「ウィンドウ」>「設定」>「一般」>「エディタ」>「テキスト・エディタ」
- 「行番号の表示」にチェック
2010-05-06 †
CHR encoding †
- 制約プログラミング的な例題をencodeページに貼っ付ける
- やりかけ
2010-05-03 †
Floyd-Warshall法の解説を読んでみた †
- あのアルゴリズムをそのままLMNtalで書けるのか
- CHR文献内のベンチマークにたまに"FLOYD-WARSH(N)"てのがある、よく調べる
2010-05-02 †
ubuntu kernel panic! †
2010-04-27 †
CHR encoding †
- CHR encodingのページを整形してみたが、ううむ
- CHRの文献をあさっていたら、いくつか新しい例題を見つけたのでちょっと書いてみる
- 輪読を忘れないようにしないと
2010-04-26 †
- とりあえず作ってみたものの、どういうレイアウトにしたらいいのか悩む
- まだまだ少ないが、突貫でまとめてみた
- CHRプログラムに与えるクエリをどうするかでいつも悩むのはなんとかならないものか
ほか †
- dijkstraは重みが非負数の場合のみ使える、O(V^2)
- Bellman-Fordは非負数でもok、O(V^3)
- Warshall-Floydは非負数ok、でもサイクルに非負数があるとダメ、O(V^3)
2010-04-25 †
SLIM他言語インタフェースドキュメント †
system_rulesetとcallback †
2010-04-24 †
graph_generator.c †
- 作ってみた、後悔はしていない
- 地味に重み付け有り無しや、出力先を選べたりする
- なぜ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 †
2010-04-23 †
Canon事業所見学会 †
- 開発職でも要素技術研究的な仕事もある、というのはどこの事業所も同じらしい
- Canon合格者のメーリス担当になった。笑
2010-04-22 †
Union Find †
- エンコードしてみた、クエリとして変数は与えられないけど
最短経路問題 †
- グラフ上の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)より若干低いくらいになるはず
- なってた
| 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プログラミング、気になること †
- CHRの例題には「処理系の実装方法的にルールの適用順序はこうなるはず」を考慮してプログラミングしているものが多い気がする(というか文献とかで明示している)
- 例えば、次の2つのルールは上から順に評価される
- itemがたくさんある中にfindminを生成するとfindmin@が一通り実行され、最後にfoundmin@が実行される
- なんかずるくないか、別にitemがあってもfoundmin@が実行されてもいいはずでは
- それともLMNtalでそういう書き方しないのは馬鹿正直すぎるのだろうか
findmin @ findmin, item(I,K,_,0,_) ==> min(I,K).
foundmin @ findmin <=> true.
2010-04-21 †
dijkstra のエンコード終わった †
その他 †
- 村岡・後町を慰める(?)会
- 生 * 21杯 / 3人 = 7 [杯/人]
- 酔いって指数関数的にくるよね
2010-04-20 †
dijkstra's algorithm with F-heap †
2010-04-19 †
chr_path_N †
- 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本目のルールで消される)
例題増やし †
- ダイクストラ
- フィボナッチヒープを用いた最適化の論文、読んでみてる
- あとはUnion findとかがいいかな
2010-04-18 †
CHR book †
2010-04-17 †
Propagationとuniqの違い †
- 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 †
ubuntuでchrを動かせた †
- 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
- バイナリの方からchrフォルダ,chr.plを持ってくる
- Sourcesに対して再度の1.の./configure以降を実行
2010-04-15班ゼミ後 †
次週までに †
- chr_path.lmnの測定、オーダー計算などもろもろ
- benchmark setの用意
2010-04-15 †
-班ゼミ用：どんな例題を早くしたいのか †
- ロックフリーで実装
- 最初は0or1価のアトムやリストを扱う例題（膜無しで）
- CHR的な何か
- NESLの例題はどうか
ubuntuでlibrary(chr)が呼び出せていない †
2010-04-14 †
ubuntu †
$ uname -a で32or64ビット版か見分けられる
Let's Noteが直った †
- パナソニック修理工房、インバータの故障(有料)だったけど、液晶パネルまで交換(無料)してくれた、出来る
2010-04-13 †
SLIMのrule trialにかかる時間(通常実行) †
- time_optimized_slim
- 手持ちの例題でざっと取ってみた、編集中
- あっているんだろうか
2010-04-09 †
- 先生からKLICやらCHRを使える環境をどこかに用意しようとのお話
- paveにはKLICが入っていた、でもうまく動かなかった
- NIOLOに入れてみようとした
- 選択肢選んでいったら、途中で無限ループしたので今日は放置
- でもgochoのubuntuではインストールまではうまくいってた、パッチ当てればうまくいく？
- NESLの論文の読み飛ばしてたところを思い出した、明日読む
- やっぱりクイックソート的な例題をやってみたいとは思う
2010-04-08 †
- M2ページ作ってみた [#f6ca3e7f]
- ubuntuを新しいPCにインストールしてみた [#e4d9ba88]
- KL1を動かしてみる [#hbc9ed25]
- KLICの実装について
- Inside KLIC（KLICのHPから）日本語
うめき †
2010-08-05 †
- 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 ( ｀з´)
2010-04-09 †
- 春だ
- 馬場駅周辺が色々変わっててびっくり
- 就職活動終了、研究がんばらないと
- 山名先生は優しかった、文面がhiroshiと同じだったが、でも優しかった
2010-04-08 †
experiment_LATEST_slim428.zip