I've now had a quick look at this too. Aside from the grammatical and spelling nitty-gritty, there are some larger scale concerns, ones that unfortunately go to the heart of the entire "literate programming" concept.
Namely, at the start it jumps very quickly into a red-black tree implementation without really motivating it. Now, it mentions wanting a binary search tree, and that a red-black tree maintains certain invariants that limit how unbalanced it can get, but the explicit motivation for this (avoiding the linear worst-case performance of a fully unbalanced tree in favor of a tree that gives guaranteed logarithmic bounds on its operations, other than the obviously-linear-best-case full traversal of course). More significantly, there's no explanation for introducing a binary search tree in the first place -- and mention of Java but no direct motivation for not using java.util.TreeMap or similar instead of rolling our own. There's a brief mention of immutability and persistence, without the connecting thoughts -- namely we want clojure to have an immutable sorted-map type, and while we could use a factory function that spits out (Collections/unmodifiableMap (doto (TreeMap.) #(doseq [[k v] kvs] (.put % k v)))), every assoc would require copying the entire map, in linear time and space, etc. etc. etc., vs. using a "persistent" data structure specifically designed for structure sharing with modified versions. And then of course the overarching purpose of Clojure itself isn't even given, let alone why it has sorted-map, and why it's an immutable sorted-map ... I know, I know, tall order, right? I hope you're at least thinking about this stuff for the eventual final version, though. (And why start with the red-black tree, anyway? After introducing Clojure I'd probably start with getting a minimalist implementation that is runnable first -- so the compiler and evaluator and repl and s-expressions, lists and any other infrastructure these need under the hood, and whatever else is needed for this -- some of the numerics stuff, symbols and symbol interning, etc.; then with already a basic Lisp environment in play, adding the other functions and data structures in core that weren't needed just to get things up and running with a basically functional repl. Maybe sorted-map (or a persistent immutable binary search tree implemented in Java) is one of the things that is needed to get the compiler working, but if so, I'd think a truly literate version is going to explain what Clojure is, and then how we're gonna implement it, and then details of the planned compiler implementation, and why this needs a persistent immutable binary search tree, and how that will also be useful later for making the user-visible sorted-map and sorted-set features, and THEN get down into the weeds of how we make a persistent immutable binary search tree, how we can avoid the linear worst-time behavior of unbalanced trees by ensuring the tree never gets too far out of balance (and even what "balanced" means in this context), and that red-black trees are among several kinds that have such properties, and then why red-black trees were chosen over, say, two-three trees, etc. Of course, you might need to ask Rich some questions to get some of this information. It's pretty clear how a persistent immutable balanced search tree is needed to make sorted-map and sorted-set work well and in a pure-functional way; it may or may not be obvious on close examination that a red-black tree is a superior choice over the alternatives; maybe it isn't and Rich's choice was more or less arbitrary, or based on what he already knew how to implement or had a reference handy for; or Rich tried several alternatives and found that he could make a Java implementation of a persistent, immutable red-black tree faster than any of the others, or better at structure-sharing; to really be sure, unless it really does become obvious on looking into the code itself why, you'd have to ask Rich why he chose red-black trees for this job. And there will probably be many other similar points in the code where there's an implementation choice that may not be obvious without Rich's input. And all of them will need some explanation, if the program is to be truly literate -- even if there turn out to be cases where that explanation will be something like "tests showed that X and Y were equally good alternatives for implementing this, so Rich just flipped a coin and it came up tails so he used Y". :) -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
