forked from CS234319/safot
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathlisp.tex
2408 lines (2152 loc) · 124 KB
/
lisp.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
%\documentclass[a4paper,12pt,reqno]{article}
%\usepackage{00}
%\raggedbottom
\def\CPL{\E|C|\xspace}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Code for collecting code exerpts into a separate library and kernel files
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcounter{kernel}
\newcounter{library}
\setcounter{library}0
\newread \tempFile % A temporary reading stream
\newwrite \slidesFile % A stream to save kernel functions
\newwrite \kernelFile % A stream to save kernel functions
\newwrite \libraryFile % A stream to save library functions
\immediate \openout \kernelFile=\jobname.kernel.lisp
\immediate \openout \libraryFile=\jobname.library.lisp
\immediate \openout \slidesFile=\jobname.slides.tex
\newenvironment{XLISP}{%
\def\fileName{\jobname.slides.\arabic{kernel}.lisp}%
\csname filecontents*\endcsname[overwrite]{\fileName}%
}{%
\csname endfilecontents*\endcsname%
\lstinputlisting[language=kernel,style=display,backgroundcolor=\color{olive!10}]{\fileName}%
}
% An environment for writing kernel functions
\newenvironment{KERNEL}{%
\stepcounter{kernel}
\def\fileName{\jobname.kernel.\arabic{kernel}.lisp}%
\csname filecontents*\endcsname[overwrite]{\fileName}%
}{%
\csname endfilecontents*\endcsname%
\LTR
\lstinputlisting[language=kernel,style=display,backgroundcolor=\color{olive!10}]{\fileName}%
\endLTR
\openin \tempFile=\fileName
\immediate\write\slidesFile {\unexpanded{\begin{frame}[fragile]}}
\immediate\write\slidesFile {\noexpand\begin{LISP}}
\begingroup\endlinechar=-1
\loop\unless\ifeof \tempFile
\read\tempFile to\fileline % Read one line and store it into \fileline
\immediate\write \kernelFile {\unexpanded\expandafter{\fileline}}
\immediate\write \slidesFile {\unexpanded\expandafter{\fileline}}
\repeat
\endgroup
\immediate\write\slidesFile {\noexpand\end{LISP}}
% \immediate\write\slidesFile {\unexpanded{\end{frame}}
\immediate\write\slidesFile {}
\closein \tempFile
}
% An environment for writing library functions
\newenvironment{LIBRARY}{%
\stepcounter{library}
\def\fileName{\jobname.library.\arabic{library}.lisp}%
\csname filecontents*\endcsname[overwrite]{\fileName}%
}{%
\csname endfilecontents*\endcsname%
\LTR
\lstinputlisting[language=kernel,style=display,backgroundcolor=\color{orange!20}]{\fileName}%
\endLTR
\newread \tempFile % open the file to read from
\openin \tempFile=\fileName
\begingroup\endlinechar=-1
\loop\unless\ifeof \tempFile
\read\tempFile to\fileline % Read one line and store it into \fileline
\immediate\write \libraryFile
{\unexpanded\expandafter{\fileline}} % print the content to copy.txt
\repeat
\endgroup
\closein \tempFile
}
%
§ מבוא
שפת LISP (כקיצור של \E|LIst ProceSsing|), היתה, יחד עם שפת Fortran (קיצור של
של \LR{FORmula TRANslation}), אחת משתי שפות התכנות הראשונות. ליספ פותחה
ב-MIT על ידי \E|John McCarthy| עוד בשנת 1956. אולם מלכתחילה, ליספ לא נתפסה על
ידי ממציאה כשפת תכנות, אלא כתחשיב מתימטי המיועד לכתיבת אלגוריתמים, הדומה לתחשיב
כתחשיב מתימטי המיועד לכתיבת אלגוריתמים, הדומה לתחשיב
ה-$λ$ \E|(lambda calculus)|. רק לאחר מכן, מומש התחשיב כשפת תכנות.
בתחשיב של \E|McCarthy|, כל תכנית היא מה שנקרא "\ע|ביטוי~S|", והרצת התכנית קרויה
"שיערוך" (\E|evaluation|) של הביטוי. יתירה מכך, כל הנתונים בשפת ליספ גם הם
ביטויי~\E|S|. תכנית בשפת ליספ היא פונקציה שיכולה לקבל כארגומנטים ביטויי~S והיא
מחזירה ביטוי~\E|S|, וכאמור, כל פונקציה כזו, היא בעצמה ביטוי~\E|S|. שפת ליספ
נחנה לכן בתכונה הידועה בשם \ע|הומואייקוניות| (\E|homoiconicity|) לפיה ניתן מתוך
השפה לבצע מניפולציה על תכניות הכתובות בשפה כאילו היו הן נתונים. שפות אחרות שהן
הומואייקוניות כוללות את פרולוג, \LR{Wolfram Mathematica}, \E|Snobol|
ו-\E|Julia|. שפות כמו~\CPL, פסקל, ו-\E|Java|, כמו מרבית שפות התכנות אינן
הומואייקוניות.
בנוסף לתחשיב McCarthy הציג גם אלגוריתם אוניברסלי, \E|eval|, המסוגל להריץ תכניות
בליספ. ליספ הפכה מתחשיב מתימטי לשפת תכנות כאשר האלגוריתם הזה מומש בשפת מכונה.
מאוחר יותר, נמצא מי שכתב מימוש של \E|eval| בשפת ליספ עצמה.
אחת המטרות החשובות של סיכום זה היא הדגמה כיצד ניתן לממש את אלגוריתם השיערוך של
שפת ליספ באמצעות שפת ליספ עצמה (עיין בהמשך, \פנה|סעיף:מימוש|).
שפת ליספ שימשה בין השאר לפיתוח \E|Macsyma|, התכנית הראשונה לחישוב מתימטי
סימבולי, כולל נגזרות, אינטגרלים, ופתרון סימבולי של משוואות.
דוגמה לחישוב סימבולי ב-\E|Macsyma| היא חישוב האינטגרל המסויים \[
∫₀⁴ e^{√{ay}}dy=-2
\] עבור~$a>0$, בעזרת ההחלפה~$y=z²/a$. ראשית נודיע-\E|Macsyma| שהערך של a חיובי,
\begin{LISP}
(%i1) assume(a > 0)$
\end{LISP}
ואחר כך, נבקש ממנה לנסות לבצע את האינטגרציה הסימבולית:
\begin{LISP}
(%i2) 'integrate (%e**sqrt(a*y), y, 0, 4);
4
/
[ sqrt(a) sqrt(y) (%o2) I %e dy
]
/
0
\end{LISP}
ורק אחר נבצע את ההחלפה:
\minipage[t]{0.5\textwidth}
\scriptsize
\begin{LISP}
(%i3) changevar (%, y-z²/a, z, y);
0
/
[ abs(z)
2 I z %e dz
]
/
- 2 sqrt(a)
(%o3)-----------------------------
a
\end{LISP}
\endminipage
שפת ליספ שימשה גם לפיתוחה של \E|ELIZA| תכנית המחשב הראשונה שהייתה מסוגלת לנהל
שיח עם משתמש בדומה לבוט. ELIZA ניסתה לדמות בשיחה את תפקיד הפסיכיאטר או
הפסיכותראפיסט ודו שיח עמה נראה כך
\begin{minipage}\textwidth
\begin{LTR}
\scriptsize
\begin{verbatim}
ELIZA: Please tell me what’s been bothering you.
ME: Oh, hello, ELIZA. It’s been a long time.
ELIZA: Hi. What seems to be your problem?
ME: Lately, I’ve been feeling a little depressed.
ELIZA: And how do you feel right now?
ME: I feel sad, but relieved to be writing.
ELIZA: Of what does feeling sad remind you?
\end{verbatim}
\end{LTR}
\end{minipage}
שפת ליספ שימשה גם לפיתוח
\E|Grammarly|, התכנה המפורסמת לתיקוני שגיאות כתיב ודקדוק.
במהלך השנים, נולדו ניבים רבים לליספ שהרחיבו בהרבה את ההגדרה המקורית. בשנת 1984
אוחדו רבים מהניבים
הללו לכדי הגדרה של שפה אחת הידועה בשם \E|Common Lisp|. ניבים נפוצים
אחרים כוללים את Emacs Lisp (המשמשת כשפת סקריפטים בעבור עורך הקבצים (\E|text
editor|) הידוע בשם \E|Emacs|), AutoLisp (המשמשת כשפת סקריפטים בתכנת
\E|AutoCad|), \E|Scheme|, \E|Clojure|, ואפילו שפת התכנות \E|Dylan|, אשר למרות
הדקדוק השונה בתכלית שלה, היא מבוססת על ליספ.
\begin{editing}
§ שפות המגדירות את עצמן
בהינתן שפת תכנות אוניברסלית~$𝓛$ יש טעם לשאול באיזו שפה כתוב המהדר או המפרש
של~$𝓛\). אך, כיוון ש-\(𝓛$ היא אוניברסלית, הרי אם אפשר לכתוב את המהדר (לחילופין,
המפרש) של~$𝓛$ בשפה '~$𝓛$ הרי גם ניתן לכתוב את המהדר (לחילופין, המפרש) בשפה~$𝓛$
עצמה. מתברר שמקובל מאוד לכתוב את המהדר של השפה בשפה עצמה. כך למשל, המהדר של
שְׂפַת \סי כתוב בִּשְׂפַת \סי. המהדר של שְׂפַת \גאוה כתוב בִּשְׂפַת \גאוה, וכו'. כמובן שהדבר
מעורר קושי: כי אם המהדר עבור שפה מסוימת כתוב באותה שפה, הרי כיצד הודר המהדר?
התשובה הפשוטה היא שהמהדר הידר את עצמו, וכך הם בדרך כלל פני הדברים. אלא, שהדבר
מוביל לרקורסיה אינסופית.
חז"ל-הבחינו בבעיה דומה של רקורסיה אינסופית מעין זו בסוגיא התלמודית הידועה בשם
"צבת בצבת עשוייה". בגמרא, במסכת פסחים דף נ"ד עמוד א' נאמר:
\יניב{צבתא בצבתא מתעבדא וצבתא קמייתא מאן עבד הא לאי בריה בידי שמים}
ובתרגום לעברית: "הצבת אינה נעשית אלא בצבת אחרת. וראשונה מי עשאה? על כרחך מאליה
נעשית בידי שמים.". כלומר, צבת שהיא מכשיר לאחיזת מטילי ברזל לשם ליבונם באש
ועיבודם, עשוייה אף היא ברזל, ואף היא מיוצרת בצבת אחרת שקדמה לה. כיצד אם כן
נוצרה הצבת הראשונה? הפתרון המוצע על ידי הגמרא הוא שהצבת הראשונה נבראה בערב שבת
הראשון, בזמן "בין השמשות", שעה שאלוהים סיים לברוא את כל הדברים האחרים, והתכונן
לשבות ממלאכתו לקראת ירידת השבת.
פתרון ניסי שכזה אינו בא בחשבון עבור שפות תכנות. מסכת פסחים מציגה גם דרך אחרת
שבה יוצרה הצבת הראשונה (על ידי דפוס נחושת). לעומת זאת, בשפות תכנות, ניתן לבצע
תהליך של \E|bootstrapping| שבאמצעותו ניתן לפתח מהדר המסוגל להדר את עצמו. התהליך
דומה מאוד למה שהיה עושה נַפָּח עני שברשותו ברזל, אך לא כסף לרכישת צבת. נפח כזה היה
משתמש בכבשנו באופן איטרטיבי, כאשר בכל פעם הוא היה משתמש בגוש הברזל הדומה ביותר
לצבת שיש ברשותו, כדי ליצר קירוב טוב יותר לצבת.
§§ מדד לאלגנטיות של שפה
אבן בוחן מרתקת לאלגנטיות של שְׂפַת תכנות היא אורך המהדר (או המפרש) של השפה, כאשר
הוא כתוב בשפה עצמה. שהרי ככל שהשפה מורכבת ומתוחכמת יותר, מחד קל יותר לכתוב את
המהדר, אך מאידך המהדר לעסוק בכל המורכבות והעושר הזה. לחילופין, שפה שהיא פשוטה
ביחס (כמו שְׂפַת ה-\שי{batch} של \קד{DOS}) שהוזכרה מעלה, היא קלה אולי להידור, אבל
הפשטות של השפה מהווה אבן נגף בבואנו להשתמש בה כדי לכתוב מהדר.
הנה מספר אורכים אופייני של מהדר לשפה הכתוב בשפה עצמה:
\begin{enumerate}
• מהדר לשפת \סי הכתוב בשפה עצמה, דורש כמה עשרות אלפי שורות. המהדר \שי{gcc} מפרס
על פני כשבעה מיליון שורות קוד.
• המהדר הראשון לשפת פסקל, אשר נכתב בִּשְׂפַת \פסקל דרש כשבעת אלפים ומאתיים שורות.
• משערך לשפת ליספ הכתוב בליספ, הידוע גם כפונקציה האוניברסלית \קד{eval} דורש
כמאה שורות.
• לעומת זאת, מפרש בסיסי לשפת פרולוג הכתוב בפרולוג יכול להכתב בשורה אחת בלבד,
ומפרש מתוחכם, המאפשר למשל מעקב אחרי החישוב, לא יארך בדרך כלל יותר מעשר שורות.
\end{enumerate}
§§ הגדרת שפות להגדרת שפה פורמלית, באמצעות עצמן
מהי שפה פורמלית, כל שְׂפַת תכנות היא שפה פורמלית. ישנן שפות פורמליות שאינן שפות
תכנות. שפות תכנות אינן מכניזים נוח להגדרת שפה פורמלית. מכניזמים להגדרת שפות
פורמליות. מתברר שגם מכניזמים אלו הם שפה פורמלית.
בדרך כלל, קל הרבה יותר להגדיר שפה פורמלית, מאשר לכתוב מהדר של השפה בעזרת עצמה.
הנה דוגמאות.
\begin{itemize}
✦ הגדרת BNF בעזרת עצמו
✦ הגדרת EBNF בעזרת עצמו
✦ ביטוי רגולרי המגדיר מהו ביטוי רגולרי חוקי
\end{itemize}
קל להגדיר את משפחת ה-BNF באצעות ביטוי רגולרי.
קל להשתמש ב-BNF כדי להגדיר מהו ביטוי רגוליר.
אבל, ניתן להגדיר ביטוי רגולרי באמצעות ביטוי רגולרי? לא! רקורסיה.
טבלת סיכום, הגדרה הדדית.
מסיבה זו, השפות BNF וְ-EBNF הן אלגנטיות יותר מביטויים רגולריים.
\end{editing}
§ מיני-ליספ
הדיון כאן איננו עוסק בליספ כשפת תכנות, וגם לא באף אחד מהניבים הנפוצים או הפחות
נפוצים שלה, אלא מתרכז אך ורק בהצגת גלעין \E|(core)| מינימלי של השפה, שהוא בעצמו
ניב של ליספ: למעט הבדלים זעירים, תכנית מיני-ליספ היא תכנית חוקית של \E|Common Lisp|.
אבל, לא כל תכנית חוקית של \E|Common Lisp| הי תכנית חוקית של מיני-ליספ. אנו נכנה גלעין זה
בשם \ע|מיני-ליספ|.
שני מרכיבים בגלעין זה:
\begin{description}
✦ [פונקציות פרימיטיביות] אילו הן פונקציות פשוטות אשר הן "אקסיומטיות",
כלומר, הגלעין מניח שהן קיימות וכי הן מצייתות למפרט מוגדר היטב. אולם, האופן
שבו ממומשות הפונקציות הפרימיטיביות אינו חלק מהגלעין.
✦ [פונקציות סיפרייה] אילו הן פונקציות אשר אותן
הגלעין מממש באמצעות קריאה לאחת או יותר מהפונקציות הפרימיטיביות.
\end{description}
לפיכך, התיאור המלא של שפת מיני-ליספ, כולל שני מרכיבים בלבד: המפרט של הפונקציות
הפרימיטיביות והמימוש של פונקציות הסיפריה.
המפרט מופיע ב\פנה|טבלה:מיני|.
\begin{table}[!hbt]
\newcounter{magicrownumbers}
\newcommand\rownumber{\stepcounter{magicrownumbers}\arabic{magicrownumbers}}
% \begin{adjustbox}{max height=0.9\textheight}
\rowcolors{2}{olive!10}{white}
\begin{tabularx}\textwidth{>{\scriptsize}r>{\setLR\scriptsize\setLR}c>{\scriptsize}c
>{\setRL\scriptsize\raggedleft\arraybackslash}X
>{\scriptsize\setLR\raggedright\arraybackslash}X
>{\scriptsize\setLR\raggedright\arraybackslash}X
}
\toprule
＃ &
\normalsize \bfseries {\text{/arity}}שם &
\normalsize \bfseries סמנטיקה &
\normalsize \bfseries תמצית &
\multicolumn1c{\normalsize \bfseries \RL{דוגמאות}} ⏎
\midrule
\rownumber &
atom/1 &
eager &
בדיקה אם הארגומנט הוא אטום &
\lisp{(atom nil)}~$⇒$ \lisp{T} \newline
\lisp{(atom t)}~$⇒$ \lisp{T} \newline
\lisp{(atom '(a a))}~$⇒$ \lisp{NIL} \newline
\lisp{(atom 'a)}~$⇒$ \lisp{T} ⏎
\rownumber &
car/1 &
eager &
חילוץ האיבר הראשון ברשימה &
\lisp{(car '(b.a))}~$⇒$ \lisp{B} \newline
\lisp{(car '(b a))}~$⇒$ \lisp{B} \newline
\lisp{(car '(a))}~$⇒$ \lisp{A} \newline
\lisp{(car 'a)}~$⇒$ \text{✗} \newline
\lisp{(car ())}~$⇒$ \text{✗} ⏎
\rownumber &
cdr/1 &
eager &
חילוץ שארית הרשימה, כלומר הרשימה ללא האיבר הראשון &
\lisp{(cdr '(a.b))}~$⇒$ \lisp{b} \newline
\lisp{(cdr '(a b))}~$⇒$ \lisp{(b)} \newline
\lisp{(cdr '(b))}~$⇒$ \lisp{NIL} \newline
\lisp{(cdr t)}~$⇒$ ✗ \newline
\lisp{(cdr ())}~$⇒$ ✗ \newline
\lisp{(cdr nil)}~$⇒$ ✗ ⏎
\rownumber &
($n≥0$) cond/n &
normal &
הכללה של פקודת \E|if|. &
\lisp{(cond (t 'A))}~$⇒$ \lisp{A} \newline
\lisp{(cond (nil 'A) (t 'B))}~$⇒$ \lisp{B} \newline
\lisp{(cond (nil 'A) (t 'B) (t 'C))}~$⇒$ \lisp{B} \newline
\lisp{(cond (nil 'A) (nil 'B) (nil 'C))}~$⇒$ \lisp{nil}\newline
\lisp{(cond)}~$⇒$ \lisp{nil} ⏎
\rownumber &
cons/2 &
eager &
הוספת איבר בתחילת רשימה &
\lisp{(cons 'a '(b c))}~$⇒$ \lisp{(A B C)} \newline
\lisp{(cons 'b nil)}~$⇒$ \lisp{NIL} \newline
\lisp{(cons 'a 'b)}~$⇒$ \lisp{(A.B)} ⏎
\rownumber &
eq/2 &
eager &
בדיקה אם שני הפרמטרים הם אטומים השווים זה לזה &
\lisp{(eq t t)}~$⇒$ \lisp{T} \newline
\lisp{(eq t nil)}~$⇒$ \lisp{NIL} \newline
\lisp{(eq nil nil)}~$⇒$ \lisp{T} \newline
\lisp{(eq 'a 'a)}~$⇒$ \lisp{T} \newline
\lisp{(eq '(a a) '(a a))}~$⇒$ \lisp{NIL} ⏎
\rownumber &
($n≥0$) error/n &
eager &
הדפסת כל הפרמטרים ועצירת ביצוע התכנית &
\lisp{(error)}~$⇒$ ✗ \newline
\lisp{(error A)}~$⇒$ ✗ \newline
\lisp{(error 'my-error 'message)}~$⇒$ ✗ ⏎
\rownumber &
set/2 &
eager &
יצירת קישור בין אטום ובין ביטוי~\E|S|. &
\lisp{(set 'a '(b c))}~$⇒$ \lisp{(b c)}\newline
\lisp{(set 'b nil)}~$⇒$ \lisp{NIL}
\label{primitive:count}
⏎
\bottomrule
\end{tabularx}
\כיתוב|הפונקציות הפרימיטיביות של מיני-ליספ|
\תגית|טבלה:מיני|
%\end{adjustbox}
\end{table}
המימוש של פונקציות הסיפרייה אף הוא אינו ארוך ביותר, והוא מונה
\begin{LTR}
\lstinputlisting[language=kernel,style=display,
numbers=left,
stepnumber=1,
numbersep=2pt,
xleftmargin=3ex,
numberblanklines=false,
numberstyle=\tiny\bf,
backgroundcolor=\color{orange!20}
]{\jobname.library.lisp}
\end{LTR}
על אף המינימליות של שפת מיני-ליספ, שפה זו היא "טיורינג שלמה". רוצה לומר: ניתן
לכתוב במיני-ליספ כל תכנית שאפשר לכתוב בשפות תכנות פחות סגפניות ממנה, כמו פסקל
ו-\E|C|.
הדיון כאן איננו עוסק בליספ כשפת תכנות, וגם לא באף אחד מהניבים הנפוצים או הפחות
נפוצים שלה, אלא מתרכז אך ורק בהצגת גלעין \E|(core)| מינימלי של השפה, שהוא בעצמו
ניב של ליספ. אנו נכנה גלעין זה בשם \ע|מיני-ליספ|. שפת מיני-ליספ היא מינימלית
ביותר, והיא כוללת שמונה פונקציות פרימיטיביות בלבד, כלומר פונקציות שלא ניתן
להגדירן באמצעות פונקציות אחרות:
\ציינן
✦ \ע|פונקציות מבניות|: \E|car|, \E|cdr| ו-\E|cons|, אשר מאפשרות ליצור ביטוי
\E|S|, ולפרק אותו לחלקיו.
✦ \ע|פונקציות לוגיות|: \E|atom|, \E|eq| ו-\E|cond|, המאפשרות לבדוק את תכנו של
ביטוי~\E|S|.
✦ \ע|פונקציות נוספות|: \E|set| המאפשרת לתת שמות לביטויי~\E|S|, ו-\E|error|
המסייעת בטיפול במקרים שבהם החישוב נתקל בשגיאה.
===
\end{document}
\פנה|טבלה:מיני| שבהמשך מסכמת את רשימת הפונקציות הפרימיטיביות שבמיני-ליספ. כל
הפונקציות הפרימיטיות של מיני-ליספ הן גם פונקציות פרימיטיביות של מרבית הניבים
החשובים של ליספ, ובפרט של \E|Common Lisp|.
בנוסף, מכילה מיני-ליספ מספר קטן של פונקציות "סיפריה", כלומר פונקציות הכתובות
בשפת מיני-ליספ תוך שימוש בפונקציות הפריטיביות.
\ציינן
✦ \ע|קבועים| (פונקציות ללא פרמטרים): \E|t| (המציין את הערך הבוליאני של אמת) ו-\E|nil|
(המציין את הערך הבוליאני של שקר).
✦ \ע|פונקציה לוגית|: \E|null| (פונקציה חד-מקומיות הבודקת אם ביטוי הוא \E|nil|).
✦ \ע| פונקציות המסייעות בהגדרת פונקציות|:
\E|quote|, \E|defun|, \E|ndefun|, \E|lambda| ו-\E|nlambda|.
===
\פנה|טבלה:סיפריה| שבהמשך מסכמת את רשימת פונקציות הסיפריה של מיני-ליספ, ומביאה
גם את מימושן במיני-ליספ. מלבד ndefun ו-nlambda ניתן למצוא את פונקציות הסיפריה
של מיני-ליספ בכל הניבים האחרים של השפה, אם כי לעיתים הפונקציה defun נקראת בשם
אחר.
בנוסף לפונקציות הפרימיטיביות ולפונקציות הסיפריה, שפת מיני-ליספ תומכת, כמו מרבית
הניבים של ליספ, בפונקציה \E|eval| אשר מקבלת ביטוי S ומשערכת אותו. הפונקציה
eval אינה פונקציה פרימיטיבית, אלא היא ממומשת כחלק מ-\E|evaluate|, אלגוריתם
השיערוך של מיני-ליספ, אשר גם הוא ממומש כפונקציה במיני-ליספ.
בניגוד לניבים האחרים של ליספ, שפת מיני-ליספ אינה תומכת במספרים ובפעולות
אריתמטיות. רוב הניבים של ליספ, יודעים להדר, באופן חלקי או מלא, תכניות ליספ לשפת
מכונה. גם הידור כזה אינו נחוץ במיני-ליספ. על אף המינימליות של שפת מיני-ליספ,
בניגוד לניבים האחרים של ליספ, שפת מיני ליספ אינה תומכת במספרים ובפעולות
שפה זו היא טיורינג שלמה: כל תכנית שאפשר לכתוב בכל שפת תכנות, אפשר לכתוב גם
במיני-ליספ.
בפרט, כפי שנדגים כאן, ניתן לממש את האלגוריתם \E|eval| עצמו במיני-ליספ, תוך
שימוש בפונקציות פרימיטיביות או בפונקציות הסיפריה, אשר כאמור מוגדרות באמצעות
הפונקציות הפרימיטיביות. מימוש זה הוא פשוט וקצר יחסית ועולה לכדי כמאה שורות
בלבד.
לבד מהמימוש של eval שפת מיני-ליספ מעניינת שכן היא מציגה בתמציתיות את מרבית
הרעיונות החשובים של ליספ, כגון עיבוד רקורסיבי של רשימות, קישור של שמות לערכים,
העברת פרמטרים, הסתכלות על תכנית כמבנה נתונים, ועוד.
לא רק תכניות הם ביטויי~\E|S|. כל הערכים בשפת ליספ הם ביטויי~S
\E|(S-Expressions)|. המונח~S-Expression בא לעולם כקיצור למונח \E|symbolic
expression| (ביטוי סימבולי). המילה "סימבולי" מטעימה שלא בהכרח מדובר
בביטוי מתימטי כגון~$13+41/2$, שבו המשמעות של כל הסימנים ידועה בדרך כלל, אלא
בביטוי כללי שיכול להכיל סימבולים שמשמעותם דורשת הגדרה מפורשת, כגון:
\begin{equation*}
(\amalg \circledcirc \maltese) ⊘ (\Re \wr \Game)
\end{equation*}
בביטוי זה, ניתן לנחש כי מופיעים בו האופרנדים ($\amalg$,~$\maltese$,~$\Re$ ו-$\Game$) ואת
האופרטורים ($\circledcirc$,~$⊘$ ו-$\wr$). ניתן גם לשרטט עץ המתאר את מבנה הביטוי:
\begin{LTR}
\begin{forest}
s tree [$⊘$,[$\circledcirc$ [$\amalg$] [$\maltese$]] [$\wr$[$\Re$][$\Game$]]]
\end{forest}
\end{LTR}
אולם, ייתכן גם כי האופרנדים הם
הסימנים~$\Game$ ו-$\maltese$
ואילו~$\amalg$,~$\circledcirc$,~$\maltese$ ו-$\Re$
הם אופרטורים אונאריים.
\begin{LTR}
\begin{forest}
s tree [$⊘$,[$\amalg$ [$\circledcirc$ [$\amalg$]]]
[$\Re$ [$\wr$ [$\Game$]]]]
\end{forest}
\end{LTR}
אולם, ייתכן גם כי האופרנדים הם
אולם כיוון שמשמעות האופרנדים והאופרטורים אינה ידועה, לא נוכל לחשב את הביטוי.
המונח שיערוך כולל בתוכו שני מרכיבים עיקריים: ראשית, איתור המשמעות של הסימבולים
המופיעים בביטוי, ושנית, חישוב הביטוי בהתאם למשמעות זו. בדרך כלל מרכיב החישוב של
השיערוך מחשב ביטוי חדש, אך לעיתים השיערוך מייצר משמעות בעבור סימבולים שלא הייתה
להם משמעות טרם השיערוך. במילים אחרות, השיערוך משתמש בהגדרות של סימבולים, ויכול
גם לייצר הגדרות כאלו.
בשפת תכנות כדוגמת~\CPL העוברות הידור \E|(compilation)| שני מרכיבי השיערוך
נפרדים. מתן המשמעות לסימבולים ואיתור המשמעות של סימבולים נעשה על ידי המהדר
\E|(compiler)|. החישוב עצמו נעשה בזמן ריצת התכנית. בליספ, כמו בשפות אחרות שבהן
יש פירוש \E|(interpretation)| של תכניות, שני השלבים של השיערוך נעשים על ידי
האינטרפטר \E|(interpreter)| אשר קורא תכניות ומשערך אותן.
\begin{minipage}\linewidth
\begin{mdframed}[backgroundcolor=Lavender!20]
האינטרפטר של ליספ, כמו האינטרפטר של פרולוג, \E|bash| ושפות תכנות אחרות העוברות
אינטרפרטציה, עובד במחזורים, בשיטה הידועה בשם
\LR{\textbf Read \textbf Evaluate \textbf Print \textbf Loop}
או בראשי תיבות \E|REPL|:
\ספרר
✦ \E|READ|: האינטרפטר קורא את הקלט, אשר חייב להיות ביטוי~\E|S| במקרה של ליספ.
✦ \E|EVALUATE|: האינטרפטר משערך את ערכו של הביטוי שקרא.
✦ \E|PRINT|: אם השיערוך של הקלט מצליח, אז האינטרפטר מדפיס את תוצאת השיערוך.
אחרת, האינטרפטר ידפיס הודעת שגיאה מתאימה.
✦\E|LOOP|: האינטרפטר חוזר לצעד הראשון, לקריאת הקלט הבא.
===
\end{mdframed}
\end{minipage}
\normalsize
האינטרפטר של ליספ מכיל לכן שלושה מרכיבים עיקריים:
\אבגד
✦ ה-Reader אשר קורא קלט שהוא סדרה של תווים, ובונה את מבנה הנתונים המתאים
לביטוי ה-S המתאים לתווים אלו.
✦ המשערך \E|(Evaluator)| אשר משערך ביטויי-S אלו.
✦ ה-Printer אשר מקבל ביטוי~S כמבנה נתונים ומתרגם אותו לסדרת תווים אשר
מייצגת מבנה נתונים זה.
===
כאן נניח שה-Reader וה-Printer נתונים והם דומים לאלו שבכל ניב של ליספ, ונתאר את
המימוש של המשערך של מיני-ליספ.
§ ביטויי~S
§§ ביטויי~S כשפה פורמלית
\newcommand\SX{\ensuremath{S_{\text{exp}}}}
בהינתן אלפבית~$Σ$, נגדיר את~$\SX(Σ)$, קבוצת "ביטויי ה-S", מעל~$Σ$.
אינטואיטיבית, ביטוי~S יכול להיות אטומי, ואז הוא חייב להיות מילה מתוך~$Σ^*$.
ביטוי~S שאינו אטומי הוא בהכרח זוג סדור של שני ביטויי~S אחרים. הזוג הסדור נכתב
עטוף בזוג סוגריים ושני הביטויים הסימבוליים שבו מופרדים בסימן הנקודה.
כמה ביטויי~S מעל האלפבית~$Σ=❴a,b,c❵$ הם \[
a,b,(a.b),(c.(b.a)),((a.b).(a.c))∈\SX❨❴a,b,c❵❩.
\] לעומת זאת,~$(a.b.c)$ אינו שייך ל~$\SX(Σ)$ משום שהוא שלשה סדורה ולא זוג סדור,
ואילו~$(a(b(c)))$ אינו שייך לקבוצה, משום שהוא אינו עונה על הדרישה שבין פריטים
ימצא סימן הנקודה.
הקבוצה~$\SX(Σ)$ היא שפה פורמלית מעל אלפבית מורחב, המתקבל מהוספת סימן הנקודה
ושני סימני הסוגריים לאלפבית~$Σ$ (אנו מניחים, בלי הגבלת הכלליות, ששלושת הסימנים
הללו אינם מצוים ב-$Σ$).
ניתן לאפיין את השפה~$\SX(Σ)$ באמצעות כללי היסק:
\begin{definition}[ביטויי~S מעל
אלפבית] בהנתן אלפבית~$Σ$ אזי,~$\SX(Σ)$, קבוצת ביטויי ה-S מעל~$Σ$ מוגדרת
באמצעות הבנאי הנולארי (כלומר איברים אטומיים): (fix font here)
\begin{equation*}
\infer{w∈\SX(Σ)}{w∈Σ^*}
\end{equation*} והבנאי הבינארי:
\begin{equation*}
\infer{(τ₁.τ₂)∈\SX(Σ)}{τ₁∈\SX(Σ) &τ₂∈\SX(Σ)}
\end{equation*}
\end{definition}
ניתן להגדיר את~$\SX(Σ)$ גם באמצעות דקדוק חסר הקשר
\begin{equation}
\begin{split}
S &→(S.S)⏎ S &→A ⏎
A &→ε⏎ A &→Aσ₁ ⏎
A &→Aσ₂ ⏎
⋮ ⏎
A &→Aσₙ ⏎
\end{split}
\end{equation} כאשר~$Σ=❴σ₁,σ₂,…,σₙ❵$.
נוח לחשוב על ביטויי~S כעצים בינאריים מלאים (כלומר, כאלו בהם לכל צומת שאינה עלה
יש בדיוק שני בנים) כאשר צומת פנימית של עץ כזה אינו נושא מידע, ואילו עלה מכיל
מילה מתוך~$Σ^*$. \פנה|איור:בינארי| מציג כמה ביטויי S יחד עם התיאור שלהם
כעץ בינארי מלא.
\newcommand{\TopAlign}[1]{\adjustbox{valign=t}{#1}}
\newcolumntype{T}{>{\collectcell{\TopAlign}}c<{\endcollectcell}}
\begin{figure}[htbp]
\כיתוב|ביטויי S והייצוג שלהם כעץ בינארי מלא|
\תגית|איור:בינארי|
\centering
\begin{LTR}
\rowcolors{2}{olive!10}{white}
\begin{tabular}{*7T}%
$(ab.cd)$ &
$(abcd.ε)$ &
$((ab.cd).ε)$ &
$(ab.(c.d))$ &
$((a.b).(c.d))$ &
$(a.(b.(c.d)))$ &
\multicolumn1c{$(((a.b).c).d)$} ⏎
\scriptsize
\Forest{s tree [{},cons[$ab$,atom][$cd$,atom]]} &
\scriptsize
\Forest{s tree [{},cons[$abcd$,atom][$ε$,atom]]} &
\scriptsize
\Forest{s tree [{},cons[\relax,cons[$ab$,atom][$cd$,atom]][$ε$,atom]]} &
\scriptsize
\Forest{s tree [{},cons[$ab$,atom][{},cons[$c$,atom][$d$,atom]]]} &
\scriptsize
\Forest{s tree [{},cons[{},cons[$a$,atom][$b$,atom]][{},cons[$c$,atom][$d$,atom]]]} &
\scriptsize
\Forest{s tree [{},cons [$b$,atom],[{},cons [$b$,atom] [{},cons[c,atom] [d,atom]]]] } &
\scriptsize
\Forest{s tree [{},cons [{}, cons [{}, cons
[a,atom][b,atom]] [c,atom] ] [d,atom]] }
\end{tabular}
\end{LTR}
\end{figure}
הייצוג הרגיל של ביטוי S במחשב הוא באמצעות עצים בינאריים. בייצוג זה, כל צומת
פנימי של העץ הוא רשומה המכילה שני מצביעים, שכל אחד מהם יכול להצביע לרשומה אחרת,
או למילה.
§§ ביטויי S בשפת ליספ וכתיב הרשימות
שפת ליספ מרחיבה מעט את ההגדרה של ביטויי-S כפי שהצגנו אותה למעלה, אבל, בסופו של
דבר, ביטויי S בליספ היא הקבוצה~$\SX$ מעל אלפבית הכולל בתוכו את האותיות
\texttt{A} עד \texttt{Z}, ספרות, וגם מרבית הסימנים המיוחדים, כולל \texttt{-},
\texttt{+} ועוד.
לביטוי S מורכב קוראים בשפת ליספ \E|dotted-pair|. לאיבר הראשון ב-dotted-pair
קוראים \E|car|, ולאיבר השני ב-dotted-pair קוראים \E|cdr|. לזוג כולו קוראים
לעיתים גם "רשומת \E|cons|".
לביטוי S אטומי בשפת ליספ קוראים אטום \E|(atom)|. דוגמאות לאטומים הן \E|A|,
\E|12B|, \E|ZZZ| ו-\E|+|. מסיבות היסטוריות, האלפבית של אטומים בליספ אינו מכיל
אותיות קטנות. מערכת ליספ מתרגמת את האותיות הקטנות לאותיות גדולות כשהן מופיעות
בתוך אטומים.
סדרת התווים המגדירה אטום יכולה להיות גם~$ε$, הסידרה הריקה. השם \E|nil| מציין את
האטום שסדרת התווים שלו היא~$ε$. כפי שנראה בהמשך, גם הכתיב \E|()| מציין את האטום
הזה. סדרת התווים המגדירה אטום היא חסרת משמעות בדרך כלל, אולם המתכנת בליספ יכול
להעניק לאטומים נבחרים משמעות. בנוסף, יש מספר אטומים שהמשמעות שלהם מוגדרת מראש
בשפה.
\ע|רשימה| \E|(list)| בליספ היא סדרה של פריטים העטופה בסוגריים. כל פריט ברשימה
יכול להיות אטום, \E|dotted-pair|, או רשימה בעצמו. ניתן לכתוב רווחים לפני ואחרי
כל אחד מהפריטים, אולם שני אטומים רצופים ברשימה חייבים להיות מופרדים בסימן רווח
אחד לפחות.
כך, \E|(a b c d)| היא הרשימה המכילה ארבעה פריטים: האטומים \E|a|, \E|b|, \E|c|
ו-\E|d|. \E|((a.c)c)| היא רשימה המכילה שני פריטים, שהראשון בהם הוא ביטויי~S מורכב,
\E|(a.c)|, והשני הוא האטום \E|c|.
הרשימה הריקה, זו שאינה מכילה אף פריט, נכתבת כ-\E|()|. כל הרשימות, למעט הרשימה הריק הן ביטוי S מורכב. הרשימה הריקה היא אטום, בפרט, האטום \E|nil|.
\E|nil|.
כל רשימה היא כתיב מקוצר לביטוי~\E|S|. הכתיב מוגדר באינדוקציה על אורך הרשימה:
הרשימה הריקה \E|()| היא כתיב אחר לאטום \E|nil|. רשימה שאינה ריקה, היא כתיב
מקוצר לביטוי~S מורכב, כלומר זוג של ביטויי~\E|S|. האיבר הראשון בזוג הוא האיבר
הראשון ברשימה. האיבר השני בזוג, הוא הייצוג של שארית הרשימה.
לפיכך, הרשימה \E|(a b c d)| היא כתיב אחר לביטוי~S
\begin{LISP}
(a.(b.(c.(d.nil))))
\end{LISP}
הפריטים ברשימה הם ביטויי~\E|S|, אבל כיוון שרשימה גם היא ביטוי~\E|S|, רשימה
יכולה להכיל בתוכה רשימות. למשל,
\begin{LISP}
((a b) c)
\end{LISP}
היא רשימה המכילה בתוכה שני פריטים, הראשון שבהם הוא רשימה בת שני אטומים, והשני
שבהם הוא אטום. רשימה זו ניתנת לתיאור באמצעות ביטוי~\E|S|,
\begin{LISP}
((a.(b.nil)).(c.nil))
\end{LISP}
\פנה|איור:רשימות| מציג רשימות אלו כעצים בינאריים מלאים.
\begin{figure}[!htbp]
\caption{יצוג רשימות כעצים בינאריים}
\label{איור:רשימות}
\begin{LTR}
\rowcolors{2}{orange!20}{white}
\begin{tabular}{*5T}
\lisp{()} &
\T|(A)| &
\T|(A B)| &
\T|(A B C D)| &
\multicolumn1c{\T|((A B) C)|}
⏎
\Forest{%
s tree [$ε$,atom]
} &
\Forest{s tree [{},cons [A,atom] [$ε$,atom]]
} &
\Forest{s tree [{},cons [A,atom] [\relax,cons[B,atom][$ε$,atom]]]
} &
\Forest{%
s tree [{},cons [A,atom]
[{},cons [B,atom]
[{},cons [C,atom]
[{},cons [D,atom]
[$ε$,atom]
]
]
]
]
} &
\Forest{%
s tree [{},cons
[{},cons
[A,atom]
[{},cons[B,atom] [$ε$,atom] ]
]
[{},cons
[C,atom]
[$ε$,atom]
]
]
}
\end{tabular}
\end{LTR}
\end{figure}
המשמעות של המונח \ע|כתיב| היא שמרכיב ה-Reader של האינטרפטר של ליספ יכול לקרוא
ביטויי S הנתונים בכתיב הרשימות ושמרכיב ה-Printer של האינטרפטר יתרגם ביטוי S
לכתיב הרשימות כשהדבר אפשרי. (לא כל ביטוי~S ניתן להיכתב בכתיב
הרשימות. למשל הביטוי \E|(a.b)| אינו ניתן להכתב כרשימה. אבל כל רשימה ניתנת
להיכתב כביטוי~\E|S|.) בהעדר סיבה מיוחדת, מתכנתי ליספ נוהגים לכתוב ביטויי~S
בכתיב הרשימות בכל אימת שניתן לעשות זאת.
§§ פעולות על ביטויי~S
שפת ליספ תומכת בפעולות מבניות אלמנטריות על ביטויי~\E|S|. המשמעות של שלושת
האטומים \T|cons|, \T|car|, ו-\T|cdr| מוגדרת מראש במיני-ליספ לציין פעולות
מבניות אלו:
\begin{enumerate}
✦ האטום \T|cons| מציין פונקציה המקבלת שני ביטויי~\E|S|, ומחזירה ביטוי~S
שהוא זוג בו האיבר הראשון הוא הארגומנט הראשון לפונקציה, ואילו האיבר השני של
הזוג הוא הארגומנט השני לפונקציה.
נשים לב לכך שאם הארגומנט השני לפונקציה זו הוא רשימה, אז הפונקציה מחזירה רשימה
חדשה שבה הפריט הראשון הוא הארגומנט הראשון לפונקציה ושאר הפריטים הם כמו אלו
שהיו ברשימה שהיא הארגומנט הראשון: הפעלת cons על האטום a ועל הרשימה
\E|((b~c)~d)| תחזיר את הרשימה \E|(a~(b~c)~d)|.
✦ האטום \T|car| מציין פונקציה המקבלת כארגומנט ביטוי~S אחד. אם ביטוי זה הוא
ביטוי מורכב, הפונקציה מחזירה ביטוי~S שהוא האיבר הראשון בזוג ממנו הארגומנט
בנוי.
לעומת זאת, אם הארגומנט לפונקציה הוא אטום, הפונקציה נכשלת. כשלון זה דומה
לכשלון של ניסיון לחלוקה באפס. ממש כשם שלא כל הפעולות האריתמטיות מוגדרות על כל
המספרים, לא כל הפונקציות המבניות מוגדרות על כל ביטויי~ה-\E|S|.
אם הארגומנט לפונקציה הוא רשימה שאיננה ריקה, אז הפונקציה מחזירה את הפריט
הראשון ברשימה: הפעלת car על הרשימה \E|((b c) d)| תחזיר \E|(b c)|. כאמור, אם
הארגומנט ל-\E|car| הוא אטום, ואפילו יהא זה האטום \lisp{nil}, כלומר הרשימה
הריקה, הפונקציה נכשלת.
✦ האטום \T|cdr| מציין פונקציה המקבלת כארגומנט ביטוי~S אחד. אם ביטוי זה הוא
ביטוי מורכב, הפונקציה מחזירה ביטוי~S שהוא האיבר השני בזוג ממנו הארגומנט בנוי.
אם הארגומנט לפונקציה הוא רשימה שאינה ריקה, אז הפונקציה מחזירה את שארית
הרשימה, כלומר, הרשימה בלעדי האיבר הראשון שבה: הפעלת cdr על הרשימה \E|((b c)
d)| תחזיר \E|(d)|. ממש כמו car הפונקציה cdr נכשלת אם היא מופעלת על אטום בודד
או על הרשימה הריקה.
\end{enumerate}
שפת ליספ תומכת גם בפונקציות לוגיות המאפשרות לבדוק את תוכנו של ביטויי~\E|S|.
שפת מיני-ליספ מסתפקת בשלוש כאלו: המשמעות של שלושת האטומים \T|atom|, \T|null|,
ו-\T|eq| מוגדרת מראש במיני-ליספ לציין פונקציות המאפשרות בדיקות כאלו:
\begin{enumerate}
✦ האטום \T|atom| מציין פונקציה המקבלת ביטוי~S אחד ומחזירה את האטום \T|t| אם
ארגומנט זה הוא אטום, ואחרת את האטום \T|nil|.
✦ האטום \T|null| מציין את הפונקציה המקבלת ביטויי~S אחד ומחזירה את האטום
\T|t|. אם ארגומנט זה הוא האטום \T|nil| ואחרת את האטום \T|t| אם הארגומנט
לפונקציה הוא רשימה, אז הפונקציה מחזירה \T|t| אם ורק אם הרשימה ריקה, ו-\T|nil|
בכל מקרה אחר.
✦ האטום \T|eq| מציין את הפונקציה המקבלת שני ביטויי~S ומחזירה את האטום \T|t|
אם שני הארגומנטים לפונקציה הם אטומים, ושני האטומים הללו שווים. בכל מקרה אחר,
הפונקציה מחזירה את האטום \T|nil|.
\end{enumerate}
ניתן לחשוב על האטום \T|nil| כמסמן את הערך של שלילה לוגית, כלומר \E|false|, ועל
האטום \T|t| כמסמן את ערך האמת, \E|true|.
§§ ביטויי S כעצים מעל אלפבית
ראינו שביטויי S ניתנים להצגה כעץ בינארי שבו העלים, והעלים בלבד, מכילים
סימבולים. אם ביטוי S ניתן להכתב כרשימה של רשימות, אז ניתן להציג את הביטוי הזה
כ\ע|עץ|, שבו קיים סימבול בכל צומת פנימית ובכל עלה. ומספר הבנים של כל צומת
פנימית יכול להיות כלשהו.
בהנתן אלפבית~$Σ$, נגדיר את~$T(Σ)$, קבוצת העצים שבכל צומת שלהם ישנו איבר של~$Σ$.
עץ כזה יכול להיות עץ אטומי, ואז העץ מצטמצם לכדי עלה בודד, שחייב להכיל איבר
של~$Σ^*$. עץ ב-$T(Σ)$ יכול להיות גם עץ מורכב, ובמקרה זה הוא מורכב מצומת פנימי
שבו יש אות של~$Σ$ ומספר כלשהו של בנים שכולם עצים ב-\E|$T(S)$|. בניסוח זה, אנו
רואים שעץ אטומי הוא עץ מורכב שיש לו אפס בנים.
נוכל להגדיר את הקבוצה~$T(Σ)$ כשפה פורמלית מעל אלפבית מורחב, הכולל גם את זוג
סימני הסוגריים ואת סימן הפסיק בא בהנתן אלפבית~$Σ$ אזי,~$T(Σ)$,
\begin{definition}[עצים מעל אלפבית]
בהנתן אלפבית~$Σ$ אזי,~\E|$T(Σ)$|, קבוצת העצים מעל~$Σ$ מוגדרת באמצעות הבנאי
ה-$n$ מקומי
\begin{equation*}
\infer{w(t₁,…,tₙ)∈\SX(Σ)}{w∈Σ^* & n≥0 & t₁∈T(Σ) & t₂∈T(Σ)&⋯& tₙ∈T(Σ)}
\end{equation*}
\end{definition}
כמה איברים פשוטים של קבוצת העצים מעל האלפבית בן שלוש האותיות~$Σ=❴a,b,c❵$ הם \[
a,b(c),a(b,c), a(b(a)), a(a,b,c)∈T(❴a,b,c❵)
\] \cref{figure:tree} מדגים את הטופולוגיה של העץ המורכב יותר \[
a(a(a,ab,abc),b(b,ab(c)),c(c(a(ab)))∈T(❴a,b,c❵)).
\] \begin{figure}[!htbp]
\centering
\forestset{%
x tree/.style={%
for tree={%
math content,
s sep'+=-3pt,
fit=band,
},
},
}
\begin{forest}
s tree [a
[a,[a][ab][abc]]
[b,[b][ab[c]]]
[c,[c[a[ab]]]]
]
\end{forest}
\כיתוב|העץ~$a(a(a,ab,abc),b(b,ab(c)),c(c(a(ab))))$.|
\label{figure:tree}
\end{figure}
אם ביטוי S הוא רשימה של רשימות, אזי ניתן להציגו כעץ. התרגום מתבצע על ידי הפיכת
כל רשימה בביטוי לתת-עץ: האיבר הראשון ברשימה הוא שורש תת-העץ. שאר האיברים
ברשימה, הם הבנים של תת העץ. לדוגמה, בעבור הרשימה
\begin{LISP}
(a b (car x) (+¢¢ b x))
\end{LISP}
יבנה כך העץ
\begin{LTR}
\scriptsize
\forestset{%
x tree/.style={%
font=\ttfamily,
for tree={%
s sep'+=-3pt,
circle,
fit=band,
},
},
}
\begin{forest}
x tree [a,
[a,[car,[x]]]
[+, [b] [x]]
]
\end{forest}
\end{LTR}
נשים לב לכך שהפונקציה \E|car|, כשהיא מופעלת על עץ מעל אלפבית מחזירה את תוכנו
של הצומת שבשורש העץ, ואילו הפונקציה \E|cdr| מחזירה את רשימת הבנים של הצומת, שכל
אחד מהם הוא עץ כזה בעצמו.
§§ עצי שיערוך
ניתן להסתכל על עץ מעל אלפבית, שבו יש סימבול בכל צומת, ושבו הדרגה אינה מוגבלת,
כעץ "שיערוך". נסתכל למשל על הביטוי הבא בשפת~\CPL
\begin{CPP}
f(2) ? g(++a,--b,-sin(c)) : 10+h()
\end{CPP}
חישוב ביטוי כגון זה, דורש ראשית הבנה של המונחים שבו. חישוב הכולל הבנת מונחים
פיענוח משמעות הסימבולים אנו קוראים שיערוך \E|(evaluation)|.
נתאר את השיערוך של הביטוי הזה על ידי הצגתו כעץ השיערוך המתואר ב\פנה|איור:עץ|.
\begin{figure}[!htbp]
\caption{%
עץ החישוב של הביטוי \protect\T|f(2) ? g(++a,--b,-sin(c)) : 10+h()|.
}
\תגית|איור:עץ|
\centering
\begin{LTR}
\scriptsize
\forestset{%
x tree/.style={%
for tree={%
font=\ttfamily\scriptsize,
s sep'+=3pt,
l sep'+=3pt,
fit=band,
},
},
}
\begin{forest}
x tree [\E|:?|,
[$f()$ [$2$]]
[$g()$
[\T|++|[$a$]]
[\T|--|[$b$]]
[$-$ [$\sin()$ [$c$]]]
]
[$+$[$10$][$h()$]]
]
\end{forest}
\end{LTR}
\end{figure}
שיערוך ביטוי ניתן לתיאור רקורסיבי באמצעות העץ שמתאר אותו.
בסיס הרקורסיה הוא שיערוך של עלה, הנעשה באמצעות פיענוח משמעותו.
בעץ שבאיור יש שישה עלים:
\begin{itemize}
✦ משמעות העלים המסומנים ב-$2$ וב-$10$ היא המספרים~$2$ ו-$10$, שכן בשפת~\CPL
סדרות התווים \T|2| ו-\T|10| הן מילולונים, כלומר סדרות אלו מציינות ערך הנקבע
באופן יחיד על ידי תוכן הסדרה, ללא תלות בטבלת סימבולים כלשהי.
✦ משמעות העלים המסומנים ב-$a$, \E|$b$| וב-$c$ נעשית על ידי חיפוש השמות הללו
בטבלת הסימבולים, שכן בשפת~\CPL סדרות התווים \T|a|, \T|b| ו-\T|c| הם מזהים. מזהים
אלו מתייחסים, ככל הנראה, למשתנים אשר הוגדרו קודם.
✦ משמעות העלה המסומן ב-$h()$ גם היא נעשית באמצעות חיפוש השם~$h$
בטבלת הסימבולים, אלא שנדרש שהחיפוש בטבלה יקשור את השם לפונקציה.
אם על פי החיפוש, משמעות השם~$h$ היא משתנה, אזי השיערוך של הביטוי יכשל.
\end{itemize}
שיערוך של צומת פנימית, מתחיל באופן דומה. ראשית יש לברר את משמעות הסימבול אשר
נמצא בתוך הצומת. בדוגמה שלנו, הסימבולים \T|+|, \T|-|, \T|++|, \T|--| ו-\T|?:|
הם אופרטורים של שפת~\E|\CPL|. כלומר, המשמעות שלהם קבועה מראש בשפה, ולכן אין לחפש את
משמעותם בטבלת שמות. לעומת זאת, \T|f|, \T|g| ו-\T|sin| הם שמות שהוגדרו על ידי
מתכנת†{נזכר שהפונקציה~$\sin$ אינה בנויה בשפת~\E|\CPL|, אלא היא מוגדרת באחת
מהסיפריות.} לאחר פענוח משמעותה של צומת פנימית, יש לחשב את ערכי תתי העצים של
הצומת, ולהעביר את תוצאות החישוב של תתי העצים כארגומנטים לפונקציה.
ניתן להבין באופן מדוייק יותר את תהליך השיערוך באמצעות בדיקה של האופן שבו הוא
מתבצע בשפת ליספ.
§ שיערוך של ביטויי S
§§ שיערוך של אטומים
השיערוך של ביטויי-S מוגדר רקורסיבית. בסיס הרקורסיה הוא בשיערוך של אטומים.
שיערוך של אטום אינו נדרש לבצע חישוב, אלא רק למצוא את משמעותו של האטום הנתון.
אטום בליספ הוא מזהה \E|(identifiier)|, וכמו בשפות תכנות אחרות, משמעותו של המזהה
נמצאת בטבלת סימבולים \E|(symbol table)|. טבלת הסימבולים היא מבנה נתונים הקושר בין
שמות ובין משמעותם, ומציאת המשמעות נעשית על ידי חיפוש בטבלה זו.
טבלת הסימבולים בליספ מאורגנת במבנה נתונים הידוע בליספ בשם \E|association list| או
בקיצור \E|a-list|. ה-\E|a-list| היא רשימה של פריטים אשר כל אחד מהם מבטא קישור
של שם לערך. כל פריט הוא dotted-pair אשר ה-car שלו הוא שם
(המיוצג כאטום) ואילו ה-cdr של הפריט הוא משמעותו של השם (שהיא~\E|S-Expression|,
אטומי או מורכב. אם משמעותו של האטום foo היא העץ~$ϕ$ אז הפריט הנשמר ב-\E|a-list|
הוא~\E|$(\text{foo}.ϕ)$|. הקישור בין השם והביטוי מתבטא בעובדה ששני אלו מחוברים
ברשומת \E|cons|.
רשימה ה-\E|a-list| מנוהלת כמחסנית, כלומר פריטים מתווספים ומוסרים ממנה רק
בתחילתה. החיפוש אחר משמעות ברשימה נעשה סדרתית, בסריקה המתחילה בתחילת הרשימה.
חיפוש המשמעות של האטום foo נעצר בזוג הראשון שבו מרכיב השם הוא \E|foo|. החיפוש
נכשל אם לא נמצא זוג כזה.
כאשר האינטרפטר של ליספ מתחיל את פעולתו, ה-\E|a-list| מכילה קישורים בעבור כמה
אטומים המוגדרים מראש בשפה. לשם פשטות נניח בשלב זה כי הרשימה מכילה קישורים בעבור
שני אטומים בלבד: \E|t| ו-\E|nil|.
התוכן המינימלי של ה-\E|a-list| הוא על כן
\begin{LISP}
(
(t.t)
(nil.nil)
)
\end{LISP}
הפריט הראשון ברשימה הוא dotted-pair הקובע שמשמעות של האטום \T|t| היא אטום זה
עצמו. הפריט השני ברשימה קובע שמשמעותו של האטום \T|nil| היא אטום זה עצמו גם כן.
לפיכך, כאשר האינטרפטר של ליספ יקרא את האטום \T|t| הוא ידפיס בתגובה \T|T|, וכאשר
הוא יקרא את האטום \T|nil| הוא ידפיס בתגובה \T|NIL|.
\begin{LISP}
> t
T
> nil
NIL
\end{LISP}
§§ הפונקציה set
הפונקציה \T|set| שבליספ היא פונקציה פרימטיבית המקבלת שני פרמטרים, שהראשון בהם
הוא אטום, והשני הוא ביטוי S כלשהו. הפונקציה מוסיפה ל-\E|a-list| פריט שהוא
dotted-pair
המבטא קישור בין האטום לביטוי. במרבית הניבים של ליספ יש ואריאנטים רבים של
\T|set| אולם במיני-ליספ נסתפק ב-\T|set| בלבד.
אם נזין לאינטרפטר של ליספ את הביטוי
\begin{LISP}
> (set foo (bar baz))
\end{LISP}
כבקשה לקשור את האטום \T|foo| לרשימה \T|(bar baz)|
נתקל בשגיאות, שכן האינטרפטר ינסה לשערך את שני הארגומנטים של הפונקציה \E|set|
טרם שהוא יפעיל פונקציה זו. אלא ששיערוך זה יכשל, שכן לאף אחד משלושת האטומים
המופיעים בקריאה ל-set אין משמעות מלכתחילה.
בכדי להתגבר על מכשלה זו יש להשתמש בפונקציה \T|quote|, פונקציה של ארגומנט אחד
אשר \ע|אינה| משערכת את הארגומנט שלה, אלא מחזירה אותו כמות שהוא.
כך למשל
\begin{LISP}
> (quote foo)
FOO
> (quote (bar baz))
(BAR BAZ)
\end{LISP}
קשירת האטום \T|foo| לרשימה \T|(bar baz)| יכול להעשות באמצעות
\begin{LISP}
> (set (quote foo) (quote (bar baz)))
(BAR BAZ)
> foo
(BAR BAZ)
\end{LISP}
נשים לב לכך שהשערוך של הביטוי
\begin{LISP}
(set (quote foo) (quote (bar baz)))
\end{LISP}
אינו במטרה לחשב ערך כלשהו, אלא במטרה לקשור שם לערך. נזכר שבאופן כללי פעולת
השיערוך בליספ כוללת שלושה סוגים של פעולות: מציאת משמעות של שם, הגדרת
משמעות של שם, וחישוב שהוא הפעלת פונקציה על ביטוי S או ביטויי \E|S|.
בכל זאת, כל פונקציה בליספ חייבת להחזיר ערך.
במקרה של הפונקציה set הערך המוחזר הוא ערכו של הפרמטר השני שלה, ואכן האינטרפטר
מדפיס את הערך \T|(BAR BAZ)| בתגובה לקלט \T|(set (quote foo) (quote (bar
baz)))|.
\begin{LISP}
> (set (quote foo) (quote (bar baz)))
(BAR BAZ)
\end{LISP}
הפונקציה set מוסיפה זוג לתחילת ה-\E|a-list|: אם התוכן של רשימת ה-\E|a-list|