Infernoとか: limbo

ラベル limbo の投稿を表示しています。すべての投稿を表示

2015年4月25日土曜日

ブロックパズルの解法

ご無沙汰です。
色々あって技術的な研究から離れていましたが、
一旦落ち着きましたので戻ってまいりました。

リハビリを兼ねて久々にLimboを触りました。

たまたまガチャガチャで木のパズルを手に入れました。
下記のように、完成形は３ｘ３ｘ３の立方体になります。
ばらすとひとつづきの木のブロックになりますが、中にゴムひもが通っていて、回すことができます。２または３ブロックおきに曲がり角があります。

手で少しいじってみましたが、すぐに諦め、計算機で解法を求めることにしました。
（手でやるのも面白そうです。意外と色がヒントになりそうです）

３または２このブロックがつながっていて、関節で必ずどちらかの方向にカーブしなければなりません。すべての関節でカーブした結果、立方体に収まっていればOKとなります。
データ構造は意外と単純で、
連続ブロック数　x　節の数
で表されてしまいます。
ブロックの色は考慮しません。
曲がる方向は上下左右の４通り。これが関節数分の組み合わせが発生します。
関節数はこのパズルでは１６あったので、4 ^ 16 の組み合わせになります。
４０億通りくらい？
（こんなの手で解けるのでしょうか。）

※コードは割愛

ループを単純に回して、総当りさせてみました。
環境はi5 のCPUのWindowsノートパソコン上のACME-SACです。

解かせてみると試した環境では総当りに１０時間くらいかかりそうです。
一晩動かしたら気づけば解けていました。（バグによりやりなおして３晩ほどかかりましたが、、、）
検算として実際のパズルに結果を適用すると完成！当たり前とはいえちょっとうれしい。

パフォーマンスですが、ACME-SACの環境(ほぼWindows上のemuと同じでしょうね)では１または２コアをだいたい専有し、全体の２，３０％を使うようでした。
シーケンシャルに試していましたが、並行にするだけで結構早くなりそうな予感です。

ただ、それでもすべてのコアを使えないかもしれません。
その場合はemuを複数立ち上げ、分散してやるとフルに活用できるのではないかと
期待しています。

今回はそこまでは手が回りませんでしたが、久々のLimboは楽しかったです。
グリッド試そうかな。
Goもやらないとな、、、

さて、このパズルプログラミングの題材としては結構適していると思いました。
ループを使ったり、多次元配列をつかったり、言語の機能が色々と試せます。
各試行は独立しているので並行処理もさせやすいです。
新人研修のネタにいいかも。

2011年4月20日水曜日

スクリプト言語並みの気軽さで使える？

ちょっとしたフィルターを書くのに、perlを使うと、

while(<>){
if(/EXPR/){
# 処理
}
}

とさっと書けて便利です。
便利すぎて他の言語に移行できません。

これをlimboでやろうとすると、以下のように大量の記述が必要となります。
モジュールのロードが面倒。

implement filter1;

include "sys.m";
sys: Sys;
include "draw.m";
include "bufio.m";
bufio: Bufio;
Iobuf: import bufio;
iobuf: ref Iobuf;
include "regex.m";

filter1: module {
init: fn(ctxt: ref Draw->Context, artv: list of string);
};

init(ctxt: ref Draw->Context, artv: list of string)
{
sys = load Sys Sys->PATH;
bufio = load Bufio Bufio->PATH;

if (bufio == nil) {
exit;
}

stdin := sys->fildes(0);
iobuf = bufio->fopen(stdin, bufio->OREAD);
if (iobuf == nil) {
exit;
}

regex: Regex;
regex = load Regex Regex->PATH;
if (regex == nil) {
exit;
}

(re, nil) := regex->compile("EXPR", 1); # flg = 1
while (1) {
s := iobuf.gets('\n');
if (s == nil) {
iobuf.close();
break;
}

rslt := regex->execute(re, s);
if(rslt == nil) {
continue;
}

(a, b) := rslt[0];
# 処理
}
}

ということで、スクリプトの代わりにするのはきつい。
shと併用しなければだめっぽいですね。

2010年1月26日火曜日

Acheron Limbo Compiler

Limbo コンパイラーとその実行環境をPOSIXに移植したプロジェクトがあるそうです。

Acheron Limbo Compiler

もしこれが普通に使えそうなら、普段からLimboがいかせるかもしれない。

コンパイルしてみようと思ったが、ごにょごにょしているうちに、
Linuxマシンをおかしくしてしまった。
やる気を失ったので後日・・

なお、ソースはアーカイブになっていないようなので、CVSで持ってくる必要がありそう。
また、コンパイルにはocamlが必要っぽい。

ほかに、Parrotについてもちょっと見てみた。
これは、仮想マシン(レジスタマシン)の実装らしい。
色々な言語に対応しているようだ。
しかし、Limboには対応していないようだ。残念。

Parrot Language

2010年1月16日土曜日

InfernoのHTTPでCGIを書く

InfernoのHTTPでCGIを作成する方法が分かりました。

・HTTPサーバーの起動

svc/httpd/httpd

オプションは
-D デバッグログを出す
-p ポート

・まずは普通のウェブページの表示方法

/services/httpd/rootというディレクトリの下に
htmlソースを置くとアクセスできる。
index.htmlというファイルを置くと、

http://host/index.htmlまたはhttp://host/ でアクセス可能。

サブディレクトリを作ってもOK。

・CGIのサンプル

CGIはhttp://host/magic というパスでアクセスする。
まずはhttp://host/magic/echo
とアクセスしてみる。
すると、なにやら情報が表示される。
これはファイルシステム上の/dis/svc/httpd/echo.disに当たる。
LimboでかかれたCGIファイルで、ソースは/appl/svc/httpdの下にecho.bがある。
これを真似して、例えば同じ場所にtest.disを置くと、
http://host/magic/test
でアクセスできる。

詳細はecho.bをみると大体わかるが、
通常のシェルコマンドと書き方がちょっと違う。

覚えきれるものでもないので、雛形にしてしまうのがよいか。


implement test;

include "sys.m";
 sys: Sys;
include "draw.m";

include "bufio.m";
include "cache.m";
include "contents.m";
include "httpd.m";
 Private_info: import Httpd;
include "cgiparse.m";
cgiparse: CgiParse;

test: module {
 init: fn(g: ref Private_info,
  req: Httpd->Request);
};

init(g: ref Private_info,
  req: Httpd->Request)
{
 sys = load Sys Sys->PATH;
 cgiparse = load CgiParse CgiParse->PATH;
 if(cgiparse == nil){
  return;
 }
 cgidata := cgiparse->cgiparse(g, req);
 bufio := g.bufio;
 Iobuf: import bufio;

 # Send header
 g.bout.puts(cgidata.httphd);

 # Send body
 g.bout.puts("<head><title>test</title></head><body>test</body>\r\n");

 g.bout.flush();
}

リクエストデータはcgiparseの結果に格納され、
method, uri, headerなどのメンバーで参照できて便利。
フォームデータはformでアクセス出来るのでこれでCGIが実現できるはず。
これはtag, valのペアのリストになっているのでhd, tlメソッドで
簡単に取り出せる。


(tag, val) = hd cgidata.form;
cgidata.form = tl cgidata.form;

のループでOK。

cgidataに関してはcgiparse.mを見ると良い。
関係ないけどacme(エディタ)でimport "cgiparse.m";の所で右クリックすると
ヘッダファイルにジャンプしてくれるので実に便利。

・その他

認証には対応していないように見える。

情報があんまり無いので、結局ソースコードから追った。
時間かかった〜。

2009年9月13日日曜日

ktrans移植難航

plan9の日本語入力環境のktransをlimboに移植しようかなー、と軽く考えてました。
元のktransはkenのccで書かれている。
おそらく実用的なレベルに達していると思われ、skk方式となっている。

辞書をハッシュテーブルに格納しているようなので、limboで書き直してみたところ、、、
うーん、どう書いていいかわからない。
リストにどんどん突っ込んでいったら、メモリがあふれたのか、segvで落ちた・・・
さて、どうしたものか。

アドレスをダンプできないから、具体的なメモリ配置がよくわからないのがつらいところ。

以下情報源。

・ktrans配布元

http://basalt.cias.osakafu-u.ac.jp/plan9/s39.html

・ktrans辞書配布元

http://basalt.cias.osakafu-u.ac.jp/plan9/s17.html

・SKK辞書をktrans用に変換する方法

http://plan9er.hp.infoseek.co.jp/plan9/9log.html

・acme-sacにはktrans.bが付属している(日本語非対応)

http://code.google.com/p/acme-sac/

戯れにktrans.bをちょっと書き換えて、ローマ字→ひらがな
変換を試してみた。

漢字変換を早く実現したい。

なお、acme-sac付属のktrans.bをwindows xp上のhosted infernoに
持ってくることは可能だった。
一時ファイル/n/tempがなぜかcreate出来なかったので、
ひとまず一時ファイル名を書き換え(ソース埋め込み)。

使い方は、wm/wm起動前に、

% pipefile -r ktrans /dev/keyboard

として、キーボード入力にフィルターとして追加する。
(起動時設定をしたい場合は、先日の日記にあるように、profileに処理を書いておく)

※acme-sacはinfernoを学ぶ上で避けて通れないな。

2009年8月8日土曜日

分散プログラミング

どう書く？のお題の分散関数呼び出しがちょうどぴったりだったので、
Limboで書いてみました。

分散関数呼び出し
http://ja.doukaku.org/comment/9449/

リンク先には説明を入れませんでしたが、次のような方針です

・サーバーでは仮想ファイル(synthetic file)を用意する。
　このファイルに対し、リードしたりライトすることで、処理を実行させることが出来る。
　（今回の例では数字をライトすると、整形した文字列がリードできる）

・クライアントではサーバーのファイルをマウントし、そのファイルに対し読み書きを行う。
　こうすることで、実際の演算はサーバー側で行われ、クライアントでは結果の収集のみが行える。

これは面白い。

ポイントは、
・#sをbindしなければならない。#sという特殊なシンボルをsynthetic fileを置こうとするディレクトリにbindする。
・sys->file2chanでsynthetic fileを生成する。
・file2chanは戻り値がFileIO型だが、そのread, writeというメソッドで、
　そのファイルに書き込みが行われたとき、あるいは読み込みが行われたときの
　処理を記述する。

その他わかったこと

・サーバーとクライアントの通信プロトコルはstyxと呼ばれ、mount サーバーホスト名マウントポイント　という処理を行えば、サーバーのネームスペースをクライアントの特定のディレクトリにマウントできるようだ。
・altというのはcaseと似ているが、数値ごとの処理わけを記述するのではなく、チャネルごとの処理わけを記述する。列挙したチャネルのどれかでイベントが発生したらブロックの中の処理に移行するが、それまでは待ち状態になる。(selectにあたる？)

alt{
<- channel1 =>
# channel1のイベントが発生した時の処理
<- channel2 =>
# channel2のイベントが発生したときの処理
}

Limbo/TkでGUIプログラムを書く場合、イベント待ちのループを書く必要があり(マウスのクリックとか)、その場合にaltを使うようだ。

・定数の記述はcon

変数名 : con 初期化データ;

2009年4月12日日曜日

Limbo でパイプを扱う

どう書く.org
http://ja.doukaku.org/127/
指定コマンドを別プロセスで起動

を考えてみました。
以前の投稿
http://inferno-hell.blogspot.com/2009/03/blog-post.html
をベースにしてみました。

パイプでのやり取りが難しく、結局C言語(posix)っぽくなりました。
明示的にパイプをクローズするのが簡単にはできないようではまりました。

以下コードです。
インデントがうまくいかなく、みづらいので、
気になる方はどう書く.orgの方の参照お願いします。
http://ja.doukaku.org/comment/8800/

implement d127;

include "sys.m";
sys: Sys;
include "draw.m";
include "sh.m";
sh: Sh;

d127: module{
init: fn(ctx: ref Draw->Context, argv: list of string);
};

init (ctx: ref Draw->Context, argv: list of string)
{
sys = load Sys Sys->PATH;
sh = load Sh Sh->PATH;
buf := array[64] of byte;
fds := array[2] of ref Sys->FD;

argv = tl argv;
if(argv == nil){
return;
}
cmd := hd argv;

sys->pipe(fds); # open pipes
spawn child(ctx, fds[0], cmd);

# Read results of child process
n: int;
fds[0] = nil;
fdd := sys->open("/dev/cons", sys->OWRITE);
for(;;){
n = sys->read(fds[1], buf, len buf);
if(n == 0){
break;
}

# print result
sys->fprint(fdd, "%s", string buf[0:n]);
}
}

child (ctx: ref Draw->Context, fd: ref Sys->FD, cmd: string)
{
# duplicate stdout to the pipe
sys->dup(fd.fd, 1);

sh->system(ctx, cmd);

# pipe close
fdn := sys->open("/dev/null", sys->OWRITE);
sys->dup(fdn.fd, 1);
fd = nil;
}

ポイントはパイプをオープンして片方を子プロセスに渡すということと、
処理終了後になんとかパイプをクローズしているところです。

ファイルやパイプをクローズするにはcloseというシステムコールはなく、
どこからも参照しなくならないようにしなければなりません。
なので、三カ所で無理矢理パイプの参照を切っています。

1. 親プロセスの中、子プロセス呼び出し後、ファイルデスクリプタにnil代入
2. 子プロセスで、stdoutをパイプではなく、/dev/nullに
3. 子プロセスで、ファイルデスクリプタにnil代入

2009年3月25日水曜日

外部コマンドを実行し、その実行結果をパイプで受け取る方法

早い話が、perlで、open("command |");というのをLimiboでやりたいのです。
ネットで調べてもずばりの情報が無く試行錯誤しました。
間違っているかもしれませんが、とりあえず現時点での解を示したいと思います。

なお、どう書く.orgにもタイムリーなお題が出ていたので、投稿しておきました。
http://ja.doukaku.org/242/

まずは外部コマンドの呼び出しです。
*.disをモジュールとしてロードしinitを呼ぶ、というのがよくある方法のようです。

hdl := Command "/dis/ls.dis"; # ls の例

その後、

hdl->init(ctx, nil); # ctxはメイン関数の第一引数を渡せばよい、第二引数はコマンドの引数リスト

としてやればコマンドが実行される。

spawn hdl->init(ctx, args);

といった感じで別プロセスでの実行も出来るようだ。

この方法とは別に、Shのsystemメソッドを使う方法もある。

sh := load Sys Sys->PATH;
sh->system(ctx, "command");

とするだけでよさそう。簡単。

次にどちらの方法でも良いが、立ち上げた外部プロセスとのパイプライン通信を考える。

Sys->pipeメソッドを使うとパイプからオープン済みのファイルデスクリプタが取得できる。
つまり、標準入出力をファイルI/Oに置き換えることが可能。

fds := array[2] of ref Sys->FD;
sys->pipe(fds);

とすると、fdsという配列が得られ、2つのパイプが得られる。
fds[0]に書き込むとfds[1]からそのデータが読まれ、
fds[1]に書き込むとfds[0]からそのデータが読めるようだ。

なので、外部プロセス実行前に標準出力をどちらかのパイプに結び付けてやり、
もう一方のパイプから読み出せば外部プロセスの出力結果が得られる。
それにはSys->dupを使用する。
Sys->dupの第一引数は結びつけるファイルデスクリプタ、第二引数は結びつける標準入出力の番号(0: stdin, 1: stdout, 2: stderr)。

以上をコードにすると、

sys = load Sys Sys->PATH; # sysのロード
c := load Command "/dis/ls.dis"; # 外部コマンドのロード

fds := array[2] of ref Sys->FD;
sys->pipe(fds); # パイプの取得

sys->dup(fds[0].fd, 1); # パイプ0に標準出力を出す

spawn c->init(ctx, nil); # コマンド実行

buf := array[64] of byte;
n := sys->read(fds[1], buf, len buf); # パイプ1から読み込むとコマンドの出力が得られる

上記コードはエラー処理がまったく入っていないのでよろしくない。

登録: 投稿 (Atom)