Wanna be a Jorneyman

2013年8月19日月曜日

An easy application of fusion law

Pearls of Functional Algorithm Design読書会で、Birdさんの"An easy application of fusion law of foldr"という１文に対して２時間ほど、どうやって融合法則を適用するか喧々諤々の議論が行われましたが、なんとなくuprefixesの定義が導き出せたような気がするので記念に。

filter (all up) . unravels
= {- definition of unravels -}
  filter (all up) . foldr (concatMap .prefixes) [[]]

Fusion law of foldr.
If f is strict, f a = b, and f (g x y) = h x (f y), then f . foldr g a = foldr h b
Let f = filter (all up), g = concatMap . prefixes, a = [[]].
Then b = f a = f [[]] = [[]]. (try it in ghci!)

f (g x y)
= {- definition of (.) -}
  (f . g x) y
= {- definition of f and g-}
  (filter (all up) . (concatMap . prefixes) x) y
= {- definition of (.) -}
  (filter (all up) . concatMap (prefixes x)) y
= {- definition of concatMap -}
  (filter (all up) . concat . map (prefixes x)) y
= {- filter-concat law, filter p . concat = concat . map (filter p). IFPH p.108 -}
  (concat . map (filter (all up)) . map (prefixes x)) y
= {- map i . map j = map (i . j). IFPH p.106 -}
  (concat . map (filter (all up) . prefixes x)) y
= {- definition of concatMap -}
  concatMap (filter (all up) . prefixes x) y

HFusion : A Fustion Tool for Haskell prgramsで紹介されている関数融合方法に従って、 (fliter (all up))と
(prefixes x)を融合して関数(f' x)を導く。
http://babel.ls.fi.upm.es/services/talks/HFusion.pdf

関数融合を行うには、filter (all up)とprefixes xの定義を書き出して、以下の2つのステップを行なう。
 1. prefixes xのデータ・コンストラクタ((:)と[])をfilter (all up)の対応する出力で置き換える。
 2. prefixes xの再帰呼び出しをf' xで置き換える。

filter (all up)の定義。
filter (all up) :: [[[a]]] -> [[[a]]]
filter (all up) [] = []
filter (all up) (xs:xss) = if (all up) xs then xs : filter (all up) xss else filter (all up) xss
prefixes xの定義。
prefixes :: a -> [[a]] -> [[[a]]]
prefixes x [] = [[[x]]] = [[x]] : []
prefixes x (xs:xss) = [(x:xs):xss] ++ map (xs :) (prefixes x xss)

f' xを導出。
f' x []
= {- prefixes x [] の定義[[[x]]]は、[[x]] : []なので、データ・コンスラクタ(:)と[]がある。filter (all up)の定義より、[]は[]に、(:)は if ~ then ~ else ~に置き換える。-}
  if (all up) [[x]] then [[x]] : filter (all up) [] else filter (all up) []
= {- (all up) [[x]]は、常にTrueなので -}
  [[x]] : filter (all up) []
= {- filter p [] = [] -}
  [[x]] : []
= [[[x]]]
f' x (xs::xss)
= {- 上と同様にデータ・コンスラクタを置換する。prefixes x (xs::xss)の定義では第1項目 [(x:xs):xss]にデータ・コンストラクタ(:)と[]がある。また、prefixes xの再帰呼び出しをf' xに置換する。-}
  (if (all up) ((x:xs):xss) then ((x:xs):xss) : filter (all up) [] else filter (all up) []) ++ map (xs :) (f' x xss)
= {- filter p [] = [] -}
  (if (all up) ((x:xs):xss) then ((x:xs):xss) : [] else []) ++ map (xs :) (f' x xss)
= {- 連結をifの中へ -}
  if (all up) ((x:xs):xss) then [((x:xs):xss)] ++ map (xs :) (f' x xss) else map (xs :) (f' x xss)

f' xの定義をまとめると。
f' :: a -> [[a]] -> [[[a]]]
f' x []       = [[[x]]]
f' x (xs:xss) = if (all up) ((x:xs):xss) then
                  [(x:xs):xss] ++ map (xs :) (f' x xss)
                else map (xs :) (f' x xss)

今、融合法則の条件を満すため、f (g x y) = h x (f y)となる関数hを見つけたい。
h x (f y) = f (g x y) = concatMap (f' x) y
なので、hはある関数h'に対して以下のような形であると推測できる。
h x (f y) = concatMap (h' x) (f y)
fが(filter (all up))であるので、(f y)は、yの要素の中で、(all up)を満すような要素からなるリストである。
(h' x)は、(all up)を満すような値(zs:zss)を取り、(f x)と同じ結果を出力する関数。
h' :: a -> [[a]] -> [[[a]]]
h' x [] = f' x [] = [[[x]]]
h' x (zs:zss)
= {- h' xはf xと同じ出力をするので。-}
  f' x (zs:zss)
= {- f' xの定義。-}
  if (all up) ((x:zs):zss) then [(x:zs):zss] ++ map (zs :) (f' x zss) else map (zs :) (f' x zss)
= {- (all up) (zs:zss) = Trueと、all upの定義より、(all up) ((x:zs):zss) = x <= head zs -}
  if x <= zs then [(x:zs):zss] ++ map (zs :) (f' x zss) else map (zs :) (f' x zss)

このh'が待望のuprefixes。

hの第2引数(f y)にある性質を仮定することがhを導き出すポイントのような気がする。今回の場合、fが(filter all up)なのでhの第2引数は(all up)がTrueになるようなものしかとらない。そのため、if文の条件が簡単にできた。

2012年12月23日日曜日

Software Development for Infrastructureの紹介

静的次元解析

Bjarne Stroustrupさんが、C++11仕様の決定を記念して書いたC++のコーディング・スタイルに関する記事 Software Development for Infrastructureで紹介されていた静的次元解析のコードを試しに実装してみた。

C++11スタイルでコードを書くと今までのスタイルとまったく違うのコードになるのに驚いた。しかし、 C++のテンプレート静的に(実行時のオーバーヘッドなしで)、ここまでできるとは素晴らしい。

上記記事、ここに挙げた静的次元解析以外にもC++で実装するときにスタイルについて、助言が書かれているのでお勧めです。

 1:  #include <iostream>
 2:  
 3:  // 単位を表現するテンプレート・クラス。
 4:  template <int M, int K, int S>
 5:  struct Unit {
 6:    enum {m = M, kg = K, sec =S};
 7:  };
 8:  // 単位付き値を表現するテンプレート・クラス。
 9:  template <typename Unit>
10:  struct Value {
11:    double val;
12:    explicit constexpr Value(double b) : val(b) {}
13:  };
14:  
15:  using Speed = Unit<1,0,-1>;
16:  using Length = Unit<1,0,0>;
17:  using Time = Unit<0,0,1>;
18:  
19:  // -------------------------ユーザ定義リテラルの定義-----------------------------------------
20:  /*
21:    C++には組み込みのリテラルがありました。C++11から、ユーザがリテラルを定義できるようになりました。
22:  
23:    true; boolリテラル。
24:    "hello, world!"; 文字列リテラル。
25:    1l; longリテラル。
26:    1.0d; doubleリテラル。
27:  
28:    型安全なコードを書くために以下のようなリテラルを定義します。リテラルには(_)アンダースコアが
29:    含まれていることに注意。(_)を付けないリテラルは標準で予約さているので警告。
30:  
31:    30.0_km; 30 kmを表現するリテラル。
32:    2.0_hr; 2時間を表現するリテラル。
33:  */
34:  constexpr Value<Length>
35:  operator"" _km(long double d) {
36:    return Value<Length>(1000*d);// Lengthの基本単位がメートルなので、1000倍して、kmからmに変換。
37:  }
38:  
39:  constexpr Value<Time>
40:  operator"" _hr(long double d) {
41:    return Value<Time>(60*60*d);// Timeの基本単位が秒(sec)なので、時から秒に変換。
42:  }
43:  
44:  // ------------------------ 単位付き値に対する演算を定義。-------------------------------------
45:  template <typename Unit>
46:  Value<Unit> operator+(Value<Unit>&& lhs, Value<Unit>&& rhs) {
47:    return Value<Unit>(lhs.val + rhs.val);
48:  }
49:  
50:  template <typename Unit1, typename Unit2>
51:  Value<Unit<Unit1::m - Unit2::m, Unit1::kg - Unit2::kg, Unit1::sec - Unit2::sec>>
52:  operator/(Value<Unit1>& n, Value<Unit2>& d) {
53:    return Value<Unit<Unit1::m - Unit2::m, Unit1::kg - Unit2::kg, Unit1::sec - Unit2::sec>>(n.val/d.val);
54:  }
55:  
56:  // Valueが正しい単位を持っているか確認するための関数テンプレートisSpeed。
57:  template <typename T>
58:  constexpr bool isSpeed(){ return false; }
59:  
60:  template <>
61:  constexpr bool isSpeed<Value<Speed>>(){ return true; }
62:  
63:  // Valueを表示するために<<演算子をオーバーロード。
64:  template <typename Unit>
65:  std::ostream& operator<<(std::ostream& os, Value<Unit>& v){
66:    return (os << v.val << std::endl);
67:  }
68:  
69:  int main() {
70:    // 家からオフィスまでの通勤時の平均時速を求めたい。
71:    auto homeToOffice(30.0_km);// 家からオフィスまでの距離。30km
72:    auto time(1.0_hr);// 所要時間 1.0時間
73:    auto average_speed = homeToOffice/time;// 時速を計算。
74:    // 計算したaverage_speedの単位が正しいかチェック。
75:    static_assert(isSpeed<decltype(average_speed)>(),"Check failed!!");
76:    std::cout << average_speed << std::endl;
77:  
78:    // 距離と時間は足せない。コンパイル・エラー。
79:    // auto bug_1 = homeToOffice + time;
80:  
81:    // 時速を計算したいのに割り算が逆。static_assert部分でコンパイル・エラー。
82:    // auto bug_2 = time/homeToOffice;
83:    // static_assert(isSpeed<decltype(bug_2)>(),"Check failed!!");
84:  
85:    return 0;
86:  }

2012年11月24日土曜日

C vs Python vs Ruby vs Haskell(無意味な処理deベンチマーク)のC++版

memo.org

最近、nshinchan01さんのブログで、4つの言語を利用したコードの実行速度(しんちゃんの日記:C vs Python vs Ruby vs Haskell(無意味な処理deベンチマーク))の比較が行われていた。

TL上で、Haskellの実行速度がありえないほど早いのを見て興味を持ったので、C++11の勉強がてら、C++版でお題の問題を書いて実行時間を計測してみた。

詳しくは、nshinchan01さんのブログを見て欲しいが、お題は、4000x4000整数の2次元配列arrayがあり、arrayの要素array[i][j]は、整数4000*i+j+1。arrayの各要素array[i](整数の配列)を反転して、 arrayの最後尾の要素の最後尾の要素を表示する処理の実行時間を測定する。

C++11で導入されたRangeベースのforループ、autoキーワードを用いた型推論を利用してお題を解いてみると以下のようなコードになった。これを、clang++ version 3.0で、O3オプションを指定してコンパイル。

#include <algorithm>
#include <iostream>
#include <vector>

static const unsigned int N = 4000;
int main(int argc, char *argv[]) {
  std::vector<std::vector<int> > array(N,std::vector<int>(N));
  int i = 0;
  for (auto& a: array) {
    std::iota(a.begin(),a.end(),N*i+1);
    ++i;
  }
  for (auto& a: array) {
    std::reverse(a.begin(), a.end());
  }
  std::cout << array.back().back() << std::endl;
  return 0;
}

しんちゃんの日記:Haskellで実行時間計測用のコマンドを作るで作った、difftimeコマンドを利用して実行時間を測定。10回の平均を取ると、0.2824988secになった。

nshinchan01さんのブログに書いてある、Cのコードを同じ環境で測定した結果は、0.2928458secとなり、C++との差が3%程とC++でCのコードと遜色のないコードが書けることがわかる。(※ただ、nshinchan01さんのところではCのコードの実行時間が0.083と、手元の環境より3倍ほど早いのが気になる。コンパイラの違いかな？)

で、最初にC++で実装するきっかけとなったHaskellのコードだが、C/C++と同じ環境で測定すると0.0282011sec となり、C/C++の約10倍という圧倒的な性能となる(^^;) Haskell恐るべし。

ただ、Haskellって遅延評価(データが欲しいときに計算を実行する)なので、Haskellとその他の言語での実装を比較するときは、問題の設定方法に気をつけないとまともな比較にならない。

今回のお題では、4000x4000の配列を生成して(処理1)、その配列を反転して(処理2)、最後尾の要素の最後尾の要素を取得(処理3)する。3処理の実行時間を計測するというもの。C/C++のような命令型であれば、処理を順に書いていくだけで単純だけど、Haskellだと遅延評価のおかげで余分な処理を実行されないので、3つの処理が実際に実行されているかはわからないような気がする。(多分されていない)

ともかく、Haskell適切に書くと読み易く効率の良いコードが書けるのが素晴しい。C++でも、遅延評価の仕組みを取り入れてHaskellにせまる実行速度のコード書けるのかな？(そもそも最初は、Templateメタプログラミングでコンパイル時に問題を解いて答えを表示するだけのコードを実装しようとしたけど、コンパイルが終了しなかったorz)

2012-11-24 Sat 13:55

2012年9月12日水曜日

emacsからBloggerに記事を投稿する方法。

outfile

普段、emacsの中で生活しているのでBloggerへの記事の投稿もemacsから行いたい(それほど、投稿は多くないのだけど。。。)

emacsからBloggerへの投稿には、Ideas and Bulbs - Andrei Matveyeuで紹介されているemacsのorg-modeと pythonスクリプトbloggerpost.pyを利用した方法を試す。org-modeはかなり有名なパッケージなので、説明は省略。

bloggerpost.pyは、Beautiful Sourp library(python HTML/XML parser)、googlecl(Googleサービスを利用するためのコマンド・ライン・ツール)に依存しているため、これらのライブラリをインストールする。

Ubuntuならばこれらのツールのパッケージが用意されているため、以下のコマンドでインストール。

sudo apt-get install python-beautifulsoup googlecl

続いて、bloggerpost.pyをダウンロードし適当な場所(例えば、~/bin)に配置する。

スクリプトbloggerpost.pyを開き、以下のオプションを自身の環境に合せて編集する。

username="my_google_user_name" #Googleのユーザ名。
orgelc="path_to_org_el" # ファイルorg.elへのパス。例えば、/usr/share/emacs/23.3/lisp/org/org.elc

emacsをバッチ・モードで実行し投稿するためのHTMLを生成している以下のラインで、org-mode 7.9.1ではHTMLの生成に失敗するため以下のように修正する。

# 修正前
os.system("""emacs --batch --load="""+orgelc+""" --visit """+outfile+""" --funcall org-export-as-html-batch """)
# 修正後。 path_to_org_mode_dir_lispはorg-modeパッケージのlispディレクトリ。例えば、 ~/.emacs.d/elisp/org-7.9.1/lisp/
os.system("""emacs --batch --directory=path_to_org_mode_dir_lisp --load="""+orgelc+""" --visit """+outfile+""" --funcall org-export-as-html-batch""")

スクリプトbloggerpost.pyでは、Asciiでエンコードできない文字列を含む記事を投稿しようとすると、googleclの呼び出しでエンコード・エラーになる。このエラーを回避するためにgoogleclの呼び出しと呼び出し用のコマンドcommand生成処理を修正する。

if tags<>"":
    # 修正前
    command=unicode(googlecl+u' blogger post --draft -u '+username+' --blog '+blogname+' --tags "'+tags+u'" --title "'+title+u'" '+postHTML)
    # 修正後
    command=unicode(googlecl+' blogger post --config /home/taka/.googlecl/config --draft -u '+username+' --tags "'+tags+'" --title "'+title+'" '+postHTML)
else:
    # 修正前
    command=unicode(googlecl+u' blogger post --draft -u '+username+' --blog '+blogname+' --title "'+title+u'" '+postHTML)
    # 修正後
    command=unicode(googlecl+' blogger post --config /home/taka/.googlecl/config --draft -u '+username+' --title "'+title+'" '+postHTML)

# 関係のないコードを省略。

# 修正前
os.system(command)
# 修正後
os.system(command.encode('utf-8'))

上記設定で、org-modeからBloggerに記事を投稿できるようになる。org-modeのファイルを開き、投稿したいツリーをリージョンとして選択する。ツリーが閉じられている場合は、ツリーのタイトルをリージョンとして選択。ツリーが開いている場合は、ツリー全体を選択。選択している状態で、M-x shell-command-on-regionで、リージョンに対して bloggerpost.pyを実行する。

2012年3月21日水曜日

Slimeで日本語を使用する

slimeモードで日本語を使おうと、以下の式を評価すると、

(code-char #\あ)

エラーに遭遇。

Coding system iso-latin-1-unix not suitable for "000041(:emacs-rex (swank:interactive-eval \"(char-code #\あ)\") nil t 1)"

slimeがSwankサーバ(common lispを実行するサーバ)と通信するためのエンコーディング設定が上手くいっていないため起きるエラー。

slimeがSwankサーバとの通信に使用するエンコーディングは、変数slime-net-coding-systemで決定される。この変数に'utf-8-unixを設定すると無事日本語が利用できるようになる。以下のように .emacsなどでslime-net-coding-system変数を変更する。

(setq slime-net-coding-system 'utf-8-unix)

すでに、slimeモードでSwankサーバを起動している場合、上記設定の変更を有効にするにはサーバ(inferior-lispプロセス)を終了して、再度起動しなおす必要がある。

参考URL:
'T: CREATE-SERVERしたSWANKに接続すると日本語の評価で切断してしまう
 Common LISP users jp:SLIME

2012年3月18日日曜日

Ubuntuでclangを利用する

clangは、GCCを置き換えることを目的としたコンパイラフロント・エンド。AppleやGoogleなどのサポートを受け活発に開発が進められている。

GoogleではC++で記述されたコードベースのリファクタリングにclangを利用しているという動画 Clang MapReduce – Automatic C++ Refactoring at Google Scaleを見て興味を持ったので clangを試してみる。

ubuntuでは、clangパッケージが存在するので、

apt-get install clang

で、必要なパッケージをインストール。

早速、Hello Worldをclangでコンパイル。

#include <iostream>

int main(int argc, char *argv[]) {
  std::cout << "Hello, world!" << std::endl;

  return 0;
}

clang HelloWorld.cpp

すると以下のようなエラー・メッセージが出てコンパイルに失敗。

/usr/bin/ld: /tmp/cc-sx9qR1.o: in function __cxx_global_var_init:HelloWorld.cpp(.text+0xc): error: undefined reference to 'std::ios_base::Init::~Init()'

/usr/bin/ld: /tmp/cc-sx9qR1.o: in function __cxx_global_var_init:HelloWorld.cpp(.text+0x30): error: undefined reference to 'std::ios_base::Init::Init()'
/usr/bin/ld: /tmp/cc-sx9qR1.o: in function main:HelloWorld.cpp(.text+0x65): error: undefined reference to 'std::basic_ostream<char, std::char_traits<char> >& std::endl<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&)'

/usr/bin/ld: /tmp/cc-sx9qR1.o: in function main:HelloWorld.cpp(.text+0x70): error: undefined reference to 'std::cout'
/usr/bin/ld: /tmp/cc-sx9qR1.o: in function main:HelloWorld.cpp(.text+0x99): error: undefined reference to 'std::basic_ostream<char, std::char_traits<char> >& std::operator<< <std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*)'

/usr/bin/ld: /tmp/cc-sx9qR1.o: in function main:HelloWorld.cpp(.text+0xa5): error: undefined reference to 'std::basic_ostream<char, std::char_traits<char> >::operator<<(std::basic_ostream<char, std::char_traits<char> >& (*)(std::basic_ostream<char, std::char_traits<char> >&))'

collect2: ld returned 1 exit status
clang: error: linker (via gcc) command failed with exit code 1 (use -v to see invocation)