************************************ מחוללים והפשטות על מבני בקרה בפייתון ************************************ בני צ'רניאבסקי, OSDC Israel 2006 ******************************** איטרטורים (Iterators) ===================== החל מפייתון 2.2 יש ממשק מוגדר לאיטרציה על אובייקטים. סדרה לעומת איטרטור ------------------ :: iterable = [0, 1, 2] for i in iterable: for j in iterable: print i, j * כל לולאת ``for`` צריכה להחזיק מצב משלה. * המצב הזה נמצא באובייקט הנקרא איטרטור. * לאובייקט אחד אפשר ליצור הרבה איטרטורים בלתי תלויים. ממשק האיטרטור ------------- * `iterable.__iter__()` מחזיר את האיטרטור. * `iter(iterable)` עושה את זה וגם תומכת אחורה בסדרות ללא `__iter__`. * `iterator.__iter__()` חייב להחזיר את עצמו => אפשר לעשות ``for`` על איטרטורים. * `iterator.next()` מחזיר את הערך הבא או זורק `StopIteration`. דוגמה: גירסה פשוטה ל־`xrange` ----------------------------- :: class XRange(object): def __init__(self, start, stop): self.start, self.stop = start, stop def __iter__(self): return XRangeIterator(self) class XRangeIterator(object): def __init__(self, xrange_obj): self._xrange = xrange_obj self.i = 0 def __iter__(self): return self def next(): self.i += 1 if self.i > self._xrange.stop: raise StopIterationError return self.i שימוש חוזר באיטרטור ------------------- אם מה שמוסרים ל־``for`` זה כבר איטרטור, אפשר להמשיך ולהשתמש בו:: arg_iter = iter(sys.argv) progname = arg_iter.next() # קידום לפני הלולאה for arg in arg_iter: if arg == '-v': verbose = True elif arg == '-f': filename = arg_iter.next() # גונבים מהלולאה elif arg == '--': break rest = list(arg_iter) # האיטרטור עדיין חי טריק: שימוש לסירוגין באותו איטרטור ---------------------------------- איך לוקחים רשימה שטוחה ומחלקים אותה לקבוצות באורך קבוע (למשל זוגות)? * נשתמש ב־`zip` שלוקח מכמה איטרטורים לסירוגין: >>> zip([1, 2, 3], ['a', 'b', 'c']) [(1, 'a'), (2, 'b'), (3, 'c')] * וניתן לו *אותו איטרטור* כמה פעמים: >>> i = iter([1, 'a', 2, 'b', 3, 'c']) >>> zip(i, i) [(1, 'a'), (2, 'b'), (3, 'c')] * או בביטוי אחד: ``zip(*[iter([1, 'a', 2, 'b', 3, 'c'])]*2)`` איטרטורים מובנים בפייתון ------------------------ לכל מבני הנתונים יש איטרטורים:ד * איטרציה על רשימות, n־יות, מחרוזות, וקבוצות מחזירה כצפוי את כל האיברים. * איטרציה על מילונים מחזירה את המפתחות. * אפשר לבחור מה רוצים: `d.iterkeys()`, `d.itervalues()`, או `d.iteritems()` שמחזיר זוגות (מפתח, ערך). איטרוטרים יכולים גם להתקיים בפני עצמם: * קובץ הוא איטרטור על עצמו והוא מחזיר שורות: ``for line in open('foo'): ...``. * `enumerate(iterable)` ו־`reversed(sequence)` מחזירות איטרטורים. צורכים מובנים בפייתון --------------------- רוב הפונקציות שעובדות על סדרות למעשה מקבלות כל דבר איטרבילי: * פונקציות הבונות מבני נתונים: `list()`, `tuple()`, `dict()`, `set()`, `sorted()`... * פונקציות ש"טוחנות" סדרה לערך בודד: `min()`, `max()`, `sum()`... * הן יכולות ישר לקבל איטרטור (כי כזכור הוא איטרטור של עצמו). * נהוג לדייק בתיעוד ולציין האם הפונקציה דורשת סדרה (sequence) או כל דבר איטרבילי (iterable). מחוללים (Generators) ==================== החל מפייתון 2.2 יש גם דרך מאוד נוחה וחזקה לממש איטרטורים. תחביר ----- פונקציה המכילה את המילה השמורה ``yield`` היא פונקציה מחוללת:: def XRangeIterator(start, stop): i = start while i < stop: yield i i += 1 * ב־2.2 צריך לרשום ``from __future__ import generators`` בראש הקובץ. החל מ־2.3 לא חייבים. פונקציה מחוללת מחזירה איטרטור ----------------------------- פונקציה מחוללת לא מחזירה תוצאות ישר — היא מחזירה "אובייקט מחולל" שמתנהג כאיטרטור: >>> g = XRangeIterator(0, 3) # שום דבר לא בוצע בשלב הזה >>> g.next() # הפונקציה רצה עד להחזרת התוצאה הראשונה 0 >>> g.next() # הפונקציה ממשיכה לרוץ מהמצב בו היא עצרה 1 >>> g.next() # ומשיכה עוד פעם... 2 >>> g.next() # חזרה מהפונקציה מסמלת עצירה ... StopIteration מחולל ישר בתור `__iter__` ------------------------- :: class XRange(object): def __init__(self, start, stop): self.start, self.stop = start, stop def __iter__(self): i = self.start while i < self.stop: yield i i += 1 מי בכלל צריך סדרה? ------------------ ברוב המקרים בהם יש פונקציונליות מעניינת באיטרטור, אין צורך להפוך אותו לאיטרטור על אובייקט כלשהוא (כמו XRange) — מספיק לממש ישר את האיטרטור (כמו XRangeIterator בדוגמה שלפני־כן). * אם השימוש הוא ``for i in XRangeIterator(0, 3):``, זה לא משנה. * יותר פשוט ויותר יעיל :-). * אם רוצים לחזור על הערכים הרבה פעמים, אפשר לקרוא לפונקציה כמה פעמים או לבנות רשימה (``list(generator())``). * ברוב המקרים פונקציות מחוללות עומדות בפני עצמן, מימוש איטרציה על אוביירטים אחרים זה רק שימוש משני. עיבוד מידע זורם =============== איטרטורים ופונקציות מחוללות מאפשרים לבצע חישובים על זרמי מידע בלי להחזיק בזכרון את כל הערכים בו־זמנית. ביצועים ------- איטרטורים יותר חסכוניים ויעילים מרשימות: * ``for key in d:`` עדיף על ``for key in d.keys():`` שיוצר רשימה של כל הערכים. * יוצא דופן: אם משנים את המילון תוך כדי הלולאה, אסור להשתמש באיטרטור. * ``for line in file('foo'):`` עדיף על ``for line in file('foo').readlines():`` שקורא את הקובץ לזכרון בבת אחת. תוצאות מוקדמות וזרמים אינסופיים ------------------------------- איטרטורים יכולים לייצג זרמי מידע "אינסופיים":: def fibonacci(a=0, b=1): # מייצר זרם ערכים אינסופי while True: yield b a, b = b, a+b def cummulative_sum(iterable): # התמרה על זרם ערכים s = 0 for i in iterable: s += i yield s for i, s in enumerate(cummulative_sum(fibonacci())): if s > 1000: break print i # כמה מספרי פיבונצ'י צריך לחבר כדי לעבור את 1000?‏ `itertools`: פונקציות בסיסיות -------------------------------------- המודול itertools מכיל הרבה כלים מגניבים לעיבוד זרמי נתונים: * `imap()`:: def dotproduct(vec1, vec2): return sum(itertools.imap(operator.mul, vec1, vec2)) * `ifilter()`:: def grep(regex, lines): regex = re.compile(regex) return ifilter(regex.search, lines) * `izip()`:: def inverse_dict(d): return dict(izip(d.itervalues(), d.iterkeys())) `itertools`: עוד כלים מגניבים ----------------------------- * `groupby(data, key_func)` מחזירה זוגות (מפתח, סדרת_ערכים). * `islice(iterable, [start,] stop, [step])` חותכת לפי מקומות. * `dropwhile(predicate, iterable)` ו־`takewhile` חותכות לפי ערכים. * `chain(*iterables)` משרשרת איטרטורים. * `count([n])` ו־`repeat(obj, [times])` מחוללות ערכים עולים\קבועים. שמירת תוצאות איטרטורים ---------------------- לפעמים חייבים לשמור תוצאות ביניים לעתיד. * `list(iterable)` בונה רשימה של כל הערכים. * גם פונקציות כגון `dict()` ו־`sorted()` זוכרות את כל הערכים. * `itertools.cycle(iterable)` בונה רשימה ועובר עליה באופן מחזורי. * `itertools.tee(iterable, n=2)` מפצל איטרטור לכמה — שימושי להצצות קדימה. מחוללים רקורסיביים ================== מחוללים רקורסיביים הם פתרון כמעט מושלם לבעיות חיפוש עם backtracking. * הדרך הקלה להבין פונקציות מחוללות היא לדמיין ש־``yield`` זה כמו ``print``. * היא לא מדוייקת! ``print`` מדפיס למסך מתוך לא משנה מאיפה קראו לו; ``yield`` מחזירה תוצאות רק לפונקציה שקראה למלחולל. * כדי שזה יעבוד צריכים לעטוף כל קריאה רקורסיבית ב־``for i in recurse(): yield i``. דוגמה: הילוך על עץ קבצים ------------------------ :: def dirwalk(dir): # Cookbook recipe 105873 for f in os.listdir(dir): fullpath = os.path.join(dir,f) if os.path.isdir(fullpath) and not os.path.islink(fullpath): for x in dirwalk(fullpath): # רקורסיה yield x else: yield fullpath ניהול מחסנית ידני ----------------- * ברקורסיה עמוקה, כל ערך מטייל כל הדרך למעלה ולמטה. * זה לא נורא כי הקפאת\הפשרת פונקציה מחוללת הרבה יותר מהירה מקריאה לפונקציה! * אבל אם זה מטריד אותכם, אפשר לפתור את זה. יותר בשביל הקטע, לא בדקתי ביצועים... * הרעיון: במקום להחזיר את כל הערכים שהקריאה הרקורסיבית מניבה, נחזיר את המחולל עצמו וברמה החיצונית ניקח ערכים ישר ממנו עד שהוא יגמר:: def dirwalk2(dir): for f in os.listdir(dir): fullpath = os.path.join(dir,f) if os.path.isdir(fullpath) and not os.path.islink(fullpath): yield dirwalk(fullpath) # רקורסיה עקיפה else: yield fullpath assert list(gen_flattener(dirwalk2(dir))) == list(dirwalk(dir)) * ברמה החיצונית צריך לנהל ידנית מחסנית של מחוללים:: def gen_flattener(values_or_gens): stack = [values_or_gens] while stack: try: val = stack[-1].next() except StopIteration: stack.pop() else: if isinstance(val, types.GeneratorType): stack.append(val) else: yield val "גרעיני מחוללים" ================ היכולת של מחוללים "להשהות" פונקציה ואחר־כך להמשיך אותה מאותה נקודה מאפשרת למדל בנוחות תהליכים מקביליים. * רעיון מתבקש: מחוללים הם "תהליכים" שכל פעם מניבים "קריאת מערכת" ל"גרעין" שמריץ אותם. * `gen_flattener()` שהובא לעיל הוא דוגמה מאוד פשוטה ל"גרעין" כזה. * יש מספר ספריות שמתבססות על המבנה הזה. MyHDL ----- * שפת מידול חומרה. חומרה מורכבת מבדלוקים העובדים במקביל. כל בלוק ממתין לשינויים בכניסות מסויימות ואז מעדכן יציאות ושוב ממתין:: def Inc(count, enable, clock, reset, n): """מונה סינכרוני עם כניסות איפשור ואיתחול.""" while 1: yield posedge(clock), negedge(reset) # המתנה לאירועים if reset == ACTIVE_LOW: count.next = 0 else: if enable: count.next = (count + 1) % n * אפשר להמתין לאירועים על סיגנלים, מחוללים אחרים או שילובים שלהם. * לפני שהעסק מתחיל לרוץ, יש שלב של תיאור המבנה. בלוקים מורכבים מחזירים את המרכיבים שלהם:: def watch(): """שעון של דקות""" clk1 = Signal(0) clkGen1 = clkGen(clk1, period=60) enable = Signal(0) reset = Signal(0) count = Signal(6) inc = Inc(count, enable, clock, reset, 60) display = Display(count) return clkGen1, inc, display sim = Simulation(watch()) * בונוסים מגניבים: טריקים של introspection ו־decorators, ממשק שקוף מול סימולטורים של Verilog שמאפשר לכתוב ב־MyHDL בדיקות לקוד Verilog, והמרה מ־MyHDL ל־Verilog לצורך סינטזה. SimPy ----- * ממשק עם הרבה פעולות. חלקן פונקציות וחלקן פקודות ``yield`` של שלישיה `(request, self, time)`:: class Firework(Process): def execute(self): print now(), ' firework activated' yield hold, self, 10.0 for i in range(10): yield hold, self, 1.0 print now(), ' tick' yield hold, self, 10.0 print now(), ' Boom!!' * הרבה פעולות: `passivate`, `waituntil`, `waitevent`, `queueevent`, `request`, `release`... * בונוסים מגניבים: מנגנוני סינכרון, ניהול משאבים, איסוף והצגה גרפית של סטטיסטיקות ועד... ביטויים מחוללים =============== בפייתון 2.4 נוספה אפשרות נהדרת לכתוב ביטויים מחוללים בדומה ל־list comprehensions. מוטיבציה לדוגמה: dict comprehensions ------------------------------------ * היו list comprehensions: ``[i**2 for i in range(10)]``. * אנשים רצה משהו דומה למילונים. ולקבוצות. וכו' — אין לזה סוף. * אפשר ליצור מילון מרשימת זוגות: ``dict([(i**2, i) for i in range(10)])``. * אבל זה לא יעיל — יוצר רשימה רק כדי לזרוק אותה מיד. * להזכירכם, `dict()` מקבל איטרטורים. אפשר לכתוב:: def gen_pairs(): for i in range(10): yield (i**2, i) d = dict(gen_pairs()) אבל זה מכוער. תחביר ----- רוצים מחולל בתוך ביטוי. קבלו:: dict(((i**2, i) for i in range(10))) (אותו דבר אבל עם סוגריים עגולות.) * במקרה שזה הפרמטר היחיד של פונקציה כמו פה, אפשר לוותר על הסוגריים הנוספות. * בניגוד ל־list comprehensions, המשתנה לא דולף החוצה (גם l.c.‎ יתוקנו בעתיד). שילוב עם פונקציות צורכות ------------------------ >>> set(x for x in range(-10, 11) if x % 3 == 0) set([0, 3, 6, 9, -9, -6, -3]) >>> sum(i**2 for i in range(10)) 285 >>> all(x > 7 for x in [6, 10, 9]) # all()/any() are 2.5 False להניב ערכים אבל גם לקבל ======================= אם מחוללים טובים לתיאור "תהליכים" מקבילים, איך הם יכולים לקבל ערכים תוכך כדי ריצה? דרך מכוערת: פרמטר הניתן לשינוי ------------------------------ כשיוצרים מחולל אפשר למסור לו אובייקט הניתן לשינוי, למשל רשימה. ואז אפשר לשים בו את הקלטים:: def upcase(input): while True: while not input: yield '' yield input.pop(0).upper() input = [] upcase_process = upcase(input) for s in ['abc Foo qUuX']: input.append(s) print upcase_process.next() ‏PEP 342: הפיכת ``yield`` מפקודה לביטוי --------------------------------------- * ב־2.5, ``yield`` יהפוך לביטוי:: def upcase(): s = yield '' # חייבים להניב לפני שמקבלים :-( while True: s = yield s.upcase() * לשימושים שונים מפשוט השמה, צריך לשים את ``(yield value)`` בסוגריים. * שולחים ערך ע"י `g.send(val)` במקום `g.next()` (ששולח None):: upcase_process = upcase(input) upcase_process.next() # ‫קידום עד ל־yield ''‎‬ for s in ['abc Foo qUuX']: print upcase_process.send(s) # ‫מוחזר מה־yield‬ שיחרור משאבים ============= נגיד שפונקציה מחוללת פתחה קובץ או נעלה איזה mutex. איך דואגים לשחרר אותם? * פייתון לא מרשה כיום לשים ``yield`` בתוך ``try..finally`` בגלל שאף אחד לא מבטיח שה־yield יחזור שוב. שימוש מכוער ב־`__del__` ----------------------- * אפשר להתעלק על `__del__`. ב־CPython (אבל לא ב־Jython וכמה מימושים אחרים!), מובטח ש־`__del__` יבוצע ברגע שמפסיקים להשתמש באיטרטור. * בעיה: איך מצמידים `__del__` למחולל? לא כיף לחזור לכתיבת מחלקות עם `next()` רק בגלל ששם אין בעיה להוסיף מתודת `__del__` :-( * פתרון: מחלקה שכותבים פעם אחת שעוטפת כל מחולל:: def safe_gen(gen): class safe_iter(object): def __init__(self, *args, **kwargs): self.iter = gen(*args, **kwargs) def __iter__(self): return self def next(self): return self.iter.next() def __del__(self): for dummy in self.iter: pass return safe_iter def gen(): ... gen = safe_gen(gen) * מה שהפתרון הזה עושה הוא להריץ את המחולל עד סופו בכל מקרה. זה לא תמיד הדבר הנכון. אין פה דרך להגיד למחולל שצריך להתקפל :-(. PEP 342: `g.throw()`, `g.close()` --------------------------------- * קבלו שוב את PEP 342! בפייתון 2.5, מחוללים יקבלו 2 מתודות חדשות: * `g.throw(exc)` מפעילה את המחולל וזורקת בתוכו שגיאה כאילו היא נגרמה ב־``yield``. * `g.close()` דומה אבל זורקת שגיאה מיוחדת `GeneratorExit` שמדמה ``return``. * ואז גם יאופשר ``try..finally`` מסביב ל־``yield``. * עדיין צריך לוודא שמפעילים את `g.close()` ידנית על מחוללים שתלויים בזה. * `__del__` מפעיל אותו אבל כאמור לא בריא לסמוך עליו. * בפרט, ``for`` **לא** מפעיל אותו (בשביל תאימות אחורה עם שימוש חוזר באיטרטור אחרי הלולאה). היפוך בקרה ========== מחולל הוא דבר פסיבי — כל ``yield`` משחרר שליטה לחסדי מי שמפעיל אותו. אבל מסתבר שנוח להשתמש במחולל כדי לתאר שליטה אקטיבית בקוד אחר. ``for`` בתור אבסטרקציית בקרה ---------------------------- אם משתמשים במחולל בלולאת ``for``, כל ``yield`` בעצם מפעיל את גוף הלולאה:: def with_opened_file(*args): f = file(*args) try: yield f finally: f.close() for f in with_opened_file('foo.txt'): do_something(f) * בעיה: כאמור, ``for`` לא מבטיח קריאה ל־`g.close()`, כך שלא מובטח מתי ה־``finally`` יתבצע. PEP 342 לא ממש עזר פה. ‏PEP 343:‏ ``with`` כאבסטרקציית בקרה ------------------------------------ בפייתון 2.5 תהיה פקודה חדשה לצורך אבסטרקציה על ``try`` (הפרטים לא סופיים):: with EXPR as VAR: BLOCK שמתנהג כך:: abc = (EXPR).__context__() exc = (None, None, None) VAR = abc.__enter__() try: try: BLOCK except: exc = sys.exc_info() raise finally: abc.__exit__(*exc) * זה מאפשר לכתוב מחלקה שאפשר יהיה להשתמש בה כך:: with opened_file('foo.txt') as f: do_something(f) * אבל אנחנו לא אוהבים לכתוב מחלקות איפה שאפשר לכתוב מחוללים. פתרון: תהיה פונקציה `contextmanager()` שעוטפת מחולל (בדיוק כזה כמו בדוגמה לעיל) בממשק המתאים ל־``with``. זהו. זה די סוגר את ההשטלטות של מחוללים על מבני בקרה בפייתון.