פרוייקט "התלמיד והמחשב", בעיה 10

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

הבעיה היא לקבל כקלט פרמטרים שמגדירים סדרה חשבונית או הנדסית, ולהוציא את סכום הסדרה כפלט. בואו נזכיר מה אלו הסדרות הללו. בשני המקרים מדובר על סדרות של מספרים (ואני מניח בפתרונות שלי שאלו אפילו מספרים שלמים) מאורך סופי כלשהו שמסומן ב-\( n \). את הסדרה עצמה אפשר לסמן, למשל, כך: \( a_0, a_1, a_2, \dots, a_{n-1} \). שימו לב שאני מתחיל את מספור האיברים מ-0 ולכן האינדקס של האיבר האחרון הוא \( n-1 \). לסדרה חשבונית יש את התכונה המיוחדת שההפרש בין כל שני איברים סמוכים בה הוא מספר קבוע שמסומן ב-\( d \); לסדרה הנדסית יש את התכונה שהמנה של כל שני איברים סמוכים בה היא מספר קבוע שמסומן ב-\( q \). שלושת הפרמטרים של מספר האיברים בסדרה, האיבר הראשון בה וההפרש/מנה הקבוע מאפיינים באופן מוחלט את הסדרה: מאוד קל לראות שהאיבר מספר \( i \) בסדרה חשבונית הוא \( a_0+id \) והאיבר מספר \( i \) בסדרה הנדסית הוא \( a_0q^{i} \).

עכשיו, מה שמבקשים מאיתנו למצוא הוא את סכום האיברים בסדרה, כלומר את \( a_0+a_1+\dots+a_{n-1} \). בעולם האמיתי יש נוסחאות פשוטות שמחזירות את הסכום הזה: \( n\left(a_0+\frac{d(n-1)}{2}\right) \) עבור סדרה חשבונית ו-\( a_0\frac{q^n-1}{q-1} \) עבור סדרה הנדסית. לא קשה להוכיח שהנוסחאות הללו עובדות אבל לא אעשה את זה כרגע כי זה פוסט על תכנות ולא על טורים; הנקודה היא שאני בכלל לא הולך להשתמש בנוסחאות הללו. אני רוצה לחשב את הסכומים בדרך הקשה - לחשב איבר-איבר, ולקחת את הסכום שלהם.

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

sum = 0
case ARGV[0]
when "A"
  a0, d, n = ARGV[1].to_i, ARGV[2].to_i, ARGV[3].to_i
  for i in (0...n) do
    sum = sum + a0+i*d
  end
when "G"
    a0, q, n = ARGV[1].to_i, ARGV[2].to_i, ARGV[3].to_i
    sum = (0...n).collect{|i| a0*q**i}.inject(0){|temp_sum, x| temp_sum + x}
end

puts "The sum is #{sum}"

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

כשאני אומר שהבדיקה היא האם הערך של המשתנה שווה לערך של מה שמופיע אחרי ה-when אני משקר בצורה גסה וגורם למשפטי case להיות הרבה פחות מגניבים ממה שהם. בפועל רובי לא משתמשת באופרטור ההשוואה הרגיל כדי לבצע את ההשוואה אלא באופרטור מיוחד, שמסומן בתור ===, כדי לבצע את ההשוואה, וזה אומר שאפשר לעשות יותר מאשר להשוות שני ערכים: אפשר אחרי ה-when לכתוב טווח של ערכים או סדרה של ערכים והתנאי יתקיים אם הערך שמכיל המשתנה משתייך אליהם; אפשר לכתוב ביטוי רגולרי והתנאי יתקיים אם המחרוזת שהמשתנה מכיל מתאימה לו; אפשר לכתוב מחלקה והתנאי יתקיים אם המשתנה הוא אובייקט ששייך למחלקה הזו… בקיצור, דברים מגניבים למדי (שייתכן מאוד שנשמעו לכם כרגע כמו ג’יבריש, וזה למה אני לא נכנס אליהם). ברובי משפטי case הם דברים מעולים ואני מאוד מחבב אותם. בשפות כמו C הם קצת יותר מושמצים ונדבר על זה כשנגיע לג’אווהסקריפט.

חישוב הסכום כשהסדרה היא חשבונית (מזהים את זה על ידי כך שהפרמטר הראשון שהתוכנית קיבלה היה “A”) הוא בנאלי ולא ארחיב עליו (נסו לראות שאתם מבינים מה אני עושה שם!). מה שמעניין הוא חישוב הסכום כשהסדרה היא הנדסית, שנעשה כולו בשורה ארוכה אחת:

sum = (0...n).collect{|i| a0*q**i}.inject(0){|temp_sum, x| temp_sum + x}

מה שקורה כאן הוא דבר די נפוץ ברובי. אנחנו מתחילים מאובייקט שהוא אוסף של מספרים - במקרה הזה, כל המספרים בין 0 ל-9, שמיוצגים על ידי אובייקט של טווח, ואז מתחילים לעשות על האובייקט הזה סדרה של פעולות. הפעולה הראשונה היא collect שמחליפה כל מספר בטווח באיבר המתאים בסדרה ההנדסית. קיבלנו מערך שכולל את כל האיברים בסדרה ההנדסית, ונותר לסכום אותו. לצורך כך אנחנו מגייסים את המתודה inject שפועלת כך: בנוסף למערך שקורא לה היא מקבלת כקלט גם פרמטר נוסף, שבמקרה הזה הוא 0, שהוא “הערך ההתחלתי”, ובלוק. בתוך הבלוק ישנם שני משתנים, שאני קורא להם temp_sum ו-x. הרעיון הוא כזה: ראשית inject מאתחלת את temp_sum להיות הערך שהועבר לה - 0 במקרה שלנו. כעת היא עוברת סדרתית על כל אברי המערך, מציבה כל אחד מהם בתוך x, מריצה את הבלוק ומציבה בתוך temp_sum את תוצאת הבלוק, שהיא במקרה הנוכחי הערך temp_sum+x. כל זה מתורגם לסכימה של איברי המערך ולכן להחזרה של התוצאה הנכונה.

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

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

import System.Environment

arithmetic_series_sum :: Int -> (Int -> (Int -> Int))
arithmetic_series_sum a0 d n = foldl (+) 0 [a0 + d*i | i <- [0..n-1]]

geometric_series_sum :: Int -> (Int -> (Int -> Int))
geometric_series_sum a0 q n = foldl (+) 0 [a0 * q^i | i <- [0..n-1]]

series_sum :: [String] -> Int
series_sum ("A":a0:d:n:[]) = arithmetic_series_sum (read a0) (read d) (read n)
series_sum ("G":a0:q:n:[]) = geometric_series_sum (read a0) (read q) (read n)

main = do
  args <- getArgs
  putStrLn (show(series_sum args))

כל החלק עם ה-series_sum לקראת הסוף בא במקום ה-case של רובי. שימו לב לשימוש שלי בתבניות של הקלט ש-series_sum מצפה לקבל, ואיך הוא מאפשר לי לתת שמות שונים למשתנים (d אל מול q). אבל זה משהו שכבר ראינו בפוסטים קודמים - החידוש מגיע במימושים של פונקציות הסכום. בשתיהן אני משתמש ב-list comprehension כדי ליצור את רשימת כל איברי הסדרה; וכדי לחשב את הסכום אני מפעיל פונקציה שנקראת foldl ומקבלת שלושה פרמטרים: הראשון הוא האופרטור +, השני הוא הערך 0 והשלישי הוא המערך. כפי שניתן לנחש, foldl עוברת סדרתית על אברי המערך ומפעילה את האופרטור + בכל פעם על ערך זמני שיש לה (שאותחל להיות 0 על פי הפרמטר שהעברתי) והאיבר הבא בתור מהמערך. הנה איך אפשר לממש את הפונקציה הזו:

foldl f z []     = z
foldl f z (x:xs) = let z' = z `f` x
                   in foldl f z' xs

</div>

אבל אין צורך לכתוב את המימוש במפורש - הוא כאן רק כדי לעזור לכם להבין את הפונקציה, ובפועל foldl היא חלק סטנדרטי מהשפה. יש גם פונקציה foldr (ה-l,r בסוף הם מלשון left, right) אבל זו פונקציה בעייתית יותר ולא אכנס לדקויות הללו כרגע.

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

<html>
<head>
<title>Targil 10</title>
</head>
<body>
  <script type="text/javascript">
    var arithmeticSeriesSum = function(a0, d, n){
      var sum = 0;
      for (var i=0; i<n; i++){
		sum = sum + (a0+i*d);
      }
      return sum;
    }

    var geometricSeriesSum = function(a0, q, n){
      var sum = 0;
      for (var i=0; i<n; i++){
		sum = sum + (a0*Math.pow(q,i));
      }
      return sum;
    }

    var computeSum = function(){
      var a0 = parseInt(document.getElementById("a0").value);
      var d_or_q = parseInt(document.getElementById("d_or_q").value);
      var n = parseInt(document.getElementById("n").value);
      var type = document.getElementById("type").value;
      var result = 0;
      switch(type){
		case "A":
		  result = arithmeticSeriesSum(a0, d_or_q, n);
		  document.getElementById("d_or_q_label").innerHTML = "d";
		  break;
		case "G":
		  result = geometricSeriesSum(a0, d_or_q, n);
		  document.getElementById("d_or_q_label").innerHTML = "q";
		  break;
      }
      document.getElementById("result").value = result;
    }
  </script>
  a0 = <input type="textbox" id="a0" value = "0" onkeyup = "computeSum()"/>
  <span id="d_or_q_label">d</span> = <input type="textbox" id="d_or_q" value = "0" onkeyup = "computeSum()"/>
  n = <input type="textbox" id="n" value = "0" onkeyup = "computeSum()"/>
  <br />
  <select id="type" onchange = "computeSum()">
    <option value="A" selected="selected">Arithmetic series</option>
    <option value="G">Geometric series</option>
  </select>
  <br />
  Sum = <input type="textbox" id="result" value = "0"/>
</body>
</html>

בכל הנוגע לחישוב הסכומים, אני עושה לולאת for “קלאסית” ובזה נגמר העניין. כדי להחליט האם לעשות טור חשבוני או הנדסי אני משתמש במשפט case, אבל התחביר שלו בג’אווהסקריפט שונה ממה שיש ברובי. ראשית, לא כותבים case ואז משתנה, אלא switch ואז משתנה (או ביטוי כלשהו שמתפרש בתור ערך) בסוגריים; אחרי זה פותחים בלוק עם סוגריים מסולסלים, ובתוכו כותבים case ואז ערך ואז נקודותיים עבור כל מקרה שבו אנחנו רוצים לטפל. אלא שבג’אווהסקריפט (ובשפות נוספות כמו C ו-++C) יש למשפטי case כאלו גם תכונה שנקראת fall-through: מרגע ש-case כלשהו התקיים, אנחנו מפעילים את הקוד שלו וגם את הקוד של כל המקרים שאחריו אלא אם עוצרים אותנו במפורש מלעשות את זה על ידי פקודת break כמו שיש לי שם. מה ההגיון כאן? ובכן, אין לי דוגמה טובה כרגע, אבל לפעמים זה שימושי. לרוע המזל, זה מאוד, מאוד מסוכן; זה פתח לבאגים איומים ונוראיים. אני רוצה לספר כאן על הבאג האיום והנורא החביב עלי מסוג זה: Yeenoghu.

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

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

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

אז חברים - כשאתם כותבים case בשפה כמו C, תזכרו את Yeenoghu! תשתמשו ב-break, תמיד!

אחרי הסיפור העגום הזה אפשר להסביר מה עוד עשיתי בקוד הג’אווהסקריפט. ראשית, איך המשתמש בוחר אם הוא רוצה סכום של סדרה חשבונית או הנדסית? הוא יכול להקליד “A” או “G” כמו קודם, אבל בשביל מה? חצי מהפואנטה בג’אווהסקריפט הוא שאפשר להשתמש בממשק שמוגדר כבר כך כחלק מהסטנדרט של HTML וכולל בתוכו, למשל, תיבות בחירה - Select. אז אני משתמש באחת כזו. ויש עוד תעלול: כזכור, את ההפרש של סדרה חשבונית אני מסמן ב-d ואת המנה אני מסמן ב-q; רציתי שבממשק ההטמלי הכיתוב של התיבה הרלוונטית ישתנה בהתאם לשאלה אם כרגע תיבת הבחירה היא על סדרה חשבונית או הנדסית. את השינוי הזה אני מבצע בתוך משפט ה-case שגם מחשב את הפלט שצריך להציג על המסך כרגע, מתוך הנחה (שיש בה הגיון אבל צריך להיות זהירים איתה) שתמיד מגיעים למשפט הזה אחרי שבוחרים את אחת מהסדרות בתיבת הבחירה.

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