【お知らせ】プログラミング記事の投稿はQiitaに移行しました。
ブログに図を入れるとき、別途作成してPNGで保存してアップするのは面倒です。インラインでSVGを埋め込むのはどうかと思いつき、試してみました。
<svg width="150" height="100" style="border:solid 1px black"> <circle cx="75" cy="50" r="30" fill="red"></circle> </svg>
ドローソフトで描いたSVGをコピペするのでは、PNGをアップするのと比べてもあまり手間が軽減されません。HTMLの手書きと同じような感じでSVGを手書きできれば良いのですが、果たしてそれは現実的なのでしょうか。慣れで済む問題なのかどうか、少し試してみようと思います。
昨日告知した初心者TypeScript入門の資料が完成しました。事前公開します。
簡単な思考ルーチンを実装しています。以下に動く状態のものを貼っておきますので、実際に試せます。コンピュータは後手固定です。
【追記】JSX移植版が公開されています。
ランダムに打つ思考ルーチンです。かなり弱いです。
一手に限定して、一番たくさん取れる場所を探して打つ思考ルーチンです。これも弱いです。
乱数を大量に使用するアルゴリズムです。ゲーム終了まで乱数で打ち続けることを1,000回繰り返して、一番勝率の高い場所に打ちます。やや強く、隅を狙ってきたりもしますが、そこまで強いわけではありません。
勝率を表示して、どのように分布しているのか確認できます。
ソース: https://bitbucket.org/7shi/ts-reversi/src/82c11bf7ceae9fa6c6fd16208195ff659680673f/Reversi.ts
3/15(金)19:00より初心者TypeScript入門を開催します。リバーシ（いわゆるオセロ）を作りながらTypeScriptに挑戦する初心者向けの勉強会です。
資料用に途中まで作ったリバーシを貼っておきます。他のサイトを埋め込んでいるのではなく、はてなブログの中に全部書いて動いているのが面白いです。
ソース: https://bitbucket.org/7shi/ts-reversi/src/1a39e97194bc1d577222894644ed8d16b4bf4b7a/Reversi.ts
PEの.idataをアセンブリ言語で記述しながら説明します。
PEからDLLを参照するには.idataセクションにDLL名とシンボル名を記述します。実行時にWindowsのローダが.idataを見てLoadLibraryとGetProcAddressに相当する処理を行い、取得したアドレスを.idataに書き込みます。アドレスが書き込まれる領域はサンクと呼ばれており、あらかじめ.idataに用意しておきます。プログラムはサンクに書き込まれたアドレスをcallすることでDLL内の関数を呼べます。
例:
| DLL | シンボル | サンク |
|---|---|---|
| a.dll | foo | |
| bar | ||
| b.dll | hoge | |
| fuga |
これがどのようにバイナリに落とされているかを見ていきます。
.idataの大まかな構造は以下の通りです。
| 名称 | 型 | 対応 |
|---|---|---|
| IDT (Import Directory Table) | IMAGE_IMPORT_DESCRIPTOR | DLL |
| ILT (Import Lookup Table) | DWORD | シンボル |
| IAT (Import Address Table) | DWORD | サンク |
| Hint/Name Table | IMAGE_IMPORT_BY_NAME | 序数・文字列（シンボル） |
| DLL Name | char | 文字列 |
文字列データは後ろの方に並んでおり、IDTやILTにはオフセットが格納されています。
参照されるDLLの数だけIMAGE_IMPORT_DESCRIPTORがあり、その後に終端としてゼロで埋められたIMAGE_IMPORT_DESCRIPTORが来ます。
フィールドにはILT/DLL名/IATへのポインタが格納されます。それ以外のフィールドは必須ではないため説明を省略します（ゼロのままでも動きます）。
ポインタの値はモジュールの先頭からの相対アドレスです。仕様書ではRVA（相対仮想アドレス）と呼ばれます。例えばEXEが0x00400000に配置され、.idataが0x00402000に配置された場合、.idataのRVAは0x2000となります。
例: （nasm形式）
org 0x2000 IDT_A_DLL: dd ILT_A_DLL, 0, 0, A_DLL, IAT_A_DLL IDT_B_DLL: dd ILT_B_DLL, 0, 0, B_DLL, IAT_B_DLL IDT_LAST : dd 0, 0, 0, 0, 0
DLLごとに、参照されるシンボルの数のH/N Tableへのポインタと終端のヌルポインタがあります。
例:
ILT_A_DLL: dd HN_foo , HN_bar , 0 ILT_B_DLL: dd HN_hoge, HN_fuga, 0
ILTは必須ではなく、なくても動きます。ILTがない場合、実行時にメモリ上のILTを参照してH/N Tableを追うことができなくなります。 → PEの.idataを図解（ILTなし）
ILTとまったく同じです。サンクとして扱われ、実行時にWindowsによって値が書き換えられます。
例:
IAT_A_DLL: imp_foo: dd HN_foo imp_bar: dd HN_bar dd 0 IAT_B_DLL: imp_hoge: dd HN_hoge imp_fuga: dd HN_fuga dd 0
プログラムから以下のように呼び出します。
call [imp_foo] call [imp_bar] call [imp_hoge] call [imp_fuga]
C言語の場合、ヘッダで__declspec(dllimport)として明示されていなければ、このようなコードは生成できません。対策として、リンク時にトランポリンを生成する方法があります。
foo: jmp [imp_foo] bar: jmp [imp_bar] hoge: jmp [imp_hoge] fuga: jmp [imp_fuga]
トランポリンがあれば、通常の関数と同様に呼び出すことができます。
call foo call bar call hoge call fuga
シンボルの序数と名前が入っています。両方を指定する必要はなく、どちらか片方だけでインポートできます。文字列のルックアップ時間を節約するため、Windows CEでは序数のみでインポートすることが多いようです。今回の例では名前だけを指定します。
2バイトでalignする必要があります。
例:
HN_foo: dw 0 db "foo", 0 align 2 HN_bar: dw 0 db "bar", 0 align 2 HN_hoge: dw 0 db "hoge", 0 align 2 HN_fuga: dw 0 db "fuga", 0 align 2
ヌル終端の文字列を並べるだけです。
例:
A_DLL: db "a.dll", 0 B_DLL: db "b.dll", 0
.idataの各ブロックを別々に作りながらRVAを埋め込んで、最後に連結してアドレスを解決すると、ほぼ仕様のまま生成できます。
Buffer create() {
Buffer idt, ilt, iat, hn, name;
uint32_t zero = 0;
for (auto dll = begin(); dll != end(); ++dll) {
idt << ilt.rva() << zero << zero << name.rva() << iat.rva();
name << dll->first;
for (auto sym = dll->second.begin(); sym != dll->second.end(); ++sym) {
iat.put(sym->second);
ilt << hn.rva();
iat << hn.rva();
hn << uint16_t(0) << sym->first;
if (hn.size() & 1) hn << uint8_t(0);
}
ilt << zero;
iat << zero;
}
idt.expand(20);
return Buffer() << idt << ilt << iat << hn << name;
}
アドレスの決定を遅延させるのにラムダ式を使おうとして試行錯誤したけど、結局アドレスをスマートポインタで共有する方法に落ち着いた。idataの構築が簡単に記述できた。(IData::create) ideone.com/c85psd
— 七誌さん (@7shi) 11月 23, 2012F# Advent Calendar 2012 第16日目の参加記事です。
今年のF# Advent Calendarは実用がテーマです。私はアクティブパターンをなかなか実用できないでいましたが、ようやく端緒がつかめたという話を書きます。その前に実用関連として、勉強会でF#を使おうとしたときの話を書きます。
私は以前から、中高生の数学学習に数式処理プログラムの自作が応用できないかということに興味を持っていました。Expert F# 2.0の第12章に数式処理についての言及があったため、それをテーマとした勉強会を開催しました。
当初の想定では数式処理が目的で、F#の学習が目的ではなかったため、簡単にF#の読み方を説明するだけに留める予定でした。ですがF#の説明を始めると想像以上に時間が掛かり、本題の数式処理まであまり手が回りませんでした。
言語の説明を適当に飛ばしてすぐに本題に入った方が無難なため、C#に切り替えることにしました。C#自体を知らなくてもJavaなどの知識から類推が利くのは大きいです。
でもやっぱりF#に比べると冗長だと感じます。理想としては、F#の知識を前提とせずにすんなり手段として使い始められるようなうまい導入をしたいです。そうすればサンプル記述用の言語としてどんどん実用できそうだという予感はあります。この方面も機会があればまた取り組んでみたいと思います。
本題のアクティブパターンに入ります。
初めてアクティブパターンを見たとき、構文の意味自体は分かりましたが、それをどういうときに使うと嬉しいのかピンと来ませんでした。そのためF#でプログラムを書くときにもアクティブパターンはまったく使いませんでした。
こういうとき、自分の書いたコードの中でアクティブパターンが適用できる箇所を指摘できれば、ぐっと実用に近付きそうです。つまり新しい知識として追加するのではなく、既存の知識の延長線上として位置付けるという発想です。判別共用体を抽象クラスの継承として捉えることでようやく腑に落ちたという前例があります。
同様に、既存のコードをアクティブパターンで書き直してみます。
例として字句解析を取り上げます。
字句解析する際に、文字の種類を判定する必要があります。C#で例を挙げます。
private void Parse(TextReader tr) { int ch = tr.Read(); if (ch < 0) Console.WriteLine("終端"); else if (ch == '\r' || ch == '\n') Console.WriteLine("改行"); else if (ch == ' ' || ch == '\t') Console.WriteLine("空白"); else if ('0' <= ch && ch <= '9') Console.WriteLine("数字"); else if (ch == '_' || ('A' <= ch && ch <= 'Z') || ('a' <= ch && ch <= 'z')) Console.WriteLine("文字"); else Console.WriteLine("不明"); }
※全角文字を対象外とするためchar.IsDigitなどは使っていません。
同じような条件分岐を複数個所で行う場合、毎回条件を書くのは無駄です。条件を修正するときに複数個所で同じ修正をする羽目になります。
このような場合は種類を列挙型で定義して、判定するメソッドを1つだけに絞ることで対応できます。
enum CharType { End, NewLine, Space, Digit, Letter, Unknown } private CharType GetCharType(int ch) { if (ch < 0) return CharType.End; else if (ch == '\r' || ch == '\n') return CharType.NewLine; else if (ch == ' ' || ch == '\t') return CharType.Space; else if ('0' <= ch && ch <= '9') return CharType.Digit; else if (ch == '_' || ('A' <= ch && ch <= 'Z') || ('a' <= ch && ch <= 'z')) return CharType.Letter; else return CharType.Unknown; } private void Parse(TextReader tr) { switch (GetCharType(tr.Read())) { case CharType.End: Console.WriteLine("終端"); break; case CharType.NewLine: Console.WriteLine("改行"); break; case CharType.Space: Console.WriteLine("空白"); break; case CharType.Digit: Console.WriteLine("数字"); break; case CharType.Letter: Console.WriteLine("文字"); break; case CharType.Unknown: Console.WriteLine("不明"); break; } }
C#をそのままF#で書き直してみます。
type CharType = | End = 0 | NewLine = 1 | Space = 2 | Digit = 3 | Letter = 4 | Unknown = 5 let getCharType ch = if ch < 0 then CharType.End else let ch = char(ch) if ch = '\r' || ch = '\n' then CharType.NewLine elif ch = ' ' || ch = '\t' then CharType.Space elif ch = '_' || ('A' <= ch && ch <= 'Z') || ('a' <= ch && ch <= 'z') then CharType.Letter else CharType.Unknown let parse (tr:TextReader) = match getCharType(tr.Read()) with | CharType.End -> printfn "終端" | CharType.NewLine -> printfn "改行" | CharType.Space -> printfn "空白" | CharType.Digit -> printfn "数字" | CharType.Letter -> printfn "文字" | _ -> printfn "不明"
ほとんど直訳ですが、普通こんなコードは書かないでしょう。列挙型を判別共用体にして、判定をパターンマッチで書き換えてみます。
type CharType = | End | NewLine | Space | Digit | Letter | Unknown let getCharType ch = if ch < 0 then End else match char(ch) with | '\r' | '\n' -> NewLine | ' ' | '\t' -> Space | ch when '0' <= ch && ch <= '9' -> Digit | ch when ch = '_' || ('A' <= ch && ch <= 'Z') || ('a' <= ch && ch <= 'z') -> Letter | _ -> Unknown let parse (tr:TextReader) = printfn <| match getCharType(tr.Read()) with | End -> "終端" | NewLine -> "改行" | Space -> "空白" | Digit -> "数字" | Letter -> "文字" | Unknown -> "不明"
構造はほとんど同じですが、書式が簡潔になりました。簡潔になるというのは「直訳でも書けるけど、なるべくこういう書き方をして欲しい」という示唆かと思います。
判別共用体と判定関数を別々にしていますが、アクティブパターンを使えば1つにまとめることができます。
let (|End|NewLine|Space|Digit|Letter|Unknown|) ch = if ch < 0 then End else match char(ch) with | '\r' | '\n' -> NewLine | ' ' | '\t' -> Space | ch when '0' <= ch && ch <= '9' -> Digit | ch when ch = '_' || ('A' <= ch && ch <= 'Z') || ('a' <= ch && ch <= 'z') -> Letter | _ -> Unknown let parse (tr:TextReader) = printfn <| match tr.Read() with | End -> "終端" | NewLine -> "改行" | Space -> "空白" | Digit -> "数字" | Letter -> "文字" | Unknown -> "不明"
かなり簡潔になりました。こういう風に書けるようにすることがアクティブパターンの着想なのかなと思います。
ちなみに(|...|)の部分を単なる名前とみなして関数として呼ぶこともできます。
let parse (tr:TextReader) = printfn <| match (|End|NewLine|Space|Digit|Letter|Unknown|) (tr.Read()) with | End -> "終端" | NewLine -> "改行" | Space -> "空白" | Digit -> "数字" | Letter -> "文字" | Unknown -> "不明"
わざわざ明示的に呼ばなくても自動的に呼ばれる点がアクティブという名前の由来なのかなと思います。
マッチしない _ を含めたものをパーシャルアクティブパターンと呼びます。これを利用すれば個々のパターンを別々に定義することができます。
let (|End|_|) ch = if ch < 0 then Some End else None let (|NewLine|_|) = function '\r' | '\n' -> Some NewLine | _ -> None let (|Space|_|) = function ' ' | '\t' -> Some Space | _ -> None let (|Digit|_|) ch = if '0' <= ch && ch <= '9' then Some Digit else None let (|Letter|_|) ch = if ch = '_' || ('A' <= ch && ch <= 'Z') || ('a' <= ch && ch <= 'z') then Some Letter else None let parse (tr:TextReader) = printfn <| match tr.Read() with | End -> "終端" | ch -> match char(ch) with | NewLine -> "改行" | Space -> "空白" | Digit -> "数字" | Letter -> "文字" | _ -> "不明"
前の例とどちらが読みやすいかは好みが分かれそうです。Unknownのようなものを定義しなくて済むのと、個々の定義が局所化されるため個別に利用できるのはメリットだと思います。終端だけ型が異なるためぎこちない書き方になっていますが、これは題材の問題です。
「新しい枠組みとして捉えて、既存のものにとらわれずに考え方を変える」のが理想ですが、現実的にはなかなか難しいです。既存の延長線上で変形して徐々に慣れれば、いずれ変形を意識しなくても実用できるようになると期待しています。
そういう意味で「既存の考え方でも書ける」というF#の特徴は、私にとってはとてもありがたいです。うまくハマったときにとても簡潔になるのは、パズルのようです。最初は泥臭く書いておいて、後で最適化するようなイメージでしょうか。
今回の記事を書くにあたってMicrosoftのF#言語リファレンスを参照しました。いつの間にか日本語訳されていて、説明も結構分かりやすいです。
これは是非目を通さねば！というわけで勉強会を企画しました。
一通りリファレンスに目を通したらfscのソースコードも読みたいですね。
Gtk#のウィジェットにファイルをドラッグ＆ドロップで渡します。
受け取る種類を指定しておくと、ドロップしたときにDragDataReceivedシグナルが発生します。ファイルは "text/uri-list" です。URIで渡されるため、ローカル名に変換が必要です。
using System; using System.Text; using Gtk; class MainClass { public static void Main () { Application.Init (); var win = new Window ("Test DnD") { DefaultSize = new Gdk.Size (100, 100) }; win.DeleteEvent += (o, args) => { Application.Quit (); args.RetVal = true; }; var vbox = new VBox (false, 5); var label = new Label (); var text = new TextView (); vbox.Add (label); vbox.Add (text); win.Add (vbox); var targets = new [] { new TargetEntry ("text/uri-list", TargetFlags.OtherApp, 0) }; Drag.DestSet (label, DestDefaults.All, targets, Gdk.DragAction.Copy); Drag.DestSet (text, 0, targets, Gdk.DragAction.Copy); label.DragDataReceived += HandleDragDataReceived; text.DragDataReceived += HandleDragDataReceived; win.ShowAll (); Application.Run (); } static void HandleDragDataReceived (object o, DragDataReceivedArgs args) { Console.WriteLine (args.Time); var uris = Encoding.ASCII.GetString (args.SelectionData.Data) .Replace ("\r", "").Replace ("\0", "").Trim ().Split ('\n'); foreach (var s in uris) { var uri = new Uri (s); if (uri.IsFile) Console.WriteLine (uri.LocalPath); } } }
Drag.DestSet() はLabelとTextViewで挙動が異なります。Labelでは2番目の引数にDestDefaults.Allを指定する必要があります。しかしTextViewでDestDefaults.Allを指定するとなぜか2度イベントが通知され、Windowsでは2回目の通知で妙なファイルが渡されます（Xでは1回目と同じ）。そのためゼロを指定しておく必要があります。
【追記】WindowsではLabelにDestDefaults.Dropを指定してもドロップを受け付けますが、Xでははじかれました。
これはC言語からGTK+を直接使用しても同じ結果となりました。GTK+本来の挙動だと思われます。
C言語で同じコードを書いてみると、改めてGtk#が薄いラッパーだと思いました。
ここまで見てきた計算方法で、どれくらい高速化するか実験します。
続きを読む