FRP (Functional Reactive Programming) とは何か
FRPというプログラミング手法について調べたので纏めてみます。
Functional Reactive Programming (以下FRPとも呼ぶ)とは, プログラミング・パラダイム(方法論)の一種です.
例えばObject Oriented Programming (オブジェクト指向プログラミング, 以下OOPとも呼ぶ)なんかと同列の言葉ですね.
OOPによってプログラムを簡潔に書ける場合があるように,
FRPによってある種のプログラムをとても簡潔に記述することができます.
※ここで一応注意しておきたいのは, OOPやFRPというのは, プログラミング言語の性質を表しているわけではなく, あくまでプログラミングの方法論に過ぎないということです. たとえばJavaやRubyはオブジェクト指向を言語の核に取り入れていますが, 言語としてオブジェクト指向をサポートしていないC言語などでも, オブジェクト指向プログラミングを行うことは可能です.
Reactive Programmingとは
FRPとは, 文字通りFunctional(関数的な) Reactive Programmingという意味です.
そこで, まずはReactive Programmingとは何かについて考えてみます.
最初に, 誤解を恐れずにReactive Programmingの本質を一言で説明すると「値そのものではなく, 値をもらう対象を保持するデータ型」を用いるプログラミングである, と言えます.
通常のプログラミングにおいては,
b = a + 1
というのは, 変数aの値に1を足した値を変数bの値とする, という意味を持つ場合が多いと思います.
しかし, Reactive Programmingにおける意味はこれとは異なり,
変数bの値は常に「変数aの値と1を足した値」であることを宣言する, という意味を持ちます.
従って, Reactive Programmingの意味において, 以下の疑似コードの出力は3となります.
a = 1 b = a + 1 a = 2 print b
一見すると奇妙なふるまいに思えるかもしれませんが, 論理回路のassignment(結線)に近い意味であるとも言えます.
e = a & b (結線) f = c & d (結線) g = e & f (結線) a = b = c = d = 1 (入力) test g == 1 (gが1であることを確認) a = 0 (入力の変更) test g == 0 (gが0であることを確認)
このように, 依存先となる(ここでは変数a)の変化に応じて反応的に変化が伝搬することから,Reactive(反応的) Programmingと呼ばれます.
さて, 「変数bの値は常に変数aの値と1を足した値であることを宣言する」という操作をもう少し現実的に考えてみましょう.
これは要するに, 変数bの値は「値をもらう対象(変数a)」と「それに1を加えるという手続き」を保持するデータ型であると言えます.
最初に述べた,「値そのものではなく, 値をもらう対象を保持するデータ型」を用いるプログラミングである, とはつまりこのことです.
Reactive Programmingで何が便利になるのか
次にReactive Programmingの用途を簡単に説明します.
Reactive Programmingが用いられている最も身近な例は, Excellなどの表計算ソフトです.
大半の表計算ソフトには関数などと呼ばれる機能があり,ユーザーはセル単位で簡単なプログラミングを行うことができます.
例えば, C1のセルを選択し, 「= B1 + B2」と入力すると, C1のセルの値はB1とB2のセルの値を足した値となります.
また,その後にB1のセルの値を変更すると, それに応じてC1のセルの値も自動的に変更されます.
すなわち, 最初に行った「C1を選択し, = B1 + B2と入力する」という操作は,
「セルC1の値は常にセルB1の値とセルB2の値を足した値であることを宣言する」操作に他なりません.
これはつまり, 表計算ソフトのユーザーは無意識のうちにReactive Programmingを行っているということです.
もしReactive Programmingを用いずに同じことを実現しようとすれば,
「セルB1およびセルB2の値が変更される度にセルC1の値を更新する」プログラムを, ユーザーが明示的に書くことになるでしょう. それではとても面倒ですね.
C言語でReactive Programmingしてみる
上で例として挙げた,
a = 1
b = a + 1
a = 2
print b (3が出力される)
といった極単純なReactive ProgrammingをC言語で実現してみましょう.
とりあえずはmain関数の中だけに注目してください.
main関数の中で行っていることは, コメントに記してある通りで,
52行目から58行目にかけてReactiveな(整数型の)値を宣言し,
60行目から62行目にかけてそれを操作しています.
※ここで少し注意して欲しいのは, 上記のC言語プログラムにおいて, 「Reactive Programmingを行っている」のは, あくまでmain関数の中においてのみであるということです. 1行目から46行目にかけて記述された処理は, あくまで「Reactive Programmingを行うための舞台セッティング」に過ぎません.
Reactive ProgrammingからFunctional Reactive Programmingへ
上記のC言語によるReactive Programmingは, 次の2つの部分に分けて考えることができます.
- Reactiveな値を宣言する部分(52行目から58行目)
- Reactiveな値を命令的に操作する部分(60行目から62行目)
ここまでの知識を用いてFunctional Reactive Programmingを一言で説明すると,「Reactiveな値を宣言する部分のみを用いたReactive Programming」であると言えます.
「Reactiveな値を宣言する部分」だけを用いてReactive Programmingを行い,
実際に意味のあるプログラムを記述することができるのか疑問に思うかもしれません.
ところが, 「Reactive Programmingを行うための舞台」が,
「元となるReactiveな入力値」と「Reactiveな値を最終的に出力する対象」を用意してさえおけば,
意外にも簡単に, というより(普通に)命令的に処理を記述するよりも直感的にプログラムを記述することができます.
例として, 標準入力から文字列を受け取り,その文字列に含まれる矢印キーの個数をカウントして現在の座標を出力するプログラムをFRPによって実現することを考えてみましょう.
(例えば, 「↑↑→→↓」と入力してEnterを押すと, (2, 1)が出力されるようなプログラムです.)
ここで「元となるReactiveな入力値」を
input = 標準入力 :: Reactiveな文字列
「Reactiveな値を最終的に出力する対象」を
output = 標準出力 :: Reactiveな整数のペア
と考えれば, このプログラムは以下の様に定義することができます.
up = inputに含まれる, ↑キーに相当する文字の個数
down = inputに含まれる, ↓キーに相当する文字の個数
left = inputに含まれる, ←キーに相当する文字の個数
right = inputに含まれる, →キーに相当する文字の個数
x = right - left
y = up - down
output = (x, y)これをC言語で記述すると, 例えば以下の様になります.
main関数内の処理はあくまでもFRPの裏方であり, FRPを行っているのはFRPCursor関数内です.
FRPCursor関数は副作用を持たない純粋な関数であることが分かります.
これこそが, FRPのFunctional(関数的)たるゆえんとなります.
includeファイルfrp_sample_lib.hは, 本例のために作成したFRPライブラリのヘッダファイルです.
ライブラリ(frp_sample_lib.c)の内容を見たい場合, あるいは上記プログラムを実行してみたい場合は,
こちらからどうぞ.
FRPとプログラミング言語
FRPの本質は言語の性質に依存しないということを強調するため,
本記事では典型的な手続き型言語である(ようするに, 普通のプログラミング言語である)C言語を用いてFRPの例を示しましたが,
高階関数や型推論などの機能を備えた関数型言語を用いることにより, より強力かつ簡潔にFRPを実現することができます.
(実際にFRPを語る上ではその辺りが一番大事な話であるわけですが, 本記事では扱いません.)
FRPの研究とは
ここまで説明してきたように, FRPの本質は意外と単純です.
言葉通り, FunctionalでReactiveなプログラミングです.
関数型言語のHaskellとセットで語られることが多いのも相まって,
アカデミックなイメージが先行しがちですが,
その実体は簡潔かつ直感的にプログラムを記述するための一つの手法に過ぎません.
しかし本質の概念が単純とは言っても, 実際にFunctional Reactive Programmingを行うための舞台を実装しようとすると,
舞台裏の処理にかかる時間だったり, 舞台裏で保持しなければならないデータのメモリ量だったりに起因する,
やっかいな問題が色々と浮上します.
FRPが最初に提案されて以降のFRPの研究の本流は, そういったやっかいな問題を解決, ないしは上手く取り扱うための研究であると言えるでしょう.
おわりに
本記事の目的は「FRPとは何か」を体系的に説明することなので,
醍醐味であるFRPの(フレームワークの)実装手法については触れていません.
またFRPの"旨味"についても本記事ではあまり説明できていないので, そこに焦点を絞った記事も書くかもしれません.
参考
- What is (functional) reactive programming?
http://stackoverflow.com/questions/1028250/what-is-functional-reactive-programming/1030631#1030631
Stack Overflowにおける質問に対する回答ですが, FRPの本質を説明してくれています.
- やさしいFunctional reactive programming（概要編）
http://maoe.hatenadiary.jp/entry/20100109/1263059731
筆者がFRPを学ぶ際に最初に参考にさせてもらった記事です.
FRPについて日本語で書かれた記事は少ないので, 大変参考になりました.
- Elm: Concurrent FRP for Functional GUIs
http://elm-lang.org/papers/concurrent-frp.pdf
Elmという, FRPでGUIを扱うことに特化した言語についての論文です.
論文の前半部分においてFRPの過去の主要な研究について纏められていて, 参考になります.
FRPとは何かが分かっていて, 多少なりとも関数型言語の知識があれば読めると思います.
- Bacon.js
http://baconjs.github.io/
JavaScriptでFRPを行うためのライブラリです. Haskell等の知識が不要なので, そこそことっつきやすいです.
RubyでバイナリデータをパースするGemライブラリ(フレームワーク)を製作した話
Ruby-Binary-Parser (今回製作したライブラリ)
インストールはgemから可能。
gem install binary_parser
ソースはgithubに上げてある。簡単な使い方の説明もgithub上のREADMEに掲載。
https://github.com/sawaken/ruby-binary-parser
成り立ち (製作の動機)
個人的な興味(必要?)のため、MPEG-2/TS形式のファイルをパースするRubyのライブラリを作成しようと思い立ち、TSデータの構造を色々と調べ、大まかな構造は把握することが出来た。
しかしながら、TSデータの構造は多種多様なバイナリ構造の入れ子になっており、それらの構造をパースするプログラムを逐一実装していては、とても骨が折れるだろうことも同時に判明した。
そこで、TSデータのパーサーを作る前に、汎用的なバイナリデータ解析のフレームワークを作り、その上でTSパーサーを実装した方が効率的に(かつ美しく)目的を達成できると考えた。
※バイナリデータとは、広義にはビットで表現されたデータ全般を差すが、ここでは「特定の構造を持った、(画像や音声、あるいはプログラム等の)情報を表現するバイト列」をバイナリデータと称する。
Rubyでのバイナリデータ解析の実情
当然(?)のことながら、Rubyでバイナリデータを扱いたいと考える人間はあまり多くはないようで、少なくとも日本語での紹介記事などは殆ど無く、Rubyではバイナリデータを特別な文字コードの文字列として扱うこと、Array#packで数列をバイナリデータに変換出来る(その逆はString#unpackで出来る)こと等を紹介する記事がちらほら見られる程度であった。
また、似たようなGemライブラリ(バイナリ解析のフレームワーク)が既に存在しないか調べてみた所、それっぽい用途のライブラリは何件か見つかったものの、どうにもショボイというか、コレジャナイ感が強く、元々自分で作るつもりだったので探索は早々に打ち切り、製作に乗り出すことにした。
どんな「フレームワーク」が欲しいのか
理想的には、「フレームワークを利用する側の人間」が自らの手で行う必要のある唯一の仕事は、「自分がやりたいことを指示すること」であって、「それをどう実現するか」を考えるのは「フレームワークを作る側の人間」が行うべき仕事である。
このことを踏まえると、良いフレームワークの条件は主に以下の３つであると考えることができる。
Rubyはフレームワークが得意
Rubyがバイナリデータを扱うことに向いているかどうかはともかくとして、Rubyがフレームワークの記述(というよりかはDSLの構築)を得意とする言語であるというのは周知の事実である。
ピンと来ない方にとっては言葉で説明されるより現物を見た方が早い気がするので、そろそろ御託は止めにして、次項からはさっそく現物の紹介を始めたいと思う。
簡単な紹介 (github上のREADMEからの抜粋)
例えば、以下の定義を持つ画像データ形式(MyImage)を考える(説明のための仮想的なデータ形式)。
| MyImage (non-fixed length) | |||
| Data Name | Type | Bit Length | Number Of Replications |
| height | UInt | 8 | 1 |
| width | UInt | 8 | 1 |
| RGB color bit-map | UInt | 8 * 3 | 'height' * 'width' |
| has date? | Flag | 1 | 1 |
| date | MyDate | 31 | 'has date?' is 1 => 1 else => 0 |
| MyDate (31 bit) | |||
| Data Name | Type | Bit Length | Number Of Replications |
| year | UInt | 13 | 1 |
| month | UInt | 9 | 1 |
| day | UInt | 9 | 1 |
以上のバイナリデータ構造をフレームワーク上に定義すると、以下の通りとなる。
require 'binary_parser' class MyDate < BinaryParser::TemplateBase require 'date' Def do data :year, UInt, 13 data :month, UInt, 9 data :day, UInt, 9 end def to_date return Date.new(year.to_i, month.to_i, day.to_i) end end class MyImage < BinaryParser::TemplateBase Def do data :height, UInt, 8 data :width, UInt, 8 TIMES var(:height), :i do TIMES var(:width), :j do data :R, UInt, 8 data :G, UInt, 8 data :B, UInt, 8 end end data :has_date, Flag, 1 IF cond(:has_date){|v| v.flagged?} do data :date, MyDate, 31 end end end
この定義クラスを用いて画像データの情報を読み込んで表示するプログラムは、例えば以下の様に書ける。
File.open('my_image.bin', 'rb') do |f| image = MyImage.new(f.read) print "Image size: #{image.height.to_i}x#{image.width.to_i}\n" pix = image.i[0].j[0] print "RGB color at the first is (#{pix.R.to_i}, #{pix.G.to_i}, #{pix.B.to_i})\n" print "Image date: #{image.date.to_date}\n" end
ファイル 'my_image.bin' にバイナリデータ[0x02, 0x02, 0xe7,0x39,0x62, 0x00,0x00,0x00, 0xe7,0x39,0x62, 0x00,0x00,0x00, 0x9f, 0x78, 0x08, 0x03]を格納し、上記のプログラムを実行した結果が以下。
Image size: 2x2 RGB color at the first is (231, 57, 98) Image date: 2014-04-03
詳細なドキュメント
残念ながら全てを網羅したドキュメントは未だ用意できていない。
github上のREADMEには本記事よりは詳しい解説を載せているので、そちらを参照して頂きたい。
Intel GalileoでPT3を動かす
IntelのGalileoという開発ボードの存在を知った。調べてみたところ、要するにRaspberry Piみたいなもののようだ。
ただしIntel製なのでアーキテクチャはRaspberry Piと異なり、ARMではなくx86(i586)。
ついでにRaspberry Piには無いMini-PCI-Expressスロットも備えている。
さてここからが本題。
x86でPCI-Expressスロット装備のボードとなれば、デジタル放送チューナーを載せてみたくなるのが人情、ということでGalileoを購入し、PT3を載せてみた。その手順を以下に記録しておく。
準備1. 必要な機器を全て接続する
※Galileoのフォームウェアをアップデートしておかないと上手くいかない(?)。
※Galileoの基本的な操作についての説明は割愛する。
まずMini-PCI-ExpressスロットをPCI-Expressスロットに変換するコネクタを用意する。
探してみたところ、以下の2製品が見つかった。
いずれも外部電源を必要とする(そして結構な値段する)。
外部電源なしで動作する製品は見つからなかったことから、Mini-PCI-Express規格はPCI-Express規格よりもスロットから供給される電力が小さいのかもしれない。
さてここで問題となるのが、外部電源を何処から持ってくるかである。
上の2製品はいずれも4ピンのFDD用電源コネクタを接続する仕様で、電力的にGalileoのボードから給電するのは無理である。
今回は仕方なく、変換コネクタに上記のKZ-B24を使用し、別途AC電源(UD-ACDC100NS http://www.amazon.co.jp/dp/B002TOK07S )を用意してそこから給電することにした。
この変換コネクタにはおまけ?でUSBポートが付いてるので、そこにカードリーダ(定番のNTTのあれ http://www.amazon.co.jp/dp/B00117VJ7O )を接続することにする。
準備2. SDイメージ(OS)を用意する
製造元であるIntelがGalileoのLinux用のBSPを配布しているので、Yocto Project (https://www.ibm.com/developerworks/jp/linux/library/l-yocto-linux/)とやらを使用して個別に専用のLinuxディストリビューションを作成してGalileo上で動かすことができる。
今回はとりあえずPT3を動かしてみることが目的なので、簡単のために他の人がビルドしたものを拝借することにした。
今回使わせてもらったのは以下のサイト様からダウンロードしたSDフルイメージ。
IntelのGalileoのSDカード用Linuxイメージを作る - Galileo - Tokoro's Tech-Note
※同サイト内のSDミニイメージを用いて、必要な(同サイトが提供している)パッケージだけをインストールして使ったほうがクリーンな気もするが、面倒なのでフルイメージを使用する。
準備3. ドライバ類をインストールする
ここから先は特にGalileoに固有の話ではなく、普通に(?)PT3のセッティングをするだけである。
ただし、OSが通常のディストリビューションではないので、基本的には全てソースコードからコンパイルしてインストールすることになる。
・PT3のドライバをインストールする
時刻設定が狂っているとビルド時に警告が出るので時刻設定を正しく行う。
# rm /etc/localtime # ln -s /usr/share/zoneinfo/Asia/Tokyo /etc/localtime # date -s "YYYY/MM/DD HH:MM:SS"
ビルドに必要なファイルのパスが特殊なので、リンクを貼る
# ln -s /usr/src/kernel/ /lib/modules/3.8.7-yocto-standard/build
ビルドに必要なカーネルモジュールを生成する
※通常の(ubuntuとかの)ディストリビューションでは元から存在するが、本システムでは手動で生成する必要がある。
※しかも生成に必要なソースコードすらシステム上には用意されていないので、ダウンロードしてくる必要がある。
unameコマンド等でカーネルのバージョンを調べ、そのバージョンのカーネルソースを入手する。
(例)
# uname -a Linux clanton 3.8.7-yocto-standard #2 Thu Feb 13 04:18:29 JST 2014 i586 GNU/Linux
より、カーネルのバージョンは3.8.7らしいので、https://www.kernel.org/ (ftp://ftp.kernel.org/pub/linux/kernel/v3.x/)からカーネルのソース(linux-3.8.7.tar.bz2)をダウンロードする。
ダウンロードしたソースから以下のファイルを、/usr/src/kernel以下の対応する場所にコピーする。
- arch/x86/tools/relocs.c
- kernel/bounds.c
- arch/x86/kernel/asm-offsets.c
- arch/x86/kernel/asm-offsets_32.c
※(例) arch/x86/tools/relocs.c => /usr/src/kernel/arch/x86/tools/relocs.c
※同名のディレクトリが多く、ややこしい構成をしているので間違えないように注意。
※カーネルソースは展開後には約450MBになるので、別のPC上にダウンロードし、
必要なファイルだけWinSCP等のソフトを用いてGalileoに転送した方が良いと思われる。
ソースをコピーし終わったら、カーネルモジュールを生成する。
途中でエラーで止まるけど必要なモジュール(scripts/basic/fixdepとscripts/mod/modpost)さえ生成できればいいので気にしない。
# cd /usr/src/kernel # make modules
PT3のドライバのソースを落としてmakeする。以下、任意の場所にて。
# wget https://github.com/m-tsudo/pt3/archive/master.zip --no-check-certificate -O pt3.zip # unzip pt3.zip; cd pt3-master # make # make install
デバイスの一覧にPT3っぽいものがあることを確認する(一度再起動する必要があるかも)。
# ls -la /dev/* | grep video crw-rw---- 1 root root 250, 0 Jan 1 2001 /dev/pt3video0 crw-rw---- 1 root root 250, 1 Jan 1 2001 /dev/pt3video1 crw-rw---- 1 root root 250, 2 Jan 1 2001 /dev/pt3video2 crw-rw---- 1 root root 250, 3 Jan 1 2001 /dev/pt3video3 ...
・カードリーダのドライバ(PCSC-liteとCCID)をインストールする
開発元からソースをダウンロードしてビルドする。
といってもビルドは全て自動化されているので簡単。
PCSC-liteをインストールする。以下、任意の場所にて。
# wget https://alioth.debian.org/frs/download.php/file/3991/pcsc-lite-1.8.11.tar.bz2 --no-check-certificate # tar -jxvf pcsc-lite-1.8.11.tar.bz2 # cd pcsc-lite-1.8.11 # chmod +x bootstrap configure # ./bootstrap # ./configure # make # make install
CCIDをインストールする。以下、任意の場所にて。
# export PKG_CONFIG_PATH=/usr/local/lib/pkgconfig # wget https://alioth.debian.org/frs/download.php/file/4016/ccid-1.4.16.tar.bz2 --no-check-certificate # tar -jxvf ccid-1.4.16.tar.bz2 # cd ccid-1.4.16 # chmod +x bootstrap configure src/convert_version.pl src/create_Info_plist.pl # ./bootstrap # ./configure # make # make install
ライブラリのロードパスを設定する。
# echo /usr/local/lib | cat > /etc/ld.so.conf # ldconfig
・arib25をインストールする。以下、任意の場所にて。
# wget http://hg.honeyplanet.jp/pt1/archive/c44e16dbb0e2.zip # unzip c44e16dbb0e2.zip # cd pt1-c44e16dbb0e2/arib25/ # make # make install
・recpt1をインストールする。以下、任意の場所にて。
# wget https://github.com/stz2012/recpt1/archive/master.zip --no-check-certificate -O recpt1.zip # unzip recpt1.zip; cd recpt1-master/recpt1/ # chmod +x autogen.sh # ./autogen.sh # ./configure --enable-b25 # make # make install
以上でPT3が使用できるようになった。
動作確認
# recpt1 --b25 --strip 27 10 test.ts using B25... enable B25 strip pid = 1524 C/N = 28.887674dB Recording... Recorded 12sec
実用には厳しいかも
PT3を搭載して使用すること自体は実現できた。
しかし残念なことに、Galileoのスペック的に実用には耐えないと思われる。
以下はスクランブル解除なしで100秒間録画し、その後b25で録画ファイルのスクランブル解除を行った様子である。
# time recpt1 27 100 test.ts pid = 1548 C/N = 28.858894dB Recording... Recorded 168sec real 2m57.739s user 0m1.460s sys 1m5.080s # time b25 test.ts test2.ts processing: finish no EMM receiving request real 4m8.947s user 0m42.860s sys 0m44.000s
参考サイト：
「Intel Galileo Development Board」を起動して動作確認
http://kei-sakaki.jp/2013/12/23/intel-galileo-development-board-bootup-and-test/
ところてんの活動記録(Galileoの項)
http://wiki.tokor.org/index.php?FrontPage
