The development of my statically typed scripting language Umka has entered the stage when it was required to test the language capabilities using more complex examples than scripts in a couple of dozen lines. For this, I decided to implement the Lisp interpreter in my language . I was inspired by a pedagogical experiment by Rob Pike, one of the creators of the Go language. Pike recently published a small Lisp interpreter in Go . I was particularly impressed by Pike's remark that the interpreter description was on one page 13 of the ancient Lisp 1.5 manual.... Given the syntactic affinity of Umka and Go, it was difficult to resist the temptation to build such an interpreter in Umka, not by literally carrying Pike's code, but completely from scratch. I hope that the connoisseurs of Lisp and functional languages will forgive me the naive amazement of being in contact with beauty.
To the uninitiated, Lisp can come across as close to shock. Where is the line between code and data? Where are the loops? Where is the stack? The only data structure is a tree. It can also represent a list. It also becomes an abstract syntax tree when the program is parsed. It also replaces the stack when evaluating expressions. Any tree can be tried to be executed as code or used as data. Instead of loops - recursion. There is not even arithmetic in the core of the language. Yet it is a Turing complete language that can be infinitely expanded and sprinkled with syntactic sugar.
Defining a minimal Lisp interpreter really takes less than a page. On a stretch, of course: it uses functions defined on several previous pages. It seems that Lisp creator John McCarthy, out of excitement, tried to surpass himself in conciseness and eventually published a micro-Lisp manual containing the definition of the language along with the source of the interpreter - a total of two magazine pages. True, he added to the title: " Not the whole truth ".
The core of the language (here we are talking about the oldest and simplest dialects) requires five elementary functions, four keywords and two constants that cannot be expressed by means of the language itself.
Basic language constructs for those who are not familiar with them
(car x)- highlighting the head of the listx(cdr x)—x(cons x y)—xy(atom x)—x(eq x y)—xy(cond (a x) (b y))—xyab(quote x)—x,((lambda (x) a) y)—a,xy((label ff (lambda (x) a)) y)—fft—nil—
, . , , , 6:
((label fac (lambda (n) (cond ((eq n 0) 1) ((quote t) (mul n (fac (sub n 1))))))) 6)
Lisp, . Lisp 1.5 13 , . . , REPL . , , , label defn, , . Lisp .
Since the entire interpreter is riddled with recursion and tree processing, it served as an excellent test for many of the features of the Umka language, from stacking to garbage collection. I think Umka did well on the test. We had to fix only two or three minor bugs related to the export of names and advanced type declarations. The entire interpreter code was less than 400 lines long.
For those who want to play with my interpreter and pass on inspiration from Rob Pike through the relay, I recommend taking the folder with examples from the master branch , and not from the latest release .