What modern web frameworks do for you

Motivation

If you are like I was, a former CS major whose programming experience consisted of writing command-line programs using C++, the world of web applications might seem mysterious and foreign.

You know how computers work i.e. you know processor architecture, you know the basics of operating systems, compilers, networking protocols… but this web stuff is something else. And it’s hard to get started – for one because there’s all this terminology, but even if you learn the terminology it feels like there’s all this magic going on.

This blog post is for people who were in the position I was in 6 months ago. It is not a tutorial – it is meant to be read before your tutorials so that things make sense.

Web Application – Basic Flow

First let’s break down the basic structure of a web application.

1. An application will expose multiple endpoints, which usually correspond to different parts of the application but don’t necessarily need to. An endpoint is represented by a URL, like www.myapp.com/register or www.myapp.com/logout.
2. Clients make requests to these endpoints. These use the HTTP protocol, which I won’t get into other than to say that a request is made up of:
1. Headers, some of which are used during transit and delivery, but you can add your own
2. The desired endpoint
3. An HTTP verb, like GET or POST
4. GET requests will often have a query string attached, like                                              /getInfo?name=Rohit&age=36
5. POST requests will usually have a body, which could be XML, JSON or something called “form-data”
3. When the application starts up, it registers its endpoints with the web server (a separate process running on that machine). Registration means providing callbacks for these endpoints.
4. When a request comes in, the web server matches the URL against the endpoints it has registered, to see if there is a listener available. If not, it returns an error message (following what the HTTP protocol defines, hopefully). Otherwise it passes it on to the registered handler.
5. The handler does what it needs to, and then sends an HTML response back to the web server
6. The web server sends this response back to the client

Ok, simple enough.

Web Frameworks

So what do web frameworks do for you? Keeping in mind the steps above, the framework should provide:

1. A simple endpoint & handler registration mechanism
2. Automatic parsing of the request, putting the information into some simple data structures
3. Simple ways for handlers to redirect a request (possible modified) to other endpoints

Another useful feature is an authentication framework, so you can mark certain endpoints as "protected" i.e. requiring a logged-in user. Of course to do this you need the concept of a user, so let's not get into that.

But an even more useful feature is layout templating. Think of your final page as being data placed in a layout container. The layout defines the colors, the text areas, navigation controls, where the scroll bars are, which buttons do what etc. Some of these don't change depending on the data being presented, and some do. The template will define the data-independent portions and indicate where the data is meant to go. It might be as simple as

<div id="userName" class="userNameDisp">

    {{userNameVar}}

</div>

The framework will read this HTML template, figure out that userNameVar is a variable whose value is required, and get that variable's value from the interpolation context. You can imagine this working like this:

getPage (templateName, dataContext):

    response = loadTemplateAsString (templateName)

    for every {{varName}} in the response string

        look up varName in the dataContext

        replace {{varName}} by this value in the response string

    return response

The two web frameworks which I know of which work this way are Django, written in Python, and Ruby on Rails, which is written in Ruby.

A different strategy

Nowadays everyone loves JavaScript, supposedly because browser support is so much better than it was before (I don't know how it used to be, this is just what I hear). In fact browsers are so good at running JavaScript now that applications are being written so that a large part just sits in the browser! 

One of these frameworks is called AngularJS, and I've actually written a small application using it. But I don't fully know how it works yet. Here's what I do know/ believe at this point:

1. Request to the web application loads a whole bunch of JavaScript code. This contains all the endpoint definitions and associated handlers.
2. As the user interacts with the application, requests will be triggered to different endpoints. These will, as far as possible, be trapped by the client-side application and NOT be translated into fresh requests to the server (since the application logic has already been loaded into the browser)
3. Of course certain requests do need to go to the server, like requests for data. The server will now just send back JSON or XML.
4. Layout templates will also be sent on request, though a framework might also provide a mechanism for pre-requesting and caching them locally. One would hope that a layout template is not loaded more than once though.

Now the server sends only three types of responses: the initial application code, layout templates, and raw data. Less network traffic, but more work for the browser.

I hope this helped. If you want to learn more about these JavaScript frameworks, you can Google 

1. AngularJS for the client side (and yes there are others)
2. Express for the server (again, there are others) 
3. and for solutions which combine both the client and server - Meteor and Sails! 

App Architecture and the Basics of Scale

Motivation
Recently a friend asked me about building applications. He is a graphics designer, and doesn't want to learn how to write code. He just wants to get a "big-picture" view of some of the common themes that arise when designing applications today. This blog post is aimed at people like him - interested but non-technical.

I'm going to start off by saying that what I'm about to describe does NOT describe all the different types of software being written today. In fact I know developers who never touch these issues. But my feeling is that this will be accurate for the vast majority of developers.

What Kind of Applications are We Talking About?
Here are some examples:

1. A blogging platform
2. An order and procurement system
3. A recruitment platform
4. A corporate HR system
5. A corporate finance system
6. A (software) bug tracking system
7. An email and chat platform

These are all very different, but let's see what's similar for most or all of them.

1. There are UI elements through which users can enter data. Very often these take the shape of forms.
2. There are UI elements which show data to users. This could be:
1. the data which they, or other users entered into the system,
2. data from external systems (machinery, sensors, the Internet),
3. the results of aggregation and computation, generally shown in a report. Think of "monthly sales totals", or your bank statement.
4. Often people want to see entire collections of similar data (your MakeMyTrip search results); these are displayed in a list.
3. There are processes which run in the background which actually do something with this data. These processes may only involve computers (generating your bank statement), or sometimes other people (processing your loan request). For something like email, one process would be the delivery of mail, which might involve looking up email addresses from nicknames; another process would be receiving mail, and running it through a spam filter.
4. All this data has to be stored somewhere, since it is generally not just sent from user to user. Even in the case of a chat system, users generally want a history of their chats stored for later. So there needs to be a database.

More and more applications today are being developed on the browser - whether Internet-facing or inside an organization, the browser is the portal of choice. We can book hotels, apply to university, check football scores... all through a single portal.

(I am completely ignoring stand-alone applications like Photoshop, Excel, Mathematica, StarCraft... I'm not understating their importance, but they're not relevant right now).

Another medium which is gaining in popularity is the mobile app. They don't run in browsers, but many of them provide functionality which would be natural on a browser. Many of them (LinkedIn, Facebook, Twitter) actually have browser counterparts.

How They Work

The following flow is widely applicable:

1. A request arrives at some endpoint. For web applications, an endpoint is just a URL, like http://www.my-awesome-app.com/login 
2. The web server decides whether or not the application can handle this request. For this to happen, the application needs to have told the web server what it can handle. Anything not on that list is a fail.
3. If the request is valid, and the endpoint exists, the web server forwards it to the appropriate handler in the application.
4. The handler takes the request and does what it needs to. This usually involves talking to the database. The list of tasks which needs to be performed fall into a workflow. Workflows will have portions which are straightfoward - "after checking that their ZIP code is valid, check their area code" - and portions which are conditional - "if their account balance is too low then deny their ATM request. Otherwise give them their money".
5. If the request has arrived "bearing data", it gets written to the database. Before that, there will usually be
1. validation e.g. the user entered their birth date. People from the future are not allowed.
2. clean-up or sanitization e.g. the user entered their name all in lowercase, so the application capitalizes the first letter
6. If the request is for data from the database, the application will ask the database for the data. When it comes back, maybe it gets re-formatted, or cleaned-up, before being sent back to the user
7. Many types of requests need to be authorized, so that not just anybody can get into the system and do just anything. Sometimes this is done using usernames and passwords. Sometimes it is outsourced to another service (sign in with Facebook!).

In summary (and since I'm too lazy to draw a picture):

    User --> Web Server --> Application --> Database --> Application --> Web Server --> User

Scaling Them Up

Now suppose you have more users - more customers, more employees, whatever. It might be obvious that the system will slow down, but how exactly does this happen?

Let's consider an analogy from the real world (which is actually more than an analogy, it really works just like this). Think of a fast-food restaurant, say one which makes sandwiches. They have 4 cashiers where customers place their orders (their requests) and the cashier forwards their order to the kitchen (the application, which starts the workflow). The workflow might look like this:

1. Get some bread
2. Put mustard on the bread
3. Put meat and cheese on the bread
4. Put the bread in the oven for 3 minutes
5. Put it on a plate with some chips and signal that its ready

Then the cashier would pick it up and give it to the user. We also assume that the restaurant hasn't figured out how to let a cashier serve more than one customer at a time - which means that until the sandwich has been made, that cashier's tied up.

Now imagine that the restaurant has a lot of customers one day. What happens?

Well, the cashiers work pretty fast, so they can handle the load. And the cooks are pretty fast too. But:

1. The oven can only handle one sandwich at a time, so there's more waiting there

Okay, so the customers wait. But if this happens repeatedly, the restaurant owners will want to do something about it. They have a few options, all of which will have an impact, but none of which will "solve" the problem permanently.

1. Buy a bigger oven
2. Buy more ovens
3. Hire more cooks

(Also, until the kitchen problem is solved, there's no point in hiring more cashiers).

Here's the analogy: The oven is the database server. A bigger oven is a more powerful server - more memory, faster CPU. More ovens means more database servers. The cooks are the application servers and the cashiers are the web servers.

The cashiers are all the same, and their job is easy. The cooks are all similar, but maybe some specialize in Reubens and some in pastrami on rye. 

The database is the real work-engine, that's where the time is spent. The performance of the application will eventually just be the performance of the database.

Terminology

Let me close with some terminology.

• Scaling up: This means making a component more powerful, generally by throwing CPU and RAM at it
• Scaling out: Add more components of the same type at that layer (like hiring more cashiers). Scaling out is cheaper (2 Marutis are cheaper than a Mercedes), but the application needs to have been designed to work that way.
• High Availability: A deployment that is fault-resistant due to intentional redundancy. Like having extra cooks waiting in case a working cook gets sick or injured.
• Disaster Recovery. How does the application react when something really bad happens e.g. the data center gets hit by a hurricane, or a virus attack. DR strategies generally involve setting up an entirely separate (and geographically separated) center, ready and waiting for such scenarios. Of course if they're ready and waiting, they cost money even while there's no disaster in-progress!
• Replication: Keep copies of the data, to protect against drive failure. Disk drives are mechanical objects, and they are the components which fail first and fail often. Data must always be stored in multiple locations

One part I left out is the entire portion of flow between the client and the web servers i.e. the network part. I left it out because one generally has no control over the network, especially if one is using the Internet. Your control starts at the web front-end, and that's where you start optimizing.

1+2+3+... = -1/12 ... huh?

Recently a video did its rounds on social media, showing how the sum of the natural numbers was $\frac{-1}{12}$. Naturally there was some skepticism from some of my friends, so I decided to write up a short note to clarify the situation.

You can find the video here, and for the more mathematically inclined, a blog post by Terry Tao.

What I'm going to show is that there is a slightly more rigorous way of interpreting the manipulations performed in the YouTube video, while pointing out the parts which are still not fully kosher.

(Could I start by saying that the sum doesn't work "because of physics"? Thank you.)

Infinite Sums

In case your response upon watching that video was "Wait a minute! That sum is clearly infinity" - you're not wrong. The typical way to define an infinite sum is as the limit of its partial sums i.e. 

$$S = a_1 + a_2 + a_3 + \cdots = \sum _{n=1} ^ \infty a_n $$

is defined to be 

$$ lim _{N \rightarrow \infty} \sum_{n=1} ^N a_n$$

and according to this definition, the sum $1+2+3+\cdots$ is certainly $\infty$.

And it gets worse - there are sums whose partial sums don't even have a limit. Here's an example which is actually from the video; the sum

$$S_1=1-1+1-1+1-1+ \cdots$$

has partial sums alternating between 1 and 0. In the video, he says that since the partial sums alternate in this way, the sum must be the "average" of these two values i.e. 1/2. 

I'm going to show you another way of seeing this. We won't actually use this sum, but it's a good way to start.

Start with the series expansion

$$\frac{1}{1-x} = \sum _{n >= 0} x^n$$

Let's first see why the fraction $\frac{1}{1-x}$ has that series expansion (you've probably seen this before):

$$(1-x) (1+x+x^2+x^3\cdots) = (1+x+x^2+x^3\cdots) - x (1+x+x^2+x^3\cdots)$$

which becomes

$$ = (1+x+x^2+x^3\cdots) - (x+x^2+x^3\cdots) $$
just by multiplying by $x$. Now all the powers of $x$ cancel, leaving only

$$ (1-x) (1+x+x^2+x^3\cdots) = 1$$

and therefore

$$(1+x+x^2+x^3\cdots) = \frac{1}{1-x}$$

Now this is fine as far as algebra goes i.e. symbolic manipulation. But what happens when we want to plug in values for $x$, say $x=500$?

Well, you can't. The problem is that the infinite sum will just stop making sense. The values of $x$ for which the sum does make sense is called its domain of convergence. For the sum $\sum x^n$, the domain of convergence is just the interval $-1<x<1$ (take my word for it - if we get into that level of detail I'll never get done here).

Okay, so 

1. When $x$ is between -1 and 1, the value of the fraction $\frac{1}{1-x}$ matches with the limit of partial sums i.e. the infinite sum of $\sum x^n$.
2. When $x=1$, both the fraction and the sum clearly blow up - the fraction gets a zero in the denominator and the sum just becomes $1+1+1+1+\cdots$. 
3. But what happens at $x=-1$?

Let's compute - I'm going to plug in some values of $x$, starting at $-0.1$ and going down to $-0.9$. You can imagine $x$ moving to the left on the number line as you go down the rows of this table: 

For each row, I've listed the first few terms of the series along with their signs so that it looks like a sum (as if I've plugged values of $x$ into $1+x+x^2+\cdots$). Then in the sixth column I have the infinite sum itself (well, not quite infinite, I did the computation with $1+x+\cdots + x^{1000}$). The final column has the value of the fraction for this value of $x$.

Here's what you're supposed to notice about this table:

1.  The sum $\sum x^n$ matches the fraction $\frac{1}{1-x}$. Of course if I had shown more digits after the decimal points they would eventually have differed, because the sum only used 1000 terms.
2. Both of these get closer to $1/2$ as $x$ gets closer to $-1$ (the bottom rows)
3. The second column is getting closer to -1, the third column to +1, the fourth to -1 and the fifth to +1.

I've attempted to draw a graph which to show (3). The different colors correspond to the rows of the table. Take a look at each block of colored bars.

1. The first one is $x^0$, which is just 1, no matter what $x$ is
2. The second one is $x^1$, so you can see the dark blue bar is for $x=-0.5$ and the red one is for $-1$
3. The third one is for $x^2$, etc...

Every time you move from blue to red in a colored block, it's like going down the rows of the table.

Now what I'm trying to show you here is how the individual terms of the series $1+x+x^2+\cdots$ get closer to $1-1+1-1+\cdots$ as $x \rightarrow -1$. So when you look at the series, this is a way you can picture it changing as $x \rightarrow -1$.

I would have been nice if I had also indicated the sums of these terms, but my graphing skills only go so far... anyway from the table you can see that they approach $1/2$. 

(And of course if you plug $x=-1$ into the fraction $\frac{1}{1-x}$, you get $1/2$, no magic there). 

So what have you just seen? What I just showed you was that $1+x+x^2+\cdots \rightarrow 1/2$ as $x \rightarrow -1$, i.e 

$$ 1-1+1-1+1- \cdots = 1/2$$
To summarize, I'm going to state all this in a very particular way:

1. There is a function $f(x) = \frac{1}{1-x}$,
2. with a series expansion $1+x+x^2+x^3\cdots$
3. and there is also a point $x=-1$ 
4. which allows us to view the sum $1-1+1-\cdots$ as $f(-1)$.

LET ME REITERATE: The sum $1-1+1-\cdots$ has no meaning according to the definitions of infinite sums. We are specifically interpreting it as the specialization of a series at a point on the boundary of the domain of convergence.

The sum $S_2$

The next sum in the video is 

$$ S_2 = 1 - 2 + 3 - 4 + \cdots $$

which they claim equals $1/4$.

If you believe what I said in the last section, this one is easy. Just differentiate

$$ \frac{1}{1-x} = 1 + x + x^2 + x^3 + \cdots $$

with respect to $x$; you get

$$ \frac{1}{(1-x)^2} = 1 + 2x + 3x^2 + 4x^3 + \cdots$$

and plug in $x=-1$ to get

$$ \frac{1}{4} = 1 - 2 + 3 - 4 + \cdots$$

A different kind of series

We just interpreted $1 - 2 + 3 - 4 + \cdots$ as the specialization of $$1 + 2x + 3x^2 + 4x^3 + \cdots$$ at $x=-1$. Now we're going to look at it differently, as the specialization at $x=-1$ of

$$\frac{1}{1^x} - \frac{1}{2^x} + \frac{1}{3^x} - \frac{1}{4^x} \cdots$$

Here comes the non-kosher part: I'm going to ask you to believe that since
$$1 - 2 + 3 - 4 + \cdots = 1/4$$
using the series
$$1 + 2x + 3x^2 + 4x^3 + \cdots,$$
it continues to be $1/4$ even when we use this new series

$$\frac{1}{1^x} - \frac{1}{2^x} + \frac{1}{3^x} - \frac{1}{4^x} \cdots$$

Accepting this for the moment, the final series we need is

$$ g(x) = \frac{1}{1^x} + \frac{1}{2^x} + \frac{1}{3^x} + \frac{1}{4^x} \cdots$$

Very similar, but now we have a + sign on every term.

Step 1. Make a modification of $g(x)$ which only uses even numbers.

This is easy - we just divide it by $2^x$; watch:

$$\frac{g(x)}{2^x} = \frac{1}{2^x} \left ( \frac{1}{1^x} + \frac{1}{2^x} + \frac{1}{3^x} + \frac{1}{4^x} \cdots \right )$$

$$ = \frac{1}{2^x} + \frac{1}{4^x} + \frac{1}{6^x} + \cdots$$

Cool.

Step 2. Now we subtract it from $g(x)$, first once:

$$ g(x) - \frac{g(x)}{2^x} =  \frac{1}{1^x} +  \frac{1}{3^x} +  \frac{1}{5^x} + \cdots $$

and then again:

$$ g(x) - \frac{g(x)}{2^x}- \frac{g(x)}{2^x} = \frac{1}{1^x} - \frac{1}{2^x} + \frac{1}{3^x} - \frac{1}{4^x} + \frac{1}{5^x}+ \cdots $$

(Looking familiar!) Let's simplify the left-hand side by grouping the $g(x)$'s

$$g(x) (1 - \frac{1}{2^x}- \frac{1}{2^x} ) = \frac{1}{1^x} - \frac{1}{2^x} + \frac{1}{3^x} - \frac{1}{4^x} + \frac{1}{5^x}+ \cdots$$

$$g(x) \left (1 - \frac{2}{2^x} \right ) = \frac{1}{1^x} - \frac{1}{2^x} + \frac{1}{3^x} - \frac{1}{4^x}  +  \frac{1}{5^x}+ \cdots $$

If we plug $x=-1$ into the left-hand side, we get $g(-1) (1-4)$, and if we plug it into the right-hand side we get $1 - 2 + 3 - 4 + \cdots =1/4$. 

Diving by $1-4$ gives us $$g(-1) = -1/12$$

And... what is $g(-1)$? Go ahead, look at the definition, you will get

$$1+2+3+4+\cdots = -1/12$$

The Non-Kosher Step

Why am I uncomfortable with saying that 

$$\frac{1}{1^x} - \frac{1}{2^x} + \frac{1}{3^x} - \frac{1}{4^x} \cdots$$
approaches $1/4$ as $x \rightarrow -1$?

Remember that whole bit above where I drew the graphs of those series and said "well, the series approaches 1/4 as $x$ approaches -1"? I showed you a table and hopefully convinced you that what I was doing wasn't complete nonsense. (Okay, I drew the graphs for $S_1$, but it works for $S_2$ as well. Try it in Excel or something).

We can't do that here.

Not only can we not approach $x = -1$, we can't even cross $x=+1$! The series converges when $x>1$, and blows up at $x=1$, but even if you try to evaluate it at $x=0.99$ it won't work. It just blows up.

So how did I jump from $x=1$, across 0 all the way to $x=-1$?

Well, that's why this is the non-kosher step. And I don't have an explanation which doesn't involve more machinery.

But it's not "because of the physics".

Playing with roots of unity

This post doesn't have a goal, I'm just recording some behavior I came across. Sometimes people approach me at parties and tell me how interested their children are into math; now I can point them here.

 Let $p$ be prime, and let $\zeta$ be a $p$-th root of unity. This means that $\zeta^p=1$ (but $\zeta \neq 1$). For every integer $k$, defined $\epsilon_k$ to be $\zeta^k + \zeta^{-k}$.

 Note that $\epsilon_0 = 2$, and $\epsilon_k = \epsilon _{-k}$. Let's see how these multiply:
$$ \begin{align} \epsilon_k \epsilon_l &= (\zeta^k + \zeta^{-k})(\zeta^l + \zeta^{-l}) \\ &= (\zeta ^ {k+l} + \zeta ^ {k-l} + \zeta ^ {-k+l} + \zeta ^ {-k-l}) \\ &= \epsilon_{k+l} + \epsilon _ {k-l} \end{align} $$
Now I will show that all the $\epsilon_k$'s can actually be expressed as polynomials in $\epsilon_1$. First let's expand powers of $\epsilon_1$ using the binomial expansion: $$ \begin{align} \epsilon_1^n &= (\zeta + \zeta^{-1})^n \\ &= \sum_{l=0}^n \binom{n}{l} \zeta^l \zeta^{-(n-l)} \\ &= \sum_{l=0}^n \binom{n}{l} \zeta^{2l-n} \end{align} $$

Let's add the terms in pairs, starting with the first and last: $$ \binom{n}{0} \zeta^{-n} + \binom {n}{n} \zeta^n. $$ This is just $\epsilon_n$.

Now add the second and second-to-last terms: $$ \begin{align} \binom{n}{1} \zeta^{2-n} &+ \binom {n}{n-1} \zeta^{2(n-1)-n} \\ \binom{n}{1} \zeta^{2-n} &+ \binom {n}{n-1} \zeta^{n-2} \end{align} $$ which is $n \epsilon_{n-2}$.

In this way, every term pairs up with another term, giving an integer times an $\epsilon_k$ (remember that binomial coefficients are always integers!). When $n$ is even, there is also the middle term $\binom{2l}{l}$, coming from $l=n/2$. This term is actually even making it an integral multiple of $\epsilon_0$.

To summarize: every $\epsilon_1 ^n$ is an integral sum of $\epsilon_k$'s for $k$ <= $n$. Even better, it is $\epsilon_n$ + an integral sum of $\epsilon_k$'s for $k$ < $n$! Which means we can turn it around to say that $\epsilon_n$ is $\epsilon_1^n$ minus an integral sum of $\epsilon_k$'s for $k$ < $n$.

Why is this good? Because continuing in this way, we can replace each $\epsilon_k$ with an $\epsilon_1^k$ plus/minus some other stuff, which we can then replace in the next step. And each time our coefficients stay integers.

So we get that $\epsilon_n$ is an integral polynomial in $\epsilon_1$. Here are the first few for $n$ <= $4$, I'm just going to write $\epsilon$ for $\epsilon_1$ now: $$ \begin{align} \epsilon_1 &= \epsilon \\ \epsilon_2 &= \epsilon^2 - 2 \\ \epsilon_3 &= \epsilon^3 - 3 \epsilon \\ \epsilon_4 &= \epsilon^4 - 4 \epsilon^2 + 2 \end{align} $$

As I find time I will study these polynomials and record my results here. Feel free to make contributions in the comments!

Tracking invitations via external services

Let's say you are writing a mobile application which allows users to invite their friends via Facebook, Gmail, and services like those. To make things concrete, let's say your application lets users create shopping lists for parties, and lets users link to their Facebook and Gmail accounts.

So Farah gets the app, links her Facebook account, creates a shopping list and invites her friend Priya to collaborate on it. By linking to Facebook, she is able to access her Facebook friend list of which Priya is a member, so that's how she sends the invitation.

Priya gets a message from Farah in her Facebook mailbox. Here's what we want to have happen:

1. If Priya already has the app, and has linked her Facebook account, she automatically sees the invitation when she next opens the app,
2. If she doesn't have the app, she will download it (by following the app-store link conveniently included in the Facebook message) and link her Facebook account. When she does that, the invitation will appear in the app.

How can we do this? Here's my solution which is simple and easy.

The app's server will maintain two types of user objects - active users and passive users. An active user is one who has downloaded the app and registered as a user. A passive user is someone to whom an invitation has been sent, but who may not have downloaded the app yet.

Active user objects have a (possibly empty) set of linked external accounts. A passive user object will contain exactly one linked account.

When Farah sends Priya the message, the system will look for an active user object containing a linked account for Priya@Facebook. If it finds one, it associates the invitation to that user object so that Priya sees it the next time she logs in.

If there is no active user, the system will look for a passive user. If it finds one, it will associate the invitation to it, and if not, it creates one and associates the invitation to the new object.

When Priya finds and downloads the app, she will hopefully link her Facebook account. At this time the system will look for passive users attached to her Facebook account. When it finds it (and there should be only one), it will link the newly created active object to this pre-existing passive object, and via the passive user will gain access to all associated invitations.

Since the passive user object is not removed from the system, no lists containing it need to be updated. So Farah's party list will continue to hold a reference to the passive object, and when the system asks for the user it will "follow the links" to the active object.

Since the passive object acts only as a forwarding mechanism now, the information about the linked Facebook account can be moved to the active object to avoid wastage of space. And in fact we don't need to hold on to the passive object at all - we could just maintain a mapping from the passive object IDs to the active ones. So a "getUser" function would look like

getUser(userId)
{
  if(userId in passiveToActive.keys)
    userId = passiveToActive[userId]
  return db.findUserObj(userId);
}

Note that multiple passive objects could link to a single active object - this would happen if someone received invitations via multiple services. When they link those services this mechanism will pull all that passive activity over to the active account, which is just what we want.

A Calculation involving Circles

This is a computation I did for a friend last month. We wanted to describe the set of points the ratio of whose distances from two other points remained fixed.

Let me say that better: I have two points in the plane, $S$ and $T$, and am given a positive fixed quantity $\alpha$. I want to describe the set of points $P$ for which

$$ \frac{\text{distance} (P,S)} {\text{distance}(P,T)} = \sqrt {\alpha}$$
The reason I put in a square-root is because I'm actually going to work with the square of this formula.

Notice that if $\alpha = 1$, then I just get a line. So I'm only going to consider the cases in which $\alpha \neq 1$.

I'll start by naming the coordinates of these points:
$$S= (a_1, b_1), T = (a_2, b_2), P= (x, y)$$

Then the ratio of distances reads as

$$\frac{(x-a_1)^2+(y-b_1)^2}{(x-a_2)^2+(y-b_2)^2} = \alpha$$

Now I'm going to do some algebra.

$$(x-a_1)^2+(y-b_1)^2 = \alpha((x-a_2)^2+(y-b_2)^2)$$

$$x^2-2a_1x+a_1^2 + y^2-2yb_1+b_1^2 = \alpha(x^2-2a_2x+a_2^2 + y^2-2yb_2+b_2^2)$$

$$x^2-2a_1x+a_1^2 + y^2-2yb_1+b_1^2 = \alpha x^2-2a_2\alpha x+\alpha a_2^2 + \alpha y^2-2y\alpha b_2+\alpha b_2^2$$

$$(1-\alpha)x^2 + (- 2a_1 + 2\alpha a_2 )x +(a_1^2-\alpha a_2^2) + (1-\alpha) y^2 + (- 2 b_1 + 2 \alpha b_2 )y + (b_1^2 - \alpha b_2^2) = 0$$

Now since $\alpha \neq 1$, I can divide by $(1-\alpha)$:

$$\left [x^2 + \frac{- 2a_1 + 2\alpha a_2 }{1-\alpha} x + \frac{a_1^2-\alpha a_2^2}{1-\alpha} \right ] + \left [ y^2 + \frac{- 2 b_1 + 2 \alpha b_2 }{1-\alpha}y + \frac{b_1^2 - \alpha b_2^2}{1-\alpha} \right ] = 0$$

Now I'm going to use a clever little transformation called "completing the square", which is basically a convenient rewriting of

$$X^2+2AX+B$$
as
$$ (X+A)^2+(B-A^2)$$

It's the same, you can check. I do this to both the $x$ component and the $y$ component (separately!), and get

$$\left [ \left (x + \frac{- a_1 + \alpha a_2 }{1-\alpha} \right )^2 + \left ( \frac{a_1^2-\alpha a_2^2}{1-\alpha} - \left ( \frac{-a_1 + \alpha a_2 }{1-\alpha} \right ) ^2 \right ) \right ]
+ \\
\left [ \left (y + \frac{- b_1 + \alpha b_2 }{1-\alpha} \right )^2 + \left ( \frac{b_1^2-\alpha b_2^2}{1-\alpha} - \left ( \frac{- b_1 + \alpha b_2 }{1-\alpha} \right ) ^2 \right ) \right ] = 0
$$

Now I move the constants (the parts not involving $x$ or $y$) to the right-hand-side of the $=$ sign. Watch those signs!

$$\left (x - \frac{a_1 - \alpha a_2}{1-\alpha} \right )^2
+ \\
\left (y - \frac{b_1 - \alpha b_2}{1-\alpha} \right )^2
=
\left ( \left ( \frac{- a_1 + \alpha a_2 }{1-\alpha} \right ) ^2 - \frac{a_1^2-\alpha a_2^2}{1-\alpha} \right ) + \left ( \left ( \frac{ - b_1 + \alpha b_2}{1-\alpha} \right ) ^2 - \frac{b_1^2-\alpha b_2^2}{1-\alpha} \right )
$$

And because $(-1)^2=-1$,

$$\left (x - \frac{a_1 - \alpha a_2}{1-\alpha} \right )^2
+ \\
\left (y - \frac{b_1 - \alpha b_2}{1-\alpha} \right )^2
=
\left ( \left ( \frac{a_1 - \alpha a_2}{1-\alpha} \right ) ^2 - \frac{a_1^2-\alpha a_2^2}{1-\alpha} \right ) + \left ( \left ( \frac{b_1 - \alpha b_2}{1-\alpha} \right ) ^2 - \frac{b_1^2-\alpha b_2^2}{1-\alpha} \right )
$$

END OF LONG CALCULATION.

What did this give us? Well, that final relation describes a circle of $(x,y)$ points, whose center is

$$\left ( \frac{a_1 - \alpha a_2}{1-\alpha}, \frac{b_1 - \alpha b_2}{1-\alpha} \right )$$

which we can write as
$$\frac{S-\alpha T}{1-\alpha}$$

The square of the radius of this circle is

$$ { \left ( \left ( \frac{a_1 - \alpha a_2}{1-\alpha} \right ) ^2 - \frac{a_1^2-\alpha a_2^2}{1-\alpha} \right ) + \left ( \left ( \frac{b_1 - \alpha b_2}{1-\alpha} \right ) ^2 - \frac{b_1^2-\alpha b_2^2}{1-\alpha} \right ) }
$$

$$=\frac{{(a_1-\alpha a_2)^2-(a_1^2 - \alpha a_2^2)(1-\alpha)+(b_1-\alpha b_2)^2-(b_1^2 - \alpha b_2^2)(1-\alpha)}}{(1-\alpha)^2}
$$

Let's simplify the numerator. We start by expanding it out:

$$(a_1^2-2\alpha a_1 a_2+\alpha^2a_2^2)-(a_1^2 - \alpha a_2^2 - a_1^2\alpha + \alpha^2 a_2^2) + (b_1^2-2\alpha b_1 b_2+\alpha^2b_2^2)-(b_1^2 - \alpha b_2^2 - b_1^2\alpha + \alpha^2 b_2^2)
$$
Lots of these terms cancel one another, and in fact we are left with
$$\alpha(a_1^2-2a_1a_2+a_2^2) + \alpha(b_1^2-2b_1b_2+b_2^2)
$$

$$=\alpha ((a_1-a_2)^2 + (b_1-b_2)^2)$$

So the radius of the circle is (the positive value of)

$$\frac{\sqrt{\alpha ((a_1-a_2)^2 + (b_1-b_2)^2)}}{1-\alpha}
$$

which is $\sqrt\alpha/(1-\alpha)$ times the distance between $R_1$ and $R_2$.

In summary

The set of points which have a fixed ratio of distances from two other fixed points is either

a. A line, if that ratio is 1
b. Another circle, whose center is $\frac{R_1-\alpha R_2}{1-\alpha}$ and radius is $\sqrt\alpha/|1-\alpha| |R_1 - R_2|$.

Valuation, Money, Trade / Part 3 / Currencies and Trade

Currencies
Now let's throw in the fact that societies developed separately. It would have been great if the world had a universal measure of value from the start, but unfortunately this is not how things happened, and money developed differently in different cultures and countries, and societies developed pride in their currencies and saw them as symbols of their identity. They were still transacting with one another though, so the valuation table needed entries to translate between different currencies now.

Suppose we take two currencies, cA and cB, and consider their valuation tables' entries for cows.

1 cow = 5 cA
1 cow = 10 cB

Well, great! We conclude that 1 cA = 2 cB.

Oh but wait, let's look at the entries for bathroom tiles.
1 tile = 1 cA
1 tile = 1.5 cB

Oops.

This is hardly unexpected - it is a reflection of how different societies have different valuation tables because of their different priorities, wants and needs, and access to resources. But it makes finding the combined valuation table's entries complicated.

So instead of trying to "solve for" the cross-currency ratios, we do something different. We make the currencies themselves things-to-be-transacted, and let individuals and societies create entries for external currencies. So the society with currency cA would have an entry in their valuation tables which looks like
1 cB = <some number> cA

Trade
Now who even needs these valuations? Why would a member of society A require the currency of society B? The only reason would be that they need to transact with members of society B i.e. engage in import and export.

So the trader in bathroom tiles would use one ratio, and the trader in cows would use another. But if they're smart, they will trade in both tiles and cows! Let's look at the perspective for a trader from society A, the case for B is just the opposite. We will use the numbers from above.

Trader A takes 15 cA and buys 3 cows. He sells these cows in society B for 30 cB. With those 30 cB he buys 20 bathroom tiles, which he brings back home and sells for 20 cA. His profit from the transaction is 5 cA.

Why couldn't he just keep doing this? Well, sometimes he can, and some people do. But usually what happens is that the other people in these transactions realize what is happening and start adjusting their prices - the cow seller in society A starts charging more for her cows and the cow buyer in society B starts paying less. Or a similar price adjustment happens with the bathroom tiles - in both cases the valuations of societies A and B start to converge.

The problem with prices converging, is that people who are not engaging in these clever cross-border trades start getting screwed. Cows become more expensive for everyone in society A, not just to our trader. And bathroom tiles become more expensive in society B, leading to great unhappiness on that side.

On the one hand one could say to the people in society A - "Look, they are willing to pay more for cows, why don't you just send your cows over instead of milking them or eating them yourselves?". But people want their cows, dammit, and they'll be damned if they're going to be forced to send them over to society B.

Duties / Tarrifs
So they band together collectively and raise the price of transporting cows across the border. The price of the cows stays the same, so they continue living happily, but the cost of doing the clever (nefarious!) cow-tile trade goes up. Now the cow-tile trader is not making so much money, and after society B enacts a similar rule on bathroom tiles, societies A and B continue to see their old prices for cows and tiles.

If the cost of doing business (the duty, or tariff) is too high, the cow-tile trader won't engage in the transactions. But the people of societies A and B are quite smart, and they don't make those costs that high. Instead, they raise them to where the trader makes only 2 cA per transaction instead of 5 cA. Now 2 cA is better than nothing, thereby giving him incentive to trade, and the remaining 3 cA gets taken in duties and is used for the beautification of the public parks. (That 3 cA will actually consist of some cA and some cB... you can figure out the details).

The last example showed the trader as being the "good guy" trying to do business despite the obstacles put in place by the duty-regimes in both nations he wants to trade in. Here's another narrative, which has also occurred several times in history. Let's use the same valuations for cows and bathroom tiles as before:

1 cow = 5 cA
1 cow = 10 cB
1 tile = 1 cA
1 tile = 1.5 cB

Again, the trader will buy tiles from nation B and sell them cows. The differences in this scenario are:

1. The trader has an abundance of cows to sell, so domestic prices are unaffected
2. The trader deploys soldiers in nation B and tells them not to raise their tile prices. Oh, and they better buy all these cows which are being sent over the border.

(Sometimes the soldiers weren't even necessary - say if the "cows" were opium and "nation B" were China...)

In fact coupling soldiers with traders is basically how European colonialism worked, certainly in Africa and Asia. I don't know enough about other types of colonialism to comment here.

Today nations don't need to deploy soldiers (although that still happens). There are other ways to coerce other nations in matters of trade.