Sambangu

Darius and the Dragons

2011-11-28T17:07:00.001-08:00

I love the writing system designed for the dragons in Bethesda's new game, Skyrim.

According to a gameinformer interview with the language's designers, the symbols are designed to look like they were gouged into stone by dragons with three talons and a dewclaw (that odd extra toe partway up your cat's leg that seems to serve no purpose)

Dragon writing from Skyrim

Bethesda (the company that makes Skyrim) was not the first bunch to encounter this graphic design problem. Cyrus the Great was an ancient Persian king (around 600 BCE) with the same idea: he wanted to create monumental inscriptions to celebrate his grandiose awesomeness, and he appeared to have a similar aesthetic, and apparently had stoneworking tools not unlike Skyrim dragon talons:

"Newer" cuneiform of Cyrus and Darius,
about 600 BCE (from Wikipedia)

That's from the Behistun inscription in Iran, which is a really good sample of this writing by a slightly later king, Darius the Great. It is a solemn record of how awesome he is, and what he's conquered: it begins, "I (am) Darius, the great king, the king of kings, the king in Persia, the king of countries."

This is technically cuneiform, "wedge-shaped" writing. Cuneiform is the oldest kind of writing we know of, originally used by the Sumerians. But Sumerian cuneiform was invented for a different medium: they wrote it by pressing a wedge-shaped tool into clay, not by whacking spikes into cliffs.

The Sumerian writing system was already at least two thousand years old and on the decline when Cyrus and Darius came along, but Cyrus's people revived it and adapted it to his language (Old Persian) to make this type of monumental inscription. I don't know why, but I wonder if they had the same feelings about it as the Skyrim artists: it evokes dragon's claws and ancient secret meanings. Maybe Cyrus hoped to co-opt the mystique of ancient Sumerian and Akkadian writing, the same way we invent Latin mottos for modern institutions.

Older cuneiform,
from Code of
Hammurabi
(~1700 BCE)

But I think Cyrus improved on the state of the art. Compare the Behistun inscription with real old skool cuneiform back when it was still in regular use a thousand years before: on the right here is a sample from the Code of Hammurabi. Cyrus's relatively simple script is almost a true alphabet (it represents syllables with about 50 symbols), but Hammurabi was writing the Akkadian language with more complicated cuneiform shapes, with more varied shapes and angles, uneven spacing, and the symbols representing, like modern Japanese, a mix of sounds and meanings. To me, Hammurabi's writing has a sloppy, random look, and as you look at even older inscriptions, it gets even sloppier. I think the simpler systems of Cyrus the Great and Skyrim's Dragon Writing look more imposing as inscription than Hammurabi's did. Each serves their purpose well enough; Hammurabi was trying to codify a stable system of law in a writing system people at the time understood, while Cyrus was trying to make people's hair stand on end.

It's time for a cuneiform revival: let's come up with a system for writing English using this style of writing, and start marking gravestones and monuments this way. The Roman alphabet has been fun for these last couple thousand years, and it's perfectly adequate for business expense reimbursement vouchers and vampire romance novels, but clearly it lacks the gravitas of stonecarved cuneiform.

Code bloat

2009-11-16T14:22:00.000-08:00

Really, Microsoft? It takes 200.2 MB of code to convert an XML file? Really?

Use case stick figures

2009-06-11T16:23:00.000-07:00

The stick figures in use case diagrams seem simple and featureless, but they undoubtedly have a rich inner life.

chi2009 -- day 3

2009-04-09T07:29:00.000-07:00

Chi day 3. Everyone here has done a formative study to show how users go about some task on the computer or in their lives, generated a list of design criteria from that, mocked up a prototype, tested it in lab study, and shown with bar graphs that people do whatever it is 22% more efficiently.

If I add up all these 22% more efficiencies in every area of my life, I somehow don't see myself as 22% better off. Lots of things seem kind of cool in isolation, and I wouldn't mind being able to use them. But there's some kind of deeper "why" question I don't really see being addressed in the formative studies. Maybe it comes down to an ROI analysis: just because something is more efficient doesn't mean it's worth your time to switch to it: consider the costs versus benefits of switching the world from QWERTY to Dvorak. Dvorak is probably slightly more efficient, but the amount of campaigning it would take to change this, would be better spent campaigning for something else.

So, when studying people doing stuff with an eye towards making that stuff easier, there ought to be a rule of thumb you can apply to find out when to drop the whole thing and say "this person is actually doing OK; they don't really need something new". I don't know what that rule might be; it would have to be pretty subtle. The most comically inappropriate example was the guy presenting on Monday who was studying love with the idea of how a device might "improve" it. Sometimes people miss each other: this emotion serves a purpose, and it's not at all clear to me that we would be better off if we had technological gimmicks to trick ourselves out of it.

That's obviously a more extreme example than someone trying to help you search for restaurant reviews faster, or keep "to-do" notes all in one place, but maybe there's some ineffable factor in all of these things that's being missed.

chi2009 -- day 2

2009-04-07T20:52:00.001-07:00

Some interesting stuff at CHI today:

- "Difficulties in establishing common ground in multiparty groups using machine translation": Naomi Yamashita talked about a study where they had a Chinese speaker, and Korean speaker, and a Japanese speaker all working together on a task over machine-translated instant messaging. Apparently this kind of works with two languages, but it's a disaster with three. She did detailed analysis of their chat logs to figure out where things went wrong: because you can't see the translation flaws between the other two speakers, you don't have enough information to understand why they make the adjustments they do in trying to communicate. So things spin out of control. They had some elaborate suggestions for fixing this, by loading up everyone with more information. I didn't really care for their solutions; I think doing three-way translations probably requires a specialized translation engine that maps words consistently among the three languages, even at the cost of some inaccuracy. I bet people could adapt better to some translation weirdness if it least everything was consistent and predictable.

- "Spectator Understanding of Error in Performance": this was a poster in the poster room, and I chatted with one of the authors. They had a psychological theory about how people interpret mistakes in musical performances, especially for unfamiliar kinds of music: did the musician hit the wrong note, or did the listener misunderstand what the musician was trying to do? The guy kindly engaged me in philosophical musing about it as I tried to think how it might relate to a programmer's perception of program errors when debugging.

- "Resilience through technology adoption: merging the old and the new in Iraq": Gloria Mark talked about internet, cell phone, and satellite TV use in Iraq. Fascinating stuff, but the biggest takeaway for me was this: bring a printout of your slides, so if the projectors or computers go horribly, horribly awry, you can give your talk without a computer in front of you. I gather that an Iraqi would have known that!

- Another poster by Anja Austerman, and Seiji Yamada: It was a very clever study about how people try to train robots. They gave people the task of training a robot. But the robot in fact already knew the task, and was programmed to behave or misbehave at certain times, in order to collect data about how the people tried to train it. Her idea was that a robot for the home might go through a pre-training phase like this, to learn its owners training styles; then later they could train it to do real tasks in a way that felt natural to them.

- alt.chi is a set of sessions with stuff that doesn't get accepted into the regular conference. So the talks are a little weird or speculative. There was one about how computers can help "improve love"; one on "thanatosensitivity" in design (product designers should plan for the death of the user and how the family is going to deal with the deceased's online identity, cell phone contacts, etc); and a study about people who do medical research online before they go see their doctor.

- Jet Townsend from CMU had a gizmo you can wear on your arm, that tells you where there are strong electromagnetic signals in the room around you. I wish I had the skills to do hardware hacking like that.

- Todd's been all a-twitter, and I've found out about cool stuff 2nd hand through him, like the MIT tour last night, and a Stockholm University shindig tonight, at which I met many cool people.

CHI2009 -- day 1

2009-04-06T20:35:00.000-07:00

I'm in Boston for CHI, a conference about human-computer interaction. It's interesting, although some of the language in the talks is a little fluffy: lots of people doing research through design to explore a process of discovery that reveals empowering affordances.

Some of the actual stuff people are coming up with is pretty cool though, so I don't meant to knock the work itself. These designers have a genuine interest in making technology work better for people, so they're trying new interface techniques all the time and reporting on how well they work for people. For example I saw today some multi-touch pressure-sensitive mousepads, only with no mouse. Simple idea but it works very nicely, and probably a lot cheaper than multi-touch sensitive screens.

There are also some wacky muppet-labs kind of inventions, like the "crowdsourced haptic interface" where you let anonymous strangers give you backrubs over the internet. I'm not sure what problem that solves, but I guess it was worth trying.

After a reception tonight, some nice MIT grad students took a bunch of us over on a tour of the CSAIL building, where we saw roombas watering plants, Richard Stallman's office, discarded dusty robots lurking in corners, and we walked the whole length of an infinite hallway. CSAIL is housed in a Frank Gehry building, and all the plants died when they finally plugged up all the leaks that had been watering them.

Syntonicity

2009-03-25T17:17:00.000-07:00

I learned a new word today, "syntonicity". Syntonicity is when you understand something by identifying with it, rather than understanding it purely abstractly. Here's a presentation by Stuart Watt talking about syntonicity in the context of programming language design.

Beginners to programming (and, frankly, all of us sometimes) have problems stepping through a program in their heads to see if it will work. They remember their intent when they wrote the code, but they have trouble putting themselves in the computer's shoes and seeing the program through its eyes. Watt claims that Seymour Papert was trying to aid this kind of thinking when he invented the Logo language. In most graphics languages, there's a set of coordinates on the screen, with (0,0) in the upper left corner, from the viewer's perspective. In Logo, everything's done from a cursor's perspective (the "turtle") as it moves around the screen.

Watt was involved in the creation of Hank, a specialized programming language for psychology students where information is shuffled around by a character named Fido. John Pane's language for children, Hands, does very nearly the same thing, but actually draws a dog ("Handy") on the screen with a pack of cards in its paw.

I don't know one way or the other if explicitly naming some part of your language or environment after an animal helps people think about programming the right way. But I can see where syntonicity could be a way of evaluating more subtle features about a language.

Consider for example the naming difference between F#'s workflows and Haskell's monads. They're similar concepts: a way of kind of quoting some code, so you can later say "execute it in the following peculiar way". The lines of the code are there, and you later say how information is passed from line to line. "Workflow" isn't a perfect description of that, but it gives the impression that you're going to hand it over to the processor later, and say, "do this work". "Monad" on the other hand is a mathematical term from category theory, that describes the mathematical relationship between the type signatures of the lines of code.

"Workflow" leads you to identify with the good old blue-collar working function you're going to hand this thing off to to execute thing, while "Monad", if you're a category theoretician, leads you to think about the types underlying the code as interesting theoretical objects: how can they be twisted around and changed and reapplied in new ways?

This fits nicely with the goals of F# and Haskell: the former is meant to be a practical programming language for scientific and financial programming, and the latter is primarily a research testbed and playground.

So, I think the names for things do matter when designing a language. If you choose names that sound like verbs, and those verbs have subjects that might be imagined to have a consistent point of view about your programming model, maybe it will help guide users into the right mindset for reasoning about your language the way you'd like them to.

Java beginners: beware the black hole of "static"

2008-12-10T10:22:00.000-08:00

I've just been grading a bunch of programming assignments from college sophomores taking their second term of Java, and I've noticed a dangerous pattern.

Suppose you have a class like this in your project:


class Foo {
   private int state = 42;
   void doStuff() { System.out.println(state); }
}

The right way to use the doStuff() method is like this:


Foo f = new Foo();
f.doStuff();

But a common mistake is for people to try to access it like this:


Foo.doStuff();

The latter doesn't work, because it's the syntax for referring to a static method: that is, a method that belongs to the class rather than to each particular object in the class.

So, if you make that mistake, Eclipse gives you the option to


change modifier of doStuff() to static?

Don't do it! Run away! That's not the right way to fix it. In most cases, it means you forgot to create a Foo object.

But suppose you take Eclipse's bad advice anyway. Then you get a new error, because now doStuff() can't see the integer state anymore. What does Eclipse offer to do for you? You guessed it:


change modifier of state to static?

If you do that, then your program will seem to work again. But the meaning is very different, and as soon as you try to use multiple instances of this Foo object, your state variable will appear to do crazy things -- because it will be shared between all your Foo's.

So beware of static. If you have a method that refers to variables that aren't either passed in as arguments, or declared inside its brackets (like state, in this example), then it probably shouldn't be static.

As for making data items static, ask yourself this: think of some future modification of this program where you might need to have several different objects made from this class. Do you want them all to have the same value for this variable? If the answer is "no", then using static is bad form, even if it doesn't currently cause a problem.

So do the extra work and eliminate "static" from your Java code if you've added it in "just to make it compile". It'll be tedious to get it to compile again. It might require you passing extra parameters to methods, or creating new object variables. But take the time to figure it out. Learning this will give you the right intuitions, and will save you headaches later on in your programming career.

Learning from game designers

2008-10-31T07:55:00.000-07:00

Here's a very readable presentation about how computer game designers
manage to build in a more evenly-sloped learning curve than application designers
do.

Princess-Rescuing Application

What kind of debugging should we be studying?

2008-08-13T12:40:00.001-07:00

I really think, but just can't back this up, that a lot of the time when programmers are debugging, they're doing it on code that they're pretty familiar with. The research literature empirically studying people debugging, seems heavily biased towards comprehension and debugging of code that people are seeing for the first time. This has got to be a methodological issue -- it's just so much easier to bring people into a lab and hand them code they haven't seen before.

Some people I've asked about this seem to disagree -- they think it's commonplace for programmers to be thrown into new unfamiliar code in their workplace and have to figure it out. Could be, but I still think they spend most of their time around familiar code, hour by hour. And that will judge their debugging tools by how well they work for them in familiar code.

This makes a big difference, because people who are debugging familiar code already have some understanding of how it works, and they're trying to compare the real code against the understanding in their head, to see where they, or it, are going wrong. So it's kind of a scientific process, coming up with hypotheses and refuting them by testing them out, until they narrow down the exact point where the code goes astray from their notions about it.

People debugging unfamiliar code, on the other hand, are going to start with a comprehension phase where they go bottom up, looking at it and just trying to make sense of it. If academic research, and product development research, puts too much focus into understanding that particular situation, I think it will be giving short shrift to the later phases of code maintenance.

Help with study of functional programmers

2008-07-15T12:10:00.000-07:00

Are you currently developing or maintaining a medium to large-sized
program written in a functional language, such as Haskell, F#, OCaml,
or Lisp? I'm doing a study of functional programmers, as part of
a research internship at Microsoft, and I would like the opportunity to look over
your shoulder while you do debugging or coding on your project.

I'm looking for people with at least a year's experience doing
functional programming, and who are currently working on a real
project (i.e. for some purpose other than learning functional
programming). I'm only allowed to use people who can work in the US
(because of the gratuity, which is taxable income). I'd simply come
watch you work, and ask a few questions along the way. You'd do
whatever you would normally be doing. If you're near Seattle or
Portland, I'd come to your office for a couple of hours. If you're
not near Seattle or Portland, then we'd set you up with LiveMeeting
or some other remote screencast software so I can watch you from here.

Obviously security concerns are an issue - I will not share any
proprietary information that I learn about while visiting you.

In exchange for your help, Microsoft will offer you your pick of free
software off its gratuity list (which has about 50 items, including
Visual Studio Professional, Word for Mac, XBOX 360 games) or any book
from MS Press.

We're doing this because expert functional programmers have not been
studied much. We plan to share our findings through academic
publications, to help tool developers create debugging tools that are
genuinely helpful in real-world settings.

I'm hoping to finish my observations by August 8th, so please contact
me immediately if you're interested!

Thank you,

Chris Bogart
425-538-3562
t-chribo@microsoft.com

icfp contest update

2008-07-13T09:02:00.000-07:00

Well, I got threads and tcp and everything all figured out, and my simple "spike" solution works the way I intended it: the rover makes a beeline for home base, ignoring craters, martians, and boulders, and usually dying or crashing.

However I can't get it to run in Mono on the LiveCD environment for the contest. I've been using Visual Studio on a virtual machine on my mac. Visual Studio runs a little slow, but the program runs fine. But when I try to run it in mono, I get a big wodge of error messages, none of them pertaining to my code. I used some new features of F#, so it may be that it exercises some corners of mono that haven't been tested yet.

I think at this point I'm going to give up on submitting a solution and just post interesting bits of my code here after the contest ends. I still want to think some about a quick and dirty way of avoiding craters, but I probably won't spend much more time on it: it's nice out today!

I feel like I've gotten what I wanted to out of this: building something significant in F#. I have 238 lines of code, and I used F#'s Erlang-style mailboxes, asynchronous workflow, discriminated unions, class definitions, and I overcame the headaches of separating things into multiple modules while making sure all references went backwards. I got threading and networking in a pretty clean way I think. The ugliest part of the code is actually probably the navigation code, that looks at where the rover is and how fast it's going, and decides how to head for home base.

ICFP contest day 2

2008-07-12T11:23:00.000-07:00

I spent a few hours programming last night, and I still don't have a running program yet. F# turns out to have some pretty interesting monad-like things for handling asynchronous code (they're called "workflows") and this appears to be the right way to handle sending and receiving stuff from a TCP/IP connection.

I think I have a pretty good idea how to make this work, but I'm banging my head against the details: for example I want to asynchronously read a line of text from a socket, passing it along to the rest of my program as soon as a carriage return is received. So, do I have to read one byte at a time in a tail-recursive function, adding to a mutable string? Or is there an object or something in the library that will do this for me? There's a tradeoff between searching and searching in the docs to find the most natural way of doing it in the language you're trying to learn, versus writing it from the ground up yourself, probably less efficiently, as a newbie.

My problem may be that I need to sit down and read a book on .NET instead of thinking I can adhoccumulate expertise efficiently.

By the way, I like Expert F# better than Foundations of F#. I wish I'd read the former instead of the latter as preparation.

Wish me luck!

ICFP contest! Rovers on Mars!

2008-07-11T12:38:00.000-07:00

The 2008 icfp contest just started! Sadly I'm at work for another several hours, but I skimmed through the description, and hopefully the programmer-lobe of my brain is already hard at work on the problem while my researcher-lobe is busy dealing with participant recruitment for a study.

This one is not all parsey like the last two years: it's all real-time execution and floating point numbers in a navigation problem. It's not the kind of thing I've thought about much, so it should be an interesting challenge. Also, my laptop plug *just* stopped working, so I may have to complete the entire task in 2 hours and 27 minutes. Hopefully they have extras in Seattle somewhere.

My plan this year is to do it in F#, since it's cool and also I'm doing a study on it for my summer internship. But they made it a little harder by not including F# in the list of supported languages. But no worries -- they do have mono (the .NET clone, not the disease), so I'll just have to upload an executable.

5 Hints for Beginning Haskellers

2007-10-10T07:46:00.000-07:00

Here are some things that have caused me headaches in learning Haskell.

Function calls. Functions are called by giving the name and the arguments separated by spaces. If a function f has two parameters, a and b, you call it with f a b not f(a,b). The latter would be a one-argument function whose argument is a pair. You can do things that way if you like, but it'll make things a lot trickier later.
Precedence. Those spaces in the function call syntax are about the tightest binding thing in the language. So if distance is an integer, and show is an (Int -> String), then show distance++" miles" is good syntax, because show distance is evaluated before the ++. On the other hand, if c is a character and cs is a string, then length c:cs is a type error. Haskell will try to evaluate length c first, then prefix that number to the front of the list cs. Instead, you want length (c:cs).
Parens in patterns. This is really an example of the precedence issue above, but it trips me up all the time. You need more parens on the left hand side of function calls than you'd think. I don't know how many times I've written code like the sample below, leaving out the parens at first.

data Coord = Coord Int Int
manhattandist :: Coord -> Int
manhattandist Coord x1 y1 = x1 + y1 WRONG
manhattandist (Coord x1 y1) = x1 + y1 RIGHT

Arrows in type declarations. The type of (+) is Int -> Int -> Int; and we're supposed to accept that the first two Ints are the arguments, and the last Int is the return value. But turns out there's a cool reason for this. An equivalent type declaration would be Int -> (Int -> Int) (because -> groups right). You can think about addition this way, and Haskell cooperates nicely: + is a function that takes one integer, and returns a function. So plus x y = x+y is equivalent to plus x = \y -> x + y (search for lambda in the Haskell docs if you don't know that backslash syntax). So if you need a one-argument function (that returns a function) for some reason, it's OK to go ahead and define it as a two-argument function returning a number; Haskell doesn't make a distinction, and it's more convenient sometimes to express it that way.
Monads. These are famously hard to get. There are 10,000 tutorials out there, and most of them help a little. I'd recommend you start by learning to use the important standard ones, like Maybe, IO, and List, more or less by rote. Beyond that, if you're in a situation where you'd need to roll your own, I'd say just forget monads exist and write the code yourself. Once you get so you really understand the ugliness involved firsthand, monads will be an obvious benefit. Anyway, that's my plan right now. I think I get them well enough to explain them, but I make a lot of stupid mistakes when I try to use them, so I probably don't understand them as well as I think I do. (More on this later -- I'm taking two classes right now that rely on Haskell, so I'll comment on this more as I have little insights).

Types to distinguish parameters and dimensions

2007-09-07T12:31:00.001-07:00

Suppose a language had a rule that said a function could only have one parameter of a given type, and each dimension of a multidimensional array had to be indexed by a different type.

This would have several benefits:

You'd get extra fine-grained checking; you couldn't possibly get parameters mixed up
When making array slices or currying, you wouldn't have to concern yourself with the ordering of the parameters.
You wouldn't need to distinguish between optional named parameters and ordinal parameters. The name of a parameter would be (or would be derived from) it's type.

With functions like + that seem to require two items of the same type, you could interpret the two (or more) arguments as a collection. Lists certainly could contain homogeneously typed members.

Python to the rescue: ICFP contest 2007

2007-07-23T11:52:00.000-07:00

The ICFP contest was great fun this year, as usual, and I actually arranged travel and moving plans so that I would be in one place for the weekend to work on it.

I resolved to work in Scala this year, because it seemed like a practical functional language I'd like to know better; and it allows imperative programming with the java libraries, so I thought it would be a smooth learning curve.

Well, I spent the first day butting my head up against Scala, and dealing with condo repair contractors and a fussy HOA board in the meantime: at the end of the day I had basically no running code and a splitting headache. The cure: beer and python.

The second day I changed to Python, which I really haven't used *that* much, but it's easier to figure out how to do things. I'm not sure why -- maybe it's a question of documentation, or maybe it's just that I don't get functional programming as well as I thought I did.

In Python I managed to get an interpreter that basically worked, reading the DNA file and creating images using Tkinter. I don't think it was ever flawless. There was a self-test screen that I eventually got all "OK"s on, but I never did see these manual pages that people on the discussion list were talking about.

The Python was still too slow to make further debugging feasible, so I rewrote it in C. Got that working sometime Sunday, and it was faster, but it wasn't faster enough. The real solution needed to be linked lists to pointers to memory, so one wouldn't need to shuffle megabytes of DNA around -- but I had no mental energy to implement anything like that by that point.

Lessons learned:
Either scala documentation needs work, or I just need to spend more time learning the paradigm
When the problem statement says that shifting byte strings around needs to be done in faster than linear time, that's an optimization I should think through up front, not "get to it later". It made all my implementations useless.
Python is the best language I know of for expressing algorithms. It isn't fast enough, though. (although I wonder what if I tried the linked-list thing in python? I may try that as an experiment)

There were some complaints on the discussion list by people saying that the up-front work was too hard, and that most people never got to the meat of the problem. I totally disagree with that. ICFP is all about making functional programming usable and efficient. If, with current tools, we are forced into low-level bit-schlepping in C, it points to a deficiency with the most common tools of functional programming, or in the training of programmers. The contest ought to be about illustrating that kind of issue in a fun way.

Here's an interesting point: languages with higher-order kinds of functionality tend to abstract one away from the machine more; working with heavy integer "objects", for example, instead of raw machine integers as C does. Is it possible to have a language where you can talk about bare metal, even registers and such, but do it in a higher-order abstract way when desired? I guess C++ attempts to do this in some ways, but it's an extremely complex language. Is there no better compromise?

Representin' in Oregon

2007-06-03T16:46:00.001-07:00

I haven't posted in a while, but I have good news -- I've been accepted into the PhD program at Oregon State University! I first discovered the program by googling what turned out to be Margaret Burnett's turn of phrase, "HCI of Programming".

It's been 15 years since I got my master's at Colorado State. Turning 40 last year, I've been thinking about where my life is headed and what I wanted to do next. I've been doing very practical programming in the title industry in the daytime, and thinking and writing about programming languages at night. So now I'm back in school, and although the faces have changed, the hassles are all the same.

Up until now I have thought more about the challenges of language design for professional programmers, but at OSU I'll be diving into the whole realm of end user software engineering.

When designing a language for a professional programmer, maybe we can assume that the user knows what he or she is doing. Programmers are expected to have an analytical mindset, and plenty of practice at debugging things. They have endured years of indoctrination into the sacraments of testing, code correctness, documentation and version control. They have fingernails that shine like justice. They have RTFM. It's safe to assume that they have this expertise. It may not actually be true that they have it, but it's safe: our asses are covered, because we said on the box "professionals only".

An "end user" may in fact be a professional programmer, but we no longer have our asses covered; the environment must share in the responsibility. There is an intelligent being sitting in front of us, who thinks in a very different way than the computer does. They have some concept of what they want the computer to do, and we have to cooperate with them in representing that concept. Without being making so many wrong assumptions, or so few right assumptions, that we annoy the user into walking away in frustration.

When I was going through the application process, I went for advice to University of Colorado professor, Clayton Lewis, who introduced me to the notion of Theory of Representation: that a lot of what's interesting in computing can be seen in terms of making valid mappings from one representation system to another. In those terms, HCI is about mapping between formal and human representations. But the human representation system is a pretty quirky thing that cognitive scientists are still attempting to explore; so HCI is kind of an engineering discipline working ahead of its time: trying to translate in and out of human representations before human representations can really be said to be understood by science.

This process has got to be a two-way street, because human representations of programming solutions are invariably wrong to start with, at least at a sufficiently fine level of detail. They need refinement, and the process of formal representation helps with that refinement.

In HCI of programming there is more going on, however. Engineering is not just a set of concepts, it's a discipline. "Discipline" is a deep set of mental habits. So to turn end users into software engineers, or to turn software engineers into better software engineers, it seems to me that an ideal software engineering environment will do more than represent users' ideas; it will help teach the user the mental habits necessary to refine those ideas efficiently. Maybe that goes beyond theory of representation.

Bring to a boil: programming with cairns

2007-05-19T21:18:00.000-07:00

I'd like to see more computer language instructions like the "bring to a boil" instruction you see in recipes. "Bring to a boil" doesn't tell you to put the pot on the stove, or how you turn the burner on, or how long it takes to boil. In fact, that may vary based on your altitude, the quality of your tap water, and the shape of your pot.

"Bring to a boil" jumps ahead past a bunch of obvious steps. It's not just like a subroutine call, encapsulating a handful of steps for brevity; it just describes the endpoint of a bunch of steps, and it's assumed you can find your way there yourself.

Finding its way there itself is something computers can do. Algorithms to traverse mazes are not that tricky, and in some limited domain, figuring out how to accomplish some process could be likened to navigating through a maze. In some limited domain where an algorithm can be generated to get from here to there, why not give programmers that for free?

Presuming that automatic programming is hard in the general case, but easy in sufficiently constrained cases, then programmers should be able to set a series of cairns for the compiler to follow, each close enough to the last for automatic programming to find its way, but far enough apart to save having to type in a lot of tedious steps.

The other nice thing about this kind of instruction is that it entails a test. Often we write code that clanks along like an insane robot, following instructions without checking every so often to see that it's still on course. "Bring to a boil" isn't the sort of instruction that can accidentally be followed when you're in the bedroom instead of the kitchen, blindly going through the motions of turning on an imaginary stove while standing in front of the laundry hamper.

Hobbling scheme for readability?

2007-03-25T10:35:00.000-07:00

There's a discussion going on over at Lambda the Ultimate about the use of Scheme as a shell scripting language (scsh). As is typical in such discussions, the people accustomed to parentheses are saying that all the parentheses aren't so bad, while the people unaccustomed to them feel that traditional shell scripting is clearer.

I gotta come down firmly on the no-parens side of this debate. Lispy parentheses are an egregious example of center embedding, which are an impossible strain on short-term memory. It's quite hard to write lisp code without help from an editor program that counts parentheses for you. Lisp is optimized for machine parsing, but pessimized for human parsing.

It would be interesting to see just what limits there are on programs you can write without center embedding. Suppose you had a dialect of lisp in which the outermost expression did not need parentheses around it, a comma would close a single paren, a period would close multiple parens, and whenever there are two levels of paren, the ONLY way to close them would be with a period, which would end the outermost expression. So something like this would be legal:


a (b c, d (e f, (g  (h (i j.

and would look like this in traditional syntax:


(a (b c) d (e f) (g (h (i j))))

The point being that you could nest as deeply as you liked, but only at the end of the expression. I don't know, it looks kind of ugly at first glance, but it parallels nicely English structures like:


This is the cat that ate the rat that lived in the house that Jack built.

If you forced yourself to write in that style, and just defined variables to refer to when you couldn't find a way to structure things in this way, I wonder what the program would look like.

select * from universe where planet=earth

2007-03-17T14:46:00.000-07:00

In Ten Ways to Sunday, Nathan Allen discusses the fact that the powerful relational model you have for referring to data in a database, does not extend to entities outside the database, and he proposes that similar relational model should be available to refer to everything a computer has access to, with some way of explicitly narrowing the scope of this system for the context of a particular task.

Referring to everything in the world with a consistent relational model is a conceptual nightmare, as Nathan hints at, and as you'll soon discover too if you peruse an upper-level ontology like SUMO or cyc, and contemplate relating some dataset that you work with into one of these ontologies. But I think something along these lines is going to end up bearing fruit in the long run. Human communication always uses words with known meanings, linked into a shared cultural knowledge set. Because of that, we can describe data, processes, and new ideas to each other without having to define terms nearly as often as we must when writing software or laying out databases. Our data is implicitly embodied as part of society's larger body of knowledge. Today's databases, on the other hand, are a bunch of arbitrary items whose interpretation is described by machine-unreadable documentation, and implicitly described by the the way software happens to be written to use it.

While humans seem to share an implicit upper-level ontology, we don't actually know what it is, as evidenced by the difficulties and controversies surrounding the building of formal upper level ontologies. If we can figure out why we can communicate so well with each other despite that, I think we'll have learned something important. I suspect what's going on is that we have multiple ontologies for different kinds of ideas and objects, that are loosely and inconsistently interrelated.

The inconsistency of our ontological landscape is evidenced by those weird questions we stay up late at night arguing about like "why is there a universe" or "does red look the same to you as it does to me" or "is there a God". It's also where "religious" debates come from, by which I mean those debates where your position seems so obvious that you think the other guy must be being deliberately obtuse not to see what you see so clearly.

Someday AIs in charge of personal data management will fritter away their spare CPU cycles arguing about whether postal codes should be intrinsic parts of addresses or derived data items by way of post office servers. During the day, though, they'll warily agree to disagree and find a practical workaround.

Lojban

2007-02-25T14:44:00.000-08:00

I just realized that although I chose a Lojban name for this blog, I haven't written much about it.

Lojban (and its predecessor/competitor Loglan) was conceived as a language that would fit more or less within the realm of human language universals, but that at the same time would be syntactically unambiguous, and its semantics would be "based on" predicate calculus. If some version of the Sapir-Whorf Hypothesis is true, then maybe learning a language based on predicate calculus would cause you to be a more logical thinker.

The Lojban experiment has been a success in the sense that a complete, usable language was developed, and there are a community of speakers doing translations, original writing, and holding conversations in it. I participated in the Lojban community in the mid 90s, and I found learning it to be an interesting mental exercise for several reasons:

It required some distinctions that are not habitually made in English; for example there are 14 logical connectives to choose from, plus some non-logical connectives. At first you find yourself drawing truth tables to figure these things out, but eventually they come more naturally as you use them enough.
Other things were easier than English. As in Japanese, in Lojban you can often elide important words, with the hole being implicitly filled in with "whatever is obvious to both speakers".
There was an incredibly fun and productive word construction process, where you'd take these three-letter word bricks and glue them together to make compounds. German's got nothing on Lojban.
The language is excessively rich in hundreds of little words that approximately fill the role of prepositions. Some of these were thought up rather cavalierly for theoretical reasons or out of a sense of completeness, to fill out a pattern of similar words, so while their meaning was clear, it was not always clear when they would be useful. Coming up with plausible usages and trying to nonchalantly work them into forum conversations was great fun.
There was also a composable vocabulary of short words made exclusively of vowels and glottal stops, called "attitudinals", representing emotions. You could often get your point across by just expressing how you felt about it, and let the content be implied.

Some of Lojban's downsides, that eventually led me away from spending time on the project:

While Lojban borrowed some concepts from propositional logic to great benefit, in the end I don't think it would be fair to say Lojban was "based on" logic. To me that would mean that language structures would be defined in terms of a simpler and pre-existing formal logic already known and understood by logicians. As it was, we had endless arguments about how to correctly translate example sentences from Quine, like, say, "I want a sloop" in the case where there is not a particular sloop you have your eye on. I think problems of this sort went pretty deep, and probably the language should have been designed from the ground up around a particular theory of meaning, right or wrong, rather than making up a grammar and arguing about what it meant later.
The community was fascinated with navel-gazing issues of this sort, which was highly addictive but not very fruitful in my opinion. It was educational and thought provoking for me, but I did not have the formal logic/philosophy of language background to contribute as productively as I wished I could have.

All that being said, I think Lojban has made an important gesture by exploring a wholly new point along the computer/human-language spectrum. One lesson I'd like to see the programming language world learn from it, is that it the names we assign to things in programming languages are almost always completely arbitrary and unanalyzable. What if something that the computer could actually dissect, akin Lojban's word-building system ("lujvo"), were mandatory for most variable/function/class names in a program? In no human language do we invent most of the words used in a paragraph, and begin by defining them; we instead stretch existing vocabulary to meet our needs. Perhaps that contributes to the error-pronity of software development in some way.

Evolution of AI

2007-02-16T07:34:00.000-08:00

Grey Thumb brings our attention to this article: The Evolution of AI, published in Artificial Intelligence last year.

The author accuses AI researchers of being crypto-creationists, for not putting more emphasis on evolutionary techniques in their research. While I think the author is essentially right in saying that evolutionary techniques will play an important role in the research and development of artificial intelligence, it seems to me to be merely practical tool in that field, not a relevant object of study in that context. What's interesting about AI is not the mere production of software that has intelligence-like features, but the deeper understanding this process can lead to: just what intelligence and consciousness really are, and how the human mind might work.

The problem with evolutionary techniques is they often lead to designs we can't understand, or that, on analysis, turn out to work for strange, quirky reasons.

I call that a "problem" only in that it doesn't naturally lead to a better understanding of a problem domain. If you're trying to design a tone discriminator, as in the article above, or a better antenna, it's fantastic what genetic algorithms can do for you. But in trying to understand intelligence, the project as a whole would be too large for a genetic algorithm to tackle and would lead to an unanalyzable mess. I'm not making that statement without evidence -- look at what nature has given us: our brains took billions of years to evolve, and after thousands of years of trial, error, and science we still can't reliably tweak it to cure common problems like depression and schizophrenia.

I'm sure as evolutionary techniques improve, people will use them to design components of intelligent systems, and analyze those designs to come up with theories about how they work. In fact we'll probably do a lot more of that in a lot of fields. But the only way I see evolutionary theory as being directly a part of the AI field is if it turns out that there are evolutionary processes going on within the human mind in real time -- a possibility the paper does not even discuss.

In short, he's conflating a research technique with a field of study.

Burrows-Wheeler Transform in Haskell

2007-01-23T18:22:00.000-08:00

I got curious about program transformation techniques, and went looking to see what kind of work had been done on round-trip parsing: i.e. using the same grammar to turn a string into an abstract syntax tree, and then to turn it back into a string.

Well, I got distracted by this very odd thing I found called the Burrows-Wheeler transform. It's a weird way of sorting a string that is reversible. (And happens to be likely more easily compressed with something like run-length encoding, hence its use in compression programs such as bzip2). Basically you sort the string, then replace each character with the one that used to appear to the left of it back in the original ordering (or an "end of string" marker for the character that came from the front of the string).

Anyway, as an exercise I wrote an encoder and decoder in Haskell. Here it is, for your amusement. Feel free to use it if you want, but it's probably not very efficient. I need to read up on when Haskell does and does not save results of function calls -- are they always memoized?



module Bwt3 where
import Ix
import Data.List

--
-- For BWT we want to compare strings with the special
-- rule that the end of string sorts as greater than any
-- other character
--
compHighEol [] [] = EQ
compHighEol lst1 [] = LT
compHighEol [] lst2 = GT
compHighEol (x:xs) (y:ys)
    | x > y    = GT
    | x < y    = LT
    | x == y   = compHighEol xs ys
    
-- Datatype for rotated string; the string starts where the
-- integer member says it does, and wraps around when it hits the
-- end, conceptually
-- This lets us store multiple rotations of the same string
-- without using storage for each one; they all point to the same
-- structure
data Rotation = Rot Int [Char] deriving Eq
instance Show Rotation where
    show (Rot k l) = (drop k l) ++ ['@'] ++ (take k l)
instance Ord Rotation where
     compare (Rot a as) (Rot b bs) = compHighEol (drop a as) (drop b bs)


-- List of all possible rotations of a string     
allrots str = [ Rot i str | i <- range(0, length str) ]

-- The actual output of this algorithm is a string with a flag
-- embedded in the middle of it, which can't be a character.  So
-- we introduce a type for this purpose that
-- allows for an EOF symbol.  Which by the way, sorts after
-- all other characters, to help with decoding

data FlaggedChar = FC Char | FC_EOF deriving Eq

instance Show FlaggedChar where
     show FC_EOF = "@"
     show (FC x) = show x
     
instance Ord FlaggedChar where
     compare FC_EOF FC_EOF = EQ 
     compare _ FC_EOF      = LT
     compare FC_EOF _      = GT
     compare (FC x) (FC y) = compare x y


-- BWT encoding: make all rotations, sort them, and take the last
-- character of each.
encode str = map lastchar (sort (allrots str))


-- lastchar just pulls the last character out of the
-- rotated string, or FC_EOF if that's the last item
lastchar (Rot 0 xs) = FC_EOF
lastchar (Rot ix xs) = FC (head (drop (ix-1) xs))

-- The rest of this stuff is for decoding the [FlaggedChar]
-- list we made above
--------------------------

-- Given a list (of anything), return a list of Ints
-- showing where the elements of the list would end up
-- if sorted.
--
-- We do that by tagging each element with an integer, sorting
-- those tagged items, and
-- collecting the tags afterwards to see where they ended up
sortPermutation xs =
   map snd ( sortBy compfst (zip xs [0..]))
   where compfst x y = compare (fst x) (fst y)

-- Turn that into a cycle by cycling through it once
getCycle xs = 
    take (length xs) 
         ((iterate ((sortPermutation xs) !!) . fromInteger ) 0)

-- apply the permutation to the encoded item
-- and rotate the result so the end of string flag comes at the end
applyCycle cycle encoded = 
    fCtoString $
    tail $
        dropWhile (/= FC_EOF) answer ++ takeWhile (/= FC_EOF) answer
        where answer = map (encoded !!) cycle  -- Oops: fixed typo 9/2008

fCtoString :: [FlaggedChar] -> [Char]
fCtoString [] = ""
fCtoString ((FC c):cs) = [c] ++ (fCtoString cs)
fCtoString ((FC_EOF):ds) = fCtoString ds -- ignore FS_EOF
    
-- Finally the decode function puts it all together
decode xs = applyCycle (getCycle xs) xs

Abstract Refactoring

2007-01-07T16:11:00.000-08:00

This week I had a subroutine, let's call it Bedrock, whose functionality I needed to expand to handle a new situation. I won't bore you with the details, but the short story is that it created and handled exceptions from an object, Fred, and now I needed the same thing done with a very similar object, Wilma, which has almost, but not quite, the same behavior.

Of course, there's always this dilemma: is it clearer to just throw a little logic in the function to handle the two cases, something like:


sub bedrock(bool need_caveman) {
  Caveperson c;
  if (need_caveman) { c = new Fred(); }
  else              { c = new Wilma(); }

  try {
    c.bang_on_rocks();
   } catch (Exception e) {
       if (need_caveman) { printf("Fred can't find a rock\n"); }
       else              { c.call_betty(); }
   }
}

...or is it better to separate the whole thing into separate functions:


sub bedrock(bool need_caveman) {
  if (need_caveman) { bedrock_fred(); }
  else              { bedrock_wilma(); }
}

sub bedrock_fred() {
  Caveperson c = new Fred();
  try {
     c.bang_on_rocks();
  } catch (Exception e) {
     printf("Fred can't find a rock");
  }
}

sub bedrock_wilma() {
  Caveperson c = new Wilma();
  try {
    c.bang_on_rocks();
  } catch (Exception e) {
    c.call_betty();
  }
}

(the latter case further invites us to make bedrock() a virtual function in the superclass of Fred and Wilma so the dispatching function is handled more discreetly, but that's an optimization for another day).

In my case, sitting there in my IDE, I wasn't sure which would be clearer. I knew what needed to be done, but I couldn't quite visualize which way would be easier to read until I typed it out. (I have to admit I'm not much of a flowcharty, UML-y kind of thinker; I have to type out code, or at least pseudocode, to see what it looks like, then refactor from there and draw diagrams after the fact.)

The thing is, there's no functional difference between these two options, outside of some extremely trivial performance issues (the second one uses one more stack frame than the first -- whoop-de-doo). Why do I have to decide at all?

The first code example has the virtue of showing you clearly the relationship between Fred and Wilma -- where their needs differ, you have an explicit if statement. Its flaw is that if you want to know just about Wilma, you have to read past the clutter of irrelevant stuff about Fred. The second example obviously has the converse strength and weakness.

I'd like my IDE or revision control system to know about this trade-off, and be able to display the underlying functionality in either manner. Think of it as something like currying. Currying, if you're not familiar with it, is where you take a function with two arguments, fill in one of them, and treat that half-filled-in function call as a new function of just one parameter. For example, "+" takes two arguments, as in 3+4 = 7. If you curry it with a "3", you get a new function, "3+_", taking one argument and returning that number plus three.

Now in my bedrock example, looking at the first function where I have everything all lumped together; suppose you curried it with the value need_bedrock = true. In two places you'd end up with:

if (true) then { foo foo foo }
else           { bar bar bar }

which a smart IDE ought to be able to display simply as:

foo foo foo

Much clearer, no?

In general, then, I'd like to have some kind of odd IDE modality that was like a debugger, in that I could play with variable values, but in which I could mutate the code to show what it would reduce to under current conditions. If I can rule out somehow that Wilma isn't relevant to the bug I'm tracking down, then the code logic can be automatically simplified for me.

What would be really cool would be if I could even edit the deWilmafied "curried" code, and it would be able to merge my changes back to the canonical codebase, just as changes to conflicting revisions in a source control system are merged. That could get messy though, so much careful treading would be in order.

Questions on Haskell Style (and Polynomials redux)

2006-12-17T22:48:00.000-08:00

Someone posted, on the Haskell "Blow your Mind" page, a much more concise implementation of Polynomials as Numbers than I managed to come up with. There are a couple things I learned by comparing it with my version:

Use of zipWith (+) instead of map (\v -> (fst v + snd v)) zip; obviously I need to get to know the libraries better
zipWith' is introduced to zipWith two lists together, padding the shortest one with zeroes. Jeremy Gibbons suggested the same thing, calling it longzipwith, and this is parallel to what I did without the "with" in my zipLong function.
They had the same questions I did about what to do with the required signum and abs functions. Mikael suggested in a comment that I should use the NumericPrelude library instead of the standard one, for a more sensible generic definition of a number.
Jeremy and Blow-your-mind both used one less line in their zip function definition than I did: they manage to define it without explicitly handling the case where both lists are null.

And here are some questions I have -- please comment if you have any ideas!

The Blow-your-mind version uses [a] instead of Poly [a] as its polynomial type. My feeling is that an explicit constructor and data type like Poly is better, because a polynomial is not the most obvious way to interpret a list of numbers. However, my functions ended up being a lot wordier, pulling that constructor on and off the list all the time. What's the better style choice here?
The multiplication function has me scratching my head. It seems terser, but less communicative to me. If you're got more experience with functional programming than I do: is the Blow-your-mind version much more clear or efficient, and is it worth it? Is mine only clearer to me because I'm not used to FP style yet? Or maybe tight APL-like gnomishness is part of the point of the Blow-your-mind page. (Here they are again if you don't want to follow all the links).

My version:

> scalarPolyMult :: (Floating a) => a -> Poly a -> Poly a
> scalarPolyMult c (Poly rs) = Poly $ map (*c) rs

> multByUnknown (Poly rs) = Poly (0:rs)

> multPoly :: (Floating a) => (Poly a) -> (Poly a) -> (Poly a)
> multPoly (Poly []) cs = Poly []
> multPoly (Poly (b:bs)) cs =
>     addPoly
>         (scalarPolyMult b cs)
>         (multPoly (Poly bs) (multByUnknown cs))

Blow-your-mind version:

  xs * ys = foldl1 (+) (padZeros partialProducts)
  where
  partialProducts = map (\x -> [x*y | y <- ys]) xs
  padZeros = map (\(z,zs) -> replicate z 0 ++ zs) . (zip [0..])

Automatic Spaghetti Refactoring

2006-12-13T22:46:00.000-08:00

I wonder under what conditions it would be possible to take a working body of spaghetti code and automatically refactor it to pull out all references to one specific resource, or some other definable subset of the program's activity. Afterwards, your code would be as bad as before, or worse, in terms of organization, but it would at least be semantically equivalent.

If you could do this quickly, on demand, you could present the object to a programmer in some kind of constrained editor for modification, then re-inline the changes back into the original structure of the code. This would let a programmer pretend a design was nicely modular and object-oriented for the sake of conceptual simplicity in making a change, but without requiring the code to actually be organized at all.

Why bother doing this? It could be that the code is already organized according to some orthogonal concern that you don't want to mess up; or it's truly messy spaghetti code that you don't understand; or maybe more interestingly, it's represented internally as a dataflow graph or something, where there may be no linear or hierarchical structure to it by nature.

I know refactoring gets done piecemeal by menu options in some IDE's, and I know something similar is done within compilers as optimization steps, for example inlining, and loop unrolling, but I haven't heard of large scale, temporary changes just for the purposes of presentation.

The idea of making a transformation, applying a change, then reversing the transformation, puts me in mind of the notion of "conjugation" from group theory. However I haven't gotten to that chapter yet in my Algebra book, so I don't really know if there are any monkeys in that tree.

Awkward db2 SQL syntax

2006-12-07T09:35:00.000-08:00

I'm continually frustrated by the awkwardness of SQL syntax in DB2 (I do database work on an IBM iSeries). You can't do an update on a joined table; you can only update one table, so you have to do a subselect, typically expressing exactly the same subselect in two places in the same query. See Brett Kaiser's helpful example. I keep shying away from doing them this way because it seems so wrong, but I keep coming back to it as my best alternative. A language should not make you say the same complicated thing twice in once sentence. Anaphora is your friend, IBM!

Simonyi on Comments in Algol-60

2006-12-05T07:53:00.000-08:00

Check out this fascinating slideshow by Charles Simonyi about how the language Algol-60 was originally used in practice -- as a language for comments. He observes that good code comments can be a good source of ideas for new programming language constructs, since comments are where programmers express ideas that they feel can't currently be made clear or concise in the code itself.

The Zen of Referential Transparency

2006-12-04T21:05:00.000-08:00

Here's another interesting connection between Buddhist philosophy and math: this blog post by metaperl draws a connection between Haskell's lack of state variables, and Eckhard Tolle's belief that "the only thing that is real is the present moment."

I'm not familiar with Tolle, but this is a part of Zen thinking as well. You could choose to look at the past and future only as memories and projections that exist now, rather than as independent realities. I'm not claiming to know something that arcane about the universe. But it makes sense, using category theory as a metaphor, that you could choose to view the past and present and future as three real objects; or you could choose to look at the currently existing traces of the past, and currently existing precursors of the future as categorical arrows, and merely define the past and future in terms of those.

A pure function will return the same value every time it is called with the same arguments; this is convenient because it makes them timeless in a sense. If you define some function


    f(x) = x+4,

you can say that f(2) = 6; and it's always true. If f(2) gets called 10 times during a program's execution, you only have to really do the addition once; after that you know it as a timeless fact. Even calculating it the once is bending to necessity; after all, it was already true before we calculated it.

But if we have some other function, g(), and we pass the result of f into it


    g(x) = x * 7
    print g(f(2))

Well, g(6) = 42 no matter what, and g(f(2)) = 42 no matter what. They're both universal timeless facts about this little system. But in practice the computer has to calculate f(2) in order to know what to feed to g, so that g(f()) relationship works like time. f is "before" g, even though they're both mathematically fixed, static, and unchanging.

My feeble understanding of Zen is that one can learn, among other things, to experience time as an artificial construct of this sort, and not as something fundamental. It's a pretty hard to nail down what's concretely different in this perspective, though, because it's probably isomorphic to the more conventional view of time as a mighty river, but supposedly there is a psychospiritual benefit to changing one's perspective in this way.

Some links:
An article about Zen, Time, and Bohm's interpretation of quantum physics
A prior post of mine on dependent origination and category theory

Moving to new URL

2006-12-03T21:35:00.000-08:00

Hi,

I'm moving to http://sambangu.blogspot.com. Please update your feed! I was doing an FTP upload from blogger.com to my ISP, but the comments never worked, and it just doesn't seem worth the trouble to do it that way.

Polynomials as numbers

2006-12-03T19:50:00.000-08:00

So, I was trying to learn category theory, having gathered it was a good thing to know for people interested in programming language theory. I kind of got bogged down though -- it's castles built on castles built on castles in the air, and I was losing track of reality in all the abstractions. My book would talk about a category of Groups, for example, so I'd go looking up Groups in my faithful Wikipedia. I'd get the concept, it's not that tricky in itself, but obviously understanding the definition of a group does not make one a group theorist.

So, I finally declared "mission accomplished" brought the troops home to a ticker-tape parade, and started in on a group theory textbook instead (Knapp's Basic Algebra). I'm enjoying it a lot more -- it starts up where I left off with math classes, so I don't feel like I'm a freshman in a senior-level class.

Anyway, this book starts with a kind of review of polynomials, simultaneous equations, matrices, vector spaces, etc. that is stuff I've seen before, but with a more theoretical spin, that either was missing from my high school algebra or I've simply forgotten it. The book points out that factoring integers into products of smaller integers, is very much like factoring polynomials into products of polynomials of smaller degree, and a prime number is like a polynomial you can't factor any further (like say x²+9 = 0, when you're dealing with Reals). Of course you can also add, subtract, multiply, and divide polynomials, and the result is always still a polynomial. If a topologist can't tell a coffee cup from a doughnut, then a group theorist can't tell a polynomial from an integer.

Well, maybe she can; obviously integers and polynomials have some different properties. But I'm tickled enough with the idea that a polynomial is a kind of number, that I created a polynomial instance of Num in Literate Haskell as an exercise, reproduced below for your edification.

Since I'm also still learning Haskell, I welcome any critiques you might have of my code. I like the fact that the data structure I used (just a list of coefficients) turned out to make for short code; but it doesn't come out very readable. The fact that prepending a 0 to a list multiplies the polynomial by X seems as cryptic as it is convenient.


> module Main where
> main = print testP

I represent a polynomial as a list of its coefficients,
with the constant first, then the X, the X^2, etc.  So
3x^2 - 4 would be Poly [-4,0,3].

> data Floating a => Poly a = Poly [a] deriving (Eq)

Now we evaluate by filling in the unknown.  Note that
ax2 + bx + c evaluated at x is the same as
(ax + b)x + c, so you can evaluate it by taking the constant
term, popping it off the list, then multiplying x by the
polynomial interpretation of the rest of the list.

> evalPoly :: (Floating a) => (Poly a) -> a -> a
> evalPoly (Poly []) x = 0
> evalPoly (Poly (c:cs)) x = c + x*(evalPoly (Poly cs) x)

To add two polynomials, add corresponding coefficients.  If
one is shorter than the other, you want to use zeroes.  I don't
know how to do this beautifully with standard functions, because
zip cuts off when the shortest list runs out.  So I defined
a helper function zipLong, that keeps going till the longest
list is done, filling in a default value.

10 Points to whoever emails me with a shorter, cleaner,
idiomatic way to do this.

> addPoly :: (Floating a) => (Poly a) -> (Poly a) -> (Poly a)
> addPoly (Poly r) (Poly s) = Poly $ map (\v -> (fst v + snd v)) (zipLong r s 0)

> zipLong [] [] d = []
> zipLong (x:xs) [] d = (x,d):(zipLong xs [] d)
> zipLong [] (y:ys) d = (d,y):(zipLong [] ys d)
> zipLong (x:xs) (y:ys) d = (x,y):(zipLong xs ys d)

Multiply a polynomial by a scalar.  I have a feeling this
could be defined somehow under an instance of Num so that
the * operator is automatically overloaded.  Not sure how.

> scalarPolyMult :: (Floating a) => a -> Poly a -> Poly a
> scalarPolyMult c (Poly rs) = Poly $ map (*c) rs

Since (ax^2 + bx + c)x = ax^3 + bx^2 + cx,
then Poly [c b a] * x = Poly [0 c b a]

> multByUnknown (Poly rs) = Poly (0:rs)

To multiply two polynomials, P1 * P2, where P2 = (dx^2 + ex + f),
rewrite as  f*P1 + P1*x*(dx + e); the first term is a scalar multiplication
and the second has one less degree, so we can recurse on it.  The
(Poly bs) term below is (dx + e) in this example.

> multPoly :: (Floating a) => (Poly a) -> (Poly a) -> (Poly a)
> multPoly (Poly []) cs = Poly []
> multPoly (Poly (b:bs)) cs =
>     addPoly
>         (scalarPolyMult b cs)
>         (multPoly (Poly bs) (multByUnknown cs))

Define a polynomial as a number.  I'm cheating a little by
picking a dumb definition of signum; really a polynomial
with an unknown isn't positive or negative before a number
is plugged into it, so I'm just defining it as the sign of
the constant term.

> instance (Floating a) => Num (Poly a) where
>     s + t  = addPoly s t
>     negate (Poly cs) = Poly $ map (\q -> -q) cs
>     s * t = multPoly s t
>     abs s
>        | signum s == -1   = negate s
>        | signum s /= -1   = s
>     signum (Poly [])  = Poly []
>     signum (Poly (c:cs)) = Poly [signum c]
>     fromInteger i = Poly [fromInteger i]

And define a cheesy way to print out a polynomial

> instance Floating a => Show (Poly a) where
>     show (Poly [])     = "null"
>     show (Poly cs)     = concatMap
>          (\c -> " + " ++ (show (fst c)) ++ "X^" ++ (show (snd c)))
>          (reverse (zip  cs  [0..length(cs)-1] ))
 
Define some examples and some tests. 

> p = Poly [2,0,1,2] -- 2x^3 + x + 2
> q = Poly [0,0,0,3,4]   -- 4x^4 + 3x^3

> testP = (p * q == Poly [0,0,0,6,8,3,10,8]) &&
>         (p + q == Poly [2,0,1,5,4]) &&
>         (evalPoly p 3 == 65.0 ) &&
>         (3 * p == Poly [6,0,3,6]) &&
>         (show p == " + 2.0X^3 + 1.0X^2 + 0.0X^1 + 2.0X^0")

SOAP: follow-up

2006-11-17T14:19:00.000-08:00

Here's a fantastic dialog that exactly captures my experiences with SOAP. (via Anarchaia)

Follow up on kanji coding method: Wuji

2006-10-25T21:52:00.000-07:00

Turns out there is a character input method like the one I described in my previous post.
Sounds like it turns out to be kind of awkward to use. Ah well...

Ban the dangling else!

2006-10-15T09:45:00.000-07:00

I was just reading through Niklaus Wirth's paper, "Good Ideas, Through the Looking Glass" (found through Lambda the Ultimate, of course!) where he talks about the Dangling Else problem.

Some programming languages have statements of the form:

if X then Y

and

if X then Y else Z

with no end keyword or bracket, leading to the problem of how to interpret:

if it's Saturday then if it's sunny then have a picnic else see a movie

Do we see a movie if it's not Saturday, or if it is Saturday, but it's cloudy?

Natural languages have exactly the same sort of problem (example from the AP Press Guide to News Writing, quoted in Language Log):

We spent most of our time sitting on the back porch watching the cows playing Scrabble and reading.

It reads funny in English, but we resolve it easily because we know the context. Obviously context is not as helpful for a compiler.

How does Language Log suggest fixing that problem in English? They give two suggestions:

We spent most of our time sitting on the back porch watching the cows, playing Scrabble and reading.

Playing Scrabble and reading, we spent most of our time sitting on the back porch watching the cows.

The first suggestion corresponds approximately to Wirth's preference for an end keyword; the comma signals a break of some kind, and the obvious interpretation is that the cows and the scrabble shouldn't be too closely associated. It's not nearly so rigorous as end, of course.

The other suggestion is a bit more interesting; they rework the entire ordering of the sentence. Although the two examples aren't really parallel, it does suggest another way to rework our if-then-if-then-else, if we intend the final else to correspond to the first if-then:

if it's not Saturday then see a movie else if it's sunny then have a picnic.

In other words, we're punting -- not solving the original ambiguity but wording around to avoid the issue.

I think that's actually a better strategy from a human reader's standpoint. We do not have much in the way of "closing braces" in natural language: they tend to lead to center embedding issues which our brains just aren't equipped to deal with. So maybe a good policy would be for a compiler to simply disallow the "if-then-if-then-else" construction with either interpretation, and force the user to rework their logic a little. Such a restriction looks like an ugly hack to a computer scientist, but I think its necessary if we take seriously the idea that programs should be human languages as well as computer languages.

Tags: language, Programming Languages, HCI, dangling modifiers

Metalanguage for Software Development

2006-10-08T20:37:00.000-07:00

Every software developer uses a variety of languages to develop a program. It may seem like you're developing something purely in Perl or Java or VB or whatever, in fact you're using a lot of mini-languages to manage the development process:

Shell: if you're using a command line, you have to know shell commands for managing files and directories, invoking the compiler, etc.
IDE: On the other hand if you're using an IDE, you could kind of consider it language-like; you invoke series of drop down menus and click options on and off
source control: whether it's IDE-based or command-line based, you're describing and querying a specialized model encompassing time, files, directories, versions, and maybe different user identities
deployment: you use FTP commands, or something equivalent, to put files on a server, configure the server to run your programs at the appropriate time, etc.
building and linking: Like makefiles or visual studio "projects"
profiling: turning a profiler on or off, configuring it, and interpreting its output, is a language-like interaction
debugging: another model of the program, where you communicate with the debugger about variable values and code structures
SQL: typically any interaction with a database within your program, is done from within a walled-off sublanguage; maybe SQL built into strings, or maybe a specialized, but usually somewhat awkward, object or function call model.
Database configuration: setting up tables and so forth is often done with a combination of SQL or database management configuration IDE manipulation

When programmers think about the development process, we have an integrated mental model of all these aspects of the process, and from that figure out how to use them all together to do what needs to be done. It would be interesting to have a single, consistent meta-language for software development that encompassed all these tasks.

The closest thing we have to that, I think, is the command-line shell. The simpler "languages", such as the compiler settings language, are encapuslated as command-line arguments, so technically from the same prompt you are doing diverse tasks like compiling your program or renaming files. But useful as it is, it's kind of a gimmick. You can't easily pull together information from, say, the profiler, the debugger, and some unit test results, and ask questions that cut across these different domains.

For example, suppose you made a change to a procedure last week, and now you think it may be running too slow on a particular dataset. A test of that is easy to express in English: run the current version of the procedure X against dataset Y and note how long it takes; also run X against Y using the version of X that was current last Thursday. Implementing it would take a little work; we'd have to check out two versions, compile them in separate directories, run them both under a profiler, and know how to interpret the profiler results. Speaking for myself, I'd probably make a mistake the first time through -- I'd check out the wrong version of the code, or run the compiler with different optimization flags or something.

There oughtta be a language that has standard terminology for all these sorts of tools, and some easy way to build little modules onto the front end of a tool, that translates this language into the tool's configuration settings, and translates its results or error messages back into the language.

The trick is you'd have to have a pretty smart front end that could pull apart commands or queries that involved multiple tools and figure out what commands to pass along to the individual tools; then integrate the results it gets back. This would not be a trivial problem, but it would be a good start just to make this kind of task *expressible*, and require a lot of user guidance at first.

Tag: ProgrammingLanguages

Buddhism and Category Theory

2006-09-07T16:43:00.000-07:00

In my previous post today I mused about using standard ontologies in programs as a way of grounding the web of connections between your objects in a framework of common terminology.

There is a concept in Buddhist metaphysics called Dependent Origination, which states that nothing exists on its own, but only manifests itself through its connections with everything else in its environment. One illustration of the concept is Indra's Net, an infinite spider web with little silver balls at all the junctions, each reflecting all the others in a way that would gum up any ray tracer.

A program that doesn't refer to much of anything external to itself is like that -- you can define data structures and pointers and files that all point to each other, but it's all meaningless without the interpretation that a programmer or user gives to it in the data they feed to it and their interpretation of its output.

I'd say that Category Theory is a mathematical restatement of Dependent Origination.

Tags: CategoryTheory, DependentOrigination

Organizing programs by their invariants

2006-09-07T15:13:00.000-07:00

It seems to me that natural langauge program specifications tend to consist of a lot of statements which are all independently true, and only dependent on context for deictic references (i.e. pronouns and pronoun-like references to concepts in surrounding sentences). In other words, I'd claim, you could make sense of a good proportion of a scrambled specification if:

Sentences remained intact
Deictic references were replaced by full references to global names of entities or processes

Now obviously, not everything in such a document will behave that way; for example an ordered list of steps will have their ordering and context lost. But I think my claim is more true of an English-language spec, then, say, a large FORTRAN program. If you have a spec you're working with closely, you might have sticky notes on different pages, and individual sentences highlighted, which you can turn to and refer to instantly without necessarily reading for context. An old-skool not-very-modular FORTRAN program, on the other hand, is meant to be executed in one fell swoop. A programmer might turn to a particular page of a printout and look for some information, but will require a lot more scanning around and reasoning to come up with an answer to their question about what's going on in the program.

A Java program might fall somewhere in between English and Fortran in that regard -- Java tends to be written with lots of smallish functions, each of which might be comprehended on its own.

Another reason a natural-language spec is easier to read in a random order, is that the words in an English sentence are more likely to be standard vocabulary not defined in the spec; and the ones that are defined in the spec are likely to be motivated* narrowings or metaphors of standard terminology. In all the programming languages I'm familiar with, almost all the entities defined in a particular system can be freely named: a there may be conventions telling a programmer what sort of thing a WidgetWindowHandlerFactory is, but the compiler doesn't care; it could be a synonym for Integer.

So this habit of natural language helps make randomly-chosen sentences more comprehensible on their own. That in turn makes it easier for us short-attention-span programmers to digest the piles of paper our managers and user groups churn out.

This suggests a couple interesting features for programming languages:

Structurally organize programs around a series of declared invariants, with the compiler (when possible) or the programmer (the rest of the time) filling in associated code to ensure the invariant remains true. This could be done in a lot of different ways depending on the need -- type systems, aspects, agents.
Create a large and varied, but standard and fixed, ontology of types that the user should almost always derive from. Give them all short names and require user-defined types and variables to end with those type names. This would have to be done carefully to avoid javaStyleWordiness(), and it would also be a larger learning curve/burden on the programmer. I'm picturing something vaguer and more flexible than a standard library; rather than providing a bunch of standard implementations, the ontology would provide standard invariants.

* "motivated" -- I got this term from George Lakoff's book "Women, Fire, and Dangerous Things" where he talks about how new uses for old words are motivated by metaphorical relations with older meanings, but not predictable from those meanings.

Tags: ontology, language, Programming Languages

Saponomancy

2006-08-19T21:14:00.000-07:00

This week I was asked to write some code to mimic a SOAP service. How hard could that be? It was a very simple service, just a couple remote procedure calls, one of which could return a large binary file.

Of course, the original one was implemented in Delphi, to run under IIS, and the new one needed to run on a UNIX-like system, but SOAP is intended on making all this easy, right? How much did I need to know?

Well, a lot, it turns out. I played with a couple different toolkits for creating SOAP services, and they kept coming up with slight variations, none of which seemed to interoperate out of the box. Little things would be different in the XML message, like whether namespaces were mentioned in the tags, or how the attachment was referenced and sent. It was easy to see and understand the problem by looking at the dumps of the XML and MIME stuff going over the wire, but much harder to plow through the documentation of the various API's to see what flags needed to be set in their object model, or what objects needed to be created, or who was responsible for allocating and freeing memory, etc.

In the end, I realized that since this was an internal service, and I controlled both endpoints, I could easily make a case to management for just using the raw HTTP protocol, and in fact as I played with that solution, it turned out to be cleaner, lighter, more maintainable, and easier to document. I'm changing my party affiliation to REST, even though it's too late to vote in the primaries.

Well, that's fine; I'm sure there must be cases where SOAP is a better solution, but it got me to thinking about why it is that the raw XML is so much easier to debug than the supposedly labor-saving frameworks built on top of it. I guess it's just that what goes across a line is easier to capture and pin down -- I can run two services, capture their input and output, and just compare the logs of them. But I can't compare the operations of their object models, because they're different.

What would be very cool, is if there were a formal way to specify a relationship between all the possible operations of an object model, and the grammar of its input and output streams. Then I could point to a rule in the grammar that I wanted to come out a certain way, and ask "what sequences of user-accessible object operations can cause this". The closest thing I've seen to this is the Whyline from project Marmelade at CMU. The Whyline is a thingy that looks like it's geared towards helping a programmer find bugs in their code, by tracing out why a particular condition was arrived at in code execution. Seems like it could be just as useful for prying apart the mysteries of someone else's prepackaged API, especially if it was closed-source, if somehow the Whyline could still operate without showing you precious vendor secrets.

Unfortunately the Whyline is still a research project built into a research language called Alice, not a handy button on my Visual Studio menubar.

Abstracting Bubblesort

2006-08-14T21:17:00.000-07:00

In my August 4th entry I conjectured that monads might be a good way to abstract away the question of whether a bubblesort was done over time or laid out across memory as a sequence of permutations.

I thought that was a good exercise for me to brush up on Haskell monads, so here's the program I wrote. It's "literate haskell", so you can take this whole posting, save it as an whatever.lhs, and it should compile.

I especially relied on a monad tutorial at A Neighborhood of Infinity, that Sigfpe happened to post just as I was in need of it. Thanks, Sigfpe!


I'll be using the State, List, and IO monads.  Eek, trial by fire.
To start with, State has to be imported:

>import Control.Monad.State

So here's my generic bubblesort to start out with.  It sets everything
up without actually having the list available yet; all it needs is the
length for now.

The cf and swap parameters are functions that compare and swap elements,
respectively.  Actually, they just take the indexes of the element(s)
and return a function which will be responsible for testing and permuting
anything the caller wants, however they want.  cf x y should compare elements
x and y (whatever that may mean), and swap x should swap the xth and (x+1)th
elements.

So this function cycles through pairs of adjacent indices in bubblesorty
fashion, and builds a list of functions, each of which is responsible
for testing, and maybe swapping, a pair of elements, with those 
user-supplied comparison and swapping functions.

>bubblesort cf swap theLen = do
>                       i <- reverse [0..theLen]
>                       j <- [0..(i-2)]
>                       [do
>                            i <- cf j (j+1)
>                            if i
>                                 then swap j 
>                                 else return ()]

Now here's a simple comparison function: it assumes that the 
list will be just an ordinary list, with elements instances of
Ord (so that > works).  What it returns is (State [a] Bool),
which is actually another function, taking one list [a]
and returning the same unchanged list [a] and a Boolean.

>cf1 :: Ord a => Int -> Int -> (State [a] Bool)
>cf1 i j = do
>            ls <- get
>            return $ (ls!!i) > (ls!!j)

And here's the corresponding swap function.  It returns a
function which takes a list, and returns a list with the
jth and (j+1)th elements swapped.

>swap1 :: Int -> (State [a] ())
>swap1 j = do
>            theList <- get
>            put $ (take j theList) ++ 
>                 [theList!!(j+1)] ++ [theList!!j] ++ drop (j+2) theList

Let's look at another pair of swapping/comparison functions,
before putting everything together:

This set has a more complicated state -- it's an ordered pair,
of the current permutation [a], and a list of strings [[Char]]
representing the Plinko toy that 
would produce the sort so far.

>cf2 :: Ord a => Int -> Int -> (State ([a],[[Char]]) Bool)
>cf2 i j = do
>            (theList, history) <- get
>            return $ (theList!!i) > (theList!!j)

And here's the corresponding swap function:

>swap2 j = do
>            (theList, history) <- get
>            let newList = (take j theList) 
>                          ++ [theList!!(j+1)] 
>                          ++ [theList!!j] 
>                          ++ drop (j+2) theList in
>                let newHistory = (( (replicate j '|') 
>                              ++ "><" 
>                              ++ (replicate ((length theList)-j-1) '|')) 
>                                  : history) in
>                    put (newList, newHistory)

In this second example, the state is more than just the
list, so we need a function to create the original ([a], [[Char]])
structure:

>buildstate2 :: [a] -> ([a], [[a]])
>buildstate2 a = (a, [[]])

And one to get our plinko toy out after we're done sorting:

>getresult2 :: (Show a) => ([a], [[a]]) -> [Char]
>getresult2 (_, b) = foldl (++) "" $ map (\b -> "\n" ++ show(b) ) b

I skipped the equivalent functions before for the straightforward
sorting example because they are straightforward:

>buildstate1 :: [a] -> [a]
>buildstate1 a = a
 
>getresult1 :: (Show a) => [a] -> [Char]
>getresult1 a = show a

So now we're ready to call this contraption.  dosort takes
the four functions that relate to our state: buildstate, getresult,
swap, and cf; along with the string to be sorted (I call it string,
but it could have been a list of anything in Ord, really).

The "sequence" function links up that list of functions that
bubblesort created, and execState is what runs them, when supplied
with the output of buildstate.

>dosort buildstate cf swap getresult string = 
>           let sorter = bubblesort cf swap $ length string in
>               getresult $ execState (sequence sorter) (buildstate string)

Here are some test functions which call both suites on the same string:

>test1 = dosort buildstate1 cf1 swap1 getresult1 "sambangu!"
>test2 = dosort buildstate2 cf2 swap2 getresult2 "sambangu!"
>
>main = do
>        putStrLn test1
>        putStrLn test2

I'm certain I'm not doing this in a very elegant way. It appears that those four characteristic functions belong together in a class declaration, and somehow different execution types would be instances of that class, but I was unable to get it to compile that way. Could be my syntax was wrong, or more likely, fuzzy thinking, which Haskell seems to be pretty (justifiably) intolerant of.

Keystroke coding system for Kanji

2006-08-14T18:39:00.000-07:00

I was thinking about ways of entering Chinese characters, and wishing there were a more intuitive way to do it. So here's a scheme I came up with. Obviously a lot of people have been thinking about how to type kanji for a long time, so it's probably been thought of and (implemented | dismissed) before, but anyway, it seems to me like it could work:

In this system each character is represented by a sequence of the letters b, n, m, and k. Each letter represents a stroke or part of a stroke:

b = diagonal downwards to left
n = downwards
m = diagonal downwards to right
k = horizontal

So for every stroke you type a letter, and if the stroke changes directions, you type the new letter, making no distinction between strokes and parts of strokes. I wonder how many ambiguities there would be? Are there any kanji with disputed stroke orders, or is it totally standardized?

Here are the numbers 1 - 10:

一 k
二 kk
三 kkk
四 nknknbnk
五 knknk
六 nkbm
七 knk
八 bkm
九 bknk
十 kn

There would have to be some standard rules about how to represent the little hooks (like the last strokes of 四 and 九) and the ones that kind of curve from one heading to another (like the first stroke of 九).

It seems like a person adept at writing kanji might be able to kind of mentally translate their mechanical skill of writing into these keystrokes.

How we talk about algorithms

2006-08-04T16:17:00.000-07:00

It's often the case that a programmer can quickly state the algorithm they want to use to solve a problem, but it takes significantly more time to cobble together the implementation. There are lots of good reasons why it has to be that way -- explaining something in English presumes an intelligent listener, but the computer you're programming to is not intelligent. But still, I'm wonder if part of the mental transformation that takes place is a conceptual restrucuring, that wouldn't be necessary if a computer language were structured differently.

A good way to look at this might be to examine some programs along with descriptions of their algorithms, and see if we can discern any structural differences, and propose new computer language structures that are closer to the human abstraction mechanisms.

So I want to take as a particular example the "BLACK" problem from this year's ICFP 2006 programming contest. After the end of the contest, participants discussed their solutions to some of the problems, and in some cases posted their code, in a public discussion list. As this was a problem I spent some time with (and didn't solve) I decided to look at the algorithms that other teams used.

Spoiler alert

The contest puzzle was an amazing construction that I'd highly recommend working on, even though the contest is over. I'll be giving away the problem description here (which is a good piece of work just to get to), and some solution algorithms.

The Problem

The problem is described here; basically you're doing a permutation of an ordered list, in steps, where each step can exchange pairs of adjacent items. When a step shifts any item to the right, there is a "plink" sound. There's no sound when shifting to the left. The task is to recreate the steps needed, given an ending permutation and the number of plinks each item would experience in tracing through the steps. So the first problem they provide looks like this:


* x -> (y,z)
* Means that if you drop a marble into pipe x, it comes out pipe y,
* and you hear z plinks
0 -> (3,4)
1 -> (2,3)
2 -> (0,1)
3 -> (1,1)

And one solution is this:

><||
|><|
><><
|><|
><><
><><

Where the ><'s represent swaps, and the |'s represent items that don't change in that step. The problem set started with this puzzle of width 4, and also included problems of width 10, 20, 30, 40, 50, 100, 200, 300, 400, and 500. Your score was based on submitting solutions; the code was not considered -- solving by hand was perfectly legal, if impractical for the larger problems.

Notation

I'll use this notation in the discussion below:

In{st}[x]: the xth hole going into step {st} of the machine (numbering starting with 0)
Out{st}[x]: the xth hole coming out of step {st}.
Target{st}[x]: the desired destination of a marble placed at In{st}[x]
Plinks{st}[x]: the plink count of a marble found at In{st}[x]
Plinktarget{st}[x]: the desired plink count of a marble found at In{st}[x]
Step{st}: The string of |'s, <'s, and >'s representing step #st of the machine

Solution Strategies

I studied the descriptions of solutions on the mailing list, and on the web pages of participants if they were linked from the list archive.

Divide and Conquer

The first insight that most solvers shared was a division into two sequential phases. As stated by Alain Frisch:

All the puzzles in the contest had a lot of plinks, [...] and it was indeed possible to first bubble sort the wires and then start from the identical permutation. That's what our team's solver does.

Jed Davis wrote:

Mine likewise -- it first does the usual selection sort, then figures
out what combination of maneuvers like that pictured above (moving a
ball N places to one side and then back) need to be placed after the
sort to reduce the remaining needed plinks to a form that can be handled
by appending only double-swaps.

Marcin Mucha wrote:

I guess you know that, be some puzzles do have solutions, but you can't decompose any solution as a sequence of a bubblesort and a solution starting from an identical permutation.

It's interesting that they all emphasize the sequentiality; the two phases can' t be done in parallel. Frisch says "to first xxxxxx and then yyyy"; Davis wrote "first xxxxxxx, then yyyyyy". Mucha uses the word "sequence". In your typical imperative language, simply listing two steps in order is sufficient to say "do one, then do the other"; this explicit statement of ordering suggests that sequentiality is not necessarily the default in English.

The Bubblesort

In two of the three quotes above, the posters mention bubblesort with the implied presumption that its application is obvious. Bubble sort is an apt description of an algorithm realizable by this type of machine, since every swap is done between adjacent elements. Here is the code Wikipedia gives for bubblesort:

function bubblesort (A : list[1..n]) {
 var int i, j;
 for i from n downto 1 {
     for j from 1 to i-1 {
         if (A[j] > A[j+1])
             swap(A[j], A[j+1])
     }
 }
}

A reasonably adept programmer should be able to read the description of the problem, and the vague advice to "apply a bubblesort", and implement it with some thought, but without any further clarification. They are making a conceptual mapping like this:

List parameter A: Mapping from exit hole# of current step to exit hole# of final step
n: The number of pipes in the machine
A[j] > A[j+1]: Pipe at j at this step is destined to a place further to the right of pipe at j+1
swap(A[j], A[j+1]): A pipe crossing is added

...so substituting the notation above, we have something like this:


function bubblesort (Dest{st}) {
 var int i, j;
 st = 0
 for i from n downto 1 {
     for j from 1 to i-1 {
         if (Target{st}[j] > Target{st}[j+1]) {
             Target{st+1}[j] := Target{st}[j+1]
             Target{st+1}[j+1] := Target{st}[j]
             st ++
         }
     }
 }
}

This is an interesting mapping because the paradigmatic bubblesort involves mutable storage, but this version builds a list of successively refined permutations. Wikipedia of course doesn't define bubblesort this way. Programmers can make this leap with some thought. Can the concept of "bubblesort" be defined such that something so fundamental is abstracted away? I'm still wrapping my brain around monads, but I think this is what they are good for.

2006-01-22T22:12:00.000-08:00

A Different Implementation of Relation-Chaining

OK, I wasn't really happy with the implemenation the relation-chaining thing I did last week, so I rewrote it. This won't make a lot of sense if you haven't read last week's installment, so go read it if you haven't yet...

This time I have the forward-linking operator sort of equivalent to the python "." operator. If romulus.father == mars, then romulus >> father == rset([mars]); in other words, the set containing mars. rset is a class derived from set. It's convenient to work with sets, because in the case of the reverse-linking operator, there could be more than one result, and I wanted some symmetry between the two cases.

To do the reverse linking, I use gc.get_objects(), which is python's garbage collector's master list of all the objects in the system. I guess that's not very efficient for a large program. In a large program I'd recommend creating a "universe" dictionary, put the objects you really care about it in it, then search that instead of get_objects().

A nice result of using sets is shown in the brother() function; the set operator "-" means to remove items from a set, so (x >> "father" << "father") - x means: find the father of x, then find the people x is a father to, then subtract x from that set, leaving only the siblings.

The only reason I create my own set class, or my own relational_object class, is to get the syntax of << and >> to work. Really, this is a demonstration of a feature I think could be central to a language, and in that hypothetical language you'd build this feature in so it could be used on any objects.

Well, here's the code. I promise I'll move on to something different next week! I just had to get this out of my system.

#!/usr/local/bin/python2.4
from gc import get_objects

class relational_object(object):
  def __repr__(self):
      return ""

  def get_conv_gen(self, att):
      for other in get_objects():
          try:
              if other.__dict__[att] == self:
                  yield other
          except Exception, e: pass

  def get_conv_any(self, att): return self.get_conv_gen(att).next()
  def get_conv_all(self, att): return rset([ x for x in self.get_conv_gen(att)])

  def __rshift__(self, att):  return rset([self.__dict__[att]])
  def __lshift__(self, att):  return rset(self.get_conv_all(att))

class rset(set):
  def __rshift__(self, att):
      result = rset()
      for x in self:
          result = result | rset([x.__dict__[att]])
      return result
  def __lshift__(self, att):
      result = rset()
      for x in self:
          result = result | x.get_conv_all(att)
      return result

class person(relational_object):
  def __init__(self, theName):
      self.name = theName
  def __repr__(self): return "<>"

mars = person("mars")
romulus = person("romulus")
remus = person("remus")
assert mars == mars
assert mars != remus

romulus.father = mars
remus.father = mars

assert mars << "father" == rset([romulus, remus])

2006-01-14T15:11:00.000-08:00

Relation-chaining gimmick in Python

This is just a piece of a whole idea, but I thought you might find it amusing.

There is an RDF notation called N3 that has an interesting syntax for quickly describing a chain of relations linking one node to another.

Here are some examples from the N3 paper:

:joe!fam:mother!loc:office!loc:zip   Joe's mother's office's zipcode
:joe!fam:mother^fam:mother           Anyone whose mother is Joe's mother.

:joe ("Colon Joe" -- sounds like a brand of medicinal coffee, doesn't it?) is an RDF node. The other strings with colons in them, fam:mother, loc:office, and loc:zip, represent binary relations. I think the part before the colon tells you the namespace it's from, but ignore that for now.

The ! is like the "." operator in most object-oriented languages. :joe!fam:mother means "Joe's Mother", and you might say this as joe.mother in some language like Python or C.

The ^ is the converse of !; so if joe!mother == sue, then sue^mother == joe. You can think of !mother as meaning "mother" and ^mother as meaning "child". ^employer means employee, ^owner means possession. "hello, world"!length == 12, so 12^length == "hello, world" (among many other strings).

My mind was brought back to this when I was working on a project with a bunch of related objects in Python, and I was looking for a clean way of expressing complicated queries among them. In my day job I do a lot of ad-hoc SQL querying, and while I don't love SQL, it is nice to be able to fluently, readably, ask some complex questions of a bunch of relations. I'd read that list comprehensions were more or less isomorphic to SQL, but I found when playing with them that my queries were inefficient and not very readable; they were no better than just writing explicit code to traverse the object tree and collect the information I wanted.

I'm not sure if these N3-style paths will be useful in practice, yet, but it was worth playing around with them. The biggest hurdle with them, as I see it, is that there's no easy way when presented with 12^length to know what string is wanted, so you have to have a well-defined universe of objects to work with, and be willing to accept multiple results from every query.

So anyway, here's some code to give you an idea what I've come up with so far:


import pprint

class relation:
 def __init__(self):
     self.forward = dict()
     self.backward = dict()

 def add(self, arg1, arg2):
     if not self.forward.has_key(arg1):
         self.forward[arg1] = dict()
     if not (arg2 in self.forward[arg1]):
         self.forward[arg1][arg2] = True
     if not self.backward.has_key(arg2):
         self.backward[arg2] = dict()
     if not (arg1 in self.backward[arg2]):
         self.backward[arg2][arg1] = True

 def __call__(self, arg1, arg2):
     try:
         return self.forward[arg1][arg2]
     except Exception, e:
         return false

 def get_all_keys(self, hash, key):
     try:
         return hash[key].keys()
     except Exception, e:
         return []

 def __rlshift__(self, other):
     result = []
     for item in other:
        result = result + self.get_all_keys(self.forward, item)
     return result

 def __rrshift__(self, other):
     result = []
     for item in other:
        result = result + self.get_all_keys(self.backward, item)
     return result

father = relation()
phone = relation()

class frank: pass
class jeff: pass
class chris: pass
class andy: pass

father.add(frank, jeff)
father.add(jeff, chris)
father.add(jeff, andy)
phone.add(andy, "101-555-1249")
assert [chris] >> father == [jeff]
assert [jeff] << father == [chris, andy]
assert [chris] >> father == [jeff]
assert [jeff] << father == [chris, andy]
assert [andy] << phone == ["101-555-1249"]
assert [chris] << phone == []
assert [andy, chris] << phone == ["101-555-1249"]
assert (([chris] >> father) << father) << phone == ["101-555-1249"]
assert [chris] >> father << father << phone == ["101-555-1249"]

Some things to note about this implementation:

I used classes like "jeff" and "chris" for nodes. You could use any Python objects; the "class X: pass" syntax is just a cheesy quick way to create a dummy object to play around with. In Python a class is a kind of object.
I used >> and <<>
nstead of the RDF "node", I use a list with one or more python objects in it, in this case strings. I'm using a list as kind of a half-assed monad. Since a >> or <<>
I define a relation object which holds all its pairs of related things in hashes. It's probably not very efficient. I originally thought I'd just use the members of objects as the relations, so that the natural joe.mother would be the basis for the relation joe >> mother. But that didn't fit in very well with the list thing. If Heather has two mommies, you can have:
```
mother("Ann", "Heather")
mother("Patricia", "Heather")
assert ["Heather"] >> mother == ["Ann", "Patricia"]
```
as opposed to
```
heather.mother = ann
heather.mother = patricia
```
where Patricia just overwrites Ann. This makes Ann sad.
Maybe there's a better way around this.
I'm not sure I've got the precedence the same as N3 has it.
It should be sets, not lists. ["Ann", "Patricia"] should be considered the same result as ["Patricia", "Ann"].

Next time I'll try to apply this to a more interesting problem to see if it holds up.

2004-06-11T06:07:00.000-07:00

Paul Graham also has some pie-in-the-sky thoughts about computer languages; see his articles, Hundred-year language and his work on a new dialect of Lisp, Arc. Arc is a little more down-to-earth than the Tunes HLL, and he appears to have done some work on it.

2004-06-11T06:02:00.000-07:00

The Tunes project has some requirements for an unnamed "High Level Language" for their project, which has a lot of good ideas init. As far as I can tell looking at the web page, it's kind of vaporware at this point. And maybe doomed to remain vaporware, since the requirements seem so abstract and idealistic. But anyway, some of their ideas have crossed my mind too, and they might at least server as a thoughtful critique of how current programming langauges feel inadequate to people.

2004-05-20T21:37:00.000-07:00

Two good articles by Cory Doctorow (Metacrap) and Clay Shirky (The Semantic Web, Syllogism, and Worldview), expressing skepticism about the Semantic Web.

Shirky says most human thought isn't deduction from syllogisms, it's much more fuzzy and heuristic than that. Doctorow points out lots of good reasons why metadata will be crap in practice.

These ideas relate to better programming languages too. There's an impedance mismatch between human concepts and the way computer software systems tend to classify things. We just don't think as rigidly about things as computers do. We get frustrated with how software will go mindlessly clanking down the wrong path (for example happily cranking out copies of a virus and emailing them to all your friends), but when we try to build smarts into it, we're frustrated by just how dumb those smarts turn out to be.

Human computer interfaces, from GUIs to languages to development and testing environments, need to help our squishy minds navigate the bizarre tinkertoy syllogismatrons we're forced to build. While we frantically look for ways to teach software to think more like we do.

2004-04-25T17:39:00.000-07:00

I just stumbled on a weblog about programming languages and their design, called Lambda the Ultimate. Similar to what I want to do here, although I want to focus more specifically on languages that bridge the gap in some interesting way between natural human languages and traditional computer languages.

2004-04-22T15:51:00.000-07:00

Apocalypse 12 is out.

In case you live in a cave, the Apocalypses are Larry Wall's occasional manifestos (manifesti?) about how some aspect of Perl 6 will work. I read them with great interest because I like how Wall thinks, and I'm an avid user of Perl, and Perl 6 has some great ideas in it. I like hyperoperators and the new regular expression syntax. That being said, I'm getting kind of worried that Perl 6 is going to be too crufty. Look at what you can do with subroutine signatures. It seems unnecessarily complex and cryptic.

Of course I thought that back when I was learning Old Perl, but now I know it well and can use pretty efficiently, so I'll withhold judgment on Perl 6 until I get a chance to use it.

2004-04-19T10:53:00.000-07:00

What this blog is about

The last post was mostly a test. What I want to do here is review computer languages that bridge the gap between computer language and human language in some interesting way.

Lojban is an attempt to make a human language somewhat more approachable by computers -- it has a yacc-parseable grammar that is syntactically unambiguous. In practice so far it has been used for communication between humans, not to specify or constrain a computer's behavior in any way. But it's a good example of an effort to think about some of the differences between the two kinds of language and find halfway points.

I do think that someday computers will be able to cope with human language. For programming I think we'll always need something a little more precise (like the language used in human legal contracts, maybe) to avoid some ambiguity.
But that day could be a ways off; why not meet the machine halfway for now? High-level languages have come a long way from raw machine code in doing this; I'm interested in seeing in what other ways computer languages can be more human without requiring outright artificial intelligence in the computer that uses them.

2004-03-28T15:28:00.000-08:00

Kevo was an object-oriented language where classes were derived from objects rather than the other way around: a "family" of objects are ones that have the same signature. Families change dynamically as object properties are changed at runtime.

I haven't been able to find much detail about Kevo; it looks like it emerged around 1993 and its author is Antero Taivalsaari who has since done a lot of work since then on Mobile Java (J2ME). Here's an interesting paper that mentions Kevo:
Psychological criticism of the Prototype-Based OO-Languages