Teaching Programming Languages

I often have the pleasure of teaching UMD CS‘s undergraduate programming languages course, CMSC 330. Taken by every sophomore in our program, it has evolved into a pretty interesting course, and I find myself talking about it with various people I meet. As such, I thought it might be worth writing down what it’s about, in case others might also find the course (or elements of it) interesting or its materials useful. (Most of the course’s materials — lecture notes, projects, exams, homeworks — are freely available at the course homepage.) There is too much to say for one post, so I’ll break it into three parts. This post covers the overview and first 1/2 of the course, and the second post will cover the third quarter, and the last post will cover the last quarter while also making some broader connections.

I apologize in advance for any errors I have made, e.g., in historical attribution of PL features. I welcome references and/or corrections!

Overview

CMSC 330 aims to give students a broader view of computation and programming languages. We want to introduce them to new ways to think about and solve programming problems, exemplified by different languages. We also try to get them to think carefully and rigorously about what languages mean (and how they are implemented), which should help them use those languages more effectively.

By the time that UMDCS students take 330, they have programmed for two semesters in Java and one semester in C. During 330, we teach them functional programming using Objective Caml, scripting languages using Ruby, and safe low-level programming using Rust.[ref]Until the Spring’18 semester we taught Prolog rather than Rust, but switched to Rust for reasons of relevance and coherence. I may say more about why in a future post.[/ref] We also look at technologies that underpin a language’s design and implementation, as well as core concepts that cut across languages, notably regular expressions, finite automata, context-free grammars, and LL-k parsing. We also teach operational semantics and lambda calculus as a means to formally understand languages and computation. Finally, we teach some core elements of secure coding, a task that many of students are sure to undertake, whether they realize it at the time or not. We also present some of the history of programming languages.

I’ll cover Ruby and OCaml in this post, language theory and semantics in the next one, and secure coding and Rust in the last (which will also talk about software security more generally).

Scripting with Ruby

The course starts by introducing Ruby. Ruby’s is the first language design our students have seen that includes implicit variable declarations and dynamic typing. We immediately consider the tradeoff of this design to the more familiar design of explicitly and statically typed declarations (as in C and Java). Later we compare these two to OCaml’s and Rust’s use of static but implicitly typed declarations.

Ruby is popularly considered a “scripting” language, useful for small tasks. Its support for syntactically lightweight regular expressions, arrays and hashes, simple pattern matching, and other features make it well suited to text processing. Students thus see the power of domain-specific constructs in making certain tasks easy. Their project during this part of the class involves building simple data structures and classes, and using regular expressions, to do some text processing. The experience of designing regular expressions to match structured text in these early projects makes it easier for us to later delve into how regular expressions work, along with their limitations.

Why Ruby?

One question I often get asked is why we don’t use Python, rather than Ruby. The honest answer is “inertia.”  We started with Ruby almost 10 years ago when Ruby on Rails was big (e.g., Twitter was using it, but now isn’t), and Python was not the clear “winner” in the dynamic/scripting language space.[ref]That Python has “won” the head-to-head with Ruby is an impression and not a fact. But, see their relative ranking on the IEEE Top Programming Languages list, which is derived from several sources of evidence.[/ref] The idea of changing to Python arises with regularity, and it may eventually happen.

That said, we did have technical reasons for choosing Ruby. I like that its coherent, object-based design (“everything is an object”) makes for interesting connections to Java-style objects. Students are surprised that the expression 1+2 is really sugar for 1.+(2). That is, we are executing the plus (“+”) method of the object representing the number 1, and passing to it the object representing 2. The result is the object representing 3. Ruby’s support for inheritance is familiar, but mixins are interesting and new (and foreshadow traits in Rust).

I also like that Ruby has long had support for higher-order programming, in the forms of code blocks and procs. Learning code blocks smooths the transition to full higher-order programming in OCaml. For example, in Ruby I could write [1,2,3].each {|x| puts x+1} to iterate through the array [1,2,3] and print out each of its elements—the {|x| puts x} part is that prints its parameter. This is like List.iter (fun x -> print_int x) [1;2;3] in OCaml. Many idiomatic Ruby programming patterns use code blocks, so by the time we get to full closures in OCaml the basic concepts are pretty familiar.

Later in the course we come back to Ruby as a web application-authoring language, which elevates security concerns.

Functional Programming with OCaml

In my estimation, ‘functional programming’ (FP) is a programming style in which mathematical (partial) functions are used as the core programming abstraction. Functional languages make this programming style more natural. Two key reasons for this are the presence of easy-to-write first-class functions (i.e., closures, not just function pointers) and a design that promotes immutability (and recursion) over destructive assignments (and iteration).

Why teach FP?

As one explanation for why one might teach FP, Swarat Chaudhuri wrote on this blog some time ago,

There are good reasons [to teach] functional programming. In imperative languages like C, a line of code within a procedure can affect the entire global state of the program. In contrast, in functional languages, such side effects are severely limited. This makes it much easier to reason about correctness and security: analyzing the correctness of the composition of procedures A and B can be broken down into analyzing A and analyzing B. Researchers have also frequently argued that functional program design makes it fundamentally easier to exploit parallelism.

I like to point out that both features and core design elements of mainstream (not primarily functional) programming languages had their origins in functional languages. As such, learning a modern functional language can give you a leg up on the next big language, or on future features of your current favorite. Examples:

• Garbage collection was part of LISP, in 1958. Now it is in nearly every mainstream language aside from C and C++ (and even there you can use a conservative collector).
• Lambda terms (anonymous, first-class functions, implemented as closures) also come from LISP and are a part of most modern languages today, e.g., Java 8, C# 3.0, Python, Scala, and many others.
• Generic types started out as parametric polymorphism in ML in the late 1970s, and earlier in more theoretical settings, e.g., System F and the polymorphic lambda calculus. Generics are now part of C++11, Java 7,  Scala, Rust, and many other languages.
• Modern type inference has its origins in Hindley-Damas-Milner type inference for ML dating from the early 80s. Type inference is now part of Java, C#, Rust, and many other languages.

Looking to the future, I think that pattern matching (e.g., on algebraic data types, ubiquitous in functional languages) will be increasingly present in mainstream languages. It is a key part of Rust, and it is coming to a new version of Java.

As a last motivation, I also mention that notable companies have taken the plunge and use functional languages like OCaml, Haskell, Clojure, Erlang, and Scala directly in major projects.

Teaching OCaml in 330

Maryland is one of the few top/large CS schools, as of the writing of Swarat’s post, that mandates students learn FP. Like many of the schools that teach FP, we use OCaml. While OCaml does not go as far as Haskell to enforce a functional style (e.g., by requiring monadic handling of effects), the language does favor immutability and first-class functions by making both syntactically lightweight. And OCaml is easier to pick up starting from programming languages the students have already seen; e.g., they don’t have to deal with Haskell type inference error messages (OCaml’s are hard enough!), and they don’t have to contend with weird behavior due to laziness.

Indeed, introducing OCaml after Ruby provides some particular benefits. Like Ruby, OCaml programs are relatively terse and require no type annotations. OCaml’s lists are very similar in style to Ruby’s arrays, as is programming over them with constructs like map and fold and first-class functions (in Ruby, the former is the collect method). These similarities help us perform an initial transition, but immediately we start to see the differences, e.g., with static typing and type inference, a lack of mutation, and the corresponding need to program recursively. These contrasts facilitate good ‘aha!’ moments.

We revamped the OCaml lecture notes last year, taking inspiration from Michael Clarkson‘s CS3110 at Cornell, which I understand drew inspiration from Dan Grossman‘s CSE 341 course at UW. The presentation style is compositional, and semantical — it uses “static” and “dynamic” semantics to explain each language construct, building towards a full-featured expression language (we don’t spend much time on the module system). This style is useful in and of itself, and it also lays the foundation for talking about context-free grammars, parsing, and operational semantics in more depth later.

Functional programming is the largest unit in 330, covering 3.5 weeks of lectures and 3 programming projects (with two of them split in half). The students complete some warmup programming exercises, and later use OCaml to build a “Small C” language interpreter and a regular expression interpreter/compiler.

Impact and Alternatives

Despite all of the attention, not many students are persuaded that OCaml is the best thing, ever. I took a poll on the last day of class last semester, asking which programming language the students liked best. Out of 107 responses, 40% preferred Java, 33% preferred Ruby, 18% preferred OCaml, and 9% preferred C. At least OCaml was preferred to C!

One interesting suggestion that was made to me was to use Scala rather than OCaml. This could work. The questions in my mind are whether the extra OO stuff would get in the way of imparting functional programming style, and whether students would “cheat” by coding up projects in the Java subset. As our class is so large, enforcing that they don’t cheat could be a major sink of teaching-assistant time better spent on something else.

Up Next: PL concepts, Security, and Rust

I’ll stop for now. In my next post, I’ll talk about 330’s coverage of some key concepts underpinning language definitions and implementations. Later, I’ll highlight 330’s recent coverage of secure programming topics, including the use of the Rust programming language, in the context of a broader missive on PL and software security.