Why is it easy to implement a Lisp? | Hacker News Reader

Why is it easy to implement a Lisp?

eli.thegreenplace.net

19 pointsTomte10 comments

Open articleView on HN

[speaking broadly about any "easy Lisp" type projects]

- Because you've not created anything even remotely for production use

- Because you're getting any/all of the following from a host language

. - garbage collection

. - I/O

. - numbers

. - exception handling

. - containers, objects, strings, regexes, unicode, ...

. - concurrency gizmos

. - even some syntax: is it your own code that scans and converts floating-point tokens?

- Perhaps you just made a parenthetical sugar that just reflects into the host language, with more or less its semantics (yes Lisp read syntax is easy-ish).

- The host language you're using was hacked on by many people over many years who produced tens of thousands of commits; all you have to do is call things in it.

- And/or, possibly:

. - your stuff segfaults when the program has a bug, like (+ "abc" 42).

. - pardon me, that was last week; I see it just quits now

. - you took shortcuts, like there will only be 100,000 conses in a static array.

. - you have not-so-accidental quadratic behavior all over the place.

. - you have almost no documentation about what you made, no test cases, and no significant amount of code.

. - you don't have a compiler.

. - ... that can compile files ahead of time into loadable object files, with fine-grained evaluation control

. - I see you have macro expander, but it has no environment parameter and is oblivious to lexical scopes.

. ...

Implementing a Lisp for real is years of hard work, and many hair-pulling moments.

I implemented a not-that-fancy Lisp in C in a few weeks. It did all its own number reading, precise GC, etc. It was embedded in a commercial product so it wasn't purely a toy. It was less sophisticated than Emacs Lisp. But Emacs Lisp itself was implemented in a matter of weeks or months (albeit by RMS, who is like ten normal good programmers). Lisp is really pretty simple, though of course adding enough to it will be a lot of work. Mine (and Emacs's) didn't have most of the stuff you listed, but that was ok.

SICP explains how to write a fairly complete version of Scheme including a compiler.

My Lisp in C had a bunch of its higher level parts like the reader implemented in C for accidental reasons because of why the program was developed in the first place. If doing it again though, the whole thing would be in Lisp except for some very low level primitives.

What's "quadratic behavior"?

Run time is O(n^2) in input size n.

Quadratic behavior is O(n^2) like bubblesort - triple the number of items to sort, and it takes 9x the time.

Really, the comment was referring to "accidentally quadratic" bugs, as documented here, for example: https://accidentallyquadratic.tumblr.com/

> Implementing a Lisp for real is years of hard work, and many hair-pulling moments.

I think this can be said about any language that came after people stopped programming directly in assembly language.

Even the low-level languages like C are programmed in themselves (mostly) after the first run of bootstrapping compilers written before most of us were even born.

One could knock out a simple C compiler, without a standard library, in not too long I suspect (and have seen examples of) but why bother if all you want to do is learn the fundamentals and there’s a simpler language you could tackle — one with many, many guides on how to make a simple one I might add.

Now I’m wondering if someone made a lisp in native wasm…

Yep you are absolutely right. It takes many years to make a high quality and performant Lisp implementation. The same way you can quickly throw together a C interpreter but it takes many years to make anything that can compete with gcc or clang.

Try writing a version of ruby or python or rust that lets you just write something meaningful that _evaluates_. Let alone the list of stuff you mentioned above. It’s far harder than for lisp.

Why is it easy to implement any toy language that is buggy, not standards compliant and slow? Well that should be kinda obvious right? It takes 10+ years to make high quality implementations of Lisp that can compete with the best out there. Same with most (all?) other languages. With the exception of Forth maybe?

Well all you really need to do is push your tongue forwards on "s" sibilants to make it more like a "th" sibilant, so it's pretty easy to do.

The trick is learning not to do it after dental surgery.

Reply on news.ycombinator.com