Computer Science Looks for a Remake

...there is a deep malaise in computer science these days. Professors bemoan falling enrollments, a decline in prestige and a lack of attention to real-world problems. But, paradoxically, they say the future of CS has never been brighter, both within the discipline and in fields that computer technology will increasingly influence. Computerworld's Gary Anthes recently asked six CS professors what lies ahead for the field.

This piece isn't directly related to programming languages (in fact, I think this is one of the problems with it), but it will interest many LtU regulars.

To make this more relevant for LtU, let me rephrase the question: What's the most important and interesting CS research at the moment, from a PL perspective?

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Personally ....

I feel that the most important PL related areas are:

  • New forms of compiler optimization
  • New kinds of static program analysis Coverity style
  • Dependent types
  • STM
  • New kinds of memory management (region inference perhaps?)

Though actually I'm not sure about the last one. GC is probably good enough these days.

That said, I'm not terribly surprised enrollments are falling. My own CS course, at Durham university in England, is everything it should not have been IMHO. And Durham is a well respected university (it's in the league below Oxbridge).

Specifically vast amounts of extremely esoteric theory and zero practical skills. Some people like that, and others argue that CS shouldn't teach practical skills, but the overwhelming opinion of the student body here seems to be that it went way too far off the beaten track. We have debts we are expected to pay off and having little or no employable skills at the end of it just isn't acceptable. Not our conditions - the banks.

For instance the lecturers here have taught propositional SAT three times now (they don't appear to communicate at all), yet have not actually covered manual memory management, not even mentioned it in passing. This is true even though they had a whole module on C++! I think it's sad that constraint solving is allowed to take a whole year yet the basics of malloc and free are not taught .... that algorithms which require a million processors to sort a thousand numbers need to be learned but the stack is still mysterious.

This results in graduates who can do clause resolution on paper but aren't able to handle any real world C/C++ codebase, which despite the flaws of that language is what a lot of useful and important software is written in. Even Java can prove a challenge. So people end up demoralised and questioning whether a career in software is for them - of all my friends on the course, I'm the only one who wants to become a computer programmer. The rest are heading either into IT departments, network administration or some non-computing related field entirely.

If asked whether I'd recommend doing computer science at Durham, I'd definitely say no, especially with the fee increases that are coming through lately. It's not financially worth it, especially as even employers like Google are wising up and often don't require a degree.

This may be somewhat OT,

This may be somewhat OT, but...

It's not financially worth it, especially as even employers like Google are wising up and often don't require a degree.

I would be careful about recommending that people try to get programming jobs without a degree. There's 2 problems:

1. How/where to get educated. When I first started learning programming, I had no idea what were good sources and what weren't. I had no idea what was a good idea. I started with Visual Basic. I didn't know any better. I then learned Bash shell programming, and then C. I think this was a group of pretty horrible first languages to learn (I actually dropped Visual Basic pretty fast, so I didn't really learn it). And then consider, for instance, algorithm analysis. It took me a long time to discover Big O notation and what that meant. And then it took longer for me to discover that that was actually something that mattered and was significant, and wasn't just some obscure weird idea. Part of the problem was that I started out trying to learn everything online instead of getting some books, but even once I started getting books, I was getting the wrong books (go into a major bookstore's programming department... You've got "Learn Visual XYZ in 21 Days" type books, and sometimes AOCP is there. And that's usually just about it. None of that was remotely appropriate for what I needed)! Eventually I learned what was what, but it took years of floundering around.

And I've still got some issues in that department. I think overall, I am fine, and competent, especially considering the state of some programmers in the industry (ever read the Daily WTF? Good grief...). But I've still got gaps. For instance, I have never met another programmer. I've never watched anyone else program. I've never had anyone else watch me program. I've never worked with anyone else on a project. I've never had a wizard read my code and comment on it. Even in terms of just plain knowledge there are some things I am lacking that most CS graduates know, and some things that I haven't done that most CS graduates have.

2. How do you get a job without a degree?! Yes, sure, some jobs don't require a degree... but they do require 5 years experience in technologies X, Y, and Z. How can I possibly get 5 years experience in these things? Not to mention the fact that I have no social connections to anyone involved in computer science. At all.


Ah yeah, OK, two good points merits two responses:

1. How/where to get educated. I think you did OK. Everybody who learns programming does so in a different way, but it's usually by picking up tools and running with them. You may feel that you did not learn coding optimally by going VB->bash->C and you're probably right, but, this is still far better than just doing the sort of degree you get at Durham which will teach you virtually no programming at all yet cost you around $20,000 for the privilege.

2. How do you get a job without a degree .... well, all I can say is that I've managed it so far, several times! I don't know if there's a general formula for this, but I did it by specialising (in Linux stuff, specifically Windows emulation and binary compatibility issues) and so whilst few people need skills in this area, few people have them too and the wonders of the internet age allow us to meet. Basically I got nearly every job so far through work in the open source community, save for one, which I got as part of a summer work/student scheme.

The impression I've got is that in business, low level software especially, people are more interested in what you can do for them than what bits of paper you have. I don't have a massive amount of experience but I do have some, and this is what I have seen so far.

This may not apply in the IT/corporate networking world where I'm told having the right Cisco/MS qualifications is a lot more important, but I'm not in that area and don't really want to be. Generally if you can make people money, you'll be ok ... good luck!

Edit: I should point out that saying Google don't require a degree is a bit misleading ... for some (many?) jobs they don't but the usual phrasing is "a degree or equivalent experience".

It's a rather hard balance

Should computer science really be about vocational education? Or should it be purely an impractical theoretical foundation? The answer is likely both and neither. It's rather like going to the Math department and demanding that they get rid of all the Calculus courses because what most of the students need is just Business Math. The Universities that I'm familiar with have set up multiple degrees within the compsci department, sharing some common courses and then specializing at the higher level.

(Could just be me but I'd much prefer spending time on constraint programming than I would on malloc and free).

Edit Note: I guess I'd fall in the camp that I don't want to spend money having someone teach me a particular language - I can do that on my own much more efficiently than I can in a classroom environment. What I want out of an education is to learn the concepts. In my experience, college should be less about rote exercises and more about learning how learn. The particular languages and libraries that one uses will vary much over time and domain. The concepts behind programming haven't changed much since the halcyon days of FORTRAN and Lisp in the late 50's.

Experience changes your perspective

Well, actually I'll happily admit that some rather esoteric areas of the course did interest me. Compiler optimisations and Haskell were pretty interesting (after all I am reading LtU :)

On the other hand, I would not be saying this if I'd started from scratch at the beginning of the course like many people did. I've been programming for long enough that I got over the "I want to make games!" stage many years ago and things like functional vs imperative or SSA form (not taught sadly) are now very interesting, but if I was still struggling with "What is scope?" advanced type theory wouldn't hold my interest. And yes sadly this is the level many people are at still .... don't even think about peripheral stuff like version control.

My post shouldn't be read as "I wish I had learned memory management", as I already understand that. My point was that many of my coursemates started out from square one, and I think it's meaningless to try and teach people how compilers work before they really understand pointers and memory (for example). Covering temporal logic or how to implement a RWLock on top of hardware primitives is ridiculous when not once has a student experienced writing concurrent code themselves.

No problem for me, but that isn't good enough. I wanted to see some of my pals consider a career in programming too. I want to work with people who have experience and are qualified to be doing their job. Basically, I expected more from the education system and it didn't deliver.

[OT] Restrict entry in CS?

Nobody expects Music departments to accept student who don't have (relatively) solid skills in an instrument as music majors. With a relatively large number of autodidacts (ideally, there'd be good pre-college CSy education available, but that's a pipedream) in CS freshmen, wouldn't it be justified to apply the same sort of policy? So maybe that's too extreme, and there could be two entry level curricula that'd merge after 1-2 years, especially since the two populations have so different educational needs (one needs to learn basic practical skills, the other to unlearn bad habits and misconceptions ;).

Considering the user in the PL equation

I find the most interesting research in programming languages (PL) to be the idea of melding human-computer interaction (HCI) principles with PL design, or at the very least, taking into consideration the act of programming itself when considering what must be specified in a program. What aspects of a full program specification can be relaxed and still provide a useful environment to get your work done in? How does one think about programming problems? Why is it so difficult for people to write a program for seemingly simple algorithms?

For example, I am working on a programming environment for experimenting with formal languages. When I talk to those who might want to make use of it (that collection is not a large collection, but nevertheless...) they are decidedly uninterested in two aspects of programming: data type specification and dealing with errors. Both of these tasks come across as "pointless busywork", that is, they distract the user too much from the ultimate goal of writing a program that executes the work desired. Unsurprisingly, they are also uninterested in speed of execution (at first, anyway). They want to easily express their thoughts in a programmatic fashion and see something happening quickly. Note the latter: they prefer getting to the stage of "seeing meaningful work being done" in short order over having the work itself being done in short order. In short, "the less I have to do, the better".

Facilitating that and allowing for specialization in the future is, to me at least, a very interesting challenge.

Well, CNN/Money says that

Well, CNN/Money says that the top job is software engineering (and #2 is being a college professor), and CS enrollment is dropping? Perhaps enrollment should drop. Everybody agrees that you can't add more doctors as easily as you'd like to. Perhaps we can't have this many CS majors, either?

I think the theory/practice balance will be taken care of by an inevitable change to six or seven year programs.

6/7 years?

Why do you say that's inevitable? Actually they're talking about reducing degree courses here from 3 to 2 years (but with much shorter summer breaks .... so it's the same amount of material but more intense).

Why do they want to change that? Financial pressures on students of course ... people aren't going to be able to afford 3 year courses soon as fees rise

Can we try to foucs the

Can we try to foucs the discussion on PL issues, and not general issues that are discussed in many other places? Thanks!

expressive power

My late friend Ken Anderson loved to reduce the size of code to its barest essentials. He did that with algorithms too. The result was incredibly elegant. So I have found that focus on programming languages to increase expressive power fits very nicely with the desire to find better algorithms. Saying more with less also helps with a new generation that wants its socks blown off.

A Practical Theory of Programming

In my last year of undergraduate studies at the University of Toronto, I had the privilege of attending Prof. E.C.R. Hehner's course Formal Methods of Software Design. The textbook used for the course was Hehner's own A Practical Theory of Programming, which is freely available for download.

To put it bluntly, this course completely transformed the way I think about mathematics and computer science. For almost three decades, Hehner has been doing innovative research on the area of formal methods and programming languages. One breakthrough this has resulted in is Unified Algebra, a single algebra that includes what are commonly called boolean algebra, number algebra, sets, lists, functions, quantification, type theory, and limits. These forms of mathematics are the foundation of much of computer science, and Hehner brings together concepts and notations that have evolved over centuries under one consistent umbrella.

UA is the basis of aPToP, and allows aPToP to be far more expressive and easier to apply than other theories of programming such as Hoare's Logic, Dijkstra's weakest precondition predicate transformer, Back's Refinement Calculus, and Jones's Vienna Development Method. From the book's introduction:

The theory in this book is simpler than any of those just mentioned. In it, a specification is just a boolean expression. Refinement is just ordinary implication. This theory is also more general than those just mentioned, applying to both terminating and nonterminating computation, to both sequential and parallel computation, to both stand-alone and interactive computation. All at the same time, we can have variables whose initial and final values are all that is of interest, variables whose values are continually of interest, variables whose values are known only probabilistically, and variables that account for time and space. They all fit together in one theory whose basis is the standard scientific practice of writing a specification as a boolean expression whose (nonlocal) variables are whatever is considered to be of interest.

Like most well-written books, aPToP is extremely dense. Hehner provides simple, precise, formal explanations of concepts that are usually explained in round-a-bout and informal manners. For example, his formulation of "Proof by induction" is especially eye-opening; it doesn't require any special notation or format. Some of the ideas presented in just a few pages required several re-readings and took me days to properly absorb. Fortunately, I was able to attend weekly office hours with Hehner (usually one-on-one), which immensely clarified my understanding of the material.

I highly recommend all of Hehner's papers to anyone studying mathematics or computer science; I definitely feel his work represents some of the most important and interesting CS research at the moment, from a PL perspective. As Graydon mentioned before on LtU, there is room for significant work to be done developing an appropriate user interface, along with tools, to help programmers efficiently develop and maintain programs using aPToP. This kind of work could very well result in dramatic improvements in our ability to create reliable, correct software.

Tools, not types

For my money I would say that PL-related research with a tool flavour is underappreciated whereas type-theoretic research is overhyped and gets way too much attention (sort of like high-ernergy particle physics within physics). For one thing, although many tools need some theory, too, as a rule tool-motivated theory (at least in the papers I have read) tends not to get out of hand whereas type-motivated theory does (a wild understatement). When asked how he'd pick a language for work, no less than Donald Knuth answered he'd go for the one with the best tools, not the most elegant one. Yet tools are seen as engineering stuff and are comparatively under-researched in academia; at least that is my impression. For examples of tools-flavored, not theory-drenched work that I like see, e.g, the PLT and Fluid groups. For the same reason I find some areas of security research (e.g., capabilities) very appealing: on the capabilities list participants strive to reason in plain english, they don't rush to write 10 pages of equations and type judgements. They try to be rigorous yet accessible and practical.

Transactional memory is fascinating, too, and could have a huge impact: it could be to concurrency as GC was to memory management (I don't see message-passing becoming the dominant concurrency paradigm: it would be a revolution, whereas STM is more of an evolution, albeit a potent one).

Last but not least, at the risk of being something of an heretic on this forum, I will also say that while all of the above has a PL angle (it being what Ehud asked for), I often find research on PLs per se rather boring.

Broken links

Olivier, your links are broken. They need to hrefs, not refs.


I would guess CS enrolment corresponds with economic prospects for CS graduates. In my CS experience I recall very few students (and in some cases professors) seriously interested in CS, actual theoretical work. The curriculum was dumbed down, not quite to point of being "built almost entirely around the mastery of Java" (Chazelle), but pretty close, it was definitely oriented toward vocation. I noticed among some professors an uncritical acceptence and sometimes promotion of Microsoft and the use of their software in course work, and as examples for study. One professor was actually handing out copies of the student version of the Microsoft compiler.

For someone who is a serious student, I wouldn't recomend a CS education or career. Mediocrity seems to be norm in both pedagogy and real world practice. As far as programming language research, I don't see any kind of widely accepted objective research program, a kind of yard stick by which to measure the signifigance of work and progress of the field as a whole. Maybe this exists for some individual researchers, but rarely is it spelled out explicitly. It is much more common to encounter a kind of postmodernist philosophy of "everything is equally valid". It is true, that some forms of progress are clear such as the advance in the efficiency of functional languages implemented on commodity machines. However, such notions of progress have to be put in the context of progress of the field in whole (I would include machine architeture, and the expression of solutions to contemporary problems), the notion of which I think is quite lacking.

Proof carrying code

I'd say the most interesting work in Programming Languages is around proof carrying code and related areas such as software verification. The potential for these techniques are huge. Imagine for example an operating system which only installs device drivers which comes with a proof that they are working correctly. This dream is not that far off as Microsoft now has a tool for verifying certain safety properties of device drivers. A termination checker for device drivers is in the making.

This technology has the potential of solving problems of reliance, security, efficiency and of course general software correctness. I guess I'm starting to sound like a car salesman but I really believe in this technology. But there is a lot of work to be done before we can reap the benefits.

SDV not correctness proof

A "proof" in the academic sense is a mathematical chain of reasoning ... SDV is more like a Coverity/smatch/sparse type tool that scans a program looking for suspicious constructs. It doesn't *guarantee* that if the program passes its tests it is correct, which is what a proof would do. But proving arbitrary programs, especially things like device drivers, is very hard and perhaps may never be possible in the general case ...

Proof, correctness and pay-as-you-go

My intention was to use the term "proof" in a very specific sense, namely the sense it is used in the area of proof carrying code. In this area the word "proof" means an object in the set of propositions in some logical framework. I know very well that SDV doesn't produce such objects but with a bit of work I believe it could. Just as I believe that the termination checker could spit out a proof object once it has established that the device driver is terminating.

You're correct when you say that a driver passing the SDV test isn't necessarily correct. And I didn't claim that it would be. I said SDV can check "certain safety properties". Surely we could have a proof that only established that the device driver adheres to those safety properties.

That's one more thing that I like about the proof carrying code framework. It can be used in a kind of pay-as-you-go fashion. Today we can only verify very restricted properties of program. Fine! Then we produce proofs for those restricted properties. And the program verifier in the user's computer only checks for these properties. But as technology advances and we learn how to establish more powerful properties about programs we can crank up both the compiler producing the proofs and the program verifier which checks the programs. The only limit is the logical framework which we use to specify properties.