4 ms·
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 j
by sph 5y ago
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?
- linguae 5y agoOne 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.
- nils-m-holm 5y agoQuasiquoting 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/ http://t3x.org/klisp/22/
- rags2riches 5y agoI 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.
- sph 5y agoWhy 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.
- KineticLensman 5y ago> 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#step-7-quoting https://github.com/kanaka/mal/blob/master/process/guide.md#s... This has a fairly good description of what happens during quasi-quoting.
- kazinator 5y agoI 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.
- KineticLensman 5y ago> 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.
- rags2riches 5y agoThat's just how I remember how it went. Up until then, everything just flowed without any big problems.
- shakna 5y agoLambda 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/mit-scheme-ref/R7RS.html https://www.gnu.org/software/mit-scheme/documentation/stable... [1] http://www.lispworks.com/documentation/lw50/CLHS/Front/index.htm http://www.lispworks.com/documentation/lw50/CLHS/Front/index... [2] https://en.wikipedia.org/wiki/Common_Lisp#The_function_namespace https://en.wikipedia.org/wiki/Common_Lisp#The_function_names...
- brennvin 5y ago- A tracing garbage collector - Tail call optimization - Closures
- deleted 5y ago[deleted]
- tsimionescu 5y agoTCO is not really that important. The Common Lisp standard doesn't even require it, though many implementations do support it.
- UncleEntity 5y agoMatt 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-calculus/ 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/ https://matt.might.net/articles/desugaring-scheme/
- MonkeyClub 5y agoI think a standard (Euclidean) list is: Quote Atom Eq Car Cdr Cons Cond Lambda Label