ארכיון חודשי: יוני 2015

recursive tail

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

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

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

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

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

הגישה המוכרת ביותר לכך נקראת tail recursion. או רקורסיית זנב בעברית טכנית.

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

מה הכוונה? אשתמש בקוד רובי (שהוא לדעתי קריא מאוד) לשם כך.

רקורסיה בגישה ה"רגילה" תהיה כתובה כך:

def recursive(n)
  if n <= 1
    1
   else
     n * recursive(n - 1)
   end
end

recursive(4)
=> 24

רקורסיית זנב, תראה כך:

def tail_recursive(current, n, result)
  return result if current <= n

  new_result = result * current
  tail_recursive(current + 1, n, new_result)
end

tail_recursive(1, 4, 1)
=> 24

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

אבל לא הכל ורוד בזה. קשה יותר לדבג בעיות ברקורסיית זנב, היות ולמעשה אין לנו stack frames רבים, שיהיה ניתן להבין באיזה שלב יש בעיה. ובכך אין לנו stack trace שיסייע לנו בנושא.

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

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

חשיבה מופשטת

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

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

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

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

תיאור זה מה שhtml עושה מצויין. למשל יש את כל הנושא של aria, המתארת איך להסביר מה בעצם לבצע עם הטאגים, המידע והאלמנטים בכלל עבור קוראי מסך (למשל), וכך למשל הטאג של role מסביר מתוך aria שה ul שיש לנו, הוא בעצם תפריט ולא bullet point, כי לעיצוב אין משמעות, וה div ההוא זה בעצם חלון דיאלוג, וביחד עם שאר ה aria, אני יכול להגיד כי ברירת המחדל שלו, הוא מוסתר.

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

אבל זה לא הכל. גם לעיצוב בhtml יש תיאור, למשל בשביל להגיד שcss הוא עבור המסך. זה נקרא media types.

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

אני מסביר לדפדפן כי הדף שנטען הוא למשל בקידוד של UTF-8, ואני מסביר לדפדפן כי אסור לו לבצע זום.

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

וזה הכיוון שאני חשבתי עליו כאשר דיברתי על מה אני הייתי רוצה ש HTML יבצע.

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

מה זה מאפשר לנו להשיג אם זה בhtml (ולא, זה לא דומה אפילו לתכנות)?
דבר ראשון, זה אומר שאנחנו טוענים פחות מידע. למשל יש עכשיו את פרוטוקול HTTP/2. הפרטוקול אומר כי בגלל שיש המון מידע שצריך להטען, במקום לחכות לכל המידע הזה, אני אכניס הכל בבקשה אחת ואצור multiplexing.
טעינה של המון לוגיקה ב Javascript, טעינה של המון CSS שלא לדבר על תוכן שאולי רק לא יוצג ב HTML, כולם יוצרים בעיות ביצועים. אך במידה ואנחנו נוכל לטעון רק את המידע הרלוונטי כאשר הוא רלוונטי בלבד, אז למעשה כמות המידע ירד, ולמרות ש HTTP/2 הוא נחמד, עדיין אשיג אופטימיזציה מצויינת רק מעצם זה שאני לא טוען מידע שאני לא זקוק לו.

אז איך ניתן להשיג את כל זה בלי תכנות? סתם רעיון, לא באמת הדרך הנכונה:

<div src="/foo.html" alt="no content" media="(max-wdith: 640px and max-height: 480px)">

הנה עוד בעיה, אתרים עובדים עם bootstrap בגרסה 3.3.4 (לצורך ההדגמה בלבד), ובאתר הראשון שנכנסתי אליו שמשתמש בו, אני מקבל עותק מקומי שעשה minified אבל למעט ה copyright נמחקו כל ההערות בפנים.
האתר השני בכלל משתמש ב cdn. האם הדפדפן שלי ידע כי מדובר באותה גרסה בדיוק? לא! אבל מה אם אוכל לתאר לו שזה המצב? האם זה לא יוסיף לי אופטימיזציה? האם זה לא יוסיף לי מהירות של חוסר טעינה מחודשת של המידע? האם זה לא יוריד את כמות התעבורה לטעינת bootstrap בגרסה זו?

הנה הדגמה גם לזה:

<link href="/styles/bootstrap.min.css" rel="stylesheet" provides="bootstrap" ver="3.3.4">

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

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

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

מעניין איך תפתרו את ה"תרגיל" למעלה …