ML (שפת תכנות)

ML
פרדיגמות	מרובת פרדיגמות: אימפרטיבית, פונקציונלית.
תאריך השקה	1973
מתכנן	רובין מילנר ואחרים
מפתח	רובין מילנר
טיפוסיות	חזקה, סטטית, הסקת טיפוסים
מימושים	New Jersey, MLton, Moscow ML, ML-Kit, Poly/ML
ניבים	SML, OCaml, F#, Lazy ML, Alice, Mythryl, Rpal
הושפעה על ידי	ISWIM
השפיעה על	Miranda‏, Haskell,‏ Cyclone,‏ ++C‏, F#,‏ Clojure‏, Felix

ערך זה עוסק בשפת תכנות. אם התכוונתם לאי-שוויון, ראו אי-שוויון ML.

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

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

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

סקירה כללית

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

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

בשונה משפת Haskell,‏ ML נוקטת בחישוב ביטויים מוקדם (Eager evaluation). עם זאת, חישוב ביטויים עצל (Lazy evaluation) ניתן להשגה באמצעות מנגנון סְגוֹר (Closure).

כיום ישנן מספר שפות במשפחת ML. שני הדיאלקטים העיקריים הם Standard ML‏ (SML) ו-Caml. עם זאת קיימים דיאלקטים נוספים, בהם F#‎ - שפה שבה תומכת מיקרוסופט עבור טכנולוגיית NET.. רעיונות משפת ML השפיעו על שפות רבות אחרות, בהן Haskell.

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

טווח ההכרה של מזהים בשפת ML הוא סטטי.

דוגמאות

הדוגמאות להלן הן בדיאלקט SML, שהוא הדיאלקט הנפוץ ביותר. דיאלקטים אחרים אינם שונים ממנו במידה רבה.

עצרת

פונקציית העצרת מבוטאת כ-ML בצורתה הטהורה, כלומר ללא תוצאות לוואי פרט לחישוב ערך הפונקציה:

fun fac (0 : int) : int = 1
 | fac (n : int) : int = n * fac (n - 1)

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

חלק מההגדרה שהוצגה כאן היא אופציונלית, ומתארת את הטיפוסים של הפונקציה. הסימון E : t ניתן להיקרא כ"לביטוי E יש טיפוס t". לדוגמה, הארגומנט n מקבל את הטיפוס מספר שלם (int), ותוצאת הפעלת הפונקציה (fac (n: int מקבלת את הטיפוס int גם כן. הפונקציה כולה מקבלת בהתאם את הטיפוס "פונקציה ממספר שלם למספר שלם" (int -> int). הודות למנגנון הסקת הטיפוסים, ניתן לוותר על כתיבת הטיפוסים במפורש ואלו יוסקו על ידי המפרש או המהדר של השפה. כתיבה מחדש של הדוגמה ללא הטיפוסים תראה כך:

 fun fac 0 = 1
 | fac n = n * fac (n - 1)

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

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

 fun fact n = let
 fun fac 0 = 1
  | fac n = n * fac (n - 1)
 in
 if (n < 0) then raise Fail "negative argument"
 else fac n
 end

המקרה הבעייתי (מספר שלילי) מנוהל בעזרת מנגנון הטיפול בחריגות של השפה.

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

fun factorial n = let
 fun fac (0, acc) = acc
  | fac (n, acc) = fac (n - 1, n*acc)
 in
 if (n < 0) then raise Fail "negative argument"
 else fac (n, 1)
 end

ראו גם

לקריאה נוספת

The Definition of Standard ML, Robin Milner, Mads Tofte, Robert Harper, MIT Press 1990; (Revised edition adds author David MacQueen), MIT Press 1997. ISBN 0-262-63181-4
Commentary on Standard ML, Robin Milner, Mads Tofte, MIT Press 1997. ISBN 0-262-63137-7
ML for the Working Programmer, L.C. Paulson, Cambridge University Press 1991, 1996, ISBN 0-521-57050-6
Robert Harper: "Programming in Standard ML", Carnegie Mellon University, 2005.