Supporting Scala Adoption in Colleges

Scala Days North America just finished, and one of the big surprises for me was how many talks focused on teaching Scala. The first day had roughly one talk on teaching Scala in every time block.

• Scala for Everyone - Marina talked about the coding workshops she is running in Australia and her book for teaching functional concepts to young kids through fairytale metaphors. (Presentation Video)
• Adventures in Teaching Scala in the B-School - Austin talked about teaching Scala and associated big data tools to students in the Business school at UT Dallas. (Presentation Video)
• Teaching Scala to the Statically Challenged - I think Rebecca wins the award for the best title with a talk on how to teach Scala to professionals coming from backgrounds where they only learned dynamically typed languages. (Presentation Video)
• Teaching Scala: A Roundtable Discussion - A general panel on teaching Scala with Ryan, Neville, Maciej, me, Kelley, Martin, and Heather. (In the order listed on the schedule. I have no idea how that order was decided on.) (Presentation Video)
• ScalaQuest: The Scala Adventure - Alejandro talked about the technology that has gone into their online game designed to teach programmers who don't know Scala. (Presentation Video)

The topic of increasing the use of Scala in colleges also came up in the final panel (Presentation Video).

I think it is pretty clear that the companies using Scala feel a need to get more developers who either know the language or can transition into it quickly and easily. Large companies, like Twitter, can run their own training programs, but that is out of reach for most companies. What most companies need is for more colleges to at least introduce Scala and the idea of functional programming in their curricula.

The Current State of Affairs

The current reality of college CS education is that imperative OO is king. For roughly two decades, Java dominated the landscape of college CS courses, especially at the introductory level. In the last ~5 years, Python has made significant inroads, again, especially at the introductory level. Let's be honest, that is really a move in the wrong direction for those who want graduates that are prepared to work with Scala because not only is Python not generally taught in a functional way, the dynamic typing doesn't prepare students to think in the type-oriented manner that is ideal for Scala programming. (I have to note that this move to Python has been predicated on the idea that Python is a simpler language to learn, but an analysis of a large dataset of student exercise solutions for zyBooks indicates this might not actually be the case.)

It is also true that some aspects of functional programming, namely the use of higher-order functions, has moved into pretty much all major programming languages. However, it isn't at all clear that these concepts are currently appearing in college curricula. Part of the reason for this is that in nearly all cases, features added to languages late are more complex than those that were part of the original development. Yes, Java 8 has lambdas and you can use map and filter on Streams, but there is a lot of overhead, both syntactically and cognitively, that makes it much harder to teach to students in Java than it is in Scala. That overhead means professors are less likely to "get to it" during any particular course.

The bottom line is that the vast majority of students coming out of colleges today have never heard of Scala, nor have they ever been taught to think about problems in a functional way.

What Can You Do?

If you work for a company that uses Scala, it would probably benefit you greatly if this state of affairs could be changed so that you can hire kids straight out of college who are ready to move into your development environment. The question is, how do you do this? I have a few suggestions.

First, contact the CS departments at local colleges and/or your alma mater. Tell them the importance of Scala and functional programming to your organization and that you would love to hire graduates with certain skills. This has to be done in the right way though, so let's break it down a bit.

Who Should You Talk To?

My guess is that a lot of people will immediately wonder who they should be reaching out to, but I'm pretty sure it doesn't matter, as long as it is a faculty member in Computer Science. You can always start with the chair and ask them if there is someone else in the department that would be better to talk to, but no matter who you start with, you'll probably wind up being directed to the most applicable person.

What Types Of Schools?

I know that it will be tempting to focus on big schools with the idea that you can get more bang for the buck if you do something with the local state school that graduates 300+ CS majors a year. The problem here is that many of the stereotypes for big organizations not being agile apply to colleges as well. The bigger the school, the harder it likely is to create change. Smaller schools might not graduate as many students, but they are probably more adaptable and open to change. Departments with <10 faculty members might not crank out hundreds of majors, but they can probably produce a few very good ones each year that you would love to have on your team.

This doesn't mean you skip on the big schools. If you can convince your local state school, the payoffs are huge. I would just urge you to cast a wide net. Any school with a CS department is worth reaching out to.

How To Start The Conversation

It probably isn't the best idea to just go to a college and tell them that they are doing things wrong and that you have ideas on how they can do it better. One way to start a conversation would be to say that you are interested in talking about pedagogy and their curriculum to get a better idea of what they do and how they do it. However, an even better idea would be to initiate the conversation by offering to do something for them.

Most colleges will have some type of venue for outside entities to give talks to their majors. Ask if they have a seminar/colloquium that you might be able to speak at. I am the current organizer for the CS Colloquium at Trinity and I would love to have speakers from industry offer to come to give interesting talks to our majors (hint, hint). I'm quite certain that I'm not alone. This gives you a great venue to say all the things that I mention in the next section, both to faculty and students, efficiently.

If you have a local Scala Meetup, you might see if they would be willing to send out an invitation to their majors for that as well.

What Should You Say?

This is where things are a bit more tricky. Most colleges do not view themselves as vocational training. They don't just put things in their curricula because companies would like it, though they do feel some pressure to make sure their graduates have the skills needed to find employment. College curricula focus on fundamental concepts, not tools because we know that technology is ever-changing, and our students are going to have to continue learning throughout their careers. We have to build the foundation for that learning. So the key is to show them how the tools that you are using represent the paradigms of the future of the industry.

With this in mind, your goal isn't to convince them to teach Scala, at least not directly. There is a reason that your company uses Scala, and my guess is that you believe that the reasons your company chose Scala are generally indicative of the way that a lot of the industry needs to move. It might be that you see that data keeps growing in importance and size and that processing that data in a way that scales is critical for the future. You know that using a functional approach is key to writing these types of applications both today and in the future. You know that while the framework you are currently using probably won't be dominant in 10 years, the ideas behind how it works and how you use it to solve real problems will still be folded into the frameworks of the future.

I would say that your first goal is to establish that in the highly parallel and distributed environment we live in, the functional paradigm has moved from an academic play area into an essential real-world skill. You might also tell them why the pragmatic approach of Scala makes sense for bringing the functional paradigm into practical usage. Highlight how it impacts your use case and how you see that being a use case that will only grow with time.

Going back to the fact that colleges want to teach things that are foundational, I would point out how many other languages are following in the footsteps of Scala. This is key because it makes it clear that learning Scala isn't just learning one language. Instead, it is opening the door to where most older languages are evolving as well as where many new languages are going. Knowing Scala helps future-proof students in this regard, and Scala isn't just sitting still and getting older. It is a dynamic language with creators who are working to keep it on the cutting else of language development while maintaining an eye to the practical aspects of what makes a language usable in industry.

If you get to the point where they are convinced but aren't certain how to put Scala and functional programming into their curricula, point them to academics who have been using Scala for teaching. I would personally welcome all such inquiries. Just tell them to write to [email protected]. In the US both Konstantin Läufer and George K. Thiruvathukal at Loyola University Chicago have experience in teaching with Scala and have an interest in spreading the word. So does Brian Howard at DePauw University. While Martin has the most experience of anyone teaching Scala, personally, I'd rather he focus his time on Scala 3 development. Also, while Heather might be a freshly minted academic at CMU, she is definitely a Scala expert and her experience with the MOOCs means that she has taught more people Scala than almost anyone in the world.

Going Further

Giving a talk every so often is a nice way to let schools know what types of technologies you use and why you see them being important in the future. As such, it can provide a subtle way to influence the curriculum. However, if you are willing and able to put in a bit more time, you can have a more explicit impact on what is being taught by offering to teach a course as an adjunct professor the way Austin is doing at UT Dallas and the way Twitter does at CU Boulder.

The challenge with this approach is that not everyone is a naturally gifted teacher and it will be a fairly significant time sink. Technically, whoever does it will get paid, just not that much. (Teaching one class as an adjunct pays well under $10,000 dollars and is often as low as $3000.) The real question is whether your employer is willing and able to let you do this. I will note that for various reasons, a developer doing this who doesn't have a Master's degree will need to be reasonably senior to make it work at a lot of Universities.

The upside of teaching a course is that you can probably get into an upper division course where you have fairly complete control over the curriculum and you can teach exactly the topics that you would most like new hires to arrive with. Due to growing enrollments, the vast majority of colleges are likely quite open to having an adjunct help out, and many will be open to an interesting upper division offering as they can probably move faculty around to cover other courses. (At Trinity, we are looking for an adjunct for next fall and while they are currently scheduled for an introductory course, if someone wanted to come in and teach my Big Data course using Scala, I could certainly switch to the introductory course to make things work.) Of course, if you want to teach CS1/CS2 with Scala, I've got a bunch of materials you can use to help organize the class.

You might also see if the department has an advisory board. Having a seat on such a board will give your company insight into the inner workings of the department and how they think about the field while also giving you a venue to talk about what you value and where you see the future of the field going.

In The Meantime

Until other colleges catch on to the value of Scala, remember that at Trinity University we are teaching all of our students both Scala and how to think functionally, so let me know when you are looking for interns or junior devs.

Performance of N-Body Simulation Styles in Scala

I spend a lot of time doing N-body simulations. My working simulation code is written in C++. The reason for that is simple, speed. It is a serious number crunching code and even written in C++ runs can take months to complete. I would love to do these simulations in some other language that I enjoyed writing code in more, but I'm not willing to give up all that much speed in order to make that happen. A number of years ago a student and I explored the performance of a Java version of the code, and we found that we could get performance within 10-20% of the C++ version, but doing so required doing a number of things in a way that made the Java almost as challenging to work with as the C++. These days, I'd really love to be able to convert my code to Scala, as I find it much more enjoyable to code in, but I'd have to be certain that I can get performance close that what I'm getting in C++. My guess is that in the end I'll wind up updating my C++ code to use features of C++11, 14, and 17, but I still like to explore the possibilities of using a different language.

There are lots of ways that you can write N-body simulations in Scala. Some of them take advantage of the expressivity of the language to produce shorter code that is easier to read and generally less bug prone. However, there are reasons to believe that those approaches might also tend to be slower. For a while I've been meaning to explore different approaches to see how much of an impact it really has on the speed of execution. While there aren't all that many people who do N-body simulations, my expectation is that the results of these performance tests will apply to many other numerically intensive applications.

Array of Mutable Classes

In C++, one represents particles with a struct and makes sequences of these using arrays, vectors, or valarrays. Everything is generally mutable. This first version of the code in Scala is written to mirror the C++ code. Of course, there is a huge difference in the memory model. When you make a sequence of a simple struct in C++, the entire memory for all elements is laid out in a single contiguous block. The way this code is written in Scala, the array is an array of references to instances of MutableBody and each of those contains two references to instances of MVect3. This matters because caching is vitally important on modern computers and contiguous memory accesses have much better caching performance. In this simple example, odds are that because all of the objects are allocated in order at the beginning of the program, they wind up being contiguous in the heap, but there are still multiple levels of references that have to be followed, which are likely to impose some performance cost.

This code really does look similar to what the C++ code for this type of thing looks like, unless you happen to have a library set up for SIMD vector operations or expression templates for the 3-D vectors. Unfortunately, that isn't a good thing. Not only is this code verbose, I can speak from experience that it is bug prone. It is just too easy to have one of those x, y, or z fields typed wrong and the resulting error is very difficult to diagnose and track down.

Array of Immutable Classes

Given the capabilities of Scala, a much "better" way to write this is to use immutable classes and add symbolic methods to a 3-D vector class so that you can simplify the math expressions and make them less error prone. Of course, this change means that you are doing a lot of memory allocation making small objects for all of the 3-D vectors.

Clearly this code is shorter and more readable. It is still using the same basic approach with a mutable array for storage, but the ability to use mathematical operators on vectors improves the code significantly. It is worth noting that in the mutable version you can make operations like +=, but given the math that is being done, they aren't all that useful unless you are making temporary values to store scaled versions and such.

Arrays with Value Class Wrapper

Now we are going to get a bit more interesting and produce a version that tries to give us contiguous memory without hurting program readability and without making lots of temporaries. Basically, this is an attempt to make a version of the code that has the best chance of being speed competitive with the C++ code while still being reasonably readable. The real key areas of this code are lines 5-29 where we make a number of arrays of doubles and then define a value class. The value class is a newer feature of the Scala language that is stack allocated and has no more overhead than a primitive, while allowing you to have nice OO syntax. Instances of it are stored as just primitives on the stack and the methods wind up being static methods in the JVM, so there is no memory or speed overhead of object allocation. In order to use a value class, we have to put the whole thing in an object declaration and not a class declaration. Value classes can't go inside of other classes because then they would be non-static inner classes and that would mean they have the overhead of keeping a reference to their enclosing instance. They could go at the top level, outside of all other declarations, but then they wouldn't have access to the arrays. Putting both the arrays and the value class in an object declaration gives us what we need here.

Unfortunately, value classes are limited in Scala because they aren't really supported by the JVM at this time. The main limitation is that they can only have a single primitive value in them. There are plans to add value types to Java and the JVM. Once that happens, which probably will be Java 10, then you could make classes with three doubles in them that are stack allocated and arrays of them would be memory contiguous, giving you behavior much more similar to C++. Until that time, code like that above can give you a reasonable approximation.

Purely Functional Approaches

Of course, the real key to Scala is the functional aspects, something that none of the above examples took advantage of. The version that used immutable classes still mutated an array that stored references to those objects. I tried two different approaches to doing things functionally that are shown in the code below. The first approach is pretty much just like our immutable class version, but it uses a Vector and the updated method. Even without speed tests, we can feel confident that this is not an efficient approach, but it is pretty much required if we want to do the minimum number of distance calculations where each pair is only visited once. The second version, called forSim2, does twice as many distance calculations, but this allows it to be written in a much more succinct manner because we produce a full sequence with the accelerations to each particle without every mutating them. As it happens, this is the approach that we need to take if we parallelize the code to prevent race conditions. I will explore that more in a future blog post.

This code uses the ImmutableBody and the immutable Vect3 class shown earlier. That makes the code more compact than the non-mutable versions. Those unfamiliar with fold methods might find forSim2 difficult to read, but in general a fold can be used to replace a loop that would accumulate a value in a mutable way. Note that like the previous code, this is put in an object, but for completely different reasons. This code isn't stateful, so there is no reason to have a class. The state is created by the initBodies method and then passed into the forSim methods, which return modified values. This code never stores the state locally. This is a significant difference from the earlier code and should probably be expected for a functional approach.

Timing Results

So how do these different versions perform? We tested all of them using Scala 2.12.1 both with no optimization flags and with -opt:l:classpath -opt:closure-invocations -opt:simplify-jumps -opt:copy-propagation -opt:redundant-casts -opt:box-unbox -opt:nullness-tracking -opt:inline-global. The timing results are shown in the following table.

Optimization	Style	Average Time [s]	rms [s]
None	Value Class	0.704	0.004
	Mutable Class	0.904	0.006
	Immutable Class	1.266	0.020
	Functional 1	8.33	0.09
	Functional 2	2.343	0.048
Optimized	Value Class	0.679	0.001
	Mutable Class	0.682	0.001
	Immutable Class	1.191	0.026
	Functional 1	8.55	0.11
	Functional 2	2.325	0.023

It is good to see that in many ways, my intuitions as to which versions would be fastest proved correct. Without optimization, the version that uses a value class and contiguous blocks of memory in arrays is clearly the fastest, followed by the mutable classes, then the immutable classes, then the purely functional approaches at the end. Note that the second functional approach takes nearly twice as long as the immutable class version. Since it is doing twice as many distance calculations, this indicates that the overhead of being functional is small and the speed difference is basically due to reorganizing the math. I will note again that this reorganization is also required for parallelization, so I would speculate that in parallelized versions, the second functional approach will be comparable to the immutable class version. The first functional approach is a clear loser. Calling updated so frequently on the Vector type is clearly inefficient. I will note though that I tried changing Vector to Array, and the resulting code was so slow for the first functional approach that I never saw it complete. On the other hand, using an array, even if it isn't mutated, seemed to slightly improve performance for the second functional approach.

It is also interesting to note that optimization benefited the mutable class version significantly, making it nearly comparable to the value class version.

Comparison to C++

We will close out this post with a comparison to C++. After all, we can't know if it is reasonable to use Scala for numerical workloads if we don't explore how it compares. I wrote a version of the code in C++ that was basically an adaptation of the mutable class version using a std::valarray for storage. I compiled it using g++ with the -Ofast compiler flag. I also made a separate application in Scala that only ran the value class version and had both the C++ and the Scala time 1000 steps of integration. The result was that the C++ generally completed in 6.22 seconds and the Scala completed in 6.88. Both were consistent across multiple runs. So the final result is a 10% advantage for C++. That isn't a huge advantage, and my guess is that most applications would be happy to live with that for the advantages that they get in coding in Scala over C++ in terms of developer productivity. Granted, that was with g++ I expect that using the Intel compiler or some other highly optimizing, and not free or open source, compiler will produce even faster executables for C++.

For me, the bottom line is that if you hear people say that Scala (or Java/JVM) are slow, there are good odds that they haven't really tested it compared to other languages/platforms. For straight number crunching applications, feel free to point them to this blog post to show them that the difference in speed really doesn't have to be all that large. My guess is that using macros, it would also be possible to create Scala code that has the readability of the immutable Vect3 class with symbolic methods, but without the speed cost for allocating lots of temporary values. This would be akin to expression templates for that purpose in C++. Maybe I'll take a stab at creating that code and write a blog about it as well. I also look forward to the Java 10 JVM adding value types, as I believe that they have the potential to significantly improve the performance of numerical code in all JVM languages.

Other Code

Here is the code for C++ and the timing in Scala in case anyone wants to be able to run everything.

C++ Code

Scala Timing

Performance of Scala for Loops

One of the interesting features of the Scala programming language is that the for loop is basically syntactic sugar for calls to collection methods like foreach, map, filter, and flatMap. They are often called for-comprehensions and they have a lot more flexibility than what you get from a standard for loop in most languages or for-each loops in the languages that have them. The fact that they get compiled to calls to these other methods also means that Scala for-loops can be used on things that aren't collections like Options and Futures.

Unfortunately, this flexibility has often come at a price. As I noted in an earlier post, Loop Performance and Local Variables, using a for loop produced code that was significantly slower than using while loops. That was back in 2013, and I was using Scala 2.10. With the release of Scala 2.12, I really wanted to see if this was still the case. The primary change in 2.12 was to make Scala compile to Java 8 bytecode using all the new features of the Java 8 JVM. One of the main additions in Java 8 was lambda expressions. Since the foreach, map, filter, and flatMap are higher order methods that take functions, compiling to Java 8 lambdas seemed like it might improve performance. This post looks at testing that hypothesis.

Previous Code

We start by repeating the previous test that was written to look at where variables are declared. I took the same code as used before and simply ran it with three different versions of Scala, both with and without optimization. The following table shows the results.

Version	Opt	Loop	Var Loc	Average Time [ns]	Time Deviation [ns]
2.10.6		for	In	3.410	0.141
			Out	3.700	0.293
		while	In	2.823	0.270
			Out	2.861	0.311
	-optimize	for	In	3.712	0.588
			Out	3.856	0.653
		while	In	2.895	0.252
			Out	2.881	0.279
2.11.8		for	In	3.221	0.351
			Out	3.666	0.397
		while	In	3.023	0.510
			Out	2.848	0.243
	-optimize	for	In	3.389	0.402
			Out	3.014	0.120
		while	In	2.858	0.287
			Out	2.848	0.254
2.12.1		for	In	3.154	0.354
			Out	3.456	0.407
		while	In	2.765	0.167
			Out	2.751	0.139
	See Below	for	In	3.261	0.321
			Out	3.279	0.549
		while	In	3.141	0.207
			Out	3.164	0.264

All runs were done using Java 1.8.0_111 for the runtime. For 2.12, they added a lot of different optimization flags to the compiler. The values used for the timings in this post are -opt:l:classpath -opt:closure-invocations -opt:simplify-jumps -opt:copy-propagation -opt:redundant-casts -opt:box-unbox -opt:nullness-tracking -opt:inline-global. There is enough scatter here that it is hard to draw really strong conclusions. It appears that the while loop still has an advantage, but the percent difference in speed seems smaller across all the "current" compilers than what had been seen back in 2013. I put current in quotes because while 2.10 is older, 2.10.6 is a fairly recent release and the Scala team backports things when it makes sense, so there are good odds that 2.10.6 is incorporating optimizations of the for loop that weren't present in the earlier version of 2.10 I had been using in 2013.

N-Body Simulation

The problem of building multiplication tables was rather contrived as a simple example that worked well for testing the declaration locations of variables. If people are going to actually make their code uglier putting in while loops in place of for loops, it would be good to see if it matters on a somewhat more realistic example. For this I decided to do a simple first-order numerical integrator of bodies using gravity. This is a problem that involves a lot of number crunching in loops and which happens to be at least related to things that I write for my research, so it seemed like a good place to test performance.

The code used for this test is shown below. For the purposes of this post, what really matters is the forSim and whileSim methods. These have multiple loops including one area where they are triply nested. I store all the values in mutable arrays and then use a value class to access the elements in an object-oriented way. I chose this approach as there is minimal overhead from object allocation, potentially better cache performance, and I have a feeling that it is faster than other approaches, though testing that is a matter for later posts.

Here is a table giving the timing results for this code again the same three compilers.

Version	Opt	Loop	Average Time [s]	Time Deviation [s]
2.10.6		for	0.666	0.002
		while	0.667	0.029
	-optimize	for	0.660	0.012
		while	0.658	0.001
2.11.8		for	0.716	0.009
		while	0.669	0.007
	-optimize	for	0.675	0.006
		while	0.656	0.001
2.12.1		for	0.699	0.003
		while	0.683	0.001
	See Above	for	0.676	0.001
		while	0.683	0.003

Note that for this code, there is very little difference between a for loop and a while loop. These tests were very stable in their timing results and while building up the tests I ran them multiple times and found little variation. It really doesn't appear that 2.12 did anything to help with the difference between for and while loops in either of these examples, but in this one, there really isn't a significant difference in any version. What does that mean? As with so many things dealing with performance, you should write clean code that runs first. Once you have that, and you are tweaking things for performance, you might consider changing your inner-most loops from for loops to while loops, but it is quite possible that it won't matter.

I also feel compelled to note that the for loop version is much easier to parallelize than the while loop version because of the ease of switching to a parallel collection. I haven't done it here as one must make some alterations to prevent race conditions, but that is something that I might also explore in a future post.

Variables in for Comprehensions

There is one caveat to the conclusion that for loops don't hurt performance in the larger example. In the forSim method shown above, the variables pi and pj are both declared inside of the inner most loop. The for comprehension in Scala allows variables to be declared in the "header" section of the loop. When I first wrote this code, I declared pi between the two generators and pj right after the generator for j. One wouldn't think that this would matter much, but it did. Having the declarations up in the header instead of the body cause this code to run roughly 2.5-3x slower than when they were put as the first lines in the body of the for loop. I don't have an explanation for this behavior and I haven't explored the generated bytecode to see what might be causing it. However, based on this result, it is probably worth not using the variable declaration capabilities of for comprehensions if performance is critical to your application.

Duck Typing vs. Structural Typing

This post is in response to the post Duck Typing in Scala: Structural Typing, which was intended to introduce readers to structural types in Scala. At the beginning the author describes how structural types aren't exactly duck-typing, but I believe he draws the wrong distinction. His statement is that structural types aren't duck typing because they are checked at compile time. However, if you look at the Wikipedia entry for duck-typing, which he links to, you will see that static checking isn't what is significant here. Indeed, there is a section on duck-typing in statically typed languages. So if the static typing isn't what causes Scala's structural types to not be duck-typing, what does? I am going to argue here that it is the explicit interface of the structural types that distinguishes them from duck-typing.

When a language is duck-typed, the type correctness is determined by whether or not the value passed into a function/method supports the operations that are used on it. The author of the post is correct that most languages that use duck-typing are dynamically typed languages like Python or Scheme. In these languages, the correctness of the program is determined while it is running. Any value can be passed into a segment of code, but if that code does something the value doesn't support, it will cause a runtime error. There are no correctness checks at a "compile" phase that make sure the values passed in actually support the operations needed.

Duck-Typing in C++

We can contrast this to another language that includes duck-typing but does have static checks on the type correctness. While Wikipedia mentions Boo, C#, and F#, I would point to templated code in C++. The first example used in the original article shows Scala code that includes a structural type that requires the quack method. I will write a similar example here using templates in C++.

template
void quacker(const Q &q) {
    cout << q.quack("Quack") << endl;
}

class BigDuck {
public:
    string quack(const string &value) const;
};

class SmallDuck {
public:
    string quack(const string &value) const;
};

class NotReallyADuck {
public:
    string quack(const string &value) const;
};

string BigDuck::quack(const string &value) const {
    string ret(value);
    for(auto &c:ret) c = toupper(c);
    return ret;
}

string SmallDuck::quack(const string &value) const {
    string ret(value);
    for(auto &c:ret) c = tolower(c);
    return ret;
}

string NotReallyADuck::quack(const string &value) const {
    return "prrrrrrp";
}

int main() {
    quacker(BigDuck());
    quacker(SmallDuck());
    quacker(NotReallyADuck());

    return 0;
}

The quacker function is perfectly happy taking all three of the defined classes as arguments, despite they fact that they have no common supertype. However, if you try to call quacker with a type that doesn't have a quack method with an appropriate signature, you will get a compile error.

So how is this different from the Scala example shown in that post and why do I feel that this is duck-typing when structural types aren't? To illustrate this, we will focus in on just the quacker functions. Here is the Scala version from that post.

def quacker(duck: {def quack(value: String): String}) {
  println (duck.quack("Quack"))
}

Now compare that to the C++ code shown above. Note how the Scala code explicitly states that the argument passed in needs to have a quack method. This doesn't appear in the C++ code. In C++, the requirement for a quack method is implicit, not explicit. It is not directly stated, but instead it is inferred by the compiler when it tries to take in an argument and use the type of that argument as type Q. This is the hallmark of duck-typing. In true instances of duck-typing, you never say whether the type can walk, swim, and quack, it just tries it out and creates an error when it can't. The question of whether that check is done at compile time or during runtime is orthogonal to whether it is using duck-typing.

Structural Typing

The structural types in Scala aren't duck-typing simply because the required interface is explicit, not implicit. So if structural types aren't duck-typing, what can we say they are? Well, they are a form of structural type system. Surprising, huh? You can find information comparing structural types to nominative type systems, but the basic difference is that in a structurally typed language (or system that is part of a langauge), it is the structure of the types that matters, not the point of declaration of the name given to them. Most programmers are more used to the nominative approach, but there are languages that use structural typing. In this approach, types like class Point3D(x:Double, y:Double, z:Double) and class Vect3D(x:Double, y:Double, z:Double) would be equivalent. So you could use one in place of the other. I have to admit that this makes me cringe a bit because I would really like these to be distinct types, but there are places where this style of type equivalence has value and it is for those situations that the structural types in Scala exist.

You can effectively define subtypes in a structural type system as well. Adding members/operations to a type effectively creates as a subtype. For example Particle(x:Double, y:Double, z:Double, mass:Double) could work as a subtype of the Point3D or Vect3D types above. Any code that uses a Point3D would only access x, y, and z and those are all safe to access on Particle so it is safe to treat Particle as a subtype in a structurally typed system.

Relative Merits

I think at this point it is worth comparing the relative merits of duck-typing to structural typing and I will focus on the comparison between templates in C++ and structural types in Scala so that the issue of static checking versus dynamic checking isn't in play. (Holy wars continue to wage over that particular distinction that would only muddy the waters here.) I'm also going to ignore the question of performance, because that is really an implementation detail. Templates in C++ are generally fast because the compiler generates distinct machine code for each distinct template usage. The only potential problem with that is the code bloat that can occur if a large piece of code has multiple template arguments and is called with a lot of different types. Structural types in Scala are implemented with reflection, making them much slower than normal calls. For that reason, structural types in Scala should generally be avoided. Use them when you need them and in situations where the performance impact won't be too significant. The real question I want to consider here is, which is better, having an explicit interface that types must adhere to in order to be used or having an implicit interface that comes about simply based on the usage of that type?

While I'm not addressing the static vs. dynamic type issue here, I have a funny feeling that similar lines will be drawn in the sand for this question as well. After all, those who like dynamic typing are probably more comfortable with the "freedom" of an implicit interface. Those who prefer the "safety" of static type checking are probably more prone to like to actually see the explicit interface. I fall generally into the latter camp. The implicit interfaces of templates in C++ can, in my opinion, lead to all types of challenges. How do you know what you can pass into a templated function? Well, you could go through all the code and find every required operation, or you could just try something and see if it works. Granted if it doesn't work, the error messages you get are likely to be both long and cryptic. While C++ compilers aren't generally known for producing easy to interpret error messages, few can argue that deeply nested template functions/methods can produce wickedly long and obfuscated error messages. (Did we really need 100+ lines of error output because the type I called this with doesn't have operator< defined?) The challenges of these implicit interfaces are also seen in the documentation for C++. For example, what is the interface for an iterator? It is documented as part of the standard libraries, but it isn't really anywhere in the code. There is nothing that says that a class must have these operations to be an iterator, it is just a convention that people follow. The addition of concepts in a future release of C++ might fix this, but for now it is one of the challenges of using the language.

I have to admit though that there are some freedoms to these implicit interfaces. Going back to iterators, the list of things that are required for the iterator types in C++ is fairly long. Writing the structural type in Scala that would be equivalent to that would be a real pain. So if the number of required members/operations is long, having to explicitly declare them makes for unhappy code. Of course, if it is something that is used frequently, the proper solution would be to create a trait/interface for that type and pass that around. Doing so would also get around the performance problems in Scala. However, that approach does remove some of the freedom you get from duck-typing or structral types. Going back to the iterator example, most code won't really need all of the methods/operations of an iterator. Most of the time you are only going to use a few key ones. While the standard library code has everything in it, if you write your own for a private library, it is really nice if you can get away with only implementing those things you really need and not everything else that would normally go there. I had my students writing lots of C++ iterators in a data structures class this last semester. I never forced them to write absolutely complete iterators. There was no point. They learned what they needed from a subset of the methods and it was sufficient for the purposes of what we were doing. It is true that in Scala, you can often write a trait that has a minimal set of abstract methods and defines other things in terms of these, but I have to admit that there is still a certain benefit to having to only write the code that is absolutely needed and there are even times when not having to write all the required members explicitly is also very handy.

More Benefits of Scala in CS1

In my last post I went through most of the aspects of Scala that I feel make it a nice fit for teaching CS1. Since that post was getting a bit long I stopped it before I had completely finished. In this post I will hit the last few points.

Total Access to Java

I probably should have included this in the first post because it really is very significant for a number of reasons. The one that I think matters most for educators is that most educators have years of experience with Java and have built up a large knowledge base related to the Java API and other Java libraries. Moving completely away from that can be scary. Scala doesn't just run on the JVM, you can call Java code and libraries in a way that is completely seamless. Indeed, if it weren't for the java. at the front of the complete names of classes (or import statements) students wouldn't even realize that they are calling code written in a different language.

While there really isn't much need for java.util.Scanner in Scala, it is a library that every CS1 teacher who has used Java is likely familiar with. For that reason, I will use it as an example.

val sc = new java.util.Scanner(System.in)
val str = sc.nextLine()
val word = sc.next()
val fiveInts = Array.fill(5)(sc.nextInt())

Making objects and calling methods in Scala can use the same syntax as in Java. The Scala libraries include things for which they believed there was a benefit to creating something new using Scala style. For some functionality, you will use the Java libraries because there wasn't an advantage seen to creating a new one in Scala. For educators though, this means that if you aren't certain how something is done in Scala you can fall back on Java. Granted, over time you will want to learn the proper Scala style for doing whatever it is, but you can make the learning curve a bit less steep early on.

From the student perspective, the reality of the world is that they need to learn Java at some point. Maybe that won't be true in a decade, but it is part of the reality of things right now. Given that, the close tie between Scala and Java can make it easier for students to learn Java on their own. That will be especially true if they learn some other C-family language along the way. I would argue that they need to learn some unmanaged language, so C/C++ should appear at some point in the curriculum. That gives them the main syntactic differences between Java and Scala and they should have a reasonable knowledge of some of the more significant elements of the Java API from having learned Scala. Their Scala background will also serve them well for understanding the Java memory model other than the peculiarities of primitives, which are more similar to C/C++ behavior.

Strings as Collections

I described some of the benefits of collections in the last post. The Array and List types aren't the only types that those methods can be called on. A String can also be treated as a sequence of characters. This is made possible by an implicit conversion. The details of implicits are part of the higher levels of Scala programming and not something I deal with in CS1. In fact, I generally don't even have to tell students anything about implicits in CS1. After introducing the basic collections I can simply tell students that all the methods we just learned for working with Array and List can be called on strings and they get it.

To help illustrate this point let's look at some examples.

val upper = str.map(_.toUpper)
val vowelCount = str.count(c => "aeiou".contains(c))
val letterCount = for(c <- 'a' to 'z') yield 
  str.count(_.toLower == c)

The last two examples aren't ideally efficient, but the point is that they are very clear and simple to express and they make things very tractable for CS1 students. That allows you to push to bigger examples/exercises than you might do otherwise.

It isn't just the higher order methods that are available either. You can look at the API page for scala.colection.immutable.StringOps to see the various options. Not only does this improve expressivity over plain Java strings, it goes back to making things uniform. When students get comfortable calling methods with certain names to do various things on the collection types, it is remarkably handy that they can call the same methods to do the same things on Strings as well.

Files as Collections

One of the topics that I find really opens up options for what I can have students do in CS1 is text files. Without files you are limited to information that exists for a single invocation of the program, and you are limited with how you can handle larger data sets. I really like having my students play with big files. After all, if they could do something by hand with a calculator it is challenging to convince them that there was really a need to program a computer to do that task. However, any student who looks at a file with over 10,000 lines of data in it knows immediately that answering any question I ask about that file is a task better left to a computer.

I mentioned java.util.Scanner above. In a Java course that would be the primary class used to read text files. As the code shows, there is no problem at all using Scanner in Scala as well. However, the Scala API provides another class called scala.io.Source that can be used to read text data as well. The advantage of Source over Scanner is that Source fits in with the Scala collections library, which means all the methods on collections that students learned earlier in the semester work here as well. Probably the best way to illustrate the power this gives is with an example. If I have a file that has a matrix of numeric values in it separated by spaces, the following code will read it in.

def parseLine(line:String):Array[Double] =
  line.split(" +").map(_.toDouble)

val source = io.Source.fromFile("data.txt")
val data = source.getLines.map(parseLine).toArray
source.close()

This code starts with a function called parseLine that convers a line of text into the data that we want. The body of this function is simple enough that we could have done it inline below. However, I find this to be more readable and it is a pattern that students will repeat for lots of different file formats, including those where the logic for parsing one line is more complex. After this we open a file using scala.io.Source. Due to the way that packages and imports properly nest in Scala and the fact that the scala package is imported by default, we can use the shorter name of io.Source.

The Source type is an Iterator[Char]. The Iterator type does what you would expect from Java or other languages in that it has methods called next() and hasNext(). It is also part of the collections library and has most of the other methods that one expects to have on a sequence of values. The only difference is that for an Iterator, the values are consumed as you move through them and not all stored in memory.

Most of the time you don't really want to work with individual characters. The method getLines returns an Iterator[String] that does what the name implies. In this example, we call the map method on the result of getLines and pass it the parsing function we had written above. This would give us an Iterator[Array[Double]], which would be consumed as you go through it. For most applications we would want to be able to go through the data multiple times, hence the call to toArray

What should really jump out to you in this example, in terms of the impact on CS1 instruction, is how consistent the problem solving approach is from the collections to the file handling. The fact that the Source acts just like other collections in terms of the available functionality allows students to begin using files more rapidly than if the code were completely different from anything they had seen before.

Now I can see someone who has taught Java pointing out here that files aren't something completely new because in Java they use Scanner for both standard input and files. There is uniformity there in Scala as well. If I wanted my data to come from standard input, the previous example would have simplified to the following.

val data = Array.fill(numLines)(readLine()).map(parseLine)

This uses the same parseLine function as above, but now works on an Array[String] that we get from combining Array.fill with the basic readLine function that has been used since the first week of class.

case classes are Like Records/Structs

What if my the data in my file wasn't just a bunch of numbers? CS1 needs to include the grouping of heterogeneous data elements together. Early in the semester I do this with the tuple mechanism in Scala. I haven't gone into that in these posts, but tuples are also very handy in CS1, especially if you ever run into functions that need to return more than one value. Around the same time that I cover files, I also cover case classes. Remember that in CS1 I am not intending to teach full object-orientation. I don't want to go into a lot of details about classes and methods. I just want a simple way to group together data in a manner where the elements have meaningful names. In my mind, I want something similar to a struct in C.

One of the examples I frequently do that involves files and case classes is processing of historical weather data. The Oak Ridge National Laboratory has a nice site where you can pull down historical data from across the country. I generally download a file and include a few key fields like min, max, and average temperatures, as well as precipitation. The data also includes other fields for the date and location the data comes from. This data has some fields that are integer values only, some that have decimals, and some that aren't simple numbers. I want my students to create their own type that stores some of these values. Consider what this code might look like in Java.

public class TempData {
  public final int month;
  public final int year;
  public final double precip;
  public final int minTemp;
  public final int maxTemp;
  public final int aveTemp;
  public TempData(int m,int y,double p,int min,int max,int ave) {
    month = m;
    year = y;
    precip = p;
    minTemp = min;
    maxTemp = max;
    aveTemp = ave;
  }
}

I made all the values final so that it is safer to make them public. Had we wanted them private and mutable, this code would get a lot longer with the required getters and setters. In this case I'm really happy with having the type be immutable. I'm just not happy with the amount of code or the fact that I'm definitely going to have to cover constructors for students to be able to write this.

Now compare this to the equivalent case class in Scala.

case class TempData(month:Int,year:Int,precip:Double,minTemp:Int,maxTemp:Int,aveTemp:Int)

Yes, that's it. The syntax for classes in Scala was designed to reduce boiler-plate. The case keyword adds a number of nice things in here as well. The only one that really matters for CS1 is that the arguments to the class all become public vals. Recall that a val is the same as a final variable in Java so we really are creating similar things here. It turns out, the Scala code comes with a lot of bonuses as well because case classes get their own definition of equals and hashCode. They also come with the ability to pattern match, a feature that some instructors could make use of in CS1, depending on how they teach their course.

To help illustrate how this might be used, let's look at code I would write to read in the contents of a data files into this case class and then to calculate the averages for the min, max, and average temperatures across all the data.

case class TempData(month:Int,year:Int,precip:Double,minTemp:Int,maxTemp:Int,aveTemp:Int)

def parseLine(line:String):TempData = {
  val parts = line.split(",")
  TempData(parts(2).toInt,parts(4).toInt,parts(5).toDouble,parts(6).toInt,parts(7).toInt,parts(8).toInt)
}

val source = io.Source.fromFile("temps.csv")
val data = source.getLines.drop(2).map(parseLine).toArray
source.close()
val aveMin = data.map(_.minTemp).sum.toDouble/data.length
val aveMax = data.map(_.maxTemp).sum.toDouble/data.length
val aveAve = data.map(_.aveTemp).sum.toDouble/data.length

The call to drop(2) is in there because the data file starts off with two lines of header information. Everything else should be fairly self-explanitory at this point. As an exercise for the reader, write this in the language you use for CS1 and compare the code length and the difficulty of construction.

GUIs and Graphics Without Explicit Inheritance

I remember when I started college and most students in CS1 would actually be impressed by having written their Hello World program or writing something that counted to ten in a text interface. The standards for what students expect from their computers has changed a lot since then, and as most faculty teaching early CS courses realize, it really helps to have a graphical interface if you want to get students involved. This is why I was very happy when I found that I could get students to write GUIs and even do Java 2D based graphics without them having to know about inheritance.

The first time I taught Scala in CS1 I was still pulling on a lot of my knowledge of Java. In Java, I felt that I really couldn't do GUIs without students understanding inheritance so that they could make subtypes of things like listeners. I really didn't want to cover inheritance during CS1, but both the students and I really wanted to do something graphical. After thinking about it for a while, I realized that using the scala.swing package I would be able to do GUIs easily with no explicit inheritance and using a syntax that I felt students would understand without knowing inheritance.

To illustrate this, here is a short script that brings up a GUI with three elements, a test field, a list, and a button. Text in the text field is added to the list when the user hits enter. Selected items in the list are removed when the button is clicked.

import swing._
import event._
import BorderPanel.Position._

val list = new ListView[String]
val field = new TextField
field.listenTo(field)
field.reactions += {
  case ed:EditDone => 
    if(field.text.nonEmpty) {
      list.listData = list.listData :+ field.text
      field.text = ""
    }
}
val frame = new MainFrame 
frame.title = "Simple GUI"
val bp = new BorderPanel
bp.layout += field -> North
bp.layout += list -> Center
bp.layout += Button("Remove") {
  list.listData = list.listData.diff(list.selection.items)
} -> South
frame.contents = bp
frame.size = new Dimension(300,500)
frame.centerOnScreen
frame.open

This particular solution has no inheritance at all. I show it to make it clear how this can be done, though I have to admit this isn't my normal style. My normal style for this code would use anonymous classes where the inheritance is implicit and code related to many of the GUI elements is nested in those GUI elements.

val list = new ListView[String]
val field = new TextField {
  listenTo(this)
  reactions += {
    case ed:EditDone =>
      if(text.nonEmpty) {
        list.listData = list.listData :+ text
        text = ""
      }
  }
}
val frame = new MainFrame {
  title = "Simple GUI"
  contents = new BorderPanel {
    layout += field -> North
    layout += list -> Center
    layout += Button("Remove") {
      list.listData = list.listData.diff(list.selection.items)
    } -> South
  }
  size = new Dimension(300,500)
  centerOnScreen
}
frame.open

Since students are used to seeing curly braces being used to signify the body on things like function, it isn't a significant cognitive leap for them to see how the curly braces after something like new TextField define a scope and body associated with a text field. Whichever approach you prefer, the bottom line is that you can build GUIs and make them interactive without students understanding inheritance.

This example code hopefully also illustrates again the benefit of Scala's close ties to Java. While there are differences between the details of how things are done in javax.swing and scala.swing, the approaches are similar enough that anyone with a working knowledge of Swing and some knowledge of the Scala syntax can quickly figure out how to make things work.

I also like to have my students use graphics, and here again I stick with Java libraries and use Java 2D. It is possible that at some point I might switch to JavaFX and the wrapper classes in ScalaFX, but since I prefer to work with libraries that are part of the default install, I expect that even if I move to JavaFX, I will use the Java interface.

To get graphics into a GUI I wind up needing to do a little bit of inheritance and I do have to introduce the override keyword. The following code gives a simple demonstration where a dot follows the mouse around on the window.

import java.awt.Graphics2D
import java.awt.Color
import swing._
import event._
import java.awt.geom._

var mx = 0
var my = 0
val panel = new Panel {
  override def paint(g:Graphics2D) {
    g.setPaint(Color.white)
    g.fill(new Rectangle2D.Double(0,0,size.width,size.height))
    g.setPaint(Color.blue)
    g.fill(new Ellipse2D.Double(mx-5,my-5,10,10))
  }
  listenTo(mouse.moves)
  reactions += {
    case mm:MouseMoved =>
      mx = mm.point.x
      my = mm.point.y
      repaint()
  }
  preferredSize = new Dimension(400,400)
}
val frame = new MainFrame {
  title = "Follow the Mouse"
  contents = panel
  centerOnScreen
}
frame.open

It is not too hard to go from this to simple games. The scala.swing package includes a Swing object that makes it easy to create ActionListeners that can be used with a javax.swing.Timer to create regular updates in a game.

Parallelism

This list wouldn't be complete without some mention of parallelism. I hold off on most of my coverage of parallel until CS2, but I like to introduce it in CS1 to get the concept into their heads early. This can be done nicely with parallel collections. You can get a parallel collection from a regular collection with the par method. You might not have many things in CS1 that benefit from being done in parallel, but you can fairly easily demonstrate some of the challenges and why making things immutable is beneficial in a parallel world with the following simple example.

var cnt = 0
for(i <- (1 to 1000000).par) cnt += 1
println(cnt)

Clearly this code should print out one million at the end. Of course, it doesn't because the increments are happening to a mutable value across multiple threads and race conditions are causing some of those operations to be lost. If you happen to have larger problems where they actually take a while to accomplish (something that is fairly challenging on modern processors), you could easily use the parallel collections to enhance the speed of that workload.

This finishes off my list for CS1. A lot of these items are improvements on Java that put Scala more on-par with Python or other scripting languages for the purposes of CS1. In my next post I'll hit on why I like using Scala in CS2. That is where I think that Python falls a little flat.

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.

Why Scala for CS1 and CS2?

+Thomas Lockney pointed me to a Tweet by +martin odersky today with a link to the following blog post: http://teaching.software-carpentry.org/2013/11/28/choosing-scala/. This has prompted me to write a bit about my own experience with teaching CS1 and CS2 using Scala. In this first post I will focus on why we chose Scala and continue to use it. In a second post I will run through what I see as the most significant benefits of Scala, especially in CS1.

I got the Odersky, et al. book and started learning about Scala in 2009 because I was working with students on some projects that involved the experimental X10 and Fortress languages and they both borrowed ideas from Scala. Indeed, the big push for me was that X10 switched from having a Java-based syntax to a Scala-based syntax around version 1.7. Since these experimental languages don't have learning guides, just language specs, I decided that I probably needed to actually learn Scala from a useful book before I tried to tackle X10 in its new form.

I will admit that for the first 200 pages or so I was very skeptical. There were a number of language decisions that simply didn't make sense to me. At that point they seemed ad hoc. However, by the time I was half way through the book I was hooked. I had loved programming in ML a few years prior, but I couldn't do much in it because of the lack of library support. Scala brought me many of the things I loved from ML and the full Java libraries that I had years of experience with. Even then though I was thinking about using it in upper division classes and I recall saying to myself that it couldn't work for introductory courses.

Around this time our department also started evaluating our curriculum to make sure that everything was in order with ACM guidelines and to try to patch issues that we felt existed in how we were doing things. In Fall 2002 we had adopted an approach where we taught CS1 with no OO in C, CS2 with heavy OO in Java, and our Data Structures course using C++. In many ways we were happy with this setup, but there was one glaring issue. The breadth of languages had many benefits, but at the end of the day, students didn't feel comfortable in any single language. For that reason, we wanted to change things so that CS1 and CS2 were taught in one language while Data Structures and a new course on Algorithms were taught in another. It was fairly easy to pick C++ for the 3rd and 4th semesters. (I'm sure there could be endless discussion on that and comments are welcomed, but I'll just say here that it works well for us and we believe it works well for the students.) However, the choice for CS1 and CS2 was more challenging.

We were happy with focusing on logic in the first semester and holding off real OO until the second semester. After all, OO really shines on large projects and CS1 is not about writing long programs. CS1 is about figuring out how to break down problems and construct logic in the formal terms of a programming language. I'm also not a fan of using tools explicitly designed for education in majors courses. Tools like BlueJ, Greenfoot, and DrJava can be great for getting around some of the problem areas of Java early on and we are happy using them for non-majors, but we would rather work with "real" tools with majors.

We also had to consider the requirements of CS2. This isn't just a class about OO. It is also about abstraction and polymorphism. We want students to understand things like inheritance hierarchies and parametric polymorphism (generics/template/type parameters). We think it is nice to throw in things like GUIs, graphics, multithreading, and networking along the way in CS1 and CS2 to allow students to build applications they find more interesting and because we want to make sure those things are seen by everyone, even if they skip one or two of those topics in their upper division courses.

We had pretty much ruled out Java because of the tool issue and the fact that the language just doesn't support programming in the small well on its own. The keyword soup that is "Hello World" in Java wasn't an option for us. In many ways, Python was the early front runner at Trinity, as it has become in many other departments looking to change the early curriculum. Python works wonderfully for CS1 and has a feature set that fits well with what we want to teach in that course. Unfortunately, Python doesn't fit our learning objectives for CS2. The OO isn't very pure, and many of the topics we want to cover really only make sense in a statically typed language.

It was during these discussions about languages that I had my Scala educational epiphany. I realized that many of the things that made Python great for CS1 were also features of Scala. The availability of a REPL and a scripting environment meant that Scala was just as good for writing small programs and testing things out as Python or other scripting languages. Unlike Python though, Scala was even better than Java at handling the OO and related topics in CS2.

What we decided to do was run an informal experiment. For 1.5 years we ran sections using our old approach, Python, and Scala to see if there were any glaring holes. While everyone felt that each style did a reasonable job, there was some anecdotal evidence that students who started in Python had a slightly harder time moving to C/C++ because of little things like having to declare variables and worry about types. This isn't something that would be likely to be seen in final outcomes from the major, but it is the type of thing that can slow the class down the next semester and prevent them from getting quite the same depth or breadth.

In many ways, the decision was made to go with Scala because the primary supporter of Python retired and I didn't. We are now in the first half of the 4th year using Scala and the 2nd full year where all sections are using Scala. In general, I think the decision to go with Scala has served us well. In my next blog post, I will go into the details of how I use Scala in CS1 and the features that I think are most useful for that course.