691 lines
39 KiB
TeX
691 lines
39 KiB
TeX
\newpart
|
|
\section{From Lisp to Scheme}\label{sec:lisp}
|
|
|
|
After the discussions about minimalism outside programming in last part, now
|
|
we come back to the subject of programming; but before examining Unix itself,
|
|
let's first discuss something outside the Unix circle -- the Lisp family of
|
|
programming languages\cupercite{wiki:lisp}. Born in 1958, Lisp is one of the
|
|
oldest programming languages, along with Fortran (1957), Algol (1958) and Cobol
|
|
(1959), and is perhaps the only one of them still constantly attracting new
|
|
interest as of now: Fortran finds little (and still diminishing) use outside
|
|
of numerical computation in science and engineering, few young programmers are
|
|
interested in maintaining existent (stale and also diminishing) Cobol codebases,
|
|
and it is fair to say that Algol as a language has been dead for long. So what
|
|
is the reason for the continued vitality of Lisp? The answer is Lisp's inherent
|
|
simplicity, and its strong \stress{expressiveness} despite the simplicity;
|
|
in this section, we will briefly examine the simplicity of Lisp.
|
|
|
|
Lisp was designed by John McCarthy\footnote{By the way,
|
|
he was also one of the pioneers in time-sharing operating systems
|
|
(\cf~Section~\ref{sec:intro}).}, who showed that a practically usable
|
|
Turing-complete language can be built with a handful of primitive
|
|
functions in addition to conditional expressions and recursive function
|
|
definitions\cupercite{mccarthy1960}. Steve Russell noted, to McCarthy's
|
|
surprise, that the \verb|eval| function in Lisp could be directly translated
|
|
into assembly code, and the result was the first Lisp interpreter, running on
|
|
an IBM 704 mainframe, compiled manually by Russell. Alan Kay, the designer of
|
|
Smalltalk, made the following comment\cupercite{feldman2004} about the idea:
|
|
\begin{quoting}
|
|
\emph{[...]} that was the big revelation to me when I was in graduate
|
|
school -- when I finally understood that the half page of code on the
|
|
bottom of page 13 of the Lisp 1.5 manual\cupercite{mccarthy1962} was Lisp
|
|
in itself. These were ``Maxwell's Equations of Software!'' This is the
|
|
whole world of programming in a few lines that I can put my hand over.
|
|
\end{quoting}
|
|
Although Lisp can be reduced to a minimal core, not all languages in
|
|
the Lisp family are indeed minimalist: for example, now the unqualified
|
|
name ``Lisp'' often means Common Lisp, which is fairly big even in terms
|
|
of core functionalities; nevertheless, proper abstractions to compress
|
|
boilerplate code are still strongly encouraged by Common Lisp experts,
|
|
like Paul Graham\cupercite{graham1993}. However, there does exist
|
|
a truly minimalist Lisp, and it is Scheme.
|
|
|
|
Scheme was not intended to be minimalist from the beginning, according to its
|
|
designers, Gerald Jay Sussman and Guy L.\ Steele Jr.\cupercite{sussman1998}\ %
|
|
(note how similar this is to Unix's conscious pursuit of simplicity after
|
|
the inception of pipes -- \cf~Section~\ref{sec:mcilroy}):
|
|
\begin{quoting}
|
|
We were actually trying to build something complicated
|
|
and discovered, serendipitously, that we had accidentally
|
|
designed something that met all our goals but was much simpler
|
|
than we had intended. \emph{[...]} we realized that the
|
|
\stress{$\bm{\lambda}$-calculus} -- a small, simple formalism --
|
|
could serve as the core of a powerful and expressive programming language.
|
|
\end{quoting}
|
|
Anyway, minimalism became a defining property of Scheme, as can be seen
|
|
from the first sentence from the introduction to its specifications,
|
|
\emph{Revised$\,^3\!$ Report on the Algorithmic Language Scheme} and
|
|
onward (usually called \rnrs{3}, \rnrs{4} \etc)\cupercite{scmreports:home}%
|
|
\footnote{\label{fn:r6rs}The specifications up to \rnrs{5} were all a few
|
|
scores (usually less than 60) pages of text, including examples and rationales;
|
|
\rnrs{6} significantly expanded both the core and standard libraries\cupercite%
|
|
{weinholt2019}, in order to standardise some (more or less legitimately)
|
|
demanded features present in mainstream languages. \rnrs{6} was highly
|
|
controversial, most importantly because certain features are less useful
|
|
for educators, hobbyists \etc{} who use just a small subset of the
|
|
functionalities\cupercite{scmreports:position}; as a result, \rnrs{7}
|
|
was intentionally separated into a ``small'' specification and a
|
|
``large'' one. Incidentally, the specification of Go is also
|
|
rough 50 pages, but Go is much less expressive than Scheme
|
|
(\cf~Section~\ref{sec:homoiconic} for an example).}:
|
|
\begin{quoting}
|
|
Programming languages should be designed not by piling
|
|
feature on top of feature, but by removing the weaknesses and
|
|
restrictions that make additional features appear necessary.
|
|
\end{quoting}
|
|
This attitude clearly resembles the Unix philosophy, and it makes Scheme
|
|
the most expressive programming language in my opinion; for this reason,
|
|
in all following text in this document I will use Scheme to represent Lisp.
|
|
|
|
The reason for this digression about Lisp is its strong expressiveness despite
|
|
the simplicity, and this expressiveness largely comes from the way Lisp code is
|
|
written -- \stress{S-expressions} (short for symbolic expressions)\footnote%
|
|
{In the original paper for Lisp\cupercite{mccarthy1960}, McCarthy actually
|
|
intended to use another form called M-expressions (short for meta expressions)
|
|
for source code, and let the computer translate them to S-expressions;
|
|
however, programmers at that time generally preferred to use S-expression
|
|
directly. M-expressions are homoiconic just like S-expressions,
|
|
and a format closely related to the former is used by Mathematica,
|
|
the computational software.}; for example, the factorial function
|
|
can be written in Scheme and Python respectively as\footnote{They
|
|
are not exactly equivalent: first, Scheme does not have a \texttt{return}
|
|
primitive, and instead uses expressions in \stress{tail positions} as well as
|
|
\stress{continuations} (\cf~Footnote~\ref{fn:cps}) to return values; second,
|
|
\texttt{(define (fn (args ...)) ...)} is a shorthand for \texttt{(define fn
|
|
(lambda (args ...) ...))} in Scheme, while Python's \texttt{lambda} is
|
|
severely limited (\cf~Section~\ref{sec:homoiconic} for an example).}:
|
|
\colskipa\begin{multicols}{2}
|
|
\begin{wquoting}
|
|
\begin{Verbatim}
|
|
(define (f i)
|
|
(if (> i 1)
|
|
(* (f (- i 1)) i)
|
|
1))
|
|
\end{Verbatim}
|
|
\end{wquoting}
|
|
\begin{wquoting}
|
|
\begin{Verbatim}
|
|
def f(i):
|
|
if i > 1:
|
|
return i * f(i - 1)
|
|
return 1
|
|
\end{Verbatim}
|
|
\end{wquoting}
|
|
\end{multicols}\colskipb\noindent%
|
|
S-expressions would probably appear unintuitive to a newbie, but they are in
|
|
fact much easier for computers to process than most alternative source code
|
|
formats, and still quite readable to the programmer after a small degree of
|
|
familiarisation. You may note that this is very similar to why text streams
|
|
are used as the interface for traditional Unix tools (\cf~Section~%
|
|
\ref{sec:mcilroy}), so why are S-expressions more machine-friendly, and
|
|
what technical advantages do they bring us? Please read the next section.
|
|
|
|
\newpart
|
|
\section{S-expressions and homoiconicity}\label{sec:homoiconic}
|
|
|
|
To understand the machine-friendliness of S-expressions, we first need to
|
|
know how source code for a program is represented internally by the computer:
|
|
whatever language you use, the source code will be converted (\stress{parsed})
|
|
into a data structure that represents its syntax elements necessary for the
|
|
computer to understand the program, and this data structure is called the
|
|
\stress{abstract syntax tree}\cupercite{wiki:ast}. For instance, the
|
|
AST corresponding to the expression $4 \times 2 - (a + 3)$ and
|
|
the S-expression equivalent to the latter are shown below:
|
|
\colskipa\begin{multicols}{2}
|
|
\begin{wquoting}[innerleftmargin = 0.45em,
|
|
innertopmargin = -0.15em, innerbottommargin = 0.15em]
|
|
\begin{forest}
|
|
for tree = {l sep = 0pt, l = 2.25em}
|
|
[$-$,
|
|
[$\times$, [$4$] [$2$]]
|
|
[$+$, [$a$] [$3$]]]
|
|
\end{forest}
|
|
\end{wquoting}
|
|
\columnbreak\vspace*{-0.64em}
|
|
\begin{wquoting}
|
|
\begin{Verbatim}
|
|
(-
|
|
(* 4 2)
|
|
(+ a 3))
|
|
\end{Verbatim}
|
|
\end{wquoting}
|
|
\end{multicols}\colskipb\noindent%
|
|
S-expressions can be regarded as representations for nested lists, and
|
|
as we can see from the example above, nested lists map to tree structures
|
|
(including ASTs) naturally; additionally, although S-expressions do not
|
|
eliminate the need for parsing, they are technically much easier to parse
|
|
than other formats, which makes them a most convenient representation for
|
|
ASTs. Therefore in combination with the strong capability for list
|
|
manipulation in Lisp (originally ``LISt Processor''), S-expressions enable
|
|
Lisp to almost effortlessly process Lisp code just like regular data.
|
|
|
|
When a language can modify source code written in itself just like other
|
|
data, it is called a \stress{homoiconic} language\cupercite{wiki:homoiconic};
|
|
the ability to treat code as data has extremely profound implications,
|
|
as can be seen from the beginning of the half-joking document \emph{The
|
|
Gospel of Tux}\footnote{Apart from the von Neumann Architecture\cupercite%
|
|
{wiki:neumann}, the profundity of the ``code is data'' idea can be
|
|
traced to earlier origins, for instance Gödel numbering\cupercite%
|
|
{wiki:godelnum} and the halting problem\cupercite{wiki:halt}.}, which
|
|
is why I consider homoiconicity a notion as profound as complexity:
|
|
\begin{quoting}
|
|
In the beginning Turing created the Machine. And the Machine was crufty
|
|
and bogacious, existing in theory only. And von Neumann looked upon
|
|
the Machine, and saw that it was crufty. He divided the Machine into
|
|
two Abstractions, \stress{the Data and the Code, and yet the two were
|
|
one Architecture}. This is a great Mystery, and the beginning of wisdom.
|
|
\end{quoting}
|
|
It was mentioned in Section~\ref{sec:boltzmann} that all Turing-equivalent
|
|
models of computation are not equally wieldy for generic discussions, and
|
|
similarly all homoiconic languages are not equally wieldy for practical ``code
|
|
as data'' usage\footnote{Another example is XML, a descendant of SGML; the
|
|
latter is in turn a document markup language, which makes the XML markup quite
|
|
verbose. Although XML naturally models a tree structure, its use outside of
|
|
document markup often results in files with more markups than contents; in
|
|
addition, the complex specification of XML makes it nontrivial to parse, and
|
|
therefore unsuitable as source code for programs.}: for example, it might be
|
|
said that all languages which support text processing are in a sense homoiconic,
|
|
because the source code is text; however, most \stress{code transformations},
|
|
that are interesting to implementers of interpreters and compilers, would be
|
|
very cumbersome to implement only with text processing mechanisms. For this
|
|
reason, in all following text in this document, when discussing homoiconicity
|
|
I will specifically mean it on the \stress{AST level}, or in other words
|
|
the ability to easily modify the AST of source code just like regular data.
|
|
|
|
In a language with AST-level homoiconicity, the macro system can be implemented
|
|
to use functions, that transform ASTs, as macros; with this kind of macros, new
|
|
syntaxes can be easily defined, and many \stress{language features} that are
|
|
hardcoded in non-homoiconic languages can be implemented as elegant extensions
|
|
to the core language. For example, goroutines, which are usually considered
|
|
one of the main features of Go, are essentially \stress{syntactic sugar} for
|
|
interfaces to lightweight coroutines in the libthread\cupercite{lucent2002}/%
|
|
libtask\cupercite{swtch:libtask} model\footnote{\label{fn:cps}Another model is
|
|
based on the \stress{continuation-passing style}\cupercite{wiki:cps}.}, and
|
|
they are hardcoded in Go exactly because new syntaxes cannot be easily added
|
|
to Go. The example about goroutines might seem slightly abstract because
|
|
we have not seen code transformations in action, and here I give
|
|
an example that is both more concrete and more advanced.
|
|
|
|
Anonymous functions, essentially $\lambda$-expressions, are very useful
|
|
when used as function arguments, as is shown in the Python code below:
|
|
\begin{wquoting}
|
|
\begin{Verbatim}
|
|
sorted(l, key = lambda e: e[0])
|
|
\end{Verbatim}
|
|
\end{wquoting}
|
|
However, the function body of \verb|lambda| in Python must be an expression,
|
|
so assignment cannot be used, for instance the following function on the left
|
|
cannot be directly transformed to a \verb|lambda|. But if we regard assignment
|
|
as a kind of filter that converts a tuple of input values (\eg~$(x, y)$) into
|
|
a modified tuple of values (\eg~$(x, y')$), the function can be transformed
|
|
into the composition of multiple \verb|lambda|s, as is shown on the right.
|
|
\colskipa\begin{multicols}{2}
|
|
\begin{wquoting}
|
|
\begin{Verbatim}
|
|
def f1(x, y):
|
|
y = y / (1 - x)
|
|
x = x + y
|
|
return x * x + y
|
|
\end{Verbatim}
|
|
\end{wquoting}
|
|
\begin{wquoting}
|
|
\begin{Verbatim}
|
|
f2 = lambda x, y:
|
|
((lambda v: v[0] * v[0] + v[1])
|
|
((lambda v: (v[0] + v[1], v[1]))
|
|
((x, y / (1 - x)))))
|
|
\end{Verbatim}
|
|
\end{wquoting}
|
|
\end{multicols}\colskipb\noindent%
|
|
The definition of \verb|f2| is evidently ugly, and part of the ugliness
|
|
lies in the explicit value tuple \verb|v|; another source of ugliness is the
|
|
reversed order of filters -- the last \verb|lambda| to be applied is written
|
|
first, because it is the outermost. In Scheme, the \verb|let| form has
|
|
its input values written before its body, so we can use it to compose
|
|
filters in the desired order, as is shown below on the left.
|
|
\colskipa\begin{multicols}{2}
|
|
\begin{wquoting}
|
|
\begin{Verbatim}
|
|
(define f3
|
|
(lambda (x y)
|
|
(let ((y (/ y (- 1 x))))
|
|
(let ((x (+ x y)))
|
|
(+ (* x x) y)))))
|
|
\end{Verbatim}
|
|
\end{wquoting}
|
|
\begin{wquoting}
|
|
\begin{Verbatim}
|
|
f3 = lambda x, y: \
|
|
(lambda y:
|
|
(lambda x: x * x + y)
|
|
(x + y)) \
|
|
(y / (1 - x))
|
|
\end{Verbatim}
|
|
\end{wquoting}
|
|
\end{multicols}\colskipb\noindent%
|
|
As you might have already guessed, \verb|let| is just syntactic sugar for
|
|
\verb|lambda|, and \texttt{(let ((a \emph{e$_1$}) (b \emph{e$_2$}) ...) ...)}
|
|
is a shorthand for \texttt{((lambda (a b ...) ...) \emph{e$_1$} \emph{e$_2$}
|
|
...)}, so \verb|f3| is equivalent to the Python function above on the right.
|
|
You should have also noticed \verb|v| is absent from \verb|f3|, and this
|
|
works because arguments of inner \verb|lambda|s (\eg~the \verb|x|
|
|
in \texttt{lambda x: x * x + y}) shadows outer variables with
|
|
the same names (\eg~the argument \verb|x| of \verb|f3|).
|
|
|
|
\colskipa\begin{multicols}{2}
|
|
\begin{wquoting}
|
|
\begin{Verbatim}
|
|
f4 = lambda x, y: check(
|
|
divide(y, 1 - x),
|
|
(lambda y:
|
|
(lambda x: x * x + y)
|
|
(x + y)))
|
|
\end{Verbatim}
|
|
\end{wquoting}
|
|
\begin{wquoting}
|
|
\begin{Verbatim}
|
|
check = lambda arg, fn: \
|
|
None if arg == None else fn(arg)
|
|
|
|
divide = lambda a, b: \
|
|
None if b == 0 else a / b
|
|
\end{Verbatim}
|
|
\end{wquoting}
|
|
\end{multicols}\colskipb
|
|
Nevertheless, this is not the end of the story, because $1 - x$ might
|
|
be zero, and I want the function to return \verb|None| in such cases;
|
|
but considering that functions are only evaluated when applied to some
|
|
arguments, \verb|f3| can be transformed into the function above on the left,
|
|
with ancillary functions on the right. Moreover, I did not tell you $x$ and
|
|
$y$ might be \verb|None| instead of numbers, but following the line of thought
|
|
above, we can further transform \verb|f4| into\footnote{Incidentally, this is
|
|
reminiscent of the continuation-passing style (\cf~Footnote~\ref{fn:cps}),
|
|
which is in fact not a coincidence\cupercite{troelskn2009}.}
|
|
\begin{wquoting}
|
|
\begin{Verbatim}
|
|
f5 = lambda x, y: check(
|
|
x, (lambda x: check(
|
|
y, (lambda y: check(
|
|
divide(y, 1 - x), (lambda y: check(
|
|
x + y, (lambda x: x * x + y))))))))
|
|
\end{Verbatim}
|
|
\end{wquoting}
|
|
Using this technique, we have actually implemented exceptions in a purely
|
|
functional way\footnote{Conversely, we can also see that, as a matter of fact,
|
|
exceptions have a ground in type theory. Besides, I find it necessary to note
|
|
that unlike Haskell, Lisp does not pursue purely functional programming, though
|
|
the functional style is certainly preferred.}; if you are familiar with Haskell,
|
|
you might realise this is essentially using a monad. A Haskell counterpart of
|
|
\verb|f5| can be written in the form below on the left, which is equivalent
|
|
to the form on the right using syntactic sugar hardcoded in Haskell\footnote%
|
|
{\texttt{return} in Haskell is just a function, and the two \texttt{return}s
|
|
on the right correspond exactly to the two \texttt{Just}s on the left,
|
|
which are needed due to type-theoretical requirements in Haskell.}.
|
|
\colskipa\begin{multicols}{2}
|
|
\begin{wquoting}
|
|
\begin{Verbatim}
|
|
f5 = \x y ->
|
|
(x >>= \x ->
|
|
(y >>= \y ->
|
|
(divide y (1 - x) >>= \y ->
|
|
(Just (x + y) >>= \x ->
|
|
Just (x * x + y)))))
|
|
\end{Verbatim}
|
|
\end{wquoting}
|
|
\begin{wquoting}
|
|
\begin{Verbatim}
|
|
f5 = \x y -> do
|
|
x <- x
|
|
y <- y
|
|
y <- divide y (1 - x)
|
|
x <- return (x + y)
|
|
return (x * x + y)
|
|
\end{Verbatim}
|
|
\end{wquoting}
|
|
\end{multicols}\colskipb\noindent%
|
|
So what is the role of Scheme and S-expressions here? As was mentioned
|
|
just now, the syntactic sugar above is hardcoded in Haskell;
|
|
in Scheme, it can be implemented as a syntactic extension.
|
|
|
|
In the end of this section, I find it necessary to note that in the operating
|
|
system, \stress{directory trees resemble S-expressions} in that they are
|
|
essentially tree structures; the ``everything is a file'' principle of Unix
|
|
(\cf~Section~\ref{sec:plan9}) is a direct result of this idea, although
|
|
most important contributors to Unix probably did not realise the similar
|
|
potential of S-expressions. For example Daniel J.\ Bernstein noted, in the
|
|
context of security, that parsing and quoting of textual data significantly
|
|
complicate software systems\cupercite{djb:qmailsec}; instead, he extensively
|
|
used directory trees with very simple formats to configure his software, and
|
|
this practice is also adopted by some programmers with close relation
|
|
to his software, as can be seen in most daemontools-ish systems.
|
|
|
|
The complexity of parsing could have been greatly alleviated had we used
|
|
homoiconic formats, like S-expressions, when processing data with complicated
|
|
structures; the implications of homoiconicity in the context of Unix philosophy
|
|
will be further examined in the rest of this document, and here I instead
|
|
want to consider a little more about directory trees: given the similarity
|
|
between directory trees and S-expressions, why don't we simply replace most
|
|
configuration directories with files containing S-expressions? In my opinion,
|
|
an S-expression file is indeed easier to work with than a directory tree is,
|
|
but it is also more rigid and monolithic; in comparison, with a directory
|
|
tree we can update parts of the configuration atomically, and can assign
|
|
different permissions to different parts. Both of the latter are much
|
|
harder to achieve with a single file, which I believe shows the
|
|
advantage of directory trees as a configuration interface.
|
|
|
|
\section{The New Jersey and MIT~/ Stanford styles}\label{sec:wib}
|
|
|
|
In last section, we have seen the unrivaled power from homoiconcity, which
|
|
allows the macro system to easily manipulate ASTs in order to implement new
|
|
language features; furthermore, because the macro expansion is recursive,
|
|
macros in later parts of a program can access all language features defined
|
|
earlier. When writing high-performance interpreters and optimising compilers,
|
|
homoiconicity enables us to not only write transformations on the processed
|
|
source code succinctly by using these \stress{structural macros}, but also
|
|
implement the transformations as multiple simple, clear and reliable passes,
|
|
similar to traditional Unix tools connected by pipes. The prime example for
|
|
this \stress{multi-pass processing} scheme\footnote{\label{fn:slew}Noticing
|
|
the analogy between directory trees and S-expressions in Section~%
|
|
\ref{sec:homoiconic}, we can also implement multi-pass preprocessors for
|
|
configuration directories\cupercite{gitea:slewman}; furthermore, from the
|
|
viewpoint of the Prototype Pattern, \texttt{fork()}/\texttt{exec()} and
|
|
Bernstein chainloading can also be regarded as similar designs.} is the
|
|
nanopass framework\cupercite{andersen2016}\footnote{Incidentally, the
|
|
name of one main author of nanopass, when abbreviated, becomes ``AWK''.},
|
|
which is used by Chez Scheme\cupercite{wiki:chez}, the prestigious Scheme
|
|
compiler that became open-source in 2016; Chez Scheme often produces
|
|
executables that are even faster than workalikes written in C, yet it
|
|
has a codebase more than one order of magnitude smaller than that of GCC,
|
|
and self-compiles in seconds while GCC requires thousands of seconds.
|
|
|
|
As can already be seen above, in comparison with Lisp, C is in many aspects an
|
|
inferior language\cupercite{graham2002}, to put it bluntly, and the pros and
|
|
cons of both will be further examined in the next section; this is a result of
|
|
effects from multiple historical and methodological factors, and I summarise
|
|
them as the following. Due to hardware limitations, C basically began as a
|
|
portable assembly language, reasonably simple to implement with acceptable
|
|
performance on computers at Bell Labs; due to the success of Unix, continued
|
|
efforts are made to create stronger optimising C compilers, so it is still one
|
|
of the most performant languages; and while it certainly has multiple weaknesses
|
|
in comparison with other languages, people usually either do not find the
|
|
weaknesses a major drawback, or simply use alternative languages. In simple
|
|
words, C was chosen by Unix initially because the former was simple to implement
|
|
and fairly easy to use, and later mainly because of inertia; the first reason
|
|
highlights some kind of pragmatism present throughout the development of Unix,
|
|
and a well-known summary of it is Richard P.\ Gabriel's ``worse is better''%
|
|
\cupercite{dreamsongs:wib}\footnote{As you can see from the page, Richard
|
|
P.\ Gabriel had still not decided which style was better. Additionally,
|
|
the complexity issue of interruptible system calls in Unix can be bypassed
|
|
by userspace wrappers that simply retry until the system calls return without
|
|
interruption; however, current standards curiously do not require such
|
|
wrappers, which is one reason why Daniel J.\ Bernstein created
|
|
his own interface set (\cf~Section~\ref{sec:devel}).}.
|
|
|
|
Gabriel compared Lisp with Unix and concluded that, basically, when simplicity
|
|
of the interface and simplicity of the implementation conflict\footnote{Richard
|
|
P.\ Gabriel later noted in \emph{Worse is Better is Worse} that people often
|
|
ignore this central premise, and instead just blindly aim to produce software
|
|
that only implements 50\% of the requirements. Another sign of ignoring the
|
|
premise, I believe, is the objection to refactoring when attempting to fulfill
|
|
the complete requirements, with ``worse is better'' as an excuse\cupercite%
|
|
{chiusano2014}.}, Lisp would choose the former (``\stress{the right thing}'' or
|
|
the MIT~/ Stanford style), while Unix would choose the latter (``\stress{worse
|
|
is better}'' or the New Jersey style). Apart from C, another main manifestation
|
|
of ``worse is better'' in Unix is the preference of textual interfaces by
|
|
traditional Unix tools\footnote{In addition to the plain text \vs~S-expressions
|
|
debate, there is also the text \vs~binary debate; in my opinion, from cases
|
|
like the use of CDB in qmail and s6-rc, we can see that binary files are not
|
|
always avoided, but only when there are simple ways to use text files without
|
|
compromising the requirements (\eg~performance and security).} (\cf~Section~%
|
|
\ref{sec:mcilroy}); and just like C, textual interfaces are often criticised in
|
|
the Lisp circle, because plain text is unstructured unlike homoiconic formats
|
|
(\eg~S-expressions). However, from the perspective of minimising the system's
|
|
total complexity which covers both the interface and the implementation, I
|
|
believe that \stress{the choice between plain text and S-expressions is not
|
|
a black-or-white problem}: when processing data with simple structures, using
|
|
plain text is usually better because the interface is still easy enough to use;
|
|
in contrast, when processing data with complicated structures, the decrease in
|
|
interfacial complexity of using S-expressions often outweighs the increase
|
|
in implementational complexity. When dealing with languages, extensive
|
|
processing of data with deeply nested and often self-referencing
|
|
structures are necessary, so S-expressions are undoubtedly preferable.
|
|
|
|
Another common criticism against Unix from the Lisp circle is that the former
|
|
relentlessly exposes low-level details to the user, and that instead these
|
|
details should be hidden from the user by means of encapsulation\footnote{From
|
|
this criticism, we can also understand why Lisp focuses more on the interfacial
|
|
complexity.}; however, a common problem with encapsulation is \stress{leaky
|
|
abstractions}, where customisation often has to be achieved by working around
|
|
the encapsulation. systemd and Linux distributions from Red Hat, examined
|
|
in the first part of this document, are the more severe examples; actually
|
|
I believe there are few abstractions that are satisfactorily airtight,
|
|
and among them are certain well-designed programming languages as well
|
|
as kernels of Unix-like operating systems. Even when we distinguish
|
|
between ``normal'' and ``advanced'' users, providing encapsulation
|
|
to the former without interfering with the latter's convenience
|
|
in customising and debugging does not seem like a solved problem.
|
|
|
|
\section{Benefits of reconciling Unix and Lisp}\label{sec:benefits}
|
|
|
|
As was noted in last section, C is an inferior language to Lisp, most
|
|
importantly due to its lack of expressiveness: for example, had it used a macro
|
|
system (like that in Dale\cupercite{github:dale}) that could modify ASTs, then
|
|
features like object-oriented programming would be implementable using macros,
|
|
and C++ would perhaps have been unnecessary. Another prominent weakness of C,
|
|
widely noted both inside and outside the Lisp circle, is its memory unsafety
|
|
which results in buffer overflows, null-pointer dereferences \etc; alternative
|
|
C libraries like skalibs (\cf~Section~\ref{sec:devel}) surely help to reduce
|
|
this kind of bugs, but are far from able to reducing them to the minimum,
|
|
and I will mention a possible strategy for this in the next section.
|
|
|
|
However, to be fair, Lisp also has its weaknesses, among which a best-known is
|
|
the performance cost of dynamic type checking, especially in scenarios like
|
|
numerical computation; automatic type inference, even in its advanced form in
|
|
\eg~Chez Scheme, is not a universal solution to this problem. Another main
|
|
problem is the necessity of garbage collection in Lisp implementations, which
|
|
makes compiled executables larger in size and often unsuitable for use in
|
|
real-time environments; furthermore, advanced requirements for low-level
|
|
development, for instance cryptography (\cf~NaCl and BearSSL) which often
|
|
requires both constant-time execution and high performance (often involving
|
|
assembly), seem largely ignored in the Lisp circle. To summarise them up,
|
|
from what I know, I feel that while Lisp is good at implementing complicated
|
|
application requirements through abstractions, it is less involved
|
|
in low-level development, where it has big potentials in fact.
|
|
|
|
Something interesting lies in the observations above -- the pros and cons
|
|
of Lisp and C seem to be complementary; this naturally leads to the guess
|
|
that if we somehow manage to design \stress{a minimalist homoiconic language
|
|
that combines their strengths while avoiding their weaknesses}, it would be,
|
|
in Tony Hoare's words\cupercite{hoare1981}\footnote{A most important lesson we
|
|
have to learn from the speech, as Tony Hoare put it, is that simplicity must
|
|
be taken as the first priority when pursuing an ultimate language.},
|
|
\begin{quoting}
|
|
\emph{[...]} a language to end all languages, designed to meet the needs
|
|
of all computer applications, both commercial and scientific, \emph{[...]}
|
|
\end{quoting}
|
|
But is that achievable? If yes, how to do it, and what would we get?
|
|
If no, would the attempt be worthwhile? My guess for the first question
|
|
is ``yes'', while the second and the fourth will be respectively
|
|
explored in the next section and Section~\ref{sec:toe}; in the rest
|
|
of this section, I will give some examples for the third question.
|
|
|
|
As was mentioned in Section~\ref{sec:exec}, Laurent Bercot implemented the unit
|
|
operations in chainloading as a set of command-line tools; in order to implement
|
|
unit operations involving two commands (\eg~loops and pipelines), he designed
|
|
a special quoting syntax for command line arguments, and wrapped it up as
|
|
``blocks''\cupercite{ska:elblocks} in his language called execline\footnote{Its
|
|
design is similar to the initial shell in Unix, the Thompson shell\cupercite%
|
|
{wiki:thompson}, which was substituted by the Bourne shell in Unix v7 due to
|
|
its inadequacy for more complex programming.}. Nevertheless, chainloading
|
|
does not necessarily imply \verb|exec()|, and instead can be done in a
|
|
shell-like language\cupercite{vector2016a} (\cf~shell commands like \verb|cd|
|
|
and \verb|umask|); based on the model of scsh\cupercite{scsh:home}, the execline
|
|
language can be replaced with scsh-like Scheme, with chainloaders replaced by
|
|
scsh-like Scheme programs analogous to the following shell reimplementation of
|
|
the \verb|cd| chainloader provided by execline\cupercite{vector2018c}:
|
|
\begin{wquoting}
|
|
\begin{Verbatim}
|
|
#!/bin/rc -e
|
|
cd $1; shift; exec $*
|
|
\end{Verbatim}
|
|
\end{wquoting}
|
|
|
|
Following this line of thought, it is not unimaginable to replace traditional
|
|
Unix tools with Scheme programs as well; considering the expressiveness of
|
|
Scheme and the existence of elegant Scheme compilers like Chez Scheme, this
|
|
would surely help to reduce the total complexity of the system. So now we
|
|
see that by migrating to Lisp for system programming, even these simple
|
|
tools can be further simplified; and as was noted before, Lisp is probably
|
|
even more powerful for application programming, so I find it undoubted
|
|
that \stress{by embracing homoiconicity, we will be able to build
|
|
systems that are more Unix-ish than was possible before}.
|
|
|
|
Now that we have seen the power of homoiconicity in system programming, it is
|
|
appropriate to revisit the Trusting Trust issue in Section~\ref{sec:security};
|
|
at that time I noted that one method against Trusting Trust is to construct the
|
|
compiler from the machine code in multiple steps, and it should be self-evident
|
|
that the auditability of this procedure directly depends on the latter's total
|
|
complexity. It was also noted in Section~\ref{sec:lisp} that Steve Russell
|
|
implemented the first Lisp interpreter in assembly by hand, which in combination
|
|
with the elegance of Chez Scheme tells us that \stress{homoiconicity will
|
|
dramatically reduce the total complexity of bootstrapping from machine code},
|
|
and therefore strengthen our defence against Trusting Trust\footnote{Another
|
|
potential problem is hardware backdoors, and I think a way to deter them is to
|
|
leave adequate room for variation in every step of the bootstrapping procedure:
|
|
because the semantics of low-level code is difficult to analyse (which results
|
|
in the importance of open source), any attempt at mechanically injecting
|
|
malicious code may trigger false positives, which may expose the backdoor.}.
|
|
|
|
\section{Lisp~/ C reconciliation: how to?}\label{sec:howto}
|
|
|
|
As was emphasised in Section~\ref{sec:devel}, we should analyse specific issues
|
|
specifically, and while the disappearance of resource limitations does not imply
|
|
simplicity was no longer important, it surely motivates us to rethink previous
|
|
compromises made due to these limitations. We are well past the era where
|
|
garbage collection was prohibitively expensive for regular computers, and now
|
|
for devices with severely limited resource we generally prefer cross-compilation
|
|
over native compilation. Given this observation while considering the issue
|
|
of big executables and real-time requirements in last section, the proposed
|
|
language (I give it the codename ``Nil'', for uNIx plus Lisp) should be able
|
|
to use GC for its interpreter and compiler, but \stress{executables produced
|
|
by the compiler might need to avoid using GC whenever reasonable}\footnote%
|
|
{And the programmer should be aware of how to avoid GC when implementing
|
|
special requirements, or alternatively we can perhaps consider (optional and
|
|
configurable) real-time GC\cupercite{bernstein2013}. Furtherly, considering
|
|
the inherent pros and cons of different methods for memory management (GC, RAII,
|
|
manual management \etc), we probably need a minimal mechanism where multiple
|
|
memory-management methods can be used at the same time without conflicts.}.
|
|
|
|
In last section, we revisited the issue of bootstrapping, and I hinted about
|
|
a procedure where a minimal interpreter is somehow built, and then in a later
|
|
step a production-ready compiler is produced; a first point to note is that
|
|
this deviates from today's common practice of using a compiler to build an
|
|
interpreter, and instead constructs an interpreter first. However, as can be
|
|
guessed, Nil interpreters would probably be easier to write in assembly than
|
|
Nil compilers are, just as with Lisp which Nil is modeled upon, so from the
|
|
viewpoint of complexity it would be better to generate the compiler from a
|
|
primitive interpreter\footnote{Probably in multiple steps, involving more and
|
|
more powerful compilers, interpreters and even assemblers, and the assemblers
|
|
would probably somehow resemble the proposed Nil-powered assembly; to facilitate
|
|
auditing, a smaller number of intermediate steps should probably be preferred,
|
|
as long as the total size of the codebase involved is close to the minimum.
|
|
Besides, on a more theoretical level, I find the notion of Futamura projections
|
|
(essentially \stress{partial evaluation})\cupercite{wiki:parteval} highly
|
|
interesting.}. Similarly, noticing the expressiveness of Nil, it would
|
|
be natural to use a self-bootstrappable Nil compiler as the base
|
|
compiler in production systems, from which other compilers (if
|
|
still necessary, and perhaps including one for C) are produced.
|
|
|
|
Hitherto in this section, we have been examining the Lisp-like aspects of Nil,
|
|
but what about the C-like aspects? I consider Dale, mentioned in last section,
|
|
a possible prototype for a C-like layer, upon which a Lisp-like layer would
|
|
be implemented using macros, and many other languages (\eg~shell and Makefile)
|
|
would be emulated in turn on the Lisp-like layer, accessible to the user via
|
|
something like \hologo{LaTeX}'s \stress{macro packages}. Another approach I
|
|
have thought of, which I give the codename Nil-powered assembly, is based on the
|
|
notion of a portable assembly\footnote{Since the C-like layer would essentially
|
|
be a machine code generator, similar generators like Chez Scheme's built-in
|
|
assembler and Daniel J.\ Bernstein's qhasm might be highly instructive
|
|
references.} (\cf~Section~\ref{sec:wib}): the C-like layer would be implemented
|
|
based on the Lisp-like layer as most other languages would be, and it
|
|
would be a markup-like ``reverse-macro'' system which provides primitive
|
|
procedures that when called emit assembly instructions to the output.
|
|
|
|
In addition, as was noted in last section, Nil needs a type system stronger than
|
|
that of Lisp, for which I find Yin Wang's design base on \stress{contracts}%
|
|
\cupercite{wangyin2013a, wangyin2013b} a very thought-provoking reference;
|
|
it is worth noting that this design helps to boost memory safety of the C-like
|
|
layer, and even facilitates the formal verification of written programs (\cf~%
|
|
Footnote~\ref{fn:formal}). The foreign function interface between the Lisp-like
|
|
and C-like layers will also be an issue, which I am not yet knowledgeable enough
|
|
to comment on. Finally, before ending this section, I need to stress the
|
|
non-technical issue of inertia, which troubles Scheme (\cf~Footnote~%
|
|
\ref{fn:r6rs}), Plan~9 (\cf~Footnote~\ref{fn:plan9}) as well as qmail and
|
|
other excellent (or not) software projects: apart from the technical challenges
|
|
Nil will inevitably encounter, it will also have to attract some attention
|
|
from both academia and industry to gain enough momentum (there is surely the
|
|
possibility that the latter simply does not care, but see the next section);
|
|
and even if Nil might have some success, getting rid of historical burdens
|
|
while adapting to new requirements\footnote{For programming languages, one
|
|
of its most important aspects is the (careful) standardisation of additional
|
|
language features and libraries, which is in my opinion done terribly by
|
|
the Scheme community.} would not be easy for it, as is for other projects.
|
|
|
|
\section{Toward a ``theory of everything''}\label{sec:toe}
|
|
|
|
As was noted in last section and Section~\ref{sec:benefits}, Nil might be a
|
|
language that is impossible even in the theoretical sense, or might not attract
|
|
adequate attention from the industry, so would the exploration on Nil still be
|
|
worthwhile in such cases? In this final section, I will give my answer
|
|
to this question based on the analogy I made in \parencite{vector2018c}:
|
|
\begin{quoting}
|
|
I guess reconciling Lisp and Unix would be much easier than
|
|
reconciling quantum mechanics and general relativity; and
|
|
it would be, in a perhaps exaggerated sense, as meaningful.
|
|
\end{quoting}
|
|
|
|
Theoretical physicists and high-energy physicists have long pursued a theory
|
|
of everything that can reconcile quantum field theory and general relativity,
|
|
because the theory would provide a unified basis for all low-level physical
|
|
phenomena. To my knowledge, there does not seem to be a firm guarantee such
|
|
a theory can be successfully achieved by humans: for example, the best-known
|
|
candidate, string theory, still appears far from testable, even though it does
|
|
agree with observed facts. On the other hand, there is not a proof that such
|
|
a theory is unachievable, either; and apart from the theoretical promises,
|
|
research on it has always been giving rise to exciting advancement in diverse
|
|
fields ranging from pure mathematics (profoundly connected to theoretical
|
|
physics) to civil engineering (involved in the construction of large
|
|
facilities for physical experiments). For these two reasons,
|
|
a ToE is still the lifelong pursuit to many physicists.
|
|
|
|
Similarly, although the efforts at Lisp~/ C reconciliation are not guaranteed
|
|
to really result in an ultimate language, it would surely be rewarding to
|
|
explore \stress{the best way the two languages can collaborate}, so that the
|
|
system's complexity is minimised and the programmer's productivity is maximised:
|
|
as has already been seen in Section~\ref{sec:benefits}, the reconciliation, even
|
|
in a very primitive form, can already contribute greatly to the reduction in the
|
|
complexity of Unix systems; I believe that further simplification of these
|
|
systems will attract more people to explore the fundamental aspects of computer
|
|
systems, just like how the Raspberry Pi reignited the enthusiasm for low-level
|
|
development. And even if our efforts might not result in production-ready
|
|
Nil-based systems finally, I am completely convinced that insightful
|
|
communication between the Unix and Lisp circles will, as was explained in
|
|
Section~\ref{sec:worklife}, definitely result in a lot of \stress{byproducts
|
|
that are both interesting and meaningful}, therefore I conclude this document
|
|
with two quotations respectively from Rob Pike\cupercite{pike2000}%
|
|
\footnote{The description is, ironically, applicable to himself as well
|
|
regarding programming languages.} and Hal Abelson\cupercite{abelson2008}:
|
|
\begin{quoting}
|
|
Narrowness of experience leads to narrowness of imagination.
|
|
\end{quoting}
|
|
\colskipc
|
|
\begin{quoting}
|
|
If you \emph{[carefully study the example interpreters in this book]},
|
|
you will change your view of your programming, and your view of
|
|
yourself as a programmer. You'll come to see yourself as a designer
|
|
of languages rather than only a user of languages, as a person
|
|
who chooses the rules by which languages are put together, rather
|
|
than only a follower of rules that other people have chosen.
|
|
\end{quoting}
|
|
|