Sleep sort in Nemerle - 捨てられたブログ

非同期の例題として sleep sort は実によろしい。などという妄想の下に sleep sort を Nemerle で実装してみましょう。

Concurrency

Nemerle には Concurrency マクロなるマクロがあります^[A]。

SleepSort.nusing Nemerle.Assertions;
using Nemerle.Concurrency;
 
using System.Threading.Thread;
 
public class SleepSort
{
   private weight : int;
    
   public this(weight : int)
      requires weight > 0
   {
      this.weight = weight;
   }
    
   [ChordMember]
   public Put(value : int) : void
      requires value >= 0;
 
   public Get() : int
   chord
   {
      | Put => {
         Sleep(value * this.weight);
         value;
      }
   }
}

SleepSort.n
01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28	`using` `Nemerle.Assertions;` `using` `Nemerle.Concurrency;` `using` `System.Threading.Thread;` `public` `class` `SleepSort` `{` `private` `weight :` `int;` `public` `this(weight :` `int)` `requires weight > 0` `{` `this.weight = weight;` `}` `[ChordMember]` `public` `Put(value :` `int) :` `void` `requires value >= 0;` `public` `Get() :` `int` `chord` `{` `\| Put => {` `Sleep(value *` `this.weight);` `value;` `}` `}` `}`

ChordMember なメソッド (Put) は状態を表します， Get メソッドは状態依存で呼び出され， Put 状態の時に Put の引数 (value) × weight ミリ秒待ってからその値を返します。パターンマッチのような書き方ができるのが面白いですね。

Put を呼び出さずに Get を同期呼び出しすると， Put を待つためにスレッドをロックするのでにっちもさっちもいかなくなります。使い方が難しいので，あまり public にしない方が良いかもしれません。

これを使ってソートします。

Main.nusing System;
using Nemerle.Collections;
using Nemerle.Concurrency;
 
def data = {
   def r = Random();
   $[1..10].Map(_ => r.Next(10, 30));
};
Console.WriteLine($"Sort $data");
 
def s = SleepSort(50);
repeat (data.Length)
{
   async
   {
      s.Get() |> Console.WriteLine;
   }
}
data.Iter(s.Put);

Main.n
01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19	`using` `System;` `using` `Nemerle.Collections;` `using` `Nemerle.Concurrency;` `def` `data = {` `def` `r = Random();` `$[1..10].Map(_` `=> r.Next(10, 30));` `};` `Console.WriteLine($"Sort $data");` `def` `s = SleepSort(50);` `repeat` `(data.Length)` `{` `async` `{` `s.Get() \|> Console.WriteLine;` `}` `}` `data.Iter(s.Put);`

Put が呼び出されたら Get がロックを解放して Sleep 後に値を返します。 Sleep の時間は Put で与えた値が小さい程短いので，値が小さい順に返ってくる，つまりソートされた状態で値が返ってくるというわけですね。

値をコンソールに出力しているだけなので厳密にソートと呼べるかは疑問ですが，もしソートした結果をちゃんとキープしたい場合は F# でやったみたいに ConcurrentQueue に値を突っ込んでいけば良いでしょう。今回は concurrency マクロを使いたかっただけなので省略します。次の Async 節ではきちんと ConcurrentQueue を使ってソートしています。

Async

もう 1 つの解法です。 F# でやった方法と同じですが，少し注意する点があります。

Main.nusing System;
using System.Collections.Concurrent;
using Nemerle.Collections;
using Nemerle.ComputationExpressions;
using Nemerle.ComputationExpressions.Async;
 
using System.Threading.Thread;
 
def data = {
   def r = Random();
   $[1..10].Map(_ => r.Next(10, 30));
}
Console.WriteLine($"Sort $data");
       
def queue = ConcurrentQueue();
def sleepWeight = 50;
def enqueue(value)
{
   Sleep(value * sleepWeight);
   queue.Enqueue(value);
   FakeVoid.Value;
}
data.AsyncMap(enqueue).WaitAll();
queue.Iter(Console.WriteLine);

Main.n
01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24	`using System;` `using System.Collections.Concurrent;` `using Nemerle.Collections;` `using Nemerle.ComputationExpressions;` `using Nemerle.ComputationExpressions.Async;` `using System.Threading.Thread;` `def data = {` `def r = Random();` `$[1..10].Map(_ => r.Next(10, 30));` `}` `Console.WriteLine($"Sort $data");` `def queue = ConcurrentQueue();` `def sleepWeight = 50;` `def enqueue(value)` `{` `Sleep(value * sleepWeight);` `queue.Enqueue(value);` `FakeVoid.Value;` `}` `data.AsyncMap(enqueue).WaitAll();` `queue.Iter(Console.WriteLine);`

20 行目の FakeVoid.Value は FakeVoid 型のシングルトンインスタンスです。これを返しておかないと enqueue が void を返す値となってしまい AsyncMap が使えません^[B]。その AsyncMap を使うことで非同期にリストの値を Sleep してからキューに突っ込んでいきます。

これでうまくいくように見えるのですが，実はうまくいきません。というのは AsyncMap は， ExecutionContext 引数を与えない場合では ThreadPool.QueueUserWorkItem を利用しているからです。スレッドプールは同時実行数が調節されているので，リストの要素すべてに対して enqueue が同時に実行されるとは限りません。そのため同時実行スレッド数が管理されないように，自身でスレッドを立ち上げて実行してやるような ExecutionContext を用意する必要があります。なお ExecutionContext クラスは System.Threading 名前空間にもありますが，ここでは Nemerle.ComputationExpressions.Async 名前空間のクラスです。

GreedyExecutionContext.nusing Nemerle.DesignPatterns;
using Nemerle.ComputationExpressions.Async;
 
[Singleton(Public)]
public class GreedyExecutionContext : ExecutionContext
{
   private this()
   {
   }
    
   public override Execute(computation : void -> void) : void
   {
      System.Threading.Thread(computation).Start();
   }
}

GreedyExecutionContext.n
01 02 03 04 05 06 07 08 09 10 11 12 13 14 15	`using` `Nemerle.DesignPatterns;` `using` `Nemerle.ComputationExpressions.Async;` `[Singleton(Public)]` `public` `class` `GreedyExecutionContext : ExecutionContext` `{` `private` `this()` `{` `}` `public` `override` `Execute(computation :` `void` `->` `void) :` `void` `{` `System.Threading.Thread(computation).Start();` `}` `}`

Execute メソッドをオーバーライドして，計算要求がきたら別スレッドで計算を行うようにします。なんとなくデザインパターンマクロを使ってみました。

これを用いて先ほどのコードを次のように修正します。

Main.n
22	`data.AsyncMap(enqueue, GreedyExecutionContext.Instance).WaitAll();`

これで期待通りに動作するようになるはずです。

Async コンピューテーション式もあるのですが，今回は出番がありませんでした。 async キーワードがかぶっているので concurrency マクロと一緒に使うことができません。残念です。

ソースコード

GitHub にアップロードしています。

脚注

このマクロは昔 Polyphonic C# という言語があって，そのモデルを Nemerle に取り入れたものだそうです。 [↩]
実際のところ enqueue が返す値は FakeVoid である必要はありません。ですが enqueue が本来 void を返すということを示す意味で FakeVoid.Value を返すのは良いことだと思います。 [↩]