Monday 25 February 2008

More adventures in the land of free operating systems

I didn't get much programming done this weekend because I spent most of my time screwing around with my Linux installation, much of which was just fixing things I'd managed to break somehow. My two goals were to switch to KDE and get some sort of remote desktop solution configured so that I could program on my laptop's Linux environment via my Windows desktop. I'm pleased announce success on both counts! It appears that virtually everything is customizable when running Linux and the desktop environment is no exception. As far as I can tell, the two most popular are GNOME and KDE. Ubuntu comes with GNOME but I wanted to try KDE because I had heard that it was more windowsy and shiny. It turns out there is something called Kubuntu which is Ubuntu with KDE instead of GNOME and so installing the kubuntu-desktop package did the trick. Surprisingly, you can actually have both installed simultaneously and choose which one you want when logging in! So far I prefer KDE's style and plan to stick with it for the time being. The two products differ on many levels beyond the aesthetic but I'm too much of a noob to appreciate most of them. One of the significant aspects of the desktop environments is the extra software they come with such as email client, news client, contacts management, etc. The thing is, I really don't care about this stuff because I use this thing called a "web browser". This magical device is slowly but surely making desktop applications irrelevant. Annoyingly, all these extra apps are somehow dependencies of the kubuntu-desktop and so they will be staying installed for now. I am sure there is some way to get rid of them without blowing the whole thing up but it will no doubt involve editing obscure configuration files and executing cryptic commands. Hang on, if I don't like that stuff, why the hell did I install Linux again?? I was asking myself this very question today when I was summarily dumped into a command line after installing the kubuntu-desktop and then rebooting. So I rebooted again and was greeted by the command line again. Wait a minute, I was supposed to have TWO desktop environments, not zero! Various googling and typing of commands happened and somehow it got fixed - I forget the details. So anyway, the other thing I managed to do this weekend was use some software called freeNX to get a remote desktop solution up and running. I had to research for quite a while before I found a guide that was appropriate for my setup and not horribly out of date. Following the guide carefully, it all went very smoothly. I am happy to report that the Windows NX client operates very similarly to good 'ole mstsc.exe in terms of performance. Now I can do all my ruby/rails/android/etc development in Linux and do so from either machine. All this tinkering is time consuming but not without value. I am learning alot and that is the primary goal, after all.

Sunday 24 February 2008

Status update: compilers and ruby on rails

So you probably noticed I haven't been posting much about the parsing stuff lately and thats because I stopped working on it. I got to the point where wikipedia + lecture notes isn't quite cutting it and I've been unable to find a resource that tackles the subject matter in a way I am comfortable with. A good textbook could make a big difference and there are a few out there that look promising but my heart is not in it at the moment. I'm somewhat torn in between wanting to finish the projects I start and making sure that I am enjoying the projects. However the simple fact is that this plan of less video games and more programming/reading/learning is only sustainable if I am really enjoying the work. My intention is to come back to the compilers stuff in a few months and spend time looking at some of the programs out there that make compiler/interpreter development easier. Previously I avoided this because I wanted to learn the fundamentals and I found this to be worthwhile. It was never my intention to implement an actual compiler or interpreter completely from scratch, although I had hoped to get somewhat further than I did. In any case, the topic that holds my interest at the moment is that of a web development framework called Ruby on Rails. Rails interests me for a number of reasons but I think the primary driver is frustration with ASP.NET at work. I have read about the model-view-controller pattern but never actually worked with it first hand so I am curious about how it compares to developing with web forms. Rather than downloading and configuring Rails locally I am making use of Heroku - they provide free Rails hosting with an integrated development environment. I'm sure you will hear how I'm finding it soon enough.

Monday 18 February 2008

I installed Ubuntu on my laptop

If you read the first two posts on this blog you might notice a discrepancy. In the first post I identified that I only know how to use Windows. But if you take a look at the second post, I did not propose a remedy. I'll be honest - its because I really did not want to learn Linux. I am unable to give a good reason for this so how about a bad one: fear of change. The thing is, this entire project is about moving outside of my comfort zone and learning Linux is no different so I bit the bullet on Friday night and burned the iso for Ubuntu 7.10. (Random aside - it was a cd iso but I tried burning it onto a dvd, and surprisingly it worked! I was expecting a coaster.) I was immediately impressed. I had no idea that you could boot and run some Linux distributions directly from the disc (perhaps some of you are rolling your eyes at my ignorance? If so, get used to it - there is plenty more where that came from!). The ability to preview an operating system without installing it certainly has some merits. I was able to establish that my wireless would work fine and investigate the options the installer gave me all without making a commitment. I played around for an hour or so and then proceeded with the installation. I had the option to do a "guided" install which would resize some of my partitions but it failed to inspire much confidence so instead I did some reading and set the partitions up manually. Configuring dual boot required zero intervention on my part as it was all automatic and best of all it worked first go. As a basic user, I would say that the two most confusing things about Linux are user permissions and the file system. If I want to copy things to certain directories it seems I have to use a command line and execute the command as the root user. But what if I want to use the nice explorer-style gui for doing this stuff? Figuring out which directories to actually put stuff in is also difficult as there is no obvious program files location. There are definitely things to like as well. For example, I like being able to install applications via a single command such as "sudo apt-get install sun-java6-jdk" ( now I finally understand this xkcd, yay!). Its quite convenient! The small memory and disk space footprint is obviously great. I only set aside 15gb for the Linux partition and it looks it will be more than enough. There are some random quirks that I sort of expected when using a laptop without all the custom driver stuff. Last night I discovered that my brightness-up key doesn't work but the brightness-down key does - I ended up having to reboot the darn thing because my random mashing had made the screen so dark. I've done a bit of googling and it looks like there are pages out there with specific instructions for running Ubuntu on an A8Js so I expect with time I'll be able to iron out most of the quirks. In summary this experience has been remarkably positive. Its great how easy it is to get a taste of the "other side" without making a commitment. If you are at all curious why not just burn an iso and pop it in your drive? I should have done this sooner!

Thursday 14 February 2008

Fixing the grammar

The test that was failing was this one:

  def test_left_compound # "((500*20)+16)"
  tokens = [LeftParenToken.new(), LeftParenToken.new(), IntegerToken.new(500), MultiplicationToken.new(), IntegerToken.new(20), RightParenToken.new(), AdditionToken.new(), IntegerToken.new(16), RightParenToken.new()]
  assert(tokens_are_valid(tokens))
end
Why? Well, do what I did - try to build the expression ((500*20)+16) by hand using the rules. Here they are again:
E => (E) | nT T => +E | -E | * E | /E | ε
Give up yet? It can't be done! Also, for the same reason, this grammar cannot generate (1)+2. The simple fact is that I botched the job of making the grammar LL(1) compatible. So how to fix it? Well its simple really, especially when you take the (1)+2 example. Seems to me that a slight tweak to the production rules for E is necessary:
E => (E)T | nT
Great! Lets modify the lookup table accordingly:
lookup[:E][LeftParenToken] = [:lpar, :E, :rpar, :T]
The tests all pass! Now I can turn my attention to using the same algorithm for building the tree. However I have some more reading to do before I can proceed. Come on CS164 lectures notes, don't let me down!

Monday 11 February 2008

Syntax checking with a LL(1) parser

After reading about some different types of parsers, I decided to have a go at LL(1). This means the parser works Left-to-right, generates the Leftmost derivation and looks one token ahead. The basic idea of LL(1) is to build a stack of symbols that represent the derived expression by using a lookup table that tells you what rule to apply based on the current symbol and current token. Not all context free grammars can be parsed using LL(1) but I think the calculator's grammar can, with some modification. Lets break the work into some smaller steps:

  1. Modify the grammar I described last week to support LL(1) parsing.
  2. Modify the tokens_are_valid method to use LL(1) to verify whether the token stream is well formed. Given that I already have tests for tokens_are_valid, I will know that I am already on the right track once the existing tests are passing with the new implementation.
  3. Add syntax tests for parentheses. Watch them fail.
  4. Modify the tokens_are_valid implementation to make the new tests pass. Once this is happening we are done with using LL(1) for syntax verification and can move on to using LL(1) to actually do the parsing.
  5. Modify the build_tree method to use LL(1) and watch the operator precedence tests fail because my grammar doesn't deal with the precedence issue.
  6. Fix the grammar to support operator precedence, make the corresponding changes to the lookup table and watch the tests pass.
  7. Add evaluation tests for parentheses . I think these babies should automatically work if I've done the other steps right.
In this post I will tackle steps 1,2 and 3. Here is the grammar I described last week:
E => n | E+E | E-E | E*E | E/E | (E)
As it stands, this grammar will not work with LL(1) because to figure out which rule to apply, I have to look at least 2 tokens ahead. For example, starting with E and given two different inputs "1" and "1+1", its obvious that I need to use a different rule for each input, but both of them start with the token "1". This problem can be fixed by modifying the grammar. Here goes:
E => (E) | nT T => +E | -E | * E | /E | ε
The symbol 'ε' seems to represent null or empty. Basically it means that the symbol T can just disappear without producing anything. Resuming the above example, now there is only one rule to apply: E => nT. In the "1" case, the T disappears. In the "1+1" case the T is expanded to +E. Here is the lookup table for this grammar:
n + - * / ( ) $
E nT (E)
T +E -E *E /E ε ε
The '$' represents the end of the input string. The gaps in the table represent syntax errors. Writing the code There are a few issues that need addressing when it comes to implementation. The most obvious one is that I need some way to represent the symbols in the above table. Well it turns out Ruby has a symbol class, though it was not designed to represent grammar symbols - Ruby symbols are just named constants that have no intrinsic value(as far as I can tell). They use the :symbol_name syntax, so for example E and T are now represented as :E and :T. I amended the existing token classes to expose their corresponding symbol:
class AdditionToken < OperatorToken
def symbol
  return :plus
end
end
I need a way to determine if a symbol is terminal or not, and there is a rather nice way to do this - simply defining an extra method on the Symbol class:
class Symbol
def non_terminal?
  return (self == :T || self == :E)
end
end
Just to be clear, Symbol is not my class, I'm just adding an extra method to an existing class. Executing :T.non_terminal? will return true. Next on the agenda is the end token. We don't strictly need an end token but it does make the algorithm simpler.
class EndToken
def symbol
  return :end
end
end
The lookup table can be done as 2 dimensional hash:
def create_lookup_table()
lookup = {}
lookup[:E] = {}
lookup[:E][IntegerToken] = [:int,:T]
lookup[:E][LeftParenToken] = [:lpar, :E, :rpar]
lookup[:T] = {}
lookup[:T][AdditionToken] = [:plus, :E]
lookup[:T][SubtractionToken] = [:minus, :E]
lookup[:T][MultiplicationToken] = [:multiply,:E]
lookup[:T][DivisionToken] = [:divide, :E]
lookup[:T][RightParenToken] = []
lookup[:T][EndToken] = []
return lookup
end
As you can see, the table is first indexed with the non-terminal (:E or :T) and then with a token type. The result is an array of symbols, which may be empty. If an attempt to lookup an undefined entry is made then nil is returned and this is interpreted as a syntax error. Right, with that out of the way, I can begin work on tokens_are_valid. The goal is to replace the old implementation with an LL(1) algorithm and hopefully all the existing tests will pass:
def tokens_are_valid(tokens)
tokens = tokens.dup
symbols = [:E]
lookup = create_lookup_table()

# The symbol and token arrays can be used as stacks if the contents is first reversed.
# An end token/symbol is appended to each before they are reversed.
tokens.push(EndToken.new())
tokens.reverse!
symbols.push(:end)
symbols.reverse!

while(tokens.size > 0)
  current_symbol = symbols.pop() #The current symbol will always be consumed. Safe to pop.
  current_token = tokens.last    #The current token won't necessarily be consumed, cannot pop it yet.
  if(current_symbol.non_terminal?)
    result = lookup[current_symbol][current_token.class]
    return false if result.nil?   
      symbols.push(result.reverse)
      symbols.flatten!     
  else
    return false if current_symbol != current_token.symbol
    tokens.pop()
  end             
end

return true
end
Hopefully this is relatively self-explanatory. The bit that may need some explanation is in bold. See, I am using arrays as stacks but to do so I need to reverse the contents - I do this once at the beginning for the tokens and the symbols. However its also necessary to reverse the result of the table lookup for the same reason. Yes, I could have coded the table with the symbols backwards but that is more confusing. Easiest just to push a reversed copy of the result onto the symbol stack. The only problem with doing this is that you end up with an array inside an array, which is why I call the flatten! method. In case you were wondering, Ruby has a convention to use the exclamation mark for methods that modify the instance you called the method on, rather than just returning a modified object. The following should demonstrate:
irb(main):001:0> x = [1,2,3]
=> [1, 2, 3]
irb(main):002:0> y = x.reverse
=> [3, 2, 1]
irb(main):003:0> x
=> [1, 2, 3]
irb(main):004:0> x.reverse!
=> [3, 2, 1]
irb(main):005:0> x
=> [3, 2, 1]
Well, my proposed change to tokens_are_valid works fine - all my tests are still passing! The next step is to write some tests that include parentheses. Here are a few (no need to bore you with the full set):
class ParenthesesSyntaxTests < Test::Unit::TestCase
def test_surround_one_number # "(1)"
  tokens = [LeftParenToken.new(),IntegerToken.new(1), RightParenToken.new()]
  assert(tokens_are_valid(tokens))
end   

def test_surround_operation # "(1+2)"
  tokens = [LeftParenToken.new(),IntegerToken.new(1), AdditionToken.new(), IntegerToken.new(2), RightParenToken.new()]
  assert(tokens_are_valid(tokens))
end

def test_left_compound # "((500*20)+16)"
  tokens = [LeftParenToken.new(), LeftParenToken.new(), IntegerToken.new(500), MultiplicationToken.new(), IntegerToken.new(20), RightParenToken.new(), AdditionToken.new(), IntegerToken.new(16), RightParenToken.new()]
  assert(tokens_are_valid(tokens))
end

def test_right_compound # "(16+(500*20))"
  tokens = [LeftParenToken.new(), IntegerToken.new(16), AdditionToken.new(), LeftParenToken.new(), IntegerToken.new(500), MultiplicationToken.new(), IntegerToken.new(20), RightParenToken.new() , RightParenToken.new()]
  assert(tokens_are_valid(tokens))
end

def test_empty_parens_error # "()"
  tokens = [LeftParenToken.new(), RightParenToken.new()]
  assert(!tokens_are_valid(tokens))
end

def test_wrong_order_error # ")2("
  tokens = [RightParenToken.new(), IntegerToken.new(1), LeftParenToken.new()]
  assert(!tokens_are_valid(tokens))
end

def test_no_operator_adjacent_to_paren_error # "1+2(3+4)"
  tokens = [IntegerToken.new(1), AdditionToken.new(), IntegerToken.new(2), LeftParenToken.new(), IntegerToken.new(3), AdditionToken.new(), IntegerToken.new(4), RightParenToken.new()]
  assert(!tokens_are_valid(tokens))
end

end
All but one pass! Can you guess which one? It turns out this is a problem with my grammar, not the implementation. Next post I will discuss the failing test and what I have to do to fix it.

Saturday 9 February 2008

More on context free grammars

I started writing a post on the work I've done this week but soon realised that it would be useful to explain grammars a bit more before continuing. After all, it is possible that some of you went to the Wikipedia page for context-free grammars and were (like me) unable to curb the involuntary reflex to close the tab as soon as that stack of ugly math symbols came into view. Anyway, lets get to it. To make a grammar you need the following:

  1. One or more terminal symbols.
  2. One or more non-terminal symbols.
  3. A start symbol (must be non-terminal).
  4. Production rules that relate a non-terminal symbol to a set of symbols.
Terminal symbols are the output of the grammar and are usually written in lower case. Non-terminal symbols are temporary - they cannot appear in a generated string and are designed solely for consumption via production rules. They are usually written using upper case. Ok, so lets define a grammar: Terminal(s): a, b Non-terminal(s): S Start symbol: S The only thing left is the production rule(s):
S => aS | b
This rule says that the non-terminal S can be replaced with either aS or b. Given this fact, it should be apparent that this grammar produces strings that consist of zero or more a's and end with a b. Just to be clear, let me show you the 4 smallest strings that it can produce:
b ab aab aaab
And now some strings that this grammar cannot produce:
a ba baab abaab
So now that we have that clear, the question is how would you write a program that would return true for the top 4 and false for the bottom 4. Ok thats not the question - its trivial. But given an arbitrary set of production rules... now thats much more tricky. In my previous post I proposed a grammar for my calculator and discussed some valid and invalid strings. From what I've read so far, it looks like that getting an implementation that will return true for the valid strings and false for the invalid ones will actually take me 90% of the way to having an implementation for building a parse tree based on the grammar.

Monday 4 February 2008

Parentheses in the calculator: a first look at context-free grammars

This series on writing a program that can evaluate simple arithmetic expressions is all about baby steps. I have no idea what I'm doing in terms of the problem space and I'm similarly ignorant of my tool, Ruby. But I'm making progress and have a good idea of what is next:

  • expand number support to the rationals
  • report the position of a syntax error when found
  • implement support for parentheses
The first two shouldn't be a big deal, I could probably get them working pretty quickly with the existing code base. Parentheses however, are significantly more work. I know of only one way to deal with them: context-free grammars. Even if I was aware of another way to deal with the parens I would ignore it - this exercise is about learning compilers and I know that implementing a context-free grammar is necessary. I have found the lecture notes for CS 164 at Berkeley University to be quite useful. They read well without a lecturer and handle the topics with a degree of patience that allows me to comprehend it. I really wish I had been given the chance to do a course like this while I was at university. I think the context-free grammar I need can be defined as follows:
E => n | E+E | E-E | E*E | E/E | (E)
E stands for Expression and is the only non-terminal in this grammar. A non-terminal is a token that can be "expanded" further using the grammar rules. The grammar contains the following terminal tokens: 'n', '+', '-', '*', '/', '(' and ')'. Basically this grammar says that an expression can consist of either a number (n), or a combination of two expressions, or an expression in parentheses. Using this grammar we could derive the following strings:
120+16*2 6+((120-2)*4) (((1)))
But note that we couldn't derive:
1+*2 )2+3 4+(-)
Obviously this is the sort of behaviour we want. So now that I have a grammar, I want to implement a function that will take a string and tell me whether it is derivable from the grammar. There are a few ways to do this but I have to read more before I can figure out which one to try to implement first. Its also possible that I will have to modify my grammar to make it parse able.

Saturday 2 February 2008

The calculator, version one

There are a few loose ends to tie up and then the first pass of the calculator is complete. If you've forgotten where I was up to, here is a quick reminder:

  • The calculator falls over when the numbers get big because I implemented the tree evaluation in a educational but less than practical manner.
  • Whitespace should be ignored.
  • The codebase needs a general cleanup.
None of these are particularly involved - this should be a relatively short post! During the last post I discussed a few ways to implement the tree evaluation. I pointed out the most obvious solution (a switch statement), mentioned polymorphism and then ventured forth into using unbound methods. Upon discovering the issues with the latter approach it was a no brainer to go back to polymorphism:
class OperatorToken
 attr_reader :multitive, :value

 def evaluate(container_node)
   return do_operation(container_node.left_child.evaluate(), container_node.right_child.evaluate())
 end 
end

class AdditionToken < OperatorToken
 def initialize()
   @value = "+"
   @multitive = false
 end

 def do_operation(left_child_value, right_child_value)
   return left_child_value + right_child_value
 end 
end
I think you can guess what the other Tokens look like. The @value field isn't necessary to the implementation but it allowed me to keep a bunch of existing tests. The @multitive field is a replacement of the crappy named "major" field I used to determine whether the operator was higher precedence. I had to make a few minor changes to other sections of the program but it was all very easy. Whitespace is trivial to deal with. I could have easily handled it when implementing the tokenization but I guess it slipped my mind. Lets add a test for it:
  def test_spaces
   assert_equal([14,"+",62,"*",127], tokenize_for_value("  14 +62*   127 ") ); end
The fix is just stripping whitespace from the string each time a token is generated. I added a few small tests and did my best to clean up the code. You can download it here. Some sample output:
C:\Users\Paul>irb
irb(main):001:0> require 'calculator_v1'
=> true
irb(main):002:0> calculate "10 + 2*6"
=> 22
irb(main):003:0> calculate "1000000000000000000000000000000000-1"
=> 999999999999999999999999999999999
irb(main):004:0> calculate "x-1"
=> "Syntax Error"
irb(main):005:0>
Next post I discuss the what I would like to achieve in the next version.

Friday 1 February 2008

Thoughts on Android Code Day London

I spent today at Google London participating in an Android Code Day. The structure of the event was pretty simple. Roughly, it was:

  • 2 1/2 hours: presentation and questions.
  • 2 1/2 hours: "hacking".
  • 1 hour: networking (no, the OTHER type of networking, you know, the one that involves humans communicating - not machines).
I don't intend to report on the details of the day - but I have some observations. I attended the event in a non-professional capacity and in that regard I was definitely in the minority. Many of the attendees were there to assess the platform, rather than code against it. Many of the questions boiled down to "how are you going to stop the manufacturer/network operator from screwing this up for everyone by doing X?". I think working in the mobile development industry must make you jaded. Our host, Jason Chen, was great. He had an excellent blend of technical and presentation skills and also a great deal of patience. I suppose its given for a developer advocate to have these traits but there was one other thing I liked about Jason: he was genuine. A developer advocate is supposed to be enthusiastic about the product - its a fundamental part of their job! But sometimes this can be taken too far and results in a credibility drain. With Jason this was certainly not the case. Unfortunately, there was not enough Jason to go around. For an event advertised with a focus on coding, I was disappointed that there wasn't more Google staff attending to assist developers. Somehow I managed to break the debugger bridge between Eclipse and the Android emulator on my laptop and it wasted a lot of my time. It would have been nice if there was a group I could join that was discussing how the integration between Eclipse and the emulator works, perhaps it would have helped me solve my problem. Instead the groups that formed were oriented on different types of apps: locational, multimedia based, etc. I'm sure this was great for some, perhaps the majority - it just didn't work out so great for me. On a related note, I think the general lack of focus for the coding portion of the day was a problem. There are probably lots of different ways you can run an effective session aimed at developers but simply letting them loose for 2.5 hours isn't one of them. A live tutorial that you can code along with would have been cool. Perhaps something that picked up where the online notepad tutorial left off. Another idea would have been to prepare some sort of incomplete application the developers could download over the wifi and amend. Couple it with a list of small features that the developers can attempt to implement within the session and I think you have a much more compelling activity. But hey, this is the first time I've been to a "code day" so what do I know? I don't really fit the target profile. It was fun to see some of the Google offices. They are quite colourful. I enjoyed the opportunity to speak briefly with a couple of Googlers, especially Jason. Although I had a few negative things to say about the event in this post, I still enjoyed it and am glad I went. You can be sure that there will be plenty of Android related posts appearing here in the coming months but before that happens I will be returning to my parsing project. I have to be careful about letting myself get spread across too many different things at once. This is another good example of how maintaining this blog is beneficial - it greatly increases my chances of finishing the projects I start.