chicken-and-egg.tex

גם מי שאינו אורניתולוג יודע כי כל תרנגולת היא אפרוח שהתפתח לאחר שבקע מביצה, וכל
ביצה הוטלה על ידי תרנגולת קודמת. \מונח[פרדוקס הביצה והתרנגולת]{פרדוקס הביצה
והתרנגולת} המיוחס לאריסטו\הערת␣שוליים{384-322 לפנה"ס, יליד סטאגירה, מגדולי
הפילוסופים ביוון העתיקה, ובנו של ניקומכוס, רופא החצר של מלך מוקדון.}, שואל מה
אם הביצה קדמה לתרנגולת, או שמא, התרנגולת קדמה לביצה.
\begin{itemize}
• הטענה שהתרנגולת קדמה לביצה לא יכולה להיות נכונה, כי התרנגולת הראשונה הייתה אפרוח שבקע מביצה.
• אם תמצי לומר שהביצה קדמה לתרנגולת, מיד יטען כנגדך שהביצה הזו הוטלה על ידי תרנגולת.
ההנחה הסמויה בפרדוקס זה היא ששרשרת הזמן, כשהיא נמתחת לאחור, היא סופית, כלומר שגילו של היקום הוא סופי.
\end{itemize}
בפרק זה, נעסוק במופעים של פרדוקסים אלגנטיים דומים בתחום של שפות התכנות. בדיוק כמו הביצה והתרנגולת, הפרדוקסליות הטמונה בפרדוקסים אלו היא קלה ביותר להבנה.

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

נדגים זאת במספר היתרים שונים של \מונח{פרדוקס הביצה והתרנגולת}.
\begin{enumerate}
• \גיבור{היתר תנ"כי:} התרנגולת, עם שאר בעלי הכנף, נבראה במאמרו של אלוהים ביום החמישי לבריאה ככתוב, "וַיִּבְרָא אֱלֹהִים אֶת-הַתַּנִּינִם הַגְּדֹלִים; וְאֵת כָּל-נֶפֶשׁ הַחַיָּה הָרֹמֶשֶׂת אֲשֶׁר שָׁרְצוּ הַמַּיִם לְמִינֵהֶם וְאֵת כָּל-עוֹף כָּנָף לְמִינֵהוּ וַיַּרְא אֱלֹהִים כִּי-טוֹב.", בראשית א' כ"א.). עיון מפורט בתיאור הבריאה, אינו מותיר ספק: התרנגולת, נבראה ראשונה בין שאר העופות שהלא נאמר "וַיְבָרֶךְ אֹתָם אֱלֹהִים, לֵאמֹר פְּרוּ וּרְבוּ וּמִלְאוּ אֶת-הַמַּיִם בַּיַּמִּים וְהָעוֹף יִרֶב בָּאָרֶץ. ".
• \גיבור{היתר יווני:} \מונח[אלוהים]{אלוהים} ברא הן את התרנגולת והן את הביצה. אף זה הינו היתר דתי לפרדוקס, וריאציה להיתר הראשון. בגרסא זו, נבראו ע"י האל התרנגולות והביצים, בבת אחת. פתרון זה עוקף את ההנחה שמקורן של תרנגולות בהכרח מביצים.
• \גיבור{היתר אבולוציוני:} לדידם של אלו המאמינים בתורת האבולוציה, אין הכרח שכל ביצה ממנה נוצרה תרנגולת היא של תרנגולת. למעשה, מדובר בהנחה פשטנית אשר אינה מתארת נכונה את היווצרות החיים. כל מין התפתח ממין קודם וקדום על ידי שורה של מוטציות גנטיות אקראיות שהתרחשו במרוצת השנים. באמצעות מנגנונים של מוטציות \הערת␣שוליים{למעשה, אין זה מדויק. לקורא המעוניין בהעשרה ביולוגית, נרחיב כי מנגנון בשם "רקומבינציה" (שאינו נחשב ל"מוטציה") יוצר מגוון ביולוגי בין-דורי אף באדם, אשר באמצעותו, באפיק נפרד להורשה "רגילה", מתקבל מגוון גנטי במין מסוים. לפרטים נוספים.} וברירה טבעית, התפתחו לאורך השנים, באופן הדרגתי, יצורים שהם התרנגולות אותם אנחנו מכירים היום. הנ"ל-סותר במידת מה את הגדרת הפרדוקס גם כן, וגם לו וריאנטים רבים. באופן כללי, לפי רובן התרנגולות התפתחו מאב קדמון כלשהו בתהליך הדרגתי, כך שלשאלת "מי קדם למי" לא נותרת משמעות רבה.
• \גיבור{ההיתר ה"נכון":} התרנגולת והביצה - חד המה. התהליך האבולוציוני שאחראי ליצירת תרנגולות כולל שתי שרשראות שונות, אך מצומדות. השרשראות הללו מתחילות בתא הראשון בו היו חיים, כאשר השרשרת הראשונה היא שהשפיעה על מהלך חייו של יצור התרנגולת-ביצה, כלומר על מהלך חייו כצעיר, ואילו השרשרת השנייה השפיעה על מהלך חייו כבוגר.

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

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

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

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

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

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

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

נשים לב כי הוכחה זו, וכל דרך החשיבה הזו הנוגעת להיתר זה, היא למעשה \מונח {רדוקציה} של אופן יצירת החיים. הסתכלנו על שרשרת בעלי חיים המקושרת ביחסי "התפתח מ-", שמתחילה בנו ונגמרת בתא החי הראשון. הבעיה של יצירת החיים נחשבת פרדוקסלית הרבה פחות, וגם לה היתרים רבים (דתיים, ביולוגיים וכו'), אך הם נחשבים בעיני רבים "מוזרים" הרבה פחות, שכן יש לכל היתר שכזה תימוכין וראיות.
\end{enumerate}
ראינו אם כן פרדוקס משובב נפש. פרדוקס שקל מאוד להבין אותו, קל להתירו באמצעים מטאפיזיים.

§ מקום תחילת ביצוע

נעסוק בתת-פרק זה בסוגיית \מונח[מקום תחילת ביצוע התכנית]{מקום תחילת התכנית} ביצוע התכנית.

ראינו, בין השאר בתכניות "שלום, עולם!", הוראות בקוד אשר אחראיות להדפסת שורות טקסט. חלק מהוראות מעין אלו מכונות "\פקודות", והן בין השאר מרכיבות תכנית. \פקודות עשויות להיות מאוגדות במקטעים, שכל אחד מהם מכוה \מונח{בלוק}. בלוקים אלו עשויים להיות \מונח[קינון]{מקוננים} אלו באלו, וניתן לכנותם בשם. בשפות שונות, ובכללן שפת \סי, לבלוקים משוימים כאלו ניתן השם "פונקציה" (בְּ-\שי{Pascal}, למשל, מבחינים בין "פונקציות" ל"פרוצדורות" - שני סוגים שונים של בלוקים שכאלו).

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

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

נתאר לפיכך גישות שונות של שפות תכנות שונות באשר לסוגיה זו.
\begin{enumerate}
•\גיבור{הגישה האוטרקית - פסקל:} על פי \מונח{הגישה האוטרקית}, קיימת בתכנית מילה מוגדרת מראש, שחייבת להופיע פעם אחת ויחידה בתכנית, אשר החל ממנה מתחילה לרוץ התכנית. בשפת \שי{פסקל}, למשל, המילה השמורה \קד{program} מגדירה את מקום תחילת ביצוע התכנית. בשפת התכנות \שי{AWK}\הערת␣שוליים{שפת סקריפט שפותחה במעבדות בל בשנת 1977. תוכננה לעיבוד טקסט וזהו עיקר השימוש בה.} התכנית מתחילה לרוץ החל מהמילה השמורה \קד{begin}, אך בשפה זו אין חובה לתת שם לבלוק ממנו מתחיל הביצוע.
• \גיבור{הגישה המטאפיזית - שפת \סי:} \מונח{הגישה המטאפיזית} היא הנפוצה יותר בשפות תכנות, לפיה ריצת התכנית מתחילה בפונקציה בעלת שם מסוים, אלא ששם זה אינו מוגדר מראש, אלא ניתן לשינוי ע"י המשתמש. שם הפונקציה ממנה מתחילים
בפרט אינו מוגדר על פי סביבת העבודה. בשפת \סי, למשל, ממומשת גישה זו, ולא קיימת מילה המקבילה
ל-\קד{program} בְּPascal. ריצת התכנית מתחילה בדר"כ-מהפונקציה \קד{main}, ועם זאת אפשר לשנות זאת באמצעות
הגדרות ההידור של תכנית. להלן דוגמה לכך משפת \סי: (המקור- מסמך "צעדים ראשונים", עמוד 20)

\הכנס␣קוד␣נקי{sources/hello.cpp}{C++}

• \גיבור{הגישה ההוליסטית - \גאוה:} גישה שמכלילה את הגישה הקודמת. לפי גישה זו, נקודת התחלת הביצוע עודנה חיצונית לשפה עצמה, אך עם זאת השפה מגדירה קביעות מדויקות באשר לנקודת תחילת הביצוע. לא יתכן במצב זה כי תחילת הביצוע תוגדר ב\מונח{סביבת הפיתוח}, ולכן לא יתכן שתהיה נקודת תחילת ביצוע שונה ב-2 סביבות פיתוח שונות. הנ"ל-מתקיים בשפת \שי{Eiffel}, שם כותב המתכנת קובץ בתחביר הדומה לזה של השפה, בו מוגדרת בין היתר נקודת תחילת הביצוע. זהו המצב גם בשפת \גאוה\הערת␣שוליים{ברוסית - קרפדה!}, בה ניתן באמצעות מנגנון בשם "\מונח{צורת התבוננות}", להתחיל ביצוע מכל מקום, בעזרת פונקציית \קד{main} בכל מחלקה. הנ"ל-מציב קושי בתכנון שפה יבילה והוליסטית (מדוע?).
• \גיבור{הגישה של ביצוע אינטרקטיבי - שפות עם מפרשים:} בשפות מֵפוׂרַשוׂת, המצב מעט שונה. תחילת ביצוע התכנית היא בפקודה הראשונה המובאת בפני ה\מונח{מפרש}, וממשיכה הלאה ככל שחפץ לב המתכנת להמשיך ולתת פקודות בפני מפרשו. הנ"ל-מתרחש בלולאה המכונה: \קד{read-interpret-execute-loop (reipl)}. משמעותה נובעת משמה - עבור כל פקודה מבצע המפרש ארבעה שלבים בעיבוד הפקודה: קריאתה, פרשונה, ביצועה והמשך לפקודה הבאה. נקודת ההתחלה תהיה אפוא הפקודה הראשונה המוקלדת, או הנטענת לפרשון. שפה המממשת עקרון זה היא \שי{Ocaml}.
\end{enumerate}

עסקנו עד כה בנקודת תחילת הביצוע של תכניות מחשב, ועם זאת זנחנו את הנושא החשוב מכל: איך המחשב מתחיל לעבוד? הרי ידוע לכל שעל מנת להפעיל תכניות מחשב, על תכניות אחרות להפעילן טרם לכך. נשאלת השאלה מי הפעיל את התכנית הראשונה? ובכן, נסביר: בחומרת המחשב קיים קוד צרוב, כלומר סדרת הוראות בסיסיות למחשב הצרובה ב\מונח{זיכרון קריאה בלבד} - מדובר בקובץ הוראות בסיסי ביותר הגורם לביצוען של הפעולות ההִיוּלִיוֹת ביותר בהפעלת המחשב. הן מפעילות אחת, בשלב מסוים קוראות מידע והוראות מזיכרון המחשב, ובעקבותן מופעלת אחרת, בשרשרת עד להדלקת המחשב. למותר לציין שהתהליך כולל שלבים מרובים, בהם ניתן לעשות בדרגות שונות. למעוניינים בהרחבה: הסבר קצר, הסבר מקיף יותר, פקולטה שזהו עניינה.

§ צבת בצבת עשוייה

בהינתן שְׂפַת תכנות אוניברסלית $𝓛$ יש טעם לשאול באיזו שפה כתוב המהדר או המפרש של $𝓛\). אך, כיוון ש-\(𝓛$ היא אוניברסלית, הרי אם אפשר לכתוב את המהדר (לחילופין, המפרש) של $𝓛$ בשפה ' $𝓛$ הרי גם ניתן לכתוב את המהדר (לחילופין, המפרש) בשפה $𝓛$ עצמה.
מתברר שמקובל מאוד לכתוב את המהדר של השפה בשפה עצמה. כך למשל, המהדר של שְׂפַת \סי כתוב בִּשְׂפַת \סי. המהדר של שְׂפַת \גאוה כתוב בִּשְׂפַת \גאוה, וכו'. כמובן שהדבר מעורר קושי: כי אם המהדר עבור שפה מסוימת כתוב באותה שפה, הרי כיצד הודר המהדר? התשובה הפשוטה היא שהמהדר הידר את עצמו, וכך הם בדרך כלל פני הדברים. אלא, שהדבר מוביל לרקורסיה אינסופית.
​§§ סוגיה תלמודית

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

\יניב{צבתא בצבתא מתעבדא וצבתא קמייתא מאן עבד הא לאי בריה בידי שמים}

ובתרגום לעברית: "הצבת אינה נעשית אלא בצבת אחרת. וראשונה מי עשאה? על כרחך מאליה נעשית בידי שמים.". כלומר, צבת שהיא מכשיר לאחיזת מטילי ברזל לשם ליבונם באש ועיבודם, עשוייה אף היא ברזל, ואף היא מיוצרת בצבת אחרת שקדמה לה. כיצד אם כן נוצרה הצבת הראשונה?
הפתרון המוצע על ידי הגמרא הוא שהצבת הראשונה נבראה בערב שבת הראשון, בזמן "בין השמשות", שעה שאלוהים סיים לברוא את כל הדברים האחרים, והתכונן לשבות ממלאכתו לקראת ירידת השבת.
פתרון ניסי שכזה אינו בא בחשבון עבור שפות תכנות. מסכת פסחים מציגה גם דרך אחרת שבה יוצרה הצבת הראשונה (על ידי דפוס נחושת). לעומת זאת, בשפות תכנות, ניתן לבצע תהליך של \setLTR{\מונח{bootstrapping}} שבאמצעותו \setRTL{ניתן} לפתח מהדר המסוגל להדר את עצמו.\הערת␣שוליים{לא נתאר כאן את התהליך, אבל בסופו של יום, הוא דומה מאוד למה שהיה עושה נַפָּח עני שברשותו ברזל, אך לא כסף לרכישת צבת. נפח כזה היה משתמש בכבשנו באופן איטרטיבי, כאשר בכל פעם הוא היה משתמש בגוש הברזל הדומה ביותר לצבת שיש ברשותו, כדי ליצר קירוב טוב יותר לצבת.}
§§ מדד לאלגנטיות של שפה
אבן בוחן מרתקת לאלגנטיות של שְׂפַת תכנות היא אורך המהדר (או המפרש) של השפה, כאשר הוא כתוב בשפה עצמה. שהרי ככל שהשפה מורכבת ומתוחכמת יותר, מחד קל יותר לכתוב את המהדר, אך מאידך המהדר לעסוק בכל המורכבות והעושר הזה.
לחילופין, שפה שהיא פשוטה ביחס (כמו שְׂפַת ה-\שי{batch} של \קד{DOS}) שהוזכרה מעלה, היא קלה אולי להידור, אבל הפשטות של השפה מהווה אבן נגף בבואנו להשתמש בה כדי לכתוב מהדר.
הנה מספר אורכים אופייני של מהדר לשפה הכתוב בשפה עצמה:
\begin{enumerate}
•מהדר לשפת \סי הכתוב בשפה עצמה, דורש כמה עשרות אלפי שורות. המהדר \שי{gcc} מפרס על פני כשבעה מיליון שורות קוד.
•המהדר הראשון לשפת פסקל, אשר נכתב בִּשְׂפַת \פסקל דרש כשבעת אלפים ומאתיים שורות.
•מפרש לשפת ליספ הכתוב בליספ, הידוע גם כפונקציה האוניברסלית \קד{eval} דורש כמאה שורות, או מעט פחות מכך.
\end{enumerate}
לעומת זאת, מפרש בסיסי לשפת פרולוג הכתוב בפרולוג יכול להכתב בשורה אחת בלבד, ומפרש מתוחכם, המאפשר למשל מעקב אחרי החישוב, לא ידרוש בדרך כלל יותר מעשר שורות.
​§§​ הגדרת שפות להגדרת שפה פורמלית, באמצעות עצמן
מהי שפה פורמלית, כל שְׂפַת תכנות היא שפה פורמלית. ישנן שפות פורמליות שאינן שפות תכנות.
שפות תכנות אינן מכניזים נוח להגדרת שפה פורמלית.
מכניזמים להגדרת שפות פורמליות. מתברר שגם מכניזמים אלו הם שפה פורמלית.

בדרך כלל, קל הרבה יותר להגדיר שפה פורמלית, מאשר לכתוב מהדר של השפה בעזרת עצמה.
הנה דוגמאות.
​§§§ הגדרת BNF בעזרת עצמו
​§§§ הגדרת EBNF בעזרת עצמו
​§§§ ביטוי רגולרי המגדיר מהו ביטוי רגולרי חוקי
קל להגדיר את משפחת ה-BNF באצעות ביטוי רגולרי.
קל להשתמש ב-BNF כדי להגדיר מהו ביטוי רגוליר.
אבל, ניתן להגדיר ביטוי רגולרי באמצעות ביטוי רגולרי? לא! רקורסיה.
טבלת סיכום, הגדרה הדדית.

מסיבה זו, השפות BNF וְ-EBNF הן אלגנטיות יותר מביטויים רגולריים.

​§​ המספר השלם החיובי הקטן ביותר שאי אפשר לתאר בתריסר מילים או פחות
המשפט "הַטִּבְעִי הַקָּטָן בְּיוֹתֵר מֵאֵלּו שֶׁאֵינָם גְּדִירִים בְּפָחוֹת מִתְּרֵיסָר מִלִּים" הוא מופע של הפרדוקס של ברי. לִכְאוֹרָה, ברור שקיימים המונים של טבעיים מהסוג הנדון במשפט, שכן מספר הטבעיים גדול בהרבה ממספר ההגדרות. יש הלא אינסוף טבעיים ולעומתם, מספר ההגדרות האפשריות הוא סופי, על אף היותו עצום ורב\הערת␣שוליים{ואף מספר זה הוא אפסי לאין שיעור לעומת המספר של גרהאם, מספר טבעי שהוא כה גדול, שהיקום כולו אינו מספיק לכתיבתו, אפילו לא בצורת מגדל חזקות, ואפילו אם נניח שכל ספרה תופסת את נפח פלאנק בלבד. בכל זאת, את המספר של גרהאם של ניתן להגדיר בפחות מתריסר מילים: "המספר הגדול ביותר ששימש אי פעם בהוכחה מתימטית עד שנת 1980".
}. שהרי, יגדל מספר המילים בשפה העברית ככל שיגדל, סופי הוא יוותר עדיין. ממילא, מספר הצירופים בני פחות מתריסר מילים בשפה העברית, לא יוכל להיות אינסופי.
נסמן על כן בְּ-\שי{X} את הקבוצה האינסופית של המספרים שאינם גדירים. הרי ודאי שימצא ב-\שי{X} אחד, \שי{x}, הקטן שבחבריו, כלומר כזה \שי{x} הנקבע על ידי: \[
∃ x∈X\mbox{}∀ x'∈X\mbox{}x'≠x\mbox{}⇒ x'>x
\] אלא, וכאן נגלה הפרדוקס שבדבר, שכן המשפט שהובא בפתיח נצרך לתשע של מילים בלבד כדי להגדיר את \שי{x} זה עצמו, ועל כן על כרחך נמצאת אומר~$x∉ X$.

ההיתר של הפרדוקס נגלה מהבנת השוני בין הגדרה מתימטית "רגילה" ובין שפה טבעית. הפרדוקס שבמשפט, אשר כתוב בשפה טבעית, נובעת מכך שהמשפט מדבר על משפטים אחרים בשפה הטבעית. בשפה טבעית קיימת אפשרות לנסח בשפה עצמה משפטים הנוגעים למשפטים אחרים בשפה עצמה. עצימת העין נוכח הקשיים שבמגבלות של התייחסות עצמית, היא זו שמביאה לסתירה.
בניסוח המשפט האמור או כל גִּרְסָה אחרת שלו\הערת␣שוליים{ ובפרט, המשפט שמופיע בכותרת סעיף זה (ואגב, הערת שוליים זו, אף היא דוגמא לטקסט בשפה טבעית המתייחס לעצמו.)
}, טמונה הנחה סמויה לפיה קיימת משמעות מדוייקת למונחים "גדיר", "בר-הגדרה" או "ניתן לתיאור".

נכון, נדמה כאילו אנחנו יודעים לזהות הגדרה מדוייקת כשזו מופיעה לפנינו, ולדחות מלפנינו כל הגדרה ערטילאית או לא מדוייקת. אך מתברר כי אי אפשר לעשות זאת בהיסח הדעת במבנים שכליים כגון תיאוריה מתימטית או שפה טבעית, שהם מורכבים מספיק כדי להכיל "התייחסות עצמית". "התייחסות עצמית" זו היא שעומדת מאחורי הפרדוקס של ברי, כמו גם הפרדוקס של ראסל \גיבור{("תהי~$U$ הקבוצה של כל הקבוצות שאינן מכילות את עצמן, האם~$U∈U$?")} ופרדוקסים אחרים\הערת␣שוליים{ובהם פרדוקס הגלב, הפרדוקס של בהארטירהארי, והפרדוקס של גרלינג-נלסון, הדן בלוגיקות שאינן עוסקות בעצמן. }.

בפרט, המשפט שבפתיח הוא הגדרה העוסקת בהגדרות. כיוון שמשפט זה הוא הגדרה בעצמו, הוא עוסק בעצמו. אמרנו שהפרדוקס שבמשפט נובע מההנחה הסמוייה שהמונח "גדיר", הוא אכן מוגדר היטב. ציינו, שההטעייה המבריקה שבמשפט היא שאכן, בדרך כלל, קל להבחין בין משהו שניתן להגדרה, ומשהו שאינו ניתן להגדרה. הפרדקוס יופרך משנשים לב לכך שההבחנה הקלה בין הגדרה ובין "לא הגדרה" נכשלת כשהיא נדרשת להגדרות, כמו המשפט שבפתיח, שמתייחסות לעצמן. הפרדוקס של ברי מוכיח מגבלה מהותית של שפה אנושית\הערת␣שוליים{המונח שפה אנושית כולל גם שפות טבעיות מהאטרוסקית אל שְׂפַת הפקצות, ושפות מלאכותיות, מהאספרנטו ועד הננדורינית שדיברו אותה בני לילית שבחבל ננדור שבארץ התיכונה.
}. בפרט, ניתן (במאמץ הגדרתי לא מבוטל) לנסח משפט מתימטי שמשמעותו היא הבאה

\begin{mybox}
תהי H שפה אנושית שהיא מורכבת מספיק כדי לאפשר:
\begin{itemize}
• דיון על השפה בתוך השפה עצמה,
• דיון על קבוצות לא חסומות בגודלן.
\end{itemize}
הרי בתוך השפה H ישנם משפטים שלא ניתן לתת להם משמעות עקבית עם שאר מרכיבי השפה.
\end{mybox}

נדגיש שתי אלו:
\begin{itemize}
• אי אפשר ליצור את הפרדוקס בלא שהשפה H תהיה מסוגלת להכיל היגדים בדבר "קבוצת כל מי שאפשר לתאר ב-H באמצעות תריסר מילים". הפרדוקס נשען על היגד זה.
• לעומת זאת, אין צורך לדרוש שהשפה H תהיה מורכבת דיה כדי לדון במספרים או במתימטיקה. כל שנדרש הוא האפשרות לדון בקבוצות לא חסומות. ניתן לנסח את הפרדוקס של ברי כך שיסוב על סדריות, ואפשר גם לנסות לכתוב: \גיבור{"הַפְּרִיט הָרִאשׁוֹן שֶׁיִּמָּכֵר בְּ-\שי{EBAY} מִבֵּין אֵלּוּ שֶׁתֵּאוּרָם נִדְרָשׁ לְיוֹתֵר מִתְּרֵיסָר מִלִּים"}. ניסוח זה מדגים היטב את הדרישה לדיון בקבוצה בלתי חסומה. אין במשפט משום כל, אם קבוצת הפריטים שעשויה להימכר ב-\שי{EBAY} היא קטנה ממספר התיאורים בני תריסר מילים או פחות. לעומת זאת, הפרדוקס נוצר אם מספר הפריטים שיכול להמכר ב-\שי{EBAY} הוא בלתי חסום, ולכן גדול ממספר התיאורים הללו.
קורט גֶדֶל הכיר בעובדה שמשפט מתימטי מוביל לפרדוקס אם המשפט טוען שהוא עצמו אינו נכון. אבל הוא גם הבחין בכך שאין פרדוקס במשפט הטוען שהוא עצמו אינו יָכִיחַ. משפט אי השלמות הראשון של גֶדֶל הוא ניסוח מתימטי מדוייק של הטענה לעיל בדבר שפה טבעית.
\end{itemize}

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

\begin{mybox}
בכל תיאוריה מתימטית~$ T~$ אשר מקיימת את התנאים הבאים:
\begin{itemize}
• העדר סתירות
• מורכבת מספיק כדי להכיל את האקסיומות של המספרים הטבעיים.
\end{itemize}
קיים משפט~$ T~$, כך ש-$ T∈T~$, הוא נכון, אך לא יָכִיחַ בתיאוריה~$ T~$.
\end{mybox}
האינטואיציה של הוכחת משפט אי השלמות הראשון של גדל מתחילה בדיון בפרדוקס של ברי. אלא שבתיאוריות המתימטיות של גדל, קל למשפטים שמדברים על עצמם. הסיבה היא שבמערכת מתימטית שהיא מספיק מורכבת כדי להכיל את המספרים הטבעיים מצטיינת בתכונות הבאה:
\begin{itemize}
• כל משפט, הוכחה או טענה, ניתנים לקידוד כמספר טבעי בודד. (קידוד זה נקרא קידוד גדל, ואפשר לבנות אותו למשל באמצעות התרגום של כל משפט לכתיב ה-ASCII).
• כל משפט שעוסק במספרים, עוסק לפיכך גם במשפטים, וגם בהוכחות של משפטים.
\end{itemize}
 המשפט~$ T~$ נבנה באופן הבא: נסתכל על כל ההוכחות האפשריות בתיאוריה~$ T~$, נקודד כל הוכחה כזו כמספר טבעי, ואחר נבנה מספר טבעי אחר, מספר גדל של התיאוריה~$ T~$, שהוא גם נכון כמשפט, וגם לא יָכִיחַ בתיאוריה~$ T~$. מספר גדל של תיאוריה מסוימת, הוא קידוד של משפט נכון אך לא יָכִיחַ בתיאוריה. הבניה של מספר גדל היא מפורשת. היא בונה מספר כזה המקודד משפט שהוכחתו שונה מזו מכל ההוכחות הקיימות בשפה. ואינה נובעת משיקולי ספירה.

 במילים אחרות, משפט אי השלמות של גדל אומר שתיאוריה מתימטית אם היא לא טריביאלית, היא לא שלמה.

וכיצד כל זאות קשור לנושא?
\newpage

§ הסכנה שבתכניות המשעשעות המדפיסות את עצמן

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

לפיכך, ההגדרה היא כדלקמן: תכנית המדפיסה את עצמה, \מונח{דפסן}, היא תכנית לא ריקה אשר לא מקבלת קלט והפלט היחידי שלה הוא התכנית עצמה (כך נימנע גם מלכלול תכניות אשר מדפיסות לאורך הזמן את כל הפלטים האפשריים, בזה אחר זה, עד אשר תדפיס בעת מסוים את עצמה). תכניות מעין אלו מהוות אבן שואבת במדעי המחשב, וניתן להתייחס אליהן בצורה מתמטית באופן הבא: אם נתייחס לסביבת הביצוע כאל פונקציה (מקבוצת התכניות אל קבוצת הפלטים), נקבל כי תכנית המדפיסה את עצמה היא נקודת שבת\הערת␣שוליים{\שי{Fixed Point}. נציין כי למונח הרחבות רבות בתחום הטופולוגיה המתמטית, המכלילות את המונח למרחבים מטריים שונים. לפרטים נוספים.}.

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

נראה מספר דוגמאות\הערת␣שוליים{ראוי להדגיש נקודה חשובה זו.} לתכניות המדפיסות את עצמן:

\הכנס␣קוד{sources/quine.java}{Java}{גאוה}
\הכנס␣קוד{sources/quine.perl}{Perl}{Perl}
\הכנס␣קוד{sources/quine.py}{Python}{Python}

ולהלן דוגמה ב-שיא חד, המלווה בהסבר ובהרחבה.

מהו הטריק\הערת␣שוליים{סיבה נוספת להתעניינות בנושא זה היא הופעתו כשאלה בשיעורי הבית, בסמסטר בו נכתב סיכום זה.} שבזכותו עובדות תכניות אלו? ניתן לחלק באופן גס את הקוד ל-2 חלקים:
\begin{enumerate}
• מערך מחרוזות ו/או אוסף קבועים, אשר מכילים את קוד הביצוע של התכנית.
• קוד הביצוע של התכנית, אשר מכיל הוראות להדפסה פעמיים של מערך המחרוזות המדובר, וכן קבועים נוספים הדרושים לשכפול מדויק של הקוד לתוך מה שיודפס.
\end{enumerate}
בריצת התכנית יודפס, כאמור, פעמיים המערך והתווים הרלוונטיים - בפעם הראשונה עבור הדפסת החלק הראשון של התכנית (מערך המחרוזות), ובפעם השנייה עבור הדפסת החלק השני - קוד הביצוע ממש.

עם זאת, טמונה בקודים מעין אלו סכנה של ממש. תכניות כאלו עשויות להוות כלי להחדרה של \מונח{וירוסים}\הערת␣שוליים{למעשה, מינוח מדויק יותר הוא סוס טרויאני, מונח שעל משמעותו ניתן וראוי לדון רבות.} בידי זֵדִים\הערת␣שוליים{הסבר מלא למילה זֵד שֵם ז: בלשון המקרא אדם רע, רשע; "טָפְלוּ עָלַי שֶׁקֶר זֵדִים" (תהלים קיט סט). [מילון רב-מילים]}. כתב על כך \מונח{קן תומפסון}\הערת␣שוליים{אבי !UNIX חלוץ אמריקאי בתחום מדעי המחשב, ידוע בשל תרומתו לפיתוח שפות התכנות B,Go והגדרת UTF-8} במאמרו\הערת␣שוליים {להבנה מלאה יותר של אופן הפעולה של סוס טרויאני, ניתן ללחוץ כאן.
 }.

נתחיל בתיאור מנגנון רלוונטי. נניח שנתון לנו קובץ המקור של המהדר של שפת \סי, ונרצה להכניס בו שינוי מסוים - נרצה שבהינתן תו הבקרה \קד{/v}, תודפס מפלצת \קד{ASCII} הזו. כיצד נעשה זאת? ובכן, בהינתן קוד המקור האידיאלי הבא של המהדר, נגלה כי אין זו משימה קשה במיוחד:

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

על מנת להשלים את הקוד על מנת שיכיל את התוספת שלנו (ידוע שהדפסת מפלצות \קד{ASCII} שכאלו מביאה למורת רוח מרובה בקרב המשתמשים), נבצע את השינוי הבא:
הוספנו את השורה המתאימה, וננסה עתה להדר את הקובץ החדש של המהדר באמצעות המהדר הישן שברשותנו. אך, אבוי, שוד ושבר, נקבל שגיאה! הרי המהדר הישן לא יודע מפלצות \קד{ASCII} מהן, ולא יודע מהו התו \קד{/v}.

נרצה לפיכך "לאלף" את המהדר הישן להכיר תוסף זה, על מנת שיוכל להדר אותו, ולהפוך אותו ל\מונח{מהדר} תקני המכיל את השינוי. ניגש אפוא לקובץ המקור של המהדר הישן, ונוסיף בו את השינוי הבא (אחרון, מבטיחים!):
כעת, המהדר הישן מכיר את התו \קד{/v}. נניח שקיימת מחרוזת תווים כלשהי, המייצגת את מפלצת ה-\קד{ASCII} המועדפת עלינו, וכי היא מיוצגת ע"י ה-11 בדוגמה שלהלן. נהדר באמצעותו את המהדר החדש שכתבנו, ונקבל \מונח{קובץ} \קד{binary} שמכיל \מונח{מהדר} חדש, המטמיע את התוספת החדשה. ניתן באמצעות תוצר זה להדר תכניות שיבצעו תוספת זו.

באופן דומה, אך זהה מבחינה רעיונית, ניתן, לאחר מאמץ מחשבתי ניכר, לתאר נזקים כבירים אף יותר מהופעה של מפלצת (מאיימת ככל שתהיה) על צג המחשב. דוגמה לכך היא פריצה לחשבונות פרטיים במערכות \שי{UNIX}, ע"י הוספת פרצה, לפיה ניתן יהיה להתחבר לכל חשבון באמצעות סיסמא כלשהי (נניח \קד{iAmHackerHoHoHo}). בשלב הבא, נבצע את התהליך כפי שביצענו בדוגמה הקודמת, ובאמצעותו נקבל את מערכת \שי{UNIX} החדשה, בה תהיה קיימת פרצה זו. הפרצה תהיה מקודדת ומוטמעת במערכת החדשה, ללא יכולת זיהוי. זהו \מונח{סוס טרויאני} עמיד בפני התקפות.

§ גבולות התכנית
נוסחת הירון לחישוב השטח S של משולש שגדלי צלעותיו הן a, b וְ C היא אלגנטית במיוחד: \[
S=√{p·(p-a)·(p-b)·(p-c)}
\] כאשר \[
p=\frac{a+b+c}{2}
\] הבה נכתוב בזריזות תכנית \פסקל בעבור הנוסחה הזו

\הכנס␣קוד{sources/triangle.pas}{Pascal}{לדוגמא תכונית}

מי שכתב אי פעם תכנית בִּשְׂפַת מכונה כלשהי, יכול לשוות בנפשו כיצד יתרגם המהדר את התכנית לעיל לשפת המכונה שעליה היא תרוץ, למעט ענין פעוט אחד: ידוע לכל כי ישנן פקודות מכונה לחישוב הסכום הסכום, המכפלה, ההפרש והמנה של שני מספרים ממשיים. אבל, כיצד יחושב השורש הריבועי? אפילו אם נניח כי יש המכונה מכילה פקודה לחישוב השורש, עדיין ישנה השאלה של התרגום של פקודות הקלט והפלט שבתכנית, שהרי אלו בוודאות אינן מצויות באוסף פקודות המכונה.
על כרחך אתה נאלץ לומר כי התרגום של תכנית בִּשְׂפַת תכנות מסוימת, פשוטה ככל שתהייה, לשפת מכונה, חייב להשתמש בפרודצרות ופונקציות אשר אינם מצויים בתכנית עצמה. השאלה בה עוסק פרק זה היא, בניסוח לא פורמלי, היא: "כיצד נקבעים גבולות התכנית?"\הערת␣שוליים{הקורא הכמה בשלב זה לארמז ספרותי או תיאולוגי, יכול לללמוד מעט על התהליכים היהודיים והננוצריים של קנוניזציה של כתבי הקודש, אשר בהם נקבע אלו מבין הספרים שייכים לתנ"ך. פלגים שונים בנצרות הגיעו לתוצאות שונות ביחס לשאלה זו. מעניין לציין כי בתנ"ך היהודי ישנם מה שהיינו קוראים שגיאות עקידה \שי{(Linking Error)}, ככתוב "כִּי אַרְנוֹן גְּבוּל מוֹאָב בֵּין מוֹאָב וּבֵין הָאֱמֹרִי. עַל-כֵּן יֵאָמַר בְּסֵפֶר מִלְחֲמֹת יְהוָה: אֶת וָהֵב בְּסוּפָה וְאֶת הַנְּחָלִים אַרְנוֹן…" אלא שספר מלחמות ה' אינו מצוי בידינו. (אגב, בברית החדשה הנוצרית, בכל הגדרותיה השונות, אין הפניה לספרים חיצוניים או לספרים שאבדו.)
}, או בלשון אחרת, בהינתן שְׂפַת תכנות מסוימת, ובהינתן כל קטעי הקוד הקיימים בעולם הכתובים בשפה זו:
\begin{itemize}
• אלו קטעים יוצרים תכנית מסוימת, ואלו תכנית אחרת?
• האם יתכן שקטע קוד מסוים יהיה שייך ליותר מאשר תכנית אחת? ואם כן, מתי יקרה הדבר?
• היאך מוגדר בכלל "קטע קוד"?
• בהינתן כל קטעי הקוד מהם מורכבת התכנית, כיצד נקבע מאיזה מהם יתחיל הביצוע?
\end{itemize}
כדי לדעת את התשובה לכל אלו, בדרך כלל אין זה מספיק להכיר את הדקדוק והמשמעות של השפה, אלא נדרשת הבנה של הסביבה בה פועלת התכנית, והאינטרקציה של התכנית עם סביבתה.
הגישה הנקוטה בִּשְׂפַת פסקל, היא \גיבור{הגישה האוטרקית}, על פיה יש רק קטע קוד אחד היוצר תכנית, וקטע זה מצוי בקובץ אחד. כל הפונקציות והפרוצדורות אשר יכולות להיות מופעלות על ידי התכנית מצוייות בקטע זה, או מוגדרות על ידי שְׂפַת התכנות.

בְּPascal ישנה גם מילה שמורה \מש{program} המגדירה את התחלת התכנית, באשר הביצוע יתחיל במילה השמורה \מש{begin} המתאימה לה. בשפות אוטרקיות אחרות, כמו גירסאות ישנות של בייסיק למשל, תחילת הביצוע יכולה להקבע בדרך אחרת, למשל מהפקודה הראושנה בתכנית.

הגישה האוטרקית בְּPascal נובעת מייעוד השפה ללומדים. לשם קיומו של חזון זה, בחר מתכנן השפה גם להימנע משימוש בספריות. כל הפונקציות והפרודצרות אשר בהן יכול המתכנת בשפה להשתמש הן אלו שהוא כתב בעצמו, או אלו שמוגדרות כחלק מהשפה. בפרט, המפרט של הפונקציות \מוגדרת␣מראש{writeln} וְ-\מוגדרת␣מראש{writeln} מצוי בהגדרת השפה עצמה. יוצר השפה בחר שלא להשתמש במילים שמורות בכדי לציין את הפונקציות והפרוצדרות המוגדרות על ידי השפה, אלא לקבוע שאלו הם מזהים מוגדרים מראש. הבחירה הזו מבטיחה ששירותים אלו יהיו זמינים למתכנת בכל עת, זאת, מבלי לסרבל את השפה בהגדרה של מספר גדול של מילים שמורות, אשר ימנעו מהמתכנת להשתמש במילים אלו לצרכיו.

רעיון זה מתפרס בְּPascal לא רק על הפונקציות והפרוצדרות, אלא גם על הטיפוסים היסודיים, ואף על שמות הקבועים. המילים \קד{true}, \קד{integer} וְ-\קד{false} אינן מילים שמורות בשפה, והמתכנת יכול להגדירן מחדש. בפרט, התכנית הבאה המדגימה את סיסמת המפלגה בספר 1984 של ג'ורג' אורוול היא תכנית חוקית בְּPascal:

\הכנס␣קוד{sources/1984.pas}{Pascal}{מספר? ... הוא ושקר שקר הוא אמת}

מרבית הסיכויים הם שאם תזין תכנית זו במהדר ה-Pascal החביב עליך, הוא יפלוט בתגובה שגיאות הידור לרוב. התפתחות השפה הביאה לכך שהמילים \קד{true} וְ-\קד{false} הפכו בחלוף השנים למילים שמורות, וההבדל בין המילה \קד{true} ובין הישות שהיא מציינת, הלא היא ערך האמת המופשט, נמוג.

מנגד, האבחנה בין הסימון ובין הישות שהוא מייצג מתחזקת בשפות מודרניות, אשר בהן הסימן '+' למשל, נבדל מפעולת החיבור אותה הוא מייצג. כך ב\שי{C++} למשל, המתכנת יכול להשתמש בסימן זה גם לפעולות אחרות באמצעות תהליך הקרוי העמסת אופרטורים.

מנגד לגישה האוטרקית, קיימת \גיבור{הגישה המטאפיזית} הנקוטה על ידי שְׂפַת \סי. על פי גישה זו, תיחום התכנית נעשה מבחוץ לה, באמצעות כלים אשר אינם מוגדרים בשפה. בגישה זו, אוסף של קטעי קוד המצויים (למשל) בקבצים שונים נאסף על ידי העוקד\הערת␣שוליים{הלא הוא ה-Linker} לכדי תכנית אחת, אך השפה עצמה אינה מתייחסת להגדרת העוקד. העוקד גם מחבר לתכנית ספריה של שירותים. הספריה היא סטנדרטית, במובן זה, שלהגדרת השפה נלווית גם הגדרה של הספריה הסטנדרטית, אך שתי הגדרות אלו הן בלתי תלויות. ניתן לשנות ולפתח את הספריה הסטנדרטית מבלי לשנות את השפה ואת המהדר שלה. המתכנת אף הוא יכול לבחור להחליף חלקים מהספריה הסטנדרטית, או את התכנית כולה.

נעיין כעת בתכנית שלום עולם בִּשְׂפַת \סי:
\הכנס␣קוד␣נקי{sources/hello.c}{C}

טרם שנמשיך, נדרשות כמה מילים כדי להפיס את דעתו של מי שיזעם על התכנית כפי שהיא כתובה כאן, משום שלכאורה חסרה בה ההוראה:
\setLTR{}

\cpp{#include <stdio.h>}

\setRTL{}

אשר כביכול גורמת לקישור של התכנית לספריה הסטדנדרטית, אשר בה מוגדרת הפונקציה \קד{printf}.

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

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

לאחר דברי פיוס אלו נציין כי התכנית הזו משתמשת בשירותי הספריה הסטנדרטית בשתי דרכים.
\begin{itemize}
• ראשית, ישנו השימוש הברור בפונקציה \קד{printf} אשר לקוחה מהספריה. פונקציה זו כתובה בִּשְׂפַת C, והיא נגישה לכל דיכפין אשר יכול אף לשנות אותה אם יחפוץ בכך.
• התלות השניה בשירותי הספריה היא בקביעה כי נקודת תחילת הביצוע היא בפונקציה \קד{main}. החלטה זו מוכתבת על ידי העוקד, אשר אוסף את כל קטעי התכנית, ובכללם שלושת השורות מעלה, הגדרת הפונקציה \קד{printf} מהספריה, כמו גם את כל הפונקציות והמשתנים בהם משתמשת \קד{printf}, ויצירת תכנית אחת מהם. אחרי האיסוף הזה, יש גם לקבוע את נקודת ההתחלה.
העובדה שהעוקד בוחר להתחיל את הביצוע בפונקציה \קד{main} היא מוסכמה, אולם, ישנם מקרים בהם היא אינה מקויימת. כך למשל תכניות הכתובות עבור מערכת ההפעלה חלונות יתחילו ב-\קד{WinMain}.
\end{itemize}

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

\begin{center}
\rowcolors{2}{red!10!green!10}{blue!15}
\begin{tabular}{c c c}
\toprule

&
אוטרקית
&
מטאפיזית/ספריה
 ⏎
\midrule
נקודת התחלה
&
שורה ראשונה או ממילה שמורה
&
\pbox{7cm}{
\leavevmode
\newline
מוגדרת מחוץ לתכנית.
בדרך כלל ישנם נהגים מקובלים, קונבנציות, (אולם הנוהג אינו בהכרח דין).
\newline
}
 ⏎
\pbox{3cm}{
\leavevmode
\newline
קלט/פלט
שגרות עזר וכיוצא בזה
\leavevmode
\newline
}
&
 אחד משלושה:
\pbox{4cm}{
\leavevmode
\newline
- מהווים חלק מהגדרת השפה
\newline
- מזהים מוגדרים מראש
\newline
- מילים שמורות
\newline
}
&
בקבצי ספריה למיניהם שעל המתכנת לחבר לתכנית.
 ⏎
טיפוסים יסודיים
&

\pbox{5cm}{
\leavevmode
\newline
-בשפה
\newline
-מילים שמורות
\newline
-מילים מוגדרות מראש
\newline
}

&
בדרך כלל מילים שמורות
 ⏎
היקף התכנית
&
תמיד יהיה בקובץ בודד
&
\pbox{6cm}{
\leavevmode
\newline
 מוגדר מחוץ לשפה באמצעות הלינקר או כלי אחר.
 כלומר מוגדר גם מחוץ לתכנית עצמה.
\newline
}
 ⏎

\bottomrule
\end{tabular}
\end{center}
§§ רקורסיה הדדית
נתאר לעצמנו שתי פונקציות הקוראות זו לזו ברקורסיה הדדית, \קד{f()} ו-\קד{g()}. נתאר לעצמנו שני טיפוסים \שי{Male} ו-\שי{Female} שהגדרת האחד תלויה בהגדרת האחר.
איך ניתן לכתוב זוג הגדרות שתלויות זו בזו הדדית? במיוחד בשיטה שבה ה-\מונח{טווח} מתחיל בהגדרה, ומסתיים בסוף הבלוק?
שתי אפשרויות עיקריות:
\begin{enumerate}
• ניתן להשתמש בשם של טיפוס עוד לפני שהטיפוס הוגדר.
\begin{itemize}
• בִּשְׂפַת \סי, אפשר להגדיר משתנה המצביע לטיפוס רשומה, עוד לפני שהטיפוס מוגדר.

\הכנס␣קוד␣נקי{sources/pointer_before_declaretion.c}{C}

 בדוגמה רואים הגדרה של המשתנה \קד{p} שהטיפוס שלו הוא מצביע למשתנה מהטיפוס \קד{struct Data} וזאת עוד לפני שהטיפוס \קד{struct Data} הוגדר.
• בשפת \פסקל, ניתן להשתמש בטיפוס של מצביע לטיפוס, עוד טרם שהטיפוס הוגדר.
\end{itemize}
• ביצוע Declaration לאחד מבני הזוג, ואחר כך, Definition לבן הזוג השני, ולבסוף Definition לבן הזוג השני.
\begin{itemize}
• הנה דוגמא בִּשְׂפַת \סי:

\הכנס␣קוד␣נקי{sources/declarationₐnd_definition.c}{C}

• והנה דוגמא בִּשְׂפַת \פסקל:

\הכנס␣קוד␣נקי{sources/declarationₐnd_definition.pas}{Pascal}

\end{itemize}
\end{enumerate}

§§ רקורסיה הדדית הבנויה בשפה
כאשר תוכננו שפות התכנות הראשונות, למחשבים היה כוח חישוב מועט. ההידור התבצע ככל שאפשר במעבר אחד על התכנית. זו אחת הסיבות לקיום כלל ה-Scope לפיו הגדרה מוכרת מהשורה שבה היא מבוצעת ועד לסוף הבלוק. בשפות תכנות חדשות יותר, כמו \גאוה, שְׂפַת \שי{C++}, וְ-\שי{C＃}, קיים מנגנון חזק יותר, לפיו הטווח של הגדרה הוא הבלוק שבה היא מתבצעת, כלומר ה-Scope של הגדרה יכול להתחיל עוד לפני שההגדרה עצמה בוצעה.

\הכנס␣קוד␣נקי{sources/friendlyᵣec.cpp}{C++}

§§ הגדרות קולטרליות
הגדרות של פונקציות ומחלקות בתוך מחלקה של \שי{C++}, או \גאוה, מוכרות בכל המחלקה.
תכונה זו מאפשרת רקורסיה הדדית. המצב ההפוך מתקיים בהגדרות קולטרליות. המילה
קולטרלי באה לומר שאין לאף הגדרה עדיפות לאחרת, כל אחת מהן יכולה להופיע לפני כל
אחת אחרת. הצורך בהגדרות קולטרליות (או סימולטניות) אינו ברור מיידית, וזו אולי
הסיבה שהן נדירות, אבל הן קיימות בִּשְׂפַת \שי{ML}, באמצעות המילה השמורה \מש{and}.

הנה דוגמא לשימוש במילה זו
\begin{center}
\קד{val x=y and y=x}
\end{center}

בהגדרה זו, המשמעויות של המזהים x וְ-y מתהפכות.
§ בעיית העצירה

\leavevmode
\newline
אֵין תָּכְנִית שֶתֵּדַע מָה אֲחֶרֶת עוֹשָׂה.
זוֹ עֻבְדָּה מוּצָקָה, וְלֹא סְתָם מְצוּצָה:
תּוּכָל עַד מָחָר אֶת הַמֹּח לִשְבֹּר-

לֹא תּוּכַל לְנַבֵּא אִם תָּכְנִית תַּעֲצֹר.
נַנִּיחַ שֶ-P הִיא שִיטָה שֶכָּזֹאת
שֶלְּתוֹך כָּל תָּכְנִית מְצִיצָה, לְגַּלּוֹת
שֶאֵין שוּם לוּלָאָה אֵינְסוֹפִית מִסְתַּחְרֶרֶת;
וְאִם אֵין שָם כְּלוּם- אָז 'טוֹב!' הִיא אוֹמֶרֶת.

מְזִינִים אֶת הַקּוֹד וְאֶת כָּל הַנְּתוּנִים,
וְ-P אָז תַּחֲקֹר בַּפְּרָטִים הַקְּטַנִּים
וּתְחַשְבֵּן אִם הַכֹּל מִסְתַּדֵּר כָּרָאוּי
(בְּנִגּוּד לְמַצָּב לוּלָאִי לֹא רָצוּי).

הָאֱמֶת הִיא שֶ-P כָּזוֹ לֹא תִּתָּכֵן,
כִּי אִם תִּכָּתֵב P, וְלִי תִּנָּתֵן,
אֶשְתַּמֵּש בָּהּ לִצֹּר כֶּשֶל לוֹגִי מֻצְלָח
שֶיִּשְבֹּר הֶגְיוֹנְךָ וְחוּשֶיךָ יִמְעַךְ.
\leavevmode
\newline

הַתַּכְסִיס הוּא פָּשוּט וְיוֹצֵא מִן הַכְּלָל.
אַגְדִּיר עוֹד תָּכְנִית, בְּשֵם Q, לְמָשָל,
שֶתִּקַּח כָּל תָּכְנִית, וּלְ-P אָז תִּקְרָא,
שֶתִּקְבַּע אִם יֵש בָּהּ לוּלָאָה מַמְאִירָה;
\leavevmode
\newline

אִם יֵש, אָז Q תַּדְפִּיס 'אוּף!' וְתִפְרֹש;
אַךְ אִם אֵין, אָז Q תַּחֲזֹר לָהּ לָרֹאש,
וְתַתְחִיל מֵחָדָש, תִּסְתּוֹבֵב בְּלִי לַחֲדֹל,
עַד יִגְוַע הַיְּקוּם וְיִקְפָּא וְיִבֹּל.

\leavevmode
\newline

הַתָּכְנִית הַזּוֹ, Q, לֹא תֻּשְאַר יְתוֹמָה;
מַמְזֵר שֶכְּמוֹתִי- אַפְעִילָהּ עַל עַצְמָהּ!
אֵיךְ Q תִּתְנַהֵג בְּמַצָּב שֶכָּזֶה?
כְּשֶתִּקְרָא אֶת עַצְמָהּ- מָה בְּדִיּוּק תַּעֲשֶׂה?
\leavevmode
\newline

אִם P תְּגַלֶּה לוּלָאָה- Q תֵּצֵא;

אַךְ P אֲמוּרָה לְדַוֵּחַ עַל זֶה.

כָּךְ שֶאִם Q תֵּצֵא- אָז P תֹּאמַר 'טוֹב!'

וְQ תֵּאָלֵץ לְהַתְחִיל שוּב לָסֹב!
\leavevmode
\newline

מָה שֶ-P לֹא תַּגִּיד, Q יָשָר מְעַקֶּמֶת;

Q גוֹרֶמֶת לְ-P לָצֵאת דֵּי מְטֻמְטֶמֶת.

כִּי אִם P צוֹדֶקֶת- יוֹצֵא שֶשִּקְּרָה;
\leavevmode
\newline

וְאִם מְשַקֶּרֶת- אֱמֶת הִיא דִּבְּרָה!

כָּזֶה פָּרָדוֹקְס אֱלֶגָנְטִי יָצָא,

פָּשוּט בִּגְלַל P, הַהֲלִיך הַמֻּמְצָא.

אִם תַּנִּיחַ שֶ-P אֲמִתִּי- הִסְתַּבַּכְתָּ;

בְּפַח הַיּוֹקְשִים שֶטָּמַנְתִּי- נִלְכַּדְתָּ!
\leavevmode
\newline

אָז אֵיך נֵחָלֵץ מִצָּרָה כֹּה סְבוּכָה?

לֹא צָרִיךְ שֶאַגִּיד; תְּנַחֵש לְבַדְּךָ.

מַסְקָנָה הֶכְרֵחִית, שֶבְּזֶה הָעוֹלָם,

יְצוּר אֲגָדִי כְּמוֹ P לֹא קַיָּם.
\leavevmode
\newline

לֹא תַּצְלִיחַ לִבְנוֹת מִין מִתְקָן שֶכָּזֶה

שֶיּוּכַל לְנַבֵּא מָה מַחְשֵב יַעֲשֶׂה.

זֶה בִּלְתִּי אֶפְשָרִי. וְלָכֵן אֲנָשִים

מוֹצְאִים בָּאגִים לְבַד; מַחְשֵבִים הֵם טִפְּשִים!!
\leavevmode
\newline