20 ms·

Computers are made of metal, not category theory

80 points by stakent 12y ago

mcguire 12y ago
I'm a little confused: the author is speaking of "metal" but isn't writing assembly. (And I'm a little snarky today.)
yzzxy 12y ago
I'm no expert on these matters, but it seems a bit ridiculous to call out entire swaths of the programming/computer science world while referencing the JVM as a benchmark.
- cantankerous 12y ago
  I think the critique is with the implied (but not always understood) overhead of some of FP's common types of abstraction.
- yummyfajitas 12y ago
  I'm (author here) not "calling them out" - most people doing research in FP are well aware of these issues. This is aimed at people like me who merely implement stuff in those languages. Also, most of the Scala code I'm describing compiles down to very straightforward instructions that would be the same on almost any compiler. If you can show me any other language which will handle a linked list as rapidly as the JVM handles an array, I'll be extremely impressed.
  - dons 12y ago
    > handle a linked list as rapidly as the JVM handles an array A linked list is not an array. Particular operations will have different complexities. One data structure is not "more rapid" than another.
    - kasey_junk 12y ago
      This is precisely the kind of thinking people need to be careful about. Some data structures are more rapid than others even with more complex operations, because they conform to the reality of the underlying hardware better.
      - codygman 12y ago
        Can you please provide some examples? It would be much appreciated.
        noblethrasher 12y ago
        http://youtu.be/YQs6IC-vgmo http://youtu.be/YQs6IC-vgmo Stroustrup describes why –on modern hardware– vectors are faster than linked list for insertion and deletion.
  - comex 12y ago
    But your post makes more claims than merely computers not being able to arbitrage data structures. In your first example, while I don't have any experience with Scala, any competent compiler for C++, Haskell, Rust, etc. will inline a function like "map", so there is no "function call overhead" whatsoever. (This example is too simple to benefit from stream fusion as such.) The resulting machine code will look fairly similar; if there is a performance difference, it would be far more subtle than your 10x, and would probably have to do with whether the map implementation in question is specialized for the Array->Array case. One that is will allocate the right number of elements up front and perhaps even skip bounds checks that the compiler might or might not be able to optimize out from the explicit version, but one that isn't will not only include bounds checks but repeatedly have to grow the result array and copy the elements so far to the new allocation.
    - yummyfajitas 12y ago
      Yes, in the conclusion I remark that a Sufficiently Smart Compiler can do all of this. I don't know that either Haskell or C++ compilers will inline your maps, but if so, that's very cool. And yes, specializing for the Array -> Array case and eliminating bounds checks will be necessary to get real performance.
dons 12y ago
Title is misleading. This is about some Scala microbenchmarks. There is no CT or metal here.
jcromartie 12y ago
He keeps using the word "pointer" ...
cantankerous 12y ago
Good read. Minor quibble: I'm not sure calling Julia a functional language is really a fair statement. Yes it's LISP-like, but if you want to go there, Ruby is a LISP-like language in the same ways Julia is. I don't really encounter many folks making the claim that Ruby is a functional language.
- dragonwriter 12y ago
  > I don't really encounter many folks making the claim that Ruby is a functional language. Ruby is a multiparadigm language, and functional is one of the important paradigms it supports. A rather popular essay on Ruby from nearly a decade ago (surprising for me to discover that it was that long ago!) was "Why Ruby is an acceptable LISP" [1] Its true that recently much of the recent focus on functional languages has been on statically-typed and/or pure functional languages, which neither Ruby nor Lisp is... [1] http://www.randomhacks.net/2005/12/03/why-ruby-is-an-acceptable-lisp/ http://www.randomhacks.net/2005/12/03/why-ruby-is-an-accepta...
rollo 12y ago
What I took from this post, is that we should keep working on compilers. They could provably optimize away most of the performance issues and move us closer to doing category theory instead of dealing with the metal.
- cantankerous 12y ago
  Agree with you there. Programmers need to understand the semantics of their language and use it to their advantage. I think this is especially the case in functional languages, especially in Haskell, where two seemingly similar pieces of code can execute in different ways, especially given the presence of lazy semantics. Knowing how to write efficient code in your language can be significantly different than knowing how to write code that works, depending on the language.
  - sanderjd 12y ago
    But that's why the abstraction is leaky. You no longer need to think at just the level of the abstraction, but also at the level of the implementation of the abstraction. This is fine, but it's one of the reasons abstractions tend to be less useful than they seem. If you're always thinking about what's really going on, you might as ditch the abstraction and only think about what's really going on. The less you have to think about its implementation, the better an abstraction is.
    - codygman 12y ago
      You might as well ditch the abstraction? So you program everything in assembler then? OOP is leaky, maybe we should ditch it. The ADT and typeclasses in Haskell are much more general and well-behaved than objects in my experience.
      - sanderjd 12y ago
        I sort of buried the lede in my comment... My main point was that while all abstractions are leaky, it's reasonable to judge them on the relative extent of their leakiness.
deleted 12y ago
[deleted]
dschiptsov 12y ago
- There is nothing absolute in the world. - Metal rails are.
minimax 12y ago
The most important thing here is to measure. Always measure. It doesn't matter what you think is going to be fast or not. The combination of super smart (or not so smart) compilers, multi-level hierarchal caches, pipelining, branch (mis)prediction, etc means you can't just look at a piece of code in a high level language and know how fast it will be. You always have to run the code and measure how long it takes. For anything where you really care about latency, measure.
- TheLoneWolfling 12y ago
  ...And then have something in an entirely unrelated set of code change and make the code you oh-so-carefully benchmarked become half as fast. Because you just caused cache line aliasing, or your pushed your function code across a boundary, or you're now killing your branch predictor, or, or... At this point, in any optimized language benchmarking parts of your code is practically useless for finer optimization. There are some things you will pick up on, sure, but trying to squeeze the last drop of performance out of your code? Good luck. Too many global interactions. I mean: even GCC doesn't generate statistically significantly faster code on O3 versus O2.
kyllo 12y ago
Computers are metal but programming languages are for humans. The purpose of functional abstractions is primarily to help humans produce correct code, not necessarily to optimize for speed. Referentially transparent functions, immutable data and type checking are meant to provide guarantees that reduce complexity, make a program easier to reason about and help stop the programmer from introducing costly and dangerous bugs. It doesn't matter how fast your "fugly imperative code" is, if it's incorrect. And the lesson we've learned the hard way over and over again is that humans are just not smart enough to reliably write correct fugly imperative code.
- kasey_junk 12y ago
  I'm not sure I buy your argument, but even if I did, there is no evidence as of yet that says that fugly functional abstractions provide for lower error rates. Further, performance is part of correctness for nearly any real word example.
  - DanWaterworth 12y ago
    > there is no evidence as of yet that says that fugly functional abstractions provide for lower error rates. Sure there is. Compare the incidence of buffer overflows in C programs vs Haskell ones. > performance is part of correctness for nearly any real word example. No it's not. See the definition of correctness [1]. [1] http://en.wikipedia.org/wiki/Correctness_%28computer_science%29 http://en.wikipedia.org/wiki/Correctness_%28computer_science...
    - dragonwriter 12y ago
      In most real world software, performance constraints are part of the specification, and thus, performance is part of correctness by the definition you cite. (And where they aren't part of the formal specification, it often is later discovered that that was simply a failure of requirements gathering/analysis, in that the specification did not completely capture the expectations of the entity that the software was being built for.)
deleted 12y ago
[deleted]
bkeroack 12y ago
"No, don't take away my beautiful abstractions!"
exDM69 12y ago
If you take a look at how the GHC Haskell compiler (A "Sufficiently Smart Compiler(tm)" in my opinion) works, for example, it is not naively pushing allocating objects, creating thunks and emitting trampoline code. Instead, it analyzes the program structures from graphs and emits rather efficient machine code in the end. Not too dissimilar from what your native code emitting C compiler does. If you look at the machine code for something as "stupid" as the Haskell example below, the output object code does not resemble the semantics of the source program at all. (it's not quite as efficient as the same from a C compiler, but still proves a point) foreign export ccall fac :: Int -> Int fac :: Int -> Int fac n = foldl (*) 1 . take n $ [1..] Compiler and programming language research is a very important topic that yields real performance benefits as well as better programmer productivity. That includes using Category theory to reason about program correctness. If you're interested in how the Haskell compiler works, "Implementation of Functional Programming languages" is a good (albeit a bit outdated) starting point. The whole book is freely available here: http://research.microsoft.com/en-us/um/people/simonpj/papers/slpj-book-1987/ http://research.microsoft.com/en-us/um/people/simonpj/papers... I do agree with the title a bit, though. Some of our computer programming environments are just ridiculously slow. Being slow also means "consumes a lot of power" which is important when more and more computers are powered by batteries.
- dinglefuk 12y ago
  It's amazing the author could be so naive, in my opinion.
- cantankerous 12y ago
  Seconding on the SPJ book! It's a solid start for learning about the particulars of FP implementation.
- cpa 12y ago
  The OP (which I totally agree with!) also states: > Such a compiler could properly determine that intermediate steps are unused, merge them (e.g. translate x.map(f).map(g) to x.map(x => g(f(x)))) Ironically, GHC does that already[0], and will also do TCO. [0] http://metagraph.org/papers/stream_fusion.pdf http://metagraph.org/papers/stream_fusion.pdf
nine_k 12y ago
Aircraft are made of metal, not fluid dynamics. Rockets are made of metal, not ballistics equations. Nuclear bombs are made of metal, not quantum theory. Well, metal is important, but to put it to any use other than very naïve fiddling with it, good abstractions are indispensable. Flamebait titles, on the other hand, don't help it the smallest bit.
chriswarbo 12y ago
The metal is also made of category theory: http://conal.net/blog/posts/circuits-as-a-bicartesian-closed-category http://conal.net/blog/posts/circuits-as-a-bicartesian-closed...
serve_yay 12y ago
Well, OK. I have never seen anyone argue that functional programming is beneficial for performance reasons.
- kasey_junk 12y ago
  Really? I hear it all the time. The argument paraphrased is "we've maxed out what we can do in a serial fashion, so we need to start working concurrently and/or in parallel. Functional paradigms are much easier to reason about concurrency so we switch to them for the win!"
  - TheLoneWolfling 12y ago
    More than that. Functional programming in general tends to be better in terms of cache locality and number of dereferences required. Largely because it tends to encourage storing things "column-oriented". Ever looked at cache locality and the number of dereferences required in an overly-object-oriented program? Not pretty. Pointer chasing all over the place. Although this is more of a push away from OO programming than a push towards functional programming. OO implicitly assumes RAM - and in modern computers memory is decidedly not random-access.
    - kasey_junk 12y ago
      "Functional programming in general tends to be better in terms of cache locality" I've seen no evidence to support the "in general" part of this claim. I will agree that pointer chasing kills cache locality and that in some object systems dereferences have a bad impact on this. But in many functional systems you encounter the same problem with cache locality due to the nature of immutable data structures.
      - TheLoneWolfling 12y ago
        Hence the next paragraph: "Although this is more of a push away from OO programming than a push towards functional programming."
- 12y ago
chriswarbo 12y ago
Quick question: when the article calls a pair of mutually-recursive functions "corecursive", is this a commonly-used meaning of the term, or just a mistake (since they're certainly not corecursive in the coinductive sense)
- recursive 12y ago
  That's the meaning I use.
sklogic 12y ago
Stalin and MLton are sufficiently smart. Probably too smart in some cases.
tlarkworthy 12y ago
silicon is not really metal[1], it's rock. It's the most abundant element on earth & the universe, which I find interesting. Most of our planet and universe could be turned into a giant computer. [1] it's a metaloid
- ars 12y ago
  Silicon is not rock, rock is Silicon Dioxide, which is not the same thing. It's not the most abundant element on earth - Iron is. It's not even the most abundant on the earth's crust, oxygen is. (Silicon is second place.) And it's certainly not the most abundant in the universe - hydrogen is. Silicon is 8th.
  - tlarkworthy 12y ago
    Yes I should check my factoids before regurgitation. In atom counts there is more silicon than iron though, but more oxygen than either. Still interesting though that silicon is so plentiful. Doesn't matter if its bonded to an oxygen. I suppose the bonding explains why the oxygen count on earth is so high also. Oxygen is also (part of) rock.
    - ars 12y ago
      > Still interesting though that silicon is so plentiful. It makes sense if you look at https://en.wikipedia.org/wiki/Stellar_nucleosynthesis https://en.wikipedia.org/wiki/Stellar_nucleosynthesis since carbon, silicon, oxygen and iron are some of the main results. What's more odd is just how useful silicon-dioxide and iron is for building planets! Some of the most plentiful elements, just so happen to be perfect for making planets. And carbon with its amazing array of compounds no other element can match is also plentiful. Then you have iron which is the end result of this process, which just so happens to be perfect for building man-made things. It's strong, yet unlike the other strong elements, iron is also easy to work. And water - oxygen and hydrogen, very common elements. And water expands when it freezes, if not for that small small, non-obvious thing, life could not exist. The most abundant elements, the ones that don't need a supernova, just so happen to also be the most useful ones. Well, it's pretty obvious to me this universe was designed specifically for us.
Tloewald 12y ago
Surely the point is to use an effective language (for your particular definition of effective) and then optimize based on performance testing. Otherwise you lose time writing fast low level code that doesn't need to be fast or low level, and possibly never get to the important stuff.
- tjradcliffe 12y ago
  This. "No optimization without quantification" should be pasted up beside Knuth's laws of optimization. Performance testing and profiling will tell you where the code is really spending its time. Fix those problems. The past 20 years have shown us that naive optimization, which was never all that good, breaks completely in modern compilers, which often emit code that is optimized for the underlying architecture in ways that it's difficult for the programmer to anticipate. Like everyone who used to do a lot of hand optimization, in the late 90's I started seeing more and more cases where my clever tricks were making things worse, not better. So you can't just optimize by rote: you have to understand the specific problem you're dealing with.
ffn 12y ago
One can just as easily make the counter-argument people understand theory, not computer instructions. So the cleaner and more functional your code is, the easier (and faster) it becomes for other people to build on top of / around it. But that counter-argument only works given that the current application requires tons of people of work on your code. Just as the article's argument works only if you actually need to squeeze out those extra ms on your 1 machine. My only take away from this is "use the right tools for the right job".
dxbydt 12y ago
When you first wrote about how hadoop is a waste of time if you don't have multi-TB worth of data (http://www.chrisstucchio.com/blog/2013/hadoop_hatred.html http://www.chrisstucchio.com/blog/2013/hadoop_hatred.html ), I thought that was classic linkbait. And then I actually started seeing real benefits of not doing map-reduce for smaller datasets ( small = 1GB-1TB) & just sticking to plain old scala ( poso as opposed to pojo :) Similarly, this article seems linkbait on the surface but makes a lot of sense if you do anything performance intensive. I recently tried implementing a multi layer neural net in Scala - I eventually ended up rewriting your mappers as while loops & introduce some mutables, because at some point, all this FP prettiness is nice but not very performant. It looks good as textbook code for toy examples, but takes too long to execute. Am still a huge fan of FP, but nowadays I don't mind the occasional side effect & sprinkling some vars around tight loops. Its just much faster, & sometimes that is important too.
- codygman 12y ago
  I'd like to add that "sprinkling side effects & vars around tight loops" doesn't generalize to all languages. For isntance, GHC can optimize pure code MUCH more than impure code. Meaning that with purity you get increased performance in many cases.
chriswarbo 12y ago
Related links: Cost semantics http://lambda-the-ultimate.org/node/5021 http://lambda-the-ultimate.org/node/5021 Recent efforts to bring together "logical" CS (lambda calculus, type theory, etc.) and "combinatorial" CS (machine models, big-O, etc.) http://existentialtype.wordpress.com/2014/09/28/structure-and-efficiency-of-computer-programs/ http://existentialtype.wordpress.com/2014/09/28/structure-an...
mrwilliamchang 12y ago
Love the title. A more common mistake I notice people making is writing code that makes more memory allocations than necessary. # Bad: Makes an extra instantiation of a list with 1 in # it which then needs to be read x = set([1]) # Good x = set() x.add(1) Overall, I think it is important to remember that when you write a program that every step translates to a set of operations. And this applies to all kinds of programming, not just functional programming.
- TheLoneWolfling 12y ago
  Any half-decent optimizing compiler will turn those two implementations into the exact same assembly. That being said, that looks like Python source code - and as the default Python interpreter doesn't do much in the way of optimization, you are correct in that case. (Although I wonder about PyPy.)
Rusky 12y ago
Computers are "made of metal", and category theory does often lead far away from that reality. But that doesn't mean function calls are slow, or that we need Sufficiently Smart Compilers just to use map efficiently. What it means is that abstractions should be designed with both the use and the implementation in mind. One way to do that is "zero-cost abstractions" a la C++, where the abstractions are pretty minimal. Another way is things like stream fusion and tco, where it's easy to accidentally stray out of the efficiently representable subset. But there are a lot of ways to get abstractions that are both higher-level and "zero-cost" (generating the code you would have if you hadn't used them). For example, Python generators and C# iterators (coroutine-looking functions internally transformed into state machines) look a lot like Haskell higher-order functions but the benefits of laziness and stream fusion and tco are just built into the abstraction, rather than optimizations that may or may not happen, depending on the language/compiler. They also turn out to be more flexible, since the iterator state is reified. Another example is entity-component systems in game engines. You still get a nice abstraction of game-world objects composed from behaviors, like you might see in an OO hierarchy, but the cache behavior is vastly improved and the behaviors are again more flexible.
sitharus 12y ago
When I started programming it was ZX Spectrum BASIC. No abstractions other than some symbols. Then I moved on to Perl, then PHP and eventually C# - all increasing abstraction from the hardware, but all mutable state and based off how hardware works. Recently I've started moving on to F# and Haskell, and it's really opened my eyes. While computers keep getting faster the humans who input the programs do not. While programming is about getting a computer to do things the most important part is making it do what you want it to to. Anything that helps humans reason about what the computer will do - rather than exactly how - is a good thing in my book.

80 points by stakent 12y ago

I'm a little confused: the author is speaking of "metal" but isn't writing assembly. (And I'm a little snarky today.)

yzzxy 12y ago

I'm no expert on these matters, but it seems a bit ridiculous to call out entire swaths of the programming/computer science world while referencing the JVM as a benchmark.

cantankerous 12y ago
I think the critique is with the implied (but not always understood) overhead of some of FP's common types of abstraction.
yummyfajitas 12y ago
I'm (author here) not "calling them out" - most people doing research in FP are well aware of these issues. This is aimed at people like me who merely implement stuff in those languages. Also, most of the Scala code I'm describing compiles down to very straightforward instructions that would be the same on almost any compiler. If you can show me any other language which will handle a linked list as rapidly as the JVM handles an array, I'll be extremely impressed.
- dons 12y ago
  > handle a linked list as rapidly as the JVM handles an array A linked list is not an array. Particular operations will have different complexities. One data structure is not "more rapid" than another.
  - kasey_junk 12y ago
    This is precisely the kind of thinking people need to be careful about. Some data structures are more rapid than others even with more complex operations, because they conform to the reality of the underlying hardware better.
    - codygman 12y ago
      Can you please provide some examples? It would be much appreciated.
      - noblethrasher 12y ago
        http://youtu.be/YQs6IC-vgmo http://youtu.be/YQs6IC-vgmo Stroustrup describes why –on modern hardware– vectors are faster than linked list for insertion and deletion.
- comex 12y ago
  But your post makes more claims than merely computers not being able to arbitrage data structures. In your first example, while I don't have any experience with Scala, any competent compiler for C++, Haskell, Rust, etc. will inline a function like "map", so there is no "function call overhead" whatsoever. (This example is too simple to benefit from stream fusion as such.) The resulting machine code will look fairly similar; if there is a performance difference, it would be far more subtle than your 10x, and would probably have to do with whether the map implementation in question is specialized for the Array->Array case. One that is will allocate the right number of elements up front and perhaps even skip bounds checks that the compiler might or might not be able to optimize out from the explicit version, but one that isn't will not only include bounds checks but repeatedly have to grow the result array and copy the elements so far to the new allocation.
  - yummyfajitas 12y ago
    Yes, in the conclusion I remark that a Sufficiently Smart Compiler can do all of this. I don't know that either Haskell or C++ compilers will inline your maps, but if so, that's very cool. And yes, specializing for the Array -> Array case and eliminating bounds checks will be necessary to get real performance.

dons 12y ago

Title is misleading. This is about some Scala microbenchmarks. There is no CT or metal here.

jcromartie 12y ago

He keeps using the word "pointer" ...

cantankerous 12y ago

Good read. Minor quibble: I'm not sure calling Julia a functional language is really a fair statement. Yes it's LISP-like, but if you want to go there, Ruby is a LISP-like language in the same ways Julia is. I don't really encounter many folks making the claim that Ruby is a functional language.

dragonwriter 12y ago
> I don't really encounter many folks making the claim that Ruby is a functional language. Ruby is a multiparadigm language, and functional is one of the important paradigms it supports. A rather popular essay on Ruby from nearly a decade ago (surprising for me to discover that it was that long ago!) was "Why Ruby is an acceptable LISP" [1] Its true that recently much of the recent focus on functional languages has been on statically-typed and/or pure functional languages, which neither Ruby nor Lisp is... [1] http://www.randomhacks.net/2005/12/03/why-ruby-is-an-acceptable-lisp/ http://www.randomhacks.net/2005/12/03/why-ruby-is-an-accepta...

rollo 12y ago

What I took from this post, is that we should keep working on compilers. They could provably optimize away most of the performance issues and move us closer to doing category theory instead of dealing with the metal.

cantankerous 12y ago
Agree with you there. Programmers need to understand the semantics of their language and use it to their advantage. I think this is especially the case in functional languages, especially in Haskell, where two seemingly similar pieces of code can execute in different ways, especially given the presence of lazy semantics. Knowing how to write efficient code in your language can be significantly different than knowing how to write code that works, depending on the language.
- sanderjd 12y ago
  But that's why the abstraction is leaky. You no longer need to think at just the level of the abstraction, but also at the level of the implementation of the abstraction. This is fine, but it's one of the reasons abstractions tend to be less useful than they seem. If you're always thinking about what's really going on, you might as ditch the abstraction and only think about what's really going on. The less you have to think about its implementation, the better an abstraction is.
  - codygman 12y ago
    You might as well ditch the abstraction? So you program everything in assembler then? OOP is leaky, maybe we should ditch it. The ADT and typeclasses in Haskell are much more general and well-behaved than objects in my experience.
    - sanderjd 12y ago
      I sort of buried the lede in my comment... My main point was that while all abstractions are leaky, it's reasonable to judge them on the relative extent of their leakiness.

deleted 12y ago

[deleted]

dschiptsov 12y ago

- There is nothing absolute in the world. - Metal rails are.

minimax 12y ago

The most important thing here is to measure. Always measure. It doesn't matter what you think is going to be fast or not. The combination of super smart (or not so smart) compilers, multi-level hierarchal caches, pipelining, branch (mis)prediction, etc means you can't just look at a piece of code in a high level language and know how fast it will be. You always have to run the code and measure how long it takes. For anything where you really care about latency, measure.

TheLoneWolfling 12y ago
...And then have something in an entirely unrelated set of code change and make the code you oh-so-carefully benchmarked become half as fast. Because you just caused cache line aliasing, or your pushed your function code across a boundary, or you're now killing your branch predictor, or, or... At this point, in any optimized language benchmarking parts of your code is practically useless for finer optimization. There are some things you will pick up on, sure, but trying to squeeze the last drop of performance out of your code? Good luck. Too many global interactions. I mean: even GCC doesn't generate statistically significantly faster code on O3 versus O2.

kyllo 12y ago

Computers are metal but programming languages are for humans. The purpose of functional abstractions is primarily to help humans produce correct code, not necessarily to optimize for speed. Referentially transparent functions, immutable data and type checking are meant to provide guarantees that reduce complexity, make a program easier to reason about and help stop the programmer from introducing costly and dangerous bugs. It doesn't matter how fast your "fugly imperative code" is, if it's incorrect. And the lesson we've learned the hard way over and over again is that humans are just not smart enough to reliably write correct fugly imperative code.

kasey_junk 12y ago
I'm not sure I buy your argument, but even if I did, there is no evidence as of yet that says that fugly functional abstractions provide for lower error rates. Further, performance is part of correctness for nearly any real word example.
- DanWaterworth 12y ago
  > there is no evidence as of yet that says that fugly functional abstractions provide for lower error rates. Sure there is. Compare the incidence of buffer overflows in C programs vs Haskell ones. > performance is part of correctness for nearly any real word example. No it's not. See the definition of correctness [1]. [1] http://en.wikipedia.org/wiki/Correctness_%28computer_science%29 http://en.wikipedia.org/wiki/Correctness_%28computer_science...
  - dragonwriter 12y ago
    In most real world software, performance constraints are part of the specification, and thus, performance is part of correctness by the definition you cite. (And where they aren't part of the formal specification, it often is later discovered that that was simply a failure of requirements gathering/analysis, in that the specification did not completely capture the expectations of the entity that the software was being built for.)

deleted 12y ago

[deleted]

bkeroack 12y ago

"No, don't take away my beautiful abstractions!"

exDM69 12y ago

If you take a look at how the GHC Haskell compiler (A "Sufficiently Smart Compiler(tm)" in my opinion) works, for example, it is not naively pushing allocating objects, creating thunks and emitting trampoline code. Instead, it analyzes the program structures from graphs and emits rather efficient machine code in the end. Not too dissimilar from what your native code emitting C compiler does. If you look at the machine code for something as "stupid" as the Haskell example below, the output object code does not resemble the semantics of the source program at all. (it's not quite as efficient as the same from a C compiler, but still proves a point) foreign export ccall fac :: Int -> Int fac :: Int -> Int fac n = foldl (*) 1 . take n $ [1..] Compiler and programming language research is a very important topic that yields real performance benefits as well as better programmer productivity. That includes using Category theory to reason about program correctness. If you're interested in how the Haskell compiler works, "Implementation of Functional Programming languages" is a good (albeit a bit outdated) starting point. The whole book is freely available here: http://research.microsoft.com/en-us/um/people/simonpj/papers/slpj-book-1987/ http://research.microsoft.com/en-us/um/people/simonpj/papers... I do agree with the title a bit, though. Some of our computer programming environments are just ridiculously slow. Being slow also means "consumes a lot of power" which is important when more and more computers are powered by batteries.

dinglefuk 12y ago
It's amazing the author could be so naive, in my opinion.
cantankerous 12y ago
Seconding on the SPJ book! It's a solid start for learning about the particulars of FP implementation.
cpa 12y ago
The OP (which I totally agree with!) also states: > Such a compiler could properly determine that intermediate steps are unused, merge them (e.g. translate x.map(f).map(g) to x.map(x => g(f(x)))) Ironically, GHC does that already[0], and will also do TCO. [0] http://metagraph.org/papers/stream_fusion.pdf http://metagraph.org/papers/stream_fusion.pdf

nine_k 12y ago

Aircraft are made of metal, not fluid dynamics. Rockets are made of metal, not ballistics equations. Nuclear bombs are made of metal, not quantum theory. Well, metal is important, but to put it to any use other than very naïve fiddling with it, good abstractions are indispensable. Flamebait titles, on the other hand, don't help it the smallest bit.

chriswarbo 12y ago

The metal is also made of category theory: http://conal.net/blog/posts/circuits-as-a-bicartesian-closed-category http://conal.net/blog/posts/circuits-as-a-bicartesian-closed...

serve_yay 12y ago

Well, OK. I have never seen anyone argue that functional programming is beneficial for performance reasons.

kasey_junk 12y ago
Really? I hear it all the time. The argument paraphrased is "we've maxed out what we can do in a serial fashion, so we need to start working concurrently and/or in parallel. Functional paradigms are much easier to reason about concurrency so we switch to them for the win!"
- TheLoneWolfling 12y ago
  More than that. Functional programming in general tends to be better in terms of cache locality and number of dereferences required. Largely because it tends to encourage storing things "column-oriented". Ever looked at cache locality and the number of dereferences required in an overly-object-oriented program? Not pretty. Pointer chasing all over the place. Although this is more of a push away from OO programming than a push towards functional programming. OO implicitly assumes RAM - and in modern computers memory is decidedly not random-access.
  - kasey_junk 12y ago
    "Functional programming in general tends to be better in terms of cache locality" I've seen no evidence to support the "in general" part of this claim. I will agree that pointer chasing kills cache locality and that in some object systems dereferences have a bad impact on this. But in many functional systems you encounter the same problem with cache locality due to the nature of immutable data structures.
    - TheLoneWolfling 12y ago
      Hence the next paragraph: "Although this is more of a push away from OO programming than a push towards functional programming."
12y ago

chriswarbo 12y ago

Quick question: when the article calls a pair of mutually-recursive functions "corecursive", is this a commonly-used meaning of the term, or just a mistake (since they're certainly not corecursive in the coinductive sense)

recursive 12y ago
That's the meaning I use.

sklogic 12y ago

Stalin and MLton are sufficiently smart. Probably too smart in some cases.

tlarkworthy 12y ago

silicon is not really metal[1], it's rock. It's the most abundant element on earth & the universe, which I find interesting. Most of our planet and universe could be turned into a giant computer. [1] it's a metaloid

ars 12y ago
Silicon is not rock, rock is Silicon Dioxide, which is not the same thing. It's not the most abundant element on earth - Iron is. It's not even the most abundant on the earth's crust, oxygen is. (Silicon is second place.) And it's certainly not the most abundant in the universe - hydrogen is. Silicon is 8th.
- tlarkworthy 12y ago
  Yes I should check my factoids before regurgitation. In atom counts there is more silicon than iron though, but more oxygen than either. Still interesting though that silicon is so plentiful. Doesn't matter if its bonded to an oxygen. I suppose the bonding explains why the oxygen count on earth is so high also. Oxygen is also (part of) rock.
  - ars 12y ago
    > Still interesting though that silicon is so plentiful. It makes sense if you look at https://en.wikipedia.org/wiki/Stellar_nucleosynthesis https://en.wikipedia.org/wiki/Stellar_nucleosynthesis since carbon, silicon, oxygen and iron are some of the main results. What's more odd is just how useful silicon-dioxide and iron is for building planets! Some of the most plentiful elements, just so happen to be perfect for making planets. And carbon with its amazing array of compounds no other element can match is also plentiful. Then you have iron which is the end result of this process, which just so happens to be perfect for building man-made things. It's strong, yet unlike the other strong elements, iron is also easy to work. And water - oxygen and hydrogen, very common elements. And water expands when it freezes, if not for that small small, non-obvious thing, life could not exist. The most abundant elements, the ones that don't need a supernova, just so happen to also be the most useful ones. Well, it's pretty obvious to me this universe was designed specifically for us.

Tloewald 12y ago

Surely the point is to use an effective language (for your particular definition of effective) and then optimize based on performance testing. Otherwise you lose time writing fast low level code that doesn't need to be fast or low level, and possibly never get to the important stuff.

tjradcliffe 12y ago
This. "No optimization without quantification" should be pasted up beside Knuth's laws of optimization. Performance testing and profiling will tell you where the code is really spending its time. Fix those problems. The past 20 years have shown us that naive optimization, which was never all that good, breaks completely in modern compilers, which often emit code that is optimized for the underlying architecture in ways that it's difficult for the programmer to anticipate. Like everyone who used to do a lot of hand optimization, in the late 90's I started seeing more and more cases where my clever tricks were making things worse, not better. So you can't just optimize by rote: you have to understand the specific problem you're dealing with.

ffn 12y ago

One can just as easily make the counter-argument people understand theory, not computer instructions. So the cleaner and more functional your code is, the easier (and faster) it becomes for other people to build on top of / around it. But that counter-argument only works given that the current application requires tons of people of work on your code. Just as the article's argument works only if you actually need to squeeze out those extra ms on your 1 machine. My only take away from this is "use the right tools for the right job".

dxbydt 12y ago

When you first wrote about how hadoop is a waste of time if you don't have multi-TB worth of data (http://www.chrisstucchio.com/blog/2013/hadoop_hatred.html http://www.chrisstucchio.com/blog/2013/hadoop_hatred.html ), I thought that was classic linkbait. And then I actually started seeing real benefits of not doing map-reduce for smaller datasets ( small = 1GB-1TB) & just sticking to plain old scala ( poso as opposed to pojo :) Similarly, this article seems linkbait on the surface but makes a lot of sense if you do anything performance intensive. I recently tried implementing a multi layer neural net in Scala - I eventually ended up rewriting your mappers as while loops & introduce some mutables, because at some point, all this FP prettiness is nice but not very performant. It looks good as textbook code for toy examples, but takes too long to execute. Am still a huge fan of FP, but nowadays I don't mind the occasional side effect & sprinkling some vars around tight loops. Its just much faster, & sometimes that is important too.

codygman 12y ago
I'd like to add that "sprinkling side effects & vars around tight loops" doesn't generalize to all languages. For isntance, GHC can optimize pure code MUCH more than impure code. Meaning that with purity you get increased performance in many cases.

chriswarbo 12y ago

Related links: Cost semantics http://lambda-the-ultimate.org/node/5021 http://lambda-the-ultimate.org/node/5021 Recent efforts to bring together "logical" CS (lambda calculus, type theory, etc.) and "combinatorial" CS (machine models, big-O, etc.) http://existentialtype.wordpress.com/2014/09/28/structure-and-efficiency-of-computer-programs/ http://existentialtype.wordpress.com/2014/09/28/structure-an...

mrwilliamchang 12y ago

Love the title. A more common mistake I notice people making is writing code that makes more memory allocations than necessary. # Bad: Makes an extra instantiation of a list with 1 in # it which then needs to be read x = set([1]) # Good x = set() x.add(1) Overall, I think it is important to remember that when you write a program that every step translates to a set of operations. And this applies to all kinds of programming, not just functional programming.

TheLoneWolfling 12y ago
Any half-decent optimizing compiler will turn those two implementations into the exact same assembly. That being said, that looks like Python source code - and as the default Python interpreter doesn't do much in the way of optimization, you are correct in that case. (Although I wonder about PyPy.)

Rusky 12y ago

Computers are "made of metal", and category theory does often lead far away from that reality. But that doesn't mean function calls are slow, or that we need Sufficiently Smart Compilers just to use map efficiently. What it means is that abstractions should be designed with both the use and the implementation in mind. One way to do that is "zero-cost abstractions" a la C++, where the abstractions are pretty minimal. Another way is things like stream fusion and tco, where it's easy to accidentally stray out of the efficiently representable subset. But there are a lot of ways to get abstractions that are both higher-level and "zero-cost" (generating the code you would have if you hadn't used them). For example, Python generators and C# iterators (coroutine-looking functions internally transformed into state machines) look a lot like Haskell higher-order functions but the benefits of laziness and stream fusion and tco are just built into the abstraction, rather than optimizations that may or may not happen, depending on the language/compiler. They also turn out to be more flexible, since the iterator state is reified. Another example is entity-component systems in game engines. You still get a nice abstraction of game-world objects composed from behaviors, like you might see in an OO hierarchy, but the cache behavior is vastly improved and the behaviors are again more flexible.

sitharus 12y ago

When I started programming it was ZX Spectrum BASIC. No abstractions other than some symbols. Then I moved on to Perl, then PHP and eventually C# - all increasing abstraction from the hardware, but all mutable state and based off how hardware works. Recently I've started moving on to F# and Haskell, and it's really opened my eyes. While computers keep getting faster the humans who input the programs do not. While programming is about getting a computer to do things the most important part is making it do what you want it to to. Anything that helps humans reason about what the computer will do - rather than exactly how - is a good thing in my book.