Fork me on GitHub

Friday, April 26, 2013

Time In Programming Languages

One of the most remarkable aspects of programming is the way in which time is modeled in our programs. I try to explain the way in which time is handled in functional and non-functional languages in this blog post.

What is a variable?

A variable in an imperative language is a named memory location. 

that is,  in a statement like

                       int a = 37;      //in c and c++ and Java

'a' denotes a named memory location which can hold a value. That memory location gets updated each time we assign a new value to a. That is,

if you say,
                  a = a+1;

a now holds the value 38.

(Note that in languages like python, variables are not typed but values are. So if you were to say a = [1, 2, 4] and later say a = 20 , the principle is still valid. That is, 'a' refers to a memory location which can be updated and accessed. The difference is:  a is not constrained to hold objects of a single type.)


What does this have to do with time?

As it turns out, everything. If you do not have assignment in your programming language, your programming language becomes purely functional in nature. That is, it loses the ability to model time.

Let me illustrate that with an example from Lisp where assignment is discouraged.

example:
     computing a factorial of a number in Lisp

        (define    (factorial    n)
            (define  (fact-iter   fact   n)                      ;;inner function for making the process iterative
                   (if (or (= n 0)  (= n 1))   fact            ;;return fact when n becomes zero or one
                        (fact-iter (* fact n) (- n 1))))        ;;recursive call
          (fact-iter 1 n))                                           

In this factorial function, we have no variables to which anything is assigned.  No assignment is necessary. If you were to write the factorial function in C or its descendants, it would look something like this:

int factorial(int n)
       int fact = 1;
       for(int i = 1; i <=n ; i++)
             fact  *=  i;
       
       return fact;
}

Notice that there is assignment in almost every statement. 

What is a variable in  a functional language?

In functional languages, a "variable" stands for  a value. That is, you must stop thinking about a variable as a location in memory somewhere that holds a value.  In fact, you must think of the variable as a "shorthand".

So instead of typing 3.14159 each time, you alias it by saying

(define Pi 3.14159)

in Lisp. There is no concept of updating the value of pi to a different value "later on". Why? because "later on" doesn't even make sense when you have no time.

It still isn't clear what I mean when I say time doesn't exist without assignment. So let me explain further: When you have assignment, you are updating a value in a memory location somewhere. So if you were to call a function with a variable as an argument, it will return a result. If you now update the variable's value and call the same function with the same variable passed in as argument, you now get a different result. That is, there are points in time when you get different results. And the reason you get different results is because you have assigned a different value. So time comes into play. There is a distinct concept of "result before assigning the new value" and "result after assigning the new value".

What happens when you get rid of assignment?

If you have no assignment, it means that variables truly are the values they alias. So, no matter how many times you call a function with a variable, you always get the same answer. If you want to get a different answer, you call the function with a different value (variable). Note that "before and after" don't exist in this scenario. 

Why is time or the lack of it important?

Well, if you don't have time in your language, then the programs you write will be mathematical in nature. They will be akin to mathematical functions like f(x) = x^2 or f(x,y) = x+y which specify a distinct mapping. So they exist "timelessly" which means, there are no synchronization errors. Also, the order of substitutions don't matter. What do I mean by that? well, consider the sequence of statements:
1. i = 1;
2. j = 2;
3. j = i +1;
4. i  =  j + 1;

If  I interchange statements 3 and 4, I get different values for i and j. So, the order of substitution matters. However, in the factorial procedure written in lisp, in the line:

(fact-iter (* fact  n) (- n 1))
the order in which I substitute the value of n doesn't matter. Because n is the same throughout. If n is say,  5, the expression becomes:

(fact-iter  (* fact 5) (- 5 1))


On the other hand, if you have time in your programming language, then the order of statements matters and your programs will have 'state'. As it turns out, having state in a programming language leads to some horrible things like worrying about synchronization when you have multiple threads or when you are running  parallel algorithms. And you get a lot of bugs if you update the wrong variable first. 

The advantage of course is that, you have the power to represent and model the time [which we observe in the real world] in your computation. There are some situations where modeling time is of immense importance: how would you model the transactions of a  bank account in a purely functional language for example? The time of transactions is tied to having the correct balance.

There seem to be situations which purely functional languages cannot handle. So even though Lisp is considered a functional language, it provides an assignment operator called SET!. And Lispers are careful not to use it too often. The challenge is to retain as much functional nature as possible while admitting state into our programs.


Why did you write this post?

Nobody explained to me the consequences of having an assignment statement and how it relates to time. In fact, I had not even thought about it. Luckily, I read Structure and Interpretation of Computer Programs and watched the Abelson and Sussman videos which explained what the consequences of having an assignment statement in a language were. I hope readers of this post see assignment in a new light. And I am fascinated at how a simple thing like an assignment statement in a programming language can raise questions about a deep concept we call time. Perhaps things would be different if we all existed in some timeless eternal universe...

Saturday, April 13, 2013

Not quite at Home?

As companies try to control and compete for users' attention, value diminishes.

A couple of days ago, David Pogue reviewed Facebook's latest offering: Facebook home for android. An app that comes pre-installed on HTC First and is downloadable for certain other android phones.
He raised a very important and pertinent question:

 What exactly is the point ?

Mobile devices are experiencing a meteoric rise in their usage. PC sales have dropped 14% this quarter.
How do you compete when the screen is just 5 inches or even 10 inches?
Google figured this out very nicely. It open-sourced the Android OS so that hardware manufacturers used it to make smartphones. These smartphones would all come pre-loaded with Google's apps. Its search engine, voice search, Streetview and tons of other apps. Google then created an eco-system similar to Apple's. The genius lies in the fact that 1) The ecosystem is so pervasive now that most people (nearly all) look at what apps are available for a phone before they buy it. 2) Google made this happen out of thin air: without the hassles of making their own handsets and without the cost and associated risks of entering the hardware market (Motorola acquisition is relatively recent). But others were not so fortunate and fell behind. (Yahoo! comes to mind.)

Google gained the users' attention through a process that can only be described as 'passive Hypnosis'.
This does not mean that Google is bad. I am merely appreciating the genius and the nonchalance with which it was able to place itself in the center of the smartphone market. Other companies have been slow to react.(Yahoo! comes to mind). Facebook paid Instagram a billion dollars for a reason. Yahoo! acquired Summly for the same reason.

Yet, for all the hype created by the companies that ask you to download their app, the value provided to the user is actually diminishing. Websites were neat and pretty once. Now every webpage is a mammoth that hogs network and carries a lot of surplus- stuff you don't actually want to look at. Same with smartphone apps: Google removed the ad-block which was one of the most popular apps so ads could be displayed on the apps that you used. And every time I access Facebook through my mobile web browser, there is an ad (thinly disguised as a "suggested post") right in the middle of my news-feed  .Facebook's new "Home for Android" is its latest attempt to imitate Google- to become what Google has become on smartphones - The very core.

The early reviews suggest that users are not very happy with this new offering. As Pogue writes,"The ads are coming soon." That means whenever you wake your phone, there may be an ad waiting. Suppose I use my phone to find out what time it is, and instead of just showing the clock widget on the home-screen, I am (probably going to be) greeted with a nice offer to buy jewelry or movie tickets. Nobody would ever want to own such a phone. In fact,  and I am really sticking my neck out here: It may increase the popularity of G+.

Users were once controlling technology. You chose to call someone. You decided to text your friends.
You decided which website was your homepage. That isn't the case anymore. All the stuff that's out there is thrown at you whether you like it or not. And you have to mine all that stuff to find what you are really looking for.

We should control technology. The user must be free to choose what sites he/she wants to visit. What their wallpaper looks like, what their default search engine should be. When and where they want to connect with their friends and most importantly: the user should decide to log in to your website rather than you trying to log in to his/her life.