• בלוג
  • קוד פרוצדורלי וקוד פונקציונאלי נפגשו לצהריים

קוד פרוצדורלי וקוד פונקציונאלי נפגשו לצהריים

21/09/2018

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

1. גירסא פרוצדורלית - חישוב גורמים ראשוניים של מספר

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

הנה דוגמא עבור המספר 18: נתחיל עם חלוקה ב-2 ונקבל 9. את ה-2 נרשום בצד. אחרי זה את 9 כבר אי אפשר לחלק ב-2 אז עוברים לחלק ב-3. תשע חלקי שלוש נותן 3 אז את 3 נרשום בצד ופעם שניה 3 מתחלק ב-3 ונותן 1 אז נרשום אותו שוב בצד. סך הכל קיבלנו ש-18 מורכב מ 2, 3 ו-3.

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

def factors_for(number)
  i = 2
  res = []

  while i < number
    while number % i == 0
      res << i
      number /= i
    end
  i += 1
  end

  res
end

puts factors_for(18).inspect

בואו ננסה לכתוב לו טבלת מעקב כזו: המשתנים שלנו הם number, i ו res. בכניסה לפונקציה ערכיהם:

number: 18
i: 2
res: []

נכנס לתוך לולאה ה while הפנימית וקל לראות ש number כלומר 18 מתחלק ב i שהוא 2. מוסיפים ל res את i ומחלקים ובסיום האיטרציה הראשונה נקבל:

number: 9
i: 2
res: [2]

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

2. גירסא פונקציונאלית - חישוב גורמים ראשוניים של מספר

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

כך נראה אותו הקוד בגירסת האליקסיר:

defmodule PrimeFactors do
  def factors_for(number, i \\ 2) do
    cond do
      number < i ->
        []

      rem(number, i) == 0 ->
        [i|factors_for(div(number, i), i)]

      true ->
        factors_for(number, i + 1)
    end
  end
end

IO.inspect PrimeFactors.factors_for(18)

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

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

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

תחילה הפונקציה factors_for מופעלת עם הערכים:

number: 18
i: 2

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

rem(number, i) == 0 ->
        [i|factors_for(div(number, i), i)]

המספר 18 מתחלק ב-2 ולכן אנחנו בתנאי של החלוקה. במצב כזה הפונקציה תחזיר רשימה שמורכבת מהאיבר i כלומר 2 ואחריו תוצאת הפעלת הפונקציה על חלוקת number ב i. זאת הדרך הפונקציונאלית לרשום "בצד" את המספר 2.

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

number: 9
i: 2

זכרו שיש לנו בצד את 2 כי כשנצא מההפעלה הפנימית הזו של הפונקציה ה-2 שרשמנו בצד יחכה לנו. הפעם אף אחד משני התנאים הראשונים לא מתקיים ולכן אנחנו מגיעים למצב השלישי:

true ->
        factors_for(number, i + 1)

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

number: 9
i: 3

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

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

defmodule PrimeFactors do
  def factors_for(number, i \\ 2, res \\ []) do
    cond do
      number < i ->
        res

      rem(number, i) == 0 ->
        factors_for(div(number, i), i, [i | res])

      true ->
        factors_for(number, i + 1, res)
    end
  end
end

IO.inspect PrimeFactors.factors_for(18)

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

יש אנשים שיטענו שקוד פונקציונאלי יותר קל לקריאה וכתיבה וכאלה שיטענו הפוך. מה שבטוח שבגלל שבקוד פונקציונאלי כל המשתנים הם Immutable יהיה לנו הרבה יותר קל למקבל תהליכים או להוסיף אופטימיזציות בהשוואה לגישה פרוצדורלית. בדוגמא של קוד שמחשב גורמים ראשוניים מה היה קורה אם היינו שומרים בצד אוסף של מספרים ידועים ואת הגורמים הראשוניים שלהם? בגישה הפונקציונאלית מאוד קל לעשות את זה ומאוד ברור מה עושים עם הערכים ששמרנו בצד. אם אתם כבר יודעים מה פונקציה מסוימת תחזיר על קלט מסוים אתם יכולים לחסוך את החישוב ופשוט להשתמש בערך השמור (זה נקרא Memoization). בגישה הפרוצדורלית לעומת זאת היה עלינו לחשוב מה עושים עם הערך ואיך משלבים את הערך ששמרנו בחישוב ואיך זה משפיע על כל שאר המשתנים. בחישוב גורמים ראשוניים די ברור מה לעשות אבל לא בטוח שזה יהיה כך במקרה הכללי.