Lincoln's blog

Value Systems, AI and Human Existence (part 2)

My strengths lie in software construction, so that is where I expect to contribute most.

posted at: 16:10 | path: /self | permanent link to this entry

Building a Kegerator

I brew beer at home. My roommates and I decided to take it to the next level and build a kegerator (keg refrigerator) so we can have cold draft beer dispensed from a tap in our kitchen.

There are lots of parts. To dispense draft beer, at a minimum you need: kegs (pressurized containers that store and dispense beer), a CO2 tank (to pressurize the kegs), tubing and disconnects for gas and liquid, and some kind of faucet.

To keep it cold, you need some kind of fridge. We are using a GE chest freezer, and we're using a temperature controller to prevent it from actually freezing the beer.

To avoid drilling big holes in the freezer itself, we used the popular method of building a wooden collar. You remove the lid, put the collar on the edge of the freezer, and then reattach the lid to the collar. You can easily drill holes in the collar to allow taps and cables through. And if you don't want the kegerator anymore, the freezer can return to normal freezer status.

The temperature controller is also homemade. I picked up an Arduino microcontroller, temperature sensor for Arduino, relay for wall current, and a few other electronic parts, so my Arduino can turn a plug-in device on or off.

Item	Source	Cost
Refrigerator assembly
GE Chest Freezer 7.0 ft3	Home Depot - we got their floor model for cheaper	150
Collar lumber, screws, stain, & caulk	Home Depot	15
1st tap assembly
Keg kit (1 Cornelius keg, CO2 tank, regulator, fittings)	Rebel Brewer	180
Fill CO2 tank (it ships empty)	Modern Brewer (local homebrew shop)	25
1st Perlick faucet	Modern Brewer	40
1st shank, beer nut, and washer	Modern Brewer	20
2nd tap
2nd keg	Modern Brewer	40
2nd Perlick faucet	Modern Brewer	40
2nd shank, beer nut, and washer	Modern Brewer	20
Gas 5-way manifold	Modern Brewer	120
Gas line 2-way splitter and valve (no longer used)	Modern Brewer	40
2nd beer+gas line, disconnects, & misc supplies	Modern Brewer	20
Last 2 taps
2 Perlick Faucets	RiteBrew	50
Homemade temperature controller
Arduino Duemilanove	Modern Device	30
Arduino Temp Sensor	Modern Device	10
Relay & misc parts	Digi-Key	20
	Total	820

For the collar, we followed this guy's instructions. We bought 10 feet of 2x6 pine from Home Depot, measured it against our freezer, and cut it with a table saw. We screwed it together with 2.5" wood screws. You can see the screws on the front on one of the pictures above. If I had thought ahead more, I would've made the short sides longer and screwed it in from the side instead.

After putting the collar together and sanding it, we applied pre-stain to the soft pine, let it dry for 2 hours, applied stain, and let it dry for 24 hours. Then we went to the local homebrew shop to pick up the faucet and shank. They sold us the parts and loaned us the correct hole saw for cutting the faucet holes. So we cut the holes and stained it once more.

Then we stuck it onto the freezer by laying down a line of caulk and putting the wood on. Left it for 24 hours with our brewpot full of water to weigh it down. We should have used new silicone caulk, but we used 10-year-old caulk which didn't set properly. Nonetheless, the collar doesn't budge, so we're leaving it that way.

Last step is the temperature controller. I don't know too much about electronics, but I know enough to be dangerous. In this case, I was attempting a project I'd never done before: switching mains voltage (120V powering the freezer) with a microcontroller.

The mains voltage must be isolated from the arduino using a relay, which lets us have separate switching circuit and power circuit. My original plan was to use a 5V relay, with the coil across the Arduino's digital pin and ground.

However, I read about it enough to determine that that's a bad idea: the relay is an inductive load, which produces "back emf" when it is turned off. Back emf is a voltage spike which can blow transistors if you're not careful. The way you deal with back emf is with a flyback diode. I also used a transistor on the Arduino's output pin, because I wasn't sure how much current the relay would draw through the Arduino. In all, I ended up using the circuit given here. Soldered it together without a breadboard. It's been a while since I soldered anything, but I managed to get the device working on the first shot -- no shorts, no blown circuit breakers, or anything.

Initially I had the temperature sensor about halfway to the bottom of the fridge, and it was reading very high temperatures. The fridge has a very strong temperature gradient; it can be below freezing at the bottom when it's still 50F at the top. (This is probably due to the poor insulation at the top due to the wood and holes through the wood.)

So I made an extension cable for the temperature sensor. Now the sensor itself is nearly at the bottom, and the Arduino and the rest of the kit can sit outside the freezer. After only a few soldering problems I had it working. Of course, while trying to install the extension cable, I snapped one of the pins off my transistor, so I had to redo the soldering for that circuit.

For the party this weekend, I wanted to label the taps. I discovered that whiteboard marker works beautifully and erases well from the front of the fridge.

And that's a kegerator! I'll continue updating the price sheet above, and adding descriptions of anything interesting we come across as we fill out the four taps. And if you are near Boston, feel free to stop by, have some beer and talk about the project.

posted at: 17:38 | path: /projects | permanent link to this entry

Why Someone Like Me Should Go To Grad School Now

The primary reason I should be convinced to go is that I want to do research. I've done some research-like work in the past, learned a lot, and found it fulfilling: my undergrad work with the programming language we were designing, and the work on the Starcraft AI.

In research, you are working on open-ended problems. That's good: I have (actually) tuned my life to work on these.

posted at: 17:33 | path: /self | permanent link to this entry

Value Systems, AI and Human Existence

The Singularity Institute has recognized that nonhuman intelligences can have -- or evolve -- arbitrary value systems. And arbitrary value systems seem likely to be incompatible with ours: human value systems are generally based on continuing human existence, which seems fairly constraining in the scope of all value systems. For example, any value system which wants to consume lots of a resource that humans depend on (air, sunlight, carbon atoms, habitable planets, ...) will probably conflict with most human values.

So why do we still exist? No intelligence has yet succeeded in consuming our resources. We've not even managed to find convincing evidence of the existence any other intelligence which can compete for the resources we need. Lucky. (Or apply the anthropic principle.)

However, people are working on improving artificial intelligence in software. Currently AI is not very smart or powerful. But contrasted with our own brains, AI is very flexible -- it doesn't come with any assumptions or value systems and it is easy to change by editing the source code. It's easy to imagine an AI which could edit its own source code. ¹

Given that an AI is editing its own code, and doing so in an intelligent manner, with the goal of making itself more intelligent, there is no obvious limit on the rate of improvement and scope of intelligence that such a self-improving entity could achieve. This is what's known as the technological singularity -- an AI that improves itself rapidly until it vastly outstrips human intelligence.

Up to this point, the only thing we are assuming about an intelligent AI's value system is that it wants to make itself more intelligent. Without any other assumptions, this isn't likely to be compatible with the human value of continuing existence -- for example, to become more intelligent, perhaps the AI needs all the sunlight hitting earth for energy to run more brain cells. Since the AI is so much smarter than us, it would outsmart us to get itself to that point, extinguishing the human race in the process. Oops.

Having followed this train of thought, and considering it a serious risk to continuing human existence, the Singularity Institute was formed. Its purpose is to mitigate the risk of human extinction by technological singularity. Rather than trying to prevent a singularity from occurring, which seems unlikely to work², SIAI is trying to figure out how to make an AI whose values are sufficiently aligned with human values such that singularity doesn't pose significant risk of human extinction.

I recently learned that SIAI is sponsoring Visiting Fellows -- essentially an internship at the Institute to work on these problems. As part of my application, they asked me to explain SIAI's purpose and how I can contribute. Having done the former, I will attempt to answer the latter in the next blog post (linked here when it's ready).

posted at: 15:44 | path: /self | permanent link to this entry

Introducing Break Ideas

I mentioned in a blog post that I had this idea for a project called Break Ideas. Well, it's working now, sorta. I started working on it because at BarCamp Boston this weekend, there was a programming contest where you were supposed to learn a new language and implement something useful in it. Well, I learned Arc for this project.

GitHub project page

What is Breakideas? It's an idea sharing site. I started to spend a few minutes just letting my mind come up with creative thoughts each day, and I felt like I was discovering a lot of interesting and occasionally useful insights about technological and social issues. Eight minutes is the length of my twice-a-day wrist break, and it seemed like a reasonable length of time to think -- not so short that I couldn't develop any ideas, but not so long that it takes a significant chunk out of my day.

How should I use it? Go to the site! Take a break! Think! Write a summary! If you can't think of anything, other people's ideas are provided to give you inspiration. Pick one of them and develop it further. If you want people to be able to contact you, put your contact information in your profile.

Thoughts on Arc after about 6 hours using it:

I feel like I can see into PG's brain!

Paul Graham, PG for short, is the designer of Arc. He wrote Hacker News in it. As far as I know, News is the only substantial production app written in Arc.

The language is basically a dialect of Scheme, but it has a very different feel from the little bit of Scheme that I've done. There are a TON of little macros and shortcut functions that capture a pattern that showed up -- one I liked was iflet which, given a variable and a test (as well as a then-body and else-body), binds the variable to the result of the test, then executes the then-body or else-body depending on the truth of the test. It's a useful idiom for when something can be nil. The sheer number of these little shortcuts makes reading other people's (pg's) code hard, because while I can sometimes guess at their behavior by name, the precise semantics can be hard to divine.

Other than the pile of macros, the language is very satisfying to program in. I was successfully able to read, understand and modify the blog.arc program (distributed with the arc source) to do what I wanted, and in a fairly short period of time I had something functional.

I liked Arc for its simplicity in implementation -- looking at the source code and making tweaks was extremely feasible, as well as the many features it provided to reduce friction in web development.

I had trouble with the heavy usage of macros in the example code (treating them like functions is a bad idea), as well as the built-in user authentication system (it seems quite inflexible). The development environment REPL currently requires 3 commands after pressing Ctrl-C in order to restart the server and pick up your changes (one in MzScheme to get back to Arc, one to reload the code and one to start the server).

Overall I'd recommend it to anyone who wants to do hobby web development, and doesn't mind working in an environment which always feels like a prototype -- good because it's simple enough to be easy to change, but bad because it doesn't seem robust.

posted at: 04:55 | path: /projects | permanent link to this entry

JIT review paper

I am compiling links and notes to papers about JIT bytecode techniques. Eventually, this collection will become a full-fledged review paper.

Tracing JIT compilers

http://lambda-the-ultimate.org/node/3851#comment-57761

Good discussion and links here. Highlights: LuaJit, Dynamo

Mozilla JagerMonkey

http://hacks.mozilla.org/2010/03/a-quick-note-on-javascript-engine-components/

Interesting hybrid approach.

Equality Saturation

http://lambda-the-ultimate.org/node/3220

Not extremely JIT related, but interesting nonetheless. Instead of applying peephole optimizations, a model is constructed which represents all programs which do the same thing as the input. Then the problem is treated as an actual comb.opt problem and the answer is searched/solved for.

Dynamo

http://arstechnica.com/reviews/1q00/dynamo/dynamo-1.html

Dynamo is a JIT translator from a native code to itself, optimizing in the process. Most gains are probably from turning complicated control flow into straight-line code. Transmeta Crusoe was a hardware-accelerated version of a similar concept.

posted at: 00:40 | path: /projects | permanent link to this entry

Solving the procrastination problem

I love sites like reddit and Hacker News. They occupy me when I'm bored at work, and they expose me to a huge number and variety of comments, blog posts and news stories, so I feel like I am learning a lot about a lot of topics.
They give me the sense that I'm staying current on technology.

However, over the last two or three years, Reddit and HN have become the "go-to" sites when I have a browser open. I need only to type a single letter in my browser in order to visit them. Nearly every time at work that I tell my code to compile, I tab over to Firefox and refresh HN, looking for something new, any snippet of information that will capture my interest for a few short minutes. And it's all nearly unconscious at this point. Recently I idly typed news.ycombinator.com in the address bar when I was already at news.ycombinator.com. I noticed, and was surprised, only because the page didn't change -- I didn't get my fix.

And the addiction metaphor is apt. I have observed my own nearly unconscious, highly trained behavior to go to a new page, scan down the page for unread headlines, and learn a new tidbit of advice from a blog about Haskell, JSON or entrepreneurship. As I understand it, learning is connected with dopamine, so it sounds reasonable that someone could become addicted to it -- dopamine is implicated in lots of other addictions, including gambling, drugs and sex. I also noticed that my "learning addiction" is interfering with other aspects of my life, specifically my own sense of productivity; there are plenty of days where I come home thinking "if only I hadn't spent so much time on Hacker News, I might have gotten all this other stuff done". And I beat myself up over it, a little bit.

I can't be alone. HN has a "noprocrast" feature, where it will give you a friendly message and prevent you from visiting the site if you come too often. The existence of this feature makes me think that other people have some form of this addiction too. But the feature is frustrating to use: every time I am denied my fix, I get a little bit annoyed, and when I'm annoyed, I don't go back to my work -- instead I visit Reddit or Slashdot to cool down and get my fix there. It's much harder for me to focus when I'm frustrated, so it sort of makes the problem worse. It doesn't help that HN's noprocrast message shows a timer (you can't come back for 30 minutes!) which lets me look forward to exactly when I can come back, and that's distracting too.

So I'm looking for other ways to train myself off of this habit. So far, while writing this post, I already had the urge to visit HN four times. Three of those times, I noticed what I was doing, and stopped myself from loading the page. Once, I did actually load HN; I was thinking to myself "I shouldn't be reading this, I have a blog post to write, but I just want to see what's new on this one comment thread."

One way of easing my addiction could be reducing the delivery rate of the drug. If HN had more momentum (for example, if the top stories changed more slowly), it might reduce my desire to come to the page, because my expectations of getting my fix would be lower. Then again, maybe it would just cause me to look at the "new" page more often, which just shows the 30 newest submissions, regardless of quality.

Here's a more radical idea: what if the whole site only updated once every four hours? No realtime comments, no stories, etc.; when people make submissions and comments, the site queues them up for the next big update. This would still have the countdown-timer effect, giving me something to look forward to, but there would be no incentive for me to refresh the page between those moments. (I note that you could implement something like this cheaply using an HTTP proxy by tweaking the caching headers.)

I am also trying to come up with productive activities which compete with browsing for when I'm bored. I don't always want to think about work during compiles, but I also don't want to visit Hacker News and lose half an hour or more.

So what makes me feel productive that I could do at work? Well, when I get a few minutes to brainstorm, I sometimes come up with ideas which seem original and worth keeping. It seems like browsing Hacker News directly cuts into time that I could otherwise spend just thinking, away from the computer and other distractions. So here's my idea: when you're bored, you go to this site, and it presents you with some other people's postings as inspiration, and instructs you to spend eight minutes brainstorming about whatever you want. You step away from the computer, come back in eight minutes, and the site asks you to write down what you thought about. Then the next person who comes to the site might see your idea as inspiration.

Clearly there are some issues -- it would be nice to have usernames and attribution -- but I think the idea is sound, and I know that I would probably contribute to it sometimes instead of visiting HN. I know from experience that it takes some mental effort to choose to produce something new instead of just consuming, but I am willing to put in that effort if it makes me feel less like my time is being wasted.

posted at: 20:50 | path: /projects | permanent link to this entry

My blog is working again

Blog was broken because of a server upgrade. It was broken because the code I'm using (pyblosxom 1.4) was testing for the presence of a feature and behaving differently.

The feature is the standard library's wsgiref. If the wsgiref module is present, it tries to use it instead of just calling the CGI script directly. Unfortunately the wsgiref module uses some settings for PYTHONPATH that I didn't bother to try to figure out, so the script broke.

posted at: 23:09 | path: /projects | permanent link to this entry

Git-rebase and Django's dev server

At Newsbrane internally we use Git to manage our repository, Python for much of our Web code, and Django as our framework. I just had an interesting time diagnosing a problem which I thought I would share.

Git is a well-known revision control system. I'm not going to go into it much save to say that it lets you edit the history of your changes to the code, as long as you haven't shared those changes with anyone. Normally when you're working with Git you make a bunch of changes and then when you want to share them, you merge your changes with anything that's changed the last time you synced up. Doing this in Git requires making a 'merge commit'.

At Newsbrane, we prefer not to make merge commits when they're not really needed -- we pretend that most small changes to the code happen linearly, one change after the other. This reduces clutter in the log and makes it easier to examine the history. But in order to do this, when you sync up with the repository, you have to perform a 'rebase' -- edit the history so that your changes seem to have been applied after the other guy's changes instead of in parallel. So while most people don't have much use for editing the history, we make the rebasing process a common part of our development cycle. The way rebasing works is that it generates the diff of the actual changes you made and 'replays' them atop the other guy's changes, one by one.

Anyway, I had just tested and committed a local change and intended to share it with the company's repository. I downloaded the code, noticed that there had been a remote change, so I rebased against it. Since this rebasing process is a bit fragile, the best practice is to test your code before pushing to ensure that the rebase didn't screw anything up. I tested the code, and it was broken. Oops! The rebase screwed up? I started looking at the backtrace. I stared it it for about 5 minutes and I just couldn't believe that that line of code could fail. Not in the way that it did. So I went looking elsewhere.

Maybe my testing failed. Django, the Python web framework we use, has a development server which lets me test my changes locally without having to publish them. The development server has a nice feature where it reloads the code when you change the source, so you don't have to explicitly restart it. Thus I generally leave it running all the time. In this case, it was running when I tried to test the code, and so I had an idea: "oh, the rebase confused it somehow, I'll restart it".

Well, restarting the dev server didn't fix the problem. Okay, so what's wrong? Based on the error, it seemed like this one file wasn't properly updated after the rebase. But I checked the source and the file was fine. Some weird operator precedence error? I looked at the backtrace again. Impossible. Check 'git status' -- if anything is different in my source code from the committed version, it'll let me know. But nothing is different. Pull my hair out, walk away from the computer.

Is the operating system's buffer cache becoming corrupted due to the interaction between 'git rebase' and the devserver? Seems very far-fetched; the operating system isn't that fragile. I'm thinking about every layer between my monitor and the disk. There's caching everywhere... surely one of these caching layers is responsible?

Programming language. Python. Python "compiles" its modules to *.pyc (bytecode) files when you load them. It doesn't compile them every time, or there would be no need for pyc files at all (it would just keep them in memory). But it has to compile them if you changed the source. Wait! Does it really?

How does Python actually determine whether you've changed the source since the last time it compiled it? It uses the date. If the date recorded in the compiled file doesn't match exactly the operating system's date of the source, it will recompile the file.

OK, now I understand what happened: we saw a race condition between the rebase and the development server. The devserver watches for changes in the files (I still have no idea how it does this), and rebase updates them quickly. As part of its operation, the rebase must update the working copy files in place for each change that it is applying. The devserver noticed the mid-rebase update (with the old version of the source), reloaded the code, causing Python to compile the module. Right after it started to reload the code, the rebaser applied my change and wrote the new Python source file out -- in the same second that it had written the previous, unchanged source file. Once the devserver finished loading the module, the .pyc for the old source is written to disk, with the modification time of the old source file (same as that of the new source file), tricking Python: Python has no way to know to recompile the source file.

So there you have it. A rare race. Who to blame? I don't think I can really blame the development server. It didn't do anything especially unexpected -- it was really the victim. Maybe we can blame it for trying to read the working copy directory while Git was writing to it. Should we blame Git? Perhaps: I can't think why it should need to write to the working copy during a rebase until it's done or finds a conflict, but maybe the developers were lazy and this was the easiest way to implement it.

But I would actually like to blame Python, which uses a fragile caching strategy for module recompilation. Modification time, especially with such a coarse (1 second) granularity, shouldn't be the only shootdown criterion for any type of cache, because sometimes lots of stuff can happen in 1 second.

Anyway, to solve the problem, I just used the UNIX command 'touch' on the Python source file (which just updates its modification time) and it started working. Like magic. Exciting, isn't it?

posted at: 04:28 | path: /newsbrane | permanent link to this entry

Cavendish's Physics Experiment

Joe Marshall posted the details of his replication of the Cavendish experiment on his blog. At the bottom he didn't do the calculations, so I got excited and worked them out.

Here's my math:

Laws

F = ma (Newton's motion)
x = sin t/(2pi*T) (simple harmonic motion with period T)
F_s = -kx (Hooke's law)
F_g = G m1 m2 / rad^2 (newton's grav.)

Observations

m1 = 0.9kg
m2 = 3.6kg
T (period of oscillation) = 40 min

To find the distance between centers of mass, for the G calculation, I had to guess based on the objects he used.

He said 1 inch, I assumed this was one inch separation between edge of the water jug and edge of the lead cylinder. Assumed radius of milk jug = 9cm; lead cylinder = 2.5 cm; separation = 2.5cm, for a total of 14cm between center of mass.

rad_g = 0.14m

I also had to assume he placed the centers of the lead cylinders at the end of his 3ft dowel.

rad_dowel = 1.5ft

And I also assumed that he was projecting the laser onto a perpendicular wall (20ft away):

rad_wall = 20ft

light moved "1 or 2 inches": I assumed 3cm

delta_x_wall = 0.03m

Calculations

First, find the spring constant, k, for the hanging system.

Doubly differentiating the harmonic motion equation and solving leads to:

a = -x / (2pi * T)^2

Substitute f = kx and f = ma

k = m / (2pi * T)^2

Use m = 2m1 (2 lead weights in motion). Neglect the mass of the dowel. I got

k = 1.9 * 10^-5 kg/sec^2

Now we can figure out G. By similarity of triangles,

delta_x = delta_x_wall * rad_dowel / rad_wall

By hooke's law, F_spring = k (delta_x). Since we are concerned with the system's new rest position, total forces are zero so F_gravity = F_spring.

There are two instances of gravitational interactions we're measuring which sum:

F_spring = F_gravity
k*(delta_x) = 2 * G * m1 * m2 / rad_g^2

Plug in values and solve for G.

G = 1.32 * 10^-10

whereas Google says

G = 6.67300 * 10^-11 m^3 kg^-1 s^-2

(too big by about a factor of 2)

posted at: 21:00 | path: /projects | permanent link to this entry

Evernote might just change my life

I've just received a new iPhone (23rd birthday). One of the first applications I installed was Evernote. They bill it as an extension for your brain and it's likely I'll soon become severely dependent on it.

You see, I've got an organization problem. I don't want to keep things organized. It's not that I can't: there's a delicately balanced pile of incredibly important papers in my room, and if anyone or anything were to disturb them, I'd be screwed to the tenth. But, predictably, it's inefficient and highly error-prone. The main psychological barrier to me is that organization is basically a lot of wasted effort: it takes a long time (and lots of filing boxes, which I don't yet own) to sort and store everything, and I'm unlikely to need whatever it is that I'm organizing (so I would like to save time and not organize it). The drawback is that on the rare occasion that I do need it, I'm unlikely to be able to find it unless my collection is neatly organized.

Furthermore, I really have to limit the number of documents I keep, to prevent the stack of papers from overflowing. I don't keep receipts for more than a few days, for example, and thus I have no idea how much money I spend. I make efforts to keep old bank statements -- but the few times that I've needed to look something up, I was able to find ten or twelve old statements, but the one I need has never actually been there. I manage to successfully keep my passport and incorporation documents and such, but only barely. There's no chance in hell I can keep more frequently useful but less important things, like takeout menus from nearby restaurants, product warranty documents and manuals, CD-keys, and so on.

I think Evernote is about to change all this. It's a personal notes database. The notes are stored on their server. You can type notes in and search them out later. You can take snapshots with your iPhone and upload them, and the system recognizes any text in the snapshot and indexes it for search. This is an ungodly killer feature. It means that I just have to think "Gee, this might be useful info later", whip out Evernote and take a snapshot. I never have to decide whether I will actually use the thing. As long as it can be digitized, I can save it, and that's crucial.

I've often thought about using Spotlight on the Mac for this, but it's never clicked for me. No text recognition, no easy way to photograph documents for later use, search scope is too great (I don't want it to search every document I've ever edited -- most of that stuff I know I'll never need again). Evernote seems to perfectly fit the niche I have.

Oh, and by the way, it saves the GPS coordinates and date and time of your note. I'm really looking forward to using this thing while exploring the city. Find a cool looking restaurant? Snapshot its menu and hours, and look it up later. Run across free wifi? Take a note of its SSID, and come back to that location later.

I've only had Evernote for a couple days, so I'll report back in a few months and let you know whether it was as useful as I think it will be. Anyone have experiences with it?

I'm now on twitter -- lincolnq -- if you have other note-taking advice or software you recommend. (Twitter on the iPhone is another killer app, but that's for another post.)

posted at: 03:20 | path: /tech | permanent link to this entry

Time Subdividing Physics

Chris Hecker wrote an awesome series of articles on physics simulation in 1996, and they're available on his site.

I've been doing some sorts of simulation since I was very young (QBasic years). Let's say you're trying to simulate a ball with gravity. You keep track of the ball's x and y position, and x and y velocity. Every frame, you add the velocity to the position to get the new position. Then you add some constant to the y velocity to simulate gravity.

When the ball hits something (like the ground, or a wall), you have to bounce it. To do this you can just invert the component of the velocity according to the wall it bounced off (for ground/ceiling invert the y component, and for side walls, the x component).

But things are always tricky. Sometimes, you're not careful, and the ball goes right into the floor and instead of bouncing, it gets stuck, because it's always colliding every frame so you keep inverting the velocities and it never goes anywhere. Or you discover that the ball isn't bouncing quite perfectly right. Or you try to make a billiards simulation, but the pool balls end up interpenetrating too far and your balls bounce at really odd angles. These things always frustrated me and I never knew how to deal with them well until I read Chris's papers.

One thing I did figure out in order to make my simulation smoother was to add a time parameter to the simulation. Every frame, you take the amount of real-world time that passed since the last frame and use that as the value for delta-T. Then, instead of adding the velocity itself to the position, you multiply by the delta-T, so that no matter what interrupts your program or makes it slower (more objects on screen), the simulation makes objects move across the screen at the same real-world speed. But this also came in useful later.

Anyway, I wanted to make a better physics simulator than I had done as a kid, so I dug up the old Chris Hecker. The idea in the above paper series I always liked (and you can read it in part 3) is the idea of subdividing time in order to find the exact point that two objects begin colliding, so you can do the nice collision response. By "exact" here, I really mean "to the desired epsilon," which is not actually exact at all but it's a hell of a lot better than the simplistic method I learned as a kid.

The way time subdividing works is that you have three outputs from your collision detector: "No collision", "Interpenetrating" and "Colliding". When simulating, you advance the positions of the objects, then check for collisions. If there's no collision, you go onto the next frame; if they're interpenetrating, you went too far -- back up. Go back to the previous gamestate (where, presumably, you knew all the objects were in valid positions) and then set delta-T to be half of what it was before. Advance the position again -- this time things only move by half as much. Test for collision again in the same way.

When you actually see the result "Colliding," it means that you've subdivided time enough (moved the objects in tiny enough increments) for the collision detector to say that two objects are touching, but not penetrating. This is where the desired epsilon comes in. Your collision detector will return "colliding" when the objects are not quite touching but they're within the tiny epsilon of doing so. At this time, you apply collision response as if they were actually colliding, and expect that this estimate is close enough to the correct answer. And most of the time, it is.

Once you apply that collision response, you can continue simulating the gamestate normally. You have to finish out that simulation frame, so you step forward in time until you get back to the original step size. If the collision response worked (and nothing else is colliding), the collision tester will return "No collision" and you're done with the frame.

I decided to implement it in Haskell, and the time subdivision algorithm came out really beautifully. I picked Haskell because I figured it would be fun to write collision detection and response methods using a functional style: accept a GameState and return "Colliding" or "Not Colliding, here's your new GameState". And it would be easy to return to a previous gamestate. So that's what I did.

Here's the type signature of my collision detection/response function, as well as the game state it operates on:

data GameState = GameState {
          t :: Double                                       -- The current time
          ,objs :: [((Double, Double), (Double, Double))]   -- List of objects with (x,y) and (xvel, yvel)
          }

collides :: GameState -> Maybe GameState

The spec for this function is: If the state is interpenetrating, it returns Nothing. Otherwise, if the state is colliding, apply the appropriate collision response and return the new game state. Otherwise (no collision), just return the same game state.

It's also worth looking at the (very simple) advance function, which just advances the position of every object by its velocity times the delta-T:

advance :: Double -> GameState -> GameState
advance dt (GameState t objs) = GameState (t+dt) $ map (\ ((x,y), (xv, yv)) -> ((x+xv*dt, y+yv*dt), (xv,yv))) objs

Now, you can appreciate how easy and beautiful it was to write the simulation function, which accepts a gamestate and a delta-T, and (using the given 'collides' function), simulates delta-T worth of time using the physics:

simulate :: Double -> GameState -> GameState
simulate dt gs =
        let gs_dt = advance dt gs in
        case (collides gs_dt) of
                Just gs' -> gs'
                Nothing ->      -- Break it down.
                        let gs' = simulate (dt / 2) gs
                        in        simulate (dt / 2) gs'

As you can see, it cleanly, recursively implements the above time-subdivision algorithm. "Try to advance the whole time step. If you can't, advance it halfway, and then advance it halfway again." It was a bit mind-blowing the first time I tried to write it. "It can't possibly be that simple!" But it actually is that simple, and trying to analyze the runtime of this function can help explain its workings.

What are the cases? If no collision or colliding, the function returns immediately (Just gs' -> gs'). So that's constant time (pretending 'advance' and 'collides' run in constant time).

If interpenetrating, the function calls itself recursively twice. So it's tree-recursive. But (if there's only one collision to deal with), one of the recursive calls will always return immediately. Additionally, once dt is small enough, BOTH calls will return immediately.

Worst case: you keep calling simulate until dt is on the order of epsilon. Since you're dividing by two each time you recur, the number of calls to simulate to find one collision is about O(-log(epsilon)) -- if epsilon is a small number like .00001, -log(epsilon) is 5.

This algorithm handles gamestates with multiple collisions. Simulate will end up subdividing time until it resolves the first one, then it will do it for the second, and so on until they're all resolved. So the actual runtime is O(c * -log(epsilon)) where c is the number of different collisions to be resolved in advance gs.

posted at: 02:17 | path: /coding | permanent link to this entry

25 Things

There's this Facebook virus going around: "Once you've been tagged, you are supposed to write a note with 25 random things, facts, habits, or goals about you. At the end, choose 25 people to be tagged."

Effective? Yes. Everybody loves an opportunity to write a long post about themselves! I had fun reading a couple instances of the meme by some friends, so here ya go. I'm not going to "tag" anyone except for the people who tag me, because I still ethically refuse to spread the virus. If you wish to be tagged, let me know (though if you're reading this, I don't know why you need that...)

1. The number one thing that makes me happy is interacting with friends. Laughter, helping someone out, cooperating to do something amazing, and falling in love have undoubtedly been the most satisfying experiences in my life, and I never expect this to change. People are the entire meaning of life to me.
2. Secondarily, what makes me happy is learning (through games, computer programming, reading, etc.) I have high expectations for myself being able to learn things quickly and well, and I wish to keep it up. When I stop learning in a game, I stop enjoying it. Same for programming projects. My enjoyment in classes tended to be proportional to the rate I was learning from them (of course, there were variations, but I think this is a generally true trend). It explains why I hated long homework assignments: I never felt like the learning to work ratio was high enough for it to be fun. But I usually enjoyed the genuinely difficult homeworks.
3. I have dreams of making a difference to lots of people. I don't know whether I can do this directly through starting a company, but it is always one of my goals when I start one. If not, I want to become independently wealthy and use my money to allow me to work on projects which can make a difference to people. I guess I will admit I also want to be remembered, although if I made a difference and nobody knew it but me, I would be satisfied.
4. I ski. Fast. Straight down.
5. I strive to have more self control. My friends criticize me for not knowing what the hell is going on with myself and I think they're right. I have bad habits that I can't quit. I am easily distracted from work (even important, satisfying work) by short-term desires which won't make me a better person. My goals in this are to give myself a little negative feedback when I notice I'm out of control, by writing them down.
6. Tom Mendoza, the president of NetApp, came to speak to the interns a few times when I worked there. He always gave the same speech: improve yourself and you can achieve great things. Small steps are the key to success; you need to set goals for yourself, but not abstract ones -- they must be concrete. "Time- bound and measurable" was the phrase he drummed into us. And I would say he is a great man. So I'm setting myself time-bound and measurable goals.
7. OK, onto less weighty matters. I have an interesting relationship with music. I took violin lessons at my mother's insistence from when I was two until when I was eighteen (!!). (Technically I switched to viola for the last two or three years of lessons, but that was barely different.) I never really liked it, but it was always part of my life. Went off to college and, because of momentum, joined a chamber group first semester. It was pretty good; I always like playing in groups. Of course, I stopped after that because my momentum ran out and I never really felt like I wanted to practice. (Unlike programming or gaming, I don't feel like I learn very quickly, so it's not as fun.) I recently got ahold of a very cheap electric violin and I've been practicing again! I'm much more satisfied playing it than classical violin, and I'm also less self-conscious (especially in an apartment where my roommates and neighbors hear me much less with a quiet instrument).
8. Maybe it's that I feel better about playing music I like to listen to on violin. I listen to a good amount of electronic music -- good for programming -- as well as some rock, with the occasional pop thrown in. Video game music is often electronic or classical sounding, and I know a lot of it by heart (and it can be fun to play too!) Yasunori Mitsuda is my favorite video game music composer.
9. I notice that music can affect my mood a lot. When a movie has good music, it tremendously amplifies the experience; Slumdog Millionare was a recent movie which had really excellent music. It's so rare to find good movies with good music. Another recent one was Kill Bill. I also put on music when I'm doing a depressing task, like cleaning the kitchen by myself, and it can often pick me up and make me excited to do it.
10. I have glasses and I am quite happy about that. I felt like they were part of my identity before I actually had them, so it was basically a relief in 8th grade when I got them. For some reason, glasses connote a certain personality type that I want to be (and incidentally one I tend to be attracted to as well).
11. Memorizing lyrics to songs is really entertaining, especially if you actually perform the song for people. I can do "Star Wars Gangsta Rap" and "It's All About the Pentiums" (both are rap, which is even more hilarious) by heart. In high school, my friends and I used to do the Gangsta Rap for nerds in Magic card shops, who always looked at us funny. But we didn't care what anybody else thought, even other nerds.
12. Richard Feynman is my hero. Based on his autobiography ("Surely You're Joking, Mr. Feynman"), he thinks about the world similarly to how I do. His thought processes seem to be based on strong, intuitive mental models, which is exactly how I understand everything. Also, one of my favorite lines from one of his stories was "What do YOU care what other people think?" It became my personal motto.
13. I accidentally the whole number thirteen. Is that bad?
14. I don't use Gmail. Almost all my friends use it as their main email account. I'm successfully resisting it though!
15. I bake bread. You can read about it elsewhere on my blog. It's an instance of bounded creativity -- you can go crazy and try changing the recipe all around, but it won't work if constraints aren't met and it's quite delicate, so there's always some risk and learning. It also has some aesthetic aspects -- getting it cooked an attractive color, getting a nice grigne and so on. And it's one of my favorite things to eat. Always nice when you can cook and make yourself the happiest.
16. Things I hate: driving cars, unfair assumptions. For different reasons. And there are probably other things too, but that's as far as I got before I decided to go onto the next question.
17. When I was younger, I hated rice, pasta, and anything spicy. My brother hated tomatoes, mushrooms, and milk. At the time I thought he was the crazy one but I am now pretty sure I was crazier. Now I pretty much just hate cilantro. (It's genetic, so I have an excuse.) There are other foods I don't like very much because they're boring, but I've been hungry enough to gain an appreciation for many foods I didn't used to like. (Is that legitimate grammar?)
18. I have an active profile on a dating site. Mostly it sucks. I've talked to several girls who were attractive, and met a couple of them in real life, but one or both of us always lost interest. It can be quite addictive to browse people's profiles on the site (maybe the NEXT one will be perfect!) But it's really hard for me to be attracted to someone I haven't met, so the most initially interesting profiles are ones who share my interests, and profiles that don't give a good first impression (all capital letters anyone?) are right out -- it's a bad first impression and that's really all you get. I feel a bit bad profiling like that, but it's to be expected I think. Meh.
19. I've never smoked pot or used any other drug illegally (except for alcohol before I was 21). I don't intend to. This is an interesting part of my value system because I don't really understand it. I do think marijuana should be legalized. I might even try it then; we'll see.
20. I've had good luck with backpacks. I've had the same backpack for five years (all through college). The one before that, I had only for a year or so, but the one before THAT I had for another four years or something. Different brands, too; I don't know why they are so good for me. I don't treat them especially well (or poorly, for that matter), but I use them a lot.
21. Computer Science was easy for me. I had the "computer science is hard" complex while I was in school, because everyone else in the department had that sense of elitism, but when I look back at it, it was a pretty easy major. I'm not saying this to brag but just to think "maybe I didn't get the most out of my college experience?" It's a bit unfortunate. I'm still thinking of going to grad school. Hopefully it'll be hard then.
22. I have a beard, for the first time in my life. It's not a part of my identity, although sometimes when I look in the mirror I see a different person with that beard and think "Oh, I could be him". Weird.
23. I admire persistence. I don't think of it as a trait I normally have, although I can sometimes dredge up a good reserve of persistence for weird shit (like doing stuff I'm not supposed to be able to do -- there's a certain room in Metroid Prime that you need like two or three items to climb and I didn't have either one and I figured out how to climb it, but it took me a couple hours and a LOT of tries.)
24. I'm usually optimistic. Sometimes it gets on people's nerves. But it makes me happier overall, because I have less sadness being disappointed than being worried.
25. I think of the daily shower as one of the greater pleasures in the modern lifestyle. It's warm, comfortable, nobody can bother you and I occasionally even solve an interesting problem. I always look forward to showers.

posted at: 05:17 | path: /self | permanent link to this entry

The Lowest Common Denominator Problem

I had a long post here, but I moved it over to blog.newsbrane.com instead, our Newsbrane developer blog. Since that exists, I'll reduce Newsbrane related material here. Suffice it to exist that you can join Newsbrane by going to Newsbrane's website and typing in your information. If when you view the site invites are required, you can email me to get an invitation.

posted at: 01:59 | path: /newsbrane | permanent link to this entry

Breads

I've been reading The Bread Baker's Apprentice by Peter Reinhart. It's an excellent book, explaining both the chemistry and the art behind bread making, and it's taught me a lot. I've made several breads in the past few days and they've been really quite good.

The "standard" bread recipe is flour, water, salt and yeast. Mixed in the right proportions, and allowed to rise, it should produce good bread. Theoretically, but whenever I did it, something didn't come out quite right. Now that I'm reading this book I'm slowly fixing the things I do wrong and it's very satisfying.

First, the fermentation (rising) of the bread strongly controls the flavor. There are several reactions that go on -- yeast converts simple sugar into carbon dioxide and alcohol, enzymes convert starches into simple sugars, etc. The point is that if you let the dough to sit around for a while before you use it, you can improve the flavor of the bread. Depending on the ingredients and conditions in which you let it sit around, you can produce drastically different results.

For instance, if you use poolish, you mix flour, water, and yeast the day before, let it sit around for a few hours, then pop it in the fridge. The next day, you add it to the dough you make and the flavor is noticeably different (more mature, a stronger flavor). Similarly, if you use really cold water for a dough and knead it quickly by machine, then refrigerate it overnight, you get pain à l'ancienne, which has a distinctive rich flavor. I have been experimenting with both those recipes and they've turned out extremely well.

Other variables, I'm learning, have similarly powerful effects. Steam in the oven during the first two minutes of baking makes a big difference to the crust. A poorly heated baking stone can prevent the bottom from cooking, but a well-heated one (at least 40 minutes in the oven) can bring the crust from "lame" to "awesome". The temperature of the oven affects the quality of the interior and the crust. When scoring the dough, you can do it right before it goes in the oven if you've let it rise properly and not too long. But if you wait too long, it will have already risen its max and won't produce a nice bloom. If you cook the bread too early, it will be too dense and heavy.

I'm still experimenting, but so far it's been a really awesome few weeks learning about bread. I feel like I will soon produce something awesome. So far I've made some mistake each time (overcooking, undercooking, failure to rise) and if I fix all my mistakes, I think it will work out well.

posted at: 22:57 | path: /cooking | permanent link to this entry

Compositionality

This essay is still in progress. Send me comments if it interests you.

Compositionality (or composability) is a strong word in computer science. It means you can put two things together, and get the effect of both. This is pretty much what everyone always wants. It is at the core of reusable programs -- programs that are not only useful in their own right but can actually be used by other programs to produce new, powerful functionality.

The standard, classic example of this is UNIX command-line programs. The shell pipe (|) lets you feed the output of one command into the input of the next. This is useful because there are lots of programs that do something useful by themselves, but they can do something more than twice as useful when you put them together. Look at sort and uniq. Sort will sort lines of a file lexicographically. Useful on its own, if a program spits output that you might like in alphabetical order. Uniq will remove duplicate lines next to each other. Useful if a program spits lots of identical log messages and you only want to see one of them at a time. But they become much more useful when combined, because now, you can take some output, sort it, and now all the identical lines in the file are next to each other, so uniq will remove them, and all of a sudden you've turned a sequence which may contain duplicate elements into a set which does not. I don't have to think too hard about how sort or uniq work; I just use them.

Subroutines in a program are also an example of compositionality. I can write a subroutine X for one purpose, then while writing subroutine Y, realize that part of the requirement is to do the thing X does, and just call X in order to achieve that part rather than writing it again -- you don't have to think about it. This is standard practice, right? Well, I have found, especially in large systems, that this is rarely the case in practice.

You have to think hard about X! In Java, X is probably a method on a class. The method might mutate the instance, which screws everything up because it wasn't expected to be called from that location, but if you don't think about it, you just use it and then you have a difficult bug. This has happened to me on tons of occasions. Systems code is even scarier, because X might disable interrupts, or sleep, or do something weird that you can't do from whatever context you're in, and everything gets upset. Programming languages like C are designed for composability, but they fail at it because low-level code can take actions that high-level code doesn't expect or can't deal with. Even going into a loop is a risky action on the part of low-level code, because code who calls you might be expecting a certain level of performance.

In thread programming the problem is even worse -- look at locking. If your code uses locking, you must know exactly which locks are being taken by code you call, because otherwise you risk deadlock. Software transactional memory helps on this issue, but the performance of composition of atomic blocks can be worse than the performance of the components (since transactions are larger, either commit probability or concurrency goes down).

My argument is that compositionality in most modern languages is terrible. It exists, and it is certainly possible to write compositional code, but making your user think hard about what your code does is nearly as bad as making them do it themselves.

Now, there are a lot of ways the situation is slowly being rectified. Haskell is a really interesting example of strongly compositional code: functions outside the IO monad have no side effects, period. Since they have no side effects, they accept your data and return a result. You are guaranteed that they don't do anything else.

It is worthwhile to note how monads fit into this. Functions are a little less predictable since the monad syntax hides the possibility of changing monad state, but (outside the I/O monad) the side effect possibilities are highly controlled and they are within the interface of the function.

In terms of performance, Haskell's composability is only a little better than that of most languages. Because of laziness, unneeded work of a called function is not done. But since the results of the called function will be needed before the calling function can produce a value, there's not usually very much performance difference in the long run compared to eager languages -- if you don't know whether an inner function is slow, then you don't know anything about the performance of the function you're writing. And that's bad.

I want to mention combinators. Combinators are components which are a combination of other components. The UNIX pipe I mentioned above is a combinator: it means "make a new component, which is the result of taking the output of that one, and sending it to this one." C and Java don't have the idea of combinators for functions, because there's little that could be done. If you want a function C which is the result of calling A and sending its output to B, you write C. Haskell has several combinators: the dot operator is like the UNIX pipe, in that A . B means A(B(x)).

Combinators are only useful when you have a lot of different components that are highly compositional. Flapjax is one of my favorite languages because of this. You have two types of objects, behaviors (time-varying values -- streams) and events, and you can combine them with all sorts of exciting combinators (merge these two streams, snapshot a behavior with an event, etc.), to produce new behaviors or events. Then you can create all sorts of interesting interactions with the rest of the system.

The language we're designing has a different characteristic. We aren't solving the problem completely, but we think our approach has a lot of merit in terms of compositionality.

posted at: 02:11 | path: /coding | permanent link to this entry

A Fitting Analogy

I thought of an analogy for our project that seems to fit fairly well. We're the "relational database for code". Relational databases change the way people think about storage. Before they existed, if you wanted to store some data, you opened a file and put whatever you wanted into it. When you read the data, you have to parse the file format, and you can only read the file sequentially, and so on and so forth. There are tons of different file formats that people use, but everybody does it differently, and if you wanted to be able to use the data in a lot of different ways, you had to think very hard about the different ways and design a file format that allows you to be efficient about it -- leading to greater complexity, bugs, and poor flexibility.

Enter the Relational Database. In order to use a relational database, you have to think a little about the data you intend to store. You have to organize it into relations: what pieces of data are associated with what other pieces of data, etc. You also have to tell the system a few other details about how the data will be used -- indexes, views, etc. But once you do this, it's massively easier to deal with all sorts of data. It's more flexible, because you can write queries that ask the database all sorts of questions that you couldn't have anticipated while you were creating it. Relational databases are also better performing, because the database creators were able to put in a lot of advanced technology to use indexes and perform query optimization and so on that you would rarely have the resources to be able to write yourself. Both this performance and this flexibility are gained from telling the database some critical information about the data that you're storing; you can't generalize the idea of a join between relations without the user telling you what is in a column.

We are aiming for a similar paradigm shift for software, especially communicating software: tell the system a little bit about how your functionality is structured -- what operations apply to which pieces of data. Stuff that you probably know anyway, or can figure out. Once you've explained this to the system, the system provides lots of flexibility (through making it easy to send messages, implement new objects, etc.) and performance (through parallelism, optimization, distribution, etc.).

posted at: 21:40 | path: /projects/x | permanent link to this entry

Structuring your app with Units

A major component of our design for a message-passing framework is the idea of a Unit. A unit in our language is an aggregation of data and code that can receive and send messages. It's analogous to an object in object-oriented languages.

Note that I said analogous. They're defined similarly to objects in that you specify fields and functionality, but you have to treat units differently from objects because of their runtime characteristics. Specifically, at most one message that uses the state of a particular unit can execute at once. This has extremely interesting implications.

For one thing, units' state is consistent between messages. What do I mean by that? Well, contrast it with most shared memory systems, where if two threads are trying to increment a shared counter, one thread might interleave one read operation between the other thread's read, add-one, and write sequence. If this interleaving occurs, then the system is brought to an "inconsistent" state. We obviate synchronization problems like this one -- the analogous problem is that an incrementer unit receives two simultaneous messages to "increment yourself", which is defined as read, add-one, and write. However, the runtime ensures that the two "simultaneous" messages are actually executed in sequence, so the problem above never occurs.

When I say that only one message on a unit can execute at once, I actually mean something a bit different: only one message appears to execute. In fact, the runtime might be executing many messages, but they will never notice. Another way to put it is that the runtime enforces that messages are transactional upon the state of the unit: messages appear (to observers -- other messages) to happen all at once and in isolation from other messages.

These transactional semantics have great implications to the design of systems. Traditional object oriented programming requires the programmer to break up their code by functionality. While designing a Web server, for example, a reasonable object-oriented design would include a module that listens on the socket and provides events, one that parses the HTTP protocol, one that looks an object up in the VFS based on the GET string, and one that spews the object back to the user in the HTTP protocol across the socket. Note how this is segmented by functionality -- take a moment to think about what features of the code are required at each level. Now think about how these modules communicate. The event comes in. That code (the event handler) probably calls a parseHTTP method to achieve an HTTPMessage structure. Then the event handler passes that to the parseGET method, which calls the vfsLookup at each level of the GET string until it reaches a terminal object. It returns the object. Lastly, the event handler passes the GET string and any query options, post data, and the socket descriptor to the object and tells it to handle the request and send the user the data. For file objects, the object just sends the mime type and the data. For other objects, some special code might be run.

In our system, you can organize your functionality in this way but it's more important to think about the data. What data is involved in handling a web request? Clearly each web request is a separate event to the server, and they have no shared state. So the incoming socket listener is probably bound to a "free operation" -- a message with no unit attached. This free op accepts data on the socket, parses it (using an HTTP parser library), parses the GET string into components (using another library), and sends these components to a VFS unit which knows how to do the lookups. This unit may just be a front-end to a tree of separate VFSDirectory units. Anyway, once the path components are resolved into a target object (itself another unit), the object is passed a message with the correct arguments as well as the capability of writing to the socket (derived from the event) and is expected to write its output to the socket in the same way.

So what's different? Units make the user focus at first on the data, not on the code. Only after the system is correctly separated into units do we think about organization of functionality, which is nearly orthogonal to the question of how data is broken into units.

Code and more case studies to follow.

posted at: 05:11 | path: /projects/x | permanent link to this entry

The List Monad

You might still be confused by the concept of monads. I'm not going to provide a comprehensive monads introduction, but I'll show you a simple example of the List monad in action, and maybe it will provide some movement towards a general understanding of monads.

The idea behind the List monad is that it captures the essence of "multi-valued functions." Let's say that a problem might have several possible solutions, and you want to capture all of them, but you also want to treat the problem each step of the way as though you were only dealing with one of the answers at one time. The List monad allows this, and I'll show you how.

The problem I'll examine is: given a sorted sequence of items, what are all the different binary search trees you can put the items in?

Recall that a binary search tree is a sorted tree where each element has zero, one, or two children. My tree will be of Ints, each Node will contain an Int and two children, and children can either be Nodes or Leaf items (an "end of tree" marker). Thus the Haskell structure I will use is the following:

data Tree = Leaf | Node Int Tree Tree deriving Show
-- For example, the tree
--    4
--  2   5
-- would be constructed using the code:
testTree = Node 4 (Node 2 Leaf Leaf) (Node 5 Leaf Leaf)

OK, so now we have a Tree structure. Let's look at the problem again. What are all possible trees?

   2            2
     4             5
       5          4

    5         5             4
 2           4            2   5
  4         2

How did I arrive at this? Do it yourself and see. I selected a root node (2), then tried to figure out all the possible subtrees on the left and right of that 2. In this case there were two: 4-5 and 5-4. Same for if I selected 5. But when I selected 4 as the root, there was only one subtree possibility for each side.

As you can probably see, we can solve it with a neat recursive solution: arbitrarily select a root, partition the list into sublists on the left and right side, solve the problem recursively for the sublists, then combine the solutions in all possible ways to produce all the trees rooted at the selected root. Select the next root and continue.

An iterative programmer will look at that and see three nested for-loops. Take a look and see if you agree:

def getAllTrees(lst):
    outputs = []
    for root in lst:
        lhs <- items left of root
        rhs <- items right of root
        for lhstree in getAllTrees(lhs):
            for rhstree in getAllTrees(rhs):
                add new Node(root, lhstree, rhstree) to outputs

    return outputs

The List monad, however, allows us to do something much neater. Our getAllTrees function is fundamentally a multi-valued function, but it also makes use of some multi-valued functions: one to select a root (the function that returns each root), and the recursive calls to getAllTrees.

Let's write getAllTrees in Haskell. First, the type signature, and let's also think about what happens in the base case. When we are given a single element list, we want that element in a Node with two Leafs. That means that getAllTrees of an empty list must return a single Tree as its result, the "empty tree".

getAllTrees :: [Int] -> [Tree]
getAllTrees [] = [Leaf]

Now, the rest of the function. Let's split the tree at each possible place: the beginning, after the first item, after the second item, and so on. We always want to leave one item for the root, and we're splitting it before the root each time, so there are n ways to split the tree. The splitAt function is what we want: given an n and a list, it gives us the tuple (n-long prefix, rest of items). The root will be the first element of the 'rest', so we uncons it, and now we have lhs, root, and rhs. Look at the algorithm, and I'll explain it more below.

getAllTrees lst = do
    rootIdx <- allPossibleRoots
    let (lhs, root:rhs) = splitAt rootIdx lst
    lhstree <- getAllTrees lhs
    rhstree <- getAllTrees rhs
    return $ Node root lhstree rhstree
    where allPossibleRoots = [0..(length lst)-1]

Do you see how it works? rootIdx gets the value 0 and then the rest of the algorithm runs: splitAt is called; lhs, root, and rhs are assigned; getAllTrees is called; lhs- and rhstree get values; and a new Node is built with the results. The magic of the List monad is that this process happens once for each item returned from allPossibleRoots and getAllTrees. At the end, the algorithm calls 'return' a whole bunch of times. Isn't it neat?

posted at: 18:16 | path: /coding | permanent link to this entry

Grad school

I'm in the midst of applying to graduate school. I have been writing essays about why I want to go to grad school. Basically, I want to make a difference in the world, and I think grad school is the place to do it.

Why is grad school the place to make a difference? What are the other options? Going to work for some corporation? I doubt that's an effective way of helping the world, although it could certainly help the company. I prefer to help the world without helping a greedy entity, though. So instead I want to do research. Research is implicitly contributed to the greater good and seems more effective for the effort than working for a corporation.

Help me decide: I've applied to MIT Media Lab as well as several places for CS (MIT, Berkeley, Stanford, Harvard). If I get into the Media Lab, do I want it? I think I do, because of the helping the world thing. I think the Media Lab is the best place to help the world.

posted at: 02:22 | path: /brown | permanent link to this entry