Blog Without An Important Name

Here’s something a bit more computer-sciencey than usual. For something at work, I have had to implement a function parser, so you can type ‘1+2*b‘ and it’ll work it all out, with correct operator precedence and so forth. To do this, I use a three-step process:

1. Tokenise the input, and at the same time convert any variables found to their numeric values
2. Convert the input tokens to RPN using the Shunting Yard algorithm
3. Evaluate the RPN form of the equation using an RPN parser, which is really easy to write

This did the job nicely, however the time came when it had to be extended, and able to accept functions, such as ‘max(1,2,3)‘. The standard shunting yard algorithm can handle functions, but with the restriction that the number of arguments to them is known (really, this is a limitation of the RPN algorithm, but it’s at this point in the process that we need to deal with the problem). In this case, I wanted to handle functions with a variable number of arguments, so ‘max(1,2)‘ would work, and so would ‘max(1,2,3,4,5)‘. To do this, I extended the standard algorithm. Below is the algorithm from Wikipedia. My additions are in bold. This requires two more stacks, a ‘were values‘ stack, and an ‘arg count‘ stack. It also requires that you can attach the number of arguments to an instance of a function. In my case, I did it with a small class that took the function and an argument count, with one of these created during tokenisation for each function encountered.

• While there are tokens to be read:

• Read a token.
• If the token is a number, then add it to the output queue. If the were values stack has a value on it, pop it and push true.
• If the token is a function token, then push it onto the stack. Push 0 onto the arg count stack. If the were values stack has a value on it, pop it and push true. Push false onto were values.
• If the token is a function argument separator (e.g., a comma):

• Until the topmost element of the stack is a left parenthesis, pop the element onto the output queue. If no left parentheses are encountered, either the separator was misplaced or parentheses were mismatched. Pop were values into w. If w is true, pop arg count into a, increment a and push back into arg count. Push false into were values.

• If the token is an operator, o₁, then:

• while there is an operator, o₂, at the top of the stack, and either

o₁ is associative or left-associative and its precedence is less than (lower precedence) or equal to that of o₂, or

o₁ is right-associative and its precedence is less than (lower precedence) that of o₂,

pop o₂ off the stack, onto the output queue;

• push o₁ onto the operator stack.

• If the token is a left parenthesis, then push it onto the stack.
• If the token is a right parenthesis:

• Until the token at the top of the stack is a left parenthesis, pop operators off the stack onto the output queue.
• Pop the left parenthesis from the stack, but not onto the output queue.
• If the token at the top of the stack is a function token
  • Pop stack into f
  • Pop arg count into a
  • Pop were values into w
  • If w is true, increment a
  • Set the argument count of f to a
  • Push f onto output queue
• If the stack runs out without finding a left parenthesis, then there are mismatched parentheses.

• When there are no more tokens to read:

• While there are still operator tokens in the stack:

• If the operator token on the top of the stack is a parenthesis, then there are mismatched parenthesis.
• Pop the operator onto the output queue.

• Exit.

Note that because I didn’t feel like correctly listifying most of it, consider an if to apply to the end of that sentence only. Operation order is usually important.

With this done, the part of the RPN algorithm that says:

It is known that the function takes n arguments.

can now be satisfied.

This is a pretty small one, mostly just to fix a problem some people were having.

Changelog:

• Truncate the pathname to save files to if it gets too long on windows (which has stupidly low limits) Some classical albums have really long names, and there were some that couldn’t be downloaded as a result. This hopefully fixes the problem, although I haven’t tested it yet.
• Added option to allow the user to specify that they don’t want cover art to be downloaded. This is done by adding the line ‘downloadCoverArt=false’ to ~/.emusicj/emusicj.prop. Someone wanted this, I can’t remember why, but it was easy enough to do.
• Updated build.xml to allow more flexible compiles, such as not always creating a dist build Apparently some people are making distro packages of eMusic/J, and this makes life easier for them. Related to this, I’ve started posting the source code of each release on the site, too.

It can be downloaded here.

Yesterday I got back from a bit of a holiday in Auckland. The purpose of the trip was to go to Kiwi Foo Camp (a.k.a. Baa Camp). It is a gathering of 150 people with creative interests in various, generally technology related, things. It’s aim is to be a way for all these people to get together in a way the breaks down normal barriers of hierarchy so that they can share ideas, plots, and schemes without these getting in the way.

I met a bunch of people that I’ve heard about or only ever talked to via email, such as Don Christie and Peter Gutmann, along with a host of people I probably would have never heard of if they weren’t there but who are also doing interesting work in a variety of fields. A nice effect, which is by design, of the 150 people cap is that you have the ability to meet nearly everyone there. It also means they can put on free beer and wine for the entire event.

Almost everyone was sleeping on the school grounds where it was hosted, or nearby, which meant that things like game playing (Werewolf is a favourite) carried on to 4am, and people were happily getting up at 8am for breakfast in the morning. I was supposed to be sleeping in the Wharenui at the school, however due to getting to bed a little late and an apparent overbooking of it meant that I ended up sleeping outside on the deck of it the first evening. From what I could tell, I got the better deal. It wasn’t hot and stuffy, and the one person out there with me didn’t snore too much. The following night was inside one of the school rooms, which was helpful because it kept the mosquitoes somewhere where I wasn’t, although I think by then they’d decided I was bled dry anyway.

As is common with conferences, and even moreso with this one being an ‘unconference’, much of the value isn’t so much from the sessions, but from chatting to people you happen to sit beside because there’s a spare seat, whether they do programming, community projects, are politicians (I talked with Judith Tizard extremely briefly), or whatever. They all seem to be doing good stuff. I did, however, do a session of my own. I was planning on doing one on neural networks and genetic algorithms, and another on Amazon web services but due to time constraints (some uncharitable folk may call it laziness) beforehand, I only had time to prepare the GA stuff. That worked out OK, as it managed to take up the whole hour anyway. I didn’t get a big turnout, but I didn’t expect one – this was a fair bit more on the computer science side than most of the things there.

The photos I took are here, many more can be found on flickr.

The rest of the time in Auckland was catching up with friends there, and spending way too much money at JB Hi-Fi on music and a little bit of anime.