6 ms·

OK, point taken about #1. It is valuable to have the basic axioms and then separate syntactic sugar. But #2 and #3 are what I would call bootstrapping problem

by chubot 11y ago

OK, point taken about #1. It is valuable to have the basic axioms and then separate syntactic sugar. But #2 and #3 are what I would call bootstrapping problems... in other words, there is a reason that C is the foundation of computing rather than Lisp. I don't think anybody really thinks otherwise anymore. But for example, set-cdr! is not in the lambda calculus, and you need it even for basic things. Likewise, Scheme implementations have mutable hash tables, but they're written in C and not Scheme. I don't know how you even write a hash table based on cons cells rather than O(1) indexing. Regarding #4, here is a good link. The basic idea is that macros could just be functions on lists, and then you get composition of macros like you have composition of functions. Paul Graham incorporated this into Arc. http://matt.might.net/articles/metacircular-evaluation-and-first-class-run-time-macros/ http://matt.might.net/articles/metacircular-evaluation-and-f... My point is you could say Scheme sits at a somewhat awkward place between "not foundational enough" (not fully bootstrapped) and "awkward in practice" (compared to say Python). Though I wouldn't go as far as to say that... Obviously it was groundbreaking work that influenced Python and R and tons of stuff we use today. It's outstanding research, but it feels like it has been almost fully incorporated into the computing culture now.

davexunit 11y ago
>there is a reason that C is the foundation of computing rather than Lisp. I don't think anybody really thinks otherwise anymore. C is not the foundation of computing. Why would you say this? >Likewise, Scheme implementations have mutable hash tables, but they're written in C and not Scheme. A native code compiler written in Scheme would have its hash table implementation also written in Scheme. >I don't know how you even write a hash table based on cons cells rather than O(1) indexing. You wouldn't do that! Cons cells are not the only primitive data type! Another primitive type in Scheme is the vector, which is a mutable array. I'm sorry, but you greatly misunderstand Lisp and how compilers work.
- chubot 11y ago
  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 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 11y ago
    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 11y ago
    > 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 11y ago
      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 11y ago
        "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!"
- coldtea 11y ago
  >C is not the foundation of computing. Why would you say this? Because all the popular OSes, drivers, userlands, servers, GUI libraries, and compilers/languages are 99% written in C (or C++ which is close enough).
  - nickpsecurity 11y ago
    That's different. It means C is the most popular language in system programming. Makes so much sense when I explain above that C's prevalence is due to social and economic reasons given you argued it won a popularity contest. Hillary and Trump are also winning those right now if you want to argue how logical correctness and utility are connected to popularity. ;)
    - coldtea 11y ago
      >That's different. It means C is the most popular language in system programming. And the basis upon which computing sits upon. Take away all C/C++ code and we have nothing or almost nothing. Take away all Lisp/Scheme code and people will barely notice. >Makes so much sense when I explain above that C's prevalence is due to social and economic reasons given you argued it won a popularity contest. If by economic you mean "pragmatic" and "engineering considerations", then yes.
      - nickpsecurity 11y ago
        "Take away all C/C++ code and we have nothing or almost nothing." In that meaning, it's true but only as an accident of history that has little to nothing to do with C's design itself. "If by economic you mean "pragmatic" and "engineering considerations", then yes." BCPL was whatever compiled on a machine from the 1960's. C was what compiled on a machine from the 1970's. ALGOL was engineered. C was what compiled and ran fast on old hardware. That's it. http://pastebin.com/UAQaWuWG http://pastebin.com/UAQaWuWG The rest was social factors. Even when alternative languages did better, most people didn't adopt them. Most buyers also paid for performance per dollar totally ignoring reliability, security, maintenance, and so on. Unless you argue these don't matter, then the dominance of C and UNIX is once again due to something other than their technical merits. Plus, the fact that their problems stayed in... intentionally... once better hardware came online while other players fixed them in various ways.
nickpsecurity 11y ago
" there is a reason that C is the foundation of computing rather than Lisp" That's a myth. Try using first-hand sources like the papers from people who designed BCPL, B, and C to understand why it's that way. Answer: terrible hardware back then. That's it. Its popularity was result of prevalence of terrible hardware and that UNIX was written in C. I broke it's history down in just a few pages with a timeline and references here: http://pastebin.com/UAQaWuWG http://pastebin.com/UAQaWuWG Likewise, before the social effect, the OS's were coded in a number of HLL's with capabilities UNIX lacked. Languages included ALGOL, PL/0, and Pascal. Later, they were done in Modula, Oberon, Ada, Fortran (yeah lol), LISP, and so on as hardware improved beyond 1970's minicomputers. Here's some UNIX alternatives and their capabilities that developed... some of which you still don't have. :) https://news.ycombinator.com/item?id=10957020 https://news.ycombinator.com/item?id=10957020 Far as LISP, it's been implemented in hardware multiple times. This included naive ones that worked like a simple evaluator with garbage collection built into the memory-management unit. There was also one that had four specialized units for more sophisticated execution. One Scheme was designed and mathematically verified using the DDD toolkit that was also LISP if I recall. http://www.cs.indiana.edu/pub/techreports/TR544.pdf http://www.cs.indiana.edu/pub/techreports/TR544.pdf Oh heck, forgot they did it with VLISP. That was a Scheme48 interpreter and PreScheme compiler rigorously verified for correctness. PreScheme was a Scheme subset for systems programming. So, the work actually took a verified Scheme then mechanically derived verified HW from that Scheme code using a LISP-based tool. I recall from other papers they got it working on a FPGA and some PAL's. Whereas, I don't know many small teams producing verifiable C code on verifiable C processors from verifiable C tools. Nah, I don't think your favorite language is anywhere near where you think it is. I don't even find LISP ideal here by far. It just did more in functionality & bare metal. Also, first LISP machine was started when UNIX was released interesting enough.
wtbob 11y ago
> there is a reason that C is the foundation of computing rather than Lisp. I don't think anybody really thinks otherwise anymore I must not be anybody, then, because I think that Lisp provides a wonderful notation for thinking about symbolic computation which will last for millennia while C is … a successful programming language of the late 20th century. > I don't know how you even write a hash table based on cons cells rather than O(1) indexing. A cons cell is just a double-pointer. You can write a hash table using conses just as easily as you would using pointers (note, I'm not saying that'd be efficient, which is why Lisp offers arrays as well as conses).
dragonwriter 11y ago
C isn't the foundation of computing. It's a popular systems language largely because of, first, it's connection with UNIX, and, second, network effects of its early popularity.
sklogic 11y ago
C is far too high level to be a "foundation". NAND gate is a foundation.

by chubot 11y ago

davexunit 11y ago

>there is a reason that C is the foundation of computing rather than Lisp. I don't think anybody really thinks otherwise anymore. C is not the foundation of computing. Why would you say this? >Likewise, Scheme implementations have mutable hash tables, but they're written in C and not Scheme. A native code compiler written in Scheme would have its hash table implementation also written in Scheme. >I don't know how you even write a hash table based on cons cells rather than O(1) indexing. You wouldn't do that! Cons cells are not the only primitive data type! Another primitive type in Scheme is the vector, which is a mutable array. I'm sorry, but you greatly misunderstand Lisp and how compilers work.

chubot 11y ago
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 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 11y ago
  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 11y ago
  > 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 11y ago
    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 11y ago
      "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!"
coldtea 11y ago
>C is not the foundation of computing. Why would you say this? Because all the popular OSes, drivers, userlands, servers, GUI libraries, and compilers/languages are 99% written in C (or C++ which is close enough).
- nickpsecurity 11y ago
  That's different. It means C is the most popular language in system programming. Makes so much sense when I explain above that C's prevalence is due to social and economic reasons given you argued it won a popularity contest. Hillary and Trump are also winning those right now if you want to argue how logical correctness and utility are connected to popularity. ;)
  - coldtea 11y ago
    >That's different. It means C is the most popular language in system programming. And the basis upon which computing sits upon. Take away all C/C++ code and we have nothing or almost nothing. Take away all Lisp/Scheme code and people will barely notice. >Makes so much sense when I explain above that C's prevalence is due to social and economic reasons given you argued it won a popularity contest. If by economic you mean "pragmatic" and "engineering considerations", then yes.
    - nickpsecurity 11y ago
      "Take away all C/C++ code and we have nothing or almost nothing." In that meaning, it's true but only as an accident of history that has little to nothing to do with C's design itself. "If by economic you mean "pragmatic" and "engineering considerations", then yes." BCPL was whatever compiled on a machine from the 1960's. C was what compiled on a machine from the 1970's. ALGOL was engineered. C was what compiled and ran fast on old hardware. That's it. http://pastebin.com/UAQaWuWG http://pastebin.com/UAQaWuWG The rest was social factors. Even when alternative languages did better, most people didn't adopt them. Most buyers also paid for performance per dollar totally ignoring reliability, security, maintenance, and so on. Unless you argue these don't matter, then the dominance of C and UNIX is once again due to something other than their technical merits. Plus, the fact that their problems stayed in... intentionally... once better hardware came online while other players fixed them in various ways.

nickpsecurity 11y ago

" there is a reason that C is the foundation of computing rather than Lisp" That's a myth. Try using first-hand sources like the papers from people who designed BCPL, B, and C to understand why it's that way. Answer: terrible hardware back then. That's it. Its popularity was result of prevalence of terrible hardware and that UNIX was written in C. I broke it's history down in just a few pages with a timeline and references here: http://pastebin.com/UAQaWuWG http://pastebin.com/UAQaWuWG Likewise, before the social effect, the OS's were coded in a number of HLL's with capabilities UNIX lacked. Languages included ALGOL, PL/0, and Pascal. Later, they were done in Modula, Oberon, Ada, Fortran (yeah lol), LISP, and so on as hardware improved beyond 1970's minicomputers. Here's some UNIX alternatives and their capabilities that developed... some of which you still don't have. :) https://news.ycombinator.com/item?id=10957020 https://news.ycombinator.com/item?id=10957020 Far as LISP, it's been implemented in hardware multiple times. This included naive ones that worked like a simple evaluator with garbage collection built into the memory-management unit. There was also one that had four specialized units for more sophisticated execution. One Scheme was designed and mathematically verified using the DDD toolkit that was also LISP if I recall. http://www.cs.indiana.edu/pub/techreports/TR544.pdf http://www.cs.indiana.edu/pub/techreports/TR544.pdf Oh heck, forgot they did it with VLISP. That was a Scheme48 interpreter and PreScheme compiler rigorously verified for correctness. PreScheme was a Scheme subset for systems programming. So, the work actually took a verified Scheme then mechanically derived verified HW from that Scheme code using a LISP-based tool. I recall from other papers they got it working on a FPGA and some PAL's. Whereas, I don't know many small teams producing verifiable C code on verifiable C processors from verifiable C tools. Nah, I don't think your favorite language is anywhere near where you think it is. I don't even find LISP ideal here by far. It just did more in functionality & bare metal. Also, first LISP machine was started when UNIX was released interesting enough.

wtbob 11y ago

> there is a reason that C is the foundation of computing rather than Lisp. I don't think anybody really thinks otherwise anymore I must not be anybody, then, because I think that Lisp provides a wonderful notation for thinking about symbolic computation which will last for millennia while C is … a successful programming language of the late 20th century. > I don't know how you even write a hash table based on cons cells rather than O(1) indexing. A cons cell is just a double-pointer. You can write a hash table using conses just as easily as you would using pointers (note, I'm not saying that'd be efficient, which is why Lisp offers arrays as well as conses).

dragonwriter 11y ago

C isn't the foundation of computing. It's a popular systems language largely because of, first, it's connection with UNIX, and, second, network effects of its early popularity.

sklogic 11y ago

C is far too high level to be a "foundation". NAND gate is a foundation.