Ada 的泛型程式設計 ── 以型別撰寫契約,零成本達成程式碼重用

· · Ada, ProgrammingLanguage, Generics, TypeSystem, StaticTyping, ContractModel, ZeroCostAbstraction, GNAT, Alire, 高信賴性, 程式碼重用

1. 前言 ── 不是「什麼都能接受」,而是「約定了什麼」

在靜態型別語言中嘗試撰寫可重用的程式碼時,很快就會遇到相同的困擾。為整數撰寫的堆疊也想用在字串上。為浮點數陣列撰寫的統計處理,也想用在其他型別上。升序排序的邏輯,也想用在降序排序上。然而,若針對每種型別都複製相同的程式碼,就會出現修改遺漏。反過來,若設計成用 void* 或轉型接受任何東西,型別安全性就會崩潰。

Ada 給出的答案是 泛型(generic units)

Ada 的泛型不是單純的文字取代。它可以把型別、值、子程式,甚至套件本身當作形式參數接收,並在實例化(instantiation)時進行靜態型別檢查。也就是說,這不是在執行時檢查「這個型別真的沒問題嗎」,而是在編譯時就確定「這個部件是否滿足這個契約」的機制。

想要重用的處理如何重用複製貼上void* / Object / 轉型Ada 泛型容易出現修改遺漏容易出現執行時錯誤或型別崩潰型別安全編譯時檢查執行時沒有多餘的分派

本文將依下列流程,整理 Ada 的泛型程式設計。

  • 泛型子程式
  • 泛型套件
  • 型別參數、值參數、子程式參數
  • privaterange <>digits <> 等型別類別
  • 排序、堆疊、統計處理、Count_If、鍵值儲存的實作範例
  • 透過正式套件參數實現的高階泛型
  • Ada 的 contract model 與實務設計思路

這個主題延續自本部落格系列文章「Ada 語言的魅力」「SPARK 形式驗證入門」「安全的並行處理」「即時系統」之後。本文將從泛型這個切入點,深入探討 Ada「以型別闡述設計」的思路。

2. 本文的架構

首先用一張圖掌握全貌。如果只把 Ada 的泛型理解成「以型別作為引數的功能」,那就是相當狹隘的看法。實際上,會依照想要重用的單位,組合子程式、套件、子程式參數、值參數、正式套件參數。

Ada GenericsGeneric SubprogramSwapCount_IfSortGeneric PackageStackStatisticsKV StoreFormal ParametersTypeprivatelimited privaterange boxmod boxdigits boxdelta boxdiscrete boxObjectMax_SizeThresholdSubprogramLess functionEquals functionPredicatePackagewith package P is newGenericDesign IdeasContract ModelStatic CheckingZero-Cost AbstractionSeparate Specification andBody

本文的閱讀方式很單純。前半段會追蹤語法,後半段則討論設計判斷。第一次閱讀 Ada 的讀者,一開始不必勉強記住細部語法,而應該關注「把什麼當作形式參數」「這個形式參數允許哪些操作」。

3. 執行環境與編譯方式

本文的程式碼假設使用 GNAT 15.x 以上版本。GNAT 是 Ada 具代表性的編譯器,可以透過 Alire 安裝。Alire 是 Ada / SPARK 的套件管理工具,也可以用於工具鏈管理與建置。

gnat --version
# GNAT 15.2.1

請透過 Alire(Ada 的套件管理工具)執行 alr install gnat_native gprbuild 來安裝 GNAT,並設定好 PATH

本文所使用的範例,假設在儲存庫中依下列方式放置。

ada-generic-programming/src/snippets/01_swap.ada02_stack.ada03_sort.ada04_statistics.ada05_filter.ada06_kv_store.adaREADME.md

把多個編譯單元合併在一個檔案中的範例,要先用 gnatchop 分割,再用 gnatmake 建置。

mkdir work
cd work
gnatchop ../src/snippets/01_swap.ada
gnatmake -gnata swap_demo
./swap_demo

-gnata 是啟用斷言(assertion)的選項。雖然使用泛型本身並不需要它,但在學習用的範例中,開啟它能更容易確認契約與邊界條件。

執行檔gnatmakegnatchop開發者執行檔gnatmakegnatchop開發者傳入一個 .ada 檔案分割成 .ads / .adb / maingnatmake -gnata main執行到繫結與連結為止./main執行結果

4. Ada 泛型的基本模型

Ada 的泛型,大致上用下列 3 個步驟來思考會比較容易理解。

  1. 撰寫泛型單元
  2. generic 部分撰寫形式參數
  3. 在使用端透過 new 進行實例化
generic 宣告形式參數泛型本體透過 new 實例化作為一般的子程式或套件使用型別子程式套件

舉例來說,把交換兩個值的處理寫成泛型時,可以只把型別當作形式參數。

generic
   type Element is private;
procedure Generic_Swap (A, B : in out Element);

在這個階段,Generic_Swap 還無法呼叫。這只是「可用於任意 Element 型別的交換處理範本」。只有給定具體型別之後,它才會成為一般的程序。

procedure Swap_Integer is new Generic_Swap (Integer);

用圖表示,關係如下。

傳入 Integer傳入 Character傳入 My_RecordGeneric_Swaptype Element is privateSwap_IntegerSwap_CharacterSwap_My_Record交換 Integer 變數交換 Character 變數交換 My_Record 變數

重要的是,範本本體只使用能對 Element 使用的操作來撰寫。若宣告為 type Element is private;,可以使用指派、相等比較等基本操作,但無法使用大小比較或算術運算。也就是說,泛型的宣告本身就表達了「這個部件可以假設什麼」。

5. 形式參數的種類 ── Ada 泛型的詞彙

Ada 的泛型能接收的東西不只有型別。這是與 C# 或 Java 常見的泛型相比,差異最大的一點。

generic formal parameters型別參數物件 / 值參數子程式參數套件參數type Element is privatetype Index is boxtype Real is digits boxMax_Size : PositiveDefault_Value : Elementwith function Less...with procedure Put ...with package P is new ...

把具代表性的形式參數整理成表格如下。

種類 範例 意義
型別參數 type Element is private; 接收任意 definite、非 limited 型別的基本形式
limited 型別參數 type Element is limited private; 也能接收無法複製的型別
離散型別 type Index is (<>); 整數型別或列舉型別等,可用於陣列索引的型別
帶符號整數型別 type Count is range <>; 可假設 +-、大小比較等整數運算
模數整數型別 type Word is mod <>; 處理位元運算或模數性質的整數
浮點型別 type Real is digits <>; FloatLong_Float、使用者自訂浮點型別等
定點型別 type Money is delta <>; 處理定點運算
值參數 Max_Size : Positive; 讓大小或閾值等在每個實例中固定下來
子程式 with function Predicate (...) return Boolean; 注入比較函式或述詞等行為
套件 with package P is new Some_Generic (<>); 把已生成的泛型套件當作部件接收

正因為擁有這套詞彙,在 Ada 中可以很自然地寫出「只接收能做這個操作的型別」,而不是「什麼都能接受,但內部做危險的事」。

6. 泛型子程式 ── 透過 Generic_Swap 理解最小結構

首先來看第一個範例:可交換任意型別的兩個變數的 Generic_Swap

6.1 規格部分

generic
   type Element is private;
procedure Generic_Swap (A, B : in out Element);

緊接在 generic 之後的部分就是形式參數。這裡接收的是名為 Element 的型別。is private 表示,從泛型本體的角度來看,並不知道該型別的內部表示方式。

從這個宣告可以知道下列 2 件事。

  • Generic_Swap 可用於任意的 Element 型別
  • 本體不依賴 Element 的內部結構或大小比較

6.2 本體

procedure Generic_Swap (A, B : in out Element) is
   Temp : constant Element := A;
begin
   A := B;
   B := Temp;
end Generic_Swap;

這個本體對 Element 只使用了指派操作。既沒有使用 A < B,也沒有使用 A + B。因此,只要是可以指派的型別,例如 IntegerCharacter、記錄型別、列舉型別等,都能自然地使用。

呼叫後呼叫前A = 20B = 10A = 10B = 20Temp = A

6.3 實例化

使用端要用 new

procedure Swap_Int  is new Generic_Swap (Integer);
procedure Swap_Char is new Generic_Swap (Character);

這樣一來,Swap_IntSwap_Char 就能作為一般的程序被呼叫。

with Ada.Text_IO; use Ada.Text_IO;

procedure Swap_Demo is
   generic
      type Element is private;
   procedure Generic_Swap (A, B : in out Element);

   procedure Generic_Swap (A, B : in out Element) is
      Temp : constant Element := A;
   begin
      A := B;
      B := Temp;
   end Generic_Swap;

   procedure Swap_Int is new Generic_Swap (Integer);

   X : Integer := 10;
   Y : Integer := 20;
begin
   Put_Line ("Before: X=" & Integer'Image (X) & ", Y=" & Integer'Image (Y));
   Swap_Int (X, Y);
   Put_Line ("After : X=" & Integer'Image (X) & ", Y=" & Integer'Image (Y));
end Swap_Demo;

執行結果大致如下。

Before: X= 10, Y= 20
After : X= 20, Y= 10

這裡不能把 Float 變數傳給 Swap_Int (X, Y);。因為 Swap_Int 是為 Integer 實例化的一般程序。把泛型理解成「為每種型別建立安全具體物件的機制」,而不是「什麼都能塞進去的洞」,會比較容易理解。

7. 泛型套件 ── 把型別與值當作參數

若不只是想重用單一個子程式,而是想把多個操作與內部狀態整合起來重用,就使用泛型套件。具代表性的例子就是堆疊。

堆疊只要改變元素型別與最大容量,基本邏輯就是相同的。

Generic_StackElement_TypeMax_SizePush / Pop / Size / Is_Empty / Is_FullInt_StackElement=IntegerMax_Size=5Float_StackElement=FloatMax_Size=3String_StackElement=Unbounded_StringMax_Size=20

7.1 規格部分

generic
   type Element_Type is private;
   Max_Size : Positive;
package Generic_Stack is
   procedure Push (Item : Element_Type);
   function Pop return Element_Type;
   function Is_Empty return Boolean;
   function Is_Full  return Boolean;
   function Size return Natural;

   Stack_Overflow  : exception;
   Stack_Underflow : exception;
end Generic_Stack;

這裡使用了 2 種形式參數。

  • Element_Type 是型別參數
  • Max_Size 是值參數

由於 Max_SizePositive,因此無法用 0 以下的大小來實例化。像這樣,值參數也可以透過型別附加限制。

7.2 本體

package body Generic_Stack is
   subtype Index_Type is Positive range 1 .. Max_Size;
   type Storage_Type is array (Index_Type) of Element_Type;

   Data : Storage_Type;
   Top  : Natural := 0;

   procedure Push (Item : Element_Type) is
   begin
      if Top = Max_Size then
         raise Stack_Overflow;
      end if;

      Top := Top + 1;
      Data (Top) := Item;
   end Push;

   function Pop return Element_Type is
      Result : Element_Type;
   begin
      if Top = 0 then
         raise Stack_Underflow;
      end if;

      Result := Data (Top);
      Top := Top - 1;
      return Result;
   end Pop;

   function Is_Empty return Boolean is
   begin
      return Top = 0;
   end Is_Empty;

   function Is_Full return Boolean is
   begin
      return Top = Max_Size;
   end Is_Full;

   function Size return Natural is
   begin
      return Top;
   end Size;
end Generic_Stack;

這個套件本體中重要的一點是,DataTop 會在每個實例中分別建立。

package Int_Stack   is new Generic_Stack (Integer, 5);
package Float_Stack is new Generic_Stack (Float,   3);

這兩者是從相同範本建立的,但內部狀態並不共用。

Float_Stack 的狀態TopData : Float 陣列Int_Stack 的狀態TopData : Integer 陣列Generic_StackInt_StackFloat_Stack

7.3 堆疊的狀態轉換

把堆疊視為狀態機來看會比較容易理解。

PushPush / Pop以 Pop 取出最後一個元素以 Push 到達 Max_SizePopPushPopEmptyNonEmptyFullOverflowUnderflow

7.4 使用範例

with Ada.Text_IO; use Ada.Text_IO;

procedure Stack_Demo is
   generic
      type Element_Type is private;
      Max_Size : Positive;
   package Generic_Stack is
      procedure Push (Item : Element_Type);
      function Pop return Element_Type;
      function Is_Empty return Boolean;
      function Is_Full  return Boolean;
      function Size return Natural;
      Stack_Overflow  : exception;
      Stack_Underflow : exception;
   end Generic_Stack;

   package body Generic_Stack is
      subtype Index_Type is Positive range 1 .. Max_Size;
      type Storage_Type is array (Index_Type) of Element_Type;

      Data : Storage_Type;
      Top  : Natural := 0;

      procedure Push (Item : Element_Type) is
      begin
         if Top = Max_Size then
            raise Stack_Overflow;
         end if;

         Top := Top + 1;
         Data (Top) := Item;
      end Push;

      function Pop return Element_Type is
         Result : Element_Type;
      begin
         if Top = 0 then
            raise Stack_Underflow;
         end if;

         Result := Data (Top);
         Top := Top - 1;
         return Result;
      end Pop;

      function Is_Empty return Boolean is (Top = 0);
      function Is_Full  return Boolean is (Top = Max_Size);
      function Size     return Natural is (Top);
   end Generic_Stack;

   package Int_Stack is new Generic_Stack (Integer, 5);
begin
   Int_Stack.Push (10);
   Int_Stack.Push (20);
   Int_Stack.Push (30);

   Put_Line ("Size=" & Natural'Image (Int_Stack.Size));
   Put_Line ("Pop =" & Integer'Image (Int_Stack.Pop));
   Put_Line ("Pop =" & Integer'Image (Int_Stack.Pop));
   Put_Line ("Size=" & Natural'Image (Int_Stack.Size));
end Stack_Demo;

泛型套件在實務上,常用於「小型容器」「固定長度緩衝區」「環形緩衝區」「日誌用佇列」「硬體抽象層」等場合。尤其在 Ada 中,比起在執行時動態調整大小,把大小以型別或值參數的形式靜態固定下來的設計,與高信賴系統相性更好。

8. 形式子程式參數 ── 注入行為

即使只接收型別,仍有無法表達的事情。例如在排序中,除了元素型別之外,還需要「哪一個排在前面」這種比較邏輯。

在 Ada 中,可以把這個比較函式當作泛型的形式參數。

Generic_Insertion_SortItem_TypeIndexItem_Array比較函式使用標準比較傳入 Greater 做降序傳入自訂順序

8.1 規格部分

generic
   type Item_Type is private;
   type Index is (<>);
   type Item_Array is array (Index range <>) of Item_Type;
   with function "<" (Left, Right : Item_Type) return Boolean is <>;
procedure Generic_Insertion_Sort (Items : in out Item_Array);

這裡有 4 個形式參數。

  1. Item_Type:陣列元素的型別
  2. Index:陣列索引的型別
  3. Item_Array:實際的陣列型別
  4. "<":比較函式

type Index is (<>); 接收的是離散型別。不只整數型別,也能接收列舉型別。除了以 Positive 作為陣列索引之外,也能使用像 Day 這樣的列舉型別,這是 Ada 的特色所在。

with function "<" ... is <>; 中的 is <>,意思是在省略實際參數時,會使用可見範圍內的標準運算子或相符的函式。也就是說,像 Integer 這種本來就有 < 的型別,不必明確指定比較函式也能使用。

8.2 本體

procedure Generic_Insertion_Sort (Items : in out Item_Array) is
   J   : Index;
   Key : Item_Type;
begin
   if Items'Length <= 1 then
      return;
   end if;

   for I in Index'Succ (Items'First) .. Items'Last loop
      Key := Items (I);
      J := I;

      while J > Items'First and then Key < Items (Index'Pred (J)) loop
         Items (J) := Items (Index'Pred (J));
         J := Index'Pred (J);
      end loop;

      Items (J) := Key;
   end loop;
end Generic_Insertion_Sort;

插入排序不適合用在大型陣列,但很適合用來說明泛型。因為只要替換比較函式,同一個迴圈結構就能同時用於升序與降序。

YesNoNoYes未排序陣列依序從左取出 KeyKey 排在前一個元素之前?把前一個元素往右移插入 Key處理到最後了嗎?已排序的陣列

8.3 從相同本體建立升序與降序

type Int_Array is array (Positive range <>) of Integer;

procedure Sort_Asc is new Generic_Insertion_Sort
  (Item_Type  => Integer,
   Index      => Positive,
   Item_Array => Int_Array);

function Greater (Left, Right : Integer) return Boolean is
  (Left > Right);

procedure Sort_Desc is new Generic_Insertion_Sort
  (Item_Type  => Integer,
   Index      => Positive,
   Item_Array => Int_Array,
   "<"        => Greater);

Sort_Asc 使用標準的 <。另一方面,Sort_Desc 則透過 "<" => Greater 替換了比較函式。

99, 3, 47, 12Sort_Asc標準比較Sort_Desc將 Greater 當作比較函式傳入3, 12, 47, 9999, 47, 12, 3

這種機制近似於 C++ 中把比較函式物件當作模板引數傳遞的設計,或是 Rust 中透過 trait bound 要求排序的設計。不過在 Ada 中,是以形式子程式參數明確表達「要傳入這種形式的函式」。

9. 型別類別 ── 撰寫比 private 更具體的契約

type T is private; 雖然方便,卻不是萬能的。對於 private 型別,並不能理所當然地使用四則運算或大小比較。因此,Ada 允許在形式型別參數上指定類別。

Formal Typeprivatelimited privatediscrete box: 離散型別range box: 帶符號整數mod box: 模數整數digits box: 浮點數delta box: 定點數access 型別列舉型別整數型別FloatLong_Float使用者自訂浮點型別

9.1 指定類別有什麼好處

舉例來說,計算平均值或變異數需要加法、減法、乘法、除法。private 型別無法假設這些運算。因此,把型別限定為浮點型別。

generic
   type Real is digits <>;
   type Real_Array is array (Positive range <>) of Real;
package Generic_Statistics is
   function Mean (Values : Real_Array) return Real;
   function Variance (Values : Real_Array) return Real;
end Generic_Statistics;

透過 type Real is digits <>;,就能確定 Real 是浮點型別。因此,泛型本體中可以使用 +-*/ 等運算。

9.2 本體

package body Generic_Statistics is
   function Mean (Values : Real_Array) return Real is
      Sum : Real := 0.0;
   begin
      if Values'Length = 0 then
         return 0.0;
      end if;

      for V of Values loop
         Sum := Sum + V;
      end loop;

      return Sum / Real (Values'Length);
   end Mean;

   function Variance (Values : Real_Array) return Real is
      M   : constant Real := Mean (Values);
      Sum : Real := 0.0;
   begin
      if Values'Length = 0 then
         return 0.0;
      end if;

      for V of Values loop
         declare
            D : constant Real := V - M;
         begin
            Sum := Sum + D * D;
         end;
      end loop;

      return Sum / Real (Values'Length);
   end Variance;
end Generic_Statistics;

9.3 在 FloatLong_Float 中使用

type Float_Array is array (Positive range <>) of Float;
type Long_Array  is array (Positive range <>) of Long_Float;

package Float_Stats is new Generic_Statistics (Float, Float_Array);
package Long_Stats  is new Generic_Statistics (Long_Float, Long_Array);

同一套統計處理,可以重用在精度不同的浮點型別上。

Generic_StatisticsReal is digits boxFloat_StatsLong_StatsMy_Real_Stats以 Float 計算 Mean / Variance以 Long_Float 計算 Mean / Variance以使用者自訂 Real 計算 Mean / Variance

9.4 類別指定就是「型別層級的規格說明書」

類別指定並不只是為了讓編譯器閉嘴的語法。對讀者而言,它同時也是一份傳達「這個部件要求什麼」的規格說明書。

想撰寫的處理 適合的形式型別 理由
交換、儲存、取出 private 只要能指派即可
無法複製的資源管理 limited private 不以指派為前提
陣列索引、列舉狀態的走訪 (<>) 可以使用 FirstLastSuccPred
整數的加總、計數器 range <> 可以假設整數運算
位元遮罩、循環計數器 mod <> 可以假設模數運算
平均、變異數、數值計算 digits <> 可以假設浮點運算
金額、控制量等固定精度 delta <> 可以假設定點運算

10. 注入述詞 ── 用 Ada 的方式撰寫 Count_If

形式子程式參數不僅可用於比較函式,也能用於述詞。述詞是指接收一個值並回傳 Boolean 的函式。

在 Ada 中,可以用泛型的形式子程式來表達與 C# 的 Func<T, bool>、Java 的 Predicate<T>、C++ 的 lambda 或函式物件相近的角色。

10.1 規格部分

generic
   type Element is private;
   type Index is (<>);
   type Array_Type is array (Index range <>) of Element;
   with function Predicate (Item : Element) return Boolean;
function Generic_Count_If (Arr : Array_Type) return Natural;

這裡並沒有給 Predicate 加上 is <>。因為並不存在標準上可見的述詞函式,所以設計成一定要由使用端傳入。

10.2 本體

function Generic_Count_If (Arr : Array_Type) return Natural is
   Count : Natural := 0;
begin
   for Item of Arr loop
      if Predicate (Item) then
         Count := Count + 1;
      end if;
   end loop;

   return Count;
end Generic_Count_If;

處理流程很單純。

TrueFalse陣列走訪每個元素Predicate(Item)?增加 Count不做任何事前往下一個元素回傳 Count

10.3 計算偶數個數與閾值個數

type Int_Array is array (Positive range <>) of Integer;

function Is_Even (N : Integer) return Boolean is
  (N mod 2 = 0);

function Is_Large (N : Integer) return Boolean is
  (N > 50);

function Count_Even is new Generic_Count_If
  (Element    => Integer,
   Index      => Positive,
   Array_Type => Int_Array,
   Predicate  => Is_Even);

function Count_Large is new Generic_Count_If
  (Element    => Integer,
   Index      => Positive,
   Array_Type => Int_Array,
   Predicate  => Is_Large);

從相同的走訪邏輯,可以建立出只有條件不同的兩個函式。

Generic_Count_IfCount_EvenPredicate = Is_EvenCount_LargePredicate = Is_Large12, 7, 88, 3, 56, 91, 44, 19, 62偶數的個數大於 50 的個數

在這個範例中,陣列的走訪、計數器的管理、結果的回傳全部都是共用的。另一方面,「要計算什麼」則是以函式的形式注入進去。這就是 Ada 中高階設計的基本形式。

11. 組合多個參數 ── 通用鍵值儲存

在實際的部件中,光靠一個型別參數就能解決問題的情況並不多見。鍵與值的型別、鍵的比較方式、最大筆數等,往往需要組合多個條件。

這裡以固定長度的簡易鍵值儲存為例。

Generic_KV_StoreKey_TypeValue_Type鍵值一致函式Max_EntriesPut / Get / Contains設定值儲存小型快取嵌入式用固定長度字典

11.1 規格部分

generic
   type Key_Type is private;
   type Value_Type is private;
   with function "=" (Left, Right : Key_Type) return Boolean is <>;
   Max_Entries : Positive := 50;
package Generic_KV_Store is
   procedure Put (Key : Key_Type; Val : Value_Type);
   function Get (Key : Key_Type) return Value_Type;
   function Contains (Key : Key_Type) return Boolean;

   Key_Not_Found : exception;
   Store_Full    : exception;
end Generic_KV_Store;

這個套件有 4 個形式參數。

參數 種類 角色
Key_Type 型別 鍵的型別
Value_Type 型別 值的型別
"=" 子程式 鍵的一致性判定
Max_Entries 最大項目數

Max_Entries:= 50 給定了預設值。因此,若沒有特別指定,就會建立可容納 50 筆的儲存。

11.2 本體

package body Generic_KV_Store is
   subtype Index_Type is Positive range 1 .. Max_Entries;

   type Key_Array   is array (Index_Type) of Key_Type;
   type Value_Array is array (Index_Type) of Value_Type;
   type Used_Array  is array (Index_Type) of Boolean;

   Keys   : Key_Array;
   Values : Value_Array;
   Used   : Used_Array := (others => False);

   function Find_Index (Key : Key_Type) return Natural is
   begin
      for I in Index_Type loop
         if Used (I) and then Keys (I) = Key then
            return I;
         end if;
      end loop;

      return 0;
   end Find_Index;

   function Find_Free return Natural is
   begin
      for I in Index_Type loop
         if not Used (I) then
            return I;
         end if;
      end loop;

      return 0;
   end Find_Free;

   procedure Put (Key : Key_Type; Val : Value_Type) is
      Pos : Natural := Find_Index (Key);
   begin
      if Pos = 0 then
         Pos := Find_Free;

         if Pos = 0 then
            raise Store_Full;
         end if;

         Used (Pos) := True;
         Keys (Pos) := Key;
      end if;

      Values (Pos) := Val;
   end Put;

   function Get (Key : Key_Type) return Value_Type is
      Pos : constant Natural := Find_Index (Key);
   begin
      if Pos = 0 then
         raise Key_Not_Found;
      end if;

      return Values (Pos);
   end Get;

   function Contains (Key : Key_Type) return Boolean is
   begin
      return Find_Index (Key) /= 0;
   end Contains;
end Generic_KV_Store;

這個實作採用線性搜尋,因此不適合大量資料。不過,在固定長度、小規模、不需動態記憶體配置這些性質很重要的場合,這是很好用的形式。

Keys/Values/UsedGeneric_KV_Store 實例呼叫端Keys/Values/UsedGeneric_KV_Store 實例呼叫端alt[已存在該鍵][新的鍵]Put(Key, Value)Find_Index(Key)Values(Pos) := ValueFind_FreeKeys(Pos) := KeyValues(Pos) := ValueUsed(Pos) := TrueGet(Key)Find_Index(Key)PosValues(Pos)

11.3 實例化範例

with Ada.Strings.Unbounded;
use Ada.Strings.Unbounded;

procedure KV_Demo is
   package Int_String_Store is new Generic_KV_Store
     (Key_Type    => Integer,
      Value_Type  => Unbounded_String,
      Max_Entries => 10);
begin
   Int_String_Store.Put (1, To_Unbounded_String ("Ada"));
   Int_String_Store.Put (2, To_Unbounded_String ("SPARK"));

   if Int_String_Store.Contains (1) then
      -- 可以透過 Get (1) 取得值
      null;
   end if;
end KV_Demo;

這裡省略了 "="。因為 Integer 本來就有標準的相等運算子,透過 is <> 就會使用它。

如果鍵是忽略大小寫的字串之類的型別,就可以傳入自訂的相等函式。

function Same_Key (Left, Right : Unbounded_String) return Boolean is
  (To_Lower (To_String (Left)) = To_Lower (To_String (Right)));

package String_Key_Store is new Generic_KV_Store
  (Key_Type    => Unbounded_String,
   Value_Type  => Integer,
   "="         => Same_Key,
   Max_Entries => 100);

12. 正式套件參數 ── 讓泛型進一步模組化

在 Ada 的泛型中,可以把套件本身當作形式參數。利用這一點,就能把「由某個泛型套件建立出的實例」,當作另一個泛型的輸入來處理。

Generic_StackInt_StackGeneric_Stack_LoggerInt_Stack_Logger_Instance

12.1 接收堆疊的日誌記錄器

舉例來說,假設要建立一個接收先前的 Generic_Stack 實例,並顯示其大小的日誌記錄器。

generic
   with package Stack is new Generic_Stack (<>);
package Generic_Stack_Logger is
   procedure Print_Size;
end Generic_Stack_Logger;

本體如下所示。

with Ada.Text_IO; use Ada.Text_IO;

package body Generic_Stack_Logger is
   procedure Print_Size is
   begin
      Put_Line ("Stack size =" & Natural'Image (Stack.Size));
   end Print_Size;
end Generic_Stack_Logger;

在使用端,首先建立堆疊,再把這個堆疊傳給日誌記錄器。

package Int_Stack is new Generic_Stack
  (Element_Type => Integer,
   Max_Size     => 10);

package Int_Stack_Logger is new Generic_Stack_Logger
  (Stack => Int_Stack);

透過這樣的設計,就能把泛型部件互相組合起來。

第二階段第一階段Int_Stack_LoggerGeneric_Stack_LoggerInt_StackGeneric_StackPrint_Size

這是與 C++ 模板模板參數相近的用途,但在 Ada 中可以明確表達「接收這個泛型套件的實例」。在大規模的 Ada 程式碼中,這在把容器、演算法、日誌、檢查、測試輔助等分開並加以組合時很有用。

13. Contract Model ── Ada 泛型最重要的思路

理解 Ada 的泛型時,重要的關鍵在於 contract model

泛型本體必須只使用形式參數所約定的操作來撰寫。例如,若只宣告了 type Element is private;,就不能對 Element 使用 <。若想使用 <,就必須明確地以形式子程式表達,或是把型別類別指定得更具體。

generic formal part契約generic body在契約範圍內實作本體單獨進行型別檢查實例化actual parameters實際型別・實際函式・實際值檢查實際參數是否滿足契約一般的套件/子程式

透過這樣的設計,不僅泛型的使用者,撰寫泛型的一方也同樣受到保護。

13.1 與 C++ 模板的觀感差異

C++ 的模板雖然強大,但在歷史上有著「只有在把模板本體實例化之後才會出現錯誤」的特性。這一點在 C++20 的 concepts 中已有所改善,但 Ada 的泛型從一開始就是明確表達契約的模型。

C++ templatesinstantiation 時要求式才會具體化撰寫 template body可用 concepts 明確表達限制Adabody 在契約範圍內檢查在 formal part 撰寫契約於 instantiation 檢查 actual

Java 或 C# 的泛型,設計核心在於參照型別、限制、型別抹除,以及與執行時表示方式之間的關係。相對地,Ada 的泛型更偏向於在編譯時建立具體實例的思路。

觀點 Ada C++ Java Rust
契約的撰寫方式 在 formal part 撰寫型別・值・函式・套件 templates / concepts 型別參數與 bounds trait bounds
本體的檢查 在形式參數的契約內檢查 以實例化時的具體化為核心 在 bounds 內檢查 在 trait bounds 內檢查
執行時成本 以靜態解析為基本 以靜態生成為基本 受型別抹除影響 以單態化為基本
值參數 有限支援 const generics
把子程式當作形式參數 以函式物件等方式表達 lambda / 函式介面 閉包/函式/trait
把套件當作形式參數 模板模板等 與模組結構分開

各語言在細部功能上各有不同,但 Ada 的特徵在於「先以語法寫下契約」。

14. 實務上的設計判斷 ── 什麼該做成泛型

泛型雖然方便,但並不是什麼都做成泛型就好。實務上,依照下列方式判斷,會比較不容易失敗。

YesNoYesNoYesNoYesNo有想要重用的處理只有型別不同?考慮型別參數大小或閾值也不同?加入值參數比較或判斷的行為不同?加入形式子程式想把內部狀態或 API 整合起來?泛型套件一般的子程式就足夠

14.1 適合泛型子程式的場合

泛型子程式適合用於不具狀態的演算法。

  • Swap
  • Sort
  • Count_If
  • Find
  • 類似 Map 的轉換
  • Min / Max

若演算法本體簡短、輸入與輸出明確,比起套件,用子程式會更容易閱讀。

14.2 適合泛型套件的場合

泛型套件適合用於想連同型別一起擁有多個操作或內部狀態的場合。

  • 固定長度堆疊
  • 環形緩衝區
  • 小型字典
  • 統計處理組
  • 各裝置的 I/O 抽象化
  • 帶單位系統的數值型別運算組

尤其在 Ada 中,套件的規格部分是公開 API,套件本體則是實作,兩者是分離的,因此泛型套件可以當作「型別安全的模組範本」來使用。

隱藏package spec公開 API使用端package body內部實作generic formal part型別・值・函式的契約

14.3 一開始讓形式參數保持精簡

若形式參數增加太多,實例化就會變得難以閱讀。一開始保持在最小限度,等出現想要替換的理由時再增加,會比較安全。

-- 容易變得難以閱讀的範例
package X is new Generic_Foo
  (A, B, C, D, E, F, G);

-- 用具名關聯保留意圖
package X is new Generic_Foo
  (Element_Type => Integer,
   Index_Type   => Positive,
   Buffer_Size  => 128,
   "<"          => Less);

在 Ada 中,實例化時可以使用具名關聯。由於泛型設計上的重點會顯現在實例化上,因此在實務程式碼中,以具名方式撰寫通常更容易維護。

15. 常見的卡關之處

Ada 的泛型雖然強大,但一開始容易卡關的地方也不少。

15.1 private 型別無法做大小比較

無法撰寫下列這樣的本體。

generic
   type Element is private;
function Bad_Min (A, B : Element) return Element;

function Bad_Min (A, B : Element) return Element is
begin
   if A < B then      -- 這裡會出錯
      return A;
   else
      return B;
   end if;
end Bad_Min;

由於 Element 只被宣告為 private,因此不保證能使用 <。若想比較,就要像下面這樣把它加進契約中。

generic
   type Element is private;
   with function "<" (Left, Right : Element) return Boolean is <>;
function Generic_Min (A, B : Element) return Element;
本體想要使用比較在 formal part 撰寫比較函式於實例化時確認是否可比較只有 private泛型本體發生編譯錯誤

15.2 is <> 不是「什麼都能自動推論」

is <> 雖然方便,但並非魔法。在實例化的地點,必須要能看得到相符的運算子或子程式。若把自訂的比較函式放在別的套件中,適當地進行 withuse,或是以具名方式明確傳入,會比較安全。

procedure Sort_By_Age is new Generic_Insertion_Sort
  (Item_Type  => Person,
   Index      => Positive,
   Item_Array => Person_Array,
   "<"        => Younger_Than);

15.3 每個實例的例外也會變成不同的東西

若在泛型套件的規格部分宣告例外,那麼每個實例都會產生不同的例外。

package Int_Stack   is new Generic_Stack (Integer, 5);
package Float_Stack is new Generic_Stack (Float, 3);

在這種情況下,Int_Stack.Stack_OverflowFloat_Stack.Stack_Overflow 會被視為不同的例外。若想當作共通例外處理,也可以考慮在泛型外部定義例外的設計。

不同的例外Generic_StackStack_Overflow 宣告Int_Stack.Stack_OverflowFloat_Stack.Stack_Overflow

15.4 程式碼大小有時會增加

泛型一方面容易避免執行時多餘的間接參照,但另一方面由於會為每種型別建立實例,實例數量一多,程式碼大小就有可能增加。

這是在 C++ 的模板或 Rust 的單態化中也能看到的一種取捨。在偏向高信賴、嵌入式、即時性的開發中,思路會變成:以管理建置時產出物的大小,來換取降低執行時的不確定性。

單一個 generic 本體Integer 版Float 版Long_Float 版My_Type 版產生的程式碼容易避免執行時的型別判定或裝箱實例一多要注意大小增加

15.5 應該使用 limited private 的場合

type Element is private; 是以指派為前提的。若要處理像檔案控制代碼、鎖、裝置控制代碼這類不想被複製的東西,就要考慮使用 limited private

generic
   type Resource is limited private;
   with procedure Close (R : in out Resource);
procedure Generic_Use_And_Close (R : in out Resource);

在處理無法複製的型別的設計中,比起儲存值的容器,套用程序的演算法,或是明確表達參照的設計,會更加安全。

16. 小型設計模式集

接下來,簡短整理實務上常用的形式。

16.1 只對可比較的值提供 Min

generic
   type Element is private;
   with function "<" (Left, Right : Element) return Boolean is <>;
function Generic_Min (A, B : Element) return Element;

function Generic_Min (A, B : Element) return Element is
begin
   if A < B then
      return A;
   else
      return B;
   end if;
end Generic_Min;
Element需要比較函式Generic_Min回傳較小的一方

16.2 把閾值當作值參數

generic
   type Count_Type is range <>;
   Threshold : Count_Type;
function Generic_Is_Over (Value : Count_Type) return Boolean;

function Generic_Is_Over (Value : Count_Type) return Boolean is
begin
   return Value > Threshold;
end Generic_Is_Over;

值參數適合用於想固定成實例性質的值,而不是執行時的設定值。

16.3 注入輸出手段

generic
   type Element is private;
   with procedure Put (Item : Element);
procedure Generic_Print_Twice (Item : Element);

procedure Generic_Print_Twice (Item : Element) is
begin
   Put (Item);
   Put (Item);
end Generic_Print_Twice;

採用這種形式,就可以替換輸出目標,例如標準輸出、日誌、測試用緩衝區等。

Generic_Print_Twice把 Put 當作形式子程式接收主控台輸出日誌輸出測試用緩衝區

16.4 不固定陣列的索引型別

在 Ada 中,陣列的索引型別也是重要的型別資訊。不要死板地固定用 Positive,若有需要,把索引型別也當作形式參數,可以提高重用性。

generic
   type Element is private;
   type Index is (<>);
   type Array_Type is array (Index range <>) of Element;
procedure Generic_Clear (Arr : in out Array_Type; Value : Element);

採用這種設計,就不只能對應 Positive 索引的陣列,也能對應列舉型別索引的陣列。

Index is discretePositive rangeDay 列舉型別State 列舉型別自訂整數型別

17. 讓 API 更具 Ada 風格的檢查清單

撰寫泛型時,最後從下列觀點重新檢視,會讓程式碼更容易閱讀。

Generic 設計檢查形式參數是否精簡是否在 formal part 明確表達必要的運算private / range / digits 等類別是否恰當能否用具名關聯讓實例化易讀是否意識到每個實例各自的狀態或例外能否接受程式碼大小增加是否準備了測試用實例

用文字整理如下。

  • 本體中使用的操作,一定要以形式參數契約中可見的形式呈現。
  • private 就夠了,就用 private。需要算術運算就使用 range <>digits <>
  • 比較、雜湊、輸出、轉換等隨型別而變的行為,做成形式子程式。
  • 若大小或閾值是實例的性質,就做成值參數。
  • 具狀態就先考慮泛型套件,不具狀態就先考慮泛型子程式。
  • 實例化時,引數越多越要使用具名關聯。
  • 設計時要以「例外與內部狀態在每個實例中都是獨立的」為前提。

18. 範例整體結構範例

若要把文中的範例分成檔案,採用下列這種結構會比較容易閱讀。

ada-generic-programmingsrcgenericsdemosgeneric_swap.adsgeneric_swap.adbgeneric_stack.adsgeneric_stack.adbgeneric_insertion_sort.adsgeneric_insertion_sort.adbgeneric_statistics.adsgeneric_statistics.adbgeneric_count_if.adsgeneric_count_if.adbgeneric_kv_store.adsgeneric_kv_store.adbswap_demo.adbstack_demo.adbsort_demo.adbstatistics_demo.adbcount_if_demo.adbkv_demo.adb

若是給文章用的小型範例,整合成一個檔案再用 gnatchop 分割也很方便;但若考慮到實務或長期維護,把規格部分 .ads 與本體 .adb 分開,會是更有 Ada 風格的結構。

19. 結語 ── 以型別劃定重用的界線

Ada 的泛型程式設計,並不僅僅是「撰寫不依賴型別的程式碼的功能」。其本質毋寧在於,把可重用部件所要求的東西,以型別、子程式與值的契約明確表達出來

撰寫契約撰寫泛型本體傳入型別・值・函式進行實例化型別安全地使用無需複製即可重用

如本文所見,在 Ada 的泛型中,可以把下列這些東西當作形式參數。

  • 型別
  • 子程式
  • 套件

此外,關於型別,還可以指定 privatelimited privaterange <>mod <>digits <>delta <>(<>) 等相當細緻的類別。藉此,泛型本體不必依賴「不確定能不能做的操作」,而能只用契約中寫明的操作來安全實作。

在 C 語言或舊式 C++ 的資產中,有時會為了重用而使用巨集、void*、函式指標、手寫的型別分支。Ada 的泛型可以把這些用途中的許多部分,替換成型別安全且易讀的形式。特別是在長期維護、嵌入式、即時性、高信賴性軟體中,這種「在編譯時就決定界線的設計」具有很大的價值。

20. 相關的諮詢領域

合同會社小村軟體處理 Windows 應用程式開發、既有資產的調查與改造、COM / ActiveX / 32bit / 64bit 邊界整理、技術諮詢・設計審查等業務。除了 Ada 這類靜態型別、偏高信賴性的設計之外,如何整理既有的 C/C++、C#、VB6、MFC、COM 資產,並對其進行延命或遷移,同樣是實務上常見的相近主題。

參考資料

共用相同標籤的最新文章。能以相近的主題延伸理解。

Ada 的安全並行處理 ── 任務與保護物件實戰指南

本文是 Ada 語言內建並行處理機制──任務(task)與保護物件(protected object)的實戰入門文章。內容涵蓋會合(entry/accept)、選擇性接受(select)、生產者消費者模式、保護物件實現的排他控制、帶屏障的保護入口、附逾時的呼叫,以及任務優先...

與本文相近的主題頁面。以本文為起點,可進一步連到相關服務與其他文章。

常見問題

整理諮詢這個主題時常見的問題。

Ada 的泛型是什麼?
泛型是一種把型別、值、子程式,甚至套件本身當作形式參數接收,並在透過 new 實例化時進行靜態型別檢查的重用機制。它不是單純的文字取代,而是在編譯時就確定「這個部件是否滿足這個契約」。泛型子程式只宣告是無法呼叫的,只有給定具體型別並完成實例化之後,才能作為一般的程序或函式使用。
Ada 的泛型與 C++ 的模板有什麼不同?
Ada 從一開始就採用明確表達契約的 contract model,泛型本體只使用形式參數所約定的操作來撰寫,本體本身就會獨立進行型別檢查。C++ 的模板在歷史上有「只有實例化之後才會報錯」的特性,這一點在 C++20 的 concepts 中已有所改善。另外,Ada 除了值參數、子程式參數之外,還可以把套件本身當作形式參數,藉此把泛型部件互相組合起來。
為什麼要在 Ada 的形式型別參數中指定型別類別?
這是為了把本體中可以使用的操作明確表達為契約。type T is private 只能以指派、相等比較等基本操作為前提,無法使用大小比較或算術運算。若需要整數運算就指定 range <>,需要浮點運算就指定 digits <>,需要位元運算就指定 mod <> 這類類別。類別指定同時也具有向讀者傳達「這個部件要求什麼」的型別層級規格說明書的作用。
使用 Ada 的泛型時有哪些需要注意的地方?
由於會為每種型別建立實例,實例數量一多,程式碼大小就可能增加。這是在 C++ 的模板或 Rust 的單態化中也能看到的一種取捨。此外,在泛型套件規格部分宣告的例外,在每個實例中都會變成不同的例外。實務上的方針是:形式參數一開始保持最少,出現需要替換的理由時再增加;在引數較多的實例化中使用具名關聯。

作者檔案

本文作者的個人檔案頁面。

Go Komura

小村軟體有限公司 代表

以 Windows 軟體開發、技術諮詢與故障調查為中心,在難以重現的故障調查與既有資產仍在運作的專案上具有優勢。

回到部落格一覽