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

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

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

על השפות הפונקציונליות נמנות שפות כגון LISP הוותיקה, Dax ,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

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

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

מנגנון אחר הוא סלקטור, הדומה ל-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

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


קישורים חיצוניים

ויקישיתוף מדיה וקבצים בנושא תכנות פונקציונלי בוויקישיתוף


הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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