関数型 | プログラマーズ雑記帳

「関数型」タグ記事

Dart における高階関数を使ったデータ処理 2014-11-05
Haskell の Windows へのインストールと Emacs モードの設定 2014-11-17
データ共有の新潮流 - アクター, Agent, STM 2014-12-24

Dart 関数型

最近ではコンテナークラスなどのデータを高階関数を使って処理する手法が広がってきています。
今回はその高階関数を使ったデータ処理を Dart で行う方法について紹介します。

高階関数を使ったデータ処理

まず、高階関数を使ったデータ処理について説明します。

プログラミング言語の傾向

高階関数を使ったデータ処理は Lisp や関数型言語でよく使われてきた方法で、関数型プログラミングには欠かせないものです。

しかし、関数型言語でなければ使えないというものではありません。
高階関数を使ったデータ処理はコードを短くかつわかりやすく記述することができます。そのため、 Ruby, C#(LINQ) を始めとした多くの言語で取り入れられてきました。

最近では、 Java や C++ にも取り入れられてきており、これからのプログラミングでは一般的な手法になって来ています。

処理の対象

これまで処理の対象をデータと表記していますが、リスト(配列)のようなコンテナーだけでなく、様々なものに対しても処理を行うことができるためです。

Dart では具体的には Iterable クラスを継承したクラスで使うことができます。 Dart のコンテナークラスは Map(連想配列) を除いて、この Iterable を継承しています。

さらに、 Dart には Mix-in の機能があるため、 IterableMixinを使えば、自作したコンテナークラスでもこれから紹介する多くのデータ処理用のメソッドが使えるようになります。

また、ファイル等の並列処理のための Stream クラスも Iterable を継承してはいませんが、同じようなメソッドを持っています。

逐次処理

データ処理の中でもっとも基本的な逐次処理を例に高階関数を使う方法を説明します。

C, C++ 風にリストの要素に順に処理していく場合にはループカウンターを使うと思います。

  var lis = ["foo", "bar", "baz"];
  for (var cnt = 0 ; cnt < lis.length ; cnt++) {
    print(lis[cnt]);
  }
  // foo
  // bar
  // baz

これを Dart では for-in を使って書くことできます。

  for (var elem in lis) {
    print(elem);
  }

ループカウンターを使うよりも短く書けますし、リストの要素を処理しているということが分かりやすくなっていると思います。

これを高階関数を使って書きなおしてみます。
高階関数のデータ処理では forEach を使います。渡す関数は、無名関数を使っていますが、通常の関数でも構いません。

  lis.forEach( (elem) => print(elem) );
  // 無名関数の別の書き方
  lis.forEach( (elem) { print(elem); } );

for-in 版とそんなには変わりません。ですが、これは逐次処理に限って言語に制御文が用意されているからです。
高階関数のデータ処理では逐次処理にかぎらず、処理が短くかつ分かりやすく書けるようになります。
次の章からその高階関数を使ったできるデータ処理の基本的なものについて見てきます。

なお forEach も後で説明する"連結"で使えるため、いらないというわけでもありません。

基本的なメソッド

それでは、ここから高階関数を用いたデータ処理でまず最初に覚えておいた方がよいと思われる機能について説明していきます。主要な機能は次の 5 つです。

逐次処理(forEach)
写像(map)
フィルター(where)
並び替え(sort)
畳み込み(fold, reduce)

このうち逐次処理は先ほど説明しました。残りの 4 つを説明していきます。

map : 写像

写像というのは map, mapping と呼ばれる処理で、配列などのコレクションのメンバーに一つずつ関数を適用して戻り値で新しいコレクションを作ります。

Dart ではそのまま map という関数名です。

  var src = [3, 2, 9, 6];
  var mapped = src.map((elem) => elem * 2); // [6, 4, 18, 12]

map に渡す関数は要素の型を引数にとる関数で、その戻り値が新しいコレクションの要素となります。 map は渡す関数の戻り値の型を変えれば、値を変えるだけでなく、型を変えた新しいコレクションも作ることができ、用途の広いメソッドです。

where : フィルター

フィルターはコレクションの中から条件にあう要素を取り出す処理です。

Datt では where() という名前になっています。

  src = [3, 2, 9, 6];
  var filtered = src.where((elem) => elem % 2 == 1); // [3, 9]

データ処理で重要なメソッドをさらに絞るとすると、前節のマップとこのフィルターが、特に重要度が高いです。

sort : 並び替え

sort は要素の並び替えを行います。
基本的な処理に入れましたが、並び替えは逐次的な処理では無いため少し特殊です。そのせいか Dart では Iterable には含まれておらず、 List のメソッドとなっています。

sort では何も指定しなければ、要素の compareTo を使って比較します。比較用のメソッドを渡すと比較の基準を変えることができます。

  lis = [-3, 2, -9, 0];
  lis.sort();                                     // [-9, -3, 0,  2]
  lis.sort((x, y) => x.abs().compareTo(y.abs())); // [0, 2, -3, -9]

fold, reduce : 畳み込み(縮退)

畳み込みは要素を順に取得し、それらを計算に使った結果を返す処理です。

畳み込みは他言語では fold, reduce, inject などの関数名が使われます。 Dart では fold, reduce の 2 つが用意されています。

先に reduce を見ていきます。

  src = [3, 2, 9, 6];
  var sumval = src.reduce((sum, elem) => sum + elem);                // 20
  var maxval = src.reduce((max, elem) => (max < elem) ? elem : max); // 9

reduce に渡す関数は 2 つの引数を取り、 2 つ目が各要素で、関数の戻り値が次に呼ばれた時の 1 つ目の引数です。これにより、各関数の結果を重ねていったものが reduce の戻り値として得られます。
1 番最初に呼ばれる場合、 1 つ目の要素は最初の要素です。

1 番最初に呼ばれる場合の初期値を指定する場合に fold を使います。

  src = [3, 2, 9, 6];
  var leng = src.fold(0, (count, elem) => count+1);  // 4
  var cons = src.fold("", (str, elem) => str += elem.toString() + ' '); // "3 2 9 6 "

その他のメソット(プロパティー)

データ処理の定番のメソッド以外で、抑えておいた方がいいかなと思うものも挙げて置きます。

length、 isEmpty

要素数の取得と空かどうかのチェック (プロパティー)

var src = [3, 2, 9, 6];
src.length;   // 4
src.isEmpty;  // false

take

指定した要素数の取り出し。

var src = [3, 2, 9, 6];
src.take(2); // (3, 2)

firstWhere, lastWhere

指定した条件に最初(最後)にマッチする要素の検索。
検索もデータ処理ではよく行う処理ですが、条件にあうすべての要素を取得するのがフィルター(where)で、最初の要素を取得するのが firstWhere です。

var src = [3, 2, 9, 6];
src.firstWhere((elem) => elem % 2 == 1); // 3
src.lastWhere( (elem) => elem % 2 == 1); // 9

contains

要素を含んでいるかの判定。

var src = [3, 2, 9, 6];
src.contains(9);  // true
src.contains(5);  // false

any, every

要素どれか一つ(すべて)が条件を満たすかどうかの判定。

var src = [3, 2, 9, 6];
src.any(  (elem) => elem % 3 == 0); // true
src.every((elem) => elem % 3 == 0); // false

ここで紹介した以外にもまだメソッドはあります。詳しくは Dart のリファレンスを見て下さい。

dart-core.Iterable API Docs

メソッドの連結

map や where の返すものをちゃんと見てみると、iterable を返しています。

var src = [3, 2, 9, 6];
var result = src.map((elem) => elem * 2);
print(result);              // (6, 4, 18, 12)
print(result.runtimeType);  // MappedListIterable

このため、これらのデータ処理は連結して書いていくことができます。

var src = [3, 2, 9, 6];
src.where((elem) => elem % 2 == 1)
  .map((elem) => elem * 2)
  .forEach((elem) => print(elem));
// 6
// 18

遅延評価

メソッドを連結して書くとメモリーがもったいないと思われる人もいるかもしれません。
しかし、 map 等の返す iterable は特殊なもので、 必要になるまで実行されないという遅延評価の機能があります。前節の例では forEach で一つずつ取り出す時が実行のタイミングです。

連結の処理は一見、次のように処理してるように見えます。

              where           map
{3, 2, 9, 6}    →   {3, 9}    →   {6, 18}

しかし、実際には遅延評価により、メソッドごとに結果をためるのではなく、 1 要素ずつ流すように次のメソッドに渡していきます。

    where       map
3    →    3     →    6
2    →    ☓
9    →    9     →    18
6    →    ☓

なお、ソート(sort)は全要素が揃わないと完了しない処理なので、言語によって扱いが変わってきます。

Dart ではソートでは遅延処理はしないという方針です。
そのため、 toList で一旦リストに変えてから List のメソッドでソートする必要があります。このリストにする時が "必要なとき" となり、その時点で評価が行われます。

var src = [3, 2, 9, 6];
var resultsort = src.where((elem) => elem % 2 == 1)
  .map((elem) => elem * 2)
  .toList();
resultsort.sort((x, y) => y.compareTo(x));
print(resultsort); // [18, 6]

サンプルコード

説明で使用したサンプルのコードは以下のリンクからダウンロード(リンク先を保存)できます。

transform.dart

コンパイルする場合は以下のコマンドを実行します。

 > dart transform.dart

Dart をコマンドラインから使う方法については以前の記事を見て下さい。

Dart をコマンドラインから使う | プログラマーズ雑記帳

スポンサーサイト

Haskell の Windows へのインストールと Emacs モードの設定

使い方インストール関数型

Haskell は純粋関数型のプログラミング言語です。今回は Haskell の Windows へのインストール、使い方および Emacs での設定について説明します。

Haskell とは

Haskell は関数型プログラミングをやるために作られたような言語で、大きな特徴は次の 2 つです。

純粋関数型言語
遅延評価

関数型プログラミングでは値を変更しないように作ります。しかし、関数型言語はいろいろとありますが、多くは使いやすさ等の理由により、制限付きで値が変更できるようになっています。
そんな中 Haskell は純粋関数型なので、本当に値が変更できません。これは融通が利かないとも思われるかもしれませんが、純粋に関数型でプログラミングできるだけの機能がそろっているとも言えます。

最近では C# の LINQ といったように関数型にとどまらず、高階関数を使った Stream 系のデータ処理が広がってきました。そこでは必要になったときに初めて計算するという遅延評価になっていることが多いです。
これはメモリーの使用量を減らすなどのメリットがあってそうなっているのですが、 Haskell では全てで遅延評価となります。こちらも関数型言語といわれる言語でもそこまで対応している言語はほとんどありません。

また、 Haskell はスクリプトとして動作させることもできますが、ソースコードをビルドして、実行ファイルを作るコンパイル型の言語です。ただ、コンパイル型といってもそんなに速いわけではありません。

Scala は JVM, F# は .NET というように新しい関数型言語の多くは仮想マシンで動作する言語が多いです。新しい言語ではライブラリー等の環境が成熟していないといったデメリットがついて回るものなのですが、 JVM や .NET の言語ではそれがありません。
そういった意味では、 Haskell は学術的な意義の高い言語ですが、実用性という面ではこれからの言語だと思います。

インストール

Haskell には Haskell Platform というコンパイラーや開発ツールがセットになったものが用意されていて、インストーラーもあるので、インストールは簡単です。

ダウンロード

以下のサイトからインストールする環境にあわせて 32 ビットまたは 64 ビット版のインストーラーをダウンロードします。

Haskell Platform for Windows

インストール

ダウンロードしたインストーラー(HaskellPlatform-YYYY.X.X.X-zzzz-setup.exe)を実行するとインストールが始まります。

インストール先を指定して、ウィザードを続行すればインストールは完了です。

インストールすると "(インストール先)/bin" 以下にコンパイラー等の実行ファイルが格納されます。 bin フォルダーへの PATH の登録もインストーラーが行ってくれます。

使い方

bin フォルダー内の実行ファイルのうち、主に使うのは次の 3 つです。

GHCi : REPL(対話型)
runghc : スクリプトとして実行
ghc : コンパイラー

REPL(対話型) : GHCi

REPL は入力行をすぐ評価することができ、動作確認など開発時に使用します。

~/lang/hs $ ghci
GHCi, version 7.8.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Prelude> print "Hello world!"
"Hello world!"
Prelude> :quit
Leaving GHCi.

ghci で起動し、 :? でヘルプ、 :quit で終了します。

Windows のスタートメニューから [Haskell Platform YYYY.X.X.X] → [WinGHCi] を選択すると WinGHCi が起動します。こちらは多少 GUI で操作できる GHCi です。

runghc : スクリプトとして実行

まず、ソースファイルを用意します。 Haskell ではファイルの拡張子には hs が使われます。

hello.hs :

main =
    print "Hello world!"

スクリプトとして使う場合には、 runghc にソースコードを渡して実行します。

~/lang/hs $ runghc.exe hello.hs 
"Hello world!"

スクリプトとして実行する場合 runhaskell(.exe) も使えます。
微妙な違いはありますが、ほぼ同じものです。

haskell - What's the difference between runghc and runhaskell? - Stack Overflow

GHC : コンパイラー

GHC(Glasgow Haskell Compiler)ではソースファイルをコンパイルして実行ファイルを作ることができます。

~/lang/hs $ ghc hello.hs
[1 of 1] Compiling Main             ( hello.hs, hello.o )
Linking hello.exe ...
~/lang/hs $ ./hello.exe 
"Hello world!"

実行ファイル名はデフォルトでは「ソースファイルのベース名 + ".exe"」となります。指定したい場合は -o オプションを使います。

その他

bin フォルダー内のその他の実行ファイルについても簡単に紹介します。

コマンド	機能	参考
ghc-pkg	Haskell のパッケージ管理ツール。パッケージ管理には cabal も使います。 cabal の方は lib/extralibs/bin フォルダーにあり、こちらにも PATH は通っています。	Haskellのパッケージ管理について調べてみた - りんごがでている
haddock	ソースコードからドキュメントを作成。 Haskell 版の Doxygen や JavaDoc のようなものです。	Haskell の Javadoc, Haddock を使う - 一歩前進
hp2ps	ヒープ領域のプロファイラー。	本物のプログラマは Haskell を使う - 第 46 回　ヒープ・プロファイラで領域漏れを探る： ITpro
hpc	Haskell Program Coverage: カバレッジ(テストでソースコードをどの程度実行できたか)の計測ツール。	Haskell program coverage - HaskellWiki
hsc2hs	C のコードを Haskell から利用するための補助ツール	12.2. C コードへの Haskell インタフェースを書く: hsc2hs

Emacs モードの設定

Hakell 用のパッケージはいろいろありますが、最低限必要なのは haskell-mode です。これはパッケージマネージャーから簡単にインストールすることができます。

Emacs のパッケージ管理機能の使い方 | プログラマーズ雑記帳

インストールすると hs などのファイルを開いた時に haskell-mode になります。

ただし、そのままではインデントをしようとすると変なエラーが出ます。これはインデントのモードを設定していないためなので、モードを 3 つの中から選んで、設定しておく必要があります。

Indentation · haskell/haskell-mode Wiki · GitHub

モード	説明
haskell-simple-indent	単純な TAB によるインデント
haskell-indent	コードの構造を考慮したインデント
haskell-indentation	haskell-indent に加え、 `[RET]` や `[DEL]` のキーを拡張

これらのモードにする場合は turn-on-xxxx の関数を haskell-mode になった時に呼び出すようにします。

(add-hook 'haskell-mode-hook 'turn-on-haskell-indent)

Emacs では「改行 + インデント」はC-jを使うのが普通だと思うので、個人的にはhaskell-indent でいいと思います。

Emacs の使い方基本のキー | プログラマーズ雑記帳

なお、インデントに関しては hi2 というパッケージもあり、インデントルールは同じで、もう少し複雑な動きをします。

nilcons/hi2 · GitHub

使う場合は hi2 をインストールして、同じような設定を書きます。

(add-hook 'haskell-mode-hook 'turn-on-hi2)

データ共有の新潮流 - アクター, Agent, STM

関数型 Clojure 言語比較

スレッドなどの並列処理でデータを共有する場合、従来はロックを使って共有する方法が主流でした。
しかし、最近では関数型言語を中心に新しいデータの共有方法が出てきています。今回はその内の アクター、 Agent 、 STM について説明します。

これらの方式のうち、どれを採用するかは言語によって変わってきます。
わかりやすさと言語に依存しないようにするため、 C++ 風の擬似コードをサンプルとして説明し、その後実際の言語でのコードを挙げています。

ロック : 従来の方法の問題点

ロック方式とは

今までよく使われていたのは ロック や Mutex(排他制御) と呼ばれる方式です。

データを扱う場合、普通は次のような一連の処理になります。

データの読み取り
なにかの処理
データの更新(書き込み)

主にデータベース(DB)で使われる用語ですが、この関連・依存する複数の処理をまとめて トランザクション(transaction) 呼ばれています。

データ読み取りから書き込みまでの間によそから値が変更されると整合性に問題が生じます。このため、並列処理で共有しているデータを使う場合には、そのデータを変更する側がデータをロックし、他の処理からはアクセスできないようにします。

他の処理からも値を読み取るだけであれば、通常問題は無いのですが、読み取った値を更新に使うのかどうか分からないため、読み取りもロックされます。

この処理はすべて実行するか、全くしないかなので、アトミック(Atomic)実行とも呼ばれます。
ちなみに、原子のアトム(Atom)の名前も「これ以上分けられないもの」というところからきています。ただ、実際は科学が進んで、電子、陽子、中性子とさらに分けられることがわかっています。

ロック方式の問題点

ロック方式には大きな問題点があります。
それはロックしている間は他の処理が待ちになってしまう点です。せっかく並列処理にしているのに、他の処理が終わる待っているようではその時間が無駄になってしまいます。

ただ、この方式でも今まではそれほど問題ではありませんでした。それはコンピューターの多くが CPU が一つだけのシングルコアだったためです。
シングルコアの場合、並列処理といっても実際に動作しているのは一つの処理だけで、それを切り替えていく擬似的なものです。

しかし、最近では複数の CPU を積んだマルチコアが増えてきました。マルチコアでは並列処理は本当に平行して動作し、ロックによる待ちは時間のロスになってしまいます。
これから紹介する方式はマルチコア時代のための止めないデータ共有方法です。

アクターモデル (Actor Model) : メッセージの送信

アクターモデルとは

アクターモデル と呼ばれる方法では並列処理の一方から他の処理にメッセージ(データ)を送信します。この時、キューを使って受け渡しされるので、受け手の応答を待つ必要はありません。

送り手、受け手の要素をアクターといいます。棒人形を使って書いていますが、ユースケース図のアクターとはあまり関係無いです。

このアクターモデル、実はそれほど新しい概念というわけでもありません。プロセス間のメッセージキュー、 PC 間のソケット通信のような非同期通信と同じものです。アクターはそれをプログラム内で行います。
というよりも、アクターの方が定義が広く、それらの非同期通信もアクターモデルに入ります。もっと言えば、電子メール、郵便などもアクターモデルです。

アクターの処理

アクターを使う場合には、受け手側はループで待機し、データの受信をトリガーとして処理する仕組みにする必要があります。

// 受け手側の処理
void act(msgQueue)
{
    while (true)
    {
        int x = msgQueue.receive();
        print("Reciever : %d", x);
    }
}
// アクターを作成して、処理を登録
Actor agent;
agent.set_action(act);


// 受け手側の並列処理を起動
agent.start()


// 送り手側の処理
print("Sender : 1, 10");
agent.send(1);
agent.send(10);

$ pseudo actor.psd
Sender : 1, 10
Reciever :  1 
Reciever :  10

アクターは Scala, F#, Erlang(Elixir) といった関数型言語だけでなく、 Io, Fantom といったオブジェクト指向言語でも使わています。

新しい言語では言語の機能として取り込まれていますが、 Ruby での Celluloid ように昔からある言語でもライブラリーがあるものも多いです。
(昔といっても自分の中では結構最近だったのですが、この前、生まれたときから Ruby があるという人が Ruby の開発に参加しているというブログを見かけて若干ショックでした)

気を取り直し、ここでは F# を使って、サンプルコードを書いてみます。 F# ではアクターは MailboxProcessor というクラスを使って実現します。

open System
open Microsoft.FSharp.Control

let agent =
    new MailboxProcessor<int>(
        fun inbox ->
            let rec loop n = async {
                let! x = inbox.Receive ()
                System.Console.WriteLine ("Reciever :  {0} ", x)
                return! loop x
            }
            loop 0
    )

agent.Start()

System.Console.WriteLine ("Sender : 1, 10")
agent.Post(1)
agent.Post(10)

// 処理が終わらないように止めておく
System.Console.Read () |> ignore

Agent : アクターの改良

Agent とは

Agent はアクターとほぼ同じ意味で、アクターのサンプルコードで Agent を使っているのもわざとです。
ただ、 Agent というときはアクターとは微妙に違っています。 Wikipedia によるとエージェントシステムは多くの場合アクターモデルに何らかの制限を課している点が異なり、自発的で自律的であることが要求されるということらしいです。

例えば、 Visual Studio の C++ ライブラリーの Agent では、アクターのやり取りを一方向ではなく、双方向で行います。

非同期エージェントライブラリ

Agent はアクターモデルをベースとした非同期処理のための機能であることは共通していますが、ハッキリとどういった機能ということは決まっていないようです。
そのため、ここでは言語機能として Agent を採用している Clojure での agent の機能に限って説明していきたいと思います。

Clojure, Leiningen の Windows へのインストールと使い方 | プログラマーズ雑記帳

agent の処理

agent では、それ用の型(クラス)を用意します。データが変更される前に agent にアクセスすると更新前の値を返すので、必ず初期値が必要です。

agent の値を更新する場合は、値を直接送るのではなく、処理(関数)を渡します。送るのはトランザクション処理で、 agent は受け取った関数を自分で別スレッドを立てて実行し、データを変更します。

// 初期値 1 で Agent を作成
Agent foo(1);

// Agent に処理を送る
int act(int x)
{
    return x + 10;
}
foo.send(act)


// Agent の値を表示
print(foo);  // 11

これを Clojure で書くと次のようになります。

(def foo (agent 1))

(defn act [x]
  (+ x 10))
(send foo act)

(println @foo)  ; 11

;; agent を使うときは、これを呼ばないと終了しない
(shutdown-agents)

Clojure の agent は、状態を変更する必要があってもそれを待機する必要がない場合、複数の並列処理によって変更が行われるときにその順序は問題にならない場合など特定の場面でのみ使える簡易的なものです。(待機もできるのですが、それだとロックです)
そのため、 Clojure では他のデータ共有方法もいろいろ用意されていて、そのうちの一つが次の STM です。

STM (Software Transactional Memory) : トランザクションの管理

STM とは

最初に説明したトランザクションの用語はハードにある DB に対して使われることが多いですが、 STM はメモリー上にあるデータに対するトランザクション処理のシステムです。

STM ではトランザクションの処理は、それが明示的にわかるようにします。(サンプルでは transaction_block)
そのため、一方の処理がトランザクション中でも、読み取りだけなら、そのまま読み取れます。

// STM 用のデータを用意
stm_data<int> foo(1);


// 処理 B
async 
{
    sleep(1000);
    int tmp = foo.get();    // 読み取り
    print("B : Get %d", tmp);
}

// 処理 A (メイン)のトランザクション処理
transaction_block
{
    int tmp = foo.get();
    print("A : Get %d", tmp);
    sleep(2000);
    tmp += 10;
    foo.set(tmp);
    print("A : Set %d", tmp);
}

問題はトランザクション処理が並列実行で被った場合です。

この時の処理を逐次的に見ていきます。

例として、値が 1 である STM 用のデータ foo があったとします。
まず、値を読み取るときには特に問題なく並列処理 A, B ともに 1 を取得します。

処理 A は foo の値を 11 に更新します。この時、処理 B はまだ処理中です。

今度は処理 B が foo の値を 11 に更新しようとします。
しかし、ここで問題が生じます。処理 B の読み取り時の値は 1 なのに書き込もうとした時には 11 に変更されています。

STM では読み取り、書き込み時の値をログを取って覚えています。書き込もうとした時に読み取った時の値から変更されている場合、すなわちトランザクション中に値が変更された場合には 処理をもう一度繰り返します。

このようにトランザクションが被った場合には、その処理をやり直します。

アクターモデルは従来のロック方式と比べると受け手がループで待機しておく必要があり、シーケンスそのものがガラッと変わっています。それに対して STM は従来の方式と基本的な流れは同じで、処理を止めないように改良されています。
その代わり、トランザクション処理はやり直しがあり、何度も繰り返す可能性があります。このため、繰り返した際に結果が変わるようなものではダメで、副作用を起こさない(状態を変更しない)純粋な関数である必要があります。

また、トランザクション処理が頻発にかぶる場合にはやり直しが何度もおきて、パフォーマンスが低下します。

STM の処理

先ほどのシーケンスを擬似コードを使って書いてみます。

// STM 用のデータを用意
stm_data<int> foo(1);


// 処理 B
async 
{
    sleep(1000);
    // トランザクション処理
    transaction_block
    {
        int tmp = foo.get();    // 読み取り
        print("B : Get %d", tmp);
        sleep(2000);
        tmp += 10;
        foo.set(tmp);           // 書き込み
        print("B : Set %d", tmp);
    }
}

// 処理 A (メイン)のトランザクション処理
transaction_block
{
    int tmp = foo.get();
    print("A : Get %d", tmp);
    sleep(2000);
    tmp += 10;
    foo.set(tmp);
    print("A : Set %d", tmp);
}

出力は次のようになります。処理 A では最初の書き込みでは矛盾ができるのでやり直しています。
なお、次の Clojure で実際に実行した場合には IO の都合で少し出力順は変わります。

$ pseudo stm.psd
A : Get  1
B : Get  1
A : Set  11
B : Get  11
B : Set  21

STM を言語機能としてで対応しているのは Clojure と Haskell です。どちらも関数型言語ですが、トランザクション処理は純粋関数型である必要があるため、関数型言語の方が向いている機能だと思います。

Haskell の Windows へのインストールと Emacs モードの設定 | プログラマーズ雑記帳

STM としては Clojure の方が有名な気がするので、Clojure のコードを挙げておきます。

(def foo (ref 1))

(.start (Thread.
         (Thread/sleep 1000)
         (fn []
           (dosync
            (let [tmp @foo]
              (Thread/sleep 2000)
              (println "B : Get " tmp)
              (ref-set foo (+ tmp 10))
              (println "B : Set " (+ tmp 10)))))))

(dosync
 (let [tmp @foo]
   (Thread/sleep 2000)
   (println "A : Get " tmp)
   (ref-set foo (+ tmp 10))
   (println "A : Set " (+ tmp 10))))

なお、「やり直しではなく、トランザクションとしてアクセスするときだけロックした方がいい時もあるのでは？」と思った人もいるかもしれません。
確かにその通りで、やり直しの方法をとっているのは、単に Haskell や Clojure のデフォルトがそうだというだけです。例えば Clojure では ensure を使うとロックになります。
STM のポイントはトランザクション処理を管理する というところです。効率的に対処法を切り替えるなど、今後いろいろな発展が期待される分野です。

日	月	火	水	木	金	土
-	-	-	-	1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30	-

プログラマーズ雑記帳

Dart における高階関数を使ったデータ処理

高階関数を使ったデータ処理

プログラミング言語の傾向

処理の対象

逐次処理

基本的なメソッド

map : 写像

where : フィルター

sort : 並び替え

fold, reduce : 畳み込み(縮退)

その他のメソット(プロパティー)

メソッドの連結

遅延評価

サンプルコード

Haskell の Windows へのインストールと Emacs モードの設定

Haskell とは

インストール

ダウンロード

インストール

使い方

REPL(対話型) : GHCi

runghc : スクリプトとして実行

GHC : コンパイラー

その他

Emacs モードの設定

データ共有の新潮流 - アクター, Agent, STM

ロック : 従来の方法の問題点

ロック方式とは

ロック方式の問題点

アクターモデル (Actor Model) : メッセージの送信

アクターモデルとは

アクターの処理

Agent : アクターの改良

Agent とは

agent の処理

STM (Software Transactional Memory) : トランザクションの管理

STM とは

STM の処理

参考