[tromp]

Lambda Calculus is computationally foundational. Lisp carries a lot of non-foundational baggage, some of which (like number primitives) makes it far more efficient for running on actual hardware.

> As such, Lisp's identification of CONS/CAR/CDR/COND as a sufficient set of primitives for a universal Turing machine

You don't need any of those for universality. They are trivially expressible in Lambda Calculus. LAMBDA is really the only necessary primitive.

[lisper]

Yes, that is why I said sufficient and not necessary. The reason CONS/CAR/CDR/COND matter is not because they are necessary. That they are not necessary was known long before 1958. The reason they matter is that they are a better impedance match to human cognition than LC. People can actually write useful programs in Lisp. Very few people can write useful code in LC. Lisp matters because it is a local maximum on the ratio of real-world utility to the size of the formalism.

[UPDATE] One idea I've been kicking around for a long time but have not yet acted on is to explore using abstract associative maps as a primitive and see how far that gets you. I suspect this would be a significant win in terms of comprehensibility of code. The foundational axiom would be something like:

((amap k1 v2 k2 v2 ... kn vn ...) kn) == vn

So IF, for example, can be written as (amap true [then] false [else]), CONS is (amap car [left] cdr [right]), etc.

Or something like that.

Oh, yeah, Lisp also introduced symbols as first-class entities. That's a big win.

[tromp]

> People can actually write useful programs in Lisp.

I find programming in Haskell much more pleasant. Using car/cdr feels rather primitive compared to pattern matching.

> Lisp matters because it is a local maximum on the ratio of real-world utility to the size of the formalism.

I feel that role is better served by Haskell, which is basically typed lambda calculus with syntactic sugar on top.

Ben Lynn's awesome work [1] shows how minimal a Haskell implementation can be...

[1] https://crypto.stanford.edu/~blynn/compiler/

[kazinator]

Pattern matching appeared in Lisp in the 1960's. See The COMIT Feature in LISP II, https://www.softwarepreservation.com/projects/LISP/lisp2/MIT...

Most mainstream Lisp dialects have some sort of structural pattern matching. Common Lisp has destructuring-bind, which is enough for avoiding car/cdr. Plus a number of advanced pattern matching libraries that are not just for matching lists.

Same with Scheme dialects.

Even Emacs Lisp has pattern matching: https://www.emacswiki.org/emacs/PatternMatching

Nobody needs to work without pattern matching in Lisp, save for maybe some hapless AutoCAD users.

[lisper]

> I find programming in Haskell much more pleasant.

Sure, but that misses the point. Some people like Java. Some like Perl. Some like C++. But, none of these languages come close to Lisp's ratio of utility vs size. So the fact that some people gravitate towards Haskell means nothing in and of itself. (Also, and I mean this with the utmost respect, your brain doesn't work like most people's brains.)

> Ben Lynn's awesome work [1] shows how minimal a Haskell implementation can be...

I'm not sure what you are referring to here. There are two links on that page. One is to an entry in the obfuscated C contest and the other is to Duet. The former is impressively small but, well, it is an entry in the obfuscated C contest and so it's pretty obfuscated. Duet is not obfuscated, but it doesn't seem to me to be particularly minimal. A minimal Lisp compiler can be both readable and an order of magnitude smaller.

> Using car/cdr feels rather primitive compared to pattern matching.

But adding pattern matching to Lisp is an elementary exercise and can be done at the user level. (And surely you knew that too.)

> Haskell, which is basically typed lambda calculus with syntactic sugar on top

Yes, but Haskell's syntactic sugar is significant for two reasons. First, it's not optional. You can put all sorts of fancy syntax on top of Lisp too, but you don't have to, and empirically, most Lisp programmers try this once early in their careers and come to realize that it is a bad idea, that working directly in the AST is weird at first but that it is actually much more productive in the long run. In Haskell there is no AST exposed to the user so this is not an option. There is one syntax and you're stuck with it. And second, Haskell's syntax not well designed IMHO. I am not a particularly skilled coder, but I have worked in a lot of different languages and I find Haskell borderline impenetrable.

BTW, this is a tangent, but I feel the need to say this since you brought up pattern matching: IMHO, if you are using pattern matching in real-world code, you are doing something wrong. Pattern-matching is a way to impose some discipline on punning cons cells to hold structured data, but punning cons cells is a fundamental mistake. If you have structured data, that data should be contained in structures, not cons cells.

(The only exception to this rule is a macro expander, where you have no choice but to deal with cons cells because that is what is handed to you by the reader. But if you are writing a lot of macro expanders then that too is an indication that you are doing something wrong.)

IMHO of course.

[kazinator]

> If you have structured data, that data should be contained in structures, not cons cells.

There is pattern matching on structures. If you switch from conses to structures, the relevance of pattern matching doesn't go away.

Types divide the data into categories, but the categories don't capture all the variation among the instances.

Pattern matching in functional languages is mostly done on algebraic types.

[kazinator]

I agree with everything you wrote, except: adding pattern matching that hits even the lower rungs of good quality is sweating bullets. (So good thing users of Lisps don't have to.)