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.

Programming languages bubble chart

Programming languages galore!

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. 1 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 with 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. 2 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:

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.

Notes:

  1. 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.
  2. 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.

12 Comments

Filed under Dynamic languages, Education, Functional programming

12 Responses to Teaching Programming Languages

  1. Or perhaps substitute OCaml with Standard ML? Simplicity is king.

    When I took a similar course, the textbook was “Modern Programming Languages: A Practical Introuction”:

    For the Object Oriented aspect, Java was replaced with SmallTalk (Squeak)

    Rust would be an excellent alternative to C/C++, and it introduced after SML and an OOP it would be easier to adopt I’d think

  2. Grayswandyr

    When I was a student myself back in 1997, we were given the same programming project (solving the 15 puzzle using a basic breadth-first exploration (so as to rely on a plain list, no explicit tree exploration)) first in Caml Light and then in C (so you had to program your own list). The first project was done few days, the latter was much much harder to get right.

    This was very instructive as it showed that any non-trivial program manipulating symbolic data benefits from typed FP. In particular, it alleviates from a lot of testing, but do students test their Ruby code thoroughly to experience this reduction in OCaml?

    The second, tremendous advantage of these languages is harder to show to students: it allows safe refactoring, something that unfortunately can rarely be experienced on smallish-sized programs as the ones you usually write in programming classes.

    PS: I think “pure” (for Haskell for instance) is an unfortunate word, it conveys some sort of meliorative meaning that is not scientific (of course, sticking to “purity” has been a tremendous source of good research). So one shouldn’t “apologize” for using an ML language. Both sorts of languages are lambda calculi with a reasonably clear semantics (in particular an operational one) and strong typing by inference, and that is a distinguishing feature wrt lots of other paradigms. BTW the domain semantics of lambda-calculus sort of shows that FP functions are not even functions in a classical sense, don’t you think?

    (@mlhaufe I don’t see the difference between OCaml and SML at this level of detail)

    • The students see imperative and C programming in earlier courses, and so some of the friction you mention between low-level and high-level languages does come out. And per the poll, students prefer OCaml to C!

      We do cover the power that type-safe abstractions get you in languages like OCaml, but don’t connect the benefit of that to refactoring; mostly we use it to talk about security. So that’s a good thing to consider updating.

  3. Ian Sweet

    Some quick thoughts:

    1. I was surprised to hear that the OCaml lectures have been restructured so much since I took / TA’d 330. I remember briefly looking at the materials for [Dan Grossman’s Coursera Course](https://www.coursera.org/learn/programming-languages#syllabus) and liking that presentation style. In particular, the recipe of presenting language features incrementally, and using a static/dynamic semantics approach, is really nice.

    2. I’m strongly opposed to using Scala in 330. It is a weird combination of OO and FP, and also has unique features like implicits that are powerful but easily abused.

    3. If we imagine evaluating effects across different languages, I think there are two important factors to consider. First, how ergonomic are they? In other words, does the language make it easy to use effects? Second, how controlled are they? Does the language make it easy to control the “blast radius” of effects if they are used incorrectly?

    From this perspective, ML variants (OCaml in this case) strike the ideal balance. OO/imperative languages give you maximum ergonomics (effects are the default way of programming), but very little way to control their use. On the other end of the spectrum, Haskell gives you maximum control through monads, but [they are not ergonomic](https://www.cs.indiana.edu/~sabry/papers/exteff.pdf).

    I argue that OCaml strikes the right balance between ergonomics and control, primarily due to parametricity. It is very easy to use effects because their use is not restricted by the type system. There is also dedicated syntax (`a.(5) <- "foo"`). In contrast to a language like Java, however, OCaml gives you a strong module system. This allows you to use effects but hide them effectively. For example, you can [implement laziness using references](http://typeocaml.com/2014/11/13/magic-of-thunk-lazy/) but present the user with an interface that hides that fact. Also, the context in which the module is being used cannot affect the internal state.

    In summary, OO/imperative like Java make it easy to write effectful code, but hard to control it. Haskell makes it hard to write effectful code, but easy to control it. ML variants make it sort-of easy to write effectful code, and sort-of easy to control it.

  4. Cameron Moy

    I was surprised only 18% of students preferred OCaml. I don’t think this has to do with OCaml as a language, but difficulty with functional programming as a whole. While FP is the largest topic in 330, it’s tiny compared to the two-or-so years of prior imperative experience students come into the class with. Many are angry they can’t seem to express themselves in the language since usually they know how to write an imperative solution to the problem. Occasionally I’ve seen students revert back to imperative patterns by the end of the semester (like trying to “assign” to the accumulator in a fold).

    Conversely, students in 131A who mastered recursion and functional programming patterns seemed to have a lot of complaints when programming in Java. They were frustrated at the verbose syntax and seemingly pointless constructs (why would I use an iterator when I could just use recursion?) It was a bizarre contrast. I think paradigm shifts are tricky no matter what your background.

    Next semester will be the first when students who took 131A will be taking 330. I’m very curious to see how they find Ruby, OCaml, and Rust respectively. As well as how their experiences compare to students who took the traditional track.

    • I’m very interested to see how the 131/132A students (who have seen functional programming from the outset, via an alternative introductory track) handle 216, our C programming course. They will have to flex their “mutation and iteration” muscles far more than they’ve been asked to so far.

  5. The fact that 3.5 weeks of OCaml is sufficient to convince 18% of the class that it is their favorite language, despite the fact that they have had 2 years of Java experience, is pretty cool! It’s too bad that they aren’t exposed to it earlier in the curriculum, alongside imperative/OO languages.

    • What Cyrus said. Asking students what they “like” is meaningless gigo.

    • Good point! I should say that while we only “teach” OCaml directly over 3.5 weeks, they program with it over the course of about 7-8 weeks. It is the most used implementation language in 330.

      As for seeing functional programming earlier: Per my above comment, we are experimenting with a path that starts with functional programming. This is 131A and 132A (as opposed to 131 and 132). David Van Horn is teaching these courses. We will do a full assessment during/after this year. If these courses stick around, it will affect what we teach in 330.

  6. Pingback: Teaching at Scale with Clickers - The PL Enthusiast

  7. Pingback: Teaching Programming Languages (part 2) - The PL Enthusiast

  8. Pingback: Software Security is a Programming Languages Issue - The PL Enthusiast

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.