Friday, November 29, 2013

Benefits of Scala in CS1

In my last post I described why Trinity decided to give Scala a go as our language of instruction for CS1 and CS2. In this post I'll run through many of the key aspects of the language that I see as being significant for teaching CS1. I should note that when we started using Scala one of the challenges we faced was a lack of teaching material. To address this, I wrote my own. The text of that material came out as a textbook published by CRC Press in the fall of 2012. Since the book came out I have focused more on making screencast videos of live coding to support a flipped classroom style of teaching. In many ways, what I describe here follows my approach to CS1, which is not purely functional and includes many imperative elements. I truly hope that Scala will catch on stronger in the CS education market and someone will write a textbook for CS1 and CS2 using Scala that has a more purely functional approach. Trinity has a separate course on functional programming so we really don't want to focus on that in CS1.

The REPL and Scripting

As I mentioned in the last post, my real epiphany came when I realized that some of the key features that make Python so great for teaching introductory CS apply just as well to Scala. In particular, the REPL and the scripting environment really stand out as being beneficial. I also feel that having the type inference in the REPL is particularly helpful early on. Just consider the following part of a REPL session.
scala> 5
res0: Int = 5

scala> 4.3
res1: Double = 4.3

scala> 5+7
res2: Int = 12

scala> 2+4.3
res3: Double = 6.3
Entering a few simple expressions with literals and mathematical operators allows you to demonstrate each of the different types and what they do. Just like in Python, the REPL gives students the ability to explore on their own and test things out in an environment with immediate feedback. The biggest difference is that when the values are displayed, students get to see their types as well.

The scripting environment also makes the first programs that you write extremely simple. Here is the canonical "Hello World" program written as a Scala script.
println("Hello world!")
Compare that to what you would write in Java. Even the command for printing is more like what you expect from Python than what you get with Java. The big difference is, of course, that the Scala is doing static type checks are reports type errors as syntax errors, though admittedly the line is a bit blurred with the REPL and scripts as there isn't a separate compile phase that is obvious to the user. If you enter a type mismatch in the REPL you will get output that looks like this.
scala> math.sqrt("64")
<console>:8: error: type mismatch;
 found   : String("64")
 required: Double
              math.sqrt("64")
                        ^
When writing scripts, it is helpful to have easy text input and output. The code above showed that printing is done with a call to println (or print if you don't want the line feed). Simple text input is just as easy with functions like readLine(), readInt(), and readDouble(). All of these read a full line then try to return the specified type. The downside is that you can't use readInt() when reading multiple numbers on one line. This is fine for the first programs and it isn't too long before students can read a line full of numbers with something like the following.
val nums = readLine().split(" ").map(_.toInt)
This code returns an Array[Int] with as many values as are entered on the given line of input. The split method is from the Java API and breaks a String into an array around some delimiter. Unfortunately, many educators who aren't familiar with functional programming have a negative reaction to map. They shouldn't, but I think there is a natural reaction that if they don't know something then it is obviously too complex for the novice. In reality, map is much simpler than the equivalent code in most other languages and students pick it up nicely when exposed to it early on.

Programming Environment/Tooling

One of the standard complaints about Scala is that the tooling isn't as advanced as other languages. Inevitably there is some truth to this as any new language starts with a disadvantage in that area. However, people leveling this complaint really need to have worked with Scala very recently for it to carry weight as the support environment around Scala is advancing by leaps and bounds.

In a Twitter conversation, Martin Odersky mentioned that he prefers IDEs for students because of the immediate feedback. There is no doubt that this is a great strength of IDEs. I also feel that in languages like Scala with type inference the ability of the IDE to display types is extremely beneficial. I use Eclipse for my own code development and I have felt that Eclipse works really well in the MOOCs that Martin has run on Coursera.

Despite these things, we use command line and a basic text editor in our CS1 and that works well with Scala. Inevitably part of our choice of these tools is historical. There are also many pedagogical reasons we choose to have students use these basic tools for CS1. They include things like leveling the playing field for experienced and novice programmers and our desire to have Linux and command line early in the curriculum. Comparing command line tools to Eclipse though I think the biggest reason to go command line in CS1 is the relative complexity of Eclipse. I agree that it is a great tool for the MOOCs, but the MOOCs have people like me signed up for them. My guess is that very few participants have never written a line of code before in their lives. Thanks to the current state of CS education in the US, 50% or more of my CS1 students have never seen or written code before entering my class. (I am hopeful that Code.org and the general push to include more coding in schools will help to change that.) The other half has taken a course using Java under Windows with an IDE in their High School. Starting off in Eclipse would give those experienced students even more of an advantage coming in. I'd rather give them something new to learn to keep them engaged.

One last point I would offer in support of command line is that I think it helps to instill some good practices. If you are editing your code in a text editor you really do need to stop every so often and make sure that what you have written does what you want. The lack of immediate feedback and hover-over types forces students to focus more on what they are doing. They have to think through the types of their expressions instead of relying on their tool to do that work for them. As a result, students truly appreciate Eclipse when I introduce them to it at the end of CS1 as we start the transition to object-orientation and CS2.

Regular Syntax

Another complaint that one often hears about Scala is that it is too complex. I think that this complaint has been well dealt with in other spaces, especially with the concept of there being different levels of Scala programming. I want to briefly dispell this for topics at the CS1 level. Indeed, I would argue that for CS1 Scala is significantly simpler than Java because it is more completely object-oriented and has a more regular syntax. One of the first examples of this that comes up in CS1 is what happens when you have to convert types.

Anyone who has taught CS1 knows that it doesn't take long before you run into situations where your students have one type and they need another. If they have an Int and need a Double everything is good. However, if they have a Double and need an Int then things aren't so simple. Even worse, they get a value as a String and they need a numeric type. We can illustrate the problem here using Java. If you have a double and need an int then you need to do a narrowing cast.
double estimate = Math.sqrt(input);
functionThatNeedsAnInt((int)estimate);
The first time you hit this in your course you have to take a little detour to describe some completely new piece of syntax. They won't see many other uses of syntax for a long time after this first introduction and hopefully when you actually get to inheritance hierarchies you spend some time telling students that narrowing casts are risky and lead to runtime errors if they aren't guarded with a check of instanceof.

The real problem here is that Java has primitive types. When Java was created this was a smart thing to include. Just look at the performance of Smalltalk to see what happens when you treated basic numeric types as objects in the mid-90s. However, they add a lot of complexity to the language including many details that students have to struggle with. Autoboxing hides some of the details associated with primitives in Java, but that doesn't mean students are freed from understanding the details. If anything, it just makes it harder for students to really understand.

The following week you run into the situation where students have a String and need a numeric type. So students naturally go for the obvious solution of a type case with code like (int)str. Only this doesn't work. So now you get to introduce something else new. In this case Integer.parseInt(str). You can either present this as a complete black box or you can choose to spend some time talking about the wrapper classes and static methods in them that can help you do things with primitives.

As promised, this is much simpler in Scala, in large part because everything is treated as an object at the language level. Yes, primitives still compile down to something different on the JVM to maintain speed, but that is an implementation detail, not something that matters to CS1 students who are trying to solve simple problems on a computer. In Scala you get to have code like this.
val estimate = math.sqrt(input)
functionThatNeedsAnInt(estimate.toInt)
println("Enter a number or quit")
val str = readLine()
if(str!="quit") {
  functionThatNeedsAnInt(str.toInt)
}
The use of methods like toInt is standard and uniform. You have the toString you are used to in Java, but it works on Int and Double too. You can also do other conversions that make sense such as toDouble from a String or toChar from and Int. Once you hit collections students find the use of toList and toArray to be perfectly natural.

One final point on primitives and the lack of them in Scala is the type names themselves. It seems like a small issue to capitalize types like int, but when you are working with the novice programmer, having to describe why int is lower case and String is capitalized actually matters. What is more, when you get to the point where students are creating their own types it is much easier to get them to adhere to the standard if every type they have ever seen starts with a capital letter. Telling them that variable and method names start lower case while type names start uppercase is much nicer if the language itself doesn't break that simple rule.

Getting rid of primitives isn't the only enhancement to the syntax that makes Scala work well for CS1. Scala lets you nest anything anywhere. The rules of Java, which can seem rather arbitrary to a novice programmer, aren't an issue in Scala. Helper functions can be nested inside of the function they help just as an if can be nested in another if. When you get to classes later on the same type of freedom applies there as well.

Another change in the language that I have found to really help in CS1 and CS2 is the removal of the static keyword. My personal experience with CS2 was that static was a concept that students really struggled with. The fact that this confusing keyword had to appear on the main method of their first program didn't help. Scala does away with the static keyword and instead provides object declarations that create singleton objects in the scope they are declared in. Since students are used to interacting with objects, this makes much more sense to them in CS1 when I can just say they are calling a method on an object instead of saying that they are calling a static method, like sqrt or parseInt on a class. Indeed, I don't even mention the word "class" in CS1 until we start bunding data together with case classes. Before that it is the objects that are important, not the classes.

To be fair, there is one minor challenge with the object declaration in Scala, and that is just one of terminology. It is challenging, when talking to students, to differentiate between usages of the word "object".

The last syntactic change that I have noticed, which I find helps make things more regular in Scala is that every declaration begin with a keyword. The code samples above show that val can be used to declare values. There is also a var keyword that creates what you normally think of as a variable. (val is like a final variable in Java.) Functions and methods are declared using the def keyword. There is a type keyword for making shorter names as well as class, trait, and object keywords for declaring those constructs. Again, the benefit here is regularity of syntax. It is easy to tell students that declarations start with the appropriate keyword and students can easily look at a declaration and know from the keyword what type of thing is being declared.

It is worth noting with val and var that Scala is making it easier to get students to use good style. In Java you really should make variables that don't change final. However, getting students to type those extra keystrokes is a bit challenging. I find it works much better to tell students to use val by default and only change things to a var if it is actually needed. Not all students will follow this recommendation. Some will get lazy and just make everything a var, but the percentage who do so is much smaller than if you are requesting the final keyword in Java.

Functional Aspects

This is where it is possible to lose a lot of instructors. Yes, the functional paradigm is not as widely spread as the impertive paradigm. However, that is largely a historical artifact and something that is changing. After all, the newest versions of both C++ (C++11) and Java (Java 8) include lambda expressions as a language feature. So the reality is that teachers are going to have to deal with some aspects of functional programming at some point. Why not do it in a language that had those features from the beginning instead of one where they were tacked on later. I promise you, the former option leads to a more regular syntax and usage than the later.

As was mentioned in the last post, I don't teach my Scala class from a purely functional perspective. It wouldn't be hard to do so. Simply skip the section on var and don't show the students the Array type, which is mutable, and what you are left with is very functional. However, I agree with the developers of the language that functional is great when it is great, but that there are places where it just makes more sense for things to be imperative. For that reason, I use functional and imperative aspects side-by-side. I highlight when things are mutable and when they aren't, something I already did in Java to explain why toUpperCase on a String didn't alter the original value. I use whichever approach makes the most sense for whatever we are doing. When neither approach is distinctly better I often ask students to do things multiple ways just to make sure that they understand the different approaches.

The first place where having functional programming really alters what I teach in CS1 is when I introduce lambda expressions/function literals right after talking about normal functions. We use this early on to make our functions more powerful. I don't abstract over types in CS1, but I can abstract functionality by passing in a function as an argument and I do spend time showing them this.

Where the lambda expressions really come into play is when I start dealing with collections. I teach both Arrays and Lists in CS1. One huge change from previous languages in that in Scala I teach these collections before loops. In Java or C there is only so much you can do with an array if you don't have loops. However, the higher order methods in Scala and the fact that the for loop is really a foreach allows collections to not only stand on their own, but to really belong before loops.

The power of the collections comes largely from the higher-order methods that take functions as arguments. The map and filter methods are the ones used most frequently, but there are many others available that make it easy to do fairly complex tasks with collections. There are also some more simple methods like sum that come in very handy for many of the simpler examples that are common for CS1. One of the standard examples of this that I give is the problem of finding all the minors in a list of people. Let's start with the Java code for doing this.
List minors = new ArrayList();
for(p:people) {
  if(p.age < 18) minors.add(p);
}
This code assumes that you are far enough along to be using java.util.ArrayList. If you are still working with just the built in arrays you need something a bit longer.
int count = 0;
for(p:people) {
  if(p.age < 18) count++;
}
Person[] minors = new Person[count];
int i = 0;
for(p:people) {
  if(p.age < 18) {
    minors[i] = p;
    i++;
  }
}
I could have taken out a line by reusing the count variable instead of introducing i as a variable, but such variable reuse is a risky habit to into.

So how does this look in Scala?
val minors = people.filter(_.age < 18) // could be p => p.age < 18
Now I have had some people try to convince me that this is harder to read. I would argue that is a clear indication that they aren't familiar with filter, because once you understand what filter means, the meaning of the Scala code is immediate. Once you feel comfortable with filter you would read this line of code as "declare minors with the value of the elements of people whose age is less than 18." What is more important in many situations is that the Scala code is also far less bug prone, and is especially resistant to logic errors. There aren't many things you can change in the Scala code that won't lead to a syntax error. Changing the < to a > or typing in the wrong number are about the only possibilities and both languages suffer from those.

You might wonder what the type of minors is in the Scala code. The answer is that it is whatever collection type people was to start with. If you were unhappy with that you could use methods like toArray or toList to convert it to the collection type you really wanted.

Now what if we wanted to find the average age of those minors? We can start again with the Java code.
int sum = 0;
for(m:minors) {
  sum += m.age;
}
double averageAge = (double)sum/minors.length; // or .size() for the ArrayList
Note that cast to a double to prevent this code from doing integer division. So what about in Scala?
val averageAge = minors.map(_.age).sum.toDouble/minors.length
// or
val averageAge2 = minors.foldLeft(0.0)((sum,m) => sum + m.age)/minors.length
// or
val averageAge3 = minors.foldLeft(0.0)(_ + _.age)/minors.length
I have presented three possibilities to illustrate some options. I expect my CS1 students to write the first version, where we use a call to map to pull out all of the age values. This version is less efficient because it actually creates a new collection. The other two are more equivalent to the Java code in how they run, but I have to be honest and say that students often do find the fold methods to me more difficult to reason about.

If one were looking for something to complain about, you might argue that the Java versions are teaching the students more about problem solving as they force them to break things down further. While I'm not at all convinced that this is true, I would certainly note that you can write code just like the Java version using Scala. The difference is that in Scala you don't have to. So I would show my students both approaches in Scala and expect that most will pick the more Scala-like option. The exceptions to that rule would likely be students who had previous experience in Java.

I also believe that at some level CS1 students can only handle a certain spread between the magnitude of the problems they are solving and the smallest details that they have to go down to. So if you force them to go to a lower level of detail in their solutions you aren't so much forcing them to learn more problem solving, but instead constraining the scope of the problems that you can ask them to solve.

There are a few other things I would want to comment on related to CS1, but this post is already getting to the TL;DR length so I'm going to stop this one here and save the rest for a later post. Your comments and thoughts are welcomed.