Of course I've read it. He says just the foundations are math. He says actual programs (e.g. those implementing networking protocols) are not math. Curry and Howard beg to differ.
They can be interpreted as math, but they aren't really. If you are using Coq or something verified it can be, but especially when you are using a dynamic language and you have no idea of the types of objects that will be passed as parameters or when you are just slapdashing bits of scripts together (like, "hmm, that failed, maybe I should just +1 to it?") it's hard to compare that to the rigorous discipline called math.
Math went on for millenia without computerized proof checking and yes, some of those proofs were buggy. The difference between a professional mathematician and a software engineer is no more than that between a C and a Prolog programmer. Anyone who has written both proofs by induction and recursive programs can easily see the correspondence, even without the Curry-Haskell proof that the correspondence exists.
You are correct that it's too strong. Most interesting programs cannot be fully studied analytically. The largest piece of software that has been proved correct is less than 10,000 lines of code. (Sadly, I have no reference for that - a recent speaker here talking about software testing made this claim with a reference that I have forgotten.) But real programs very quickly get to the point that it's impractical to fully understand them analytically. We have to execute them and observe their behavior.
Sorry if I seemed offensively skeptical, it wasn't my intent. I was wondering if I was missing something obvious ...which happens more than I'd like to think about. I agree with you on the lines of code. I think SeL4 is about 9,300 and I can't come up with something much longer (I don't think CompCert can really count because it's really just a lot of separate smaller programs running in succession, and generally one probably doesn't count Coq code as part of the program being verified, but everybody's got their own opinion).
I read the article and disagree. Computer science is a discipline of applied mathematics.
Saying that computer science is not mathematics because it involves real world complications, is like saying that experimental physics isn't physics because it is not done by theorists.
I'm having a hard time seeing how you can come to that conclusion based on the article you reference. Certainly a mathematical proof can be written in a program-style formal language, and then that type of programming becomes equivalent to those types of proofs.
However, programming in general is simply not like that, and programming in general does not, to me, seem to be anything like doing math.
And since that's a very personal statement, let me add by way of context that I have a PhD in math, I have programmed for a living, and I have written computer verified proofs.
It seems to me that most of the people who claim that "programming is math" (and there are many, but perhaps not as many as the OP is implying) have never actually done any math at an advanced level.
I'd be happier saying that programming is a lot like doing word problems, where it's essential not only to get the right answer, but also to use the the right terms, with the right grammar, and in a limited amount of space.
>programming in general does not, to me, seem to be anything like doing math.
Hi Colin, can you substantiate that? PhD in CS here and I've done some pretty hardcore math in my academic life.
After writing lots of proofs and lots of programs the two activities don't seem that dissimilar. They are very different "programming languages" indeed, but debugging, modularity, recursion are important for both activities. To give a more concrete example: for my thesis I've implemented at one point a geometric algorithm. Some of the computer code proved buggy so I went to the white board and simply increased the complexity of the math formulas, which allowed me to write less code. I don't see an immense difference between this and, say, combining C and Python code in the same project.
>> programming in general does not, to me,
>> seem to be anything like doing math.
> Hi Colin, can you substantiate that?
It's a statement about what I feel. As I say, I have a PhD in math (Pure Math: Graph Theory and Combinatorics). I have written many, many programs (both for money and not for money, both for myself and for others.)
Coming up with proofs of things believed true but not yet proven does not feel to me to be at all, in any way, like programming.
> After writing lots of proofs ...
What sorts of proofs? Are these proofs of theorems, or are they calculations of formulas?
> I went to the white board and simply increased
> the complexity of the math formulas
This feels to me like you are using "doing math" in a similar way to the way that someone "uses math" when adding up the grocery bill or dividing a restaurant check (but obviously insanely more complicated). I, too, have frequently stepped to the whiteboard to make more complex calculations, or derive more complex formulas, in order to simplify computations that must be done. That's not what I call "doing math."
As I say, programming feels more to me like solving word problems, and I suspect that most of the divide and argument around this topic is caused by a lack of precision in the definition of "doing math".
>Are these proofs of theorems, or are they calculations or formulas?
A calculation is a kind of proof, isn't it? Lots of papers contain theorems and lemmas of the form "f(x) = g(x)". I don't think proving such a formula is the same as applying some well-known algorithm (grocery / restaurant bill).
And there's the difference. I do not think a calculation is necessarily a proof, but some proofs are accomplished by calculations. Some papers may contain a proof that "f(x)=g(x)" and proceed to prove the result by calculation, but that's not the only kind of proof, and it's not the only kind of calculation.
And doing the kind of calculation that's in the intersection is not then programming. Sometimes in the act of programming you will do some math, but doing the math is enabling the programming. Doing the programming is not doing the math. It's a separate activity and a separate skill.
Of course the boundaries are blurred, but I've honestly seen people write a program to take data from a database, present it nicely on the screen, and then assert that programming is just math. I doubt you're claiming that, but I've seen it claimed, and I think it's not only wrong, but misleading, and demeaning to both subjects.
Sometimes you will use math in programming, and sometimes you will use programming in math. That doesn't mean that either is the other.
And now I'm going to be controversial.
And in case anyone else is still reading, here's a theorem:
Theorem: A prime number can be written as the
sum of two squares if and only if it
is of the form 4k+1 .
Just as there are many ways to write a program to accomplish a given task, there are many proofs of this theorem. If you're a programmer, and you think that programming is just math, then you should be able to come up with a proof for that theorem.
The reason this is controversial is that many mathematicians couldn't come up with a proof quickly either. Here's another:
Theorem: A number N is prime if and only if (N-1)!+1 is
a multiple of N.
And finally, one from my own area:
Given a graph G=(V,E), a proper coloring is an assignment c:V->{1..n} of
integers to vertices such that for every edge (u,v) in E, c(u) != c(v).
(In words, color the vertices so that the endpoints of an edge are always
colored differently).
The "Chromatic Function" of a graph takes the number colors and returns
the number of proper colorings.
Theorem: For every graph, the Chromatic Function of G is a polynomial.
People say that a good programmer can pick up a new language and/or library quite quickly and become productive in fairly short order. Most of the comments on HN about hiring practices say that you shouldn't test for knowledge of language or libraries or frameworks, but for actual ability to get things done.
If programming is math, and someone is a programmer, shouldn't they be able to prove these theorems?
========
Disclaimer: This is a stronger position than I'm actually willing to defend, but I'm interested to hear people's views.
ADDED IN EDIT: I've spent way too long on this and have things I must do. I'll return later to check for any replies. I'll also get a HN_Notify email if you do reply. Or email me directly.
Not every programmer can write any program with equal ease, can we? It depends on your knowledge of available primitives: programming languages, libraries. One who knows OpenGL will have an easier time spinning a 3D model than another who parses log files for a living. Similarly, a graph theorist like yourself will find it easier to prove theorems of form 3. than the rest of us. (At least half of th. 2 seems easier though. Suppose N divides (N-1)!+1; none of 2...(N-1) divides (N-1)!+1; so none of 2...(N-1) divides N.)
I guess the main confusing part about the Howard-Curry isomorphism is that the code / comment conventions are commonly reversed between proofs and programs. Programs show a sequence of actions, and may show machine state in the comments, e.g.
...
x = x * f; //x now contains factorial(n)
...
Proofs show state instead (i.e. the proposition that was proven so far), and may contain the operation in the comments:
...
(x + y) ^ 2 = (x + y) * (x + y)
Using the distributivity of addition:
(x + y) ^ 2 = (x + y) * x + (x + y) * y
...
In either case, you:
- start with an initial state
- choose a sequence of operations from an existing set
- end up with a desired state
If either your program or proof has bugs, there are certain initial states that will break some step in the operation sequence and cause an undesired final state.
I've not been able to study the link about Howard-Curry isomorphism, but it seems largely to be talking about writing proofs in code. That's not the point. There are people who program for a living who I expect can't do that, and I expect that because I believe there are people who program for a living who can't do math (yet).
Work has taken me away and I can't reply at length. I'm trying to find a math equivalent of FizzBuzz. I still claim programming is not math, and math is not programming. Skills in each can help the other, but aren't necessary.
Engaging in the activity of programming is not "doing math."
I will return to this topic when I can - now is not a good time.
PhD in CS here as well, and I've passed on doing a lot of hardcore math. If you're going to call what I do "math," then I feel you've stretched the definition of "math" to the point that it's meaningless.
Also, one mathematician that I've worked with would object to calling CS math because he doesn't want it infecting his beautiful discipline!
And if those functional languages are Turing complete, then they are equivalent to all other Turing complete languages, and thus the C-H isomorphism would hold for all Turing complete languages.
Nope. C-H concerns the simply typed lambda calculus which is not Turing-complete. Thus C-H only applies to non-recursive functional programs (or equivalent).
A proof is a program, but a program is not always a proof (as proofs must terminate).
computer science = information theory + software engineering
My opinion is that education should split computer science into the information theory part and the engineering part. The information theory part might even merge back into the math departments where it came from.
I think the integration of software engineering as the core of a computer science program essentially destroys the computer science program. Sure, many people with CS degrees wind up doing software engineering, but comparing CS to SE is like comparing a metallurgist to a blacksmith.
:-) I think another important thing to note is that both software engineers and computer scientists reinforce and add value to each other's work. CS can improve and verify the methods employed by those in SE and those in SE can provide direction (necessity is the mother of invention) to and implement the methods developed by CS. It's a very unrefined observation, but I think it gets the general idea across.
education should split computer science into the information theory part and the engineering part.
Then the engineers will complain that "Software Engineering" doesn't have enough rigor to be called engineering. Actually, it's been happening for years.
The problem is that there are two kinds of "software engineering." There's the practice of software engineering, which is the (hopefully) disciplined process of designing and implementing software. We're not sure how to best do it yet, but we all agree that it's important to get right because it's being done every day. Then there's software engineering research, which tries to evaluate ways in which people build software - but it's goal is not itself to build software. I admit I have been unimpressed by some software engineering research, but at the same time, I have no problem saying that the practice of software engineering is extremely important.
Actually, I think information theory is the only branch of science that has something genuinely useful to say about computers. Unfortunately, it has few people working on it in the context of computer systems. The world is dying for useful models of (real) CPUs and complex networks based on information theory, but that's not really happening. Computer "scientists" rather spend their time building example systems that no one will ever use, or creating theoretical models that have no connection to reality. No idea what the purpose of either is.
I have a problem with his analogy to physics. The experimental physicist purpose is to verify in the real world the laws discovered... but the person actually using those laws to build products (I'm skipping a few steps) is called an engineer. Physicists prove the existence of atoms then engineers use knowledge of them to build chips.
But we don't start grouping those engineers in with the physicists. We treat those as two separate disciplines. Well, lets keep computer science a theoretical science and call those people who apply those theoretical discoveries engineers. Much neater and cleaner and makes sense to me.
Which is a fair point - I grapple with how much of what I do is science, how much is engineering, and how much is neither. But, the problem is, that's what the word "computer science" means now. We could try to retroactively redefine a word to fit what we feel is a more natural division, but how often is that successful?
In what I do (mostly business cruds) it is mostly an art. The skill is not to get it done, but to organise the code effectively so that it will be easy to debug and adapt and reuse etc. It really doesn't feel like a science and more like being an editor of an anthology.
I consider that software engineering. "Doing" computer science means you're doing research. To keep abusing the physics analogy, your work (software engineering) is to mine (computer science) as mechanical engineers are to physicists.
Interesting. I talked about this with a friend, who did her BS in Math and Physics and now is a PhD in engineering. What we finally agreed was that physics is just so vast, that the `practical' aspects have spawned engineering branches. i.e mechanics == mechanical engineering, electromagnetism == electrical engineering, atomic physics == nuclear engineering and so on. Maybe we should do the same with Computer Science
Note to OP, I'm really not a huge fan of people posting links to their own blogs...
And in response to your essay, which by and large was tldr, I don't think many people run around saying that CS is math. Many computer scientists, as I'm quite sure you know, need to model their computable structures formally, show reductions or equivalences to other well-studied constructs, and then use the properties of these constucts to establish the expressiveness/complexity/whatever of their model. If outstanding questions remain then it can motivate basic research into the relevant mathematical field (particularly true with cryptography). These people "do math" - many other's from a CS background don't.
I've been here for a few years. It's a common enough practice that I felt it was okay. Further, I wrote this because I have made the same comment here at least five times (http://news.ycombinator.com/item?id=3596446).
is Computer Science the same as Software Engineering or Software Development? If it is then sure, this article makes a fair point, but I've always thought these were related but distinct things. And if they are in fact distinct, then Computer Science is the part that is Applied Mathematics by another name.
But really, all of this is just quibbling about semantics.
As much as I agree that everyone is just quibbling about semantics it is something that needs to be finalized and agreed on.
In some states it's illegal to say you're an engineer unless you specifically have an engineering degree. Most CS degrees are offered as a science degree with an alternate Software Engineering degree being an engineering degree. There's also a noticeable gap in what you're taught depending on which path you take. Friends of mine who majored in software engineering ended up learning more practical languages, how to use source control, software engineering practices, and never had to take a class related to the theory side of it. Whereas half of my classes were information theory, and abstract or theory based math classes.
Does this make them better programmers because they know more languages and tools? That's subjective. However, there are times when you need a computer scientist and not a software engineer but most companies and even developers themselves couldn't tell you the difference between the two.
Purely hypothetical at this point but suppose you were tasked with creating the first ring based authentication system. This involves a decent understanding of group theory . I don't doubt for a second that a software engineer would be able to accomplish this after first teaching them self about group theory but my first bet would be to go to the person with the CS training. Sure they might not be able to code it as well but once the idea has been developed and proven to be mathematically sound it can just be sent off to the engineer.
Programmers are perfectly comfortable talking about history,psychology,philosophy,economics,the arts,but when math comes up everyone starts crafting intricate theories why it really has nothing to do with his craft(and is therefore not worth wasting time on).Is this a rationalized adult version of math phobia?
There are two "extreme" ways of doing things, the "crafting" way in one side of the spectrum and the "engineering" way on the other side.
You can "craft" a car without knowing a single formula, but that proved to be inefficient.
In programming is kind of the other way around. There is a way to use formal mathematical methods to "engineer" programs, but for general use they seem to be economically "inefficient".
The article can be efficiently summed as: Computer Science is not always Math, sometimes it is more of a Science or Engineering or something of all of them.
I think this is one of those places where a word has different meanings to different people and correctness takes a religious quality and fruitful discussion requires telepathy. Also often depending on the resolution of the definition and where a person stands on if the thing and its description can/should be distinguished.
People who say computer science is math I suspect are hard pressed to find anything that isn't. Myself for example, I define math as the maximal object that has something to say - about anything that has structure - in a systematic way. You magnify/exaggerate a certain aspect of the structure you think is key and explore it in a systematic way to gain insight on the whole thing. So while aspects of computer science are more engineering or science than math, I can look at the whole system of doing computer science in an engineer like function as mathematically describable.
Still haven't read through all the articles referenced to in the comments, but please - do not equate "what I do every day as a computer scientist" to "what computer science is".
Let's keep the ideals, shall we?
I would claim that Computer Science is a term that is supposed to apply to any science directly interested in computation. I really see no point in that. Mathematicians are interested in algorithms and complexity and the like, software engineers/db engineers are concerned with databases and UIs. There are different programming languages for each purpose. I see no reason to insist on clumping them in the same group.
tl;dr: every study involving computation or programming doesn't need to be in the same department.
I believe that designing and building software systems is not "equivalent" to experimental physics, that it is not "experimental" computer science. Following the metaphor, I believe it's more accuarate to relate it to design and engineering. As in physics, there are very exact scientific theories that, mixed with technical/practical knowledge and insight about systems and people, can be used to create technology.
But I would also argue that there may be a way to "experiment" in a similar way physicist do, and it's by looking at "computing" as a phenomenon of the natural world.
Computing can be considered a science similar to phyisics, because it can be seen as laws that describe nature, or more specifically how information is processed in the natural world. This "computing" works at a "higher level" than physics, which studies the laws of the "hardware". The most used example is the DNA, with information in a higher level of abstraction than the chemical physical support.
I always find amusing to imagine what if Newton had developed his theories as a way to solve practical problems instead of trying to explain motion laws[1], and how maybie that's what happened to "computing".
And software engineering is quite dissimilar, if not completely different to computer science. Creating API's, building user interfaces, testing, has little to do with computer science, or information theory, or mathematics. Yes, it has some overlap, but not nearly as much as academics like to think.
Take an example as implementing a 3D renderer. A computer scientist might argue that underlaying 3D calculations should be correct. A software engineer might optimize for speed, and simply allow incorrect/imprecise calculations, as long as the rendered result does not look very different.
Except underlying that 3D renderer is a whole bunch of Computer Science research that had to be done in order to allow the engineer to make an optimized implementation. And I doubt a decent Computer Scientists would argue that. In fact, you might need some more CS (or science in general) to figure out what tolerance can be allowed for. Further more, while an optimized implementation is good, an optimized algorithm is probably even better, and right there i more CS.
This is a problem of definition more than anything else. I feel more comfortable thinking of Computer Science as the Math used to study algorithms and processes. The rest, although based on Math and the scientific process, looks more like Engineering to me.
Computer Science has always seemed to me to be the study of algorithms and information, correctness, methodologies, and their applications. Math is used in order to advance this knowledge. It is readily apparent to me that everything in CS is applied math and logic.
And in the same way a mechanic uses physical principles (arrived at by way of math), software engineering uses insights, practices, methods, and languages (which are mathematical entities to control a Turing machine) developed by computer science. Computer scientists in turn also learn quite a bit from challenges found and attacked by the engineers.
A few computer scientists I've met have math degrees and they enjoy exploring intersections of discrete math and formal methods; some also do research almost exclusively in engineering / application domains (e.g. computer graphics). And, some engineers I know do quite a bit of graph theorizing before hitting the keyboard (whether they recognize it or not) because it's useful.
A good SE will be a computer scientist when faced with a new, challenging problem and a CS will engineer on occasion to help her research.
http://en.wikipedia.org/wiki/Curry%E2%80%93Howard_isomorphis...
reply