פולימורפיזם (תוכנה)

מתוך ויקיפדיה, האנציקלופדיה החופשית

פולימורפיזם (בעברית: "רב צורתיות") הוא מנגנון המאפשר כתיבת תוכנה ברמות הפשטה שונות. המנגנון מהווה חלק חשוב במתודולוגית תכנות מונחה עצמים.

[עריכה] הרעיון הבסיסי

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

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

[עריכה] דוגמאות

כדי להדגים את הכוח של המנגנון, אפשר לחשוב על דוגמה שכיחה מחיי היום יום, אלגוריתם להחלפת גלגל ברכב:

1. עצרו בצד והציבו סימנים המיידעים שהרכב בטיפול.
2. הציבו את המגבה במקומו ושחררו מעט את ברגי הגלגל.
3. הגביהו את הרכב בעזרת המגבה.
4. פרקו את הגלגל והרכיבו במקומו גלגל תקין.
5. חזקו מעט את הברגים.
6. הנמיכו את הרכב עד שהגלגל יגע קלות בקרקע.
7. חזקו את ברגי הגלגל בהצלבה.
8. הנמיכו את הרכב, איספו את הכלים והמשיכו בנסיעה.

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

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

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

1. בחרו וקטור כלשהו ונרמלו אותו.
2. בחרו וקטור נוסף והטילו אותו על תת המרחב הנפרש על ידי הווקטורים שכבר בחרתם.
3. מצאו את ההפרש בין הווקטור להטלה שלו, נרמלו אותו והוסיפו אותו לרשימת הווקטורים שכבר נבחרו.
4. חיזרו על הפעולות 2 ו 3 עד שיגמרו הווקטורים בבסיס המקורי. רשימת הווקטורים שנבחרו מהווה בסיס אורתונורמאלי למרחב.

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

[עריכה] מימוש בתכנות

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

class Car {...};

class Bus: public Car{...};

class PrivateCar: public Car{...};

void changeWheel(Car *p) {
    p->stop();
    p->placeJack();
    p->lift();
    ...
}

int main() {
   Car* array[3];
   array[0]=new Bus();
   array[1]=new PrivateCar();
   array[2]=new Bus();
   for(int i=0;i<3; ++i)
   changeWheel(array[i]);
}

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

הפונקציה מקבלת מצביע למכונית כללית. למעשה מדובר בסוג מסוים של מכונית, מכונית ספציפית, אבל changeWheel מתייחסת אליה פשוט כמכונית ומבצעת עליה רק פעולות שאפשר לעשות על כל מכונית. כאשר changeWheel תבקש ממכונית לעשות פעולה מסוימת, המכונית תבצע את הפעולה באופן ייחודי לה. ניתן לראות שהממשק למכונית מוגדר על ידי ההתייחסות המופשטת (המצביע למכונית כללית) ואילו הפעולה שתתבצע למעשה מוגדרת על ידי הטיפוס הספציפי (סוג המכונית).

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

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

ב - ++C , פולימורפיזם של זמן קומפילציה ממומש על ידי template:

class Bus {...};
class PrivateCar {...};

template<typename Car>
void changeWheel(Car car){
   car.stop();
   car.placeJack();
   car.lift();
   ...
}

int main() {
   Bus bus;
   PrivateCar pcar;
   changeWheel(bus);
   changeWheel(pcar);
}

כפי שניתן לראות, ניתן לקרוא לפונקציה changeWheel עם סוגים שונים של רכבים. עבור כל סוג נפרשות בזמן קומפילציה הפונקציות המתאימות.

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

[עריכה] מימוש פולימורפיזם על־ידי המהדר

נתבונן שוב בקטע הקוד המממש פולימורפיזם בזמן ריצה:

   p->stop();
   p->placeJack();
   p->lift();
   ...

נשאלת השאלה כיצד מתורגם קטע זה לשפת מכונה. לדוגמה הפעלת הפונקציה stop:

   p->stop(); 

בניגוד להפעלת פונקציה רגילה, בזמן הקומפילציה לא ידוע איזה קוד יש להפעיל. האם מדובר ב -() Bus::stop ,ב -() PrivateCar::stop או אולי פונקציית stop של טיפוס אחר. התשובה לשאלה זו מתבררת רק בזמן ריצה, כאשר ידוע על איזה טיפוס ספציפי מצביע p. הקומפיילר, אם כן, צריך לייצר קוד הקורא לפונקציה מסוימת בהתאם לטיפוס האובייקט שמוצבע על ידי p באותו הרגע. בכדי לייצר קוד כזה, יש להתייחס לקוד הנמצא בכתובת משתנה. במילים אחרות יש להשתמש במושג של מצביע לפונקציה.

הקוד הבא מדגים איך אפשר לממש polymorphism בשפת C, שפה שלא תומכת ב - polymorphism באופן מובנה:

#include <malloc.h> 
#include <stdio.h> 
 

typedef void (*fun_t)(void);   

typedef struct Car {  
  fun_t stop; 
  /* fun_t placeJack, lift, ... */ 
} Car; 

Car* createCar(fun_t stopFunction) {/*fun_t placeJackFunction, fun_t liftFunction,...*/
  Car *p = (Car*)malloc(sizeof(Car)); 
  p->stop = stopFunction;
  /* p->placeJack = placeJackFunction; p->lift = ... */
  return p; 
 }

void busStop() { printf("Stopping the bus...\n"); }
/* void busPlaceJack() {...} void busLift() {...} ... */
Car* createBus() { return createCar(busStop); } 

void privateStop() { printf("Stopping the private car...\n"); }
/* void privatePlaceJack() {...} void privateLift() {...} ... */
Car* createPrivate() { return createCar(privateStop); } 

void changeWheel(Car *car) {
  car->stop(); 
  /* car->placeJack(); car->lift();... */
}

int main() {
  Car *p1 = createBus(), *p2 = createPrivate();
  changeWheel(p1);
  changeWheel(p2);
  /* free memory .. */ 
  return 0; 
}

הדוגמה האחרונה פשטנית במקצת. היא מתחמקת מבעיות טכניות שונות המופיעות באובייקטים פחות מנוונים מאלה שבדוגמה. בנוסף, ניתן לראות שהשיטה המוצגת בדוגמה, בזבזנית בזיכרון. עבור כל אובייקט (מכונית) יש לשמור מספר מצביעים לפונקציות כמספר הפונקציות שיש למכונית. אותם מצביעים לפונקציות יכולים להוות את רוב הזכרון הדרוש לאיכסון האובייקט. בזבוז הזיכרון נובע מהעובדה, שאוסף הפונקציות עליהם מצביע האובייקט הוא מאפיין של ה - class ולא של האובייקט הספציפי. לדוגמה, לכל האובייקטים מסוג Bus יהיו בדיוק אותם ערכים בכל מצביעי הפונקציות שלהם.

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

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

p1.placeJack()

יתורגם לקוד הדומה לקוד הבא:

p1.m_vtbl_ptr[2]()

כפי שניתן לראות, קיימת כאן הסתמכות על העובדה שהפונקציה placeJack נמצאת תמיד באותו אינדקס, בכל הטבלאות הווירטואליות (במקרה זה - 2).

[עריכה] מחיר פולימורפיזם הממומש על ידי virtual table

מבחינת זיכרון, כאשר ל - Class יש לפחות פונקציה פולימורפית (וירטואלית) אחת, כל אובייקט מסוגו יכיל מצביע virtual table pointer. עבור אובייקטים גדולים הדבר עשוי להיות זניח אבל עבור אובייקטים קטנים, במיוחד אם יש מופעים רבים שלהם, הדבר עלול להיות משמעותי.

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

באופן כללי, נהוג להתייחס לשימוש בפונקציות פולימורפיות כטכניקה יעילה.

[עריכה] קישורים חיצוניים

• הרצאה על פולימורפיזם במסגרת קורס שניתן באוניברסיטה העברית.