Abstraction: Not what you think it is
pathsensitive.com
pathsensitive.com
"Bad programmers worry about the code. Good programmers worry about data structures and their relationships."
- Linus Torvalds
"Fold knowledge into data, so program logic can be stupid and robust."
- Eric S. Raymond
"Data dominates. If you’ve chosen the right data structures and organized things well, the algorithms will almost always be self-evident. Data structures, not algorithms, are central to programming."
- Rob Pike
"Representation is the Essence of Programming"
- Fred Brooks
"One of the key attributes of a "Good" representation, is the ease in which it is transformed into other valid information the computer can process."
- https://www.cs.utah.edu/~germain/PPS/Topics/information_repr...
"Syntax without representation is tyranny!"
- Gerald Jay Sussman
Data structures can be used as part of an abstraction. So can functions. But neither one is the abstraction.
In the case of data structures, you might use a particular data-structure as the domain of the simpler world, but it's the mapping itself that is the abstraction, and that mapping is not part of the code, it's a conceptual thing that must be documented.
All of those quotes say how important data and its representation is to a programmer, but that doesn't equate to saying data structures are abstractions, because abstractions aren't the only important thing. I'm not sure they're even the most important thing.
Building abstractions can be ery much like creating a new language.
I think a lot depends on where your cost goes. E.g. you could create hyper-optimized code that performs incredibly well, but it is also hard to maintain, next to impossible to comprehend and cannot adapt to change very well.
I believe it is possible to create code that does well on all fronts (readable, maintainable, adaptable, performant), it is just a much harder search task (you pay it with developer time/experience).
The usual way to make abstractions useful is to choose a restricted problem space, compressible enough to offset the abstraction's overhead.
And then a data scientist with expertise in differentiable programming zooms in on a motorcycle to back them up.
And then a mathematician with expertise in linear algebra time travels in from the 19th century to join the party, although they're admittedly a bit lost and confused and not much help in this particular conversation because they're not familiar with modern jargon.
Which isn't to say that those quotes aren't valid or don't express concepts worth knowing and internalizing. But they're practical statements that apply to a certain way of looking at things. A very useful one, to be sure, but not the only one. The distinction between functions and data has a tendency to disappear upon close examination.
(Almost as if the concepts of "function" and "data structure" were themselves abstractions.)
You've failed to account for the interpreter and the hardware it runs on that provides operational properties necessary for human use, i.e. performance
Maybe, but this is not at all what the article is arguing, however.
Edit. If the vertical axis is time and the horizontal plane is space, then the floating something in the middle is the 'abstraction', its shadow on the plane below is its data structure and its projection onto the vertical axis is its function. The need to compress everything into the 1-dimensional time is what creates those for-loops and ifs. The art of finding the right data structure is the art of finding the right angle at which the 'abstraction' drops a good descriptive shadow.
[edit] spelling [/edit]
I think type level functions, like Functor or Monad, also qualify as abstractions.
That distinction sounds mildly problematic when one can turn a data structure into a function.
The decision of what a function will do over and over again is abstracting the layer below which if it weren't for the function, would have repetition of some kind. It's taking those repeated bits, and factoring out the different elements reducing them to a function call.
That said, I understand where this perspective is coming from, and perhaps "refinement" is more descriptive of a more practical approach.
Ah, they're advocates for strongly-typed programming and they didn't even know it!
A common example of a harmful abstraction, in C and C++, is a typedef of a pointer to an opaque name. The typedef conceals, when you read code using it, that the type is really a pointer, and so subject to all the excess operations provided for pointers in those languages. But one thing every C and C++ programmer always needs to know about a type they are working with is whether it is a pointer.
Every abstraction has an unavoidable cost. The value it provides has to exceed that cost for it not to be a liability. Usually the main cost is that it is not as comprehensively documented as its creator imagines (if at all), and the user cannot trust what it will do without tracing through and understanding what details and pitfalls it hides. The more comprehensive its documentation, the more time it takes to read and understand, and the more likely it is to be, or later become, inaccurate.
Thus, part of the job of every programmer is to distrust abstractions. An abstraction works on cases it has been seen to work on, but often cannot be trusted otherwise. This is what makes Standard Library abstractions valuable: you have confidence the implementation has been verified to match the specification, and the specification (1) has been carefully designed to avoid pitfalls and (2) documents them, where it cannot. J. Random Abstraction in your local library rarely gets that much attention.
Make your abstractions earn their keep.
I.e., "intermediately-experienced" and younger than the "most experienced". As I said. You are unlikely to find yourself relying on a library written by a beginner.
Nah, I don't agree at all. Renamed generic pointers are actually an extremely useful signal. They say "you should not concern yourself with what this pointer points to. You should only be using it through the library's functions. Do anything else with it at your own peril". Also, no, C and C++ programmers don't really care whether a value of some novel type is actually a pointer or not (C++ programmers much less so). They only care about what size it is to know how to pass it around and whether it needs to be cleaned up in some specific way. If I tell you that when you're done with a fluor_t you should pass it to release_fluor(), do you need to know whether fluor_t is a pointer or a struct, or whether release_fluor() is a function or a macro?
If users have to call release_fluor(), your abstraction has failed to earn its keep.
Programmers understand that referents of pointers have lifetime that must be managed. Hiding that quality of your special-snowflake type does nobody any good.
You really don't. If the documentation says that after calling release_fluor(), the fluor_t that was passed to it can't be passed to get_fluor_mass(), it doesn't matter whether fluor_t is a pointer or not.
I'm sorry, but you're just plainly wrong.
Programmers understand pointers and pointer semantics: when they see a pointer, they know what is required of them. An opaque type that has pointer semantics you can't tell without reading up on documentation is, exactly, an abstraction that costs more than it delivers.
As fluoridation indicated, this is the norm in C programming. By means of example, in the OpenCL C library, bitfields all use the same type. You have to consult a function's documentation to know what you're allowed to pass. [0]
I do agree that the 'Ada-style' approach to types is far superior to the 'C-style', but Doing It Wrong seems a bit strong, unless you want to condemn all C code.
With the right library you can use the 'Ada-style' in C++. Specifically, using a 'strong typedef' library which prevents implicit conversions, such as [1], but not Boost's strong_typedef which permits implicit conversion back to the underlying type. Unfortunately this kind of thing isn't possible in C.
> Programmers understand pointers and pointer semantics: when they see a pointer, they know what is required of them
Not really. Should you call free on the pointer once you're done with it? The type alone doesn't tell you. You need to consult the documentation to know how you are meant to use the value, whether or not a pointer type is used.
[0] https://www.khronos.org/registry/OpenCL/specs/2.2/html/OpenC...
There are plenty of APIs that have similar semantics (connect/disconnect) that must be followed. And even if something is a pointer doesn't mean you can just free() it -- you might need to use whatever method the API provides to get proper operation.
This is the main abstraction mechanism in C programs -- the abstract data type. A piece of data you pass around but never know the innards of.
When something has reference semantics but isn't an actual pointer, that is an extra fact that the reader of code needs to know in order to reason correctly about it. That is, thus, a burden above what would be needed for an actual pointer. It is a burden that is harmful to impose entirely unnecessarily.
Managing any resource is trivial with destructors. If you need to manage a resource, a pointer is a poor way to do it.
In C, you have a poverty of choices, but people are anyway used to being careful around pointers.
In this view, there is something ironic about how many of the complexities of the language came about to enable the abstractions of the Standard Library, which greatly simplify writing applications in the language!
Many languages have strictly limited power, in order to keep non-professionals from getting into trouble.
UFCS is better than C++ ranges. builtin sum types are better than std::variant, etc..
All languages have weaknesses, and so end up with core features. Sometimes the language evolves to the point where the core feature is not needed anymore because a library does equally well, or sometimes better. A good example is the C++ Standard Library std::array, which is better than a built-in C-style array in every way except being a little longer to type.
C (and C++) programmers only need to know if a type is a pointer if they are meant to know it is a pointer. Otherwise very often a foo_t is meant to be used via manipulation functions and it being a pointer or an integer or whatever else is a detail that the programmers do not need to care about. This is a very common approach for libraries when trying to make a shared library with a stable ABI, though it is also common when you want to isolate accessing the underlying data of whatever a "foo_t" represents to a single known module.
Often you see "foo_t*" instead of "foo_t" (with foo_t being an undefined struct) but with "foo_t" being unusable by itself it is always stored and passed around as a pointer and thus the same -incredibly few and irrelevant in practice- pitfalls would apply anyway, so in reality it all boils down to personal stylistic preference if you want to litter all those stars in a project or not. Personal preferences like that have nothing to do with youthfulness or even experience.
I have been working with C codebases for decades and have more than enough experience thank you.
You didn't really reply to what i wrote though.
IMO, HANDLEs are probably a bit too opaque for my taste, as you have to know what operations you should be using with them. I'd prefer opaque structs if I had to choose.
HANDLE is the worst of all possible worlds.
An opaque struct confers the ability to know the set of valid operations involving said type, while not giving up any advantages of a HANDLE. Issues of indeterminate size can be worked around with a single void*/uintptr_t field.
There is a reason that the language permits "auto& r = " and "auto* p = ". That reason is, specifically, to help prevent errors. Failing to spend a single keystroke to help prevent errors is false economy.
auto* does not add anything to making code more reliable, either; it just makes code tied to a particular implementation detail (e.g. I could redefine things using my own pointer-like object, and the * would simply stand in the way for no good reason whatsoever.)
First, both adding an ampersand after auto when you shouldn't have and not adding it when you should have can lead to logic errors of different kinds. Sometimes either one is fine, sometimes you have to use the correct one.
Second, auto * vs auto by itself has no effect on the generated code, but it can lead to a more robust source. Imagine that you get a pointer from some function and you perform some operations with it, assuming it actually is a pointer in a way that would be invalid if it wasn't. If the function signature later changes to return a pointer-like object, you'd want the compiler to give you an error to know to fix that code. In other words, you should use auto if you really don't care at all if the value is a pointer or not, and you should use auto * if you're assuming it's a pointer.
struct Opaque {
int data;
};
typedef Opaque *OpaqueRef;
void bar(const OpaqueRef ref) {
ref->data = 42; // compiles fine, ref is 'Opaque *const'
}
void baz(const Opaque *ref) {
ref->data = 42; // does not compile, ref is 'const Opaque *'
}But I feel like it tries a bit too hard to re-define what abstraction means ("only this subset of abstractions are real abstractions"), instead of just putting "abstract interpretation" next to it. This idea can stand on its own without trying to re-define the world.
Secondly I understand the discussed notion of abstraction as a domain model, which is information (data and functions) _about_ the world. I like the term model better here than "idealized mapping" because the former implies a bit more that there are assumptions about the data and usage context of said model (often implicit, unstated) and that it is incomplete.
> But we've had a pretty good definition of abstraction since 1977, originally in the context of program analysis, and — I claim — it actually translates quite well into a precise definition of “abstraction” in engineering.
So I don't think the author is saying that all these other people are "wrong", but rather that this one particular definition seems to capture the underlying essence of what we intuitively think of when we say "abstraction", and the rest of the "hodgepodge of different concepts" break down if you analyze them a bit deeper (as the author did in the "Not Abstraction" section).
The common theme in the Not Abstraction section is: These things are used to build abstractions and are not necessarily abstractions themselves. This is not only nitpicking but it's also false. Programming language features like functions and interfaces are already abstractions, even in the narrow sense that the article describes. They are an idealized mapping to something concrete (register machines, vms etc.) and provide precision, soundness and are based on specification.
Again, I very much like the core idea presented here, but I think it is completely unnecessary to make the claims about what is and isn't "true" abstraction.
Take this quote:
"Abstractions are separate from the code, and even from the abstract domain. It does not make sense to say that the bookTable function or anything else in this file “is” the abstraction, (..)"
The function _is_ not the abstraction because abstractions are entirely conceptual? Is it a way to communicate an abstraction then? What about the actual machine code the compiler produces from that function, is there some abstraction?
None of this helps me. The interesting part is that code is used to model information, it's not the world itself or even tries to be.
Then this:
"Feel free to call numbers an abstraction of the hardware, but be prepared to switch to this precise terminology when there's tension on the horizon."
Simple abstractions that are not discussed are names and signs. These are abstractions in the very real sense and they are very simple on their own. But they are entirely contextual and are allowed to mean different things. For example the term "abstraction".
Let's design a system that allows us to run virtual computers on a single hardware platform. In some part of this system we need to map real hardware addresses to virtual ones in order to isolate the different virtual computers.
Now you might need a way to take a real, logical address to a memory location on this machine and get a virtual address. You might have to run this system on many different hardware platforms and you only know the platforms you will run on today (or the next few months). Almost without thinking about it you might choose to use a virtual method on a class to define a function signature for this operation. That way folks implementing this system for different hardware platforms can create a sub-class and fill in a concrete definition of the virtual method. Now users of the system can translate an address and don't have to think about the underlying hardware platform they're running on! Abstraction!
Only it's not an abstraction.
If you attempt to formalize what it means to map a hardware address to the virtual address you will find it quite difficult because your interface provides no information about hardware addresses. In other words the virtual method does not put in all of the details of the concrete implementation and so we cannot maintain an invariant in our specifications that would ensure that we only translate valid addresses, or that translation is deterministic -- properties that would be important for users of the abstraction to truly be able to ignore the underlying complex domain. If we could write such a specification for this virtual method though, it would be very complicated, and that is a good sign this is not a good abstraction.
Abstractions are often separate from the code because they're much more general than a single program. If we came up with a better abstraction in a formal logic like separation logic or using Hoare logic -- we might be able to prove that the properties we care about hold and therefore any program that implements this specification will have the same properties. And there might be several such programs!
So what industry programmers are often saying when they are talking about "abstraction" is "indirection and vagueness." What this article is trying to show is that we can give precise definitions to our abstractions so that we can build new _semantic_ layers that have precise meaning: when I translate a hardware address I get a valid, deterministic virtual address and nothing else.
Both this OC and the wiki article on 'abstraction', wrt to software design (eg OOAD) make me think of generalization and specialization.
--
My own working definition of 'abstraction' vs 'mental models', because I lack more proper terms:
- abstractions hide details, aka black box
- mental models explain how something works, even if over simplified
An example of a good (quite useful) abstraction is the initial Java Virtual Machine. Its 'interface' (per this OC) is quite good, meaning comparatively small impedance mismatch, and acceptable 'leakiness'. As we've seen over time, driven by optimization, that abstraction is necessarily bypassed or mitigated with JMM, FFI, unsafe stuff, intrinsics, direct memory, etc.
Using an example of a mental model from my prior works, because I'm precaffeinated, and I can't think of a better example than Newtonian mechanics, already mentioned.
I used to work in print production, like books and magazines. For bookwork, I created an algorithm for the folding of big sheets of paper into 'signatures' containing printed pages. My app accounted for folds, binding, and cutting. It revealed the manufacturing process, so there could be no mistake. It reduced an Illustrator-like application (ScenicSoft' Preps imposition app) to a simple form. This simplification was possible because I had invented a better mental model.
--
My working definition of abstraction doesn't jive with anyone else's. I'm open to alternate suggestions. https://en.wikipedia.org/wiki/Abstraction
A (logical) model is a simplified representation of the real thing that is still complete enough that it can be used to successfully reason about and accomplish goals with a system. A linked list datastructure is a real thing with a number of possible implementation details, but it still has a straightforward, concrete model of what it is. It's not an abstraction.
A model does not have to be abstract at all; it can be very concrete, even if it in practice hides some underlying details.
It seems common in software to either get lost in abstraction so that you forget the model, or consider the model so rigid that you miss useful, simplifying abstractions.
Ya, abstractions vs models. I'll drop the "mental" qualifier, thanks.
> get lost in...
Totally. Too many times, the implementation comes to be treated as the model, completely obfuscating the client's actual problem.
In other words, the definition of a word depends on its real-world usage; dictionaries attempt to capture common usages, but no definition of a word can be considered the "true" definition more than any other used and understood application of the word.
So in this case, calling these definitions "imposters" or "not-abstractions" is absolutely wrong. That said, I like the attempt to introduce names for different flavours of abstraction to make discussion easier. That's definitely useful. Just wish it wasn't off the back of incorrectly telling people that their use of the language is incorrect.
> That said, I like the attempt to introduce names for different flavours of abstraction to make discussion easier. That's definitely useful.
Is the real value of this article.
[edit: this information might be out of date - looks like there isn't a central forum for this in French any more, however forums do spring up periodically]
But yes, English is - these days - predominantly handled within a descriptive framework, and dictionaries such as Miriam Webster [1] and Oxford English Dictionary [2] point out that they only exist to describe usage.
There may be an argument to be made about definitions within scientific fields; but without the dictates of a cohesive authority, it's very hard to claim this as truly prescriptive. It is up to groups of expert practitioners to come to consensus on the definitions. And you can argue whether that is the very definition of prescriptive (because they prescribe the word's usage on the rest of the world) or descriptive (because they as the predominant users of those words are describing the academic usage of the words)
But I have yet to see an English dictionary that claims to be fully prescriptive. If it did, it would have dubious authority to do so. Similarly, I feel like we're so many miles away from a consensus on the Computer Science definition of "an Abstration" that my original point stands.
[1]: https://www.merriam-webster.com/words-at-play/descriptive-vs...
Encapsulation might be a more appropriate word in most cases, since abstraction doesn't tell you what specifically you're abstracting away from.
Coming from OOP, I've always thought of abstraction as just "A thing that hides the real nature of something and presents it as a standard and simplified model, and lets you ignore more things than the non-abstract truth allows".
drawImage(file, x, y) is an abstraction, because I don't need to know how it works or how it knows what decoder to use.
One might even say a toilet is an abstraction because what goes into it is(Presumably) dealt with in a sanitary manner by professionals.
Things like monads and composition are abstractions in the colloquial sense, objects far from some concrete thing like a car or a pen, but using them effectively requires understanding the logic, so in a sense they are leaky, because the act of using them "leaks" the mathematical logic, and subjectively nothing like that comes to mind when I think of abstractions in programming.
They're definitely abstractions, but they are used to reveal and illuminate a program's structure, not to hide it in a black box.
In my mind, abstractions are used to reveal the program's interface and intent more than its structure. The functions, data structures, variables, and ultimately the source code reveal the program's true structure.
It has been done. Category Theory (a.k.a. "abstract nonsense") has been pretty successful describing abstraction using the language of functors.
If it is not lossy, it is likely not to be providing net value.
Instead, I propose that we consider abstractions with respect to some problem domain. If you have states {null, notnull} then this is lossless but {null, notnull, top, bottom} is lossy.
When we code, we're philosophizing about information in some language (itself an applied ontology), for the decreasingly worse.
Occasionally one arrives at a coherent, stable product.
The fact that some languages, as mentioned in the article, have a language feature called “interface” is somewhat unfortunate, because it makes unclear when someone says “interface” whether they refer to the language feature or to the more general meaning. (For example, every Java class has an interface-in-the-general-sense, just like every class has an implementation, regardless of whether the class happens to implement an interface-the-language-feature or not.) Prior to that, it was always understood that “interface” implies a certain contract, usually one that imposes conditions beyond the mere type signature of the respective entity.
Incidentally, that’s also one benefit of nominal typing (as opposed to structural typing), because it expresses the fact that the interface is usually more than its type signature, and therefore two entities having compatible type signatures are not necessarily compatible in terms of their interface contract, and thus shouldn’t be implicitly convertible/assignable to each other.
I realize this is subjective, but I hear it as the author arrogantly assuming that their insight or approach is objectively better than those of their entire audience. Without even knowing their audience members are. They just know they're more correct than you, and they're happy to advertise that.
I'm sure it drives engagement, but it definitely reduce the chance of me reading the article.
I am sure category theory can say much about this.
Some abstractions are more useful/helpful/powerful than others. The usefulness of an abstraction often depends on the domain. Much of the time, the best way to find out the right abstractions is to first create multiple things with no new abstractions, then decide that everyone will save time if you merge some of the concepts you created. It's good to use well-known, tested abstractions early on, but it's risky to create new abstractions prematurely.
Sometimes a function, data structure, interface, or API happens to embody an abstraction very cleanly. When that works out, the abstraction is easy to teach and tends to be more useful. Most abstractions are a bit messier than that, though, which is why abstraction is really a human-level teaching/learning construct rather than any element of programming languages.
For example, I consider most SDKs to be abstractions.
It’s really just semantics, as I guess we could argue that the “classic” definition applies to code, as well as to coders.
[0] - https://medium.com/clean-code-development/stratified-design-...
That's catchy. But:
The practice of programming is about manipulating a special kind of data (code). And so: "Good programmers worry about code structures and their relationships."
(Even more so in the age of devops, infrastructure as code, etc.)
In programming, it could be the boundaries of a concept independent of implementation. In visual art, it could be a few lines on canvas that evoke the spirit of the thing referenced. In jazz, it could be strange notes on the peripheries and askew of rhythm that by being what is not, circumscribe what is.
“But fundamentally, computer science is a science of abstraction — creating the right model for thinking about a problem and devising the appropriate mechanizable techniques to solve it.”
So easy to get wrapped up in all the syntactic sugar.
I agree with this. And to me, this means a good abstraction is necessary to be ambiguous. For example, number is an abstraction. But a type that is int32 is not an abstraction. In fact, we are not using a meta-layer that allow ambiguity is the reason that most abstractions force readers to be concerned with details in order to understand code.
Math abstractions are good and rigorous. That is because math is never concerned with reality. As soon as you deal with reality, math is ambiguous from start to end. For example, what is one? Math throw away all the physical details, that is what allows it to be useful -- one can understand math without ever concerned with physical details.
The current popular programming language are not suitable for abstractions. Our natural language are good for abstractions. But I think we probably can have something in-between, like what we come up with math.
There are multiple layers of abstraction. int32 is just one layer lower than you're used to.
Wether to know if something is an abstraction, could be tested by asking, is this thing useful to operate with different child categories in just one place ?
When you have an abstraction with just one child category, rather than useful is just confusing.
For example if in your universe would exist just on type of Vehicle called Car, but you would use Vehicle abstraction.
Isn't that just what people usually refer to as "inlining"?