Agreed on the benchmarks – that's the next (and last) part on the list I'm going to do with this series.
And yes, of course, at some point, constant factors break into applications. Would it be better if add in a short comment on "practically O(1) for non-HPC applications", or would you phrase it differently to give it better context?
I understand your concern, but I don't really think the problem is within Clojure people: When I started out explaining the structure to other people and that most operations have O(log n) runtime, people dismissed Clojure as being too slow for practical purposes. Part of this is because programmers, not Clojure devs in particular, connotate O(log n) with "much slower than O(1)". However, this data structure is incredibly much faster than the "O(log n)" people are generally used to.
And this is the problem. As you yourself say, most programmers usually associate/assume "Big-O notation is intended to describe how the time required for an operation grows as the number of items being handled gets large".
But formally, this is not the case at all. O(g(x)) tells you the that the worst case input to the algorithm will require less operations (usually operations, sometimes memory or other things) than the function g multiplied by some positive constant. g is usually determined by the size of the input. (This definition is also simplified somewhat, but it illustrates the problem)
We can say that ArrayLists.add have O(n) runtime and that quicksort have O(n²) runtime, but they both also have O(n³) and O(n!) runtime.
In addition, Big-O does not describe how the algorithm runs in the average case, or how frequent the worst case is. In and of itself, the Big-O notation tells us almost nothing about an algorithm – you barely conclude anything from it. I guess that is part of why it has become this very simplified term with a very wibbly-wobbly definition from time to time.
So when you're saying that calling it "practically O(1)" is lying, I agree if this was in an academic context. But for the average programmer (regardless of language!), O(g(x)) is usually thought of as the "worst case runtime for an algorithm". Since the actual runtime is – well – effectively constant, I considered it okay.
---
That being said, I have formally explained the persistent vector if you're interested in the academic version. The background chapter in http://hypirion.com/thesis.pdf should cover it.
That's a red herring: You're asking why the majority of software is written in imperative languages instead of functional ones, which is a very complex question with very many factors. It is not an argument which invalidates nor counters the author's claim: Namely that "mostly functional languages" is unfeasible and only increases the bugs caused by side effects.
Constant time in practise is a notable difference from saying constant time.
I can always sort a 32-bit int array in worst case linear time using counting sort, which in theory is better than the worst case runtime of quicksort, O(n²). Is it better in practise? Of course not, the constant factor is just too high, both for time and memory.
I've managed to do the opposite: Scala didn't stick, Clojure did. I guess there's some subjective reason why or why not Clojure/Scala would stick with someone.
However, it's false that Clojure doesn't have a company behind it: Cognitect is certainly backing up Clojure by developing ClojureScript and Clojure itself, Clojure consulting, the Datomic database and the Pedestal "framework".
And if you ask me, its just so good that we haven't needed a revision in 20 years.
What about threading and/or concurrency? CLTL doesn't mention it, yet it is something which is now considered a requirement for real, general purpose programming languages.
Could you elaborate on how generics makes code less safe? In my experience, the lack of generics is much more type unsafe, as you often have to do casts at runtime (and handle them) when you have to implement your own data structures. In contrast, languages with generics handle those at compile time.
Just for reference, a single goroutine has a 8 kb stack size. Having one million of these things in memory at once would require 8 Gb of memory. Obviously, the scheduler kicks in, but 8 kb chunks of memory still has to be assigned and freed for every routine started and stopped.
Using val King = 13; val Queen = 12; in Scala is not equivalent with using Clojure keywords, as their printed variant will be 13 and 12, not :king and :queen. Reading debugging output or logs would force you to manually convert those values.
Ordering for free is valuable, I guess, but it sort of depends on the situation. Sometimes face cards are worth 10, other times they are worth 11, 12, 13. If you use val King = 10;, then it suddenly is impossible to distinguish between face cards and tens.
I do agree that the structure is influenced by the paper, so I've added that in. I don't agree that they are "virtually identical" however, because there are significant differences leading to a lot of performance improvements (never any hash collisions, insertion and removal only at the end, resulting in perfect balancing, etc) and, as swanodette mentioned, Bagwell himself mentioned that they were pioneered by Hickey.
> Rich goes through this in one of his talks but I don't recall which.
Author here: I think you talk about the persistent hashmaps, not the persistent vectors. I've been looking for papers explaining Clojure's persistent collections, and Bagwell seems to cover the hash maps and hash sets quite well. However, I've not seen a paper on the persistent vectors, which was quite a bummer, and that was the reason I started explaining them in the first place.
If you have a reference to a paper explaining something similar (or the actual implementation), I'd love to put it in the post for others.
To get an even better explanation on what the word "simple" means and what it derives from, I would recommend "Simplicity Ain't Easy" by Stuart Halloway[1]. While it is very similar to "Simple made Easy", it focuses a lot more on the etymology of the words "simple" and "complex" and how people misuse the word.
Generics may not be the correct solution, but I would really like a way to make collections which are general enough to be used by any datatype. As of now, I cannot do that without doing the typical `interface{}` approach.
The built-in data structures + channels are able to handle this, but if I just want a set of elements, what do I do? Make a `map[foo] bool`? If I see such a piece of code in an unfamiliar code base, I have no idea whether to test for key existence or whether I have to test whether the bool is true. A generic set would leave me puzzled and type unsafe[1]: What types could possibly exist in this set? A set of foos is not that hard to comprehend, and is in fact very much more straightforward to understand than a generic set, which in unfamiliar code may contain anything, or a mapping from foos to bools.
[1]: Rob Pike mentions in http://www.youtube.com/watch?feature=player_detailpage&v... that type safety is of high importance for Golang, but how does one achieve that if all the different datatypes I implement/need use `interface {}` where I have to cast all values afterwards? That seems very type unsafe, from where I stand.
Well, there are some comments just about that in the "coming soon" part, and it seems that the selling point is about making multiplayer easier for you compared to Minecraft.
Whereas you have to host a Minecraft server yourself (or host a world on a LAN) in order to play multiplayer, Skycraft doesn't require you to do that. All you have to do is share a link with your friends. In addition, you can "[i]nvite anyone to fly or walk around in your world in spectator-mode", which I optimistically intepret as "walk around in my world without buying the game". (Of course, that's my take on it.)
Curiously, NTNU/NTH got a similar tradition which officially started in 1914, 8-11 years earlier[1, 2]. I wonder if these rings or the "identity crises" (the NTH-ring was designed to give former NTH (now engineering) students an identity, whereas this iron ring represents the obligations and ethics) have some correlation or not.
In these competitions, it's about implementing a solution as fast as possible, while still get it working under the time limit (5/8 minutes). It's mostly about having the right idea and implement it.
In very many cases, you would like to be able to manipulate and play with algorithms and have efficient mutable data structures. For this, Java/C++ (Essentially C with data structures) is very suitable.
However, in some cases, you'd like to perform advanced simulations, mathematical calculations or manipulations where immutable data structures are more suitable. In those cases, you would LIKE to have magic: Arbitrary numbers, ratios, (efficient) immutable data structures and a more functional style would not only eliminate work, but also reduce the amount of errors you're likely to do.
The important part is that the implementation uses the right idea, not that the implementation is fast. Usually it's handy with a lower-level language to implement the algorithm right, but at times, a higher level (functional) language is better when it comes to implementation speed.
This is currently not possible with lein (bug/enhancement), but will be with 2.1.0. See #966[1] for details. As a workaround, any project dependent of Clojure 1.5.0 will utilize that for the repl. So when in a project using 1.5.0, the repl will be 1.5.0 too.
There's a lot of new small improvements in this update which are great for Clojure users, but the fundamental difference between 1.4 and 1.5 is the reducer library which was implemented. It's added mostly for performance reasons: By using this library, you will utilize Fork/Join in Java, but with a functional interface instead of the "gory" one. Very interesting, because the complexity of a typical `(reduce (map ...))` won't change, and you're suddenly utilizing all the cores on your computer. Rich Hickey had a talk about the new Reducers library[1], and I'd recommend you to see it, as it gives you a good understanding of how it works (and why it was implemented that way).
Another slightly interesting thing is the sudden enhancement to read-eval and EDN[2]. That's mainly because of the rough weather Ruby/Rubygems was in with the YAML-exploits, which caused a heated discussion on how the Clojure reader should act by default[3][4].
And yes, of course, at some point, constant factors break into applications. Would it be better if add in a short comment on "practically O(1) for non-HPC applications", or would you phrase it differently to give it better context?