伏字しりとりをリリース
伏字を使った少し変わった「しりとり」で遊べるサービス「伏字しりとり」 をリリースしました。
少しでも遊んでいただけたら幸いです。
こうしたらいいよというアドバイスや
おもしろい/つまらないといった感想を歓迎します。
Rubyで伏字検索
Rubyで伏字を解析するプログラムを書いてみました。
fuseji.net に接続して、返ってきた検索結果から
正規表現で取り出します。
検索結果は配列に入りますので、ご利用くださいまし。
#!/usr/bin/ruby -Ku
# -*- coding: utf-8 -*-
require "net/http"
require "kconv"
=begin
伏字検索 検索サンプルプログラム
<tt>〜</tt>取り出し結果を配列で返す
動作確認バージョン
* ruby 1.9.3 i386-mingw32
* ruby 1.8.7 i386-mswin32
=end
def fuseji_search(str)
ret = []
return ret if str.size == 0
escaped_str = "/" + URI.escape(str)
body = ""
Net::HTTP.version_1_2
Net::HTTP.start('fuseji.net',80) {|http|
response = http.get("#{escaped_str}", 'User-Agent' => "sample.rb" )
body = response.body
}
body.each_line do |line|
until line.empty? do
case line
when /\A\s+/
;
when /\A<tt>(.*)<\/tt>/
ret << $1
when /\A./
;
else
raise RuntimeError, 'must not happen'
end
line = $'
end
end
ret
end
=begin
サンプルメイン
伊集院○を検索、検索結果を表示する
結果はUTF-8で得られるので必要に応じて文字コードを変換すること
=end
result = fuseji_search("伊集院○")
print "マッチ数: #{result.size}\n"
result.each{|word|
print word + "\n"
}
SMC(The State Machine Compiler)を試す その3
テキストで書いた状態遷移マップから
Cのコードを生成し、実行、出力コードの解析までできました。
今回は他の言語も試してみます。
各言語のサンプルEX1はC版と同じで0*1*をチェックする
状態遷移機械です。
%cd examples/C++/EX1 %make java -jar ../../../bin/Smc.jar -c++ -g AppClass.sm c++ -g -Wall -Wextra -I../../../lib/C++ -o checkstring AppClass_sm.cpp AppClass.cpp Main.cpp % ./checkstring.exe 001 The string "001" is acceptable. % ./checkstring.exe 001119 0 The string "010" is not acceptable. % ./checkstring.exe 01010190000 The string "100" is not acceptable.
GNU c++でコンパイルしましたが問題なく動作しました。
C++版サンプルは、VC++でもビルドできるように
プロジェクトワークスペースを用意してくれてあります(ex1.dsw)。
%cd examples/Perl/EX1 %make java -jar ../../../bin/Smc.jar -perl -g AppClass.sm % perl -I ../../../lib/Perl/lib checkstring.pl Can't locate DFA/Statemap.pm in @INC (@INC contains: ...
Statemap.pmが見つからないようです。ふむ。
% perl -I ../../../lib/Perl/lib checkstring.pl Can't locate DFA/Statemap.pm in @INC (@INC contains: ...
ライブラリをmake installするとDFAというフォルダに
コピーするようです。
とりあえずは以下のようにごまかしました。
% diff -u AppClass_sm.pm.org AppClass_sm.pm
--- AppClass_sm.pm.org 2012-03-27 21:35:26.640625000 +0900
+++ AppClass_sm.pm 2012-03-27 21:35:58.859375000 +0900
@@ -6,7 +6,7 @@
use strict;
use warnings;
-use DFA::Statemap;
+use Statemap;
package AppClassState;
use base qw(DFA::Statemap::State);
% perl -I ../../../lib/Perl checkstring.pl 0010101
The string "0001" is acceptable.
% perl -I ../../../lib/Perl checkstring.pl 000110
The string "0010" is not acceptable.
% perl -I ../../../lib/Perl checkstring.pl 001001101
The string "0011" is acceptable.動きました。
% make java -jar ../../../bin/Smc.jar -ruby -g AppClass.sm % cp ../../../lib/Ruby/statemap.rb . % ruby checkstring.rb 001 The string "001" is acceptable. % ruby checkstring.rb 001 The string "00" is acceptable. % ruby checkstring.rb 0010 The string "010" is not acceptable.
動きました。
% make java -jar ../../../bin/Smc.jar -python -g AppClass.sm bash-3.2$ cp ../../li ../lib/Python/ Makefile README.txt setup.py statemap.py % cp ../../../lib/Python/statemap.py . % python checkstring.py No string to check. % python checkstring.py 010 The string "010" is not acceptable. % python checkstring.py 010 000 The string "000" is acceptable.
動きました。
C++、Perl、Ruby、Pythonでサンプルが正しく動きました。
では次回はRubyのサンプルをもう少し見ていこうと思います。
SMC(The State Machine Compiler)を試す その2
その1では、テキストで書いた状態遷移マップから
Cのコードを生成し、実行してみました。
今回は実際に生成されたコードを読んでみたいと思います。
ライセンス
生成されたコードのライセンスは?
FAQに記載がありました。
Does the SMC license cover the files SMC generates? No. The .sm files and the output files SMC generates from .sm files belong to you and are covered by your copyright (if you are using one.)
とあるので、
Q.SMCのライセンスは、SMCが生成するファイルをカバーしますか?
A. .smファイル、およびSMCが.smファイルから生成する出力ファイルは、
あなたが所有しており、あなたの著作権によってカバーされます。
ご自由にどうぞと読めます。
思い込み
生成コードを想像してみました。
ぱっと思いつくのは状態を変数でもち、イベント判定をして、
代入によって遷移を行なうコードです。
switch(状態変数)
{
case 状態1:
if(イベント1発生()) {
状態変数 = 状態2;
}
break;
case 状態2:
if(イベント2発生()) {
状態変数 = 状態1;
}
break;
}この想像はまったく役に立ちませんでした。
状態変数の定義もないし、状態を判定している
処理もありません。
ではsmcはどうやって状態遷移を実現しているのでしょうか。
ファイル
ユーザーが書くコードのサンプル
- AppClass.c
- AppClass.h
- main.c
SMCにより提供されたヘッダファイル
- ../../../lib/C/statemap.h
SMCが生成したコード
- AppClass_sm.c
- AppClass_sm.h
デバッグコード
コード生成したときに-gオプションを付けていると
トレース用のデバッグコードが埋め込まれて、読みにくいので
オプション(-g)を外して生成してみます。
オプション有り %wc *.[ch] 401 967 10783 AppClass_sm.c 77 160 1721 AppClass_sm.h オプション無し %wc *.[ch] 254 487 5892 AppClass_sm.c 68 133 1415 AppClass_sm.h
ぐっとコード量が減りました。
これで読みやすくなりました。
関数群
はじめにtagsファイルを作ってみました。
appclass.c(48) : void AppClass_Init(struct AppClass *this) appclass.c(58) : void AppClass_Acceptable(struct AppClass *this) appclass.c(63) : void AppClass_Unacceptable(struct AppClass *this) appclass.c(68) : int AppClass_CheckString(struct AppClass *this, const char *theString) appclass_sm.c(29) : static void AppClassState_EOS(struct AppClassContext *fsm) appclass_sm.c(34) : static void AppClassState_One(struct AppClassContext *fsm) appclass_sm.c(39) : static void AppClassState_Unknown(struct AppClassContext *fsm) appclass_sm.c(44) : static void AppClassState_Zero(struct AppClassContext *fsm) appclass_sm.c(49) : static void AppClassState_Default(struct AppClassContext *fsm) appclass_sm.c(95) : static void Map1_Start_EOS(struct AppClassContext *fsm) appclass_sm.c(107) : static void Map1_Start_One(struct AppClassContext *fsm) appclass_sm.c(116) : static void Map1_Start_Unknown(struct AppClassContext *fsm) appclass_sm.c(125) : static void Map1_Start_Zero(struct AppClassContext *fsm) appclass_sm.c(136) : static void Map1_Zeros_EOS(struct AppClassContext *fsm) appclass_sm.c(148) : static void Map1_Zeros_One(struct AppClassContext *fsm) appclass_sm.c(157) : static void Map1_Zeros_Unknown(struct AppClassContext *fsm) appclass_sm.c(166) : static void Map1_Zeros_Zero(struct AppClassContext *fsm) appclass_sm.c(177) : static void Map1_Ones_EOS(struct AppClassContext *fsm) appclass_sm.c(189) : static void Map1_Ones_One(struct AppClassContext *fsm) appclass_sm.c(198) : static void Map1_Ones_Unknown(struct AppClassContext *fsm) appclass_sm.c(207) : static void Map1_Ones_Zero(struct AppClassContext *fsm) appclass_sm.c(220) : static void Map1_Error_EOS(struct AppClassContext *fsm) appclass_sm.c(231) : static void Map1_Error_One(struct AppClassContext *fsm) appclass_sm.c(237) : static void Map1_Error_Unknown(struct AppClassContext *fsm) appclass_sm.c(243) : static void Map1_Error_Zero(struct AppClassContext *fsm) main.c(46) : int main(int argc, char *argv[])
なんとなく分かってしまいましたかね。
Map1_Start_One()は Start状態で、Oneイベントが
発生したときに実行される関数です。
同じルールで「状態の数 x イベントの数」分の関数が生成されています。
関数の中身は
- .EXIT_STATE 状態から出て行く処理
- .AppClass_Acceptable() イベント処理
- .setState() 遷移処理
- .ENTRY_STATE 新しい状態に入った処理
遷移先の情報はこれらの関数が持っています。
状態発見
生成されたコードを眺めていると状態を見つけました。
AppClass_sm.c(133): const struct AppClassState Map1_Start = { POPULATE_STATE(Map1_Start), 0 };
AppClass_sm.c(174): const struct AppClassState Map1_Zeros = { POPULATE_STATE(Map1_Zeros), 1 };
AppClass_sm.c(215): const struct AppClassState Map1_Ones = { POPULATE_STATE(Map1_Ones), 2 };
AppClass_sm.c(217): const struct AppClassState Map1_OK = { POPULATE_STATE(Map1_OK), 3 };
AppClass_sm.c(248): const struct AppClassState Map1_Error = { POPULATE_STATE(Map1_Error), 4 };状態は変数ではなく、定数でROMコード上に存在しました。
マクロ展開してみましょう。
const struct AppClassState Map1_Start = {
Map1_Start_EOS,
Map1_Start_One,
Map1_Start_Unknown,
Map1_Start_Zero,
AppClassState_Default,
0 };状態は、関数へのポインタを持ちます。
何を指すのか？
先ほど「状態の数 x イベントの数」と書いた
遷移用の関数へのポインタを持ちます。
AppClassState構造体の定義を見ると、
間違い無いことが分かります。
struct AppClassState
{
void(*EOS)(struct AppClassContext*);
void(*One)(struct AppClassContext*);
void(*Unknown)(struct AppClassContext*);
void(*Zero)(struct AppClassContext*);
void(*Default)(struct AppClassContext*);
STATE_MEMBERS
};重要なのでもう1度。
状態はROMコード上に存在し、遷移を持ちます。
遷移は状態+アクション用の関数へのポインタで表現します。
では全体の流れを把握するために
main.cから見てみましょう。
int main(int argc, char *argv[])
{
struct AppClass thisContext;どうやら thisContext が現在の状態を保存する
変数のようです。AppClassの型を見てみましょう。
struct AppClass
{
/* If a string is acceptable, then this variable is set to YES;
* NO, otherwise.
*/
int isAcceptable;
struct AppClassContext _fsm;
};さらに深追いし、AppClassContextの定義を見ます。
struct AppClassContext
{
struct AppClass *_owner;
FSM_MEMBERS(AppClass)
};*_ownerはポインタ変数でした。
なるほど、状態を格納した変数が存在しなかったのはポインタ変数
で表現されているからなのでした。
ではmain.cに戻ります。
main.cの主な処理は
- .初期化 AppClass_Init()
- .状態遷移 AppClass_CheckString()
です。
AppClass.c内に記述された
AppClass_CheckString()を見てみます。
int AppClass_CheckString(struct AppClass *this, const char *theString)
{
while (*theString)
{
switch (*theString)
{
case '0':
AppClassContext_Zero(&this->_fsm);
break;
case '1':
AppClassContext_One(&this->_fsm);
break;
default:
AppClassContext_Unknown(&this->_fsm);
break;
}
++theString;
}
/* end of string has been reached - send the EOS transition. */
AppClassContext_EOS(&this->_fsm);
return this->isAcceptable;
}文字列が終端にくるまで繰り返し、イベントの判定をしています。
0だったらAppClassContext_Zero()
1だったらAppClassContext_One()
それ以外だったらAppClassContext_Unknown()
を実行。
ここがイベントの判定と実行です。
AppClassContext_Zero()はAppClass_sm.hで定義された
マクロです。
#define AppClassContext_Zero(fsm) \
assert(getState(fsm) != NULL); \
getState(fsm)->Zero(fsm);
<<
分かりづらいのでプリプロセスを通したあとのコードを見ましょう。
>||
gcc -E -I../../../lib/C AppClass_sm.c AppClass.c main.cプリプロセス前: getState(fsm)->Zero(fsm);
プリプロセス後: (&this->_fsm)->_state->Zero(&this->_fsm);
ゼロを見つけたときに実行した
AppClassContext_Zero()
は、現在の状態(ROMコード上へのポインタ)のもつ
Zero関数ポインタが示す関数を実行するのでした。
Zero()イベントが成立したとき
Start状態の場合は、Map1_Start_Zero()を実行
Zeros状態の場合は、Map1_Zeros_Zero()を実行
Ones状態の場合は、Map1_Ones_Zero()を実行
Error状態の場合は、Map1_Error_Zero()を実行
Zero()成立時、わざわざ状態を判定しなくても良いのが良いですね。
おさらい。
smcが生成するCのコードは、
- 状態 x イベント分の関数を生成し、遷移先を記述する。
- ROMコード上に状態つくり、遷移は関数テーブルで格納する。
- 現在状態はROMコード上の状態へのポインタで表現する。
- 遷移は、現在の状態のもつイベント(関数ポインタ)を実行する。
ことで実現する。
最初は分かりづらいコードだと思いましたが
ROMコード上に、実際に状態が存在し、ポインタで
現在状態を示すのは実世界を具現化しているようで
面白いコードだと感じました。
次回は他言語でもコード生成を行なってみます。
SMC(The State Machine Compiler)を試す その1
デビッドハレルが1987年に状態遷移図を提唱してから四半世紀。
今でも状態遷移設計、状態遷移プログラミングが
廃れることなく、当たり前のように開発の現場で利用されています。
今日は状態遷移設計プログラミングの味方となる
SMC (The State Machine Compiler)というツールを試してみました。
SMCはテキストで書いた状態機械定義から、
ステートパターンのコードを生成してくれるツールです。
プロジェクトページ
バージョン
2012/3/24現在のバージョンは 6.1.0 です。
対応言語
なんと15もの言語に対応してくれます。
個人的にはC,C++,Rubyだけでも十分なのですが、
対応言語が多いのは嬉しいですね。
ついでにHTMLテーブルやGraphVizのDOTファイルまで
出力してくれるようです。
ダウンロード
SmcSrc_6_1_0.zip
インストール
SmcSrc_6_1_0.zip を伸張します。
~/work/smc
どうやって使うの?
README.txtを読んでみるとJavaが必要なようです。
JRE (Standard Edition) 1.6.0 or better.
SMC自体のビルド等は要らなそうです。
実行ファイルはどれ?
~/work/smc/bin/Smc.jar
JAR = Java Archiveなんだけどなんでbinにあるのかな
と思ったら、JARは圧縮ファイルなんだけど
そのまま実行できるとか。ふむふむ。
サンプル
Cのサンプルを実行してみます。
% cd ~/work/smc/exsamples/C/EX1 % make java -jar ../../../bin/Smc.jar -c -g AppClass.sm gcc -g -I../../../lib/C -o checkstring AppClass_sm.c AppClass.c main.c
Smc.jarにAppClass.smを食わせて、AppClass_sm.c を生成し、
gcc でコンパイルされました。
実行してみましょう。
% ./checkstring 00000 The string "00000" is acceptable
動きました。
で、何のサンプルでしょう?
README.txtを見てみると...
This state machine "recognizes" the string 0*1*
(which includes the empty string).
とあるので文字列が 0個以上の0に続き、0個以上の1であれば
真となる状態遷移機械のようです。
% ./checkstring 0 The string "0" is acceptable % ./checkstring 1 The string "1" is acceptable % ./checkstring 000111 The string "000111" is acceptable % ./checkstring 010 The string "010" is not acceptable
しっかり動いています。
テキストで定義した状態遷移マップを見てみましょう。
Start
{
Zero Zeros {}
One Ones {}
Unknown Error {}
EOS OK {Acceptable();}
}
Zeros
{
Zero Zeros {}
One Ones {}
Unknown Error {}
EOS OK {Acceptable();}
}
...(以下略)
状態名
{
イベント 遷移先状態 {アクション();}
イベント 遷移先状態 {アクション();}
イベント 遷移先状態 {アクション();}
}
というルールです。わかりやすい。
遷移図を出力することもできます。
% make png
なるほどなるほど。
状態遷移マップから、状態遷移のコードが生成されるのは
わかりますが、状態遷移条件や、アクションの内容については
自動生成されるはずがありません。
なので、プログラマがどこかに記述しているはずです。
と言うわけで今回は、SMCのインストールと、
C言語のサンプルを実行してみました。
次回は実際に生成されたコードを読んでみたいと思います。
