Ada 的泛型编程 —— 用类型编写契约,零成本实现代码复用

· · Ada, ProgrammingLanguage, Generics, TypeSystem, StaticTyping, ContractModel, ZeroCostAbstraction, GNAT, Alire, 高可靠性, 代码复用

1. 引言 —— 不是”什么都能接受”,而是”约定了什么”

在静态类型语言中尝试编写可复用的代码时,很快就会遇到相同的困扰。为整数编写的栈也想用在字符串上。为浮点数数组编写的统计处理也想用在别的类型上。升序排序的逻辑也想用在降序排序上。但是,如果针对每种类型都复制相同的代码,就会出现修改遗漏。反过来,如果设计成用 void* 或类型转换接受任何东西,类型安全性就会崩溃。

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

Ada 的泛型不是单纯的文本替换。它可以把类型、值、子程序,甚至包(package)本身作为形式参数接收,并在实例化(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

GNAT 可以从 Alire(Ada 的包管理器)通过 alr install gnat_native gprbuild 安装,请确保将其加入 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)。

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 常见的泛型(generics)相比是很大的不同。

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 的意思是,从泛型本体的角度看,不知道该类型的内部表示。

从这个声明可以了解到以下两点:

  • 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. 泛型包 —— 把类型和值作为参数

如果不是想复用单个子程序,而是想把多个操作和内部状态整合起来复用,就要使用泛型包。典型的例子是栈(stack)。

栈只要改变元素类型和最大大小,基本逻辑就是相同的。

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;

这里使用了两种形式参数。

  • 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 / PopPop取出最后一个元素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;

插入排序不适合大数组,但很适合用来说明泛型。因为只需替换比较函数,就能让同一套循环结构同时适用于升序和降序。

未排序数组从左侧依次取出 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 允许为形式类型参数指定类别(category)。

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 的函数。

与 C# 中的 Func<T, bool>、Java 中的 Predicate<T>、C++ 中的 lambda 或函数对象所承担的角色类似,在 Ada 中可以用泛型的形式子程序来表达。

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 加 1什么都不做进入下一个元素返回 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++ 的模板模板参数(template template parameter)用途相近,但在 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 范围内检查
运行时开销 以静态解析为基础 以静态生成为基础 受类型擦除影响 以单态化(monomorphization)为基础
值参数 有限 const generics
把子程序作为形式参数 通过函数对象等表达 lambda / 函数式接口 闭包 / 函数 / trait
把包作为形式参数 模板模板参数等 与模块结构是分开的概念

各语言的具体特性各不相同,但 Ada 的特点在于”先以语法的形式写出契约”。

14. 实务中的设计判断 —— 什么应该做成泛型

泛型很方便,但并不是什么都适合做成泛型。在实务中,按照下面的方式判断可以减少失败。

有想要复用的处理只是类型不同?考虑类型参数大小或阈值也不同?增加值参数比较或判定的行为不同?增加形式子程序想把内部状态或 API 整合起来?泛型包普通子程序就足够了

14.1 适合使用泛型子程序的场景

泛型子程序适合用于不持有状态的算法。

  • Swap
  • Sort
  • Count_If
  • Find
  • 类似 Map 的转换
  • Min / Max

当算法本体简短、输入和输出明确时,子程序比包更易读。

14.2 适合使用泛型包的场景

泛型包适合在需要将类型与多个操作、内部状态一起持有的场合使用。

  • 固定长度栈
  • 环形缓冲区
  • 小规模字典
  • 统计处理集合
  • 各设备的 I/O 抽象
  • 带单位系统的数值类型运算集合

尤其在 Ada 中,包的规格部分(spec)就是公开 API,包本体(body)则是实现,二者是分离的,因此泛型包可以作为”类型安全的模块模板”来使用。

隐藏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 中,实例化时可以使用具名关联(named association)。由于泛型设计上的关键点会体现在实例化中,实务代码里用具名方式书写通常更便于维护。

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_Stack声明 Stack_OverflowInt_Stack.Stack_OverflowFloat_Stack.Stack_Overflow

15.4 代码体积可能会增加

泛型一方面容易避免运行时多余的间接引用,另一方面由于会为每种类型生成实例,如果实例数量很多,代码体积可能会增加。

这是在 C++ 的模板或 Rust 的单态化(monomorphization)中也能看到的一种权衡。在偏向高可靠、嵌入式、实时的开发中,其理念是:以减少运行时的不确定性为代价,来管理构建时产物的体积。

单个 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. 打造符合 Ada 风格 API 的检查清单

编写泛型时,最后从以下角度重新审视,会让代码更易读。

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 的泛型是什么?
泛型是一种把类型、值、子程序,甚至包本身作为形式参数接收,并在通过 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 软件开发、技术咨询与故障排查为中心,擅长难以复现的故障调查,以及既有资产仍在运行的项目。

返回博客列表