Archive for July, 2006

Oh yes, that research stuff

I had a productive conversation with Didier Rémy this morning about various type inference topics; he had given a very nice talk on the latest MLF research yesterday. He also seemed quite interested in OCamlTeX. I read through some papers by Pottier on solving subtyping constraints in preparation for beginning work on InforML.

I'd like to think that I should have the higher-rank extension to AspectML finished soon, and then be done with the initial InforML prototype in a couple months. Really, how soon I graduate is proportional to how quickly I can get it running. It is unfortunate that I have a very clear idea of most of the algorithms and things that need to be done, but that there will be a considerable amount of grubby hacking and plumbing to realize them.


The Bringhurst Correspondence

I finally got around to asking Robert Bringhurst whether he minded if I published excerpts of his response, and he suggested that it might be better to just make the entire thing available. So here are the questions Chris and I asked, and Robert Bringhurst's response. Enjoy.

Comments (2)

Avoiding typographic pretentiousness?

I just saw a discussion on the LaTeX mailing list started by someone who was complaining that their documents looked "too good for correspondence", and wanted suggestions for other fonts to be using.  I found this kind of strange.  There is such a thing is looking too formal, but that is a separate issue than "looking too good".  There are certainly fonts one can choose to make a document less stuffy.

Comments (2)

ICFP Programming Contest coda

By the time scoreboard closed we had dropped to 24th place. Mostly the problem was that by Sunday most of us were pretty burnt out and didn't make that much additional progress. Still, I think we performed pretty respectably, and beat out more than ninety percent of the competition.

The contest was designed very differently than in previous years; I'm not sure if this was a good thing or not. As I mentioned previously, myself and others felt that it primarily encouraged hacking up throw-away code. Much credit goes to Luke and Peng for their work on our virtual machine: It appears to be one of the fastest around. I helped with a little bit of debugging of the virtual machine, but mostly I worked on trying to solve the ADVIS, BLNCE, and ADVNTR tasks.

The ADVIS task was essentially to develop a method of computing around the silly rewriting semantics they had chosen for "O'Cult". Most of the time I focused on trying to figure out a general method of compiling or transforming a more sensible language to O'Cult. In the end, I believe the general solution was approximately: use a continuation passing transform to ensure computation evaluates the way you'd like and use SKI combinators to write your continuations. It was apparently possible to do better by just attacking the problem directly, which is not surprising given that I was trying to develop a general solution so for the first part so I could use it to make writing the second part trivial. However, in the end I decided it was too much effort to write a tool to do all the work, so I mostly used some small bits of code to compute SKI encodings of λ-terms.

I also spent some time trying to figure out the "trick" behind the Balance programming language, which was essentially a very wacky 8-bit register machine. However, it is still not clear to me that there was any known methodology for solving the problem. The best I could figure out was to use brute force to find ways of synthesizing more sensible operations, and then build a little assembler on top of that. However, I did not have the time to try writing a program to do the brute force searching, so Brian wound up solving about half the problems by plenty of thinking and experimentation.

Peng worked out about the first half of the "adventure" game program, by writing a "robot" client in Haskell to find the appropriate parts and solve the constraints. After that though, came the extremely novel problem of having to reprogram the game's command processor to perform actions that would not be possible otherwise. I made some very good headway on this, but became fatally stuck on trying to figure out how to read a blueprint whose contents were block by the game's "Censory Engine". I spent just about all of Sunday afternoon trying everything I could think of to solve it, and Peng put in a bit of time too. I'm told by other contestants after the fact that I was actually on the correct track by trying to read the blueprint via indirection, but somehow we must have not gotten some detail quite correct and had abandoned that tactic too early.
It was certainly a nice distraction, and I look forward to seeing how they actually constructed their programs and solutions.

Comments (3)

Rendering inconsistency

The other day while looking at Jason Reed's latest specimen for his typeface "Austin", I noticed a rather annoying difference in the italic version of the letters "i" and "j"

Picture 3.png Picture 1.png

However, when I mentioned this to him he said he didn't notice anything, and said that the dots both used the same control points. Puzzled, I tried loading the specimen in Acrobat Reader rather than Apple's Preview, and it looked just fine

Picture 2.png Picture 21.png

I found this quite strange because you would think that given Apple helped develop the TrueType format that they would know how to write a very good renderer. I can only guess that perhaps the hints FontForge produced weren't quite correct and that Acrobat uses some non-standard rendering/hinting algorithm.

I'm also a bit surprised at how much worse these PNGs look when I upload them to WordPress than they do in Photoshop. I'll have to look into it.  Update: I think I figured it out.  For some reason WordPress was insisting on resizing the images.


Another day of hacking

We've been continuing to make progress, but several teams have been overtaking us. In particular, there seems to be a huge number of points to be had for the "ray tracing" problem in the two-dimensional language. Last I heard from Peng he was making good progress on a robot to solve the "adventure game" puzzle. We're still in the top ten, which regardless of where we place in the end, is pretty respectable out of 238 teams (so far).

I finally cobbled together solutions for the O'Cult puzzles. After finishing the first one, which involved addition and multiplication, I thought I had figured out a way to generalize the solution to such that I could write a small compiler for the "document optimization" problem. However, I hadn't quite found the right pattern and wound up mostly constructing it by hand with a few small bits of code to generate the appropriate patterns.

Overall, this contest seems to have been much more about quickly writing throw-away code, rather than producing beautiful, extensible, and maintainable code. It has still been fun, at least when we aren't cursing their sadistic puzzles, but it is unclear that this contest says anything specific about the benefits of functional programming. Our Subversion repository is a melting pot of languages. So far I believe we have used C++, shell scripts, Haskell, OCaml, and Perl. I am hoping that the organizers release the tools that they used to construct the contest, because I'm very curious as to how they did a few things.

Anyway, it is getting late and I should probably get some sleep to prepare for a final push tomorrow.


Squeaking ahead

We've made it to third place (as of Saturday July 22, 2006 12:39PM). Now if I could only figure out where this darned bug is in my Advise interpreter.



Our team, Free the Mallocs, is holding down a respectable 7th place at the moment.


You may have already won!

For the past day and half, my focus has been on the ICFP 2006 Programming Contest. Yesterday, the organizers released what they called "The Codex" without any explanation of its nature. This of course led to considerable speculation and analysis. The organizers have been trying their best to mislead us with red herrings. For example, embedded in the codex is the following GIF image

Cult of CBV

Not to mention another version of the same image in a bitmap format, as well as numerous conspiratorial strings.

However, it turns out that the codex is actually an executable for the "Universal Machine", so the first order of business was to write a virtual machine to run it. Peng hacked out a Haskell based virtual machine in short order, but it proved to be far too slow to be usable. Luke came to our rescue with a C++ based virtual machine that was fast enough to get us to the point where we got the codex to dump a new program. The fun was only beginning.

The Universal Machine image produced by the codex is an image of the "UMIX" operating system, that presented us with a login. Logging as a guest presented us with faux Unix shell where we discovered we had e-mail, which provided us with more clues. In particular, the task was to finish a program written in BASIC to crack passwords on the machine. That's right. They implemented their own BASIC interpreter inside of this thing. Not only that, to make life difficult, all numbers in this variant of BASIC had to be entered as Roman Numerals.

Cracking passwords made several other accounts accessible, each presenting challenges to obtain more points and clues. For example, one account had an adventure game in its home directory. Another had an interpreter for a two-dimensional circuit based language. And another an interpreter for some kind of term rewriting language called O'Cult. There also seems to be a problem involving "antomata". Yes, "ant".

The folks at CMU have put a crazy amount of effort into this. I'm almost certain that they must have some kind of ML to Universal Machine compiler that they used to write all of this.

Anyway, I'm just resting my brain for now, and will perhaps attack some more problems before I call it a night. However, at the moment, I'm really curious as to where any additional programing effort external to their OS may be required. Because just about the only way to go to get a half-way decent virtual machine was to use C or C++. And it seems kind of suspect that they would want to encourage people to use imperative languages to win the contest. We'll see I guess. There are still forty-eight plus hours left in the contest.


Now we’re cooking..

12:00:00 1/1/19100
Welcome to Universal Machine IX (UMIX).
This machine is a shared resource. Please do not log
in to multiple simultaneous UMIX servers. No game playing
is allowed.
Please log in (use 'guest' for visitor access).

Comments (1)

« Previous entries Next Page » Next Page »