Sub Ubi

Actually, two.

What I’ve been doing, in English

First, a bit about what I’ve been working on: trees. No, I haven’t become an arborist, but I have become interested in determining how different two programs are. One way to get at this is to look at the source code for the program, and treat it as a string. You then ask “how different are the two strings?”

Or, put in plain English, I’m asking (essentially) how different two words are.

Consider the words “god” and “good”. These words are separated by a distance of 1. One insertion needs to be made to “god” to turn it into the word “good.” For another example, consider the words “bird” and “fish”. These words are separated by a distance of three: the ‘b’->’f', ‘r’->’s’, and ‘d’->’h’. The ‘i’ is identical in both words.

Using this notion of ‘different,’ I can take the source code for a program and see how much editing has been done. But, this ignores the structure of the program. For example, I could take two essays, and look for how much has changed, but if I ignore the fact that the essay has structure (paragraphs, sentences, etc.), then I’m really ignoring an important part of the document. Programs are the same way–they have sentences and paragraphs as well, and those differences have a lot of meaning in terms of the way a program executes.

To get at the problem of structure, you have to consider the distance between words again, but it needs to be more complex. Instead of two words (like “bird” and “fish”), consider two crossword puzzles. How can you tell how different two (completed) crossword puzzles are?

For example, how different is the puzzle

 f
bird
 s
 h

 t
bard
 r
 p

Ahh. That’s hard.

A lesson (re)learned about research

The algorithms (recipes, directions) employed in comparing two crossword puzzles are not simple. In researching these algorithms, I asked some friends at Indiana where to start (not being familiar with the field), and then immediately began tracing the evolution of ideas in this area to the present. I looked for the most recent papers on the subject.

Typically, you go back to seminal papers to understand a subject; because I wanted to write fast, working code now, I went for the most recent work in the field. As a result, I spent a week frustrated, reading breadth-first across the field in the present, as opposed to a depth-first dig through the past.

This week, I went back to ‘83 and ‘93. Those were the good years–the algorithms weren’t as fast, but they weren’t poor either. And, they were easier to understand; there are fewer tricks at work in ‘93.

So, here, at the end of the week, I think I have in place all the tools to make comparisons between student code at two different levels–the word level, and the structural level.

More on why later.

I hate it when you spend half a day trying to get something to compile, only to have it “magically” work when you show it to someone else.

To finish off the technical report I’m writing, I really wanted to be able to download a running version of a tree-edit algorithm, and use that in my prototyping. I think I need to implement one of the algorithms, and be done with it.

I would rather like to do this without having to bother a paper author with questions about their algorithm. I must admit that I’ve learned something new: algorithmics papers are not typically eloquent. I have routinely encountered bits of papers where I have to interpret what I think the author meant if I’m going to do an implementation of my own.

If everyone provided the core algorithm in some concise, functional-esque language (say, Scheme), the world would be a much better place. (Read: pseudocode is always better than a plain-English description of the algorithm.)

I’ve been working on a (paid) side project for a while, and it was nice to bring a bit of closure to it today.

Now, back to the things that seem to have no closure.

Like my stomach. It’s time to go home for dinner.

I’ve been “distracted” from transcription for a week now by questions surrounding analysis of code between compiles. I don’t think this was a bad distraction, but I need to keep transcribing.

Right now, my data is on Minidisc. This is OK, except it makes it a real pain to do transcription–the MD player I have (an MZ-R700) doesn’t have the ability to accept input from a footswitch. This means that hands-free transcription (that is, keeping my hands on the keyboard) isn’t possible. So, I can either

1. Do all of my transcription with ViaVoice. This works well enough, but sometimes I need the keyboard.
   
2. Transfer the audio from the MD to the Mac first, and then go about doing the transcription. Now, I can control playback from the keyboard (with either the right software, or writing some of my own).
   
3. Hack the unit to accept footswitch input.
   

Of course, I hadn’t considerd the last option until I stumbled on a post from 1998 in the MD-community discussion archives. This eventually led me to the TechDis accessibility archives, and further searches for footswitches in the UK. These are hard to find, ya know? At least, I think it is.

Then, I started looking explicitly for hacks on the MZ-R700, having stumbled upon mention of them in Google previously. This led me to a tempting hack, but there is no need right now to destroy my only MD player. There was something very useful in this page, though.

Function Value |<< 1000 ohms Sound 2300 ohms >>| 3640 ohms Pause 5160 ohms Stop 7100 ohms Vol - 8400 ohms Vol + 9900 ohms Rpt/Ent (aka Track Mark) 11900 ohms Display 16700 ohms

Now, these are the resistance values across pins 2 and 4 for the MZ-R900 remote. This remote is compatible with my MZ-R700; perhaps, then, the resistances are similar (or close) for the 700. If not, I certainly can figure this out with some straight-forward experimentation.

Time to make some friends over in physics or electronics. With just a little bit of work, I think I can wire in a footswitch with the right amount of resistance to pause and unpause my MD. That would make life a good bit simpler.

(I haven’t figured out why I include that from time to time… perhaps just because the button to do it is there?)

NetLOGO looks to be related to (or the evolution of) StarLOGO. Both are environments for exploring massively parallel, agent-based simulations in LOGO.

I especially like the HubNet feature; many users can participate in a simulation, playing the roles of agents in the system. The example they give is of students controlling traffic lights in a traffic simulation. It is up to each student to control one traffic light, but still participate in the optimization of the whole.

That, I think, has lots of cool opportunities for getting students communicating about the nature of distributed processes and programming. Very cool.

Not actually a big deal (any Scheme programmer could hack one out), but after finally deciding on what the backend should be, I have a Scheme to Dot translator.

This makes looking at the effects on the parse tree of small (and large) changes in the source code much easier.

The Tau of Programming.

This is good poo.

Consider the program

(define fact
  (lambda (n)
    (if (zero? n)
      (1)
      (* n (fact (sub1 n))))))

which has an obvious error (extra parens around the ‘1′). How much difference is there between this program and this one?

(define fact
  (lambda (n)
    (if (zero? n)
      1
      (* n (fact (sub1 n))))))

Not much is the correct answer. STRING-EDIT claims we have only two operations; in terms of the parse tree, there is only one deletion–an empty child node that used to hang of the ‘1′. Yet, this is the kind of difference, I think, that I’m interested in when examining code changes between compiles.

Its a neat problem. Time to write it up with pictures and more analytical detail and a more thorough examination of potential changes that I might want to be interested in.

We’ve been discussing the nature of student interactions with the compiler. In particular, we know (informally) there are different types of students; we’ve seen them at work (or hacking), and they behave differently. Can we classify this behavior; that is, can we use the student’s pattern of interaction with the compiler as a predictor or a way to classify them early, so we might assist where necessary?

This is not at all about finding plagarism. I don’t think the problem is the same. In this case, I expect the code to be quite similar between compiles, and I am looking for metrics to help measure how different any two subsequent compiles are.

Tonight I’m going to run some algorithms on some code by hand; I’ll use STRING-EDIT (which I’ll actually use the Perl String::Approx module for), and will do the analysis of the parse trees of a few programs by hand. Then, I’ll have some numbers to kick around for a few, simple, but likely types of student changes to code.

I hope this whole sidetrack is productive…

Tim Mullen penned a guest article for The Register a few days back. He’s writing about software that would enable the killing of rogue processes on other people’s machines.

For example, my machine is infected by a worm. The idea is that someone else can, remotely, kill the rogue process without my knowledge or direct participation. This, of course, has stirred up some criticism.

Tim’s answer is straight-forward:

Since the owner of a system has no responsibility for the actions of a worm, or any malicious process, that runs without their knowledge, I submit that they also have no rights to the process. No responsibility means no rights.

…

If parents don’t vaccinate their children, the state takes them out of school. If a dog consistently attacks people, the authorities put it down. If someone commits three felonies, they are put away for life. This is because the rights of the many outweigh the rights of the one.

I have often found one critical problem with instructional theory: it “involves telling people how to teach.” This was how it was put to me, flat out, in a meeting regarding a curricular suggestion I had made.

Well, yes. If you don’t want to make an effort to teach in a way consistent with the type of learning outcomes we want from our students, then I say you loose the right to teach. If you don’t want to acknowledge that lecture is about as far from appropriate for teaching most of maths and computing as you can get, please, leave the lectern behind and find a job as a consultant somewhere in the backwaters of industry. Get out of the way, and bring someone in who at least is willing to make mistakes in an attempt to improve the situation.

Our students deserve the best education we can give them. If you think you have more right to remain stuck in your ways than they have to the best we can offer, then make way.

Now, all we need is a way for the students to issue a ’shutdown’ request from the lecture hall…