[chubot]

C is the foundation of computing in the sense that essentially every programming language and operating system is written in C or C++, and those are the tools that enable every other piece of software. More precisely, I would say that C is the foundation of software; it's how we stopped throwing out our programs when we changed computers. The first portable operating system kernels were written in C.

I guess I could have been more precise and said that the lambda calculus (rather than Scheme/Lisp) is not the foundation of computing. It seems like there are people who still think this; see my recent response here:

https://news.ycombinator.com/item?id=11412392

You could say Lisp and Scheme are proof of that. To actually be bootstrapped, they had to add all this other stuff like vectors and hash tables. I don't know the details of how well those are axiomatized. Paul Graham's Arc tried to a little further down, i.e. unifying functions and macros, defining numbers in terms of lists a la Peano arithmetic, etc., but I'm not sure how far that effort went.

I mentioned all my experience with Lisp... doing SICP 19 years ago, and then coming back to it. As I said, I think it's outstanding research, but if you are trying to build an entire computing universe out of it, that's folly. Good luck. It's just not powerful enough -- once you add all the stuff you actually need, you're not far from the complexity of C.

[brlewis]

In the 1980s Scheme was not performant enough. C was how you got tolerably fast programs. A lot of research, notably in garbage collection, has made Scheme much more performant since then. Additionally, computer hardware has improved to the point where people write useful programs in languages that are dramatically slower than Scheme, e.g. PHP, Python, Ruby.

You are conflating minimalism with the Scheme language because Scheme is often used to illustrate minimalism. Vectors and hash tables are not "all this other stuff", they're part of the language spec[1]. You're also throwing Lisp in there even though minimalism is not a central theme of Lisp.

[1] When you did SICP hash tables were not part of the language spec although implementations generally had them; they got standardized in 2007 with R6RS. But vectors were in the language spec since at least 1985.

[clacke2]

> To actually be bootstrapped, they had to add all this other stuff like vectors and hash tables.

Just like C had to add things like arrays to the Turing machine? C doesn't even have hash tables in the spec! According to your definitions, C is a toy language.

[chubot]

No, because it's possible to implement efficient hash tables with C's primitives -- in fact that's how hash tables in essentially ALL languages ARE implemented.

cons cells are not sufficient to implement hash tables. Scheme needs arrays for that. cons cells can be implemented efficiently using arrays, but the converse isn't true, so arrays are more fundamental in some sense.

If you don't care about algorithmic efficiency, then you could choose either cons cells or arrays as your primitive. But obviously we do care, so arrays were the right choice. IOW, C was the right choice, not Scheme.

[nickpsecurity]

"No, because it's possible to implement efficient hash tables with C's primitives -- in fact that's how hash tables in essentially ALL languages ARE implemented."

Because each architecture has a C compiler that's been highly optimized. Popularity plus money invested. That's it. If you were right, we'd see optimizations coded in C even when alternative, optimizing compilers were available. I got a one-word counter to that interestingly enough from "high-performance computing" field: FORTRAN. Free Pascal people are doing fine in performance and low-level code as well despite little to no investment in them.

Seems throwing money at a turd (eg FORTRAN, C) can get a lot of people's hands on it despite some of us shuddering and saying "Get that pile of crap away from me!"

[pjmlp]

It is a toy language.

One step above a portable macro assembler, developed in a decade where research labs outside AT&T were already using safe systems programming languages for about a decade.

Their big failure was that they were selling their work, instead of doing like AT&T that initially gave UNIX for free, because it was forbidden to sell it.

Unfortunately free always wins, regardless of quality.

[davexunit]

>cons cells are not sufficient to implement hash tables.

Again, cons cells are not the only primitive type for making compound data structures.

[sklogic]

> in fact that's how hash tables in essentially ALL languages ARE implemented

Obviously a false statement.

[fredmorcos]

> Just like C had to add things like arrays to the Turing machine?

Care to elaborate on that?