Lisp

Lisp

פרדיגמות	תכנות פונקציונלי, תכנות פרוצדורלי, תכנות השתקפותי, מֶטַא־תכנות
מתכנן	ג'ון מקארתי
מפתח	סטיב ראסל, טימותי פ הארט, ומייק לוין
טיפוסיות	חזקה, דינמית
ניבים	Arc, AutoLISP, Clojure, Common Lisp, Emacs Lisp, EuLisp, Franz Lisp, Hy, Interlisp, ISLISP, Le Lisp, LFE, Maclisp, MDL, newLISP,NIL, PicoLisp, Portable, Standard Lisp, Racket, RPL, Scheme, SKILL, Spice Lisp, T, Zetalisp ועוד..
הושפעה על ידי	IPL
השפיעה על	CLIPS, CLU, COWSEL, Dylan, Elixir, Falcon, Forth, Haskell, Io. loke, JavaScript, Julia, Logo, Lua, ML, Nim, Nu, OP35, Perl, POP-2/POP-11, Python, R, Rebol, Ruby, Scala, Smalltalk, Tcl, Wolfram Language

Lisp היא משפחת שפות תכנות פונקציונליות בעלת תחביר ייחודי המתאפיין בכתיב תחיליתי וביטויי־S. השם Lisp נגזר מראשי תיבות של המילים ”List Processor“ (בעברית: מעבד רשימות) שציין את ייעודה המקורי של שפת Lisp שהוצגה לראשונה בשנת 1958, והייתה מאז לשפת תכנות עילית השנייה הוותיקה ביותר שנעשה בה שימוש נפוץ עד היום (רק Fortran שהופיעה שנה אחת לפניה ותיקה ממנה). השפה השתנתה מאז והתפתחה באופן ניכר, במשך הזמן פותחו לה ניבים רבים בעלי מאפיינים שונים. ניבי Lisp הרב־תכליתיים הנפוצים ביותר כיום הם Common Lisp ו־Scheme. בנוסף קיימים עוד עשרות ניבים שרובם משמשים כשפות מאקרו/תסריט של תוכנות מסוימות (למשל: AutoCad, GIMP ו־Emacs).

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

היסטוריה

Lisp פותחה במקור על ידי ג'ון מקארתי בשנת 1958 כשהיה באוניברסיטת MIT. מקארתי פרסם לראשונה את מאפייניה של Lisp ב־1960, בכתב העת המדעי Communications of the ACM, תחת הכותרת Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I (תרגום לעברית: פונקציות רקורסיביות של ביטויי־S והעיבוד שלהן על ידי מכונות, חלק א'), הוא הסביר שבעזרת פרמטרים ספורים והתחביר הפונקציונלי הייחודי ל־Lisp יהיה אפשר לפתח שפת אלגוריתמים שתשתווה ביכולותיה למכונת טיורינג.

Lisp יושמה לראשונה על ידי סטיב ראסל במחשב מסוג IBM 704. ראסל קרא את המאמר של מקארתי והבין (להפתעתו של מקארתי) שפונקציית ההערכה של Lisp הייתה אפשרית ליישום בקוד מכונה. התוצאה הייתה מפרש שיכול להריץ תוכנות שנכתבו ב־Lisp, או ליתר דיוק, להעריך ביטויי Lisp.

התחביר המקורי של מקארתי היה כתוב ב"ביטויי־M" שהיה ניתן לתרגם לביטויי־S. ההבדל המהותי בין התחבירים היה השימוש בסוגריים העגולים שעטפו את הפרמטרים יחד עם הפונקציה בתחביר ה-S, כנגד הסוגריים המרובעים של תחביר ה-M שעטפו רק את הפרמטרים ואילצו להפריד בינם בעזרת פיסוק והשאירו את הפונקציה מחוץ לסוגרים בדומה לצורת הכתיבה של פונקציות במתמטיקה. כשהשפה יושמה רוב המתכנתים העדיפו את תחביר ה-S באופן מכריע ותחביר ה-M ננטש ונזנח למרות הניסוים הכושלים להחזיר אותו לשימוש בניבים ושפות כמו MLisp ו־CGOL.

שני תסריטי המאקרו הראשונים שנכתבו בשפת סף עבור מחשב IBM 704 שמהוות מאז לפעולות היסודיות של Lisp על מנת לפרק רשימות נקראו בראשי תיבות car עבור "Contents of the Address part of Register number" (בעברית: תוכן הכתובת של הזיכרון) ו־cdr עבור "Contents of the Decrement part of Register number" (בעברית: תוכן ההפחתה של הזיכרון). הפעולות נמצאות בשימוש עד היום על מנת להוציא את הפריט הראשון מהרשימה (car) או על מנת להתייחס לשאר הרשימה ללא הפריט הראשון (cdr) ונשארו באותם השמות בדיוק (ובשילובים שונים) ברוב הניבים של Lisp.

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

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

בשנות ה־80 וה־90 של המאה ה־20 נעשה מאמץ רב כדי לאחד את כל הניבים של Lisp (לרוב יורשי MacLisp כגון ZetaLisp ו־NIL) לתוך שפה אחת. השפה החדשה, Common Lisp, הייתה לרוב תואמת את הניבים שהחליפה. בשנת 1994, מכון התקנים האמריקני הוציא לאור את התקן ל־Common Lisp.

חידושי השפה

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

נוסח ההתניה המוכר כ־if-then-else במקור הומצא על ידי מקארתי, הוא הציע לשלב את צורת ההתניה ב-ALGOL אבל הרעיון נדחה. למרות זאת מקארתי הוסיף את הניסוח ב־Lisp כפונקציה ומאוחר יותר אימצו אותו גם ב־Algol 58 כצורת תחביר שהפכה את הניסוח למאוד פופולרי.

Lisp הייתה למקור השפעה מרכזי על אלן קיי, שהיה מחלוצי המפתחים של Smalltalk. מאוחר יותר Smalltalk השפיעה בחזרה על Lisp בכל הנוגע לתכנות מונחה־עצמים לקראת סוף שנות ה־70.

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

תחביר וסמנטיקה

ביטוי־S

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

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

עם זאת Lisp עדיין איננה מוגבלת לשימוש המסורתי שלה בסוגריים, לדוגמה XMLisp היא תוספת ל־Common Lisp שמאפשרת לגלם ביטויי־S בעזרת תגיות כמו בתקן XML במקום השימוש בסוגריים.

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

דוגמאות

קריאה לפונקציה או למבנה תחבירי תיכתב כרשימה עם שם הפונקציה או האופרטור בהתחלה, והארגומנטים אחר־כך; למשל, פונקציה f שמקבלת שלושה ארגומנטים עשויה להיקרא באמצעות (f x y z).

הדוגמה הבאה, סכום שלושה מספרים, ממחישה את השימוש בכתיב הפולני:

(+ 1 2 3)
; => 6

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

בהתאם לייעודה המקורי כשפת עיבוד רשימות, עושה שפת LISP שימוש רב ברקורסיה.

תוכנית דוגמה לחישוב עצרת, בדיאלקט Common Lisp:

 (defun factorial (n)
 (if (= n 0)
 1
 (* n (factorial (- n 1)))))

שתי פקודות חשובות ב־Lisp הפועלות על רשימות מכל סוג הן car ו־cdr (והמקבילות המודרניות: first ו־rest, בהתאמה). הפקודה car (או first) מחזירה את האיבר הראשון ברשימה, והפקודה cdr (או rest) מחזירה את הרשימה ללא האיבר הראשון.

(car (list 1 2 3))
; => 1
(first (list 1 2 3))
; => 1
(cdr (list 1 2 3))
; => (2 3)
(rest (list 1 2 3))
; => (2 3)

יתרון בשימוש ב־car וב־cdr הוא שניתן לשכפל את האות האמצעית בפקודות אלו על מנת לבצע הפקודה בצורה רקורסיבית מספר פעמים: אם למשל כותבים caaar, מקבלים את האיבר הראשון של האיבר הראשון של האיבר הראשון (3 פעמים) של הרשימה המקורית (איבר ברשימה יכול להיות גם הוא רשימה).

בדומה לכך, אם רושמים cddr, מקבלים את הרשימה המקורית ללא שני האיברים הראשונים שלה (שגם הם יכולים להיות רשימות). ניתן גם לערבב: אם רושמים למשל cadaadr, מקבלים את האיבר הראשון של שאר הרשימה של האיבר הראשון של האיבר הראשון של שאר הרשימה של הרשימה המקורית, וכן הלאה.

(caar (list (list 11 12) 2 3 4 5))
; => 11
(cadr (list (list 11 12) 2 3 4 5))
; => 2
(cddr (list (list 11 12) 2 3 4 5))
; => (3 4 5)
(caddr (list (list 11 12) 2 3 4 5))
; => 3

ניבים וסדר יוחסין

לאורך יותר מ־50 שנות קיומה של Lisp נוצרו לה ניבים רבים בעלי מאפיינים וכללי תחביר שונים, ואפילו נבדלים זה מזה בפרדיגמות סותרות. עם זאת מה שמאפיין את כל הניבים של Lisp ומאחד ביניהם זה השימוש בביטויי־S. השוני בין הניבים כולל לפעמים אפילו מילות מפתח שונות. לדוגמה מילת המפתח defun שמגדירה פונקציה חדשה ב־Common Lisp נקראת define ב־Scheme ו־defn ב־Clojure. אולם בניבים בעלי תקן אחיד כגון Common Lisp, כל היישומים בנויים על אותה הליבה, אך מציעים ספריות שונות.

ניבים בעלי חשיבות היסטורית

• LISP 1.0 - היישום הראשון.
• LISP 1.5 - היישום הנפוץ הראשון שפותח על ידי מקארתי ואחרים מ־MIT. נקרא כך כי היו בו מספר חידושים ושיפורים להבדיל מקודמו, אך לא שכתוב מחדש של המפרש כולו כפי שהיה מתוכנן ב־LISP 2.
• Stanford Lisp 1.6 - היה הניב שפותח במעבדת הבינה המלאכותית באוניברסיטת סטנפורד, הופץ לרוב עבור מערכות PDP שהריצו את מערכת הפעלה TOPS-10. הניב נחשב למיושן כש־Maclisp ו־InterLisp ראו אור.
• MacLISP - פותח עבור פרויקט MAC ב־MIT (אין קשר למקינטוש של אפל או רמיזה על שמו של מקארתי). הניב ירש את LISP 1.5 באופן ישיר ורץ על מערכות Multics ו־PDP-10. (בהמשך הניב נודע בשם "Maclisp" ונכתב בדרך כלל כ־"MacLisp")
• InterLisp - פותח על ידי BBN Technologies עבור מערכות PDP-10 שהריצו את מערכת ההפעלהTenex, מאוחר יותר הניב אומץ עבור מכונות ה־Lisp של Xerox בשם InterLisp-D. גרסה מזערית בשם InterLISP 65 הופצה עבור מחשבי ה־8-ביט של אטארי מבוססי מעבד ה6502. לאורך זמן רב עד לפני איחוד ה-Common Lisp שני הניבים Maclisp ו־InterLisp התחרו זה בזה בתעשייה.
• Franz Lisp - במקור פרויקט של אוניברסיטת קליפורניה בברקלי. המשך הפיתוח של הניב נעשה על ידי קבוצת Franz Inc. שם הניב במקור נגזר מהשם "פרנץ ליסט" כבדיחה. אין קשר לAllegro Common Lisp ניב של Common Lisp שפותח ומופץ על ידי אותה הקבוצה.
• XLISP - ניב שעליו התבסס הניב AutoLISP.
• Standard Lisp ו־Portable Standard Lisp שני ניבים שנעשה בהם שימוש רב כדי לייצא תוכנות Lisp עבור מערכות ה-REDUCE.
• Le Lisp - ניב צרפתי של Lisp. היה מהניבים הראשונים של Lisp ששימשו לפיתוח ממשק משתמש במחשבי המקניטוש.
• Scheme - ראה אור לראשונה ב־1975.
• Common Lisp - ראה אור לראשונה ב־1984. היווה למאמץ האיחוד של מספר ניבי Lisp מתחרים כגון ZetaLisp, Spice Lisp, NIL, ו־S-1 Lisp על מנת ליצור ניב משותף והמשכי עבור כל יורשי ניב ה־Maclisp, ולכלול בו חלק ממאפייני Scheme. הגרסה הראשונה של Common Lisp הייתה זמינה עבור מגוון רחב של פלטפורמות והפכה להיות הניב הסטנדרטי דה פקטו של Lisp עד לפרסום התקן על ידי מכון התקנים האמריקני.
• Dylan - השפה הייתה בגרסתה הראשונה כשילוב של Scheme עם מערכת המובנת־עצמים של Common Lisp.
• EuLisp - ניסיון לפתח ניב מחודש ויעיל יותר של Lisp על ידי מדעני מחשב מאירופה.
• ISLISP - ניסיון לפתח ניב מחודש ויעיל יותר של Lisp.
• IEEE Scheme - ניב שנוצר מתקן Scheme על ידי IEEE 1178–1990 (R1995).
• ANSI Common Lisp - ניב מעט שונה מהמקור שנוצר מתקן מכון התקנים האמריקני ל-Common Lisp אחרי תהליך הקונצנזוס שנעשה כדי למצוא פתרון עבור האי־תאימות של מגוון היישומים של Common Lisp שסתרו זה את זה.
• ACL2 - או בשמה המלא "A Computational Logic for Applicative Common Lisp" הייתה וריאציה פונקציונלית טהורה של Common Lisp (כלומר שלא איפשרה לשינוי מצב או תוצאות לוואי).
• Clojure - ניב חדש יחסית של Lisp שמהדר את הקוד לJVM.

במאה ה־21

למרות הדעיכה של שנות ה־90, העניין ב־Lisp הולך וגובר בקרב מתכנתים רבים בשנים האחרונות. רוב התעוררות והפעילות כיום היא מסביב לניבים Common Lisp, Clojure, Racket, Scheme, ו־Emacs Lisp. הגל החדש מסביב ל־Lisp כולל פיתוח של ספריות חדשות ופיתוח תוכנות.

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

קהילת הקוד הפתוח פיתחה תשתית חדשה עבור Lisp בשם CLiki, שהיא בעצם ויקי שמציעה מגוון רחב של כלים ומידע הקשורים ל־Common Lisp עבור מתכנתים חדשים, כולל הדרכה ושיתוף של דגימות קוד בין חברי הקהילה. אתר אחר בשם Planet Lisp אוסף תכנים הקשורים ל־Lisp ממגוון בלוגים ומרכז אותם במקום אחד. LispForum מאפשר דיונים בין מתכנתי Lisp בנושאים קשורים. Common-lisp.net מציע אחסן לקוד פתוח עבור פרויקטים שפותחו ב-Common Lisp. ו־Quicklisp מנהל ספריות צד שלישי עבור Common Lisp.

קהילת ה־Scheme מתחזקת באופן פעיל יותר מ20 יישומים שונים. כמה מהמימושים החשובים של Scheme הופיעו רק לאחרונה בשנים האחרונות (Chicken, Gambit, Gauche, Ikarus, Larceny, Ypsilon) הקהילות מסביב ליישומים השונים של Scheme גם הן הולכות ומתרחבות באופן פרטני. תהליך מסביב לתקן חדש של Scheme שהתחיל ב־2003 הסתיים ויצא לאור ב־2007. השימוש ב־Scheme באקדמיה לעומת זאת מעט מאבד ממעמדו, ב-MIT כבר לא משתמשים ב־Scheme בקורסים הראשונים למדעי המחשב כמו בעבר.

מספר ניבים חדשניים של Lisp הופיעו רק בשנים אחרונות כגון Arc, Hy, Nu, Clojure, Liskell, LFE ו־Racket והם מהווים לנקודת ציון חשובה בגל הפופולריות המחודשת של Lisp.

ניבים מרכזיים

Common Lisp ו־Scheme מייצגים כיום את שני הזרמים העיקריים בפיתוח של Lisp. השפות הללו מגלמות גם שוני מהותי בעיצוב התוכנה זו מזו.

Common Lisp הוא ניב שירש במקור את MacLisp. ההשפעות העיקריות על Common Lisp באו מ־Lisp Machine Lisp, MacLisp, NIL, S-1 Lisp, Spice Lisp ו־Scheme. יש לו את רוב התכונות שיש לניב Lisp Machine Lisp (ניב Lisp מגושם שהשימוש המרכזי בו היה במכונות Lisp), אך בניגוד לו, עוצב כך שיוכל לרוץ באופן יעיל על כל מחשב פרטי. ל־Common Lisp קיים תקן די רחב הכולל בו מגוון טיפוסי נתונים מובנים וכמו כן תמיכה בתכנות מונחה־עצמים (Common Lisp Object System). בניב זה קיימות גם תכונות מ־Scheme כמו למשל אופטימיזציית הסגור שמאפשרת גישה למשתנים מקומיים שמיוחסים באופן דינאמי מחוץ לפונקציה לסירוגין עם גישה לקסיקלית סטטית.

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

Clojure הוא ניב Lisp חדש יחסית שבאופן עקרוני מכוון את הקוד ל־Java Virtual Machine וכמו כן גם ל־Common Language Runtime, ל־VM של Python, ל־VM של Ruby (נקרא YARV) וגם מהדר את הקוד ל־JavaScript. הניב עוצב להיות פרגמטי ורב־תכליתי. ל־Clojure קיימת השפעה ניכרת מ־Haskell וישנו דגש חזק על אי־שינוי במצב הנתונים בזיכרון בזמן הריצה (שאופייני לתכנות פונקציונלי טהור). Clojure מספקת גישה לתשתיות וספריות Java בלי הצורך בהשתקפות כדי לאפשר ביצוע מהיר עם פעולות פרמיטיביות תוך כדי שימוש במתודות מתוך ספריות Java.

ניבי Lisp משמשים כשפות תסריט בהרבה תוכנות, כש־Emacs Lisp הוא הניב החלוץ כשפת תסריט כיום (נקרא כך על שם תוכנת העריכה שלו Emacs) אחרי כן AutoLisp ומאוחר יותר Visual Lisp שנעשה בה שימוש ב־AutoCAD, וכמו כן Nyquist ב־Audacity ו־Scheme ב־LilyPond. גודלו הזעיר של מפרשן ה־Scheme הפך אותו למאוד פופולרי כשפת תסריט מובנת.

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

מדיה וקבצים בנושא Lisp בוויקישיתוף

• Common-lisp.net
• CLiki
• Lisp, באתר אנציקלופדיה בריטניקה (באנגלית)

הערות שוליים

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

36186775Lisp