אז מה בכלל יש לכם נגד לולאות?

10/04/2021

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

def double(arr):
    result = []
    for item in arr:
        result.append(item * 2)

    return result
def 

ולעומתה:

def mymap(f, arr):
    result = []
    for item in arr:
        result.append(f(item))

    return result

def double(arr):
    return mymap(lambda x: x * 2, arr)

וזו:

def double(arr):
    return map(lambda x: x * 2, arr)

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

1. עקרונות תכנות פונקציונאלי

ביקור בויקיפדיה מראה לנו את העקרונות הבאים של תכנות פונקציונאלי:

  1. פונקציות הן First Class Citizens

  2. העדפת פונקציות טהורות וביטויים טהורים

  3. רקורסיה

  4. הימנעות מ Side Effects ו Referential transparency

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

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

2. לולאת for

הלולאה הראשונה היא לולאת for שיכולה להופיע עם משתנה רץ או בתור לולאת for ... in. דוגמת הקוד הבאה מ JavaScript ממלאת מערך במספרים מ-0 עד 9 כולל:

const arr = [];
for (let i=0; i < 10; i++) {
    arr.push(i);
}

הקוד לא מתאים לגישה הפונקציונאלית בגלל שהביטוי בתוך ה for אינו ביטוי טהור: אם אריץ את הפקודה arr.push כמה פעמים תוצאת התוכנית כולה תהיה שונה.

כשמסתכלים על התמונה הגדולה שמים לב שהבעיה היא מהותית ללולאות for. בלולאת for אין ערך החזר ולכן כל מה שיקרה בתוך גוף הלולאה ישפיע על מידע חיצוני או ייצור Side Effect. ב Python המצב עוד יותר מוזר כי משתנה שמוגדר כחלק מלולאת for נשאר פעיל בתוכנית גם אחרי הלולאה, כלומר הקוד הבא מדפיס 9:

for i in range(10): pass

print(i)

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

3. לולאת while

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

4. רקורסיה

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

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

def create_array(count):
    if count == 0:
        return []

    return [*create_array(count - 1), count - 1]

arr = create_array(10)
print(arr)

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

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

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

arr = []

def init(count=0):
    if count >= 10:
        return

    arr.push(count)
    init(count + 1)

init()
print(arr)

5. הרכבת רשימות

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

אליקסיר היא שפה פונקציונאלית אהובה עליי שבין השאר לא מאפשרת כלל עדכון של מידע אחרי שנוצר, כלומר כל המידע הוא Immutable. התחביר שלהם להרכבת רשימות דווקא משתמש במילה for אבל בצורה מעניינת. הקוד הבא מאתחל ומדפיס מערך באליקסיר מריבועי המספרים מ-0 עד 9:

arr = for i <- 0..9, do: i * i

IO.inspect(arr)

ב Elixir, כמו בשפות פונקציונאליות רבות, המילה for לא מתפקדת כפקודת Flow Control ללא ערך החזר אלא בתור פונקציה לכל דבר: פונקציה שמקבלת פרמטרים ומחזירה ערך שהוא מערך. למרות הכתיב המשונה, אין שום דרך להשתמש ב for כמו בדוגמת ה JavaScript הראשונה ובכל איטרציה להוסיף משהו למערך, פשוט בגלל שבאליקסיר אנחנו לא משנים מערך מרגע שיצרנו אותו. אבל הדבר החשוב הוא מה הקוד כן נותן לנו - בכתיב הרכבת רשימות אין קשר בין "איטרציות" שונות של הלולאה ובעצם אפשר לדמיין שהשפה מפעילה את כל 10 החישובים במקביל. אנחנו לא בונים משהו בהדרגה אלא מריצים 10 חישובים ומשלבים את כל 10 התוצאות. והדבר החשוב, הקוד שבתוך המבנה לא משפיע על המידע שחיצוני לו, כמו ברקורסיה ולא כמו בלולאות ה for וה while המסורתיות.

אגב הרכבת רשימות הוא מבנה פופולרי בהרבה שפות כך למשל אותו קוד נראה בפייתון:

arr = [i * i for i in range(10)]
print(arr)

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

arr = []
[arr.append(i) for i in range(10)]
print(arr)

6. פונקציית map

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

הנה הקוד ב JavaScript שמייצר מערך של ריבועי המספרים מ-0 עד 9:

const arr = new Array(10).fill(0).map((_, i) => i * i);

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

7. לסיכום

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

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

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