Ask HN: What does a developer need to know to build their own Lisp from scratch?

Why is Lisp/Scheme a good candidate for something to implement oneself? Because it has hardly any syntax, so writing the parser is relatively easy compared to writing the parser for other languages.

> What's at the heart of Lisp that makes it so simple and elegant?

In terms of implementing it, probably the Cons Cell. The insight being that the heart of Lisp is pairs, not lists:

https://www.gnu.org/software/emacs/manual/html_node/elisp/Co...

https://cs.gmu.edu/~sean/lisp/cons/

the classic introduction to building a lisp (interpreter) in different programming languages is:

https://github.com/kanaka/mal

Not much really; I would recommend working through SICP [0], it is fun and in the end you know a lot and can move on from there to even more advanced topics.

Together with the YouTube recordings of the lectures about the book will give you many AHA moments about why it’s so elegant etc.

Including topics like types and a prolog like logic language.

[0] https://en.m.wikipedia.org/wiki/Structure_and_Interpretation...

If by "lisp from scratch" you mean an s-expression interpreter that can run programs like recursive exponentiation or recursive fibonnaci, very little. You can do that in a low few hundred lines of code.

If you mean for the full power of a lisp then you still have to pick: for Scheme that might be call-with-cc and hygienic macros. For Common Lisp that might be regular macros and reader macros. Those take more code and thought.

I have experimented with several lisp-like environments. Parsing s-exprs is simple. The choice of primitives, i.e. built-in functions which differ from those in Common Lisp or Scheme, can lead to interesting behavioral dynamics.

I have tended to implement more complex core data structures than cons-cells. E.g native strings, maps and arrays.

Suggest looking at newLisp and picoLisp for ideas on how non-traditional Lisps have been implemented.

http://www.norvig.com/lispy.html Plug: https://github.com/ravish0007/geekskool/blob/main/assignment... (still broken)

There's a book for just that.

The title is "Build Your Own Lisp" and it is free to read [0].

You learn C and build your own Lisp dialect.

[0]: https://buildyourownlisp.com/

Look into “Make a Lisp” (MAL). Language agnostic step by step instructions for writing a fully featured interpreter, including tail recursion and reader macro support. Plus, examples in every language. It’s on github.

This isn't a traditional approach, but you might consider using a JSON parser in your favorite language and then implementing `eval` and `apply` over that data structure [0]. It saves you from dealing with the mundane lexer/parser stuff and lets you dive straight into an actual interpreter:

    ["define", ["factorial", "n"],
        ["if", ["=", "n", 0], 1,
             ["*", "n", ["factorial", ["-", "n", 1]]]]]

    ["display", ["factorial", 10]]

Here, JSON strings are symbols (identifiers). In a language like Python or JavaScript, you wouldn't even need to use the JSON parser. Just skip straight to doing eval and apply over the list/Array, and you can use dict/Object as your environment to hold definitions. You could be up and running in a few hours, and I think that would feel satisfying.

Then again, maybe that's too ugly to consider. :-)

In addition to some of the other book and web site recommendations people have made (SICP, MaL, etc...), I think "Lisp in Small Pieces" by Christian Queinnec is really good if you want to take it further.

[0] https://wiki.c2.com/?EvalApply

    [\s,]*(~@|[\[\]{}()'`~^@]|"(?:\\.|[^\\"])*"?|;.*|[^\s\[\]{}('"`,;)]*)

> What's at the heart of lisp that makes it so simple and elegant?

IMO, it's a synergy of several things. Trivial parsing*, homoiconicity, automatic memory management, dynamic types, first class symbols, first class everything†, extensible everything†, heavy reliance on anonymous functions, flexible scope rules.

All of those have since been adopted by other languages, but only Lisps have them all working together. (And not every Lisp has every feature.)

* ... until you consider various extensions

† almost

At the simplest:

1. Parse and produce S-Expresseions ("read" and "print").

2. Use the object system of the implementation language as much as possible. If necessary, implement some lisp-specific types like the cons pair, empty list, symbol. First get it to work correctly, you can optimise later.

3. Implement all the "special forms" which can't be implemented using macros in the implementation language.

4. Implement any library functions that can't be implemented in lisp itself using the implementation language.

5. Implement "eval" (evaluates S-Expresseions). Now you've got a working interpreter.

6. Use your interpreter to evaluate macros. Use that to implement any additional "special forms".

7. Write any additional library functions in your own lisp.

That's it, at this point you have a working lisp implementation. There are many opportunities for optimisation, from lambda lifting and continuation passing style to hygienic macros and even just in time compilation.

Happy Hacking!

scheme is kindof the fix point of sequential programming languages

it eats itself into constancy

University of Maryland's compilers class has the lectures/notes online. The course is about implementing a reduced (but still pretty big) subset of Racket. https://www.cs.umd.edu/class/spring2022/cmsc430/Notes.html.

Pyramid[1] was based on the last chapter of SICP, was executable after a couple weeks, and I had never written any lisp before(outside of a couple hours playing with Scheme once).

Most of that time was the code generator. An interpreter is much simpler and you could have something similar in a couple hours. Especially if you use a JSON parser to start, and switch to S-expressions once you get everything working. Or use an existing Lisp with a (read) primitive that knows the syntax.

As for "why Lisp?", it's a bit like how you never need to read the JSON spec to write JSON in practice, because they unified the syntax into a few core datatypes(primitives, arrays, objects). Besides the simple syntax, they also include a symbol table core concept that tells you how to interpret the minimal syntax.

In most languages, it's a lot of work adding a new feature to the language: Lexer to recognize token, backtracking parser, adding a new internal type, etc. In a Lisp interpreter, you just edit the symbol table to know about a new form and you're done.

Despite the core being simple, a practical Lisp environment is going to have thousands of primitives with a variety of effects on the runtime, and you'll need to look them up. Racket has about 1700[2] implemented in Chez Scheme, for example. But at least they're "only primitives", so there's uniformity in how they're used. Nothing like "What's the syntax for an anonymous function that takes 1 callback as argument that captures a local by reference and 3 other variables by value?"

[1] https://www.michaelburge.us/2017/11/28/write-your-next-ether...

[2] https://github.com/racket/racket/blob/master/racket/src/cs/p...

Here's how I did it, I would say it's solid, approachable, and enjoyable:

Go through the first half of Crafting Interpreters [0]. And then try to complete mal - Make a Lisp [1]. That's it. You'll only need these two.

P.S. People also say good things about Build Your Own Lisp [2], but I didn't finish it because I find spending quite some time writing C doesn't make me feel I'm enjoying something elegant.

[0]: https://craftinginterpreters.com/ [1]: https://github.com/kanaka/mal [2]: https://buildyourownlisp.com/

See how to fit a Lisp system into a boot sector of a floppy disk:

https://justine.lol/sectorlisp2/

See also 'LISP from Nothing', a Nils Holm book:

https://www.t3x.org/lfn/index.html

lisp

People who don't have a solid couple of years working in Lisp invariably do a cargo-culted botch job of implementing it.

You see issues in their code like confusing the concept of "atom" and "symbol", or symbols just being strings, evaluation level confusions and things of that nature.

There is more than one elegance in Lisp; what people find elegant is subjective. Some people are charmed by a meta-circular interpreter. Some are charmed by interned symbols: two symbols are equal or not based on just some machine word comparison. Some are charmed by the way lists are made of garbage-collected pairs so you can endlessly rearrange lists like pouring water from one container to another, without having to worry about the storage allocation. Some are charmed by being able to quote any part of a program to turn it into a data literal.

None of these things are exactly simple under the hood.

Many elegant aspects in a mdoern Lisp woudn't have been found in the classic Lisp 1 or 1.5. I think it's elegant that a type error (or any other) results in an exception that can be handled. I think unwinding a stack is elegant. Structural pattern matching is elegant. Bignum integers are elegant. File compilation with fine-grained evaluation control is elegant.

Elegant is about UX, and elegance can come off as simplicity (especially if we examine just one area at a time rather than the integrated whole); but underneath the UX there is a lot of huffing and puffing under the hood.

Code is data.

LISP builds upon a very simple, yet powerful data structure (pairs that can be arranged into binary trees) that has a direct correspondence with its syntax. This means that it is very simple to write a very basic LISP interpreter in almost any programming language, and to use it to bootstrap a more fully-featured one. It's even quite feasible to write one in assembly language, and the very first ones indeed have been implemented that way.

I recommend Dmitry Soshnikov's video tutorials _Building an Interpreter from scratch_ [0]

[0] https://www.dmitrysoshnikov.education/p/essentials-of-interp...

Start by dealing (or not) with "dotted pair" notation up front. eg (a . b) (a b . c) etc.

This confronts a whole bunch of issues directly and immediately. What is a list, really? How do I handle recursion in my parsing--implementation language (fast--but maybe not tail recursive and weak to cycles) or lisp (slower--but probably infinite and handles circular lists)? How do I deal with garbage (long parses kick up a lot of garbage)?

Dealing with dotted pairs is the difference that means you understand implementing lisp rather than are just toying with it.

If you read SICP you are good to go (mitpress.edu/sicp). Or you can read the code of an existing implementation

take a look at my scheme to c compiler written in Common Lisp for reference. I implemented a parser. https://github.com/Jobhdez/scheme-to-c