Ada 202x (10日目) - reduction expression
========================================

.. post:: Dec 10, 2019
   :tags: ada, ada_2022

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

経緯
----

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

Ada 202xでの改善
----------------

'Reduce
+++++++

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

.. code-block:: ada

 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式は

.. code-block:: ada

 function Contains (C : Integer_Array; Item : Integer) return Boolean is
   (for some E of C => E = Item);

.. code-block:: ada

 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のときの議論はなんだったのでしょうね……。

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

.. container:: strike

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

.. code-block:: ada

 declare
    package Integer_Sets is new Ada.Containers.Ordered_Sets (Integer);
    S : Integer_Sets.Set :=
      Data'Reduce (Integer_Sets.Insert, Integer_Sets.Empty);

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

.. container:: strike

 .. code-block:: ada
 
  declare
     V : Integer_Vectors.Vector := [for E of Data => E];

.. code-block:: ada

 declare
    S : Integer_Sets.Set := [for E of Data => E];

.. container:: inserted

 ``Append_One`` の追加が中止になりました。
 ``Vectors.Append`` はデフォルト付きの第3引数 ``Length`` があるため ``'Reduce`` で使えるかはちょっと確信が持てません。
 そのため例を ``Ordered_Sets.Insert`` に差し替えました。

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

.. code-block:: ada

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

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

.. container:: strike

 閑話休題。
 ``'Reduce`` 属性にはオプションの第3引数として結果の値同士を合成するサブプログラムを渡すこともできます。
 
 .. code-block:: ada
 
  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`` を使って並列化を指示できます。
詳しくは後日。

.. container:: strike

 第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`` 属性の対象となるコンテナは一度変数に入れなくてもインラインで書いて良いことになっています。

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

.. code-block:: ada

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

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

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

.. code-block:: ada

 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
------

- `AI12-0242-1`_ **Shorthand Reduction Expressions for Objects**
- `AI12-0262-1`_ **Map-Reduce attribute**

所感
----

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

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

.. _`AI12-0242-1`: http://www.ada-auth.org/cgi-bin/cvsweb.cgi/ai12s/ai12-0242-1.txt
.. _`AI12-0262-1`: http://www.ada-auth.org/cgi-bin/cvsweb.cgi/ai12s/ai12-0262-1.txt