[3-1]
Javaの関数型言語への挑戦/
ベターオブジェクト指向言語からの脱皮
2015年4月8日
富士通株式会社
数村 憲治
関数型言語とは
Javaと関数型言語
関数型言語の特徴
参照透過性
再帰
ストリーム
遅延評価
ストリームで注意すべきこと
Javaにおける並列プログラミングの実力
アジェンダ
関数型言語(FP)とは
Haskell
Scala
Erlang
F#
Lisp
無名関数
遅延評価
末尾再帰
高階関数
参照透過性
モナド
なぜ、今、関数型言語か
ハードウェア
メニーコア
大容量メモリ
SSD
並列プログラミングの
必然性
関数型言語に注目
手続き型言語では難しい
IoT
ビッグデータ
インメモリデータベース
環境・プラットフォーム
メニーコアで性能向上させるには
プログラマーは、どれだけ頑張ればよいのか?
並列処理は、どんな言語でも頑張ればできる。
低い
高い
熟練プログラマ 手続き型言語 熟練プログラマ 関数型言語 一般プログラマ 関数型言語 一般プログラマ 手続き型言語性能+品質
≧
≫
≒
並列と並行
並列(Parallel)
とは、
一つの作業を複数に分割し、
それぞれを「本当に」同時に実行することで、
全体処理時間を短くする。
並行(Concurrent)
とは、
複数の作業を別々のスレッドで、
(同期を取りながら)実行する。
必ずしも「本当に」同時に実行しなくてもよい。
並列と並行の例
Parallel GC
Concurrent GC
GC thread #1 GC thread #2 GC thread #3GC処理を
複数スレッドで
同時に実行
GC thread APP thread #1 APP thread #2GC処理とアプリ処理を
同時に実行
並行・並列プログラミングレベル
レベル1 レベル2 レベル3 スレッド生成・終了 アプリ 言語システム 言語システム 排他制御 アプリ 言語システム 言語システム スレッドプール管理 アプリ 言語システム 言語システム タスク指向 fork/join・future なし アプリ 言語システム Actorモデル なし なし アプリ ストリーミング なし なし アプリC/C++
Java SE 5-7
FP
Java SE 1.4
Java SE 8
レベル1からレベル2へ
スレッド指向
・スレッドを作るところから始める
・スレッドから子スレッドを作ると収集つかない
・スレッドプールは自作
タスク指向
・スレッドの生成やプーリングはシステムで
・プログラマは、スレッドで行う仕事にフォーカス
・結果を同期、非同期いずれでも確認可能
スレッド指向とタスク指向
スレッド指向
タスク指向
class Target
implements Runnable {
public void run() { // do something }
}
Target target = new Target(); Thread t1 =
new Thread(target); t1.start();
t1.join();
result = target.get();
class Task
extends RecursiveTask <Object> { Object compute() { // do something } } ForkJoinPool pool = new ForkJoinPool(N); Future future =
pool.submit(new Task()); if (future.isDone())
レベル2からレベル3へ
アクターモデル
akka等 Javaの標準ライブラリには含まれていないレベル2
ストリームAPI
レベル3
並列処理
並行処理
関数型言語とは
Javaと関数型言語
関数型言語の特徴
参照透過性
再帰
ストリーム
遅延評価
ストリームで注意すべきこと
Javaにおける並列プログラミングの実力
アジェンダ
パラダイムシフト
命令型
オブジェクト指向
関数型
C
C++
Java
Scala
Haskell
ベターC
ベターOOP
?
?
?
継承 カプセル化 ・・・ 参照透過 ラムダ ・・・ モジュール 構造化 ・・・Javaはどこへ向かうのか
It is my belief that the best direction for evolving Java is to encourage
a more functional style of
programming
. The role of Lambda is primarily to support the development and consumption of more functional-like libraries; I've offered examples such as filter-map-reduce to illustrate this direction.Simply put, we believe the best thing we can do for Java developers is to give them a gentle push towards a more functional style of programming.
We're not going to
turn Java into Haskell, nor even into Scala.
http://mail.openjdk.java.net/pipermail/lambda-dev/2011-August/003877.html
OOPとFP
・データはオブジェクト。メッセージはメソッド。
・オブジェクトにメッセージを送り状態を変化。
OOP
FP
・データは不変。
・データに関数を適用し、新しいデータを作る。
データ(オブジェクト)
1 →
3
→
9
データ:1
データ:3
データ:9
メッセージ:
+2
メッセージ:
X3
関数:
+2
関数:
X3
FP品質 - 制約プログラミング
関数型言語で新たに出来ることよりも、
オブジェクト指向言語で出来たことが、
関数型言語では出来なくなることが重要。
破壊的代入
副作用
プログラマに制約をかけ、自由度を減らす
ループ
プログラム品質の向上
FP品質 - 数学的プログラミング
証明された定理を積み上げて
新たな定理を証明
動作保証された小さな関数を合成して
新たな関数を作成
コンパイルが通れば動作の証明(型に関して)
数学
Curry-Howard同型対応
プログラム
命題=型 証明=プログラム
直感主義命題論理と単純型付ラムダ計算の対応
関数型言語とは
Javaと関数型言語
関数型言語の特徴
参照透過性
再帰
ストリーム
遅延評価
ストリームで注意すべきこと
Javaにおける並列プログラミングの実力
アジェンダ
参照透過性
Javaのメソッド
関数型言語の関数
・関数の引数が同じなら、戻り値は同じ
・関数呼び出しによる副作用(状態変化)なし
→ 並列化しやすい
・メソッド呼び出しは、メッセージ送信
・メソッドはオブジェクトの状態を変化させる
→ 並列化しにくい
・変数の再代入(破壊的代入)ができない
Javaで参照透過を実現するには
・メソッドは副作用がないように書く。
・変数には、「final」をつける。
・Immutableオブジェクトを作成・使用。
→ できる範囲で
Immutableオブジェクト
char* str = ・・・
str[3] = ‘¥0’;
String str = ・・・
str = str.substring(3);
Cプログラム
Javaプログラム
オーバランの危険性
Stringはimmutable
常に新しいString生成
複数スレッドで操作すると
データ破壊の可能性
ImmutableなStringがJavaを高品質に
Mutableなクラス
public class SuperMarket {
private ArrayList<Food> foodList;
public List<Food> get() {
return foodList;
}
public void add(Food food) {
foodList.add(food);
}
public void remove(Food food) {
foodList.remove(food);
}
複数スレッドから
呼べない
mutable
安全にするには?(並行プログラミング)
mutableなクラスを安全に
public class SuperMarket {
private ArrayList<Food> foodList;
public
synchronized
List<Food> get() {
return foodList;
}
public
synchronized
void add(Food food) {
foodList.add(food);
}
public
synchronized
void remove(Food food) {
foodList.remove(food);
}
mutableなクラスを安全に
public class SuperMarket {
private ArrayList<Food> foodList;
public
synchronized
List<Food> get() {
return
foodList.clone();
}
public
synchronized
void add(Food food) {
foodList.add(food);
}
public
synchronized
void remove(Food food) {
foodList.remove(food);
更新があまりないなら
public class SuperMarket {
private
CopyOnWriteArrayList
<Food> foodList;
public synchronized List<Food> get() {
return
foodList.clone();
}
public synchronized void add(Food food) {
foodList.add(food);
}
public synchronized void remove(Food food) {
foodList.remove(food);
}
Listを更新されたくないなら
public class SuperMarket {
private CopyOnWriteArrayList<Food> foodList;
public List<Food> get() {
return
Collections.unmodifiableList
(
foodList.clone());
}
java.util.Collections.unmodifiableListで
read-onlyのListの作成
関数型言語とは
Javaと関数型言語
関数型言語の特徴
参照透過性
再帰
ストリーム
遅延評価
ストリームで注意すべきこと
Javaにおける並列プログラミングの実力
アジェンダ
ループから再帰
int foo(Bar[] bars) { int result = 0;
for (int i = 0 ; i < bars.length ; ++i)
result += bars[i].get(); return result;
}
int foo(final Bar[] bars) { return foo1(0, 0, bars); }
int foo1(final int n, final int result, final Bar[] bars) { if (n == bars.length)
return result;
return foo1(n+1, bars[n].get()+result, bars); }
ループ
再帰
末尾再帰最適化(TCO)
Java(JIT)では未対応
最後の処理が自分自身への呼び出しなら、
関数コール(新しいスタック作成)しない。
ループ処理のように同じスタックで処理する。
int foo1(final int n, final int result, final Bar[] bars) {
if (n == bars.length)
return result;
return
foo1
(n+1, bars[n].get()+result, bars);
}
最後の処理が
自分自身への
呼び出し
関数型言語とは
Javaと関数型言語
関数型言語の特徴
参照透過性
再帰
ストリーム
遅延評価
ストリームで注意すべきこと
Javaにおける並列プログラミングの実力
アジェンダ
ストリーム(パイプライン)とは
UNIXのパイプ処理
% cat input | grep keyword | sort | head -5 > output
read(input).stream()
.filter(keyword)
.sorted()
.limit(5)
.writeTo(output)
ストリームプログラミング
FPスタイル
ループからストリーム
Java SE 7の
糖衣構文
int foo(Bar[] bars) { int result = 0;
for (int i = 0 ; i < bars.length ; ++i)
result += bars[i].get(); int foo(Bar[] bars) {
int result = 0; for (Bar b : bars)
result += b.get();
int foo(Bar[] bars) {
return Arrays.stream(bars)
.mapToInt( b -> b.get() ); .sum();
Java SE 8の
stream API
ループv.s.ストリーム(並列化)
int foo(Bar[] bars) throws InterruptedException { BarSum[] barSum = new BarSum[N];
for (int i = 0 ; i < N ; ++i)
barSum[i] = new BarSum(bars, bars.length/N*i, bars.length/N*(i+1)); int result = 0;
for (int i = 0 ; i < N ; ++i) { barSum[i].join();
result += barSum[i].result; }
return result; }
class BarSum extends Thread { Bar[] bars;
int begin, end; int result;
BarSum(Bar[] bars, int begin, int end) { this.bars = bars;
this.begin = begin; this.end = end; }
public void run() {
for (int i = begin ; i < end ; ++i) result += bars[i].get();
}
ループの並列化
int foo(Bar[] bars) {
return Arrays.stream(bars)
.parallel()
.mapToInt( b -> b.get() ); .sum();
関数型言語とは
Javaと関数型言語
関数型言語の特徴
参照透過性
再帰
ストリーム
遅延評価
ストリームで注意すべきこと
Javaにおける並列プログラミングの実力
アジェンダ
遅延評価
デメリット
・メモリ使用量が増える
・デバッグが難しくなる
必要になるまで評価しない
メリット
・無駄な処理をしなくてよくなる
・重い処理を後回しにできる
・並列処理効率を上げられる
Javaでの評価タイミング
nの値はここで決定
if ( f1() && f2() ) {
f1()がfalseならf2()は評価しない
int n = foo();
// nに関係ない処理
System.out.println(n);
一般的には遅延評価と言わない
例1
例2
ここなら
遅延評価という
Javaでは
普通のメソッド呼び出しは遅延評価しない
Javaにおける遅延評価
ストリームの中間操作は遅延評価
終端操作実行時に評価
int foo(List<Integer> list) {
return list.stream()
.filter(i -> i > 30)
.mapToInt(i -> i * 2)
.limit(50)
.sum();
}
中間操作
中間操作
終端操作
中間操作
ストリーム操作の種類
ストリーム操作
ステートフル操作
distinct/sorted
ステートレス操作
map/filter
終端操作
forEach/count
中間操作
遅延評価
並列化しやすい
多段ループ処理
int foo(List<Integer> list) {
ArrayList<Integer> list2 = new ArrayList<>; for (int i : list)
if (i > 30) list2.add(i);
ArrayList<Integer> list3 = new ArrayList<>; for (int i : list2) list3.add(i * 2)
int result = 0; int count = 0; for (int i : list3) {
result += i; count ++; if (count == 50) break; }
待ち合わせ
待ち合わせ
メニーコアにおける並列化
コア1理想
現実
コア2 コア2 コアn コアn コア1 タスク タスク タスク タスク タスク タスク タスク タスク タスク タスク タスク タスク タスク タスク・・・
同時に終わる
タスク タスク タスク タスク 空き 空き・・・
CPUに空き
ループの並列処理化
int foo(List<Integer> list) { int result = 0;
int count = 0; for (int i : list) {
if (i > 30) { result += i *2; count ++; if (count == 50) break; } } return result; }
複数スレッドで
同期を取りながら
50数える必要がある
ループは一つになったが
並列化するには、
遅延評価と並列化
int foo(List<Integer> list) {
return list.stream()
.parallel()
.filter(i -> i > 30)
.mapToInt(i -> i * 2)
.limit(50)
.sum();
}
待ち合わせ
待ち合わせ
待ち合わせ
遅延評価がないと
並列化の源は遅延評価
関数型言語とは
Javaと関数型言語
関数型言語の特徴
参照透過性
再帰
ストリーム
遅延評価
ストリームで注意すべきこと
Javaにおける並列プログラミングの実力
アジェンダ
並列から逐次へ
ソート後は逐次に
someStream .parallel() .filter(e -> e.shouldHandle()) .sorted() .limit(100) .forEach(e -> System.out.println(e)); someStream .parallel() .filter(e -> e.shouldHandle()) .sorted() .sequential() .limit(100) .forEach(e -> System.out.println(e));ソートされない
出力
streamは速やかに流す
Synchronizedを使わない
static Object lock = new Object();
Bar foo(List<Bar> list) {
return list.stream()
.parallel()
.map(b -> {
synchronized
(lock) { return b.baz();}
})
.max(comparator);
}
副作用を書かない
void foo(List<Bar> list) {
ArrayList<Bar> result = new ArrayList<>();
list.stream()
.parallel()
.filter(b -> b.baz())
.forEach(b ->
result.add(b)
);
List<Bar> result = list.stream()
.parallel()
.filter(b -> b.baz())
Collectors(リダクション)
・リダクション用のstaticメソッド群が定義
・Stream.collect()メソッドに指定する
・toList/groupingBy/summingIntなど
例:
java.util.stream.Collectors
List<Bar> result = list.stream()
.parallel()
.filter(b -> b.baz())
CollectorとStreamの属性
UNORDERED: 順序が保証されない
IDENTITY_FINISH: フィニッシャー不要
CONCURRENT: アキュムレータの同時呼び出し可
Collectorの属性
Streamの属性
unordered: 順序不定のストリーム
parallel: 並列ストリーム
並列リダクションの条件
(A) Streamがparallel
かつ
(B) CollectorがCONCURRENT
かつ
(C) Streamがunordered または
CollectorがUNORDERED
並列リダクション
Map<Foo, Bar> result = source.stream()
.parallel()
.filter(b -> b.baz())
.collect(
toMap
(b->b.foo(), b));
ConcurrentMap<Foo, Bar> result =
source.stream()
.parallel()
.filter(b -> b.baz())
.collect(
toConcurrentMap
(b->b.foo(), b));
非並列
並列
CONCURRENT属性なし CONCURRENT属性 UNORDERED属性 parallel stream parallel stream
関数型言語とは
Javaと関数型言語
関数型言語の特徴
参照透過性
再帰
ストリーム
遅延評価
ストリームで注意すべきこと
Javaにおける並列プログラミングの実力
アジェンダ
Stream APIによる並列性能
レベル2のプログラム(fork/join使用)と
レベル3のプログラム(stream使用)との比較
ベンチマークモデル
100万件の購買伝票を基に、
購入関連の高い商品群を抽出し、
未購入ユーザにレコメンドする。
指標
生産性(ソース行数)と性能(実行時間)
生産性(ソース行数)
static Map<Account, List<Product>> createProductMap(Account[] accounts) { return Arrays.stream(accounts).parallel() .collect(Collectors.toMap(Function.identity(), acc -> acc.records.stream() .flatMap(rec -> rec.orders.stream()) .map(ord -> ord.product) .distinct() .collect(Collectors.toList()))); }
static Map<Account, List<Product>> createProductMap(Account[] accounts) { Map<Account, List<Product>> map = new ConcurrentHashMap<>(); ArrayList<ForkJoinTask> tlist = new ArrayList<>();
for (Account acc : accounts) {
ForkJoinTask task = pool.submit(new Runnable() { public void run() {
ArrayList<Product> list = new ArrayList<>(); for (PurchaseRecord pr : acc.records)
for (Order ord : pr.orders)
if (!list.contains(ord.product)) list.add(ord.product); map.put(acc, list); }}); tlist.add(task); }
for (ForkJoinTask task : tlist) task.join(); レベル2のソース レベル3のソース 0 20 40 60 80 100 120 140 レベル2(fork/join) レベル3(stream) ス テ ッ プ 数 ソース行数(除共通部分)