November 25, 2017 7:52 AM

Sure, In the End, It's Just Objects and Functions

After implementing the patterns from James Noble's Arguments and Results, Gregory Brown reflects:

After taking a look at the finished Turtle object, I did wonder a little bit about whether the idea of a curried object in Ruby is nothing more than an ordinary object making use of object composition. However, because the name of the pattern is helpful for describing the intent of this sort of object in a succinct way, it may be a good label for us to use when discussing the merits of different design options.

In the end it is, indeed, all just objects, or functions, or whatever the primitives structures are in your programming style du jour. The value of design patterns in any styles lies in teaching us stereotypical patterns of usage, the web of objects or functions we might not have thought of in the course of design. Once we know about the patterns, the names become a valuable part of the vocabulary we use to talk about design.

I know that Brown's blog entry is six years old, that Noble's paper is seventeen, and that talking about design patterns is passé in many circles. But I still find the notion of patterns and pattern languages to be immensely useful, and even in 2017 I hear people express surprise at patterns are just commonsense or bad design dressed up in fancy writing. That makes me sad. We need more descriptions of experts' implicit holistic design knowledge, not fewer.

In closing, though, please don't read my reaction here as a diss of Brown's blog entry. His two entries on Noble's patterns do a nice job showing how these patterns can improve a Ruby program and exploring the trade-offs between the "before" and "after" versions of the code. I hope that he bring his Practicing Ruby project back to life.

Posted by Eugene Wallingford | Permalink | Categories: Patterns, Software Development

November 24, 2017 12:30 PM

Thousand-Year Software

I recently read an old conversation between Neil Gaiman and Kazuo Ishiguro that started out as a discussion of genre but covered a lot of ground, including how stories mutate over time, and that the time scale of stories is so much larger than that of human lives. Here are a few of the passages about stories and time:

NG   Stories are long-lived organisms. They're bigger and older than we are.
NG   You sit there reading Pepys, and just for a minute, you kind of get to be 350, 400 years older than you are.
KI   There's an interesting emotional tension that comes because of the mismatch of lifespans in your work, because an event that might be tragic for one of us may not be so for the long-lived being.
KI   I'm often asked what my attitude is to film, theatrical, radio adaptations of my novels. It's very nice to have my story go out there, and if it's in a different form, I want the thing to mutate slightly. I don't want it to be an exact translation of my novel. I want it to be slightly different, because in a very vain kind of way, as a storyteller, I want my story to become like public property, so that it gains the status where people feel they can actually change it around and use it to express different things.

This last comment by Ishiguro made me think of open-source software. It can be adapted by anyone for almost any use. When we fork a repo and adapt it, how often does it grow into something new and considerably different? I often tell my compiler students about the long, mutated life of P-code, which was related by Chris Clark in a 1999 SIGPLAN Notices article:

P-code is an example [compiler intermediate representation] that took on a life of its own. It was invented by Nicklaus Wirth as the IL for the ETH Pascal compiler. Many variants of that compiler arose [Ne179], including the USCD Pascal compiler that was used at Stanford to define an optimizer [Cho83]. Chow's compiler evolved into the MIPS compiler suite, which was the basis for one of the DEC C compilers -- acc. That compiler did not parse the same language nor use any code from the ETH compiler, but the IL survived.

That's not software really, but a language processed by several generations of software. What are other great examples of software and languages that mutated and evolved?

We have no history with 100-year-old software yet, of course, let alone 300- or 1000-year-old software. Will we ever? Software is connected to the technology of a given time in ways that stories are not. Maybe, though, an idea that is embodied in a piece of software today could mutate and live on in new software or new technology many decades from now? The internet is a system of hardware and software that is already evolving into new forms. Will the world wide web continue to have life in a mutated form many years hence?

The Gaiman/Ishiguro conversation turned out to be more than I expected when I first found it. Good stuff. Oh, and as I wrap up this post, this passage resonates with me:

NG   I know that when I create a story, I never know what's going to work. Sometimes I will do something that I think was just a bit of fun, and people will love it and it catches fire, and sometimes I will work very hard on something that I think people will love, and it just fades: it never quite finds its people.

Been there, done that, my friend. This pretty well describes my experience blogging and tweeting all these years, and even writing for my students. I am a less reliable predictor of what will connect with readers than my big ego would ever have guessed.

Posted by Eugene Wallingford | Permalink | Categories: Computing, General

November 20, 2017 2:58 PM

Tests That Protect Your Code From Without

I recently ran across an old post from Spotify about how the confluence of Spotify's generous policy for usernames, the oddities of Unicode, and a change in standard Python libraries led to a situation in which a person could hijack an existing username. The post explains how Spotify tracked down the problem and fixed it -- a good read.

The paragraph before the closing "Some Take-Aways" section says:

So changes in the standard python library from one python version to the next introduced a subtle bug in twisted's nodepre.prepare() function which in turn introduced a security issue in Spotify's account creation.

... which, to my mind, hints at a bonus takeaway not listed in the closing. It would really have been nice to have had a test that noticed when nodeprep's method for canonicalizing (ugh) usernames was no longer idempotent.

Not having such a test is understandable. I don't write tests for all or even many of the library functions I use. This means trusting the creators of the libraries I use. (It also means choosing libraries judiciously.) In this case, there wasn't even a bug in twisted's original code; a change in Python introduced one. It is hard to anticipate when a language upgrade will create a bug in a library that I am using.

However, when something like this occurs, I find that it is a good time to add a test. This bug exposed just how important it is for the code to ensure idempotence when lower-casing a username. A new test or two can protect the code base from unexpected errors from without without placing an unreasonable burden on me as a developer. And those tests give me peace of mind, which is usually more than worth an extra millisecond when running my tests.

Posted by Eugene Wallingford | Permalink | Categories: Software Development

November 15, 2017 4:03 PM

A Programming Digression: Kaprekar Numbers

Earlier this week I learned about Kaprekar numbers when someone re-tweeted this my way:

Kaprekar numbers are numbers whose square in that base can be split into 2 parts that add up to the original number

So, 9 is a Kaprekar number, because 9 squared is 81 and 8+1 equals 9. 7777 is, too, because 7777 squared is 60481729 and 6048 + 1729 equals 7777.

This is the sort of numerical problem that is well-suited for the language my students are writing a compiler for this semester. I'm always looking out for fun little problems that I can to test their creations. In previous semesters, I've blogged about computing Farey sequences and excellent numbers for just this purpose.

Who am I kidding. I just like to program, even in small language that feels like integer assembly language, and these problems are fun!

So I sat down and wrote Klein functions to determine if a given number is a Kaprekar number and to generate all of the Kaprekar numbers less than a given number. I made one small change to the definition, though: I consider only numbers whose squares consist of an even-number of digits and thus can be split in half, a lá excellent numbers.

Until we have a complete compiler for our class language, I always like to write a reference program in a language such as Python so that I can validate my logic. I had a couple of meetings this morning, which gave just the time I needed to port my solution to a Klein-like subset of Python.

When I finished my program, I still had a few meeting minutes available, so I started generating longer and longer Kaprekar numbers. I noticed that there are a bunch more 6-digit Kaprekar numbers than at any previous length:

 1: 1
 2: 3
 3: 2
 4: 5
 5: 4
 6: 24
Homer Simpson says, 'D'oh!'

I started wondering why that might be... and then realized that there are a lot more 6-digit numbers overall than 5-digit -- ten times as many, of course. (D'oh!) My embarrassing moment of innumeracy didn't kill my curiosity, though. How does that 24 compare to the trend line of Kaprekar numbers by length?

 1: 1    of        9  0.11111111
 2: 3    of       90  0.03333333
 3: 2    of      900  0.00222222
 4: 5    of     9000  0.00055555
 5: 4    of    90000  0.00004444
 6: 24   of   900000  0.00002666

There is a recognizable drop-off at each length up to six, where the percentage is an order of magnitude different than expected. Are 6-digit numbers a blip or a sign of a change in the curve? I ran another round. This took much longer, because my Klein-like Python program has to compute operations like length recursively and has no data structures for caching results. Eventually, I had a count:

 7: 6    of  9000000  0.00000066

A big drop, back in line with the earlier trend. One more round, even slower.

 8: 21   of 90000000  0.00000023

Another blip in the rate of decline. This calls for some more experimentation... There is a bit more fun to have the next time I have a couple of meetings to fill.

Image: courtesy of the Simpsons wiki.

Posted by Eugene Wallingford | Permalink | Categories: Computing

November 14, 2017 3:52 PM

Thinking about Next Semester's Course Already

We are deep into fall semester. The three teams in my compilers course are making steady progress toward a working compiler, and I'm getting so excited by that prospect that I've written a few new programs for them to compile. The latest two work with Kaprekar numbers.

Yet I've also found myself thinking already quite a bit about my spring programming languages course.

I have not made significant changes to this course (which introduces students to Racket, functional programming, recursive programming over algebraic data types, and a few principles of programming languages) in several years. I don't know if I'm headed for a major re-design yet, but I do know that several new ideas are commingling in my mind and encouraging me to think about improvements to the course.

The first trigger was reading How to Switch from the Imperative Mindset, which approaches learning functional style explicitly as a matter establishing new habits. My students come to the course having learned an imperative style in Python, perhaps with some OO in Java thrown in. Most of them are not yet 100% secure in their programming skills, and the thought of learning a new style is daunting. They don't come to the course asking for a new set of habits.

One way to develop a new set of habits is to recognize the cues that trigger an old habit, learn a new response, and then rehearse that response until it becomes a new habit. The How to Switch... post echoes a style that I have found effective when teaching OOP to programmers with experience in a procedural language, and I'm thinking about how to re-tool part of my course to use this style more explicitly when teaching FP.

My idea right now is something like this. Start with simple examples from the students' experience processing arrays and lists of data. Then work through solutions in sequence, such as:

  1. first, use a loop of the sort with which they are familiar, the body of which acts on each item in the collection
  2. then, move the action into a function, which the loop calls for each item in the collection
  3. finally, map the function over the items in the collection

We can also do this with built-in functions, perhaps to start, which eliminates the need to write a user-defined function.

In effect, this refactors code that the students are already comfortable with toward common functional patterns. I can use the same sequence of steps for mapping, folding, and reducing, which will reinforce the thinking habits students need to begin writing FP code from the original cues. I'm only just beginning to think about this approach, but I'm quite comfortable using a "refactoring to patterns" style in class.

Going in this direction will help me achieve another goal I have in mind for next semester: making class sessions more active. This was triggered by my post-mortem of the last course offering. Some early parts of the course consist of too much lecture. I want to get students writing small bits of code sooner, but with more support for taking small, reliable steps.

Paired this change to what happens in class are changes to what happens before students come to class. Rather than me talking about so many things in class, I hope to have

  • students reading clear expositions of the material, in small units that are followed immediately by
  • students doing more experimentation on their own in Dr. Racket, learning from the experiments and learning find information about language features as they need them.

This change will require me to package my notes differently and also to create triggers and scaffolding for the students' experimentation before coming to class. I'm thinking of this as something like a flipped classroom, but with "watching videos" replaced by "playing with code".

Finally, this blog post triggered a latent desire to make the course more effective for all students, wherever they are on the learning curve. Many students come to the course at roughly same level of experience and comfort, but a few come in struggling from their previous courses, and a few come in ready to take on bigger challenges. Even those broad categories are only approximate equivalence classes; each student is at a particular point in the development we hope for them. I'd like to create experiences that can help students all of these students learn something valuable for them.

I've only begun to think about the ideas in that post. Right now, I'm contemplating two of ideas from the section on getting to know my students better: gathering baseline data early on that I can use to anchor the course, and viewing grading as planning. Anything that can turn the drudgery of grading into a productive part of the course for me is likely to improve my experience in the course, and that is likely to improved my students' experience, too.

I have more questions than answers at this point. That's part of the fun of re-designing a course. I expect that things will take better shape over the next six weeks or so. If you have any suggestions, email me or tweet to me at @wallingf.

Posted by Eugene Wallingford | Permalink | Categories: Patterns, Teaching and Learning

November 05, 2017 9:42 AM

One Way I'm Like Maurice Sendak

In this conversation, the interviewer asked Maurice Sendak, then age eighty-three, how long he could work in one stretch. The illustrator said that two hours was a long stretch for him.

Because I'm older, I get tired and nap. I love napping. Working and napping and reading and seeing my students. They're awfully nice. They're young and they're hopeful.

I'm not quite eighty-three, but I agree with every sentence in Sendak's answer. I could do worse than be as productive and as cantankerous for as long as he was.

Posted by Eugene Wallingford | Permalink | Categories: General, Personal