I modified my tipcalc program to handle expressions of arbitrary depth, so now it can handle input like ((($100 + 2%) + 2%) - 3%) + 3.5%.

The trick was to change the start symbol to match binary_expression, and then define binary_expression recursively, like so:

1
2
3
4
5
6
7
8
binary_expression:
    dollars OP_PLUS percentage
    |
    dollars OP_MINUS percentage
    |
    LPAREN binary_expression RPAREN OP_PLUS percentage
    |
    LPAREN binary_expression RPAREN OP_MINUS percentage

This is what makes this new version a context-free grammar and not a regular grammar. Now, if you think that you could still handle this input with a regular expression, notice that adding percentages is not associative. For example, you might think we could drop the parens and just parse $100 + 2% + 2% + 2% using /\$\d+ (\+ \d\%)+/

1
\$\d+ (\+ \d\%)+

Regular expression visualization

Debuggex Demo

However, if instead we wrote $100 + 2% - 2% + 2%, associativity says we can reduce it to $100 + 2%, however, when associated to the left (($100 + 2%) - 2%) + 2% it is clear that the result is different from $100 + 2%.

As long as I’ve been able to do arithmetic, I’ve been able to figure out calculating taxes and tips, it’s easy. Given a dollar value $17.91 we can figure out the total with a tip of 18% as $17.91*(1.18) = $21.14

However, it would be nice just to enter in $17.91 + 18% and have the computer figure it out. So one time at lunch after calculating the tip for a burrito I decided to learn lex and bison, which can be used together to create a mini language.

The grammar I used was the following:

1
2
3
4
5
6
7
8
9
10
start:
    dollars OP_PLUS percentage
    |
    dollars OP_MINUS percentage

dollars:
    TOKDOLLAR NUMBER

percentage:
    NUMBER TOKPERCENT

Where OP_PLUS and OP_MINUS come from + and -. Also, TOKDOLLAR and TOKPERCENT are $ and %.

Then, below each grammar rule, I added some C code that would be generated if the input matches that rule:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
start:
    dollars OP_PLUS percentage
    {
        double dollars = $1;
        double percentage = ($3)/(100.0);
        double total = dollars + dollars*percentage;
        printf("$%.2f", total);
    }
    |
    dollars OP_MINUS percentage
    {
        double dollars = $1;
        double percentage = ($3)/(100.0);
        double total = dollars - dollars*percentage;
        printf("$%.2f", total);
    }

The full source code is available here.

Now, it is true that this is no more powerful than a regular expression, however, I intend on modifying it to allow nested expressions like (($2 + 4%) + 4%), which would be useful for compound interest calculations. That would be more powerful than regular expressions, meaning it would be at least a context-free grammar.

Update: In the future, I wrote about implementing this

When working with git at the command line, I frequently want to see the last changes made to a repository. To see the result of the last commit (diff’d with it’s parent commit), you can just type git show. Git assumes the HEAD pointer and just spits it out:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
$ git show
commit 112379bca37e89c719c54be1598eeea5dbeede82
Author: Tobi Lehman <tlehman@example.com>
Date:   Thu Nov 20 10:31:59 2014 -0800

    add -r flag to regenerate fastroutes file

diff --git a/fastroutes b/fastroutes
index 55920ce..666a2ab 100755
--- a/fastroutes
+++ b/fastroutes
@@ -39,6 +39,10 @@ function main {
 if [[ "$1" == "-f" ]]
 then
   show_current_filename
+elif [[ "$1" == "-r" ]]
+then
+  rm $cached_routes_filename
+  cache_routes
 else
   main
 fi

Sometimes I want to step back through all the commits though, I can run git show HEAD^ and git show HEAD^^, and keep appending ^ characters, but that gets old fast. Also, sometimes I just want to look at the commits that changed a file.

To solve this, I wrote git log-display. Here’s an example to see how it can be used:

git log-display

To see all the commits from HEAD all the way back to initial commit, run git log-display:

To step back through commits, hit ‘q’, and to exit press ‘Ctrl-C’

git log-display FILENAME

To see all the commits that make modifications to FILENAME, just run git log-display $FILENAME:

git subcommands

One nice thing about git is that you can make a subcommand git foo just by having an executable called git-foo somewhere in your PATH variable. So to install this, just copy git-log-display to a directory in your PATH.

The most common business models on the internet are:

  • ad-supported free services (Google, Facebook, Twitter, etc.)
  • freemium (reddit, Hulu, apps with in-app purchases, etc.)
  • donation (Wikipedia, NPR, etc.)
  • subscription (The Economist, Netflix, WSJ, NYTimes, etc.).

The first type of business, the Google model, have been tremendously successful over the last 15 years or so. The users don’t have pay anything, and advertisers have a wealth of information to use to find better ways of serving ads. The obvious downside is that your activity is the product that is sold to the ad companies that partner with Google or Facebook. That information is also low-hanging fruit for government surveillance.

Obviously, people want convenient services for free, but companies like Google and Facebook have enormous data centers and expensive engineers to pay for. So we have ads, it’s a reasonable tradeoff. I want free stuff too, but I understand that it will mean ads targeted at me, well-informed by my online activity. Many people don’t understand this tradeoff, and just think Google and Facebook magically work and keep their information private. The obvious solution if you want your online information private is to pay for services that don’t have to sell your information to advertisers. Another is to buy your own servers and host things yourself, and learn enough about cryptography to be able to keep it secure. Either way, it will cost money, since you are no longer benefiting from those ad-based subsidies.

Personally, I hate almost all ads, but I understand why they are there, because I’m using Gmail, GovTrack, Twitter, etc. using up server resources without paying for it. For a long time, I’ve been using the Adblock plus browser plugin, and it blocks ads so I don’t have to look at them. About three months ago I changed my mind though, and it had to do with the reason I think voting is important.

Why we should all vote

My thought process was as follows:

  1. My individual vote will almost certainly not change the outcome of an election.
  2. I am equivalent to all citizens in terms of rights and responsibilities.
  3. Most of the population needs to vote in order for the policies and politicians to approximately represent us voters.

So, it’s pretty clear that (3) is an extreme hypothetical, but it’s an important ideal to use when deciding how to behave as a civilized human (Kant called this the Categorical Imperative). From (2), I can conclude that if I am going to decide to do something, I need to consistently apply my reasoning to the whole population. Finally, if I use (1) to justify not voting, it follows by (2) that each citizen should not bother voting. If every citizen then decided not to vote, democracy wouldn’t work. Therefore, I will vote, an encourage others to follow suit.

So what does voting have to do with Adblock?

Why we should all uninstall adblock

The reason I see a related issue behind adblock and voting is that services like Gmail, Facebook and GovTrack require that most of their users see those ads, and occasionally follow them. And each individual user decides that they don’t want to look at ads, and that their own attempt to block ads aren’t going to bankrupt the companies behind them.

The thought process behind it is very similiar:

  1. My individual installation of adblock will almost certainly not bankrupt the company behind the site I’m using.
  2. I am equivalent to all users of the software service who are using it free of charge.
  3. Most of the userbase needs to see and interact with ads in order for the company to make money and continue existing.

The similarity should be clear now. I personally don’t want ads, but I understand that if all Gmail and Facebook users blocked ads, Google and Facebook would have to change their services to a subscription model, and users would have to pay money to use them.

Conclusion

Either uninstall adblock (or whatever is used to block ads), or start paying. I was pleased to hear that Google is offering an alternative to ads where you pay a small monthly fee to have a totally ad-free Google experience. If you are on the internet, you are paying for electricity and the connection itself, so you can pay for the services you use. Otherwise, live with ads.

NOTE: My site doesn’t have ads, nor does it cost to read it, it’s closer to a donation model, I pay a small fee to host the site, and I don’t expect people to pay me for it. However, it’s static content, so most of the computational work happens on the client site (handled by your browser). I do have a bitcoin donation address.