The last talk I attended at StrangeLoop 2012 was Bret Victor's Visible Programming. He has since posted an extended version of his presentation, as a multimedia essay titled Learnable Programming. You really should read his essay and play the video in which he demonstrates the implementation of his ideas. It is quite impressive, and worthy of the discussion his ideas have engendered over the last few months.
In this entry, I give only a high-level summary of the idea, react to only one of his claims, and discuss only one of his design principles in ay detail. This entry grew much longer than I originally intended. If you would like to skip most of my reaction, jump to the mini-essay that is the heart of this entry, Programing By Reacting, in the REPL.
Programmers often discuss their productivity as at least a partial result of the programming environments they use. Victor thinks this is dangerously wrong. It implies, he says, that the difficulty with programming is that we aren't doing it fast enough.
But speed is not the problem. The problem is that our programming environments don't help us to think. We do all of our programming in our minds, then we dump our ideas into code via the editor.
Our environments should do more. They should be our external imagination. They should help us see how our programs work as we are writing them.
This is an attractive guiding principle for designing tools to help programmers. Victor elaborates this principle into a set of five design principles for an environment:
As I watched the talk, I found myself reacting in a way I had not expected. So many people have spoken so highly of this work. The crowd was applauding! Why was I not as enamored? I was impressed, for sure, and I was thinking about ways to use these ideas to improve my teaching. But I wasn't falling head over heels in love.
A Strong Claim
First, I was taken aback by a particular claim that Victor made at the beginning of his talk as one of the justifications for this work:
If a programmer cannot see what a program is doing, she can't understand it.
Unless he means this metaphorically, seeing "in the mind's eye", then it is simply wrong. We do understand things we don't see in physical form. We learn many things without seeing them in physical form. During my doctoral study, I took several courses in philosophy, and only rarely did we have recourse to images of the ideas we were studying. We held ideas in our head, expressed in words, and manipulated them there.
We did externalize ideas, both as a way to learn them and think about them. But we tended to use stories, not pictures. By speaking an idea, or writing it down, and sharing it with others, we could work with them.
So, my discomfort with one of Victor's axioms accounted for some of my unexpected reaction. Professional programmers can and do manipulate ideas abstractly. Visualization can help, but when is it necessary, or even most helpful?
Learning, Versus Doing
This leads to a second element of my concern. I think I had a misconception about Victor's work. His talk and its title, "Visible Programming", led me to think his ideas are aimed primarily at working programmers, that we need to make programs visible for all programmers.
The title of his essay, "Learnable Programming", puts his claims into a different context. We need to make programs visible for people who are learning to program. This seems a much more reasonable position on its face. It also lets me see the axiom that bothered me so much in a more sympathetic light: If a novice programmer cannot see what a program is doing, then she may not be able to understand it.
Seeing how a program works is a big part of learning to program. A few years ago, I wrote about "biction" and the power of drawing a picture of what code does. I often find that if I require a student to draw a picture of what his code is doing before he can ask me for debugging help, he will answer his own question before getting to me.
The first time a student experiences this can be a powerful experience. Many students begin to think of programming in a different way when they realize the power of thinking about their programs using tools other than code. Visible programming environments can play a role in helping students think about their programs, outside their code and outside their heads.
I am left puzzling over two thoughts:
Mark Guzdial has written a more detailed analysis of Victor's essay from the perspective of a computer science educator. As always, Mark's ideas are worth reading.
My favorite parts of this talk were the sections on creating by reacting and abstracting. Programmers, Victor says, don't work like other creators. Painters don't stare at a blank canvas, think hard, create a painting in their minds, and then start painting the picture they know they want to create. Sculptors don't stare at a block of stone, envision in their mind's eye the statue they intend to make, and then reproduce that vision in stone. They start creating, and react, both to the work of art they are creating and to the materials they are using.
Programmers, Victor says, should be able to do the same thing -- if only our programming environments helped us.
As a teacher, I think this is an area ripe for improvement in how we help students learn to program. Students open up their text editor or IDE, stare at that blank screen, and are terrified. What do I do now? A lot of my work over the last fifteen to twenty years has been in trying to find ways to help students get started, to help them to overcome the fear of the blank screen.
My approaches haven't been through visualization, but through other ways to think about programs and how we grow them. Elementary patterns can give students tools for thinking about problems and growing their code at a scale larger than characters or language keywords. An agile approach can help them start small, add one feature at a time, proceed in confidence with working tests, and refactor to make their code better as they go along. Adding Victor-style environment support for the code students write in CS1 and CS2 would surely help as well.
However, as I listened to Victor describe support for creating by reacting, and then abstracting variables and functions out of concrete examples, I realized something. Programmers don't typically write code in an environment with data visualizations of the sort Victor proposes, but we do program in the style that such visualizations enable.
We do it in the REPL!
A simple, interactive computer programming environment enables programmers to create by reacting.
Programmers from the Lisp and Smalltalk communities, and from the rest of the dynamic programming world, will recognize this style of programming. It's what we do, a form of creating by reacting, from concrete examples in the interaction pane to code in the definitions pane.
In the agile software development world, test-first development encourages a similar style of programming, from concrete examples in the test case to minimal code in the application class. Test-driven design stimulates an even more consciously reactive style of programming, in which the programmer reacts both to the evolving program and to the programmer's evolving understanding of it.
The result is something similar to Victor's goal for programmers as they create abstractions:
The learner always gets the experience of interactively controlling the lower-level details, understanding them, developing trust in them, before handing off that control to an abstraction and moving to a higher level of control.
It seems that Victor would like to perform even more support for novices than these tools can provide, down to visualizing what the program does as they type each line of code. IDEs with autocomplete is perhaps the closest analog in our current arsenal. Perhaps we can do more, not only for novices but also professionals.
I love the idea that our environments could do more for us, to be our external imaginations.
Like many programmers, though, as I watched this talk, I occasionally wondered, "Sure, this works great if you creating art in Processing. What about when I'm writing a compiler? What should my editor do then?"
Victor anticipated this question and pre-emptively answered it. Rather than asking, How does this scale to what I do?, we should turn the question inside out and ask, These are the design requirements for a good environment. How do we change programming to fit?
I doubt such a dogmatic turn will convince skeptics with serious doubts about this approach.
I do think, though, that we can reformulate the original question in a way that focuses on helping "real" programmers. What does a non-graphical programmer need in an external imagination? What kind of feedback -- frequent, even in-the-moment -- would be most helpful to, say, a compiler writer? How could our REPLs provide even more support for creating, reacting, and abstracting?
These questions are worth asking, whatever one thinks of Victor's particular proposal. Programmers should be grateful for his causing us to ask them.
I have been using Racket since before it was Racket, back when it was "just another implementation of Scheme". Even then, though, it wasn't just another implementation of Scheme, because it had such great libraries, a devoted educational community around it, and an increasingly powerful facility for creating and packaging languages. I've never been a deep user of Racket, though, so I was eager to see this talk by one of its creators and learn from him.
Depending on your perspective, Racket is either a programming language (that looks a lot like Scheme), a language plus a set of libraries, or a platform for creating programs. This talk set out to show us that Racket is more.
Flatt opened with a cute animated fairy tale, about three princesses who come upon a wishing well. The first asks for stuff. The second asks for more wishes. The third asks for a kingdom full of wishing wells. Smart girl, that third one. Why settle for stuff when you can have the source of all stuff?
This is, Flatt said, something like computer science. There is a similar progression of power from:
Computer scientists wish for a way to write programs that do... whatever.
This is the Racket way:
The rest of the talk was a series of impressive mini-demos that illustrated each part of the Racket way.
To show what it means to say that everything is a program, Flatt demoed Scribble, a language for producing documents -- even the one he was using to give his talk. Scribble allows writers to abstract over every action.
To show what it means to say that concepts are programming language constructs, Flatt talked about the implementation of Dr. Racket, the flexible IDE that comes with the system. Dr. Racket needs to be able to create, control, and terminate processes. Relying on the OS to do this for it means deferring to what that OS offers. In the end, that means no control.
Dr. Racket needs to control everything, so the language provides constructs for these concepts. Flatt showed as examples threads and custodians. He then showed this idea at work in an incisive way: he wrote a mini-Dr. Racket, called Racket, Esq. -- live using Racket. To illustrate its completeness, he then ran his talk inside racket-esq. Talk about a strange loop. Very nice.
To show what it means to say that programming languages are extensible and composable, Flatt showed a graph of the full panoply of Racket's built-in languages and demoed several languages. He then used some of the basic language-building tools in Racket -- #lang, require, define-syntax, syntax-rules, and define-syntax-rule -- to build the old text-based game Adventure, which needs a natural language-like scripting language for defining worlds. Again, very nice -- so much power in so many tools.
This kind of power comes from taking seriously a particular way of thinking about the world. It starts with "Everything is a program." That is the Racket way.
Flatt is a relaxed and confident presenter. As a result, this was a deceptively impressive talk. It reinforced its own message by the medium in which it was delivered: using documents -- programs -- written and processed in Racket. I am not sure how anyone could see a slideshow with "hot" code, a console for output, and a REPL within reach, all written in the environment being demoed, and not be moved to rethink how they write programs. And everything else they create.
As Flatt intimated briefly early on, The Racket Way of thinking is not -- or should not be -- limited to Racket. It is, at its core, the essence of of computer science. The duality of code and data makes what we do so much more powerful than most people realize, and makes what we can do so much more powerful than most us actually do with the tools we accept. I hope that Flatt's talk inspires a few more of us not to settle for less than we have to.
I don't know if it was coincidence or by design of the conference organizers, but Wednesday morning was a topical repeat of Tuesday morning for me: two highly engaging talks on functional programming. I had originally intended to write them up in a single entry, but that write-up grew so long that I decided to give them their own entries.
Watching talks and reading papers about the Y combinator are something of a spectator code kata for me. I love to see new treatments, and enjoy seeing even standard treatments every now and then. Jim Weirich presented it at StrangeLoop with a twist I hadn't seen before.
Weirich opened, as speakers often do, with him. This is a motivational talk, so it should be...
But it will be, he promises, fun!
Before diving in, he had one more joke, or at least the first half of one. He asked for audience participation, then asked his volunteer to calculate cos(n) for some value of n I missed. Then he asked the person to keep hitting the cosine button repeatedly until he told him to stop.
At the dawn of computing, to different approaches were taken in an effort to answer the question, What is effectively computable?
Alan Turing devised what we now call a universal Turing machine to embody the idea. Weirich showed a video demonstration of a physical Turing machine to give his audience a sense of what a TM is like.
(If you'd like to read more about Turing and the implication of his universal machine, check out this reflection I wrote earlier this year after a visit by Doug Hofstadter to my campus. Let's just say that the universal TM means more than just an answer to what functions are effectively computable.)
A bit ahead of Turing, Alonzo Church devised an answer to the same question in the form of the lambda calculus, a formal logical system. As with the universal TM, the lambda calculus can be used to compute everything, for a particular value of eveything. These days, nearly every programming language has lambdas of some form
... now came the second half of the joke running in the background. Weirich asked his audience collaborator what was in his calculator's display. The assistant called out some number, 0.7... Then Weirich showed his next slide -- the same number, taken out many more digits. How was he able to do this? There is a number n such that cos(n) = n. By repeatedly pressing his cosine button, Weirich's assistant eventually reached it. That number n is called the fixed point of the cosine function. Other functions have fixed points to, and they can be a source of great fun.
Then Weirich opened up his letter and wrote some code from the ground up to teach some important concepts of functional programming, using the innocuous function 3(n+1). With this short demo, Weirich demonstrated the idea of a higher-order function, including function factories, a set of useful functional refactorings that included
At the end of his exercise, Weirich had created a big function call that contained no named function definitions yet computed the same answer.
He asks the crowd for applause, then demurs. This is 80-year-old technology. Now you know, he says, what a "chief scientist" at New Context does. (Looks a lot like what an academic might do...)
Weirich began a second coding exercise, the point behind all his exposition to this point: He wrote the factorial function, and began to factor and refactor it just as he had the simpler 3(n+1). But now inlining the function breaks the code! There is a recursive call, and the name is now out of scope. What to do?
He refactors, and refactors some more, until the body of factorial is an argument to a big melange of lambdas and applications of lambdas. The result is a function that computes the fixed point of any function passed it.
That is Y. The Y combinator.
Weirich talked a bit about Y and related ideas, and why it matters. He closed with a quote from Wittgenstein, from Philosophical Investigations:
The aspects of things that are most important for us are hidden because of their simplicity and familiarity. (One is unable to notice something -- because it is always before one's eyes.) The real foundations of his enquiry do not strike a man at all. Unless that fact has at some time struck him. -- And this means: we fail to be struck by what, once seen, is most striking and most powerful.
The thing that sets Weirich's presentation of Y apart from the many others I've seen is its explicit use of refactoring to derive Y. He created Y from a sequence of working pieces of code, each the result of a refactoring we can all understand. I love to do this sort of thing when teaching programming ideas, and I was pleased to see it used to such good effect on such a challenging idea.
The title of this talk -- Y Not? -- plays on Y's interrogative homonym. Another classic in this genre echos the homonym in its title, then goes on to explain Y in four pages of English and Scheme. I suggest that you study @rpg's essay while waiting for Weirich's talk to hit InfoQ. Then watch Weirich's talk. You'll like it.
Most of the Tuesday afternoon talks engaged me less deeply than the ones that came before. Part of that was the content, part was the style of delivery, and part was surely that my brain was swimming in so many percolating ideas that there wasn't room for much more.
Oleg Kiselyov, a co-author of the work behind yesterday's talk on miniKanren, gave a talk on how to implement guessing in computer code. That may sound silly, for a couple of reasons. But it's not.
First, why would we want to guess at all? Don't we want to follow principles that guarantee we find the right answer? Certainly, but those principles aren't always available, and even when they are the algorithms that implement them may be computationally intractable. So we choose to implement solutions that restrict the search space, for which we pay a price along some other dimension, often expressiveness.
Kiselyov mentioned scheduling tasks early in his talk, and any student of AI can list many other problems for which "generate and test" is a surprisingly viable strategy. Later in the talk, he mentioned parsing, which is also a useful example. Most interesting grammars have nondeterministic choices in them. Rather than allow our parsers to make choices and fail, we usually adopt rules that make the process predictable. The result is an efficient parser, but a loss in what we can reasonably say in the language.
So, perhaps the ability to make good guesses is valuable. What is so hard about implementing them? The real problem is that there are so many bad guesses. We'd like to use knowledge to guide the process of guessing again, to favor some guesses over others.
The abstract for the talk promises a general principle on which to build guessing systems. I must admit that I did not see it. Kiselyov moved fast at times through his code, and I lost sight of the big picture. I did see discussions of forking a process at the OS level, a fair amount of OCaml code, parser combinators, and lazy evaluation. Perhaps my attention drifted elsewhere at a key moment.
The speaker closed his talk by showing a dense slide and saying, "Here is a list of buzzwords, some of which I said in my talk and some of which I didn't say in my talk." That made me laugh: a summary of a talk he may or may not have given. That seemed like a great way to end a talk about guessing.
I don't know much about the details of Akka. Many of my Scala-hacking former students talk about it every so often, so I figured I'd listen to this quick tour and pick up a little more. The underlying idea, of course, is Hewitt's Actor model. This is something I'm familiar with from my days in AI and my interest in Smalltalk.
The presenter, Akka creator Jonas Boner, reminded the audience that Actors were a strong influence on the original Smalltalk. In many ways, it is truer to Kay's vision of OOP than the languages we use today.
This talk was a decent introduction to Hewitt's idea and its implementation in Akka. My two favorite things from the talk weren't technical details, but word play:
We have made some optimizations to random.Ah, aren't we all looking for those?
Expressiveness and Abstraction
This talk by Ola Bini was a personal meditation on the expressiveness of language. Bini, whose first slide listed him as a "computational metalinguist", started from the idea that, informally, the expressiveness of a language is inversely proportional to the distance between our thoughts and the code we have to write in that language.
In the middle part of the talk, he considered a number of aspects of expressiveness and abstraction. In the latter part, he listed ideas from natural language and wondered aloud what their equivalents would be in programming languages, among them similes, metaphors, repetition, elaboration, and multiple equivalent expressions with different connotations.
During this part of the talk, my mind wandered, too, to a blog entry I wrote about parts of speech in programming languages back in 2003, and a talk by Crista Lopes at OOPSLA that year. Nouns, verbs, pronouns, adjectives, and adverbs -- these are terms I use metaphorically when teaching students about new languages. Then I thought about different kinds of sentence -- declarative, interrogative, imperative, and exclamatory -- and began to think about their metaphorical appearances in our programming languages.
Another fitting way for a talk to end: my mind wondering at the end of a wondering talk.
Tuesday morning kicked off with a keynote address by Jeff Hawkins entitled "Computing Like The Brain". Hawkins is currently with Numenta, a company he co-founded in 2005, after having founding the Redwood Neuroscience Institute and two companies most technophiles will recognize: Palm and Handspring.
Hawkins said he has devoted his professional life to understanding machine science. He recalls reading an article by Francis Crick in Scientific American as a youth and being inspired to study neuroscience. It was a data-rich, theory-poor discipline, one crying out for abstractions to unify our understanding of how the brain works from the mass of data we were collecting. He says he dedicated life then to discovering principles of how the brain works, especially the neocortex, and to build computer systems that implement these principles.
The talk began with a primer on the neocortex, which can be thought of as a predictive modeling system to controls human intelligence. If we take into account all the components of what we think of as our five senses, the brain has millions of sensors that constantly stream data to the neocortex. Its job is to build an on-line model from this streaming data. It constantly predicts what he expects to receive next, detects anomalies, updates itself, and produces actions. When the neocortex updates, we learn.
On this view, the brain doesn't "compute". It is a memory system. (I immediately thought of Roger Schank, his views on AI, and case-based reasoning...) The brain is really one memory algorithm operating over all of our sensory inputs. The key elements of this memory system are:
Hawkins spoke briefly about hierarchy and sequence memory, but he quickly moved into the idea of sparse distributed representation (SDR). This can be contrasted to the dense, localized memory of traditional computer systems. For example, ASCII code consists of seven bits, all combinations of which we use to represent a single character. Capital 'A' is 65, or 1000001; the digit '5' is 55, or 0110111. The coincidence of '5' and 55 notwithstanding, the individual bits of an ASCII code don't mean anything. Change one bit, and you get a different character, sometimes a very different one.
An SDR uses a large number of bits, with only a few set to 1. Hawkins said that typically only ~ 2% of the bits are "on". Each bit in an SDR has specific meaning, one that has been learned through memory updating, not assigned. He then demonstrated several properties of an SDR, such as how it can be used to detect similarities, how it can do "store-and-compare" using only indices, and how it can perform remarkably well using on a sampling of the indices. Associative look-up in the brain's SDR produces surprisingly few errors, and those tend to be related to the probe, corresponding to similar situations encountered previously.
The first takeaway point of the talk was this: Intelligent systems of the future will be built using sparse distributed representation.
At this point, my note-taking slowed. I am not a biologist, so most of what Hawkins was describing lies far outside my area of expertise. So I made a master note -- gotta get this guy's book! -- and settled into more focused listening.
One phrase that made me smile later in the talk was the semantic meaning of the wrongness. Knowing why something is wrong, or how, is a huge step up on "just" being wrong. Hawkins referred to this in particular as part of the subtlety of making predictions.
To close, Hawkins offered some conjectures. He thinks that the future of machine intelligence will depend on us developing more and better theory to explain how the brain works, especially in the areas of hierarchy and attention. The most compelling implementation will be an embodied intelligence, with embedded agents distributed across billions of sensors. We need better hardware in order to create faster systems. recall that the brain is more a memory systems than a computation device, so better memory is as or more important than better processors. Finally, we need to find a way to increase the level connectivity among components. Neurons have tens or hundreds of connections to other neurons, and these can be grown or strengthened dynamically. Currently, our computer chips are not good at this.
Where will breakthrough applications come from? He's not sure. In the past, breakthrough applications of technologies have not always been where we expected them.
I gotta read more. As a student of AI, I was never been all that interested in neurobiology or even its implications for my discipline. The cognitive level has always excited me more. But Hawkins makes an interesting case that the underlying technologies we need to reach the cognitive level will look more like our brains than today's computers.
The StrangeLoop program had a fair amount of functional programming talks, and I availed myself of two to complete the first morning of the conference.
Monad Examples for Normal People
The web is full of tutorials claiming to explain monads in a way that anyone can understand. If any of them had succeeded, we wouldn't need another. How could I not attend a talk claiming to slay this dragon?
Getz started out with a traditional starting point: a sequence of operations that can be viewed as composition of functions. That works great for standard business logic. But consider a common exceptional case: given a name, looking up an account number fails. This requires us to break the symmetry of the code with guards. These break composition, because now the return type of the function doesn't fit.
The Maybe monad factors these guards out of the business logic. If we further need to record and capture error coded, we can use the Error monad, which factors the same sort of plumbing out of the business logic and also serves as a facade for a tuple of value and error code.
After these simple examples, the speaker dove into the sort of exercise that tends to lose the interest of programmers in the trenches building apps: building a Lisp interpreter in Python, using monads to compose the elements of the interpreter. The environment consists of a combination of the reader monad and the writer monad; the interpreter consists of a combination of the environment and the error monad. Several other monads play a role in representing values, built-in procedures, state, and non-standard control operators. An interpreter is, he said, "monad heaven".
The best part of this talks message was in viewing a monad as a design pattern that abstracts repetitive plumbing out of applications in such a way that preserves function composition.
After the talk, someone asked a question to the effect, "I get by fine with macros and higher-order functions. When do I need monads?" Getz answered from his personal experience: monads enable him to write more elegant code, by factoring repetition that other tools could not reach as nicely.
This wasn't the monad explanation to end the need for new monad explanations, but it was a decent effort. With the Getz's focus on factoring code and the question mentioning macros, I could not help but think of this essay that presents monads in the light of code transformation, and Brian Marick's approach treating a monad as a macro. Perhaps we are getting near a metaphor for monads that will help "normal people" grok them without resorting to abstract abstract math.
Functional Design Patterns
From the moment I saw the StrangeLoop line-up, I was excited to see Stuart Sierra speak on functional design patterns. Sierra is one of the few prominent people in the Lisp and Clojure worlds to acknowledge the value of design patterns in functional style -- heck, even to acknowledge they exist.
He opened his talk in a way that confronted the view commonly held among Lispers, He conceded that, for many, "design pattern" is a loaded term, bringing to mind an OO cult and the ominous voice of the Gang of Four. The thing is, Sierra said, Design Patterns is a pretty good book, given the time it was written and the programming language community to which it. speaks. However, in the functional language community, the design patterns in that book are best known for being debunked by Peter Norvig in a 1998 tutorial.
Sierra reminded this audience that patterns can occur at all levels of a program. He pointed to a lower-profile patterns book of the mid-1990s, Pattern-Oriented Software Architecture (now a five-volume series), which organized patterns at multiple levels:
Sierra then went on to list, and describe briefly, several common patterns he has noticed in functional programs and used himself in Clojure. Like POSA, he organized them into categories. Before proceeding, he admitted to any Haskell programmers in the room that, yes, many of these patterns are monadic in nature.
I'd very much like to write about some of Sierra's patterns in greater detail than a single entry permits, including providing links to blog entries he and others have written about them. For now, let me list the ones I jotted down, in Sierra's categories:
Before describing Reduce/Combine, Sierra took a short digression to talk about MapReduce, a pattern accepted by many in the world of big data. He reminded us that this pattern is predicated on the spinning disk becoming the bottleneck of our system. In the future, this pattern will become less useful as other forces come to dominate our system architecture.
Two of the control flow patterns, Observer and Strategy, are held in common with the GoF catalog, though in the context of functional programming a few new variations become more obvious. It also seemed to me that Sierra's Wrapper is a lot like the GoF's Decorator, though he did not make an explicit connection.
As I wrote a couple of years ago, the time is right for functional design patterns. I'm so glad that Sierra has been documented patterns of this sort and articulating the value of thinking in terms of patterns. The key is not to look to OO programs for patterns of value to functional programmers, but to look at functional programs for recurring choices among design alternatives. (It's not too surprising that many OO design patterns don't mean much to functional programmers, just as it's not surprising that FP patterns dealing with, say, state are afterthoughts in the OO world.)
The first day of StrangeLoop was off to a great start.
The conference opened with a keynote address by Michael Stonebraker, who built Ingres, Postgres, and several other influential database systems. Given all the hubbub about NoSQL the last few years, including at StrangeLoop 2010, this talk brought some historical perspective to a conversation that has been dominated in recent years by youngsters. Stonebraker told the audience that the future is indeed here, but from the outside it will look a lot like the past
The problem, of course, is "big data". It's big because of volume, velocity, and variety. Stonebraker framed his opening comments in terms of volume. In the traditional database setting back in the 1980s, we all bought airplane tickets through a travel agent who acted, for all meaningful purposes, in the role of professional terminal operator. We were doing business "at the speed of the intermediary". The ACID properties were inviolable: "Don't you dare lose my data."
Then came change. The internet disintermediated access to database, cutting intermediaries out of the equation. Volume shot through the roof. PDAs further disintermediated access, removing limitations on the locations from which we accessed our data. Volume shot up even further. Suddenly, databases came to be part of the solution to a much broader class of problems: massively online games, ad placement, new forms of commerce. We all know what that meant for volume.
Stonebraker then offered two reality checks to frame the solution to our big data problems. The first involved the cost of computer memory. One terabyte is a really big database for transaction processing, yet it 1TB of memory now costs $25-50K. Furthermore, the price is dropping faster than transaction volume is rising. So: the big data problem is really now a problem for main memory.
The second reality check involved database performance. Well under 10% of the time spent by a typical database is spent doing useful work. Over 90% is overhead: managing a buffer pool, latching, locking, and recovery. We can't make faster databases by creating better DB data structures or algorithms; a better B-tree can affect only 4% of application runtime. If we could eliminate the buffer pool, we can gain up to 25% in performance. We must focus on overhead.
Where to start? We can forget about all the traditional database vendors. They have code lines that are thirty years old and older. They have to manage backward compatibility for a huge installed customer base. They are, from the perspective of the future, bloatware. They can't improve.
How about the trend toward NoSQL? We can just use raw data storage and write our own low-level code, optimized to the task. Well, the first thing to realize is that the compiler already translates SQL into lower-level operations. In the world of databases as almost everywhere else, it is really hard to beat the compiler at its game. High-level languages are good, and our compilers do an awesome job generating near-optimal code. Moving down an abstraction layer is, Stonebraker says, a fundamental mistake: "Always move code to the data, never data to the code."
Second, we must realize that the ACID properties really are a good thing. More important, they are nearly impossible to retrofit into a system that doesn't already provide them. "Eventually consistent" doesn't really mean eventually consistent if it's possible to sell your last piece of inventory. In any situation where there exists a pair of non-commutative transactions, "eventually consistent" is a recipe for corruption.
So, SQL and ACID are good. Let's keep them. Stonebraker says that instead of NoSQL databases, we should build "NewSQL" databases that improve performance through innovative architectures. Putting the database in main memory is one way to start. He addressed several common objections to this idea ("But what if the power fails??") by focusing on speed and replication. Recovery may be slow, but performance is wildly better. We should optimize for the most common case and treat exceptional cases for what they are: rare.
He mentioned briefly several other components of a new database architecture, such horizontally scaling across a cluster of nodes, automatic sharding, and optimization via stored procedures targeted at the most common activities. The result is not a general purpose solution, but then why does it need to be?
I have a lot of gray hair, Stonebraker said, but that means he has seen these wars before. It's better to stick with what we know to be valuable and seek better performance where our technology has taken us.
For my lunch break, I walked a bit outside, to see the sun and bend my knee a bit. I came back for a set of talks without an obvious common thread. After seeing the talks, I saw a theme: ideas for writing programs more conveniently or more concisely.
Data Structures and Hidden Code
The message of this talk by Scott Vokes is that your choice in data structures plays a big role in determining how much code you have to write. You can make a lot of code disappear by using more powerful data structures. We can, of course, generalize this claim from data structures to data. This is the theme of functional and object-oriented programming, too. This talk highlights how often we forget the lowly data structure when we think of writing less code.
As Vokes said, your choice in data structures sets the "path of least resistance" for what your program will do and also for the code you will write. When you start writing code, you often don't know what the best data structure for your application is. As long as you don't paint yourself into a corner, you should be able to swap a new structure in for the old. The key to this is something novice programmers learn early, writing code not in terms of a data structure but in terms of higher-level behaviors. Primitive obsession can become implementation obsession if you aren't careful.
The meat of this talk was a quick review of four data structures that most programmers don't learn in school: skip lists, difference list, rolling hashes, and jumpropes, a structure Vokes claims to invented.
This talk was a source of several good quote, including
The first two quotes there would make nice mottos for a debate between functional and OO programming. They also are two sides of the same coin, which destroys the premise of the debate.
As a Scheme programmer and a teacher of programming languages, I have developed great respect and fondness for the work of Dan Friedman over the last fifteen years. As a computer programmer who began his studies deeply interested in AI, I have long had a fondness for Prolog. How could I not go to the talk on miniKanren? This is a small implementation (~600 lines written in a subset of Scheme) of Kanren, a declarative logic programming system described in The Reasoned Schemer.
This talk was like a tag-team vaudeville act featuring Friedman and co-author William Byrd. I can't so this talk justice in a blog entry. Friedman and Byrd interleaved code demo with exposition as they
The cool endpoint of using logic programming to build the interpreter is that, by using variables in a specification, the interpreter produces legal programs that meet a given specification. It generates code via constraint resolution.
If that weren't enough, they also demo'ed how their system can, given a language grammar, produce quines -- programs p such that
(equal p (eval p))-- and twines, pairs of programs p and q such that
(and (equal p (eval q)) (equal q (eval p)))
Then they live-coded an implementation of typed lambda calculus.
Yes, all in fifty minutes. Like I said, you really need to watch the talk at InfoQ as soon as it's posted.
In the course of giving the talk, Friedman stated a rule that my students can use:
Will's law: If your function has a recursion, do the recursion last.
Will followed up with cautionary advice:
Will's second law: If your function has two recursions, call Will.
We'll see how serious he was when I put a link to his e-mail address in my Programming Languages class notes next spring.
This week I have the pleasure of spending a couple of days expanding my mind at StrangeLoop 2012. I like StrangeLoop because it's a conference for programmers. The program is filled with hot programming topics and languages, plus a few keynotes to punctuate our mental equilibria. The 2010 conference gave me plenty to think about, but I had to skip 2011 while teaching and recovering. This year was a must-see.
I'll be posting the following entries from the conference as time permits me to write them.
You can find links to other write-ups of the conference, as well as slides from some talks and other material, at the StrangeLoop 2012 github site.
Now that the conference has ended, I can say with confidence that StrangeLoop 2012 was even better than StrangeLoop 2010.
Over the summer, I gave a talk as part of a one-day conference on the STEM disciplines for area K-12, community college, and university advisors. They were interested in, among other things, the kind of classes that CS students take at the university and the kind of jobs they get when they graduate.
In the course of talking about how some of the courses our students take (say, algorithms and the theory of computing) seem rather disconnected from many of the jobs they get (say, web programmer and business analyst), I claimed that the more abstract courses prepare students to understand the parts of the computing world that never change, and the ones that do. The specific programming languages or development stack they use after they graduate to build financial reporting software may change occasionally, but the foundation they get as a CS major prepares them to understand what comes next and to adapt quickly.
In this respect, I said, a university CS education is not job training. Computer Science is a liberal art.
This is certainly true when you compare university CS education with what students get at a community college. Students who come out of a community college networking program often possess specific marketable skills at a level we are hard-pressed to meet in a university program. We bank our program's value on how well it prepares students for a career, in which networking infrastructure changes multiple times and our grads are asked to work at the intersection of networks and other areas of computing, some of which may not exist yet.
And, yes, students in a CS program must learn to write code. That's a basic skill. I often hear people comment that computer science programs do not prepare students well for careers in software development. I'm not sure that's true, at least at schools like mine. We can't get away with teaching all theory and abstraction; our students have to get jobs. We don't try to teach them everything they need to know to be good software developers, or even many particular somethings. That should and will come on the job. I want my students to be prepared for whatever they encounter. If their company decides to go deep with Scala, I'd like my former students to be ready to go with them.
In a comment on John Cook's timely blog entry How long will there be computer science departments?, Daniel Lemire suggests that we emulate the model of medical education, in which doctors serve several years in residency, working closely with experienced doctors and learning the profession deeply. I agree. Remember, though, that aspiring doctors go to school for many years before they start residency. In school, they study biology, chemistry, anatomy, and physiology -- the basic science at the foundation of their profession. That study prepares them to understand medicine at a much deeper level than they otherwise might. That's the role CS should play for software developers.
(Lemire also smartly points out that programmers have the ability to do residency almost any time they like, by joining an open source project. I love to read about how Dave Humphrey and people like him bring open-source apprenticeship directly into the undergrad CS experience and wonder how we might do something similar here.)
So, my claim that Computer Science is a liberal arts program for software developers may be crazy, but it's not entirely crazy. I am willing to go even further. I think it's reasonable to consider Computer Science as part of the liberal arts for everyone.
I'm certainly not the first person to say this. In 2010, Doug Baldwin and Alyce Brady wrote a guest editors' introduction to a special issue of the ACM Transactions on Computing Education called Computer Science in the Liberal Arts. In it, they say:
In late Roman and early medieval times, seven fields of study, rooted in classical Greek learning, became canonized as the "artes liberales" [Wagner 1983], a phrase denoting the knowledge and intellectual skills appropriate for citizens free from the need to labor at the behest of others. Such citizens had ample leisure time in which to pursue their own interests, but were also (ideally) civic, economic, or moral leaders of society.
[Today] people ... are increasingly thinking in terms of the processes by which things happen and the information that describes those processes and their results -- as a computer scientist would put it, in terms of algorithms and data. This transformation is evident in the explosion of activity in computational branches of the natural and social sciences, in recent attention to "business processes," in emerging interest in "digital humanities," etc. As the transformation proceeds, an adequate education for any aspect of life demands some acquaintance with such fundamental computer science concepts as algorithms, information, and the capabilities and limitations of both.
The real value in a traditional Liberal Arts education is in helping us find better ways to live, to expose us to the best thoughts of men and women in hopes that we choose a way to live, rather than have history or accident choose a way to live for us. Computer science, like mathematics, can play a valuable role in helping students connect with their best aspirations. In this sense, I am comfortable at least entertaining the idea that CS is one of the modern liberal arts.
Last month I was teaching my wife to drive [a manual transmission car], and it's amazing how easy stick shifting is if the car is already moving.... However, when the car is stopped and you need to get into 1st gear, it's extremely difficult. [So many things can go wrong:] too little gas, too much clutch, etc. ...
The same is true with the work day. Once you get going, you want to avoid coming to a standstill and having to get yourself moving again.
As I make the move from runner to cyclist, I have learned how much easier to keep moving on a bike than it is to start moving on a bike.
This is true of programming, too. Test-driven development helps us get started by encouraging us to focus on one new piece of functionality to implement. Keep it small, make it work, and move on to another small step. Pretty soon you are moving, and you are on your way.
Another technique many programs use to get started is to code a failing test before you stop the day before. This failing test focuses you even more quickly and recruits your own memory for help in recreating the feeling of motion more quickly. It's like a way to leave the car running in second gear.
I'm trying to help my students, who are mostly still learning how to write code, learn how to get started when they program. Many of them seem repeatedly to find themselves sitting still, grinding their gears and trying to figure out how to write the next bit of code and get it running. Ultimately, the answer may come down to the same thing we learn when we learn to drive a stick: practice, practice, practice, and eventually you get the feel of how the gearshift works.
A week or so ago I tweeted about a student who came by the office for some help with a programming assignment. When told that he'd be hearing this explanation again in class later in the day, he said, that's okay, "that way I get to learn it better".
This episode came to mind again when I wrote this paragraph in my entry yesterday about learning to talk about their programs, the ideas they embody, and the reasons they wrote the code they did:
To learn learn such skills, students need practice. The professor needs to ask open-ended questions in class and out. Asking good questions outside of class is especially important because it's in the hallway, the lab, and office hours where students find themselves one on one with the professor and have to answer the questions themselves. They can't fall back on the relative anonymity of even a small class to avoid the hard work of forming a thought and trying to say it out loud.
This is another good reason for students to go to office hours and otherwise to engage with the professor outside of class: Not only do they get answers to the questions. they also get more and better practice talking about problems and solutions than students who don't.
This offers an unexpected advantage to the student who doesn't quite "get it" yet over the student who just barely gets it: The former might well come in to get help. The latter probably won't. The former gets more interaction and more individualized practice. The latter gets neither.
A lot of professors encourage all students to talk to them about their programs. Obviously, students doing poorly obviously can benefit from help. Students at the top of the curve are ones who often can benefit from going beyond what they see in class, going farther or deeper. But perhaps we should work even harder to encourage an unlikely group of students to come see us: the ones who are doing just well enough. They don't stand out in any way that makes the prof seek them out, and that may place them at risk of losing ground to other students.
That's a tough sell, though. It's human nature not to seek help when we don't think we need it. If we seem to understand the material and are doing okay on the assignments, do we really need help? There are also pragmatic issues like time management. Student who are doing okay in my course are likely to focus their efforts on other courses, where they feel like they need more work and help.
So, it becomes even more important for the professor to engage all of the students in a course, both as a group and as individuals, in reflective thinking, speaking, and writing. Otherwise, some students who need practice with these skills might not seek it out on their own.
Most of us know that there was an advantage to being willing to ask questions. Rarely do we think about how there might be an advantage to needing to ask questions.
One of my CS colleagues gives only multiple-choice and true/false tests. He swears by how well scores on them track with performance on programming assignments, which he views as a valuable form of consistency. And, boy, are they easy to grade.
I'm not a fan. I can't recall the last I time used them. If I ever did, it was surely for a narrow purpose, say, to test quickly the student's familiarity with vocabulary. "Choose one" questions are too limiting to be used wholesale, because they test only recognition, not recall. They certainly can't test the synthetic skills we need as programmers and solvers of problems, and those are the most important part of computer science.
My course this semester has brought this idea to the forefront of my mind again. I've helped students a lot on their first two programming assignments, as they learn a little Java and revisit the concept of modularity they learned in their Data Structures course. I've been struck by how often they cannot talk about their code.
When I ask "What is this statement doing?" or "Why are you <x>?", many struggle. They want to answer in terms of the code they have written, either reading it back to me in English or telling me the code that surrounds it. This is true for almost any value of <x>. This week, "assigning a value to this variable" and "using an if statement" were common topics.
Most of these students had a reason that they wrote the code they did, even if it was merely a reaction to a specific behavior they observed in the compiler or executable. But even in the best cases the idea is usually not clear in their minds. Unclear ideas are nebulous and rambling. This is why the students have so much trouble trying to express them at all, let alone concisely.
Perhaps it's not surprising that students at this level struggle with this problem. Most are coming directly out of their first-year courses, where they learned a single programming language and used it to build data structures and small programs. They are often able to solve the tasks we set before them in these courses without having to understand their own programs at a deep level. The tasks are relatively simple, and the programs are small enough that bits of code cobbled together from examples they've seen get the job done.
It takes practice to learn how to think at a higher level, to express ideas about solutions and code without speaking in terms of code, or even the solutions they have settled on.
To learn learn such skills, students need practice. The professor needs to ask open-ended questions in class and out. Asking good questions outside of class is especially important because it's in the hallway, the lab, and office hours where students find themselves one on one with the professor and have to answer the questions themselves. They can't fall back on the relative anonymity of even a small class to avoid the hard work of forming a thought and trying to say it out loud.
They also need practice in the form of homework questions, quizzes, and even tests. Each of these exacts an increasing level of accountability, which creates an increasing sense of urgency for their efforts. One of my favorite experiences as a teacher is when students visit after a course is over and tells me the pride they felt while taking the final exam and finally -- finally! -- feeling like they could express the thoughts they had in their minds. That's a proud moment for the teacher, too.
The first four weeks of this course reminds me that one of the essential goals for the intermediate computing course is to strengthen the skills needed to reason about ideas and express them clearly. When students make the move to a second programming language and a second programming style, they have to come to grips with the fact that programming is not just about Python or Ada anymore. In fact, it never was.
In an old Geek of the Week interview, the interviewer asks Donald Knuth what gets him started writing. Knuth gives an answer that puts his writing in the context of teaching someone who is reading the book because she wants to, not because she must. His answer culminates in:
Instead of trying to impress the reader with what I know, I try to explain why the things I've learned impress me.
That's not only the kind of teacher we all want to have, it's the kind of teacher we all want want to be.
I sometimes feel guilty that most of what I write here describes connections between teaching or software development and what I see in other parts of the world. These connections are valuable to me, though, and writing them down is valuable in another way.
I'm certainly not alone. In Why Read, Mark Edmondson argues for the value of reading great literature and trying on the authors' view of the world. Doing so enables us to better understand our own view of the world, It also gives us the raw material out of which to change our worldview, or build a new one, when we encounter better ideas. In the chapter "Discipline", Edmondson writes:
The kind of reading that I have been describing here -- the individual quest for what truth a work reveals -- is fit for virtually all significant forms of creation. We can seek vital options in any number of places. They may be found for this or that individual in painting, in music, in sculpture, in the arts of furniture making or gardening. Thoreau felt he could derive a substantial wisdom by tending his bean field. He aspired to "know beans". He hoed for sustenance, as he tells us, but he also hoed in search of tropes, comparisons between what happened in the garden and what happened elsewhere in the world. In his bean field, Thoreau sought ways to turn language -- and life -- away from old stabilities.
I hope that some of my tropes are valuable to you.
The way Edmondson writes of literature and the liberal arts applies to the world of software in a much more direct ways too. First, there is the research literature of computing and software development. One can seek truth in the work of Alan Kay, David Ungar, Ward Cunningham, or Kent Beck. One can find vital options in the life's work of Robert Floyd, Peter Landin, or Alan Turing; Herbert Simon, Marvin Minsky, or John McCarthy. I spent much of my time in grad school immersed in the writings and work of B. Chandrasekaran, which affected my view of intelligence in both humans and machines.
Each of these people offers a particular view into a particular part of the computing world. Trying out their worldviews can help us articulate our own worldviews better, and in the process of living their truths we sometimes find important new truths for ourselves.
We in computing need not limit ourselves to the study of research papers and books. As Edmondson says the individual quest for the truth revealed in a work "is fit for virtually all significant forms of creation". Software is a significant form of creation, one not available to our ancestors even sixty years ago. Live inside any non-trivial piece of software for a while, especially one that has withstood the buffets of human desire over a period of time, and you will encounter truth -- truths you find there, and truths you create for yourself. A few months trying on Smalltalk and its peculiar view of the world taught me OOP and a whole lot more.
or, "Where's Your Github Repo?"
The last couple of class sessions have taught me a lot about what my students know and what they are ready to learn about programming. As a result, I'm adjusting my expectations and plans for the course. Teachers have to be agile.
A couple of my students are outliers. They have a lot of programming experience, sometimes with relatively exotic languages like Clojure. I hope that their time with me this semester is as useful to them as it is to less experienced students. Even the more advanced students usually have a lot to learn about building big systems, and especially about OOP.
After an interesting conversation with one of the more advanced students today after class, I was reminded of the role that trust plays in learning. A student has to trust that his or her professor knows enough of the right stuff to teach the class.
Most students trust their professors implicitly, based on their academic degrees and their employment at a university. (*) That makes teaching much easier. If I as a teacher start every new topic or even every course having to establish my credibility, or build trust from scratch, progress is slow.
Once the course gets going, every interaction between professor or student either reinforces that implicit trust or diminishes it. That's one of the most important features of every class day, and one we professors don't always think about explicitly as we prepare.
Working with more advanced students can be a challenge, especially in a course aimed at less experienced students. Much of what we talk about in class is at a more basic level than the one on which the advanced students are already working. "Why listen to a prof talk about the design of a method when I've already written thousands of lines of code in a complex language?"
That's a fair question. It must be tough for some students at that level to accord the same level of implicit trust to the professor as a beginner. This wasn't a problem for me when I was among the more advanced students in the class. I found it easy to trust my professors' expertise. That's how I was raised. But not all students have that initial disposition.
I've learned over the years to empathize more in this regard with the experienced students in my classes and to make efforts to earn and maintain their trust. Without that, I have little chance of helping them to learn anything in my course.
Of course, we also live increasingly in a world in which the tools of our trade give us a vehicle for establishing trust. I love it when students or prospective students ask me, "What are you working on in your spare time?" I'm waiting for the day when our upper-division students routinely ask their profs, "Where's your Github repo?"
(*) The department head in me is acutely aware that that the department also puts its credibility on the line every time a professor walks in the classroom. That is a big challenge even for departments with strong faculties.
Patrick Honner has been writing a series of blog posts reviewing problems from the June 2012 New York State Math Regents exams. A recent entry considered a problem in which students were asked to compute the probability that a dart hits the bull's eye on a dartboard. This question requires the student to make a specific assumption: "that every point on the target is equally likely to be hit". Honner writes:
... It's not necessarily bad that we make such assumptions: refining and simplifying problems so they can be more easily analyzed is a crucial part of mathematical modeling and problem solving.
What's unfortunate is that, in practice, students are kept outside this decision-making process: how and why we make such assumptions isn't emphasized, which is a shame, because exploring such assumptions is a fundamental mathematical process.
The same kinds of assumptions are built into even the most realistic problems that we set before our students. But discussing assumptions is an essential part of doing math. Which assumptions are reasonable? Which are necessary? What is the effect of a particular assumption on the meaning of the problem, on the value of the answer we will obtain? This kind of reasoning is, in many ways, the real math in a problem. Once we have a formula or two, we are down to crunching numbers. That's arithmetic.
Computer science teachers face the risks when we pose problems to our students, including programming problems. Discovering the boundaries of a problem and dealing with the messy details that live on the fringe are an essential part of making software. When we create assignments that can be neatly solved in a week or two, we hide "a fundamental computing process" from our students. We also rob them of a lot of fun.
As Honner says, though, making assumptions is not necessarily bad. In the context of teaching a course, they are necessary. Sometimes, we need to focus our students' attention on a specific new skill to be learned or honed. Tidying up the boundaries of a problem bring that skill into greater relief and eliminate what are at the moment unnecessary distractions.
It is important, though, for a computing curriculum to offer students increasing opportunities to confront the assumptions we make and begin to make assumptions for themselves. That level of modeling is also a specific skill to be learned and honed. It also can make class more fun for the professor, if a lot messier when it comes time to evaluating student work and assigning grades.
Even when we have to make assumptions prior to assigning a problem, discussing them explicitly with students can open their eyes to the rest of the complexity in making software. Besides, some students already sense or know that we are hiding details from them, and having the discussion is a way to honor their knowledge -- and earn their respect.
So, the next time you assign a problem, ask yourself: What assumptions have I made in simplifying this problem? Are they necessary? If not, can I loosen them? If yes, can my students benefit from discussing them?
And be prepared... If you leave a few messy assumptions lying around a problem for your students to confront and make on their own, some students will be unhappy with you. As Honner says, we teachers spend a lot of time training students to make implicit assumptions unthinkingly. In some ways, we are too successful for our own good.