This is the story of how I was no-hired by Microsoft; surprisingly, it is germane to our discussion of unusual list structures. Continue reading
An interesting list structure, part 3
9
Tag Archives: Immutability
An interesting list structure, part 2
Last time on FAIC I gave a standard implementation of a persistent immutable linked list, with cheap — O(1) — Push, Pop, Peek and IsEmpty operations, and expensive — O(n) — Append and Concatenate operations. In this episode we’re going to implement a Hughes list, which “flips” those costs: Pop, Peek and IsEmpty become O(n), Append and Concatenate become O(1). Push stays O(1) also. This data structure is useful for scenarios where we are accumulating a large list “from both ends” or out of smaller lists, and then want to read the whole thing out as a normal list once we’re done the accumulation.
An interesting list structure, part 1
As long-time readers of my blog know, I’m a big fan of functional persistent immutable list data structures. I recently learned about a somewhat bizarre but very practical implementation of such lists, and naturally I wanted to implement it myself to try it out. The list data structure I’m going to discuss today is called a “Hughes list”, after its creator John Muir Hughes. The Haskell implementation is called “DList”, which stands for “difference list”, and this data structure is also commonly used in Prolog and Scala.
Persistence, façades and Roslyn’s red-green trees
We decided early in the Roslyn design process that the primary data structure that developers would use when analyzing code via Roslyn is the syntax tree. And thus one of the hardest parts of the early Roslyn design was figuring out how we were going to implement syntax tree nodes, and what information they would proffer up to the user. We would like to have a data structure that has the following characteristics:
- Immutable.
- The form of a tree.
- Cheap access to parent nodes from child nodes.
- Possible to map from a node in the tree to a character offset in the text.
- Persistent.
Atomicity, volatility and immutability are different, part three
So what does the keyword “volatile” mean, anyway? Misinformation abounds on this subject.
Atomicity, volatility and immutability are different, part two
Last time we established that an “atomic” read or write of a variable means that in multithreaded scenarios, you never end up with “halfway mutated” values in the variable. The variable goes from unmutated to mutated directly, with no intervening state. I also talked a bit about how making fields of a struct readonly has no effect on atomicity; when the struct is copied around, it may be copied around four bytes at a time regardless of whether its fields are marked as readonly or not.
Atomicity, volatility and immutability are different, part one
I get a fair number of questions about atomicity, volatility, thread safety, immutability and the like; the questions illustrate a lot of confusion on these topics. Let’s take a step back and examine each of these ideas to see what the differences are between them.
First off, what do we mean by “atomic”? From the Greek ἄτομος, meaning “not divisible into smaller parts”, an “atomic” operation is one which is always observed to be done or not done, but never halfway done. The C# specification clearly defines what operations are atomic in section 5.5. The atomic operations are: reads and writes of variables of any reference type, or, effectively, any built-in value type that takes up four bytes or less, like int, short and so on. Reads and writes of variables of value types that take more than four bytes, like double, long and decimal, are not guaranteed to be atomic by the C# language. (There is no guarantee that they are not atomic! They might in practice be atomic on some hardware. Or they might not.)
Immutability in C# Part Eleven: A working double-ended queue
At long last, let’s get to that double-ended queue. Sorry for leaving you in suspense!
Continue readingImmutability in C# Part Ten: A double-ended queue
Based on the comments, the implementation of a single-ended queue as two stacks was somewhat mind-blowing for a number of readers. People, you ain’t seen nothing yet.
Continue readingImmutability in C# Part Nine: Academic? Plus my AVL tree implementation
Good Monday morning all. I have received a lot of good comments on this series so far that I thought I would speak to a bit.
Continue reading
Fabulous adventures in coding 