forked from CS234319/safot
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathlisp.tex
2953 lines (2663 loc) · 165 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
\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 \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
% An environment for writing kernel functions
\newenvironment{KERNEL}{%
\stepcounter{kernel}
\def\fileName{\jobname.kernel.\arabic{kernel}.lisp}%
\global\let\savedifeof=\ifeof
\def\ifeof##1{\global\let\ifeof=\savedifeof\iftrue}%
\csname filecontents*\endcsname{\fileName}%
}{%
\csname endfilecontents*\endcsname%
\pagebreak[3]%
\LTR
\lstinputlisting[language=Mini,style=display,backgroundcolor=\color{olive!10}]{\fileName}%
\endLTR
\pagebreak[3]%
\openin\tempFile=\fileName
\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}}%
\repeat
\immediate\write \kernelFile {¢}%
\immediate\write \kernelFile {\unexpanded\expandafter{\pagebreak}[3]}%
\immediate\write \kernelFile {¢}%
\endgroup
\closein \tempFile
}
% An environment for writing library functions
\newenvironment{LIBRARY}{%
\stepcounter{library}
\def\fileName{\jobname.library.\arabic{library}.lisp}%
\global\let\savedifeof=\ifeof
\def\ifeof##1{\global\let\ifeof=\savedifeof\iftrue}%
\csname filecontents*\endcsname{\fileName}%
}{%
\csname endfilecontents*\endcsname%
\pagebreak[3]%
\LTR
\lstinputlisting[language=Mini,style=display,backgroundcolor=\color{orange!20}]{\fileName}%
\endLTR
\pagebreak[3]%
\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}), אחת משתי שפות התכנות הראשונות. LISP פותחה ב-MIT על
ידי \E|John McCarthy| עוד בשנת 1956. אולם מלכתחילה, מלכתחילה, לא נתפסה LISP
על ידי ממציאה כשפת תכנות, אלא כתחשיב מתמטי המיועד לכתיבת אלגוריתמים,
הדומה לתחשיב ה-$λ$ \E|(lambda calculus)|. רק לאחר מכן, מומש התחשיב כשפת תכנות.
בתחשיב של \E|McCarthy|, כל תכנית היא מה שנקרא \textbf{ביטוי~\E|S|}, והרצת
התכנית קרויה "\ע|שיערוך|" (\E|evaluation|) של ביטוי~\E|S|. ניתן לחשוב על
ביטוי~\E|S| כעץ בינארי מלא, כלומר עץ שדרגת כל צומת בו היא 0 או 2. העלים של עץ
בינארי זה, כלומר הצמתים שדרגתם 0, נושאים תגיות. לצמתים שדרגתם 2 לעומת זאת אין
תגיות. לדוגמה, בעץ הבא, יש שני צמתים פנימיים, ושלושה עלים מתוייגים, שניים מהם
בתגית~$a$, והשלישי בתגית~$b$.
\begin{quote}
\center
\Forest{s tree [{},cons
[$a$,atom],[{},cons [$b$,atom] [$a$,atom]]] }
\end{quote}
שיערוך של ביטוי~\E|S| נתון כולל שני צעדים מושגיים:
\אבגד
✦ \ע|מציאת משמעות| בעבור תגיות המופיעות בעליו של הביטוי. למספר תגיות ישנה
משמעות קבועה תמיד. בעבור התגיות האחרות נעזר תהליך השיערוך בטבלת עזר המעניקה
משמעות לתגיות.
✦ \ע|חישוב| ערכו של הביטוי בהתאם לפרשנות. גם חישוב זה יכול להיכשל, ואזי גם
השיערוך נכשל. תוצאת השיערוך היא תוצאת החישוב שנעשה בצעד זה.
===
אם השיערוך אינו נכשל, תוצאת השיערוך היא ביטוי~\E|S|, שהוא, במרבית המקרים, שונה
מהביטוי הנתון. במילים אחרות, שיערוך הוא טרנספורמציה (העשוייה להיכשל) המעתיקה
ביטויי~\E|S| אל ביטויי~\E|S|. פעולת השיערוך אינה מבצעת רק את הטרנספורמציה הזו,
שכן במסגרת השיערוך יתכנו עדכונים לטבלת העזר הנותנת משמעות לתגיות.
לא רק תכניות הן ביטויי~\E|S|. כל הנתונים בשפת ליספ גם הם ביטויי~\E|S|. תכנית
בשפת ליספ היא פונקציה שיכולה לקבל כארגומנטים ביטויי~\E|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}
ואחר כך, נבקש מ-\E|Macsyma| לחשב את האינטגרל הלא מסויים:
\begin{LISP}
(%i2) 'integrate (%e**sqrt(a*y), y, 0, 4);
4
/
[ sqrt(a) sqrt(y) (%o2) I %e dy
]
/
0
\end{LISP}
ורק אחר נבצע את ההחלפה:
\begin{LISP}
(%i3) changevar (%, y-z²/a, z, y);
0
/
[ abs(z)
2 I z %e dz
]
/
- 2 sqrt(a)
(%o3)-----------------------------
a
\end{LISP}
שפת ליספ שימשה גם לפיתוחה של \E|ELIZA|, תכנית המחשב הראשונה שהייתה מסוגלת לנהל
שיח עם משתמש בדומה לבוט. ELIZA ניסתה לדמות בשיחה את תפקיד הפסיכיאטר או
הפסיכותראפיסט ודו-שיח עמה נראה כך
\begin{quote}
\begin{minipage}{0.8\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}
\end{quote}
שפת ליספ שימשה גם לפיתוח \E|Grammarly|, התוכנה המפורסמת לתיקוני שגיאות כתיב
ודקדוק.
במהלך השנים, נולדו ניבים רבים לליספ שהרחיבו בהרבה את ההגדרה המקורית. בשנת 1984
אוחדו רבים מהניבים הללו לכדי הגדרה של שפה אחת הידועה בשם \E|Common Lisp|. ניבים
נפוצים אחרים כוללים את Emacs Lisp (המשמשת כשפת סקריפטים בעבור עורך הקבצים
(\E|text editor|) הידוע בשם \E|Emacs|), AutoLisp (המשמשת כשפת סקריפטים בתכנת
\E|AutoCad|), \E|Scheme|, \E|Clojure|, ואפילו שפת התכנות \E|Dylan|, אשר למרות
הדקדוק השונה בתכלית שלה, היא מבוססת על ליספ.
%
%בהינתן שפת תכנות אוניברסלית~$𝓛$ יש טעם לשאול באיזו שפה כתוב המהדר או המפרש
%של~$𝓛\). אך, כיוון ש-\(𝓛$ היא אוניברסלית, הרי אם אפשר לכתוב את המהדר
%(לחילופין, המפרש) של~$𝓛$ בשפה '~$𝓛$ הרי גם ניתן לכתוב את המהדר (לחילופין,
%המפרש) בשפה~$𝓛$ עצמה. מתברר שמקובל מאוד לכתוב את המהדר של השפה בשפה עצמה. כך
%למשל, המהדר של שְׂפַת \סי כתוב בִּשְׂפַת \סי. המהדר של שְׂפַת \גאוה כתוב בִּשְׂפַת \גאוה,
%וכו'. כמובן שהדבר מעורר קושי: כי אם המהדר עבור שפה מסוימת כתוב באותה שפה, הרי
%כיצד הודר המהדר? התשובה הפשוטה היא שהמהדר הידר את עצמו, וכך הם בדרך כלל פני
%הדברים. אלא, שהדבר מוביל לרקורסיה אינסופית.
%
%חז"ל-הבחינו בבעיה דומה של רקורסיה אינסופית מעין זו בסוגיא התלמודית הידועה בשם
%"צבת בצבת עשוייה". בגמרא, במסכת פסחים דף נ"ד עמוד א' נאמר:
%
%\יניב{צבתא בצבתא מתעבדא וצבתא קמייתא מאן עבד הא לאי בריה בידי שמים}
%
%ובתרגום לעברית: "הצבת אינה נעשית אלא בצבת אחרת. וראשונה מי עשאה? על כרחך מאליה
%נעשית בידי שמים.". כלומר, צבת שהיא מכשיר לאחיזת מטילי ברזל לשם ליבונם באש
%ועיבודם, עשוייה אף היא ברזל, ואף היא מיוצרת בצבת אחרת שקדמה לה. כיצד אם כן
%נוצרה הצבת הראשונה? הפתרון המוצע על ידי הגמרא הוא שהצבת הראשונה נבראה בערב שבת
%הראשון, בזמן "בין השמשות", שעה שאלוהים סיים לברוא את כל הדברים האחרים, והתכונן
%לשבות ממלאכתו לקראת ירידת השבת.
%
%פתרון ניסי שכזה אינו בא בחשבון עבור שפות תכנות. מסכת פסחים מציגה גם דרך אחרת
%שבה יוצרה הצבת הראשונה (על ידי דפוס נחושת). לעומת זאת, בשפות תכנות, ניתן לבצע
%תהליך של \E|bootstrapping| שבאמצעותו ניתן לפתח מהדר המסוגל להדר את עצמו.
%התהליך דומה מאוד למה שהיה עושה נַפָּח עני שברשותו ברזל, אך לא כסף לרכישת צבת. נפח
%כזה היה משתמש בכבשנו באופן איטרטיבי, כאשר בכל פעם הוא היה משתמש בגוש הברזל
%הדומה ביותר לצבת שיש ברשותו, כדי ליצר קירוב טוב יותר לצבת.
%
%§§ מדד לאלגנטיות של שפה
%אבן בוחן מרתקת לאלגנטיות של שְׂפַת תכנות היא אורך המהדר (או המפרש) של השפה, כאשר
%הוא כתוב בשפה עצמה. שהרי ככל שהשפה מורכבת ומתוחכמת יותר, מחד קל יותר לכתוב את
%המהדר, אך מאידך המהדר לעסוק בכל המורכבות והעושר הזה. לחילופין, שפה שהיא פשוטה
%ביחס (כמו שְׂפַת ה-\שי{batch} של \קד{DOS}) שהוזכרה מעלה, היא קלה אולי להידור, אבל
%הפשטות של השפה מהווה אבן נגף בבואנו להשתמש בה כדי לכתוב מהדר. הנה מספר אורכים
%אופייני של מהדר לשפה הכתוב בשפה עצמה:
%\begin{enumerate}
% • מהדר לשפת \סי הכתוב בשפה עצמה, דורש כמה עשרות אלפי שורות. המהדר \שי{gcc}
% מתפרס על פני כשבעה מיליון שורות קוד.
% • המהדר הראשון לשפת פסקל, אשר נכתב בִּשְׂפַת \פסקל דרש כשבעת אלפים ומאתיים שורות.
% • משערך לשפת ליספ הכתוב בליספ, הידוע גם כפונקציה האוניברסלית \קד{eval} דורש
% כמאה שורות.
% • לעומת זאת, מפרש בסיסי לשפת פרולוג הכתוב בפרולוג יכול להכתב בשורה אחת בלבד,
% ומפרש מתוחכם, המאפשר למשל מעקב אחרי החישוב, לא ידרוש בדרך כלל יותר מעשר
% שורות.
%\end{enumerate}
%
%\begin{editing}
% §§ הגדרת שפות להגדרת שפה פורמלית, באמצעות עצמן
% מהי שפה פורמלית, כל שְׂפַת תכנות היא שפה פורמלית. ישנן שפות פורמליות שאינן שפות
% תכנות. שפות תכנות אינן מכניזם נוח להגדרת שפה פורמלית. מכניזמים להגדרת שפות
% פורמליות. מתברר שגם מכניזמים אלו הם שפה פורמלית.
%
% בדרך כלל, קל הרבה יותר להגדיר שפה פורמלית, מאשר לכתוב מהדר של השפה בעזרת
% עצמה. הנה דוגמאות.
% \begin{itemize}
% ✦ הגדרת BNF בעזרת עצמו
% ✦ הגדרת EBNF בעזרת עצמו
% ✦ ביטוי רגולרי המגדיר מהו ביטוי רגולרי חוקי
% \end{itemize}
% קל להגדיר את משפחת ה-BNF באמצעות ביטוי רגולרי.
% קל להשתמש ב-BNF כדי להגדיר מהו ביטוי רגוליר.
% אבל, ניתן להגדיר ביטוי רגולרי באמצעות ביטוי רגולרי? לא! רקורסיה.
% טבלת סיכום, הגדרה הדדית.
%
% מסיבה זו, השפות BNF וְ-EBNF הן אלגנטיות יותר מביטויים רגולריים.
%
%\end{editing}
§ מיני-ליספ
הדיון כאן איננו עוסק בליספ כשפת תכנות, וגם לא באף אחד מהניבים הנפוצים או הפחות
נפוצים שלה, אלא מתרכז אך ורק בהצגת גלעין \E|(core)| מינימלי ביותר של השפה, שהוא
בעצמו ניב של ליספ. אנו נכנה ניב זה בשם \ע|מיני-ליספ|. למעט הבדלים זעירים, תכנית
מיני-ליספ היא, בדרך כלל, תכנית חוקית של \E|Common Lisp|. אבל, בדרך כלל, תכנית
של \E|Common Lisp| אינה תכנית חוקית של מיני-ליספ.
בניגוד לניבים האחרים של ליספ, שפת מיני-ליספ אינה תומכת במספרים ובפעולות
אריתמטיות, והיא מזניחה את ענין היעילות כמעט לחלוטין: לא נעשה כל מאמץ להבטיח כי
המימוש של מיני-ליספ יהיה יעיל. בנוסף, רוב הניבים של ליספ, יודעים להדר, באופן
חלקי או מלא, תכניות ליספ לשפת מכונה. גם הידור כזה אינו נחוץ במיני-ליספ.
על אף המינימליות של שפת מיני-ליספ, השפה היא מה שקרוי \E|Turing complete|. לא
נגדיר מונח זה בדיוק כאן. אבל, משמעות הטענה היא שניתן לכתוב במיני-ליספ כל תכנית
שאפשר לכתוב בשפות תכנות פחות סגפניות ממנה, כמו פסקל ו-\E|C| למשל. אנחנו
נראה בהמשך שאפשר להוסיף למיני-ליספ תמיכה במספרים טבעיים. באופן דומה ניתן
להרחיבה כך שתתמוך במספרים שליליים, רציונליים, ממשיים, מרוכבים, וגם מחרוזות,
וברבות מהתכונות של ניבים אחרים של ליספ. מטבע הדברים, הרחבות אלו לא תהיינה
יעילות במיוחד.
לא זו בלבד שהביצוע של תכניות בשפת מיני-ליספ אינו יעיל, גם תכנות בשפה רחוק
מלהיות יעיל: בהעדר, למשל, תמיכה בפעולת החיבור או בפעולות קלט פלט. לעומת זאת,
שפת מיני-ליספ יעילה מאוד ללימוד: בזכות המינימליות של השפה ניתן ללמוד אותה על
בוריה בקלות. כדי להבין את השפה כולה, כל מה שנדרש להכיר הוא את הדקדוק הפשוט
מאוד של ביטויי~\E|S|, את שמונת הפונקציות האטומיות של השפה, את שמונה הפונקציות
המוגדרות מראש, ואת אלגוריתם השיערוך. את כל אלו נעשה כאן.
אכן, שפת מיני-ליספ אינה משמשת בדרך כלל לתכנות. היא פותחה על ידי מחבר מסמך זה
לצורך הוראה והדגמת העקרונות היסודיים של שפת ליספ, פרדיגמת התכנות הפונקציונלית,
ואלגוריתם השיערוך. למרבה הצער, אין עדיין מימוש מדוייק של שפת מיני-ליספ, כלומר,
מימוש שאינו מסתמך על \E|Common Lisp|, והעדר מימוש זה אינו מפתיע במיוחד.
כאמור, ישנם שלושה מרכיבים עיקריים למיני-ליספ:
\begin{description}
✦ [פונקציות אטומיות] אילו הן פונקציות פשוטות אשר הן "אקסיומטיות", כלומר,
הגלעין מניח שהן קיימות וכי הן מצייתות למפרט מוגדר היטב. אולם, האופן שבו
ממומשות הפונקציות האטומיות אינו חלק ממיני-ליספ.
לעיתים קוראים לפונקציות האטומיות גם \ע|פונקציות פרימיטיביות|, במובן זה שהן
הבסיסיות ביותר. אנחנו נעדיף את המינוח "האטומי", המדגיש את העובדה שהן בלתי
ניתנות ל-"חלוקה", ואם נעיין בקרבי המימוש שלהן, לא נמצא שם פונקציות אחרות של
מיני-ליספ, אלא מבנים אחרים, ככל הנראה מימוש בשפת~\CPL.
✦ [פונקציות מוגדרות מראש] בנוסף לפונקציות האטומיות, מציעה מיני-ליספ לנוחות
המשתמש בשפה מספר פונקציות נוספות, אשר אותן מממש הגלעין באמצעות קריאה
לאחת או יותר מהפונקציות האטומיות.
בבדיקה השוואתית של שפות תכנות, נבחין בין פונקציות מוגדרות מראש ובין
\ע|פונקציות ספרייה|. ספרייה של פונקציות היא אוסף של פונקציות המאורגנות יחד
והממוממשות באמצעות האטומים של השפה. המשמשות למטרה קרובה או דומה. המשתמש
בשפה רשאי, אך אינו חייב להשתמש בספרייה, ולכן פונקציות הספרייה הן אופציונליות
בעבורו. לעומתן, קבוצת הפונקציות המוגדרות מראש בשפה היא חלק מהגדרת שפת התכנות,
והמשתמש אינו יכול לבחור אם להשתמש בה אם לאו.
בשפת התכנות~\CPL אין פונקציות מוגדרות מראש. גם פונקציה בסיסית כגון printf
המשמשת להוצאת פלט ממוממשת כחלק מספרייה. ישנן סיפריות רבות לשפת~\CPL, אך
הספרייה אשר מכילה את הפונקציה printf היא יחודית בכך שהיא קרויה \ע|הספרייה
הסטנדרטית| (בה' הידיעה), או \E|libc|. מקובל לכלול את \E|libc| כחלק
מתכניות~\CPL. אולם, ניתן לכתוב תכניות~\CPL גם מבלי להשתמש בספרייה זו, וישנן
תכניות שימושיות שאינן משתמשות כלל בסיפריות של השפה.
המקבילה בפסקל לפונקציה printf בשפת~\CPL, היא הפרוצדורה הידועה בשם
\E|WriteLn|. פרוצדורה זו מוגדרת מראש בשפה. לא ניתן לכתוב תכנית פסקל אשר אינה
כוללת את \E|WriteLn|, אם כי המתכנת אינו חייב להשתמש בפרוצדורה זו, והוא אף
יכול להשתמש בשם \E|WriteLn| לצרכיו, ובכך להסתיר את הפרוצדורה המקורית.
✦[אלגוריתם השיערוך] שפת מיני-ליספ, כמו בניבים אחרים של ליספ, מכילה פונקציה
מיוחדת, \E|eval| שמה, אשר מקבלת ביטוי~\E|S| ומשערכת אותו. מסיבות טכניות
(עליהן נעמוד בקצרה בהמשך) הפונקציה eval נחשבת אף היא פונקציה אטומית, אולם, את
רובה ככולה ניתן לממש כפונקצית ספרייה.
\end{description}
§§ הפונקציות האטומיות
כל הפונקציות האטומיות של מיני-ליספ הן גם פונקציות אטומיות של מרבית הניבים
החשובים של ליספ, ובפרט של \E|Common Lisp|, אם כי יתכנו הבדלים קלים במשמעות של
הפונקציות האטומיות בין מיני-ליספ ובין הניבים השונים.
בניבים אחרים של ליספ, יש בדרך כלל מספר רב של פונקציות אטומיות נוספות. לעומת
זאת, יש במיני-ליספ שמונה פונקציות אטומיות בלבד (למעט \E|eval|):
\ציינן
✦ \ע|שלוש פונקציות מבניות|: \E|car|, \E|cdr| ו-\E|cons|, אשר מאפשרות ליצור ביטוי
\E|S|, ולפרק אותו לחלקיו.
✦ \ע|שתי פונקציות לוגיות|: \E|atom|, \E|eq| ו-\E|cond|, המאפשרות לבדוק את תוכנו של
ביטוי~\E|S|.
✦ \ע|שתי פונקציות נוספות|: הפונקציה \E|set| המאפשרת לתת שמות לביטויי~\E|S|,
והפונקציה \E|error| המסייעת בטיפול במקרים שבהם החישוב נתקל בשגיאה.
===
הערכים בהם מטפלת שפת ליספ הם ביטויי~\E|S|, ונדרשות במיני-ליספ שמונה פונקציות
אטומיות כדי לבצע את כל המניפולציות הנחוצות של ערכים אלו, וביניהן פעולה המקבילה
להצבה ופעולה המקבילה להדפסת שגיאה. בהשוואה לאלו, התמיכה של שפת פסקל בטיפוס של
מספרים שלמים משתמשת ב-14 פריטים שונים: 5 אופרטורים אריתמטיים בינאריים, 2
אופרטורים אריתמטיים אונאריים, 6 אופרטורים של השוואה, וכן סימן מיוחד, \E|:=|,
אשר אינו נחשב לאופרטור בשפת פסקל, לציון פעולת ההצבה. (שפת פסקל אינה מציעה תמיכה
יחודית לתמיכה בשגיאות).
\פנה|טבלה:אטומיות| שבהמשך מתארת את הפונקציות האטומיות במדוייק. מיני-ליספ מעלה
על נס את המינימליות, ואכן למרות שהטבלה מביאה מפרט מלא של הפונקציות הללו ואת כל
מה שנדרש כדי להשתמש בהן, היא אינה משתרעת על פני יותר ממחצית העמוד. (יש עדיין
צורך בכמה הגדרות וסימונים כדי לקרוא את הטבלה ולהבין את משמעות 8 הפונקציות בה,
אולם ניכר כי תיאורן קצר.)
אנו נתאר ראשית את הפונקציות המבניות, ואחר כך את הפונקציות הלוגיות \E|atom|,
ו-\E|eq| יחד עם הפונקציה המוגדרת מראש \E|null|. המשך הדיון יוביל לתיאורה של
הפונקציה \E|set|, ואחריה \E|cond|. הצורך בפונקציה \E|error| יגיע כאשר נממש את
אלגוריתם השיערוך במיני-ליספ.
§§ פונקציות מוגדרות מראש
מיני-ליספ מכילה שמונה פונקציות מוגדרות מראש, כלומר פונקציות הכתובות
בשפת מיני-ליספ תוך שימוש בפונקציות האטומיות, ואשר נטענות תמיד יחד עם
מיני-ליספ.
\ציינן
✦ \ע|קבועים| (פונקציות ללא פרמטרים):
\begin{itemize}
✦ \E|t| (המציין את הערך הבוליאני של אמת).
✦ \E|nil| (המציין את הערך הבוליאני של שקר).
\end{itemize}
✦ \ע|פונקציה לוגית|: \E|null| (פונקציה חד-מקומיות הבודקת אם ביטוי הוא \E|nil|).
✦ \ע| פונקציות המסייעות בהגדרת פונקציות|:
\E|quote|, \E|defun|, \E|ndefun|, \E|lambda| ו-\E|nlambda|.
\begin{itemize}
✦ הפונקציה defun משמשת להגדרת פונקציות חדשות.
✦ הפונקציה quote משמשת למניעת השיערוך של ביטויי~\E|S|.
✦ בפונקציות \E|ndefun|, \E|lambda| ו-\E|nlambda|, נדון בהמשך.
\end{itemize}
===
מלבד ndefun ו-nlambda ניתן למצוא, לעיתים בשינויים קלים, את הפונקציות המוגדרות
מראש של מיני-ליספ גם ב-\E|Common lisp| ובניבים אחרים של השפה.
\פנה|טבלה:מראש| שבהמשך מתארת את הפונקציות המוגדרות מראש, והיא כוללת, בנוסף
לתיאור הפונקציות הללו, גם את המימוש המלא שלהן במיני-ליספ, ובכל זאת, טבלה זו
קצרה אף יותר מ\פנה|טבלה:אטומיות| המתארת את הפונקציות האטומיות.
בהמשך נראה כי מימושן של הפונקציות המוגדרות מראש נעשה באמצעות קשירה
(\E|binding|) של שמן למה שקרוי "ביטוי \E|lambda|" או "ביטוי \E|nlambda|",
באמצעות הפונקציה \E|set| (ישירות או בעקיפין). במונח binding אנו מתכוונים לקישור
בין שם לבין המשויים אותו מציין השם. נניח ש-$f$ היא פונקציה מוגדרת מראש. אזי~$f$
היא ביטוי S שהוא מהצורה המיוחדת של ביטוי \E|lambda| או מהצורה המיוחדת של
ביטוי \E|nlambda|. מתן שם למשויים~$f$ הוא הקישור בין אטום של מיני-ליספ (שהוא
השם) למשויים~$f$.
קישור של שם למשויים קיים בכל שפות התכנות: כאשר אנו מגדירים בשפת תכנות כמו פסקל
משתנה אשר שמו הוא \T|i|, אנו נותנים שם לתא בזכרון שמכיל את ערכו של המשתנה.
המשויים הוא תא בזיכרון שמכיל את ערכו של המשתנה, ו-\T|i| הוא השם שאנו קושרים לתא
זה. המונחים קישור והגדרה הם זהים: פונקציות מוגדרות מראש בשפת מיני-ליספ הן
פונקציות אשר הקישור בין שמן ובין הגוף שלהן נעשה עוד טרם ריצת התכנית. כאשר אנו
אומרים שהסימן \T|+| מציין את פעולת החיבור בשפת פסקל, אנו בעצם אומרים שיש קישור
בין הסימן ובין הפעולה. גם הסימן \T|+| וגם \T|i| הם שמות של משוימים. הסימן~\T|+|
מציין משויים שהוא פעולה, ואילו \T|i| מציין משויים שהוא משתנה. הבדל אחד, אך לא
הבדל מהותי, בין~\T|+| ובין~\T|i| הוא שלמתכנת (בשפת פסקל לפחות) אין אפשרות
להשתמש בסימן~\T|+| כדי לציין משויימים שהוא יצר.
הדיון כאן יתאר תחילה את הקבועים, כלומר הפונקציות האפס-מקומיות, \E|t| ו-\E|nil|,
ולאחר את הפונקציה החד-מקומית \E|null|. אחר כך נעבור לתאר את \E|quote|, את
\E|defun| ואת \E|lambda|. הפונקציות \E|ndefun| ושל \E|nlambda| דורשות מעט יותר
תשומת לב, והן תוצגנה אחרונות.
§§ הפונקציה eval והסביבה
בנוסף לפונקציות האטומיות ולפונקציות המוגדרות מראש, שפת מיני-ליספ תומכת, כמו
מרבית הניבים של ליספ, בפונקציה \E|eval| אשר מקבלת ביטוי~\E|S| ומשערכת אותו.
הפונקציה eval גם היא נחשבת, מסיבות טכניות, לפונקציה אטומית. אנחנו נדגים כיצד
ניתן לממש אותה באמצעות מימוש פונקציה דומה \E|evaluate| כפונקצית ספרייה.
ישנו הבדל קטן בין \E|eval|, הפונקציה הפרימיטיבית, ובין \E|evaluate|, אותה נממש
כפונקציית ספרייה. שתי הפונקציות מקבלות ביטוי-S ומשערכות אותו, אלא שהפונקציה
\E|evaluate| מקבלת פרמטר נוסף, המתאר את הקישורים שנעשו בתכנית עד כה.
לאוסף זה של ההגדרות, קוראים \ע|סביבה|. הסביבה ממומשת בשפת ליספ באמצעות
מבנה נתונים הקרוי \E|a-list|. הפונקציה eval משתמשת אף היא בסביבה, אלא שבתוך
המימוש של מיני-ליספ, אין צורך להעביר את הסביבה כפרמטר: רשימת ה-\E|a-list| נגישה
לפונקציה \E|eval| כמין משתנה גלובלי, אותו אין צורך להעביר כפרמטר מפורש, וניתן
לשנותו מכל נקודה בתכנית. העדר הצורך להעביר את ה-\E|a-list| כפרמטר ל-eval הוא זה
אשר מבחין בינה ובין \E|evaluate| אשר אין לה גישה לערכים גלובליים, ועל כן היא
נדרשת לקבל את הסביבה, המיוצגת באמצעות-\E|a-list| כפרמטר.
המימוש של האלגוריתם שמאחורי \E|eval| (כלומר המימוש של הפונקציה \E|evaluate|)
נעשה כולו במיני-ליספ, תוך שימוש בפונקציות אטומיות או פונקציות מוגדרות מראש, אשר
כאמור גם הן ממומשות באמצעות הפונקציות האטומיות. מימוש זה הוא פשוט וקצר יחסית
ועולה לכדי כמאה שורות בלבד.
לבד מהמימוש של eval שפת מיני-ליספ מעניינת שכן היא מציגה בתמציתיות את מרבית
הרעיונות החשובים של ליספ, כגון עיבוד רקורסיבי של רשימות, קישור של שמות לערכים,
העברת פרמטרים, הסתכלות על תכנית כמבנה נתונים, ועוד.
§§ עצי שיערוך
לא רק תכניות הם ביטויי~\E|S|. כל הערכים בשפת ליספ הם ביטויי~\E|S|
\E|(S-Expressions)|. המונח~S-Expression בא לעולם כקיצור למונח \E|symbolic
expression| (ביטוי סימבולי). המילה "סימבולי" מדגישה את העובדה כי אין מדובר
בהכרח בביטוי מתמטי כגון~$13+41/2$, שבו המשמעות של כל הסימנים ידועה ומוכרת לכל,
אלא בביטוי \E|כללי| שיכול להכיל סמלים שמשמעותם דורשת הגדרה מפורשת, כגון
\begin{equation}
(\amalg⊚✠) ⊘ (\Re≀⅁)
\end{equation}
פרשנות הביטוי הזה תלוייה במשמעות הסמלים המופיעים בו: האם הם אופרטורים בינאריים
(דו-מקומיים), אונאריים (חד מקומיים), או שמא הם אופרנדים, כלומר נולאריים
(אפס-מקומיים), הקריים גם אופרנדים.
אם האופרנדים בביטוי הם~$\amalg$,~$✠$,~$\Re$ ו-$⅁$, והאופרטורים
(הבינאריים) הם~$⊚$,~$⊘$ ו-$≀$, אזי עץ השיערוך הוא:
\begin{quote}
\center
\begin{forest}
s tree [$⊘$,[$⊚$ [$\amalg$] [$✠$]] [$≀$[$\Re$][$⅁$]]]
\end{forest}
\end{quote}
אולם, יתכן גם כי האופרנדים הם הסימנים~$⅁$ ו-$✠$, כלומר אלו הם אופרטורים
נולאריים, ואילו~$\amalg$,~$⊚$,~$✠$ ו-$\Re$ הם אופרטורים אונאריים (ממבנה
הסוגריים בביטוי עולה כי~$⊘$ הינו אופרטור בינארי). במקרה זה, עץ השיערוך הוא
\begin{quote}
\center
\begin{forest}
s tree [$⊘$,[$\amalg$ [$⊚$ [$\amalg$]]]
[$\Re$ [$≀$ [$⅁$]]]]
\end{forest}
\end{quote}
בין כך, ובין כך, כיוון שלא רק המקומיות של הסמלים המופיעים בביטוי אינה ידועה,
אלא גם משמעותם אינה ידועה, לא נוכל לשערך את הביטוי.
נשים לב לכך שכל ביטוי בשפת פסקל (למשל) ניתן להצגה כעץ שיערוך, וכי כל עץ שיערוך
ניתן להצגה כרשימה של רשימות. אולם, לא כל רשימה של רשימות ניתנת להצגה כעץ
שיערוך. בפרט, אם הפריט הראשון ברשימה הוא בעצמו רשימה, כמו למשל כאן,
\begin{LISP}
((car '(f g)) x)
\end{LISP}
אזי לא ניתן להציג את הרשימה כולה כעץ שיערוך. הסיבה לכך היא שהטופולוגיה של עצי
השיערוך בה עשינו שימוש מניחה שבכל צומת פנימי של העץ, ישנה תגית, המציינת את
הפונקציה שיש להפעיל בצומת זה.
§§ האינטרפרטר של ליספ
אנו רואים כי המונח שיערוך כולל בתוכו שני מרכיבים עיקריים: ראשית, איתור המשמעות
של הסמלים המופיעים בביטוי, ושנית, חישוב הביטוי בהתאם למשמעות זו.
בדרך כלל מרכיב החישוב של השיערוך מחשב ביטוי חדש, אך לעיתים השיערוך מייצר משמעות
בעבור סמלים שלא הייתה להם משמעות טרם השיערוך: השיערוך אינו לקוח בלבד
בלבד של הגדרות הסמלים, הוא גם עשוי לייצר הגדרות חדשות כאלו.
בשפות תכנות כדוגמת~\CPL ופסקל, העוברות \ע|הידור| \E|(compilation)| שני מרכיבי
השיערוך נפרדים. מתן המשמעות לסמלים ואיתור המשמעות של סמלים נעשה על ידי
ה\ע|מהדר| \E|(compiler)|. החישוב עצמו נעשה בזמן ריצת התכנית. בליספ, כמו בשפות
אחרות שבהן עיבוד התכנית בשפה נעשה באמצעות אינטרפרטציה \E|(interpretation)| של
תכניות, שני השלבים של השיערוך נעשים על ידי האינטרפרטר \E|(interpreter)| אשר
קורא תכניות ומשערך אותן בזו אחר זו. האינטרפרטציה כוללת לכן לא רק את תהליך החישוב,
אלא גם את התהליכים הנלווים של מתן משמעות לסמלים, ואיתור משמעות זו.
\begin{minipage}\linewidth
\footnotesize
\begin{mdframed}[backgroundcolor=Lavender!20]
האינטרפרטר של ליספ, כמו האינטרפרטר של פרולוג, \E|bash| ושפות תכנות אחרות
העוברות אינטרפרטציה, עובד במחזורים, בשיטה הידועה בשם
\LR{\textbf Read \textbf Evaluate \textbf Print \textbf Loop}
או בראשי תיבות \E|REPL|:
\ספרר
✦ \E|READ|: האינטרפרטר קורא את סדרת תווים מהקלט, ומנסה להציג את סדרה זו
כמבנה בשפת התכנות. במקרה של ליספ, האינטרפרטר קורא סדרת תווים, ומנסה להציג
אות כביטוי~\E|S|. אם לא ניתן לעשות כן, האינטרפרטר מדפיס הודעת שגיאה וחוזר
לתחילת הלולאה של \E|REPL|, כלומר חוזר לקרוא קלט חדש.
✦ \E|EVALUATE|: האינטרפרטר משערך את ערכו של הביטוי שקרא.
✦ \E|PRINT|: אם השיערוך של הקלט מצליח, אז האינטרפרטר ידפיס את תוצאת
השיערוך. אחרת, האינטרפרטר ידפיס הודעת שגיאה מתאימה.
✦\E|LOOP|: האינטרפרטר חוזר לצעד הראשון, לקריאת הקלט הבא.
===
\end{mdframed}
\end{minipage}
האינטרפרטר של ליספ מכיל לכן שלושה מרכיבים עיקריים:
\begin{enumerate}
✦ ה-Reader אשר קורא קלט שהוא סדרה של תווים, ובונה את מבנה הנתונים המתאים
לביטוי ה-S המתאים לתווים אלו.
✦ המשערך \E|(Evaluator)| אשר משערך ביטויי~\E|S| אלו.
✦ ה-Printer אשר מקבל ביטוי~\E|S| כמבנה נתונים ומתרגם אותו לסדרת תווים אשר
מייצגת מבנה נתונים זה.
\end{enumerate}
כאן נניח שה-Reader וה-Printer נתונים והם דומים לאלו שבכל ניב של ליספ, ונתאר את
המימוש של המשערך של מיני-ליספ.
§ ביטויי~\E|S|
§§ ביטויי~\E|S| כשפה פורמלית
\newcommand\SX{\ensuremath{S_{\text{exp}}}}
בעבור מי שאין לו די בתיאור האינטואיבי של ביטויי \E|S|, תת פרק זה מוסיף הגדרות
מדוייקות מעט יותר: בהינתן אלפאבית, סופי או אינסופי,~$Γ$, נגדיר את~$\SX(Γ)$,
\textbf{קבוצת ביטויי ה-\E|S|, מעל האלפאבית~$Γ$}. אינטואיטיבית, ביטוי~\E|S| יכול
להיות אטומי, כלומר ביטוי S שאינו ניתן לפירוק לביטויי S אחרים, ואז הוא חייב
להיות סימן מתוך~$Γ$. ביטוי~\E|S| שאינו אטומי נקרא ביטוי מורכב, ואז הוא בהכרח
זוג סדור של שני ביטויי~\E|S| אחרים, שיכולים להיות אטומיים או מורכבים. הזוג
הסדור נכתב עטוף בזוג סוגריים כאשר שני ביטויי ה-S שבו מופרדים בסימן הנקודה.
כמה ביטויי~\E|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(Γ)$ באמצעות שני כללי היסק:
\begin{definition}[ביטויי~\E|S| מעל
אלפאבית] בהנתן אלפאבית~$Γ$ אזי,~$\SX(Γ)$, קבוצת ביטויי ה-S מעל האלפאבי~$Γ$
מוגדרת באמצעות שני בנאים
\begin{enumerate}
✦ הבנאי הנולארי, המגדיר את הביטויים ה\ע|אטומיים|, כלומר, ביטויי~\E|S| אשר
אינם ניתנים לפירוק לביטויי~\E|S| אחרים. בנאי זה מוגדר באמצעות כלל היסק שיש
לו הנחה אחת בלבד,~$γ∈Γ$.
\begin{equation*}
\infer{γ∈\SX(Γ)}{γ∈Γ}.
\end{equation*}
לפי בנאי זה, כל מילה ב-$Γ$ היא ביטוי~\E|S| אטומי. הבנאי נקרא נולארי, משום
שעל פי בנאי זה ניתן "ליצור" איברים של הקבוצה~$\SX(Γ)$ ללא "שימוש" באיברים
אחרים של הקבוצה.
✦ הבנאי הבינארי, המתאר את המבנה של ביטויי~\E|S| \ע|מורכבים|:
\begin{equation*}
\infer{(s₁.s₂)∈\SX(Γ)}{s₁∈\SX(Γ) & s₂∈\SX(Γ)}.
\end{equation*}
לפי בנאי זה, אם~$s₁$ ו-$s₂$ הם ביטויי~\E|S| (שיכולים להיות אטומיים או
מורכבים) אזי~$(s₁.s₂)$ הוא ביטוי~\E|S| (מורכב). בנאי זה נקרא בנאי
בינארי, משום שבכלל ההיסק המתאר אותו
יש שתי הנחות, וכל אחת מתייחסת לאיברים של~$\SX(Γ)$. במילים אחרות, על פי בנאי
זה ניתן "ליצור" איבר חדש של הקבוצה~$\SX(Γ)$ מתוך "שימוש" ב-\ע|שני| איברים
קיימים של הקבוצה.
\end{enumerate}
\end{definition}
כאמור, נוח לייצג ביטויי~\E|S| כעצים בינאריים מלאים (כלומר, כאלו בהם לכל צומת
שאינו עלה יש בדיוק שני בנים) כאשר צומת פנימי של עץ כזה אינו נושא מידע, ואילו
עלה מכיל סימן מתוך~$Γ$. \פנה|איור:בינארי| מציג תיאור כעץ בינארי מלא של כמה
ביטויי~\E|S| מעל האלפאבית (האינסופי) \[
Γ=❴a,b,c,d❵^*,
\] כלומר, קבוצת ביטויי~\E|S| שהאטומים שלהם הם מילים
הנבנות מהאלפאבית (הסופי)~$❴a,b,c,d$.
\newcommand{\TopAlign}[1]{\adjustbox{valign=t}{#1}}
\newcolumntype{T}{>{\collectcell{\TopAlign}}c<{\endcollectcell}}
\begin{figure}[htbp]
\כיתוב|ביטויי~S והייצוג שלהם כעץ בינארי מלא|
\תגית|איור:בינארי|
\centering
\begin{LTR}
\rowcolors{2}{blue!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}
ניתן להגדיר את~$\SX(Γ)$ גם באמצעות דקדוק חסר הקשר. כלומר, הקבוצה~$\SX(Γ)$ היא
שפה פורמלית מעל אלפאבית מורחב,~$Γ'$, המתקבל מהוספת סימן הנקודה ושני סימני
הסוגריים לאלפאבית המקורי~$Γ$. אנו מניחים, בלי הגבלת הכלליות, ששלושת הסימנים
הללו אינם מצויים ב-$Γ$.
\begin{equation}
\begin{split}
S &→(S.S)⏎ S &→A ⏎
A &→ε⏎ A &→Aγ₁ ⏎
A &→Aγ₂ ⏎
⋮ ⏎
A &→Aγₙ ⏎
\end{split}
\end{equation} כאשר~$Γ=❴γ₁,γ₂,…,γₙ❵$.
אבל, הגדרה זו באמצעות דקדוק סופי לא תוכל לפעול כאשר האלפאבית~$Γ$ הינו אינסופי.
כזה המצב למשל בשפת מיני-ליספ, שבה האלפאבית~$Γ$ שמעליו נבנים ביטויי ה-S הוא
אינסופי, ומוגדר כאוסף כל ה\ע|מילים| מעל~$Σ_{\text{Mini-Lisp}}$, האלפאבית המכיל
את כל ה\ע|תווים| שיכולים להופיע במה שקרוי בשפת ליספ \ע|אטום|:
\begin{equation}
Γ_{\text{Mini-Lisp}}=Σ_{\text{Mini-Lisp}}^*,
\end{equation}
כאשר
\begin{equation}\label{alpahet:C}
Σ_{\text{Mini-Lisp}}=
Σ_{\text{upper}}∪
Σ_{\text{digit}}∪
Σ_{\text{other}}.
\end{equation}
בפרט~$Σ_{\text{Mini-Lisp}}$ מכיל 67 תווים:
\begin{enumerate}
✦ \ע|26 אותיות אנגליות גדולות| \[
Σ_{\text{upper}}=❴⌘A,⌘B,⌘C,⌘D,⌘E,⌘F,⌘G,
⌘H,⌘I,⌘J,⌘K,⌘L,⌘M,⌘N,⌘O,⌘P,⌘Q,⌘R,⌘S,⌘T,⌘U,⌘V,⌘W,⌘X,⌘Y,⌘Z❵.
\] \relax
✦ \ע|10 ספרות| \[
Σ_{\text{digit}}=❴⌘0,⌘1,⌘2,⌘3,⌘4,⌘5,⌘6,⌘7,⌘8,⌘9❵.
\] \relax
✦ \ע|11 סימנים מיוחדים| \[
Σ_{\text{other}}=❴⌘|, ⌘＆, ⌘?, ⌘!, ⌘:, ⌘+, ⌘*, ⌘/, ⌘-, ⌘<, ⌘>, ❵.
\] \relax
\end{enumerate}
הייצוג הרגיל של ביטוי~\E|S| במחשב הוא באמצעות עצים בינאריים: כך נעשה במימושים
הראשונים של ליספ. בייצוג זה, כל צומת פנימי של העץ הוא רשומה המכילה שני מצביעים,
שכל אחד מהם יכול להצביע או לרשומה אחרת מסוג צומת, או לאטום, כלומר לעלה של העץ.
§§ ביטויי~\E|S| בשפת ליספ וכתיב הרשימות
הניבים השונים של ליספ משתמשים בהגדרה דומה של ביטויי-\E|S|, ומוסיפות על ההגדרה
מונחים, כינויים, הרחבות וקיצורים שונים. במיני-ליספ נשתמש בשתי תוספות בלבד:
\אבגד
✦ כתיב הרשימות
✦ סימן ה-\E|quote| \E|(')|
===
תוספות אלו תוצגנה בהמשך.
מסיבות היסטוריות, לביטוי~\E|S| מורכב קוראים בשפת ליספ \E|dotted-pair|. לאיבר
הראשון ב-dotted-pair קוראים \E|car|, ולאיבר השני ב-dotted-pair קוראים \E|cdr|.
לזוג כולו קוראים לעיתים גם \ע|רשומת cons|.
לביטוי~\E|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)| היא רשימה המכילה שני פריטים, שהראשון בהם הוא
ביטויי~\E|S| מורכב, \E|(a.c)|, והשני הוא האטום \E|c|. הרשימה הריקה, זו שאינה
מכילה אף פריט, נכתבת כ-\E|()|. כל הרשימות, למעט הרשימה הריקה הן ביטוי~\E|S|
מורכב. הרשימה הריקה היא גם אטום, בפרט, האטום \E|nil| הוא גם שמה של הרשימה הריקה.
כל רשימה היא כתיב מקוצר לביטוי~\E|S|. הכתיב מוגדר באינדוקציה על אורך הרשימה:
הרשימה הריקה \E|()| שהיא גם כתיב אחר לאטום \E|nil|. רשימה שאינה ריקה, היא כתיב
מקוצר לביטוי~\E|S| מורכב, כלומר זוג של ביטויי~\E|S|. האיבר הראשון בזוג הוא
האיבר הראשון ברשימה. האיבר השני בזוג, הוא הייצוג של שארית הרשימה.
לפיכך, הרשימה \E|(a b c d)| היא כתיב אחר לביטוי~\E|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
[B,atom]
[{},cons[C,atom] [$ε$,atom] ]
]
[{},cons
[C,atom]
[$ε$,atom]
]
]
}
\end{tabular}
\end{LTR}
\end{figure}
המשמעות של המונח \ע|כתיב| היא שמרכיב ה-Reader של האינטרפרטר של ליספ יכול לקרוא
ביטויי~\E|S| הנתונים בכתיב הרשימות ושמרכיב ה-Printer של האינטרפרטר יתרגם
ביטוי~\E|S| לכתיב הרשימות כשהדבר אפשרי (לא כל ביטוי~\E|S| ניתן להיכתב בכתיב
הרשימות; למשל הביטוי \E|(a.b)| אינו ניתן להכתב כרשימה, אבל כל רשימה ניתנת
להיכתב כביטוי~\E|S|). בהעדר סיבה מיוחדת, מתכנתי ליספ נוהגים לכתוב ביטויי~\E|S|
בכתיב הרשימות בכל אימת שניתן לעשות זאת.
§§ שלוש פעולות היסוד על ביטויי~\E|S|, ושלושת ההיבטים שלהן
§§§ פונקציות מתמטיות מעל קבוצת ביטויי~\E|S|.
על ה\ע|חוג החילופי| \E|(abelian ring)|~$ℤ$ של המספרים השלמים \E|(the ring~$ℤ$
of integers)| מוגדרות שלוש פעולות: שתי הפעולות הבינאריות של הכפל והחילוק,
והפעולה האונארית של מציאת ההופכי החיבורי. באופן דומה, נגדיר שלוש פעולות על כל
קבוצה~$𝓢$ של ביטויי~\E|S|:
\begin{enumerate}
✦ הפעולה הבינארית~$p$ המצרפת ב-\E|dotted-pair| שני ביטויים של~$𝓢$,
\begin{equation}
p(s₁,s₂)=⌘(s₁⌘.s₂⌘),
\end{equation}
✦ ושתי הפעולות האונאריות ההופכיות לה:
\begin{enumerate}
✦ הפעולה~$p₁^{-1}$ המחזירה את המרכיב
הראשון של ביטוי מורכב ב-$𝓢$
\begin{equation}\label{eq:p1}
p₁^{-1}(s)=\begin{cases}
s₁ & ∃ s₂, s₁ ∙ s₂=⌘(s₁⌘.s₂⌘) ⏎
⊥ & \textit{otherwise},
\end{cases}
\end{equation}
✦ והפעולה~$p₂^{-1}$ המחזירה את המרכיב השני של ביטוי כזה,
\begin{equation}\label{eq:p2}
p₂^{-1}(s)=\begin{cases}
s₂ & ∃ s₁, s₁ ∙ s₂=⌘(s₁⌘.s₂⌘) ⏎
⊥ & \textit{otherwise}.
\end{cases}
\end{equation}
\end{enumerate}
\end{enumerate}
הסימןש~$⊥$ (אותו יש לבטא \E|bottom|) המופיע ב-\פנה|eq:p1| וב-\פנה|eq:p2|
מציין שערך הפונקציות~$p₁^{-1}$ ו-$p₂^{-1}$ אינו מוגדר כאשר הארגומנט שלהן הוא
איבר אטומי של~$𝓢$. נסכם ונאמר
\begin{equation}
\begin{split}
p&:𝓢×𝓢→𝓢⏎
p₁^{-1}&:𝓢 ⇸𝓢⏎
p₂^{-1}&:𝓢 ⇸𝓢.
\end{split}
\end{equation}
כלומר,~$p$ היא פונקציה שהתחום הוא זוג של ביטויי~\E|S| והטווח שלה הוא ביטוי כזה.
הפונקציה היא פונקציה \ע|מלאה|, במובן זה \ע|שלכל ערך| בתחום, ממופה ערך בטווח.
לעומת זאת הפונקציות~$p₁^{-1}$ ו-$p₂^{-1}$ אשר התחום והטווח שלהן הוא~$𝓢$, הן
פונקציות חלקיות. שכן \ע|לא לכל ערך| של התחום מתאימות~$p₁^{-1}$ ו-$p₂^{-1}$ ערך
של הטווח. בפרט,~$p₁^{-1}$ ו-$p₂^{-1}$ אינן מוגדרות בעבור האטומים של~$𝓢$.
שפות מעטות בלבד, ובהן \E|Wofram Language| ו-\E|Newspeak| תומכות באופן ישיר
בייצוג של \ע|כל| מספר הלקוח מ-$ℤ$. עצם הייצוג של מספרים שאינן חסומים בגודל
הוא קל לתכנות, למשל באמצעות רשימה (שאינה חסומה בגודלה) של הספרות בייצוג עשרוני.
כמובן, במגבלות יצוג זה מוגבל על ידי הזיכרון הפיזי: גם עבור מחשב שבו הזיכרון
הכולל הוא~$2^{100}$ בתים, קל לתאר מספר ב-$ℤ$ שהוא גדול מכדי שיהיה ניתן לייצגו
במחשב זה.
ובכל זאת, מרבית שפות התכנות אינן תומכות במספרים שלמים במובן של החוג
החיבורי~$ℤ$. חוג זה מכיל אינסוף איברים, ולכן לא ניתן לייצג את כל המספרים
הלקוחים ממנו באף מבנה בעל גודל סופי. מתוך תשומת לב ליעילות התכניות הנכתבות בהן,
שפות תכנות נוטות לייצג מספרים שלמים באמצעות מילת מחשב \E|(word)| בת 32 או 64
ביטים, ולכן הן תומכות רק בקבוצה סופית של מספרים שלמים הלקוחים מ-$ℤ$.
כך לדוגמה, הטיפוס \E|\kk{long}| בשפת \Java הוא קירוב של הקבוצה~$ℤ$: בטיפוס זה מוצגים
מספרים שלמים, שליליים וחיוביים \E|(unsigned int)| בשיטת "המשלים לשתיים" באמצעות מילה בת
64 ביטים.
הערכים האפשריים של הטיפוס \E|\kk{long}| הם מספרים מהתחום
בטיפוס הזה הוא \begin{equation}
-2^{63},…,2^{63}-1=-9,223,372,036,854,775,808,…,9,223,372,036,854,775,807
\end{equation}
על אף היות התחום גדול מאוד, הוא עדיין סופי, ולכן הוא כאיין לעומת
הקבוצה האינסופית~$ℤ$.
יש בטיפוס \E|\kk{long}| לא מעט זוגות של ערכים חיוביים, שהסכום שלהם הוא שלילי.
הסיבה לכך היא שהחישובים ב-\Java בטיפוס \E|\kk{long}| הם חישובים
בקבוצה~$ℤ_{2^{64}}$, הלא היא חוג השאריות מודולו~$2^{64}$. ב-$ℤ_{2^{64}}$. בחוג
זה האבחנה בין מספרים "חיוביים" ו"שליליים" אינה מוגדרת, ויחס ה"סדר"
ב-$ℤ_{2^{64}}$ (ככל שיש כזה) אינו מקיים תכונה חשובה של יחס הסדר של השלמים:
שהעוקב של כל מספר גדול ממנו, או בניסוח אחר, שאין מעגלים ביחס העוקב.
אנו מקבלים לכן שלא זו בלבד שהטיפוס \E|\kk{long}| הוא קירוב של~$ℤ$, גם "\cc+",
הסימן לציון החיבור, וגם "\cc*", הסימן לציון הכפל \Java (כאשר הם
מופעלים על ערכים מטיפוס \E|\kk{long}|), אינם מציינים את פעולות החיבור והכפל
ב-$ℤ$, כי אם קירוב סופי שלהן. בדומה לכך, סימן המינוס, "\cc-", מציין את פעולת
ההופכי החיבורי בקבוצה~$ℤ_{2^{64}}$, אך פעולה זו היא קירוב בלבד של פעולת ההופכי
החיבורי שב-$ℤ$. מספר הערכים השונים של הטיפוס \kk{long} הוא זוגי, וכיוון
שהערך אפס נמנה עם ערכים אלו, קיים ערך בטיפוס ששונה מאפס שהוא הההופכי החיבורי של
עצמו,
תכונה שאינה מתקיימת ב-$ℤ$, בפרט מתקיים בטיפוס זה \begin{equation*}
-❨-2^{63}❩=-2^{63}.
\end{equation*}
בניגוד למרבית שפות התכנות, ו-\E|Common Lisp| בתוכן, מיני-ליספ אינה תומכת
במספרים כלל. כיוון שכך, אין לה צורך להשתמש בטיפוסים כגון \E|\kk{long}|. מנגד,
כיוון שמיני-ליספ תומכת בביטויי~\E|S| בלבד, יש לה צורך לתמוך בשלוש פעולות היסוד
על ביטויי~\E|S|, הלא הן~$p$,~$p₁^{-1}$, ו-$p₂^{-1}$.
האופרטורים של חיבור וכפל במרבית שפות תכנות מהווים קירוב בלבד של הפעולות על
השלמים. בניגוד לזאת, הפעולות בשפת ליספ הן מימוש מלא של הפונקציות
המתמטיות~$p$,~$p₁^{-1}$, ו-$p₂^{-1}$. כפי שנראה בתרגילים, ניתן להשתמש בשפת
ליספ כדי להגדיר יצוג מלא ולא מקורב של~$ℕ$ (המספרים הטבעיים),~$ℤ$ (השלמים),~$ℚ$
(הרציונליים),~$ℝ$ (הממשיים), ו-$ℂ$ (המרוכבים).
\פנה|טבלה:השוואה| משווה בין ביטויי~\E|S| ובין החוג~$ℤ$, חוג המספרים הטבעיים,
מבחינת התמיכה בהם בשפות תכנות שונות.
\begin{table}[!htbp]
\rowcolors{2}{blue!10}{white}
\begin{tabularx}\textwidth{r>{\small}X>{\small}X}
\toprule
\bf &
\bf \normalsize חוג המספרים השלמים~$ℤ$ &
\bf \normalsize~$𝓢$, קבוצת ביטויי~\E|S|⏎
\midrule
פעולות יסודיות &
כפל, חיבור, ומציאת ההופכי החיבורי &
$p$,~$p₁^{-1}$, ו-$p₂^{-1}$. ⏎
תמיכה בשפות תכנות &
פסקל,~\CPL, \Java, \E|Common Lisp|, וכו' &
כל הניבים של ליספ ⏎
טיב התמיכה &
בדרך כלל קירוב סופי באמצעות~$ℤ_{2ⁿ}$, עבור \[
n=3,4,5,6.
\] תמיכה מלאה בשפות
תכנות פחות נפוצות, כגון \textsc{Mathematica} ו-\textsc{Newspeak}.
&
תמיכה מלאה במיני-ליספ כמו גם הניבים של ליספ ⏎
סימון פעולות היסוד &
בפסקל,~\CPL, \Java, ועוד:~\cc{+}, \texttt{*} (אופרטורים
בינאריים), ו-\texttt{-}, אופרטור אונארי. &
\E|cons|, \E|car|, \E|cdr| ⏎
תמיכה בפעולות נוספות &
\textbf{בפסקל:} אופרטורים בינאריים "\texttt{*}", "\texttt{/}" \texttt{*},
\kk{mod}, \kk{div} ואופרטורים אונאריים \texttt{-}, \kk{succ}, ו-\kk{pred},
ומספר פונקציות מוגדרות מראש.\hfill\newline
\textbf{בשפות כגון~\CPL, ו-\E|\textsc{Go}|:} אופרטורים רבים
נוספים, עליהן נוספת ספרייה עשירה &
\textbf{במיני-ליספ:} קומץ פונקציות מוגדרות מראש. \hfill\newline
\textbf{בניבים אחרים של ליספ:} פונקציות אלמנטריות נוספות כגון, כגון
\E|caar|, \E|cdar|, \E|cadr|, פונקציות מוגדרות מראש נוספות, וספרייה עשירה
יותר ⏎
פעולות השוואה
&
$n₁<n₂$,~$n₁=n₂$, וצירופים שלהם &
בדיקה אם שני אטומים הם זהים ⏎
\bottomrule
\end{tabularx}
\כיתוב|תמיכת שפות תכנות בקבוצת ביטויי ה-S לעומת תמיכתן בחוג~$ℤ$|
\תגית|טבלה:השוואה|
\end{table}
§§§ סימון פעולות היסוד באמצעות פונקציות של ליספ
ההיבט הראשון של שלוש פעולות היסוד על ביטויי~\E|S| הוא הייצוג שלהן כפונקציות
מתמטיות מעל~$𝓢$, ממש כשם שהפעולות האריתמטיות הן פונקציות מתמטיות המוגדרות על
החוג~$ℤ$. ההיבט השני של פעולות היסוד הוא ה\ע|סימון| של פעולות היסוד בשפת ליספ,
מה שקוראים גם הציון שלהן על ידי אטומים, ממש כשם שסימן הפלוס (\T|"+"|) משמש לציון
של פעולת החיבור בשפות תכנות אחרות.
המשמעות של שלושת האטומים \T|cons|, \T|car|, ו-\T|cdr| מוגדרת מראש במיני-ליספ
לציון פעולות אלו:
\begin{enumerate}
✦ האטום \T|cons| מציין את הפונקציה~$p$, שהיא פונקציה אטומית המקבלת שני
ביטויי~\E|S|, ומחזירה ביטוי~\E|S| שהוא זוג בו האיבר הראשון הוא הארגומנט
הראשון לפונקציה, ואילו האיבר השני של הזוג הוא הארגומנט השני לפונקציה.
✦ האטום \T|car| מציין את הפונקציה~$p₁^{-1}$, שממומשת כפונקציה אטומית של
ליספ. פונקציה זו מקבלת כארגומנט ביטוי~\E|S| אחד. אם ביטוי זה הוא ביטוי מורכב,
כלומר ביטוי שהוא \E|dotted-pair| הפונקציה מחזירה ביטוי~\E|S| שהוא האיבר
הראשון בזוג ממנו הארגומנט בנוי.
לעומת זאת, אם הארגומנט לפונקציה הוא אטום, הפונקציה נכשלת. כשלון זה דומה
לכשלון של ניסיון לחלוקה באפס. ממש כשם שלא כל הפעולות האריתמטיות מוגדרות על כל
המספרים, לא כל הפונקציות המבניות מוגדרות על כל ביטויי~ה-\E|S|.
✦ באופן דומה, האטום \T|cdr| מציין את הפונקציה~$p₂^{-1}$ שממומשת גם היא
כפונקציה אטומית. פונקציה זו המקבלת כארגומנט ביטוי~\E|S| אחד, ואם ביטוי זה
הוא ביטוי מורכב, הפונקציה מחזירה ביטוי~\E|S| שהוא האיבר השני בזוג ממנו
הארגומנט בנוי. ממש כמו car הפונקציה cdr נכשלת אם היא מופעלת על אטום בודד
או על הרשימה הריקה.
\end{enumerate}
נדגיש שוב את ההבדל בין שלושת האטומים ובין שלושת הפעולות אותן הם מציינים, ונזכיר
שהבדל זה אינו יחודי לשפת מיני-ליספ. בשפת~\CPL, יש הבדל בין הסימן \T|+| ובין
הקירוב לפעולת החיבור, אותו מציין סימן זה. בהמשך, נשתמש לא מעט באבחנה בין שם
הפונקציה, ובין גוף הפונקציה שאותו מציין השם.
§§§ פעולות היסוד על ביטויי~\E|S| כפעולות על רשימות
ההיבט השלישי של פעולות היסוד על ביטוי~\E|S| נוגע להסתכלות על ביטויי~\E|S|
כרשימות.
\begin{enumerate}
✦ אם נעביר לפונקציה \T|cons| ערך כלשהו~$x$, כלומר ביטוי~\E|S| שיכול להיות
אטומי או מורכב,~$x$ וביטוי~\E|S| אחר שהוא רשימה~$ℓ$, אזי הפונקציה תוסיף את~$x$
בתחילת הרשימה~$ℓ$: הפעלת cons על האטום a ועל הרשימה \E|((b~c)~d)| תחזיר את
הרשימה \E|(a~(b~c)~d)|.
✦ אם הארגומנט לפונקציה \T|car| הוא רשימה~$ℓ$ שאיננה ריקה, אז הפונקציה מחזירה
את הפריט הראשון ברשימה: הפעלת car על הרשימה בת שני איברים \E|((b~c)~d)| תחזיר
את הפריט הראשון ברשימה זו, \E|(b c)|, שהוא בעצמו רשימה בת שני איברים.
כאמור, אם הארגומנט ל-\E|car| הוא אטום, ואפילו יהא זה האטום \lisp{nil},
כלומר הרשימה הריקה, הפונקציה נכשלת.
✦ באופן דומה, אם הארגומנט לפונקציה \T|cdr| הוא רשימה~$ℓ$ שאיננה ריקה, אז
הפונקציה מחזירה את הרשימה המתקבלת מ-$ℓ$ אחרי שהסרנו ממנה את הפריט הראשון שבה:
הפעלת cdr על הרשימה \E|((b~c)~d)| תחזיר \E|(d)|, רשימה בת איבר אחד. הפונקציה
\E|cdr| גם היא נכשלת אם היא מופעלת על רשימה ריקה, כלומר על האטום \E|nil|, או על
כל אטום אחר.
\end{enumerate}
תכנות ברשימות אופייני לשפות רבות אחרות מלבד ליספ. לפונקציה הדומה ל-cons קוראים
לעיתים \E|prepend|. כיוון ששלושת הפעולות הללו משתמשות ברשימה כמחסנית,
אנו מוצאים מקרים בהם קוראים ל-\E|cons| גם בשם \E|push|. באופן
דומה, לפונקציה car קוראים בשפות תכנות אחרות בשמות כגון \E|first|, \E|head| (או
בקיצור \E|hd| ו-\E|top|), ולפונקציה cdr קוראים בשפות תכנות אחרות בשמות כגון
\E|rest|, \E|body| ו-\E|pop|.
§§ בדיקת התוכן של ביטויי~\E|S|
הקבוצה~$ℤ$ היא קבוצה סדורה היטב. ניתן לבדוק לגבי כל שני מספרים שלמים~$n₁,n₂∈ℤ$
מתקיים אחד מבין ההיגדים הבאים:~$n₁=n₂$,~$n₁<n₂$ או~$n₁>n₂$. אין יחס סדר דומה
לקבוצת ביטויי ה-S, אבל ניתן לבדוק את תוכנם באמצעות פונקציות מתאימות בליספ.
ליספ בדרך כלל תומכת בפונקציות לוגיות רבות המאפשרות לבדוק את תוכנו של
ביטויי~\E|S|. שפת מיני-ליספ מסתפקת בשלוש פונקציות כאלו בלבד: המשמעות של שלושת
האטומים \T|atom|, \T|null|, ו-\T|eq| מוגדרת מראש במיני-ליספ לציין פונקציות