תכנות פונקציונלי

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

על השפות הפונקציונליות נמנות שפות כגון LISP הוותיקה, Haskell, ML ו-Scheme.

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

רקע תאורטי[עריכת קוד מקור | עריכה]

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

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

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

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

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

טרמינולוגיה[עריכת קוד מקור | עריכה]

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

פונקציות כערכים לכל דבר[עריכת קוד מקור | עריכה]

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

העברת פונקציה כפרמטר[עריכת קוד מקור | עריכה]

פונקציה המקבלת פונקציה כפרמטר נקראת "פונקציה מסדר גבוה". שלוש דוגמאות לפונקציות חשובות מסדר גבוה: map, filter, reduce.

  • map, המקבלת פונקציה ורשימה, ומפעילה את הפונקציה על כל איבר ברשימה. הקוד הבא בשפת Haskell יוצר רשימה שכל איבריה חיוביים בעזרת פונקציית ערך מוחלט (abs) שמועברת לפונקציה map:
map abs [0,-1,2,-3]
-- result: [0,1,2,3]
  • filter, המקבלת פרדיקט ורשימה, ומחזירה רשימה ללא האיברים עבורן הפרדיקט החזיר false. דוגמה בשפת Haskell:
filter odd [1,2,3,4,5]
-- result: [1,3,5]
  • reduce (נקראת גם accumulate או foldl, קיצור של fold left), המקבלת אופרטור בינארי op, איבר אדיש a0, ורשימה של איברים a1, a2,... an, ומחזירה את תוצאת הפעולה a0 op a1 op a2... op an:
foldl (+) 0 [1,2,3,4,5]
-- result: 15

החל מתקן C++11, שפת התבניות של ++C מאפשרת העברה של תבניות כפרמטר לתבניות אחרות, ובכך יש תמיכה ישירה בתבניות (שהן ה"פונקציות" בשפה) ממעלה גבוהה.

בשפות תכנות לא פונקציונליות[עריכת קוד מקור | עריכה]

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

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

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

ביטויי למבדא[עריכת קוד מקור | עריכה]

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

filter (\x-> x<3 ) [1,2,3,4,5]
-- result: [1,2]

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

קיומם של ביטויי למבדא מאפשר חישוב עצל של ביטויים, דבר המאפשר גמישות ב#בקרת זרימה. הקוד הבא בשפת ML מדפיס "hello world":

map (fn f => f()) [
    fn () => print "hello ",
    fn () => print "world\n"
];

List Comprehension[עריכת קוד מקור | עריכה]

שימוש משולב בפונקציות map ו-filter יחד עם ביטויי למבדא הוא נפוץ כל כך שבשפות מסוימות קיים תחביר מיוחד עבורו. אם בשפת ML כותבים:

map (fn x => x*x) (List.filter (fn x => x mod 2 = 0) [1,2,3,4]);

אזי בשפת Haskell ניתן לכתוב בצורה המזכירה הגדרה מתמטית של קבוצה (האופרטור -> מסמן שייכות):

[ x*x | x <- [1,2,3,4], x `mod` 2 == 0 ]

המבנה הופיע לראשונה בשפת NPL והוא קיים, בין היתר, בשפות Haskell,‏ Erlang‏, #F, ואף בשפות לא פונקציונליות ביסודן כגון פייתון. בשפת #C ניתן לדמות את המבנה בעזרת שימוש ב LINQ.

בקרת זרימה[עריכת קוד מקור | עריכה]

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

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

 int x = 1;
 for (int i = 1; i <= 10; i++)
     x = x * i;

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

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

fun fact 0 = 1
  | fact n = n * (fact n-1)
 
fact 10

המימוש הזה תואם ישירות את ההגדרה המתמטית הרקורסיבית של פעולת העצרת: \ n! = n \cdot (n-1)! ותנאי ההתחלה \ 0!=1. במימוש זה, אין כל שינוי בערכי המשתנים! למעשה, המשתנים בשפות פונקציונליות אינם ברי שינוי: בכל קריאה לפונקציה נוצרים משתנים חדשים, המקבלים ערכים חדשים, וכן הלאה.

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

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

בשפות מסוימות (כגון Haskell) כל הביטויים שאין להם תופעת לוואי מחושבים באופן עצל, ובשפות אחרות ניתן להגדיר במפורש דרישה לחישוב עצל (כגון מנגנון הquote בשפת LISP).

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

ביטויי Let ו-Where[עריכת קוד מקור | עריכה]

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

let x=3+2 in x*x

המילה Let (בעברית "יהי") נלקחה מהביטוי המקביל במתמטיקה.

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

x*x where x=3+2

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


קישורים חיצוניים[עריכת קוד מקור | עריכה]