-
Notifications
You must be signed in to change notification settings - Fork 0
/
thesis.tex
3855 lines (3223 loc) · 183 KB
/
thesis.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,10pt,twoside]{report}
%\documentclass[b5paper,8pt,twoside]{article}
%\documentclass[a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
%\usepackage{fontspec}
\usepackage{fixltx2e}
\usepackage{graphicx}
\usepackage{longtable}
\usepackage{float}
\usepackage{wrapfig}
\usepackage{rotating}
\usepackage[normalem]{ulem}
\usepackage{amsmath}
\usepackage{textcomp}
\usepackage{marvosym}
\usepackage{wasysym}
\usepackage{amssymb}
\usepackage[hidelinks]{hyperref}
\usepackage{cite}
\tolerance=1000
%\usepackage{minted}
\usepackage{todonotes}
\usepackage{comment}
\usepackage{listings}
\usepackage{lipsum}
\usepackage{tikz}
\usepackage{syntax}
\setcounter{secnumdepth}{4}
\usetikzlibrary{trees}
%\tikzstyle op=[draw, circle]
%\tikzstyle arg=[]
\tikzstyle op=[inner sep=0,draw,circle,minimum size=0.8cm,execute at begin node=$,execute at end node=$]
\tikzstyle arg=[minimum size=.6cm,inner sep=0,draw,circle,fill=gray!50!white]
\author{Nathanael Schweers}
\date{\today}
\title{Proof of Concept: An implementation of a reader for extensible syntaxes for Emacs Lisp}
% \hypersetup{
% pdfkeywords={},
% pdfsubject={},
% pdfcreator={Emacs 25.0.91.1 (Org mode 8.2.10)}}
\newcommand{\el}{Emacs Lisp}
\newcommand{\cl}{Common Lisp}
\newcommand{\elr}{el-reader}
\newcommand{\sym}[1]{\texttt{#1}}
\newcommand{\fun}[1]{\texttt{#1}}
\newcommand{\emacs}{GNU~Emacs}
\newcommand{\emacsv}[1]{GNU~Emacs~#1}
\newcommand{\unix}{\textsc{unix}}
\newcommand{\windows}{MS Windows\texttrademark}
\newcommand{\Read}{\fun{read}}
\newcommand{\nil}{\sym{nil}}
\newcommand{\tee}{\sym{t}}
% \newenvironment{myEnv} [2]
% {\begin{frame} \frametitle{#1} \framesubtitle{#2} \begin{center}}
% {\end{center} \end{frame}}
% \newenvironment{sourcecode} [2]
% {\begin{listing}[h] \label{#1} \caption{#2} \begin{verbatim}}
% {\end{verbatim} \end{listing}}
%\newminted{cl}{}
\lstset{ %
language=Lisp, %
frame=single, %
%float, %
captionpos=b}
\lstdefinestyle{lispcode}{
language=Lisp,
basicstyle=\scriptsize,
frame=single,
%float,
captionpos=b,
%stringstyle=\color{red},
%keywordstyle=\bfseries\color{purple}
showstringspaces=false
}
\lstdefinestyle{lispinline}{
language=Lisp,
showstringspaces=false}
\lstdefinestyle{pythoncode}{
language=python,
basicstyle=\small,
showstringspaces=false
}
\lstdefinestyle{rubycode}{
language=ruby,
basicstyle=\small,
float,
captionpos=b,
showstringspaces=false
}
\lstdefinestyle{rubyinline}{
language=ruby,
basicstyle=\small,
showstringspaces=false
}
\begin{document}
\maketitle
\begin{abstract}
This thesis discusses the design and implementation of a proof of concept for
an \el{} compatible reader for extensible syntaxes, in \el{}, named
``\elr{}''. In Lisp parlance, the reader is the part of the
interpreter/compiler, which converts the characters in the source code to data
structures, which are then further processed. In an extensible reader, new
syntactic constructs may be defined from within the language. These new
constructs take effect when specific characters are encountered in the source
code, and may interact with the existing reader to create arbitrary data
structures which are later either interpreted or compiled by the Lisp
environment.
Some other languages feature such capabilities, of which \cl{} is most widely
known. Some Scheme implementations also provide these or similar
possibilities, yet this is not part of the standard. SRFI-10 provides a
specific character sequence with which all read macros must
start. \cite{srfi-10}
In \cl{} the possibility to interact with the reader is called a read macro or
reader macro, and these terms will also be used throughout this thesis.
\el{} does not provide reader macros. As of the upcoming version 25.1 the
reader is implemented in C and does not provide any hooks into it, apart from
the usual advice system which all \el{} functions provide.
The code underlying this thesis provides a means to replace the reader built
into Emacs. The main point of this thesis is to show that the flexible nature
of a Lisp environment may be used to replace even such a crucial part of the
system as the reader at runtime without affecting unrelated parts or making
the original part unavailable.
While a short recap of Lisps basics---especially where relevant to reading
code---is given, a working knowledge of Lisp and modern language constructs
like closures is assumed. Pointers to additional Lisp resources are provided
in the text.
\end{abstract}
\tableofcontents
\chapter{Introduction}
\label{chapter:introduction}
In this thesis a proof of concept for a new reader for \emacs{} is discussed.
The reader (called \elr{}) provides \cl{}-style reader macros, which allow the
user of the language to extend the syntax of the language without leaving the
language or even restarting the program.
The advantage of such a system is that new syntactic constructs may be
implemented without the restriction of merely re-using existing ones, as would
be the case using operator overloading. Also, several completely
different---even incompatible---syntaxes may coexist within one program, as long
as their uses do not overlap. To a certain extent these syntaxes can be
composable, yet in such a case caution is advised.
The outline of this thesis is as follows:
Chapter~\ref{chapter:introduction} provides a short history of how \emacs{} came
into being and how the language extended here (\el{}) is part of \emacs{}.
Other Emacs variants (also known as \emph{emacsen}) are not discussed here.
Also a short history of Lisp is given, as well as a few basics of the language
and what makes it special. Also some motivation is given as to why the reader
should be replaced.
% Chapter ~\ref{chapter:lisp-hist} gives a brief history of the conception and
% further development of Lisp and its dialects.
% Chapter ~\ref{chapter:lisp-special} shows how Lisps in general differ from other
% programming languages. This chapter is especially important for people
% unfamiliar with Lisps in general, yet will hopefully also be of interest to the
% more casual lisper.
% Chapter ~\ref{chapter:lisp-basics} gives a short introduction to programming in
% Lisp, as Lisp knowledge will make the rest of this thesis much easier to
% understand.
% Armed with the knowledge of previous chapters, chapter ~\ref{chapter:motivation}
% finally gives some motivation of why one would want to allow users to extend the
% syntax of a language. As with all features, taste is advised in doing so.
% Chapter ~\ref{chapter:repl-reader} discusses how the reader may be replaced and
% what the pros and cons of each approach are.
Chapter~\ref{chapter:reader-printer} discusses what a reader actually is and how
it differs from the more traditional parsers found in other programming
languages. This chapter also discusses the inner workings of the algorithm used
to implement \elr{}.
Chapter~\ref{chapter:api-overview} gives an overview on how to use the
reader presented in this thesis, including some explanations often lacking in
tutorials found both on the web and in books.
Finally chapter~\ref{chapter:future-work} outlines some possible work in the
future to improve the situation.
\section{Lexical conventions}
\label{sec:lexical-conv}
Throughout this thesis, the names of functions, classes, variables and plain
symbols are written in a \texttt{monospace} font. Code is mostly placed in
boxes and listings, but the occasional short expression may be put between
``double quotes''. Single characters embedded into the text are surrounded by
single quotes. Note that only the quote signs as used in source code of
virtually all programming languages (i.e. the characters ‚'’ and ‚"’) are to be
taken as part of such an expression or character.
When functions are presented, their signature is shown too.
Figure~\ref{sig:example} shows an example.
\begin{lstlisting}[style=lispcode,label={sig:example},caption={Example function
signature},numbers=left]
(el-reader/read (&optional INPUT-STREAM
(EOF-ERROR-P T)
EOF-VALUE
RECURSIVE-P
KEYS))
\end{lstlisting}
The parentheses denote a list. The first element is the name of the function in
question. All other elements are either arguments or qualifiers for further
arguments. One such qualifier is ``\&optional''. It means that all further
arguments are optional. The following arguments may either be an argument name
or a list. If a name is given, the value will be \nil{} if the caller does not
supply an argument. In case of a list, the first element of said list must be a
name, while the second may be an arbitrary expression which will be evaluated as
the function is called. The result of said expression will be bound to the
argument.\footnote{Note that this is a consequence of using the \texttt{CL}
package distributed with \emacs{}, which provides some \cl{} emulation. The
list may also provide another value which may be used by the called function
to determine whether an argument was supplied or not, yet this is not used in
this thesis. The appropriate info page discusses these features in more
depth.} Another argument is ``\&rest''. This must always be followed by
exactly one argument name. It means that all further arguments given---which
may be zero or more---are collected into a list and bound to this argument.
As \el{} does not provide any namespace support worthy of the name, it is sadly
necessary to prefix all names one uses to avoid clashes. As the package
developed for this thesis has been named ``el-reader'', this is also used as a
prefix. Many \el{} packages simply delimit prefixes with a dash for public
variables or functions and a double dash for private ones, yet in this package a
single and double forward slash are used for this purpose as it is more easily
distinguished from the other dashes used to separate names.
Special (a.k.a. dynamic, a.k.a. global) variables are---by
convention---surrounded by asterisks, yet only the part of the name which does
not include a prefix. For example the readtable is placed in
\sym{el-reader/*readtable*}, not \sym{*el-reader/readtable*}.
Hence, every symbol which begins with \sym{el-reader/} and is not followed by a
second immediate slash, denotes a public variable or function.
To make the names used in this thesis shorter, the full name is used once, and
from then on the part after the slash(es) is used.
\section{A brief history of (GNU) Emacs}
\label{sec:emacs-intro}
Emacs was at first a text editor at MIT, written in machine language and
extensible with an interpreted command language. The interpreter was taken from
TECO, another text editor used at MIT at the time. According to Richard
Stallman \cite{emacs-hist} there was an implementation on a Lisp Machine and
later on Multics. Both of these were written in Lisp, hence were extensible in
Lisp. When Stallman started the GNU project, he needed an implementation for
\unix{}. As Lisp programs on regular machines could not perform runtime type
checks at the same speed as Lisp Machines could one had to choose performance or
safety, but could not have both. Stallman decided to write a Lisp interpreter
and editor primitives like display handling in C while writing as many higher
level functions as possible in Lisp.\footnote{Why Stallman felt that using C
instead of an optimizing Lisp compiler is beyond me. Both suffer from the
lack of type checking, while using Lisp would have been far more productive
than programming in C. Possibly the lack of decent free Lisp compilers played
a part in this decision.} The dialect he designed and implemented is called
\el{}, or elisp for short\footnote{Note though, that there once was an unrelated
dialect of the name elisp.}. In 1984 Stallman wrote what is now known as
\emacs{}\cite[See ``History'']{emacs-first-release}. Since then, \el{} has grown
and changed a lot.
While \emacs{} is primarily a text editor, it achieves its extensibilty by
being/providing a virtual Lisp Machine. So far only some experimental features
exist to incorporate shared objects into a running instance of \emacs{}, so the
only ways to add features is to modify the C code base, which requires
recompilation, or by loading \el{} code. All C functions which users may need
are exported to Lisp and are largely indistinguishable from Lisp functions,
macros or special forms. This extensibility has made \emacs{} one of the most
powerful editors available. For the rest of this thesis, the editing
capabilities of \emacs{} are rather unimportant. The thesis will concentrate
more on the Lisp Machine part of \emacs{}.
The capabilities of \el{} have drastically improved over the last years. Until
\emacsv{24.1} \el{} only featured dynamic scope\cite[See “* Lisp changes in
Emacs 24.1”]{Emacs-Lexical}.\footnote{See \cite{CLTL2}
(\url{http://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node43.html})for an
explanation of why ``dynamic scope'' is a misnomer, yet still useful as a
term. While the differences in scope and extent are interesting, they are not
relevant to this thesis.} In what will probably be called \emacsv{25.1},
support for watered down \cl{} style multimethods will be included. As these
methods were used for the code in this thesis, said code requires at least a
pretest version of \emacs{}\cite{emacs-pretest}.
\section{A brief history of Lisp}
\label{sec:lisp-hist}
Pinpointing Lisps exact moment of birth is rather difficult, as it is often the
case with ideas which take some time to develop. John McCarthy published a
paper in 1960 on the language\cite{rec-fun-sym-expr} in which some ideas,
notation among others, from Alonzo Church’s $\lambda$-calculus are used.
The gist of the paper is that McCarthy devised a theoretic system to represent
functions in programs. This was originally meant as a theoretic foundation,
yet, as McCarthy writes in his retrospective notes on Lisp history
\cite{lisp-hist}: “S.R. Russell\footnote{One of his students at the time.}
noticed that eval could serve as an interpreter for LISP, promptly hand coded
it, and we now had a programming language with an interpreter.”
While it may have been an accident that Lisp got an implementation, thus
becoming an actual programming language at the time that it did, the foundation
was laid down at that time, so it could have happened at any later point.
As Lisp introduced several ideas which were new to programming, resulting in
high expressive power, it quickly became popular in some circles, especially the
artificial intelligence community, of which McCarthy was a part. This was
probably simply because Lisp was more powerful than any other language of the
time, even though it was very slow. It was slow compared to other languages of
the time, namely machine language/assembly and FORTRAN. It was also slow simply
because compiler technology was not nearly as advanced as it is today.
What makes Lisp so expressive is discussed in greater detail in
section~\ref{sec:lisp-special}.
Lisp was originally supposed to adopt a different syntax, especially for
function calls and definitions. McCarthy even used this syntax, called
M-expressions, in his original paper \cite{rec-fun-sym-expr}. They were to be
translated into S-expressions (short for Symbolic expressions). While in the
original paper the syntactic representation of S-expressions and lists was
slightly different\footnote{McCarthy originally allowed spaces in atoms,
i.e. symbol names, and separated list elements with a comma. Today spaces are
used to delimit elements.}, they essentially had their current form, namely
consisting of symbols and lists, using a prefix scheme, i.e. having the operator
as the first element of a list.
McCarthy himself used the term S-expression for symbols while today most Lisp
programmers use the term S-expression, or sexp for short, to mean any string of
characters which may be \emph{read} by a Lisp implementation. The latter
meaning will be used in this thesis from now on.
This proposed translation was not merely a syntactic, let alone cosmetic change.
Compilers and interpreters in general need some form of source representation
which is above the character level of the source code which they take as input.
This is typically called an abstract syntax tree (AST)\footnote{The exact
differences and relationships between ASTs, concrete syntax trees and the like
are beyond the scope of this thesis.}. Lisp, being a dynamically typed
language, allows the syntax tree to be particularly simple. While a tree in a
statically typed language may need structures to differentiate between a
function call (which has a name and zero or more arguments), and a number
literal, in Lisp one can simply use dynamic typing. This way, numbers, strings,
symbols etc. can be put directly in place, while nested lists provide the tree
structure needed.
As Lisp programs can be represented with data structures which Lisp provides,
higher-order programs became possible quite early in the history of computers.
Lisps syntax and its relationship to metaprogramming is discussed in further
detail in section~\ref{sec:lisp-special}.
As Lisp is rather a set of ideas on how a language should be, rather than a
single language, different Lisp dialects were developed. Among the most well
known are \cl{} and Scheme. Another rather recent addition to the Lisp family
of languages is Clojure, which is rather important, as it is very different from
other Lisps, especially \cl{}. Another Lisp dialect which is somewhat
widespread is \el{}, which is rather similar to \cl{} is some respects. This
language is used---as the name suggests---as an extension language for \emacs{}
and some other Emacs variants.
\section{What makes Lisp special}
\label{sec:lisp-special}
As outlined at the end of section~\ref{sec:lisp-hist}, Lisp code can be
represented in its own data structures. This sets it apart from most (if not
all) mainstream languages in use today. As this is vital to the rest of this
thesis, it is discussed in detail here.
As an example, we will transform a simple algebraic expression. The simple
expression \(a + b \cdot c\) can be put into a tree form
(figure~\ref{fig:simple-tree}). Note that in tree form parentheses are no
longer needed to group terms. Also, all precedence becomes explicit.
\begin{figure}[h]
\centering
\begin{tikzpicture} %[every node/.style = {shape=circle, draw}]
\node [op] {+} child { node [arg] {a} } child { node [op] {\times}
child { node [arg] {b} } child { node [arg] {c} } };
\end{tikzpicture}
\caption{Tree form of an algebraic expression}
\label{fig:simple-tree}
\end{figure}
Alternatively, given lists of arbitrary length (represented by surrounding
parenthesis), symbols and dynamic typing, the same tree may also be represented
like this:
% Given a list notation as used in Lisp, i.e. parentheses and spaces which delimit
% elements, together with prefix notation, it may as well look like this:
\begin{lstlisting}[style=lispinline]
(+ a (* b c))
\end{lstlisting}
Given that Lisp syntax is given as nested lists, symbols and prefix notation, it
becomes apparent that Lisp only has (linear) syntax for ASTs. This means that
programmers do not enter syntactic forms, but directly enter the AST for their
programs.
This may put off some programmers as unaesthetic\footnote{Many non-lispers claim
that Lisps syntax---or lack thereof---is difficult to read, yet I and many
other Lisp programmers disagree. Once a programmer has become accustomed to
this kind of source code, it can become quite appealing, and the parenthesis
are not as intrusive to the mind as many initially suspect.}. While it is
difficult to meaningfully argue over such subjective topics, there are technical
advantages to this approach, which come in at least four categories, each of
which are discussed in more detail in the following sections: macros, sexp
communication, editing tools, customizable syntax.
\subsection{Macros}
\label{subsec:macros}
As programs can be represented by data structures which are accessible to the
user of the language, an implementation may provide hooks which allow the user
to add transformation routines. Such a routine may take a source tree, which
has been read, but not evaluated, and return such a source tree, which is
evaluated instead of the invocation of the transformer itself. In lisp, such
transformers are called macros. A macro is a procedure, written in Lisp, which
operates on Lisp source code. The result of calling a macro procedure is called
the expansion of said macro. Listing~\ref{code:increment} is taken from the
``GNU Emacs Lisp Reference Manual''.\footnote{Note that this definition has some
(fixable) problems, which make it unsuitable for production work.}
\pagebreak
\begin{lstlisting}[style=lispcode,caption={Increment as a
macro.},label={code:increment}]
(defmacro inc (var)
(list 'setq var (list '1+ var)))
\end{lstlisting}
This macro can be invoked via \texttt{(inc x)} where \sym{x} is an already
existing variable. Inside the macro procedure \sym{val} is \emph{not} bound to
the value which \sym{x} will hold at runtime, but with the \emph{symbol}
\sym{x}. This makes it possible to perform macro expansion at runtime. The
procedure returns a list which is evaluated at runtime. As the first element of
this list is the symbol \sym{setq}, it sets a variable to a value. The code
which produces the expansion as well the expansion itself may be arbitrarily
complex. There is a lot more to write about how to use macros in practice. The
``GNU Emacs Lisp Reference Manual'' has a section devoted to macros in \el, and
Paul Grahams book ``On Lisp'' \cite{on-lisp} features an excellent chapter on
macros in \cl{}.
A more sophisticated macro can be found in the source code to this thesis (see
listing~\ref{code:make-accessors}, which generates getters and setters for a
class). The arguments to the macro are a symbol which denotes the class for
which accessors shall be created, and an optional second symbol which denotes a
prefix for all accessors.
Note that the mechanism to create classes is not part of the core of \el{} but
is implemented on top of \el{}. This is done with a package named
EIEIO\footnote{EIEIO stands for “Enhanced Implementation of Emacs Interpreted
Objects” and is shipped with \emacs{}}.\cite{eieio}
\begin{lstlisting}[style=lispcode,caption={Create accessors for all data members
of a given class.},label={code:make-accessors}]
(defmacro el-reader//make-public-accessors (class &optional prefix)
(cons 'progn
(seq-map
(lambda (e)
`(progn
(defun ,(intern (s-concat (if prefix (symbol-name prefix)
"")
(symbol-name e)))
(obj)
,(s-concat "Extract the element " (symbol-name e)
" from OBJ. ")
(slot-value obj ',e))
(cl-defmethod (setf ,(intern (s-concat
(if prefix
(symbol-name prefix)
"")
(symbol-name e))))
(new-elt (obj el-reader/readtable))
(setf (slot-value obj ',e) new-elt))))
(seq-map #'eieio-slot-descriptor-name
(eieio-class-slots class)))))
\end{lstlisting}
For every data member \sym{memb}, prefix \sym{prefix/} in the class \sym{klass},
the code in listing~\ref{code:data-member} has to be generated.
\begin{lstlisting}[style=lispcode,caption={Getter and Setter for a member called
\sym{memb}.},label={code:data-member}]
(defun prefix/memb (obj)
"Extract the element invalid-chars from OBJ. "
(slot-value obj (quote invalid-chars)))
(cl-defmethod (setf prefix/memb)
(new-elt (obj klass))
(setf (slot-value obj (quote memb)) new-elt))
\end{lstlisting}
This code inspects the slots (i.e. member variables) of the class given in the
first argument with the function \fun{eieio-class-slots} which returns a list of
slot descriptors. The function \fun{eieio-slot-descriptor-name} in turn returns
the name of the given slot, which is done for each slot (with \fun{seq-map}).
For each slot name a getter (\fun{defun}) and setter (\fun{cl-defmethod}) is
created. Note that the macro itself does not create these functions. The macro
returns code which---when run---creates said functions. The alternative to this
macro would have been to write getters and setters for every data member in a
class manually.\footnote{For this program, the macro was used only once. The
expansion is almost 80 lines long, if properly formatted.} This is not only a
menial task not worthy of a self respecting programmer, but also error prone and
highly unmaintainable. If for instance the desired prefix changes, every getter
and every setter has to be inspected and changed.
\subsection{Communication via sexps}
\label{subsec:sexp-communication}
When a given program needs to save or read data from a file, a stream or some
other medium, some form of structure is needed. The simplest case is a binary
format, yet these schemes often suffer from lack of extensibility and
debugability. If a text based scheme is called for, some sort of syntax is
needed. In the \unix{} culture plaintext files with assignments using the
\texttt{=} is and was often used. Programs on \windows{} often used INI files.
Both cultures seem to tend towards XML. They do so with good reason: there are
parsers for XML which are readily available, and XML offers a tree structure.
XML and sexps are quite similar. Both describe a tree shaped structure without
specifying which labels are permitted. XML seems to focus on cases where there
is a lot of text and little markup (hence making it quite suitable for the web),
while sexps are well suited for cases with lots of markup and little text. One
could say that sexps focus more on symbols, while XML focuses on strings.
While it is possible to describe both a document and a program with XML or with
sexps, it quickly becomes ugly to describe a document with sexps because text
must be escaped. Likewise, describing programs in XML is very verbose and ugly.
Both XML and sexps serve the purpose of providing a linear syntax for data
objects. A syntax which may not only be read by a program, but also which may
be written, as data objects may be printed in XML or sexps notation.
The obvious benefit of using sexps to share data between processes for a Lisp
programmer is rather obvious: the syntax is the same as the language itself and
both readers and printers are available by definition. At least in \cl{} both
are customizable, which allows for new syntax for new data types. Often new
syntax is not needed, as printing can produce an expression which can be
transformed at runtime. A hash table might be printed like this:
\pagebreak
\begin{lstlisting}[style=lispinline]
(hash-table size 65 test eql rehash-size 1.5
rehash-threshold 0.8
data (:foo "FOO!" :bar "BAR!"))
\end{lstlisting}
In such an example the mere reading of an expression will not yield a hash
table. Yet interpreting such a structure gives enough details on how to
construct the table in memory, similar as would be done using XML.
\subsection{Editing Tools}
\label{subsec:edit-tools}
While editing any kind of language one may encounter intermediate states which
are invalid. While typing ``<a href=http://example.com>link</a>'' in an XML
document, the person typing this will break the structure of the file in several
ways: ``<'' alone is not valid in XML. ``<a'' too, is invalid. The same
problem exists for sexps: ``(a ((href . "http://example.com")) "link")'' is an
sexps which has roughly the same structure as the previous XML example. Here,
unbalanced parentheses cause the text to become invalid syntax, i.e. no tree can
be constructed from it.
For \emacs{} there are at least two tools which address this problem:
paredit\cite{paredit} and lispy\cite{lispy}. Both tools provide alternative
editing commands which ensure a valid tree: if an open paren is inserted, a
closing paren is also inserted. A list may be expanded to include the next
element, or eject the last element from the list (thus always keeping the tree
intact). These tools also offer commands which raise a whole expression (of
arbitrary size) up one level in a tree, deleting one level. An example may be
used to illustrate:
\begin{lstlisting}[style=lispinline]
(if (some-predicate arg1 arg2 and some more really
complex code!)
simple-value)
\end{lstlisting}
Given this code, a programmer might discover that the whole if expression is not
needed, and that \sym{simple-value} should always be used. Given very few
commands, both paredit and lispy can \emph{raise} the token \sym{simple-value}
to produce a new tree:
\begin{lstlisting}[style=lispinline]
simple-value
\end{lstlisting}
Note that this is done (somewhat) atomically: at no point is there an opening or
closing paren which distorts the syntax tree.
While such tools may not be impossible for other languages, sexps (and XML
probably too, yet the I am not aware of such tools for XML) make this much
easier than in other languages.\footnote{To show how ``simple'' this can be, one
can simply take a look at the length of the source code of such tools: the
lispy version I use at the time of writing consists of 12 files for several
languages, and less than 10,000 lines of \el{} code (including comments etc).
While this is still quite a lot, it probably would be a lot more for languages
with more ``traditional'' syntax, let alone for languages with undecidable
grammars like C++.}
\pagebreak
\subsection{Customizable Syntax}
\label{subsec:custom-syntax}
As Lisp syntax is merely syntax for an AST, i.e. data, this syntax can be
customized to include new data types, or to redefine existing syntactic
constructs. It is important to note that this is not true of Lisps in general,
only that it is possible for a Lisp to exhibit this kind of behavior. \cl{}
features a customizable reader \el{} does not, which is why this thesis
addresses the issue for \emacs{}.
Not many users of \cl{} seem to use this set of features, as free and good
introductory material on the topic is quite lacking on the web, although
Graham’s On Lisp does feature a short chapter on read macros.\cite[Chapter
17---``Read Macros'']{on-lisp}
\section{Lisp Basics}
\label{section:lisp-basics}
This chapter is both a short recap of some Lisp basics, and on the stages code
goes through, which is more explicit in Lisp than in other languages. At
first, the symbol and list type will be introduced, which play a very important
role in Lisp, and without neither reader nor compiler would make much sense.
Later on the stages through which code may flow will be discussed. This
includes the range from reading to evaluation.
Unless stated otherwise the examples given refer to \el{}, not to every Lisp in
general.
\subsection{Datatypes}
\label{subsec:datatypes}
\subsubsection{Symbols}
\label{subsubsec:symbols}
The symbol is a type which represents a name, often together with places for
values and/or functions. The latter depend on the Lisp dialect. An important
property of symbols is that fast lookup is supported, and that symbols are
interned. This means that each symbol which is read, which has the same name,
returns the same Lisp object.\footnote{This is, in effect, a singleton.}
In \el{}, which is the Lisp under consideration for this thesis, a symbol has
the following attributes:
\begin{description}
\item[{Name}] A name for the symbol. This may be retrieved as a string at any
time by calling \fun{symbol-name}. Also, a string may be used to retrieve the
symbol instance with the function \fun{intern}.
\item[{Value}] This is the value of the symbol. It may be retrieved by a call
to \fun{symbol-value} or by simply appearing in a program (macros or special
forms may treat symbols differently).
\item[{Function}] This cell is looked up if the symbol is the first element of a
list which is evaluated (more on this later). Alternatively, a call to
\fun{symbol-function} returns the function to which it points (if any).
\item[{Property List}] A symbol may also have a Property List, or plist for
short, which is a mapping from a key (mostly a symbol) to a value. This is
intended as a mechanism to store arbitrary metadata in a symbol.
\end{description}
In \el{} a fifth attribute exists, which is not visible from Lisp code. Symbols
are placed into so called ``obarrays'', which are similar to hashtables, but are
specialized to symbols (i.e. no other objects can be stored in them). To
support fast lookup and low memory usage, each symbol contains a pointer to the
next symbol in the same bucket of the obarray. For this reason a symbol may
only be interned in one obarray.\cite[Section 8.3 ``Creating and Interning
Symbols'']{elisp-reference} Because of this limitation it is not possible (at
the time) to implement \cl{} compatible packages for \emacs{} (not to be
confused with the packages provided in \fun{package.el}, which are installable
units).
\subsubsection{List}
\label{subsubsec:list}
In Lisp parlance, when a list is mentioned, it is almost always a singly linked
list. While by far not the only compound data structure\footnote{Strictly
speaking, lists by themselves do not exist: there are only cons-cells, yet
this nuance is not very important for the current discussion.}, it is a very
important one.
For the moment, the most important aspect of lists is that they may be
heterogeneous, i.e. contain objects of different types, and that they may have
varying length.
\subsection{Stages}
\label{subsec:stages}
When a Lisp expression is to be evaluated, it goes through up to three stages,
all of which are discussed here at least briefly, including some implications.
Note that all of these steps can be invoked---independently of each other---by a
running Lisp program. It is also possible for each stage to invoke the others.
Depending on the Lisp environment a user chooses to
employ, these steps (apart from evaluation) may be invoked in sequence to
produce an executable. This is not exactly the case for \emacs{}; here, the
last step in a batch compile is bytecode.
\subsubsection{Reading}
\label{subsubsec:reading}
The first stage is reading. Before this stage, the source code is present in
the form of a linear string of characters, for instance from a file. The result
of this is a Lisp object. This object may be very simple, but it may be a huge
object composed of many sub-objects. The object returned mirrors the structure
of the source. Variable and function names are symbols, parenthesis denote
lists, number literals are converted into numeric objects etc.
This stage already exists in stock \emacs{}, yet \elr{} replaces this stage in
order to enable this stage to a) recognize additional (user supplied) patterns
and b) to reach out into the other stages. In a way the reader included in
stock \emacs{} will call functions which are also exposed to \el{}, such as
\fun{intern}, yet this is not in any way user controllable. In stock \emacs{},
the reader is the only stage which can never reach out to other stages.
With \elr{} it is possible to run and/or compile code at readtime. This may be
used to provide nonstandard semantics for an embedded domain specific language
(EDSL), or may be used to pull calculations from runtime to readtime in order to
improve performance.
Besides providing syntax for data types (like symbols and lists), readers may
also provide shorthand notation for common scenarios. The first shorthand
everyone who learns to program in lisp encounters is quote (\sym{'}). This
reads another expression and wraps it in a list where the first element is the
symbol \sym{quote}. Hence ``'foo'' becomes \texttt{(quote foo)}. This special
form is relevant when code is evaluated, as it prevents evaluation of its
argument. If its argument is a symbol, the symbol is returned, if it is a list,
it is not treated as a function call or macro expansion or special form
invocation.
\paragraph{Example}
\label{par:read-example}
Assuming a file with the contents shown in figure~\ref{code:read-example},
reading the contents yields a list as its result: the first element is the
symbol \fun{defun}, followed by the symbol \sym{factorial}, followed by a list
containing the symbol \sym{n} as its sole element, and so on.
Note that when the code is evaluated, it defines a function (hence the symbol
\sym{defun}, a contraction of \textbf{def}ine \textbf{fun}ction, yet reading it
merely results in a list. This means that Lisp does not have keywords in the
sense that more mainstream languages have.
\begin{lstlisting}[style=lispcode,label={code:read-example},caption={A function
which calculates the factorial of its argument.},numbers=left]
(defun factorial (n)
(let ((result 1))
(while (not (zerop n))
(setf result (* result n))
(decf n))
result))
\end{lstlisting}
While it has nothing to do with reading, it is very important for the next
sections that the first element of a list (should it ever be evaluated) should
be either a special form, a macro or a function (i.e. something ``invokable'').
The exception to this rule is quoting which will be discussed in the section on
evaluation~(\ref{subsubsec:evaluation}).
\subsubsection{Macro expansion and compilation}
\label{subsubsec:compilation}
The next step is to optionally compile the code. During this step (if it is
performed) macros are expanded. In the end, every single step involved must be
a primitive operation, such as addition, calling and defining functions or
setting variables. In the example given, three macros are used: \fun{defun},
\fun{setf} and \fun{decf}. The invocation of \fun{(decf n)} expands to the form
\texttt{(setq n (1- n))}, where \fun{setq} is a primitive which performs
assignments\footnote{Either a single assignment, or many assignments may be
performed with \fun{setq}.}.
While the transformation which \fun{decf} performs may be trivial, it is already
very useful, as it shows the intent of the code a little more clearly than
spelling it out. Also, macros may become arbitrarily complex, effectively
becoming languages in their own right. The multimethod facility discussed in
section~\ref{subsubsec:multimethods} is implemented entirely as macros. Also,
\fun{cl-loop}, a port of the \cl{} looping construct is in effect a very large
macro.
This works by associating a function with a name. When this name is the first
element of a list which is evaluated, the function is called, yet not in the
normal way. The function is called with the rest of the list elements, which
have been read but not yet evaluated. This means that a macro invocation which
has the form \texttt{(+ 1 2)} as its argument is given a list of the symbol
\sym{+}, the number one and the number two. This means that the code has not
yet been evaluated (i.e. is not the number three)! The result of this function
is used as a replacement for the macro invocation. This is applied repeatedly
until no further unexpanded macro invocations remain. This mechanism allows
users to write code which transforms other code (takes code as input and
produces code as output).
This is one of the reasons Lisp code is so much more compressible than that of
many other languages.\footnote{It may be that full support for lazy evaluation
is similarly powerful.}
For a more in depth discussion of (\cl{}) macros and how to employ them, see On
Lisp by Paul Graham.\cite{on-lisp}
\subsubsection{Evaluation}
\label{subsubsec:evaluation}
If no compilation has been performed (i.e. the code is interpreted) macro
expansion as described in the previous section is performed as needed.
The exact evaluation semantics strongly depend on the Lisp dialect at hand.
Here are merely a few rules of thumb. When a list is evaluated, the first
element denotes what operation to perform while the other elements of the list
are arguments to this operation. The operation may be a macro expansion (see
the previous section), a function call or a special form. The latter is an
operation which must be built into the language runtime. In \el{} \fun{setq} is
such an operation. Special forms---like macros---may choose whether and how
often to evaluate their arguments.\footnote{Macros themselves often do not
evaluate their arguments at all, yet the code emitted by the macro may
evaluate its arguments once, several times or not at all!} The special form
\fun{setq} for instance does not evaluate its first argument, but checks whether
it is a symbol or not. If it is, the next argument is evaluated and its value
is assigned to the value slot of the symbol at hand.
If the operation is a symbol which is not a macro, all arguments are evaluated
and passed to the function which is to be found in the function slot of the
symbol.
Evaluating a symbol is done by referencing the value slot of the symbol.
% \chapter{Lisp Basics}
% \label{chapter:lisp-basics}
% This section is only intended as a short recap of what Lisp syntax is, and how
% it relates to the reader. For more details, a Lisp textbook is more
% appropriate. A good reference for \el{} is found at \cite{elisp-reference}.
% Lisp syntax never directly describes control flow, function definitions, or
% other actions, but merely data. If the described data consists of lists and
% symbols, it will later on be treated as code, which can be compiled and
% executed.
% Such data structures can represent code by having a list with an ``action'',
% which may be a special form, a macro or a function, as its first element. Any
% further elements are arguments to said operator.
% As an example, here is some code which performs a variable binding with
% \fun{let} (which is a special form), an assignment with \fun{setf} (a macro)
% and a function call to \fun{message}.
% \begin{lstlisting}[style=lispinline]
% (let ((var 5)) (setf var "Hello") (message "%s" var))
% \end{lstlisting}
% When Lisp source code is processed, it goes through three distinct stages:
% reading, macro expansion (optionally this can also be a compile phase), and
% evaluation (which can be the execution of compiled code).
% The first stage is somewhat unique to Lisp---most languages only have this as an
% implementation detail in the compiler or interpreter.
% \section{Important Lisp Data Types}
% \label{subsec:important-types}
% A few Lisp data types are of particular importance, both because they are
% relatively rare in other languages, but also because they are very widespread in
% Lisp code, i.e. the reader often creates them.
% Every Lisp dialect the author is aware of provides at least the following:
% \subsection{Symbols}
% \label{subsubsec:symbols}
% The symbol is a type which represents a name, often together with places for
% values and/or functions. The latter depend on the Lisp dialect. An important
% property of symbols is that fast lookup is supported, and that symbols are
% interned. This means that each symbol which is read, which has the same name,
% returns the same Lisp object.\footnote{This is, in effect, a singleton.}
% In \el{}, which is the Lisp under consideration for this thesis, a symbol has
% the following attributes:
% \begin{description}
% \item[{Name}] A (typically hashed) name for the symbol. This may be retrieved
% as a string at any time.
% \item[{Value}] This is the value of the symbol. It may be retrieved by a call
% to \fun{symbol-value} or by simply appearing in a program (macros or special
% forms may treat symbols differently).
% \item[{Function}] This cell is looked up if the symbol is the first element of a
% list which is evaluated (more on this later). Alternatively, a call to
% \fun{symbol-function} returns the function to which it points (if any).
% \item[{Property List}] A symbol may also have a Property List, or plist for
% short, which is a mapping from a key (mostly a symbol) to a value. This is
% intended as a mechanism to store arbitrary metadata in a symbol.
% \end{description}
% A fifth attribute exists, which is not visible from Lisp code. Symbols are
% placed into so called ``obarrays'', which are similar to hashtables, but are
% specialized to symbols (i.e. no other objects can be stored in them). To
% support fast lookup and low memory usage, each symbol contains a pointer to the
% next symbol in the same bucket of the obarray. For this reason a symbol may
% only be interned in one obarray. Because of this limitation it is not possible
% (at the time) to implement \cl{} compatible packages for \emacs{} (not to be
% confused with the packages provided in \fun{package.el}, which are installable
% units).
% \subsubsection{Read Syntax}
% \label{subsubsec:symbol-syntax}
% The read syntax for a symbol is any token of text which is not also a valid
% number, does not contain any unescaped terminating macro characters and does not
% start with an unescaped macro character.
% Thus \sym{foo}, \sym{1+}, \sym{contains?} and \sym{set!} are valid symbols.
% \sym{+1} is not, as it is the positive number one. \sym{\textbackslash{}+1} on
% the other hand is a valid symbol, as the \sym{+} sign is escaped. Its name is
% ``+1'' (i.e. the escape character is only part of the read syntax, not of the
% outcome).
% \subsection{List}
% \label{subsubsec:list}
% In Lisp parlance, when a list is mentioned, it is almost always a singly linked
% list. While by far not the only compound data structure\footnote{Strictly
% speaking, lists by themselves to not exist: there are only cons-cells, yet
% this nuance is not very important for the current discussion.}, it is a very
% important one.
% Not only is there syntax for lists; together with the symbol, the list is used
% as the prime representation for code. Lists are made up of cons cells, which
% are ordered pairs of Lisp objects. They can be constructed at runtime with a
% call to \fun{cons}, passing the two objects as arguments. Two additional
% operations fetch the contents and serve as setf-able places: \fun{car} and
% \fun{cdr}. The former fetches the first element of the cons, the latter the
% second. Cons cells can be linked. By convention, the cdr of a cons points to
% the next cons, or \sym{nil}, if at the end of a list. This type of structure is
% called a proper list. A chain of conses which do not end in a cons with a cdr
% of \sym{nil} is called an improper list.
% \subsubsection{Read Syntax}
% \label{subsubsec:list-syntax}
% Cons cells, proper and improper lists have read syntax to create them at
% read-time:
% \begin{description}
% \item[cons] A single cons may be notated as a ``dotted-pair'': \texttt{(car
% . cdr)}
% Here a new cons is created which has a car of \sym{car} and a cdr of
% \sym{cdr}.
% \item[proper list] A proper list is notated with whitespace separated elements
% surrounded by parentheses: \texttt{(foo bar)}
% This is equivalent to \texttt{(foo . (bar . nil))}
% \item[improper list] An improper list looks like a proper list, yet uses
% embedded dotted pair syntax at its end: \texttt{(foo bar . spam)} is
% equivalent to \texttt{(foo . (bar . spam))}.
% \end{description}
% \subsection{Other Types}
% \label{subsec:other-types}
% Most other types are rather unspectacular and depend on the dialect under
% consideration. Practically all Lisps provide strings, \el{} even provides an
% alternate notation which provides text properties: \texttt{\#("foo" 0 1 (escapedp
% t))}. This represents a string ``foo'', with the property \sym{'escaped} and
% the corresponding value \sym{t} on the first letter.
% Numbers are also often a little different than in mainstream languages. Both
% \cl{} and scheme provide exact fractions. \cl{} and \el{} provide read syntax
% for integers in several bases: \texttt{\#b1111} \texttt{\#o17} \texttt{\#xF} and
% \texttt{15} all represent the number 15 in base 10. This notation is the same
% in \cl{} and \el{}. This notation has a certain air of elegance to it as soon
% as one realizes that \texttt{\#} is a dispatching macro character (see section
% ~\ref{subsec:dispatching-macro-chars} for details). This means that
% \texttt{\#b}, \texttt{\#o} and \texttt{\#x} may be implemented as read macros.
\section{Motivation}
\label{section:motivation}
Users of other Lisp dialects, especially of \cl{}, have enjoyed the possibility
to modify the syntax they use to write programs for a long time. This