tag:blogger.com,1999:blog-77621049831572653882024-03-14T09:12:55.717+09:00low codeThink about science.koshimoto, hiroohttp://www.blogger.com/profile/09141449095639790908noreply@blogger.comBlogger15125tag:blogger.com,1999:blog-7762104983157265388.post-27802002886870043542008-07-01T12:58:00.000+09:002008-07-01T13:00:53.745+09:00滅却すべし、滅却すべし、滅却すべし続きは<a href="http://ratiwo.blogspot.com/">Web</a>でkoshimoto, hiroohttp://www.blogger.com/profile/09141449095639790908noreply@blogger.com0tag:blogger.com,1999:blog-7762104983157265388.post-41510966519644674122008-02-22T19:35:00.003+09:002008-02-22T19:47:06.792+09:00Customizing on ASUS Launcher the EeePC's WM easy modeapt-getでウィンドウマネージャを追加すると自由にカスタマイズが可能です、では面白くないどころか、折角の軽快さが失われてしまいます。そこで、必要最低限の修正で利便性の向上を図ってみます。とか何とか言って<a href="http://eeesite.net/2007/11/add-start-menu-to-eee-pc-and-customize.html">ここ</a>のパクリです。<br /><br />まずFile Managerからターミナルの起動がウザくて仕方ないです。これはCtrl+Alt+Tでショートカット可能。個人的にはこれで十分ですが、<br /><br />Easy Modeにスタートメニューをくっ付ける。<br /><ol><br /><li>ターミナル上げる。</li><br /><li>> mkdir /home/user/.icewm</li><br /><li>> cp /etc/X11/icewm/preferences /home/user/.icewm/</li><br /><li>.icewm/preferencesのTaskBarShowStartMenuを0から1に変更。</li><br /><li>X Windowを再起動します。</li><br /><li>Ctrl+Alt+BSでスタートメニューが現れます。</li><br /></ol><br />あとは適当に設定を編集してメニューをカスタマイズします。koshimoto, hiroohttp://www.blogger.com/profile/09141449095639790908noreply@blogger.com0tag:blogger.com,1999:blog-7762104983157265388.post-46876936706619168862008-02-19T02:19:00.006+09:002008-02-21T13:31:57.218+09:00Localization on Eee PC<a href="http://eeepc.asus.com/global/">ASUS Eee PC</a><br />この手の超軽量ノートはガジェット好きのギーク魂をくすぐるものの、ほとんどの場合において中途半端な完成度で飽きてしまうのですが、それでもついウッカリと手を出さずに居れないのもまた事実。中文版の黒を入手したのでl10nの覚書を交えて簡単にレビュー。<br /><br />まずこのサイズのノートにしては満足のいく鍵打感、かつASCII配列。もうこの時点で、私個人の費用対効果は合格点だと言えます。かつて過ぎ去っていったガジェット達も、多くがこの辺りに敗因がありますので。<br /><br />ゼロスピンドルかつ小型。いやMacBookAirは当然あこがれるけど、あまり大きなバッグを持たない私にとっては薄さより小ささ、軽さが重要。これまた合格点。<br /><br />ちなみに国内版はJIS配列かつWindows搭載というF**kin' shitな仕様ですが、それが嬉しい人にとってはまたやはりプラスですね。ヨドバシの店頭で触った限りで言えば、わりと軽快に動作していました。メモリは換装されていない状態です。<br /><br />では中文版Xandrosの日本語化の流れ。実態はDebian Linuxに皮被せたような代物ですから、問題は読めない漢字の海の中からターミナルを起動する事、その一点だと言えるでしょう。正直に申せば、先人のまとめを見るまで分かりませんでした。GRUBでスタンドアロンに入ろうかと思ったくらい。なのでほとんど<a href="http://www.potech.jp/pote/archives/2007/10/30-024620.php">ここ</a>を参照。<br /><br /><ol><br /><li>左から二つ目のタブを選択し、なんとか管理員と書かれたアイコンをクリック。</li><br /><li>FileManagerが起動するので、Ctrl-Tでターミナルを起動。</li><br /><li>> sudo su -</li><br /><li>> cd /etc/apt; vi sources.list</li><br /><li>deb http://ftp.jp.debian.org/debian/ etch main contrib non-free を append し保存。</li><br /><li>> apt-get update</li><br /><li>> apt-get install ttf-vlgothic いやまぁフォントはお好きなのをどうぞ。</li><br /><li>> dpkg-reconfigure locales</li><br /><li>メニューで ja_JP.EUC-JP EUC-JP, ja_JP.UTF-8 UTF-8 を選択。</li><br /><li>> apt-get install emacs</li><br /><li>> apt-get install ddskk scim-skk</li><br /><li>再起動後は Ctrl-SPC で日本語入力が可能です。</li><br /></ol><br /><br />他にも色々と入れたいところですが、容量は割と小さいので目的を絞っておくことを忘れないで下さい。ちなみに私は gcc, ghc6, swi-prolog, latex を入れたわけですが。<br /><br />備忘録代わりに Emacs の haskell-mode の設定について。まず<a href="http://www.iro.umontreal.ca/~monnier/elisp/haskell-mode-2.4.tar.gz">ここ</a>からファイルを wget か何かして来て、適当に展開。設定ファイル .emacs に以下を追記。<br /><pre><br />(load "~/haskell-mode-2.4/haskell-site-file")<br />(setq load-path (cons "~/haskell-mode-2.4" load-path))<br />(setq auto-mode-alist<br /> (append auto-mode-alist<br /> '(("\\.[hg]s$" . haskell-mode)<br /> ("\\.hi$" . haskell-mode)<br /> ("\\.l[hg]s$" . literate-haskell-mode))))<br />(autoload 'haskell-mode "haskell-mode"<br /> "Major mode for editing Haskell scripts." t)<br />(autoload 'literate-haskell-mode "haskell-mode"<br /> "Major mode for editing literate Haskell scripts." t)<br />(add-hook 'haskell-mode-hook 'turn-on-haskell-decl-scan)<br />(add-hook 'haskell-mode-hook 'turn-on-haskell-doc-mode)<br />(add-hook 'haskell-mode-hook 'turn-on-haskell-indent)<br />(add-hook 'haskell-mode-hook 'turn-on-haskell-ghci)<br />(setq haskell-literate-default 'latex)<br />(setq haskell-doc-idle-delay 0)<br /></pre><br /><br />そのままでも非常によく出来たモードなのですが、以下のように手を入れます。これらの修正は<a href="http://d.hatena.ne.jp/n9d/20071216/1197794904">ここ</a>を参照です。<br /><pre><br />-- haskell-site-file.el<br />+ (autoload 'inferior-haskell-load-and-run "inf-haskell" "\<br />+ Pass the current buffer's file to the inferior haskell process.<br />+ If prefix arg \\[universal-argument] is given, just reload the previous file.<br />+<br />+ \(fn &optional RELOAD)" t nil)<br />(autoload 'inferior-haskell-type "inf-haskell" "\<br /><br />-- haskell-mode.el<br />- (define-key map [?\C-c ?\C-l] 'inferior-haskell-load-file)<br />+ (define-key map [?\C-c ?\C-l] inferior-haskell-load-and-run)<br /></pre><br /><br />このモードを使い始めた時に思う勘違いにインデントがありますが、これはTABを押すごとに候補となるインデントをローテートします。是非たぶたぶしてやって下さい。<br /><br />あとコンパイルエラー時のカーソルの飛び先をカレントウィンドウにする場合は、<a href="http://d.hatena.ne.jp/r-west/20070409/1176138107">こちら</a>を参照して haskell-ghci-gen-load-file を次のように書き換えます。<br /><br /><pre><br />-- haskell-ghci.el<br />(defun haskell-ghci-gen-load-file (cmd cd)<br /> (save-excursion (haskell-ghci-go cmd cd))<br /> (let ((haskell-file-buffer (current-buffer)))<br /> (pop-to-buffer haskell-ghci-process-buffer)<br /> (goto-char haskell-ghci-load-end)<br /> (if (re-search-forward<br /> "^Ok, modules loaded" nil t)<br /> (progn (goto-char (point-max))<br /> (recenter 2)<br /> (message "There were no errors.")<br /> (pop-to-buffer haskell-file-buffer))<br /> (goto-char haskell-ghci-load-end)<br /> (haskell-ghci-locate-next-error))))<br /></pre>koshimoto, hiroohttp://www.blogger.com/profile/09141449095639790908noreply@blogger.com0tag:blogger.com,1999:blog-7762104983157265388.post-10997014788435968392007-11-10T09:02:00.000+09:002007-11-11T02:31:23.411+09:00setitimer on leopardPOSIX系OSでプロファイラなどを作る際にsetitimer関数を利用します。以下のようにするとタイマを設定することが出来ます。<br /><pre><br />struct itimer value, ovalue;<br /><br />value.it_interval.tv_sec = 0;<br />value.it_interval.tv_usec = 1;<br />value.it_value.tv_sec = 0;<br />value.it_value.tv_usec = 1;<br />if (setitimer(ITIMER_PROF, &value, &ovalue) != 0)<br /> { error_code; }<br /></pre><br />ここで設定した秒数ごとにSIGPROFシグナルが投げられますので、プロファイラをsigactionでSIGPROFに設定しておきます。<br /><pre><br />struct sigaction old;<br />struct sigaction new;<br /><br />memset(&new, 0, sizeof(new));<br />new.sa_handler = プロファイラ関数;<br />if (sigaction(SIGPROF, &new, &old) != 0)<br /> { error_code; }<br /></pre><br />ところでプロファイラを起動する間隔ですが、これは先ほど設定したSIGPROFを投げるインターバルに依存しますから、上の例のように気軽に1マイクロ秒とかには出来ないわけです。基本的には。でもLinuxなどでは適当な値に丸められるので、上記のようなコードが放置されるケースが見受けられます。<br /><br />さて先頃リリースされたLeopardにコレといった不具合も出てないようだったので喜んでインストールした私です。そして色々とソフト入れてて上の問題にぶつかったわけです(SWI-Prologでしたが)。なんとLeopardは1マイクロ秒でもタイマが起動しちゃようです、ビビりました。そんな間隔で起動されたら他のプロセスにちっともスイッチされなくなります。そういうわけなので統計クロックから適切な値を設定してやるようにしましょう。<br /><pre><br />value.it_interval.tv_usec = 1000000/(int)sysconf(_SC_CLK_TCK);<br /></pre>koshimoto, hiroohttp://www.blogger.com/profile/09141449095639790908noreply@blogger.com0tag:blogger.com,1999:blog-7762104983157265388.post-19592355462144121252007-11-06T13:43:00.001+09:002007-11-06T15:00:52.215+09:00Prolog (6)なんかunfoldの定義を少し間違って記憶してたように思います。Haskellでリスト用の定義を見るとこんな感じ。<br /><pre><br />unfold p f g x = <br /> if p x <br /> then [] <br /> else f x : unfold p f g (g x)<br /></pre><br />Prologでは前回示したようにunfoldの外のゴールでバックトラック制御を行えますから、終了判定は要らないですね。アレはアレで使い道はあるのでunfold2とかにリネームしておいて、リスト用unfoldlを正しく書くとこんな感じですかね?<br /><pre><br />% unfoldl/5<br />unfoldl(Fn1, _, X, L, L1) :-<br /> G =.. [Fn1, X, Y],<br /> call(G),<br /> append(L, Y, L1).<br />unfoldl(Fn1, Fn2, X, L, L2) :-<br /> unfoldl(Fn1, Fn2, X, L, L1),<br /> G =.. [Fn2, X, Y],<br /> call(G),<br /> unfoldl(Fn1, Fn2, Y, L1, L2).<br /><br />% make_list/2<br />make_list(X, [X]).<br /><br />?- unfoldl(make_list, inc, 1, [], L), length(L, 100), foldl(plus, 0, L, Sum).<br />L = [1, 2, 3, 4, 5, 6, 7, 8, 9|...],<br />Sum = 5050<br /></pre><br />ただHaskellだと型システムのチェックが働く部分や、カリー化された関数が書き易い部分が組み合わさって強力なfold/unfoldですが、Prologだとその辺りでメリットが無いので正直なところ使い勝手は微妙です。<br /><br />ところで最近都内でProlog勉強会をやっています。ご興味をお持ちの方が居られましたら是非ご一報を。隔週で長期的にやっております。<br />次回開催概要<br />場所: 中目黒GTタワー<br />日時: 11/10(Sat) 14:00-<br />内容: Prologへの入門 4-5章<br />連絡: hiro.kosh@gmail.comkoshimoto, hiroohttp://www.blogger.com/profile/09141449095639790908noreply@blogger.com0tag:blogger.com,1999:blog-7762104983157265388.post-28240286750195708162007-11-04T02:26:00.000+09:002007-11-04T02:59:18.540+09:00Prolog (5)前回に引き続きリスト系のユーティリティ述語の紹介です。<br /><br />fold(l/r)を定義したら当然のことですがunfoldが定義したくなりますね?幸いにもPrologはバックトラックがありますから、特に遅延評価のための仕組みを用意せずとも、Haskellのようにunfoldを書くことが出来ます。しかしその前にもっと細かいユーティリティを定義しておきます。<br /><br />まずはリストの最後の要素を取得するlast/2です。<br /><pre><br />% last/2<br />last([X], X).<br />last([_|R], X) :- last(R, X).<br /><br />?- last([1, 2, 3], X).<br />X = 3<br /></pre><br /><br />続いてリストの最後以外の部分を取得するunlast/2です。<br /><pre><br />% unlast/2<br />unlast(L, R) :-<br /> last(L, Y),<br /> append(R, [Y], L).<br /><br />?- unlast([1, 2, 3], L).<br />L = [1, 2]<br /></pre><br />個人的にはこの述語なんか簡単で、如何にも宣言的な書き方かなぁと思っています。二つ目のゴールで最後の要素を後ろに付けたリストが元のリストだと宣言してるわけですね。<br /><br />さてリストのN番目の要素を取得するnth/3はこんな感じ。<br /><pre><br />% nth/3<br />nth(1, [X|_], X).<br />nth(N, [_|R], X) :- N > 1, N1 is N - 1, nth(N1, R, X).<br /><br />?- nth([1, 2, 3], 2, X).<br />X = 2<br /></pre><br /><br />ところで引数の並びをどうするかというのは悩みどころです。特に高階述語を書く場合は、与える引数の位置が重要ですからね。そこで自分の中でルールを決めておくという手もあるのですが、順番を変えたい場合はチェインというのを定義してやります。<br /><pre><br />% last1/2<br />last1(X, L) :- last(L, X).<br /></pre><br />上のlast1/2ではlastを呼び出すことしかしません。ただし引数を並び替えています。このようにエイリアスのような役目をする述語を(慣用的に)チェインと呼びます。<br /><br />それではunfold/4を定義してみましょう。<br /><pre><br />% unfold/4<br />unfold(Fn, X, L, L1) :-<br /> last(L, Y),<br /> G =.. [Fn, X, Y, Y1],<br /> call(G),<br /> append(L, [Y1], L1).<br />unfold(Fn, X, L, L2) :-<br /> last(L, Y),<br /> unfold(Fn, X, L, L1),<br /> unfold(Fn, Y, L1, L2).<br /><br />?- nth(10, L, X), unfold(plus, 0, [1], L).<br />L = [1, 1, 2, 3, 5, 8, 13, 21, 34|...],<br />X = 55<br /></pre><br />出来ました。ちなみにnth/3を使っている理由はもうすでにお気づきですね?それではunfold/4単体でフィボナッチ数を計算してみましょう。<br /><pre><br />?- unfold(plus, 0, [1], L).<br />L = [1, 1] ;<br />L = [1, 1, 2] ;<br />L = [1, 1, 2, 3] ;<br />L = [1, 1, 2, 3, 5] ;<br />...<br /></pre><br />ご覧の様に、別の解を要求する度にリストが伸びて計算を行っていきます。上の例ではnth/3でリストの幾つ目の要素が欲しいのかを条件として与えていますから、それを満たすリスト長になるまでバックトラックを起こして次の値を計算しているわけです。koshimoto, hiroohttp://www.blogger.com/profile/09141449095639790908noreply@blogger.com0tag:blogger.com,1999:blog-7762104983157265388.post-25049307858082118492007-11-01T18:58:00.000+09:002007-11-01T19:32:34.040+09:00Prolog (4)Prologは高級言語に属すると思うのですが、昨今のプログラミング言語を見るとLLは言うに及ばずc++でもSTLという便利なライブラリが付いてきます。最もそういったユーティリティはPrologでは大体が簡単に作れるものなので、マイライブラリを構築している人が大半かと思われます。とりあえず定番どころからそういったものを晒して行く事にします。<br /><br />リストオブジェクトが使えるとプログラマの本能は、要素に対する関係を記述してやりたくなります。まずは個々の要素と関係を満足する要素のリストを作るmapです。<br /><pre><br />% map/3<br />map(_, [], []).<br />map(Fn, [X|Xs], [Y|Ys]) :-<br /> G =.. [Fn, X, Y],<br /> call(G),<br /> map(Fn, Xs, Ys).<br />% inc/2<br />inc(X, Y) :- Y is X + 1.<br /><br />?- map(inc, [1,2,3], L).<br />L = [2,3,4]<br /></pre><br /><br />続いて関係を満足した要素だけからなるリストを作るfilterです。<br /><pre><br />% filter/3<br />filter(_, [], []).<br />filter(Pr, [X|Xs], [X|Ys]) :-<br /> G =.. [Pr, X],<br /> call(G),<br /> filter(Pr, Xs, Ys).<br />filter(Pr, [_|Xs], Ys) :-<br /> filter(Pr, Xs, Ys).<br /><br />?- filter(number, [a,1,b,2,3,4], L).<br />L = [1,2,3,4]<br /></pre><br /><br />さらに一般的な高階関数fold(l/r)はこんな感じです。<br /><pre><br />% foldl/3<br />foldl(_, X, [], X).<br />foldl(Fn, Y1, [X|Xs], Y) :-<br /> G =.. [Fn, Y1, X, Y2],<br /> call(G),<br /> foldl(Fn, Y2, Xs, Y).<br /><br />?- foldl(plus, 0, [1,2,3,4], Sum).<br />Sum = 10<br /><br />% foldr/3<br />foldr(_, X, [], X).<br />foldr(Fn, Y1, [X|Xs], Y) :-<br /> foldr(Fn, Y1, Xs, Y2),<br /> G =.. [Fn, X, Y2, Y],<br /> call(G).<br />% minus/3<br />minus(X, Y, Z) :- plus(Z, Y, X).<br /><br />?- foldr(minus, 0, [1,2,3,4], Q).<br />Q = -2<br /></pre><br /><br />ところで上で出てきたオペレータに入門書では見慣れないものがありますね。=..って奴です。コイツは複合項(Compound TermあるいはStructureとも呼ぶ)を作成する演算子(正確には(=..)/2で自由変数とリストが引数)です。call/1は引数として渡されたゴールを実行しますので、それを用意しているわけです。<br /><pre><br />G =.. [Fn, X, Y].<br />G = Fn(X, Y)<br /></pre><br />処理系によっては次のようにしてcallを使えるものもあります。<br /><pre><br />call(Fn, X, Y). % Fn(X, Y) to be executed.<br /></pre>koshimoto, hiroohttp://www.blogger.com/profile/09141449095639790908noreply@blogger.com0tag:blogger.com,1999:blog-7762104983157265388.post-65245624257659794072007-10-29T10:49:00.000+09:002007-10-29T10:57:14.950+09:00.emacs (3)Emacsでc++のソースを編集すると名前空間がインデント付いてとても嫌なので。あとヘッダファイルは標準ではc-modeなのでこれをc++-modeに加える。<br /><pre><br />(setq auto-mode-alist<br /> (append '(("\\.h$" . c++-mode))<br /> auto-mode-alist))<br />(add-hook 'c++-mode-hook<br /> '(lambda ()<br /> (c-set-style "gnu")<br /> (c-set-offset 'innamespace 0)))<br /></pre><br />ちなみにGNUスタイルは個人的には好きなのでそのまま。ブロックインデント時にカーリーブラケットの有無でインデントが変わるのは視認性が高まって良い。koshimoto, hiroohttp://www.blogger.com/profile/09141449095639790908noreply@blogger.com0tag:blogger.com,1999:blog-7762104983157265388.post-33021585339111531532007-10-25T07:37:00.000+09:002007-10-25T08:00:13.379+09:00asdf on windowsCommon LispにはASDFという便利なパッケージツールがありますが、利用法が基本的にUNIXベースのものとなっているのでWindows上で動かす場合に困りました。<a href="http://www.cliki.net/asdf#clispWindows">CLikiを見ると対処法</a>があったのでメモしておきます。(clisp用です、というかWindows上のSBCLはまだ挙動が怪しいです。)<br /><br /><ol><br /> <li><a href="http://common-lisp.net/project/asdf/">asdf.lisp</a>を取得し適当なディレクトリに置く。</li><br /> <li>.asdファイルを格納するASDFディレクトリを用意する。</li><br /> <li>ダウンロードしたパッケージの中の.asdファイルへのショートカットを作成する。</li><br /> <li>ショートカットを先のASDFディレクトリに入れる。</li><br /> <li>ショートカットファイルの名前から ~へのショートカット を削除する。</li><br /> <li>(user-homedir-pathname)で取得出来るディレクトリに.clisprc.lispファイルを以下の内容で作成する。<br /><pre><br />(load "上で取得したasdf.lispへのフルパス")<br />(push "ASDFディレクトリへのフルパス" asdf:*central-registry*)<br /></pre></li><br /> <li>後は処理系を再起動後に(asdf:oos 'asdf:load-op 'hoge)でhogeパッケージをロード可能。</li><br /></ol>koshimoto, hiroohttp://www.blogger.com/profile/09141449095639790908noreply@blogger.com0tag:blogger.com,1999:blog-7762104983157265388.post-21646467303881135722007-10-14T05:00:00.000+09:002007-10-14T05:07:41.432+09:00OpenGLUT on MacOSX 10.4GLUTの実装はフリーのものが色々あります。MacOSXにはGLUT frameworkも付いています。しかしX11上で動かすツールと相性が悪いようなので、OpenGLUTを使ってみました。少しはまったので覚え書きです。<br /><br /><a href="http://sourceforge.net/projects/openglut/">OpenGLUT</a><br />適当な場所に展開したあとconfigureを行いますが、v10.4-では次のように変数を設定してやって下さい。<br /><pre><br />CPPFLAGS="-I/usr/X11R6/include" LD_FLAGS="-R/usr/X11R6/lib"<br /></pre><br />ちなみにOpenGLUTのコンパイルにはX11 on MacとX11SDKをそれぞれインストールする必要があります。koshimoto, hiroohttp://www.blogger.com/profile/09141449095639790908noreply@blogger.com0tag:blogger.com,1999:blog-7762104983157265388.post-51182463074106175602007-10-12T01:27:00.000+09:002007-10-12T01:51:18.930+09:00Prolog (3)簡易電卓を作成するとき、優先括弧に"(",")"という表記を使いました。実はPrologの仕様で(,)と.は自由なアトムとして使うことが出来ないからです。ところで、このダブルクオーテーションで囲んだ表記法ですが、一般的な言語では文字列リテラルと解釈されます。しかしPrologでは厳密な文字列型というオブジェクトは存在しません。一見文字列のようなこの値は、述語名や定数などと同様、小文字から始まるアトム型で、その別表記に過ぎません。同時に、データ上は数値リストとして扱うことが可能です。<br /><br />リスト中に文字と数字が並ぶ際には上記の事を注意しなければいけません。<br /><pre><br />?- [X] = "(".<br />X = 40 ;<br />No<br /></pre><br />というように、リスト要素をマッチングして行くと思わぬところで単一化されてしまいます。これを除こうと思っても、実際に数値なのでnumber/1は使えません。但し[X]全体をマッチしてやればnumber/1はfalseとなります。<br /><br />アトムの文字列表記が数値リスト(ASCII値となります)であることを利用して、シーザー暗号を作ってみましょう。変換部分はそのままです。<br /><pre><br />translate([], []).<br />translate([X|R], [X1|R1]) :-<br /> plus(X, 3, X1),<br /> translate(R, R1).<br /></pre><br /><br />アトムとその文字列表記の変換にはatom_codes/2を利用します。他にもchar_code/2やnumber_codes/2などが仕様にあります。ちなみにこの述語の引数をどちらも変数にすると例外が発生しますから、暗号のエントリ述語はこんな風に書きました。<br /><pre><br />caesar(Flat, Unflat) :-<br /> ((nonvar(Flat),<br /> atom_codes(Flat, C1));<br /> (nonvar(Unflat),<br /> atom_codes(Unflat, C2))),<br /> translate(C1, C2),<br /> atom_codes(Flat, C1),<br /> atom_codes(Unflat, C2).<br /></pre><br />平文も暗号文も可逆入力ですが、なんだかちょっと冗長ですね :)koshimoto, hiroohttp://www.blogger.com/profile/09141449095639790908noreply@blogger.com0tag:blogger.com,1999:blog-7762104983157265388.post-82401837461642155892007-10-11T18:36:00.000+09:002007-10-11T19:29:47.771+09:00Prolog (2)前回は四則演算だけ行う簡単な電卓を作成しました。四則演算だけと言っても、せめて'(',')'は使えないと不便ですので今回はあれを拡張していくプロセスを紹介します。<br /><br />'(',')'で囲まれた数式は外の部分より先に計算しなければいけません(あーでもCall by Needな言語ではそうとも限らんでしょうけど)。ので、これを検知して区間を取り出してcalcに渡してやれば良いだけだよね、と考えます。<br /><br />でも今回も天邪鬼をして、再帰的に毎回'(',')'を探して区間を抽出する方法を辞めるとしましょう。前回の実装では、数式リストを先頭から順番にマッチングしていくというステージを2回行っていました。もしこのステージ毎に先行計算区間の抽出を行うと馬鹿正直に計算量が増えます。リストを何度もスキャンするようなことはせずに、漢らしく(?)ステージごとに1パスで行く実装にします。<br /><br />とは言うものの、最初はえらく手続き的で冗長な記述になってしまいました。スタックをパスごとにたらい回して計算するような事を書いたんですが、最初に言ってる漢らしさ(?)が感じられなかったので破り捨てました。でも絶対にどうしてもパス間で共有したい変数があったので、論理の起点を次のように変えてみました。<br /><pre><br />calc(Exp, Ans) :- calc0([], Exp, [Ans]).<br /></pre><br />calc0はcalc1とcalc2を制御する論理ですが、NILが渡されている最初の引数には演算して問題の無いTodo式(計算する式)が入ります。二つ目の引数は、まだ演算していないし中身もまだ見ていない数式が入ります。二つ目は継続点になるわけですが、前方からTodoに詰めて行くことで、継続位置は単調後退するようにすれば、計算量は固定長ですよね(定数がでかいのはさて置き)。最低限これだけの情報があれば、式をパースしつつ計算を回すことが出来ます。<br /><br />まず具体的に演算を実行する部分です。具体的にってことは、継続位置が最後尾に来ているハズなので次のようになります。<br /><pre><br />% calc0/3<br />calc0(Todo, [], Ans) :- calc1(Todo, Tmp), calc2(Tmp, Ans).<br /></pre><br /><br />続いて簡単なところを先に固めましょう。'(',')'が出てこない部分はそのままTodoに詰めます。これは単純。<br /><pre><br />calc0(Todo, [X | Cont], Ans) :-<br /> not(X = "("), not(X = ")"),<br /> append(Todo, [X], T1),<br /> calc0(T1, Cont, Ans).<br /></pre><br /><br />では式をスキャンしていて'('が出てきたら、それまで続いていたTodoとは関係なく、先行して別途計算しないといけませんから、<br /><pre><br />calc0(Todo, ["(" | Cont], Ans) :-<br /> calc0([], Cont, A1),<br /> calc0(Todo, A1, Ans).<br /></pre><br />というようにして、後続の式をとりあえず新しい式としてcalc0に渡します。その答えを見て行く形にしようと思うのですが、ここでA1の中は')'の後にある式がそのまま"手付かず"で入っていなければなりません。そこで、<br /><pre><br />calc0(Todo, [")" | Cont], Ans) :-<br /> calc0([], Todo, A1),<br /> append(A, Cont, Ans).<br /></pre><br />として')'を発見したらそこまでのTodoを計算して、Todoの答えと')'以降の式を繋げた数式リストを返すよう書いてやります。'('にマッチングすると新しいcalcが計算されるということがポイント(同様のことをSchemeでやれば当然ながらクロージャを生成する感じですかね)。<br /><br />これまでのコードをマージすると<a href="http://homepage.mac.com/boqu/calc.pl">こんな</a>かんじです。前回のロジックは一切変更していない点がポイントです。<br /><pre><br />?- calc([2,*,"(",1,+,"(",2,-,5,")",")",+,5], Ans).<br />Ans = 1 ;<br />No<br /></pre><br />正しい答えがただ1つ得られました。<br /><br />このように、自分が欲しいと思う仕様を思い描いてみて、それが問題の全ての局面をカバーするよう、条件を網羅・記述(MECE... MECE... MECE...)していくのがPrologによるプログラミングのコツだと思います。koshimoto, hiroohttp://www.blogger.com/profile/09141449095639790908noreply@blogger.com0tag:blogger.com,1999:blog-7762104983157265388.post-75747509921336609732007-10-05T17:10:00.000+09:002007-10-05T17:33:00.133+09:00.emacs (2)MacOSXで<a href="http://aquaskk.sourceforge.jp/">AquaSKK</a>を使っていると困るのがEmacsのキーバインドとの衝突。^C-jで日本語入力に変わるのですが、アプリケーションにメッセージが渡る前の処理なのでEmacsでキーが捕まえられません。でも他のアプリケーションでは^C-jでの切替は便利なので変えたくありません。<br /><br />そんな場合に.emacsの設で、(global-set-key key cmd)を使って実行コマンドの割り当てを変更しても良いのですが、もっと根本的で簡単な方法があります。Emacsでは<a href="http://flex.ee.uec.ac.jp/texi/faq-jp/faq-jp_78.html">keyboard-translate-table</a>という変数があるので、これを弄ってやりましょう。<br /><pre><br />(keyboard-translate ?\C-m ?\C-j)<br />(keyboard-translate ?\C-j ?\C-m)<br /></pre><br />ついでにvi(m)バインドに慣れている人はDELも^C-hに割当ててしまいましょう。<br /><pre><br />(keyboard-translate ?\C-h ?\C-?)<br />(keyboard-translate ?\C-? ?\C-h)<br /></pre><br />これでvi(m)とEmacsを使い分ける際の違和感が一つなくなります。koshimoto, hiroohttp://www.blogger.com/profile/09141449095639790908noreply@blogger.com0tag:blogger.com,1999:blog-7762104983157265388.post-35778668457824920602007-10-04T12:20:00.000+09:002007-10-04T17:28:49.379+09:00.emacs (1)会社の作業環境をターミナル越しのemacsから<a href="http://www.meadowy.org/meadow/wiki/">Meadow 2.10</a>に移行しました。<br /><br />Windows端末は検証もありますから極力弄らないのが仕事の流儀、だからEmacs lisp内で完結してしまっている環境は大変便利なわけです(本当はEclipseがちっとも好きになれないだけ)。ところでMeadow 2.XXはNetinstallerがあるので拡張の追加が楽でした。SKKを使う人はapelも入れる事をお忘れなく。<br /><br />現状の.emacsはこんな感じ(memo)です。SKK + Common Lispというありがちな設定の間にPrologなんかを挟んでるのが僕の特徴です(どんだけー)。こういった古い言語の設定もちゃんと今に生きている辺りはEmacsの素晴らしさですねー(?)。<br /><pre><br />;; Fundamentals<br />(global-font-lock-mode t)<br />(show-paren-mode t)<br />(setq transient-mark-mode t)<br /><br />;; SKK<br />(autoload 'skk-mode "skk" nil t)<br />(global-set-key "\C-x\C-j" 'skk-mode)<br />(global-set-key "\C-xj" 'skk-auto-fill-mode)<br />(global-set-key "\C-xt" 'skk-tutorial)<br />(add-hook 'isearch-mode-hook<br /> (function (lambda ()<br /> (and (boundp 'skk-mode) skk-mode<br /> (skk-isearch-mode-setup)))))<br />(add-hook 'isearch-mode-end-hook<br /> (function (lambda ()<br /> (and (boundp 'skk-mode) skk-mode<br /> (skk-isearch-mode-cleanup)<br /> (skk-set-cursor-color-properly)))))<br />(setq skk-large-jisyo "C:/Meadow/packages/etc/skk/SKK-JISYO.L")<br />(setq skk-tut-file "C:/Meadow/packages/etc/skk/SKK.tut")<br /><br />;; SWI-Prolog - http://www.swi-prolog.org/ -<br />(setq auto-mode-alist<br /> (append '(("\\.pl" . prolog-mode))<br /> auto-mode-alist))<br />(setq prolog-program-name "C:/Program Files/pl/bin/plcon")<br />(setq prolog-consult-string "[user].\n")<br /><br />;; CLISP - http://clisp.cons.org/ -<br />(setq inferior-lisp-program "C:/clisp/clisp")<br /><br />;; SLIME - http://common-lisp.net/project/slime/ -<br />(add-to-list 'load-path "C:/Meadow/slime-2.0/")<br />(require 'slime)<br />(slime-setup)<br />(setq slime-net-coding-system 'euc-jp-unix)<br />(setq common-lisp-hyperspec-root "c:/clisp/doc/HyperSpec/")<br />(add-hook 'inferior-lisp-mode<br /> (lambda () (inferior-slime-mode t)))<br />(add-hook 'lisp-mode-hook<br /> (lambda ()<br /> (slime-mode t)<br /> (show-paren-mode)))<br />(slime-autodoc-mode)<br /></pre><br /><br />ただもっぱら納品仕事はc++なのでvi(m)で書いています。<br />c/c++は構文がそもそも行指向なところがありますから、Emacsによるメリットが薄いというのが個人的な印象です。特に対話実行など一切無い世界ですし、<CTRL>や<META>を組み合わせた操作が入らない分、タイピング総数はvi(m)での編集の方が圧倒的に楽かも、と思っています(だったらEclipse使えよという見方もあるけど)。koshimoto, hiroohttp://www.blogger.com/profile/09141449095639790908noreply@blogger.com0tag:blogger.com,1999:blog-7762104983157265388.post-82342519966488566092007-10-04T03:05:00.000+09:002007-10-11T18:34:18.866+09:00Prolog (1)Prologの強みはなんと言ってもパターンマッチングとバックトラックです。それを利用することによって、「どうやって(how)?」ではなく「どんな(what)?」でプログラミングを行うことが可能となります。またPrologは型の無い動的な言語なので、自分がどういった仕様を欲しているのか、スケッチするように考えながら作ることが出来ます。例えば簡単な電卓を作るプロセスを紹介します。<br /><br />まずは四則演算がどういったものなのか、思いついたまま書き下してみました。<br /><pre><br />% calc_op/4<br />calc_op(X, +, Y, Z) :- Z is X + Y.<br />calc_op(X, -, Y, Z) :- Z is X - Y.<br />calc_op(X, *, Y, Z) :- Z is X * Y.<br />calc_op(X, /, Y, Z) :- Z is X / Y.<br /></pre><br />引数の部分がこれで良いのかどうか、現時点では分かりません。なので他のアイデアとして、こんな事も考えてみました。<br /><pre><br />calc_op([X, +, Y | R], Ans) :-<br /> calc_op(R1, Ans),<br /> append([Z], R, R1),<br /> Z is X + Y.<br /></pre><br />ですが、この方法だと演算子の優先度を解決するために、演算子の組み合わせの数だけパターンを用意してやらなければならない事が分かります。だって、+Yの後に*が来たら、Zはまだ計算しちゃいけませんからね。もちろん、後者の方法でも場合分けのパターンを網羅してやれば(MECE... MECE... MECE...)、誤った選択はバックトラックによって解の候補から消えていくので間違った実装では無いでしょう。でも組み合わせの数は簡単に膨れ上がることは察してやる必要があります。<br /><br />ここではとりあえず、演算子が増える事を想定して、演算操作と操作の組み合わせは別の論理として表現する道を選びました。それでは、前者の個別に表現された演算の論理を制御する部分を考えます。<br /><pre><br />% calc/2<br />calc([], []).<br />calc([X], [X]).<br />calc([X, Y, Z | R], Ans) :-<br /> calc_op(X, Y, Z, A1),<br /> append([A1], R, E),<br /> calc(E, Ans).<br /></pre><br />一歩づつ、とにかく実行させて行くことが重要です。クロッキー片手に製図のような線を引くことはないですよね?とりあえず数式をリストで渡してやれば、頭から演算を適用して答えを返すところまで来ました。当然、数式によっては間違います。<br /><br />ここまではほとんど何も考えずに来るわけですが、ここで少し考えます。さて演算子の優先順位をどうやって解決してやろうか?と。僕も含め、恐らく多くの人はまず入力されたリストをパースしてRPNのような構造に変換しようと考えると思います。今回はそれだと普通過ぎるなと思ったのでわざと違うことをしてみました。実際に目の前に式を提示されたらどうやって順番決めて解いていくかしら?というアプローチです。<br /><br />ここは極端な話、人によりけりですし、問題によって解き易いように分解したりファクタリングしたりすると思います。ですが単調な方法で行けば、まず一番優先度の高いところを解決して項を書き換えて、新しい式に次の優先度の書換えを施して、という手順です。<br /><pre><br />1+2*3-4/2 => 1+6-4/2 => 1+6-2 => 7-2 => 5<br /></pre><br />左から右、乗除から加算。つまり数式に対してステージングを行っているわけですね。そこで2つのステージに分けてみます。<br /><pre><br />% calc/2<br />calc(Exp, Ans) :- calc1(Exp, Tmp), calc2(Tmp, Ans).<br /><br />% calc1/2<br />calc1([], []).<br />calc1([X], [X]).<br />calc1([X, Y, Z | R], Buf) :-<br /> calc1op(X, Y, Z, A1, B1),<br /> append(A1, R, E),<br /> calc1(E, A2),<br /> append(B1, A2, Buf).<br /><br />% calc2/2<br />calc2([], []).<br />calc2([X], [X]).<br />calc2([X, Y, Z | R], A2) :-<br /> calc2op(X, Y, Z, A1),<br /> append(A1, R, E),<br /> calc2(E, A2).<br /></pre><br />どちらのステージでもリストの先頭から順にマッチングしたものを演算論理に渡します(ちなみにこれって、C/C++で言うディスパッチャみたいな処理ですね。パターンマッチのおかげで多重ディスパッチも簡単です)。演算論理の結果と先頭を挿げ替えて、再帰的に、ただしステージごとに分離した形で、マッチングを行っていきます。<br /><br />1つめのステージ(calc1)では乗除算だけが実行されて、項が書き換わった式を生成します。2つめのステージ(calc2)では渡された加減算のみの式に演算を適用して答えを求めます。ステージ別に演算に要求される仕様が変わりましたから、このままでは動きません。最初の演算ルールを修正しましょう。<br /><pre><br />% calc1op/5<br />calc1op(X, *, Y, [Z], []) :- Z is X * Y.<br />calc1op(X, /, Y, [Z], []) :- Z is X / Y.<br />calc1op(X, +, Y, [Y], [X, +]).<br />calc1op(X, -, Y, [Y], [X, -]).<br /><br />% calc2op/4<br />calc2op(X, +, Y, [Z]) :- Z is X + Y.<br />calc2op(X, -, Y, [Z]) :- Z is X - Y.<br /></pre><br />1つめのステージでは+,-演算を書き換えず、またバックトラックを起こさないために若干不恰好な論理を加えています。これで一先ずは四則演算が行えるようになりました。<br /><pre><br />?- calc([2,*,4,-,3,*,1], Ans).<br />Ans = 5 ;<br />No<br /></pre><br />正しい答えがただ1つ見つかりました。koshimoto, hiroohttp://www.blogger.com/profile/09141449095639790908noreply@blogger.com0