> When someone else uses it in conversation, it's absolutely guaranteed that the person is a pretentious asshole.
I don't get your angle here. You realise an isomorphism is actually a well-defined mathematical concept, right? Are you advocating we use another, plainer word for an isomorphism, or do just naturally get angry when you hear words you don't understand?
Considering that TFA pokes fun at the word in the very first footnote, I took this comment to be mostly in jest. But if we’re going to be serious about it, technical jargon is really only appropriate when the speaker is 100% sure the audience 100% understands it.
There is sometimes a problem (I wouldn't use personal terms to describe it, but still) where technical terms are slung about without regard for whether people understand them. That’s poor communication, and as a bad side-effect, it encourages people to misuse the words in ways that don’t match the formal definitions.
In any event, if a comment is criticizing the article for using the word “isomorphism,” we could quite fairly ask if there is a bijective between algorithm and data structure, and whether the morphisms preserve behaviour.
> But if we’re going to be serious about it, technical jargon is really only appropriate when the speaker is 100% sure the audience 100% understands it.
I disagree. Half the reason I come here is to be exposed to new ideas or concepts. This isn't a lecture, I'll gladly take time to learn about a new concept if it seems relevant.
Fair enough, and here is an interesting thing: In a talk, if you stop to explain every technical term, you break up the flow and make it tedious for those who know the words.
But in a web article, we have hyperlinks, footnotes, asides, and other devices for allowing some readers to skim and others to dive in.
So to me, the choice for whether to use a word in an essay is different than the choice for whether to use a word in a talk at a conference, which is different than the choice for whether to use a word in a conversation where I am familiar with the participants.
Since we're on the subject of recursion, there is a problem when somebody uses a term that they only understand 90%. Somebody else reads that and understands 90%, and then they use, and then another person reads it...
And then we arrive in the current situation where people use terms like "rainbow table" or "HFT" to describe who knows what.
With that standard, we'd all be stuck at grunting.
Words exist for a reason. They allow precision, brevity, and – as Reginald so often shows – beauty. I expect readers to be willing to right-click an unknown word and quickly learn its meaning.
I'd also expect programmers to know what isomorphic means. Heck, you could even guess it: iso, like the standards. Morph as in morphology, "shape".
Pretentious or not, the term is used erroneously here.
Recursive data structures and recursive algorithms are, quite plainly, not isomorphic. They are not two equivalent representations of the same thing.
Something that is isomorphic to a recursive function that works on a quadtree would be an imperative function that works on a quadtree with identical functionality.
I don’t know that an algorithm and a data structure have to be equivalent representations of the same thing to be isomorphic. In the case of the algorithm, is it the code that must be equivalent? Or the runtime behaviour?
The runtime behaviour of the ‘whirling regions’ algorithm clearly is not an equivalent representation of the two-dimensional array representation of an image. However, the runtime behaviour of the quadtree algorithm exactly matches the quadtree data structure.
This is my proposition: That what matters is whether the algorithmic behaviour is equivalent. I would say the same thing about `binrec` matching a binary tree.
...Or at least, I would have, up until today. I am open to being disabused of this notion.
Isomorphic means "have the same shape". It means that there is some structural property that the two objects have in common. The more interesting/complex the property is (and the more superficially different the two objects look), the more defensible the use of the word is.
I am following the mathmatical definiton of isomorphism:
The two sets are Quadtree instances and calls of `myself`. The map from calls to instances is "instance that was given as argument". This map is obviously bijective. The structure that is preserved is "is a child of".
> They are not two equivalent representations of the same thing.
Algorithms encoded as a program end up as an abstract syntax tree in the compiler. Algorithm -> Data structure. The compiler then turns that ast into some other representation (e.g. machine instructions, JavaScript) which is again the algorithm. Data structure -> algorithm. Bijection identified.
An isomorphism is more than a bijection, unless it is between sets and the category is the one of all functions from one set to another.
Isomorphism is about preserving relations as well. For example, consider the ring of integers and the field of rational numbers. One can construct a bijection between one to the other (they both have the same cardinality as the natural numbers), but they are significantly different constructs. The bijection would not be able to preserve the operations - in fact, the rational numbers as a ring is significantly different, and unless one wants to use information about the cardinality, a bijection between the two is otherwise worthless.
Correct. A bijection implies isomorphism in the category of sets. Thus an isomorphism exists. I suppose we need to convince ourselves that algorithms and abstract syntax trees do indeed form sets. (Exclude such things as "the algorithm that computes the set of all algorithms", etc.)
But that is typically not how the word is used because to substitute bijection with isomorphism, it would only make sense when talking about cardinality - that is not how you used it.
Even with a non-mathematical definition such as yours, I don't see the isomorphism. Recursive code that acts on a quadtree does not itself take the shape of a quadtree. Not the text, not the AST, not the machine code.
The code is treelike, but that's because all code is treelike(1).
As a counterexample, consider code that acts on arbitrary graphs. DFS on an arbitrary graph doesn't itself take the form of an arbitrary graph. It is still treelike.
(1) My old Atari 800 BASIC programs notwithstanding.
The thing that has the shape of a quadtree is the callgraph. That means there is one call for every instance of the data class, which makes it easy to reason about the code.
OK so the callgraph is isomorphic in some sense when using recursion. If this was the intent of the author, it was not clear.
I would still argue that call-graph isomorphism to the data structures they work is of little relevance to software practitioners.
1. Multithreaded algorithms acting on trees do not necessarily have callgraphs that are isomorphic to the trees.
2. As I mentioned elsewhere, arbitrary graph data structures, or even the more constrained subset of DAGS, are not isomorphic to call graphs of the algorithms that work on them. Recursive algorithms have the same exact applicability to these structures as they do quadtrees.
3. Also as I mentioned elsewhere, recursive algorithms can be implemented with loops and an explicit stack without any function calls at all. This is at times the best way to implement algorithms on trees (particularly where trees are deep and the platform has a small stack - yes I've had to do rewrite recursive code because it overflowed a small, non-configurable stack).
I was speaking to the relationship between the code's runtime behaviour and the structure of the data.
When I say the word "algorithm," am I talking about the way the code is noted in a particular language? Or the steps one takes to perform the operation?
In some other languages, even the notation itself has obvious parallels between data definition and process definition. Consider a list and `map` in Standard ML:
datatype 'a list =
Nil
| Cons of 'a * 'a list;
val rec map : ('a -> 'b) -> 'a list -> 'b list =
fn f => fn xs =>
case xs of
Nil => Nil
| Cons(x, xs') => Cons(f x, map f xs');
The case analysis of a list is obviously isomorphic to the definition of a list, in the sense that the data and the process have the same shape: a list is a `Nil` or a `Cons(item, more list)`, while a function that traverses a list checks if a list is `Nil` and does something, otherwise it's a `Cons(...)` and it does something else. The linear recursive nature of the list definition lends itself naturally to algorithms which are similarly linearly recursive. (`map` itself can be said to create homomorphisms, but that's beside the point here; I use this particular example only because it happens to be the simplest non-trivial one I could think of).
Okay, so perhaps this isn't quite what "isomorphic" means in category theory, or topology, or graph theory, or set theory, or what have you. Even in mathematics, though, it's obvious that terminology gets borrowed between the branches when there are concepts that are somehow related. Why should programming be any different? So, I argue that it's not wrong to use "isomorphic" in the sense that you have—in fact, it's a term that I've seen used in the same sense on numerous occasions, and something that I think experienced programmers have internalized. In this case, the structure of the data, that is, a linearly recursive collection of elements, precisely matches the structure of the process, that is, a linearly recursive traversal of elements. Whether or not there actually exists an isomorphism between the two is irrelevant to the notion that the two are isomorphic, that is, they have "equal shapes".
I think a habit of thinking of words in an etymological way leads naturally to borrowing those words for similar concepts. This is neither the first time such a thing has happened, nor will it be the last. To knowledgeable parties, your use of the word communicated a characteristic of your program in a succinct way that you continued to illustrate—that the shape of the quad tree data structure reflects the shape of the algorithms used to process instances of said structure.
One might say that the various meanings of the term "isomorphic" are... isomorphic ¬_¬
> You realise an isomorphism is actually a well-defined mathematical concept, right?
I think a prime example of how words loose their precise mathematical meaning is the word "function". It has a precise definition in maths but we programmers use it often with a different meaning. We used to have the terms "subroutine" and "procedure" for what we use "function" for nowadays. We even came up with the term "pure function" to refer to the original mathematical meaning of "function".
I found the article to be very pretentious too. Although the author doesn't really try to convince you otherwise, if you read the footnotes: "In computer science, two things are isomorphic if the person explaining a concept wishes to seem educated.". But you know, if you claim that isomorphism makes the code easier to understand, support the claim by at least something. If anything the code with the "isomorphism" looks unnecessary complicated and harder to understand.
I don't get your angle here. You realise an isomorphism is actually a well-defined mathematical concept, right? Are you advocating we use another, plainer word for an isomorphism, or do just naturally get angry when you hear words you don't understand?