Ada 2020 (10日目) - reduction expression

aggregate式シリーズもそろそろ大詰め。

経緯

昨日紹介したquantified式は Boolean 限定のfold式でした。 一般化したいというのは人情です。 (昨日の内容は適当に間に合わせた回に見せかけて伏線を張る高等テクニック。)

Ada 2020での改善

‘Reduce

'Reduce 属性が追加されました。 高階関数として振る舞います。

declare
   type Integer_Array is array (Positive range <>) of Integer;
   Data : constant Integer_Array := (for I in 1 .. 10 => I);
   Total : Integer;
begin
   Total := Data'Reduce ("+", 0); -- 55

この例では Data (1) + Data (2) + ... Data (10) と等しくなります。

配列中に特定の値があるか調べる次のquantified式は

function Contains (C : Integer_Array; Item : Integer) return Boolean is
  (for some E of C => E = Item);
function Contains (C : Integer_Array; Item : Integer) return Boolean is
   function Reducer (A : Boolean; E : Integer) return Boolean is
     (A or else E = Item);
begin
   return Data'Reduce (Reducer, False);
end Contains;

と書くことができます。 ……やっぱりdeclare式による式中での関数内関数の宣言欲しいですよねえ。

'Reduce 属性の第1引数はサブプログラム名そのものです。 そのため最初の例では + ではなく "+" と書いています。

generic の引数風に書けば次のような関数または手続きとなります。

  • with function Reducer (Accumulator : Accum_Type; Value : Value_Type) return Accum_Type;

  • with procedure Reducer (Accumulator : in out Accum_Type; Value : in Value_Type);

このように 'Reduce 属性は異例尽くしとなっています。 delta aggregateのときの議論はなんだったのでしょうね……。

手続きも使えますので既存のサブプログラムを使ってコンテナに値を追加していくこともできます。

declare
   package Integer_Vectors is new Ada.Containers.Vectors (Positive, Integer);
   V : Integer_Vectors.Vector :=
     Data'Reduce (Integer_Vectors.Append_One, Integer_Vectors.Empty);

これはまあ次のように書けば同じですけれどね。

declare
   V : Integer_Vectors.Vector := [for E of Data => E];

悪用の方向で想像を膨らませますとファイルに出力するような真似もできるかもしれません。

New_Line (Data'Reduce (Put, File)); -- あくまでイメージです

実際にはlimited型は使用できないようですのでいい感じのラッパーが必要になると思われます。 (悪用を諦めない。)

閑話休題。 'Reduce 属性にはオプションの第3引数として結果の値同士を合成するサブプログラムを渡すこともできます。

function Contains (C : Integer_Array; Item : Integer) return Boolean is
   function Reducer (A : Boolean; E : Integer) return Boolean is
     (A or else E = Item);
begin
   return Data'Reduce (Reducer, False, "or");
end Contains;

第3引数を指定しない場合は素直に False or else Data (1) = Item or else Data (2) = Item or else ... Data (10) = Item と展開されますが、第3引数がありますと Data を複数ブロックに分けて (False or else Data (1) = Item or else ... Data (5) = Item) or (False or else Data (6) = Item or else ... Data (10) = Item) みたいに並列化されるかもしれません。

明示的に 'Parallel_Reduce を使って並列化を指示できます。 詳しくは後日。

第3引数は generic の引数風に書けば次のような関数または手続きとなります。

  • with function Combiner (Accumulator, Value : Accum_Type) return Accum_Type;

  • with procedure Combiner (Accumulator : in out Accum_Type; Value : in Accum_Type);

また、'Reduce 属性の対象となるコンテナは一度変数に入れなくてもインラインで書いて良いことになっています。

つまり最初の例であればこれでいいです。

declare
   Total : Integer;
begin
   Total := [for I in 1 .. 10 => I]'Reduce ("+", 0); -- 55

このように書きますとメモリ上で配列を組み立てたりせず数列を生成した端から畳み込んでいく最適化も期待できます。 所謂map-reduceを行う式を一行でそれもfor文と同じ効率で書けてしまうことになります。

quantified式からの例もこう書くことはできますが

function Contains (C : Integer_Array; Item : Integer) return Boolean is
  ([for E of C => E = Item]'Reduce ("or", False));

"or" 「関数」は短絡評価できませんので or else に劣ります。 やはり Boolean の場合はquantified式を使うほうがいいです。

関連AI

所感

'Reduce 属性は明示的なインスタンス化をせずに使用できる generic 関数ということになってしまいます。 言語仕様を決める側は自由自在にできてずるい。

generic 一般の暗黙のインスタンス化は提案されはしましたが採用されませんでした。