Ada 202x (12日目) - procedural iterator
=======================================

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

今回、構文糖ですので簡単だぜと思ってましたら分量的には今までで最長に……何故だ。

経緯
----

``Ada.Containers`` 以下のコンテナには要素を列挙する方法が2つあります。
一般に内部イテレータと外部イテレータと言われます。

内部イテレータはコールバック関数を使ったものです。
通常、ループはライブラリの中で行われます。

.. code-block:: ada

 declare
    package String_Lists is
      new Ada.Containers.Indefinite_Doubly_Linked_Lists (String);
    L : String_Lists.List := ...; -- 適当に値を詰める
    procedure Process (Position : in String_Lists.Cursor) is
    begin
       Ada.Text_IO.Put (String_Lists.Element (Position));
       Ada.Text_IO.New_Line;
    end Process;
 begin
    String_Lists.Iterate (L, Process'Access);

外部イテレータは列挙状態を持つオブジェクト(インデックス値、 ``Cursor`` 、ポインター等、コンテナオブジェクト自体が列挙のための状態を持つ場合もある)を使ったものです。
通常、ループはライブラリの外で行います。

.. code-block:: ada

 declare
    Position : Cursor := String_Lists.First (L);
 begin
    while String_Lists.Has_Element (Position) loop
       Ada.Text_IO.Put (String_Lists.Element (Position));
       Ada.Text_IO.New_Line;
       String_Lists.Next (Position);
    end loop;

この例ですとコンテナ全体の列挙です。
加えてAda 2012では ``Ada.Iterator_Interfaces`` に範囲を限定することもできる ``interface`` が整備されました。

.. code-block:: ada

 declare
    Ite : String_Lists.List_Iterator_Interfaces.Reversible_Iterator'Class :=
      String_Lists.Iterate (M);
    Position : Cursor := String_Lists.List_Iterator_Interfaces.First (Ite, L);
 begin
    while String_Lists.Has_Element (Position) loop
       Ada.Text_IO.Put (String_Lists.Element (Position));
       Ada.Text_IO.New_Line;
       Position := String_Lists.List_Iterator_Interfaces.Next (Ite, Position);
    end loop;

複数言語使いの方にはややこしいですが、AdaのIteratorはC++等でいうrangeでありC#等の(I)Enumeratorです。
C++等のiteratorに相当するものはAdaではCursorです。
この文章ではそれとはまた別に「内部イテレータ」「外部イテレータ」も使ってますから余計ややこしいですねスミマセン。

C++にrange-based for文が、C#にforeach文がありますように、AdaでもIteratorを使ったループはfor文で短く書けます。

.. code-block:: ada

 begin
    for Position in String_Lists.Iterate (M) loop
       Ada.Text_IO.Put (String_Lists.Element (Position));
       Ada.Text_IO.New_Line;
    end loop;

値のみが必要で位置情報はいらない場合は ``of`` 形式が使えます。

.. code-block:: ada

 begin
    for E of M loop
       Ada.Text_IO.Put (E);
       Ada.Text_IO.New_Line;
    end loop;

まあ、このへんは今更説明しなくても普通に使ってきましたよね。
おさらいということで。

使う側としてみれば外部イテレータのほうが便利です。
例えば2つのCursorを同時に進めていくようなループは内部イテレータでは書けません。

一方で実装するのは内部イテレータのほうが遥かに楽です。

外部イテレータには構文糖が用意されていますが、内部イテレータには何もありませんでした。

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

内部イテレータもfor文で書けるようになりました。

.. code-block:: ada

 begin
    for (Position : in String_Lists.Cursor) of String_Lists.Iterate (M) loop
       Ada.Text_IO.Put (String_Lists.Element (Position));
       Ada.Text_IO.New_Line;
    end loop;

インデックスの部分にサブプログラム宣言の引数リストを書きます。
その引数リストとループ本体が匿名の手続きとして ``of`` 以降の呼び出しに渡されます。

オーバーロードされていて字面が同じ ``String_Lists.Iterate (M)`` ですから分かり辛いですが、イテレータの例ではイテレータを返す関数、この例ではクロージャを受け取る手続きの呼び出しです。

| http://www.ada-auth.org/standards/2xrm/html/RM-A-18-3.html#p45
| http://www.ada-auth.org/standards/2xrm/html/RM-A-18-3.html#p46.1

引数リストの型は省略できます。

.. code-block:: ada

 begin
    for (Position) of String_Lists.Iterate (M) loop
       Ada.Text_IO.Put (String_Lists.Element (Position));
       Ada.Text_IO.New_Line;
    end loop;

最後の引数以外にループ本体を渡したい場合は ``<>`` を使います。

.. code-block:: ada

 begin
    for (Position) of String_Lists.Iterate (Container => M, Process => <>) loop
       Ada.Text_IO.Put (String_Lists.Element (Position));
       Ada.Text_IO.New_Line;
    end loop;

このように内部イテレータのときは引数リストで型が書けます。
同様に外部イテレータの方も型が書けるようになっています。

.. code-block:: ada

 begin
    for Position : String_Lists.Cursor in String_Lists.Iterate (M) loop
       Ada.Text_IO.Put (String_Lists.Element (Position));
       Ada.Text_IO.New_Line;
    end loop;

.. code-block:: ada

 begin
    for E : String of M loop
       Ada.Text_IO.Put (E);
       Ada.Text_IO.New_Line;
    end loop;

コンテナのときはあまり役に立ちそうにないですが、地味に普通の整数値をループするときに嬉しかったりします。

.. code-block:: ada

 begin
    for I in 1 .. 10 loop

この ``I`` の型は ``in`` 以降に指定された範囲を見ても特定できません。
こんな場合はフォールバックとして ``Integer`` 型が使われます。

ですので他の整数型を使いたい場合はひとひねり必要でした。

.. code-block:: ada

 begin
    for I in Short_Integer'(1) .. 10 loop

.. code-block:: ada

 begin
    for I in Short_Integer range 1 .. 10 loop

直接型を指定できるようになったことでこう書けます。

.. code-block:: ada

 begin
    for I : Short_Integer in 1 .. 10 loop

あんまり変わらない？
あ、はい、そうですね。

自前のコンテナに実装する方法
----------------------------

構文糖ですのでこれまで通り内部イテレータを書けばいいだけです。

.. code-block:: ada

 declare
    procedure Countdown
      (N : in Natural;
       P : not null access procedure (I : in Positive)) is
    begin
       for I in reverse 1 .. N loop
          P (I);
       end loop;
    end Countdown;
 begin
    for (I : in Positive) of Countdown (10) loop
       Ada.Integer_Text_IO.Put (I);
    end loop;

ただしこのままではループ中で ``exit`` することはできません。

Allows_Exitアスペクト
+++++++++++++++++++++

``Allows_Exit`` アスペクトを指定することで ``exit`` できるようになります。

.. code-block:: ada

 declare
    procedure Countdown
      (N : in Natural;
       P : not null access procedure (I : in Positive))
       with Allows_Exit is
    begin
       for I in reverse 1 .. N loop
          P (I);
       end loop;
    end Countdown;
 begin
    for (I : in Positive) of Countdown (10) loop
       exit when I = 5;
       Ada.Integer_Text_IO.Put (I);
    end loop;

実際は ``Countdown`` と匿名の手続きの2つのサブプログラムがネストされて呼び出されているわけですので ``exit`` の動作は例外を用いて再現されています。
``Allows_Exit`` は例外のための追加のコードを生成しますので ``exit`` 不要であれば付けないほうが生成されるコードサイズが減ります。

Parallel_Iteratorアスペクト
+++++++++++++++++++++++++++

``parallel for`` に対応させるためには ``Parallel_Iterator`` アスペクトを指定します。

.. code-block:: ada

 declare
    procedure Parallel_Countdown
      (N : in Natural;
       P : not null access procedure (I : in Positive))
       with Parallel_Iterator is
    begin
       parallel for I in reverse 1 .. N loop
          P (I);
       end loop;
    end Countdown;
    protected Locked is
       procedure Put (I : in Integer);
    end Locked;
    protected body Locked is
       procedure Put (I : in Integer) is
       begin
          Ada.Integer_Text_IO.Put (I);
       end Put;
    end Locked;
 begin
    parallel for (I : in Positive) of Parallel_Countdown (10) loop
       Locked.Put (I);
    end loop;

これは並列化しておきながら同期させているダメな例です。
最初に出力にしてしまったのが失敗でした。

``Parallel_Iterator`` と ``parallel for`` は一致させる必要があります。
また ``Parallel_Iterator`` と ``Allows_Exit`` は同時に指定できません。
(``parallel for`` からは ``exit`` できません。)

関連AI
------

- `AI12-0156-1`_ **Use subtype_indication in generalized iterators**
- `AI12-0189-1`_ **loop-body as anonymous procedure**
- `AI12-0326-2`_ **Bounded errors associated with procedural iterators**

ボツ案の紹介
------------

- `AI12-0009-1`_ **Iterators for Directories and Environment_Variables**

これまで内部イテレータしか提供されてこなかったライブラリに外部イテレータを追加する提案。
内部イテレータにも構文糖ができたことでこれらのライブラリも ``for`` で使えるようになりましたので見送られています。
番号が若いことからわかりますように一連の議論の発端ですたぶんきっとおそらく。

- `AI12-0197-1`_ **Generator Functions**

C#やPythonですと内部イテレータっぽく書いて外部イテレータとして使うことができます。
一般にネイティブコンパイルされる処理系でこの変換をスレッド等を使わず軽量に実装しようとするのは難しいです。
VMで実行されるものはどうにでもなるとしましてC#は状態遷移機にコンパイルされているっぽいですね。
同じことをAdaでもしようという提案。

- `AI12-0197-2`_ **Passive tasks**

そもそもAdaの ``task`` はスレッドとして実現される必要はなく状態遷移機として実装されることも視野に入れたものでした。
それを掘り下げてジェネレーターっぽく使ってしまおうという提案。

- `AI12-0197-3`_ **generator functions**

C#のジェネレーターそのまま持ってくればええやん。(再)

- `AI12-0197-4`_ **Coroutines and channels**

いやいや時代はgoroutineだぜ。

所感
----

今振り返るとGo言語の流行はピークを過ぎた感ありますよね。
諸行無常。
(これからだぜ！って方がいらしたらごめんなさい。)

`私はどうやら外部イテレータが嫌いのようですので <https://twitter.com/niha28/status/3344034336>`_\ (？？？)、内部イテレータの強化は嬉しいです。

.. _`AI12-0156-1`: http://www.ada-auth.org/cgi-bin/cvsweb.cgi/ai12s/ai12-0156-1.txt
.. _`AI12-0189-1`: http://www.ada-auth.org/cgi-bin/cvsweb.cgi/ai12s/ai12-0189-1.txt
.. _`AI12-0326-2`: http://www.ada-auth.org/cgi-bin/cvsweb.cgi/ai12s/ai12-0326-2.txt
.. _`AI12-0009-1`: http://www.ada-auth.org/cgi-bin/cvsweb.cgi/ai12s/ai12-0009-1.txt
.. _`AI12-0197-1`: http://www.ada-auth.org/cgi-bin/cvsweb.cgi/ai12s/ai12-0197-1.txt
.. _`AI12-0197-2`: http://www.ada-auth.org/cgi-bin/cvsweb.cgi/ai12s/ai12-0197-2.txt
.. _`AI12-0197-3`: http://www.ada-auth.org/cgi-bin/cvsweb.cgi/ai12s/ai12-0197-3.txt
.. _`AI12-0197-4`: http://www.ada-auth.org/cgi-bin/cvsweb.cgi/ai12s/ai12-0197-4.txt