כיצד לומדי תכנות פונקציונלי מפרשים פונקציות רקורסיביות

י. סגל

Segal, J. (1995). Empirical studies of functional programming learners evaluating recursive functions. Instructional Science 22, 385-411.

התקציר המצורף נערך ע"י ד"ר דלית לוי

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

הוצאת "מחשבה" – מרכז המורים הארצי למדעי המחשב, 2001. עמודים 72-77.

 

אודות המאמר

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

 

רשימת מושגים

w אסטרטגית חישוב מושהה – Delayed evaluation

w אסטרטגית חישוב מיידי – Immediate evaluation

w חישוב מושהה מלמעלה למטה - Top-down delayed evaluation

w חישוב מושהה מלמטה למעלה - Bottom-up delayed evaluation

w יחס של התרחשות חוזרת (יחס רקורסיבי) - Recurrence relation

w שפת תכנות פונקציונלית –Functional programming language

w תפיסות שגויות –Misconceptions

 

הקדמה

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

הרקע למחקר

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

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

אפשר לראות רקורסיה ככלי שמאפשר להגדיר פונקציות הפועלות על תחום אינסופי של משתנים בצורה תמציתית, "מכווצת". פונקציות רקורסיביות מתוארות במונחים של תנאי עצירה מצד אחד, ושל יחס התרחשות חוזרת   (recurrence relation) מצד שני. למשל, אם התחום של הפונקציה f הוא קבוצת המספרים הטבעיים שיסומנו ב- n, תנאי העצירה יכול להיות הערך של הפונקציה כאשר n=0, כלומר הערך של f(0). יחס ההתרחשות החוזרת במקרה זה יבטא את האופן שבו הפונקציה f(n) מתייחסת ל- f(p), כאשר p מספר טבעי קטן מ- n. דוגמה נפוצה היא הדוגמה של פונקצית העצרת fact. הייצוג המתמטי הרקורסיבי של פונקציה זו נתון כך: fact(0) = 1 - זהו תנאי העצירה. יחס ההתרחשות החוזרת הוא fact(n)=n*fact(n-1) כאשר n>0. הייצוג הרקורסיבי של פונקצית העצרת בשפת תכנות פונקציונלית כמו מירנדה לא שונה בהרבה:

Fact n = 1                               if n = 0

            = n * fact (n-1)              if n > 0

 

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

 

Fact 2   = 2 * fact (1)

            = 2 * 1 * fact (0)

            = 2 * 1 * 1

            = 2 * 1

            = 2

 

במאמר של קהני  [Kahney 1989, המופיע אף הוא בסקר ספרות זה – ד"ל], מוצגת גישה אחרת לתיאור רקורסיה, תוך שימת דגש על תהליך הביצוע של הפונקציה הרקורסיבית ולא על רקורסיה ככלי להגדרת פונקציות. במונחים אלה של תהליך הביצוע, אם נניח שהמחשב "יודע" את ההגדרה של פונקצית העצרת ועליו לבצע חישוב של fact 2 , אזי מה שיתרחש הוא ש fact 2  תזמן את fact 1  אשר תזמן את fact 0 – כל אלה זימונים של העתקים חדשים של הפונקציה המקורית fact. הזימון האחרון יחזיר תוצאה ל – fact 1 ולאחר מכן תוחזר תוצאה לזימון המקורי של fact 2. גישה נוספת לרקורסיה, היא כאל טכניקה לפתרון בעיות. על פי גישה זו, פתרון בעית העצרת מתקבל מפירוק הבעייה המקורית (של חישוב fact n ) לתת-בעייה פשוטה יותר מאותו סוג. המקרה הבסיסי נחשב לתת-הבעייה הפשוטה ביותר שאותה ניתן לפתור ישירות, בלי צורך להזדקק לפירוק נוסף.

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

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


 


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

ממצאים

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

תפיסה מוטעית בולטת: המקרה הבסיסי כתנאי העצירה

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

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

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

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

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

  g (L) = first(L) + g (tail (L) ) + first(L)   .

במקרה כזה, יש סטודנטים שחושבים שהערך של L במרכיב השלישי (הימני ביותר) של הביטוי משתנה לאחר שהתבצע המרכיב השני. באופן זה, אם הרשימה L היתה בהתחלה [1 5 3] , אז המרכיב הראשון בביטוי יחזיר את המספר 1, אבל במרכיב השני קוצצים את ראש הרשימה ונשארת הרשימה [5 3], ולכן – לפי התפיסה המוטעית – מה שיחזיר המרכיב השלישי בביטוי הוא המספר 5.

g (L) = first (L) + g (tail (L) ) + first (L)

      L= [1 5 3]      L= [1 5 3]        L= [5 3]

    first(L)=1       tail(L)=[5 3]    first(L)=5

[הייצוג כאן הוא תרגום מייצוג בשפת מירנדה לייצוג שיהיה בהיר יותר לקוראים. משמעות first   היא המספר הראשון ברשימה, ומשמעות  tail  היא הרשימה ללא המספר הראשון שלה – ד"ל].

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

ההשפעה של אסטרטגית החישוב

ממצא נוסף מהמחקרים קשור בהשפעתן של האסטרטגיות בהם השתמשו הלומדים לחישוב ערכן של פונקציות רקורסיביות על הביצועים של הסטודנטים שהשתתפו במחקרים. מהתצפיות מתברר כי הסטודנטים משתמשים בשתי אסטרטגיות בולטות לחישוב: חישוב מושהה (delayed evaluation) וחישוב מיידי (immediate evaluation). האסטרטגיה הראשונה דומה לחיפוש לרוחב (breadth first): הסטודנטים מחשבים ומציבים את ערכן של כל הפונקציות המרכיבות את ההגדרה, פרט לערך של הקריאה הרקורסיבית לפונקציה – שחישוב ערכה מושהה. במלים אחרות, הם רואים את הערך של הפונקציה בכל נקודה כביטוי שלם, שיתכן וחלק ממרכיביו עדיין לא חושבו. בחישוב מיידי, לעומת זאת, החישוב מתקדם משמאל לימין, כאשר חישוב הערך של קריאה רקורסיבית מתבצע מיד כשנתקלים בקריאה כזו. אסטרטגיה זו דומה יותר לחיפוש לעומק (depth first).

בתרשים הבא מושוות שתי האסטרטגיות לחישוב הפונקציה הרקורסיבית הבאה –

f(n) = n + f(n-1) + n

f(1) = 2

החיצים בתרשים מייצגים את סדר החישוב, במקרה של הפעלת הפונקציה כאשר n=3.

 

        חישוב מושהה                                                                                 חישוב מיידי

 f (3) = 3  +                                + 3                                           f (3) = 3 +   f (2)  + 3

                   2  +           + 2

                             2                                                                             2 + f (1) + 2

 

                                                                                                                    2

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

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

סיכום

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

חזרה לאתר המרכז הארצי

חזרה להבטים ינואר 2002

חזרה לאתר סקר ספרות