Channels ▼
RSS

Parallel

The Case for D


A Word on The Standard Library

This subject is a bit sensitive politically because, as mentioned, there are two full-fledged libraries that can be used with D, Phobos and Tango. I only worked on the former so I will limit my comments to it. For my money, ever since the STL appeared, the landscape of containers+algorithms libraries has forever changed. It's changed so much, in fact, that every similar library developed after the STL but in ignorance of it runs serious risks of looking goofy. (Consequently, a bit of advice I'd give a programmer in any language is to understand the STL.) This is not because STL is a perfect library -- it isn't. It is inextricably tied to the strengths and weaknesses of C++, for example it's efficient but it has poor support for higher-order programming. Its symbiosis with C++ also makes it difficult for non-C++ programmers to understand the STL in abstract, because it's hard to see its essence through all the nuts and bolts. Furthermore, STL has its own faults, for example its conceptual framework fails to properly capture a host of containers and ways of iterating them.

STL's main merit was to reframe the entire question of what it means to write a library of fundamental containers and algorithms, and to redefine the process of writing one in wake of the answer. The question STL asked was: "What's the minimum an algorithm could ever ask from the topology of the data it's operating on?" Surprisingly, most library implementers and even some algorithm pundits were treating the topic without due rigor. STL's angle put it in stark contrast to a unifying interface view in which, for example, it's okay to unify indexed access in arrays and linked lists because the topological aspect of performing it can be written off as just an implementation detail. STL revealed the demerit of such an approach because, for example, it's disingenuous to implement as little as a linear search by using an unifying interface (unless you enjoy waiting for quadratic algorithms to terminate). These are well-known truths to anyone serious in the least about algorithms, but somehow there was a disconnect between understanding of algorithms and their most general implementations in a programming language. Although I was conversant with algorithm fundamentals, I can now say I had never really thought of what the pure, quintessential, Platonic linear search is about until I first saw it in the STL 15 years ago.

That's a roundabout way of saying that Phobos (places to look at in the online documentation: std.algorithm and std.range) is a lot about the STL. If you ask me, Phobos' offering of algorithms is considerably better than STL's, and for two reasons. One, Phobos has the obvious advantage of climbing on the shoulders of giants (not to mention the toes of dwarfs). Two, it uses a superior language to its fullest.

Ranges are Hot, Iterators are Not. Probably the most visible departure from the STL is that there are no iterators in Phobos. The iterator abstraction is replaced with a range abstraction that is just as efficient but offers vastly better encapsulation, verifiability, and abstraction power. (If you think about it, none of an iterator's primitive operations are naturally checkable. That's just bizarre.) Code using ranges is as fast, safer, and terser than code using iterators -- no more for loop that's too long to contain in one line. In fact, thinking and coding with ranges is so much terser, new idioms emerge that may be thinkable but are way too cumbersome to carry through with iterators. For example, you might have thought of a chain function that iterates two sequences one after another. Very useful. But chain with iterators takes four iterators and returns two, which makes it too ham-fisted to be of any use. In contrast, chain with ranges takes two ranges and returns one. Furthermore, you can use variadic arguments to have chain accept any number of ranges -- and all of a sudden, we can avail ourselves of a very useful function. chain is actually implemented in the standard module std.range. As an example, here's how you can iterate through three arrays:


<b>int</b>[] a, b, c;
...
<b>foreach</b> (e; chain(a, b, c))
{
    ... use e ...
}

Note that the arrays are not concatenated! chain leaves them in place and only crawls them in sequence. This means that you might think you could change elements in the original arrays by means of chain, which is entirely true. For example guess what this code does:


sort(chain(a, b, c));

You're right -- the collective contents of the three arrays has been sorted, and, without modifying the size of the arrays, the elements have been efficiently arranged such that the smallest come in a and so on. This is just a small example of the possibilities offered by ranges and range combinators in conjunction with algorithms.

Laziness to Infinity and Beyond. STL algorithms (and many others) are eager: by the time they return, they've finished their job. In contrast, Phobos uses lazy evaluation whenever it makes sense. By doing so, Phobos acquires better composition capabilities and the ability to operate with infinite ranges. For example, consider the prototypical higher-order function map (popular in functional programming circles, not to be confused with the homonym STL data structure) that applies a given function to each element in a range. If map were insisting to be eager, there'd be two problems.

  • First, it would have to allocate new space to store the result (e.g., a list or an array).
  • Second, it would have to consume the range in its entirety before returning control to the caller.

The first is an efficiency problem: memory allocation could and should be avoided in many cases (for example, the caller wants to just look at each result of map in turn). The second is a problem of principles: eager map simply can't deal with infinite ranges because it would loop forever.

That's why Phobos defines map to return a lazy range -- it incrementally makes progress as you consume elements from it. In contrast, the reduce function (in a way a converse of map) is eager. Some functions need both lazy and eager versions. For example, retro(r) returns a range that iterates the given range r backwards, whereas reverse(r) reverses r in place.

Conclusion

There would be more things to talk about even in an overview, such as unit tests, UTF strings, compile-time function evaluation (a sort of D interpreter running during compilation of a D program), dynamic closures, and many others. But with any luck, your curiosity has been piqued. If you are looking for a system-level language without the agonizing pain, an application language without the boredom, a principled language without the attitude, or -- most importantly -- a weighted combination thereof, then D may be for you.

If you feel like asking further questions, write the author, or better yet, tune to the Usenet server news.digitalmars.com and post to the digitalmars.d newsgroup -- the hub of a vibrant community.

Acknowledgments

Many thanks to Scott Meyers who pointed out the necessity of such an article and suggested its title. I have gotten excellent reviews, feedback, and suggestions from Bill Baxter, Jason House, John "Eljay" Love-Jensen, Denis Koroskin, leonardo maffi (sic), Petru M?arginean, Bartosz Milewski, Derek Parnell, Brad Roberts, Joel Salomon, Benjamin Shropshire, David Simcha, Florin Trofin, Cristian Vlasceanu, and Walter Bright.


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Video