Why is studying a Lisp interpreter in lisp so important?

Question

I have seen many CS curriculums and learning suggestions for new programmers that call for the aspiring programmer to study a Lisp interpreter that is specifically written in Lisp. All these sites say things similar to, "its an intellectual revelation", "it is an enlightenment experience every serious programmer should have," or "it shows you hardware/software relationships," and other vague statements, particularly from this article taken from this reputable how-to.

The general sentiment of my question is, how does Lisp achieve the above goals and why Lisp? Why not some other language?

I am asking this because I just finished writing a scheme interpreter in scheme (taken from SICP http://mitpress.mit.edu/sicp/ ) and now I am writing a python interpreter in scheme and I am struggling to have this legendary epiphany that is supposed to come specifically from the former. I am looking for specific technical details between the two languages that I can exploit in their scheme interpreters to gain understanding about how programs work.

More specifically:

Why is the study of an interpreter that is written in the language it interprets so emphasized - is it merely a great mental exercise to keep the original language and built language straight or are there specific problems whose solutions can only be found in the nature of the original language?

How do Lisp interpreters demonstrate good architecture concepts for one's future software design?

What would I miss if I did this exercise in a different language like C++ or Java?

What is the most used takeaway or "mental tool" from this exercise? **

** I selected the answer I did because I have noticed that I have gained from this exercise more skill in designing parsing tools in my head than any other single tool and I would like to find different methods of parsing that may work better for the scheme interpreter than the python interpreter.

• gnat: meta.programmers.stackexchange.com/a/6488/40980
• Robert Harvey: @gnat Not exactly career advice, more of a "what's so great about Lisp" question.
• gnat: @RobertHarvey that link is not only for career but also for education advice, I meant this. But, well, Lisp-is-so-great is probably a good fit too
• Jimmy Hoffa: You seem to be asking what you'll learn from a particular exercise. Your reticence is a sign of laziness, key to any good programmer, but regardless the only way to find out what you'll learn from an exercise is to do it and see. No one can tell you what you'll learn from doing that, you'll just have to do it.
• TheRubberDuck: While this question relates to education as a whole, I wouldn't classify it as "education advice" in the way "What language should I learn?" is. That is, it's not specific to a certain type of course or job. In fact, if you trim away some of the education buzzwords, this is a question about programming languages as a whole, whose answers discuss language features. It's really not specific to Lisp, either, but can be applied to other homoiconic languages like xslt. So I won't say this is a perfect question, just that it's not simply "career advice".

Answer 1

At the risk of giving a "me too" answer, if you try it you'll see...

If you study computer languages, you're likely to get the impression that it's at least half about parsing. If you learn Lisp, you'll realize parsing the surface syntax is nothing more than a convenience for people (like most of us) who don't like Lots of Irritating Single Parentheses.

Then you could realize that a big price was paid for that convenience. In Lisp it is trivial for a program to build another program and execute it. In other languages it is an advanced technique, like doing multiplication in roman numerals.

Of course, nearly everybody would ask "who needs to do that?" Well, you could very well see that it opens up a whole vista of things you never even realized you couldn't do before. You can do it in other languages, but not nearly so easily.

INSERTED to answer Izkata comment:

• The SHRDLU natural-language-understanding program worked by translating an English statement or question into a program in a Lisp dialect called MICRO-PLANNER and executing it.
• Programs that manipulate programs, for example to simplify them or prove them correct are naturally written in Lisp.
• I used program generation in a program to comprehend visual scenes, where it had to deal with all the symmetries capable in 3-dimensional objects, without multiplying the code.
• Anything having to do with logic and theorem-proving deals in manipulating logical expressions, which are a form of program.
• Symbolic math, such as symbolic integral or differential calculus, involves manipulating math expressions, which are like miniature programs.
• Any problem involving code generation, or the more highbrow term "partial evaluation", is natural in Lisp. I did this for a database bridge program a long time ago. I did it in C, which was not as easy as Lisp, but I got the idea from Lisp. That was regarded as a technique that almost nobody could do at that time (especially the COBOL-heads). Maybe more now, I hope.

... that's just a few ...

Then you realize some things that are considered "modern" today have been old-hat in Lisp for 40-some years. Like functional programming. Like garbage collection. Like closures.

That's not to say modern languages don't have new good ideas, like OOP, etc. But if you learn Lisp it will broaden your perspective.

• Izkata: You can do it in other languages, but not nearly so easily. - Like? (The question to me seems to be because statements like these are often made, but almost never get more specific)
• Dmytro: I first thought the world was revolutionized when I realized javascript could print it's own source code and objects could be traversed to obtain string literal that can be evald into the object literal. Then I realized Perl had this all along with $Data::Dumper::Deparse, and then I realized lisp had this forever. Understanding interpretors unlocks this power that has always there to build living modules, and in Lisp this is more accessible than any other language.
• Dmytro: funny thing is a Lisp programmer aware of Lisps internals can always make their own Lisp frontend to any dynamic language from javascript to bash or perl or python; lisp nicely bootstraps from available environment.

Answer 2

The simple answer to your question is to try Lisp, preferably in conjunction with SICP. Then you will be enlightened.

That said...

Code is Data
Most languages make a sharp distinction between code and data; Lisp does not. This makes it possible to, for example, trivially write a Lisp parser in Lisp, and to manipulate Lisp code within Lisp. The best description of this enlightenment that I have found is The Nature of Lisp.

This is true in part because the syntax for the language is so simple. It makes possible things in Lisp (like metaprogramming) which are impractical in other languages because the syntax gets in the way.

Further Reading
Beating the Averages

• user39685: 2nd paragraph doesn't make sense: homoiconicity != simple syntax; simple syntax makes it easy to write a Lisp parser in any language (see this). 3rd paragraph is vague, needs example(s).
• Jimmy Hoffa: @MattFenwick it's true that homoiconicity can be done with complex syntax, but that would be exceedingly difficult. It's fair to assume that if you're dealing with a homoiconic syntax, it is going to be simple, if for no other reason than the consistency demanded of it that will make it ineffibly easier to follow than a non-homoiconic syntax. Though your second point is a good one, LISP is easy to parse because it's simple syntax, not because of homoiconicity (even if the homoiconicity is the cause for that simplicity)
• nomen: In any case, there is little overhead to taking a data value and interpreting it as a program. This is a nice thing. Programming by configuration is straight-forward when all you have to do is write an interpreter for the configuration data. Advanced mathematical transformations (which are difficult to implement in stateful langauges) are often "reduced" to mere syntactic transformations of the pure fragment of Lisp.
• Robert Harvey: @MattFenwick: I've removed the word "Homoiconicity" from my answer.
• Doval: I wish I could give more than a +1 for The Nature of Lisp; I've never seen such a great explanation.

Answer 3

Why is the study of an interpreter that is written in the language it interprets so emphasized?

In general, studying an interpreter gives you insight into its language and features. In general, studying code in a programming language is like practicing a spoken language by listening and reading: it familiarizes you with what that language can do, how it's used, and common "idioms". More specifically, Lisp is a homoiconic language, meaning its syntax for expressions is the same as its syntax for data. Writing code in Lisp looks awfully like you're writing out a list, and vice-versa. Thus, interpreting Lisp code with Lisp code is as simple as running through lists with car and cdr.

How should I capitalize on this exercise to get the most out of it conceptually?

Think about how the interpreter would interpret itself - in many meta-circular interpreter implementations (where a homoiconic language interprets itself) can just "pass through" the function. For example, To implement car, simply take the car of the argument. This takes the emphasis away from data storage mechanisms and focuses on functionality.

How do lisp interpreters demonstrate good architecture concepts for one's future software design?

Interpreters can be very complicated, which encourages good architecture in designing them. With that in mind, this one is more dependent on the individual interpreter.

What would I miss if I did this exercise in a different language like C++ or Java?

These languages aren't homoiconic, so they don't benefit from the grace and simplicity of a meta-circular Lisp interpreter. This makes the exercise harder, and perhaps less common, but I wouldn't say it's really any less beneficial.

What is the most used takeaway or "mental tool" from this exercise?

I'm not sure I have a good answer for this one; simply that it helps to see how the interpreter works and, maybe more importantly, tinker around with it to see how minor changes to the language can be easily implemented.

Answer 4

LISP is itself structured in a way which makes it extremely easy to parse. If you try to write a compiler, you will notice that it's a lot easier if everything in your language is an expression and has a low level of ambiguity. LISP forces parentheses everywhere to eliminate ambiguity and has no statements, only expressions.

The very fact that LISP is very easy to parse encourages users to parse their own source code and do magic tricks with it. The line between data and code becomes blurred and you can easily do things which normally require quite some effort, like reflection, dynamic code rewrite, plugins and serialization.

That's the gist of it. The exercise is probably meant to give you some insight into what is possible when the code is easily parseable from itself.

• Rainer Joswig: It's not Lisp that's easy to parse. S-Expressions are easy to parse. On top of that you THEN need to parse Lisp.
• Alexander Torstling: @Rainer: Isn't that just nitpicking? In my world parsing means going from text to an AST, which says nothing about interpreting the commands.
• Rainer Joswig: In C++ the parser will detect a syntactically wrong function declaration. In Lisp not. The reader does not know anything about the programming language Lisp. The C++ parser knows the full C++ syntax. The Lisp reader does only know s-expressions.
• Alexander Torstling: Ah, then I understand what you mean. True, although I still think a simple lisp evaluator would be simpler to construct than a simple c++ one. That's what they do in SICP, isn't it (been a while since I read it)?
• Rainer Joswig: the language used in SICP is very simple, not even full Scheme. An interpreter for a tiny C like language should also be simple. C++ is large. Some of its difficulty comes from a relatively high number of built-in syntax. In a typical Lisp system much of the syntax is built with macros - outside of the interpreter. Macros implement syntax and an extension mechanism for source transformations. This keeps the core smaller. But the macros can be massive. For example the implementation for the LOOP construct has more than 2000 lines of complex macro code.

Answer 5

I'm not sure it is really important for everyone. You can be a successful developer without knowing how a Lisp interpreter works. When studying Computer Science, the basic ideas of Lisp should be learned though.

Lisp interpreters are important for Lisp programmers. They need to understand how an Interpreter ([and compiler]1) works, to fully understand how to use the language.

A Lisp interpreter is often used as a tool in computer science to teach students a few things:

• understanding a compact and minimal language definition through an implementation: Alan Kay called it the Maxwell’s Equations of Software.

• understanding language-level programming, by changing and extending the interpreter

• understanding meta-level programming and the effects it has on the design and usage of a programming language. For example understanding what 'quoting' means and why it is necessary

• understanding the interpretation of the programming language Lisp and its connection to the Lambda Calculus

As a teaching device, a Lisp interpreter is helpful, because it can be learned and understood in small time. Since few students already know about Lisp, the students are on a level field when it comes to learning above concepts.

Answer 6

A Lisp interpreter written in Lisp can be given as a weekly or even overnight homework assignment. Whereas making a from-scratch interpreted language would be more of a semester project.

A Lisp interpreter written in Lisp can have working, albeit poorly optimized lexical environments, including correctly working lexical closures, with hardly any difficulty. Moreover, these features are specifically not borrowed from the hosting Lisp, so the exercise conveys an understanding of how they work (at least in one particular reference model, as implemented in the interpreter).

There is absolutely nothing to do in a Lisp-in-Lisp interpreter but to implement the task of interpretation. It's a software engineering ideal: you have a requirement X, and you write a piece of code which is entirely concerned with requirement X, and no other requirement. All the necessary representations are already there: the notation for the program is already parsed, and the language has a library of code to manipulate the parsed representation, plus easy data structures for implementing environments: assoc lists, which behave in exactly the right ways for extending a scope and capturing it in a closure.

Imagine if someone said, "there is new requirement: make the system distributed over multiple machines, and secure", and imagine you could just add two small functions to it: distribute() and secure() and be done! That's what it's like to write a Lisp-in-Lisp interpreter. Thus, of course instructors like it.

Answer 7

The exercise in question is a self-interpreter (or meta-circular evaluator) - an interpreter which is powerful enough to execute its own source code.

The point of the self-interpreter is to examine how code execution is conceptually simple and can be built on just a handfull of primitive operations. A Scheme implementation written in Python will not show you that, since it still depends on Python (or at least a subset of Python) which is itself more complex than the Scheme implementation! But a language implemented "in itself" will let you examine what is the simplest possible implementation and smallest set of necessary primitives which is still able to execute itself (which means it can be extended to execute anything else also).

So a self-interpreter can be written in any Turing-complete language. But Lisp is just a really simple language which means a self-interpreter in Lisp can be made as a relatively simple exercise. (To be fair, some even more minimalist languages exist (like FORTH or the notorious Brainfuck), but Lisp strike a good balance between being very simple and still quite readable (as long as you can get used to the parentheses)).

I'm sure you would learn just as much (perhaps a lot more) from writing a Java interpreter in Java or a C++ interpreter in C++. But such a project would be huge. Just parsing Java code (never mind C++ code) will lead you down the rabbit hole of regular expression, context-free grammars, and parsing algorithms, which is a whole separate subject in the CS curriculum. Then you get to the AST which would be a very complex structure given the many different syntax elements of the language. Then type-checking which again is a whole subject on its own. And so on.

In contrast, a self-evaluator in Lisp is one page of code in a textbook. In particular the very simple syntax of Lisp avoids a lot of the accidental complexity in other language implementations.

Whether developing such a self-evaluator is a big revelation for you probably depend on your background. If you have have already implemented multiple interpreters or compiler, it might be less impressive, but it is still pretty neat to see how simple it can be.