Archive for the 'Ideas' Category

The Roles of Journals

January 8, 2010

Academic journal publications are the lifeblood of science: The medium for serious communication, the marker of career success, and moderator of scientific integrity. Modern technology is disrupting the funding model that has supported the system for hundreds of years. As things change, it becomes worthwhile to consider the various functions journals perform. Only with new understanding can we identify the pieces we shall need to rebuild if the established structures cannot adapt.

Before the Internet, printing and distributing physical documents was sufficiently complicated to warrant specialized organizations. It was natural to capture the value of this service by asking readers to pay. These subscriptions effectively subsidized other journal services.

Now, printing and distribution are cheap commodities. For pennies, a scientist can make work available to every interested reader. This undermines the subscription business model, and it isn’t clear how existing journals can measure or capture the value of their other jobs.

To stave off collapse, journal publishers now fight bitterly to keep their publications closed to all but paying subscribers. This pits them directly against their contributing authors, who favour openness on principle and on the pragmatic realization that open publication means more citation.

Let us explore some of the unfunded roles journals play:

Editing: Journal-funded editors raise the basic quality of writing in scientific publication, filtering out spelling and grammatical errors.

Coordination of peer review: Journals arrange for qualified scientists to review others’ work, guaranteeing authors a source of feedback that is sometimes even useful.

Formalization of discussion: Journals provide a generally-accepted forum for comments on a paper and a system of retraction for severe flaws discovered after publication.

Reputation assignment: Within every scientific subfield, there is a generally-understood status hierarchy of journals. Publication in prestigious journals bestows honor on a paper, its authors, and their institutions. In some fields and journals, the order of the author list tweaks this assignment of credit.

Some fields formalize this system into a mathematical formula in an attempt to fairly measure the impact of a scientist, institution or journal.

Attention assignment: Journals regularly aggregate related content in a field, focusing the attention of interested parties. The structure of journal articles permits sophisticated searches of the literature.

Durability assurance: Journal publications are archived reliably, making it rare for a piece of work to become completely inaccessible.

Canonical citation: The scientific community generally agrees on how to cite articles from journals. A journal article citation is sufficient for a reader to uniquely identify the work being discussed.

Any serious effort to replace or fix journals will need to consider more than just the obvious, formal processes. The unwritten social roles and subtle benefits must not be overlooked.


Language Monoliths

December 30, 2009

“Write programs that do one thing and do it well.”

The Little Computer Scientist appreciates simple design. To design systems, design teams of cooperating specialists. To keep warm, wear a coat on your body, scarf on your neck, boots on your feet, and mittens on your hands. Don’t wear a seamless fullbody wintersuit—it will be hard to go pee.

Computer people mostly get it. We write special-purpose programs and break them down into special purpose pieces. We try not to make mittens that spontaneously unravel when you change your hat.

We get it, that is, until we build our programming languages.

Programmers have gotten used to the idea that choosing a programming language is a big important decision. Why? Because you can’t just choose a syntax expressing a few core abstractions. For each language, only a handful of editors are reasonable. There’s a standard library to mentally index. There’s an incumbent community of developers, and they have a philosophy of software development. There are idioms to learn and implicit “you’re a bad programmer unless you do it this way” rules. There’s a generally accepted tao of quality assurance. There’s a small council of key thought leaders and They have RSS feeds. There’s a preferred build tool, a deployment tool, and the non-standard-library standard library, like CPAN or Ruby Gems or PyPI.

Now, there are many valid forces that push things to be this way. The people who go with the grain aren’t dumb.  But we should recognize the problem and ensuing opportunities here. Monoliths are bad. Programming languages are intrinsically monolithic. Working to oppose monolithic forces is good.

Many projects do it right. XML, JSON, Protocol Buffers and Avro tackle interlanguage data representation: programmers should use them for making their data objects. Tools like CouchDB with language-agnostic HTTP interfaces are winners. CoffeeScript puts a new syntax on JavaScript: A worthy experiment. Scala and Closure compile to the JVM: There’s little excuse for language designers building VMs any more.

The Little Computer Scientist hopes to see more work breaking languages down. Make them smaller, less monolithic, more flexible. Compose them of special-purpose pieces. Expose the AST as a protobuf. Give a meta-circular interpreter and little compiler so that building correct new implementations is a day’s work. Isolate the syntax as much as possible so it’s easy to make correct highlighting editors, pretty printers and style-checkers.

Decouple, specialize, cooperate. One thing done well is a good thing.

Research Ideas

December 17, 2009

I’m planning Project February: What Aran Does When His Master’s Is Done. I’ve got a startup on standby, and interviews with companies large and small.

One possibility to stay in academia for a PhD. If I were to do this, I would need a research direction. This would then influence who I’d court as a supervisor (Greg is leaving for industry) and therefore where I’d go to school.

I could stay at the University of Toronto (I’m already in. I love it here. Path of least resistance.) or look elsewhere and aim for a later start date. Washington is on the up and up. Stanford is the de facto Silicon Valley university. It would be a good fit for my entrepreneurial ambitions. And I follow the work of researchers at many other UK and American universities.

Of course, there’s no guarantee I could get in to these places. I have no connections, no reputation, no GRE scores and currently no publication record.

In any case, the first step is to figure out if I want to do more research. Since I’m brainstorming anyway, I figure I’d post my thoughts.

Dataflow languages

Dataflow languages don’t just separate what from how, as declarative languages do, they separate what and how from when. Spreadsheets are dataflow, and there are a couple dataflow languages and libraries, but I don’t feel dataflow programming as a general-purpose paradigm has gotten the attention it deserves. Dataflow becomes especially interesting when the execution is distributed and operations are expensive, since there are all sorts of wonderful scheduling problems and optimization opportunities.

Performance Types

Traditional separation of interface from implementation deals only with functionality. But sometimes, we want to specify performance characteristics in an interface. Take real-time programming or large-scale programming for example. What’s a good language for describing performance specifications? Can we encode it into a type system?

A/B User Interfaces

Modern web user interfaces are optimized on-the-fly. Can we make better tools for UI designers to manage hundreds of variations of a UI?

Algorithmic Information Theory and Machine Learning

Algorithmic Information Theory gives us a quantitative way of thinking about intelligence. Can we learn new things by bringing this view to bear on machine learning? Example research project: Define a programming language with boolean strings as values, do learning by highly-optimized program generation.


I find it easy to come up with ideas in Empirical Software Engineering, so there’s a disproportionate number of these below.

Tool-aware development

We’re all familiar with software quality attributes like performance, readability, security and so on. And we’re aware of good coding practices like mnemonic variable names and short functions. There’s a new quality attribute in town, though, and as far as I know, nobody’s talking about it yet.

Modern software engineers use a variety of tools, such as version control systems. In the presence of these tools, certain constructs become worse.

For example, in C, you might see a construct like

#define some_flag_1 0x0001
#define some_flag_2 0x0002
#define some_flag_3 0x0004

Nothing wrong with this on the surface, but in the presence of concurrent development, version control and automerges, this code is a hotspot for a merge error if two programmers add flags.

As another example,

y = f(x);
if(y < z)

is more friendly to someone stepping through a debugger than

if(f(x) < z)

because most debuggers only let you step through statements, not expressions.

One last example: On some teams, everyone uses the same tools. On others, everyone uses different tools. Some coding practices are annoying to deal with in certain development environments. Homogeneous tool environments call for different practices than heterogeneous environments. I believe research is warranted into the ways our coding practices should change based on the development context.

Tool-aware languages

How do you design a programming language differently when you know the developer won’t just have a text editor, but will have a debugger, static checker, syntax highlighter, unit test suite, doctests, version control system, code reviews and more?

Software Development Practice Interactions

Nobody uses code reviews or unit tests or pair programming or whatever in isolation. And not all bugs are equally important. Which practices find which bugs? And how do they overlap?

Empirical Bug Prioritization

Modern software is shipped rife with known bugs. Project managers prioritize bugs and optimize for “good-enough” quality in a largely ad-hoc way. Can we offer something better than “estimated number of affected users * expected annoyance” for prioritization? Are there unpublished best practices to be discovered and optimized?

Technique Drills for Programmers

Technique drills are used in just about every other skilled human activity. Why not programming?

Bug introduction in detail

How far can we push Ko’s framework on error introduction? Can we do a better job of putting programmers under the microscope and really zoom in on what happens when bugs are introduced?

Syntax Pragmatics

I’m pretty sure from my work on DSLs that syntax matters. Can I drop another level of abstraction and find out why? This would be an investigation of the connections between semiotics, programming languages and information visualization.

A Language for Empirical Programming Language Design

If we want to learn about the usability of programming language features, we’d like to be able to turn features on and off. Most languages are designed to be as good as possible for real-world use. What about a language with dozens of syntactic and semantic knobs just for experimenting on features in isolation?

What do you want?

November 6, 2009

I was asked today what I wanted in a job.

It was surprisingly difficult to answer.

I like achievable challenges. That’s obvious. But—getting some CSS to display just right on Internet Explorer 6 is an achievable challenge, but it’s not work I’ll enjoy. Crushing a hard bug is fun, but debugging code that should never have made it through review is not. Writing efficient code is fun. Dealing with low-level memory management, not-so-much. Type errors in loosely typed languages feel preventable. Not fun. Designing a good API: Fun. Dealing with legacy constraints: Not fun.

These days it’s popular to filter software engineers: Front-end or back-end? Applications or systems?

But this isn’t a key distinction for me. It doesn’t capture the essence of what I care about. I could be happy working on front-end or back-end code. I could be unhappy working on front-end or back-end code.

Now, moments after my interview ended, I’ve managed to figure out the answer…

Accidental complexity: Not fun. Intrinsic complexity: Fun.

Job Interview Notes

November 4, 2009

A message I sent to the students of CSC 290 (Communication for Computer Scientists) following our class with practice job interviews.

Alexey said: “I wish I had not used `you know`, `er`, and `well` that often. But these words come out instinctively, as they give me time (a second or two) to think of what I am going to say next. Still, there must be other ways.

Here is a golden phrase to memorize when you need time to think about your answer for a question:

That’s a good question. Let me think for a moment so I can give you a really good answer.

You can also buy time by paraphrasing their question:

Just so I know exactly what you’re asking—Are you saying <your interpretation of their question>?

Of course, if you use one of these on a question that should be easy, you’ll seem dumb. And you probably can’t get away with using either more than once.

Yanshuai mentioned that he should have prepared a pitch for his computer vision project. In fact, you should prepare a pitch for every single item on your resume. You should also prepare pitches about your experiences in overcoming challenges or conflict, working in a team, dealing with difficult people, disagreeing with a superior or with your team, and so on.

You shouldn’t memorize your pitch, though. Instead, think about and jot notes about the importance of the project, the transferable skills you learned, and how it might relate to work at X.

Lots of interviewers also ask, “Tell me about yourself.” “Why do you want to work for X?” “Why should we hire you?” “Where do you see yourself in 5 years?” There is no excuse for stumbling on any of these questions. To answer them, remember: They are asking you to tell them about a personal quality or skill set. Lil gives an example: “I can multitask and meet difficult deadlines.  For example, when I was taking X course, I was also working on project Y, and had deadline W at work.  I was able to complete all these tasks by ___ and ___ resulting in ___.

George mentioned doing mock interviews with a friend. This is a great idea.

Leon said, “I practiced answering questions rather than exploring my experiences themselves. If I had another chance, I would have prepared differently by studying past experiences and situations carefully.”

This is an important point and applies to more than just job interviews. Once you have developed good foundational speaking skills, your best preparation is not canned answers or prepared words. Your preparation will be about becoming deeply comfortable with your material. Then the words will flow.

Reza asked, “Also knowing that the interview is short should I let him ask more questions?

While it is important to give complete answers, you should always leave the interviewer in control. In fact, you should carefully listen to the interviewer to get a sense of whether he or she wants you to take charge and talk a lot, or whether he or she would prefer to move things along.

In an interview, it may feel as if you should talk a lot, but in fact a big part of the game is listening to your interviewer (deeply listening—not just staying quiet while they talk.) You should listen actively—for example, paraphrase them and ask questions. Another one from Lil: “So you’re saying that the researcher wants you to organize data on 10,000 irradiated mice and you’re looking for a way to automate it:  Is that it? What are the resource constraints?

I should probably explain “deep listening” better. Here’s an attempt.

We learn as children that “listening” means not interrupting the other person.

“Active listening” is a skill that involves engaging the other person in a conversation to gain a clear understanding of what they are saying.

When I say “deep listening,” I mean listening with all your brainpower. It’s hard work. You’re not just trying to understand their words. You’re also analyzing: What are they saying between the lines? How does this person feel? What’s going on in the back of their mind? What are they like as a person? What’s important to them?”

Actually, if you do this, you won’t need to worry about eye contact or eager posture since it will come naturally.

Taking a step back, the best way to prepare for an interview has nothing to do with interview questions, practice, listening or public speaking skills. To prepare, you must build your resume. By that I don’t mean putting words on page. Build your resume means actively seeking out new experiences. Then you can put them on your resume. Joining and contributing to team projects boosts your leadership and teamwork credentials. Writing open-source code outside of class is one of the best ways to get new technical experiences.

And of course,

  • Smile
  • Make eye contact
  • Shake hands firmly
  • Sit up
  • Judo: Turn weakness into strength
  • Give complete answers
  • Demonstrate enthusiasm and confidence
  • Be specific

Most importantly:

  • Prepare
  • Listen to your interviewer

If you have other important comments that I’ve missed, please let me know.

Your loquacious TA,


11 Proposals For A Better DCS

September 16, 2009

Incoming graduate chair Peter Marbach has been leading a series of “town hall” meetings to build support for a Department of Computer Science conference, organized by graduate students. The stated goals are a) to improve the quality of the graduate experience by promoting interaction between areas and b) to build the Department’s reputation in industry and academic circles by effectively communicating our successes.

I’m happy that Peter cares enough to try something big, and doubly happy that he is trying to listen to us and involve us in his work. But, while the goals are lofty, I don’t agree with the conference approach. I think that there are lightweight projects that would contribute more to interaction between areas, and I feel that hosting a conference is not an effective way to build a reputation for our work. I would also criticize the proposal for lacking specificity (especially budget, organizing team, schedule) and accountability (no simple success or failure metrics).

I hate to criticize an ambitious and well-meaning proposal without suggesting a replacement. Accordingly, I’ll list some specific proposals below, without taking credit for any of the ideas. Before I do, I’ll list a few of the community projects that already exist.

CSGSBS “big” events

The CSGSBS hosts large, general-interest events a few times a year, including an upcoming BBQ.

CSGSBS “little” events

The CSGSBS coordinates weekly events including cookie breaks, movie nights and pub nights. There are attended by a small percentage (~10%) of the grad student population, and most weeks attract the same crowd again and again.

Research-In-Action showcase

Annual conference hosted on campus with posters and demos from graduate students. A few industry and political guests attend. Typically heavily-weighted on demo-friendly DGP work.

Area talks

Most areas have weekly talks. Outsiders are welcome in theory, though an interested outsider would have to find the right mailing list and often the material is too advanced.

11 Proposals for a better DCS

1. Lightweight talks

1.a Area intro talk series

Each week, a different area gives the talk. At a casual, accessible level, the talk covers why the area is interesting, the most important fundamental closed and open problems in the area, key results, and how each student’s work in the area fits into the big picture. The speaker recommends a survey paper or introductory book for students interested in more. No posters, textual or mathematical slides or chalkboards allowed. Each proposed speaker is vetted by the organizer in advance to ensure a minimum public speaking ability.

1.b Monthly Mini-TED

Monthly casual 1.5 hour meeting in a lounge with coffee. Three speakers give TED-format talks on any beginner-accessible topic of intellectual interest not related to research. Given the variety of DCS member  interests, we might hear talks on sailing, design, typography, photography, quantum physics or hooping.

2. DCS Portfolio

2.a Technical reports database

For communication of early or small research, revive the technical reports database or provide a DCS-only externally-accessible site with functionality.

2.b Publication portfolio

Provide an RSS feed with links to PDFs of all research published by members of the department.

2.c Entrepreneurial portfolio

Directory of links to companies founded by members of the DCS.

2.d Graduate success portfolio

Track the alumni network (undergrad and grad) and list the institutions they join after graduation.

2.e Blogroll

Directory and firehose of blogs written by DCS members. Michael Famelis has done good work in this area for software engineering. Extend it to the whole department. For bonus marks, provide a global WordPress installation on for DCS member blogs.

2.f Software Portfolio

Directory of software written by members of the DCS. This can include side projects, not just research-related work. Subsection for links to software to which DCS members have contributed. For bonus marks, provide distributed version control hosting and virtual private servers for hosting web applications.

3. Activities

3.a Pick-up sports

Weekly pick-up soccer or ultimate games in the summer and fall.

4. Structural Changes

This is the controversial stuff.

4.a Common-space whiteboards

Move whiteboards out of private, locked areas into public spaces where they can foster discussion.

4.b Cooperative Education

This is the biggest proposal, with highest cost and greatest potential payoff.

For the undergraduate program, provide institutional support for four-month co-op terms after first and second years, and break the PEY into four consecutive four-month terms. For MSc students provide institutional support for corporate research internships between completion of class and start of full-time research. A common infrastructure would support both missions.

Why co-op?

Work terms create a feedback loop with in-class education. Real work motivates study and supports good study habits. Programming skills honed in the workplace support theoretical learning in the classroom or lab. Problems discovered in the workplace can motivate research directions.

Work terms create a feedback loop with companies. With more work terms, more companies see more students. Companies are eager to hire students who have worked for them before. Companies are willing to contribute resources to universities that are an important part of their HR pipeline.

Weakness of the PEY

I claim the following weaknesses in the PEY program:

  1. Students make long-term commitments on their first-ever round of interviews. They often have no professional experience, and thus are not yet qualified for advanced work. This restricts their placement to beginner work, but this commitment to beginner work lasts sixteen months instead of four.
  2. Some students just don’t fit with some companies. In other cases, companies abuse long-term students for menial tasks such as manual testing. Four-month terms salvage these cases, without restricting a student from returning to a particularly good employer.
  3. Students see only one corporate culture, team culture and set of engineering practices before graduation.
  4. Students only get one round of interview practice.

Each of these is addressed in the proposed model.

Addressing Common Objections to Co-op for the DCS

I have heard two common objections.

  1. Prohibitive cost: This program would be expensive to administer. Answer: Everyone wants something for nothing, but a program like this is an investment. Other universities successfully mitigate the costs of similar programs. We can do it too.
  2. Competition with Waterloo (and other schools): The implementation of such a program would position us as an alternative to Waterloo’s well-oiled machine, and would contradict our years of PEY marketing. Answer: We should neither hesitate to adopt a good idea just because someone else uses it, nor should we allow a desire for self-consistency to trump innovation.


A frank an open discussion of ideas might lead us to improvements in our graduate experience, provided we restrict ourselves to specific proposals with measurable outcomes.

Here’s where you come in

  1. Leave a comment in your real name, and rank the ideas you care about. “++” for “would actively support, defend and work for”, “+” is “support passively”, “-” is “oppose passively” and “–” is “would actively oppose, attack and work against.”  So if you hate co-op, dislike pick-up sports, but would fight to see whiteboards moved to hallways, write this: [3.a-, 4.a++, 4.b–].
  2. Go find someone else in the department, force them to read this through and make them think through their opinions on these issues.

Let’s send a message about how to make our department better.

Having an Awesome Time Doing Science

September 10, 2009

I noticed that an two-day old highlight on a paper looked richer than new highlights, even though the highlighter was the same.

The experiment: Highlight a block on a piece of paper. Cover half the block, leaving half exposed to the sunlight and evil fluorescent office lighting.

Controlling for: Effect of time on highlight colour.

Observation: Covered half is lighter than half exposed to light.

Conclusion: Lighting interacts with highlight colour.

Threat to validity: What if air flow is the real cause of highlight colour change?

Future research: Does it matter if the light is fluorescent or sunlight?

Intelligence from scratch

September 9, 2009

Sometimes I get bored at breakfast and start to derive the first principles of fields I know nothing about. I don’t feel bad about it—I could learn something new, but if I get something wrong or get stuck, no harm done. Today’s topic is intelligence.

What does it mean for a critter to be intelligent? I would start with, “an intelligent critter acts in ways that tend to cause outcomes it likes”.

I want to work on this definition a bit. First, I want to separate out that “likes” bit. I think knowing what “likes” means is a hard and worthy problem, but I’m not interested in it today. So I’ll say instead, “an intelligent critter acts in ways that tend to cause predicted outcomes.” If the critter can predict the outcomes of its actions, then it could choose actions with outcomes it liked.

Now, our critters need to know what’s going on in the world. We all make decisions based on a constant input stream of information from the world. Sights, sounds, smells and tastes and are just the beginning—we can also feel whether our arms are above our head, and whether that leftover chinese food is sitting properly, and whether that bad knee tells us a storm is coming. If we’re general with these “internal” senses, we might find it useful later to think about our “likes” as a part of that input stream. We might even go so far as to talk about remembering as if it was turning on an internal input stream that we control.

These input streams change all the time and they’re full of rich experience. If we wanted to build a robot critter, it would need to process megabytes and megabytes of data every instant. I’m happy to leave this problem for someone else, and treat our critter’s input as a big list of bits [0,1,0,0… ( millions more )…] that gets updated many times per second. Maybe the first bunch of bits say what color the world is in the top-left corner of your left eye, and the last bunch talk about whether you’re getting a massage behind your right shoulder-blade. It doesn’t really matter.

Real quick now, we apply the same principle to the critter’s output and treat is as a similar big vector of bits. Maybe turning on the first 100 bits means “raise your hand straight up.”

So we’ve got these big vectors of bits, and they change over time. Our little critter finds patterns in the input and predicts how actions on the output bits will change the input patterns. Then it chooses the actions that give it new inputs that it likes.

Let’s say our critter learns that some output bit always affects the same input bits in the next time step. That’s close to learning that a bunch of input bits are related to each other. So I’m not going to worry about finding patterns within one input vector. Instead I want to focus on finding patterns in the inputs as time changes. So, I’ll construct an idealized problem. Every time step, the critter gets to choose a one or zero as its output, and it gets as input a one or a zero. The critter is also allowed to remember its past inputs and outputs, because we’ve now broken the system of imagining memory retrieval as just another input.

What happens if the critter’s actions have no effect on its inputs? Well, the critter would feel very frustrated and have a low sense of self-efficacy. It might still be able to amuse itself by detecting a pattern in its input, though. We could call this problem “pattern recognition.”

What happens if the critter’s input has no pattern? First, that implies that the critter would be frustrated as above. An input with no pattern would be a world in which every input bit was a coin toss. No critter could do better than 50% for very long. This teaches us that it matters “how much” pattern there is in the input. Just to make something up for now, we’ll call that quantity Q and come back to it later.

With these cases in mind, let’s write down more precisely the problem of intelligence:

Given input [{0,1}, {0,1}, …, {0,1}] and output [{0,1}, {0,1}, …, {0,1}], n = |input| == |output|, give [input(n+1 | output(n) = 0), input(n+1 | output(n) = 1)]. That is, given a history of n input bits and n output bits, provide a prediction for input bit n+1 for both possibilities of output bit. (That is, the prediction has two bits.)

In the pattern recognition problem, the two bits of the prediction are always equal, because the output bit has no effect.

Over time, we can measure how well our critter does. Each turn, the critter chooses an output, and then we get to find out if its input prediction given this output was right. (It’s too bad, but we only ever get to test the possibilities the critter chooses.) If the critter always gets the right predictions, we would call it omniscient. If the critter’s predictions are completely random and unintelligent, it would get 50% right. (If it did worse than 50%, say getting 40% right, it could just flip its predictions to get 60% right.) So we can put an objective measure our critter’s perceived intelligence, which is how often its predictions are right, and the maximum limit of this intelligence depends on Q, “how much pattern” there is.

That was too much pseudo-math, so let’s take a walk in the park and look at some ants before talking about what “how much pattern” means.*

An ant can seem to behave intelligently. It leads other ants to food, it carries dead ants away from the ant hill, and fights off mean bugs like spiders. Of course, ants aren’t really intelligent. We find this out when we take an ant away from its environment and it can’t adapt.

The ant isn’t really learning patterns in its environment to act on them. The ant detects and acts on shallow indicators of patterns that its DNA already knows. Evolution executed a learning algorithm, partially evaluating it on the “pattern” of the ant’s environment. It was an engineering tradeoff, sacrificing adaptability to get a simplified design.

From the ant we learn that our critter can have some built-in knowledge, and it behaves just like built-in knowledge in other theories of communication.

Let’s return to discussing “how much pattern.” Kolmogorov teaches us that we can measure the information content of a string by the length of the smallest program that generates that string. There might be other measures we want to use, but I’m satisfied that there is at least one measure that gives us something to work with.

The critter’s input is its environment’s output. In our simplified world, we’ll say that the the universe is a program that feeds the critter its bits. The critter, wishing to learn the patterns in its input, needs to figure out the universe’s program.

For the sake of the argument, we’ll limit the universe’s program to be finite. If the universe’s program grows infinitely, the critter can never win, and that’s no fun.

Suddenly it makes sense to think of the (infinite) set of all possible finite programs. (Actually, the set of all possible programs that input and output one bit per time-step.) We’ll call it PROGRAMS, because that’s appropriately big and bold. The universe is a finite program, so it’s an element of PROGRAMS. The critter’s learning algorithm is a program, so it’s an element of PROGRAMS. Finally, the critter’s learning algorithm has the unenviable task of searching PROGRAMS for the universe’s program.

Let’s give every program in PROGRAMS a number. I don’t know how to do this, but I’m happy to pretend that I can for now. If you’re feeling really generous, we’ll eliminate programs that don’t terminate with an output each turn, because they’re no fun. Then one possibility for the critter’s learning algorithm looks something like:

program_num = 0;
/* Find a simple model of the universe 
   that's consistent with our memory */
    program_num = program_num + 1;
/* Generate predictions of what the 
   universe will do next */
/* If I output 0, what will the universe do? */
prediction[0] = PROGRAMS[program_num](output_so_far + 0)
/* If I output 1, what will the universe do? */
prediction[1] = PROGRAMS[program_num](output_so_far + 1)
/* Emotions and feelings go here */
return better_for_me_of(prediction[0], prediction[1])

I hope you get the idea.

This critter is actually very greedy and short-sighted. Another critter might simulate the universe for a few turns ahead before deciding what outcome it likes best. A very clever critter might become curious, and use carefully chosen outputs to strategically eliminate possibilities.

There’s lots of interesting things we can think about next. For example, what happens when the universe is a program that deliberately tries to fool the critter’s program? Exactly much better would a critter do if, each turn, we informed it what would have happened if it had chosen the other output? What is the Q of a neuron? What is the Q of a strand of DNA of some length?

We can also play a fun game to try and develop a critter program that doesn’t require us to enumerate PROGRAMS. I think this would be a fun competition. Let’s see what we can learn right away:

At time 0, the critter knows nothing about the universe. Its choice of output is arbitrary. Call it a.

At time 1, the universe has provided input i, which is either a or ~a. The universe’s program could be: Always output i, or always echo the critter’s output, or something else. I think we can prove, though, that the critter’s optimal strategy is to predict and output i on the next turn, just in case the universe is one of the really simple programs.

After that, things get a little more complicated, and it’s lunch time now.

* This is how far I got before I decided it was time to get dressed and go to school. At school I spoke with Zak, who pointed me at Algorithmic Information Theory, which is a new-ish branch of mathematics and computer science that studies these things.

Business Process Design and Software Design

July 30, 2009

In fact, I think that more attention needs to be drawn to the parallels between business process design and software architecture. I think that modern businesses are so complex that you basically have to have the skills of a software architect to get them right.

—Joel Spolsky, The Best Software Writing I, 2005.

Game: Make statements that are true of software architecture and business design.

My turn: “Modularization promotes correctness and maintainability through coherency and information-hiding, but sacrifices cross-cutting performance optimizations. ”

Your turn:

Journal Publication and Subscription Fees

July 4, 2009

Greg shares

Journal publishers worry that university libraries will stop paying for journals. This would take away the funding that currently supports (a) profits and (b) a quality control process for papers via peer review.

The current unofficial system differs from the official system. In the official system, an interested reader must be affiliated with a paying institution to get access to papers, and thus institutions have an incentive to pay. In the unofficial system, everyone has access to published papers, and university libraries pay to maintain the status quo.

People generally agree that it would be nice to bring the official and unofficial systems together, but nobody knows exactly how the new system will work.

Text-editing for programming is pathetic

June 13, 2009

You give someone a configuration file and you tell them that mistakes in it are expensive.

They make mistakes all the time. They eventually get fed up and say to you: “Make me a graphical interface to these configuration options. Make it impossible to make mistakes.”

We’re moving to doing the same thing for programmers.

Let’s say I want to declare a new variable in my program.

Here’s what that line of code looks like, changing over time:





var r

var ra

var rad

var radi

var radiu

var radius

var radius;

You get the idea. In ten of the eleven states, the program is incorrect. Multiply this effect by thousands of programmer actions and you get errors. Errors waste time.

Instead, your environment should provide an “Introduce Variable” command.

Personality quiz: Did you just think, “What a terrible idea, that would be horribly kludgy and slow!” Or did you think, “Good thought, how can we make that work?”

Here is how I would design this feature. Let’s say variables v and r are already declared in the scope where you want to introduce a new variable called radius.

You click where you want to introduce the variable, and then type v. This is what shows up:

var new-variable;

If you hit the down-arrow, you would get

v = v + 1;

Let’s say in this language, in this scope, these are the only two possible expressions that start with v.

Anyhow, you have

var new-variable;

and you hit tab.

var new-variable;

Now you type r. r is already used as a variable name, so var r; is not a correct statement.

var r-new-variable;


var ra;


var radius;

You’re done! At every stage, you had a syntactically correct program, the interface provided support for recognition instead of recall, and your mind stayed focused on your program semantics instead of barely-relevant syntactic details!

Google Fusion Tables: Useful for Scientific Collaboration and Reproducible Research?

June 9, 2009

Check it out:

Google Fusion Tables

My BibTeX Trick

May 12, 2009
@article {citation-needed,
title={{Citation Needed: A To Do Item}},
author={Del. A. Procrast}

Thesis-hunting through time

May 11, 2009

I find it interesting that, over the course of my readings and idea-generation to find a thesis topic, I have gradually, inevitably and finally converged on topics of current modern research.

Captain Obvious and the Thesis Hunt

May 7, 2009

New experimental blog post format today. Lots of little items.

I skimmed about half the ICSE influential papers. Topics: Software architectures, modularity, distributed computing, software processes, requirements, assertions in code, program slicing.

There were more than fifty papers published in ICSE’08. A small fraction were ESE. As I browse the archives, I see no common themes. It seems to me that ICSE’s scope is basically anything interesting in software engineering. And here I was thinking it was an Empirical Software Engineering conference. Whoops!

Barry Boehm has A View of 20th and 21st Century Software Engineering: A high level overview of trends in SE.

Sudden realization: Jorge’s gold standard thesis had an obvious result. It’s a nice paper because of the crisp demonstration of that obvious result. I need to turn off my “I don’t want to do it because it’s obvious” filter.

Some researchers at the University of Calgary outline the place of ESE in ICSE: On the Success of Empirical Studies in the International Conference on Software Engineering.

DSLs suck as a research target for at least four reasons: It is impossible to define a representative sample of DSLs, it is impossible to generate an “equivalent” non-DSL program, DSL creation requires expertise that isn’t commonly taught, DSL usage is subject to extreme practice effects.

No matter what DSLs are chosen, a critic could argue that they are bad examples and not representative of the results of Language-Oriented Programming in general.

Some DSLs don’t have clear non-DSL equivalents. What would be the equivalent non-DSL representation for an HTML + CSS page? For DSLs for which we can specify equivalent behaviour in a general programming language, if we find the DSL superior, a critic could argue that our “equivalent” program was just not a good program. If we fail to find a superiority, a critic could argue that our “equivalent” program was in fact a DSL.

Even DSL supporters admit that it isn’t easy to make new DSLs. One requires a good grounding in language implementation (rare) and it helps to have a helping of good taste (rarer). The trouble is that every practioner has extensive training on LOP’s main competitor, that is, proper library design using language-provided abstractions as designed.

Greg’s idea of demonstrating the inferiority of DSLs in debugging tasks is a good one but the factors above mean the experimental design will require some ingenuity. If you’re an ingenious experiment designer, call me.

A Loose Upper Bound on Intra-Programmer Skill Variability.

Counterbalanced one-factor within-subjects study. Experiments were separated by two weeks.

Condition one: Participants were encouraged to get a good night’s rest. One hour before the task, they were fed a light meal of  healthy juices, coffee and foods. They were presented with exercises and reading designed to enhance a sense of self-efficacy and boost self-confidence. They were led through a mild yoga routine designed to increase concentration and mental acuity.

Condition two: Participants were invited to a late-night sexy party the night before the task. One hour before the task they were fed a heavy meal of pizza, candy and decaffeinated high-fructose carbonated beverages, carefully timed to cause low blood sugar at the time of the task. In the hour leading up to the task they were presented with unrelated hard problems designed to mentally exhaust them and crush their puny sense of self-worth.

Task: Participants completed three archived ACM-ICPC programming problems at each session and were allowed to work on them until a white-box test suite completely passed. We timed the results.

Results: The mean performance ratio between conditions was 6:1. Null hypothesis of a 1:1 ratio rejected, (Χ t, p < 0.01)

Discussion: It was a really fun sexy party. Also we faked our Ethics Review Board approvals. Also the authors are like, so drunk right now.

Oh, it’s nice to dream.

Andreas Zeller and Microsoft Research applied principal components analysis to several code complexity measures to better predict defect locations. Cool.

Microsoft Research straightened out some myths on how developers spend their time. Maintaining mental models. (Juicy tidbit: No, IMs and email don’t help productivity by preventing face-to-face interactions.) I especially like their idea of IDE hyperlinks to design documents or whiteboard snapshots. Somebody has to have made an Eclipse plugin that does this already.

Zak informs me that the Scala Eclipse plugin has inferred type hovers. Go Scala. May you change the world of IDEs forever in ways I’ve predicted.