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.

I now have the maximum possible number of assurance points for CACert, 150. This means two things. One is that I can now get SSL and email certificates that last two years, and the other is that I can now allocate points to others.

So if anyone who happens to be in the same place as me (generally Dunedin, but right now various bits of Australia) wants some, they should get in touch.

A nice side effect is that there is now enough people in Dunedin to get another person up to the required 100 points so they can then allocate them, so the region can now bootstrap itself fairly easily.

Someone at paypal doesn’t get phishing, and is sending out emails that look like they really could be scams. Not only that, but the email shouldn’t even be sent, according to the paypal preferences.

read more | digg story

Found on Digg:
“Once enough votes have been collected, the genetic algorithm gets to work. It picks the good images and breeds them using either mutation or crossing-over. Since the images’ genes are just trees, it is simple to cross-over two of them and produce new ones.”

It’s a nice idea, similar-but-different to what I’m planning on trying to implement one day. I’m skeptical about how well it’ll work when faced with multiple people having disparate ideas of what looks good, along with people trying to game the system a bit. But for something fun, it’s interesting. They’ve also implemented it, which is something I haven’t gotten around to yet
the site (more description) | digg story

A few years ago, I learnt LISP at university. Just for a semester, write a poetry generator, things like that. All pretty simple. I didn’t get into it much at the time, beyond what I had to, but I do remember thinking that it looked like quite a powerful and fun language.

A while ago, someone on Slashdot mentioned LISP and referred to a book that was online for learning it. So I checked it out, and it seems to be pretty good. I’m about half way through it. It has the large amount of basic instruction in the language, which is always necessary. However, after a while of that, it has a chapter on ‘Practical’ stuff, which involves implementing actual code, which is a good change, and a nice place to read chunks of code, put them into the interpreter, and play with them a bit.

Normally when reading books on programming languages, I get frustrated when they start explaining “This is a variable. You can store values in them. You can also change them. …”, as it’s a concept I’ve seen over and over, and so is quite boring. This isn’t the case here, I don’t know if it’s because LISP is different enough from the languages I usually use that it seems new, or the book just manages to avoid these kinds of problems.

If I see it lying around (or maybe even if I don’t, and I just get paid enough one day), I think I might pick up a dead tree copy.

Oh, and the book itself? Practical Common Lisp.

A little project I’m working on at the moment: creating a neural network that will (maybe) learn the aesthetic tastes of a person.

There are two parts to this, the first creates tree-like shapes (what Richard Dawkins calls biomorphs in his book The Blind Watchmaker). Here is an online demo of these biomorphs. My version is going to allow for significantly more complex biomorphs.

When interacting with the program, the user selects the biomorphs that they like, and that is used as the progenitor of the next batch. Mutation is then applied to these, and the set of modified versions is presented to the user to select the next ‘best’ one.

The other part of this program is the neural network. It will be trained on the user’s input and selections, and after a while it will be allowed to run on its own, selecting what it thinks is the best based on its training. After running for a while (several dozen generations or so), the results will be displayed.

The point of this (aside from the fun of implementing it) is to see how well the neural network can pick up the ’styles’ that the user was going for, and thus to see if it can end up knowing what people like.

Here are the current details on the design of this. These designs are getting updated over time. Comments/suggestions/whatever are welcome.