From the April Communications of the ACM, the Kode Vicious column is on The Data-Structure Canon.

The reader question is:

In most areas of science there are a few basic underlying laws that inform the rest of the study of a given subject. Physics, chemistry, and electrical engineering all have these basic equations. What are the basic equations in computer science? Or is computer science baseless?

In other words, what's the fundamental intellectual basis of computer science? Well, according to KV, it's data structures!

If there were any set of basics that I wanted to hammer into software engineers and programmers, it would be the basic data structures, their features and pitfalls. ...

The basic data structures are the array, list, tree, and hash table. That seems like a short list, and I'm sure some of the more experienced readers of this column are warming up their mail applications to write me nasty notes about how there are more basic data structures than just these four. To these people I say, "Go for it!"

What I find most interesting about this list is how many programmers take it for granted and how few of them understand the implications of using one data structure versus another. Try as I might, I cannot lay all the blame at the feet of the programmers using these data structures; a good deal of the blame has to go to their teachers and the legions of poorly written "how to program" books that emphasize how to use a data structure rather than the underlying implications of what happens when they are used. Abstraction is a fine thing-it makes understanding large systems easier--but it also can obscure important facts: in particular, the performance implications of certain choices.

*snip*

Given the different complexities I've just mentioned, I think you'll see that these four data structures, which form the basis of most computer programs, are worth studying time and again. A good place to start is Knuth's

The Art of Computer Programming, Volume 1, Chapter 2, which covers all of these subjects more seriously and in depth. When you're done reading all that he has to say, please write me, though I should be retired by then.

Interesting. Although he probably conflates computer science with programming a little too much for my taste, I'm probably mostly in agreement with KV's point of view. But I was wondering what all of you out there in Computer Science Land think?

- Log in to post comments

Erm, Church-Turing thesis?

Computer science is not science, it is engineering.

A good rule of thumb is that if a field of study has to include the word 'science' in its title, then it isn't (e.g. Political Science, Library Science, etc.).

My definition of science is "a model of reality", which works quite well for physics & chemistry. All laws, theorems, postulates, and facts in physics & chemistry pertain to explaining what reality does. What is the reality of computer science? I guess I would have to say it is information.

The whole point of graph theory, Boolean logic, automata, computational geometry, computability, complexity, algorithms, data structures, etc. is to contain, morph, manipulate, understand, and change information.

So I guess I would say the basis of computer science is information theory. For example, what separates sorting algorithms is how they extract and use information (commonly by comparing two items) from the data to put it in order.

Sorry, forgot to address Tex's assertion of engineering.

Computer science is not engineering: not even close. I'm not even sure this merits real argument simply because you cannot practice computer science. You can *use* computer science to solve problems (the engineering) but computer science is not in itself engineering because the requirement of any engineering field is the practice of it.

Building a bridge is engineering. Designing an EM transceiver is engineering. Analyzing the complexity of bubble sort is not engineering.

Political science, sociology, economics, etc. are "soft sciences" in that they are rooted in human behavior.

If you use my previous argument, library science is actually fairly close to computer science in that both deal with information. Library science is not about shelving books.

Thanks, everyone. This is pretty well the reaction I expected. The root problem is that KV sees computer science as more or less the same as computer programming, which I don't think it is nor do I think most computer scientists see them as equivalent.

Which raises another interesting question. To what degree is computer science just programming? And, to what degree is the practice of computer science the practice of programming. I think some Venn diagrams are called for!

No, Colin #4, I don't buy your argument. Engineering doesn't just mean making stuff, it also includes all the supporting theory and principles. As you say, building a bridge is engineering, but so is designing a bridge, and so is the theory used when designing that bridge. And the generic theory of how how cable stayed bridges, suspension bridges, box girder decks, foundations, etc. work.

Analysing a bubble sort that can be realised on a computer is just the same as calculating stresses in a notional structure that could be built.

Both use mathematics and general priniciples to analyse and describe what's going on.

Engineering disciplines share one important feature with sciences: a common core of evidence-based rationality - but being rational is part of being a science, not the whole of it.

Computer science is definitely engineering in my opinion. It's about understanding and designing technologies in the man-made world. It's not about understanding the natural world.

Computer science (as described in the previous posts) seems to be the theoretical foundations of computer programming (and perhaps computer design). It's studying computer programming without the programming! (Perhaps Library Science is libraries without the books?)

So I say CS is engineering, and none the worse for it. Be proud of it!

However, I do agree with your previous post's opinion that information theory is probably the basis of computer science (if one thinks of CS mainly in terms of algorithmics rather than designing processors, for example). But CS isn't information theory, in the same way that structural engineering is not physics.

agrthink

I'm pretty sure computer science is just logic. Curry-Howard, anyone? Proofs are programs, programs proofs? Saying there aren't laws of CS is like saying there aren't laws of logic. In fact, it's the exact same thing as saying there aren't laws of logic.

Sam C:

I propose a middle ground - CS is both engineering _and_ science.

Certain aspects of CS, like Turing machine, computability, lambda calculus are pure math and can be thought of as abstract science.

Other aspects, like complexity theory are engineering.

Sam C, is there a cultural/national/academic difference/distinction here?

Computer science: boolean negation

Computer engineering: NOT gate

Electrical engineering: MOSFET

Chemistry: semiconductor doping

Physics: quantum mechanics

I know there is often a mix of the top three in that list and they can mean different things.

I'm not saying computer scientists don't dabble in computer engineering (and vice-versa) but I see them as entirely distinct.

Engineers also are required, by the nature of the profession, to dabble in the science. However, material science is not mechanical engineering even though there is a lot of overlap when designing, say, a bridge.

@4 John: I would absolutely concur that KV's basis of data structures is wrong.

There is a lot of imprecise meaning in all of these terms (computer science, programming, software engineering, computer engineering, electrical engineering, etc.) but I think there are clean cleavage lines between them all if you sit down and think about it.

In theory: they are all distinct; in practice: they are very often blended. The problem is that a lot of these terms are rooted and thought of in terms of practice.

Thanks, Colin.

Yes, the areas are distinct theoretically (if not in practice). In that sense, then perhaps we need to think of each separate area as having it's own foundational concepts. In that light, then perhaps data structures can be argued as the foundational concept for programming. I don't think it's a slam dunk argument, but I think it's easier to make than arguing that they're foundational for all of CS.

This article bothers me, although I'm not sure I'm going to do a good job of explaining why. I think part of it is the notion that computer science == programming---which, ok, fair enough, if you're going to claim that, then I'd argue that perhaps design patterns would also be a "foundation" or canon or what have you of *programming*. I think this bothers me because it completely ignores that CS is also about *algorithms* and all the theory that goes along with that.

The author's view/description of data structures courses is also troubling me, though. I'm currently teaching that course, and I can't imagine just teaching the course with the abstractions and implementations and ignoring performance issues. I mean, if you ignore performance issues, then all your course is, really, is just a list of data structures you *could* use. If a student came out of my course not being able to reason about what data structure is best in what circumstances, and give me pros and cons for various scenarios, then that student is *not* proficient in data structures. I guess I can't fathom a course being taught that way....Maybe that's just a digression, but that's really hanging me up.

It is not Engineering, it is Mathematics. Before there was a Computer Science degree program, people doing computer science were getting their degrees in Applied Mathemetics. I was at the University of California when Computer Science became a degree program and I know. I have a BSCS and it wasn't even available until my Junior year.

The theory of Algorithms is one of the main themes of Computer Science. My University Theory of Algorithm class kicked my b*tt and was about as pure of Comp Sci as you can get. I got a B+ in that class and not sure how I got that. Data Structures are derived from Algorithms.

Computer science includes areas of study that clearly don't fall under the "engineering" umbrella. The key unsolved question of computer science, whether or not P = NP, is a purely mathematical undertaking. Questions about resource bounded Kolmogorov complexity have no practical relevance for engineering. Neither does any other question of which complexity classes are proper subsets of each other.

Hell, computer science started without any consideration for building real world computers. Combinators and Turing machines were used to produce the initial mathematical results of recursion theory. You can argue that this is all mathematics and not really science, but nor is it engineering.

Okay, since no-one seems to have picked up on my comment, I re-assert the Church-Turing thesis, which to me seems almost self-evidently the foundation of computer science. It might not be in a form of a equation, but it is the fundamental statement without which it would be very hard to imagine computer science at all. Most of the comments seem to me minutiae of whether CS is science or engineering, but whichever it is, I challenge anyone to present a more fundamental fact about it than the Church-Turing thesis.

As mentioned in other comments - this is really the same argument you have for mathematics (is it a science?) and also for medicine. Medicine has clinical parts but also lab science parts... maybe that's a good analogy.

As for library science - hrumph.

mathematics (is it a science?)

Hell, no. Least me and my math degree say so! It's damn useful, and science would be screwed without it, but it isn't science.

CS is a mix of math, logic (which falls under the math, honestly) and engineering. It isn't science, though. There's no hypothesis, experiment, analyze data, accept/reject in there.

Medicine has clinical parts but also lab science parts... maybe that's a good analogy.

Medicine is applied science, hopefully. With the backing of a whole lot of 'pure' science - medicine is much closer to engineering than science, though, and doesn't really track to CS - they have an idea based on their training, do tests to check their idea, and apply a solution discovered by the more 'pure' science side.

Much like designing a bridge involves having the basic idea from your training, doing calculations to figure out what's necessary, and then using components and equations other people figured out. There is, of course, some overlap with science (and a lot of doctors and engineers are also scientists), but that's just because science doesn't have a good formal definition or delineation.

CS, though, is more into proving things based on certain assumptions (math part) or using existing data structures and methods to accomplish and end (programming == engineering part).

...accomplish and end..

Yeah, that should have read 'an end'.

And in response to the actual post - I'd say CS is as baseless as math or logic. They all work in the areas they apply to, so screw anyone who wants to reject 'em.

Not sure what I'd call it besides CS at this point, but I certainly wouldn't have chosen that name if I was given the almighty Naming Powerâ¢

Sigh...Entirely distinct fields that are so often confused...

Programming falls under the domain of SOFTWARE ENGINEERING.

SOFTWARE ENGINEERING is the meeting of the fields of COMPUTER ENGINEERING, BUSINESS, and COMPUTER SCIENCE.

COMPUTER ENGINEERING is a specialized sub-field of ELECTRICAL ENGINEERING, which is itself derived from ELECTRICITY & MAGNETISM, a field of PHYSICS, and is therefore itself APPLIED PHYSICS. APPLIED PHYSICS, obviously, is PHYSICS applied; PHYSICS is modeled on CALCULUS and, therefore, ANALYTICS.

BUSINESS is for the most part a meeting of STATISTICAL MATHEMATICS and ECONOMICS, and PSYCHOLOGY.

Lastly, COMPUTER SCIENCE is a meeting ground of FIRST-ORDER LOGIC, SET THEORY, COMBINATORICS, DOMAIN THEORY, GRAPH THEORY, RECURSION THEORY, ALGORITHM THEORY, and NUMBER THEORY. If you include the sub-domain of COMPUTER GRAPHICS as well, then COMPUTER SCIENCE also includes CALCULUS, LINEAR ALGEBRA, and MECHANICS.

Now that the distinctions have been stated, to assert that Computer Science is not a science is nothing short of ignorant; the complete opposite is true: In a list of the pure sciences, only Computer Science and Physics are directly derivative from Mathematics. Chemistry is derivative from Physics and Biology is derivative from both Chemistry and Statistics. Other "sciences" are impure to the point of being not worth mentioning in context of this debate.

If you seek the foundations of Computer Science, then look to the Church-Turing thesis, look to Boolean Algebra, look to Georg Cantor's Naive Set Theory and the ideas of Axiomatic Set Theory and Type Theory which followed from paradoxes such as Russell's Paradox, look to the ideas of Von Neumann and Godel. Look at all of the great logicians up to and after the early twentieth century and in their work you will find most, if not all, of the ideas which have since shaped the progression of the meeting of mathematical fields which we call Computer Science.

For a sample ``fundamental intellectual basis of computer science'' how about Turing's Universal Machine Theorem [1] (i.e., there exists a Turing machine that is an interpreter for all TM-programs). Knuth considers Turing's universal machine the first programming language interpreter. When you look at the mathematical consequences of the universal machine theorem, you get computability theory. When you look at the machine organizational consequences of the universal machine trick, you get the von Neumann architecture. (Turing was JVN's post-doc at Princeton.) The universal machine trick is also what lets you bootstrap higher-level languages on low level hardware. Etc. Modern computing systems are towers of interpreters starting with the micro-code level and working up. The ideas behind the Universal Machine Theorem get used as much as, say, Maxwell's equations get using in Electrical Engineering or Newton's Laws in classical mechanics.

[1]A.Â Turing. On computable numbers, with an application to the entscheidungsproblem. Proceedings of the London Mathematical Society, 42:230â265, 1936.

Engineering is also analysis - analyzing a bubble sort is really no different than analyzing a circuit design. Theory applies to both, although I wouldn't say information theory is the basis of computer science. Information theory involves a knowledge of things like entropy, not just logic and boolean algebra and signal processing which is predominantly taught in electrical engineering courses uses a lot of information theory. I think computer "science" is a combination of logic theory and software engineering, and is therefore mostly engineering because logic theory doesn't really have "open" problems like other sciences (like the dark matter problem in physics and what causes epithelial to mesenchymal cell transition in biology, for instance). I think Computer Science is a valuable field and should not be merged into engineering, although 90% of those who "practice" computer science are software engineers and should be knowledeable about engineering. Just my take.

Thanks, Mike & everyone else. This is a great conversation, let's keep it going!

My understanding of engineering (and correct me if I'm wrong) is applying methods and knowledge from science to create applications, fulfilling objectives and inventions.

Computer Science has a lot of engineering in it, like software engineering, computer programming and others. People have mentioned that the analytical equations are also present in engineering, but what's present in engineering is merely the --application-- of equations, methods and knowledge that have been obtained by mathemathicians and scientists, not the --derivation and deep property study-- of said abstract objects.

CS is much more than merely applying equations. It's area of study includes a whole universe of abstract objects whose properties computer scientists explore, like the complexity classes of computational problems, theoretical computational models, effective computational processes, etc.

Saying that Computer Science is merely about applying equations, methods and knowledge is basically not fully understanding the field. CS is a field of knowledge that deeply studies it's abstract universe, discovering patterns on the objects' properties, making statements, deriving and demonstrating algorithms and formulating theoretical computational models, studying their computational possibilities and demonstrating them. So if anything, CS definitely has a whole core of actually generating equations, methods and knowledge based on abstract studies rather than just using them.

In conclusion, if anything, CS is more Mathematics than Engineering. Engineering is the study (both theoretical and technical, as it was already stated) behind building and implementing things, and Computer Science is much more than simply a study of implementations, and an actual study of deep properties of computation and processing. Implementation is sure big among CS programmes, but we need to clarify that Computer Science is not limited to the application of scientifical concepts, but also the obtaining of said concepts by studying and researching.