Getting Started in Programming Languages

A student in Northeastern’s Fundamentals of Computing course, in which I’m a TA, recently asked me how to learn what the “state of the art” is in the study of programming languages. It’s a long road from Fundamentals to reading and understanding today’s research, but this post is my answer to how to start down that path.

First, a distinction: to study programming languages, many people will point you to a book on compilers or interpreters. While those comprise a large fraction of programming languages, they are only a piece of the puzzle. The heart of (the study of) programming languages is formal semantics: the idea that one can mathematically specify the meaning of expressions and constructs in a programming language to avoid the ambiguity that otherwise arises from plain-English descriptions. Equipped with a formal semantics, one can develop multiple techniques to run programs (compilers, interpreters, hybrid approaches like JITs, etc.), new kinds of optimizations, and manual and automatic techniques to find bugs or prove properties of programs, all while remaining faithful to the intended definition of the programming language. I recommend first learning how to build and run your own language, then moving on to learning formal semantics to get a solid foundation for understanding current research.

With that in mind, here are some resources for the new (or not so new) computer scientist wishing to learn more about programming languages:

Essentials of Programming Languages: EOPL, as it’s better known, introduces readers to the internal workings of programming languages by describing small programming languages and creating an interpreter for each one. The book is very hands-on, with lots of exercises for the reader to modify the interpreters with new features. It touches on the ideas of reasoning about languages and formal semantics, but mostly sticks to the interpreter-as-semantics approach.

Jonathan Turner’s Reading List: Turner is an engineer on Mozilla’s Rust team and recently posted his reading list for getting up-to-speed on programming languages. The list starts with some resources on how to build interpreters and compilers, but also points to more academic material later.

Types and Programming Languages: TAPL (rhymes with “apple”), as it’s better known, has a solid introduction to formal semantics in the first few chapters and would be my pick for a starting point on formal semantics. The remainder of the book deals with type systems, which form only one part of programming languages, but it’s the canonical reference if you’re looking to learn about types.

Semantics Engineering with PLT Redex: The PhD-level programming languages course here at Northeastern uses the Redex book, and I found it to be a good introduction. The tool itself (Redex) is a great way to experiment with semantics, including reduction relations (roughly, the part of the semantics that says how the program runs) and type systems. You could use this book as a substitute for TAPL (at least for learning the basics of formal semantics), or you could use Redex to experiment with the languages described in TAPL.

10PL: This is a list compiled by Northeastern’s PL faculty of (roughly) ten academic papers that they think every student in PL should know. Not all of them are PL papers themselves, and they don’t form a full foundation on their own, but they form a kind of “great books” list for PL. Benjamin Pierce, the author of TAPL, also has a similar list (although with a slightly more type-heavy and theoretical bent).

That list is more than enough to get you started. I omitted resources for learning about formal methods and software engineering, two fields that overlap heavily with PL, but you may be interested in learning about them, too. For more information, I recommend talking to students or faculty in PL at your school, joining (or starting) a PL reading group, or eventually even applying to grad school if you’re so inclined.

Good luck!

Lifetime Parameters in Rust

Not long ago, when I first started working with Rust, lifetime parameters were one of the trickiest aspects to wrap my head around. What was this strange <'a> thing I saw at the beginning of some function and struct definitions, and what was it for?

I’m writing this post to solidify my own understanding of this unfamiliar feature, and hopefully it helps you, too. In it, I’ll cover:

  • the problem lifetime parameters solve
  • the places in Rust where lifetime parameters can be used, and what each location represents
  • the use of lifetimes as bounds on both generic type parameters and other lifetime parameters
  • the 'static lifetime
  • lifetime elision (a set of rules that allow you to omit explicit lifetime parameters in all but the most ambiguous cases)

I assume the reader is familiar with the basics of ownership, borrowing, and references in Rust, as well as generic types; if not, the book is an excellent reference.

Let’s get started!

The Problem

Imagine that we have a hypothetical version of Rust without lifetimes on reference types, and we try to run this program:

At line 15, x would be assigned a reference to memory owned by the coordinate c (through the call to get_x). But at line 16, c would go out of scope, so its memory would be freed. That means that at line 18, x would point to invalid memory—a classic use-after-free error.

So why didn’t the compiler catch this? The problem is that without any extra information on the type signature for get_x, the compiler doesn’t know that the returned reference’s lifetime should be the same as the input reference’s. We could have, say, written a version of get_x that returns a reference with a completely different lifetime, like a reference to a constant.

A similar issue can occur with references stored inside structs. Consider if a similar struct that instead stored references to its x and y fields and we tried the following:

Again, running this program would cause a use-after-free error. In this case, example_x and example_y are freed when the block ends at line 13, so c.x at line 15 would reference a freed location in memory. For the compiler to catch this error before we run the program, we need to establish some sort of relationship between the lifetime of a RefCoordinate and of the references it contains.

As you’ve probably already guessed, lifetime parameters solve both problems.

The Basics of Explicit Lifetimes and Lifetime Parameters

Although they are not always made explicit, every reference type in Rust has an associated lifetime describing the scope in which the reference can be used.

In cases like the above, we do want to make the lifetimes explicit so that we can express, for example, that the reference returned by get_x has the same lifetime as the input argument, c . That would give the compiler enough information to know that the use of x at line 18 is invalid.

Rust does not provide a way to write down concrete lifetimes (e.g. there’s no way to express “the lifetime starting at line 13 and ending at line 16”), but typically that’s not what we want, anyway. Instead, we want to abstract over all possible lifetimes; this is what lifetime parameters provide.

Lifetime parameters are special generic parameters on items like functions and structs, much like generic type parameters. The parameters provide names for our lifetimes that can be used as explicit lifetimes in our reference types. To make this concrete, here is the program after adding the proper lifetime parameters to get_x:

Let’s break this down one step at a time. In general, 'a means “the lifetime a”, and &'a T is the type for a reference of type T with lifetime 'a (or &'a mut T for a mutable reference).

get_x has a single lifetime parameter, 'a, declared immediately after the name. c’s declared type says that it is a reference whose lifetime is 'a. This declaration does not change c’s lifetime; it only gives it a name so we can refer to it later. Finally, the return type &'a i32 says that get_x returns a reference to an i32, whose lifetime is the same as the input argument’s lifetime. In other words, from the caller’s perspective the returned reference is only usable as long as the input c is still in scope. With this information (and replacing our hypothetical, lifetime-ignoring Rust with the real thing), the compiler is able to report that our use of get_x is invalid, because c does not live long enough.

We could write the code like this instead to get a working program:

Structs work similarly, as seen in this lifetime-ified example of RefCoordinate :

The struct Coordinate is now parameterized over a lifetime 'a, and its references are each declared to have that same lifetime 'a. In effect, this expresses the constraint that any reference to the struct may not outlive its contained references.

Lifetimes on Other Items

Traits can also have lifetime parameters, with the same syntax and meaning as structs:

Finally, when implementing methods in an impl block, the block itself can declare lifetime parameters to be used in the named struct or trait:

In general, lifetime parameters are declared as generic parameters on items like functions, structs, traits, and impls, and they are used both in reference types and as arguments to items that take generic parameters (as with GetXRef and RefCoordinate in the above example).

Bounded Lifetimes, Lifetimes as Bounds

If you’re familiar with advanced uses of generic types, you know that they can have bounds, as in fn foo<T: S>(x: T). Here the provided T must be a type that implements S.

Similarly, lifetimes can act as bounds to other lifetimes. A parameter like <'a: 'b> means “I expect some lifetime 'a that is at least as long as 'b”.

Addtionally, lifetimes can act as bounds on types. A type parameter such as <T: 'a> means “I expect some type T such that all references in T have a lifetime at least as long as 'a”.

Bounds in both cases can be combined using the + operator just as with normal type bounds.

The ‘static Lifetime

There is one particular lifetime in Rust that can be named without abstracting over it: the static lifetime, 'static. This is the lifetime for references that are alive throughout the entire execution of a program, such as references to string literals and global constants.

Lifetime Elision

Lifetime parameters provide the compiler with the extra information it requires to prevent use-after-free issues, but writing explicit lifetimes for every single reference type can be cumbersome, especially for obvious cases like this:

We would rather write the following and have the compiler figure out where to insert the lifetime annotations:

Fortunately, Rust has a simple set of rules, called the elision rules, that allow the programmer to elide (leave out) lifetime parameters in functions in the obvious cases (structs, however, must always use explicit lifetimes for their fields). The rules refer to input and output lifetimes, which simply refer to the lifetimes used in input types or return types, respectively. The rules are (as quoted from the book):

  • Each elided lifetime in a function’s arguments becomes a distinct lifetime parameter.
  • If there is exactly one input lifetime, elided or not, that lifetime is assigned to all elided lifetimes in the return values of that function.
  • If there are multiple input lifetimes, but one of them is &self or &mut self, the lifetime of self is assigned to all elided output lifetimes.

Eliding any other output lifetimes is a compile-time error. The book has many more examples to help you understand the elision rules.

Summary

  • Lifetime parameters abstract over the lifetimes used in type annotations and allow the programmer to express relationships between lifetimes.
  • Lifetime parameters are declared as generic type parameters to functions, structs, traits, and impl blocks and can be used in reference types, struct types, and trait uses. They can also act as bounds on type and lifetime parameters.
  • The 'static lifetime extends over the whole program and is used for constants and string literals.
  • A simple set of lifetime elision rules allows programmers to omit explicit lifetimes in most cases.

Hopefully this has helped clear up one of the more confusing aspects of Rust’s type system. If you have questions I didn’t answer, please sound off in the comments. Happy hacking!

The PLAI Philosophy: An Interpretation

As a PhD student in PL who came from four years of industrial software development, lately I’ve been trying to figure out what working programmers should know from the study of programming languages. As part of that investigation I’ve been looking over some of the better books on programming languages to see what their take is. In the introduction to Shriram Krishnamurthi’s Programming Languages: Application and Interpretation, Shriram forgoes a description of the book’s philosophy in favor of a link to a video of the first lecture for the course. What follows is my own interpretation of the philosophy from that video, as an attempt to both put some of that material down into written, searchable form and discover my own thoughts on the matter.

(Disclaimer: this is my interpretation of what was said in the video, not necessarily what was meant, so any mistakes in the below description are my own)

Inspiration from Science

To the extent that computer science is a science, we should look to science for ways to approach our own field. One of the primary tasks of science is to come up with categories to better understand similarities and differences between objects or living things. Think of taxonomies in biology, for example, that might classify an organism as a plant, animal, or a member of some other kingdom.

We programmers often do this with programming languages at a high level. We categorize them as “functional”, “object-oriented”, “imperative”, “scripting”, and all sorts of other categories. However, this categorization breaks down upon further inspection: the categories are not well-defined, and many languages fit into more than one category (for example, Scala proponents often emphasize that it is well-suited for both object-oriented and functional programming).

Perhaps this kind of categorization would be useful at a different level. Another use of science is to study the smallest building blocks of objects, such as atoms or DNA base pairs, and determine how they combine to gain a better understanding of the larger structure. This approach is helpful in studying programming languages. By understanding the individual building blocks of the language (e.g. values, expression forms, types) and the rules for putting them together (i.e. the semantics), we gain a much deeper understanding of the language as a whole. Furthermore, at this level it can be useful to categorize the small building blocks or semantic rules in different ways, as the similarities and differences are more restricted and well-defined than for programming languages as a whole. The divide between call-by-name and call-by-value semantics is one such categorization familiar to PL researchers.

Programming Language = Core + Syntactic Sugar

The philosophy of the course is that every language has a small “essence” to it, made up of these small building blocks, and that the rest of the language is just syntactic sugar. That is, the non-core features of the language can be expressed in terms of the core features (if perhaps in a verbose manner). Finding and understanding that core provides a framework for understanding the rest of the language, and helps language designers understand the effect new features will have on their language.

The course has students write a desugaring process for the language under study, then write an interpreter for the remaining core language to better understand its semantics. The goal is to end up finding the “essence” of the language. One difficulty is that the implementer of both the desugaring process and the interpreter must also prove that their language implementation has the same semantics as the official language (whether that’s a formal specification, a reference implementation, or what have you). In other words, when one runs a program under the new implementation and gets an answer, that answer must be the same as the one predicted by the reference language.

Later on in the video, Shiram calls this a “recipe for [language] design”: start with the right core, think about the next necessary features, and add them in a way that works well with the core.

Motivation

One might ask, “Why study programming languages at all?”. After all, only a very select few work on the commonly-used programming languages.

The problem is this: no one sets out to build a programming language. They start by writing something simple, such as a configuration file format. Then a colleague asks them for a way to save repeated computations, so they introduce variables. Then another colleague asks for a conditional construct, so they introduce “if”. Then another colleague asks for another feature, and so on and so on until the tiny configuration language has morphed into a full-blown programming language.

Every programmer will run into this situation at some point. In other words, every programmer will eventually end up writing a programming language, whether they wanted to or not. The key difference is that those who don’t understand programming languages will write it badly.

Or as Shiram put it, “we have a social obligation” to make sure the programming languages of the future are well-constructed, by teaching programmers the fundamentals of PL.

My Take

When considering what the take-aways are for most working developers, I think the most important part is the focus on understanding the core of a language and how it works. Even disregarding any issues around language engineering, if a programmer understands how their language works at that level, they will have a much better grasp on how all the pieces fit together and will write code that’s less prone to errors caused by weird corner cases of their language.

Certainly I think the core-first recipe for language design is the right way to go, and although I still have my doubts on how useful this is for all programmers, the discussion around configuration languages that grow out of control is well-taken. Also, the idea of a social obligation to ensure better semantics for “the next big thing” resonated with me—even if we can’t find a reliable way to become the designer of the next hot language, we can do our best to make sure the person who gets there knows what they’re doing.

One issue I noted is that it’s not always clear what the core of a given programming language is. There might be many opinions on what features make up the core, which was discussed briefly in the lecture when mentioning that there are usually multiple ways to desugar some feature. Finding the right core is probably not as important as finding a core, though, and my hypothesis is that most desugarings will give some insight into the workings of the language.

All in all, I think this is a great philosophy for those interested in knowing a bit more about programming languages to improve their own programming, and all programmers would be well-served by at least taking this approach to understanding their own language for day-to-day use.

Thoughts on Net Neutrality

With the FCC’s rules being struck down and arguments between Netflix/Cogent/Comcast/Verizon in the news lately, I thought this would be a good time to revisit net neutrality. I’ve generally been in favor of the idea ever since I heard about the issue (less restrictions on content creators and users of the Internet overall is a good thing), but I’ve never stopped to really think about all the details, and having been studying computer networks for the last couple of years, I figure this is as good a time as any to analyze the issue and come up with a more concrete and well-thought-out opinion.

The Issue

First off, for those who aren’t familiar, what is net neutrality, and what’s the whole debate about? At a high level, net neutrality is the principle that all traffic on the Internet should be treated equally by those who carry that traffic from one place to another. So no matter if you’re browsing Wikipedia, listening to music on Pandora, or watching movies on Netflix, all of the networks between you and the computers serving your content should treat your packets the same (for some definition of “the same”—more on that later).

The Internet started with this principle (at least understood, if not explicitly stated by early members), and carriers have largely followed it ever since. However, with the rise of bandwidth-heavy applications like streaming video and peer-to-peer file sharing, carriers are looking for more ways to ease the load on their saturated networks. One of the proposed methods is to throttle certain types of traffic in preference to others, based on criteria like the type or source of the content. Even past that point, many are worried that ISPs will actually start charging users to access certain sites, or that they will slow certain sites down to a crawl unless the customer pays up for “fast lane” access to that site. Alternatively, there’s also the possibility that ISPs charge the content providers themselves for the right to have their traffic carried to users, since certain providers (e.g. Netflix, YouTube) take up a large fraction of the available bandwidth. For example, in 2005, CEO of SBC Edward Whitacre stated in an interview that companies like Google, Yahoo! and Vonage would like to “use my pipes free, but I ain’t going to let them do that because we have spent this capital and we have to have a return on it.” This requirement to pay for access to users also brings up the fear that ISPs will start blocking or throttling services that compete with their own (e.g. Comcast slowing down Netflix to convince customers to use its own Xfinity video streaming).

Are these fears well-founded? Well, perhaps. In the US, we haven’t seen any cases of an ISP outright blocking a legal website (to my knowledge), but back in 2007, it was discovered that Comcast was throttling BitTorrent traffic to essentially unusable levels because of the load it caused on their network. An agreement was eventually reached, but many worry that this sort of situation could become more commonplace. Much more recently, in the last few months we’ve seen multiple disagreements (1, 2) between Netflix and ISPs like Comcast and Verizon about who should pay for what when it comes to giving users better levels of service on their Netflix streams (more on this in a later article).

Today, there are two primary questions: (1) should we still have network neutrality at all? and (2) if so, should we regulate it? There’s also the more nuanced issue of “exactly what do we mean by ‘net neutrality’?”.

My Take

Having researched the issue and thought about arguments from each side, my position is that the federal government should regulate ISPs to follow the principle of network neutrality. I define network neutrality as the combination of the following rules:

* ISPs can only charge a fee for those who connect directly to its network, not the sources or destinations of its traffic.
* ISPs can allocate resources differently for different kinds of applications (e.g. video streaming versus web browsing), but not according to the source or destination of that traffic (with the exception of allocating bandwidth to customers according to their pricing plan).
* ISPs can charge differently for different levels of service, but the level of service must be the same across all the rest of the Internet, not on a per-site basis. The same offerings must be available to all customers.

These rules are largely inspired by a net neutrality definition from Tim Berners-Lee (inventor of the World Wide Web): “If I pay to connect to the Net with a certain quality of service, and you pay to connect with that or greater quality of service, then we can communicate at that level.” These rules also make exceptions for things like illegal activity, security attacks, etc. to the extent that reasonable efforts to prevent these issues must violate the rules.

My primary rationale is that if ISPs start charging users or content providers different amounts to access different parts of the Internet, then I believe (as many do) that the Internet will become much more closed off and we won’t see nearly the free-flowing exchange of ideas and content that we do now. This becomes especially hard on content providers who end up having to pay every last ISP just to reach all of their subscribers.

Furthermore, customers are already paying ISPs for the cost of maintaining their network and carrying traffic. It shouldn’t matter what type of traffic that is. Figuring out how to deliver the user’s requested content is the ISP’s problem, not the user’s.

Opposing arguments

I’d like to take some time to address some of the trickier arguments that took me a while to fully answer.

Why should content providers have free access to an ISP’s “pipes”?

The Edward Whitacre argument is one that’s tricky to address at first, but much less so once you understand the overall payment structure of the Internet. The short answer is that content providers don’t use ISPs’ “pipes” for free, although the payment may be indirect. This is because of two forms of connection agreements between networks, known as “peering” and “transit”. Ars Technica has a good writeup on this, but I’ll give a quick overview.

Transit is similar to the relationship between a customer and an ISP: when network A pays network B for transit, A expects B to carry any and all of A’s traffic to the rest of the Internet. The cost is often in terms of dollars per amount of data transferred.

Peering, on the other hand, is a more mutual agreement, and traditionally (though not always) does not involve payment from either side. When two networks agree to peer with one another, they agree to exchange traffic directly between their customers, but not between their upstream connections. For example, if Verizon and Comcast peer with each other, a Verizon customer’s computer can communicate with a Comcast customer’s computer, but that same Verizon customer’s computer could not use Comcast’s transit provider to access the rest of the Internet.

Given that every network must connect to its neighbors through either peering or transit, any network that is carrying traffic from one place to another must have already made some agreement to carry that traffic. For example, if traffic from a YouTube video is traveling through AT&T’s network on the way to a Comcast customer, there must have been some agreements (paid or not) between the networks between YouTube and AT&T to allow the traffic to flow. So even if YouTube’s transit provider did not pay AT&T directly, there’s still a chain of payments between said transit provider and AT&T (with the possible exception of peering connections)

Networks are indeed expensive to maintain and upgrade, but the users and content providers creating the traffic flowing across those networks are certainly paying their fair share.

People who download lots of videos slow down network access for everyone else

I’m okay with routing traffic so that certain kinds of traffic don’t take up all the bandwidth from other users. This does not violate my principle of net neutrality. Ideally, ISPs would divide up their total available bandwidth at various points in the network and divide it up evenly among the customers who are currently sending and receiving packets. So regardless of what type of traffic the user is causing, they still get the same bandwidth as everyone else. That said, this may not be feasible given the complexity of most networks and the difficulty in configuring network management policies, but it’s an ideal to shoot for.

The real solution is to have more competition among ISPs—then the free market would encourage net neutrality as users buy access from ISPs that follow the principle.

Would “real” competition help? Well, maybe. I don’t know of any place in the US that has more than a small handful of available providers (often just one or two), so we don’t have actual experience to extrapolate from. A big problem, though, is that it’s hard to encourage competition in the Internet access space. Laying cables across cities and rural areas to connect residences and businesses to the Internet is a large expense, and not many companies are willing to take that kind of risk.

What are some of the options for encouraging competition? We could force all ISPs to open access to their cable lines to other ISPs, lowering the barrier to entry. However, the owning ISPs rightfully expect to make profits off of the lines they dug, so we shouldn’t force them to open their cable access. We could allow them to charge licensing fees for the access right, but without forcing them to do so, there’s no guarantee that would happen. We could require all future network lines to offer licensed access, but that doesn’t do anything for all the existing lines connecting most of the US already.

We could also have the government take over building the physical networks instead, but then we have the usual problem with government-run projects that there’s less incentive to upgrade and innovate.

I don’t see a great way forward here, but I’d love to know if there are other good ideas out there.

Some users/content providers might want to pay extra for a guaranteed quality of service (QoS) level

This type of argument can be made for those who use the Internet for mission-critical, drop-sensitive tasks. For example, one could imagine a military network that needs to route a video feed from soldiers on the ground to commanders on the other side of the globe. The military might be willing to pay more for access to a high-speed line with very little contention.

This is still doable, but I think it should happen only at the direct-connection level. If you want a fast connection, then you pay your ISP for it, who pays someone else for a fast connection, who pays someone else, etc. Forcing the end-customer to pay every middle man along the way seems impractical.

It’s possible that this is less efficient than having specifically outlined QoS levels that a user can pay for, but I’m not convinced that this is impossible to implement within a net neutrality framework.  Even if it is, I think it’s a good trade-off to make to maintain the openness of the Internet.

Network neutrality is a good principle, but regulating it would cause more issues than it solves

This is perhaps my main concern. I haven’t had a chance to research this yet, so expect it to be the topic of a future article.

Conclusion

Net neutrality is a great principle to help keep the Internet an open environment that allows for rapid exchange of information, services, or just the latest funny cat pictures. It can take several forms, though, and the arguments against it (or against regulating it) should not be trivially dismissed. My own position is that we should regulate it to prevent abuses from ISPs, but allow for reasonable traffic prioritization. I encourage you to learn more, keep an eye on the news, and if you agree that this is a principle we need to enforce, contact your legislators when the issue comes up again.

I’m sure there are plenty more issues about net neutrality than I’ve covered here, so I’m happy to continue the discussion in the comments below.