4 ms·

MIX/MMIX are close to how CPUs work physically. scheme is close to how computation works theoretically. The pedagogical approach that appeals to individuals t

by ska 6y ago

MIX/MMIX are close to how CPUs work physically. scheme is close to how computation works theoretically. The pedagogical approach that appeals to individuals tends to align with how they are most comfortable thinking about it.

spekcular 6y ago
Let me say something that may reveal my ignorance, but which I'm very happy to be corrected on: for the purpose of writing moderately-sized, everyday programs, I've never needed to understand how computation works theoretically (more abstractly than introductory algorithms and data structures). And that's not because I'm not comfortable with abstraction, or because I don't know how it works theoretically, I just haven't. Further, the obstacles I face when coding are mostly tightly coupled to the fact that I'm programming on physical hardware – again, nothing to do with the theory of computation. Even in a high-level language like Python, if you program the Sieve of Eratosthenes in a naive way without understanding what's going on under the hood with deleting an element from a list, you're going to have a bad time [0]. To caricature SICP-style instruction a bit, I'm imagining someone learning that recursion is useful (Scheme peeps seem to love it) without also being taught it generally has poor performance characteristics. Perhaps a better criticism is the mostly useless emphasis on immutable data structures. The example I like to bring up is how Haskell for a long time didn't have a readily-available hash table implementation for completely ideological reasons. No, hash maps are strictly worse, thank you. [0] https://stackoverflow.com/questions/3939660/sieve-of-eratosthenes-finding-primes-python https://stackoverflow.com/questions/3939660/sieve-of-eratost...
- Jtsummers 6y ago
  > To caricature SICP-style instruction a bit, I'm imagining someone learning that recursion is useful (Scheme peeps seem to love it) without also being taught it generally has poor performance characteristics. SICP teaches that recursion can have bad performance and how to use it without blowing the stack or wasting time with unnecessary computations. Scheme, the language, requires tail call elimination so compilers will transform tail recursion into something as fast as a conventional loop.
  - spekcular 6y ago
    Yes, I agree, that is a caricature. More seriously, I think leaning on this language-specific feature in a book that's supposedly teaching "general programming 101," or whatever, is in bad taste. As it says: > One reason that the distinction between process and procedure may be confusing is that most implementations of common languages (including Ada, Pascal, and C) are designed in such a way that the interpretation of any recursive procedure consumes an amount of memory that grows with the number of procedure calls, even when the process described is, in principle, iterative. As a consequence, these languages can describe iterative processes only by resorting to special-purpose ``looping constructs'' such as do, repeat, until, for, and while. The implementation of Scheme we shall consider in chapter 5 does not share this defect. It will execute an iterative process in constant space, even if the iterative process is described by a recursive procedure. An implementation with this property is called tail-recursive. With a tail-recursive implementation, iteration can be expressed using the ordinary procedure call mechanism, so that special iteration constructs are useful only as syntactic sugar. This is an example of a point where an algorithms book is helpful + clarifying and SICP is really not. (fake quote: "Be conceptually sloppy and let Scheme take care of it, kid.") It has a few pages on orders of growth, but the coverage is not amazing.
    - chongli 6y ago
      I wouldn’t really call tail-call elimination a feature, language-specific or otherwise. Instead, I would describe the lack of it as a bug. If you examine what’s actually going on in compilers that lack tail call elimination, what you witness is the saving of registers to the stack whose values are provably never going to be used.
      - spekcular 6y ago
        You contend that all C compilers prior to their introduction of TCE were bugged?
    - ckcheng 6y ago
      Tail-call elimination / optimization is not a Scheme language-specific feature though. Other popular languages have TCO to varying degrees, like C and C++ when using fairly standard compilers like MSVC, GCC, Clang, or ICC [1]. Destructors do get in the way though sometimes. Java/JVM doesn't support TCO, but Kotlin and Clojure make do with special syntax to support tail-recursion (i.e. tailrec, recur). Apparently JavaScriptCore supports TCO for JavaScript [2]. The book makes it sound like TCE is language-specific, but since that book was published, it's spread to many other mainstream languages too. [1]: https://stackoverflow.com/questions/34125/which-if-any-c-compilers-do-tail-recursion-optimization/34129#34129 https://stackoverflow.com/questions/34125/which-if-any-c-com... [2]: https://dev.to/rohit/demystifying-tail-call-optimization-5bf3 https://dev.to/rohit/demystifying-tail-call-optimization-5bf...
- tome 6y ago
  > Perhaps a better criticism is the mostly useless emphasis on immutable data structures. The example I like to bring up is how Haskell for a long time didn't have a readily-available hash table implementation for completely ideological reasons. Can you link to some evidence that the reasons were completely ideological?
bogomipz 6y ago
>"MIX/MMIX are close to how CPUs work physically." What is MIX/MMIX? Is this something specific to the SICP book?
- Jtsummers 6y ago
  From Knuth’s The Art of Computer Programming. MIX is the earlier version, MMIX is the more recent (though now 20 or so years old) version. They are descriptions of a computer architecture and machine instructions used to explore algorithms in his books. https://en.m.wikipedia.org/wiki/MMIX https://en.m.wikipedia.org/wiki/MMIX
- astrange 6y ago
  Knuth's TAOCP was originally written in an imaginary 60s-style CISC assembly called MIX (with some oddities like being decimal) but newer editions are in a RISC style one called MMIX (which Knuth claims is more practical but really isn't.)
  - disgruntledphd2 6y ago
    Well, all I can say about that is that I read through the MMIX supplement and did a bunch of the exercises, and I know have enough knowledge to vaguely understand assembly. It hasn't been massively useful to me in my professional life (I'm a data scientist), but it definitely has helped me to gain a deeper appreciation of how computing works.
    - astrange 6y ago
      By practical I meant it's hard to implement in hardware. As far as I know it's easy to learn, having register windows is just kind of weird.
      - disgruntledphd2 6y ago
        Ah OK. I guess that makes sense (especially as Knuth implemented its interpreter in C, as documented in MMIXware).
vram22 6y ago
Both understandings are needed for best results.

by ska 6y ago

spekcular 6y ago

Let me say something that may reveal my ignorance, but which I'm very happy to be corrected on: for the purpose of writing moderately-sized, everyday programs, I've never needed to understand how computation works theoretically (more abstractly than introductory algorithms and data structures). And that's not because I'm not comfortable with abstraction, or because I don't know how it works theoretically, I just haven't. Further, the obstacles I face when coding are mostly tightly coupled to the fact that I'm programming on physical hardware – again, nothing to do with the theory of computation. Even in a high-level language like Python, if you program the Sieve of Eratosthenes in a naive way without understanding what's going on under the hood with deleting an element from a list, you're going to have a bad time [0]. To caricature SICP-style instruction a bit, I'm imagining someone learning that recursion is useful (Scheme peeps seem to love it) without also being taught it generally has poor performance characteristics. Perhaps a better criticism is the mostly useless emphasis on immutable data structures. The example I like to bring up is how Haskell for a long time didn't have a readily-available hash table implementation for completely ideological reasons. No, hash maps are strictly worse, thank you. [0] https://stackoverflow.com/questions/3939660/sieve-of-eratosthenes-finding-primes-python https://stackoverflow.com/questions/3939660/sieve-of-eratost...

Jtsummers 6y ago
> To caricature SICP-style instruction a bit, I'm imagining someone learning that recursion is useful (Scheme peeps seem to love it) without also being taught it generally has poor performance characteristics. SICP teaches that recursion can have bad performance and how to use it without blowing the stack or wasting time with unnecessary computations. Scheme, the language, requires tail call elimination so compilers will transform tail recursion into something as fast as a conventional loop.
- spekcular 6y ago
  Yes, I agree, that is a caricature. More seriously, I think leaning on this language-specific feature in a book that's supposedly teaching "general programming 101," or whatever, is in bad taste. As it says: > One reason that the distinction between process and procedure may be confusing is that most implementations of common languages (including Ada, Pascal, and C) are designed in such a way that the interpretation of any recursive procedure consumes an amount of memory that grows with the number of procedure calls, even when the process described is, in principle, iterative. As a consequence, these languages can describe iterative processes only by resorting to special-purpose ``looping constructs'' such as do, repeat, until, for, and while. The implementation of Scheme we shall consider in chapter 5 does not share this defect. It will execute an iterative process in constant space, even if the iterative process is described by a recursive procedure. An implementation with this property is called tail-recursive. With a tail-recursive implementation, iteration can be expressed using the ordinary procedure call mechanism, so that special iteration constructs are useful only as syntactic sugar. This is an example of a point where an algorithms book is helpful + clarifying and SICP is really not. (fake quote: "Be conceptually sloppy and let Scheme take care of it, kid.") It has a few pages on orders of growth, but the coverage is not amazing.
  - chongli 6y ago
    I wouldn’t really call tail-call elimination a feature, language-specific or otherwise. Instead, I would describe the lack of it as a bug. If you examine what’s actually going on in compilers that lack tail call elimination, what you witness is the saving of registers to the stack whose values are provably never going to be used.
    - spekcular 6y ago
      You contend that all C compilers prior to their introduction of TCE were bugged?
  - ckcheng 6y ago
    Tail-call elimination / optimization is not a Scheme language-specific feature though. Other popular languages have TCO to varying degrees, like C and C++ when using fairly standard compilers like MSVC, GCC, Clang, or ICC [1]. Destructors do get in the way though sometimes. Java/JVM doesn't support TCO, but Kotlin and Clojure make do with special syntax to support tail-recursion (i.e. tailrec, recur). Apparently JavaScriptCore supports TCO for JavaScript [2]. The book makes it sound like TCE is language-specific, but since that book was published, it's spread to many other mainstream languages too. [1]: https://stackoverflow.com/questions/34125/which-if-any-c-compilers-do-tail-recursion-optimization/34129#34129 https://stackoverflow.com/questions/34125/which-if-any-c-com... [2]: https://dev.to/rohit/demystifying-tail-call-optimization-5bf3 https://dev.to/rohit/demystifying-tail-call-optimization-5bf...
tome 6y ago
> Perhaps a better criticism is the mostly useless emphasis on immutable data structures. The example I like to bring up is how Haskell for a long time didn't have a readily-available hash table implementation for completely ideological reasons. Can you link to some evidence that the reasons were completely ideological?

bogomipz 6y ago

>"MIX/MMIX are close to how CPUs work physically." What is MIX/MMIX? Is this something specific to the SICP book?

Jtsummers 6y ago
From Knuth’s The Art of Computer Programming. MIX is the earlier version, MMIX is the more recent (though now 20 or so years old) version. They are descriptions of a computer architecture and machine instructions used to explore algorithms in his books. https://en.m.wikipedia.org/wiki/MMIX https://en.m.wikipedia.org/wiki/MMIX
astrange 6y ago
Knuth's TAOCP was originally written in an imaginary 60s-style CISC assembly called MIX (with some oddities like being decimal) but newer editions are in a RISC style one called MMIX (which Knuth claims is more practical but really isn't.)
- disgruntledphd2 6y ago
  Well, all I can say about that is that I read through the MMIX supplement and did a bunch of the exercises, and I know have enough knowledge to vaguely understand assembly. It hasn't been massively useful to me in my professional life (I'm a data scientist), but it definitely has helped me to gain a deeper appreciation of how computing works.
  - astrange 6y ago
    By practical I meant it's hard to implement in hardware. As far as I know it's easy to learn, having register windows is just kind of weird.
    - disgruntledphd2 6y ago
      Ah OK. I guess that makes sense (especially as Knuth implemented its interpreter in C, as documented in MMIXware).

vram22 6y ago

Both understandings are needed for best results.