Lambda the Ultimate

So let's ask a different one. What if we think of our field as "problem solving" rather than programming or programming languages. Then we have a more productive question: what are the important problems in this field?

Answer:

• how do we solve bigger and more complicated problems (building more sophisticated module systems i.e using aspects, composition filters or some other technique that offers different abstractions for programming in the large)
• how do we make the best problem solving tools available to the mainstream (so that instead of complaining about the limitations of java/c++/c/c# when compared to smalltalk/lisp we start removing these limitations)

Good question. I just had a conversation with a friend, a proffesional programmer, and he basically said that (a) he prefers C over Java/C++ and (b) he thinks imperative languages (he didn't use the term) are going to remain the mainstream language - the ones taught to all undergrads etc.

I was bold enough to conjecture that in five to ten years newcomers will learn very different languages.

Now let's make that happen...

Well we could go away and design yet another great language and spend ages telling people about it's greatness. Unfortunately there are too many of those out there.

A better approach would be to take a leaf out of Stroustrup's book and ask what are the minimal changes we'd need to make to a mainstream language like Java or C# to take advantage of the advanced programming techniques available?

Richard Gabriel has some interesting articles about new language acceptance at http://www.dreamsongs.com/WorseIsBetter.html. I think of particular interest is "Models of Software Acceptance: How Winners Win": http://www.dreamsongs.com/NewFiles/AcceptanceModels.pdf

I think there is one big meta-question: "How do I reduce complexity?" (or how to Keep It Simple and Stupid...and efficient).

My Nobel Prize candidate would be the computer scientist responsible for introducing *Parametric polymorphism* to programming languages. Was it the inventor of ML Milner?

I'd nominate this person because parametric polymorphism seems to be the one thing from computer science theory that is being adopted by mainstream languages (C++,Java,C#) to reduce complexity nowadays: C++ templates in SETL, Generic Java, Generic C# with generic extensions to the .NET VM (ILX).

Thanks for the reference to the Nice Programming language I'm definitely going to check it out.

I worked on a very high level language called Tecton and read a lot: from a plethora of papers on programming language design to Logical Summa of William of Occam - Aristotle and medieval logicians knew a lot about different kinds of logical structures that appear in the natural languages and their formal properties. .... I also developed a large library of algorithms and data structures in Scheme. This work led to a development (together with Dave Musser) of Ada Generic Library. After a brief stint at Bell Labs, where I worked on a library of algorithms in C++, I moved to HP Labs in Palo Alto (1988). (Source, my emphasis)

There is definitely a Stepanov connection to ADA. Also sounds like he would have liked LTU if it had been around when he was developing his ideas. In the interview Stepanov is also not completely confident that C++'s generic features (STL) will be adopted by mainstream programmers.

I think the papers of Prof. Don Batory's group at the University of Texas provide an interesting historical perspective on generic object oriented programming.

Application generators are said to reduce library complexity ( A Scalable Approach to Software Libraries (1993), Singhal Univ. Texas Phd Thesis, Ch 2.2) but it is worth noting that the Predator generators (P1, P2, P2) are supersets of C. If object orientation is added to the language and then generics (templates + STL) you've already reduced library complexity significantly. So it seems that some of the original cited reasons for using application generators disappear in the face of object-oriented generic programming languages.

But then these applications generators are also uni-lingual and IP's and Stratego's goal is to be multi-lingual, so the focus of application generators also seems to have changed a bit.

The STL design cannot be directly translated into Ada. You should check the old papers from Musser and Stepanov. For a more recent perspective, check out the resources from the Ada-Europe container library design workshop I chaired, esp. the design document of Charles.

I've looked at D, Eiffel and OCaml. They're all viable replacements for C/C++ but none of them are offering the kind of massive productivity improvements that the world needs to tackle increasinly complex problem domains like Bioinformatics. The only people who seem to even believe that these productivity gains can be made tend to be proponents of ideas like Model Driven Architecture and Executable UML. These all want to abandon traditional programming languages in favour of some visual notation.

The alternative to adopting these visual notations would lie in finding a way to build more sophisticated abstractions through a programming language/notation which makes problem solving significantly easier.

However, I am quite sure things like executable UML are not the way to go.

What is needed is better concepts and better glue to connect components, not a grpahical/visual tool oriented gloss over the real issues of software design.

All IMHO of course.

There is another alternative though, let people just go on creating this complexity, let everyone do their own thing with their own languages, let complex multi-faceted evolution do its work, and then from another perspective seek to integrate them in some way. That seems to be the multi-lingual impetus behind IP, and Strategic Programming.

There are so many useful applications (many open sourced) coming out of the various language communities ranging from Mathematica to C++ to Perl and Python to Cobol, and you're not going to be able to convince anyone in these communities that anything is better than their language. Furthermore, all languages will eventually die or evolve into something completely different creating an ever heavier load and inertia of old languages

Most of the people who understand programming focus their research on technical areas -- programming languages, libraries, and tools -- rather than focusing on any broader social issues. Even within the technical areas, the focus tends to be on writing programs, with little work being done on debugging or maintaining them. In my opinion, doing research into writing programs is like spending years optimizing the parser, when your application only spends 5 to 10% of its time parsing.

Unfortunately, the nature of the craft of programming (and the discipline of computer "science") attracts people who tend towards solitude, and who look for questions that have precise answers. The social questions I think we need answers for now are not, in general, the kinds of questions that appeal to these people. And many of those questions may not actually have answers.

So, finally, my answers Ethan's question from last week, "What does everyone think the great questions of programming languages are?" are in areas more related to social science than computer science:

• How can a programming language help improve communication among programmers on a given project?
• How can a programming language help improve the accuracy of schedule estimates?
• How can a programming language help improve UI design and popular acceptance of new applications?
• How does one "grow" a programming language along with its user community? {See Guy Steele's outstanding paper "Growing a Language" ...)
• How does the quality of a programming language user community affect its acceptance and its effects on programmer productivity? [See the Python community for an outstanding positive example of this.]
• How does one infiltrate industry to get them to use programming languages better than C-based ones? (A.k.a., how to get "everyone" to move forward at least into the 1980's?)
• How does a programming language become mainstream? (Or at least mainstream enough to make it possible to convince managers to allow its use for development?)

For anyone looking for an area to research, well, I think it's quite an opportunity. Difficult, but if it were easy, it wouldn't be research, would it? For what it's worth, I think that many of the principles of "eXtreme Programming" are steps in the right directions.

[Yeah, probably if I were in academia instead of industry, I'd be among the people looking at programming languages -- i.e., part of the problem -- because I think it's more fun. I suspect that the same is true for most of you.]

[BTW, as most of you probably already know, Guy Steele is the originator of the phrase "Lambda: The Ultimate". See http://library.readscheme.org/page1.html or papers.html .]

Even within the technical areas, the focus tends to be on writing programs, with little work being done on debugging or maintaining them. In my opinion, doing research into writing programs is like spending years optimizing the parser, when your application only spends 5 to 10% of its time parsing.

This is the sort of argument promulgated by advocates of dynamic typing, because they already accept as an axiom the notion that bugs cannot be caught while writing the program. Advocates of static typing believe otherwise.

Unfortunately, the nature of the craft of programming (and the discipline of computer "science") attracts people who tend towards solitude, and who look for questions that have precise answers. The social questions I think we need answers for now are not, in general, the kinds of questions that appeal to these people.

I don't buy the bit about solitude, but part of the reason computer scientists look for "questions that have precise answers" is that the nature of computation is such that it really is possible to pose and answer such questions (unfortunately, few programmers seem to believe this fact), and being able to address doubts conclusively is an effective means of technological progress.

After all, it has worked remarkably well in other fields like physics and mathematics. Maybe you should ask yourself whether we would be living in a better world if Newton had given up on the idea of identifying and codifying natural laws in favor of studying the effect on society of heavenly bodies and their motion. ("Astrological Principle the First: gather Ye not under Trees bearing heavy Fruite!")

Sociology, history, psychology, etc. are important and interesting fields, but do you think they would not adopt formal methods in a second if they were actually tractable and effective in those domains? Indeed, in sociology and psychology, statistical methods have become much more popular in recent years, precisely because they are more objective and incontrovertible than qualitative reasoning.

Saying that the significant questions in computer science should be ones that bear on social science is simply not an answer to the question, "What are the significant questions in computer science?" Your questions look more like answers to the question, "What are the significant questions in the social science of computer programming?" And that is totally different field. Hamming's question cannot be answered by redefining the notion of what belongs in a field itself.

In my opinion, an academic field is largely defined by the body of literature it generates. Therefore, it makes sense that the answers to significant questions will be the ones that are cited most often in papers. So, let's look at ResearchIndex:

Most cited source documents in the ResearchIndex database as of May 2002

There I see papers on binary decision diagrams, encryption, high-performance numerical computation, rewriting theory, parallel distributed computing, model checking, semantics of logics and theorem proving. This gives you a pretty good idea of what has been influential in enabling other research.

Also, we can look at authors:

Most cited authors in Computer Science - May 2002 (ResearchIndex)

The names I see suggest that results on parsing theory, type systems, theorem proving, pi-calculus, RSA encryption, complexity theory, data structures, TeX and LaTeX, distributed computation, compiler implementation and specification logic have been influential.

Finally, the citations themselves, which are by far the most explicit:

Most cited articles in Computer Science - May 2002 (ResearchIndex)

Here it seems that the notions of NP-completeness, data structure algorithms, Hoare's CSP, genetic search algorithms, pattern recognition, adaptation, logic programming, sorting, process algebra, automata theory and BDD's turned out to be very useful.

So, those suggest what questions which have been answered are significant. What about the future? What can we imagine would be widely cited?

Well, an obvious one is the question of whether P=NP; a resolution of this issue would bear heavily on every nook and cranny of computer science.

Judging from the list above, then, other important problems probably include: how to make model checking scale better, how to factor large numbers, how to make programming languages better at concurrency, how to make programs easier to specify, how to quickly decide satisfiability of logical propositions, etc.

Obviously, algerbrraic methods provide the most promising research problems

"What does every[one] think the great questions of programming languages are?"

Programming language design has more social aspects than most people consider, and programming language research seems for the most part to ignore this.

Programming language design and deployment -- development, community, and widespread adoption -- is fundamentally a social activity. Technical aspects of programming languages are secondary factors in a language's success.

I suppose there might be other reasons, but I think the main reason for caring about programming language design is to improve programmers' productivity. To decrease the time taken to create and modify programs, to make it possible to create and maintain kinds of programs that we couldn't create yesterday, and secondarily to improve the robustness, reliability, speed, security, or correctness of programs. A few of the latter goals have some partially technical solutions, and certainly formal methods may play a part in some of those. But the major one, IMHO, is almost wholly a complex of social factors.

Even within the technical areas, the focus tends to be on writing programs, with little work being done on debugging or maintaining them. In my opinion, doing research into writing programs is like spending years optimizing the parser, when your application only spends 5 to 10% of its time parsing.

This is the sort of argument promulgated by advocates of dynamic typing, because they already accept as an axiom the notion that bugs cannot be caught while writing the program. Advocates of static typing believe otherwise.

Actually, I'm a big fan of the kinds of static typing systems that Haskell, SML and OCaml have. I do write a lot of code in Python, though.

In industry, program specs almost always change during program development or after delivery. In fact, bugs of this nature cannot be caught until after delivery of some kind, which is why you see early (prototype) deliverables and close communication with customers at the heart of the xP approach.

.. part of the reason computer scientists look for "questions that have precise answers" is that the nature of computation is such that it really is possible to pose and answer such questions ...

I quite agree here, and certainly formal methods are a big part of getting answers to some of those general computer science questions. However, we were talking about programming language design, where I think formal methods are considerably less applicable (except in implementation issues like parsing and compiler optimization).

Saying that the significant questions in computer science should be ones that bear on social science is simply not an answer to the question, "What are the significant questions in computer science?"

Indeed, and I did not claim that it was.

Your questions look more like answers to the question, "What are the significant questions in the social science of computer programming?"

As far as I'm concerned, after the substitution of "programming languages" for "computer science", the word "social" would be almost completely redundant here: most of the important questions in programming language design are social questions, IMHO. My main point was that this is the "elephant in the living room" that few in the programming language research community acknowledge.

In my opinion, an academic field is largely defined by the body of literature it generates.

Ok; but the research trends in any given segment of academia can be more readily applicable to "the real world", or less so. In the computer industry in general, we're spoiled in that many kinds of programming research can lead and have led quite quickly to usable products that improve our programming lives. But in research in programming language design, I see a fair amount of less-applicable research -- technically interesting and elegant language designs, without any hope of, plan for, or intention to inspire widespread adoption of such languages.

Maybe this is because it's no easier to plan for a programming language to become popular than it is to plan for a recording to become a number 1 hit. Throwing a whole lot of money and marketing at the problem seems to help in both cases.

I guess I desire to see more readily applicable research in the programming languages area. But the social nature of programming large systems is too intractable a problem to research, so we get small or individual teams (there's that solitude thing I mentioned) researching smaller, more formal, or easier problems ... or we get Microsoft's research.

Judging from the list above, then, other important problems probably include: how to make model checking scale better, how to factor large numbers, how to make programming languages better at concurrency, how to make programs easier to specify, how to quickly decide satisfiability of logical propositions, etc.

There's a few good topics in there, and I'll look forward to seeing some of those precise answers.

I think you missed my main point, though. As I said, I was responding specifically to Ethan Aubin's question

"What does every[one] think the great questions of programming languages are?"

You're right; I was addressing the question, "What are the significant problems in CS?"

Programming language design and deployment -- development, community, and widespread adoption -- is fundamentally a social activity.

I vehemently disagree about design, but not deployment. Deployment is obviously a social process.

Technical aspects of programming languages are secondary factors in a language's success.

I agree with this. If technical superiority were the most important factor in popular adoption of a language (which is, apparently, your definition of "success"), then languages like VB, Cobol, C++ and Perl would all have been stillborn, and C would have breathed its last more than a decade ago. I'm not talking only about "worse is better" factors, but also things like hype, availability of hand-holding, peer pressure, egoism and so on. These are definitely social factors!

But, maybe you ought to consider whether popularity is actually the most important goal for a programming language. Is Britney Spears the best musician because she is the most popular? Is special relativity the most useful scientific theory because everybody has heard of Einstein? Does George Bush make a better president than Al Gore because (OK, it's debatable, but :) most Americans voted for him?

There are two reasons I can think of why we might consider popularity as a measure of success for a programming language: 1) because more users will produce more libraries, 2) because if no one uses a language, it doesn't ultimately contribute anything to society. But both these arguments fall down if the language is technically superior to existing languages. 1a) Superior languages increase productivity, so fewer users can produce more libraries. 1b) Superior languages promote reuse, so libraries can be used more often, and fewer libraries are needed. 2) Though most people switch languages for social reasons, as you suggest, there are always some well-informed people who adopt languages for technical reasons, so in practice we are always talking about a non-zero user base.

Of course, I admit this also depends on the degree of technical superiority (but, as I suggest below, there are only a few different degrees of difference anyway), and how effectively it is demonstrated.

In industry, program specs almost always change during program development or after delivery. In fact, bugs of this nature cannot be caught until after delivery of some kind, which is why you see early (prototype) deliverables and close communication with customers at the heart of the xP approach.

I don't see how that bears on static vs. dynamic typing. If anything, when you are in a situation where the spec changes often, it is even more important to have a language supporting static typing, since correctness is that much harder to verify, and lots of changes engender lots of tiny bugs (esp. the sort which static typing catches easily, like passing an integer where a string is expected).

I quite agree here, and certainly formal methods are a big part of getting answers to some of those general computer science questions. However, we were talking about programming language design, where I think formal methods are considerably less applicable (except in implementation issues like parsing and compiler optimization).

Wow, that's a real shocker! Programming language design, as practiced in the academic community, is nothing but formal methods. It is precisely in order to separate the wheat from the chaff, i.e., the core features from the syntactic sugar, that we adopt formal methods to study programming languages. And it is probably because language designers outside the academic community and users don't see that distinction that they run excitedly from Perl to Python to Ruby, despite the fact that, from a formal viewpoint, (I strongly suspect) they are essentially identical.

In fact, from a formal viewpoint, there are only a few genuine differences between programming languages which can logically affect productivity; everything else is just a kind of permutation, or can be expressed using preprocessing/macros. The important questions are: Functional or Prolog-like? Untyped or typed? Explicit typing or type inference? Weak or strong typing (type safety)? Referentially transparent? Higher-order functions? First-class continuations? Reflection (supports eval)? Lazy? And then whether these features hold at the level of types again (do types have types? can type expressions include variables?), etc. There are some other, more technical, properties too, and some things, like subtyping, assignment and concurrency, which you can quibble about, but that's basically it for the features which appear in 99% of extant (sequential) languages. (Some researchers will disagree with me on this opinion, but I believe it is basically true.)

Actually, getting back to the original topic, an important question in programming language research would be "What other feature can we add to the above list?" That is, "What else is a genuine core feature of a sequential programming language?" Being able to answer that question would lead to a language with shorter programs, better reuse, and greater programmer productivity.

Anyway, if you think formal methods have nothing to do with language design, you need to get a good book, like Mitchell's Foundations of Programming Languages. Language design is more than picking a syntax and deciding whether to add XML support. That's all marketing crap which has nothing to do with actual productivity.

In the computer industry in general, we're spoiled in that many kinds of programming research can lead and have led quite quickly to usable products that improve our programming lives. But in research in programming language design, I see a fair amount of less-applicable research -- technically interesting and elegant language designs, without any hope of, plan for, or intention to inspire widespread adoption of such languages.

I agree that there is a lot of programming language research which does not turn out practical, for some reason or other (though I do see a positive correlation between technically interesting results and practical results). But are you so sure that's not also the case in other academic fields? What makes you think the hit/miss ratio is smaller in PL research than in, say, semiconductor design? It's like the anthropomorphic principle. As a consumer, you are only really aware of the hits.

Having said that, I do agree that PL research is under-used in industry. But it's making some headway. For example, I think the W3C committee working on XQuery has adopted some formal methods.

Frank, since we are interested in programming languages, it may be interesting to try to identify trends in PL research (as opposed to general CS). Problem is, there are quite a few groups, each pursuing its own agenda, that citations alone can be a bit misleading.

Well, I would think the citations might be less useful for this narrower topic not because of the diversity of approaches, but rather because PL research is a relatively small sector of the CS community. But if you look at the topics mentioned in the citations there is actually (surprisingly) a fairly large number of PL-related topics, like rewriting theory, semantics of logics, theorem proving, type systems and process algebra. My summary of the results is a bit biased, though, since I tended to include the citations with which I had some familiarity.

If you ask me, though, off the top of my head, I think most PL research can be broadly categorized as dealing with: logic languages, process algebra, OO languages, functional languages, low-level compiler implementation details, type systems, theorem-proving, semantic models and applications.

Instead of taking my word for it, though, you can look at the ACM Computing Classification System (1998). I think D.3, F and G.2 include the vast majority of what I regard as "PL research".

Obviously, algerbrraic methods provide the most promising research problems

I guess you say this because I harp on so much about algebraic methods. I do think that algebraic theory is the most productive way to approach PL design, but only because it is the best developed and most abstract, letting you focus on the really essential issues rather than peculiarities of syntax or expression. One expects, though, that no matter what formalism one uses, we are all studying "the same thing", i.e., the underlying mathematical object of study is the same.

Algebraic theory is also a very fruitful field to mine for new language features. For example, many of the features and concepts underlying typed functional languages were discovered almost half a century ago in that context. Since number systems, spaces and topology are essentially algebraic, and they underly (at least conceptually) the vast majority of modern physics, you can also expect that eventually functional languages will be the best languages for programming scientific applications, since they will provide the most obvious mapping between language- and domain-specific concepts.

As for business applications, I am content to leave those to better minds. :)

Frank: "I don't see how that bears on static vs. dynamic typing."

It doesn't; it is one of the reasons why "the notion that bugs cannot be caught while writing the program" is an axiom in industry.

Thanks for the link to Mitchell's book. I still disagree about the importance of syntax, marketing and popularity. I'd love to get to do more of my work-day programming in Haskell instead of C, but Haskell isn't popular enough in industry yet, despite its clear technical superiority.

I guess you say this because I harp on so much about algebraic methods...

Well, I was trying to lure you into joining the discussion but I agree that algebraic methods are interesting and the research about them quite fruitful.

1. Bad habits established whilst writing small programs
2. Reinforcement of the bad habits they acquired earlier
3. Cynicism about the benefits of any technology they don't already know
4. No impetus to change practices/tools that seem to work well enough

Using Haskell for example, and insisting students prove their programs correct.