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

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

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

1. מה אנחנו בונים

הנה בעיה שהופיעה ב Advent Of Code ב 2017. נתון הטקסט הבא שמייצג רשימה של קשרים בין תוכניות:

0 <-> 2
1 <-> 1
2 <-> 0, 3, 4
3 <-> 2, 4
4 <-> 2, 3, 6
5 <-> 6
6 <-> 4, 5

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

בקלט לדוגמא התשובה היא 6, כיוון ש-0 מחוברת ל-2, 2 מחוברת ל 3 ו-4, 4 מחוברת ל-6 ו-6 מחוברת ל-5. סך הכל אם מתחילים מ-0 והולכים לפי הקווים אפשר להגיע ל-6 תוכניות (כולן חוץ מתוכנית מספר 1).

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

2. פיתרון ב Python בגישה מונחית עצמים

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

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

class Program:
    def __init__(self, id):
        self.friends = set([self])
        self.id = id
        self.group = None

    def connect(self, other_program):
        self.friends.add(other_program)
        other_program.friends.add(self)

    def mark_friends(self, group):
        if self.group is not None:
            return

        self.group = group
        for p in self.friends:
            p.mark_friends(group)

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

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

class Parser:
    def __init__(self):
        self.programs = {}

    def program(self, id):
        if id not in self.programs:
            self.programs[id] = Program(id)

        return self.programs[id]

    def all_programs(self):
        return self.programs.values()

    def read_file(self, filename):
        with open(filename) as f:
            for line in f:
                left_id, right = line.strip().split(' <-> ')
                ids = right.split(', ')
                left = self.program(left_id)
                for id in ids:
                    left.connect(self.program(id))

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

p = Parser()
p.read_file('input.txt')
p.program('0').mark_friends(0)
print(len([program for program in p.all_programs() if program.group == 0]))

3. פיתרון ב Clojure בגישה הפונקציונאלית

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

(def input-graph {
                  0 (set [2]) 
                  1 (set [1])
                  2 (set [0 3 4])
                  3 (set [2 4])
                  4 (set [2 3 6])
                  5 (set [6])
                  6 (set [4 5]) 
                  })

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

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

(def input-graph-2 {
                  0 (set [2 3 4]) 
                  1 (set [1])
                  2 (set [0 3 4])
                  3 (set [2 4])
                  4 (set [2 3 6])
                  5 (set [6])
                  6 (set [4 5]) 
                  })

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

(defn step [data id]
  (let [found-programs (get data id)
        new-programs (apply clojure.set/union (map data found-programs)) 
        ]
    (assoc data id (clojure.set/union new-programs found-programs))
    )
  )

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

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

הקוד ב clojure יחסית פשוט ונראה כך:

(defn count-programs [data id]
  (let [result (step data id)]
    (if (= result data) (count (get result id)) (recur result id))
    ))

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

(def input-text "
0 <-> 2
1 <-> 1
2 <-> 0, 3, 4
3 <-> 2, 4
4 <-> 2, 3, 6
5 <-> 6
6 <-> 4, 5
")

(defn build-graph [input-text]
  (let [
        lines (clojure.string/split-lines input-text) 
        connections (map (fn [line] (re-seq #"\d+" line)) lines) 
        ]
    (into {} (map (fn [[x & y]] [x (set y)]) connections))))

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

(count-programs (build-graph input-text) "0")

4. אז מה עדיף

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

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