tag:blogger.com,1999:blog-87045107215940306642024-03-16T00:07:49.924-07:00Dynamics of ProgrammingMarkCLewishttp://www.blogger.com/profile/14261945946844997477noreply@blogger.comBlogger86125tag:blogger.com,1999:blog-8704510721594030664.post-25325862837738191852019-07-21T09:37:00.003-07:002019-07-21T10:19:47.519-07:00One Month Into Driving a Tesla Model 3I have been driving my new Tesla Model 3 to work for about a month now. This blog is intended to give my overall impressions so far. My commute is 20-40 minutes each way depending on traffic and most of it is on highways. I've tried as much as possible to use the AutoPilot feature using different options to see what works best for me. (tl;dr, the Tesla Model 3 is incredible and you should buy one)<br />
<br />
Upfront, let me say that we didn't get a Tesla for me to drive to work. We bought the Tesla for my wife to commute in. She works in a different city and commutes about 250 miles each way once a week plus a 45-minute drive from "her house" to work. The result of all this driving is that our 2014 Prius hit 160,000 miles before the 5-year loan was even paid off. Given the number of miles she is putting on it, the low maintenance costs of an electric car, paired with the fact that the electric motors should last ~1 million miles is really appealing. The fact that most of her miles are US interstate miles led us to believe that Tesla's Autopilot would also go a long way to making her commute more manageable. Due to the complexities of life though, I get to be the primary driver for the first few months.<br />
<h2>
Basics</h2>
If you have read anything about the Model 3, you know that it is a bit different as a car. Having minimalist controls with pretty much everything on a single touch screen really hasn't been a big adjustment for me. The speedometer is a bit to the right instead of center, but that was easy to adjust to. Everything I actually use on a regular basis is still controlled by the two knobs on the steering wheel or the two stalks that are pretty much ubiquitous on modern cars. Turn signals are pretty much normal. Wipers are automatic and a little button on the turn signal stalk will do a quick wipe or spray the front windshield. You switch from park to reverse to drive with the right stalk and also use it to activate cruise control and Autopilot. I can adjust volume and channels with the small control on the left side of the steering wheel. Cruise speed and following distance is altered with the one on the right.<br />
<br />
Honestly, the biggest adjustment in driving is the fact that when you let off the gas pedal it immediately starts regenerative braking. Once you get used to this though, you begin to wonder why every other car isn't this way. I literally only have to hit the brake pedal when I'm coming to a complete stop at a light or stop sign. A huge amount of driving can be done with just one pedal and once you get used to that, driving other cars where you have to use the brake so much becomes annoying.<br />
<br />
Now you might be unhappy that you have to keep pressure on the accelerator and can't coast, but this is easily overcome by the remarkably smooth adaptive cruise control (and Autopilot, but more on that later). My previous experience with adaptive cruise control was not pleasant. It was way too timid and would slow down so early behind other cars that I found it really hard to drive with. Tesla's adaptive cruise control is awesome and the only reason I don't use it much is that I activate Autopilot instead.<br />
<h2>
Control Panel</h2>
<div>
Things I don't use as much are all on the large flat-panel display. This shows my speed, lane tracking, and a little figure indicating where various cars are around me. By default, there is also a navigation map up at all times that uses Google maps. I've gotten into the habit of setting it to navigate to most places that I'm going as soon as I get into the car. The on-screen keyboard might annoy me except that I rarely type more than four characters before the smart predictions list the place that I'm trying to get to.</div>
<div>
<br /></div>
<div>
This panel also has all the other settings that I would want to play with including mirrors, driving options, security, audio, climate control, etc. I have found that the things I go to a lot are easy and quick to access. The first week I went through the options for driving quite a bit, but after that, I found the settings I liked and rarely went into them again.</div>
<div>
<br /></div>
<div>
At first, I was worried about having things like the mirror controls on the central panel. I'm almost a foot taller than my wife, so we do a lot of adjustments when we swap who is driving. My fear was unfounded though as the Tesla recalls the settings for different drivers and everything except the primary rearview mirror goes back to where I want it just by pressing a button that says that I'm the one driving. Most luxury cars have this type of feature and I can't overstate how nice it is if you have different drivers who need seats, mirrors, and even steering wheels in different places.</div>
<div>
<br /></div>
<div>
The bottom line is that while the central panel might seem daunting at first, you quickly set what needs to be set and most of the options don't get altered after that time. Contrast this to most cars where you have buttons and knobs that you have likely never pressed after driving the car for years. Why did they make a whole knob for that anyway?</div>
<h2>
Acceleration</h2>
<div>
I've been a big proponent of autonomous cars since the early DARPA Grand Challenges. When Google first announced its autonomous car project, I was super-excited. This isn't just because I'm a technophile. The main reason is that I have never liked to drive. I know that there are people who say they enjoy driving, but I never understood them. Most driving is boring. There is nothing exciting about my commute to and from work. At least I hope there isn't anything too exciting as that generally implies something very bad when it comes to rush-hour commutes.</div>
<div>
<br /></div>
<div>
Having said this, the Tesla is the first car that I have owned where I think some little parts of the driving experience are fun. This is mainly because of the acceleration. Note that the car we traded in for the Tesla was a Mercedes C300 4matic. It was no slouch in terms of performance, especially compared to the Prius, but honestly, I preferred driving the Prius because of all the other features of the car. The Tesla puts the Mercedes to shame. The thing is, we didn't get the performance version. We just got the long-range upgrade so that my wife could drive 300+ miles on a single charge. We didn't go for the performance upgrade. Despite that fact, the car has serious acceleration. The 0-60 in 4.5 seconds isn't that fast compared to a lot of other Tesla models, but it is still enough to push you back in the seat. More importantly, it will also go from 40-70 on demand when you get on the highway. Our old Mercedes had good acceleration, but there was a noticeable delay between I would put my foot down and when it would really accelerate. In the Tesla, it is automatic and equally effective at whatever speed. Because I'm often watching energy consumption, I try not to drive with a lead foot, but I have to admit that it is fun to shoot off the line every so often.</div>
<div>
<br /></div>
<div>
I also have to point out that because it is electric, it does all of this remarkably quietly.</div>
<h2>
Autopilot</h2>
<div>
There is a certain irony to the fact that the Tesla Model 3 is fun to drive in that my real goal with this car is to not actually drive. As I mentioned above, we bought this car to help with my wife's long commutes and I personally can't wait until robotaxis dominate the road providing transportation as a service. While I wait for the true revolution in transportation to arrive, the Tesla lets me get an early taste.</div>
<div>
<br /></div>
<div>
Our two main upgrades were the long-range and full autonomy. Of course, the current Tesla isn't fully autonomous. Still, it does a really good job on highways. Most of my commute is on highways and when my wife drives between cities it is almost all on high-quality, boring interstate. So a lot of this first month of driving the car has been spent pushing the envelope on Autopilot to see how well it does on my commute and other highway stretches.</div>
<div>
<br /></div>
<div>
Every morning, as soon as I get on the highway, I switch on Autopilot. This is done by pushing down on the right stick twice, something like a double click. At the lowest level, this just activates steering that holds the lane to go along with the great adaptive cruise control that I mentioned above. The result is that the car can drive down a highway with basically no input from the driver.</div>
<div>
<br /></div>
<div>
Of course, the current version of Autopilot isn't designed to drive independently. When you turn it on there is a message telling you to keep your hands on the wheel. In addition, every so often it wants you to apply a little torque to the wheel. When I was first testing this out, that message confused me some because I never took my hands off the wheel, and even if I squeezed tight, it wasn't happy. That's because what it is sensing is the torque, not the pressure. I just have to apply a little turning force. Not too much, because if you really turn the wheel you take back over control and Autopilot goes off, though cruise control will remain on until you tap the break.</div>
<div>
<br /></div>
<div>
For the first week or so I would turn on Autopilot but leave my hands on the wheel. This let me get a feel for what the system is currently good at and what causes it problems. The short version is that Autopilot is a really great driver and I'd feel much safer on the road if every car were using it. Unfortunately, they aren't and it is the poorly behaved human drivers that make it so you can't trust Autopilot completely.</div>
<div>
<br /></div>
<div>
It is worth noting that the three miles of highway closest to my house is a construction zone that has lights. Autopilot still does a great job in this area. I turn it one as soon as I'm heading the right direction in the construction zone in the morning and most days I don't turn it off or take control until I exit the freeway near my destination. In the afternoon I do the same thing in reverse on the way home. The success in the construction zone is largely due to the heavy traffic in the area. Autopilot doesn't do lights, so if I'm ever approaching a red light in Autopilot without a car in front of me, I have to take over. Due to the heavy traffic, I think that has only happened to me once.</div>
<div>
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjfIZd5FnUEMKr7urZMDskzG5TeIomxcaU2s2vXBtj_sFWPdU8sKLPggj6nIQl3iME2x_C7zsFxZJNwFccyLWLgvrlHPiJBxzKHYeeN4UK0lQKOu25T-Jno20ngaPDufhthackac6VyD3X9/s1600/IMG_20190702_194604.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="240" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjfIZd5FnUEMKr7urZMDskzG5TeIomxcaU2s2vXBtj_sFWPdU8sKLPggj6nIQl3iME2x_C7zsFxZJNwFccyLWLgvrlHPiJBxzKHYeeN4UK0lQKOu25T-Jno20ngaPDufhthackac6VyD3X9/s320/IMG_20190702_194604.jpg" width="320" /></a></div>
<div>
<br /></div>
<div>
After the first week, I started testing it without my hands on the wheel. I actually find this to be much more comfortable. As I said before, the sensor that detects if you are touching the wheel isn't based on pressure, it is based on torque. So even when my hands are on the wheel I still get the message telling me to apply pressure to the steering wheel and I have to do something different. With my hands off the wheel, it is just natural to reach up and push on one side when I get that message. I still pay close attention to what is going on around me and I am ready to take over, but my hands can rest on my lap or the console instead of the wheel.</div>
<div>
<br /></div>
<div>
After the third week, I tried turning on the option for Autopilot to automatically change lanes instead of having me verify/motivate lane changes using the turn signal. Unfortunately, the system requires that you apply torque to the wheel every time it does a lane change, so I didn't find this feature to be very useful. I also don't like all the lane change choices it makes, so I've since turned that option off.</div>
<div>
<br /></div>
<div>
It is interesting to note that the main changes I disagree with relate to the Autopilot wanting to move into a faster lane. As I said above, I don't like to drive. When I do drive, I'm a left lane driver because I want to get to my destination and be done with the tedious driving. I'm not a speed demon, but I do get really frustrated with people going slowly in the left lane. With Autopilot I'm a much more relaxed driver. The driving doesn't suck, so I'm not in as much of a hurry to get it over with. I'm okay staying in a lane that is going a few mph below my desired speed and that stop-and-go traffic in the image above doesn't bother me at all.</div>
<h2>
Autopilot Shortcomings</h2>
<div>
The Autopilot system isn't perfect and I do still need to pay attention, especially in heavy traffic. For my route to and from work, I've pretty quickly learned where it is likely to run into trouble. There are some specific locations like one place in the construction zone where the lanes swerve to the left and going straight in the right lane becomes is a right turn lane that I don't want to take. I just make sure I'm in the left lane there and I have no problems. There are places where the lane lines are far apart because lanes are merging or splitting where it often needs to be reassured that I'm paying attention. There is also a spot coming off a ramp where it goes a little further left than I would like. It never leaves my lane, but if there is a large truck in the next lane over it will make me uncomfortable. None of these ever cause me to take over now that I know about them.</div>
<h3>
Merging</h3>
The area where Autopilot struggles the most is merging. This should be no surprise. If you are a young driver or have recently taught a young driver how to drive, you know that changing lanes on highways is often one of the things they find most challenging. For Autopilot there are two sides to this. There is the act of Autopilot changing lanes and there is Autopilot dealing with human drivers changing into the lane I'm in.<br />
<br />
When we first got the car, we went through the settings and made pretty much everything as conservative as possible. I still have those settings for most things so if the car in front of me slows enough that I could even potentially hit it I get a notification. However, I had to change the option for Autopilot merging. On the most conservative setting, it would never actually manage to change lanes in busy traffic, it was simply too timid. Once I realized this, I moved up the aggressiveness every few days and I have it on the "Mad Max" setting where it does a pretty good job but still can't move over in some places in heavy, stop-and-go traffic. Granted, that is in part because human drivers are jerks who don't yield when they see a turn signal. If I really have to get over in heavy traffic, I do occasionally have to take over to make it happen.<br />
<br />
Speaking of human drivers, the biggest challenge for Autopilot is clearly dealing with other cars in merging situations. In normal flowing traffic on the freeway, it is fine. Autopilot maintains a sufficient following distance that people can get in and it does a very good job of slowing and adjusting following distance when that happens. However, in really tight traffic when you have the jerks who are just going to merge over and take off your front bumper, you have to hit the brakes because Autopilot won't notice what they are doing in time. (As I write that I realize that I could be wrong here, it might notice it, but I'm not willing to take the risk so I hit the brakes before it does.)<br />
<br />
When I have to turn off Autopilot, it is basically always due to merging. I'd say that 80% of the time it is because I have to yield more than Autopilot would in order to let someone in. (They need to work on Autopilot's recognition of turn signals.) The other 20% is because I need to get into a lane and Autopilot isn't being aggressive enough. Keep in mind when I say this that most days each week Autopilot completes the freeway part of my commute without me taking over at all.<br />
<h3>
Braking</h3>
One of the other features that you have to play with to get comfortable is adjusting the "following distance". You can do this by pushing the right ball on the steering wheel to the left and right. They say that you are adjusting car lengths and it goes from 1 to 4. Based on my experience, that's not what is happening, but that's a good thing. A one-car follow distance at 70 mph would be stupid. Instead, what it seems to change is how aggressive the car is in terms of braking and how close it gets before it starts braking. Early on I was going between 1 and 3 depending on how heavy traffic was. Now I just leave it at 3 because I find that the 1 and 2 options do more heavy braking than I would like.<br />
<h2>
Driving the Future</h2>
<div>
In summary, I absolutely love my Tesla. There is a certain irony that the first car I've ever really enjoyed driving is one where the biggest selling point is that it drives itself so that I don't have to. Thanks to Autopilot, I find my commute to be far less stressful. The improvement to my quality of life in that regard is significant.</div>
<div>
<br /></div>
<div>
Perhaps the most telling thing I can say is that I've been wanting to take a road trip with the Tesla. In the past, the words "road trip" could cause me to turn and run in the opposite direction as fast as possible, but having seen how well the Tesla does on freeways, I'm pretty certain that I can now do most of the trip sitting back and just watching my surroundings or interacting with the other passengers. Granted, how well this works will depend a lot on where I'd be driving, but a lot of our potential road trips are across stretches of the western US where there are lots of highways and not many people. The one weakness of dealing with merging humans isn't really a problem in low-density traffic. Instead, I'll just get to deal with route planning around charging options in sparsely populated areas.</div>
<div>
<br /></div>
<div>
In conclusion, every time I take the Tesla for a drive, I feel like I'm driving a car from the future. What is most awesome is that between software updates and additional charging stations I expect the experience will only continue to get better.</div>
Mark Lewishttp://www.blogger.com/profile/11308517561967709446noreply@blogger.com1tag:blogger.com,1999:blog-8704510721594030664.post-85924421163880703132019-02-03T12:06:00.000-08:002019-02-03T15:14:28.625-08:00Picking a Language for Introductory CS - Why I don't like Python<h2>
Introduction</h2>
<div>
The purpose of this blog post is to explore issues related to the selection of a first programming language for CS majors. I originally started it with the intention of raising questions related to the rapid adoption of Python that is currently happening in CS departments across the US. However, I decided to make it more general to "score" a variety of different languages. I will generally restrict my comments to languages in the top 15 on RedMonk that I know people have used for introductory programming courses or which I can easily imagine people using for that purpose.<br />
<br /></div>
<h2>
Why It Matters</h2>
<div>
There are many factors that go into why faculty and departments pick a language for CS1. Different departments and educators will weigh them all differently. The thing that I feel really is important to get out of the way is that we don't teach languages for the sake of languages. Instead, languages are a means to tell computers what we want them to do and, in that way, they are a vehicle for us to teach students the fundamental concepts that we really care about. Those concepts tend to carry across languages and time. Languages and technologies are constantly being created/updated and old ones tend to decline in usage as others replace them. These days, software development is a polyglot activity. No single language dominates the development landscape. Even the most popular of languages appear in well under 50% of the job posting for developers, so there isn't some obvious pick that is 100% essential for students to know. Contrast this with version-control systems where git is currently the clear winner. The decision of what language to use is more challenging.<br />
<br />
So what factors should be considered when picking a language for CS1 instruction? My short list for this post is the following:<br />
<ul>
<li>Ability to cover important concepts.</li>
<li>Enforcing good practices so students don't develop bad habits.</li>
<li>Low overhead for small programs.</li>
<li>Ability to solve reasonable problems without introducing too much complexity.</li>
<li>Early error reporting.</li>
<li>Make it easy to learn other languages.</li>
<li>Ability to write things that are interesting in the first semester.</li>
<li>Bonus points: be open, multi-platform, and preferably open source.</li>
</ul>
One thing that I have to point out here is that I'm specifically considering CS1 with the intent that students in CS1 intend to go on to gain a deeper knowledge of programming, software development, and computer science in general. I'm not as interested in the introduction to programming courses that are terminal or specialized for some particular application. Those courses can have very different learning outcomes that vary greatly based on the intended audience. Since I also think there can be advantages to teaching CS1 and CS2 in the same language, I'll occasionally mention things that would more likely be relevant in CS2 than CS1, but for the most part, I will focus on CS1.<br />
<br />
<h2>
Covering Key Concepts</h2>
It is critical to remember that in CS, especially the early classes, what we really want to teach are concepts. Languages are vehicles for that teaching, not the end goal. We aren't trying to teach students about Java, Python, or C++, we are trying to teach them about how to structure logic in formal grammars to solve problems in ways that experience has shown will be scalable and maintainable. Granted, CS1 isn't going to get to the point where scaling to large code bases and maintaining software in teams for years matters, but we are laying the foundation for that.<br />
<br />
There are lots of concepts that any reasonable programming language will do a good job teaching. Things like functions, conditional execution, and iteration are found across all languages of interest. However, there are some other concepts that I think are important to teach early that not all languages are equally successful at.<br />
<br />
<h3>
Types</h3>
<div>
The notion of types is significant in all programming languages, but some languages bring it to the foreground more than others to force students to be aware of it. For the most part, this is a difference between statically typed languages and dynamically typed languages. Statically typed languages make students aware of types right of the bat. Dynamically typed languages require a little coaxing. In addition, topics like subtyping and parametric polymorphism can't really be explained or introduced at all in dynamically typed languages. Depending on when OO concepts are covered, this could be a significant omission.</div>
<br />
The difference can manifest in subtle ways too. Consider the difference in the REPL experience between dynamically typed languages like Python and statically typed languages like Scala. In the Python REPL, executing the expression <span style="font-family: "courier new" , "courier" , monospace;">4+5</span> and the statement <span style="font-family: "courier new" , "courier" , monospace;">print(4+5)</span> produce exactly the same result. In the Scala REPL, they produce very different results, in large part because the Scala REPL shows the types of expressions. So the response to <span style="font-family: "courier new" , "courier" , monospace;">4+5</span> is something like <span style="font-family: "courier new" , "courier" , monospace;">res0: Int = 9</span>. This isn't just based on the typing system in the language, it relates to deeper decisions for those who implement the REPLs. For example, the JavaScript console in Google Chrome produces slightly different output for evaluating an expression and printing, but it doesn't show types by default. The creators of the Java <span class="" style="font-family: "courier new" , "courier" , monospace;">jshell</span> utility also made the decision to not show types, despite being a statically typed language, and <span class="" style="font-family: "courier new" , "courier" , monospace;">jshell</span> also has very different responses to the two commands. The Python REPL is particularly poor here in the decision to not distinguish at all between the two. I say this is particularly poor because I know from years of experience that one of the things students often struggle with is the difference between printing and returning values. It is useful to have a REPL that helps to make the distinction.<br />
<br />
To make this completely clear, consider the following REPL session in Python 3.<br />
<pre>>>> def foo1():
... return 9
...
>>> foo1()
9
>>> def foo2():
... print(9)
...
>>> foo2()
9
</pre>
<br />
Now compare that to the equivalent Scala code.<br />
<pre>scala> def foo1() = 9
foo1: ()Int
scala> foo1()
res0: Int = 9
scala> def foo2() = println(9)
foo2: ()Unit
scala> foo2
9
</pre>
Which one of these do you think is going to help a student understand that there is a difference between returning a value and printing one?<br />
<br />
<h3>
Constants</h3>
<div>
This is one that I find to be significant and which <a href="http://qr.ae/TUNefw" target="_blank">many novices might not understand</a>. Most languages have a way to express that a variable can't change. Part of me wants to say that C++ has the edge here because the use of const is so critical to good C++ programming, but C++ also lacks immutable collections, as do most imperative languages. In that regard, functional languages might be better, but pure functional languages don't let students see non-const values. In that regard, Scala gets high marks as a language where an instructor can really explore the role of mutation.</div>
<div>
<br /></div>
<div>
This is an area where Python completely falls down. Making a value constant in Python is way beyond what you can do with a novice. JavaScript was bad here too until ES6 introduced const.<br />
<br /></div>
<h3>
Scope</h3>
<div>
Speaking of the additions to JavaScript in ES6, I also feel that scope is a significant concept for programming and one that can be challenging for novice programmers to understand. Most of the languages that are commonly used have block scope. The exceptions tend to be scripting languages that were created for writing only small programs and therefore have simplified systems like only having global scope and function scope. The ECMAScript committee realized that this really isn't a good thing for a language being used to develop larger programs, so they introduced let and const basically to replace var. Unfortunately, both Python and PHP still lack block scope. Python also has another very odd behavior for default arguments that is closely related to scoping that I will come back to later.<br />
<br /></div>
<h3>
Private</h3>
<div>
If OO is done early, I would also argue that private is a really important concept to cover. Other visibility options are helpful, but making members private is a big part of what allows OO to simplify life in large code bases because you can hide away certain details and know that certain parts of state can only be modified in a small region of code. In practice, this matters less if everything is made immutable, but in CS1 the goal is teaching concepts and if a language doesn't have a construct for doing something, it makes it a lot harder to teach.<br />
<br />
<br />
This is an area where JavaScript has been bad. One could argue that because it was prototype based, JavaScript has always been something of an odd duck in this regard and that teaching students JavaScript to start with was going to make moving to other languages more challenging in terms of OO. However, the newest additions to JavaScript make it feel more like other class-based OO languages, including the ability to declare private members. Python is still weak here as the only notion of private is by convention. I can imagine the student questions asking if something is so important why doesn't the language take it seriously.<br />
<br /></div>
<h2>
Discourage Bad Habits</h2>
I firmly believe that the choice of a first programming language is critical for another key reason, it is hard to break bad habits and unlearn things. This rule applies to all things, not just programming. I recall my High School physics teacher telling me that about physics. I have also experienced it myself in the area of programming both from my own learning experience and from working with students. I learned to program in line numbered BASIC with <span style="font-family: "courier new" , "courier" , monospace;">GOTO</span> and <span style="font-family: "courier new" , "courier" , monospace;">if</span> as the primary control structures. Even after moving to Pascal and C, then C++ in college, the remnants of the style I adopted from BASIC were still present for many years.<br />
<br />
Many readers will be familiar with the following quote from Edsger Dijkstra.<br />
<blockquote class="tr_bq">
It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration.</blockquote>
It takes a long time to break away from the habits instilled by learning to code in line-numbered BASIC. I saw this up close early in my teaching career when I had a student who had also learned how to code that way. I think it took two years to finally convince him that the style of programming he was used to was not a good one. He missed out on a lot of potential learning because he was stuck in that old style.<br />
<br />
The thing is, this student could defend his style because he was good at that style and as a result, he could make it work. This is challenging to deal with and I certainly don't think that it is unique to this student.<br />
<br /></div>
<h3>
Dynamic Typing</h3>
This is the area where I worry most about students picking up poor habits with modern programming languages. GOTO isn't a problem anymore as many newer languages don't support it, few examples students will stumble across on the web will use it, and because it is a language feature, students can't accidentally start using it without seeing an example. However, abusing types is something that students can easily fall into. Indeed, some languages have major libraries that basically tell students that this is okay.<br />
<br />
The simplest example of this is probably heterogeneous collections. In dynamically typed languages, if a student has an assignment where they have to store multiple names and ages, they could easily set up something like <span style="font-family: "courier new" , "courier" , monospace;">["Pat", 34, "Bob", 40, "Betty", 25]</span>. Even index elements are names and the following odd index is the age. They can easily make this work, and because they can make it work, it can be very hard to convince them that this style of programming by convention leads to brittle code that is hard to maintain and is likely to break.<br />
<br />
The challenge of convincing students that they should do the right thing with types becomes especially challenging if they see examples of what they are doing in libraries that they use in class. One behavior that I find particularly disturbing is when functions in dynamic languages return different types based on the values of the inputs. Unfortunately, this isn't all that uncommon in dynamically typed languages, even though it produces code that is nearly impossible to maintain. One example of this is the <span style="font-family: "courier new" , "courier" , monospace;"><a href="https://pandas.pydata.org/pandas-docs/stable/reference/api/pandas.DataFrame.xs.html" target="_blank">pandas.DataFrame.xs</a></span> method in the Python Pandas library, which is used extensively for data science. Statically typed languages tend to make it very clear that this type of behavior is problematic by making it painful to do if it can be done at all. As a result, students are unlikely to do it by accident and then find ways to "make it work."<br />
<br />
<h3>
Cute Tricks</h3>
Another habit that I don't want to encourage in novice programmers is "cute trick" types of solutions. These are ways of writing things that tend to produce code that can be hard to read and maintain. One example of this that jumps out to me is using short-circuit logic operators for things other than logic in languages that have "truthy" and "falsey" values instead of actual Booleans.<br />
<br />
For example, doing something like <span style="font-family: "courier new" , "courier" , monospace;">result = funcThatIsFalseyOnFailure() || defaultValue</span> instead of using a conditional expression. This type of code hides what is really going on and uses the or operator to do something that clearly isn't just Boolean logic.<br />
<br />
<div>
<h3>
But I can teach it the right way...</h3>
</div>
<div>
I feel that I can already hear some readers saying that they don't need languages to help enforce good style because they will teach students to the do things the right way, and they can enforce approaches that avoid the bad habits. Unfortunately, I think that this ignores how much our students learn from sources other than the classroom. Personally, I think it is good to have students learn from other sources. Our real goal should be to set them up for life-long learning. Learning from other students and other resources should probably be viewed as a positive, but we have to acknowledge that when that happens, it is outside of our control. As such, students are going to see and probably adopt whatever a language allows, even if we don't tell them about it. The more popular the language, the more likely this is to happen.<br />
<br /></div>
<div>
<h2>
Low Overhead for Small Programs</h2>
</div>
<div>
I've seen some debate about this, but personally, I like languages used in introductory programming classes to have low overhead for small programs. This is an area where scripting languages like Python and JavaScript shine while more traditional languages fall down. Java is particularly horrible in this regard as the traditional "Hello World" program involves a large number of keywords that you can't possibly explain to students on the first day of class. I would argue that this is why teaching environments like BlueJ and Greenfoot were created for Java. Note that I love Greenfoot and have used it for teaching non-majors, but I'd really prefer to just use a language where "Hello World" reads something like <span style="font-family: "courier new" , "courier" , monospace;">println("Hello World.")</span>. The only aspect of that which needs explaining is the double quotes for making string literals, and pretty much every programming language is going to have something like that.</div>
<div>
<br /></div>
<div>
I'm also fond of REPLs (Read, Evaluate, Print Loop). Here again, scripting languages shine, though even Java now has jshell. The first day I talk about a language, I like nothing better than to drop the students into a REPL and let them play around. As I mentioned above though, not all REPL experiences are created equal in terms of teaching, some provide more information to help students understand what is going on than others.</div>
<div>
<br /></div>
<div>
I also have to point out that scripting languages aren't the only languages that score well here. Functional languages, both statically typed and dynamically typed varieties, also tend to have both REPLs and support a style that is closer to scripting languages than to languages like Java and C++.<br />
<br /></div>
<h2>
Hold Complexity at Bay</h2>
<div>
Limiting complexity isn't just about the first day and "Hello World". Every practical language is going to have advanced methods and dark corners. Languages that are good for CS1 don't force the instructor to introduce these before they want. The complexities that I refer to here come in a lot of forms and vary by language. Some are "concessions" that the language creators made early on to make a language more practical. Others are advanced features that benefit professional development, but only complicate life for developers. Some are just elements inherent to the programming model for that language.</div>
<div>
<br /></div>
<div>
I would argue that this is another area where Java falls down. One simple example fits in with the last point, every Java application requires at least one usage of the static keyword, but static is really challenging to explain to novice programmers. A slightly more subtle example is the distinction between primitives and object types in Java. The motivation for this in Java is simple, when Java was created, they needed to have primitives to make the language sufficiently performant, so they sacrificed some of the purity of the object model to put in primitive types and enable programs written in Java to run faster. They had learned from Smalltalk that making every value an object was too big of a drag on performance and would seriously hamper adoption. (I have to wonder if this might also have been a factor in the late adoption of Python, which is slightly older than Java, but didn't see broad adoption until many years after Java had become a dominant language and computers had gotten much faster.)</div>
<div>
<br /></div>
<div>
To understand what I mean about the problem with primitives, consider the issue of converting doubles and Strings to ints in Java. These are things that will inevitably come up in CS1. If you aren't doing this in CS1 it's probably because you have either intentionally or subconsciously created examples that avoid this. If you have <span style="font-family: "courier new" , "courier" , monospace;">double x</span> and you need an int, you would use a C-style cast like <span style="font-family: "courier new" , "courier" , monospace;">(int)x</span> to do the conversion. However, if you have <span style="font-family: "courier new" , "courier" , monospace;">String s</span> and you want an int, you need to use <span style="font-family: "courier new" , "courier" , monospace;">Integer.parseInt(s)</span> to do the conversion.</div>
<div>
<br /></div>
<div>
Later in the semester you probably teach students to use Java collections. Then you get to explain why they can't declare a <span style="font-family: "courier new" , "courier" , monospace;">List<int></span> and instead have to do <span style="font-family: "courier new" , "courier" , monospace;">List<Integer></span>. As an instructor, you just have to pray that no student ever tries to create a <span style="font-family: "courier new" , "courier" , monospace;">List<String>[]</span>, or an array of any generic type so you don't have to explain why they can't do that.</div>
<div>
<br /></div>
<div>
The thing is, these are all things that are going to come up in CS1 naturally, and they are going to slow you down if you are an instructor. They also aren't anything more than artifacts of the early history of the language. You can see this in how Scala, which is also a statically typed language that compiles to the JVM, handles these same situations. The conversions to integers are done with <span style="font-family: "courier new" , "courier" , monospace;">x.toInt</span> and <span style="font-family: "courier new" , "courier" , monospace;">s.toInt</span>. For some reason, I never have any trouble explaining that to students. If a student chooses to make an <span style="font-family: "courier new" , "courier" , monospace;">Array[List[Int]]</span> there isn't a problem either. Interestingly, Scala can do this without sacrificing speed either. The reason is that Scala's compiler is smarter and it compiles thing to primitives whenever it can, but that is an implementation detail that never comes up in CS1 or CS2 and would only matter if you get to the point where you are trying to do high-performance computing.</div>
<div>
<br /></div>
<div>
I feel that C++ also falls down in the area of exposing complexities early, but mostly in the area of the memory model and memory handling. You really can't push C++ all that far before you are going to have to start discussing references, pointers, and memory handling. These are all things that students really need to learn and understand before they graduate, but personally, I don't want to have them take time out of my CS1 course.<br />
<br /></div>
<div>
<h2>
Early Error Reporting</h2>
<div>
One of the fundamental rules in education is that early feedback is good. It is true for software development as well, whether you are talking about finding out if a change needs to be made to the product you are building or just an error in the code. The earlier you find out about things, the less it costs to deal with it. I believe that the same applies to how students find out about errors. Students benefit from error messages that they get early as opposed to finding out that something is wrong later on.<br />
<br />
One of the things I like to discuss in CS1 is different types of errors. I tell them about the hierarchy of syntax, runtime, and logic errors. I point out how syntax errors are generally preferred because they get nice error messages telling them what and where the problem is while logic errors are the worst because they get very little assistance in finding those errors. As a developer, I really prefer languages and programming styles that turn as many errors as possible into syntax errors and produce as few logic errors as possible.<br />
<br />
This is another place where dynamically typed languages, like JavaScript and Python, score poorly. Both produce very few syntax errors. Most of the errors that students are going to see will be runtime or logic errors that won't pop up until they run the code and use inputs that cause the offending path to be executed. JavaScript is particularly bad about trying to get things to work so you don't even get many runtime errors and lots of mistakes become logic errors.<br />
<br />
In professional environments, developers deal with this by building up a suite of unit tests. While testing is something that I talk about in CS1, if I have to cover testable code and a unit testing framework to help my students do proper development in a language, then the lack of syntax errors becomes something that introduces extra unnecessary complexity early.<br />
<br /></div>
<h2>
Ease of Learning Other Languages</h2>
<div>
Back in the mid-1990s, before Java had gained momentum, the question of what language a fresh grad was going to use in their first job was as simple as C or C++. At the time, C++ hadn't diverged nearly as much from C as it had today, so a department could easily give students a deep coverage of all the languages they were likely to use in their first job. Even with the rise of Java, a 4-year degree could be structured to introduce students to every language in significant usage.<br />
<br />
When I look at the <a href="https://redmonk.com/sogrady/2018/08/10/language-rankings-6-18/" target="_blank">most recent RedMonk language ranking</a> I feel like my students could easily use almost any of the top 20 languages in their first job. Indeed, I have graduates working with languages well below the top 20 in their jobs. When it comes to programming, we now live in a polyglot world. We shouldn't even be trying to teach students every language they might use in their first few jobs because there are too many possibilities. Instead, we need to strive to lay a foundation where students learn a diverse set of languages that will enable them to pick up new languages quickly. Personally, I think it would be helpful if the language they learn in CS1 makes it easier for them to pick up the other languages they are going to exposed to in your program instead of harder. If the instructors in later courses are able to draw parallels between languages features in the language used in CS1 and the next few languages students learn, this can definitely facilitate learning.<br />
<br />
So what are the properties of a language that can help students move to other languages? As far as I know, there haven't been any rigorous studies done on this topic. While that is unfortunate, I completely understand why it is the case. Large-scale educational experiments are challenging to do well and are influenced by a lot of different variables. Creating a study where language feature influence was larger than the noise would be very challenging. As such, I'm just going to throw out some ideas.<br />
<br />
I feel that a language that leads well into other languages is one that isn't too odd in either syntax or semantics so that students can move to a variety of other languages and paradigms without being surprised by the new language. Let's start with the easy part of this, use a language that isn't too syntactically different from the ones they will learn next. Most people would likely agree that you shouldn't start in <a href="https://en.wikipedia.org/wiki/APL_(programming_language)" target="_blank">APL</a> or <a href="https://en.wikipedia.org/wiki/J_(programming_language)" target="_blank">J</a>. I see this as an argument against Scheme/Racket as well. (I have to point out that every language will have strikes against it, and what matters is the total weight of pros and cons. For me, the dynamic typing of Scheme/Racket is a bigger killer than the syntax for the reasons listed above, but everyone places different weights on these things and there are certainly some big positives for Scheme/Racket.)<br />
<br />
I'd even go further and argue that if a language has too many control structures that aren't seen in other places, that could be a problem as well. For example, Python supports an <span style="font-family: "courier new" , "courier" , monospace;">else</span> clause on loops that you won't see in other languages. The use of Boolean operators as shortcuts that I mentioned above could be seen as a fail here as well.<br />
<br />
On the semantic side, I think that scope is again significant. I have been told by a TA from Rice University that when students get to Java in their third semester, after having two semesters of Python, that many find block scope to be confusing. Outside of Python, PHP, and Ruby, block scope is the standard rule, and given that scope is something beginning students struggle with, having a first language that handles it differently than most others seems problematic to me for future growth. Python also has very unusual handling of default parameters to functions. Consider the following code.<br />
<div>
<br />
<pre>>>> def foo(a, b=[]):
... b.append(a)
... return b
...
>>> foo(3)
[3]
>>> foo(4)
[3, 4]
</pre>
</div>
<br />
While the scope of <span style="font-family: "courier new" , "courier" , monospace;">b</span> is only inside of <span style="font-family: "courier new" , "courier" , monospace;">foo</span>, its memory is allocated at the same level as the declaration of <span style="font-family: "courier new" , "courier" , monospace;">foo</span> and it is remembered from one invocation to the next. I have yet to find another language that has this semantics for default values to functions.<br />
<br />
Again on the semantic side, languages that have very different models of OO from the "norm" is also a red flag for me. JavaScript recently gained classes, but the OO model in JavaScript is still prototype based and very different from every other language in significant use today. Python also has odd elements to its OO model, like the need to list self as the first argument for methods. I can see how some might see this as a nice advantage for teaching showing how the object is available, but when the student moves to another language, it is yet one more thing to handle differently.<br />
<br />
Lastly, I feel very strongly that before graduating, students should be exposed to multiple paradigms of programming. If a major never covers anything other than the OO-Imperative style of Java and C++, they will find it much harder to pick up other languages later that either aren't object-oriented or that focus on functional instead of imperative. For this reason, I actually like the idea of multi-paradigm languages for CS1 and CS2. Of course, one has to keep in mind that multi-paradigm can break a lot of the other things we are looking for if it makes things more complex.<br />
<br /></div>
<h2>
Interesting First Semester Assignments</h2>
<div>
One of the reasons that Java took off in the education space was the relative ease with which students would write graphical code, especially using Applets. The Applets have long since died, but the ability to put interesting assignments into CS1 and CS2 is still very strong. Interesting here can mean many things and goes well beyond graphics today to include things like playing with data, robotics, or socially relevant problems. Regardless of the details, a general requirement is that you have strong library support, and hopefully ways of bringing in those libraries that doesn't overly complicate things. This is an area where JVM languages and Python excel. Really low-level languages, like C, tend to fall down the most here because the amount of code that is required to do anything interesting is often quite large.<br />
<br /></div>
<h2>
Other Factors</h2>
<div>
There are a number of other factors that impact my thoughts on picking a language for introductory programming. I personally also appreciate languages that run on multiple platforms and are hopefully open source. Those languages generally are better for allowing students to work on their own machines, regardless of their OS, and have tooling that is free of cost. I also really like a language that works well for both CS1 and CS2. I discuss that in more depth in an <a href="http://dynamicsofprogramming.blogspot.com/2013/11/why-scala-for-cs1-and-cs2.html" target="_blank">earlier post</a>.</div>
<div>
<br /></div>
<div>
I also like to use a language and accompanying tools that are used professionally. It doesn't have to be a top 5 language. I'm fine with top 20 because the reality is that no single language dominates today, so whatever language you pick, the ability to learn other languages is more significant than knowing a specific language. The thing is, I'm not all that big on teaching languages and teaching environments in courses for CS majors. The reason is pretty simple, I only have students for 4 years and a limited number of hours and since I want to use the same language for CS1 and CS2, I don't feel comfortable spending that much time teaching something that I know isn't used anywhere outside of the classroom.</div>
<div>
<br /></div>
<div>
We also have to realize that the languages used in industy aren't fixed and what we choose to teach in colleges has an impact on them. One of the things people consider when they pick the language for a new project is whether they can hire enough developers of sufficient talent who know it. The more colleges that teach a language, the more likely it is to be adopted in industry. I'm quite certain that the broad adoption of Java in colleges played a major factor in its dominance in industry. Similarly, the current growth in Python is inevitably fuelling its professional adoption. So when you pick a language to teach, you might ask yourself, "Is this the language I want the software that runs my life to be written in?" If you don't think you want your bank or the elevator you ride in using that language, perhaps you should pick a different one.</div>
<div>
<br /></div>
<h2>
Why People Choose Python</h2>
The language that seems to be taking over early CS education right now is Python. That is actually what prompted me to write this post because I worry about this particular choice for introductory language. There is no doubt that Python has some real advantages in the fact that it has low overhead in CS1 and that there is broad library support to enable students to do interesting things. Unfortunately, it falls down in other areas. The ones I worry most about are an inability to cover certain topics that I consider significant and the possibility for students to pick up bad habits that the language doesn't prevent.<br />
<br />
Perhaps the most standard argument that I hear for Python is that it is "simple" and easy for students to learn. While I completely agree that Python is an easy language for experienced programmers to pick up, it isn't at all clear that being easy for experienced programmers to learn is the same as being easy for beginning developers to learn. Learning to program isn't just about syntax. It is about learning a new way of thinking, how to structure logic, and the general semantics of that syntax. Having a language that enforces more structure and which <a href="https://www.quora.com/Can-you-give-a-concrete-example-of-a-bug-that-would-have-been-caught-in-a-statically-typed-language-like-Java-or-C-but-would-not-have-in-a-dynamically-typed-language-like-Python/answer/Victor-Volkov-3" target="_blank">gives early feedback when rules are broken</a> could actually be very useful for novices. Some evidence for this was provided by <span id="goog_1615359934"></span><span id="goog_1615359935"></span><a href="https://dl.acm.org/citation.cfm?id=3160586" target="_blank">Alzhrhani et al. (2018)</a> who found that students in a large data sample struggle more with Python than they do with C++. Indeed, I would argue that moving from a language that provides more error checking to one that provides less error checking is generally easier than going the other way, and that more assistance from the language to write good code is especially beneficial for the novice. Having a language that helps the student to build their mental model of the semantics of programming could actually be more significant than having a simple syntax.<br />
<br />
I feel compelled to mention that another common argument for Python is that it teaches indentation. There is definitely truth to this, but I can't say I find this very motivating, especially since Python lacks the block scope that the indented blocks indicate. The reality is that auto-formatting tools for languages without significant whitespace are well developed and companies with strict style guides can easily have them enforced by software. In contrast to this, automatically cleaning up poor type usage in programs written for dynamically typed languages is a far more complex problem.<br />
<br />
In some ways, the true challenge of teaching introductory programming using Python is probably summed up well by terms frequently seen in discussions of Python programs. It doesn't take much reading on Python to come across the term "Pythonic". When I asked a Python programmer about functions that return different types based on the argument values, like <span style="font-family: "courier new" , "courier" , monospace;">xs</span> on Pandas' Datasets, I was told that was un-Pythonic. The problem is that Pythonic and un-Pythonic are advanced concepts. When you are dealing with students who are still trying to understand the basics of conditionals, iterations, and functions, they simply aren't prepared to comprehend "Pythonic". Instead of having good coding done by convention, those students need a language that does more to enforce good style.<br />
<br />
<h2>
My Choice for CS1 and CS2</h2>
</div>
<div>
If you've gotten this far, you have already shown great perseverance in our current age of short attention spans. You might be wondering what language I would pick for teaching CS1 and CS2. I actually like Scala as the language for these courses. We've been using Scala in this role at <a href="http://www.trinity.edu/" target="_blank">Trinity University</a> for almost 10 years now, and I have very few complaints. As I've said before in this post, no language is perfect, but I find that the pros for Scala definitely outweigh the cons. I have some older blog posts (<a href="http://dynamicsofprogramming.blogspot.com/2013/11/benefits-of-scala-in-cs1.html" target="_blank">here</a> and <a href="http://dynamicsofprogramming.blogspot.com/2013/12/more-benefits-of-scala-in-cs1.html" target="_blank">here</a>) where I discuss this in more detail as part of my thoughts from the first ~5 years of using Scala. I'll just list some of the highlights here.<br />
<br />
<ul>
<li>REPL and Scripting interface for CS1.</li>
<li>Static type checking and lots of syntax errors instead of runtime errors or logic errors.</li>
<ul>
<li>Type errors prevent a lot of issues.</li>
<li>CS1 students should never see a NullPointerException.</li>
</ul>
<li>Syntax/semantics allow coverage of things I care about including const/mutability, block scope, OO, subtyping, parametric types, etc.</li>
<li>Access to the full JVM for libraries.</li>
<li>Expressive syntax that combined with libraries that allow me to give interesting assignments that don't take thousands of lines to code.</li>
<li>Solid APIs that include links to the types for arguments and return values.</li>
<ul>
<li>In CS2 I can cover multithreading and networking.</li>
</ul>
<li>I can cover CS1 and CS2 topics without the language forcing me to talk about things I'm not ready to cover yet.</li>
<li>Uniform OO syntax without primitives.</li>
<li>Fairly standard OO model.</li>
<li>Multiparadigm so students have a nice path to C++, Haskell, Java, etc.</li>
</ul>
<br />
<br /></div>
<div>
<br /></div>
Mark Lewishttp://www.blogger.com/profile/11308517561967709446noreply@blogger.com2tag:blogger.com,1999:blog-8704510721594030664.post-34922196674281859582018-10-20T16:43:00.000-07:002018-10-20T16:43:08.829-07:00Scala Numerical Performance with Scala Native and GraalThis post is a follow-on to my <a href="http://dynamicsofprogramming.blogspot.com/2017/01/performance-of-n-body-simulation-styles.html" target="">earlier post</a> looking at the performance of different approaches to writing an n-body simulation using Scala. That post focused on the style of Scala code used and how that impacted the performance. This post uses that same code, so you should refer to it to see what the different types of simulations are doing.<br />
<h3>
<br /></h3>
<h3>
Comparing Runtimes</h3>
<div>
For someone who is interested in doing numerical simulations, Scala and the JVM might seem like odd choices, but the benefits of having a good language that is highly expressive and maintainable can be significant, even for numerical work. In addition to the impact of programming style and the optimizations done by the compiler that produces JVM bytecode, performance can also be significantly impacted by the choice of runtime environment.<br />
<br />
Historically, there wasn't much in the way of choice. Sun, then later Oracle, made the only JVM that was in even reasonably broad usage, and enough effort was put into making the hotspot optimizer work that it was generally a good choice. Today, however, there are a few more options. If you are running Linux, odds are good that you have OpenJDK by default and would have to specifically download and install the Oracle version if you want it. In addition, Oracle has recently been working on Graal, a new virtual environment for both JVM and non-JVM languages. Part of the argument for Graal was that the old C2 hotspot compiler, written in C++, had simply because too brittle and it was hard to add new optimizations. Graal is being built fresh from the ground up using Java, and many new types of analysis are included in it. While I have seen benchmarks indicating the Graal, though young, is already a faster option for many Scala workloads, I wasn't certain if that would be the case for numerical work. This is at least in part due to the fact that one of the Graal talks this last summer at Scala Days mentioned that Graal was not yet emitting SIMD instructions for numerical computations.<br />
<br />
In addition, the newest addition to the list of supported environments for Scala is Scala Native. This project uses LLVM to compile Scala source to native executables. One of the main motivators for this right now is using Scala for batch processing because native executables don't suffer from the startup times of bringing up the JVM. This project is still in beta, but I wanted to see if it might be able to produce executables with good numerical performance as well.<br />
<br />
For these benchmarks, the Scala code was compiled with -opt:_ and run on each JVM with no additional options. I am using a different machine from my earlier post, which explains the significant runtime differences between this post and the earlier one using a similar JVM. The following table gives timing results for the five approaches using the five different runtimes.</div>
<br />
<div>
<table border="1">
<thead>
<tr><th>Environment</th><th>Style</th><th>Average Time [s]</th><th>Stdev [s]</th></tr>
</thead>
<tbody>
<tr><td rowspan="5">Oracle JDK 8-191</td><td>Value Class</td><td>0.394</td><td>0.012</td>
</tr>
<tr><td>Mutable Class</td><td>0.683</td><td>0.015</td>
</tr>
<tr><td>Immutable Class</td><td>0.809</td><td>0.010</td>
</tr>
<tr><td>Functional 1</td><td>4.246</td><td>0.439</td>
</tr>
<tr><td>Functional 2</td><td>1.723</td><td>0.027</td>
</tr>
<tr><td rowspan="5">Oracle JDK 11</td><td>Value Class</td><td>0.378</td><td>0.006</td>
</tr>
<tr><td>Mutable Class</td><td>0.690</td><td>0.012</td>
</tr>
<tr><td>Immutable Class</td><td>0.940</td><td>0.083</td>
</tr>
<tr><td>Functional 1</td><td>4.420</td><td>0.059</td>
</tr>
<tr><td>Functional 2</td><td>1.589</td><td>0.021</td>
</tr>
<tr><td rowspan="5">OpenJDK 10</td><td>Value Class</td><td>0.388</td><td>0.008</td>
</tr>
<tr><td>Mutable Class</td><td>0.715</td><td>0.006</td>
</tr>
<tr><td>Immutable Class</td><td>0.892</td><td>0.013</td>
</tr>
<tr><td>Functional 1</td><td>4.405</td><td>0.039</td>
</tr>
<tr><td>Functional 2</td><td>1.689</td><td>0.013</td>
</tr>
<tr><td rowspan="5">GraalVM 1.0.0-rc7, Java 1.8</td><td>Value Class</td><td>0.377</td><td>0.003</td>
</tr>
<tr><td>Mutable Class</td><td>0.396</td><td>0.003</td>
</tr>
<tr><td>Immutable Class</td><td>0.694</td><td>0.108</td>
</tr>
<tr><td>Functional 1</td><td>4.054</td><td>0.151</td>
</tr>
<tr><td>Functional 2</td><td>0.793</td><td>0.016</td>
</tr>
<tr><td rowspan="5">Scala Native 0.3.8</td><td>Value Class</td><td>2.603</td><td>0.185</td>
</tr>
<tr><td>Mutable Class</td><td>1.028</td><td>0.020</td>
</tr>
<tr><td>Immutable Class</td><td>2.595</td><td>0.020</td>
</tr>
<tr><td>Functional 1</td><td>16.84</td><td>1.39</td>
</tr>
<tr><td>Functional 2</td><td>5.232</td><td>0.655</td>
</tr>
</tbody>
</table>
</div>
<br />
<div>
Looking at the first three runtimes, we notice that there is very little difference between Oracle and OpenJDK over various Java versions from 8 to 11. In all three, the value class approach is fastest by far followed by the version with the mutable classes, then the immutable classes with functional approaches being slowest by a fair margin.<br />
<br />
Things get more interesting when we look at Graal. The performance of the value class version is roughly the same as for the other JVMs, but every other version runs significantly faster under Graal than in the others. The ordering stays the same as to which approaches are fastest, but the magnitude of how much slower each version is than the value class version changes dramatically. Under Graal, the mutable class version is almost as fast as the value class version instead of being almost a factor of two slower. Most impressive is that the second functional version is only a factor of two slower than the value class version instead of being four times slower. This is significant for two reasons. One is that it is the version written in the most idiomatic Scala style. The other is that this version literally does twice as much work in terms of distance calculations as the other versions. That means that we really can't expect it to do any better than being 2x as slow. The fact that it takes nearly twice as long to run means that using Graal there isn't a significant overhead to the functional approach the way there is using the older JVMs.<br />
<br />
At the end of the table, we have the results for Scala Native. Unfortunately, it is clear that Scala Native is not yet ready for running with performance-critical numerical code. One result that stands out is that the value class version is not the fastest. Indeed, it runs at a speed roughly equal to the immutable class and 2.5x slower than the mutable class. I assume that this means that the value class optimizations have not yet been implemented in Scala Native. As to why even the mutable class version is more than 2x slower than Graal and at least 50% slower than the other VMs is a bit puzzling to me as I did the timing using a release build. I expect that this is something that will improve over time. Scala Native is still in the very early stages, and there is a lot of room for the project to grow.<br />
<h3>
<br /></h3>
<h3>
Comparison to C++</h3>
As before, I also ran a test comparing these Scala results to C++ code compiled with the GNU compiler using the -Ofast flag. This uses a simpler test with the value class technique. You can see in the table below that the Scala code is performing about 15% slower than C++ in all of the environments except Scala Native, which is several times slower. Given the results above indicating that Scala Native isn't nicely optimizing value classes yet, this result for Scala Native isn't surprising.<br />
<br /></div>
<div>
<table border="1">
<thead>
<tr><th>Environment</th><th>Average Time [s]</th></tr>
</thead>
<tbody>
<tr><td>g++</td><td>3.29</td></tr>
<tr><td>Oracle JDK 8-191</td><td>3.88</td></tr>
<tr><td>Oracle JDK 11</td><td>3.77</td></tr>
<tr><td>OpenJDK 10</td><td>3.82</td></tr>
<tr><td>GraalVM 1.0.0-rc7</td><td>3.82</td></tr>
<tr><td>Scala Native</td><td>21.6</td></tr>
</tbody>
</table>
</div>
<h3>
<br /></h3>
<h3>
Conclusions</h3>
<div>
For me, there are two main takeaway messages from this. The first is that while Scala Native holds the longterm potential to give Scala a higher performance platform for running computationally intensive jobs, it isn't there yet. A lot more work needs to go into optimization to get it to reach its potential of competing with other natively compiled languages. I firmly believe that it can get there and is moving in that direction, but it isn't ready yet.<br />
<br />
On the other hand, these results indicate to me that if you are programming Scala, you should strongly consider using Graal, even if you are doing numeric work. Based on presentations at Scala Days 2018 in New York, I know that this is the case for non-numeric codes, but at the time Graal wasn't emitting SIMD instructions, so it wasn't clear if it would compare well to the old C2 hot-spot optimizer. These results show that regardless of style, Graal is at least as performant as the other JVM options and that in some cases it is much faster. Perhaps most significantly, the functional 2 style, which is written in a much more idiomatic style for Scala, is more than 2x as fast with Graal was with the other JVMs. I should also note that Graal still allows me to run graphical applications like my <a href="https://github.com/MarkCLewis/SwiftVis2" target="_blank">SwifVis2 plotting package</a>, so there isn't any loss of overall functionality.<br />
<br />
Going forward, I want to test the performance of more complex n-body simulations using trees and also look at multithreaded performance to see how Graal compares for those. Scala Native is still only single threaded for pure Scala code, so it will likely be left out of those tests.<br />
<br />
GraalVM native images are another feature that I would really like to explore, but there are some challenges in building them from Scala code that I did take the time to overcome for this post.</div>
Mark Lewishttp://www.blogger.com/profile/11308517561967709446noreply@blogger.com0tag:blogger.com,1999:blog-8704510721594030664.post-49829124887803011742018-08-06T19:51:00.005-07:002018-08-07T07:24:17.046-07:00Why is JavaFX so slow? SwiftVis2 and Speed Problems with JavaFX 2D CanvasFor the last year or so I've been working on a plotting package called <a href="https://github.com/MarkCLewis/SwiftVis2" target="_blank">SwiftVis2</a>. There are a number of goals to this project, but a big one is to provide a solid plotting package for Scala that can be used with Spark projects in Scala and which can draw plots with a large number of points. My own personal use case for this is plotting ring simulations often involving millions of particles, each of which is a point in a scatter chart. The figure below shows an example of this made with SwiftVis2 using the Swing/Java2D renderer with 8.9 million particles.<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiTIMdDFa32zOrmVhky_xGfCP9e4dVqFPcc1DnEZoo2VOmVdLaqyc-nxYVvG3lI8kmXndOo_Jpps0_a8RWudKkf9ThPMiFOuXaOWv54xnk7nNP5_GFgZsJS2wuLl4Sy7CMHYqdsVXr60MY6/s1600/Java2DvsJavaFX.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" data-original-height="1221" data-original-width="1600" height="488" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiTIMdDFa32zOrmVhky_xGfCP9e4dVqFPcc1DnEZoo2VOmVdLaqyc-nxYVvG3lI8kmXndOo_Jpps0_a8RWudKkf9ThPMiFOuXaOWv54xnk7nNP5_GFgZsJS2wuLl4Sy7CMHYqdsVXr60MY6/s640/Java2DvsJavaFX.png" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">SwiftVis2 plot of ring simulation using Swing renderer.</td></tr>
</tbody></table>
<br />
This particular use case pretty much precludes a lot of browser-based plotting libraries that seem to be popular these days as converting 8.9 million data points to JSON for plotting in JavaScript simply isn't a feasible thing to do for both memory and speed reasons.<br />
<br />
As the name SwiftVis2 implies, there is an earlier <a href="http://www.cs.trinity.edu/~mlewis/SwiftVis/" target="_blank">SwiftVis</a> plotting program. It is a GUI based program written in Java. One of the things that excited me about the upgrade was the ability to use JavaFX instead of Java2D. My understanding is that one of the main reasons for building JavaFX new from the ground up was to take better advantage of graphics cards, and I was really hoping that a JavaFX based rendering engine would outperform one based on the older Java2D library.<br />
<br />
I didn't really test this until I was writing up a paper on SwiftVis2 for <a href="https://americancse.org/events/csce2018" target="_blank">CSCE'18</a> and I did performance tests against some other plotting packages. In particular, I compared to <a href="https://github.com/scalanlp/breeze/tree/master/viz" target="_blank">Breeze-Viz</a>, which is a Scala wrapper for <a href="http://www.jfree.org/jfreechart/" target="_blank">JFreeChart</a>. JFreeChart uses Swing and Java2D, so I was really hoping that SwiftVis2 would be faster. At the time, I only had a renderer that used JavaFX in SwiftVis2, and I was really disappointed when Breeze-Viz turned out to run roughly twice as fast on a plot like the one above. Tests of <a href="https://pityka.github.io/nspl/" target="_blank">NSLP</a>, a different Scala plotting package using Swing/Java2D, showed that it also ran at roughly twice the speed of SwiftVis2 using JavaFX.<br />
<br />
Some searching on the internet showed me that there were known issues with drawing too many elements at once on a JavaFX canvas because of the queuing. So I enhanced my renderer to batch the drawing. This has a nice side effect that users can see the plot draw incrementally, so they know their program isn't frozen, but it didn't help the overall speed at all.<br />
<br />
Since SwifVis2 was written to allow multiple types of renderers, I went ahead and wrote a Swing renderer that uses Java2D, just to see what the performance was like. The results, shown in the following table, were pretty astounding to me. Note that these times were for drawing plots like the one above. It is also worth noting that upgrading my graphics driver improves the performance for JavaFX more than it did for the Swing based libraries, but even with new drivers, JavaFX is still slower.<br />
<br />
<br />
<table style="border: 1px solid black; width: 100%;">
<thead>
<tr><th style="background-color: lightblue;">Package</th><th style="background-color: lightblue;">Render Time for 8.9 million Points</th></tr>
</thead>
<tbody>
<tr><td style="background-color: darkblue;">Breeze-Viz</td><td style="background-color: darkblue;">80 secs</td></tr>
<tr><td style="background-color: darkblue;">SwiftVis2 with JavaFX</td><td style="background-color: darkblue;">108 secs</td></tr>
<tr><td style="background-color: darkblue;">SwiftVis2 with Swing/Java2D</td><td style="background-color: darkblue;">13 secs</td></tr>
</tbody>
</table>
<br />
Keep in mind here that the two SwiftVis2 options are running the exact same code for everything except the final drawing as the only difference is which subclass of my Renderer trait is being used. While I do feel a certain amount of happiness in the fact that SwiftVis2 using Swing is significantly faster than the Breeze-Viz wrapper for JFreeChart, I'm still astounded that JavaFX is nearly 10x slower than Swing/Java2D.<br />
<br />
Not only is JavaFX slower, it does an inferior job of antialiasing when drawing circles that are sub-pixel in size. The following figure shows the plot created using the same data and the JavaFX renderer. The higher saturation is obvious. The rendering with Swing/Java2D is the more accurate of the two.<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjwOJjn-6toI-_iS6xVGBLed9X4yKKgFAEQgkCN0KHWiy9e4hHVmXF6rL2hYVx3Xoo71YAFFzSuPubrhkZ54vd-NNq-iIRCl4IGRR35GCmOyDNCXhU6cY3j28JjfWRc-E9lJhZ4JtO_dgXj/s1600/SwiftVis2-JavaFX.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" data-original-height="1267" data-original-width="1600" height="506" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjwOJjn-6toI-_iS6xVGBLed9X4yKKgFAEQgkCN0KHWiy9e4hHVmXF6rL2hYVx3Xoo71YAFFzSuPubrhkZ54vd-NNq-iIRCl4IGRR35GCmOyDNCXhU6cY3j28JjfWRc-E9lJhZ4JtO_dgXj/s640/SwiftVis2-JavaFX.png" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Ring simulation plot made using the JavaFX renderer. Note that the points are sub-pixel and this renderer over-saturates the drawing.</td></tr>
</tbody></table>
To me, this seems like a serious failing on the part of JavaFX. JavaFX is actually harder to use than Swing, and I always forgave that based on the assumption that special handling was needed to work with the GPU, but that the tradeoff would be significantly improved performance. I can only hope that whatever ails JavaFX in this regard can be fixed and that at some point in the future, JavaFX rendering can match the performance promise that comes with completely rebuilding a GUI/graphics library from the ground up.<br />
<br />
Also, in case anyone is wondering why I'm bothering to create yet another plotting package, I will note that SwiftVis2 looks significantly better than JFreeChart, especially in the default behavior. For comparison, the figure below shows the output of the most basic invocation of Breeze-Viz for this plot, which is comparable to the above plots for SwiftVis2. Even if the range on the y-axis is adjusted, it still generally doesn't look as good as the SwiftVis2 output, especially in regards to axis labels. This is the reason I never really got into using JFreeChart in the past. SwiftVis2 is still in the early stages of development, but it already does a better job with my primary use cases.<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhi3QGQtnAfuuj7qsmWEt-uWTjnZWXpanHRABmKq2JeXx8pAxQF8Hyom9SMRL1_1G9k5Ed6FPeQS0HFUJpoFej5jQTv5U9U3SQOiQsEq4QP3CGcUyjSJi995Fbr43qa6d5FUPpnUKf7wEKw/s1600/Breeze-Viz.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" data-original-height="1221" data-original-width="1600" height="488" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhi3QGQtnAfuuj7qsmWEt-uWTjnZWXpanHRABmKq2JeXx8pAxQF8Hyom9SMRL1_1G9k5Ed6FPeQS0HFUJpoFej5jQTv5U9U3SQOiQsEq4QP3CGcUyjSJi995Fbr43qa6d5FUPpnUKf7wEKw/s640/Breeze-Viz.png" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">This is the same figure as those above made with default settings using Breeze-Viz instead of SwiftVis2.</td></tr>
</tbody></table>
You can find the code for my basic performance tests <a href="https://github.com/MarkCLewis/WorldCongress2018/tree/master/PerformanceTesting" target="_blank">on GitHub</a>. The data file is not on GitHub because it is rather large. You can find a copy of it on <a href="http://www.cs.trinity.edu/~mlewis/pub/CartAndRad.88840.bin" target="_blank">my web space</a>.Mark Lewishttp://www.blogger.com/profile/11308517561967709446noreply@blogger.com0tag:blogger.com,1999:blog-8704510721594030664.post-15973823755537977142018-06-24T08:10:00.003-07:002018-07-04T05:56:54.552-07:00Supporting Scala Adoption in Colleges<a href="http://na.scaladays.com/" target="_blank">Scala Days North America</a> 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.<br />
<br />
<ul>
<li><a href="https://na.scaladays.org/schedule/scala-is-for-everyone" target="_blank">Scala for Everyone</a> - <a href="https://twitter.com/BesseIFunction" target="_blank">Marina</a> talked about the coding workshops she is running in Australia and her book for teaching functional concepts to young kids through fairytale metaphors. (<a href="https://slideslive.com/38908724/scala-is-for-everyone?subdomain=false" target="_blank">Presentation Video</a>)</li>
<li><a href="https://na.scaladays.org/schedule/adventures-in-teaching-scala-in-the-b-school" target="_blank">Adventures in Teaching Scala in the B-School</a> - <a href="https://www.linkedin.com/in/austinhenslee/" target="_blank">Austin</a> talked about teaching Scala and associated big data tools to students in the Business school at UT Dallas. (<a href="https://slideslive.com/38908892/adventures-in-teaching-scala-in-the-bschool">Presentation Video</a>)</li>
<li><a href="https://na.scaladays.org/schedule/teaching-scala-to-the-statically-challenged" target="_blank">Teaching Scala to the Statically Challenged</a> - I think <a href="https://twitter.com/0hrely" target="_blank">Rebecca</a> 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. (<a href="https://slideslive.com/38908894/teaching-scala-to-the-statically-challenged">Presentation Video</a>)</li>
<li><a href="https://na.scaladays.org/schedule/teaching-scala-a-roundtable-discussion" target="_blank">Teaching Scala: A Roundtable Discussion</a> - A general panel on teaching Scala with <a href="https://twitter.com/youfoundryan" target="_blank">Ryan</a>, <a href="https://twitter.com/sinisa_lyh" target="_blank">Neville</a>, <a href="https://twitter.com/makingthematrix" target="_blank">Maciej</a>, <a href="https://twitter.com/DrMarkCLewis" target="_blank">me</a>, <a href="https://www.twitter.com/kelleyrobinson" target="_blank">Kelley</a>, <a href="https://www.twitter.com/odersky" target="_blank">Martin</a>, and <a href="https://www.twitter.com/heathercmiller" target="_blank">Heather</a>. (In the order listed on the schedule. I have no idea how that order was decided on.) (<a href="https://slideslive.com/38908895/teaching-scala-a-roundtable-discussion">Presentation Video</a>)</li>
<li><a href="https://na.scaladays.org/schedule/scalaquest-the-scala-adventure" target="_blank">ScalaQuest: The Scala Adventure</a> - <a href="https://www.twitter.com/andanthor" target="_blank">Alejandro</a> talked about the technology that has gone into their online game designed to teach programmers who don't know Scala. (<a href="https://slideslive.com/38908750/scalaquest-the-scala-adventure">Presentation Video</a>)</li>
</ul>
<br />
The topic of increasing the use of Scala in colleges also came up in the final panel (<a href="https://slideslive.com/38908826/closing-panel" target="_blank">Presentation Video</a>).<br />
<br />
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.<br />
<br />
<h2>
The Current State of Affairs</h2>
<div>
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 <a href="https://dl.acm.org/citation.cfm?id=3159450.3160586" target="_blank">analysis of a large dataset of student exercise solutions for zyBooks</a> indicates this might not actually be the case.)</div>
<div>
<br /></div>
<div>
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.</div>
<div>
<br /></div>
<div>
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.</div>
<div>
<br /></div>
<h2>
What Can You Do?</h2>
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.<br />
<br />
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.<br />
<br />
<h3>
Who Should You Talk To?</h3>
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.<br />
<br />
<h3>
What Types Of Schools?</h3>
<div>
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.</div>
<div>
<br /></div>
<div>
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.</div>
<div>
<br /></div>
<div>
<h3>
How To Start The Conversation</h3>
<div>
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.</div>
<div>
<br /></div>
<div>
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.</div>
<div>
<br /></div>
<div>
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.<br />
<br /></div>
</div>
<h3>
What Should You Say?</h3>
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.<br />
<br />
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.<br />
<br />
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.<br />
<br />
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.<br />
<br />
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 <a href="mailto:mlewis@trinity.edu">mlewis@trinity.edu</a>. In the US both <a href="https://twitter.com/klaeufer" target="_blank">Konstantin Läufer</a> and <a href="https://www.luc.edu/cs/people/ftfaculty/gkt.shtml" target="_blank">George K. Thiruvathukal</a> at Loyola University Chicago have experience in teaching with Scala and have an interest in spreading the word. So does <a href="https://www.depauw.edu/directories/detail/1508518504791/" target="_blank">Brian Howard</a> at DePauw University. While <a href="https://twitter.com/odersky" target="_blank">Martin</a> has <a href="https://twitter.com/0hrely/status/1009536004368359424" target="_blank">the most experience of anyone teaching Scala</a>, personally, I'd rather he focus his time on Scala 3 development. Also, while <a href="https://twitter.com/heathercmiller" target="_blank">Heather</a> 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.<br />
<br />
<h3>
Going Further</h3>
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.<br />
<br />
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.<br />
<br />
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.<br />
<br />
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.<br />
<br />
<h3>
In The Meantime</h3>
Until other colleges catch on to the value of Scala, remember that at <a href="http://www.trinity.edu/" target="_blank">Trinity University</a> 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.Mark Lewishttp://www.blogger.com/profile/11308517561967709446noreply@blogger.com0tag:blogger.com,1999:blog-8704510721594030664.post-75735306718780157962017-08-20T16:57:00.004-07:002017-08-20T16:57:54.861-07:00Want to make America Great? Go learn something new."Make America Great Again" is a slogan that all Americans are inevitably familiar with these days. Whether they love hearing it, or roll their eyes at it, everyone has heard it many time. While I am not opposed to the argument that America is currently great, the reality is that it doesn't feel very great for a lot of people because of the way our economy has changed. The <a href="https://www.google.com/search?q=s%26p+500+index&oq=s%26p+500&aqs=chrome.1.69i57j0l5.2985j0j7" target="_blank">US stock market</a> has actually been on a very nice climb since around 2009. Nothing really special has been happening in 2017 other than perhaps we have a President who likes to claim credit for everything positive, even if he didn't have anything to do with it. The problem is that the gains from those stocks and the corporate profits that have driven them there aren't trickling down to a large fraction of the population.<br />
<br />
Unfortunately, the "plan" from the Trump administration on how to fix things in America was largely to try to roll us back to the 1950s. He promised to bring back jobs in things like coal mining and manufacturing. Of course, those promises are all empty. You can't just roll back the clock and proclaim that the economy is going to work the way that it did decades ago. Things have changed. Technology has changed them.<br />
<br />
There are a variety of reasons that lots of people feel left behind in the current US economy, but the one that really stands out to me is the skills gap. Technology has changed the economy, but not enough people have stayed up with technology to keep themselves relevant in the current job market. The manufacturing sector is an area often sited for people losing jobs, but the reality is that <a href="https://fred.stlouisfed.org/series/OUTMS" target="_blank">US manufacturing output</a> is at an all time high. The thing is, the factories don't need as many workers, and the worker that they need are ones with higher level skills. This was highlighted in the article "<a href="https://www.washingtonpost.com/national/high-tech-us-plants-offer-jobs-even-as-the-laid-off-struggle/2017/08/15/bccaae78-8178-11e7-9e7a-20fa8d7a0db6_story.html" target="_blank">In US, factory jobs are high-tech, but the workers are not</a>".<br />
<br />
As that article mentions, what US employees need is training, but US employers aren't prone to pay for it. Neither is the Republican leadership we currently have running most states as well as the federal government. There are some serious challenges with training everyone as well. A number of these were outlined in "<a href="https://qz.com/1028532/technology-is-setting-us-up-for-a-training-crisis/" target="_blank">Technology is setting us up for a training crisis</a>".<br />
<br />
The thing is, we really have two problems. The one we are feeling right now is that labor is losing out to capital in terms of employer spending, so money isn't trickling down, even when stock prices and company profits are really high. The other problem is that the lack of skilled people is setting up a really bad dynamic where the top companies become superstars. This problem was highlighted in the MIT Technology Review article, "<a href="https://www.technologyreview.com/s/608095/it-pays-to-be-smart/" target="_blank">It Pays to Be Smart</a>". That article had the much more informative subtitle of , "Superstar companies are dominating the economy by exploiting a growing gap in digital competencies".<br />
<br />
This article addresses the fact that for a number of years now, economists have worried about a stall in the growth of productivity. This is significant, productivity growth has been the key driver of economic growth and the increase in societal wealth for about as long as humans have had organized civilization. This slowing of productivity has also seemed very counter intuitive because during this time digital technology has grown by leaps and bounds and has changed our lives in many very fundamental ways. What "It Pays to Be Smart" discusses is a different analysis that looks only at the top performing companies in each segment of the economy. It turns out that the top companies still have great productivity growth. All the other companies are lagging behind though, and putting a drag on the economy. Why is that? Well, the top companies are doing a really good job of harnessing digital technology, while everyone else struggles to do so in an effective way.<br />
<br />
Why is it that the top companies can use technology efficiently while most other companies struggle? To my mind the answer is once again the skills gap. In this case, a shortage of people with sufficient skills to really harness technology in a way that improves productivity. To put it another way, the small companies suck at technology because there are only so many people with the skills, and the big companies have the money to attract or buy out that small population of people. There are certainly other factors like the growth in the importance of data and the fact that large pools of data are worth a lot more than small pools of data (some of these are discussed by the Economist in "<a href="https://www.economist.com/news/leaders/21721656-data-economy-demands-new-approach-antitrust-rules-worlds-most-valuable-resource" target="_blank">The world's most valuable resource is no longer oil, but data</a>"), but it seems to me that the real challenge for small businesses that want to succeed is that they have to somehow attract and retain good people with high end skills who can bring the efficiencies of modern digital technology to bear. This would be a lot easier to do if there were more such people.<br />
<br />
Based on this reasoning, the fundamental problem holding back our economy today isn't anything related to foreign competition or immigrants, it is a lack of people with the right skills to drive the economy forward. So if you believe that America has lost its greatness, and you want to actually do something the make America great again, go out and learn something new. Thanks to the multitude of online learning sites (see links below for some), it has never been easier or cheaper to pick up new skills. It does take effort, but if you really want to improve America, sitting around complaining about the loss of the jobs of old isn't going to do it. Putting in the effort to learn new skills yourself is the activity that I truly believe will have the greatest long term benefit, and unlike many other things, your learning is something you have control over.<br />
<br />
<h4>
Online Learning Sites</h4>
<div>
I'm listing some of the big ones here. If you think I missed one, let me know in the comments and I'll add it.</div>
<div>
<br /></div>
<div>
<ul>
<li><a href="http://coursera.com/" target="_blank">Coursera</a></li>
<li><a href="https://www.udacity.com/" target="_blank">Udacity</a></li>
<li><a href="https://www.edx.org/" target="_blank">edX</a></li>
<li><a href="https://www.udemy.com/" target="_blank">Udemy</a></li>
<li><a href="https://www.khanacademy.org/" target="_blank">Khan Academy</a></li>
</ul>
</div>
Mark Lewishttp://www.blogger.com/profile/11308517561967709446noreply@blogger.com6tag:blogger.com,1999:blog-8704510721594030664.post-74293981975163309882017-06-18T06:46:00.000-07:002017-06-18T06:46:10.858-07:00How will technological unemployment impact birthrate?<span style="font-family: Arial, Helvetica, sans-serif;">This blog post is a short exploration of a thought that hit me about how birth rates might be impacted by the changes in employment caused by future technological change. I consider technological unemployment to be a significant issue as AI and robotics continue to become more capable. I'm not going to support that belief in this post, as that is many posts worth of material. I will assume that to be the case here, and briefly explore one impact of it that I hadn't thought of until recently.</span><br />
<span style="font-family: Arial, Helvetica, sans-serif;"><br /></span>
<span style="font-family: Arial, Helvetica, sans-serif;">Birth rates have been decreasing in the developed world so much that in many countries, the death rate is larger than the birth rate. According to the CIA World Fact book, there were 26 nations in 2014 for which this was the case. Japan (-1.8 net) and Germany (-3.1 net) are the ones most commonly mentioned, but there are many others. A nice treatment of this can be found at <a href="https://ourworldindata.org/fertility/">https://ourworldindata.org/fertility/</a>. There are a variety of reasons for this. Historically, the first was probably lower infant mortality rates. The more significant ones to me though are the ones that center on the increase in women's rights. As women gain more control over their their reproductive rights, they generally choose to have fewer children. In developed nations we are also seeing a decline in marriage rates and more women entering the workforce. Both of these tend to further reduce the birth rate. </span><span style="font-family: Arial, Helvetica, sans-serif;">It is the last factor mentioned that I want to focus on, as it is the one most related to technological unemployment.</span><br />
<span style="font-family: Arial, Helvetica, sans-serif;"><br /></span>
<span style="font-family: Arial, Helvetica, sans-serif;">It is worth taking a few sentences to explain why these thoughts popped into my head. I often debate the future impacts of technology with a friend who we will just call by his last name, McLane. He doesn't believe that technological unemployment will be an issue, and one of the many reasons he has sited is articles about there not being enough people to work in countries that have low population growth. He is correct that there are a number of countries providing incentives for people to have kids because they are worried about not having enough people to care for the elderly and keep the economy moving forward. Given the variety of reasons for lower fertility rates, I can indeed imagine a day when the global population goes into a tailspin simply because there are no kids born.</span><br />
<span style="font-family: Arial, Helvetica, sans-serif;"><br /></span>
<span style="font-family: Arial, Helvetica, sans-serif;">So let's assume that McLane is wrong and we get technological unemployment and have to do something, possibly a basic income, so that a large fraction of the population can live a life with dignity is a world where they can't do anything to earn a living wage because everything they have the skills to do can be done better and cheaper by machines. What happens to the birth rate at that point?</span><br />
<span style="font-family: Arial, Helvetica, sans-serif;"><br /></span>
<span style="font-family: Arial, Helvetica, sans-serif;">I'm going to by optimistic and assume that in such a world, women have at least equal power in society relative to men. I also assume that women maintain general control over their reproductive rights, and generally have all the freedoms of men. (I can actually imagine women having more power at that time as there are indications that technological unemployment so far has hit men harder than women, so if more women have jobs than men for any period of time, they could be the gender with greater social power.) Still, you get a different dynamic when people aren't chasing careers. Right now both men and women often put much of their personal lives on hold until they are well established in a career. If we have a social structure where machines are doing so much of the work that people live comfortable lives without having careers, that changes.</span><br />
<span style="font-family: Arial, Helvetica, sans-serif;"><br /></span>
<span style="font-family: Arial, Helvetica, sans-serif;">One of the standard arguments that I hear "against" technological employment is that people get lots of meaning from their jobs. I use quotes, because that isn't really an argument for why it won't happen, just something that could cause problems if it does. Personally, I think that people can find meaning in lots of other things, like hobbies or families and friends, if they don't need to work to live a comfortable life. Let's be honest, lots of people today have rather meaningless jobs and they already get much more of the meaning for their lives from other activities.</span><br />
<span style="font-family: Arial, Helvetica, sans-serif;"><br /></span>
<span style="font-family: Arial, Helvetica, sans-serif;">Given that, I can see a scenario where the birth rate goes up, and people decide to spend a lot more of their time raising children and focusing on family life. Of course, I can also imagine a world where everyone is just watching things on their screens, they have little physical contact with other humans, and the birth rate continues to sink. I'm wondering what other people think? If technology takes away the need to chase a career, will birth rates in the developed world start to rise again, or will we be so far into a situation where we enjoy our technology that the idea of having kids and a family will continue to decline?</span>Mark Lewishttp://www.blogger.com/profile/11308517561967709446noreply@blogger.com0tag:blogger.com,1999:blog-8704510721594030664.post-27494354424211359462017-04-19T09:27:00.000-07:002017-04-19T09:27:12.946-07:00Does Big Data Make Centralized Control the Better Option?I grew up in the waning years of the Cold War. I remember doing a project in High School on the possibility and repercussions of nuclear war. I got to see the fall of the Berlin Wall and many other events that went along with the crumbling of the world's other superpower as their system of government, communism, proved to be inferior to the combination of democracy and free market capitalism.<div>
<br /></div>
<div>
One of the standard arguments I recall for why communism failed was that it was inefficient and wasteful, particularly when it came to the allocation of resources. A standard example was that local farmers knew better when to plant and harvest than the central government, but that in the USSR they had to do those things when the federal government told them to. By contrast, in the US, farmers would make decisions based on their experience to try to maximize their yields. They did that because that was how they made money. A year of bad yields would be an economic hardship in the best case and possibly lead to losing the farm.</div>
<div>
<br /></div>
<div>
A thought that struck me recently is that this particular argument against communism might not apply anymore. The reason is that we have moved into the era of "big data". In fact, I wonder if centralized control might not have the advantage these days, assuming that centralized control does things in an optimal way.</div>
<div>
<br /></div>
<div>
To illustrate this, consider the farming example I just gave. The local farmers have a lot of experience they can fall back on, but these days I'm guessing that even better decisions for allocating resources could be made using a data set that included crop yields across an entire nation for many years, combined with detailed weather data during that same time and other potentially relevant information.</div>
<div>
<br /></div>
<div>
Consider <a href="http://www.economist.com/news/business/21720675-firm-using-algorithm-designed-cern-laboratory-how-germanys-otto-uses" target="_blank">this article</a> about a company that uses predictive AI to place orders in advance to improve shipping efficiency and reduce the number of returns. It is just one of many examples of how computer systems can now make decisions much better than humans are capable of because they can pull in much larger quantities of data.</div>
<div>
<br /></div>
<div>
Of course, the key here isn't centralized control, and I'm sure that many people would argue that centralized control still fails because it lacks the motivation to do well that individuals have. In that regard, this isn't a call to switch to communism. Instead, the key here is the data, and this is an area where government can play a role. Even better than one big centralized decision making process is a system where everyone has access to all the relevant data, and they can all try out various ways to process it to make optimal decisions.</div>
<div>
<br /></div>
<div>
In that regard, I think that government could play a role by making data available and helping different groups to make their data accessible and consistently formatted so that it can be more broadly used. This doesn't just apply to crops with data on weather, planting dates, harvesting dates, and yields by location, this could also be useful for a lot of data related to health including air and water quality and potentially consumption habits. I don't have a full mental image of what exactly this looks like in a broad sense, and I can clearly see challenges related to privacy issues. Still, I feel that we need to push for making more data generally available so that individuals and companies can utilize it to make better decisions. Regardless of where the control comes from, the way forward for efficient decision making is clearly availability of useful data.</div>
Mark Lewishttp://www.blogger.com/profile/11308517561967709446noreply@blogger.com11tag:blogger.com,1999:blog-8704510721594030664.post-2764168221809871182017-01-04T06:57:00.002-08:002017-01-04T13:20:02.625-08:00Performance of N-Body Simulation Styles in Scala<p>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.</p>
<p>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.</p>
<h3>Array of Mutable Classes</h3>
<p>In C++, one represents particles with a <code>struct</code> 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 <code>struct</code> 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 <code>MutableBody</code> and each of those contains two references to instances of <code>MVect3</code>. 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.</p>
<script src="https://gist.github.com/MarkCLewis/d06d1305fa1a4de49cd3faae793aee9c.js"></script>
<p>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 <code>x</code>, <code>y</code>, or <code>z</code> fields typed wrong and the resulting error is very difficult to diagnose and track down.</p>
<h3>Array of Immutable Classes</h3>
<p>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.</p>
<script src="https://gist.github.com/MarkCLewis/cb76b2029e0d01ae9ed014a9ef781175.js"></script>
<p>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 <code>+=</code>, 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.</p>
<h3>Arrays with Value Class Wrapper</h3>
<p>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.</p>
<script src="https://gist.github.com/MarkCLewis/ea7101eee6a67d65d3f8cb31958f82db.js"></script>
<p>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.</p>
<h3>Purely Functional Approaches</h3>
<p>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 <code>updated</code> 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 <code>forSim2</code>, 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.</p>
<script src="https://gist.github.com/MarkCLewis/e5ea7756dcb2bd2b04fa55f258dd9f93.js"></script>
<p>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 <code>fold</code> methods might find <code>forSim2</code> 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 <code>object</code>, but for completely different reasons. This code isn't stateful, so there is no reason to have a <code>class</code>. The state is created by the <code>initBodies</code> method and then passed into the <code>forSim</code> 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.</p>
<h3>Timing Results</h3>
<p>So how do these different versions perform? We tested all of them using Scala 2.12.1 both with no optimization flags and with <code>-opt:l:classpath -opt:closure-invocations -opt:simplify-jumps -opt:copy-propagation -opt:redundant-casts -opt:box-unbox -opt:nullness-tracking -opt:inline-global</code>. The timing results are shown in the following table.</p>
<table border="1">
<tr><th>Optimization</th><th>Style</th><th>Average Time [s]</th><th>rms [s]</th></tr>
<tr><td rowspan="5">None</td><td>Value Class</td><td>0.704</td><td>0.004</td></tr>
<tr><td>Mutable Class</td><td>0.904</td><td>0.006</td></tr>
<tr><td>Immutable Class</td><td>1.266</td><td>0.020</td></tr>
<tr><td>Functional 1</td><td>8.33</td><td>0.09</td></tr>
<tr><td>Functional 2</td><td>2.343</td><td>0.048</td></tr>
<tr><td rowspan="5">Optimized</td><td>Value Class</td><td>0.679</td><td>0.001</td></tr>
<tr><td>Mutable Class</td><td>0.682</td><td>0.001</td></tr>
<tr><td>Immutable Class</td><td>1.191</td><td>0.026</td></tr>
<tr><td>Functional 1</td><td>8.55</td><td>0.11</td></tr>
<tr><td>Functional 2</td><td>2.325</td><td>0.023</td></tr>
</table>
<p>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 <code>updated</code> so frequently on the <code>Vector</code> type is clearly inefficient. I will note though that I tried changing <code>Vector</code> to <code>Array</code>, 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.</p>
<p>It is also interesting to note that optimization benefited the mutable class version significantly, making it nearly comparable to the value class version.</p>
<h3>Comparison to C++</h3>
<p>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 <code>std::valarray</code> for storage. I compiled it using <code>g++</code> with the <code>-Ofast</code> 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 <code>g++</code> 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++.</p>
<p>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 <code>Vect3</code> 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.</p>
<h3>Other Code</h3>
<p>Here is the code for C++ and the timing in Scala in case anyone wants to be able to run everything.</p>
<p><a href="https://gist.github.com/MarkCLewis/e1bf5fca8394916231cdc0ccbecdefc3">C++ Code</a></p>
<p><a href="https://gist.github.com/MarkCLewis/dee8310e90d45dbe246901f3544b8894">Scala Timing</a></p>
Mark Lewishttp://www.blogger.com/profile/11308517561967709446noreply@blogger.com0tag:blogger.com,1999:blog-8704510721594030664.post-56363723051844487172017-01-01T15:34:00.001-08:002017-01-04T06:58:38.452-08:00Performance of Scala for Loops<p>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 <code>Options</code> and <code>Futures</code>.</p>
<p>Unfortunately, this flexibility has often come at a price. As I noted in an earlier post, <a href="http://dynamicsofprogramming.blogspot.com/2013/01/loop-performance-and-local-variables-in.html">Loop Performance and Local Variables</a>, 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.</p>
<h3>Previous Code</h3>
<p>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.</p>
<table border="1">
<tr><th>Version</th><th>Opt</th><th>Loop</th><th>Var Loc</th><th>Average Time [ns]</th><th>Time Deviation [ns]</th></tr>
<tr><td rowspan="8">2.10.6</td><td rowspan="4"> </td><td rowspan="2">for</td><td>In</td><td>3.410</td><td>0.141</td></tr>
<tr><td>Out</td><td>3.700</td><td>0.293</td></tr>
<tr><td rowspan="2">while</td><td>In</td><td>2.823</td><td>0.270</td></tr>
<tr><td>Out</td><td>2.861</td><td>0.311</td></tr>
<tr><td rowspan="4">-optimize</td><td rowspan="2">for</td><td>In</td><td>3.712</td><td>0.588</td></tr>
<tr><td>Out</td><td>3.856</td><td>0.653</td></tr>
<tr><td rowspan="2">while</td><td>In</td><td>2.895</td><td>0.252</td></tr>
<tr><td>Out</td><td>2.881</td><td>0.279</td></tr>
<tr><td rowspan="8">2.11.8</td><td rowspan="4"> </td><td rowspan="2">for</td><td>In</td><td>3.221</td><td>0.351</td></tr>
<tr><td>Out</td><td>3.666</td><td>0.397</td></tr>
<tr><td rowspan="2">while</td><td>In</td><td>3.023</td><td>0.510</td></tr>
<tr><td>Out</td><td>2.848</td><td>0.243</td></tr>
<tr><td rowspan="4">-optimize</td><td rowspan="2">for</td><td>In</td><td>3.389</td><td>0.402</td></tr>
<tr><td>Out</td><td>3.014</td><td>0.120</td></tr>
<tr><td rowspan="2">while</td><td>In</td><td>2.858</td><td>0.287</td></tr>
<tr><td>Out</td><td>2.848</td><td>0.254</td></tr>
<tr><td rowspan="8">2.12.1</td><td rowspan="4"> </td><td rowspan="2">for</td><td>In</td><td>3.154</td><td>0.354</td></tr>
<tr><td>Out</td><td>3.456</td><td>0.407</td></tr>
<tr><td rowspan="2">while</td><td>In</td><td>2.765</td><td>0.167</td></tr>
<tr><td>Out</td><td>2.751</td><td>0.139</td></tr>
<tr><td rowspan="4">See Below</td><td rowspan="2">for</td><td>In</td><td>3.261</td><td>0.321</td></tr>
<tr><td>Out</td><td>3.279</td><td>0.549</td></tr>
<tr><td rowspan="2">while</td><td>In</td><td>3.141</td><td>0.207</td></tr>
<tr><td>Out</td><td>3.164</td><td>0.264</td></tr>
</table>
<p>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 <code>-opt:l:classpath -opt:closure-invocations -opt:simplify-jumps -opt:copy-propagation -opt:redundant-casts -opt:box-unbox -opt:nullness-tracking -opt:inline-global</code>. 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.</p>
<h3>N-Body Simulation</h3>
<p>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.</p>
<p>The code used for this test is shown below. For the purposes of this post, what really matters is the <code>forSim</code> and <code>whileSim</code> 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.</p>
<script src="https://gist.github.com/MarkCLewis/f6693794beff9daa76a2a46025e24e13.js"></script>
<p>Here is a table giving the timing results for this code again the same three compilers.</p>
<table border="1">
<tr><th>Version</th><th>Opt</th><th>Loop</th><th>Average Time [s]</th><th>Time Deviation [s]</th></tr>
<tr><td rowspan="4">2.10.6</td><td rowspan="2"> </td><td>for</td><td>0.666</td><td>0.002</td></tr>
<tr><td>while</td><td>0.667</td><td>0.029</td></tr>
<tr><td rowspan="2">-optimize</td><td>for</td><td>0.660</td><td>0.012</td></tr>
<tr><td>while</td><td>0.658</td><td>0.001</td></tr>
<tr><td rowspan="4">2.11.8</td><td rowspan="2"> </td><td>for</td><td>0.716</td><td>0.009</td></tr>
<tr><td>while</td><td>0.669</td><td>0.007</td></tr>
<tr><td rowspan="2">-optimize</td><td>for</td><td>0.675</td><td>0.006</td></tr>
<tr><td>while</td><td>0.656</td><td>0.001</td></tr>
<tr><td rowspan="4">2.12.1</td><td rowspan="2"> </td><td>for</td><td>0.699</td><td>0.003</td></tr>
<tr><td>while</td><td>0.683</td><td>0.001</td></tr>
<tr><td rowspan="2">See Above</td><td>for</td><td>0.676</td><td>0.001</td></tr>
<tr><td>while</td><td>0.683</td><td>0.003</td></tr>
</table>
<p>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.</p>
<p>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.</p>
<h3>Variables in for Comprehensions</h3>
<p>There is one caveat to the conclusion that for loops don't hurt performance in the larger example. In the <code>forSim</code> method shown above, the variables <code>pi</code> and <code>pj</code> 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 <code>pi</code> between the two generators and <code>pj</code> right after the generator for <code>j</code>. 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.</p>Mark Lewishttp://www.blogger.com/profile/11308517561967709446noreply@blogger.com2tag:blogger.com,1999:blog-8704510721594030664.post-65801818466341374242016-07-01T15:22:00.001-07:002016-07-01T15:23:19.332-07:00The Value of pass-by-name Semantics<p>One of the nice features of the Scala language is the ability to use pass-by-name semantics. This isn't something that was invented for Scala. I remember first encountering it while studying for the CS subject GRE back in the mid-1990s. However, it is a feature that isn't very common in modern languages. For those who aren't familiar with this passing style, an argument that is passed-by-name is not evaluated when the function/method is called. Instead, a "thunk" is passed into the function/method. This "thunk" is basically a closure over the code with no arguments. It is evaluated each time that the value is used in the function/method. If it helps, you could think of it as being a lazy argument that doesn't cache its value, so it is re-evaluated each time. This might not sound like much, but it enables a lot of the powerful features of the Scala language, especially in regards to creating DSLs.</p>
<p>Today I was asked about an ideal way of doing something in Java. The problem involves reading through a file and adding values to a <code>Map</code>. After some testing, it was discovered that these files include duplicate keys. Since the Java libraries don't include a multimap, the solution is to use a <code>Map<String, List<Integer>></code>. The person working on this code was trying to find a succinct way of writing the code that will add values to this <code>Map</code>. Of course, the first time a key is found, you have to create a new <code>List</code> and add the one value. Subsequent matches on that key need to add the value to the <code>List</code> that is already there. Here is the straightforward approach to doing this.</p>
<pre class=brush:java>
if(map.containsKey(key) {
map.get(key).add(value);
} else {
map.put(key, value);
}
</pre>
<p>It's not really all that long or complex, but the question was, can it be improved upon, especially since Java 8 added some new, more expressive, functional features. If I were doing this in Scala, I would use <code>get</code> on the <code>Map</code> to get back an <code>Option</code> and work with that, or I could use <code>getOrElse</code> on the <code>Map</code> directly. It happens that Java 8 added <code>Optional</code> as well as a <code>getOrDefault</code> method on their <code>Map</code> type. As a result, we can write the following code in Java 8.</p>
<pre class=brush:java>
map.put(key, map.getOrDefault(key, new ArrayList<String>()).add(value));
</pre>
<p>This is perfectly fine code in many ways. It compiles. It runs. It does what you are expecting. People familiar with this library will even find it to be easy to read. However, there is a detail in here that isn't immediately obvious that makes this code rather wasteful with memory. (That really just means that your garbage collector is going to be invoked most often than it really needs to be.) The problem is that all arguments in Java are evaluated then passed either by value or by reference depending on whether they are primitives or object types. The key is that the <code>new ArrayList<String>()</code> is going to be evaluated every time this line is executed, even if the value is in the <code>Map</code>. On the other hand, in Scala, the <code>getOrElse</code> method passes the second argument by name. As a result, it will never be evaluated unless needed. So when you do something like this, you are not doing extra work to calculate a default unless you actually need it. Granted, the library writers for Java 8 could have opted to make the second argument of <code>getOrDefault</code> a function or something like it that could be passed as a lambda expression. However, they didn't. Probably because doing so would have made the calling syntax uglier. Pass-by-name does not have that drawback.</p>
<p>Of course, pass-by-name has a lot of other handy uses in Scala. It is probably the most important feature when it comes to Scala's ability to implement Domain Specific Languages and create libraries that function like language extensions. This was the first time though that I could recall really feeling the lack of this feature in some other language. Other new languages, that I have looked at some, Rust and Kotlin come to mind, seem to have also skipped over this feature. Perhaps it is time other languages began to bring it back into standard usage.</p>
Mark Lewishttp://www.blogger.com/profile/11308517561967709446noreply@blogger.com0tag:blogger.com,1999:blog-8704510721594030664.post-75756260266096636672016-02-12T08:02:00.000-08:002016-02-12T08:02:03.234-08:00Are College Students Customers?<p>I'm writing this blog post in response to <a href="https://www.linkedin.com/pulse/students-customers-santiago-iniguez">Students are not customers; Are they?</a>. I actually have a fairly simple view of this issue. The student sitting in front of me today is not my customer. The person that student will be in 5-50 years is my customer. From the student perspective, education is an investment in your future self. From the college perspective, alumni are the real test of whether or not the college is doing what it should. Alumni who are successful in life benefit the University in many ways, going well beyond their financial support.</p>
<p>Taking this viewpoint, my goal is not to make my current students happy. My goal is to equip them for later success in life. I want to make certain that when they graduate, they are have the skills to enter the workforce and do what they are hoping to do. That isn't going to happen if I coddle them and give everyone good grades. It means that I need to challenge them, but support them. I get to spent time with my students and come to know them. I can gauge how much assistance different students need to master the material. I need to impart to them the knowledge and skills that I think will put them ahead of others in the workforce when the first enter. I also need to try to develop their ability to teach themselves so that they will continue to learn through their careers so that they can keep themselves relevant.</p>
<p>I appreciate the small, liberal arts setting that I teach in, because I think that it really allows me to do what is best for my students. It also forces my students to pick up the other skills that they will need to know for their future, that I'm probably not the ideal person to teach. I stress to prospective students and occasionally to current students how important communication skills and critical thinking are going to be in their careers. I focus mostly on teaching them how to break down problems and communicate the solution method to a computer to make the computer solve the problems. The successful alumnus isn't going to just sit in front of a computer and code all day for 40 years after graduation. They should advance to being team leads, managers, even vice presidents and CTOs. Those jobs also require knowing how to communicate with humans in both written and spoken form. Many of my current students don't like that they have to take a bunch of courses outside of CS, but the people that I think of as our customers, the future selves of these students, inevitably come to appreciate the breadth of their education as much as they appreciate the rigors of the technical aspects of my personal instruction.</p>
<p>As a final benefit of this approach to "students as customers", I get to tell students who do complain about courses being hard (with a hint of sarcasm) that I am just looking out for their future selves. If I have to tear down the current version to build a better one, then so be it. ;)</p>Mark Lewishttp://www.blogger.com/profile/11308517561967709446noreply@blogger.com1tag:blogger.com,1999:blog-8704510721594030664.post-80504127357077254772015-12-07T07:33:00.001-08:002015-12-07T07:33:14.353-08:00A Recursively Enumerable Grammar for Binary Addition<p>As part of my 2nd semester CS course, I introduce students to the Chomsky hierarchy of grammars. We only go into details about regular grammars and the main learning objective is regular expressions, but I talk about context-free, context-sensitive, and recursively enumerable as well. Part of the reason is to show that there are limits to what you can do with grammars at each level, at least up to recursively enumerable, RE. I tell them that RE grammars are Turing complete, so they can compute anything that any computer could. I often use the example of a factorial because it is a fairly simple function that they are used to coding that doesn't seem at all like it would be doable with grammars.</p>
<p>This year I had a student ask about that on the questions they give me at the end of each class. He said that he couldn't see how a grammar could calculate factorial. I went to be that night trying to think of how to illustrate that a grammar could do math. I knew that I wasn't likely to write factorial, but I figured that if I started with addition might might be enough to show that you can build more complex math. The next question was how to represent that numbers. Addition in strings that use a unary format is simple, so I decided to go to binary. As an assignment in the 1st semester class I have students implement addition, multiplication, and exponentiation using only recursion, successor, and predecessor. I decided to take the approach here that I would do for addition there. We say that a+b = (a+1)+(b-1) and have a base case when b is 0. It turns out that you can implement successor and predecessor in binary strings fairly easily.</p>
<p>I put my code for doing this in a GitHub Gist that you can see at the link below. There are 14 productions in the grammar. In addition to the '0', '1', and '+' that I need to represent binary addition, I bracket the numbers with 'N' so that I can tell when I am at the beginning or end of a number. There are a few productions at the end that are used to "clean up" at the end so we get a single number in a string. There are only three productions that are used to create the successor functionality, which is done by putting in a 'S' character. The harder part is getting predecessor because the 'P' character needs to be inserted at the right end of the second number, and when it is done, we have to have that information sent back to the plus sign to say that the current operation is done. So while there are only two productions labeled as predecessor, the left and right message productions are also part of making the predecessor work.</p>
<a href="https://gist.github.com/MarkCLewis/bf83f4e4a8c0dade34ed">Gist of the Code</a>
To see how this works, I ran it and entered the numbers 5 and 6. You can see the output of that here. The first line shows that we are adding 5 and 6. Each line below that is the application of a single production. The ones that don't have a ' after the plus sign are completed steps in the addition algorithm. The last line is printing the final result, which you can see is 11 in binary.
<pre>
N101N+N110N
N101SN+'NL110N
N101SN+'N1L10N
N10S0N+'N1L10N
N10S0N+'N11L0N
N10S0N+'N110LN
N10S0N+'N110PN
N110N+'N110PN
N110N+'N11P1N
N110N+'N1R01N
N110N+'NR101N
N110N+N101N
N110SN+'NL101N
N110SN+'N1L01N
N111N+'N1L01N
N111N+'N10L1N
N111N+'N101LN
N111N+'N101PN
N111N+'N10R0N
N111N+'N1R00N
N111N+'NR100N
N111N+N100N
N111SN+'NL100N
N111SN+'N1L00N
N111SN+'N10L0N
N11S0N+'N10L0N
N11S0N+'N100LN
N1S00N+'N100LN
N1S00N+'N100PN
NS000N+'N100PN
NS000N+'N10P1N
N1000N+'N10P1N
N1000N+'N1P11N
N1000N+'NR011N
N1000N+N011N
N1000N+N11N
N1000SN+'NL11N
N1000SN+'N1L1N
N1001N+'N1L1N
N1001N+'N11LN
N1001N+'N11PN
N1001N+'N1R0N
N1001N+'NR10N
N1001N+N10N
N1001SN+'NL10N
N1001SN+'N1L0N
N1001SN+'N10LN
N1001SN+'N10PN
N100S0N+'N10PN
N100S0N+'N1P1N
N100S0N+'NR01N
N1010N+'NR01N
N1010N+N01N
N1010N+N1N
N1010SN+'NL1N
N1011N+'NL1N
N1011N+'N1LN
N1011N+'N1PN
N1011N+'NR0N
N1011N+N0N
N1011N+NN
N1011N
N1011N
</pre>Mark Lewishttp://www.blogger.com/profile/11308517561967709446noreply@blogger.com0tag:blogger.com,1999:blog-8704510721594030664.post-5189841706056206882015-02-25T13:35:00.003-08:002015-02-25T13:36:17.947-08:00Straw at Saturn's Keeler Gap<p>The term "straw", in relation to planetary rings, was coined during the orbital insertion of Cassini at Saturn when images like the following, available from the <a href='http://photojournal.jpl.nasa.gov/catalog/PIA06095'>JPL site</a>, were taken with high resolution because the probe was so close to Saturn and the rings. The "ripples" that run through this image diagonally are density waves. In the bottom left corner there is a large density wave that has course structures in it. Someone in the room when these images came down thought that they looked like straw, and the name stuck.</p>
<img src="http://photojournal.jpl.nasa.gov/jpeg/PIA06095.jpg"></img>
<p>Just a bit before Cassini arrived at Saturn, I had been doing simulations of the Encke gap that showed extremely large self-gravity wakes forming near the gap edge. These gravity wakes form as the Pan wakes damp out downstream from the moon. They were described in an <a href='http://www.sciencedirect.com/science/article/pii/S0019103505001326'>Icarus paper</a> (<a href='http://www.cs.trinity.edu/~mlewis/Rings/Icarus2004/'>Web supplement</a> with movies). The figure below comes from that paper, and the top four panels in the right column show some frames where these oversized wakes appeared in four different simulations. Since that time, "straw" type features have been seen at the edge of the B ring as well, but I am not aware of any observations of them at the Encke gap. Perhaps the end of life mission will manage to fix that with higher resolution images of the rings as Cassini dips inside the D ring.</p>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjxPLFC_wSzB7m8YMityclzchbseHmhEsJlDzeWt-7DxTmVMCsvdoGxxeokIyr9ajzPoWQUcYTq6iqkc5rJ_hC9TCQpFGIb6qwheP5JuRLjzX9rgSDwUjR7BSO2rQesTZnOxZlgF5irLuBT/s1600/StrawFig.png" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjxPLFC_wSzB7m8YMityclzchbseHmhEsJlDzeWt-7DxTmVMCsvdoGxxeokIyr9ajzPoWQUcYTq6iqkc5rJ_hC9TCQpFGIb6qwheP5JuRLjzX9rgSDwUjR7BSO2rQesTZnOxZlgF5irLuBT/s1600/StrawFig.png" /></a>
<p>It is natural for gravity wakes to form in these simulations. The frames on the left column show the situation early in the simulation when the clumping is from normal sized gravity wakes. The surface density of the simulations varies by row, and generally increases from the bottom row to the top. The size of the gravity wakes is a direct function of the surface density. Notice that the size of the clumps is much larger at the inner edge of the right column cells than it is anywhere in the left column.</p>
<p>This last year, Nicole Albers at the Laboratory for Atmospheric and Space Physics (LASP) found some interesting features in Cassini UVIS occultations of the Keeler gap region. These features are basically holes in the ring material roughly a kilometer in radial extent that are located just a bit inside of the edge of the gap itself. So you have the gap, with effectively no material, followed by a few kilometers of ring material, followed by a kilometer or so of no material, then back to the normal rings. These holes are found in the region a few degrees downstream from Daphnis, the moon that maintains the Keeler gap. (I hope to do a systematic search for these things myself using public data from the rings PDS node. I'll put up another blog post on that so I can make figures without infringing on what Nicole has done.) Some of these holes also appeared around the Encke gap.</p>
<p>I've been <a href='http://www.cs.trinity.edu/~mlewis/Rings/KeelerGap2005/'>simulating the Keeler gap</a> for a while, so I was wondering if I might see something similar in simulations. The problem was that I needed to do a big simulation to get to the region where these were seen by Cassini. My hypothesis was that straw might form near the edge of the Keeler gap, and the regions between those oversized gravity wakes would be cleared out enough to appear as a hole. To test this hypothesis, I have been running a very large simulation of the Keeler gap involving 80 million particles with collisions and particle self-gravity. At this time, the simulation has been running for about three months, and it is a bit over half way done. The animation below shows a large-scale view of the simulation. It is using a gray scale to show the geometric optical depth. That is just a ratio of how much area the particles in a small region cover divided by the total area of that small region. This isn't exactly what one would see looking at this material in the rings, but it is a reasonable approximation.</p>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjpcMYVUU74AC9Qh9qxitdr2ARbNHlvAdfgZF6qpTsnu6qhg175D_DX3ZALsqd1ebhpQb5Cp6JUdMn5fi5_bE1QVuGXa8weZAlnoTZsAihpqHB44m_mb6YK4VJdKuraMFg22w-UU21oKhcO/s1600/Orbit15Surface.gif" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjpcMYVUU74AC9Qh9qxitdr2ARbNHlvAdfgZF6qpTsnu6qhg175D_DX3ZALsqd1ebhpQb5Cp6JUdMn5fi5_bE1QVuGXa8weZAlnoTZsAihpqHB44m_mb6YK4VJdKuraMFg22w-UU21oKhcO/s1600/Orbit15Surface.gif" /></a>
<p>There is a lot going on in this plot. The coordinate system is centered on the average position of Daphnis. The particles drift from right to left with a drift speed that is proportional to their radial distance from the moon. When they go past the moon, the gravity of the moon pulls them onto eccentric orbits. This leads to the wavy structures that are visible. Daphnis has a fairly eccentric orbit relative to the width of the gap, so the magnitude of how much it pulls on the particles varies with time. The fact that Daphnis has a non-negligible eccentricity and inclination makes this part of the rings difficult to simulate. I'll plan to write a different post describing how these simulations are done, compared to the Encke gap where those values can be set to zero without losing too much information about the system. The combination of the wavy motion and the shear that results from more distance particles drifting faster leads to compression regions that we call moon wakes. Since Daphnis is the moon, I will sometimes call them Daphnis wakes. The collisions in these wakes dissipate the forced eccentricity caused by the gravitational pull of the moon, so the waviness decreases as you go to the left after passing by the moon.</p>
<p>The first question is, does straw form? If we believe from the Encke gap simulations that straw is just long, stringy gravity wakes that have grown over-large due to systematic motions of the population of particles, then this is equivalent to asking if large gravity wakes form near the edge of the Keeler gap in this simulation. The answer to this question turns out to be yes. It took 12 orbits downstream from the moon for them to begin to appear, but the figure below, which shows a region ~16 orbits after passing the moon, clearly shows that there are large gravity wakes. Going back to the figure above, if you look at the last few wake peaks, those just past 2000 km downstream from the moon, on the inner edge, there is coarse graininess that was not present in the earlier wakes. This appears to be what those large wakes manifest as in the binned data.</p>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi6sQ7IRCirOg5U3r4-siD_5gPUvSaM5e_59F8XXeXw3QM6Kh1qZX0_0Bc23RlQ66CpKKB6HYsdpbdI_5tkdtwbqLm8PGFVXP0znfkqi89OR7BNCF8JySmfV4il2FRr4NWe8bWF3Y-V1L2C/s1600/Zoom16000.png" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi6sQ7IRCirOg5U3r4-siD_5gPUvSaM5e_59F8XXeXw3QM6Kh1qZX0_0Bc23RlQ66CpKKB6HYsdpbdI_5tkdtwbqLm8PGFVXP0znfkqi89OR7BNCF8JySmfV4il2FRr4NWe8bWF3Y-V1L2C/s1600/Zoom16000.png" /></a>
<p>This simulation still needs to go another 10 orbits or so further downstream before it gets to the point where the first "holes" have been seen in occultations. That should take about another two months gives the current speed the simulation is running at. At this point we can say that straw definitely forms near the edge of the Keeler gap, but it is very unclear if the straw can cause the observed holes.</p>Mark Lewishttp://www.blogger.com/profile/11308517561967709446noreply@blogger.com0tag:blogger.com,1999:blog-8704510721594030664.post-40601601441771511632014-05-15T16:34:00.001-07:002014-05-15T18:11:23.506-07:00Strong Typing vs. Weak Typing vs. Static Typing vs. Dynamic TypingThis post is basically a little rant of mine related to misuse of terms related to typing. In particular, I get frustrated when people use the term "strongly typed" when what they really means is "statically typed". There are also many situations where people will say that something is "weakly typed" when what they really mean is "dynamically typed". The key to understanding these things is that there are two different orthogonal issues here. The first is strong vs. weak typing and the second is static vs. dynamic type checking. Programming languages can exist in the space defined by these two independent axes.
<br/><br/>
<h3>Strong vs. Weak Typing</h3>
A strongly typed language is one where every statement that is executed must follow the proper rules of the type system. A weakly typed language is one where this isn't the case. It turns out that most all of the languages people are working with these days are strongly typed. People often don't think of languages like Python as strongly typed, but just try doing something that isn't allowed with a value in Python. The program will run, but only up until that point. Then it will crash. This same thing is true for pretty much all scripting languages. It is also true for most compiled languages.
<br/><br/>
Now, different languages might be more liberal with what is "allowed" by the type system. Languages like Perl and JavaScript take great liberties in converting things so that they "work". They might implicitly convert strings to numbers and back as needed for different expressions. However, those are the operations that are defined by the language for those types. One can come up with many reasons why doing these things is bad in large software development projects, but that is why they are scripting languages. Being liberal with type conversions doesn't really mean the same thing as saying that the language has weak typing.
<br/><br/>
So then what languages do actually have weak typing? What languages allow you to do things that are completely outside of the type system? The simplest answer to this is C/C++. To illustrate this, consider the following code, which compiles without complaint under g++ version 4.7.3 using the -Wall and -pedantic options.
<pre class="brush:cpp">
int main() {
double a = 5.0;
double *d = &a;
cout << a << endl;
int *b = (int*)d;
cout << b[0] << endl;
cout << b[1] << endl;
b[0] = 99;
b[1] = 98;
cout << b[0] << endl;
cout << b[1] << endl;
cout << a << endl;
return 0;
}
</pre>
Granted, this is something that would be considered very poor C++ code because you should never do C-style casts in C++. However, that type cast on line 5 is perfectly valid in both C and C++, even though it breaks the type system. Indeed, any code that you see in the C standard libraries that takes a <code>void*</code> works by virtue of the fact that the type system is weak and can be broken. In case you are wondering, the output for this code on my machine happens to be the following.
<pre>
5
0
1075052544
99
98
2.07956e-312
</pre>
This is allowed because there are times in system level programming when you have real pointers into memory and you really just want to force the type that you are dealing with at that address. Such activities are dangerous and generally not cross-platform compatible, but when you are doing system level programming you are programming for a particular system and don't really expect it to work on others.
<br/><br/>
In a certain sense, languages are either strongly typed or they are weakly typed. Either the language allows you to break the type system with something like the code shown above, or it doesn't. However, even languages that let you break the type system can discourage it. I'm sure that many C++ programmers would be unhappy with the characterization that C++ is weakly typed. The above code is proof that it is true, but a lot of effort has gone into making it so that the proper style of code in the newer releases of C++ is strongly typed. Well written C++ code will almost certainly be done using a subset of the language that is strongly typed. They just happen to have this hole in the type system for reasons of backward compatibility and for those rare situations when system level programming really does require that you treat a block of memory as something that it isn't. I should also note that doing this with floating point numbers, as shown in my example, would be much less common than doing it with integer types of different sizes.
<br/><br/>
<h3>Static vs. Dynamic Type Checking</h3>
The more interesting aspects of programming languages have nothing to do with strong vs. weak typing. They instead center on the way in which a language does type checking. The static vs. dynamic type checking distinction focuses on whether types are checked at compile time or during the runtime. A purely statically typed language would make certain that every type was correct at compile time and no checks would ever be done at runtime. A purely dynamic language doesn't check anything related to types a compile time and all those checks are done at runtime. (I use the term "compile time" loosely here because dynamically typed languages can be interpreted and might never go through a formal compilation step.)
<br/><br/>
Most of the arguments that people get into regarding type systems focus on this static vs. dynamic distinction and the way it is implemented. Proponents of statically type checked languages argue that they provide a certain level of safety in that the compiler does a formal proof that the types in the program are correct. Proponents of dynamically typed languages argue that the type systems associated with static type checking are overly restrictive and add a burden to the programming process. While I sit strongly on the side of static type checking, the purpose of this post is to draw distinctions in terminology, not to get involved in that debate, which has been hashed out in many places.
<br/><br/>
<h3>Where Languages Stand</h3>
In some ways, where a language fits into this depends a fair bit on how you program it. That isn't true for every language, though. Some languages have a very specific location in the plane of these two axes. Even for the languages that don't, we can probably say some general things about the standard styles in them. If you follow normal style rules, few languages are going to be weakly typed in practice. C is probably the weakest, simply because the primary method of creating polymorphism in C involves casting to <code>void*</code> and losing type information. If you do this improperly, you won't find out about it until runtime and the result could be a runtime error where you program terminates or it could be a logic error where the program simply outputs garbage. In general, languages you use today other than C/C++ are probably strongly typed. Any violation of the type system causes an error either at compile time or runtime.
<br/><br/>
The static vs. dynamic axis is much more interesting. Scripting languages and functional languages derived from LISP often sit completely on the dynamic type checking extreme. If your code contains an expression like <code>sqrt("hi")</code>, things will run just fine until that line is actually executed. This is very typical for languages that use traditional, dynamic duck-typing.
<br/><br/>
There are also some languages that fall at the other extreme of the spectrum where absolutely everything has passed through type checks at compile time and nothing remains to be done at runtime. Many of the languages in the ML family, including SML and Haskell fall here. Those languages typically have type inference where the types of values are inferred by their usage and those inferred types are checked for correctness. Older procedural languages, such as Pascal, also fell at this extreme. The lack of OO and inheritance hierarchies made the type systems of these languages very straightforward.
<br/><br/>
Most of the languages that people think of as being statically typed actually include some dynamic typing as well. This is because they include things that simply can't be checked at compile time. In OO languages, you run into this when you have to downcast to a more specific type. As a general rule, this is considered a bad thing to do. In C++ the <code>dynamic_cast</code> is there because they need it, but it is intended to look ugly. In Java, unfortunately, the early versions of the language, before generics were introduced in 1.5, required a lot of downcasting. The collections were collections of type Object and every time you took something out of a collection you needed to cast it to a more specific type. This is ugly and error prone. Hence, the addition of generics. My own favorite language, Scala, includes an <code>asInstanceOf</code> method in the Any type, but use of it is strongly discouraged. (Just search for it on StackOverflow and you'll see how much it is discouraged.) The approach that is recommended in Scala is to use a match expression. This is still a runtime type check, so even well written Scala includes features that involve dynamic type checking. This is a feature of OO languages because of their type hierarchies and the occasional need to downcast. The ML family languages avoid that by simply not having type hierarchies.
<br/><br/>
<h3>Summary</h3>
So that wraps up my discussion of different terms for type systems. Next time you want to call something "strongly typed", think a bit and consider if what you really mean isn't "statically typed". A lot of the time, that is what people really mean.Mark Lewishttp://www.blogger.com/profile/11308517561967709446noreply@blogger.com0tag:blogger.com,1999:blog-8704510721594030664.post-48794908200129808132013-12-26T11:23:00.000-08:002014-02-09T18:40:56.403-08:00Duck Typing vs. Structural TypingThis post is in response to the post <a href="http://java.dzone.com/articles/duck-typing-scala-structural">Duck Typing in Scala: Structural Typing</a>, 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 <a href="http://en.wikipedia.org/wiki/Duck_typing">Wikipedia entry for duck-typing</a>, 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.
<br/><br/>
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.
<br/><br/>
<h3>Duck-Typing in C++</h3>
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++.
<pre class="brush:cpp">
template<typename Q>
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;
}
</pre>
The <code>quacker</code> 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 <code>quacker</code> with a type that doesn't have a <code>quack</code> method with an appropriate signature, you will get a compile error.
<br/><br/>
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 <code>quacker</code> functions. Here is the Scala version from that post.
<pre class="brush:scala">
def quacker(duck: {def quack(value: String): String}) {
println (duck.quack("Quack"))
}
</pre>
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 <code>quack</code> method. This doesn't appear in the C++ code. In C++, the requirement for a <code>quack</code> 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 <code>Q</code>. 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.
<br/><br/>
<h3>Structural Typing</h3>
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 <a href="http://en.wikipedia.org/wiki/Structural_type_system">structural type system</a>. Surprising, huh? You can find information <a href="http://c2.com/cgi/wiki?NominativeAndStructuralTyping">comparing structural types to nominative type systems</a>, 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 <code>class Point3D(x:Double, y:Double, z:Double)</code> and <code>class Vect3D(x:Double, y:Double, z:Double)</code> 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.
<br/><br/>
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 <code>Particle(x:Double, y:Double, z:Double, mass:Double)</code> could work as a subtype of the <code>Point3D</code> or <code>Vect3D</code> types above. Any code that uses a <code>Point3D</code> would only access <code>x</code>, <code>y</code>, and <code>z</code> and those are all safe to access on <code>Particle</code> so it is safe to treat <code>Particle</code> as a subtype in a structurally typed system.
<br/><br/>
<h3>Relative Merits</h3>
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?
<br/><br/>
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 <code>operator<</code> 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.
<br/><br/>
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.
Mark Lewishttp://www.blogger.com/profile/11308517561967709446noreply@blogger.com0tag:blogger.com,1999:blog-8704510721594030664.post-17004999501468493392013-12-01T20:00:00.000-08:002014-01-14T17:22:02.032-08:00More Benefits of Scala in CS1In 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.<br />
<br />
<h3>Total Access to Java</h3>
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 <code>java.</code> 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.<br />
<br />
While there really isn't much need for <code>java.util.Scanner</code> 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.
<pre class="brush:scala">
val sc = new java.util.Scanner(System.in)
val str = sc.nextLine()
val word = sc.next()
val fiveInts = Array.fill(5)(sc.nextInt())
</pre>
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.<br />
<br />
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.<br />
<br />
<h3>Strings as Collections</h3>
I described some of the benefits of collections in the last post. The <code>Array</code> and <code>List</code> types aren't the only types that those methods can be called on. A <code>String</code> 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 <code>Array</code> and <code>List</code> can be called on strings and they get it.<br />
<br />
To help illustrate this point let's look at some examples.
<pre class="brush:scala">
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)
</pre>
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.<br />
<br/>
It isn't just the higher order methods that are available either. You can look at the API page for <a href="http://www.scala-lang.org/api/current/#scala.collection.immutable.StringOps" target="_blank">scala.colection.immutable.StringOps</a> 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 <code>String</code>s as well.<br />
<br />
<h3>Files as Collections</h3>
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.<br />
<br />
I mentioned <code>java.util.Scanner</code> 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 <code>Scanner</code> in Scala as well. However, the Scala API provides another class called <code>scala.io.Source</code> that can be used to read text data as well. The advantage of <code>Source</code> over <code>Scanner</code> is that <code>Source</code> 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.
<pre class="brush:scala">
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()
</pre>
This code starts with a function called <code>parseLine</code> 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 <code>scala.io.Source</code>. Due to the way that packages and imports properly nest in Scala and the fact that the <code>scala</code> package is imported by default, we can use the shorter name of <code>io.Source</code>.<br />
<br />
The <code>Source</code> type is an <code>Iterator[Char]</code>. The <a href="http://www.scala-lang.org/api/current/#scala.collection.Iterator" target="_blank"><code>Iterator</code></a> type does what you would expect from Java or other languages in that it has methods called <code>next()</code> and <code>hasNext()</code>. 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 <code>Iterator</code>, the values are consumed as you move through them and not all stored in memory.<br />
<br />
Most of the time you don't really want to work with individual characters. The method <code>getLines</code> returns an <code>Iterator[String]</code> that does what the name implies. In this example, we call the <code>map</code> method on the result of <code>getLines</code> and pass it the parsing function we had written above. This would give us an <code>Iterator[Array[Double]]</code>, 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 <code>toArray</code><br />
<br />
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 <code>Source</code> 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.<br />
<br />
Now I can see someone who has taught Java pointing out here that files aren't something completely new because in Java they use <code>Scanner</code> 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.
<pre class="brush:scala">
val data = Array.fill(numLines)(readLine()).map(parseLine)
</pre>
This uses the same <code>parseLine</code> function as above, but now works on an <code>Array[String]</code> that we get from combining <code>Array.fill</code> with the basic <code>readLine</code> function that has been used since the first week of class.<br />
<br />
<h3><code>case class</code>es are Like Records/Structs</h3>
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 <code>case class</code>es. 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 <code>struct</code> in C.<br />
<br />
One of the examples I frequently do that involves files and <code>case class</code>es is processing of historical weather data. The Oak Ridge National Laboratory has a <a href="http://cdiac.ornl.gov/epubs/ndp/ushcn/ushcn_map_interface.html" target="_blank">nice site</a> 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.
<pre class="brush: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;
}
}
</pre>
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.<br />
<br />
Now compare this to the equivalent <code>case class</code> in Scala.
<pre class="brush:scala">
case class TempData(month:Int,year:Int,precip:Double,minTemp:Int,maxTemp:Int,aveTemp:Int)
</pre>
Yes, that's it. The syntax for classes in Scala was designed to reduce boiler-plate. The <code>case</code> 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 <code>val</code>s. Recall that a <code>val</code> 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 <code>case class</code>es get their own definition of <code>equals</code> and <code>hashCode</code>. 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.<br />
<br />
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.
<pre class="brush:scala">
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
</pre>
The call to <code>drop(2)</code> 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.<br />
<br />
<h3>GUIs and Graphics Without Explicit Inheritance</h3>
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.<br />
<br />
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 <code>scala.swing</code> 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.<br />
<br />
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.
<pre class="brush:scala">
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
</pre>
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.
<pre class="brush:scala">
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
</pre>
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 <code>new TextField</code> 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.<br />
<br />
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 <code>javax.swing</code> and <code>scala.swing</code>, 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.<br />
<br />
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.<br />
<br />
To get graphics into a GUI I wind up needing to do a little bit of inheritance and I do have to introduce the <code>override</code> keyword. The following code gives a simple demonstration where a dot follows the mouse around on the window.
<pre class="brush:scala">
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
</pre>
It is not too hard to go from this to simple games. The <code>scala.swing</code> package includes a <code>Swing</code> object that makes it easy to create <code>ActionListener</code>s that can be used with a <code>javax.swing.Timer</code> to create regular updates in a game.<br />
<br />
<h3>Parallelism</h3>
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 <code>par</code> 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.
<pre class="brush:scala">
var cnt = 0
for(i <- (1 to 1000000).par) cnt += 1
println(cnt)
</pre>
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.<br />
<br />
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. Mark Lewishttp://www.blogger.com/profile/11308517561967709446noreply@blogger.com0tag:blogger.com,1999:blog-8704510721594030664.post-60385764696300355222013-11-29T17:32:00.000-08:002014-07-25T15:16:11.250-07:00Benefits of Scala in CS1In 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 <a href="http://www.amazon.com/gp/product/B00AR3E2ZY" target="_blank">textbook</a> published by CRC Press in the fall of 2012. Since the book came out I have focused more on making <a href="https://www.youtube.com/user/DrMarkCLewis" target="_blank">screencast videos</a> 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.<br />
<br />
<h3>The REPL and Scripting</h3>
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.<br />
<pre class="brush:scala">
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
</pre>
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.<br />
<br />
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.
<br />
<pre class="brush:scala">
println("Hello world!")
</pre>
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.<br />
<pre class="brush:scala">
scala> math.sqrt("64")
<console>:8: error: type mismatch;
found : String("64")
required: Double
math.sqrt("64")
^
</pre>
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.<br />
<pre class="brush:scala">
val nums = readLine().split(" ").map(_.toInt)
</pre>
This code returns an <code>Array[Int]</code> with as many values as are entered on the given line of input. The <code>split</code> method is from the Java API and breaks a <code>String</code> into an array around some delimiter. Unfortunately, many educators who aren't familiar with functional programming have a negative reaction to <code>map</code>. 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, <code>map</code> is much simpler than the equivalent code in most other languages and students pick it up nicely when exposed to it early on.<br />
<br />
<h3>Programming Environment/Tooling</h3>
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.<br />
<br />
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.<br />
<br />
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 <a href="http://code.org">Code.org</a> 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.<br />
<br />
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.<br />
<br />
<h3>Regular Syntax</h3>
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 <a href="http://www.scala-lang.org/old/node/8610" target="_blank">levels of Scala programming</a>. 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.<br />
<br />
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 <code>Int</code> and need a <code>Double</code> everything is good. However, if they have a <code>Double</code> and need an <code>Int</code> then things aren't so simple. Even worse, they get a value as a <code>String</code> and they need a numeric type. We can illustrate the problem here using Java. If you have a <code>double</code> and need an <code>int</code> then you need to do a narrowing cast.
<pre class="brush:java">
double estimate = Math.sqrt(input);
functionThatNeedsAnInt((int)estimate);
</pre>
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 <code>instanceof</code>.<br />
<br />
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.<br />
<br />
The following week you run into the situation where students have a <code>String</code> and need a numeric type. So students naturally go for the obvious solution of a type case with code like <code>(int)str</code>. Only this doesn't work. So now you get to introduce something else new. In this case <code>Integer.parseInt(str)</code>. 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.<br />
<br />
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.
<pre class="brush:scala">
val estimate = math.sqrt(input)
functionThatNeedsAnInt(estimate.toInt)
println("Enter a number or quit")
val str = readLine()
if(str!="quit") {
functionThatNeedsAnInt(str.toInt)
}
</pre>
The use of methods like <code>toInt</code> is standard and uniform. You have the <code>toString</code> you are used to in Java, but it works on <code>Int</code> and <code>Double</code> too. You can also do other conversions that make sense such as <code>toDouble</code> from a <code>String</code> or <code>toChar</code> from and <code>Int</code>. Once you hit collections students find the use of <code>toList</code> and <code>toArray</code> to be perfectly natural.<br />
<br />
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 <code>int</code>, but when you are working with the novice programmer, having to describe why <code>int</code> is lower case and <code>String</code> 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.<br />
<br />
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 <code>if</code> can be nested in another <code>if</code>. When you get to classes later on the same type of freedom applies there as well.<br />
<br />
Another change in the language that I have found to really help in CS1 and CS2 is the removal of the <code>static</code> keyword. My personal experience with CS2 was that <code>static</code> was a concept that students really struggled with. The fact that this confusing keyword had to appear on the <code>main</code> method of their first program didn't help. Scala does away with the <code>static</code> keyword and instead provides <code>object</code> 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 <code>sqrt</code> or <code>parseInt</code> on a <code>class</code>. Indeed, I don't even mention the word "class" in CS1 until we start bunding data together with <code>case class</code>es. Before that it is the objects that are important, not the classes.<br />
<br />
To be fair, there is one minor challenge with the <code>object</code> 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".<br />
<br />
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 <code>val</code> can be used to declare values. There is also a <code>var</code> keyword that creates what you normally think of as a variable. (<code>val</code> is like a <code>final</code> variable in Java.) Functions and methods are declared using the <code>def</code> keyword. There is a <code>type</code> keyword for making shorter names as well as <code>class</code>, <code>trait</code>, and <code>object</code> 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.<br />
<br />
It is worth noting with <code>val</code> and <code>var</code> that Scala is making it easier to get students to use good style. In Java you really should make variables that don't change <code>final</code>. However, getting students to type those extra keystrokes is a bit challenging. I find it works much better to tell students to use <code>val</code> by default and only change things to a <code>var</code> if it is actually needed. Not all students will follow this recommendation. Some will get lazy and just make everything a <code>var</code>, but the percentage who do so is much smaller than if you are requesting the <code>final</code> keyword in Java.<br />
<br />
<h3>Functional Aspects</h3>
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.<br />
<br />
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 <code>var</code> and don't show the students the <code>Array</code> 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 <code>toUpperCase</code> on a <code>String</code> 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.<br />
<br />
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.<br />
<br />
Where the lambda expressions really come into play is when I start dealing with collections. I teach both <code>Array</code>s and <code>List</code>s 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.<br />
<br />
The power of the collections comes largely from the higher-order methods that take functions as arguments. The <code>map</code> and <code>filter</code> 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 <code>sum</code> 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.
<pre class="brush:java">
List<Person> minors = new ArrayList<Person>();
for(p:people) {
if(p.age < 18) minors.add(p);
}
</pre>
This code assumes that you are far enough along to be using <code>java.util.ArrayList</code>. If you are still working with just the built in arrays you need something a bit longer.
<pre class="brush:java">
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++;
}
}
</pre>
I could have taken out a line by reusing the <code>count</code> variable instead of introducing <code>i</code> as a variable, but such variable reuse is a risky habit to into.<br />
<br />
So how does this look in Scala?
<pre class="brush:scala">
val minors = people.filter(_.age < 18) // could be p => p.age < 18
</pre>
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.<br />
<br />
You might wonder what the type of <code>minors</code> is in the Scala code. The answer is that it is whatever collection type <code>people</code> was to start with. If you were unhappy with that you could use methods like <code>toArray</code> or <code>toList</code> to convert it to the collection type you really wanted.<br />
<br />
Now what if we wanted to find the average age of those minors? We can start again with the Java code.
<pre class="brush:java">
int sum = 0;
for(m:minors) {
sum += m.age;
}
double averageAge = (double)sum/minors.length; // or .size() for the ArrayList
</pre>
Note that cast to a <code>double</code> to prevent this code from doing integer division. So what about in Scala?
<pre class="brush: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
</pre>
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 <code>map</code> 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 <code>fold</code> methods to me more difficult to reason about.<br />
<br />
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.<br />
<br />
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.<br />
<br />
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.Mark Lewishttp://www.blogger.com/profile/11308517561967709446noreply@blogger.com1tag:blogger.com,1999:blog-8704510721594030664.post-86138459466846204622013-11-28T22:07:00.001-08:002014-01-14T17:19:10.464-08:00Why Scala for CS1 and CS2?<a class="g-profile" href="http://plus.google.com/117450883654185743920" target="_blank">+Thomas Lockney</a> pointed me to a Tweet by <a class="g-profile" href="http://plus.google.com/117708211719030258230" target="_blank">+martin <span class="GINGER_SOFTWARE_mark" ginger_software_uiphraseguid="f49da7dd-6de1-49ca-b696-17b62cad9523" id="3d43f49c-2ed0-45d3-ba49-afad5c3b3488">odersky</span></a> today with a link to the following blog post: <a href="http://teaching.software-carpentry.org/2013/11/28/choosing-scala/">http://teaching.software-carpentry.org/2013/11/28/choosing-scala/</a>. 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.<br />
<br />
I got the Odersky, et al. <span class="GINGER_SOFTWARE_mark" ginger_software_uiphraseguid="9af944cc-f2af-4993-a566-42964e7c5324" id="c58f53a7-d916-4a32-b739-7879e45a7561">book</span> 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 <span class="GINGER_SOFTWARE_mark" ginger_software_uiphraseguid="e2af1af2-0388-4474-9b99-8714547a9836" id="11705a4d-7d6c-480e-aa6c-c68066fc1650">don't have learning</span> 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.<br />
<br />
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.<br />
<br />
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 <span class="GINGER_SOFTWARE_mark" ginger_software_uiphraseguid="a20a031f-3ae0-4312-a363-1ef55d3f56e0" id="5ab286de-28d7-48b9-a188-7c14f57e649a">heavy OO</span> 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.<br />
<br />
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.<br />
<br />
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.<br />
<br />
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.<br />
<br />
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 <span class="GINGER_SOFTWARE_mark" ginger_software_uiphraseguid="c0206611-564a-4e16-b220-8258b9607857" id="b1c37de5-3c51-4fe5-88f5-79b5251a12d9">was</span> 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.<br />
<br />
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 <span class="GINGER_SOFTWARE_mark" ginger_software_uiphraseguid="1f9e631d-6fd8-4cf6-8854-df6606bf752b" id="7bf33044-c4f9-459a-aafd-d6979ca80de7">types</span>. 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.<br />
<br />
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.Mark Lewishttp://www.blogger.com/profile/11308517561967709446noreply@blogger.com0tag:blogger.com,1999:blog-8704510721594030664.post-90610393913003362992013-08-31T19:04:00.001-07:002014-01-14T17:21:00.547-08:00import != #includeI spent my summer doing software development for a local company and most of what I did was structural work on a large C++ code base with a long history. Since I am teaching a data structures course this coming fall that will use C++, I figured it would be good experience. It certainly gives me some stories to tell, but it has also helped to bring into sharper relief the differences between C++ and Java (as well as all the languages that have been influenced by Java).<br />
<br />
I will write another post giving more of my thoughts on C++11, but I should mention right off the bat here that I think C++11 has a lot of really cool features that greatly improve the language. Developing modern code in C++ is not a bad thing, but the legacy of C++ means that not all code written today has to use the modern style, and worse, the code currently in existence doesn't use these features at all. Plus, even with the improvements C++ still uses pretty much the same tool chain as C and that is a bit of a problem.<br />
<h3>
How They Differ</h3>
I've always known that import and #include do different things. I make sure to point this out to students any time I am teaching a class where I can compare languages that use these two different features. However, working on a large C++ code base made the difference really stick out. What I came to realize is that #include causes a problem because it impacts the structure of code. This isn't an issue with import because it does nothing more than tell the compiler how to resolve short names in a source file into fully specified names.<br />
<br />
The difference becomes more obvious when you run into situations where the order of #includes in a source file is important. I have to point out that if one follows all the normal best practices this never happens. Unfortunately, not everyone has followed these practices. In particular, there are Windows libraries that do things which break the rules and cause the order of includes to matter. The Windows libraries also have odd behaviors where you aren't allowed to include some files directly because they depend on other things being defined first. This can be particularly challenging when you are working on a project and the IDE tools do a great job of telling you exactly what header file defines something you need, but you aren't allowed to include that file because Microsoft did something non-standard in building their libraries. (This comes up a lot with their typdefs of BOOL, TRUE, and FALSE. That topic is probably worth a whole blog post to rant about.)<br />
<br />
In some ways, I feel that the real problem is that header files can, and often must, include other header files. Because of this, putting a single #include in a source file can result in 100 or more other headers being included. Mix in a few #ifdef or #ifndef directives and things quickly become a complete mess where order matters a lot.<br />
<h3>
How This Happens</h3>
Now it is easy to throw stones at previous developers (including those for Windows) and say they just didn't know what they were doing. Inevitably there are situations where previous developers made some poor decisions that led to structural code problems in the headers. However, many of these things can creep into code over time and maintenance programmers can easily add them in not realizing what they are doing. The reason is that some flaws in code related to #includes and headers are hard to track down unless you have a powerful static analysis tool to help you. For example, files should #include all the things that they use and not things that they don't. Sounds like a simple enough rule to follow when you are the original author of a file. The compiler won't like your code if you don't #include things you are using, and unless you just have a bad habit of adding lots of #includes at the top of every file because you "might use them" you aren't going to put in extra stuff.<br />
<br />
However, even with the original author there can be some challenges if you rely on the compiler to tell you when you are including everything that you need. If you have one header file that includes a lot of others, it is possible you might include that one file and forget to include the others directly even though you use things in them. This doesn't sound like a problem until you, or someone else, makes a change in what that one header file includes and your source files break because it wasn't doing its own includes directly. Relying on one file to do things for you that aren't really part of its job description is generally a great way to give yourself headaches later on.<br />
<br />
When you consider the situation of the maintenance programmer, things get much worse, especially if the code was a bit smelly to start with. It is easy to add code and just say that if it compiles everything is happy. It takes time and effort to go to the top of the file and see if there is already a #include for the things you just added in. The time and effort grow if the file is longer than it should be. Not only do you have to jump farther from your current editing point to check, but the length of the #include list generally grows as well.<br />
<br />
The problem is even worse when you are deleting a function, method, or even a few lines of code. Figuring out if you just deleted the only reference to something in a particular #include is not a trivial task. As a result, #includes, once added, are unlikely to never go away until someone decides to spend some real time doing cleaning or if you have a static analysis tool powerful enough to tell you that some particular #include is no longer needed.<br />
<h3>
It Made Sense for C</h3>
So why was such an odd system put into place to begin with? Well, it made sense for C, which ran on limited systems and very strictly followed the requirement of everything happening in a single pass. There were lots of hardware reasons why the original C compilers needed to go through their programs in a single pass from top to bottom and not store lots of extra tables for things along the way. When your program is stored on a tape (or punch cards) and your machine has limited memory, you don't want to have to run through the source multiple times in the process of compiling.<br />
<h3>
What changed?</h3>
Of course, most of those reasons are completely moot on a modern machine. This is why we have seen a march of programming languages that move more and more of the work onto the compiler. Focusing on Java, the import statement doesn't actually do anything to the code, it just tells the compiler how to resolve short names into the longer, fully specified names that they represent. (Honestly import is really the equivalent of using in C++, not #include.)<br />
<br />
Faster machines with more memory and the fact that you were never compiling something stored on a tape made multiple passes and random access far more acceptable. So you don't have any need to have the preprocessor spit out something that can be handled in one pass from top to bottom. You don't mind if the compiler has to go looking in separate files. In fact, that can be faster. The whole idea of precompiled headers in C and C++ only exists because opening and processing the same header files over and over for every source file in a large project can really slow things down. Losing the concept of a header file removes that overhead from the compiler. (I also really appreciate that it removes code duplication. Having to touch two files any time a function signature is adjusted has always annoyed me.)<br />
<h3>
Making import work</h3>
In Java, a significant piece of what made this possible working with the computers available in the mid 90s was that there were very specific rules that had to be followed related to file names and directories. The fully specified name in Java tells the compiler exactly where it should go looking for something. So all the compiler has to do is figure out the fully specified name and that is exactly what import statements do in the code, allow short names to be turned into fully specified names.<br />
<br />
Newer languages have relaxed some of Java's strict naming rules and have put even more burden on the compiler. Scala comes to mind as a key example of this. It compiles to the JVM and the .Class files are placed in the restricted directories required by the JVM, but the compiler actually takes its cues from the source code. Of course, it is generally recommended that you follow the Java scheme because it makes it easier for programmers to find where things are as well.<br />
<h3>
Conclusion</h3>
My main conclusion from all of this was that the decision to leave behind #include semantics and switch to import semantics was a huge step forward in programming. I know that I first saw import in the Java language, but I expect that it dates back to something earlier. Perhaps someone can leave a comment on the origin of import semantics.Mark Lewishttp://www.blogger.com/profile/11308517561967709446noreply@blogger.com0tag:blogger.com,1999:blog-8704510721594030664.post-69647402864629471702013-08-27T06:45:00.001-07:002013-08-27T06:45:09.192-07:00Why does Klout undervalue Google+Let me start off by saying that I'm a fan of <span class="GINGER_SOFATWARE_correct" ginger_sofatware_markguid="1a84c588-78aa-4fc8-b3d6-720b1b3af491" ginger_sofatware_uiphraseguid="8eaf9dc9-ed7e-4316-a2d0-14a8adf3a5bc" grcontextid="Klout:0">Klout</span>. I think that they are a very interesting metric of social network activity. I like the idea of an attention based economy and I think that Klout is a potential model for how that could begin. Plus there is the Scala factor. Given the I am a Scala zealot I love that <span class="GINGER_SOFATWARE_correct" ginger_sofatware_markguid="4fb82e9c-ac11-472d-9a0a-9a1108685240" ginger_sofatware_uiphraseguid="38962301-0b83-4345-85ac-37ffddd338eb" grcontextid="Klout:0">Klout</span> not only uses Scala but that they write about it in their <a href="http://engineering.klout.com/" target="_blank">engineering blog</a>. I think they give great publicity to the language. I am also very much looking forward to having Klout include other networks in their scores. Specifically, I would love to see the inclusion of YouTube and Blogger.<br />
<br />
Having said all of that, there is one thing that has been really bothering me. I feel that Klout dramatically undervalues Google+. To <span class="GINGER_SOFATWARE_correct" ginger_sofatware_markguid="a92e13ce-6710-432f-9018-fe2cf4a5ee02" ginger_sofatware_uiphraseguid="1b880243-c2b9-45a7-92af-55d2bd4f53ec" grcontextid="illustrates:0">illustrates</span> this we can look at the my profile and the network breakdown on Klout.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhRK6i-mGWawL3q4FVhYYHQW93UBDzdgP10fPxZ1ndcZgWJNC72Au6S5-v9TLvc-gFIFh5NED2Zfa4jEMUbejNn1e0UOcAr5Sl1sqaGlMbrGcjeXFNwx7m_yFmY0zzzS6bzJIqAmGscAXaU/s1600/KloutScreen.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="278" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhRK6i-mGWawL3q4FVhYYHQW93UBDzdgP10fPxZ1ndcZgWJNC72Au6S5-v9TLvc-gFIFh5NED2Zfa4jEMUbejNn1e0UOcAr5Sl1sqaGlMbrGcjeXFNwx7m_yFmY0zzzS6bzJIqAmGscAXaU/s320/KloutScreen.png" width="320" /></a></div>
<br />
You can see that Klout says that most of my score comes from Facebook followed by Twitter and then Google+ right behind that. They also provide some summary information for what they base this on including friends, followers, and interactions on the different networks.<br />
<br />
One of the things that Klout isn't showing under the Network information is how many people have me in circles on Google+. I find this very odd given that they do list number of friends for Facebook and number of followers on Twitter. So you can see in the figure above that I have less than 200 Twitter followers and under 600 Facebook friends. To compare this to Google+ I've included my CircleCount page here.<br />
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEimTOIUAnalxL3GBg2LcHyvvlSIP-bJ5CgkRrH5AG5s2nBqfoBDCPbUptNh9jxSDkyCwieR1iaWTMlleyjQ-WlnqI62fFaDtegzqDV2EJ1AslUaJJ-hL3c5JnG_xi3cJMG7voCgyt_1Cg5Y/s1600/CircleCountScreen.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="215" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEimTOIUAnalxL3GBg2LcHyvvlSIP-bJ5CgkRrH5AG5s2nBqfoBDCPbUptNh9jxSDkyCwieR1iaWTMlleyjQ-WlnqI62fFaDtegzqDV2EJ1AslUaJJ-hL3c5JnG_xi3cJMG7voCgyt_1Cg5Y/s320/CircleCountScreen.png" width="320" /></a></div>
<br />
You can see from this that I have over 8,500 followers on Google+. I'll be the first to admit that I don't have a lot of engagement with the vast majority of those followers, but I typically get 10+ notifications of <span class="GINGER_SOFATWARE_correct" ginger_sofatware_markguid="eb0d7ad8-0892-4ad9-bb79-5da081550ea5" ginger_sofatware_uiphraseguid="cf130e17-9255-4dbc-a05f-5d6168a003be" grcontextid="some:0">some</span> type of engagement every day. I probably get a bit more engagement on Facebook, but I have much, much less on Twitter.<br />
<br />
So my question is, why does Klout say that Twitter is slightly more significant than Google+ and that Facebook is more than 6x as significant? Is there something about the API that Google provides that prevents them from getting the needed data to consider Google+ <span class="GINGER_SOFATWARE_correct" ginger_sofatware_markguid="b6bdb7dd-0b14-4fa6-aea7-0db0a25a89e7" ginger_sofatware_uiphraseguid="25dd6331-d0cb-4d5c-9339-76ea2ccde8a3" grcontextid="appropriately:0">appropriately</span> or is their formula simply messed up? I'm hoping someone working at Klout might see this and comment. Maybe even look into it and consider tweaking that part of their formula in the next major revision. I realize it is very hard to compare across networks and that probably leads to differences, but this seems a bit extreme to me. I also feel for the Klout developers as they look at how to integrate Blogger, YouTube, and others.Mark Lewishttp://www.blogger.com/profile/11308517561967709446noreply@blogger.com0tag:blogger.com,1999:blog-8704510721594030664.post-40693106096511617602013-03-19T10:13:00.000-07:002013-03-26T09:33:22.229-07:00Why coding isn't like working a printing pressYesterday I was in a meeting with other STEM faculty discussing the proposed new curriculum for Trinity. Toward the end of the meeting I turned the discussion toward the Digital Literacy Competency aspect of the proposal. I was on the committee that created the original version of that proposal, and I felt that it had been watered down a bit. In particular, the term "algorithm" had been removed. The goal that I have for that part of the curriculum is to make it so that every student graduating from Trinity has written a little code to solve a problem. There are lots of places where people have argued for the importance of this. Some of my favorites are the blog post "<a href="http://myownfortune.wordpress.com/2012/09/21/should-you-learn-to-code/" target="_blank">Should you learn to code?</a>" and the videos at <a href="http://code.org/">Code.org</a>. (If you haven't seen these PLEASE take a minute to look at them. Technically it will be 5 minutes for the normal version of the Code.org video.)<br />
<br />
What really surprised me at this meeting was how many of the STEM faculty were opposed to this idea. I used the analogy of code being a new form of literacy and a few people commented how they didn't know how to use a printing press. Later that night I realized what I should have said in response to that to illustrate that coding is nothing like being the person who runs a printing press. Here are some reasons. First, you aren't surrounded by printing presses. You are surrounded by computing devices, just like you are surrounded by books. Second, running a program someone else wrote is, at best, like reading a book. You are consuming what someone else produced. I don't think any of my peers would argue that we would be happy having students who can only read and consume written information, but are incapable of writing their own. The goal of this capacity is to give students the first glimpses of how they produce in the digital world. If you have never seen programming, you are stuck as a consumer. You can't produce anything on the devices that surround you every day.<br />
<br />
Note that I'm not asking that every student can write the equivalent of a novel. We don't do that in English either. In fact, I'm not even asking that they <span class="GINGER_SOFATWARE_correct" ginger_sofatware_markguid="3a486d16-8622-4bd1-94b9-8c5898e50997" ginger_sofatware_uiphraseguid="f4c8567b-176d-4a49-b8bc-6d1971535cef" grcontextid="be:0">be</span> able to write the equivalent of a five page essay. I'm asking that they have the experience of writing a little script to solve some problem. I would argue that is similar to asking that they know how to compose a few sentences like what kids do in early elementary school. In fact, there is a movement growing to have students doing this at the elementary school level, and the US is behind the curve in this area (see Code.org and <a href="http://neil.fraser.name/news/2013/03/16/">http://neil.fraser.name/news/2013/03/16/</a>).<br />
<br />
Why do I think this is so important? There are several reasons. We are supposed to be preparing students to live in the 21st century. Most of our students already carry a computing device, in the form of a smart phone, with them more than they do books, yet they are completely incapable of creating any level of content on that device. They are literally marginalized by that inability.<br />
<br />
In addition, programming is all about problem solving. Honestly, I think that the formalized thinking of programming is more important for students to learn today than even a foreign language. Both have cognitive advantages to those who learn them, but the way the world is moving, I believe that the thinking skills that go into programming are the more significant of the two.<br />
<br />
Going further with the topic of problem solving, the reality is that more and more problems are becoming solvable only with the use of a computer. For the most part this is happening because the data sets involved in solving these problems have gotten to the point where you simply can't manipulate them by hand. This isn't just true in the sciences, big data sets are now the norm for social sciences and many humanities as well. The argument was raised that students can just use existing programs to solve those problems. To my mind, that's like saying that students don't need to know how to write because they can just copy and paste the ideas that other people have written. Also, just like the writing, I would argue that we want our students solving novel problems so eventually they want to say something that hasn't been said before. If that happens and they don't know how to write, they are stuck. Same thing applies to code. If you need to solve something and can't find existing programs for it, you either write it yourself or you are stuck. Knowing how to code gives you the advantage of at least being able to consider writing it yourself.<br />
<br />
Once again, I'm definitely not arguing that everyone be a CS major. In fact, I don't even want these courses taught in CS. I think that CS will have to help other faculty with them, especially early on, but I think that this will be most effective if it is done in the context of students using computers to solve problems in other domains that they are truly interested in. I made the analogy to reading and writing above, but an analogy to math works just as well. We want every one of our students to know algebra. Why? Because there are many problems that are easy to solve if you know algebra and much harder if you don't. We don't want to teach algebra so that every student will be a math major. Math majors do many things that aren't even touched upon in algebra courses. In this situation, the algebra is a tool that is useful to people. As computing devices become more widespread and the data sets that are significant for problems in all fields grow, the significance of programming increases as well. Writing a script becomes just as essential a capability as writing a short letter or solving a little equation. At least that I how it seems to me. Comment with your own thoughts.<br />
<br />
Addendum: Aaron Delwich pointed out how important it is that the computer is a universal machine. A printing press <span class="GINGER_SOFATWARE_correct" ginger_sofatware_markguid="15d86b44-e103-41d7-b3af-5da8365f007f" ginger_sofatware_uiphraseguid="635749c3-a7bc-4dd2-a97e-73e35e9f9650" grcontextid="prints:0">prints</span> books, nothing else. It is specialized. One of my colleagues at the meeting also mentioned a car, saying he could argue that we should teach all students about internal combustion engines, but cars are also very special purpose. The computer is universal. It can do any operation you want with <span class="GINGER_SOFATWARE_correct" ginger_sofatware_markguid="8f2c3795-1c9d-4cbf-9927-7ec32461e99b" ginger_sofatware_uiphraseguid="5831d5b6-2799-4865-975e-7ee02a7186a7" grcontextid="information:0">information</span>. That is why they are used in every field to solve all kinds of problems and why learning about them is not the same as learning to operate a printing press or how an engine works.Mark Lewishttp://www.blogger.com/profile/11308517561967709446noreply@blogger.com4tag:blogger.com,1999:blog-8704510721594030664.post-27347032799105804032013-02-21T20:38:00.001-08:002013-11-16T17:43:29.317-08:00Are the Humanities Killing Themselves?<span class="GingerNoCheckStart"></span>This blog post, as with many of the others I have written recently, focuses on the efforts of some to change the standard student workload at Trinity to 4 courses/semester each counting for 4 credits (a 4-4 load) instead of the current 5 courses of 3 credits. This proposal normally also has attached to it a change in teaching load so that faculty teach 3 courses one semester and 2 the next instead of 3 courses every semester [*]. This change will have a lot of implications, but one interesting point to note is that, if I paint with overly broad strokes, most of the support for this comes from the humanities and social sciences, while most of the opposition comes from the STEM and pre-professional departments [**]. Something I have discussed with others, and which I truly believe to be the case, is that the departments supporting this move, along with a proposed change to our common curriculum, do so at their own peril. I want to elaborate on this idea here in part to record it and perhaps to bring it forward <span class="GRcorrect" grcontextid="for:0" grmarkguid="11373731-3e17-4e56-af1f-933dc2f7c578" gruiphraseguid="2eeb2dd0-0e50-4344-8635-4552b5f638dc">for</span> broader discussions.<br />
<br />
The move to the 4-4, and the new curriculum proposal that will come with it have one inevitable consequence, students will take a smaller number of courses and will get less diversity in the departments they are exposed to. The 4-4 makes that first point unavoidable. The second point happens because our current breadth requirements would be impossible to maintain under the 4-4 and the new proposal, which I should point out I support, does not require students to take courses in as many different departments.<br />
<br />
So why do I think that this should bother the faculty in the humanities? Well, to pick on one particular major, how many people enter college saying they want to major in Religion? Of course, Religion isn't alone. There are a number of majors that only get majors by having them take introductory courses and fall in love with the topic. Some are even in STEM. The Geoscience department comes to mind as an example. This alone should probably give those departments second thoughts, but I am sure they can easily say that it will improve their departments in other ways so it is worth it.<br />
<br />
What I feel they ignore though is the changing national view on the role of higher education. More pressure is being put on the idea that students should major in something that will get them jobs. This goes along with the complaints that students are leaving college with too much debt and then they aren't able to find jobs. This is why we see proposed legislation that will<a href="http://www.insidehighered.com/news/2013/02/06/cantor-supports-rubio-wyden-salary-disclosure-act-criticizes-funding-political" target="_blank"> force colleges to report earnings of graduates by major</a>.<br />
<br />
I am personally already feeling some of the fallout of the change in how students are picking majors. I have 35 students in my CS2 courses at Trinity. We haven't had that many students go on to the second semester in a decade. CS is one of the few areas where people hear about there being lots of jobs and not enough people to fill them these days. It might still be true that no one goes to college thinking they want to major in Geoscience, but if they look at the incomes associated with that major they can probably be convinced.<br />
<br />
What about other departments like Religion and History? I expect they are going to take a hit from this in the next few years as more and more students enter college thinking about their earning potential. Even if the Wyden-Rubio legislation does not pass, they have access to things like the "<a href="http://cew.georgetown.edu/whatsitworth/" target="_blank">What's it Worth?</a>" report for Georgetown. They will also find things like this Forbes article entitled "<a href="http://www.forbes.com/sites/jennagoudreau/2012/10/11/the-10-worst-college-majors/" target="_blank">The 10 Worst College Majors</a>", which slams most humanities majors for high unemployment and low incomes. So why would these departments support changes that are going to likely reduce the number of students coming into their classrooms and hence their ability to attract majors? Obviously I don't have an answer to that because it makes no sense to me, but I want to dig a bit deeper to make it clear what could be at stake for these departments.<br />
<br />
Let's pick the top two departments from the top of the What's it Worth salary survey and some comparison humanities departments and look at faculty counts.<br />
<br />
Engineering Science - 9<br />
Computer Science - 7<br />
Art and Art History - 12<br />
History - 11<br />
Religion - 9<br />
<br />
Right now the humanities departments have as many or more faculty than the majors that will inevitably be getting a lot more attention if students and parents really start looking at ROI on a college education. (I know that <span class="GRcorrect" grcontextid="liberal arts:0" grmarkguid="18a2a254-0450-4e39-8437-6d1060c8f4c3" gruiphraseguid="78b3b611-f953-4212-816c-d725892843cd">liberal arts</span> are all about the additional benefits of being broadly educated, but I promise you that parents are not blind to the dollar signs when they are looking at colleges for their kids. As such, this can't be ignored no matter how good the arguments are that some things matter more than money.) So the move to the 4-4 and the new curriculum will contract the distribution requirement and pull students out of almost every department, making major counts more important. Then, if we really do get a push toward majors that lead to jobs it seems to me that a lot of the humanities departments might have a hard time filling their classrooms and justifying their current faculty counts.<br />
<br />
Note that I'm not wishing this on them or saying this is a good thing. Quite the opposite. By opposing the 4-4, I'm pushing to keep students taking a broader distribution of courses and make it so that even if more students choose to major in the sciences, the humanities will retain reasonable enrollments. I'm writing this because I don't think most of the humanities faculty see it that way and I'm wondering what they expect to see happen with their total head count in the next five years if they pass the 4-4 and the new curriculum.<br />
<br />
[*] This isn't really a drop in teaching load. The current system has faculty teaching a total of 18 credit hours each year. The altered system would have them teaching 20.<br />
<br />
[**] This is an overly broad generalization. My guess is that this post will be read by at least one Communications professor who doesn't favor the proposal. It is also problematic for Music. In addition, I'm sure a few STEM faculty are supportive. However, in general this dividing line holds.<br />
<span class="GingerNoCheckEnd"></span>Mark Lewishttp://www.blogger.com/profile/11308517561967709446noreply@blogger.com2tag:blogger.com,1999:blog-8704510721594030664.post-40444591624864654382013-01-02T11:30:00.000-08:002013-01-04T13:26:59.278-08:00Loop Performance and Local Variables in Scala<span class="GingerNoCheckStart"></span>This post was motivated by <a href="http://www.javacodegeeks.com/2012/12/local-variables-inside-a-loop-and-performance.html" target="_blank">Local variables inside a loop and performance</a>. I have to admit that the results of that post didn't really surprise me. For the code that they had written I felt like any reasonable compiler should have made the stack frame for the whole function big enough to hold those variables so that there was no additional work done for <span class="GRcorrect" grcontextid="local declaration:0" grmarkguid="27412e35-715e-4af0-a843-056221d11164" gruiphraseguid="c4a88f05-e370-4d76-aa11-bc5909134566">local declaration</span> inside of a loop. What interested me though was whether the same would be true in Scala.<br />
<br />
<b>Why Scala Might Be Different</b><br />
The for loop in Java is just a dressed up while loop. It is useful because it gives you places to put all the main components of a loop so that you are less likely to forget them. However, when you convert it to the assembly level (or <span class="GRnoSuggestion GRcorrect" grcontextid="bytecode:0" grmarkguid="af167c6e-c7b3-41c8-ace2-292f354fac7f" gruiphraseguid="b3cb6e43-6d8b-4613-9b08-1199120ba636">bytecode</span> level) it should have a conditional branch at the top and a non-conditional branch at the bottom with little additional overhead. In Scala however, the for loop is better described by the name "for comprehension". In a sense, there is no for loop in Scala. Instead, <span class="GRcorrect" grcontextid="uses:0" grmarkguid="c281b766-68ff-4c7f-8667-52e8df5b1636" gruiphraseguid="41146748-a09e-4272-b7cf-5c7553c88fe3">uses</span> of <span class="GRcorrect" grcontextid="for gets:0" grmarkguid="6cbd057b-9e17-41f0-9273-a7a954bcee95" gruiphraseguid="cfe721b2-4d21-43d2-a3cd-becd1a67ef99">for get</span> translated to calls to higher order methods like <span class="GRcorrect" grcontextid="map:2" grmarkguid="bcee7d54-08ae-4bb5-9d61-d3b7c5d0465b" gruiphraseguid="41146748-a09e-4272-b7cf-5c7553c88fe3">map</span>, flatMap, <span class="GRcorrect" grcontextid="filterWith:1" grmarkguid="4e3887b5-9048-442a-86c7-e9ab82977ac4" gruiphraseguid="cfe721b2-4d21-43d2-a3cd-becd1a67ef99">filter</span>, and <span class="GRcorrect" grcontextid="foreach:2" grmarkguid="aabb82e1-5861-41fa-989b-750f01f04c24" gruiphraseguid="cfe721b2-4d21-43d2-a3cd-becd1a67ef99">foreach</span>. As an example, consider this for loop in Scala.<br />
<br />
<span style="font-family: Courier New, Courier, monospace;"><span class="GRcorrect" grcontextid="for:0" grmarkguid="04141fad-6ca7-4d1c-ba00-e149260285bc" gruiphraseguid="37e3b3a0-cf2b-4e96-8fc5-ab2a35d69a54">for</span> (<span class="GRcorrect" grcontextid="i:1" grmarkguid="fe98e4f0-af18-4fd6-88d7-c40a4335a8f5" gruiphraseguid="37e3b3a0-cf2b-4e96-8fc5-ab2a35d69a54">i</span> <- 0 until runs) {</span><br />
<span style="font-family: Courier New, Courier, monospace;"> <span class="GRcorrect" grcontextid="val:0" grmarkguid="f51dd618-9470-4b75-9c99-77d4afe84817" gruiphraseguid="de2b6743-0e38-4cb7-b208-b5ce7072e9ba">val</span> x = <span class="GRcorrect" grcontextid="i:1" grmarkguid="85bab554-a461-4d9c-9347-a3192dc841da" gruiphraseguid="de2b6743-0e38-4cb7-b208-b5ce7072e9ba">i</span> % 12</span><br />
<span style="font-family: Courier New, Courier, monospace;"> <span class="GRcorrect" grcontextid="val:0" grmarkguid="1d2df7d2-aa67-4951-b851-5f48d03d2dc2" gruiphraseguid="dced7713-e16b-49e5-838b-7a986fb52654">val</span> y = <span class="GRcorrect" grcontextid="i:1" grmarkguid="8205c905-1e6f-4f01-8ab2-d49133433c09" gruiphraseguid="dced7713-e16b-49e5-838b-7a986fb52654">i</span> / 12 % 12</span><br />
<span style="font-family: Courier New, Courier, monospace;"> <span class="GRcorrect" grcontextid="val:0" grmarkguid="af8d4f1a-1ba6-47dd-b9f4-5030f5c3e3a2" gruiphraseguid="496f42ac-c9c9-4c4c-bac7-4de046bcd178">val</span> times = x * y</span><br />
<span style="font-family: Courier New, Courier, monospace;"> <span class="GRcorrect" grcontextid="counters:0" grmarkguid="c3632d26-2049-48c3-b4e0-c7fda7e130a7" gruiphraseguid="c40ac66b-314c-423e-8315-bc1798505b05">counters</span><span class="GRcorrect" grcontextid="(:1" grmarkguid="4147d856-e708-43f0-93b2-0b926526ff62" gruiphraseguid="c40ac66b-314c-423e-8315-bc1798505b05">(</span>times) += 1</span><br />
<span style="font-family: Courier New, Courier, monospace;">}</span><br />
<br />
<span style="font-family: inherit;">This gets translated to the following:</span><br />
<span style="font-family: inherit;"><br /></span>
<span style="font-family: Courier New, Courier, monospace;">(0 until runs)<span class="GRcorrect" grcontextid=".:0" grmarkguid="7f85b5db-b236-4aa2-99cd-60cb33d78521" gruiphraseguid="3668eb8f-defc-4c9c-91d1-f49f67dff22a">.</span><span class="GRnoSuggestion GRcorrect" grcontextid="foreach:1" grmarkguid="2b178a76-194e-41a9-b2cf-ac12b25e809b" gruiphraseguid="3668eb8f-defc-4c9c-91d1-f49f67dff22a">foreach</span><span class="GRcorrect" grcontextid="(:2" grmarkguid="5b057575-6143-4668-b018-79dfaadb456e" gruiphraseguid="3668eb8f-defc-4c9c-91d1-f49f67dff22a">(</span><span class="GRcorrect" grcontextid="i:3" grmarkguid="30312326-b6e2-4ba3-ae17-14f35b00a0e8" gruiphraseguid="3668eb8f-defc-4c9c-91d1-f49f67dff22a">i</span> => {</span><br />
<span style="font-family: Courier New, Courier, monospace;"> <span class="GRcorrect" grcontextid="val:0" grmarkguid="6bba3a4e-cee0-49b1-985f-4fba7df6a570" gruiphraseguid="dc5bc603-2f3a-4518-9181-d15a31f3f16c">val</span> x = <span class="GRcorrect" grcontextid="i:1" grmarkguid="684e63d1-ae01-4c24-b887-aa1ad601a1ef" gruiphraseguid="dc5bc603-2f3a-4518-9181-d15a31f3f16c">i</span> % 12</span><br />
<span style="font-family: Courier New, Courier, monospace;"> <span class="GRcorrect" grcontextid="val:0" grmarkguid="63fcdfad-0484-47da-8090-20e413029b74" gruiphraseguid="5e5c525c-d243-4b6d-9e4f-fce467af9c5a">val</span> y = <span class="GRcorrect" grcontextid="i:1" grmarkguid="12ac0318-8aeb-44c8-a31b-e7f3a22ef420" gruiphraseguid="5e5c525c-d243-4b6d-9e4f-fce467af9c5a">i</span> / 12 % 12</span><br />
<span style="font-family: Courier New, Courier, monospace;"> <span class="GRcorrect" grcontextid="val:0" grmarkguid="76048772-b021-4f08-979f-ecfc36b5cc1b" gruiphraseguid="e0358283-39a9-42ee-bcbc-4d6530097edc">val</span> times = x * y</span><br />
<span style="font-family: Courier New, Courier, monospace;"> <span class="GRcorrect" grcontextid="counters:0" grmarkguid="f4d2466a-f1aa-4a44-8195-909800d567f6" gruiphraseguid="071f5665-439a-47be-a6aa-b62e58bdfa0e">counters</span><span class="GRcorrect" grcontextid="(:1" grmarkguid="1ca2520e-8a36-4452-9a0e-66d98c6ecfe7" gruiphraseguid="071f5665-439a-47be-a6aa-b62e58bdfa0e">(</span>times) += 1</span><br />
<span style="font-family: Courier New, Courier, monospace;">}</span><br />
<span style="font-family: inherit;"><br /></span>
<span style="font-family: inherit;">This very simple example doesn't really show the power that is gained <span class="GRcorrect" grcontextid="by:0" grmarkguid="800055c7-c8aa-4639-965d-a543041a945d" gruiphraseguid="065d73ae-63b3-44e6-bb12-a9e0a1e5e725">by</span> this translation, but the capabilities of for comprehensions really do add a lot to Scala. Some of these features include simple data parallelism with <a href="http://docs.scala-lang.org/overviews/parallel-collections/overview.html" target="_blank">parallel collections</a> and concise syntax for Futures in the <a href="http://akka.io/" target="_blank">Akka framework</a>. However, this greater power does come with some overhead in terms of performance. This change also makes it less clear to me if local variables in for loops would be significant.</span><br />
<span style="font-family: inherit;"><br /></span>
<span style="font-family: inherit;"><b>Test Code</b></span><br />
The following code shows how I modified the Java from Peter's blog post. The initial calls to the test functions are there to allow the JIT to go through the code before any timing is done. I also went a bit further and had each function call happen multiple times so that I could get a standard deviation in addition to average values. There are two functions using the for loop and two using the while loop.<br />
<br />
<span style="font-family: Courier New, Courier, monospace;"><span class="GRcorrect" grcontextid="object:0" grmarkguid="29a3be64-eb21-471a-bb06-7e15a81e68ff" gruiphraseguid="a6c430be-38f7-4685-83b2-8554b0f383ff">object</span> LocalVars {</span><br />
<span style="font-family: Courier New, Courier, monospace;"> <span class="GRcorrect" grcontextid="def:0" grmarkguid="34d0c1fd-2b68-4813-8d0c-d532eaddf349" gruiphraseguid="5d65ea54-215c-4357-9f1b-b0a4c2e0c65c">def</span> <span class="GRcorrect" grcontextid="main:1" grmarkguid="aaaca5e8-23c0-436b-8e5b-9b219085d40b" gruiphraseguid="5d65ea54-215c-4357-9f1b-b0a4c2e0c65c">main</span><span class="GRcorrect" grcontextid="(:2" grmarkguid="09edc064-68ba-4144-bd21-8d879d752d05" gruiphraseguid="5d65ea54-215c-4357-9f1b-b0a4c2e0c65c">(</span>args:Array[String]) {</span><br />
<span style="font-family: Courier New, Courier, monospace;"> testInsideForLoop</span><br />
<span style="font-family: Courier New, Courier, monospace;"> testOutsideForLoop</span><br />
<span style="font-family: Courier New, Courier, monospace;"> testInsideWhileLoop</span><br />
<span style="font-family: Courier New, Courier, monospace;"> testOutsideWhileLoop</span><br />
<span style="font-family: Courier New, Courier, monospace;"> printResults("In for loop:",Array.fill(10000)(testInsideForLoop))</span><br />
<span style="font-family: Courier New, Courier, monospace;"> printResults("Out of for loop:",Array.fill(10000)(testOutsideForLoop))</span><br />
<span style="font-family: Courier New, Courier, monospace;"> printResults("In while loop:",Array.fill(10000)(testInsideWhileLoop))</span><br />
<span style="font-family: Courier New, Courier, monospace;"> printResults("Out of while loop:",Array.fill(10000)(testOutsideWhileLoop))</span><br />
<span style="font-family: Courier New, Courier, monospace;"> }</span><br />
<span style="font-family: Courier New, Courier, monospace;"><br /></span>
<span style="font-family: Courier New, Courier, monospace;"> def printResults(header:String,results:Array[Double]) {</span><br />
<span style="font-family: Courier New, Courier, monospace;"> println(header)</span><br />
<span style="font-family: Courier New, Courier, monospace;"> val average = results.sum/results.length</span><br />
<span style="font-family: Courier New, Courier, monospace;"> printf("Average = %.3f ns\n", average)</span><br />
<span style="font-family: Courier New, Courier, monospace;"> val aveSqr = results.map(x => x*x).sum/results.length</span><br />
<span style="font-family: Courier New, Courier, monospace;"> printf("Standard dev = %.3f ns\n\n", math.sqrt(aveSqr-average*average))</span><br />
<span style="font-family: Courier New, Courier, monospace;"> }</span><br />
<span style="font-family: Courier New, Courier, monospace;"><br /></span>
<span style="font-family: Courier New, Courier, monospace;"> def testInsideForLoop:Double = {</span><br />
<span style="font-family: Courier New, Courier, monospace;"> val start = System.nanoTime()</span><br />
<span style="font-family: Courier New, Courier, monospace;"> val counters = Array.fill(144)(0)</span><br />
<span style="font-family: Courier New, Courier, monospace;"> val runs = 1000 * 1000</span><br />
<span style="font-family: Courier New, Courier, monospace;"> <span class="GRcorrect" grcontextid="for:0" grmarkguid="cd3f5386-803a-4b7b-a10b-2c020c5bd7ee" gruiphraseguid="2c550836-b6db-4ca6-9fde-fc4d709c56a1">for</span> (<span class="GRcorrect" grcontextid="i:1" grmarkguid="a9fc6b94-6fda-4bbf-bccd-b1bc2fef6924" gruiphraseguid="2c550836-b6db-4ca6-9fde-fc4d709c56a1">i</span> <- 0 until runs) {</span><br />
<span style="font-family: Courier New, Courier, monospace;"> <span class="GRcorrect" grcontextid="val:0" grmarkguid="fa01bd3a-46e4-4300-a89f-36ff9c2292f7" gruiphraseguid="11e6b14e-e120-4efe-9a7d-d59b8cf011fb">val</span> x = <span class="GRcorrect" grcontextid="i:1" grmarkguid="cc85bd38-c563-4147-b3fc-245e27e929b8" gruiphraseguid="11e6b14e-e120-4efe-9a7d-d59b8cf011fb">i</span> % 12</span><br />
<span style="font-family: Courier New, Courier, monospace;"> <span class="GRcorrect" grcontextid="val:0" grmarkguid="59624969-1b49-44da-ae9b-37b434d6ebe7" gruiphraseguid="787c8f76-a677-49e3-ac8e-45784b260f04">val</span> y = <span class="GRcorrect" grcontextid="i:1" grmarkguid="75c456dc-8ee1-449f-b98b-3fa147ad3b96" gruiphraseguid="787c8f76-a677-49e3-ac8e-45784b260f04">i</span> / 12 % 12</span><br />
<span style="font-family: Courier New, Courier, monospace;"> <span class="GRcorrect" grcontextid="val:0" grmarkguid="8abdf570-e25f-4e26-b35e-c2aca866d4e5" gruiphraseguid="a430f217-d476-445c-96b1-d522013e7e6d">val</span> times = x * y</span><br />
<span style="font-family: Courier New, Courier, monospace;"> <span class="GRcorrect" grcontextid="counters:0" grmarkguid="71205dd4-7d62-40c8-bd19-7d7361e270f5" gruiphraseguid="c4feb7c0-7d44-4284-8715-bef77bd8d445">counters</span><span class="GRcorrect" grcontextid="(:1" grmarkguid="cbeb39e2-7e8a-4bbd-94cf-b3f0694c71d9" gruiphraseguid="c4feb7c0-7d44-4284-8715-bef77bd8d445">(</span>times) += 1</span><br />
<span style="font-family: Courier New, Courier, monospace;"> }</span><br />
<span style="font-family: Courier New, Courier, monospace;"> (System.nanoTime() - start).toDouble / runs</span><br />
<span style="font-family: Courier New, Courier, monospace;"> }</span><br />
<span style="font-family: Courier New, Courier, monospace;"><br /></span>
<span style="font-family: Courier New, Courier, monospace;"> def testOutsideForLoop:Double = {</span><br />
<span style="font-family: Courier New, Courier, monospace;"> val start = System.nanoTime()</span><br />
<span style="font-family: Courier New, Courier, monospace;"> val counters = Array.fill(144)(0)</span><br />
<span style="font-family: Courier New, Courier, monospace;"> val runs = 1000 * 1000</span><br />
<span style="font-family: Courier New, Courier, monospace;"> var x, y, times = 0</span><br />
<span style="font-family: Courier New, Courier, monospace;"> <span class="GRcorrect" grcontextid="for:0" grmarkguid="75bcf36a-7b62-41d0-8ac5-ba4ed5fa4220" gruiphraseguid="39e60e0d-565d-4f83-be3e-974396f3d8f8">for</span> (<span class="GRcorrect" grcontextid="i:1" grmarkguid="befb83ce-1c3d-465b-925b-457828922527" gruiphraseguid="39e60e0d-565d-4f83-be3e-974396f3d8f8">i</span> <- 0 until runs) {</span><br />
<span style="font-family: Courier New, Courier, monospace;"> x = i % 12</span><br />
<span style="font-family: Courier New, Courier, monospace;"> y = i / 12 % 12</span><br />
<span style="font-family: Courier New, Courier, monospace;"> times = x * y</span><br />
<span style="font-family: Courier New, Courier, monospace;"> <span class="GRcorrect" grcontextid="counters:0" grmarkguid="828c65f8-78d0-4605-b5ad-26a58494f3bb" gruiphraseguid="99d38826-3b3a-4e16-a5c6-7d19cef855a2">counters</span><span class="GRcorrect" grcontextid="(:1" grmarkguid="89505592-2be8-4e05-b968-5f58dd46d8a5" gruiphraseguid="99d38826-3b3a-4e16-a5c6-7d19cef855a2">(</span>times) += 1</span><br />
<span style="font-family: Courier New, Courier, monospace;"> }</span><br />
<span style="font-family: Courier New, Courier, monospace;"> (System.nanoTime() - start).toDouble / runs</span><br />
<span style="font-family: Courier New, Courier, monospace;"> }</span><br />
<div>
<br /></div>
<div>
<div>
<span style="font-family: Courier New, Courier, monospace;"> def testInsideWhileLoop:Double = {</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"> val start = System.nanoTime()</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"> val counters = Array.fill(144)(0)</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"> val runs = 1000 * 1000</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"> var i = 0</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"> while (i < runs) {</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"> <span class="GRcorrect" grcontextid="val:0" grmarkguid="da68b0b7-d170-426f-aa36-015c688fb92a" gruiphraseguid="432e30d9-3c90-4235-8326-89a69ea335f1">val</span> x = <span class="GRcorrect" grcontextid="i:1" grmarkguid="ca5bf41e-986b-48a3-a2e2-91ef32f5606b" gruiphraseguid="432e30d9-3c90-4235-8326-89a69ea335f1">i</span> % 12</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"> <span class="GRcorrect" grcontextid="val:0" grmarkguid="1dd054ad-9591-4430-adf2-2089b5d59a2f" gruiphraseguid="95ca51d5-bf65-4b62-baa3-2ada186325b0">val</span> y = <span class="GRcorrect" grcontextid="i:1" grmarkguid="cd6f329e-98a6-4792-bad9-6f33610cd821" gruiphraseguid="95ca51d5-bf65-4b62-baa3-2ada186325b0">i</span> / 12 % 12</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"> <span class="GRcorrect" grcontextid="val:0" grmarkguid="0e5adbaf-6f85-4948-86e3-06d225d53c91" gruiphraseguid="b4fe3c52-cc76-4eb5-aa1d-6f636beecdba">val</span> times = x * y</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"> <span class="GRcorrect" grcontextid="counters:0" grmarkguid="64acad3e-c742-434e-beb7-b3cdcf1b766a" gruiphraseguid="f118ac7a-87c5-46ff-bc68-a082444903f4">counters</span><span class="GRcorrect" grcontextid="(:1" grmarkguid="d5bf30e2-ea22-4851-8a9b-e490c2164778" gruiphraseguid="f118ac7a-87c5-46ff-bc68-a082444903f4">(</span>times) += 1</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"> i += 1</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"> }</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"> (System.nanoTime() - start).toDouble / runs</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"> }</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"><br /></span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"> def testOutsideWhileLoop:Double = {</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"> val start = System.nanoTime()</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"> val counters = Array.fill(144)(0)</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"> val runs = 1000 * 1000</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"> var x, y, times, i = 0</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"> while (i < runs) {</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"> x = i % 12</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"> y = i / 12 % 12</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"> times = x * y</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"> <span class="GRcorrect" grcontextid="counters:0" grmarkguid="3db12c34-6dd0-46ac-bc05-4f555791e089" gruiphraseguid="18e21aa7-4293-46af-8b8d-8284f109ed3f">counters</span><span class="GRcorrect" grcontextid="(:1" grmarkguid="48d15c26-6d53-43bc-a2b4-e73fb1e8effd" gruiphraseguid="18e21aa7-4293-46af-8b8d-8284f109ed3f">(</span>times) += 1</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"> i += 1</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"> }</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"> (System.nanoTime() - start).toDouble / runs</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"> }</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;">}</span></div>
</div>
<div>
<br /></div>
<div>
<b>Results</b></div>
<div>
I compiled the above code using using Scala 2.10.0-RC5 with the -optimise option. When I ran it I got the following output.</div>
<div>
<br /></div>
<div>
<div>
<span style="font-family: Courier New, Courier, monospace;">In for loop:</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;">Average = 6.073 ns</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;">Standard dev = 0.448 ns</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"><br /></span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;">Out of for loop:</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;">Average = 6.084 ns</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;">Standard dev = 0.507 ns</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"><br /></span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;">In while loop:</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;">Average = 4.670 ns</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;">Standard dev = 0.322 ns</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"><br /></span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;">Out of while loop:</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;">Average = 4.669 ns</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;">Standard dev = 0.320 ns</span></div>
</div>
<div>
<br /></div>
<br />
It is clear that where you declare local variables doesn't matter at all as all variations are inside the error bars for the measurement. However, there is a reasonable performance penalty for using the for loop. The <a href="http://code.google.com/p/scalacl/" target="_blank">ScalaCL project</a> provides one approach to getting around this. Since ScalaCL is not up to date with 2.10 I didn't test this out. Earlier testing under 2.8 showed me that it generally did bring the performance of for loops in line with while loops. I would love to see the ScalaCL project get more support both for this reason and to improve the OpenCL collections.<br />
<br />
<b>More Questions</b><br />
I have two problems with what is done here. First, my Scala code is not at all Scala-like. Part of this is because Peter picked a problem that is best solved in a very imperative way. It would be interesting to pick a problem that also has a nice functional solution and then play with that a bit. This would also make it possible to try seeing how using parallel collections could be beneficial.<br />
<br />
A more significant question was posed in a discussion on Google+ by one of my former students, Will Shepherd. This is the question of what happens with memory if the variables are a bit more complex. Here again, the chosen example code holds us back a bit as there doesn't seem to be much need for non-primitive variables here. However, the results could be extremely different if the variable were to hold an array or some type of mutable object.<br />
<br />
Perhaps someone can suggest a problem that would make some sense in exploring these two avenues.<br />
<span style="font-family: inherit;"><br /></span>
<b>Conclusion</b><br />
My take away message from Peter's original blog, which I think hold true here as well is that your best bet is to write good code first, then worry about performance as needed. Declaring variables locally is just a good idea. Limiting scope is remarkably helpful in preventing bugs. So that is how you should write your code. If you find that your code isn't fast enough once you have it working, then you explore options for making it faster. In the case of local declarations of primitive variables in loops, I think it is clear that there isn't any point in even trying that route. However, if you do decide to start exploring optimizations, you need to be careful and meticulous. Re-benchmark after each "optimization" because it is possible that you might make a change which leads to uglier, harder to maintain code without getting any speed benefit at all.<br />
<span class="GingerNoCheckEnd"></span>Mark Lewishttp://www.blogger.com/profile/11308517561967709446noreply@blogger.com0tag:blogger.com,1999:blog-8704510721594030664.post-56278068888617198682012-11-25T19:24:00.001-08:002012-11-25T21:42:49.393-08:00The Fallacy of "Deep" Courses and Workloads<b>Background</b><br />
<br />
This is back on the proposal that is being considered at Trinity to change student course loads to 4 courses per semester, each worth 4 credits (4-4) and the associated change in teaching load to five courses each year with 3 one semester and 2 the next (3-2). I am writing this blog post because I am finally getting fed up with statements that I keep hearing about how some courses simply require more time than others, especially time spent outside of class. There is also an associated aspect of this, where the same people who make these statements insinuate that this extra time is needed for their courses because they are too "deep" for a normal 3 credits.<br />
<br />
<b>Why I <span class="GRcorrect" grphrase="2073a170556e4db159ed94e9ad8539dde3c12460" grtype="null" id="GRmark_2073a170556e4db159ed94e9ad8539dde3c12460_am Upset:0">am Upset</span></b><br />
<br />
Here is the problem, you don't hear these things coming from STEM faculty. You know, the people teaching the science and math courses that most students consider to be the hardest courses on campus. The majority of STEM faculty <span class="GRcorrect" grphrase="5c8abe7bb448d337b6fb28e46872730841c3053c" grtype="null" id="GRmark_5c8abe7bb448d337b6fb28e46872730841c3053c_seem:0">seem</span> to be quite happy with how things are. The push for change seems to be coming largely from the humanities and social sciences.<br />
<br />
I guess what really offends me is that these statements imply that because I am happy with my course counting for 3-credits that somehow my course is easier and less deep. I'm sorry, but I have had many students tell me that the courses I teach are the hardest ones they take during their entire time at Trinity. My courses also keep students very busy outside of the classroom. My guess is that most of the students in my courses will spend more time on my class than on any of the other courses they are taking. In fact, when students can't do that they tend to wind up withdrawing from my course.<br />
<br />
My courses aren't time consuming because they are full of busy work either. They are time consuming because students have to wrap their heads around completely new ways of thinking, and they have to learn to break down problems to levels they have never done before. Then they are forced to apply those capabilities and they are forced to make things work. My courses aren't fluff. They are rigorous and challenging and it is really getting on my nerves how so many faculty seem to be saying that their courses are harder than mine and hence need to count for more credits.<br />
<br />
This doesn't just apply to my courses either. Anyone who tells you that courses like E&M, Quantum Mechanics, or Complex Analysis don't require deep thinking or much time spent outside of class clearly has no idea what he/she is talking about. They have obviously not spent time trying to picture a vector field flowing through a Gauss pillbox.<br />
<br />
If people really want to get some data on what departments have more challenging courses, and which ones require more time and effort both inside and outside of class, there is a publicly available data set for that called RateMyProfessors.com. They list ease as a criteria. If you scan through it for faculty with an ease rating of 2.5 or less, you will notice that STEM faculty <span class="GRcorrect" grphrase="b7f6f2f6adabb432f98eb3d0da32a70cc3e0c715" grtype="null" id="GRmark_b7f6f2f6adabb432f98eb3d0da32a70cc3e0c715_are:0">are</span> extremely over represented. (So is the English department.)<br />
<br />
(Here is a coding assignment for any of my students reading this. Write a program to scrape data from RateMyProfessor.com. I'm most interested in <span class="GRcorrect" grphrase="acba8799a39e209873af9ee2cd5ee9a99b0c5e78" grtype="null" id="GRmark_acba8799a39e209873af9ee2cd5ee9a99b0c5e78_department:0">department</span> and ease for this topic, though it would be good to have names so that people who aren't current faculty can be removed.)<br />
<br />
<b>Enforcing Work</b><br />
<br />
My gut feeling is that faculty who think they need students to take fewer courses and want students to have more time outside of class really just need to find better ways of enforcing work done outside of class. The idea that students are booked solid with academics when taking five 3-credit courses is absurd. Trinity students spend lots of time doing many things that aren't academic. Give them more time outside of class and they will use it for a variety of non-academic activities unless you can enforce that they use it doing the work for your class.<br />
<br />
The fallacy that STEM courses somehow require less time outside of class is absurd. The reality is that STEM courses typically do a much better job of enforcing that students actually do what they are supposed to do outside of class. I can give my students assignments and exercises and if they don't take the time to learn the material, they will be completely incapable of doing those assignments. No, my students don't read everything I assign. However, they will read enough to be able to write the programs I ask them to do. (Honestly, many students would probably spend a little less time on my class if they would do the <span class="GRcorrect" grphrase="0efb6dc6b69e86133e0a99d39c889fbf5b3d7bcf" grtype="null" id="GRmark_0efb6dc6b69e86133e0a99d39c889fbf5b3d7bcf_reading:0">reading</span> up front instead of wasting hours trying to code before they understand what they are doing.) I know this is more challenging for many non-STEM courses, but that doesn't mean it is impossible.<br />
<b><br /></b>
The bottom line, as I see it, is that changing the number of hours/credits for a course doesn't make students do more work, and making new policies based on the idea that it will <span class="GRcorrect" grphrase="5aecc1dcab3e933301e7390a44cb4599847aa780" grtype="null" id="GRmark_5aecc1dcab3e933301e7390a44cb4599847aa780_is:0">is</span> a great way to reduce the quality of a Trinity education. If faculty want students to do more work on their course, they need to be inventive and creative and find ways to enforce students doing the required work. That is the only way to make change happen.<br />
<br />
<b>Feedback</b><br />
<br />
I'd love to hear back from anyone who reads this and is willing to say which courses they had in college that challenged them the most or kept them busy the most. I'd also love to hear why. This is especially true for Trinity students.<br />
<br />
(<b>Update</b>: I would like to thank Laura Gibbs for pointing out the <a href="http://nsse.iub.edu/html/annual_results.cfm" target="_blank">National Survey of Student Engagement</a> in the Google+ discussion of this post. Ideally students should be spending 2 hours outside of classes for every hour inside of class. This survey shows that students spend between 12 and 18 hours total prepping for class. In other words, they aren't even close to the 2-hour mark. If faculty want students to work harder, the reality is that most students have time in their schedules. They just need to be forced to take the time.)<br />
<br />
<b>Aside: A Useful Technique</b><br />
<b><br /></b>
I'll close with a technique that I learned in grad school for Amer Diwan who taught a course on program analysis. This course was all about reading journal articles. I have used this approach to good effect in similar courses at Trinity. Make students show up to class with written questions on the reading. If you don't want to do questions, have them write a short paragraph instead. Base the in class discussion on the questions students hand to you when they first walk in. Have a portion of the semester grade come from the quality of what the students write for this. Call students out when what they provide sucks and shows that they didn't really put in the effort.Mark Lewishttp://www.blogger.com/profile/11308517561967709446noreply@blogger.com0