• בלוג
  • מימוש שערים לוגיים ב Clojure

מימוש שערים לוגיים ב Clojure

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

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

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

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

circuit = Connector(gate=OrGate, input_gates=[OrGate, AndGate])
print(circuit.send_inputs([False, False, False, False]) == False)

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

2. איך זה נראה בקלוז'ר

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

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

בקצרה ובקוד קלוז'ר אפשר לבנות את הקוד הבא כדי לייצג שער לוגי של "או":

(defn or-gate [[v1 v2 & values]]
  [(or v1 v2 false) values])

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

(println (or-gate [false true false true])) 

; prints:
; [true (false true)]

התוצאה היא שני ערכים, הראשון הוא הפעלת or על שני הפרמטרים הראשונים ברשימת הערכים (false ו true במקרה שלנו) והשני הוא רשימת הערכים שנשארו, אותם נעביר הלאה לשער הבא.

ובאותו הפורמט לבנות גם את השערים הלוגיים של "וגם" ו"לא":

(defn and-gate [[v1 v2 & values]]
  [(and v1 v2) values])

(defn not-gate [[v1 & values]]
  [(not v1) values])

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

(defn connector [input-gates output-gate]
  (fn [values]
      (->
        (loop [
             values values
             [gate & gates] input-gates
             results []]
          (if (nil? gate) (concat results values)
            (let [
                  [res next-values] (gate values)
                  ]
              (recur next-values gates (conj results res)))))
        output-gate)))

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

בשביל לבנות מעגל חשמלי נשתמש ב connector ובשערים שיצרנו, לדוגמה:

(def circuit (connector [or-gate and-gate] or-gate))

יוצר מעגל עם שני שערי כניסה, אחד מסוג or והשני מסוג and ושער יציאה אחד מסוג or.

בגלל שהממשק של connector זהה לממשק של gate אפשר להרכיב מספר connectors כדי לבנות מעגלים יותר מתוחכמים. הדוגמה הבאה מתוך התרגיל של ים עובדת בלי בעיה בתרגום לקלוז'ר:

(let [
      first_connector (connector [or-gate and-gate] or-gate)
      second_connector (connector [first_connector] or-gate)
      circuit (connector [second_connector not-gate] or-gate)
      inputs [ false false false true false true ]
      ]
  ;; false
  (println (check circuit inputs)))

3. מה נשאר

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

(defn or-gate [[v1 v2 & values]]
  [(or v1 v2 false) values])

(defn and-gate [[v1 v2 & values]]
  [(and v1 v2) values])

(defn not-gate [[v1 & values]]
  [(not v1) values])

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

(def or-gate (gatify or 2))
(def and-gate (gatify and 2))
(def not-gate (gatify not 1))

הבעיה כמובן היא ש or ו and הם מאקרו-אים ולכן אי אפשר לקחת את הערך שלהם ולהעביר אותו ל gatify. אם יש לכם רעיון איך לארגן את הקוד טוב יותר בלי כפילות אשמח לשמוע בתגובות.