I Open at the Close
Summarizing PoP Spring 2020
I had been teaching the first semester-long course of my life — an elective on compiler design — in Fall 2019, when after one fine class I came to know that I was being looked upon as the next person to offer the core course named Paradigms of Programming in Spring 2020. Now teaching a specialized course on compilers is one thing, teaching a programming language (though a relatively boring task) is another thing, but PoP is an amalgam of many different ways of thinking about designing and writing programs. Honestly speaking, I was a bit scared. Not about the number of students or it being a core course — I am fine as long as the class strength and structure allow me to directly connect with each student — but about the challenge of organizing content in a way that students who had already been through five semesters of CSE education still find such a fundamental course interesting.
Many Dilemmas
I first talked to few final year students from my compilers class who had taken PoP the previous year, and found that they had a good understanding of the same. So I talked to the previous instructor, who apprised me of his own experiments with teaching the multi-dimensional course over the last three years. I also flipped through my experiences of taking Principles of Programming Languages as a student, and browsed through popular courses on the topic in and outside India. What I found was amazing — variants of this course are taught as early as the first semester (with a focus on shaping the expectations of students with Computer Science, in general, for the rest of their BTech), to as late as graduate-level courses that haunt programming-language researchers. Further, they are taught using either a single programming language: ranging from simple academic ones such as Scheme and Racket (derivates of the legendary language Lisp) to industry-standard ones such as OCaml, Haskell and Scala; or with multiple languages in each paradigm (such as C/Python for imperative, Java for object-oriented, Scala/Haskell for functional, and Prolog/Datalog for logic).
What should be my strategy?
My PoP
After fantasizing with Haskell for two months, fifteen days before the offering I decided to go with the older MIT way of using the amazing book Structure and Interpretation of Computer Programs (popularly abbreviated as SICP) along with its Lisp variant Scheme as the base for all the paradigms. But MIT itself has stopped teaching SICP (due to reasons explained in the next paragraph), so was I going backwards? I decided to retrofit SICP with case studies from representative modern languages in each paradigm, and additionally use this to show that the underlying concepts, if understood in a language as simple (and cool) as Scheme, can be used to easily learn new languages as vast as Haskell. Thus the course webpage was formed, and the journey began with a charming class of 60 students.
Why did MIT stop teaching SICP and why is it still relevant nevertheless? To understand this, we first need to reckon that SICP used to be taught as one of the first CS courses in the curriculum at MIT, intended to introduce fresh students to the ways of structuring programs and the underlying technology, so that when they are faced with larger computing problems in future, they could handle them as fine computer engineers. However, as one of the authors of SICP had himself explained, computing science has changed in the twenty-first century: engineers no longer build complex systems by combining simple and well-understood parts; they routinely write code for systems that they don’t fully understand. As we can (sadly, in my opinion) see, now-a-days computing is more and more about working with large amounts of data, and primarily involves figuring out how to plug-in different libraries and searching through StackOverflow when faced with problems. People work as part of gigantic projects in the industry (sometimes not even knowing what the larger software is about), and the interesting ways of designing systems from scratch have become obsolete. But then, where I was placed, PoP was not the first CS course; students had already gotten experience with the plug-and-play approach, which indicated that they might still be willing to learn the traditional art of writing beautiful programs and the ways to experiment with the underlying technology, given that they see it helps them easily adapt to (or even design) future languages that are still not invented.
1. Going Back to Functional
PoP starts by taking students back to their high-school days and introduces them to the concept of pure functions: those that given the same input, produce the same output, always. Students find it amazing to recall that they were indeed flabbergasted upon seeing the following mathematically invalid statement on the first day of learning a (usually imperative) programming language:
x = x + 1Obviously, you never write let x = x + 1 in your high-school mathematics class, and just this simple assignment statement should make you wonder whether the mathematical programs (even, odd, factorial, prime, and so on) you were taught in your first programming course were even valid mathematical expressions! So we start with the functional paradigm and discover that mathematics can indeed be expressed elegantly on computers.
Next, PoP teaches you the most important mantra of dealing with software: never repeat; “abstract” instead. We take the following example (mind the parentheses, this is Lisp):
(define (sum-integers a b)
(if (> a b)
0
(+ a (sum-integers (+ a 1) b))))(define (sum-cubes a b)
(if (> a b)
0
(+ (cube a) (sum-cubes (+ a 1) b))))(define (sum-pi a b)
(if (> a b)
0
(+ (/ 1.0 (* a (+ a 2))) (sum-pi (+ a 4) b))))
Now even a kid will see the similarities. We introduce the idea of higher order functions and show that it can be used to represent the general “concept” of summing a series itself (flashback: there is a reason you had the summation symbol in mathematics):
(define (summation term a next b)
(if (> a b)
0
(+ (term a) (summation term (next a) next b))))(define (sum-integers a b)
(sum identity a inc b))); where 'identity' and 'inc' are existing or explicitly defined procedures
This naturally leads us to lambdas: first as a way of expressing short-lived computations, and then as the base of the whole concept of computation itself, in form of Church’s lambda calculus (this is different from the bookish approach of kind of arbitrarily starting with lambda calculus). By this time, students feel blessed — functional programming not only provides solutions to very practical aspects associated with software construction, but also satisfies the soul of a theorist! Meanwhile, they realize how everything in Lispy languages can be expressed using lists, and how functional and data abstractions give rise to modular programs that compose well. Somewhere mid-way we also introduce the underlying mechanism of reasoning about and executing purely functional programs, by modeling procedure application as substitution.
2. The Stateful World
FP finishes (to come back later!) right at the point where imperative and object-oriented paradigms can begin. I flipped imperative and OO though, and took the approach of introducing OO first by motivating students to model the real world in terms of objects, and then showing that changing objects cannot be modeled without maintaining an explicit state that can be mutated. Here starts the fun! We realize that substitution breaks, and that stateful programs require a more elaborate model of evaluation. This is done by introducing the environment model, with various colorful diagrams describing the existence of bound and free variables, the creation of closures and frames, and the general ideas of dispatching and message passing.
With OO, imperative programming (the one you typically learn even before FP) comes more naturally — it just becomes a syntactic subset! Finally, when students are shown a real-world OO language, in this case Java, they see how the understanding of core concepts makes large parts of sophisticated programming languages plain syntactic sugar, and how PoP teaches them just that necessary core.
3. Taking Out Time
Once students start getting the notion of the right way of doing things, we turn them upside down by introducing them to the notion of non-existent streams. An example would help here:
(define ones (cons-stream 1 ones))This is an infinite list of ones. It isn’t stored. It doesn’t exist. It’s implemented by attaching the first 1 to a promise that the remaining list will be generated, which is indeed generated (aka forced), piece-by-piece, efficiently, upon demand. The previous obvious way of representing the real world gets replaced with another obvious statement:
Objects in the world do not have states! It’s just a changing world, with observably different objects (implemented as persistent data structures) coming up at each instance of space-time (tribute to Albert Einstein here).
Apart from the expected mesmerization, there is a deeper truth we realize by this time: “There is no one way of doing things, and there is no one right way of doing things”; if we realize just this, all problems of the world caused by human egos melt away in an instant.
4. The Universal Machine
Having introduced at least three ways of thinking about programs and talking about the absence of a single right way of doing things, it’s just the right time to introduce programs that take programs as input, and consequently dissolve the difference between program and data. Scheme helps here again: as both programs and data look exactly alike in Scheme (enclosed within the same confusing parentheses), that earth-shattering idea becomes so obvious that students don’t even get surprised by the mention of a program itself being the input or output data for another program.
We next dive deeper into the universal program that consumes all other programs — the interpreter — and claim that it’s just a simple cycle of two functions: eval that produces new procedures to be applied to new arguments from given expressions, and apply that produces new environments and expressions to be evaluated. The beauty of recursion becomes explicit here: you just keep doing the same thing, and monotonicity+base-case finally break the cycle — wishful thinking at its best!
We didn’t stop here and continued to explore further with this PL technology. This included describing how simple changes to the interpreter, without making any fundamental changes to the underlying eval-apply cycle, can allow one to explore various design choices in the space of designing programming languages themselves. We chose the same three examples that the magician duo Sussman-Abelson show in their SICP offering to HP employees far back in 1986: varargs, dynamic scoping, and lazy evaluation; and included new experiments with the last two in a confusing-but-insightful programming assignment.
5. Breaking Logic
At this point, I deviated a bit from my initial plan, and chose to pick a more representative programming language for the logic paradigm: Prolog. Though it was perfectly possible to teach logic using Scheme, I limited myself to abstractly explaining how it could be done by modifying the interpreter, and then jumped directly to examples in Prolog. This was prompted mainly by the risk of students getting bored with large pieces of interpreter code thrown upon their screens in an online setting (more on this topic later).
By not going deeper into the various syntactic elements of Prolog, we kept the initial promise of PoP not being a course that just teaches various programming languages, and yet we enjoyed novelty by seeing the ability to express puzzles and to solve them, just by writing and interpreting programs!
6. The Culmination
Which is the most beautiful functional programming language? A vim-vs-emacs kind of question with many more candidates in the queue. I used the following arguments and chose Haskell (over three other strong candidates OCaml, Clojure and Scala):
- I wanted a language with static typing: though this course was not supposed to go deep into type theory, I felt seeing types as a powerful way of expressing program construction is something students really deserved after working with a language without explicit types throughout the course.
- Though Scala is a very natural language for people coming from C/C++/Java backgrounds, it’s hybrid, and hence it becomes not so straightforward to stick to programs that are not OO.
- Though Clojure could have been a natural candidate after Scheme (being still Lispy), it won’t be as novel to keep people excited, and is more suited while teaching concurrency (that’s another paradigm, if you think a bit).
- (Last but definitely not the least): I happened to have met several giants behind Haskell just within the last few months, from Simon Peyton Jones to John Hughes (those who have been reading my travelogue The Stark Traveller would know about my more-than-a-lakh-kilometres of travel in the 12 months starting from February 2019), so it just sounded the most interesting way to go at this point of time (obviously apart from Haskell further being the purest lazy functional programming language).
The Devil that Spoiled Mission 2020
I had mentioned in the beginning that I wasn’t scared of teaching large classes, unless I couldn’t reach out to every student. And this is what happened just when we were four weeks into the course: Covid-19 forced students to go home for an indeterminate amount of time, and we had to shift to online teaching/learning amidst all the associated challenges: connectivity, technology, unreachability, and so on.
This post is not about online classes, but those for PoP started smoothly — the biggest challenge being bringing students, at least those who could, live. If it was just a passive lecture to the wall, I realized there was a high chance I might err, apart from students losing out on doubts and discussions. But liveness was never very popular in terms of the percentage of students (which usually ranged between 25 and 40): I always had to keep inventing ways of making a concept sound interesting in order to attract crowds for the next few lectures. However, I took a feedback and realized it was not that I was mis-doing something, but the students were too busy with internships, other courses and various tasks at home, and hence preferred to watch videos at night, when the homes were calm.
The next challenge was that we got into a three-month break! Luckily, I found students back on track just after 2–3 lectures post the break; forcing an assignment being a sure-shot attack. However, I still do not know for sure if it’s possible in online settings to keep as many students on the same page as it would have been in a physical class. Another problem: programming assignments turn out to be the best evaluation mechanism without actual exams (in particular to check plagiarism), but absence of physical labs creates a huge challenge for students to cope up (lack of technological space to promote discussions among them being a major hindrance).
Endings
As soon as I thought I had found the right way to finish the vast course (see my plan for the last week below), some e-mails and a doubt session prompted me to think that many students were feeling overwhelmed. After all, though it would be good to teach more number of interesting and useful things, it’s impossible to teach all interesting and useful things; so it’s OK if you terminate abruptly, specially during unfortunate and uncontrollable times like in 2020. Hence I decided to replace the remaining classes with a funny-yet-educating video by a giant, and my trademark last lecture with the current blog post, apart from encouraging more flipped discussions.
A simple problem-solving strategy that came out through PoP is that while designing computing systems, we should: (i) think about the problem and possible scenarios; (ii) come up with simple abstractions that compose well; (iii) share knowledge and experience, and iterate (or recurse, if you have switched sides to the FP land). If the underlying programming language is designed well, this “software engineering” matches your thought pattern in a comfortable manner. Various paradigms of programming support this process in a different way, and the abstraction and composition capabilities provided to the programmer also depend on the underlying evaluator.
An important skill you have garnered through the course is to be able to choose the right PL ecosystem for the problem at hand. Thus, though it would be great to have a single best programming language for all computational tasks (something modern PL designers are doing more and more), trying to fit everyone into the same shoes doesn't always work. Some languages such as Scheme, Java, Haskell and SQL have definitely emerged as winners in their respective domains — occasionally due to luck or timing, but most of the times due to deeply thought innovation — and courses such as PoP Spring 2020 further teach you that when not satisfied with a language, you can always tweak it, or even create a new one, yourselves :-)
Personally, the course has left me wondering where the balance between traditional and flipped classrooms is, specially in an online environment. But as one of my TAs pointed out, it probably lies in the way we have ended. So let me be hopeful that students enjoyed the course (I definitely did), and move on with an open mind at the unusual-but-satisfying close, with a promise to force those coffees, once life comes back to educational campuses.
