Roll a Lisp in C – Evaluation | Hacker News Reader

Roll a Lisp in C – Evaluation

swatson555.github.io

86 pointsswatson74133 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.

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?

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.

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/

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

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.

> 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.

That's just how I remember how it went. Up until then, everything just flowed without any big problems.

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 tracing garbage collector

- 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.

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/

I think a standard (Euclidean) list is:

  Quote
  Atom
  Eq

  Car
  Cdr
  Cons

  Cond

  Lambda
  Label