California: June

I have been in Mountain View, CA for 2 weeks now. The internship at Google has been going well. The basic time line has been as follows:

• I arrived in Mountain View on May 31st.
• My first day at Google was Jun 2nd.
• They did “on-boarding” for most of that week. Which was kinda painful at times, but I did learn a lot about how Google works.
• On Friday I finally got a chance to start to do a little real work and I started to figure out what project I would be doing. More on that below.
• The next week (last week) I had only one class I had to attend so I finally started to get real amounts of work done.

I’ve been meeting lots of good people both at Google and from my housemate Dave’s social group. There are board games every Tuesday night and dinner and movies every Saturday, so I have not been suffering from lack of socialization which has been nice (it keeps Arthur from getting even more crazy). Yesterday I went on a hike with a bunch of Google interns. It was fun though the group was a bit too big and for some reason everyone wanted to walk really fast, so I ended up at the very back keeping track of the stragglers and taking pictures. The stragglers where actually a really fun group of people it turned out.

The hike was to the beach at Reyes Point (click the link to see a map of our route). It was a really nice hike (though longer than I expected). I got some good pictures and even a couple panoramas. I also met several really good people and chatted about all sort of nerdy things (these are Google interns after all).

My Google project is related to type checking Python code. I probably shouldn’t go into too much detail online since I don’t know what is secret and what isn’t, but I know I can tell you about the code that is open-source already. I have been working with PyTypeDecl and a metacyclic Python bytecode interpreter called Byterun. It’s been quite interesting and I think the I will be proud of the results.

So overall California is treating me well. Tomorrow I will be back to work and trying to push forward with my plan of action. And trying not to eat too many snacks. Oh, that reminds me. As some of you I’m sure know, Google has free food all over the place. They have cafes all over campus that are all free (for Googlers), and they actually produce very good food. I mean not everything is great, but it’s better than most of the $5 lunches I could get around UT. Also they have kitchenettes on each floor which have a lot of snacks and tea and stuff like that. I guess their theory is a well fed programmer is a productive programmer. I don’t mind being pampered a bit, but the chocolate they have is good enough to be really dangerous. ;-)

A musing on how to become a better programmer

• Haskell, OCaml, SML (Functional languages)
• Prolog, Mercury (Logic languages)
• Python, Ruby, JavaScript (Dynamic languages)
• Java, C#, Scala (Modern O-O languages)

Going to gradschool in Portland, OR

So for those of you who don’t know, I am planning on going to grad school for Computer Programming Languages. I have been fully accepted to Portland State University in Portland, OR. Also I was concerned that they would make me take undergrad classes because I don’t have an Undergrad CS degree, but it doesn’t look like that will be a problem. I sent them a list of theoretical CS things I have knowledge of and I think they were impressed. The professor I am communicating with said “I believe you are exceptionally well prepared for our MS program.” Which I feel really good about.

I will be moving out to Portland, OR in mid to late August. But I will probably be going to KS for a couple weeks on the way, so I will probably be leaving NYC around the end of July. It’s so soon. I’m scared and excited.

Here is the theoretical computer science bragging document I sent them. It looks pretty impressive and it’s all true! ;-)

These are the buzz-words that I know and understand and that I
think would be applicable. I also have a more complete write up below.

* Turing machines
* The halting problem
* Gödel’s Incompleteness Theorem
* Bog-O Notation
* Lambda Calculus
* Church Numeral
* Type-level meta programming
* Kernel development
* System integration
* System programming
* Compilation, assembly and linking as separate steps
* Embedded systems programming (without an OS and with a minimal OS)
* Direct I/O handling
* Interrupt programming
* Object-oriented programming
* Pure and impure functional programming
* Functional-OO-Hybrid programming
* Logic programming
* Functional Logic programming
* JOIN-Calculus and Pi-calculus
* The Actor Model
* Software Transactional Memory

I have learned about Turing machines and the halting problem and
Gödel’s Incompleteness Theorem. I have also learned about Lambda
Calculus and Pi-Calculus (to gain a better understanding of languages
based on them). I understand and use the Big-O notation of algorithmic
complexity (and its limitations). I have also dealt with Church
Numerals for the purpose of encoding numbers in Lambda Calculus and in
the type systems of other languages (such as Scala) to allow for type
level metaprogramming.

I have been using Linux for more than 10 years now. Over that time I
have done everything from desktop usage to custom turnkey system
integration and kernel development. I have worked on most parts of an
OS from the kernel to application software. I have also worked on
systems with both no OS (PIC microcontrollers) and a very small OS (TI
calculators), so I have done direct I/O and interrupt programming
(including integration with standardized protocols like USB HID). Also
I have dealt with compilation, assembly and linking as separate steps.

I have learned the new languages on a regular basis not because I need
to program in the languages but because the new languages teach me
things about programming and programming languages in general. For
instance I learn about pure functional programming from Haskell and
about hybrid-OO-functional from Nemerle (and later Scala). Also I
understand monads as both collections, processes and pseudo-containers
like the IO monad (though not the category theory from which they
derive, I must admit). I also spent some time working with
JOIN-calculus (Jocaml) and the actor model (Erland and Scala).
Recently I have been reading about Software Transactional Memory and
how it can be integrated with Actors and how transactions can follow
messages from actor to actor. I have read a lot about JOIN-Calculus
and Pi-Calculus because I am very interested in natively parallel
programming abstractions. I think natively parallel abstractions of
computation will be very important in the future of massively
multi-core computers.

I forgot to mention Object-Oriented programming above because I have
been using it for so long (I first learn OO with C++ when I was around
14). I have also attempted to learn a few logic languages (Mercury and
Prolog and also Curry from PSU), but I admit I have had very little
luck. It has turned out to be the hardest kind of language for me to
grasp. I have a basic understanding of how the languages work and I
know what the syntax means and how variable binding works and all that
and how all these pieces should work together to allow arbitrary
programs. I also read an article Sergio Antoy, et al about
multi-threaded functional logic language implementations. It was very
interesting.

Initialization order in Java classes

I just found a Java “got’cha” (there certainly are plenty aren’t there?).

When a Java object is constructed the super class constructor is called first. So far this makes sense. But this also applies to initializations that are written at the point of declaration like:

Object obj = null;

This is different then leaving out the = null in that obj is nulled after the superclass constructor runs. This is usually not a problem, but I have a situation where some of the initialization occurs in a method called from the superclass constructor (this is a dubiously good design I know). The result is that if the initialization method called from the superclass sets obj that change will be overwritten with null in the subclass constructor.

It took me several hour to find this problem. I’m going to be much more careful with calls to virtual functions in the constructor. It is considered bad form for a reason. Also this is one of the few times I have started to understand why the functional programming fan boys bash on object oriented programming. The OO methodology is flawed in a number of ways. That being said I think there is a place for it. It models the real world of things that can interact in a very nice way. I think that the actor model may turn out to be better, but that will take time.

Ray casting in Scala

Ray casting is an old rendering technique used in early “3D” games like Wolfenstein 3D. Today it is nothing much, but implementing it will test your knowledge of trig and binary rounding issues. The real reason I wrote it though was because I have tried to implment a raycasting engine several times before and failed. Until now! So it was a matter of geek pride to go back to this problem and defeat it.

I implemented the engine in as functional a way as possible. I think it came out fairly well. I did not optimize anything for performance. So I used Double values for the most part. This is very different than most implementations you see online that implement the entire algorithm with ints and use look up tables for the trig functions. One issue that I had run into before is that because parts of the algorithm are fundamentally quantized (the map cells) floating point can actually cause problems like disappearing walls or holes in walls. I was able to work around these issues through the creative use of rounding and a fudge factor (to make sure the value was on the correct side of a boundry). Regardless it works now and I’m glad I defeated the algorithm.

The project is available in github:

• Main engine source
• Swing test app
• The whole project (incl. eclipse project files)

Inlining and optimization of methods in the JVM

I was just reminded of something that I often forget. So I thought I’d mention it here.

When the JVM (at least Sun’s HotSpot) optimizes a method it will only create one optimized version. So that if more than one type of object is passed to the function it will prevent inlineing and other optimization. This means you have to be conscious of what you allow to be passed into methods that should be optimized since the compiler will optimize for the lowerest common denominator of all input values.

This is standard for JITs. However as a side note, there are JITs that do produce multiple optimized versions for functions that are used in more than one context. One example is Psyco. Work on Psyco has stopped and new development is going into PyPy which is a fascinating (and kind of deranged) project.

Metawidget BeanUtils auto-update binding

I have been using Metawidget (which is a really cool library by the way) on a project lately. I wanted to avoid the need for a save button by having changes automatically propagated to the beans when changes are made to the widgets. However I am using BeanUtils (from apache) which does not support binding internally.

I did try BeanBinding but it was really slow (I don’t know why and I didn’t have time to debug it). So I created an extension to the BeanUtilsBinding class (from Metawidget) that adds auto-save support. It’s a really ugly hackish implementation but it works reliably (though I think there may be corner cases where the save does not trigger when it should). It is also quite fast. It doesn’t run the save until all the messages currently in the swing queue are processed (using SwingUtilities.invokeLater) and then it only runs it once so even if a lot of changes happen at the same time only one save will be done.

The implementation is below. Feel free to use it. It is copyright Arthur Peters under the GNU GPL v3.

import java.awt.Component;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.awt.event.FocusEvent;
import java.awt.event.FocusListener;
import java.awt.event.KeyEvent;
import java.awt.event.KeyListener;
import java.awt.event.MouseEvent;
import java.awt.event.MouseListener;
import java.lang.reflect.Method;
import java.util.ArrayList;
import java.util.EventListener;
import java.util.List;
import java.util.Map;
import java.util.logging.Level;
import java.util.logging.Logger;

import javax.swing.SwingUtilities;
import javax.swing.event.ChangeEvent;
import javax.swing.event.ChangeListener;

import org.metawidget.swing.SwingMetawidget;
import org.metawidget.swing.propertybinding.beanutils.BeanUtilsBinding;

public class BeanUtilsAutoUpdateBinding extends BeanUtilsBinding {
	@SuppressWarnings("unused")
	private static final Logger log = Logger
			.getLogger("BeanUtilsAutoUpdateBinding");

	protected static final class ListenToRecord {
		private final Component component;
		private final String propertyName;

		public ListenToRecord(Component component, String propertyName) {
			this.component = component;
			this.propertyName = propertyName;
		}

		public Component getComponent() {
			return component;
		}

		public String getPropertyName() {
			return propertyName;
		}
	}

	private List listeningTo = new ArrayList();

	private ChangeListener changeListener = new ChangeListener() {
		@Override
		public void stateChanged(ChangeEvent e) {
			doSave();
		}
	};

	private ActionListener actionListener = new ActionListener() {
		@Override
		public void actionPerformed(ActionEvent e) {
			doSave();
		}
	};
	/*private DocumentListener documentListener = new DocumentListener() {
		@Override
		public void changedUpdate(DocumentEvent e) {
			doSave();
		}

		@Override
		public void insertUpdate(DocumentEvent e) {
			doSave();
		}

		@Override
		public void removeUpdate(DocumentEvent e) {
			doSave();
		}
	};
	*/
	private KeyListener keyListener = new KeyListener() {
		@Override
		public void keyPressed(KeyEvent e) {
			doSave();
		}

		@Override
		public void keyReleased(KeyEvent e) {
			doSave();
		}

		@Override
		public void keyTyped(KeyEvent e) {
			doSave();
		}

	};
	private MouseListener mouseListener = new MouseListener() {
		@Override
		public void mouseClicked(MouseEvent e) {
			doSave();
		}

		@Override
		public void mouseEntered(MouseEvent e) {
			// Ignore
		}

		@Override
		public void mouseExited(MouseEvent e) {
			// Ignore
		}

		@Override
		public void mousePressed(MouseEvent e) {
			// Ignore
		}

		@Override
		public void mouseReleased(MouseEvent e) {
			doSave();
		}
	};
	private FocusListener focusListener = new FocusListener() {
		@Override
		public void focusGained(FocusEvent e) {
			// Ignore
		}

		@Override
		public void focusLost(FocusEvent e) {
			doSave();
		}
	};

	private boolean saveAlreadyInEventQueue;

	public BeanUtilsAutoUpdateBinding(SwingMetawidget metawidget) {
		super(metawidget);
	}

	@Override
	public void bindProperty(Component component,
			Map attributes, String path) {
		super.bindProperty(component, attributes, path);

		String valueProperty = getMetawidget().getValueProperty(component);
		// component.addPropertyChangeListener(valueProperty, this);
		attemptToCall(component, "addChangeListener", ChangeListener.class,
				changeListener);
		attemptToCall(component, "addActionListener", ActionListener.class,
				actionListener);
		// attemptToCall(component, "addDocumentListener",
		// DocumentListener.class, documentListener);
		component.addKeyListener(keyListener);
		component.addMouseListener(mouseListener);
		component.addFocusListener(focusListener);
		listeningTo.add(new ListenToRecord(component, valueProperty));
	}

	private void attemptToCall(Component component, String methodName,
			Class eventListenerCls,
			EventListener eventListener) {

		try {
			Class cls = component.getClass();
			Method method = null;
			while (method == null && cls != Object.class) {
				try {
					method = cls.getMethod(methodName, eventListenerCls);
				} catch (NoSuchMethodException e) {
					// Ignore
				}
				cls = cls.getSuperclass();
			}
			method.invoke(component, eventListener);
		} catch (Exception e) {
			// Ignore it and return. This function is an attempt.
			log.log(Level.FINE, "Failed to call " + methodName + " on "
					+ component, e);
		}
	}

	@Override
	public void unbindProperties() {
		super.unbindProperties();

		for (ListenToRecord listenToRecord : listeningTo) {
			Component component = listenToRecord.getComponent();
			// component.removePropertyChangeListener(listenToRecord.getPropertyName(),
			// this);
			component.removeKeyListener(keyListener);
			component.removeMouseListener(mouseListener);
			attemptToCall(component, "removeChangeListener",
					ChangeListener.class, changeListener);
			attemptToCall(component, "removeActionListener",
					ActionListener.class, actionListener);
			// attemptToCall(component, "removeDocumentListener",
			// DocumentListener.class, documentListener);
		}
		listeningTo.clear();
	}

	protected void doSave() {
		synchronized (this) {
			if (!saveAlreadyInEventQueue) {
				saveAlreadyInEventQueue = true;
				SwingUtilities.invokeLater(new Runnable() {
					@Override
					public void run() {
						getMetawidget().save();
						synchronized (BeanUtilsAutoUpdateBinding.this) {
							saveAlreadyInEventQueue = false;
						}
					}
				});
			}
		}
	}
}

Java for Google App Engine

When Google App Engine first came out I was really surprised it didn’t support Java, because Google was (and is) really pushing GWT, so to have them release a web deployment platform that did not support their own favorite framework was odd. However they have now released a preview version of Google App Engine running Java. It doesn’t do everything I might want, for instance Lift doesn’t run on it out of the box and it doesn’t allow you to spawn your own threads (these problems are directly related). There is some work going on to make Lift work on it though (see the email thread).

Overall though I’m really excited. I have been looking for a platform that will allow me to run Java based web apps for a reasonable price and I think this is the first one that provides something that I may actually use. For a low traffic site it is free and it looks to me that the prices are pretty good even as the traffic increases.

Installing and upgrading plugins in Eclipse

I have had problems with “No repository found at” errors while trying to install or update eclipse plugins. Other people have had similar problems (on the andriod forums for instance).

I found that the solution was to open eclipse on a fresh workspace (just specify an empty directory for the workspace it will create the stuff it needs). Once the install/upgrade is done I can just switch back to my normal workspace and everything is as it should be. The upgrades and installs are installation-wide so the workspace change does not effect them. For some reason the stuff in my workspace was causing problems. It doesn’t make much sense really.

Installing Subversive on Eclipse

I ran into a problem with installing Subversive (An eclipse plugin that interfaces to Subversion). The issue is that the plugin comes in 2 pieces that are both required: the Subversive plug-in and the Subversive SVN Connectors plug-in. This was not obvious to me and I ran into this problem not once but twice.

The solution is to add these 2 update sites (current as of Apr 2nd, 2009):

• http://www.polarion.org/projects/subversive/download/eclipse/2.0/update-site/
• http://download.eclipse.org/technology/subversive/0.7/update-site/

And install the following features from them:

• Subversive SVN Team Provider (from the http://download.eclipse.org/technology/subversive/0.7/update-site/ site)
• Subversive SVN Connectors (from the http://www.polarion.org/projects/subversive/download/eclipse/2.0/update-site/ site)
• SVNKit 1.2.2 Implementation (from the http://www.polarion.org/projects/subversive/download/eclipse/2.0/update-site/ site)

The error message in the eclipse logs was as follows when I failed to add the site for and install the “Subversive SVN Team Provider”. I hope this will help people find this and not have the same problems I did.

!ENTRY org.eclipse.equinox.p2.ui 4 10005 2009-04-06 15:30:28.470
!MESSAGE Cannot complete the request.  See the details.
!SUBENTRY 1 org.eclipse.equinox.p2.ui 4 10005 2009-04-06 15:30:28.470
!MESSAGE Cannot complete the request.  See the details.
!SUBENTRY 1 org.eclipse.equinox.p2.director 4 0 2009-04-06 15:30:28.470
!MESSAGE Unsatisfied dependency: [org.polarion.eclipse.team.svn.connector.feature.group 2.1.0.I20090213-1500] requiredCapability: org.eclipse.equinox.p2.iu/org.eclipse.team.svn.feature.group/[0.7.2.I20080801
-1500,1.0.0)
!SUBENTRY 1 org.eclipse.equinox.p2.director 4 0 2009-04-06 15:30:28.470
!MESSAGE Unsatisfied dependency: [org.polarion.eclipse.team.svn.connector.svnkit15.feature.group 2.1.0.I20090213-1500] requiredCapability: org.eclipse.equinox.p2.iu/org.eclipse.team.svn.feature.group/[0.7.2.I20080801-1500,1.0.0)
!SUBENTRY 1 org.eclipse.equinox.p2.director 4 0 2009-04-06 15:30:28.470
!MESSAGE Unsatisfied dependency: [org.polarion.eclipse.team.svn.connector.svnkit15 2.1.0.I20090213-1500] requiredCapability: osgi.bundle/org.eclipse.team.svn.core/0.0.0
!SUBENTRY 1 org.eclipse.equinox.p2.director 4 0 2009-04-06 15:30:28.470
!MESSAGE Unsatisfied dependency: [org.polarion.eclipse.team.svn.connector.svnkit15 2.1.0.I20090213-1500] requiredCapability: osgi.bundle/org.eclipse.team.svn.core/0.0.0
!SUBENTRY 1 org.eclipse.equinox.p2.director 4 0 2009-04-06 15:30:28.471
!MESSAGE Unsatisfied dependency: [org.polarion.eclipse.team.svn.connector.feature.group 2.1.0.I20090213-1500] requiredCapability: org.eclipse.equinox.p2.iu/org.eclipse.team.svn.feature.group/[0.7.2.I20080801-1500,1.0.0)
!SUBENTRY 1 org.eclipse.equinox.p2.director 4 0 2009-04-06 15:30:28.471
!MESSAGE Unsatisfied dependency: [org.polarion.eclipse.team.svn.connector.svnkit15.feature.group 2.1.0.I20090213-1500] requiredCapability: org.eclipse.equinox.p2.iu/org.eclipse.team.svn.feature.group/[0.7.2.I20080801-1500,1.0.0)
!SUBENTRY 1 org.eclipse.equinox.p2.director 4 0 2009-04-06 15:30:28.471
!MESSAGE Unsatisfied dependency: [org.polarion.eclipse.team.svn.connector.svnkit15.feature.group 2.1.0.I20090213-1500] requiredCapability: org.eclipse.equinox.p2.iu/org.polarion.eclipse.team.svn.connector.feature.group/0.0.0
!SUBENTRY 1 org.eclipse.equinox.p2.director 4 0 2009-04-06 15:30:28.471
!MESSAGE Unsatisfied dependency: [org.polarion.eclipse.team.svn.connector.svnkit15.feature.group 2.1.0.I20090213-1500] requiredCapability: org.eclipse.equinox.p2.iu/org.polarion.eclipse.team.svn.connector.svnkit15/[2.1.0.I20090213-1500,2.1.0.I20090213-1500]