[sago]

Writing your own Lisp-ette is a brilliant evening or weekend project, regardless of the language. It's some of the simplest non-toy parsing you can attempt, a bit of light data structure work, and understanding eval/apply is 80% of the work in implementing it. I would highly recommend anyone to have a go, and try not to follow existing code too closely: figure out the problems in your language of choice.

The post identifies some of it's own weaknesses (memory handling, errors), which are quite C specific. Or at least easier to handle in other languages, where you can punt those issues to the host language runtime. But it will be a fun extension to fix them (a job for the second evening / weekend of coding ;) )

But, imho, the beauty of writing a Lisp is that there are a bunch of things you can do from there, some more difficult, but several are achievable step-by-step in a day or a few days each. I'd first add a few special forms more than the OP (quote, if, progn, math operations), then my suggestions:

1. Defining names (if you haven't already), both let and define special forms.

2. Lambdas.

3. Tail call optimisation (I suggest this not because it's an optimisation, this Lisp doesn't need optimising, but because TCO is a bite-sized extension.)

4. Lexical scoping of lambdas.

5. Continuations. call/cc

6. And if you're really brave (or skilled, or just masochistic), macros.

I was encouraged to do this as a new grad student, and it was one of the most fun and educational experiences I remember. I didn't get as far as macros back then, but implementing call/cc was a definite pivot point in my programming competence.

[ioddly]

> Writing your own Lisp-ette is a brilliant evening or weekend project, regardless of the language.

Just be careful about scope creep. I started one as a weekend project five years ago and I'm still not finished ;)

[DonaldFisk]

I found none of these particularly difficult. (I've never attempted 3. or 5. though.) Functional values, however, are difficult. They work effortlessly in interpreted code, but in compiled code you're faced with the upwards funarg problem: https://en.wikipedia.org/wiki/Funarg_problem#Upwards_funarg_...

A solution is needed if you want lazy evaluation.

[chrisseaton]

> They work effortlessly in interpreted code, but in compiled code you're faced with the upwards funarg problem

No it's not about interpreted or compiled. It's about using the native stack or a heap for stack frames. Compiled code and interpreters can both use either, so that's orthogonal.

[DonaldFisk]

Yes, to solve the upwards funarg problem you can't rely on a single stack. The problem is that using the heap for everything instead comes with a heavy computational cost, and using the heap only when you need it means you need to identify those circumstances, which isn't trivial.

[sago]

How did you do lambdas and lexical scoping without 'functional values'?

[DonaldFisk]

That's explained in https://en.wikipedia.org/wiki/Funarg_problem#Downwards_funar...

In addition to return address and dynamic link, you need to store a static link in each stack frame.

[theoh]

Presumably by implementing only the simpler "downwards" funargs: the ability to pass functions into a function scope but never return them.

[aarongolliver]

5 is do-able by an undergrad, though the first time you encounter the concept it can be difficult to grapple how you would implement it.

[roywiggins]

Another fun one is a Forth interpreter. I tried to make one in Rust once, I can't say I actually succeeded but it's fun to tinker with. It is simple enough that you can probably write a bad one in assembly without that much assembly knowledge.

[geon]

Or Brainfuck. It's fun and only takes half an hour or so.

[smcl]

Not sure why you're downvoted (people don't like swear words?). As a "my first interpreter" project Brainfuck is really quick, fun and could motivate you to explore the topic further.

[kovrik]

Agree.

I'm writing Scheme R5RS in Kotlin (https://github.com/kovrik/scheme-in-kotlin) and have implemented everything except macros (6).

Have no idea how to beat them.

[_sdegutis]

Just think of them as defining functions that take s expressions in and spit s expressions out before “normal” runtime evaluation and which hence only see built in symbols.

[kovrik]

Yes, I get that (in general).

But then there are things like hygiene, performance and some tricky edge-cases.

And I couldn't find any standard (and simple) algorithm to implement macros (preferably written in something other than Scheme itself).

Still trying to wrap my head around.

[UncleEntity]

"This paper describes a modified form of Kohlbecker’s algo- rithm for reliably hygienic (capture-free) macro expansion in block-structured languages, where macros are source-to- source transformations specified using a high-level pattern language."

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.464...

[quotemstr]

Lexical scoping is essential if you want to use the Lisp for anything essential. If you start with dynamic scope for everything and the system develops any real complexity, then switching to lexical scoping becomes very painful. Best to do it right the first time.

[reacweb]

7 typing and Hindley-Milner inference

[tree_of_item]

If you go with (hygenic) fexprs instead of macros, they're both easier to implement and more expressive, at the expense of performance.

Check out John Shutt's thesis for more information on hygenic fexprs: https://web.wpi.edu/Pubs/ETD/Available/etd-090110-124904/unr...

[sparkie]

Here's a small implementation of Kernel in around 700 lines of Haskell [https://github.com/vito/hummus/tree/master/src/Hummus]. Note that it's not Kernel proper, as it uses delimited continuations instead of the guarded undelimited continuations in the Kernel report, plus there's a few other differences and some bugs.

Anyone looking for a more complete implementation, check out klisp [http://klisp.org]. It's not 100%, but has some stuff not included in the Kernel report, some of it lifted from R6RS. The main thing it's missing which it desperately needs is an FFI.

[radarsat1]

On the subject of Haskell, what's the shortest Haskell (possibly Haskell subset) interpreter anyone has written?

[sago]

Thanks for the tip. If it wasn't the end of the weekend, I'd be tempted to break out emacs.