Near the end of my presentation at DDD EU, I mentioned that I was working on a precise / useful / paradigm-independent definition for some of the terms we use daily (like abstraction and indirection), based on the notion of entanglement. Later on the same day, the great Jim Coplien observed in his talk that we already have a proper definition of abstraction in the dictionary - selectively remove details (information).
However, I still find that definition almost useless, because it allows us to define everything as an abstraction, which we routinely do. It also allows any removal of information - like shortening every identifier to a single letter - to be classified as abstraction. It’s then a simple step to conclude that abstraction is “evil”.
To be honest, I’m not really interested in investigating the philosophical side of abstraction in software, nor the poetic side. I appreciate both, but I’m looking for a physics of software, and therefore I’m looking for useful definitions.
We use the term “abstraction” in a number of contexts; some are classic CS terms like Abstract Data Type, Abstract Interface, Abstract Interpretation, Abstract State Machine, but most people would also say “introduce an abstraction” when they “introduce a concept”, and so on.
Of course, under the dictionary definition, everything is OK, except that when a giant like David Parnas says “I have not found a relation, "more abstract than," that would allow me to define an abstraction hierarchy” (in his classic paper “Designing Software for Ease of Extension and Contraction”) we should perhaps stop and think on how we define our terminology.
Again at DDD EU, I made the point that we often use a single, broad and therefore ambiguous / imprecise term where many would be needed to provide a precise and useful characterization. This, I think, it’s also the case with “abstraction”. However, before stepping in with my own little contribution, I wanted to cross-check my ideas with a number of sources. Unsurprisingly, that turned out to be a lot of work, but that's probably the difference between trying to approach the problem from a scientific perspective vs. being another guy ranting on the internet.
This is the list of papers / books / etc. that I’ve rounded up. I’ve chosen both classic and obscure papers, some coming from AI and Psychology, but most are CS / IS centric as that’s the target of my work. I’ve mixed theoretical papers with papers dealing with specific usages of the term that I want to harmonize well. I've also included a few informal but popular blog posts, because they (partially) represent how the non-academic side of the world is looking at these notions.
I’ve already been through many of these references, but since some are already attempting to provide a review and a definition, they will necessarily spur more reading. Most will be only marginally relevant in the end, and I will end up citing just a few, but all will provide some angle that I’ll try to account for.
So here is the list; it’s not in a particular order (files in my folder or memos of files to download), and I haven’t provided links for most. Trust me, if you’re not motivated enough to right click and search with google, you don’t want to read them either :-). Some might be available only behind a paywall (mostly ACM/IEEE). Some are listed with more details than others (and no, I do not consider that as “abstraction” :-), it’s just a byproduct of laziness, copy & paste, non-uniform data sources). If your favorite paper on abstraction is missing, tell me on twitter!
Academic Papers and Technical Reports
Non-academic writings, blog posts, rants
However, I still find that definition almost useless, because it allows us to define everything as an abstraction, which we routinely do. It also allows any removal of information - like shortening every identifier to a single letter - to be classified as abstraction. It’s then a simple step to conclude that abstraction is “evil”.
To be honest, I’m not really interested in investigating the philosophical side of abstraction in software, nor the poetic side. I appreciate both, but I’m looking for a physics of software, and therefore I’m looking for useful definitions.
We use the term “abstraction” in a number of contexts; some are classic CS terms like Abstract Data Type, Abstract Interface, Abstract Interpretation, Abstract State Machine, but most people would also say “introduce an abstraction” when they “introduce a concept”, and so on.
Of course, under the dictionary definition, everything is OK, except that when a giant like David Parnas says “I have not found a relation, "more abstract than," that would allow me to define an abstraction hierarchy” (in his classic paper “Designing Software for Ease of Extension and Contraction”) we should perhaps stop and think on how we define our terminology.
Again at DDD EU, I made the point that we often use a single, broad and therefore ambiguous / imprecise term where many would be needed to provide a precise and useful characterization. This, I think, it’s also the case with “abstraction”. However, before stepping in with my own little contribution, I wanted to cross-check my ideas with a number of sources. Unsurprisingly, that turned out to be a lot of work, but that's probably the difference between trying to approach the problem from a scientific perspective vs. being another guy ranting on the internet.
This is the list of papers / books / etc. that I’ve rounded up. I’ve chosen both classic and obscure papers, some coming from AI and Psychology, but most are CS / IS centric as that’s the target of my work. I’ve mixed theoretical papers with papers dealing with specific usages of the term that I want to harmonize well. I've also included a few informal but popular blog posts, because they (partially) represent how the non-academic side of the world is looking at these notions.
I’ve already been through many of these references, but since some are already attempting to provide a review and a definition, they will necessarily spur more reading. Most will be only marginally relevant in the end, and I will end up citing just a few, but all will provide some angle that I’ll try to account for.
So here is the list; it’s not in a particular order (files in my folder or memos of files to download), and I haven’t provided links for most. Trust me, if you’re not motivated enough to right click and search with google, you don’t want to read them either :-). Some might be available only behind a paywall (mostly ACM/IEEE). Some are listed with more details than others (and no, I do not consider that as “abstraction” :-), it’s just a byproduct of laziness, copy & paste, non-uniform data sources). If your favorite paper on abstraction is missing, tell me on twitter!
Academic Papers and Technical Reports
- Theories of abstraction, Fausto Giunchiglia, Adolfo Villafiorita, Toby Walsh, AI Communications archive, Volume 10 Issue 3,4, December 1997
- Data Abstraction and Hierarchy, Barbara Liskov
- Behavioral Abstraction is Hiding Information, Grigore Rosu, J. of TCS, Volume 327(1-2), pp 197-221. 2004
- Abstraction and concretizing in information systems and problem domains: Implications for system descriptions, Jens Kaasbøll
- Abstraction Descant, in Patterns of Software, Richard P. Gabriel
- Information-Based Selection of Abstraction Levels, Stephan Schulz, Proceedings of the Fourteenth International Florida Artificial Intelligence Research Society Conference, AAAI Press, 2001
- Data abstraction and information hiding, K. Rustan M. Leino Greg Nelson
- Breaking Abstractions and Unstructuring Data Structures, Christian Collberg Clark Thomborson Douglas Low, Department of Computer Science, The University of Auckland
- Types, Abstractions, and Parametric Polymorphism, Part 2, QingMing Ma John C. Reynolds, Proceedings of the 7th International Conference on Mathematical Foundations of Programming Semantics, Springer-Verlag London, UK 1992
- Abstraction and Approximate Decision Theoretic Planning, Richard Dearden and Craig Boutiliery, Department of Computer Science University of British Columbia
- A Functional Abstraction of Typed Contexts, Olivier Danvy & Andrzej Filinski
- DIKU – Computer Science Department, University of Copenhagen
- Abstracting control, Olivier Danvy Andrzej Filinski, LFP '90 Proceedings of the 1990 ACM conference on LISP and functional programming
- Information Model: From Abstraction to Application, Jean SCLAVOS - Noëmie SIMONI - Simon ZNATY
- Separation Logic and Abstraction, Matthew Parkinson Gavin Bierman
- Towards Abstract Interpretation for Recovering Design Information, Coen De Roover, Kris Gybels 1, Theo D’Hondt, Programming Technology Lab Vrije Universiteit Brussel
- Abstract Argumentation, ROBERT A. KOWALSKI and FRANCESCA TONI, Department of Computing, Imperial College of Science, Technology and Medicine, London
- Object-Oriented Programming Versus Abstract Data Types, William R. Cook
- Abstract behavior types: a foundation model for components and their composition, F. Arbab, REPORT SEN-R0305 JULY 31, 2003
- Abstract Information Appliances, METHODOLOGICAL EXERCISES IN CONCEPTUAL DESIGN OF COMPUTATIONAL THINGS, Lars Hallnäs and Johan Redström
- Lazy abstraction, Thomas A. Henzinger, Ranjit Jhala, Rupak Majumdar, Grégoire Sutre, POPL '02 Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages
- On Understanding Types,Data Abstraction, and Polymorphism, Luca Cardelli, Peter Wegner
- Quantum information-flow, concretely, abstractly, Bob Coecke, Oxford University Computing Laboratory
- On the proper definition of information, Andras Kornai, ETHICOMP 2008
- Patrick Cousot, Radhia Cousot: "Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints", Conference Record of the Fourth ACM Symposium on Principles of Programming Languages, January 1977
- Generating Finite State Machines from Abstract State Machines, Wolfgang Grieskamp, Yuri Gurevich, Wolfram Schulte, Margus Veanes
- Abstraction Based Information Technology, Jacques Calmet, University of Karlsruhe
- Abstraction in perceptual symbol systems, Lawrence W. Barsalou, Department of Psychology, Emory University
- Abstractions and Implementations for Architectural Connections, Mary Shaw, Robert DeLine, Gregory Zelesnik, Computer Science Department Carnegie Mellon University
- Scalable Component Abstractions, Martin Odersky, Matthias Zenger
- On Abstraction and Interpretability: a Behavioural Perspective, Raphael Pfaff, Keith J Burnham, Control Theory and Applications Centre, Coventry University
- A Definition of "Abstraction Level" for Metamodels, Martin Monperrus, Antoine Beugnard, Joël Champeau, DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ECBS.2009.41
- Making Abstraction Concrete, Bran Selic, DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/WICSA.2011.10
- A Semantic Characterization Of Full Abstraction For Typed Lambda Calculi, K. Mulmuley , Carnegie-Mellon University, DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/SFCS.1984.715926
- The cognitive processes of abstraction and formal inferences, Yingxu Wang , Dept. of Electr. & Comput. Eng., Calgary Univ., DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/COGINF.2005.1532611
- Tutorial: Data Structures, Types, and Abstractions, K. S. Shankar, IEEE Computer 13(4): 67-77 (1980)
- Abstraction Techniques in Modern Programming Languages, M. Shaw, IEEE Software Volume 1 Issue 4, October 1984
- A Theory of Architecture for Spatial Abstraction, Juyang Weng, DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/DEVLRN.2009.5175545
- Work in progress: Abstraction as a vector: Distinguishing engineering and science, Gregory Bassett , Department of Philosophy Aquinas College Grand Rapids, Michigan, DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/FIE.2012.6462373
- The Influence of the Level of Abstraction on the Evolvability of Conceptual Models of Information Systems, Jan Verelst , University of Antwerp, DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ISESE.2004.1334890
- System-Level Abstraction Semantics, Daniel D. Gajski Andreas Gerstlauer , University of California, Irvine, DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ISSS.2002.1227183
- A taxonomy of model abstraction techniques, F.K. Frantz , Computer Sci. Corp., Syracuse, DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/WSC.1995.479055
- Modularization around a suitable abstraction, Stephen N. Zilles, DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/AFIPS.1975.99
- Ubiquitous Abstraction: A New Approach to Mechanized Formal Verification, John Rushby , SRI International, DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ICFEM.1998.730581
- Lisp: A Language for Stratified Design, Abelson, Harold; Sussman, Gerald Jay
- SOFTWARE ENGINEERING FOUNDATIONS: A SOFTWARE SCIENCE PERSPECTIVE, YINGXU WANG, Auerbach Publications
- Recognizing Design Decisions in Programs, Spencer Rugaber, Stephen Omburn, and Richard J. LeBlanc
- Using Function Abstraction to Understand Program Behavior, Philip A. Hausler, Mark G. Pleszkoch, Richard C. Linger, Alan R. Hevner
- Abstraction and Variation, Diomidis Spinellis ,IEEE Software September/October 2007, DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/MS.2007.127
- Software Evolution based on Formalized Abstraction Hierarchy, Timo Aaltonen, Tommi Mikkonen
- On Abstraction and Interpretability: a Behavioural Perspective, Raphael Pfaff, Keith J Burnham, Control Theory and Applications Centre, Coventry University
Non-academic writings, blog posts, rants
- Abstraction page from Wikipedia
- Indirection Is Not Abstraction
- Abstraction Considered Harmful
- ABSTRACTION VS COMPRESSION
RSS Feed
