日本ソフトウェア科学会第 38 回大会 (2021 年度) 講演論文集

関数リアクティブプログラミングにおける時変値の初期化手法の提案
白鳥 佑弥

森口 草介

渡部 卓雄

関数リアクティブプログラミング（FRP）は，時間とともに変化する値を時変値として抽象化することで，組込みシステム等のリアクティブシステムを時変値の更新計算として記述するプログラミングパラダイムである．更新計算に時変値の過去の値を用いることで，変化量や累積値などのシステムの状態に依存した動作を表現できるようになる
が，システム起動時には過去の値は存在しないため，あらかじめ初期値を設定する必要がある．センサの計測値や現在時刻等，実行時に決定される値について不適切な初期値を用いた場合，システム起動直後の挙動が不安定になることがある．アプリケーションごとに適当な値を想定して初期値とするといったアドホックな方法は，プログラムのモジュール化を阻害する．本研究では組込みシステム向け FRP 言語の時変値について，適切な初期値を自動的に決定する初期化手法について提案する．

メーションのために設計された Fran [3] や，Haskell

1 はじめに上の DSL である Yampa [2] などが挙げられる．

組込みシステムや GUI，ゲーム，ロボット制御な本研究で対象とする XFRP [8] とは，組込みシステ

ど，外部の入力の変化に応じて内部状態や出力を変化ム向け FRP 言語である Emfrp [7] の後継として開発させるシステムをリアクティブシステムと呼ぶ．リアされた汎用 FRP 言語である．特徴として，時間漏れクティブシステムを実現するプログラムの記述方法にや空間漏れが発生しないこと，値や関数を時変値の領は，ポーリングや割込みの他に，関数リアクティブプ域に持ち上げるための記述が必要ないこと (lift-free)

ログラミング（FRP）による記述が考えられる．関が挙げられる．

数リアクティブプログラミングとは，時間に応じて変XFRP では，時変値の更新直前の値（直前値）を化する値を時変値として抽象化し，その変化の伝播を用いて時変値の更新を行うことができる．これによっ副作用のない式として記述することでリアクティブシて，状態に依存した動作を記述することが可能とな

ステム全体を表現するプログラミングパラダイムでる．ただし，システムを起動した最初の時点では時変ある．リアクティブシステムの表現として関数リアク値の更新がまだなされていないため，現状の XFRP

ティブプログラミングを採用する利点としては，1 つ

では参照先の時変値に予め初期値として定数を設定の値の変化がコード上に散在することがなく 1 つのしておく必要がある．このとき，時変値の初期値が予式として表されること，安全性や活性の検証が容易でめ決められた定数であることが原因となり，プログラあること [5] [6] が主に挙げられる．FRP を実現するムの挙動が不安定になる場合がある．例えば，センサための主な言語としては，対話式マルチメディアアニの測定値を表す時変値に対して初期値を与えること

Initialization of Time-Varying Value for Functional
Reactive Programming.
Yuya Shiratori, Sosuke Moriguchi, Takuo Watanabe,
東京工業大学情報理工学院情報工学系, Dept. of Computer Science, School of Computing, Tokyo Instituteof Technology.

を考える．システム起動直後のセンサの測定値は環境によって様々な値をとるが，一定時間あたりのセンサの測定値は大きく変化するとは考えにくい．一方で，定数の初期値では環境によって変化しうる測定値との差が予測できず，想定していた変化量を超えてしまう1module LPF

である．XFRP によるプログラムの例を図 1 に示す．

2in raw: Float, t(0.0): Float

この例では，生の信号 raw と時刻 t を入力として受3

out filtered: Float

け取って，raw にローパスフィルタ（LPF）を適用し4use Std

た filtered を出力する．XFRP では時変値のことをノードと呼び，node キーワードを用いて時変値を宣言5する．例えば，図中 8 行目の node dt = t - t@last

6data freq = 200.0

7data s = 1.0 / (6.283 * freq)という部分では，dt という識別子の時変値を宣言し，8

node dt = t - t@lastt - t@last という更新式に従って更新することを定

9node k = dt / (dt + s)

義している．式中にある@last 演算子は，時変値の10node init[0.0] filtered =更新前の値（直前値）を表しており，これによって11# cutoff frequency

k * raw + (1.0 - k) * filtered@last

状態に依存した動作が可能となる．システムの起動直後は，時変値の直前値にあたる値がない．そのた

図1

XFRP で記述された LPF のプログラム．

め，直前値を要求されるすべての時変値に対して初期値を予め設定しておく必要がある．図 1 中の時変可能性がある．こうした想定されない時変値の変化が

値 filtered では，init[0.0] という部分で初期値を起こりうることで，プログラムに対して安全性を保証0.0 に設定している．また，入力時変値にも同様に初することが難しくなることにも繋がる．

期値を設定することができ，時変値 t は続く括弧内

本研究では，時変値の初期値を設定する新たな方法に記述されている 0.0 を初期値に設定している．

について提案する．初期値を定数ではなく式によって組込みシステムでは，比較的小さなメモリ環境下設定できるようにし，初期値を決定するために事前で，反応性の高いプログラムが要求される．そのたイテレーションという仕組みを導入する．これによっ

め，時変値の過去の値を再計算することによって生て，より安定した挙動になるような初期値を各時変値じる空間漏れ（space-leak）や時間漏れ（time-leak）

に対して与えられるようになり，前述の問題を解決すを防ぐ必要がある．XFRP では，時変値の過去の値ることができる．また，提案手法が有限時間内に終了として直前値しか保持しない，再帰的データ型や再し，リアクティブな動作に移行できることも示す．

帰的な関数を使わないといった制限を設けることで，本論文では，まず第 2 節で汎用 FRP 言語 XFRP の空間漏れや時間漏れのないプログラムを記述できる

概要を述べ，第 3 節では具体例を用いて現状の XFRPようになっている．

における初期値の設定方法がもたらす問題を挙げる．

XFRP の実行モデルについて説明する．XFRP で

第 4 節では，初期値を式によって設定する新たな初は，すべての時変値の更新計算（イテレーション）を期化手法について提案する．第 5 節では，前節で提反復的に行うことでリアクティブな動作を実現してい示した初期化手法によって問題が解決できること，おる．まず，プログラム中のすべての時変値について，よび XFRP プログラムのリアクティブな動作に有限更新式が現在値を参照している時変値を始点，時変値時間内に移行することを示す．提案手法の実際の適用自身を終点とする辺によって構成される有向グラフを例については第 6 節で議論する．第 7 節では関連研

事前に生成する．このとき構成される有向グラフは有究との比較を行い，第 8 節では結論と今後の課題に向非巡回グラフ（DAG）であることを要求する．イ

ついて述べる．

テレーションでは，有向グラフのトポロジカルソート
順に値を更新する．入力時変値については，外部から

2 XFRP値を取得して現在値とする．それ以外の内部時変値

XFRP [8] とは，小規模組込みシステム向け FRP 言については，更新式を評価して現在値とする．すべて

語 Emfrp [7] に基づいて再設計された，汎用 FRP 言語の時変値が更新されたら，現在のイテレーションは終1module TempAlert

1module DI2in tmp(20.0): Float # Temperature

2in tmp: Float, hmd: Float, t: Float3

out alert, d_tmp

3out di: Float

4

use Std

4use Std556

node d_tmp = tmp - tmp@last

6

newnode tmpF = LPF(tmp, t)

7

node alert = abs(d_tmp) > 2.0

7

newnode hmdF = LPF(hmd, t)8

図2

温度の急激な変化を検知する XFRP プログラム．

910tmpd_tmp

Temperature (tmp)

28.5
28.4

6

28.3

4

28.2

228.1
28
27.9

80
0

0.02

0.04

0.06

0.08

0.1

Elapsed time [s]図30.01 * hmdF * (0.99 * tmp - 14.3) + 46.3

図4
Value of d_tmp

28.6

node di = 0.81 * tmpF +図 2 のプログラムの動作例．

LPF モジュールを適用したプログラムの例．

な値とは限らない．図 3 は，図 2 の動作例を示している．この例では，入力として与えられる温度センサが 20.0 よりも大きな値で始まったため，システム起動直後に大きな値の変化を検知している．しかし実際には，入力は 27.5 から 28.5 までの値を秒速 1 の速さで往復するように変化するものを与えている．そのため，どの瞬間においても入力は 2 以上の変化をせず，システムが異常を検知した場合は誤検知となる．

了し次のイテレーションに移行する．XFRP では各

温度センサの開始時の値はセンサが置かれている環

時変値の参照先となる時変値が変化することはなく，境によって異なるため，入力時変値 tmp の初期値をイテレーションにかかる時間は概ね一定となるため，どの値で設定しても，このような誤検知が発生する可時間漏れを防ぐことができる．

能性が考えられる．
初期値が定数であることによる問題点は，モジュー3 定数初期値の問題点

ル化を考えるときにも生じる．XFRP では，newnodeXFRP では，時変値の初期値を定数で設定するこキーワードを用いて別モジュールの入出力として時とになっている．しかし，初期値として適切な値がい変値を接続することができる．例として，図 1 をサかなる状況においても同じであるとは限らない．図 2

ブモジュールとして用いている図 4 のプログラムをは，初期値が定数で設定されていることで問題が発考える．このプログラムでは，システムの入力として生しうる XFRP プログラムの例を示している．この与えられる温度センサの値 tmp と湿度センサの値 hmd

プログラムは，温度センサの値を入力時変値 tmp でをそれぞれ LPF に通してから，出力である不快指数受け取り，瞬間的な変化を計算して（d_tmp），変化di の値を計算するプログラムである．LPF モジューの絶対値が 2 を超えた時点で異常として検知し出力ルでは，フィルタをかける前の時変値 raw の初期値時変値 alert を通して報告するというシステムを表は 0 であると想定し，フィルタをかけた後の時変値している．時変値 d_tmp は時変値 tmp の直前値を参filtered の初期値を 0 に設定している．しかし，tmp照するため，tmp には初期値を設定する必要がある．

や hmd のようなセンサの値の初期値は環境によって図のプログラムでは，tmp の初期値を 20.0 としてい変化し，またセンサそれぞれで独立した値をとる．

る．しかし，温度センサの初期値は常に 20.0 が適切

このように，初期値が定数であることによって，シ

1module LPF

2in raw: Float, t: Float

3out filtered: Float

4

use Std

56

data freq = 200.0

7data s = 1.0 / (6.283 * freq)

8

node dt = t - t@last

9

node k = dt / (dt + s)
図61011init filtered = raw # explicit init. expr.

12

node filtered =13k * raw + (1.0 - k) * filtered@last

図 5 のプログラムの初期参照グラフ．

であるとみなすことができる．これにより，初期化式の導入は実質的に従来の XFRP の機能拡張となっている．

図5

初期化式を用いたプログラムの例．

初期化の手順について説明する．まず，各時変値について，その初期化式が現在値あるいは直前値を参照

ステムの起動直後の挙動が不安定になることがある．

している時変値を始点，時変値自身を終点とする辺を各時変値が初期値以外の値のみから計算される値を作り，有向グラフとする．このグラフを初期参照グラ持っていることを表すフラグ時変値を追加すること

フとよぶ．例として，図 5 のプログラムから生成さで，従来の XFRP においてもこの問題を解決するこれる初期参照グラフを図 6 に表す．初期参照グラフにとはできるが，コードが複雑になり新たなバグが発生

巡回路が含まれる場合は，巡回路中の時変値の初期値しやすくなるほか，起動直後にしか意味を成さない時を有限時間内に決定的に求めることが困難であるた変値が残り続けることでメモリ空間を必要以上に圧め，そのようなプログラムは初期化の対象外とする．

迫してしまうという別の問題が発生することになる．

初期参照グラフの生成はプログラムの静的解析で行

次節以降では，初期化の方法を変えることで，コードえる処理のため，コンパイル時に処理を行うことでシの複雑さやメモリ使用量を抑えつつ前述の問題を解

ステム実行時の起動時間やメモリ使用量を抑えるこ決できることを示す．とができるほか，初期化失敗による実行時エラーを防ぐことができる．

4 提案手法次に，各時変値 X について，初期参照グラフにおXFRP の時変値に対する新たな初期化の手法を提いて X を始点としたときのパスに含まれる直前値参案する．その準備として，他の時変値やその直前値の照の最大個数を X の遅延数 d(X) とよぶ．リアクティ

参照を含む式を初期値の代わりに設定できるようにブな動作を始める直前に，Algorithm 1 で示した手順する．このとき設定された式を初期化式とよぶ．図 5で初期化を行い，各時変値の初期値を決定させる．各は，初期化式を用いて書き直した LPF の XFRP プロ

k について，k 以上の遅延数をもつすべての時変値のグラムを示している．新たに init 宣言を導入し（11暫定初期値を決定する処理を事前イテレーションと行目），時変値に対して初期化式を明示的に与えるこ

よぶ．図 5 のプログラムでは，t のみ遅延数が 1 であとが可能となっている．初期化式が明示的に定義されり，他の時変値の遅延数は 0 である．1 回目の事前イていない内部時変値については，更新式を初期化式

テレーションでは t の値をサンプリングして，その値とみなす．これまで定数で初期値を設定していたもの

を t の暫定初期値とする．2 回目の事前イテレーショ

は，定数を評価値とする式を初期化式に設定したもの

ンでは，t の暫定初期値を t@last の値としてすべて

Algorithm 1 初期化の手順
D はすべての時変値における遅延数の最大値．
for k ← D, . . . , 0 do
入力時変値について，それぞれ値を取得し，取得した値を時変値の暫定初期値とする．

for all X: 時変値 do
if d(X) ≥ k thenX の初期化式を評価し，X の暫定初期値とする．
各時変値の暫定初期値を初期値とする．
値においても保つことができる．ある入力 x について，時刻 t のときの値を x(t)，単位時間あたりの変化
図7

初期化にかかる時間計算量が最大となるグラフの例．

量の上限および下限をそれぞれ M , m とする．このとき，経過時間 ∆t について，の時変値を更新し，結果を各時変値の暫定初期値とm · ∆t ≤ x(t + ∆t) − x(t) ≤ M · ∆t

する．遅延数 0 の時変値の暫定初期値が決定したとという関係が成り立つ．入力 x の値を受け取る時変ころで，暫定初期値を初期値として決定する．この例

値 X について，最初のイテレーションにおける値をのように，事前イテレーションによって入力値がイテX0 ，初期値を Xinit とする．初期値を定数で設定すレーションが行われる直前にサンプリングされ初期値る従来の初期化方法では，初期値の設定から最初のとして設定されるため，環境に応じた適切な値が入力イテレーションまでの時間経過はほとんどないため時変値の初期値として設定されることが期待される．

X0 − Xinit ≈ 0 であることが望ましい．しかし，X0が実行環境によって変化する一方で Xinit は定数であ5 初期化に対する保証るため，この関係は常には成り立たない．一方で，提この節では，4 節で述べた初期化が保証するいくつ案手法による初期化について，X に明示的な初期化かの性質について説明する．

式が与えられていないものとし，最初のイテレーショ初期化の処理は有限時間内に終了する．ある時変ンの開始時刻を T ，最後の事前イテレーションの開始値の遅延数を d とすると，初期化式に基づいて暫定から最初のイテレーションの開始までの経過時間を初期値を求める処理を初期値が決定するまでの間にτ とする．このとき，X0 − Xinit = x(T ) − x(T − τ )(d + 1) 回行う．1 つの時変値の暫定初期値の計算にであり，かかる時間が時変値によらず一定であると仮定する

m · τ ≤ X0 − Xinit ≤ M · τと，初期化が完了するまでに各時変値はその遅延数のという関係を保つ．ここでは入力時変値のみを取り上分だけ暫定初期値の計算を行うため，初期化にかかるげて説明したが，内部時変値についても入力値から時間計算量は時変値の遅延数の合計に比例する．n 個の推論によって同様の関係が成り立っている場合は，の時変値で構成された FRP プログラムにおいて，そその関係を保つことができる．の初期参照グラフが図 7 のように直前値参照によって一列になるとき，初期化にかかる計算時間が最も長6 適用例くなり，そのときの計算量は O(n2 ) である．有限時第 3 節で提示した問題が，提案手法によって解決さ間内に初期化が終了し，リアクティブシステムの動作れることを示す．図 8 は，図 2 のプログラムから tmpに移行することができる．の初期値を取り除いたプログラムである．時変値 tmp

提案手法によって，システムの入力に課せられた値は時変値 d_tmp によって直前値が参照されているたの変化の上限および下限に関する制約を，入力時変め初期値が要求されるが，提案手法によって tmp の1

module TempAlert

ことができるが，システムの起動直後では値の更新が2

in tmp: Float

まだ行われていないため，起動直後の状態を初期値な3

out alert, d_tmpしに取り出すことはできない．リアクティブシステム

4

use Stdの動作を常に安定させるには，初期値を適切に設定する必要がある．こうしたリアクティブシステムを表現

56

node d_tmp = tmp - tmp@last

する他の FRP 言語や同期言語を例に，関連性につい7node alert = abs(d_tmp) > 2.0て議論する．

Yampa [2] は，Haskell 上に実装された FRP の DSL
図8提案手法を適用して定数初期値が不要になった例．

である．Yampa では，fby 演算子が XFRP の初期値と同じような役割をもつため，同様の問題が発生しうる．ホスト言語上で同様の初期化処理を行ってから値

tmp
d_tmp

Temperature (tmp)

28.5
28.4

6

28.3

4

28.2

2

28.1
2827.9を渡すことで，同じ仕組みによって初期値を設定する

8
Value of d_tmp

28.6

000.020.04

0.06

0.080.1

Elapsed time [s]図9

図 8 のプログラムの動作例．

ことができる．本研究では時変値の初期化式の構造から自動的に初期化の機能を付けることができる一方で，Yampa では手動で同様の機能を付けることになるため，プログラムの変更に応じて初期化の部分も変更する必要があり，変更点が多くなってしまう．

Lustre [4] とは，リアクティブシステムを記述するための同期データフロー言語である．Lustre では，pre 演算子によってデータ列の直前の値を取り出すことができるが，最初に取り出される値は nil という値を事前に取得し自動的に初期値として設定するこ未定義の値になる．Colaço らの研究 [1] では，nil のとが可能なため，明示的な初期化式は不要である．図

値がシステム全体に影響しないかどうかを型解析を3 と同じ入力を図 8 のプログラムに与えて実行した動用いて解析する方法について提案している．本研究で作例を図 9 に示す．図 3 と比べて，起動直後の入力は，明示的に初期化されていない時変値であっても初値と初期値との間で発生していた大きな変化は観測期化によってすべての時変値に初期値を与えることがされず，異常の誤検知は発生しないことがわかる．

できるため，このような解析は必要ない．

図 4 のプログラムについても，LPF モジュールを図 5 のような実装に変更することで接続されるそれ

8 結論

ぞれの時変値に適した初期値を事前イテレーション

本研究では，汎用 FRP 言語である XFRP におけによって別々に設定することができる．これにより，る時変値の新たな初期化手法を提案した．また，提案

入力時変値の初期値によらないモジュールを作成する手法によって既存の初期値定義で生じていた問題を解ことが可能となるため，より柔軟なモジュール化を実決できることを示した．

現できるようになる．

提案手法によって，XFRP で記述された FRP プログラムの安全性に関する解析を容易にできるように

7 関連研究なると期待される．第 5 節で示したように，入力に時変値の初期値として適切な値を設定するという関する変化量の上限および下限に関する安全性が保問題は，状態に依存した動作を行うリアクティブシス

証されている場合に，入力時変値や内部時変値につテムを表現する際に発生しうる一般的な問題である．

いても同様の安全性を保証できることが提案手法に状態とは過去の値の更新によって得られた値とみなす

よって導出できるようになる．提案手法が適用された XFRP プログラムの安全性の解析手法については，今後の課題とする．
謝辞 本研究の一部は JSPS 科研費 21K11822 および 19K20245 の助成を受けている．
参 考 文 献[1] Colaço, J.-L. and Pouzet, M.: Type-based initialization analysis of a synchronous dataﬂow language,
International Journal on Software Tools for Technology Transfer, Vol. 6, No. 3(2004), pp. 245–255.
[2] Courtney, A., Nilsson, H., and Peterson, J.: TheYampa Arcade, Proceedings of the 2003 ACM SIGPLAN Workshop on Haskell, Haskell ’03, New
York, NY, USA, 2003, pp. 7–18.
[3] Elliott, C. and Hudak, P.: Functional Reactive Animation, Proceedings of the Second ACM
SIGPLAN International Conference on Functional
Programming, ICFP ’97, New York, NY, USA, Association for Computing Machinery, 1997, pp. 263–273.
[4] Halbwachs, N., Caspi, P., Raymond, P., and Pilaud, D.: The synchronous data ﬂow programming language LUSTRE, Proceedings of the IEEE,Vol. 79, No. 9(1991), pp. 1305–1320.
[5] Jeﬀrey, A.: LTL Types FRP: Linear-Time Temporal Logic Propositions as Types, Proofs as Functional Reactive Programs, Proceedings of the Sixth
Workshop on Programming Languages Meets Program Veriﬁcation, PLPV ’12, New York, NY,USA, Association for Computing Machinery, 2012,
pp. 49–60.
[6] Jeﬀrey, A.: Functional Reactive Programmingwith Liveness Guarantees, SIGPLAN Not., Vol. 48,
No. 9(2013), pp. 233–244.
[7] Sawada, K. and Watanabe, T.: Emfrp: A Functional Reactive Programming Language for SmallScale Embedded Systems, Companion Proceedingsof the 15th International Conference on Modularity,
MODULARITY Companion 2016, New York, NY,USA, Association for Computing Machinery, 2016,pp. 36–44.
[8] Shibanai, K. and Watanabe, T.: Distributed
Functional Reactive Programming on Actor-Based
Runtime, Proceedings of the 8th ACM SIGPLAN
International Workshop on Programming Based on
Actors, Agents, and Decentralized Control, AGERE
2018, New York, NY, USA, Association for Computing Machinery, 2018, pp. 13–22.