Hacker News Reader

Comment by sph | Hacker News Reader

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?

View on HN

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

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/

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.

I think a standard (Euclidean) list is:

  Quote
  Atom
  Eq

  Car
  Cdr
  Cons

  Cond

  Lambda
  Label

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

Reply on news.ycombinator.com