Generic programming ב-Ada — חוזה בטיפוסים ו-reuse ב-zero cost

· עודכן בתאריך: · · Ada, Programming Language, Generics, Type System, Static Typing, Contract Model, Zero Cost Abstraction, GNAT, Alire, High Integrity, Code Reuse

1. מבוא — לא «לקבל הכול», אלא «על מה מתחייבים»

בשפה עם טיפוסים סטטיים, ברגע שמנסים לכתוב קוד שאפשר לעשות לו reuse, נתקלים באותה בעיה. stack שנכתב ל-integers רוצים להשתמש בו גם למחרוזות. אותו עיבוד סטטיסטי רוצים להריץ גם על מערך של floating-point. לוגיקת מיון בסדר עולה רוצים גם לסדר יורד. אם מעתיקים את אותו קוד לכל טיפוס, תיקונים מתפספסים. אם מקבלים הכול עם void* או עם cast, type safety נשברת.

התשובה של Ada היא generics (generic units).

generics ב-Ada אינם החלפת טקסט. הם מקבלים טיפוסים, ערכים, subprograms, ואפילו packages שלמים כ-formal parameters, והטיפוסים נבדקים סטטית ברגע ה-instantiation. כלומר לא בודקים בזמן ריצה «האם הטיפוס הזה באמת בסדר», אלא קובעים בזמן קומפילציה «האם הרכיב הזה מקיים את ה-contract».

שלוש דרכים ל-reuse בקוד עם טיפוסים סטטייםcopy-paste נוטה לתיקונים חסרים, void או cast שוברים type safety, ו-generics של Ada נותנים בדיקה בקומפילציה בלי dispatch נוסף בזמן ריצה.עיבוד שרוצים לעשות לו reuseאיך עושים reuse?copy-pastevoid* / Object / castgenerics של Adaקל לפספס תיקוניםשגיאות runtime ושבירת טיפוסיםtype-safeבדיקה בזמן קומפילציהבלי dispatch נוסף בזמן ריצה

במאמר הזה מסודר generic programming ב-Ada לפי הסדר הבא.

  • generic subprograms
  • generic packages
  • type parameters, value parameters, subprogram parameters
  • קטגוריות טיפוס כמו private, range <>, digits <>
  • דוגמאות מימוש של מיון, stack, סטטיסטיקה, Count_If, ו-key-value store
  • higher-order generics דרך formal package parameters
  • ה-contract model של Ada וחשיבה עיצובית בפועל

1.1 למי זה מיועד, ומה לוקחים מהמאמר

המאמר מכוון לאנשים כאלה.

  • מי שעבד עם templates ב-C++, generics ב-C# או Java, או generics ב-Rust
  • מי שלא שולט בתחביר של Ada, אבל מתעניין בעיצוב שבו כותבים חוזה בטיפוסים
  • מי שבתחזוקה ארוכת טווח, embedded, או high-integrity שוקל איך לתכנן רכיבים ל-reuse

בתחביר של Ada מספיק להכיר packages (פיצול specification ב-.ads ו-body ב-.adb) ואת מצבי הפרמטרים in / out / in out. אם שני אלה לא יציבים, כדאי קודם לקרוא את «מה מושך בשפת Ada».

מה שלוקחים מכאן הוא פחות התחביר עצמו, ויותר הרגל עיצוב: לפני המימוש כותבים בטיפוסים מה רכיב ה-reuse דורש. אותו רעיון עוזר גם כשמחליטים עד כמה לכתוב מגבלות interface ב-C# או concepts ב-C++20.

1.2 מדריך קריאה — אין חובה לקרוא הכול

יש במאמר 20 פרקים. אפשר לקרוא לפי מטרה, בלי לעבור על הכול ברצף.

מטרה פרקים לקריאה
לתפוס את הרעיון בזמן קצר פרק 4 (המודל הבסיסי) → פרק 6 (generic subprogram מינימלי) → פרק 13 (contract model)
לכתוב רכיבים בעצמך פרק 4 → פרק 6 → פרק 7 (generic package) → פרק 8 (הזרקת behavior) → פרק 9 (קטגוריות טיפוס)
רק הנחיות להחלטות עיצוב פרק 13 → פרק 14 (מה להפוך ל-generic) → פרק 15 (מלכודות) → פרק 17 (checklist)
לשים ידיים על קוד בונים סביבה בפרק 3, ואז מהדוגמאות המוכנות בפרקים 6 ו-7

המסלול הקצר הוא שלושת הפרקים 4, 6 ו-13. בהם מתכנסים הליבה: formal parameters, instantiation, ו-contract model. פרקים 5 ו-9 הם רשימת formal parameters; אפשר לגשת אליהם כמילון כשצריך.

הנושא ממשיך את סדרת הבלוג «מה מושך בשפת Ada», «מבוא לאימות פורמלי עם SPARK», «concurrency בטוח», «מערכות real-time». כאן חופרים את הרעיון של Ada «הטיפוסים מדברים עיצוב» מזווית ה-generics.

knowledge map של המאמר

generics ב-Ada הם מנגנון reuse שמקבל טיפוסים, ערכים, subprograms ו-packages כ-formal parameters, ונבדק סטטית ברגע ה-instantiation עם new. generic subprogram ו-generic package הם שני עמודי התווך של המנגנון הזה: formal type parameters מציינים בקטגוריות כמו private, range <> ו-digits <> את חוזה הפעולות שהגוף רשאי להשתמש בהן, formal subprogram parameters מזריקים behavior כמו השוואה או predicate, ו-formal package parameters מקבלים כרכיב generic package שכבר עבר instantiation. ה-contract model בודק את הגוף לבד, רק בגבול ה-formal parameters, ולכן ב-Ada לא מתרחשת באופן מבני הבעיה ש-templates של C++ נשאו היסטורית, שבה השגיאה מתגלה רק ב-instantiation. עם GNAT ו-Alire אפשר לנסות את המנגנון הזה בסביבה חינמית.

knowledge map: generic programming ב-Adaתרשים שמראה ש-generic subprogram ו-generic package נשענים על חוזה (contract model) של formal parameters מסוג טיפוס, ערך, subprogram ו-package, שהחוזה הזה נבדק ב-instantiation עם new, ואת ההבדל מבעיית השגיאה שמתגלה רק ב-instantiation ש-templates של C++ נשאו היסטורית.מממש אתמשתמש במשתמש בדורשמשתמש במשתמש בדורשמוגדר בדורשדורשמממש אתמממש אתמונעעלול לגרום לדורשמממש אתמוגדר במשתמש במשתמש בדורשמממש אתAda genericscontract model של Ada genericsAdageneric subprogramgeneric packageformal typeformal subprogramformal packageinstantiationformal object (פרמטר ערך)שגיאת template שמתגלה רק ב-instantiationC++ templatesGNATAlire

ב-diagram, solid line מציינת relation שתמיד מתקיים ו-dashed line מציינת relation מותנה (התנאים מופיעים בהסבר של כל relation ב-detail page). הרשימה המלאה של ה-relations (סה”כ 21, כולל evidence ו-certainty) וההגדרות של ה-concepts המרכזיים נמצאות ב-detail page של ה-knowledge map (ביפנית). Data: JSON-LD / Turtle

2. מפת המאמר

קודם תופסים את התמונה כולה באיור. אם מבינים generics ב-Ada רק כ«פיצ’ר שמקבל טיפוס כארגומנט», זה מבט צר מדי. בפועל מחברים, לפי יחידת ה-reuse, subprograms, packages, subprogram parameters, value parameters, ו-formal package parameters.

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

באיורים, box הוא הסימן <> של Ada (box compound delimiter). Mermaid לא מצייר <> כמו שהוא, ולכן רק באיורים כותבים box.

דרך הקריאה פשוטה. במחצית הראשונה עוקבים אחרי התחביר, במחצית השנייה אחרי החלטות עיצוב. אם זו קריאה ראשונה ב-Ada, אל תנסו בהתחלה לשנן תחביר דק. שימו לב ל«מה הפך ל-formal parameter» ול«אילו פעולות מותרות על הפרמטר הזה».

2.1 מילון קצר

מילים שחוזרות בהמשך, בעברית ובאנגלית. במאמר נשארים עם המונח באנגלית generic, כמו שמהנדסים בישראל אומרים.

במאמר English משמעות
generic unit generic unit הצהרה שמתחילה ב-generic. שם כולל ל-generic subprogram ול-generic package
formal parameter generic formal parameter הארגומנט בצד המקבל, בין generic לגוף ההצהרה. טיפוס, ערך, subprogram, או package
formal part generic formal part הרשימה עצמה של ה-formal parameters. אפשר לקרוא לזה «המקום שבו כותבים את ה-contract»
actual parameter generic actual parameter הטיפוס, הערך, ה-subprogram או ה-package שמועברים בפועל ב-instantiation
instantiation instantiation יצירת subprogram או package רגיל מ-generic unit באמצעות new
box <> השם של הסימן <> ב-Ada. ב-range <> וכדומה: הטיפוס הממשי נקבע ב-instantiation
contract model contract model השיטה של Ada: כותבים את הגוף רק בגבול ההבטחות שב-formal parameters, ובודקים את הגוף לבד (פרק 13)

בגוף המאמר נכתוב כמו ב-Ada, range <> ו-digits <>, ורק באיורים range box ו-digits box. Mermaid לא מצייר תוויות שמכילות <>, והמשמעות זהה לגוף. כמו בטבלה, Ada עצמה קוראת ל-<> box, כך שהסימון באיור לא זז ממונחי השפה.

3. סביבת הרצה ואיך מקמפלים

הקוד במאמר מכוון ל-GNAT 15.x ומעלה. GNAT הוא הקומפיילר המייצג של Ada, ומתקינים אותו מ-Alire. Alire הוא package manager של Ada / SPARK, ומשמש גם לניהול toolchain ולבנייה.

gnat --version
# GNAT 15.2.1

מתקינים GNAT מ-Alire (package manager של Ada) עם alr install gnat_native gprbuild, ומוסיפים ל-PATH.

הדוגמאות במאמר מיועדות לשבת ב-repository כך.

מבנה קבצי הדוגמאות במאמרתחת ada-generic-programming נמצאים src/snippets עם קבצי ada ל-swap, stack, sort, statistics, filter ו-key-value store, וגם README.ada-generic-programming/src/snippets/01_swap.ada02_stack.ada03_sort.ada04_statistics.ada05_filter.ada06_kv_store.adaREADME.md

דוגמה שמאגדת כמה compilation units בקובץ אחד מפצלים קודם ב-gnatchop ואז בונים ב-gnatmake.

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

-gnata מפעיל assertions. זה לא חובה כדי להשתמש ב-generics עצמם, אבל בדוגמאות לימוד קל יותר לבדוק contracts ותנאי גבול.

זרימת gnatchop ואז gnatmakeמעבירים קובץ ada אחד ל-gnatchop, מקבלים ads adb ו-main, בונים עם gnatmake gnata, ומריצים את הקובץ הבינארי.קובץ הרצהgnatmakegnatchopמפתחקובץ הרצהgnatmakegnatchopמפתחמעבירים קובץ .ada אחדפיצול ל-.ads / .adb / maingnatmake -gnata mainbind ו-link עד הסוף./mainפלט הריצה

4. המודל הבסיסי של generics ב-Ada

נוח לחשוב על generics ב-Ada בשלושה שלבים.

  1. כותבים generic unit
  2. בחלק ה-generic כותבים formal parameters
  3. בצד המשתמש עושים instantiation עם new
שלושת שלבי generic ב-Adaהצהרת generic, formal parameters, גוף, ואז instantiation עם new שנותן subprogram או package רגיל.הצהרת genericformal parametersגוף ה-genericinstantiation עם newשימוש כ-subprogram או package רגילטיפוסערךsubprogrampackage

למשל, אם הופכים החלפת שני ערכים ל-generic, אפשר לקחת רק את הטיפוס כ-formal parameter.

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

באיור היחס נראה כך.

instantiation של Generic_Swap לפי טיפוסאותה תבנית Generic_Swap מקבלת Integer, Character או My_Record ויוצרת procedure נפרד לכל אחד.מעבירים Integerמעבירים Characterמעבירים My_RecordGeneric_Swaptype Element is privateSwap_IntegerSwap_CharacterSwap_My_Recordמחליף משתני Integerמחליף משתני Characterמחליף משתני My_Record

הנקודה החשובה: גוף התבנית נכתב רק עם הפעולות שמותרות על Element. אם הצהרתם type Element is private;, אפשר השמה והשוואה לשוויון, אבל לא השוואת גודל ולא אריתמטיקה. כלומר ההצהרה של ה-generic עצמה אומרת «מה הרכיב רשאי להניח».

5. סוגי formal parameters — אוצר המילים של generics ב-Ada

ב-generics של Ada מקבלים לא רק טיפוסים. זה הבדל גדול מול generics רגילים ב-C# וב-Java.

ארבעת סוגי ה-formal parametersטיפוס, אובייקט או ערך, subprogram, ו-package, עם דוגמאות כמו private, digits box, Max_Size ו-with package.generic formal parametersפרמטר טיפוסאובייקט / פרמטר ערךפרמטר subprogramפרמטר packagetype Element is privatetype Index is boxtype Real is digits boxMax_Size : PositiveDefault_Value : Elementwith function Less...with procedure Put ...with package P is new ...

באיורים, box הוא הסימן <> של Ada (box compound delimiter). Mermaid לא מצייר <> כמו שהוא, ולכן רק באיורים כותבים box.

ה-formal parameters הטיפוסיים בטבלה.

סוג דוגמה משמעות
פרמטר טיפוס type Element is private; הצורה הבסיסית: כל טיפוס definite שאינו limited
פרמטר טיפוס limited type Element is limited private; מקבל גם טיפוסים שאי אפשר להעתיק
discrete type type Index is (<>); integers, enumerations, וטיפוסים שמשמשים כאינדקס למערך
signed integer type Count is range <>; אפשר להניח +, -, השוואת גודל ואריתמטיקה של integers
modular integer type Word is mod <>; פעולות על bits ואריתמטיקה מודולרית
floating-point type Real is digits <>; Float, Long_Float, וטיפוסי floating-point שהמשתמש הגדיר
fixed-point type Money is delta <>; אריתמטיקה של fixed-point
פרמטר ערך Max_Size : Positive; מקבעים גודל או סף לכל instance
subprogram with function Predicate (...) return Boolean; מזריקים השוואה, predicate, וכדומה
package with package P is new Some_Generic (<>); מקבלים כרכיב generic package שכבר עבר instantiation

עם אוצר המילים הזה, ב-Ada כותבים באופן טבעי «מקבלים רק טיפוסים שיש להם את הפעולות האלה», ולא «מקבלים הכול ועושים משהו מסוכן בפנים».

6. generic subprogram — מבינים את המינימום עם Generic_Swap

כדוגמה ראשונה, Generic_Swap שמחליף שני משתנים מכל טיפוס.

6.1 Specification

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

מה שאחרי generic הוא ה-formal parameters. כאן מקבלים טיפוס בשם Element. is private אומר שמנקודת המבט של גוף ה-generic, הייצוג הפנימי של הטיפוס לא ידוע.

מההצהרה הזו ברורים שני דברים.

  • Generic_Swap עובד לכל טיפוס Element
  • הגוף לא תלוי במבנה הפנימי של Element ולא בהשוואת גודל

6.2 Body

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. לכן זה עובד באופן טבעי לכל טיפוס שאפשר להשים: Integer, Character, records, enumerations.

החלפת שני ערכים ב-Generic_Swapלפני הקריאה A הוא 10 ו-B הוא 20; אחרי השמה דרך Temp, A הוא 20 ו-B הוא 10.אחרי הקריאהלפני הקריאהA = 20B = 10A = 10B = 20Temp = A

6.3 Instantiation

בצד המשתמש כותבים new.

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

מכאן Swap_Int ו-Swap_Char הם procedures רגילים שאפשר לקרוא להם.

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

אי אפשר להעביר ל-Swap_Int (X, Y); משתנה מסוג Float. Swap_Int הוא procedure רגיל שעבר instantiation ל-Integer. generics אינם «חור שמקבל הכול»; הם מנגנון שמייצר לכל טיפוס דבר ממשי ובטוח.

7. generic package — טיפוס וערך כפרמטרים

כשרוצים reuse לא של subprogram אחד אלא של כמה פעולות יחד עם מצב פנימי, משתמשים ב-generic package. הדוגמה הקלאסית היא stack.

ב-stack, אם משנים רק את טיפוס האיבר ואת הגודל המקסימלי, הלוגיקה הבסיסית זהה.

Generic_Stack לפי טיפוס וקיבולתאותו Generic_Stack מקבל Element_Type ו-Max_Size ויוצר Int_Stack, Float_Stack ו-String_Stack עם אותן פעולות Push Pop Size.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 Specification

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;

כאן שני סוגים של formal parameters.

  • Element_Type הוא פרמטר טיפוס
  • Max_Size הוא פרמטר ערך

Max_Size הוא Positive, ולכן אי אפשר לעשות instantiation עם גודל 0 או שלילי. גם לפרמטר ערך יש מגבלת טיפוס.

7.2 Body

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;

בגוף ה-package חשוב ש-Data ו-Top נוצרים בנפרד לכל instance.

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

שניהם נוצרים מאותה תבנית, אבל המצב הפנימי אינו משותף.

מצב נפרד לכל instance של Generic_StackInt_Stack ו-Float_Stack נוצרים מאותו Generic_Stack אבל לכל אחד Top ומערך Data משלו.המצב של Float_StackTopData : מערך Floatהמצב של Int_StackTopData : מערך IntegerGeneric_StackInt_StackFloat_Stack

7.3 מעברי המצב של ה-stack

נוח לראות stack כ-state machine.

מעברי מצב של stackEmpty, NonEmpty ו-Full מתחלפים ב-Push ו-Pop; Push מלא מוביל ל-Overflow ו-Pop ריק ל-Underflow.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;

בונים ומריצים באותו סדר כמו בפרק 3.

gnatchop ../src/snippets/02_stack.ada
gnatmake -gnata stack_demo
./stack_demo
Size= 3
Pop = 30
Pop = 20
Size= 1

הרווח אחרי = מגיע מכך ש-'Image של טיפוס integer שם תו רווח אחד לפני ערך שאינו שלילי. אחרי 3 פעמים Push ופעמיים Pop, ה-Size האחרון הוא 1. אם קוראים ל-Push כשה-stack מלא (כאן 5, ה-Max_Size) נזרק Int_Stack.Stack_Overflow; אם קוראים ל-Pop כשהוא ריק נזרק Int_Stack.Stack_Underflow.

generic packages עובדים טוב בפועל ב«container קטן», «buffer באורך קבוע», «ring buffer», «תור לוגים», ו«שכבת הפשטה לחומרה». ב-Ada במיוחד, עיצוב שמקבע גודל סטטית כטיפוס או כפרמטר ערך, במקום להזיז אותו בזמן ריצה, יושב טוב עם מערכות high-integrity.

8. formal subprogram — מזריקים behavior

גם אחרי שמקבלים טיפוס, יש דברים שאי אפשר לבטא. במיון, למשל, צריך לא רק את טיפוס האיבר אלא גם את לוגיקת ההשוואה: מי בא קודם.

ב-Ada אפשר לקחת את פונקציית ההשוואה עצמה כ-formal parameter של ה-generic.

פרמטרי Generic_Insertion_Sort כולל פונקציית השוואהה-generic מקבל Item_Type, Index, Item_Array ופונקציית השוואה, ואפשר סדר עולה, יורד, או סדר מותאם.Generic_Insertion_SortItem_TypeIndexItem_Arrayפונקציית השוואההשוואה רגילהמעבירים Greater לסדר יורדמעבירים סדר משלכם

8.1 Specification

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

כאן ארבעה formal parameters.

  1. Item_Type: טיפוס איברי המערך
  2. Index: טיפוס האינדקס של המערך
  3. Item_Array: טיפוס המערך עצמו
  4. "<": פונקציית ההשוואה

type Index is (<>); מקבל discrete type. לא רק integers, גם enumerations. זה אופייני ל-Ada: אינדקס מערך לא חייב להיות Positive; אפשר גם enumeration כמו Day.

with function "<" ... is <>; — ה-is <> אומר: אם לא מעבירים actual parameter, משתמשים באופרטור הסטנדרטי הנראה או בפונקציה תואמת. בטיפוס כמו Integer שכבר יש לו <, אפשר בלי לציין במפורש פונקציית השוואה.

8.2 Body

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;

insertion sort לא מתאים למערכים גדולים, אבל מתאים מאוד להסבר על generics. מחליפים רק את פונקציית ההשוואה, ואותו מבנה לולאה עובד לסדר עולה ולסדר יורד.

זרימת insertion sortלוקחים Key משמאל, מזיזים ימינה כל עוד הוא לפני האיבר הקודם, מכניסים אותו, וחוזרים עד שהמערך ממוין.YesNoNoYesמערך לא ממויןלוקחים Key משמאל לפי הסדרKey לפני האיבר הקודם?מזיזים את האיבר הקודם ימינהמכניסים את 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.

אותו גוף מיון לסדר עולה וליורדSort_Asc עם השוואה רגילה נותן 3 12 47 99, ו-Sort_Desc עם Greater נותן 99 47 12 3.99, 3, 47, 12Sort_Ascהשוואה רגילהSort_DescGreater כפונקציית השוואה3, 12, 47, 9999, 47, 12, 3

המנגנון קרוב להעברת function object כארגומנט template ב-C++, או לדרישת סדר עם trait bounds ב-Rust. ב-Ada כותבים במפורש כ-formal subprogram: «מעבירים function בצורה הזו».

8.4 דוגמת הרצה

לפי המבנה בפרק 18, אם Generic_Insertion_Sort יושב בקבצים נפרדים (generic_insertion_sort.ads / .adb), צד הקריאה נראה כך.

with Ada.Text_IO;            use Ada.Text_IO;
with Generic_Insertion_Sort;

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

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

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

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

   procedure Show (Label : String; Items : Int_Array) is
   begin
      Put (Label);
      for V of Items loop
         Put (Integer'Image (V));
      end loop;
      New_Line;
   end Show;

   Asc  : Int_Array := (99, 3, 47, 12);
   Desc : Int_Array := (99, 3, 47, 12);
begin
   Sort_Asc (Asc);
   Sort_Desc (Desc);
   Show ("Asc :", Asc);
   Show ("Desc:", Desc);
end Sort_Demo;
gnatchop ../src/snippets/03_sort.ada
gnatmake -gnata sort_demo
./sort_demo
Asc : 3 12 47 99
Desc: 99 47 12 3

שני procedures מאותו גוף של Generic_Insertion_Sort מתהפכים רק בהחלפת פונקציית ההשוואה. הרווח לפני כל איבר מגיע מכך ש-'Image של integer שם תו רווח אחד לפני ערך שאינו שלילי.

9. קטגוריות טיפוס — חוזה מדויק יותר מ-private

type T is private; נוח, אבל לא עושה הכול. על טיפוס private אי אפשר להניח ארבע פעולות החשבון או השוואת גודל כאילו הן מובנות מאליהן. לכן ב-Ada אפשר לציין category על formal type parameter.

קטגוריות של formal typeprivate, limited private, discrete, range, mod, digits, delta ו-access, עם פיצול ל-enumeration, integer, Float ו-Long_Float.Formal Typeprivatelimited privatediscrete box: discrete typerange box: signed integermod box: modular integerdigits box: floating-pointdelta box: fixed-pointטיפוס accessenumerationintegerFloatLong_Floatטיפוס floating-point שהמשתמש הגדיר

באיורים, box הוא הסימן <> של Ada (box compound delimiter). Mermaid לא מצייר <> כמו שהוא, ולכן רק באיורים כותבים box.

9.1 מה מרוויחים מציון category

למשל ממוצע ושונות דורשים חיבור, חיסור, כפל וחילוק. על טיפוס private אי אפשר להניח את הפעולות האלה. לכן מצמצמים ל-floating-point.

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 הוא טיפוס floating-point. לכן בגוף ה-generic אפשר להשתמש ב-+, -, *, /.

9.2 Body

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 שימוש ב-Float וב-Long_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);

אותו עיבוד סטטיסטי עובר reuse על טיפוסי floating-point בדיוק שונה.

Generic_Statistics על כמה דיוקי floating-pointאותו package עם Real is digits box יוצר Float_Stats, Long_Stats ו-My_Real_Stats ל-Mean ו-Variance.Generic_StatisticsReal is digits boxFloat_StatsLong_StatsMy_Real_StatsMean / Variance ב-FloatMean / Variance ב-Long_FloatMean / Variance ב-Real שהמשתמש הגדיר

9.4 דוגמת הרצה

with Ada.Text_IO;        use Ada.Text_IO;
with Ada.Float_Text_IO;  use Ada.Float_Text_IO;
with Generic_Statistics;

procedure Statistics_Demo is
   type Float_Array is array (Positive range <>) of Float;

   package Float_Stats is new Generic_Statistics (Float, Float_Array);

   Samples : constant Float_Array := (1.0, 2.0, 3.0, 4.0);
begin
   Put ("Mean     = ");
   Put (Float_Stats.Mean (Samples), Fore => 1, Aft => 3, Exp => 0);
   New_Line;

   Put ("Variance = ");
   Put (Float_Stats.Variance (Samples), Fore => 1, Aft => 3, Exp => 0);
   New_Line;
end Statistics_Demo;
gnatchop ../src/snippets/04_statistics.ada
gnatmake -gnata statistics_demo
./statistics_demo
Mean     = 2.500
Variance = 1.250

Ada.Float_Text_IO הוא ספרייה סטנדרטית: instantiation של Ada.Text_IO.Float_IO ל-Float. עם Exp => 0 מקבלים כתיב עשרוני רגיל במקום צורת מעריך, ו-Aft => 3 הוא מספר ספרות אחרי הנקודה. שימו לב ש-Variance כאן הוא שונות האוכלוסייה (חילוק ב-Values'Length), לא שונות המדגם.

9.5 ציון category הוא מפרט ברמת הטיפוס

ציון category אינו תחביר רק כדי להשתיק את הקומפיילר. לקורא זה מפרט שאומר «מה הרכיב דורש».

מה רוצים לכתוב formal type מתאים למה
החלפה, שמירה, שליפה private מספיק שאפשר להשים
ניהול משאב שאי אפשר להעתיק limited private לא מניחים השמה
אינדקס מערך, מעבר על מצבי enumeration (<>) יש First, Last, Succ, Pred
סכום integers, מונה range <> אפשר להניח אריתמטיקה של integers
bit mask, מונה מעגלי mod <> אפשר להניח אריתמטיקה מודולרית
ממוצע, שונות, חישוב מספרי digits <> אפשר להניח אריתמטיקה של floating-point
כסף, גדלי בקרה בדיוק קבוע delta <> אפשר להניח אריתמטיקה של fixed-point

10. הזרקת predicate — Count_If בסגנון Ada

formal subprogram משמש לא רק להשוואה, גם ל-predicate. predicate הוא function שמקבל ערך ומחזיר Boolean.

את התפקיד שקרוב ל-Func<T, bool> ב-C#, ל-Predicate<T> ב-Java, ול-lambda או function object ב-C++, מבטאים ב-Ada כ-formal subprogram של generic.

10.1 Specification

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;

כאן אין is <> על Predicate. אין predicate סטנדרטי שנראה מעצמו, ולכן צד השימוש חייב תמיד להעביר אחד.

10.2 Body

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;

הזרימה פשוטה.

ספירה עם Predicate ב-Generic_Count_Ifעוברים על איברי המערך, מגדילים Count כש-Predicate מחזיר True, ומחזירים את Count.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);

מאותה לוגיקת מעבר יוצרים שתי functions ששונות רק בתנאי.

שני instantiations של Generic_Count_Ifאותם נתונים נספרים ב-Count_Even עם Is_Even וב-Count_Large עם Is_Large.Generic_Count_IfCount_EvenPredicate = Is_EvenCount_LargePredicate = Is_Large12, 7, 88, 3, 56, 91, 44, 19, 62מספר הזוגייםכמה גדולים מ-50

בדוגמה הזו, מעבר על המערך, ניהול המונה, והחזרת התוצאה משותפים. רק «מה סופרים» מוזרק כ-function. זו הצורה הבסיסית של עיצוב higher-order ב-Ada.

10.4 דוגמת הרצה

with Ada.Text_IO;       use Ada.Text_IO;
with Generic_Count_If;

procedure Count_If_Demo is
   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);

   Data : constant Int_Array := (12, 7, 88, 3, 56, 91, 44, 19, 62);
begin
   Put_Line ("Even  =" & Natural'Image (Count_Even (Data)));
   Put_Line ("Large =" & Natural'Image (Count_Large (Data)));
end Count_If_Demo;
gnatchop ../src/snippets/05_filter.ada
gnatmake -gnata count_if_demo
./count_if_demo
Even  = 5
Large = 4

מתוך 9 האיברים ב-Data, הזוגיים הם 12, 88, 56, 44, 62 — חמישה; הגדולים מ-50 הם 88, 56, 91, 62 — ארבעה.

11. הרכבת כמה פרמטרים — key-value store גנרי

ברכיב אמיתי לעיתים רחוקות מספיק פרמטר טיפוס אחד. צריך לחבר טיפוס מפתח, טיפוס ערך, איך משווים מפתחות, ומספר רשומות מקסימלי.

כאן דוגמה של key-value store פשוט באורך קבוע.

פרמטרים ושימושים של Generic_KV_Storeה-store מקבל Key_Type, Value_Type, פונקציית שוויון מפתח ו-Max_Entries, ומשמש כמאגר הגדרות, cache קטן, או מילון באורך קבוע ל-embedded.Generic_KV_StoreKey_TypeValue_Typeפונקציית שוויון מפתחMax_EntriesPut / Get / Containsמאגר ערכי הגדרהcache קטןמילון באורך קבוע ל-embedded

11.1 Specification

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;

ל-package הזה ארבעה formal parameters.

פרמטר סוג תפקיד
Key_Type טיפוס טיפוס המפתח
Value_Type טיפוס טיפוס הערך
"=" subprogram בדיקת שוויון מפתח
Max_Entries ערך מספר רשומות מקסימלי

ל-Max_Entries יש ברירת מחדל := 50. אם לא מציינים, מקבלים store של 50 רשומות.

11.2 Body

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;

המימוש הוא linear search, ולכן לא מיועד לנפח גדול. אבל במקומות שבהם חשובים אורך קבוע, קנה מידה קטן, ובלי הקצאת זיכרון דינמית, הצורה נוחה.

Put ו-Get ב-Generic_KV_StorePut מחפש מפתח קיים או משבצת פנויה ומעדכן Keys Values Used; Get מחפש אינדקס ומחזיר את הערך.Keys/Values/Usedinstance של Generic_KV_Storeצד הקריאהKeys/Values/Usedinstance של Generic_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 דוגמת instantiation

with Ada.Text_IO;           use Ada.Text_IO;
with Ada.Strings.Unbounded; use Ada.Strings.Unbounded;
with Generic_KV_Store;

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
      Put_Line ("1 => " & To_String (Int_String_Store.Get (1)));
   else
      Put_Line ("1 => (not found)");
   end if;

   --  Put על מפתח קיים דורס את הערך
   Int_String_Store.Put (1, To_Unbounded_String ("Ada 2022"));
   Put_Line ("1 => " & To_String (Int_String_Store.Get (1)));

   if Int_String_Store.Contains (9) then
      Put_Line ("9 => " & To_String (Int_String_Store.Get (9)));
   else
      Put_Line ("9 => (not found)");
   end if;
end KV_Demo;
gnatchop ../src/snippets/06_kv_store.ada
gnatmake -gnata kv_demo
./kv_demo
1 => Ada
1 => Ada 2022
9 => (not found)

אם קוראים ל-Get בלי לבדוק קודם ב-Contains, כשאין מפתח נזרק Key_Not_Found. בחרו לפצל עם Contains כמו בדוגמה, או לכתוב exception handler.

"=" הושמט. ל-Integer יש אופרטור שוויון סטנדרטי, ו-is <> משתמש בו.

אם המפתח הוא מחרוזת בלי הבחנה בין אותיות גדולות לקטנות, אפשר להעביר function שוויון משלכם.

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. formal package parameter — generic כרכיב

ב-generics של Ada אפשר לקחת package שלם כ-formal parameter. כך «instance שנוצר מ-generic package מסוים» הופך לקלט של generic אחר.

Generic_Stack נכנס ל-Generic_Stack_LoggerInt_Stack שנוצר מ-Generic_Stack מועבר ל-Generic_Stack_Logger ויוצר instance של לוגר.Generic_StackInt_StackGeneric_Stack_LoggerInt_Stack_Logger_Instance

12.1 לוגר שמקבל stack

למשל, לוגר שמקבל instance של 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;

בצד השימוש יוצרים קודם stack, ואז מעבירים אותו ללוגר.

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

עם העיצוב הזה מחברים רכיבי generic זה לזה.

שתי שכבות של instantiationבשלב הראשון נוצר Int_Stack מ-Generic_Stack, ובשני Int_Stack_Logger מ-Generic_Stack_Logger עם Print_Size.שלב 2שלב 1Int_Stack_LoggerGeneric_Stack_LoggerInt_StackGeneric_StackPrint_Size

השימוש קרוב ל-template template parameters ב-C++, אבל ב-Ada כותבים במפורש «מקבלים instance של ה-generic package הזה». בקוד Ada גדול זה נוח כשמפרידים container, אלגוריתם, לוג, בדיקה ועזרים לטסטים, ואז מחברים.

13. Contract model — הרעיון הכי חשוב ב-generics של Ada

כדי להבין generics ב-Ada, חשוב ה-contract model.

גוף ה-generic חייב להיכתב רק עם הפעולות שה-formal parameters מבטיחים. אם הצהרתם רק type Element is private; אי אפשר להשתמש ב-< על Element. אם רוצים <, מוסיפים אותו כ-formal subprogram או מחדדים את קטגוריית הטיפוס.

contract model של generic ב-Adaה-formal part הוא החוזה, הגוף ממומש בגבולו ונבדק לבד, וב-instantiation בודקים שה-actual parameters מקיימים את החוזה.generic formal partהחוזהgeneric bodyמימוש בגבול החוזהבדיקת טיפוסים של הגוף לבדinstantiationactual parametersטיפוס, function וערך ממשייםבדיקה שה-actual parameters מקיימים את החוזהpackage או subprogram רגיל

העיצוב הזה מגן לא רק על מי שמשתמש ב-generic, גם על מי שכותב אותו.

13.1 איך זה נראה מול templates של C++

templates של C++ חזקים, אבל היסטורית «השגיאה מופיעה רק אחרי שעושים instantiate לגוף ה-template». C++20 concepts שיפרו את זה, אבל generics ב-Ada הם מודל שכותב חוזה במפורש מההתחלה.

Ada מול templates של C++ב-Ada כותבים חוזה ב-formal part ובודקים את הגוף לפני instantiation; ב-C++ הדרישות התגבשו היסטורית ב-instantiation, ועכשיו אפשר concepts.C++ templatesב-instantiation מתממשות דרישותכותבים template bodyאפשר לציין מגבלות ב-conceptsAdaהגוף נבדק בגבול החוזהכותבים חוזה ב-formal partב-instantiation בודקים את ה-actual

ב-generics של Java ו-C# מרכז העיצוב הוא טיפוסי reference, מגבלות, type erasure, והייצוג בזמן ריצה. generics ב-Ada נוטים יותר ליצירת instance ממשי בזמן קומפילציה.

זווית Ada C++ Java Rust
איך כותבים חוזה טיפוס, ערך, function ו-package ב-formal part templates / concepts פרמטרי טיפוס ו-bounds trait bounds
בדיקת הגוף בגבול חוזה ה-formal parameters בעיקר התממשות ב-instantiation בגבול ה-bounds בגבול ה-trait bounds
עלות בזמן ריצה פתרון סטטי כברירת מחדל יצירה סטטית כברירת מחדל מושפע מ-type erasure monomorphization כברירת מחדל
פרמטר ערך יש יש מוגבל const generics
subprogram כ-formal parameter יש function object וכדומה lambda / functional interface closure / function / trait
package כ-formal parameter יש template template וכדומה אין נפרד ממבנה המודולים

פרטי השפה שונים, אבל הייחוד של Ada הוא «כותבים את החוזה קודם, כתחביר».

14. החלטות עיצוב בפועל — מה כדאי להפוך ל-generic

generics נוחים, אבל לא כל דבר צריך להיות generic. בפועל, השיפוט הבא מפחית כשלונות.

עץ החלטה מה להפוך ל-genericלפי מה שמשתנה בוחרים פרמטר טיפוס, פרמטר ערך, formal subprogram, generic package, או subprogram רגיל.YesNoYesNoYesNoYesNoיש עיבוד שרוצים לעשות לו reuseרק הטיפוס שונה?שוקלים פרמטר טיפוסגם גודל או סף שונים?מוסיפים פרמטר ערךה-behavior של השוואה או בדיקה שונה?מוסיפים formal subprogramרוצים לארוז מצב פנימי ו-API?generic packageמספיק subprogram רגיל

14.1 מתי generic subprogram מתאים

generic subprogram מתאים לאלגוריתם בלי מצב.

  • Swap
  • Sort
  • Count_If
  • Find
  • המרה בסגנון Map
  • Min / Max

כשגוף האלגוריתם קצר והקלט והפלט ברורים, subprogram קריא יותר מ-package.

14.2 מתי generic package מתאים

generic package מתאים כשרוצים כמה פעולות ומצב פנימי יחד עם הטיפוס.

  • stack באורך קבוע
  • ring buffer
  • מילון קטן
  • סט פעולות סטטיסטיות
  • הפשטת I/O לפי device
  • סט פעולות על טיפוס מספרי עם יחידות

ב-Ada במיוחד, specification של package הוא ה-API הציבורי והגוף הוא המימוש. לכן generic package משמש כ«תבנית מודול type-safe».

פיצול spec, body ו-formal partה-formal part הוא חוזה הטיפוס הערך וה-function; ה-spec הוא API לקורא; ה-body מוסתר.מוסתרpackage specAPI ציבוריצד השימושpackage bodyמימוש פנימיgeneric formal partחוזה של טיפוס, ערך ו-function

14.3 מתחילים עם מעט formal parameters

יותר מדי formal parameters הופכים את ה-instantiation לקשה לקריאה. בטוח יותר להתחיל במינימום, ולהוסיף כשיש סיבה אמיתית להחלפה.

-- דוגמה שנהיית קשה לקריאה
package X is new Generic_Foo
  (A, B, C, D, E, F, G);

-- named association משאיר את הכוונה
package X is new Generic_Foo
  (Element_Type => Integer,
   Index_Type   => Positive,
   Buffer_Size  => 128,
   "<"          => Less);

ב-Ada אפשר named association ב-instantiation. נקודות העיצוב החשובות של generic מופיעות ב-instantiation, ולכן בקוד מעשי named association בדרך כלל קל יותר לתחזק.

15. מלכודות נפוצות

generics ב-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אם הגוף צריך השוואה כותבים function ב-formal part; עם private בלבד הקומפילציה של הגוף נכשלת.רוצים השוואה בגוףכותבים פונקציית השוואה ב-formal partב-instantiation בודקים שאפשר להשוותרק privateשגיאת קומפילציה בגוף ה-generic

15.2 is <> אינו «inference אוטומטי להכול»

is <> נוח, אבל זה לא קסם. בנקודת ה-instantiation חייב להיות אופרטור או subprogram תואם שנראה. אם פונקציית השוואה ייחודית יושבת ב-package אחר, בטוח יותר לעשות with / use כמו שצריך, או להעביר במפורש בשם.

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

15.3 לכל instance יש exception משלו

אם מצהירים exception ב-specification של generic package, לכל instance יש exception נפרד.

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

כאן Int_Stack.Stack_Overflow ו-Float_Stack.Stack_Overflow הם exceptions שונים. אם רוצים exception משותף, שוקלים להגדיר אותו מחוץ ל-generic.

exception נפרד לכל instanceStack_Overflow של Int_Stack ושל Float_Stack שנוצרים מאותו Generic_Stack הם exceptions שונים.exception אחרGeneric_Stackהצהרת Stack_OverflowInt_Stack.Stack_OverflowFloat_Stack.Stack_Overflow

15.4 גודל הקוד עלול לגדול

generics מקלים על הימנעות מ-indirection מיותר בזמן ריצה, אבל כי יוצרים instance לכל טיפוס, הרבה instantiations עלולים להגדיל את גודל הקוד.

זה אותו trade-off כמו templates ב-C++ ו-monomorphization ב-Rust. בפיתוח high-integrity, embedded, או real-time, מקבלים את ניהול גודל הפלט בזמן בנייה בתמורה להפחתת אי-ודאות בזמן ריצה.

כמה instantiations מגדילים קודגוף generic אחד יוצר גרסאות Integer Float Long_Float ו-My_Type; נמנעים מבדיקת טיפוס בזמן ריצה אבל הקוד גדל.גוף generic אחדגרסת Integerגרסת Floatגרסת Long_Floatגרסת My_Typeקוד שנוצרקל להימנע מבדיקת טיפוס ומ-boxing בזמן ריצהאם יש הרבה instances, לשים לב לגודל

15.5 מתי להשתמש ב-limited private

type Element is private; מניח השמה. ל-file handle, lock, device handle, ודברים שאינכם רוצים שיעתיקו, שוקלים limited private.

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

כשמטפלים בטיפוס שאי אפשר להעתיק, בטוח יותר אלגוריתם שמפעיל procedure, או עיצוב שמצהיר על reference, מאשר container ששומר ערכים.

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;
Generic_Min דורש פונקציית השוואהElement מגיע עם פונקציית השוואה ל-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;

פרמטר ערך מתאים לערך שרוצים לקבע כתכונה של ה-instance, לא כהגדרה בזמן ריצה.

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;

בצורה הזו מחליפים יעד פלט: stdout, לוג, buffer לטסטים.

הזרקת Put ב-Generic_Print_TwicePut מגיע כ-formal subprogram ואפשר לכוון אותו לקונסול, ללוג, או ל-buffer של טסט.Generic_Print_Twiceמקבלים Put כ-formal subprogramפלט לקונסולפלט ללוגbuffer לטסט

16.4 לא מקבעים את טיפוס האינדקס של המערך

ב-Ada גם טיפוס האינדקס של מערך הוא מידע טיפוס חשוב. במקום לקבע Positive, אם צריך לוקחים גם את טיפוס האינדקס כ-formal parameter, וה-reuse עולה.

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, גם מערך עם אינדקס enumeration.

Index כ-discrete typeאותו Index יכול להיות Positive, enumeration בשם Day או State, או טיפוס integer משלכם.Index is discretePositive rangeenumeration בשם Dayenumeration בשם Stateטיפוס integer משלכם

17. checklist ל-API שנראה כמו Ada

כשכותבים generic, בסוף עוברים על הנקודות האלה והקריאות עולה.

checklist לעיצוב genericבודקים מינימום formal parameters, פעולות ב-formal part, קטגוריה נכונה, named association, מצב ו-exception לכל instance, גודל קוד, ו-instance לטסט.בדיקת עיצוב genericה-formal parameters במינימום?הפעולות הדרושות כתובות ב-formal part?הקטגוריה private / range / digits מתאימה?אפשר instantiation קריא עם named association?מודעים למצב ול-exception לכל instance?אפשר לקבל גידול בגודל הקוד?יש instance לטסטים?

במילים:

  • כל פעולה שהגוף משתמש בה חייבת להופיע כחוזה של formal parameter.
  • אם private מספיק, משאירים private. אם צריך אריתמטיקה, range <> או digits <>.
  • behavior שמשתנה לפי טיפוס — השוואה, hash, פלט, המרה — הופכים ל-formal subprogram.
  • אם גודל או סף הם תכונה של ה-instance, הם פרמטר ערך.
  • עם מצב, קודם generic package; בלי מצב, קודם generic subprogram.
  • ב-instantiation, ככל שיש יותר ארגומנטים כך named association חשוב יותר.
  • מתכננים מתוך הנחה ש-exceptions ומצב פנימי עצמאיים לכל instance.

18. דוגמה למבנה הקבצים של הדוגמאות

אם מפצלים את הדוגמאות במאמר לקבצים, המבנה הבא קריא יותר.

פיצול דוגמאות ל-generics ול-demosתחת src יושבים generics עם ads ו-adb לכל רכיב, ו-demos עם תוכניות ההדגמה.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. לתחזוקה ארוכה ולעבודה מעשית, פיצול specification ב-.ads וגוף ב-.adb הוא המבנה שאופייני ל-Ada.

19. סיכום — גבולות ה-reuse נקבעים בטיפוסים

generic programming ב-Ada אינו רק «פיצ’ר לקוד שלא תלוי בטיפוס». הליבה היא לכתוב במפורש, כחוזה של טיפוסים, subprograms וערכים, מה רכיב ה-reuse דורש.

מחוזה עד reuse בלי העתקהכותבים חוזה, מממשים generic, עושים instantiate עם טיפוס ערך ו-function, ומשתמשים באופן type-safe בלי להעתיק קוד.כותבים חוזהכותבים את גוף ה-genericinstantiation עם טיפוס, ערך ו-functionשימוש type-safereuse בלי copy-paste

כפי שראינו, ב-generics של Ada אפשר לקחת כ-formal parameters את אלה.

  • טיפוס
  • ערך
  • subprogram
  • package

ועל טיפוס אפשר לציין קטגוריות דקות: private, limited private, range <>, mod <>, digits <>, delta <>, (<>). כך גוף ה-generic לא תלוי בפעולה ש«אולי קיימת», וממומש בבטחה רק עם מה שכתוב בחוזה.

בנכסי C ו-C++ ישן, reuse נעשה לפעמים במאקרו, void*, מצביעי functions, ופיצול טיפוסים ידני. generics ב-Ada מחליפים הרבה מהשימושים האלה בצורה type-safe וקריאה. במיוחד בתחזוקה ארוכה, embedded, real-time, ותוכנה high-integrity, לעיצוב שקובע גבולות בזמן קומפילציה יש ערך גדול.

20. תחומי ייעוץ קשורים

KomuraSoft LLC מטפלת בפיתוח אפליקציות Windows, חקירה ותיקון של נכסים קיימים, סידור גבולות COM / ActiveX / 32bit / 64bit, ייעוץ טכני וסקירת תכנון. לא רק עיצוב סטטי high-integrity כמו Ada, גם איך מסדרים נכסי C/C++, C#, VB6, MFC ו-COM קיימים כדי להאריך חיים או להגר — אלה נושאים קרובים בפועל.

מקורות

מאמרים עדכניים עם אותן תגיות, להעמקה בנושאים קרובים.

העמודים האלה ממקמים את הנושא בהקשר רחב יותר של שירותים והחלטות.

שאלות נפוצות

שאלות נפוצות בפניות בנושא המאמר.

מה הם generics ב-Ada?
מנגנון reuse שמקבל טיפוסים, ערכים, subprograms, ואפילו packages שלמים כ-formal parameters, ונבדק סטטית ברגע ה-instantiation עם new. זה לא החלפת טקסט. בזמן קומפילציה נקבע אם הרכיב מקיים את ה-contract. generic subprogram אי אפשר לקרוא רק כי הצהרת עליו; הוא הופך ל-procedure או function רגיל רק אחרי שנותנים טיפוס ממשי ועושים instantiation.
במה generics של Ada שונים מ-templates של C++?
Ada משתמשת מיום הראשון ב-contract model מפורש: גוף ה-generic נכתב רק עם הפעולות שה-formal parameters מבטיחים, והגוף עצמו נבדק לבד. templates של C++ היסטורית הראו שגיאה רק ב-instantiation; C++20 concepts שיפרו את זה. ב-Ada אפשר גם, מעבר לפרמטרי ערך ו-subprogram, לקבל package שלם כ-formal parameter ולחבר רכיבי generic זה לזה.
למה מציינים type category ב-formal type parameter של Ada?
כדי לכתוב במפורש, כ-contract, אילו פעולות הגוף רשאי להניח. ב-type T is private אפשר להניח בעיקר השמה והשוואה לשוויון, לא השוואת גודל ולא אריתמטיקה. אם צריך אריתמטיקה של integers משתמשים ב-range <>, אם צריך floating-point ב-digits <>, אם צריך פעולות על bits ב-mod <>. ציון הקטגוריה הוא גם מפרט ברמת הטיפוס לקורא: מה הרכיב דורש.
למה כדאי לשים לב ב-generics של Ada?
כי לכל טיפוס נוצר instance, מספר גדול של instantiations עלול להגדיל את גודל הקוד. זה אותו trade-off כמו templates ב-C++ ו-monomorphization ב-Rust. exception שמוצהר ב-specification של generic package הוא exception נפרד לכל instance. בפועל מתחילים עם מעט formal parameters, מוסיפים רק כשיש סיבה להחלפה, וב-instantiation עם הרבה ארגומנטים משתמשים ב-named association.

פרופיל הכותב

עמוד היכרות עם כותב המאמר.

Go Komura

מנהל KomuraSoft LLC

מתמחה בפיתוח תוכנה עבור Windows, ייעוץ טכני וחקירת תקלות, בעיקר בפרויקטים עם מערכות קיימות ובאגים שקשה לשחזר.

קישורים ציבוריים

חזרה לבלוג