The ancient practice of putting various monsters in unexplored regions of maps and the phrase based on that, “Here be dragons“, applies still to programming.  Personally, I’ve always had a dragon the size of a moon (or battlestation, if one prefers) on my own mental map in the area of build systems.  Hopefully, this should be a series, with several tutorials succeeding this brief summary of available options.

What is a Build System?

Just a quick introduction for those who are uninitiated into these rgb(0,0,0) arts.  A build system offers a relatively easy way to automate building and packaging of a software system.  While something as simple as a one-line shell script could supposedly be written for smaller projects, this has several problems.  Firstly, it would tend to redundantly and naively recompile objects that have already been built and have not been changed.  Secondly, this has no portability system; that is, it has no way to analyze the host system and find the appropriate utilities and libraries on differing platforms.  There are more reasons, of course, but these are the crux of the matter.

Current Build Systems

Make

Make is one of the oldest build systems, having its first release in 1977 at Bell Labs.  It is extremely simple, but pays the price; it has no configuration system, nor any automatic dependency analysis.  This makes it a decent choice for smallish projects with any advanced portability needs, but most likely you’re better served by a more powerful tool.  However, it should be noted that various projects such as Autoconf (see below) serve to expand this utility.

Autoconf

Autoconf and Automake together form a framework for generating Make scripts.  Autoconf provides the portability configuration system, while Automake will automatically analyze your program structure to determine the order that things need to be rebuilt in.  Unfortunately, on some level, this is merely lipstick on a pig (which is an idiom I used to be able to use without shifting my eyes), and due to the obscure language (m4) used to write Autoconf scripts, this is both a finicky and difficult option to use.  Configuration is slow, and is extremely awkward if you wish to target Microsoft Windows.  Last but not least, it is legendary for being extremely difficult to learn.  It is, however, the most common build system on the Free Desktop.

SCons

I’ll get my bias off of my chest now: SCons is my current favorite build system.  The scripts are written in Python, so you have a very powerful programming language to work within.  The API is a bit less than ideal in some ways, but is still quite usable.  Compilation is fast and portable, as well as being in one step (as opposed to the two-step compilation as used in Autoconf).  The GNOME project is currently considering switching to it from Autoconf.

Waf

Waf is a descendent of SCons, and thus shares the power of Python.  However, it is expanded in several ways: the API is retooled and is more intuitive in design in some ways; the configuration stage has been spawned into its own step; and compilation is quite pretty.  Despite all of this, it does suffer from a lot of API irregularities and absolutely intolerable documentation.  It is also important to note that Waf is unique in the build systems that I’m aware of in that the preferred way to use it is to actually ship it with the application itself instead of using a system-wide installation

CMake

CMake is the build system for KDE 4, and is a very nice and simple build system for projects of any size.  However, this clean and simple design is detracted from by the simplistic (though not to the Make extreme by any means) language used to develop for it.  If you can get past this weakness, however, very nice things lie inside, such as an integrated unit testing framework.  It is worth noting that rather than being a base build system, it instead generates files for the native build system (Microsoft Visual C++ on Windows, Makefiles or KDevelop on *NIX, etc.)

Others

This is where the real dragons are; the previous build systems I have at least some experience with, but these are build systems I have only heard of.  Despite this, I would feel remiss in my duties to you the reader if I did not at least mention some of the lesser-used options.

• Apache Ant is a build system is aimed at Java projects, and has its project files written in XML.
• Perforce Jam appears to be a C/C++ build system with a syntax reminiscent of Make, but with portability features, control structures, and automatic dependency ordering.
• QMake is a Makefile generator not unlike Autoconf, only with a much easier-to-learn syntax.  It is part of the QT toolkit.

This list is by no means complete.  If you have a favorite build system, please do mention it in the comments.

Edit: The people on Reddit informed me that some of my questions go against the idea that premature optimization is a bad practice.

Introduction

“Listen. Easy now,” said the old man gently. “I know, I know. You’re afraid of making mistakes. Don’t be. Mistakes can be profited by. Man, when I was younger I shoved my ignorance in people’s faces. They beat me with sticks. By the time I was forty my blunt instruments had been honed to a fine cutting point for me. If you hide your ignorance, no one will hit you and you’ll never learn. [...]”

–Fahrenheit 451

Newbie programmers, when set to complete task, will often complete the task in the worst way possible. Of course, most programmers graduate beyond newbies. This post will detail some questions that newbies can ask in order to build better programs.

The below questions are things that all newbie programmers should be asking themselves so they can produce good programs. The questions can also be used as a very simple litmus test to see whether a programmer is a completely lost newbie or not. The Five Essential Phone-Screen Questions has a set of questions that help find good programmers.

<insert image here>

Photo credit: Flickr user anomalous4

When coming up with ideas for solutions

1) What patterns or algorithms can help me solve the problem?

Computers work well with numbers, and numbers are full of patterns and sequences. A simple example of a sequence is the Fibonacci sequence, where every number is the sum of the previous two numbers (1, 1, 2, 3, 5, 8, 13…).

A simple and useful algorithm is the Sieve of Eratosthenes, which is used to create lists of prime numbers.

2) Has somebody else already solved this problem or a similar problem?

Google called; they said they have the answer to your problem.

For those that can handle looking at the possibly messy code of others, looking online for open source code that can partly, mostly, or completely fill a need is a good idea.

A somewhat recent example is that I was looking for an open source Digg clone in PHP to make slight modifications to, and managed to find Pligg. Unfortunately, Pligg didn’t manage to fit my needs, but I managed to find PHPDug, which I like better.

3) What are potential issues I could run into when solving this problem?

It is important to think ahead about what issues could be faced when solving a problem.

For an important website, the power of the hardware, the power of the software, and the precautions taken for data loss and downtime, and more should be considered.

When looking at possible solutions

The first group of questions are things that newbie, or n00b, programmers should ask themselves when looking at a source code or a way to solve a problem.

1) Is this method fast as it can be?

Writing fast programs is a very important thing. Too many people are not patient enough for slow programs, and writing programs that can easily be made faster is not going to make users happy.

2) Is this method secure?

I sometimes wonder if it would be more beneficial to beginning developers Baller shouted “Security!” instead of “Developers!”.

Some common, but dangerous security mistakes that n00bs make are:

1) not escaping user input

2) not using file permissions properly

Chmodding everything is 777 is bad. Very bad.

3) using improper encryption to store things

3) Is there a simpler way of solving this problem?

If a person has two solutions to solve a problem, that person should always choose the simpler solution. The more complexity there is in a system, the more difficult it is to use and maintain that system.

4) Is this method scalable?

Creating software that works perfectly, with the exception it not being scalable at all, is setting up the programmer(s) for some major headaches down the road. A classic example is Twitter’s severe instability a few months ago.

Final notes

All programmers ought to subscribe to Coding Horror, a blog with far more useful content than you’ll ever find in this waste of disk space.

Also remember to ask questions on mailing lists, forums,  and so forth, but only after several hours of experimenting with Google keywords.

I had cause of late to convert an integer into a string in C.  My research indicated that there was no standardized function to do this, and thus the most portable thing to do was to write my own algorithm.  After fiddling with numbers and masks and such things, I came up with the following core algorithm:

#define CONVERT_DIGIT(mask, n, offset)    (( n/mask - ( n/(mask*10))*10) + offset )

This algorithm may not be as efficient as it could be, but I’m fairly happy with it given that normally I dodge anything with even a distant correlation to mathematics as if it were the plague.  mask is a power of your number system base b; most of the time, this is going to be a power of 10.  n is the number you want to convert.  offset is used to offset the resulting integer to an ASCII equivalent; this could actually be hard-coded as 48.

Given that the number of digits in n is L, you need to initialize mask to b^L-1.  Then run a loop that for each digit in n runs CONVERT_DIGIT( mask, n, 48) and then divides mask by b for the next iteration.

Caveats

While the algorithm itself should be O(L), the actual output is going to have some worthless zeros at the start for most values of n that may have to be stripped.  In addition, I’m not going to explain how to create a string in C, or how to implement this in other languages.  You’re on your own there.

Also note that while the premise should be solid and I haven’t seen a situation where it fails, I disavow all responsibility for algorithmic failures and weaknesses.

EDIT: Daniel Bruce informed me that the function sprintf() would do the job just as well, only should also work for floating point numbers and is more flexible.  I wish I had known about that before I had spent the time to write this algorithm.

Introduction

When you think about it, having a computer analyze your interests and tell you other things that you might be interested sounds seriously cool. But a lot of recommendation engines hardly ever actually find anything interesting for human users. This post will cover some of the issues that software developers face when trying to write a recommendation engine, and how to reduce the impact of those issues.

Developers making recommendation engines get annoyed by

1. Speed and scalability

A lot of recommendation engines are for websites such as Amazon. The recommendations have to be served up quickly. One way to solve this is by not generating the recommendations when the page with the recommendations is being requested. The recommendations can be generated at an earlier time and, on page load, can be fetched with database queries or similar.

Another way to solve this is to use the client’s processing power to either generate the recommendations. For a web application, Javascript can be used to generate recommendation, as this Delicious recommendation engine does.

There is also the issue of scalability. The system has to be able to quickly generate recommendations for large amounts of users. It would be sad for a recommendation engine to fail, Twitter style.

2. Malicious folk

This is an issue when having a recommendation engine that deals with user generated content. It doesn’t take long to find a Youtube video with literally hundreds of unrelated tags in the hope of tricking users to watch the video.

For some recommendation engines, this isn’t a problem, but for many, it can be difficult. For the Youtube example that I gave, videos with copious amounts of tags could be ignored by the recommendation engine because it is highly doubtful that nearly every single one of those hundreds of tags are relevant.

3. Little data

It would be snap-easy if all the users that your recommendation engine will analyze had large pools of data clearly describing what the users do. It is very difficult to give recommendations based on little data.

One way to attack the little data issue is to not give recommendations until enough data from the user is collected. This results in the user having to do work and wait for the recommendations to appear, which usually isn’t a good thing.

Another way is to make the recommendations based on the data of others. Recommendations popular among the vast majority of other users (think Digg front page) could be made.

4. Nothing good to recommend

Recommendation engines work really well for big sites such as Amazon, Youtube, Digg, and Delicious because those websites have a lot to recommend. It doesn’t matter what the user’s interests are, because those websites probably have to have something that would interest the user.

Smaller applications typically do not have as much to recommend, unless they are drawing upon the content of larger applications.

In order for the programmer to solve this, more content must exist in order so at least something interesting can be recommended to the user. If the content is user-generated, encourage users to generate more content by providing some sort of benefit for creating more content.

5. Duplication

Youtube is a great example of content duplication. Multiple people will frequently upload the same copyrighted content, creating duplicate content on the Youtube servers. How can a recommendation engine give relevant recommendations, but not have the recommendations be so relevant that the user sees duplicate content.

In the case of Youtube, having the recommendation engine ignore suspiciously similar video titles might help reducing the duplicate recommendations.

Recently I’ve been playing with Midori in the wake of being informed that it’s now an Xfce project.  A nice enough browser, albeit quite solidly still in the development stage.  However, on systems such as mine that lack GLib 2.16 (and therefore GIO), there is a compilation error.  Specifically, there are two problematic zones.  The first is a confusion in the macros that check for GLib 2.16 and GtkSourceView that result in a failed compile if you have an older version of GLib in combination with GtkSourceView. Secondly, Midori will attempt to use GLib 2.16 symbols without first checking if the user has GLib 2.16.

So I wrote a patch and submitted a bug report.  The bugs are now fixed in git master, but for the existing stable release (0.19), you can find my patch at the relevant bug report.  To apply it, move it into the Midori 0.19 directory and then run

cat midori-glib216.patch | patch -p1

A lot of people are out in the world, looking for something. These people are not looking for a lost dog or wristwatch, but these people are looking for something more valuable; ideas. Ideas are extremely valuable now, and they always have been. Nowadays, ideas have changed slightly. They are more likely to involve software and vast server farms. A lot of people are wondering, “How do I generate an idea that will be popular and generate income for me?”

I don’t claim to be an expert, but blogging allows people to pretend to be experts on various topics, so I’ll take a shot at explaining how to make a popular application. Remember that other negative things, such as the application having a horrible interface, may reduce the effect of these tips.

How to Make a Popular Application

1) Create something that nobody needed before, but now that you have showed them, they want it.

This can be called the Twitter effect. In the history of communications, using 140 character messages to communicate isn’t what people thought that they really needed. Now, some people are crazy about microblogging.

A huge advantage in creating something that nobody previously thought was needed is that in the beginning, the creator has no competitors. Twitter has had massive success while competitors are not close to Twitter’s user count. Of course, Twitter’s mistakes have users flocking to FriendFeed, identi.ca, and Plurk.

2) Create something that can easily be used in many, many ways.

I’m going to use Twitter as an example again. People are constantly finding new and creative ways to use Twitter. Not everybody is just using it to broadcast what they had for breakfast. CNN is using Twitter so people can quickly be notified of breaking news (find CNN’s Twitter account here). Comcast is using Twitter to interact with customers (find Comcast’s Twitter account here).

2.1) Create something extensible

Both Twitter and Firefox have had a lot of success due to the fact that both are extensible (in slightly different ways). Twitter’s API allows developers to create things such as Twhirl and Summize (the latter being acquired by Twitter recently).

When you make something extensible, it makes it much easier to use it in many ways. Firefox is a great example of having an application with many uses through extensions. The Firefox extension ScrapBook can make Firefox into a primitive web scraper, Twitterfox gives Firefox the features of a Twitter client, and I could keep going with good Firefox-related examples.

3) Create something that the user thinks saves time.

They say time is money. Interestingly, helping decrease the amount of time it takes to get something done can generate you money. Notice that the title of this tip doesn’t say, “Create something that saves time.” If an application saves time, but potential users think it will waste time, then it does not matter that it saves time.

Conversely, if your application increases the time it takes to get something done, but the user thinks that time is being saved, you will still generate money. The problem with making the user think that time is being saved when time is being wasted is that it does not take very long for the users to figure out that time is not being saved at all. What’s that? It’s the sound of the customers walking away with their money.

How does this relate to Twitter? Now, a lot of Twitter users would simply say that Twitter is a time-wasting social network. Still, if a user thinks Twitter is a time-saving service, the user will use it as a time-saving service. Of course, the user might discover that Twitter isn’t saving them any time and then stop using Twitter. The key here is to use either Twitter itself or Twitter’s extensibility creatively.

An example of applying GTD (Getting Things Done) to Twitter is to creatively use the SMS features. Depending on the user, it may or may not save time. If you spend enough time thinking about it, more ways to use Twitter and Twitter applications can be thought up.

Just now, I finished watching an episode of Nova scienceNOW (yes, that’s how it’s capitalized). Covered in that episode is the work of Dr. Hany Farid and his work to develop software to detect photoshopped images.

One technique that he demonstrated with software is to detect parts of images that are identical. This is to detect whether the clone tool has been used on parts of the image.

Another technique demonstrated is to detect where light is coming from. If two people from two different images are cobbled together into one fake image, it is highly possible that the light sources in the original two images are in different places. This means that the two people are illuminated from different directions, and this is shown on the person. If one person is being illuminated from the left side, and another is being illuminated from the right side, you know that the image was originally two images that had different light sources.

Another way to see the light source, assuming that the image you are testing has at least two people with clearly visible eyes, is to analyze the shape and location of the light being reflected off; that is, the specular highlight. As the eye can act like a mirror, you can see a little bit about the light source, such as the shape of the light source. You can also see how the light source is hitting the person. If one person has a reflection of a square light source (like from a camera flash), and another person has a reflection of a circular light source hitting the person at a completely different angle, there is a good chance that the photo isn’t completely real.

Want to learn more about Hany Farid? You can check out (I grabbed all these links from here):

• Hany Farid’s home page
• Digital Forensics: An Interview with Dr. Hany Farid
• Adobe Tackles Photo Forgeries
• A Conversation With Hany Farid: Proving That Seeing Shouldn’t Always Be Believing
• Digital Doctoring: How to Tell the Real From the Fake (PDF Warning)

So, what’s your prediction on the future of the Internet, photography, and digital photo manipulation?

I just spent today spending my time (I’m feeling redundant) with an interesting little app, Scratch. It’s a cool little application that introduces children and early teens to programming and animation.

Normally, I haven’t ever realy gotten the point of programming languages for children. I remember trying out SiMPLE to see how it compared to Python, and I wasn’t impressed. Scratch is actually pretty interesting and I would recommend it as an application to install on the computers of any young relatives you have. It’s available for Windows (appears to work on Vista), Mac, and Linux (via an unofficial installer).

Now, what are the advantages of using Scratch over some language like Python or Javascript? And is Scratch a powerful programming tool?

Well, Scratch is centered around building animations and games quickly. Plenty of children would have an easy and fun time creating games in Scratch. Doing similar things in Python or Javascript take more difficulty.

So, what does Scratch look like? A screenshot is below. Click on it to view it full screen.

Scratch has a graphical display of the code, but contains many control structures that will be familiar to programmers. Some examples are if/else, for (or rather some weaker constructs that do things that for is capable of), and exit.

Of course, many other programming languages have that and more, but the great thing about Scratch is that it has all this and is easy. Anybody can pick it up and start using it.

So, if you have access to kids, admin access to the kids’ computers, and the Internet on those computers.

I write little tools to help me all the time. An example of this is “Headliner” (source code coming soon). Headliner is a small prototype web app that takes in an essay title or newspaper headline and gives it the right capitalization. To save space, newspapers only capitalize the first word in each sentence in the headline.

Essay titles capitalize every word except for prepositions and articles (a, an, the). Headliner knows these rules and applies them on the headlines that you enter into it.

Note: This is a post restored from the previous, multi-user installation of WordPress. I didn’t bother changing the date and time to when I actually wrote this.

This is a series of posts that I will make about how to make (or make something that looks like) AJAX-style code. The basic idea behind AJAX is to build a website that runs several small HTTP requests to get the information you need instead of reloading the entire page once.

The first part of the series will tell you how to write HTML and Javascript that makes it look like you are using AJAX. It is a cheap trick that can be easily discovered and probably nothing really new. However, it is handy when you need to develop an AJAX-like website really quickly and don’t have the time to debug.

You can see the example here. View the source or use the code browser to see how it works.

UPDATE: I linked to the CE Code Browse in the above sentence if you prefer to view the source that way. I also fixed the scrollbar bug that voyagerfan5761 pointed out in the comments.