Computers are made of metal, not category theory
chrisstucchio.com
chrisstucchio.com
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..]
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...
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.
> 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.
And the entire resulting object file:
I suspect this is a disassembly of the .o file, or maybe it's some runtime dynamic linking thing? There'll be a fixup table somewhere and this stuff will be sorted out before it's executed.
- is tailored to the characteristics of extremely parallel computers which spend years unconsciously learning somewhat pointless statistical micro-rules, and then layer a formal grammar on top of that (both layers need to be correctly maintained); and
- sometimes, due to ambiguity, can't be parsed without understanding the nature of what is being referred to (which can be anything one can imagine).
The other is trying to transform expressions which are already formally specified (with semantics to a large extent based on computers' whims rather than humans', even in very high-level languages) into a more efficient form. Doing this as well as humans can could require AI-ish "reasoning" about parts of the program, but it's basically a different task. There's no need to understand everything in the world to know what a Haskell program does.
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.
Meaning that with purity you get increased performance in many cases.
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.
(I'm not trying to be snarky here, but I've studied category theory and it seems like a whole lot of effort for very little benefit. On the other hand, it's fun to figure out the metal. (Although silicon's not exactly a metal...))
Heh heh. Having worked mostly with math professors, I would say the code they write almost exclusively belongs to the car-mechanic school. Math professors never deck up their code with CT. The majority of the time a math prof has to write code, its to do heavy-duty applied math, engg stuff ( solve pde's, fluid mechanics, EE math, fourier transforms, gradients etc. ) or to display some cool visualization to the students ( here's how a vector space looks! here is what happens when you apply linear transformation!! here are all the elements of a quotient group!!! ) - those tend to be done in Matlab/Mathematica/Maple/Gap...and these tools have zero CT. The applied stuff tends to use netlib, gams, gsl, colt, apache math...mostly a lot of gsl these days...again no CT there. Most of them are very happy to declare giant matrices & happily mutate away.
I'm sure you get it, but just for the record, by math-professor I meant "very focused on things that to most people seem incredibly abstract", with a side of "passionate about solving intellectual challenges for their own sake".
http://conal.net/blog/posts/circuits-as-a-bicartesian-closed...
Cost semantics 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-an...
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.
A linked list is not an array. Particular operations will have different complexities. One data structure is not "more rapid" than another.
Stroustrup describes why –on modern hardware– vectors are faster than linked list for insertion and deletion.
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.
And yes, specializing for the Array -> Array case and eliminating bounds checks will be necessary to get real performance.
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-accepta...
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.
Further, performance is part of correctness for nearly any real word example.
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...
(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.)
Business requirements are not the same thing as program correctness.
And of course, while we're talking about business requirements, there is always project speed and budget size to account for. When optimizing for program running time and memory cost, you don't want to blow up the project's running time and dollar cost. Productivity is a huge reason why abstractions need to exist.
It's true that 1 particular instance of a functional language removes 1 particular class of problems from another non functional language. But there is no evidence that these error rates are lower in general because other classes of errors creep in. For instance, space leaks due to laziness are a class of error you are unlikely to encounter in C, but are common in Haskell.
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.
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)
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.)
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.
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".
(And I'm a little snarky today.)
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.
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!"
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.
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.
Haskell (or any other pure functional language) can often make it viable for you to write code that is much more performant than what you'd have writen in C (or any ohter mainly imperative language). Mainly so if the problem is paralelizable and can use asynchronous IO.
Done. Now you've seen somebody arguee that functional programming is benefical for performance reasons.
Of course, the previous statement is not true if you have unlimitted budget and time. At least not yet.
[1] it's a metaloid
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.
It makes sense if you look at 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.
- There is nothing absolute in the world.
- Metal rails are.