Sunday, March 28, 2010

A new language

Why, oh why, would I curse the world with another programming language? The answer is my typical, "Why not?". More seriously, there are minor deficiencies that I would like to address in the modern mainstream languages. The language I will design will be an incremental improvement over what we currently have. I don't expect it to gain much traction, but it should be enjoyable to program in and it will make for a nice side project.

Here are the major things I wish to have in my language
1. Type inferencing
2. Mutable/Immutable variables - you should be able to specify if a variable is mutable or immutable. By default, local variables are mutable. Non local variables (member variables and static variables) are by default immutable.
3. Non-nullable types - By default all types are non-nullable. You can wrap the type in a Nullable<T> and use the Nullable<T>.Null object to represent null.
4. Generic types - types can be generic.
5. "Duck" interfaces - types can be cast to an interface that they don't implement so long as they implement the correct functions. It must be an explicit cast (unless the interface is unnamed), but the cast will succeed.
6. Unnamed interfaces - When defining a generic function, you can specify an interface that the parameter must implement. The incoming object will be implicitly cast to this unnamed interface.
For example:
int f<T implements { void foo(); }>(T incoming)
7. immutable methods - methods are, by default, immutable. They can not change any of the mutable or immutable members. A method may be specified as mutable, but mutable methods may not be called on immutable objects.
8. Metaprogramming support - Compile time support for metaprogramming should come from a few different sources. First, a standard AST will be provided that can be manipulated through annotation. Basically, an annotation is like a macro that takes a statement and transforms the AST into a different statement. For example, you could write a "memoize" functional annotation that accepts a function declaration and replaces it with a different declaration that is memoized. In addition, metaprogramming can come through compiler event hooks such as "onInheritance", "onCast", "onDeclaration", etc...
9. Unit test support - I'm not yet sure what this will end up looking like, but I do plan on having the ability to write short, inline unit tests at the point of method declaration. It will act as both a user guide as well as a documented test.
10. No "new" keyword - I have never understood the point of the "new" keyword in Java and C#. Therefore, it is gone.
11. No more try - I really hate the try/catch thing. In The Design and Evolution of C++, Bjarne writes about how he had a version without try, but it was confusing. I think it is time to resurrect his experiments. I'm not yet sure of the final form, but I'm sure it will be tryless.
12. Inheritance is deprecated - Other than interfacing with other languages, there should be no need or desire for inheritance. Much of what it was designed to accomplish can be done better through syntax macros and composition. Inheritance will be kept for compatibility with Java/C#/etc..., but its use in native libraries will be deprecated.

Ok, that's 12 things that I see for my language. I don't have a name for it yet, but will accept any suggestions :) I plan to target the .net runtime at first, but the JVM should be a target as well. Comments are welcome.

Friday, March 19, 2010

Passing the Microsoft Interview

As you know, I work for Microsoft - specifically on the team, more specifically on the core core relevance team (yes, that's two cores...don't ask). Even more specifically on the anchor team in the core core relevance team of in Microsoft. Wow, that's a mouthful.

Anyway, bing is hiring and that means I'm interviewing a lot these days. I'm doing at least one interview every other week, sometimes more. In addition, not many people are passing. So, to help everyone out, I thought I would put together a list of tips to help you pass the Microsoft Interview.

Tip #1: Know your stuff

Yeah, easier said than done. However, there are a number of resources out there that can help you. I've listed them in a previous blog post, so study up and have a good understanding of data structures, algorithms, and Big O notation before getting here.

Tip #2: Understand the problem

A lot of people encourage you to ask lots of clarifying questions. I think that is good practice and would also encourage you to do it. In addition, I think you should also spend quite a bit of time at the beginning to list out examples, both positive and negative.
Let's use a concrete example. One question that I see posted all over the web is to write a function to take a string as input and reverse the order of the words in the string. So, for example, "Hello World" would get reversed to "World Hello".
The first thing you should do is ask clarifying questions. Here are some examples:
1) Should I reverse the string in place, or create a new string?
2) What is the return value for the empty string?
3) How should a null pointer be handled?
4) What constitutes a word separator?
5) ASCII or Unicode?
6) How should punctuation at the end of the string be handled?
7) What about capitalization?
8) Is it a c style string or are embedded nulls allowed?

Now that you have fleshed out the problem, the next thing to do is think of some example inputs and see what the outputs would be. I would think of this in a tabular format with input on the left and output on the right

nullassertion failure
"Hello world""world Hello"
"Hello from Microsoft""Microsoft from Hello"

There may be more examples depending on the answer to the clarifying questions, but these would be the minimum examples necessary. Go through each example with your interviewer and make sure he or she agrees with your mapping function.

Tip #3: Describe the algorithm

After you have created your examples, but before you start to code, describe, in English, the algorithm you have devised. First, this helps you to think about the algorithm before you code it and second it gives your interviewer a chance to hint at the right solution if you missed it. If, instead, you immediately start coding a poorly performing algorithm, you give your interviewer no choice but to sit idly by while you waste his time coding something he knows won't work. If you, instead, discuss the algorithm with the interviewer, it gives him or her the chance to point you in the right direction and lets you write code that the interviewer wants to see.

In our word reversal example, you might start by describing an algorithm whereby you find the first space and the last space and then swap the words and repeat until the spaces are the same. The interviewer might ask you about the complexity of this approach and then ask if there is a less expensive algorithm. Doing things in this order makes sure that you are coding the algorithm the interviewer wants to see.

Tip #4: Don't mention a naive algorithm to fill time

The interviewer has asked you a difficult question. You're not sure of the correct way to solve it. Don't just mention the first, most naive, solution that pops into your head. If you think your first solution is a good one, then by all means mention it, but if you know it sucks and is O(n!) or some such nonsense, then stop, think, and come up with something better. By giving a poor solution to begin with you are just giving the interviewer a reason to reject you. You don't have to get the right solution to begin with, just make sure it's not horrible.

Tip #5: When coding, make sure you check your boundary conditions

Nothing sets me off more than when someone forgets a null check or a boundary condition check. This is just Engineering 101 and is critical for a system such as bing. If you can't be bothered to check for null in all the right situations, then don't even apply. Sure, everyone makes mistakes, but in the interview keep null checks on the top of your mind.

Tip #6: After coding, run through your examples and make sure your code works

I've seen too many people write code on the whiteboard, spend 5 seconds looking at it, and then say "Yes, that looks good." There is NO way you have tested it in your head after 5 seconds. Even if it is correct, how do you know? The best thing to do is to use your examples that you generated to walk through your code. You might discover, for instance, that you assumed there would always be a space, when there might not. This gives you a chance to correct your own mistakes without forcing the interviewer to intervene.

Tip #7: Ask questions about the interviewer

This is just good psychology. Make the interviewer feel important by spending a few minutes at the end asking about the interviewer's team and work. The benefit to you is that you get to hear about the day to day activities and make sure they sound interesting. The benefit to the interviewer is that he or she gets to talk about his or her exciting projects. This leaves the interviewer with a good feeling leaving the interview, which is always a good thing. So, the next time you are stuck without a question, ask the interviewer to tell you about a recent project - and hopefully it excites you both!

There you have it, 7 tips on getting through a Microsoft interview. Of course, I honed in on coding, but many of the same ideas apply to the design based interview questions, as well. Regardless, be prepared, be confident, and most of all, have fun!

Friday, February 12, 2010

What have we programmers learned?

Remember when everyone wrote spaghetti code littered with gotos? Ok, I don't, and I doubt there was such a time. The really great people never wrote spaghetti code littered with gotos. They used gotos because they were all that was available, but they wrote structured code before structured code was cool. It took time, and language advances, but eventually the average joe programmer like me caught on to the practice. This led to much rejoicing and greatly improved software. Of course, by that time, the great programmers were already moving on to things like object-oriented programming and generic programming. There is always a downdraft from the great programmers exploring and pioneering to the average joe learning and improving the mean.

The questions were are here to ask (and answer) are
1) What has the average joe programmer learned over the last 10 years?
2) What are the great programmers exploring and pioneering today?

It is interesting to note that most of the things I'm going to discuss were practiced since the beginning of the computer era. They are not new ideas or inventions, it is just that it has taken this long for the rest of us to catch up and realize their significance and importance.

In this post, I'll list out what I believe we have learned and are learning and in future posts, we'll go into each in more depth.

What have we learned over the last 10 years?

1) Automated unit testing - Note, this doesn't necessarily mean TDD, BDD or any other methodology, just that we should have unit tests and they should be run automatically.
2) Refactoring
3) Small methods
4) Value Semantics - How can I say this when most VMs use references? Think immutable reference types!
5) Functional extensions to procedural languages
6) VMs are good
7) OO is not a silver bullet
8) ORM is hard
9) IDEs are vital
10) XML was a cruel joke

What are we learning?

In most of these cases, we know the concept is important, but we're still quite unsure of how to quite integrate it into our everyday lives. There are still many fledgling attempts, but nothing has quite been standardized. In some cases, it could be that web search has clouded my view of what is importat.

1) Non-nullable types
2) DSLs
3) Metaprogramming is important
4) MapReduce [or parallelism is all about the programming model]
5) Statistics
6) Column-Store DBs have a place, but so do RDBMS's
7) Convention vs Specification
8) Patterns are not a silver bullet, nor are functional languages
9) Type inferencing is a benefit
10) XML was a cruel joke (yes, it goes in both)

Please feel free to comment if you disagree or want to add.

Wednesday, January 06, 2010

My new browser

For years I have been a faithful IE user. I say faithful and not loyal because I have only used it because it suited my needs and other browsers were too cumbersome or clumsy to hold my attention for long.

FireFox is infinitely customizable, but it never felt like a well designed app - it felt clumsy to me. Plus, it always had problems rendering tables in an appropriate manner.

Chrome is sleek, fast and elegant, but in many cases it just doesn't work. I'm always finding some site that it doesn't render quite right, a video that it won't play, or a simple customization that doesn't exist.

I've also tried Safari from time to time, but never long enough because I never saw any advantages over IE.

However, a new version of an old browser has impressed me so much that I have switched for what I hope is good. Opera version 10.10 is an amazing piece of art. It renders fast and correctly, plays all the video sites I need (though I did have to "Mask as FireFox" for Netflix!), and has the simple customizations I want. For instance, I can use the address bar to search on various search engines (I'm not limited to Google like I am with Chrome.) If I want to search Bing, then I just type "b " followed by the search string into the address bar and viola! it goes to Bing and searches (I did have to manually set this up, but it was quick and easy). Other niceties include movable tabs for web pages with hover preview and a "speed dial" page that is much nicer and more customizable than Chrome's.

My requirements are simple. I want a browser that is easy to use, works on the sites I frequent, and has simple customizations. I don't want to spend a lifetime studying all the intricacies and hunting down new plug ins. I just want a browser that works. Opera satisfies those needs and left me happier than I was before. Give it a try and let me know if you feel the same way!

Saturday, September 05, 2009

C# Timings

Recently, I was adding a bit of debug code to measure how long it took to run various parts of my program (yes, I know a profiler would be more accurate, but I just needed a rough estimate). So, I had 3 or 4 areas in my code where I did something akin to

TimeSpan timer = new TimeSpan();
DateTime startTime = DateTime.Now;
Type1 rval = DoIt(a, b);
timer += DateTime.Now - startTime;

Firstly, this code is ugly. I'm obviously doing many different things here: timing code, calling a function, storing it's result, etc.... It would be much better if I could wrap the timing code into its own function. So, I esentially want something like:

TimeSpam timer = TimeIt( () => DoIt(a, b) );

The code for TimeIt is simple to write

TimeSpan TimeIt(Action a)
DateTime startTime = DateTime.Now;
return DateTime.Now - startTime;

However, that doesn't save the return value of DoIt, so that is useless for my purposes. I need TimeIt to return the value from DoIt. To do this, I make TimeIt a generic method and have it accept a function instead of an action. I pass the TimeSpan in as a reference argument. The calling code looks like

TimeSpan timeSpan = new TimeSpan();
Type1 rValue = TimeIt(() => DoIt(a, b), ref timeSpan);

The TimeIt function looks like

public static T TimeIt(Func f, ref TimeSpan timeSpan)
DateTime startTime = DateTime.Now;
T rVal = f.Invoke();
timeSpan += DateTime.Now - startTime;

There, now we have a simple and generic way to time a single method that returns a value. If you wanted to go further, you could create a class that held the TimeSpan value so that you wouldn't have to pass it in as a ref, but this worked for my needs and was clean enough so I stopped here. If I need this code again, I'll refactor it into another library and perhaps into its own class. Until then, I'll enjoy the cleanliness and conciseness.

Monday, July 20, 2009

A letter to my representative

I sent a letter to my representative regarding the health care bill and would like to repost it here for others to comment.

Hello Representative Inslee,

I wanted to write a quick letter in opposition to the upcoming health care reform. Believe it or not, health care is undergoing a major revolution today. The problem is that the traditional "insurance" programs of the past are becoming harder to use because people have confused "insurance" with "comprehensive coverage". Allergy medicine, maintenance meds, etc... are not part of any insurance program. Insurance is responsible for covering major and unexpected medical issues. Over the last 5 years, more insurance companies are coming to terms with this and are inventing things like Health Savings Accounts, which, though unpalatble to many consumers, are a cost effective means of giving consumers choice over how to best spend thier medical allowance. Unfortunately, the private sector has not sorted everything out yet, so now is a very inopportune time for the government to intervene. The government is not innovative nor is it cost effective. Instead, it simply throws constiutents money at a problem with little effect until they stop complaining about it. I do recognize the importance of helping our elderly and needy, but I also recognize the precarious position of the american economy and the health care industry. Despite Obama's claim, now is NOT the time to act. Now is the time to rely on capitalism and market forces to sort out what the future should hold and then fit our current medicare and medicaid plans into that future. The economy, the health care industry, and your constituents need you, Representative Inslee, to be a pillar of salt in today's wax and wane congress. You have been in the past and I trust you will be again.

Thanks for your time,
Tanton Gibbs
Redmond, WA

Sunday, June 28, 2009

What should Yahoo! do?

Yahoo!'s CEO, Carol Bartz, has stated firmly that Yahoo! is not a search company. In fact, Yahoo!, she states, is much closer to a portal. The goal is not search, but editorial comments and a local feel. A portal, if you will, from a major media/technology firm. Unfortunately, in the coming years, portals will be less and less necessary as people will get their news from a swath of algorithmically mined sources across the social media landscape. I'm afraid the era of Yahoo! dominance has ended and will not return.

Like IBM in the 90's, Yahoo! must redefine itself. Yahoo! must sell the mills.

Again, like IBM, who has become a major integrator, and Kimberly-Clark, who has become a consumer goods powerhouse, Yahoo! must set out on the next phase of it's life - it must enter and dominate a new area or be relegated to a technological side show until it dies. But what should it pursue? To answer that question, we need to look at its strengths and products, especially those that are hard to mimic, such as those related to its core technology.

Yahoo! has world class data centers, meaning they can store and process data cheaper than anyone else (except, perhaps, google). Yahoo! also has a data processing platform that allows it to analyze web scale data quickly and efficiently. It's also beginning to build a dataflow language which allows developers to be productive. Finally, Yahoo! has a respected research organization which keeps it at the forefront of areas such as machine learning and information retrieval.

The question then becomes: "What business needs massive computational power, data storage and processing ability, and makes heavy use of machine learning and information retrieval?" The biggest one I can think of is data marketing. Analyzing billions of consumer and business records as quickly as possible and making decisions on the fly is what data marketing is all about.

Imagine a person walking into an electronics store. Currently, if the person buys something he may get a coupon to promote his buying something more, later. However, this is suboptimal for two reasons. The simplest reason is that the coupon may be unnecessary. The patron may have been planning to return even without the coupon and so the coupon represents wasted revenue. The second reason is that the coupon may be too late. It could be that if the patron would have been given the coupon on the way in then he might have bought more or upgraded or any other number of things that could have produced more revenue. It could even be that a customer doesn't buy anything at all, but would have purchased if a coupon was given beforehand. The holy grail of marketing is to sell an item to each person at an individualized cost. You want that person to pay as much as possible for the item. If person A will pay $100 for a camera and person B will pay $300 for the same camera then you want to issue the $200 off coupon to person A and no coupon to person B.

Now, imagine a system where a customer is recognized by an image recognition system the moment they walk in. Their data is retrieved instantly and a machine learning algorithm is run to determine what the person is shopping for and what the person is willing to pay. From their online profile and twitter account, the algorithm is able to determine that the person recently broke their camera and is looking to replace one. Using data from a company such as this one the algorithm can tell that they are struggling economically and will want to buy a cheaper camera. However, it also knows from statistics that a coupon for the higher priced camera has a good probability to make the consumer stretch his budget and go for the "prestige" item. A few more checks against the data center reveals that the current store location has excess inventory of the higher priced camera and therefore the algorithm decides to dispatch a bigger discount coupon for the better model. The sales attendant walks to the customer and presents the coupon, escorting the customer to the camera aisle. The sale is made and the computer gets an extra volt in its bedtime snack ;-)

More seriously, Yahoo! could perform those computations more efficiently and with better accuracy than an enterprise. Enterprise data centers are not going to reach the efficiency of Yahoo!'s data center. Moreover, enterprise IT programmers are not going to have the time or penchant to do the necessary IR and ML research. Yahoo! is uniquely positioned to do those things; furthermore, since it is dangling on the precipice of disaster now is a good time to bite the bullet and make the change. Not that I expect them to. Change is something that is hard to accept and Ms Bartz doesn't seem like the type to change their core business...if she ever figures out what that is. More than likely the model I express above will be adopted by a new comer...perhaps by these guys.