Roll A Lisp In C – Reading (2020)

Re:Roll A Lisp In C – Reading (2020) by ggliv on Sunday May 12, 2024 @09:32AM (#40334310)

While probably a bit overkill for writing a Lisp, Robert Nystrom’s Crafting Interpreters [0] is a really fantastic book on the topic.

[0] https://craftinginterpreters.com/contents.html

[ Parent | on HN ]

Re:Roll A Lisp In C – Reading (2020) by Zambyte on Sunday May 12, 2024 @09:32AM (#40334314)

https://sicp.sourceacademy.org/chapters/4.html

This inlines the diffs between the original SICP and the new one that is implemented in Javascript too.

[ Parent | on HN ]

Re:Roll A Lisp In C – Reading (2020) by jetti on Sunday May 12, 2024 @09:33AM (#40334320)

I’m not really sure how you would be able to write an interpreter without a parser, since you need to know what the user is trying to do. For a more complete tutorial there is Make-A-Lisp (mal) [0] that has steps for making a lisp in various (including JavaScript) and has a process guide [1] to get started.

[0] https://github.com/kanaka/mal

[1] https://github.com/kanaka/mal/blob/master/process/guide.md

[ Parent | on HN ]

Re:Roll A Lisp In C – Reading (2020) by KineticLensman on Sunday May 12, 2024 @09:47AM (#40334436)

I can second Make-A-Lisp. I worked through it in C# initially, and I'm now halfway through a Rust implementation. The MAL process guide is a good set of instructions but doesn't go as far as actually presenting pseudocode, so you do have to think, and sometimes 'cheat' by looking at one of the reference implementations. In terms of tokenising and parsing, the MAL guide does include a monster regex statement that recognises the relevant tokens, and the parsing is quite easy due to Lisp's relatively simple syntax. If you choose the right implementation language, it will do some of the heavy lifting for you (notably memory management).

[Edit] Just wanted to reiterate that lexing/parsing Lisp is easy as per the MAL instructions. IIRC the things that I found hardest (in C#, as a C# newby) were understanding how to implement the closures required to support function definition, and then implementing Lisp's macro expansion.

[ Parent | on HN ]

Re:Roll A Lisp In C – Reading (2020) by naasking on Sunday May 12, 2024 @10:41AM (#40334845)

You can create an interpreter in the finally tagless style:

https://okmij.org/ftp/tagless-final/

This embeds the target language as combinators in a host language, so you can construct and evaluate programs.

[ Parent | on HN ]

Re:Roll A Lisp In C – Reading (2020) by jetti on Sunday May 12, 2024 @12:29PM (#40335648)

I have not heard of tagless final style interpreter before and that seems really neat. However, based on the link it seems that tagless final interpreter uses a strong type language like Haskell or ML so I don’t know how well it would translate to Javascript, which is what the GP comment said they were using.

[ Parent | on HN ]

Re:Roll A Lisp In C – Reading (2020) by naasking on Sunday May 12, 2024 @12:42PM (#40335746)

I've done them in C# with slightly less safety.

https://higherlogics.blogspot.com/search/label/tagless%20int...

The style of the construction is what matters most. If you're using JS then you're already giving up types, but the higher order abstract syntax is what lets you embed and play with language semantics.

[ Parent | on HN ]

Re:Roll A Lisp In C – Reading (2020) by jetti on Sunday May 12, 2024 @01:22PM (#40336017)

I think I may have misunderstood what your original comment was referring to. Were you saying that one doesn’t need a parser to make a working interpreter? I want to make sure that I understand the context of your comments because looking at the post you linked where you did this in C# you show you are using a recursive descent parser. It was when I saw the parser that I realized I could be way off base on what I was thinking you were talking about.

[ Parent | on HN ]

Re:Roll A Lisp In C – Reading (2020) by naasking on Sunday May 12, 2024 @02:45PM (#40336530)

Yes, it doesn't need a parser. I didn't link to one post, it's a tag that links a series of posts discussing tagless interpreters. You can use the interpreter in the first post directly without the parser as well, it's a separate component. IQueryLanguage<T> is the interpreter definition.

[ Parent | on HN ]

Re:Roll A Lisp In C – Reading (2020) by naasking on Monday May 13, 2024 @12:57AM (#40339913)

I should note that the other posts go into more of the theory and background of final tagless encodings, including links to Oleg's site who has done a lot of work on them. They are a very flexible for implementing embedded languages.

[ Parent | on HN ]

Re:Roll A Lisp In C – Reading (2020) by mtreis86 on Sunday May 12, 2024 @09:31AM (#40334306)

Many are based on the SICP metacircular evaluator. Write that in your language of choice then you can bootstrap into scheme from there. Also see the 1986 MIT lecture videos by the authors, to get the spirit of the thing.

[ Parent | on HN ]

Re:Roll A Lisp In C – Reading (2020) by mikelevins on Sunday May 12, 2024 @11:23AM (#40335191)

The first time I attempted a Lisp back in about 1989 or something, I used the metacircular evaluator from SICP.

A little later I used Norvig's Scheme implementation from chapters 22 and 23 of PAIP (https://norvig.github.io/paip-lisp/#/?id=paradigms-of-artifi...).

I liked Norvig's a little better. It starts with a simple interpreter and adds improvements step-by-step, winding up with an optimizing compiler that targets a bytecode VM.

That approach makes a lot of implementation details manifest in a way that is easy to grasp. For example, I think I understood continuations much better after seeing Norvig's account of how to implement them.

[ Parent | on HN ]

Re:Roll A Lisp In C – Reading (2020) by fmbb on Sunday May 12, 2024 @10:16AM (#40334678)

Check out miniMAL from the person behind Make a Lisp. It’s exactly what you want, I think: http://kanaka.github.io/miniMAL/

[ Parent | on HN ]

Re:Roll A Lisp In C – Reading (2020) by im3w1l on Sunday May 12, 2024 @10:21AM (#40334701)

Here's some pseudocode that should help you get started on a very simple thing

  evalExpression:
    switch peekChar
      ( evalFunctionCall
      0-9 parseNumber
      " parseString
      a-zA-Z parseAndGetVariable

  evalFunctionCall
     fn = evalExpression
     arguments = evalExpression  until )
     fn(arguments)

[ Parent | on HN ]

Re:Roll A Lisp In C – Reading (2020) by matheusmoreira on Sunday May 12, 2024 @10:36AM (#40334801)

Seconding the Make-A-Lisp and Crafting Interpreters recommendations. TFA is also pretty good, it contains a hard written parser that you may learn from. Lisp grammar is regarded as simple enough that full parser generators need not be used.

There are also the Lis.py articles which are incredibly good:

https://norvig.com/lispy.html

https://norvig.com/lispy2.html

You mentioned you want to write your lisp in javascript so you'll be getting quite a lot of functionality for free: memory allocation and garbage collection. That alone solves an enormous amount of problems. Just in case anyone reading is going to write in C, here's an excellent introduction to the topic:

https://journal.stuffwithstuff.com/2013/12/08/babys-first-ga...

Don't forget to spill the registers.

[ Parent | on HN ]