# How important is knowing how to program for TCS?

Coming from a more mathematical background, I never really learned how to code. I am starting a PhD in TCS and many people were surprised by how little I knew about programming (and about computer in general). I can write algorithms in pseudo-code, but I don't really know any programming language.

I can imagine that someday I may have to implement some algorithms for my work, but then can I wait for this moment? Or is there something more?

How important is knowing how to code in TCS (in fields where programming is not directly involved) : is there reasons which could bring a CC theorist (for example) to know how to code? Is it worth spending a lot of time learning how to code? And if there are, is there a category (functional, imperative, object-oriented..) of programming language that would be more suited?

-
You should have programmed some in order to write meaningful, i.e. definite and runtime-reflecting, pseudo-code. Mathematicians often do neither. Also, if you want to actually use the theory you develop, chances are you will have to implement something. As for languages, you are probably better off learning something functional. C is nice for performance but hard to reason about and messy in many aspects. (As you can see, YMMW) –  Raphael Nov 7 '11 at 18:47
I concur with "Mathematicians often do neither." A simple test for whether a mathematician describing an algorithm has ever really programmed is to ask "What exactly do you mean by 'Given an X...'?" –  JɛﬀE Nov 8 '11 at 9:52
Programming, what's that? Theorems are my programs. A cooking procedure is different from the cooking art. Sorry, in more than 20 years I cannot read any program code. Actually, I hate this "being realized on PC" mess. (Already this notation makes ill.) Euclid could not program. Yet he made programs for centuries. –  Stasys Nov 8 '11 at 20:02
@StasysJukna: Euclid was actually a really really crappy programmer. He not only never implemented his algorithms, he never even ran them by hand on moderately complicated test cases. –  JɛﬀE Nov 9 '11 at 12:27
@JɛﬀE: Yes, Euclid was a crappy programmer, exactly this I wanted to say. We, in TCS, are tending to not distinguish between cooking books and cocking art. Euclid could. I have a great respect to people who CAN program. But I don't think that this feature means "one CAN in TCS". It will just not hurt. –  Stasys Nov 16 '11 at 18:31

Theoretical computer science is a broad field and the importance of programming depends on what you do in TCS. I will mention two ways in which programming can help you, without implying that these are the only ways.

First, if you design algorithms for problems of practical importance, implementing your algorithms and making the code available to others can be a big plus. For example, the convex hull problem arises in many fields, and people use software packages such as cdd by Komei Fukuda and lrs by David Avis to solve this problem. If they had published their algorithms only in papers, probably less people would have used their algorithms. More users mean more feedback and probably also more opportunities to collaborate, which is invaluable.

Second, even if you do not work in algorithms, writing a one-time code helps you to test a simple conjecture when the conjecture is suitable to numerical calculation. For example, if you wonder whether the product of three positive definite matrices always has a positive trace, it is easy to write a code to test it for some random choices of 2×2 or 3×3 positive definite matrices and find a counterexample. Although you do not advertise that you wrote any program to test the conjecture, programming can save the time which would have been spent in vain trying to prove a false statement.

The programming language to choose depends on what you want to do with programming, and it can be a topic for a whole book in my opinion. But if you design algorithms and want to implement your algorithms so that other people can use the implementation, then one important factor is availability. Although you can expect that most potential users of your code have access to a C compiler, you cannot expect that the same people have access to a Haskell compiler. For one-time programs, the choice is more based on available libraries, and includes the environments such as Matlab.

By the way, programming can also be fun.

-
+1 for the "programming can also be fun" –  Suresh Venkat Nov 8 '11 at 1:56
@SureshVenkat: In fact, if programming is fun, the question “How important is programming?” may not be very relevant. But then the most part of my answer will become irrelevant. How sad! :) –  Tsuyoshi Ito Nov 8 '11 at 2:13
I did not think of your second argument before, indeed it seems a really good idea to test a conjecture with a short program! As for programming can be fun, so it seems, but I have yet to see over all the long week-end learning =). –  Gopi Nov 8 '11 at 17:18
@Gopi: That said, many conjectures do not fit in this “test with a simple program” framework. For example, we usually cannot test asymptotic behaviors (at least by a simple program). But when you have some conjecture that can be tested, a little programming can be a powerful tool. As for fun, yes, I understand. I just did not want to ignore the “fun” viewpoint by only listing some motivations from the “usefulness” viewpoint. –  Tsuyoshi Ito Nov 9 '11 at 15:05
Knuth's notes on a problem solving class have a wonderful example of the interplay between conjectures and code (see Problem 1): www-cs-faculty.stanford.edu/~knuth/papers/cs1055.pdf (I particularly like the image of someone rushing into the classroom bearing a heap of printouts) –  Suresh Venkat Dec 2 '11 at 6:37

I feel compelled to cite Doron Zeilberger on this:

Opinion 37: Programming is Even More Fun Than Proving, and, More Importantly It Gives As Much, If Not More, Insight and Understanding.

Read the opinion, it's full of gems (btw he tends to be deliberately provocative). For example, "The best way to understand something is to teach it. But even better then teaching it to humans is to teach it to a computer".

My personal experience is that even when doing purely theoretical work you will need some computing tools. I avoid a lot of tedious routine algebraic manipulations with Mathematica. I test my half-baked conjectures by brute-forcing small instances on Matlab or Python. I have co-written one paper that's pure combinatorics, and that's the work that has benefited most from running extensive computer experiments to understand what's going on. Euler made huge tables of tedious calculations to get insight into problems. We owe it to him to use our tools to automate this process when we do mathematics.

Aside from that, if you'll work on algorithms and data structures, programming will give an irreplaceable perspective on issues of efficiency and usability. My opinion here differs with others somewhat. I think learning a functional language so that you get to write proofs that type correctly is a waste of time (I think it's a great point that people who have experience with a strongly typed language probably tend to write more carefully structured proofs; I just don't think it's worth your time to go through that exercise). Functional programming obscures issues of algorithm design and running time and emphasizes logic and semantics issues (and, of course, learning functional programming is probably a must and will come somewhat naturally if you're interested in logic/PL semantics). Similarly, I think getting into the OO details of Java and C++ is also not the optimal way to spend your time, as the purpose of OO is to write modular re-usable code. It's the way to go if you'll produce code for others to use. But in case you want to get insight into efficiency and running time, if you care about really efficient algorithms and data structures, I second the suggestion to look into C. It lets you stay close to the machine while still providing a reasonable level of abstraction. This way you get a feel of what's fast and what's slow, what is a reasonable data structure, etc.

-
"Functional programming obscures issues of algorithm design and running time and emphasizes logic and semantics issues". Fighting words :) –  Suresh Venkat Nov 8 '11 at 17:40
"Functional programming obscures issues of algorithm design and running time and emphasizes logic and semantics issues." Which is why it is a good choice if you work in the logic or semantics side of TCS. :) –  Radu GRIGore Nov 8 '11 at 18:55
Ahem. –  JɛﬀE Nov 9 '11 at 12:31
@Sasho: All ordinary techniques still work in functional languages. The only "problem" is that functional programming encourages a style of programming and data structure design which ordinary techniques of algorithmic analysis are under-equipped to handle. (E.g., what's the big-O of function composition? The operation is trivial, but it completely breaks the assumptions of asymptotic complexity -- there's no simple numeric metric of size for a functional input.) –  Neel Krishnaswami Nov 10 '11 at 8:44
@SashoNikolov: Whenever I teach a graduate data structures class, I really really wish I could assume that everyone had some functional programming experience. Instead of spending three 90-minute lectures to explain persistence, I could just say "Hey, did you notice that your data structures already do THIS?" –  JɛﬀE Nov 10 '11 at 14:09

You can be a quite successful theoretical computer scientist without programming. For a few people, programming is quite difficult, and if you are one of them you shouldn't despair and switch fields.

However, for most math and computer science graduate students, learning to program is not particularly difficult, and is a skill which is very useful. You should learn a programming language, and if you enjoy it, you should try to get enough practice to become reasonably proficient at it. Then, when the point comes (and it will) that it will be useful in your research to write a program, you will be able to do it.

If you don't learn to program now, it is quite likely that when you eventually need to write a program, you won't have time to learn, and so you may not actually write it, and end up being less effective in your research. While getting a grad student or an undergrad to do this for you isn't too hard, there are a lot of times when it's much easier and less time-consuming to do it yourself rather than explain the problem to them.

What language should you learn? I'd recommend an object-oriented language, since these are the ones that are currently in most use, and I suspect this will be more true in the future. Maybe Python or Java—they're both object-oriented languages, and while they're used less in practice than C++, my impression is that they're both much, much easier to learn. (Caveat: I don't know C++, despite having worked at Bell Labs, so maybe I'm wrong about this.)

-
I see the truth in your third paragraph :). –  Gopi Nov 8 '11 at 17:29
"However, for most people, learning to program is not particularly difficult" -- my experience leads me to disagree with this, but most people are not TCS researchers. –  Max Nov 8 '11 at 19:24
With the rise of Sage, it is possible to work with a nice, popular language like Python while still having Mathematica/Maple/Matlab style mathematical libraries instantly available. –  András Salamon Nov 11 '11 at 13:37
C++ has the most advanced type/metaprogramming system of any mainstream general purpose programming language I've seen, except the family of Lisp languages. So if you are into type theory, language design or compiler theory, or more broadly into formal semantics, you may want to be familiar with it. In addition to C++, Java and C# are a must if you want to do research in experimental Computer Science, or hope to get a job as a programmer or software engineer in the industry. Python should be taught in high schools :D –  Antonio Valerio Miceli-Barone Nov 29 '11 at 1:10
@AntonioValerioMiceli-Barone: I have to disagree, at least for type theory, language design, formal semantics and programming language theory (PLT) in general: C++ is not the language to learn for those fields; TT and formal semantics relate almost exclusively to functional programming, while the PL community is more diverse, but prefers languages more elegant than C++. Haskell is the "mainstream" language with the most advanced type system, followed by Scala (less advanced, a bit more mainstream). C++ does have interesting features, but is too low-level for modern taste. –  Blaisorblade Mar 31 '12 at 1:19

There's another answer that no one has really brought up. Programming can actually lead to interesting theory. A lot of the recent developments in hashing (especially tabulation hashing) are motivated not by theoretical concerns per se, but by the fact that the theoretically optimal algorithms aren't that great in practice. This of course is something you don't know unless you can write code.

Even in the realm of exact exponential time algorithms, a motivation is producing algorithms that can actually work. SAT solvers are the canonical example of this.

In short, the ability to code allows you to realize shortcomings and weaknesses in what might look like optimal theoretical results, and that in turn opens up new theoretical research directions.

-
Your answer could maybe help on the question about Empirical results in TCS. –  Gopi Nov 18 '11 at 15:15
maybe: but that thread has long died out :) –  Suresh Venkat Nov 18 '11 at 16:20
Indeed, I did not look at the date, it was in the last newsletter I received, in the section "Greatest hits from previous weeks" =). –  Gopi Nov 19 '11 at 10:39

Three points:

1) There is an approach to mathematics called Experimental Mathematics (see also wikipedia://Computer-aided proof) where you use computer programs to investigate about patterns and structures of objects in order to come up with analytic proofs about these objects. For this approach, you better know how to program. You can be sure you will find yourself in the need of this approach to prove very theoretical statements. I believe that snobbery against programming often turns out not to be really helpful in TCS research.

2) When you learn how to program, as byproducts you learn skills that are useful in TCS. One example above all: I found out that people with coding background tend to type-check their proofs more. Even better, they tend to very often define the type of the objects they are considering (ex.: "let's consider the operators $A \in L(X,Y)$ and $B \in L(Y,C)$). This is good for the readers of a manuscript. Compilers (and interpreters) turn us into good scientists :) For this kind of skills, I feel to suggest some strongly-typed functional language.

3) When you say "to program" do you also mean "to linear program" or "to semidefinite program"? :)

-
Nobody I know uses "to program" for "to linear program" or "to semidefinite program". You would say "to construct/solve a linear program" instead. –  Peter Shor Nov 8 '11 at 14:37
@PeterShor Point 3 was not serious –  Alessandro Cosentino Nov 8 '11 at 14:43
And of course, you should also learn to linear program and to semidefinite program ... both useful skills. –  Peter Shor Nov 8 '11 at 14:50
+1 for point 2, I actually was taught a little OCaml when I was an undergrad, even-though I only used it for one year, I took the habit to check the types of my proofs. –  Gopi Nov 8 '11 at 17:27
I program dynamically! –  JɛﬀE Nov 9 '11 at 12:33

Thank you Gopi for this question. I'd like to extend the many interesting answers in another dimension that hasn't been mentioned yet.

Research is not the only thing we do at university: if you want to stay in academia, eventually you will have to teach. If you are lucky, you'll have to teach courses that are quite far away from your area of specialisation. Quite likely you'll be assigned courses with a substantial programming component. This is where even a moderate ability to program helps substantially: you'll be much better a teacher if you know how to program. First and foremost, you'll be more comfortable with the material, you'll be able to answer student questions better, and you understand the difficulties that students have with learning to program, as you've experienced this learning process yourself. Moreover, you can produce better teaching material. For instance you can test programming exercises yourself before giving them to students, and fine-tune the level of difficulty.

There's an additional pragmatic dimension: teaching involves various repetitive tasks that a skilled programmer can often automatise, like quickly knocking up a website that students can use to submit coursework, and have it graded automatically (according to the number of automated tests the code passes).

-
Thank you for another great argument :). –  Gopi Nov 9 '11 at 13:01
“If you are lucky, you'll have to teach courses that are quite far away from your area of specialisation.” Is that lucky…? –  Tsuyoshi Ito Nov 9 '11 at 13:16
@ Tsuyoshi: Well, it forces you to familiarise yourself with a new subject area. In the short term, that means a lot of work (which amortise in the long run, as you'll likely to teach this material more than once). At the same time, it broadens your intellectual horizons considerably. –  Martin Berger Nov 9 '11 at 14:00
@TsuyoshiIto: Yes! –  JɛﬀE Nov 10 '11 at 14:10

Programming is a good way to improve your understanding of various concepts, but it is also a dangerous time sink.

A typical argument against programming is that it makes you spend time with unimportant details; a typical argument for programming is that it makes you realise that details you thought are unimportant are in fact important. Becoming good at programming mainly means becoming able to deal with the unimportant parts quickly. Becoming good takes a long time.

As for the programming language to learn: "all of them" is my (tongue-in-cheek) answer.

-
Finaly an argument against programming :). –  Gopi Nov 8 '11 at 23:58
@Gopi, I think that programming can be a lot of fun and that the better understanding you gain is very important. The other answers give great examples of how programming helps understanding. So I would encourage you to learn programming, and not give up if the enterprise does not seem to pay off quickly. –  Radu GRIGore Nov 9 '11 at 11:21
Proving theorems is also a good way to improve your understanding of various concepts, but it's also a dangerous time sink. –  JɛﬀE Nov 9 '11 at 12:34
@JɛﬀE, my opinion is preserved by the substitution [pseudocode->proof on paper, code->proof in a proof assistant]. –  Radu GRIGore Nov 9 '11 at 21:27

I'm late to the party, and these are all great answers, but I have another reason:

Visualization.

Yes, often you will work with things that can't be visualized, but often you will work with things that can. Knowing how to program is indispensable for this task, and visualization can offer you a lot of insight into a problem.

-
I know how to program, and I am absolutely hopeless at visualization. I also suspect that there are tools that will let you visualize things without doing a lot of programming; if there aren't, there should be, and maybe will be in a few years. –  Peter Shor Nov 9 '11 at 12:27
@PeterShor: Because you do not use C++! (Just kidding) –  Tsuyoshi Ito Nov 9 '11 at 13:17
@PeterShor: I'm not referring to any specific language or environment; MATLAB counts here. But knowing how to program can get you visualizations that would otherwise be incredibly inconvenient. For example, the space of two-dimensional positive-definite matrices is three-dimensional, and I wanted to visualize a family of constructs in this space. I had to come up with a transformation and then code it up to really see my objects. –  John Moeller Nov 9 '11 at 20:00
@John ... you're right, I don't think you could have done that any other way. –  Peter Shor Nov 9 '11 at 20:13

Just a quick point: knowing how to program gives me an additional tool in theory research. When I have an algorithm that I think will work, if it's easy enough, I might code it up and check if it actually does. If my idea doesn't (even) work in practice, it's not very likely to work in theory, and this approach often saves me from sinking an enormous amount of time trying to prove something that's false.

-
Tsuyoshi Ito wrote a similar argument in his answer (second point :)). –  Gopi Nov 21 '11 at 9:46
Oops you're right - I missed it. –  Lev Reyzin Nov 21 '11 at 16:21

No one here has addressed the practical issues of why someone studying TCS should learn programming.

If you are planning to do a PhD in TCS in a Computer Science department, there is a good chance you will need to take some non-Theory courses, and those will almost certainly be very programming-intensive. Depending on the program you are in, you may also need knowledge of non-Theory subjects to pass your qualifying exams.

When you finish your PhD, most job opportunities for TCS are in academia. If you work in academia, you will be expected to teach, and you might be expected to teach an intro-level undergrad CS class that will be more programming than theory. Even if you are teaching a theory class to undergrads, like say Algorithms, you can expect that your students will know more about programming than theory, and without knowing what your students know, it will be difficult for you to bridge the gaps in their understanding. I shudder at the thought of CS undergrads being taught by someone who does not know programming!

If you don't care about these practical concerns, then you can probably get by doing research without really knowing anything about programming. Certainly you have plenty of company in the TCS community, but mileage will vary depending on what exact area of Theory you're working in. For instance, if you're doing pure computational complexity theory, proving lower bounds on classes that no one has ever heard of, then it's likely that programming will be of no use to you. But if you're doing something more algorithmic, then I feel that being able to write good clean working code will strengthen your intuition if nothing else.

I recommend learning C (not C++). Pick-up a copy of K&R and read it front-to-back. C doesn't have many of the fancy features of modern languages, but it does have simple but elegant syntax and semantics, which you should be able to learn in entirety. However, even when you understand the language in entirety, it still takes practice to master writing good elegant bug-free code in C. Nevertheless, if you can master coding in C, you will be able to master any programming language you encounter. Furthermore, that discipline will help you think how the hardware thinks, which will be beneficial when designing algorithms.

Ideas like pointers are very important to anyone who does algorithm design, but unfortunately, languages like Java and Python obscure them from you, so that's why I don't recommend them as a first language to someone with a math background. OOP is more important for people who have to maintain huge software projects, not someone who is designing algorithms.

-

I would suggest you do not await the beginning of your course since computer science at any level involves implementing algorithms through a computer in order to accomplish/verify/solve any theory you will have to face throughout your course, ESPECIALLY at your level.

I had to program in grade 10 (high school) first, and I already knew how to use a command line and this really helped (this is to show you how "basic" programming skills are considered in CS).

The astonishment of your peers is well founded, since pseudocode and algorithms are among the first things one has to learn in order to program.

However, you are not to be completely lost in your forthcoming course since you can use your broader math skills (on your own) at your advantage to skip object-oriented programming to catch up faster learning a functional programming language.

• Functional programming is VERY math-oriented, considered harder to learn for its math background needed, considered very powerful (in its "simple", mathematic way to accomplish hard problems through elegant and "clean" means).
• Object-orientation is good when you do not want to understand underlying algorithms and implementation principles and simply want to "reuse" already existing objects.

I think you could tackle Haskell (usually not a first language) because it is purely mathematic, functional and can do basically anything you want it to. Learning Haskell would put you at a level where you would not need to learn much more to keep up, and would even put you in a situation of control and power over your course. If you're into statistics, learning R is a plus, but not near as much as Haskell. I have seen reports from mathematicians stating how surprised they were about its closeness to math and how it embraced their way of thinking.

Also, a challenge worth tackling (to get your hands accustomed to a programming environment fast) would be to install and use Linux (Ubuntu Linux will do). Trust me, you will learn a lot by playing with it...

These advices are the best way I know of catching up fast and surely for a mathematician in computer science. Besides, the open source community is very friendly and helpful and if you're stuck, IRC being the most direct way to talk about any subject through specialized channels (connect on FreeNode). Remember: asking is the only way to solve questions, be it to yourself, a forum, a search engine or in chatrooms.

-
I don't know how much you are answering the original question: I did not ask "how to", but more "what for". –  Gopi Nov 20 '11 at 15:45

An example of a C++ implementation of an interactive proof system is the following paper: Time-Optimal Interactive Proofs For Circuit Evaluation, by Justin Thaler. It is available at http://people.seas.harvard.edu/~jthaler/. It appears to be a step towards the goal of developing a practical implementation of general-purpose interactive proof systems.

Similar papers and related source codes appear at the website mentioned above.

-
Would you explain how this paper is related to the question i.e How important is knowing how to program for TCS? –  scaaahu Apr 12 '13 at 2:37
Even if it was an example of theoretical result which benefited from programming, it would not answer the original question? –  Jeremy Apr 12 '13 at 8:41
The question asks if there is a need for a complexity theorist to know coding. The paper mentioned above clearly uses experimental results to complement theoretical concepts; this requires coding. In any case, it took me a very long time to find a programming project that is so closely related to a central concept in theoretical computer science. I hope this post might be useful to someone on a similar search. –  lgidwani Apr 14 '13 at 11:02