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

1. ניסיון ראשון: מציאת גורמים ראשוניים ברקורסיה

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

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

function factors_of(number, i=2) {
  if (number < i) {
    return [];
  }

  if (number % i === 0) {
    return [i, ...factors_of(number / i, i)];
  }

  return factors_of(number, i+1);
}

וזה עובד. כמעט. הנה הקודפן:

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

2. השגיאה ומשמעותה

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

Uncaught RangeError: Maximum call stack size exceeded

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

שפות מסוימות מציעות לנו דרך מילוט מהמגבלה על הרקורסיה - דרך שנקראת Tail Call Optimisation או בקיצור TCO.

נסתכל שוב על הקריאה הרקורסיבית בקוד:

  if (number % i === 0) {
    return [i, ...factors_of(number / i, i)];
  }

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

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

"use strict";

function factors_of(number, i=2, res=[]) {
  if (number < i) {
    return res;
  }

  if (number % i === 0) {
    return factors_of(number / i, i, [...res, i]);
  }

  return factors_of(number, i+1, res);
}

$('button').on('click', function() {
  const res = factors_of(Number($('input').val()));
  $('.result').text(res);
})

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

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

רקורסיה שלא צריכה להשתמש במחסנית כדי לזכור מידע נקראת רקורסיית זנב. התכונה של שפת תכנות שלא צריכה לשמור את כל שרשרת הקריאות במחסנית ברקורסיית זנב נקראת Tail Call Optimisation או בקיצור TCO.

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

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

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

3. בונוס: מימוש האופטימיזציה בעצמנו בשפת JavaScript

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

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