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
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
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
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
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:
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.)
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
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
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
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
advance gs.posted at: 02:17 | path: /coding | permanent link to this entry
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...)
posted at: 05:17 | path: /self | permanent link to this entry
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
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
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
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
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
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
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
If one were to examine computation in X, what properties hold?
If we ignore objects in the language, computations are deterministic. This will be demonstrated by breaking computations down into a series of steps and examining the results of each step. If each step is deterministic then the whole computation is deterministic. But what about steps being executed in parallel by an adversary scheduler? I'll show that even if you don't know the whole state of the machine at once, you can always predict the pieces of state that could possibly be needed by the current step.
The absence of "mutable shared state" will be key to the proof. In X, we promise to the user that there is no such thing as shared state between concurrently executing threads, except in the context of objects and their member variables. We will prove this by examining each syntactic form in the language and showing that it cannot create a reference shared with any component that could execute at an unknown time (again, in the absence of objects). If this property holds, then we guarantee that at each step, all references available to the step are either to immutable objects or to mutable unshared objects.
Now, if the reference is to an immutable object, then it must be in a known state: the state it was created in. If the reference is to a mutable unshared object, then it must also be in a known state: the state obtained by starting with the state it was created in, then applying all operations to it in order up to the current step. Since the object is unshared, there is no point where the order of operations is ambiguous. Thus all references are in a known state at each point and thus the computation is deterministic.
We would also like to show that each task, once started, is
wait-free: it completes in a finite number of steps (it never
has to wait for another task). Tasks may be spawned by other tasks
(via send), optionally passing futures. The task is never
started until all the futures in its arguments are filled.
This proof is simple, as there are no waiting constructs in our language. In order to "wait" for the value of a future, you have to make a new task which receives the value.
posted at: 18:40 | path: /projects/x | permanent link to this entry
I recently updated my resume. For the past year or so, I've had my resume in an abstract XML source format I came up with. (I'll put up the code when I have time.) I then use XSLT (Extensible Stylesheet Language Transformations) to convert from my XML source into XHTML, which you see on the resume page.
XSLT is a declarative language. You specify what elements you want transformed and what the output is, and it goes through the document and applies your transformations where they match. It's kind of enjoyable to code because there's no tedious "loop through the DOM" sorts of affairs like you might write if you were making a Python XML processor. (Although the XML syntax is its own kind of tedium, so it's a tradeoff.)
I then wrote another XSL stylesheet to transform my generated resume into the Web "clean" version linked above, which removes my email and mailing address. (I only want job offers from real, intelligent people, and my Turing test is devising a way to contact me.) It also replaces the CSS to accommodate the Web format a little bit better. (The 'print' version is almost the same, but the font sizes are a little different.)
My resume is built using a Makefile on the Techhouse server, which
does almost all the steps: xsltproc (the XSLT stylesheet
transformer tool) from the source to the full version,
xsltproc from the full to the clean version, and
xmllint --format to pretty-print the XML. But The one thing
I haven't gotten a good automated procedure for is converting my resume
into PDF. I used to like the result of printing it to PDF using Firefox
on OS X. But I won't always have OS X available, and I don't know any
way to automate that. So it's not the best situation. I tried a few
'html2pdf' type tools, but they produce poor quality results.
posted at: 13:34 | path: /projects | permanent link to this entry
Sean, Tara and I are working on a concurrent programming language. It's based on message passing. Message passing, you say sarcastically, that's a new idea: look at Smalltalk and its object oriented progeny like Java.
But our messages are different! They're asynchronous. Instead of sending a message and waiting for the response, you continue on your merry way.
You may have had this idea before. I did -- it's not really a difficult concept. The question is, when you need to get a value back from that message that you sent (like a return value), how do you do it? Stop and think about this. How do you do it?
One idea is to send a return port along with the message, and have the client send you data along that port. This is okay, and our language certainly supports it. But what if the port needs a bunch of different pieces of data as results from a bunch of different messages? You have a serious data collection problem, where all your return ports are invoked at different, unpredictable times.
Okay, so instead, let's try this -- when you send, you get back a token (let's call it a Future) which you can "force" in order to retrieve the value. When you force a future, your message blocks until the desired message produces a value, and then you get it. But let's add another constraint: messages should never block. (I'll get to why this is useful in another post.)
So what, then? Here's our proposal: sending Futures as arguments to a message causes them to be resolved before that message is delivered. That's kinda weird... but it solves our blocking problem -- the only "blocking" that occurs is that a message's delivery might be delayed, but since they are asynchronous, it doesn't matter. It also makes it easy to do the data-collection problem, as you can start a bunch of asynchronous messages and then pass all their futures to the same place -- the place where you do your work depending on those values.
posted at: 04:43 | path: /projects/x | permanent link to this entry
I put Gutsy Gibbon on my new MacBook today. It rocks. My external (23") monitor works nearly flawlessly, and the open-source Intel drivers worked out of the box to give shiny desktop effects!
I first installed ReFIT, then I used diskutil resizeVolume under Mac OS X to resize my hard drive, and then I installed Ubuntu into the empty space. It couldn't have been simpler (now that Boot Camp is no longer free from Apple). My monitor works with the Intel drivers, and I use xrandr to configure it on-the-fly because I often move my computer. The screen still goes crazy occasionally, but it's survivable.
Anyway, I highly recommend people try it. MacBooks seem to take Ubuntu very well! I have nothing to complain about at this stage.
posted at: 04:14 | path: /unix | permanent link to this entry
I've decided I want to give a talk on OLPC at Brown at the beginning of the semester. I've been pretty involved in OLPC over the summer and it seems like the sort of thing that some Brown people might be interested in.
So what should I talk about? I think I want the talk to be basically an overview of the project: explaining the driving ideas of the vision, demoing the hardware and software, showing photos of kids actually using the thing, and ideas for how to get involved.
I will most likely be giving the talk through BLUG, the Linux User Group at Brown. As such, I will be talking about Linux and Free software as a major part of the OLPC philosophy. But I don't want to focus on the Linux aspect...
Here's my structure proposal: first show the laptops off to get people's attention. Use slides with photos of the interesting hardware components so people can see them up-close, and show at the same time pictures of students in Nigeria and Thailand using them. So the first section is "What it does." The second section is "Why?" -- philosophical discussion of the reasons behind the organization, what good it does people to do such-and-such. At this point we can talk about educational mission (Constructivism), Free software, and also do demos of the activities that show how awesome these ideals really are. Collaboration is a very important one, here, so I would like to have everyone in front of a computer so that they can all play using the software.
The third section is the "get involved" section. I guess I can show some source code here and say 'yes, you can edit this, and it will ship'. I will provide a handout (?) or email with links to useful websites, git source checkouts, and presentation notes. And I will describe the full spectrum of use people can be -- kernel and activity hacking, testing, art, distribution, even donations... there's a lot that OLPC can benefit from.
Of course, there is also the 'get your hands on a laptop' part where people can come up at the end and play with my demo machines. Unfortunately I only have two, so there will be a lot of waiting and not that much playing. Nonetheless, I want to give people an opportunity to see and play with the laptops, so maybe I can lend them to people for days at a time, or something. I don't know.
posted at: 22:08 | path: /olpc | permanent link to this entry