Roll a Lisp in C – Evaluation(swatson555.github.io)
swatson555.github.io
Roll a Lisp in C – Evaluation
https://swatson555.github.io/posts/2022-05-06-make-a-lisp-2.html
35 comments
Nice work, writing a hobby lisp in C is great for building understanding. Here was my take: https://gist.github.com/cellularmitosis/d8d4034c82b0ef817913...
It looks like you did pass-by-reference on all parameters. The interpreter I wrote for the articles does pass-by-value on all parameters which has it's own quirks compared to conventional Lisps.
[deleted]
If you want to go even more minimalist then roll your own pure lambda calculus evaluator and figure out how to do if-then-else and math in it. It is good fun!
What language constructs should a (Turing complete) Lisp have to be considered one? Is there a spec somewhere, a minimal conformance guide? I don’t think it’s just the parens that make the Lisp.
I suppose it needs:
* car and cdr
* if
* list
* eval
* quoting and quasiquoting
What else?
I suppose it needs:
* car and cdr
* if
* list
* eval
* quoting and quasiquoting
What else?
Lambda is enough to get to Turing completeness (ta, Y-Combinator!). However, Scheme is a well-specified Lisp [0], which has few necessary elements that everything builds on top of. Common Lisp is also well-specified [1], though the hyperspec is a lot more painful to explore.
A lot of people mean Common Lisp when they say "Lisp".
One of the dividing lines of most Lisps, is whether they fall into Lisp-1, or Lisp-2 [2]. That is, do functions and variables share a namespace or not. Common Lisp is a Lisp-2, whereas Scheme is a Lisp-1.
[0] https://www.gnu.org/software/mit-scheme/documentation/stable...
[1] http://www.lispworks.com/documentation/lw50/CLHS/Front/index...
[2] https://en.wikipedia.org/wiki/Common_Lisp#The_function_names...
A lot of people mean Common Lisp when they say "Lisp".
One of the dividing lines of most Lisps, is whether they fall into Lisp-1, or Lisp-2 [2]. That is, do functions and variables share a namespace or not. Common Lisp is a Lisp-2, whereas Scheme is a Lisp-1.
[0] https://www.gnu.org/software/mit-scheme/documentation/stable...
[1] http://www.lispworks.com/documentation/lw50/CLHS/Front/index...
[2] https://en.wikipedia.org/wiki/Common_Lisp#The_function_names...
Quasiquoting is easily done in LISP, but you will need ATOM, and I would argue for CONS in the place of LIST. Exposing EVAL is not necessary at all. See http://t3x.org/klisp/22/
One of the most important Lisp primitives is lambda, which provides higher-order functions. It is a fundamental primitive, and the name lambda is derived from the lambda calculus which influenced the design of Lisp.
Matt Might has a pretty good article[0] on the subject (actually has a bunch of good articles if you poke around on his site) where he discusses this.
[0] https://matt.might.net/articles/compiling-up-to-lambda-calcu...
—edit—
This article has a good example in the ‘core language’ section -> https://matt.might.net/articles/desugaring-scheme/
[0] https://matt.might.net/articles/compiling-up-to-lambda-calcu...
—edit—
This article has a good example in the ‘core language’ section -> https://matt.might.net/articles/desugaring-scheme/
I wrote an interpreter on a whim a long time ago. Mainly to show a friend how quick it was to get something going. I continued working on it, had great fun. Until I got to quasiquoting. That's where my head started spinning and I lost steam.
Why would it be hard to implement? (Keep in mind I have never written a lisp so my comment is uneducated)
Quasiquoting means creating a list where some elements are evaluated at runtime. Not dissimilar to string interpolation.
Quasiquoting means creating a list where some elements are evaluated at runtime. Not dissimilar to string interpolation.
> Quasiquoting means creating a list where some elements are evaluated at runtime
Take a look at the awesome 'Make A Lisp' (MAL), in particular the section on quoting:
https://github.com/kanaka/mal/blob/master/process/guide.md#s...
This has a fairly good description of what happens during quasi-quoting.
Take a look at the awesome 'Make A Lisp' (MAL), in particular the section on quoting:
https://github.com/kanaka/mal/blob/master/process/guide.md#s...
This has a fairly good description of what happens during quasi-quoting.
I don't recommend this; it is pretty awful, and mostly particular to the internal structure and conventions of its respective project.
The actual Lisp information sources, which are numerous, cover this ground more than adequately; there is no need to turn to the internal documentation of a polyglot mock Lisp.
The actual Lisp information sources, which are numerous, cover this ground more than adequately; there is no need to turn to the internal documentation of a polyglot mock Lisp.
> there is no need to turn to the internal documentation of a polyglot mock Lisp
Well, unless you want to be able to say "I have built a self-hosting Lisp from scratch, and I understand what it is doing". Including eval, quoting and tail recursion.
Getting my C# implementation of MAL to interpret itself was one of the most compelling learning experiences in my recent programming history.
Well, unless you want to be able to say "I have built a self-hosting Lisp from scratch, and I understand what it is doing". Including eval, quoting and tail recursion.
Getting my C# implementation of MAL to interpret itself was one of the most compelling learning experiences in my recent programming history.
That's just how I remember how it went. Up until then, everything just flowed without any big problems.
I think a standard (Euclidean) list is:
Quote
Atom
Eq
Car
Cdr
Cons
Cond
Lambda
Label- A tracing garbage collector
- Tail call optimization
- Closures
- Tail call optimization
- Closures
TCO is not really that important. The Common Lisp standard doesn't even require it, though many implementations do support it.
[deleted]
More posts like this, please.
There is lots of stuff like this on my homepage, http://t3x.org.
I brought Lisp System Implementation a few weeks ago. While its pretty good, I did have one feedback: it would be great to have a book that shows making a Lisp step-by-step, rather than documenting the final version. I know a few people who are interested in learning how to write compilers, and would prefer something like that (LSI would be too hard for them, since it would require reading a large portion of the book to even gain some basic context of why we are doing what we are doing).
> it would be great to have a book that shows making a Lisp step-by-step
Excellent point! Compiling Lambda Calculus is a bit like this. It starts with Lambda Calculus and then develops multiple implementations of increasing complexity. LISP from Nothing also does this, but it is about ancient LISP.
I will definitely keep this in mind!
Excellent point! Compiling Lambda Calculus is a bit like this. It starts with Lambda Calculus and then develops multiple implementations of increasing complexity. LISP from Nothing also does this, but it is about ancient LISP.
I will definitely keep this in mind!
I've purchased Lisp System Implementation and it was very good. Thank you!
Thank you!
Oh wow, what a treasure trove! Which title would you recommend a LISP newbie should start with? Is there a sequence for the first few titles you would recommend?
If you are really new to LISP, I would recommend Sketchy Scheme, then Scheme 9 from Empty Space, then LISP System Implementation. You can read LISP from Nothing after Sketchy Scheme, but it is more about the technical history of LISP.
If you are into Theory, read Compiling Lambda Calculus instead of S9fES. Then there are some essays and interpreters that you can study with little background.
What is your opinion on the Mahayana?
It is the teacher that matters, not the school.
In pure land there is no need for a teacher
In pure land there is no need for anything. Until then a teacher may be useful.
What do you mean by this? There is still the need to do the nembutsu
I was talking about the goal, you about the path. As long as there is a path, there needs to be a teacher, which can be a formal teacher, a member of your community, or yourself. In the end it is always yourself, of course, and the teaching is always the same, be it Mahayana, Theravada, Hinduism, Yoga, or something else entirely. It does not matter which school you belong to, but the teaching needs to be understood clearly. As long as there is a path, how do you do nembutsu without inspiration?
You might like my Lisp compiler series in C: https://bernsteinbear.com/blog/compiling-a-lisp-0/
Nice. This is the perfect level for teaching/examples for a level 6
languages module. Thanks for writing and sharing this.