The Web and all that Jazz

Building a culture of teaching and learning by Dr. Tae!

2009-07-10T23:27:00.001-07:00

Posted via web from The Web and all that Jazz

Regular Expression Matching and Postfix notation

2009-07-08T05:27:00.001-07:00

As the compiler scans the postfix expression, it maintains a stack of computed NFA fragments. Literals push new NFA fragments onto the stack, while operators pop fragments off the stack and then push a new fragment. For example, after compiling the abb in abb.+.a., the stack contains NFA fragments for a, b, and b. The compilation of the . that follows pops the two b NFA fragment from the stack and pushes an NFA fragment for the concatenation bb.. Each NFA fragment is defined by its start state and its outgoing arrows:

via swtch.com

The snippet doesn't make much sense unless you read the article, but this part, I thought was rather neat. Usually, when I wrote my crappy, one-off parsers, I just used regexes to pull out the tokens that I needed. Never thought too much about how it was implemented. But what's detailed here makes sense. Regexes are just state machines where you track whether the string you're matching against lets you traverse all the way through the state machine. And to do that, it pushes each fragment of the regex onto a stack until it reaches an operator, which then pops it off and works on it. While I've usually left post-fix notation is ass-backwards from a user perspective, I can see the elegance of the implementation. I suspect Forth and Factor are similar in this regard.

Posted via web from The Web and all that Jazz

Nerd time issue 16

2009-06-29T08:13:00.001-07:00

I use to work at a research lab and while it was cutting edge in some ways, it seemed unaware of things going on in software and web. I've since left the research lab, and Nerd Time started as a mailing list to tell my friends still at the lab about things that they might be able to use in their own projects.

------------

Hey all,

It's that time again. I never get feedback about whether you guys read this or not. But apparently, some of you do, since my last trip back to MD. This is just a collection of things I found interesting since the last nerd time. Obviously, there are other trends I'm missing.

If you want off, just lemme know.

This is rather long since it's been a good 6 months since the last nerd time. Work has kept me busy, and I don't read as much as I use to. Since there's no theme, but lots of trends, they're in no particular order this time. Skim through it and see if there's anything that catches your eye.

If you have questions about stuff, feel free to ask me (don't reply all!)

First, some stuff I did on the side:
Senate Majroity vs National Debt
I was talking with Ian about graphing public data, and this was what he wanted to know. This sort of thing should be so much easier. If you find the process of getting this data to graph, lemme know. I imagine it goes in line with a lot of the net-centric buzzwording that does on in DoD projects.
http://iamwil.posterous.com/senate-majority-vs-national-debt-getting-at-p

Frock, a chicken flocking simulator
I wanted to get to know the Lua programming language, so I chose this as a project. I'm getting it to support more chickens still.
http://webjazz.blogspot.com/2009/02/introducing-frock-flocking-chicken.html

And now, the other stuff.

Twitter
So I'm sure most of you by now have heard of twitter. Considering that Oprah did a show on it, it's crossed over to mainstream. A lot of you might not think of it as anything to pay attention to. However, it's one of those things where its value depends on whom you follow. Beyond the hype, it's mainly a messaging multicast system that has a dead-simple API, so that other people can build things on top of it. People have made things that twitter, such as plants that tell you when you need to water it, when bridges go up and down, when a meteor almost hits the earth, etc.
http://www.twitter.com
http://twollars.com/
http://www.botanicalls.com/kits/
http://twitter.com/riverthames

Wolfram Alpha and Google Squared and YQL
Wolfram Alpha and Google Squared had both been announced in the last month or so. Both are looking towards being able to query large amounts of structured data. However, wolfram curates this data with experts, and google squared attempts to make structured data from indexing tables of data on the web. In addition, Yahoo released YQL, which is a query you can use to scrap the web and treat it as just another database.
http://www.wolframalpha.com
http://www.google.com/squared/
http://tables.googlelabs.com/Home?pli=1
http://developer.yahoo.com/yql/

Real-time search
Real-time search seems to be the wrestling ground for the next generation of search right now. There are a number of competitors in this field, including giants and startups. It's evident with the death of Michael Jackson that news doesn't just travel through the old channels anymore.
http://venturebeat.com/2009/06/20/who-rules-real-time-search-a-look-at-9-contenders/
http://search.twitter.com
http://www.scoopler.com

Google Wave
If you haven't heard, google released a new communication tool called google wave. It's what email would be like if it was reinvented today. It's basically combining different aspects of our communication tools and merging them all together. It's best if you watch the video and play with the demo. If you want to play with wave yourself, you don't have to wait for an invite, but can sign up with a wave server that someone set up themselves. I recommend watching the video, as it breaks your presumptions of what's possible with HTML5 and the web.
http://wave.google.com/
http://wavety.com/pygo-wave-server/

Git and github
To me, this is really old news, but just in case you're still using SVN, you should checkout Git instead for your source control. It's ass-kicking good, though it has a slight learning curve. I won't say too much more about it, but you should really look into it. It'll expand your mind.
http://git-scm.com/
http://github.com/

Key-value stores
Lately, there's been a flurry of attention on key-value stores. I've mentioned one of them before, CouchDb. There are a bunch of others. Tokyo Cabinet (link #2) is used at Mixx.jp.co, a social network in Japan. Cassandra (link #3) is used at facebook. Amazon has SimpleDB and Dynamo. I've only played with tokyo cabinet and couchdb, so I can't really do a compare and contrast between them all. But to me, TC, couchdb, and redis seem to be the most interesting. This marks a shift away from relational dbs as the default data store. Not that they'll replace relational db, but we're finding there are a different class of constraints for the web not necessarily taken care of by relational dbs. In addition, they have properties not avail to relational dbs, such as being schema-less, an http server built in, replication, distributed, etc.
http://couchdb.apache.org/
http://tokyocabinet.sourceforge.net/index.html
http://incubator.apache.org/cassandra/
http://code.google.com/p/redis/
http://memcachedb.org/
http://github.com/cliffmoon/dynomite/tree/master
http://opensource.plurk.com/LightCloud/
http://www.allthingsdistributed.com/2007/10/amazons_dynamo.html
http://www.oracle.com/technology/products/berkeley-db/index.html
http://code.google.com/p/thrudb/
http://code.google.com/p/scalaris/

The internet of things
It's something further out, but these first two talks from TED got me thinking about where the web was heading. I don't think that the semantic web, as we imagine it will come to fruition. However, having the things we own talk to each other over the internet is not unfathomable. They'll be able to negotiate with each other to perform a task, or they'll be able to keep a history of what they're doing or how you're interacting with them.

http://siftables.com/
http://www.readwriteweb.com/archives/5_companies_building_the_internet_of_things.php
www.makerbot.com
http://siftables.com/

Cheap hardware boards
Hardware is already cheap, but building hardware yourself has still been somewhat of a pain. I remember having to use Rabbit boards before. There are better ones now. I've mentioned arduino before. Beagle board is a full board that you can run Ubuntu on. Teensy is a small USB microcontroller.
http://www.arduino.cc/
http://beagleboard.org/
http://www.pjrc.com/teensy/?not_a_duplicate

Quake online
Gaming often is looked on as child's play, when in fact, it's some of the hardest programming around, and often drives innovation and progress in graphical techniques, AI, and hardware. Carmack, the guy that wrote Quake, wants to put Quake on the browser. For the longest time, people derided the web, saying it'll never match the performance of desktop apps, and never give the same user experience. If Carmack can run quake on a native browser, then I believe desktop will lose. If he's delivering quake as a video stream, then that's another matter altogether.
http://www.gamasutra.com/view/feature/3946/building_quake_live_carmack_speaks.php?print=1

Reverse HTTP
HTTP is by design a pull model, where the client requests resources from a server. If you wanted to push data to a browser client, you had to rely on a bit of javascript finangling called Comet (cousin to AJAX), where you open an http connection to the client, and leave it open until you want to push stuff to the client. This certainly puts a load on servers because you have to keep connections open. Alternatively, you can have the client keep polling the server. That sucks too. Reverse HTTP doesn't need to keep the connection open. It basically takes advantage of the upgrade field in the HTTP header normally used to find a more appropriate protocol, and instead to turn the connection around from the server to the client. It's still experimental, but it makes a lot more things simple instead of messing with javascript on clients to push data to browsers.
http://www.reversehttp.net/
http://wiki.secondlife.com/wiki/Reverse_HTTP
http://www.ietf.org/internet-drafts/draft-lentczner-rhttp-00.txt

Whiteboarding in real time
Many collaboration tools have come out. We've discovered that the web is essentially a communications medium. Anyway, this set of collaboration tools lets you whiteboard, compose text, and revise docs in real time as other people are editing them. The last link shows you a re-play of paul graham writing one of his essays. This allows people to see how they edit their text over time, and shows others how other people think as they write. It'd be useful as an educational tool.
http://www.twiddla.com/
http://www.etherpad.com/
http://www.wikirage.com/
http://www.revizr.com/
http://etherpad.com/ep/pad/slider/13sentences

Facebook's walled garden
Facebook is the AOL of today. It's basically a walled garden of data, where users live. There's a bunch of effort to break them open. Facebook also wants to open itself out as a fast follower to twitter. I won't say much more here, but there's an ongoing battle about where data gets to go on this front.
http://www.wired.com/techbiz/it/magazine/17-07/ff_facebookwall?currentPage=all
http://googledataapis.blogspot.com/2008/03/3-2-1-contact-api-has-landed.html
http://www.complang.org/dsnp/

Data.gov and the sunlight foundation
Since Obama took office, there's been a big push and initiative to open up the government to its citizens in the name of transparency. One of the things they're doing is data.gov and opening raw public data up to developers or anyone that wants to use it. The sunlight foundation is doing the same for legistator and voting data. I expect that we'll have more apps that will be able to take advantage of this data in the near future, not just to help the people govern their govenment, but also to lead more informed lives.
http://services.sunlightlabs.com/api/
http://www.data.gov/catalog/raw/category/0/agency/0/filter//type//sort//page/1/count/10

DNA engineering
A front that I don't know too much about, but is probably a bigger revolution than the information age and the internet are things that have to do with genetic and bio engineering. 23andme lets you submit cell samples of yourself, and they'll do genetic testing to tell you if you have genetic diseases, among other things. You can now submit gene sequences and get them built for a modest amount of money--not super expensive, but still out of reach for hobbists) As the cost goes down, you'll soon see designer pets and bacteria. The last post is about a guy that theoretically hacks a more potent variant of swine flu.
http://23andme.com
http://mrgene.com/desktopdefault.aspx/tabid-2/
http://www.bunniestudios.com/blog/?p=353

GWT, sproutcore, and Cappucino
Javascript is the most widely used language in the world. And while it has its merits as a functional language, people are trying to develop frameworks that compile to javascript. Javascript is not bad when you're using jQuery. Scriptaculous 2 just got released also.
http://code.google.com/webtoolkit/
http://www.sproutcore.com/
http://cappuccino.org/
http://jquery.com
http://scripty2.com/

Chat on couchdb, standalone web apps, and taking your data with you
This was curious. Couchdb is a key-value document orientated database with an http server as its frontend. They were able to demonstrate that you can fit an entire web app just in the database. Data is code, and code is data. Not only that, you can use the database's replication to port your data and sync it where-ever you go. It's an interesting head turn, even if it's just a demo.
http://damienkatz.net/2009/05/realtime_chat_on_couchdb.html
http://www.jasondavies.com/blog/2009/05/08/couchdb-on-wheels/
http://devlindaley.com/2009/2/14/couchdb-bloom-filters

Mozilla Ubiquity again, but this time hooks into webapps
I've mentioned ubiquity before, which is like a commandline interface for your browser. I use it myself, but only in limited amounts. What's interesting about the direction is that they leverage web services to complete tasks it can't complete for itself. I think that high level languages will eventually adopt the idea of being able to easily hook into web services as a natural part of the language, without extra libraries.
http://www.readwriteweb.com/archives/firefoxs_ubiqity_starts_thinking_for_itself.php

Mozilla Jetpack lets you write Firefox addons with the web
Traditionally, web developers have stayed out of the realm of desktop developers. This is one of the many indications I have that a lot of programming--especially those with user interfaces or a social aspect--will move towards web programming constructs. https://jetpack.mozillalabs.com/

Clojure, Scala, Haskell, Erlang
I'm not going to say too much about these programming languages, since I've mentioned them before, but just as a reminder, there's more than Java out there. These four to me, represent the edge of programming languages that have potential in the future. With the advent of multicores, it's likely that functional programming will lead the way in giving us adequate programming constructs to deal with multicores. If you're a programmer, it'd probably serve you well to learn at least one of these in the coming 4 years.
http://clojure.org/
http://www.scala-lang.org/
http://www.haskell.org/
http://erlang.org/

ParrotVM and mod_parrot
Admittedly, I don't know much about Parrot. But the claims it makes is big. With the rise and popularity of dynamic programming languages like Python and Ruby, we're struggling for a fast virtual machine. And to have to build a new virtual machine every time we have a new language is a pain. ParrotVM is suppose to take care of easing that pain. If that's the case, it might be easier to make languages catered to our problem domain.
http://www.linux-mag.com/cache/7373/1.html
http://www.smashing.org/talks/mod_parrot.ppt

Augmented reality and zombies
We've moved closer to having augmented reality. This is a far cry from the geeky headcam helmets and laptop backpacks that dorky MIT profs wore a decade ago. It still relies on a 2D barcode, and has limited uses, but now with the iPhone3GS out (it has a compass), we might see more augmented reality apps (as well as on android phones)
http://singularityhub.com/2009/06/19/augmented-reality-is-full-of-zombies/
http://www.thinkartificial.org/machine-interfaces/augmented-reality-iphone/
http://news.cnet.com/8301-17938_105-10266380-1.html

Sysadmin tips
Here are some good sysadmin tips. I'd like to think I know my way around linux, when in fact, I've just started.
http://www.ibm.com/developerworks/linux/library/l-10sysadtips/
http://blog.transmit.net/2008/10/my-best-unix-tricks.html

Probabilistic chips
I don't know anymore than what's written in the article. So read about it.
http://www.chron.com/disp/story.mpl/metropolitan/6252697.html

Google Moderator
Voting on websites is old hat since about 2005 with the advent of Digg.com and reddit.com. I found it curious that google has a moderator app, to help facilitate the asking of questions. If you want your own, you can create a white label voting site at slinkset.
http://moderator.appspot.com/
http://www.slinkset.com

The rest of these are related to software, but not about code. If you can only watch/read one, I'd recommend the poisonous people one. That applies to more than open source projects. In it, SVN core devs talk about how someone came in and told them they were all wrong. I have a feeling that was Linus Torvalds, as he rails on the SVN guys in his talk.

The Business and Politics of Software
http://blog.cusec.net/2009/01/05/zed-shaw-the-acl-is-dead-cusec-2008/

Pivoting, or knowing when to stop.
http://startuplessonslearned.blogspot.com/2009/06/pivot-dont-jump-to-new-vision.html

How open source projects survive poisonous people.

Linus Torvalds on Git

Build or buy?
http://sitecanary.com/blog/5

Posted via email from The Web and all that Jazz

Netflix Prize barrier of 10% has been broken

2009-06-26T17:10:00.001-07:00

via netflixprize.com

Well, looks like they did it. A bunch of teams came together and put their solutions together to do 10%. Congrats.

Posted via web from The Web and all that Jazz

Army Exoskeleton Suit Gives Man Superhuman Strength | Singularity Hub

2009-06-24T06:14:00.001-07:00

via singularityhub.com

"it is impressive enough to hear somebody say that they gave up on lifting a 200-pound weight after 500 repetitions not because they were tired but because they were bored."

I've always wanted one of these. I wonder if having mechs is too far off. Perhaps there's no tactical advantage to having a large humanoid robot.

In any case, this makes me wonder what other things DARPA funds.

Posted via web from The Web and all that Jazz

Returning the keys of all documents in CouchDb

2009-05-30T10:43:00.000-07:00

There's a bit of a learning curve when trying to use CouchDb's mapreduce. One of the harder parts is to write the reduce function, which can have two separate cases: called from the map functions, and called again from reduce functions.

When you emit data from map, the examples show you emitting the document, but you can emit any data structure you care to dream up in the key and value portion of the emit. I needed a mapreduce view that returned all the keys that were present in the all the documents. So if I had documents in the db in the form:

{"year": 2008, "birth_rate": 20.0 }
{"year": 2009, "birth_rate": 21.0 }
{"year": 2008, "death_rate": 20.0 }
{"year": 2009, "death_rate": 20.0 }

I wanted something that returned: ["year", "birth_rate", "death_rate"]

Here's one way to do it:

Tip!

How to add helpers, controllers, models, and views of your plugin into the Rails loadpath

2009-05-27T08:43:00.001-07:00

Sometimes, when you're writing a plugin, you end up writing models,
helpers, and controllers that the main app can use. However, you
don't want to copy it into the main app all the time. You'd like to
keep things separate between the plugin, but you'd like to be able to
include it in the path of the main app.

To do this, put the following in your init.rb file in the root
of your plugin. To add a new view path in your plugin that's at
PLUGIN_ROOT/lib/views (where PLUGIN_ROOT is the root directory of your
plugin):


   ActionController::Base.append_view_path(File.join(PLUGIN_ROOT, "lib", "views"))

Any template files (like html.erb) that you put in that path will be
seen in your app.

To add new helper, model, or controller directories in the rails load path:


 %w{ helpers model controller }.each do |dir|
   path = File.join(PLUGIN_ROOT, 'lib', dir)
   $LOAD_PATH << path
   Dependencies.load_paths << path
   Dependencies.load_once_paths.delete(path)
 end

And now, any models you put in lib/model, lib/controller, and
lib/helpers will be in the rails load path.

Of course, this might all be moot with the reintroduction of Rails
engines in 2.3. I haven't gotten around to using them or figuring it
out yet, but for now, this is how you do it with plugins. tip!

Posted via web from The Web and all that Jazz

Never mix package managers

2009-05-22T12:49:00.001-07:00

Today, I decided to dive into Python and explore some web frameworks.
Instead, I've spent the better part of the day messing around with
package problems on Mac OsX.

The problem? Mixing package managers. I had installed py-setuptools
from Mac Ports. Turns out it's still far behind, so it barfs when
easy_install uses it to install something like mysql-python.egg.

I should know better. On Ubuntu, I only use apt to get the language,
and the rest is managed in rubygems.

Posted via email from The Web and all that Jazz

Senate majority vs. national debt - Getting at public data is a pain

2009-04-01T18:53:00.001-07:00

Last weekend, my friend Ian and I were talking, and we got to the topic of trying to find data online to fact check newspapers. As newspapers get squeezed due to readership moving online, they have less money to do in-depth research. We hear more stories about Britney Spears and her ilk not just because of her hot pants, but because she's cheaper to cover. Sometimes, when newspapers put out something, we find out later that their facts weren't exactly right.

One of things he wanted to fact-check was the national debt, and how it related to our politicians. I imagine he was incensed at the state of financial affairs and wanted to know who were the fools that did it. He wanted to know what the senate majority was plotted against the national debt.

After that, I took some time in the last couple of days to find the data, and then write a ruby script to scrape it and plot it on a javascript webpage. Here's the resulting graph:

The first surprising thing was how fast the national debt has grown in the last 30 years. It's been an exponential growth. I think that while increased spending have happened, the interest on the debt has a significant effect on that growth.

The second surprising thing was how much democrats dominated the era between 1930 and 1980, with a sliver of Republican majority in the 50's. And before that, it was dominated by the Republicans. Apparently, political ideology shifts back and forth.

One of the things I have to note about the graph is that the first set of Red in the early 1800's is not the modern Republican party we know today. It was another party of the same name, I think also called Jeffersonian-Republicans. The gaps before and after were times when there were no Democrats or Republicans. There were Pro-administration or Anti-administration, or Pro-Jackson, Anti-Jackson, or Whigs and others. In addition, there weren't 100 seats in the Senate at the very beginning, so we see some instances where Senate Majority wasn't more than 50 seats.

Oh, and because I'm lazy, I didn't label the axis. The left y-axis is the # of senate seats held by the majority party. The right y-axis is the national debt in dollars.

We can see from the graph that the explosive rise in national debt occurred in the last two or three decades. In addition, both parties had Senate majority at the time. Not only that, but the Senate Majority party only had a slight majority, which meant that it could tip in favor of the other party from congress to congress.

Seeing how it was exponential, I plotted it as a log-plot. Ian quipped that "it's terrifying that it makes sense to plot the national debt in log scale."

You can see more details here. Remember, a line in a log plot means exponential growth. We can see that there are times in history that the US debt dropped or rose at a significantly rapid rate. I was surprised to see that in the mid 1830's, it looked like the US cleared itself of its debt. I don't know enough about history to know whether the US just defaulted or it paid the debt back. The significant rises in debt seem to correlate with the major wars. 1860's for the US Civil War, the 1915's for WWI and 1940's for WWII.

Now the last graph is not for the faint of heart. It's a graph of the rate of change of the national debt on a log scale.

Because the changes have been so dramatic in the last couple of decades, it dwarfs any changes in earlier periods on a linear scale. Here, we can see that for most of the history of the US, the debt change fluctuated up and down. There were periods of lots of spending, but then also periods of cutting back. Sometimes, one party was responsible for doing that, and sometimes, it was another. But in the recent years, we've just been accruing debt. See that little dip in the late 90's/early 2000? That was the big savings from the Clinton era. Note that it's a log scale, so that a little dip up high on the scale means that it's huge when it's lower down. If we had the level of debt back in the 1920's, we've almost have cleared it.

So all this has been interesting, but is this what falls under the "all that jazz" category? What does it have to do with the web and programming? I've been thinking about all the public the data that's out there, and how to get to it. The conclusion was that it was pretty damn hard. There were four steps to tell this story to you. I had to find the data, scrape it, clean it, and then graph it. Of the four steps, the hardest part was scraping and cleaning. It took a good 4+ hours to do it, and I'm a programmer. Most other people that were curious enough could use excel, but last I checked, excel didn't do data scraping on web pages. Hello cut and paste.

I think it should be much much easier for citizens in a country where we elect government officials to be informed and see this data for themselves. Before, we had relied on journalists to give me the straight dope on these facts. But, as I mentioned before, the newspapers have been in decline. As a result there's less budget to pay for good reporting watching the government and what it's doing. Beyond watching the government, I expect that people generally have questions that can be best answered by graphs of public data--and those answers aren't just yes or no.

As an example, another friend of mine, Matt, is single and looking for the ladies. However, living in Columbia, MD, it's a tough dating environment--everyone's under 18 or over 40. So if he could move, which counties in Maryland has the highest number of single females?

Do any of you find that you have similar questions that can be answered by public data in graphs?

Data Sources:
http://www.treasurydirect.gov/govt/reports/pd/histdebt/histdebt.htm
http://www.senate.gov/pagelayout/history/one_item_and_teasers/partydiv.htm

Posted via email from Wil's posterous

Bastardized recursion

2009-03-19T11:07:00.000-07:00

I seem to be posting less. I've been thinking about why that is. Perhaps, less things are surprising to me now (i.e. I'm not learning as much as before). When doing this Rails stuff, the bulk is standard fare, and only occasionally do you run into something mildly interesting. I have been queuing up posts, however. Between work, small side projects, reading, and hanging, there's less time than before.

I stumbled on something, which I saw in the Rails source once. Thought I'd share.

Say I have a :blog that has_many :posts. But Posts are subclassed to have many different types. But I wanted that post_type information from Blog in different formats. Originally, it looked something like this


class Blog
  has_many :posts

  def post_types
    Post.subclasses
  end

  def post_names
    post_types.map { |pt| pt.name.gsub('Post::','') }
  end

  def post_string
    post_names.map { |n| "'" + n + "'" }.join(",")
  end
end

Since they progressively built off of each other, I figured I can use a bastardized recursion, like I saw in find() in ActiveRecord::Base.


class Blog
  has_many :posts

  def post_types(format = :classes)
    case format
    when :classes
      Post.subclasses
    when :names
      post_types(:classes).map { |pt| pt.name.gsub('Post::','') }
    when :string
      post_types(:names).map { |n| "'" + n + "'" }.join(",")
    end
  end
end

Seems alright. Reduces the clutter of functions that are related to each other, so I'm on the lookout for being able to reduce related functions together like that. tip~!

Updated:
Found this reverse engineering brief on obfuscated code that recites the 12 days of Christmas. It uses the same technique that I described above. I suppose as always, case statements can be abused.

Reply comments to Frock

2009-02-13T10:35:00.000-08:00

Since I can't comment on my own blog, here we go. And people on blogger groups don't know either.

I was reading that some of the tree methods were mainly used for static collision culling, due to their expensive insertion and deletion properties. I don't know yet if Quadtrees have the desirable properties.

Thanks for the link on the Voronoi paper. I'll take a look at it.

@Wally thanks. I'll see what I can do.

@Hal Oddly enough I saw your simulation on youtube when I was browsing around the other day. Do you have source I can look at for that?

Introducing Frock, a flocking chicken simulation written in Lua with Löve

2009-02-12T04:35:00.000-08:00

I recently learned about LÖVE, a 2D game framework for Lua off HN. It looked simple enough, and when I ran the particle system demo and it was pretty fast. It seemed faster than what Ruby Shoes would be able to do. I got rather excited because

I've always wanted to make my own game. A lawnmowing game comes to mind.
I wanted to see if I could create a large flocking simulation

Also, I've decided a while back to start writing more great projects and do less reading of tech news garbage. While #1 would be on the backburner for the time being, #2 was fairly easy to do in a couple of hours. (I think about a weekend's worth of hours total tweaking things).

I've been fascinated with decentralized systems since right after college--one of them being flocks. But how do they work? For a long time, ornithologist (bird scientists) had no clue how birds flocked. Birds seem to be able to move in unison, as a super-organism, swooping, expanding/contracting, splitting. When you see massive waves of these things (these are starlings), it's something to behold. Who is the leader? How do they coordinate these flocks?

We still don't exactly know, since we don't yet have the capabilities to tap into a bird's decision making mechanism in real time. However, in the 1990's, Craig Reynolds demonstrated that you can get very convincing flock-like behavior generated procedurally, using three simple rules. And it ends up that you don't need a leader to get flocking behavior. All interactions can be local, and each flock member (or boid, as he called it), just needed to follow three simple rules:

Attraction: Move towards the perceived center of the flock according to your neighbors
Repulsion: Avoid colliding with your neighbors
Alignment: Move in the same direction and speed (velocity) as your neighbors.

Add up all these vectors together and you get a resultant velocity vector. Different amounts of the three influences leads to different looking types of flocks. As an aside, particle swarm optimization works on the same sort of principles.

So here it is. Introducing Frock, a flocking simulator in Lua Love.

I release it now, because while it's primitive, it works (release early, release often!). The screenshot doesn't really show it well, they fly about in a flock, hunting for plants to eat. It's rather mesmerizing, and I find I just stare at it, the same way I stare at fish tanks.

It was originally a port of the Ruby Shoe's hungry boids, but I used flying chickens lifted from Harvest Moon instead. I originally had cows flying about, but without flapping, it just wasn't the same. I also made the repulsion vector increase as a function of decreasing distance. Otherwise, the chickens didn't mind being right on top of each other if they were on the inside of the flock.

My immediate goal is to make it support more chickens, so I can get a whole swarm of them. Right now, I'm using an inefficient algorithm to calculate which chickens are neighbors (basically n^2 comparisons). So if any of you have good culling techniques applicable here, I'd love to hear it. I'm currently looking at R-trees.

There are different possibilities as to where it could go. I think while lots of people have written boid simulations, they haven't taken it much further than that. While I've seen ones with predators, I haven't seen anything where people try to evolve the flock parameters, or try to scale it up to a large number of chickens. One can also do experiments on whether different flock parameters have different coverage of the field, or which set of parameters minimizes the time a plant is alive.

If at the basic, it becomes a framework for me to write 'me and my neighbors' decentralized algorithms, that'd be useful too. And since Lua is suppose to be embeddable into other languages, that makes it an even more exciting possibility. Later on, I'll write a little something about Lua.

Well, if you decide to try it out yourself, get to the Frock github repo, and follow the readme. Patches are welcome, but note I haven't decided on a license yet--but it will be open source. If you have questions, feel free to contact me or comment. Have fun!

Can't comment

2009-02-03T14:00:00.000-08:00

Somehow, blogger doesn't let me comment. I'm not sure why, and I'll fix it some time later, or export to Posterous.

Thanks trevor. I've subscribed to your weekly digest. I've been reading Hacker News all this time. However, it wasn't so much that I didn't have time to read, as I didn't have time to synthesize them.

And oh, thanks for the Perforce slides. They've been really helpful.

Nerd time, issue 15

2009-02-03T12:47:00.000-08:00

Nerd time is back, due to some complaints in person about how they missed it. In brief, nerd time is an occasional mailing list I send out to people I know that work at research labs. They're usually slow in getting the tech world news, so I thought it would be fun to pass along some tech news bits. This is issue 15.
-----
Hi all.

Well, after starting work at Frogmetrics last May, I got really busy writing code, learning about business and startup related things, and absorbing sales and marketing stuff, that I simply read a lot less. There was also less tech news going on that I felt was significant. When there's no significant news, the echoes become pretty loud in the echo chamber. Since I didn't hear anyone say anything about it, I figured no one read nerd time. And since I was reading less, I became more intellectually lazy. Hence the 10 month silence on nerd time.

But about a month and a half ago, I got in-person complaints that nerd time was no longer being sent out, so here it is reinstated. Some of these might be old news, but it's what I collected and found was significant over the last couple of months. And what the hell, old news in the tech world takes a while to get to the research lab world, so hey, this might be new to you. This time is mostly about source control and languages. I have other things I'm playing with that might be of interest, but will reveal them as I mature them.

Git the decentralized version control
Decentralized version control isn't anything new, but its adoption is. Git is pretty powerful. I don't go into all the reasons why. You can read about it in my post here. But on a deeper level, git is essentially a versioned filesystem. In fact, what's most interesting about it is how general it is and how you can use it for things other than version control. You can use it to synchronize address books, remote deploy code, or even as a basic wiki or blog.
http://git-scm.com/
http://whygitisbetterthanx.com/
http://eagain.net/articles/git-for-computer-scientists/

Github a social network for developers
Github is like sourceforge, but much better designed, and has a social component to it. I can follow the coders and projects that I admire or find useful, and I can also see what projects they are committing to or watching. Thus, it gives me a sort of leading indicator of what the alpha nerds and geeks find interesting. And what they find interesting is what you and I will be using in our jobs 5 to 8 years down the line. The generality of git, as mentioned in the previous entry is given as an example in the last link. It's of Raganwald, a well known Ruby coder and blogger who blogs on Github. Having a central place to commit and share code sorta defeats a mainstay of decentralized source control, but let's ignore that point for now, and drink the github kool-aid
http://www.github.com/
http://github.com/raganwald/homoiconic/tree/master/2008-10-30/thrush.markdown

GitTorrent
Along the same lines, someone combined git with bittorrents. Whoot.
http://www.advogato.org/article/994.html

SUP friendfeed
I'm personally not as excited about SUP as I don't mess around with feeds that much. But it claims to cut down on bandwidth for servicing feeds
http://blog.friendfeed.com/2008/08/simple-update-protocol-fetch-updates.html

Sinatra
If you thought Rails was lightweight, Sinatra blows it out of the water. While there have been other micro-frameworks for web apps, sinatra takes the cake in my opinion. It doesn't take very much at all to get something up and running with sinatra. So given the amount of prototyping work that the lab does, it helps to just get something demoable up. If you wanted to continue with it, sinatra runs on pretty solid web server, and you can optionally switch it out also. I'd recommend taking a good look at it, and brush up on your Ruby skills as well.
http://sinatra.rubyforge.org/

Clojure
Clojure is a lisp dialect in a JVM. I've heard some good things about it, but I haven't really tried it out myself, so I can't speak on the merits of Clojure. However, as the second link below wonders, could Clojure be to concurrency orientated programming as Java was to OOP? I've talked about Erlang in the past, and it defn has some amazing traits as a programming language, barring the syntax.
http://clojure.org/
http://bc.tech.coop/blog/081201.html

As for actual programming languages I've been messing with, there are three. Erlang, Javascript, and Lua. I'll only talk about the last one--and I only started messing with it because of LÖVE.

LÖVE is an "unquestionably awesome 2D game engine"
More akin to Pygame in Python than to Shoes in Ruby, Love lets you quickly build a game, but still stay within the realms of programming. The reason why I find it worth mentioning are the merits of Lua. It's a basic interpreted language, but it's embeddable into other languages, and its total size is pretty small ~200k or so. This make it ideal to be used in embedded systems. In addition, it's one of the faster interpreted languages out there, and with LuaJIT (on the JVM), it's even faster.
http://love2d.org/?teej

Mozilla Weave and Prism
Google Chrome
While I'm sure the lot of you have heard about Google Chrome, what's interesting to me is in relation to the direction that Mozilla, and also Adobe Air have been trying to move towards: treating web applications like desktop applications. Not only will they be easy to install, and easy to maintain, but they afford easy collaboration with others. And with the maturity of Google Gears, being offline is not a problem now either. While there are still a couple bastions where pure desktop applications reign, such as gaming, I think we'll find that the web app style development to be more pervasive for desktop apps.
http://labs.mozilla.com/2007/10/prism/
http://labs.mozilla.com/2007/12/introducing-weave/
http://www.google.com/chrome

SVG and application development
I don't know that SVG will be the future of application development or not, but I know that the current html and css constructs were meant for documents. Web developers are actually rebending those tools for application needs. While it's useful to think of the web as a collection of resources and document--it makes for a scaleable app--the actual page elements are still stuck in document-page speak. It would make it easier for app development to have their own app-specific constructs. SVG may or may not help in that regard
http://www.sitepoint.com/blogs/2008/12/22/svg-is-the-future-of-application-development/

Stackless Python, PyCUDA
There's lot of people trying to find suitable languages for our multicore future. I'm not so sure that Erlang will be it. However, functional programming concepts are going to make a comeback, if not already. Python is poised to be ready as being able to handle concurrency through stackless. Some people are experimenting with using Python to access the new Nvidia CUDA hardware architecture.
http://www.stackless.com/
http://mathema.tician.de/software/pycuda

Gnip Central
Gnip central acts as a data middle man. Often times, getting through the API sucks for various reasons, and having a middle man that either converts that data for you, makes it available, or converts it into a push model instead makes it convenient. It's an interesting niche, and I see this is as a perennial tar pit of data portability.
http://www.gnipcentral.com/

New York Times API
New York times is probably the more forward thinking out of all the newspapers when it comes to the web. Who else do you know that has released an API?
http://developer.nytimes.com/docs/movie_reviews_api?authChecked=1

Figuring out a branching strategy

2009-01-29T06:25:00.000-08:00

To be honest, before I started working at Frogmetrics, I didn't know how project branches were managed. I was working at a research lab, and most of what we did was prototyping. After we demonstrated that it worked, we threw it over a wall, and then it was someone else's problem (poor them). A lot of the time, I was doing work on my own, so there was no (perceived) need for source control. The only time we used source control was when I was working on the New Horizon spacecraft. And even then, someone else managed the branches. Because it was SVN, we all mainly worked off trunk.

Until recently, I never contributed to an open source project either. Therefore, I really had no idea when to branch. So when we started working on the analytics, we really had no idea what a good branching strategy would be.

Googling didn't help, because either everyone else doesn't call it "branching strategy", or everyone already knew how to do it. I eventually figured something out though.

Last week, after talking to AJ of Scoopler about git, he ended up asking about branching strategy. It became apparent that branching strategy wasn't an obvious thing, so I decided to write something here. This is obviously not the only way to do it, so if you have other suggestions, by all means, comment.

At first, we didn't know what we were doing. We knew that we wanted to have a branch that had the same code on the production server, and another branch where we're working on the 'next' version. So we had a branching strategy that looked like this:

As you can see, we branched every time we deployed weekly. This gave us the option of doing bug fixes on the every deploy version, while keeping a working branch. However, this was a terrible way to do things. This branching strategy required you to keep merging back bug fixes that you had made earlier. In addition, we were using bug tracking software to track all the issues from week to week, which results in much ticket shuffling and overhead.

Now, we're doing this. Locally, we still branch for every feature that we're working on. And when there's a major set of features that need to be implemented by more than one developer, we create a remote branch for it that we push and pull to/from.

Thus, we're treating master as the golden copy of the code base. It is always deploy-able, passes all tests, and is perfect code as we know it. This allows us still the advantage of doing bug fixes and deploying independent of what features are currently on deck or in the hole, and yet we don't have to do merges every time are about to do a new version. We simply (and somewhat arbitrarily) tag versions as we go along, and only merge feature branches back. When we can, we rebase the branches to keep the history clean. In addition, we try to make our commits atomic and about one thing, rather than one feature set. That way, it makes it very helpful to remove a piece of code, cherry-pick a changeset to another branch, or find an offending commit that broke something.

So far, it's worked pretty well, but it might evolve as we go on.

Well, hope that helps. This post wasn't as fun to write, but it was something I hadn't see too much of out on the web, so I figured I'd contribute. Fun times.

Git allows my workflow to be "stateless" (or more advanced features of git)

2009-01-23T09:55:00.000-08:00

I've been using git since May, and I feel like I use it pretty comfortably now. Oddly enough, with SVN, I just learned the basic check in and out, and left it at that. With git, I find that I want to do something--after poking around docs and tutorials, I find some of the advanced features of git something that I'd want to use.

Git has a bit of a learning curve, since their commands aren't exactly intuitive (deleting a remote repository anyone?, how about reverting is different from resetting?) you have to discard your notions of Svn, and learn how Git models a repository. But once you grasp that, it's pretty easy, not to mention pretty powerful. For me, Git had certain features that gave me a "wow", as I learned about and got use to using them. Here's in order as I discovered them.

Local branching

Branching is fast, and merging is relatively painless. When branching is fast, you end up treating branches are like tabs on your browser, but for source control. This lets you experiment with different code without affecting the main branch.


git checkout -b new_branch

Builtin Grep

I hated that grep would also search through the .svn files. Sure, I wrote an alias and script so that it wouldn't, but it would leak sometimes. Having git have a built-in grep was very nice.


git grep "some_regex"

Interactive staging of commits

Git has this idea of staging files, meaning marking them for a commit. Because you can commit different files, you can fix little things that might not have to do with your current ticket, but add them as separate commits.

But what if you edited one file but the edits had to do with two different tickets? With git, you can selectively stage parts of a file for committing.


git add -p

Rebasing branches

Rebase was a little confusing to me at first. The name didn't tell me anything. Rebase isa tool with multiple functions, with the same underlying principle, which is why it has just one name.

At the very basic, you can use rebase to move the root of the local branch if you want the changes made on the parent branch since then. This is important because it puts the burden of merging on the patch writer, and not on the merger. In addition, it makes for a cleaner commit history.


git checkout child_branch
git rebase parent_branch

Even better, you can reorder the commits as long as you haven't pushed it to a remote repository yet. The same task allows you to squash your commits together for a cleaner history.


git rebase -i HEAD~n

Stashing changes

Because you can stage files for commits and you can readily switch between branches, sometimes, you might be working on something, but they're not ready to be committed. The production code has a bug that needs to be fixed immediately. Git won't let you switch branches, but you don't want to commit unfinished code. What do you do?

Git lets you stash your changes to save your uncommitted changes, but not commit them anywhere. This is useful to switch to another branch to fix an emergency bug or perform other operations that require no uncommitted changes in the working directory (like rebase).


git stash
...fix bug on other branch...
git stash list
git stash apply

Bisection of commits

Sometimes, you're humming along with your commits, and you find that there was a part of the application that is broken, but your tests didn't catch it. You need to revert back to that version and make a branch. You can use git bisect to look for a particular commit. You give it a commit, and git will checkout that version, and ask you whether it works or not. Then it bisects the commits and half and then checks out the other half and asks you if it's correct. If not, it'll keep narrowing down the space of commits until you find the right one.


git bisect commit_hash other_commit_hash

Basically, a lot of what Git enables me to do is switch between tasks easily. I don't know if it's the right word, but it lets me work statelessly. At no time does git not let me do something because of a particular part of my workflow that I'm in. Outside of a few commands like rebase and merge (which can be fixed with stash), the commands I can run in git doesn't depend on the previous commands I've run. Really, git is a tabbed browser for me.

My biggest complaint is probably that the names of the commands aren't intuitive because it goes against the usual mental model of what a repo does. The names are actually make a lot more sense only after you understand how git models a repository. So take a look at the git book, and learn what you can.

tip!

iPhone jailbreaking resources because search has failed me.

2009-01-12T11:13:00.000-08:00

A couple weeks back, I jailbroke my iPhone, so I could finally join the rest of the techno literati while on a carrier besides AT&T. However, this is one of those popular topics that are fraught with websites that just have a ridiculous number of ads on them. Not only that, it's mostly blogs repeating each other, and you get 2nd, 3rd, or maybe 50th hand information. And a lot of them are un-informational--only trying to sell you iPhone jailbreaking services. Didn't know the difference between jailbreaking and unlocking, and could barely find the page.

Because google search fails in this regard, I will recount that Jailbreaking is when you break the iPhone free of the app store, and you can install software from other sources and app installers, like Cydia. Unlocking is making your phone work with any phone carrier.

Surprisingly, these links were hard to fine--of the actual iPhone Dev Team Portal and of their forum. Those are what I found to be most helpful, though they don't even have a download page, which makes me kinda mad as I hunted around for it. Checkout yellowsn0w, as well as their QuickPwn, also here (much better than Z-phone). If you're still confused, which rightfully, you are. Over at iClarified, there are very good and clear tutorials on how to use the applications.

IPhone unlocking is one of those searches that I think Google just fails at. I hadn't noticed because most of what I search for is usually academic, mathematic, or open source developer related. Those two have been rather blissfully free of intrusive ads of non-informational webpages. With such a system, people know they're being watched and indexed, and if it's an advantage to get a 'high score', they're going to try to game (or optimize) on it. It seems uncannily related to sexual selection. I'll talk about that in another post in the future. For now, enjoy the iPhone resources

The Web and all that Jazz: Git remote branch notes

2008-12-11T14:37:00.000-08:00

A while back, I was wondering how to make a remote branch from a local branch because all the solutions I knew of created a remote branch from master, using origin

After trying out a couple things, I realized I could just create the remote branch from master, and just rebase the damn thing:


git push origin {new_remote_branch}
git branch --track {new_remote_branch} origin/{new_remote_branch}
git checkout {new_remote_branch}
git rebase {local_branch}
git push

Not super interesting, but enough and short enough to blog about. tip!

Augmenting Google's search results

2008-11-21T09:11:00.000-08:00

Here, techcrunch was complaining about Google's newly released feature of being able to change the ordering of the search results. The point that seemed to have escaped people is that, the search results that you change are only local to you. Other people don't see them.

Because of that, I think Google can encourage the behavior where people are sending links relevant to themselves up to the their front page in an honest way. If they click things up that have no relevance to themselves, they only screw up their own searches.

So if you have millions of people sending things relevant to themselves up the list, Google is basically gathering data about what the human 'gold standard' for a particular search query is (augmented by machine sorting first).

In information retrieval, one of the hard things is to know whether you've done a better job of returning search results or not, since a gold standard dataset is hard to come by and time consuming to produce.

Here, I think Google is simply using a mechanism where they're aligning people's self-interest to create accurate data they can use to compare their search algorithm tweaks.

All in all, a good thing. Even better if you can 'merge' search results from others that you trust..say your friends. I wouldn't mind merging my search results with _why's. More complexity that way, though.

Frogmetrics on techcrunch

2008-10-24T06:29:00.000-07:00

As some of you know, I joined a YCombinator company called Frogmetrics. We've launched, and was covered by Techcrunch last night.

I work on the server side of things, which means the analytics package which we call Mastermind. Working on the architecture over the summer was a little bit different than the typical rails app.

Mastermind allows users to view graphs of survey data for a particular region, location, or employee at a specific time period.

One of the comments that I saw on techcrunch was why didn't we use iPhones? That's a common question, and the answer is a mix of technical and business reasons. If we had iPhones to give to people, they would readily know that it was an iPhone and be more likely to run off with one. Sorry Nokia, but your tablets just aren't as sexy to run off with. Alternatively, telling people to go to a webpage on their iPhones would be another barrier to taking the survey. It wouldn't get the high response rates that we're seeing right now. The idea is to make it as easy and as painless as possible to take a survey. In our pilots, we found that older folks had a much tougher time reading the text. Nokias have bigger screens, and we could hence put bigger text on there, not to mention big beautiful buttons that affords pushing.

Well, if you or your company has interest in our product, feel free to let us know on the contact page. I dislike that we don't have our prices on the web page as of yet, but that'll be worked out soon.

Wish us luck (and hard work)!

As a side note, interesting things that I post on here don't always have to do with Frogmetrics. Like any good engineer, I play or think about interesting things whether they're related to work or not. So don't take it that whatever I'm playing with here is what's going into Frogmetrics. :)

Edited

Benchmarking row multiply in Ruby's Linalg

2008-10-02T20:07:00.000-07:00

While using LinAlg to write and understand/review information gain, I found that I wanted the equivalent of a row multiply, notated as [*] (it's non-standard. I made up the notation), where:

A [*] x = B

[[a₀₀, ..., a_0M]      [[x₀]    [[a₀₀ * x₀, ..., a_0M * _x0]
 [...       ...]  [*]  [x₁]  =  [... * x₁, ....      ...]
 [a_N0, ..., a_NM]]      [x₂]]    [a_N0 * x₂, ..., a_NM * _x2]]

I want to map each row with each corresponding value of x. This operation is not standard matrix multiplication, though I feel like it should be!

I admit I slept in Linear Algebra class. Thus I was a bit dumbfounded about how to express it using normal matrix multiplication. While I could do it using LinAlg's mapping functions, I knew that it could be done because it was all linear transformations.

Luckily James Lawrence, who maintains LinAlg was emailing me, and asked me about it (thanks!). He gave me some code that did it both ways. After I read it, I slapped myself.


# using straight up matrix multiplication
def calculate1(con)
  DMatrix.diagonal(con*DMatrix.new(con.hsize,1,1)).inverse*con
end

# using map
def calculate2(con)
  DMatrix.diagonal((con*DMatrix.new(con.hsize,1,1)).map { |e| 1.0/e })*con
end

I wasn't sure which one was faster. Maybe they'd be about the same. Maybe doing matrix multiply would be slower because you'd have to go through all the multiplications. Per James's suggestion, I benchmarked them, in the fine form of yak shaving.

Run on a laptop 1.1GHz Pentium M, 758MBs, I did two experiments. For one experiment, I kept the matrix at 800 rows, then I grew the columns. Let's see what it looks like:

time (secs) vs column size

I should have labeled the axis in GnuPlot, but you'll live. The y axis is the number of seconds, and the x axis is the column size. Uninteresting, but nice to know it's linear. The two functions aren't significantly different from each other in the amount of time that it takes. I expected the map (calculate2) to be much faster since it didn't have to do all the multiplies. oh well.

I almost didn't run the second test, but it proved to be a bit more interesting. This time I kept 800 columns and grew the number of rows. Same axis. Different graph:

time (secs) vs row size

Whoa! It's exponential. Or quadratic. I can't tell. Anyway, anything curving up is bad news. ~~I suspect this might have something to do with row major/column major ordering. C stores matrices row by row, whereas Fortran stores it column by column.~~. Update: As corrected by James L., in the first experiment, growing columns will create more multiplies inside the diag() call, but the size of the diagonal will stay the same. Growing the rows, however, will create less multiplies inside the diag() call, but each increase in row size will increase both dimensions of the resulting diagonal matrix, giving us n^2. So it's quadratic.

So what I went looking for wasn't what I meant to find. But given that ~~I've read about it before, it wasn't super interesting~~it would have made sense had I thought about it, I guess it's not super surprising. Let's see if we can use transpose to cut down on the time. For one part, we'll grow the rows as before, and compare it to growing rows, but transposing the input then transposing the output, to get the same deal. What's it look like:

time(secs) vs row size

This is good news. Even if transpose is an extra couple of manipulations, it saves us computation for bigger matrix sizes. The most interesting part of the graph is the crossing of the two graphs. If somehow, LinAlg (or any other package for that matter) can detect where that inflection point is going to be, it can switch off between the two. The only thing I can think of is another package lying underneath doing sampling of each implementation randomly whenever a user calls the function to do interpolation of its growth curve, and then calculate the crossing analytically. I don't currently know of any package that does this (or if it does, I don't know about it, cuz it already performs so well by doing the switch!)

This was a nice little diversion from my side projects...a side project of side projects. Back to learning about information gain and its ilk. At least something came out of it. I have a nice little experiment module that I can use to do other experiments. And I spent way too much time on it not to post something...

I share my code below, and you can run it if you want. snippet!

# These are the experiments that I ran
#!/usr/bin/ruby

require 'experiment'

require 'linalg'
include Linalg

def calculate1(con)
  DMatrix.diagonal(con*DMatrix.new(con.hsize,1,1)).inverse*con
end

def calculate2(con)
  DMatrix.diagonal((con*DMatrix.new(con.hsize,1,1)).map { |e| 1.0/e })*con
end

DATA_PTS = 10
MAX = 800
MID = MAX / 2
STEP = MAX / DATA_PTS

# Growing columns
Experiment::compare(1..MAX, STEP, 
                    proc { |col_size| DMatrix.rand(MID, col_size) },
                    proc { |matrix, col_size|
                      calculate1(matrix)
                    },
                    proc { |matrix, col_size|
                      calculate2(matrix)
                    })

# Growing rows
Experiment::compare(1..MAX, STEP, 
                    proc { |row_size| DMatrix.rand(row_size, MID) },
                    proc { |matrix, row_size|
                      calculate1(matrix)
                    },
                    proc { |matrix, row_size|
                      calculate2(matrix)
                    })

# Growing rows, transposing
Experiment::compare(1..MAX, STEP, 
                    proc { |row_size| DMatrix.rand(row_size, MID) },
                    proc { |matrix, col_size|
                      calculate1(matrix)
                    },
                    proc { |matrix, col_size|
                      calculate1(matrix.transpose).transpose
                    })

# Experiment.rb - perform timed experiments across on one dimension
require 'rubygems'
require 'gnuplot'

# Experiment is a module where you can use to plot and benchmark pieces of code
# and plot it on a gnuplot
#
# 
module Experiment
  class << self

    def timer
      start_time = Time.now
      yield
      diff_time = Time.now - start_time
      puts "That run took #{diff_time} seconds"
      return diff_time
    end

    # takes range to try and the step resolution of the range and runs 
    # the benchmark_block with each of the different ranges. 
    # the init_proc only gets run once during setup.
    #
    # Experiment::benchmark((1..50), 10, 
    #            proc { |col_size| DMatrix.rand(500, col_size)},
    #            proc { |matrix, col_size| ProbSpace.new(matrix).entropy })
    def benchmark(range, resolution, init_proc, benchmark_block)
      xs, ts = [], []
      range.step(resolution) do |x_size|
        object = init_proc.call(x_size)
        xs << x_size
        ts << timer { benchmark_block.call(object, x_size) }
      end
      plot(xs, ts)
    end

    # same idea as benchmark, but does two at the same time.  So 
    # it takes an init_proc to initialize the experiment, 
    # and two different procs, standard and comparison, to run 
    # for each step in the range at the given resolution.
    #
    # Experiment::benchmark((1..50), 10, 
    #            proc { |col_size| DMatrix.rand(500, col_size)},
    #            proc { |matrix, col_size| ProbSpace.new(matrix).entropy1 },
    #            proc { |matrix, col_size| ProbSpace.new(matrix).entropy2 })
    def compare(range, resolution, init_proc, 
                standard_block, comparison_block)
      xs, s_ts, c_ts = [], [], []
      range.step(resolution) do |x_size|
        object = init_proc.call(x_size)
        xs << x_size
        s_ts << timer { standard_block.call(object, x_size) }
        c_ts << timer { comparison_block.call(object, x_size) }
        puts "#{x_size} = standard : comparison :: #{s_ts.last} : #{c_ts.last} secs"
      end
      plot(xs, s_ts, c_ts)
    end

    def plot(x, *ys)
      Gnuplot.open do |gp|
        Gnuplot::Plot.new(gp) do |plot|
          ys.each do |y|
            plot.data << Gnuplot::DataSet.new([x, y]) do |ds|
              ds.with = "linespoints"
              ds.notitle
            end
          end
        end
      end
    end

  end
end

Somebody knows Shoes

2008-09-29T20:36:00.000-07:00

I'm a fairly late adopter compared to some of you. When Shoes came out, I had followed it, but never tried it. It's been at least 8 months now, and I finally got around to it. I guess I don't really try something out unless I have a use for it in my mind. Still waiting for that Haskell project...

Anyway, trying out Shoes was...easy. Outside of compiling it, actually. I take that back. Once I read the README and figured out what packages I needed, it was easy. Even easier when I found the executables. Running the sample code was...easy. And trying out your own app...you guessed it...even easier. It helps that there's a ton of examples and documentation. Makes me think that when programming, you should keep the API of your code in mind, so that it's easy to use after you've implemented it.

Two things strike me immediately. _why took his ability to make DSL in Ruby to heart. I don't have to think about the buffering, cursor positions, etc. Even better, the functions are orthogonal and consistent.

You can not only move shapes around to follow your mouse, but also widgets, like buttons.

Shoes.app(:width => 300, :height => 300 do
  background snow
  @o = stack do
    button("Message") { alert("Sent!") }
  end

  motion do |x,y|
    @o.move width - x, height - y
  end
end

Motion gets executed whenever your mouse moves around on the Shoes screen. So you can have a button dancing opposite to your mouse. Another surprising thing is that an app is structured like a webpage, and different pages have urls. And routing is declared in the app block itself! And not only that, it takes regexs

class Dictionary < Shoes
  url '/', :index
  url '/(\w+)', :word

  def index
    stack do
      title "Enter a Word"
      @word = edit_line
      button "OK" do 
        visit "/#{@word.text}"
      end
    end
  end

  def word(string)
    stack do
      para "No definition found for #{string}. ",
        "Sorry this doesn't actually work."
    end
  end
end

Shoes.app

I'm not sure how far this sort of thing can go when building more complex GUIs, but so far, it seems pretty promising. There were a couple things that were broken on Ubuntu, however. I couldn't get margins to work, as well as rounded corners:

Shoes.app(:margin => 20) do
  background red, :radius => 12
end

Boo. Rounded corners would have been exciting.

Well, try it out and see if you like it. There's lots of neat things people have built with Shoes already.

I, on the other hand, just built a prototype. Nothin to see here folks.

EmacsWiki: Moving The Ctrl Key

2008-09-24T10:38:00.000-07:00

EmacsWiki: Moving The Ctrl Key

I put off doing this for too long now. I have to admit, if there are settings that I can do in a GUI without mucking around in a config file, I'd do it. Ubuntu has made it easy.

Installing Ruby's linalg in Ubuntu

2008-09-22T21:28:00.000-07:00

Ruby has a project for download called linalg that exposes the LAPACK functions in Ruby. LAPACK is a set of routines written in Fortran to do Linear Algebra operations. Now, before you cry foul about Fortran, LAPACK is used in a lot of places, and it's pretty damn old and has held up over the years.

The linalg package just updated about two weeks ago, first since 2004, so it has some updates. Unfortunately, there's no easy gem to install. You'll have to download the tar, and then run


sudo ruby install.rb

Of course, you'll run into some problems, unless you have other packages installed:


sudo apt-get install lapack3 lapack3-dev libg2c0-dev

Don't worry, if you don't like it, you can run uninstall. Read INSTALL file for more directions.
I use to wonder how people knew which packages to look for. Apparently, you look at the output and see what files the configure is crapping out on. Then use apt-file to search for which package the file is in. It's one of those basic things that seems not mentioning in hindsight. Like calling "source ~/.bashrc" after you've edited your bash files. No one ever mentions that.


sudo apt-get install apt-file
sudo apt-file update
apt-file list g2c.h

Knowing that, you'll know how to fish, and I'll not post how to install stuff in the future.

tip!

Algorithm always matters, even when parallel

2008-09-12T10:00:00.000-07:00

I've finally had some time to start looking at things that looked interesting to me. One of the things that I started looking at was parallel algorithms.

I was reading Hacker News, and I saw some link that lead me to discover Cilk, a C extension to easily make parallel programs.

thread int fib(int n) {
  if (n < 2)
    return n;
  else {
    cont int x, y;
    x = spawn fib (n-2);
    y = spawn fib (n-1);
    sync;
    return x+y;
  }
}

This was the example given for calculating the Fibonacci sequence in parallel. This is the standard mathematical way to define it, and it looks clean enough. So instead of trying it out in Cilk, I fired up Erlang to try my hand at doing a port. I found it a little bit difficult because while you can easily spawn processes in Erlang, there was no quick way for the parent process to wait/sync/join child processes and get their results. Since that was besides the point of the exercise, I fired up Ruby, even though they had a slow Threading library (which is suppose to be fixed in 1.9, plus Fibers!) I'll do with it Erlang some other time.

First I wrote the threaded version to mimic the Cilk code:

def fib_threaded(n)
  if n < 2
    return 1
  else
    threads = []
    x = 0
    y = 0
    threads << Thread.new(n - 2) { |i| x = fib_threaded(i) }
    threads << Thread.new(n - 1) { |i| y = fib_threaded(i) }
    threads.each { |thread| thread.join }
    return x + y
  end
end

I don't have a multi-core processor. I'm on a 3 year old 1GHz laptop. At a mere fib(18), it was taking about 21 seconds to run. To see if there was a difference, I wrote a serial version.


def fib_serial(n)
  n < 2 ? 1 : fib_serial(n - 1) + fib_serial(n - 2)
end

This one ran much much faster. It took about 0.02594 seconds. At this point, it's probably the overhead of thread creation that's making it take so long to run. Maybe with green threads or lightweight threads, the threaded version would run much faster. That makes me want to try it in Erlang just to compare. But wtf, adding shouldn't take that long, even if it is 0.025 seconds

When I thought about it, it was an efficient algorithm: there's a lot of wasted cycles. In order to compute f(n), you have to calculate f(n - 1) and f(n - 2) in separate threads.

The f(n - 1) thread requires it to spawn two more threads to compute f(n - 2) and f(n - 3).
The f(n - 2) thread requires it to spawn two more threads to compute f(n - 3) and f(n - 4).

Notice that both the threads for f(n - 1) and f(n - 2) have to spawn two different threads to calculate f(n - 3). And since this algorithm has no way for threads to share their results, they have to recompute values all over again. The higher the n, the worse the problem is, exponentially.

To calculate the speedup given to an algorithm by adding more processors, you calculate the amount of total work required and divide it by the span of the parallel graph. If that didn't make sense, read lecture one for Cilk, which is where the diagram comes from. So for fib(n)

Twork = O(n^2)

The total amount of work is the total number of processes spawned. Since every f(n) recursively spawns two other processes, it's about n^2 processes.

Tspan = O(ln n)

The total span is how many nodes a particular calculation traverses. A la the diagram, it's about the height of the tree, so that's about ln n nodes.

Therefore, for fib(n), the processor speed up is at most:

Tw / Ts = O(n^2) / O(ln n)

I don't know of any reductions for that off the top of my head, but you can see that the processor speedup gain grows somewhere in between n and n^2. On one hand, it means this algorithm can benefit from speedups by adding up to somewhere between n and n^2 processors. However, that also means that to make this algorithm go as fast as it can to process fib(1000), you need more than 1000 processors to make it worthwhile. Not so good for a parallel program that's just doing addition.

As a last version, I wrote one that computed the Fibonacci from 0 up to n, and keeping the total as I go along, instead of the recursive version that has to work its way n back down to zero.


def fib_loop(n) 
  sequence = [1, 1]
  if n < 2
    sequence[n]
  else
    sequence = (1..n-1).inject(sequence) do |t, e|
      t << (t[-2] + t[-1])
    end
  end
  sequence[-1]
end

It's not space effective since I wrote it quickly, but this beat the pants off the other two running at 0.00014 seconds. As you can see, you're not recalculating any f(n) more times than you need to.

I wish Cilk had a better first example to parallel programs. Given that the guy making Cilk is the same guy that co-wrote the famous mobile book for algorithms, I guess I was surprised. However, it was a fun exercise, and made me think about algorithms again.

I'll find some other little project that requires me to write in Erlang, rather than falling back on the comfortable Ruby. snippet! Below if you want to run it yourself.

#!/usr/bin/ruby # rubinacci.rb by Wilhelm def fib_threaded(n) if n < 2 return 1 else threads = [] x = 0 y = 0 threads << Thread.new(n - 2) { |i| x = fib_threaded(i) } threads << Thread.new(n - 1) { |i| y = fib_threaded(i) } threads.each { |thread| thread.join } return x + y end end def fib_serial(n) n < 2 ? 1 : fib_serial(n - 1) + fib_serial(n - 2) end def fib_loop(n) sequence = [1, 1] if n < 2 sequence[n] else sequence = (1..n-1).inject(sequence) do |t, e| t << (t[-2] + t[-1]) end end sequence[-1] end def run(&algorithm) start_time = Time.now integer = 18 answer = algorithm.call(integer) elapsed = Time.now - start_time puts "Fib(#{integer}) = #{answer}" puts "Total elapsed time: #{elapsed} seconds" end puts "threaded:" run do |integer| fib_threaded(integer) end puts "serial:" run do |integer| fib_serial(integer) end puts "loop:" run do |integer| fib_loop(integer) end