This article is chock-full of misinformation.<p>> an s-expression [is] a fancy term for a list of [cons] cells<p>No, it's not. An S-expression is a <i>serialization</i> of a (single) cons cell, whose elements might be other cells.<p>> We're using a vector instead [of cons cells], but the two are equivalent<p>No, they are not. When represented as cons cells, CDR is a non-consing O(1) operation. When represented as vectors, CDR is a copying O(n) operation (and because it necessarily makes a copy, the semantics are different if you introduce mutation).<p>The fact that S-expressions represent cons cells and NOT vectors is crucially important. It is the feature from which Lisp derives much of its power.<p>It is possible to make a Lisp-like language where the surface syntax represents vectors instead of cons cells. In fact, this makes a useful exercise. If you undertake this exercise you will come to know the answer to the question: why has this idea (a vector-based Lisp) not gained more wide-spread adoption?<p>> There are three different sorts of data structure that we have so far: Strings. S-expressions, and Cells<p>As above, S-expressions are not a data type, they are a serialization of cons cells, i.e. they are a <i>mapping</i> between cons cells and strings, and this mapping has a very particular feature from which much of Lisp's power is derived, which is that it compresses a linked list of cons cells into this:<p>(1 2 3 4)<p>instead of this<p>(1 . (2 . (3 . (4 . nil))))<p>This language is missing that core feature. (It's also missing <i>symbols</i>, without which a language cannot rightfully call itself a Lisp. And first-class functions. And macros.)<p>While I don't want to discourage any attempt to make Lisp more accessible, it's important to actually get it right. What this article is describing is similar in spirit to Lisp, but it's not Lisp. It's a different (toy) language at a completely different point in the design space.
Really nice code, as someone who isn't caught up entirely with the recent work that's gone into C++, it taught me some useful features!<p>The taxonomy isn't quite right for Lisp. It's actually simpler than the post. It should be something like this (very minimalistically):<p><pre><code> <s-expression> ::= <atom> | ( <s-expression> . <s-expression> )
<atom> ::= <number> | <symbol> | <string>
...
</code></pre>
The difference between this and what the author presents is that everything is an s-expression. s-expressions are either an atomic value or a pair of s-expressions. Convenient notation `(a b c ... z)` called "list builder notation" is provided so that we don't have to write `(a . (b . (c ... (Z . NIL))))`.
This is a really nice and illuminating post!<p>Especially cool how all evaluation is done by line 33. (Minor comment: Line 14 may benefit from using a different variable for the function instead of “c”.)<p>An “aside” comment, as the title mentions “literate C++” [Edit: This was submitted as something like “Build me a Lisp: in less than 50 lines of literate C++”]. This post exemplifies one aspect of literate programming (as Knuth envisioned it), which is “let us concentrate rather on explaining to <i>human beings</i> what we want a computer to do.”<p>But there are two further features that Knuth-style LP systems have, which are missing here:<p>• The ability to write your program / explanation in any order (ideally, an order that is best for presentation, rather than an order demanded by the compiler). In this case, the program is explained strictly in the order of lines in the program, which imposes some awkwardness. (Not only in the explanation, but also in the code: e.g. putting a #include on line 34 of 49.)<p>• Named chunks. So instead of writing<p><pre><code> int main() {
try {
</code></pre>
in one code block, and having to continue it later, you could write something like, say,<p><pre><code> int main() {
try {
[[say hello world]]
} [[handle errors]]
</code></pre>
and later fill in the corresponding sections by name.<p>The original examples by Knuth are somewhat hard to read because they were written in Pascal and the programs were quite low-level but there's a great example available today (a book which won an Academy Award!), now free online — <a href="http://www.pbr-book.org/" rel="nofollow">http://www.pbr-book.org/</a> (random page: <a href="http://www.pbr-book.org/3ed-2018/Light_Transport_I_Surface_Reflection/Direct_Lighting.html" rel="nofollow">http://www.pbr-book.org/3ed-2018/Light_Transport_I_Surface_R...</a> )<p>But then again, the “no-tools” approach here does have the advantage of not requiring any special build step and not requiring the reader to understand any such conventions, so I guess that's a tradeoff. (They say one of the reasons literate programming never took off is that there are as many literate-programming tools as the number of people trying literate programming; everyone ends up having to write the tool that works for them.)
Here's a case where the previously submitted title, which included something like "in less than 50 lines of literate C++", was more indicative/compelling and I think more useful for news.yc.<p>I don't think of that as click-bait in the same way as "you won't believe #7", but rather as additional information which truthfully and transparently makes it more likely that I'll accurately gauge my interest in the linked article.<p>"Don't editorialize" in this case is a negative, but perhaps is globally optimal.
For whatever it's worth, here is the same in 24 lines of OCaml:<p><pre><code> type cell = Atom of string
| Sexpr of cell list
let library = Hashtbl.create 1
let rec eval = function
| Atom s -> s
| Sexpr [] -> failwith "Empty sexpr"
| Sexpr (head :: args) ->
let fname = eval head in
match Hashtbl.find_opt library fname with
| Some builtin -> builtin args
| None -> failwith (String.concat " " [fname; " not found"])
let main () =
let prog = Sexpr [Atom "cat"; Atom "Hello "; Atom "world!"] in
let prog2 = Sexpr [Sexpr [Atom "cat"; Atom "c"; Atom "a"; Atom "t"];
Atom "Hello "; Atom "world!"] in
Hashtbl.add library "cat"
(fun args -> String.concat "" (List.map eval args));
Printf.printf "%s\n" (eval prog);
Printf.printf "%s\n" (eval prog2)
let _ = main ()
</code></pre>
Using linked lists instead of vectors makes separating an application's head and args (CAR and CDR, if you prefer) much easier than using clunky C++ iterators. This is because linked list cells are composed of cons cells.
If you enjoy reading code and want to know a bit more about lisp, maybe this is interesting:<p>"Scheme 9 from empty space" -- <a href="https://t3x.org/s9fes/" rel="nofollow">https://t3x.org/s9fes/</a><p>It's a scheme built in c using literate programming. You can even buy a printed version.<p>Also, there's "Lisp in small pieces" if you want to go deeper -- <a href="https://books.google.de/books/about/Lisp_in_Small_Pieces.html" rel="nofollow">https://books.google.de/books/about/Lisp_in_Small_Pieces.htm...</a>
Thanks, that is a very nice writeup. I have been experimenting a bit with creating new Lisp-like languages in Racket and the idea of growing a language to solve specific types of problems is powerful (and is the way I program in Lisp, from the bottom up). Sorry if this is a bit off topic, but you might enjoy the experiences of someone building their own Lisp Machine with a eZ80, complete with hardware hacking support: <a href="https://youtu.be/Ad9NtyBCx78" rel="nofollow">https://youtu.be/Ad9NtyBCx78</a>
Nice post... even if before clicking through I expected a post about why asking "build me a lisp" could have been a good interview question :)<p>As a side note, I wrote a similar post in Swift: <a href="https://www.uraimo.com/2017/02/05/building-a-lisp-from-scratch-with-swift/" rel="nofollow">https://www.uraimo.com/2017/02/05/building-a-lisp-from-scrat...</a>
Can someone familiar with modern C++ explain the type mechanics of std::visit on line 14? In particular, it seems the “auto” parameter of the lambda expression could stand in for either type in the variant, dependent on its runtime value, but I have always thought of “auto” as a compile-time mechanism.<p>Is the “auto” in this case being filled in by some compiler-generated proxy type that can dispatch any common operation available across all variants?
> Normally programming language blog posts get started with grammars and syntax and parsing and all sorts of stuff like that. I can't be bothered with all of that,<p>And I can’t be bothered with C++ for compiler construction.