5 ms·

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 b

by sago 9y ago

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.

quotemstr 9y ago
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.
tree_of_item 9y ago
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/unrestricted/jshutt.pdf https://web.wpi.edu/Pubs/ETD/Available/etd-090110-124904/unr...
- sago 9y ago
  Thanks for the tip. If it wasn't the end of the weekend, I'd be tempted to break out emacs.
- sparkie 9y ago
  Here's a small implementation of Kernel in around 700 lines of Haskell [https://github.com/vito/hummus/tree/master/src/Hummus 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 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 9y ago
    On the subject of Haskell, what's the shortest Haskell (possibly Haskell subset) interpreter anyone has written?
DonaldFisk 9y ago
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_problem https://en.wikipedia.org/wiki/Funarg_problem#Upwards_funarg_... A solution is needed if you want lazy evaluation.
- sago 9y ago
  How did you do lambdas and lexical scoping without 'functional values'?
  - theoh 9y ago
    Presumably by implementing only the simpler "downwards" funargs: the ability to pass functions into a function scope but never return them.
  - DonaldFisk 9y ago
    That's explained in https://en.wikipedia.org/wiki/Funarg_problem#Downwards_funarg_problem 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.
- aarongolliver 9y ago
  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.
- chrisseaton 9y ago
  > 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.
  - 9y ago
roywiggins 9y ago
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 9y ago
  Or Brainfuck. It's fun and only takes half an hour or so.
  - smcl 9y ago
    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.
ioddly 9y ago
> 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 ;)
kovrik 9y ago
Agree. I'm writing Scheme R5RS in Kotlin (https://github.com/kovrik/scheme-in-kotlin https://github.com/kovrik/scheme-in-kotlin) and have implemented everything except macros (6). Have no idea how to beat them.
- _sdegutis 9y ago
  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 9y ago
    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 9y ago
      "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.1336&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.464...
reacweb 9y ago
7 typing and Hindley-Milner inference

by sago 9y ago

quotemstr 9y ago

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.

tree_of_item 9y ago

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/unrestricted/jshutt.pdf https://web.wpi.edu/Pubs/ETD/Available/etd-090110-124904/unr...

sago 9y ago
Thanks for the tip. If it wasn't the end of the weekend, I'd be tempted to break out emacs.
sparkie 9y ago
Here's a small implementation of Kernel in around 700 lines of Haskell [https://github.com/vito/hummus/tree/master/src/Hummus 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 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 9y ago
  On the subject of Haskell, what's the shortest Haskell (possibly Haskell subset) interpreter anyone has written?

DonaldFisk 9y ago

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_problem https://en.wikipedia.org/wiki/Funarg_problem#Upwards_funarg_... A solution is needed if you want lazy evaluation.

sago 9y ago
How did you do lambdas and lexical scoping without 'functional values'?
- theoh 9y ago
  Presumably by implementing only the simpler "downwards" funargs: the ability to pass functions into a function scope but never return them.
- DonaldFisk 9y ago
  That's explained in https://en.wikipedia.org/wiki/Funarg_problem#Downwards_funarg_problem 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.
aarongolliver 9y ago
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.
chrisseaton 9y ago
> 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.
- 9y ago

roywiggins 9y ago

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 9y ago
Or Brainfuck. It's fun and only takes half an hour or so.
- smcl 9y ago
  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.

ioddly 9y ago

> 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 ;)

kovrik 9y ago

Agree. I'm writing Scheme R5RS in Kotlin (https://github.com/kovrik/scheme-in-kotlin https://github.com/kovrik/scheme-in-kotlin) and have implemented everything except macros (6). Have no idea how to beat them.

_sdegutis 9y ago
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 9y ago
  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 9y ago
    "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.1336&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.464...

reacweb 9y ago

7 typing and Hindley-Milner inference