2009年9月29日火曜日

モナドを C# で 01

C# で Maybe モナドっぽいものと State モナドっぽいもの。
型構成子とか関数の拡張が自動化できればよかったけれど、とりあえずごりごり記述。
確かに使う側での副作用はなさそう。

// Haskell の >>= がなんて呼ばれているかわからない…orz。とりあえず束縛。


using System;
using System.Data;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;

class Program
{
static void Main(string[] args)
{
var result1 =
new Maybe<string[]>(new string[] { "012", "345", null, "678" })
.Bind(ss => ss.Skip(1))
.Bind(ss => ss.Skip(1).ElementAt(0))
.Bind(s => Regex.Match(s, "[0-3]+"))
.Bind(m => m.Value);

Console.WriteLine("result1 = " + result1.Apply());
// result1 =

var result2 =
new Maybe<string[]>(new string[] { "012", "345", "3", "678" })
.Bind(ss => ss.Skip(1))
.Bind(ss => ss.Skip(1).ElementAt(0))
.Bind(s => Regex.Match(s, "[0-3]+"))
.Bind(m => m.Value);

Console.WriteLine("result2 = " + result2.Apply());
// result2 = 3

var result3 =
new State<string, string>("123456789")
.Bind<string, int>(t => new Tuple<string, int>(t.State, t.State.Length))
.Bind<int, string>(t => new Tuple<int, string>(t.State, t.State.ToString()))
.Bind<string, string>(t => new Tuple<string, string>(t.State, t.State + "010101"));

Console.WriteLine("result3 = " + result3.Apply());
// result3 = 9010101


Console.ReadLine();
}
}


// Maybe モナド?
public class Maybe<T>
where T : class
{
private Func<T> func;

public Maybe(T value)
{
this.func = new Func<T>(() => value);
}

public Maybe(Func<T> func)
{
if (func == null) throw new ArgumentNullException("func");
this.func = func;
}

public Maybe<S> Bind<S>(Func<T, S> func)
where S : class
{
if (func == null) throw new ArgumentNullException("func");
return new Maybe<S>(new Func<S>(() => { var x = this.func(); return x == null ? null : func(x); }));
}

public T Apply()
{
return this.func();
}
}



// State モナド?
public class State<V1, S1>
{
private Func<V1, Tuple<V1, S1>> func;
public State(S1 s)
{
this.func = new Func<V1, Tuple<V1, S1>>(value => new Tuple<V1, S1>(value, s));
}

public State(Func<V1, Tuple<V1, S1>> func)
{
if (func == null) throw new ArgumentNullException("func");
this.func = func;
}

public State<V2, S2> Bind<V2, S2>(Func<Tuple<V1, S1>, Tuple<V2, S2>> func)
{
if (func == null) throw new ArgumentNullException("func");
return new State<V2, S2>(
new Func<V2, Tuple<V2, S2>>(value => { var t = func(this.func(default(V1))); return new Tuple<V2, S2>(t.Value, t.State); }));
}

public S1 Apply()
{
return this.func(default(V1)).State;
}
}


// C# にも Tuple 欲しいかも。
public struct Tuple<V1, S1>
{
private V1 value;
private S1 state;

public Tuple(V1 value, S1 state)
{
this.value = value;
this.state = state;
}

public V1 Value { get { return this.value; } set { this.value = value; } }
public S1 State { get { return this.state; } set { this.state = value; } }
}

2009年9月27日日曜日

JavaでLINQ03

昨日のHokuriku.Scala 第一回 : ATNDでだいぶ読み替え慣れてきた。一通りメソッドを用意。
PLINQ → Java のポーティングと、PLINQ → Scala のポーティングはどう考えても後者のほうが楽そう。
Scala で書いてコンパイルしたクラスを GAE に送り込んで、もし動けばこのシリーズはとりあえず終われるかな?

メイン:

import java.util.List;

public class Main {

public static void main(String[] args) throws InterruptedException {

System.out.println("map Result: ");
for (Integer i : Enumerable.range(1, 3)
.map(
new Func1<Integer, Integer>(){
public Integer _(Integer i) {
return i * 2;
}
}
)) {
System.out.println(i);
}
// map Result:
// 2
// 4
// 6


System.out.println("filter Result: ");
for (Integer i : Enumerable.range(1, 4)
.filter(
new Func1<Integer, Boolean>() {
public Boolean _(Integer i) {
return i % 2 == 0;
}
}
)) {
System.out.println(i);
}
// filter Result:
// 2
// 4


System.out.println("takeWhile Result: ");
for (Integer i : Enumerable.range(1, 5)
.takeWhile(
new Func1<Integer, Boolean>() {
public Boolean _(Integer i) {
return i <= 3;
}
}
)) {
System.out.println(i);
}
// takeWhile Result:
// 1
// 2
// 3


System.out.println("foldLeft Result: ");
Integer result = Enumerable.range(1, 10)
.foldLeft(0)
._(
new Func2<Integer, Integer, Integer>(){
public Integer _(Integer sum, Integer a) {
return sum + a;
}
}
);
System.out.println(result);
// foldLeft Result:
// 55


System.out.println("fibs Result: ");
for (Integer i : fibs().take(10)) {
System.out.println(i);
}
// fibs Result:
// 0
// 1
// 1
// 2
// 3
// 5
// 8
// 13
// 21
// 34
}

private static Enumerable<Integer> fibs() {

final Enumerable<Integer> initialValues =
Enumerable.yield(
0,
1
);

final Enumerable<Integer> fibsEnumeralbe =
new Enumerable<Integer>(
new Func0<Iterable<Integer>>() {
public Iterable<Integer> _() {
return fibs();
}
}
);

return initialValues.concat(
Enumerable.zip(
new Func0<Iterable<Integer>> () {
public Iterable<Integer> _() {
return fibsEnumeralbe;
}
},
new Func0<Iterable<Integer>> () {
public Iterable<Integer> _() {
return fibsEnumeralbe.skip(1);
}
}
)
.select(
new Func1<List<Integer>, Integer> () {
public Integer _(List<Integer> arg0) {
return arg0.get(0) + arg0.get(1);
}
}
)
);
}
}




関数オブジェクトの替わりのインターフェース達:

public interface Func0<TResult> {
TResult _();
}

public interface Func1<T, TResult> {
TResult _(final T arg0);
}

public interface Func2<T0, T1, TResult> {
TResult _(final T0 arg0, final T1 arg1);
}


Adaptor クラス:

import java.util.Iterator;


public class IteratorAdaptor<T> implements Iterator<T> {

@Override
public boolean hasNext() {
return false;
}

@Override
public T next() {
return null;
}

@Override
public void remove() {
}

public Iterable<T> asIterable() {
final IteratorAdaptor<T> _this = this;
return new Iterable<T>() {
@Override
public Iterator<T> iterator() {
return _this;
}
};
}

}


Enumerable クラス(これが本体):

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;


public class Enumerable<T> implements Iterable<T> {

private Func0<Iterable<T>> func;

public Enumerable(Func0<Iterable<T>> func) {
this.func = func;
}

public <TResult> Enumerable<TResult> select(final Func1<T, TResult> func) {

final Enumerable<T> _this = this;

final class IteratorImpl extends IteratorAdaptor<TResult> {

private Iterator<T> iterator;

@Override
public boolean hasNext() {
if (iterator == null) {
iterator = _this.func._().iterator();
}
return iterator.hasNext();
}

@Override
public TResult next() {
return func._(iterator.next());
}

}

return new Enumerable<TResult>(
new Func0<Iterable<TResult>>() {
public Iterable<TResult> _() { return new IteratorImpl().asIterable(); }
}
);
}

public <TResult> Enumerable<TResult> map(final Func1<T, TResult> func) {
return select(func);
}

public <TResult> Enumerable<TResult> selectMany(final Func1<T, Enumerable<TResult>> selector) {

final Enumerable<T> _this = this;

final class IteratorImpl extends IteratorAdaptor<TResult> {

private Iterator<T> iterator;
private Iterator<TResult> selectorIterator;

@Override
public boolean hasNext() {
if (iterator == null) {
iterator = _this.func._().iterator();
}
boolean hasNext;
if (selectorIterator == null) {
hasNext = iterator.hasNext();
if (hasNext) {
selectorIterator = selector._(iterator.next()).iterator();
hasNext = selectorIterator.hasNext();
}
else {
// 列挙終了。
}
}
else {
hasNext = selectorIterator.hasNext();
if (!hasNext) {
selectorIterator = null;
hasNext = hasNext();
}
}

return hasNext;
}

@Override
public TResult next() {
return selectorIterator == null ? null : selectorIterator.next();
}

}

return new Enumerable<TResult>(
new Func0<Iterable<TResult>>() {
public Iterable<TResult> _() { return new IteratorImpl().asIterable(); }
}
);
}

public Enumerable<T> where(final Func1<T, Boolean> predicate) {

final Enumerable<T> _this = this;

final class IteratorImpl extends IteratorAdaptor<T> {

private Iterator<T> iterator;

@Override
public boolean hasNext() {
if (iterator == null) {
iterator = _this.func._().iterator();
}
boolean hasNext;
while ((hasNext = iterator.hasNext())) {
if (predicate._(iterator.next())) {
break;
}
}
return hasNext;
}

@Override
public T next() {
return iterator.next();
}

}

return new Enumerable<T>(
new Func0<Iterable<T>>() {
public Iterable<T> _() { return new IteratorImpl().asIterable(); }
}
);
}

public Enumerable<T> filter(final Func1<T, Boolean> predicate) {
return where(predicate);
}

public Enumerable<T> take(final int count) {

final Enumerable<T> _this = this;

final class IteratorImpl extends IteratorAdaptor<T> {

private int index;
private Iterator<T> iterator;

@Override
public boolean hasNext() {
if (iterator == null) {
iterator = _this.func._().iterator();
}
return index++ < count ? iterator.hasNext() : false;
}

@Override
public T next() {
return iterator.next();
}

}

return new Enumerable<T>(
new Func0<Iterable<T>>() {
public Iterable<T> _() { return new IteratorImpl().asIterable(); }
}
);
}

public Enumerable<T> takeWhile(final Func1<T, Boolean> predicate) {

final Enumerable<T> _this = this;

final class IteratorImpl extends IteratorAdaptor<T> {

private Iterator<T> iterator;

@Override
public boolean hasNext() {
if (iterator == null) {
iterator = _this.func._().iterator();
}
boolean hasNext = iterator.hasNext();
return hasNext && predicate._(iterator.next());
}

@Override
public T next() {
return iterator.next();
}

}

return new Enumerable<T>(
new Func0<Iterable<T>>() {
public Iterable<T> _() { return new IteratorImpl().asIterable(); }
}
);
}

public Enumerable<T> skip(final int count) {

final Enumerable<T> _this = this;

final class IteratorImpl extends IteratorAdaptor<T> {

private Iterator<T> iterator;

@Override
public boolean hasNext() {
if (iterator == null) {
iterator = _this.func._().iterator();
for (int counter = 0; counter < count && iterator.hasNext(); counter++);
}
return iterator.hasNext();
}

@Override
public T next() {
return iterator.next();
}
}

return new Enumerable<T>(
new Func0<Iterable<T>>() {
public Iterable<T> _() { return new IteratorImpl().asIterable(); }
}
);
}

public Enumerable<T> concat(final Enumerable<T> enumerable) {

final Enumerable<T> _this = this;

final class IteratorImpl extends IteratorAdaptor<T> {

private Iterator<T> iterator;
private boolean nextIteratorInitialized;

@Override
public boolean hasNext() {
if (iterator == null) {
iterator = _this.func._().iterator();
}
boolean hasNext = iterator.hasNext();
if (!hasNext && !nextIteratorInitialized) {
iterator = enumerable.iterator();
nextIteratorInitialized = true;
hasNext = iterator.hasNext();
}
return hasNext;
}

@Override
public T next() {
return iterator.next();
}
}


return new Enumerable<T>(
new Func0<Iterable<T>>() {
public Iterable<T> _() { return new IteratorImpl().asIterable(); }
}
);
}

public Func1<Func2<T, T, T>, T> foldLeft(final T initialValue) {

final Enumerable<T> _this = this;

return new Func1<Func2<T, T, T>, T>() {
@Override
public T _(Func2<T, T, T> arg0) {
T lastValue = initialValue;

for (T current : _this.func._()) {
lastValue = arg0._(lastValue, current);
}

return lastValue;
}
};
}


@Override
public Iterator<T> iterator() {
return this.func._().iterator();
}

public static <T> Enumerable<T> iterate(final T initialValue, final Func1<T, T> func) {

final class IteratorImpl extends IteratorAdaptor<T> {

private boolean initialized;
private T next;

@Override
public boolean hasNext() {
if (!initialized) {
next = initialValue;
initialized = true;
}
else {
next = func._(next);
}
return true;
}

@Override
public T next() {
return next;
}

}

return new Enumerable<T>(
new Func0<Iterable<T>>() {
public Iterable<T> _() { return new IteratorImpl().asIterable(); }
}
);
}

public static Enumerable<Integer> range(final int start, final int count) {
return iterate(
start,
new Func1<Integer, Integer> () {
public Integer _(Integer arg0) {
return arg0 + 1;
}
}
)
.take(count);
}

public static <T> Enumerable<List<T>> zip(final Func0<Iterable<T>> func1, final Func0<Iterable<T>> func2) {

final class IteratorImpl extends IteratorAdaptor<List<T>> {

private Iterator<T> iterator1;
private Iterator<T> iterator2;

@Override
public boolean hasNext() {
if (iterator1 == null) {
iterator1 = func1._().iterator();
}
if (iterator2 == null) {
iterator2 = func2._().iterator();
}
boolean hasNext1 = iterator1.hasNext();
boolean hasNext2 = iterator2.hasNext();
return hasNext1 || hasNext2;
}

@Override
public List<T> next() {
List<T> tuple = new ArrayList<T>();
tuple.add(iterator1.next());
tuple.add(iterator2.next());
return tuple;
}
}

return new Enumerable<List<T>>(
new Func0<Iterable<List<T>>>() {
public Iterable<List<T>> _() { return new IteratorImpl().asIterable(); }
}
);
}

public static <T> Enumerable<T> yield(final Object ... objects) {

final class IteratorImpl extends IteratorAdaptor<T> {

private int index = -1;

@Override
public boolean hasNext() {
if (++index < objects.length) {
return true;
}
else {
return false;
}
}

@SuppressWarnings("unchecked")
@Override
public T next() {
if (objects[index] instanceof Func0) {
return (T)((Func0)objects[index])._();
}
else {
return (T)objects[index];
}
}

}

return new Enumerable<T>(
new Func0<Iterable<T>>() {
public Iterable<T> _() { return new IteratorImpl().asIterable(); }
}
);
}

public static <T> Enumerable<T> yieldWhile(final Func0<T> func) {
return yieldWhile(
func,
new Func1<T, Boolean>() {
public Boolean _(T arg0) {
return true;
}
}
);
}

public static <T> Enumerable<T> yieldWhile(final Func0<T> func, final Func1<T, Boolean> predicate) {
return iterate(
func._(),
new Func1<T, T>(){
public T _(T arg0) {
return func._();
}
}
)
.where(predicate);
}
}

2009年9月21日月曜日

MapReduce を C# で 05

括弧の数減らすのは断念。Map 処理やってるところと Reduce 処理やってるところが一覧できたほうがいいと思ったため。Parallel な Foreach を導入。列挙と中身の処理が 1 スレッドだったのが複数スレッド対応に。ここまで設計できれば、Java や GAE へのポーティングもラクになるはず…。

// あ、IDisposable !…後でいいか。(^_^;)



/// <summary>
/// パイプライン実行を可能にするための列挙子。
/// </summary>
/// <remarks>IEnumerator は生成後のソース変更を許可しないため、このようなインターフェースを用意。</remarks>
/// <typeparam name="T"></typeparam>
public interface ParallelIterator<T>
: IEnumerator<T>, IDisposable, IEnumerator
{
bool TryNext(out T result);
new void Reset();
}

public interface ParallelIterable<T>
: IEnumerable<T>, IEnumerable
{
ParallelIterator<T> GetIterator();
}

public interface IParallelCollection<T>
: ParallelIterable<T>, IEnumerable<T>, IEnumerable
{
int Count { get; }
bool IsReadOnly { get; }
void Add(T item);
void Clear();
bool Contains(T item);
void CopyTo(T[] array, int arrayIndex);
bool Remove(T item);

/// <summary>
/// 更新終了。
/// </summary>
bool Fixed { get; set; }
}

public interface IParallelList<T>
: IParallelCollection<T>, ParallelIterable<T>, IEnumerable<T>, IEnumerable
{
T this[int index] { get; set; }
int IndexOf(T item);
void Insert(int index, T item);
void RemoveAt(int index);
}

public interface IParallelDictionary<TKey, TValue>
: IParallelCollection<KeyValuePair<TKey, TValue>>, ParallelIterable<KeyValuePair<TKey, TValue>>,
IEnumerable<KeyValuePair<TKey, TValue>>, IEnumerable
{
IParallelCollection<TKey> Keys { get; }
IParallelCollection<TValue> Values { get; }
TValue this[TKey key] { get; set; }
void Add(TKey key, TValue value);
bool ContainsKey(TKey key);
bool Remove(TKey key);
bool TryGetValue(TKey key, out TValue value);

// NOTE: ParallelIterator&lt;T&gt; の Fixed 実装時は、 Keys や Values の中身も忘れずに Fixed すること。
}

public interface IMapper<TInKey, TInValue, TOutKey, TIntermediateValue>
{
ParallelIterable<KeyValuePair<TOutKey, TIntermediateValue>> Map(TInKey inkey, TInValue inValue);
int BufferSize { get; set; }
TimeSpan BufferFlushTimeout { get; set; }
}

public interface IReducer<TOutKey, TIntermediateValue, TOutValue>
{
ParallelIterable<TOutValue> Reduce(TOutKey outKey, ParallelIterable<TIntermediateValue> intermediateValues);
int BufferSize { get; set; }
TimeSpan BufferFlushTimeout { get; set; }
}

public interface IOperation
{
void Wait();
bool Wait(int millisecondsTimeout);
bool Wait(TimeSpan timeout);
}

public interface ITaskQueue
{
IOperation AddTask(Delegate action, params object[] state);
}

// TODO: IDisposable 実装!
public sealed class MapReduceManager<TInKey, TInValue, TOutKey, TIntermediateValue, TOutValue>
{
// 各実装に合わせた中間値保存、出力値保存用のストレージ取得処理。
public Func<IParallelCollection<TIntermediateValue>> NewIntermediateValueStorage { get; set; }
public Func<IParallelCollection<TOutValue>> NewOutValueStorage { get; set; }

// 各実装にあわせた MapReduce 処理と中間値参照用のリポジトリ。
public IMapper<TInKey, TInValue, TOutKey, TIntermediateValue> Mapper { get; set; }
public IReducer<TOutKey, TIntermediateValue, TOutValue> Reducer { get; set; }
public IParallelDictionary<TOutKey, IParallelCollection<TIntermediateValue>> Repository { get; set; }

// パイプライン実行のためのタスクキューおよび実行ハンドラ。
public ITaskQueue TaskQueue { get; set; }
public Func<IParallelCollection<IOperation>> NewOperations { get; set; }

public IEnumerable<TOutValue> DoProcess(TInKey inKey, TInValue inValue)
{
var outValues = this.NewOutValueStorage();
var reducingOperations = this.NewOperations();

// Map 処理
var mapperParallelLoop = this.NewMapperParallelLoop();
mapperParallelLoop
.Foreach(this.Mapper.Map(inKey, inValue),
new Action<KeyValuePair<TOutKey, TIntermediateValue>>(
intermediate =>
{
if (!this.Repository.ContainsKey(intermediate.Key))
{
var intermediateValues = this.NewIntermediateValueStorage();
intermediateValues.Add(intermediate.Value);
this.Repository.Add(intermediate.Key, intermediateValues);

// Reduce 処理
reducingOperations.Add(
this.TaskQueue.AddTask(
new Action(
() =>
{
var reducerParallelLoop = this.NewReducerParallelLoop();

reducerParallelLoop
.Foreach(this.Reducer.Reduce(intermediate.Key, this.Repository[intermediate.Key]),
new Action<TOutValue>(
outValue =>
{
outValues.Add(outValue);
}
)
);

reducerParallelLoop.WaitAll();
}
)
)
);
}
else
{
this.Repository[intermediate.Key].Add(intermediate.Value);
}
}
)
);

// Map 処理が一通り終わったところで、出力の列挙開始ができるように。
this.TaskQueue.AddTask(
new Action(
()=>
{
mapperParallelLoop.WaitAll();
this.Repository.Fixed = true;
reducingOperations.Fixed = true;
foreach (var operation in reducingOperations)
{
operation.Wait();
}
outValues.Fixed = true;
}
)
);

return outValues;
}


private ParallelLoop<KeyValuePair<TOutKey, TIntermediateValue>> NewMapperParallelLoop()
{
var mapperParallelLoop = new ParallelLoop<KeyValuePair<TOutKey, TIntermediateValue>>();
mapperParallelLoop.TaskQueue = this.TaskQueue;
mapperParallelLoop.NewOperations = this.NewOperations;
mapperParallelLoop.BufferSize = this.Mapper.BufferSize;
mapperParallelLoop.BufferFlushTimeout = this.Mapper.BufferFlushTimeout;
return mapperParallelLoop;
}

private ParallelLoop<TOutValue> NewReducerParallelLoop()
{
var reducerParallelLoop = new ParallelLoop<TOutValue>();
reducerParallelLoop.TaskQueue = this.TaskQueue;
reducerParallelLoop.NewOperations = this.NewOperations;
reducerParallelLoop.BufferSize = this.Reducer.BufferSize;
reducerParallelLoop.BufferFlushTimeout = this.Reducer.BufferFlushTimeout;
return reducerParallelLoop;
}
}

public class ParallelLoop<T>
{
public ITaskQueue TaskQueue { get; set; }
public Func<IParallelCollection<IOperation>> NewOperations { get; set; }
public int BufferSize { get; set; }
public TimeSpan BufferFlushTimeout { get; set; }

private IParallelCollection<IOperation> operations;
private ParallelIterator<IOperation> operationsIterator;
private IParallelCollection<IOperation> innerOperations;

public ParallelLoop()
{
this.BufferSize = 1;
this.BufferFlushTimeout = new TimeSpan(TimeSpan.TicksPerMinute);
}

public void Foreach(ParallelIterable<T> iterable, Action<T> action)
{
this.operations = this.NewOperations();
this.operationsIterator = this.operations.GetIterator();
this.innerOperations = this.NewOperations();

var iterator = iterable.GetIterator();
bool hasNext = true;

int current = 0;
while (hasNext)
{
// 列挙とその値を使った処理をパイプライン化
this.operations.Add(
this.TaskQueue.AddTask(
new Action(
() =>
{
T value = default(T);
hasNext = iterator.TryNext(out value);
if (hasNext)
{
this.innerOperations.Add(this.TaskQueue.AddTask(new Action(() => action(value))));
}
}
)
)
);

// 不必要な operation が増えすぎないよう、実装ごとの BufferSize で処理を Flush する。
if (this.BufferSize < ++current)
{
this.operations.Fixed = true;
IOperation operation = null;
while (this.operationsIterator.TryNext(out operation))
{
if (!operation.Wait(this.BufferFlushTimeout))
{
this.operations.Fixed = false;
this.operations.Add(operation);
this.operations.Fixed = true;

break;
}
}
this.operations.Fixed = false;

current = 0;
}
}


this.operations.Fixed = true;
}

public void WaitAll()
{
IOperation operation = null;
while (this.operationsIterator.TryNext(out operation))
{
operation.Wait();
}

this.innerOperations.Fixed = true;
var innerOperationsIterator = this.innerOperations.GetIterator();
while (innerOperationsIterator.TryNext(out operation))
{
operation.Wait();
}
}
}

MapReduce を C# で 04

だいぶ修正。しかし、括弧は増えるばかり(泣)

/// <summary>
/// パイプライン実行を可能にするための列挙子。
/// </summary>
/// <remarks>IEnumerator は生成後のソース変更を許可しないため、このようなインターフェースを用意。</remarks>
/// <typeparam name="T"></typeparam>
public interface ParallelIterator<T>
: IEnumerator<T>, IDisposable, IEnumerator
{
bool TryNext(out T result);
new void Reset();
}

public interface ParallelIterable<T>
: IEnumerable<T>, IEnumerable
{
ParallelIterator<T> GetIterator();
}

public interface IParallelCollection<T>
: ParallelIterable<T>, IEnumerable<T>, IEnumerable
{
int Count { get; }
bool IsReadOnly { get; }
void Add(T item);
void Clear();
bool Contains(T item);
void CopyTo(T[] array, int arrayIndex);
bool Remove(T item);

/// <summary>
/// 更新終了。
/// </summary>
bool Fixed { get; set; }
}

public interface IParallelList<T>
: IParallelCollection<T>, ParallelIterable<T>, IEnumerable<T>, IEnumerable
{
T this[int index] { get; set; }
int IndexOf(T item);
void Insert(int index, T item);
void RemoveAt(int index);
}

public interface IParallelDictionary<TKey, TValue>
: IParallelCollection<KeyValuePair<TKey, TValue>>, ParallelIterable<KeyValuePair<TKey, TValue>>,
IEnumerable<KeyValuePair<TKey, TValue>>, IEnumerable
{
IParallelCollection<TKey> Keys { get; }
IParallelCollection<TValue> Values { get; }
TValue this[TKey key] { get; set; }
void Add(TKey key, TValue value);
bool ContainsKey(TKey key);
bool Remove(TKey key);
bool TryGetValue(TKey key, out TValue value);
}

public interface IMapper<TInKey, TInValue, TOutKey, TIntermediateValue>
{
IEnumerable<KeyValuePair<TOutKey, TIntermediateValue>> Map(TInKey inkey, TInValue inValue);
}

public interface IReducer<TOutKey, TIntermediateValue, TOutValue>
{
IEnumerable<TOutValue> Reduce(TOutKey outKey, ParallelIterable<TIntermediateValue> intermediateValues);
}

public interface IOperation
{
void Wait();
}

public interface ITaskQueue
{
IOperation AddTask(Delegate action, params object[] state);
}


public sealed class MapReduceManager<TInKey, TInValue, TOutKey, TIntermediateValue, TOutValue>
{
// 各実装に合わせた中間値保存、出力値保存用のストレージ取得処理。
public Func<IParallelCollection<TIntermediateValue>> NewIntermediateValueStorage { get; set; }
public Func<IParallelCollection<TOutValue>> NewOutValueStorage { get; set; }

// 各実装にあわせた MapReduce 処理と中間値参照用のリポジトリ。
public IMapper<TInKey, TInValue, TOutKey, TIntermediateValue> Mapper { get; set; }
public IReducer<TOutKey, TIntermediateValue, TOutValue> Reducer { get; set; }
public IParallelDictionary<TOutKey, IParallelCollection<TIntermediateValue>> Repository { get; set; }

// パイプライン実行のためのタスクキューおよび実行ハンドラ。
public ITaskQueue TaskQueue { get; set; }
public Func<IParallelCollection<IOperation>> NewIntermediateOperations { get; set; }
public Func<IParallelCollection<IOperation>> NewReducingOperations { get; set; }
public Func<IParallelCollection<IOperation>> NewOutValueOperations { get; set; }

public IEnumerable<TOutValue> DoProcess(TInKey inKey, TInValue inValue)
{
var outValues = this.NewOutValueStorage();

var intermediateOperations = this.NewIntermediateOperations();
var reducingOperations = this.NewReducingOperations();
var outValueOperations = this.NewOutValueOperations();

foreach (var intermediate in this.Mapper.Map(inKey, inValue))
{
intermediateOperations.Add(
this.TaskQueue.AddTask(
new Action(
() =>
{
if (!this.Repository.ContainsKey(intermediate.Key))
{
var intermediateValues = this.NewIntermediateValueStorage();
intermediateValues.Add(intermediate.Value);
this.Repository.Add(intermediate.Key, intermediateValues);

reducingOperations.Add(
this.TaskQueue.AddTask(
new Action(
() =>
{
foreach (var outValue in this.Reducer.Reduce(intermediate.Key,
this.Repository[intermediate.Key]))
{
outValueOperations.Add(
this.TaskQueue.AddTask(
new Action(
() =>
{
outValues.Add(outValue);
}
)
)
);
}
}
)
)
);
}
else
{
this.Repository[intermediate.Key].Add(intermediate.Value);
}
}
)
)
);
}

this.TaskQueue.AddTask(
new Action(
()=>
{
intermediateOperations.Fixed = true;
foreach (var operation in intermediateOperations)
{
operation.Wait();
}

this.Repository.Fixed = true;

this.Repository.Values.Fixed = true;
foreach (var value in this.Repository.Values)
{
value.Fixed = true;
}

reducingOperations.Fixed = true;
foreach (var operation in reducingOperations)
{
operation.Wait();
}

outValueOperations.Fixed = true;
foreach (var operation in outValueOperations)
{
operation.Wait();
}

outValues.Fixed = true;
}
)
);

return outValues;
}
}

2009年9月19日土曜日

MapReduce を C# で 03

IParallelEventCollection 実装サンプル。メモリ上に展開する一番簡単なバージョン。TryNext が複雑かも。 Java の Iterator みたく、 hasNext と next に分けたほうが良さげ。

public class Sample_RAMStrage : IParallelEventCollection<string>
{
private List<string> list;
private object syncObject;

public Sample_RAMStrage()
{
this.list = new List<string>();
this.syncObject = new object();
}

private class Sample_RAMIterator : ParallelIterator<string>
{
private int count;
private Sample_RAMStrage source;
private string current;

public Sample_RAMIterator(Sample_RAMStrage source)
{
this.count = -1;
this.source = source;
}

#region Iterator<string> メンバ

public bool TryNext(out string result)
{
try
{
Monitor.Enter(this.source.syncObject);

// Wait 後に条件を再計算させるため、 this.count + 1 < this.source.Count を
// while 前にローカル変数とかに保存してしまうと悲しい結果になる・・・。
// Java の Iterator みたく hasNext メソッドと next メソッドにわけたほうが良さげ。
while (!this.source.EndIterationPending || this.count + 1 < this.source.Count)
{
if (this.count + 1 < this.source.Count)
{
result = this.source[++this.count];
this.current = result;
return true;
}
else
{
Monitor.Wait(this.source.syncObject);
}
}

result = default(string);
this.current = result;
return false;
}
finally
{
Monitor.Exit(this.source.syncObject);
}
}

public void Reset()
{
throw new NotImplementedException();
}

#endregion

#region IEnumerator<string> メンバ

public string Current
{
get
{
try
{
Monitor.Enter(this.source.syncObject);
return this.current;
}
finally
{
Monitor.Exit(this.source.syncObject);
}
}
}

#endregion

#region IDisposable メンバ

public void Dispose()
{
// NOP
}

#endregion

#region IEnumerator メンバ

object IEnumerator.Current
{
get { return this.Current; }
}

public bool MoveNext()
{
return this.TryNext(out this.current);
}

#endregion
}


#region IIterableList<string> メンバ

public string this[int index]
{
get
{
try
{
Monitor.Enter(this.syncObject);
return this.list[index];
}
finally
{
Monitor.Exit(this.syncObject);
}
}
set
{
try
{
Monitor.Enter(this.syncObject);
this.list[index] = value;
}
finally
{
Monitor.Exit(this.syncObject);
}
}
}

public int IndexOf(string item)
{
throw new NotImplementedException();
}

public void Insert(int index, string item)
{
throw new NotImplementedException();
}

public void RemoveAt(int index)
{
throw new NotImplementedException();
}

#endregion

#region IIterableCollection<string> メンバ

public int Count
{
get
{
try
{
Monitor.Enter(this.syncObject);
return this.list.Count;
}
finally
{
Monitor.Exit(this.syncObject);
}
}
}

public bool IsReadOnly
{
get { throw new NotImplementedException(); }
}

public void Add(string item)
{
try
{
Monitor.Enter(this.syncObject);
this.list.Add(item);
Monitor.Pulse(this.syncObject);
}
finally
{
Monitor.Exit(this.syncObject);
}
}

public void Clear()
{
throw new NotImplementedException();
}

public bool Contains(string item)
{
throw new NotImplementedException();
}

public void CopyTo(string[] array, int arrayIndex)
{
throw new NotImplementedException();
}

public bool Remove(string item)
{
throw new NotImplementedException();
}

#endregion

#region Iterable<string> メンバ

public ParallelIterator<string> GetIterator()
{
return new Sample_RAMIterator(this);
}

#endregion

#region IEnumerable<string> メンバ

public IEnumerator<string> GetEnumerator()
{
return this.GetIterator();
}

#endregion

#region IEnumerable メンバ

IEnumerator IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}

#endregion

#region IEventCollection<string> メンバ

public void EndIterationAsync()
{
try
{
Monitor.Enter(this.syncObject);
this.EndIterationPending = true;
Monitor.PulseAll(this.syncObject);
}
finally
{
Monitor.Exit(this.syncObject);
}
}

public bool EndIterationPending { get; set; }

#endregion
}

MapReduce を C# で 02

修正。そういえば、 IParallelEventCollection 実装が結構酷かも。バランスが難しい・・・。

/// <summary>
/// 次の値が取得可能であれば取得するための列挙子。
/// </summary>
/// <remarks>IEnumerator は生成後のソース変更を許可しないため、このようなインターフェースを用意。</remarks>
/// <typeparam name="T"></typeparam>
public interface ParallelIterator<T>
: IEnumerator<T>, IDisposable, IEnumerator
{
bool TryNext(out T result);
new void Reset();
}

public interface ParallelIterable<T>
: IEnumerable<T>, IEnumerable
{
ParallelIterator<T> GetIterator();
}

public interface IParallelCollection<T>
: ParallelIterable<T>, IEnumerable<T>, IEnumerable
{
int Count { get; }
bool IsReadOnly { get; }
void Add(T item);
void Clear();
bool Contains(T item);
void CopyTo(T[] array, int arrayIndex);
bool Remove(T item);
}

public interface IParallelList<T>
: IParallelCollection<T>, ParallelIterable<T>, IEnumerable<T>, IEnumerable
{
T this[int index] { get; set; }
int IndexOf(T item);
void Insert(int index, T item);
void RemoveAt(int index);
}

public interface IParallelDictionary<TKey, TValue>
: IParallelCollection<KeyValuePair<TKey, TValue>>, ParallelIterable<KeyValuePair<TKey, TValue>>,
IEnumerable<KeyValuePair<TKey, TValue>>, IEnumerable
{
IParallelCollection<TKey> Keys { get; }
IParallelCollection<TValue> Values { get; }
TValue this[TKey key] { get; set; }
void Add(TKey key, TValue value);
bool ContainsKey(TKey key);
bool Remove(TKey key);
bool TryGetValue(TKey key, out TValue value);
}

/// <summary>
/// 列挙終了を外部から通知可能なコレクションのインターフェース。
/// </summary>
/// <remarks>
/// </remarks>
/// <typeparam name="T"></typeparam>
public interface IParallelEventCollection<T>
: IParallelCollection<T>, ParallelIterable<T>, IEnumerable<T>, IEnumerable
{
void EndIterationAsync();
bool EndIterationPending { get; set; }
}

public interface IMapper<TInKey, TInValue, TOutKey, TIntermediateValue>
{
ParallelIterable<KeyValuePair<TOutKey, TIntermediateValue>> Map(TInKey inkey, TInValue inValue);
}

public interface IReducer<TOutKey, TIntermediateValue, TOutValue>
{
ParallelIterable<TOutValue> Reduce(TOutKey outKey, ParallelIterable<TIntermediateValue> intermediateValues);
}


public sealed class MapReduceManager<TInKey, TInValue, TOutKey, TIntermediateValue, TOutValue>
{
/// <summary>
/// 途中値を入れるストレージを生成する処理を取得・設定する。
/// </summary>
public Func<IParallelEventCollection<TIntermediateValue>> NewIntermediateValueStorage { get; set; }

/// <summary>
/// ストレージへの参照を管理するリポジトリを取得・設定する。
/// </summary>
/// <remarks>
/// 実際のストレージは IEventCollection&lt;TIntermediateValue&gt; が管理するため、
/// 特にメモリ上に展開しても問題ないと思われる。ストレージへの参照をポインタで持つか、ファイルパスで持つか、
/// はたまた URL で持つかは実装による。
/// </remarks>
public IParallelDictionary<TOutKey, IParallelEventCollection<TIntermediateValue>> Repository { get; set; }

/// <summary>
/// Map 処理を実装したオブジェクトを取得・設定する。
/// </summary>
public IMapper<TInKey, TInValue, TOutKey, TIntermediateValue> Mapper { get; set; }

/// <summary>
/// Reduce 処理を実装したオブジェクトを取得・設定する。
/// </summary>
public IReducer<TOutKey, TIntermediateValue, TOutValue> Reducer { get; set; }

/// <summary>
/// 非同期処理を取得・設定する。
/// </summary>
public Action<Action> AsyncInvoke { get; set; }

/// <summary>
/// 出力値を入れるストレージを生成する。
/// </summary>
public Func<IParallelEventCollection<TOutValue>> NewOutValueStorage { get; set; }


/// <summary>
/// 処理の実行。
/// </summary>
/// <param name="inKey">Map 処理に渡す In-Key。</param>
/// <param name="inValue">Map 処理に渡す In-Value 。</param>
/// <returns>Reduce 処理の出力結果をまとめたもの。</returns>
public IEnumerable<TOutValue> DoProcess(TInKey inKey, TInValue inValue)
{
var outValues = this.NewOutValueStorage();

foreach (var intermediate in this.Mapper.Map(inKey, inValue))
{
if (!this.Repository.ContainsKey(intermediate.Key))
{
this.AsyncInvoke(
new Action(
() =>
{
var intermediateValues = this.NewIntermediateValueStorage();
intermediateValues.Add(intermediate.Value);
this.Repository.Add(intermediate.Key, intermediateValues);
}
)
);

this.AsyncInvoke(
new Action(
() =>
{
foreach (var outValue in this.Reducer.Reduce(intermediate.Key,
this.Repository[intermediate.Key]))
{
this.AsyncInvoke(new Action(() => outValues.Add(outValue)));
}
}
)
);
}
else
{
this.AsyncInvoke(new Action(() => this.Repository[intermediate.Key].Add(intermediate.Value)));
}
}

outValues.EndIterationAsync();
foreach (var repositoryValue in this.Repository.Values)
{
repositoryValue.EndIterationAsync();
}

return outValues;
}
}

MapReduce を C# で 01

インターフェースはこんな感じでいいのかな。


/// <summary>
/// 次の値が取得可能であれば取得するための列挙子。
/// </summary>
/// <remarks>IEnumerator は生成後のソース変更を許可しないため、このようなインターフェースを用意。</remarks>
/// <typeparam name="T"></typeparam>
public interface ParallelIterator<T>
: IEnumerator<T>, IDisposable, IEnumerator
{
bool TryNext(out T result);
new void Reset();
}

public interface ParallelIterable<T>
: IEnumerable<T>, IEnumerable
{
ParallelIterator<T> GetIterator();
}

public interface IParallelCollection<T>
: ParallelIterable<T>, IEnumerable<T>, IEnumerable
{
int Count { get; }
bool IsReadOnly { get; }
void Add(T item);
void Clear();
bool Contains(T item);
void CopyTo(T[] array, int arrayIndex);
bool Remove(T item);
}

public interface IParallelList<T>
: IParallelCollection<T>, ParallelIterable<T>, IEnumerable<T>, IEnumerable
{
T this[int index] { get; set; }
int IndexOf(T item);
void Insert(int index, T item);
void RemoveAt(int index);
}

public interface IParallelDictionary<TKey, TValue>
: IParallelCollection<KeyValuePair<TKey, TValue>>, ParallelIterable<KeyValuePair<TKey, TValue>>,
IEnumerable<KeyValuePair<TKey, TValue>>, IEnumerable
{
ICollection<TKey> Keys { get; }
ICollection<TValue> Values { get; }
TValue this[TKey key] { get; set; }
void Add(TKey key, TValue value);
bool ContainsKey(TKey key);
bool Remove(TKey key);
bool TryGetValue(TKey key, out TValue value);
}

/// <summary>
/// 列挙終了を外部から通知可能なコレクションのインターフェース。
/// </summary>
/// <remarks>
/// </remarks>
/// <typeparam name="T"></typeparam>
public interface IParallelEventCollection<T>
: IParallelCollection<T>, ParallelIterable<T>, IEnumerable<T>, IEnumerable
{
void EndIterationAsync();
bool EndPending { get; set; }
}

public interface IMapper<TInKey, TInValue, TOutKey, TIntermediateValue>
{
ParallelIterable<KeyValuePair<TOutKey, TIntermediateValue>> Map(TInKey inkey, TInValue inValue);
}

public interface IReducer<TOutKey, TIntermediateValue, TOutValue>
{
ParallelIterable<TOutValue> Reduce(TOutKey outKey, ParallelIterable<TIntermediateValue> intermediateValues);
}


public sealed class MapReduceManager<TInKey, TInValue, TOutKey, TIntermediateValue, TOutValue>
{
/// <summary>
/// 途中値を入れるストレージを生成する処理を取得・設定する。
/// </summary>
public Func<IParallelEventCollection<TIntermediateValue>> NewIntermediateValueStorage { get; set; }

/// <summary>
/// ストレージへの参照を管理するリポジトリを取得・設定する。
/// </summary>
/// <remarks>
/// 実際のストレージは IEventCollection&lt;TIntermediateValue&gt; が管理するため、
/// 特にメモリ上に展開しても問題ないと思われる。ストレージへの参照をポインタで持つか、ファイルパスで持つか、
/// はたまた URL で持つかは実装による。
/// </remarks>
public IParallelDictionary<TOutKey, IParallelEventCollection<TIntermediateValue>> Repository { get; set; }

/// <summary>
/// Map 処理を実装したオブジェクトを取得・設定する。
/// </summary>
public IMapper<TInKey, TInValue, TOutKey, TIntermediateValue> Mapper { get; set; }

/// <summary>
/// Reduce 処理を実装したオブジェクトを取得・設定する。
/// </summary>
public IReducer<TOutKey, TIntermediateValue, TOutValue> Reducer { get; set; }

/// <summary>
/// 非同期処理を取得・設定する。
/// </summary>
public Action<Action> AsyncInvoke { get; set; }

/// <summary>
/// 出力値を入れるストレージを生成する。
/// </summary>
public Func<IParallelEventCollection<TOutValue>> NewOutValueStorage { get; set; }


/// <summary>
/// 処理の実行。
/// </summary>
/// <param name="inKey">Map 処理に渡す In-Key。</param>
/// <param name="inValue">Map 処理に渡す In-Value 。</param>
/// <returns>Reduce 処理の出力結果をまとめたもの。</returns>
public IEnumerable<TOutValue> DoProcess(TInKey inKey, TInValue inValue)
{
var outValues = this.NewOutValueStorage();
foreach (var intermediate in this.Mapper.Map(inKey, inValue))
{
if (!this.Repository.ContainsKey(intermediate.Key))
{
this.AsyncInvoke(
new Action(
() =>
{
var intermediateValues = this.NewIntermediateValueStorage();
intermediateValues.Add(intermediate.Value);
this.Repository.Add(intermediate.Key, intermediateValues);
}
)
);
}
else
{
this.AsyncInvoke(
new Action(
() =>
{
foreach (var outValue in this.Reducer.Reduce(intermediate.Key,
this.Repository[intermediate.Key]))
{
this.AsyncInvoke(new Action(() => outValues.Add(outValue)));
}
}
)
);
}
}

return outValues;
}
}

2009年9月13日日曜日

BCELでHello, World!!

Hello, World。すぐ自動生成コードのための自動生成コードが欲しくなると思う。.NETもそうだったし。

public class HelloWorld {

public static void main(String[] args) {
System.out.println("Hello, World!!");
}

}



生成用コード。

import org.apache.bcel.Constants;
import org.apache.bcel.generic.ArrayType;
import org.apache.bcel.generic.ClassGen;
import org.apache.bcel.generic.ConstantPoolGen;
import org.apache.bcel.generic.InstructionConstants;
import org.apache.bcel.generic.InstructionFactory;
import org.apache.bcel.generic.InstructionList;
import org.apache.bcel.generic.MethodGen;
import org.apache.bcel.generic.ObjectType;
import org.apache.bcel.generic.PUSH;
import org.apache.bcel.generic.Type;


public class Main {

public static void main(String[] args) throws Exception {

ClassGen helloWorldClassGen =
new ClassGen(
"HelloWorld",
"java.lang.Object",
"<generated>",
Constants.ACC_PUBLIC | Constants.ACC_SUPER,
null
);

ConstantPoolGen helloWorldClassConstantPoolGen =
helloWorldClassGen.getConstantPool();
InstructionList instructionList = new InstructionList();

MethodGen mainMethodGen =
new MethodGen(
Constants.ACC_STATIC | Constants.ACC_PUBLIC,
Type.VOID,
new Type[] { new ArrayType(Type.STRING, 1) },
new String[] { "args" },
"main",
"HelloWorld",
instructionList,
helloWorldClassConstantPoolGen
);
InstructionFactory instructionFactory =
new InstructionFactory(helloWorldClassGen);

ObjectType printStreamObjectType = new ObjectType("java.io.PrintStream");
instructionList.append(
instructionFactory.createFieldAccess(
"java.lang.System",
"out",
printStreamObjectType,
Constants.GETSTATIC
)
);
instructionList.append(new PUSH(helloWorldClassConstantPoolGen, "Hello, World!!"));
instructionList.append(
instructionFactory.createInvoke(
"java.io.PrintStream",
"println",
Type.VOID,
new Type[] { Type.STRING },
Constants.INVOKEVIRTUAL
)
);
instructionList.append(InstructionConstants.RETURN);

mainMethodGen.setMaxStack();
helloWorldClassGen.addMethod(mainMethodGen.getMethod());
instructionList.dispose();
helloWorldClassGen.addEmptyConstructor(Constants.ACC_PUBLIC);

helloWorldClassGen.getJavaClass().dump("HelloWorld.class");

}

}

2009年9月10日木曜日

JavaでLINQ02

変数はfinalにすればメンバに持たせる必要はないらしい。Adaptorクラスを分割。

public class Main {

public static void main(String[] args) throws InterruptedException {

Enumerable<String> query =
new Enumerable<Integer>(
iterate(
0,
new Func1<Integer, Integer>(){
public Integer _(Integer arg0) {
return arg0 + 1;
}
}
)
)
.take(10)
.select(
new Func1<Integer, String>() {
public String _(Integer arg0) {
return "Hello, World!!" + (arg0 * 2);
}
}
);


for (String s : query) {
System.out.println(s);
Thread.sleep(1000);
}
}

private static <T> Iterable<T> iterate(final T initialValue, final Func1<T, T> func) {

final class IteratorImpl extends IteratorAdaptor<T> {

private T next = initialValue;

@Override
public boolean hasNext() {
return true;
}

@Override
public T next() {
T next = this.next;
this.next = func._(next);
return next;
}

}

return new IteratorImpl().asIterable();
}

}

class IteratorAdaptor<T> implements Iterator<T> {

@Override
public boolean hasNext() {
return false;
}

@Override
public T next() {
return null;
}

@Override
public void remove() {
}

public Iterable<T> asIterable() {
final IteratorAdaptor<T> _this = this;
return new Iterable<T>() {
@Override
public Iterator<T> iterator() {
return _this;
}
};
}

}

interface Func0<TResult> {
TResult _();
}

interface Func1<T, TResult> {
TResult _(T arg0);
}

class Enumerable<T> implements Iterable<T> {

private Iterable<T> itr;

public Enumerable(Iterable<T> itr) {
this.itr = itr;
}

public <TResult> Enumerable<TResult> select(final Func1<T, TResult> func) {

final Enumerable<T> _this = this;

final class IteratorImpl extends IteratorAdaptor<TResult> {

private Iterator<T> itr = _this.itr.iterator();

@Override
public boolean hasNext() {
return itr.hasNext();
}

@Override
public TResult next() {
return func._(itr.next());
}

}

return new Enumerable<TResult>(new IteratorImpl().asIterable());
}

public Enumerable<T> take(final int count) {

final Enumerable<T> _this = this;

final class IteratorImpl extends IteratorAdaptor<T> {

private int index;
private Iterator<T> itr = _this.itr.iterator();

@Override
public boolean hasNext() {
return index++ < count ? itr.hasNext() : false;
}

@Override
public T next() {
return itr.next();
}

}

return new Enumerable<T>(new IteratorImpl().asIterable());
}

@Override
public Iterator<T> iterator() {
return this.itr.iterator();
}

}

2009年9月9日水曜日

JavaでLINQ01

とりあえず無限級数。

public class Main {

public static void main(String[] args) throws InterruptedException {

for (Integer i : iterate(0, new Func1<Integer, Integer>(){
public Integer _(Integer arg0) {
return arg0 + 1;
}})) {

System.out.println("Hello, World!!" + i);
Thread.sleep(1000);
}

}

private static <T> IEnumerable<T> iterate(T initialValue, Func1<T, T> func) {

final class Result implements IEnumerable<T> {

private T initialValue;
private Func1<T, T> func;

public Result(T initialValue, Func1<T, T> func) {
this.initialValue = initialValue;
this.func = func;
}

@Override
public Iterator<T> iterator() {

final class _Result implements Iterator<T> {

private T next;
private Func1<T, T> func;

public _Result(T initialValue, Func1<T, T> func) {
this.next = initialValue;
this.func = func;
}

@Override
public boolean hasNext() {
return true;
}

@Override
public T next() {
T next = this.next;
this.next = this.func._(next);
return next;
}

@Override
public void remove() {
throw new NotImplementedException();
}

}

return new _Result(this.initialValue, this.func);
}
}

return new Result(initialValue, func);
}

}

interface Func1<T, TResult> {
TResult _(T arg0);
}

interface IEnumerable<T> extends Iterable<T> {
}

2009年9月7日月曜日

デザインゴール01

目印

public @interface ByteCodeInject {

}



継続オブジェクト

public class Continuation {

@ByteCodeInject
public Continuation() {
// TODO:
}

@ByteCodeInject
public void Call() {
// TODO:
}

public void Save(String key, Object o) {
// TODO:
}

public Object Load(String key) {
// TODO:
return null;
}
}



注入前

public class ContinuationTestBefore extends HttpServlet {

@Override
protected void service(HttpServletRequest arg0, HttpServletResponse arg1)
throws ServletException, IOException {

Continuation c = null;
// 実際は DataStore とかにシリアライズ予定。
// DataStore からデシリアライズ。 継続オブジェクトが取れるようなら、継続。
if (c != null) {
c.Call();
}

int x;
int y;

if (Math.random() < 0.5) {
x = 50;
y = 50;
}
else {
x = 100;
y = 100;
}

c = new Continuation();

for (int i = 0; i < 100; i++) {

x += i;
y -= i;

if (i % 5 == 4) {
c = new Continuation();
}
}
}
}



注入後

public class ContinuationTestAfter extends HttpServlet {

@Override
protected void service(HttpServletRequest arg0, HttpServletResponse arg1)
throws ServletException, IOException {

Continuation c = null;
// 実際は DataStore とかにシリアライズ予定
// DataStore からデシリアライズ。 継続オブジェクトが取れるようなら、継続。
if (c != null) {
c.Call();
goto LABEL1;
}

int x;
int y;

if (Math.random() < 0.5) {
x = 50;
y = 50;
}
else {
x = 100;
y = 100;
}

c = new Continuation();
final class _165D8F20 implements Serializable {
private int x;
private int y;
public int getX() {
return x;
}
public void setX(int x) {
this.x = x;
}
public int getY() {
return y;
}
public void setY(int y) {
this.y = y;
}
}
_165D8F20 _165D8F20_s = new _165D8F20();
c.Save("_165D8F20", _165D8F20_s);
if (false) {
LABEL1: {
_165D8F20 _165D8F20_l = (_165D8F20)c.Load("_165D8F20");
x = _165D8F20_l.getX();
y = _165D8F20_l.getY();
}
}

for (int i = 0; i < 100; i++) {

x += i;
y -= i;

if (i % 5 == 4) {
c = new Continuation();
final class _165D8F21 implements Serializable {
private int x;
private int y;
private int i;
public int getX() {
return x;
}
public void setX(int x) {
this.x = x;
}
public int getY() {
return y;
}
public void setY(int y) {
this.y = y;
}
public int getI() {
return i;
}
public void setI(int i) {
this.i = i;
}
}
_165D8F21 _165D8F21_s = new _165D8F21();
c.Save("_165D8F21", _165D8F21_s);
LABEL2: {
_165D8F21 _165D8F21_l = (_165D8F21)c.Load("_165D8F21");
x = _165D8F21_l.getX();
y = _165D8F21_l.getY();
i = _165D8F21_l.getI();
}
}
}
}
}

2009年9月6日日曜日

テスト

テスト


private class Continuation {

public Continuation() {

}

public void Call() {

}

public void Save(String key, Object o) {

}

public Object Load(String key) {
return null;
}
}