Ada 2020 (12日目) - procedural iterator

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

経緯

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

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

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 、ポインター等、コンテナオブジェクト自体が列挙のための状態を持つ場合もある)を使ったものです。 通常、ループはライブラリの外で行います。

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 が整備されました。

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文で短く書けます。

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 形式が使えます。

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

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

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

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

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

Ada 2020での改善

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

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) ですから分かり辛いですが、イテレータの例ではイテレータを返す関数、この例ではクロージャを受け取る手続きの呼び出しです。

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

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

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

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;

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

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;
begin
   for E : String of M loop
      Ada.Text_IO.Put (E);
      Ada.Text_IO.New_Line;
   end loop;

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

begin
   for I in 1 .. 10 loop

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

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

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

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

begin
   for I : Short_Integer in 1 .. 10 loop

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

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

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

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 することはできません。

Allow_Exitアスペクト

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

declare
   procedure Countdown
     (N : in Natural;
      P : not null access procedure (I : in Positive))
      with Allow_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 の動作は例外を用いて再現されています。 Allow_Exit は例外のための追加のコードを生成しますので exit 不要であれば付けないほうが生成されるコードサイズが減ります。

Parallel_Iteratorアスペクト

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

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_Iteratorparallel for は一致させる必要があります。 また Parallel_IteratorAllow_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 で使えるようになりましたので見送られています。 番号が若いことからわかりますように一連の議論の発端ですたぶんきっとおそらく。

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

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

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

いやいや時代はgoroutineだぜ。

所感

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

私はどうやら外部イテレータが嫌いのようですので (???)、内部イテレータの強化は嬉しいです。