In the computing stack, PL sits between algorithms and systems. Without algorithms to implement or computer systems to run them on, there would be no need for programming languages. However, the research communities that study algorithms, PL, and systems don\u2019t really have much of an overlap. This is perhaps unavoidable: computer science is now a mature field, and researchers in mature fields tend to pursue specialized and technical research questions.<\/p>\n
At the same time, it seems important that the approaches \u2014 assumptions and methods \u2014 of different subfields of computing be compatible to some extent. At the end of the day, computer science aims to produce solutions for the whole computing stack. An \u201cimpedence mismatch\u201d between its subfields compromises our ability to come up with such end-to-end solutions.<\/p>\n
This suggests that the comparative study of assumptions, techniques and cultures of different CS fields (a sort of \u201ccomp lit\u201d for computer science) is potentially valuable.<\/p>\n
Personally, I have always been intrigued by the relationship between the fields of programming languages and algorithms. In this post, I discuss similarities and differences between these two areas, and argue that their synthesis could be interesting for both research and teaching.<\/p>\n
<\/p>\n
To compare PL with other fields, we need to first decide what PL is. I can think of a few themes that run through our field:<\/p>\n
Now let’s consider\u00a0the field of algorithms. Any algorithms research starts with a model of computation <\/em>on which algorithms are to execute. Typically, such a model distills the essence of a real-world computational setting, and constrains what an algorithm is allowed or not allowed to do. For instance, in the so-called streaming model of computation<\/a>, an algorithm can only process a few items in an input stream at one time. In sublinear algorithms<\/a>, the algorithm cannot read its input data fully (capturing real-world intuitions about large datasets), but is permitted to probe or sample from this data.<\/p>\n Any given model of computation comes with a rigorously defined notion of efficiency<\/em>. The algorithms researcher\u2019s goal is now to come up with algorithms that are provably efficient. Over the years, algorithmists have studied many different ways to make algorithms efficient. For example, a common approach to achieving efficiency is to weaken the guarantees that the algorithm offers. In particular, randomized algorithms<\/a> are allowed to have one-way or two-way probabilistic error in their outputs. Approximation algorithms<\/a> must solve hard global optimization problems in polynomial time, but are allowed to produce outputs that are only within an approximation factor of real optima.<\/p>\n There are several commonalities between\u00a0PL and algorithms and, to my mind, one key\u00a0difference.<\/p>\n One obvious commonality is the object of study: an algorithm and a program are basically the same thing (algorithms are commonly defined to be programs that terminate on all inputs, but this is a technical detail). Second, the models of computations that algorithms researchers assume are, fundamentally, nothing but programming languages: a demarcation of the set of permissible programs\/algorithms and a specification of their dynamics. One could think of streaming algorithms or sublinear algorithms as the classes of programs expressible in domain-specific languages with restrictions on how a program accesses data.<\/p>\n The fundamental difference between algorithms and PL, it seems to me, lies in a quantifier:<\/p>\n An algorithms researcher\u2019s goal is to produce an algorithm\/program with desirable properties. In contrast, whether a PL researcher is working on language design, verification or compilers, he or she aims to come up with proofs and procedures that apply to all algorithms <\/em>that can be written in a language.<\/p><\/blockquote>\n For instance, a program verifier is a procedure that can take an arbitrary<\/em> algorithm (within a certain model of computation) and check that it satisfies certain properties. The designer of a language with guarantees of memory safety aims to guarantee a theorem about the set of all algorithms possible under their model.<\/p>\n Interestingly, this makes the field of PL closer to complexity and theory of computation, which study properties of classes of algorithms. Think of two elementary statements from complexity theory: \u201cevery comparison-based sorting algorithm must have Omega(n log n) complexity\u201d and \u201cPSPACE = NPSPACE\u201d. The first statement is a meta-theorem about a programming language whose semantics comes with a quantitative model of resource consumption (that comparisons of values can be done in unit time). The second is a comparison between two different programming languages.<\/p>\n Other differences between PL and algorithms are cultural rather than technical.<\/p>\n The first such difference is that PL research is usually designed to maintain a path to execution on real computers. Models of computation in the algorithms literature are an artifact of analysis. In contrast, even the core languages designed by programming linguists tend to have the eventual goal of implementation. It also seems fair to say that PL researchers implement their ideas more often than algorithmists do. Many if not most POPL papers come with an experimental evaluation. SODA papers, on the other hand, rarely do. One corollary of this is that algorithmists are more susceptible to conflating models with reality. As one example, most algorithms hold polynomial time complexity as the<\/em> notion of efficiency. However, NP-hard problems are not always hard to solve in practice \u2014 for instance, boolean satisfiability may be NP-complete, but SAT-solvers work very well on large formulas in many domains. The empirical focus of PL researchers has allowed them to leverage such practical tools.<\/p>\n A second cultural difference between algorithms and PL lies in their attitude towards abstraction, and their definition of what makes an algorithm\/program desirable. Models of computation in the algorithms and complexity literature tend to be low-level, without the abstractions available in most modern programming languages. The main objective of design is efficiency, defined in terms of the number of low-level steps taken by executions.<\/p>\n As Bob Harper argues in his talk on “two notions of beauty in programming”<\/a>, PL researchers often have a different take on the cost of a computation. For many PL researchers (especially those who work on language design),\u00a0the true notion of a computation\u2019s cost is the effort involved in programming and reasoning about programs<\/em>. A desirable computation or proof is one that can be expressed effectively using high-level programming abstractions, and composed easily with other computations\/proofs. The design of new languages or models of computation is driven by an interest in making programs more desirable in this sense.<\/p>\n A third, related difference is that algorithms research is traditionally much heavier on quantitative reasoning. Notions of efficiency studied by algorithmists are easy to quantify. Also, in contemporary algorithms, notions of correctness are often randomized or approximate, so that correctness analysis also requires quantitative reasoning. In contrast, PL research has historically focused on reasoning about boolean properties such as type safety, deadlock-freedom, and termination. It is true that there is a growing literature in the PL world on quantitative reasoning about programs (including reasoning about probabilistic and approximate computation), but this kind of work is still in the minority.<\/p>\n Finally \u2014\u00a0and I realize that I may get some flak for saying this \u2014 it seems to me that algorithms researchers are historically much more agile than PL folks in identifying new application areas. There are many thriving research topics of the form “x + algorithms”: algorithmic genomics, algorithmic game theory<\/a>, and network science<\/a> are only three prominent examples. Algorithms researchers have been able to distill interesting algorithmic problems from these applications and come with many exciting technical results. In contrast, PL researchers have tended to focus on classic applications in system software, or chosen to be application-agnostic.<\/p>\n The technical differences between algorithms and PL are innate \u2014 there is after all a reason why these are different areas. However, the cultural differences between PL and algorithms exist primarily for historical reasons, and it seems that a synthesis of the \u201cpositive\u201d cultural attitudes of PL and algorithms can benefit both fields.<\/p>\n Specifically, it seems clear to me that there\u2019s a \u201cPL angle\u201d to most application domains that algorithmists study, and applying it would\u00a0benefit of the entirety of computer science. Take, as an example, cryptography. The vast majority of work on cryptography is algorithmic, and at a theoretical level there\u2019s nothing wrong about these algorithms. However, as we saw from the Snowden revelations<\/a>, because of vulnerabilities at the software and hardware level, guarantees at the level of abstractly defined algorithms may not transfer to implementations of these algorithms. PL techniques could have potentially prevented these errors from happening.<\/p>\n It seems to me that we can amend our list of activities of PL researchers as follows:<\/p>\n There are quite a few existing PL research efforts that can be said to fit this agenda. Examples include recent work by PL researchers on reasoning about statistical privacy<\/a>, verification of cryptographic protocols<\/a>, and analysis of probabilistic programs<\/a>. In each of these cases, our community targeted an algorithmic application and extracted PL problems from them. I would like to see many more efforts like this, in areas ranging from biology to graphics to robotics to economics (disclosure: PL approaches to robotics and computational economics are two of my current research interests). The technical problems of interest in these areas are likely to be quantitative, which opens up possibilities of generalizing the qualitative techniques that PL researchers have traditionally used.<\/p>\n There are also pedagogical benefits to a synthesis of PL and algorithms. For one, it would tie the undergraduate sequence of programming courses to undergraduate theory classes. An effort of this sort is CMU\u2019s two-course introduction to\u00a0functional programming\u00a0and algorithms (15-150<\/a>\u00a0and 15-210<\/a>), which emphasizes the benefits of functional program abstractions while teaching algorithms and data structures. For another example, PL ideas are a natural fit for a theory of computation class. Today, the standard model of programs in a class on automata and computability is the Turing machine, which is far removed from the abstraction-rich programming languages in which students implement their algorithms. Complementing the Turing machine model with recursive functions and the lambda-calculus would partly bridge this gap. Finally, finite and pushdown automata are presented in undergrad automata theory using old-fashioned applications in parsing. These applications can and should be complemented with the use of automata in modern program verification, as models of software and hardware systems.<\/p>\n All in all, it seems clear to me that bridging some of the gaps between PL and algorithms is both possible and desirable. Some encouraging steps in this direction have already been taken, but much more remains to be done. Perhaps the best way\u00a0to develop synergy between the fields is to create funding opportunities for research at their interface. Bob Harper’s recent NSF whitepaper<\/a>, which builds on the talk<\/a>\u00a0of his that I mentioned earlier, is an example of an effort to mobilize such funding. A less ambitious goal is to create fora with representation from both communities. I personally can think of worse ways to spend a few days than hanging out with some algorithms researchers, hearing about recent exciting results in their field and thinking about their language-level analogs.<\/p>\n [Note: This article has been edited since it was originally posted.]<\/em><\/p>\n","protected":false},"excerpt":{"rendered":" In the computing stack, PL sits between algorithms and systems. Without algorithms to implement or computer systems to run them on, there would be no need for programming languages. However, the research communities that study algorithms, PL, and systems don\u2019t … Continue reading PL and\u00a0algorithms: technical differences<\/strong><\/h2>\n
PL and\u00a0algorithms: cultural differences<\/strong><\/h2>\n
A synthesis?<\/strong><\/h2>\n
\n
\n
\n