Knowing and Doing

Last night I attended my daughter's high school orchestra concert. (She plays violin.) Early on I found myself watching the conductor rather than the performers. He was really into the performance, as many conductors are. He's a good teacher and gets pretty good sound out of a few dozen teenagers. Surely he must be proud of their performance, and at least a little proud of his own.

Maybe it's just the end of another academic year, but my next thought was, "This concert will be over in an hour." My mind flashed to a movie from the 1990s, Mr. Holland's Opus. What does the conductor feel like when it's over? Is there a sense of emptiness? What does he think about, knowing that he'll being doing this all again next year, just as he did last year? The faces will change, and maybe the musical selections, but the rest will be eerily familiar.

Then it occurred to me: This is the plight of every teacher. It is mine.

Sometimes I envy people who make things for a living. They create something that people see and use. In the case of software, they may have the opportunity to grow their handiwork, to sustain it. It's tangible. It lasts, at least for a while.

Teachers live in a different world. I think about my own situation, teaching one class a semester, usually in our upper division. Every couple of years, I see a new group of students. I have each of them in class once or twice, maybe even a few times. Then May comes, and they graduate.

To the extent that I create anything, it resides in someone else. In this way, being a teacher less like being a writer or a creator and more like being a gardener. We help prepare others to make and do.

Like gardeners, we plant seeds. Some fall on good soil and flourish. Some fall on rocks and die. Sometimes, you don't even know which is which; you find out only years later. I have been surprised in both ways, more often pleasantly than not.

Sure, we build things, too. We CS profs write software. We university profs build research programs. These are tangible products, and they last for a while.

(We administrators create documents and spreadsheets. Let's not go there.)

But these products are not our primary task, at least not at schools like mine. It is teaching. We help students exercise their minds and grow their skills. If we are lucky, we change them in ways that go beyond our particular disciplines.

There is a different sort of rhythm to being a teacher than to being a maker. You need to be able to delay gratification, while enjoying the connections you make with students and ideas. That's one reason it's not so easy for just anyone to be a teacher, at least not for an entire career. My daughter's orchestra teacher seems to have that rhythm. I have been finding this rhythm over the course of my career, without quite losing the desire also to make things I can touch and use and share.

I am putting the wrap on spring semester, so that I can get down to summer duties and prep for fall teaching. Here are a few lessons I learned this spring.

•  A while back, I wrote briefly about re-learning the value of a small source language for the course. If I want to add a construct or concept, then I need also to subtract a corresponding load from language. In order to include imperative features, I need to eliminate recursive functions, or perhaps eliminate functions altogether. Eliminating recursion may be sufficient, as branching to a function is not much more complex than branching in loops. It is the stack of activation records that seems to slow down most students.

•  Using a free on-line textbook worked out okay. The main problem was that this particular book contained less implementation detail than books we have used in the past, such as Louden, and that hurt the students. We used Louden's TM assembly language and simulator, and the support I gave them for that stage of the compiler in particular was insufficient. The VM and assembly language themselves are simple enough, but students wanted more detailed examples of a code generator than I gave them.

•  I need to teach code generation better. I felt that way as the end of the course approached, and then several students suggested as much in our final session review. This is the most salient lesson I take from this iteration of the course.

I'm not sure at this moment if I need only to do a better job of explaining the process or if I need a different approach to the task more generally. That's something I'll need to think about between now and next time. I do think that I need to show them how to implement function calls in a bit more detail. Perhaps we could spend more time in class with statically-allocated activation records, and then let the students extend those ideas for a run-time stack and recursion.

•  For the first time ever, a few students suggested that I require something simpler than a table-driven parser. Of course, I can address several issues with parsing and code generation by using scaffolding: parser generators, code-generation frameworks and the like. But I still prefer that students write a compiler from scratch, even if only a modest one. There is something powerful in making something from scratch. A table-driven parser is a nice blend of simplicity (in algorithm) and complexity (in data) for learning how compilers really work.

I realize that I have to draw the abstraction line somewhere, and even after several offerings of the course I'm ready to draw it there. To make that work as well as possible, I may have to improve parts of the course to make it work better.

•  Another student suggestion that seems spot-on is that, as we learn each stage of the compiler, we take some time to focus on specific design decisions that the teams will have to make. This will alway them, as they said in their write-ups, "to make informed decisions". I do try to introduce key implementation decisions that they face and offer advice on how to proceed. Clearly I can do better. One way, I think, is to connect more directly with the programming styles they are working in.

~~~~

As usual, the students recognized some of the same shortcomings of the course that I noticed and suggested a couple more that had not occurred to me. I'm always glad I ask for their feedback, both open and anonymous. They are an indispensable source of information about the course.

Writing your first compiler is a big challenge. I can't help but recall something writer Samuel Delany said when asked if he "if it was fun" to write a set of novellas on the order of Eliot's The Waste Land, Pound's The Cantos, and Joyce's Ulysses:

No, not at all. ... But at least now, when somebody asks, "I wonder if Joyce could have done all the things he's supposed to have done in Ulysses," I can answer, "Yes, he could have. I know, because I tried it myself. It's possible."

Whatever other virtues there are in learning to write a compiler, it is valuable for computer science students to take on big challenges and know that it is possible to meet the challenge, because they have tried it themselves.

After an award-winning author had criticized popular literature, Stephen King responded with advice that is a useful reminder to us all:

Get busy. You have a short life span. You need to stop this crap about sitting there and talking about what we do, and actually do it. Because God gave you some talent, but he also gave you a certain number of years.

You don't have to be an award-winning author to waste precious time commenting on other people's work. Anyone with a web browser can fill his or her day talking about stuff, and not actually making stuff. For academics, it is a professional hazard. We need to balance the analytic and the creative. We learn by studying others' work and writing about it, but we also need to make time to make.

(The passage above comes from Stephen King, The Art of Fiction No. 189, in the wonderful on-line archive of interviews from the Paris Review.)

Recently, @fogus tweeted:

I wonder if McCarthy had to deal with complaints of parentheses count in the earliest Lisps?

For me, this tweet immediately brought to mind Ward Cunningham's experiment with file signatures as an aid in browsing unfamiliar code, which he presented at a workshop on "software archeology" at OOPSLA 2001. In his experiment, Ward collapsed each file in the Java 1.3 source code distribution into a single line consisting of only braces, quotes, and semicolons. For example, the AWT class java.awt.peer.ComponentPeer looked like this:

    ;;;;;;;;{;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;} 

while java.awt.print.PageFormat looked like this:

    {;{;;}{;;};}{;;{;}{;};}{;;{;}{;};}{;{;;;;;;"";};}{;{;;;;;;"";};}{;{;}{;};}{;{;}{;};}{}{}{;}{;}{{;}{;}}{;}{;;;;;;}{}{;{;;;;;;;;;;;;;;;;;;;;;;};}}

As Ward said, it takes some time to get use to the "radical summarization" of files into such punctuation signatures. He was curious about how such a high-level view of a code base might help a programmer understand the regularities and irregularities in the code, via an interactive process of inspection and projection.

Perhaps this came to mind as a result of experiences I had when I was first learning to program in Scheme. Coming from other languages with more syntax, I developed a bad habit of writing code like this:

    (define factorial
      (lambda (n)
        (if (zero? n)
            1
            (* n (factorial (- n 1)))
        )))

When real Scheme and Lisp programmers saw my code, they suggested that I put those closing parens at the end of the multiplication line. They were even more insistent when I dropped closing parens onto separate lines in the middle of a larger piece of code, say, with a let expression of several complex values. I objected that the line breaks helped me to see the structure of my code better. They told me to trust them; after I had more experience, I wouldn't need the help, and my code would be cleaner and more idiomatic.

They were right. Eventually, I learned to read Scheme code more like real Schemers do. I found myself drawn to the densest parts of the code, in which those closing parens often played a role, and learned to see that that's where the action usually was.

I think it was the connection between counting parentheses and the structure of code that brought to mind Ward's work. And then I wondered what it would be like to take the signature of Lisp or Scheme code in terms of its maligned primary punctuation, the parentheses?

In a few spare minutes, I fiddled with the I idea. As an example, consider the following Lisp function, which is part of an implementation of CLOS written by Patrick Henry Winston and Berthold Horn to support their AI and Lisp textbooks:

    (defun call-next-method ()
      (if *around-methods*
          (apply (pop *around-methods*) *args*)
        (progn
          (do () ((endp *before-methods*))
            (apply (pop *before-methods*) *args*))
          (multiple-value-prog1
              (if *primary-methods*
                  (apply (pop *primary-methods*) *args*)
                (error "Oops, no applicable primary method!")) 
            (do () ((endp *after-methods*))
              (apply (pop *after-methods*) *args*))))))

Collapsing this function into a single line of parentheses results in:

    (()((())((()(())(()))(((())())(()(())(()))))))

The semicolons in Java code give the reader a sense of the code's length; collapsing Lisp in this way loses the line breaks. So I wrote another function to insert a | where the line breaks had been, which results in:

    (()|(|(())|(|(()(())|(()))|(|(|(())|())|(()(())|(()))))))

This gives a better idea of how the code plays out on the page, but it loses all sense of the code's structure, which is so important when reading Lisp. So I implemented a third signature, one that surrenders the benefit of a single line in exchange for a better sense of structure. This signature preserves leading white space and line breaks but otherwise gives us just the parentheses:

    (()
      (
          (())
        (
          (()(())
          (()))
          (
            (
           (())
               ())
        (()(())
          (()))))))

Interesting. It's almost art.

I think there is a lot of room left to explore here in terms of punctuation. To capture the nature of Scheme and Lisp programs, we would probably want to include other characters, such as the hash, the comma, quotes, and backquotes. These would expose macro-related expressions to the human reader. To expand the experiment to include Clojure, we would of course want to include [] and {} in the signatures.

I'm not an every-day Schemer, so I am not sure how much either the flat signatures or the structured signatures would help seasoned Lisp or Scheme programmers develop an intuitive sense of a function's size, complexity, and patterns. As Ward's experiment showed, the real value comes when signing entire files, and for that task flat signatures may have more appeal. It would be neat to apply this idea to a Lisp distribution of non-trivial size -- say, the full distribution of Racket or Clojure -- and see what might be learned.

I'll Have Another was not highly sought after as a yearling, when he was purchased for the relatively small sum of $11,000.

On Saturday, I'll Have Another rallied down the stretch to win the 2012 Kentucky Derby, passing Bodemeister, one of the race favorites that had led impressively from the gate. Afterward, a television commentator asked the horse's trainer, "What did you and the owner see in the horse way back that made you want to buy it?" The trainer's answer was unusually honest. He said something to the effect,

We buy a lot of horses. Some work out, and some don't. There is a lot of luck involved. You do the right things and see what happens.

This is as a good an example as I've heard in a while of the relationship between quantity and quality, which my memory often connects with stories from the book Art and Fear. People are way too fond of mythologizing successes and then romanticizing the processes that lead to them. In most vocations and most avocations, the best way to succeed is to do the right things, to work hard, be unlucky a lot, and occasionally get lucky.

This mindset does not to diminish the value of hard work and good practices. No, it exalts their value. What it diminishes is our sense of control over outcomes in a complex world. Do your best and you will get better. Just keep in mind that we often have a lot less control over success and failure than our mythology tends to tell us.

In recent years, it is becoming even more common for people to think of students as "paying customers" at the university. People inside of universities, especially the teachers, have long tried to discourage this way of thinking, but it is becoming much harder to make the case. Students and parents are being required to shoulder an ever larger share of the bill for higher education, and with that comes a sense of ownership. Still, educators can't help but worry. The customer isn't always right.

Rob Miles relates a story that might help us make the case:

You can join a gym to get fit, but just joining doesn't make you fit. It simply gives you access to machinery and expertise that you can use to get fit. If you fail to listen to the trainer or make use of the equipment then you don't get a better body, you just get poorer.

You can buy all the running shoes you like, but if you never lace them up and hit the road, you won't become a runner.

I like this analogy. It also puts into perspective a relatively recent phenomenon, the assertion that software developers may not need a university education. Think about such an assertion in the context of physical fitness:

A lot of people manage to get in shape physically without joining a gym. To do so, all you need is the gumption (1) to learn what they need to do and (2) to develop and stick to a plan. For example, there is a lot of community support among runners, who are willing to help beginners get started. As runners become part of the community, they find opportunities to train in groups, share experiences, and run races together. The result is an informal education as good as most people could get by paying a trainer at a gym.

The internet and the web have provided the technology to support the same sort of informal education in software development. Blogs, user groups, codeathons, and GitHub all offer the novice opportunities to get started, "train" in groups, share experiences, and work together. With some gumption and hard work, a person can become a pretty good developer on his or her own.

But it takes a lot of initiative. Not all people who want to get in shape are ready or able to take control of their own training. A gym serves the useful purpose of getting them started. But each person has to do his or her own hard work.

Likewise, not all learners are ready to manage their own educations and professional development -- especially at age 18, when they come out of a K-12 system that can't always prepare them to be completely independent learners. Like a gym, a university serves the useful purpose of helping such people get started. And just as important, as at the gym, students have to do their own hard work to learn, and to prepare to learn on their own for the rest of their careers.

Of course, other benefits may get lost when students bypass the university. I am still idealistic enough to think that a liberal education, even a liberal arts education, has great value for all people. [ 1 | 2 | 3 ]. We are more than workers in an economic engine. We are human beings with a purpose larger than our earning potentials.

But the economic realities of education these days and the concurrent unbundling of education made possible by technology mean that we will have to deal with issues such as these more and more in the coming years. In any case, perhaps a new analogy might help us help people outside the university understand better the kind of "customer" our students need to be.

(Thanks to Alfred Thompson for the link to Miles's post.)

I have not finished grading my students' compilers yet. I haven't even looked at their public comments about the project. (Anonymous feedback comes later in the summer when course assessment data arrives.) Still, one lesson has risen to the surface:

Keep the source language small. No, really.

I long ago learned the importance of assigning a source language small enough to be scanned, parsed, and translated completely in a single semester. Over the years, I had pared the languages I assigned down to the bare essentials. That leaves a small language, one that creates some fun programming challenges. But it's a language that students can master in fifteen weeks.

My students this term were all pretty good programmers, and I am a weak man. So I gave in to the temptation to add just a few of more features to the language, to make it a bit more interesting for my students: variables, an assignment statement, a sequence construct, and a single loop form. It was as if I had learned nothing from all my years teaching this course.

The effect of processing a larger language manifested itself in an expected way: the more students have to do, the more likely that they won't get it all done. This affected a couple of the teams more than the others, but it wasn't so bad. It meant that some teams didn't get as far along with function calls and with recursion than we had hoped. Getting a decent subset of such a language running is still an accomplishment for students.

But the effect of processing a larger language manifested itself in a way I did not expect, too, one more detrimental to student progress: a "hit or miss" quality to the correctness of their implementations. One team had function calls mostly working, but not recursion. Another team had tail recursion mostly working(!), but ordinary function calls didn't work well. One team had local vars working fine but not global variables, while most teams knocked out globals early and, if they struggled at all, it was with locals.

The extra syntactic complexity in the language created a different sort of problems for the teams.

While a single new language feature doesn't seem like too much in isolation, but it interacts with all the existing features and all the other new features to create a much more complex language for the students to understand and for the parser to recognize and get right. Sure, our language had regular tokens and a context-free grammar, which localizes the information the scanner and parser need to see in order to do their jobs. Like all of us, though, students make errors when writing their code. In the more complex space, it is harder to track down the root cause of an error, especially when there are multiple errors present and complicate the search. (Or should I say complect?)

This is an important lesson in language design more generally, especially for a language aimed at beginners. But it also stands out when a compiler for the language is being written by beginning compiler writers.

I am chastened and will return to the True Path of Small Language the next time I teach this course.

Guile is a Scheme. It began life as GEL, which stood for GNU Extension Language. This brief history of Guile explains the change:

Due to a naming conflict with another programming language, Jim Blandy suggested a new name for GEL: "Guile". Besides being a recursive acronym, "Guile" craftily follows the naming of its ancestors, "Planner", "Conniver", and "Schemer". (The latter was truncated to "Scheme" due to a 6-character file name limit on an old operating system.) Finally, "Guile" suggests "guy-ell", or "Guy L. Steele", who, together with Gerald Sussman, originally discovered Scheme.

That is how you name a language, making it significant on at least three levels. Recursive acronyms are a staple of the GNU world, beginning with GNU itself. Guile recurses as the GNU Ubiquitous Intelligent Language for Extensions. Synonymny with Planner and Conniver keeps alive the historical connection to artificial intelligence, and is reinforced by the use of intelligent in the acronym. Finally, the homophonic connection to Steele is pure genius.

I bow to you, Mr. Blandy.

(While we are talking about words, I must say that I love the author's use of discovered in the passage quoted above. Most people say that Steele and Sussman "created" Scheme, or "designed" it, or "invented" it. But if you read Steele's and Gabriel's The Evolution of Lisp, you will see that discovery is a better label for what happened. Scheme was lurking in the implementation of Lisp's apply primitive and Carl Hewitt's theory of actors. Hewitt, of course, created Planner, which is another connection back to Guile.)

I'm beginning to look at the compilers my students produced this semester. I teach a relatively traditional compiler course; we want students to experience as many different important ideas as possible within the time constraints of a semester. As you might expect, my students' programs read in a text file and produce a text file. These files contain a high-level program and an assembly language program, respectively.

I love seeing all the buzz floating around non-textual languages and new kinds of programming environments such as Bret Victor's reactive documents and Light Table. Languages and environments like these make my traditional compiler course seem positively archaic. I still think the traditional course adds a lot of value to students' experience. Before you can think outside of the box, you have to start with a box.

These new programming ideas really are outside the confines of how we think about programs. Jonathan Edwards reminds us how tightly related languages and tools are:

As long as we are programming in descendants of assembly language, we will continue to program in descendants of text editors.

Edwards has been exploring this pool of ideas for a few years now. I first mentioned his work in this blog back in 2004. As he has learned, the challenge we face in trying to re-think how we program is complicated by the network of ideas in which we work. It isn't just syntax or language or IDE or support tools that we have to change. To change one in a fundamental way requires changing them all.

On top of that, once researchers create something new, we will have to find a way to migrate there. That involves education and lots of existing practitioners. Here's hoping that the small steps people are taking with Tangle and Light Table can help us bridge the gap.

The SIGCSE listserv has erupted today with its seemingly annual discussion of teaching recursion. I wrote about one of the previous discussions a couple of years ago. This year's conversation has actually included a couple of nice ideas, so it was worth following along.

Along the way, one prof commented on an approach he has seen used to introduce students to recursion, often in a data structures course. First you cover factorial, gcd, and the Fibonacci sequence. Then you cover the Towers of Hanoi and binary search. Unfortunately, such an approach is all too common. The poster's wistful analysis:

Of the five problems, only one (binary search) is a problem students might actually want to solve. Only two (Fibonacci and Hanoi) are substantially clearer in recursive than iterative form, and both of them take exponential time. In other words, recursion is a confusing way to solve problems you don't care about, extremely slowly.

Which, frankly, I think is the lesson [some CS profs] want to convey.

And this on a day when I talked with my compiler students about how a compiler can transform many recursive programs into iterative ones, and even eliminate the cost of a non-recursive function call when it is in a tail position.

The quoted passage contains my favorite line of the week thus far: In other words, recursion is a confusing way to solve problems you don't care about, extremely slowly. If that's not the message you want to convey to your students, then please don't introduce them to recursion in this way. If that is the message you want to send to your students, then I am sad for you, but mostly for your students.

I sometimes wonder about the experiences that some computer scientists bring to the classroom. It only takes a little language processing to grok the value of recursion. And a data structures course is a perfectly good place for students to see and do a little language processing. Syntax, abstract or not, is a great computer science example of trees. And students get to learn a little more CS to boot!