Sunday, March 18, 2012

The Evolution of the FOR loop

The most widely and commercially used languages today are largely based on the imperative and structured programming paradigms and many have a direct and strong roots in the C language of the early seventies.

Even though there seems to have been little fundamental change in main stream programming languages over the  last 40 years, there have been subtle shifts in usage patterns, even for things as simple and fundamentally low-level as doing some things repeatedly or in a loop.

As a perfectly and randomly useless example to illustrate the evolution of looping, we are creating a list of squared numbers from the positive members of an input list.

In C or any similar imperative language of its time, the most basic way to do something like this would be something like:

out_size = 0;
for (i = 0; i < in_size; i++) {
  if (a[i] > 0) {
    b[out_size++] = a[i] * a[i];
  }
}

Languages like C++ and Java, which includes a standard library of higher level collection data types, this basic pattern of an indexing counting loop is typically replaced by some sort of iteration support of the input collection.

for (std::vector<int>::iterator it = a.begin(); it != a.end(); ++it) {
  if (*it > 0) {
    b.push_back(*it * *it);
  }
}

Which is still basically the same counting loop disguised as type-safe pointer arithmetic. Java 5 offers a slightly more elegant syntax for iteration of types supporting the Iterable interface and the new for-each variant of the for loop:


for (Integer num : a) {
  if (num > 0) {
    b.add(num * num);
  }
}

In Python, this idiom would read like:

b = []
for num in a:
  if num > 0:
    b.append(num * num)

However for usage patterns like this, which are essentially transforming an input iterable into an output, some languages also support a more functionally inspired idiom. In Python originally using the map and filter functions:

b = map(lambda x: x * x, filter(lambda x: x > 0, a))

And since the introduction of generator expressions and list comprehensions as:

b = (num * num for num in a if num > 0)

The advantage of the functional model is that in its purest forms, it allows for deferred evaluation, has generally no side effects, describes more specifically the nature of the operation than would the use of general flow-control structures and thus could more easily be parallelized by a smart runtime.

A more functional style is also possible in Java using some 3rd party libraries as Iterables from the Guava library. However without support for some sort of compact lambda function definition in current Java, this would result in significantly more complex and probably less readable code than the currently most standard variant using the for-each iteration. Until then, even the authors of the Guava library recommend to not use a functional idiom for most cases...

Saturday, March 3, 2012

Learning Computers

On Feb 29, the Raspberry Pi foundation launched the sales of a $25 credit-card sized computer, which sold out in minutes. The goal of the Raspberry Pi is to stimulate computer literacy education in schools, inspired by the impact which the BBC Micro computer had on schools in the UK - compared with a similar wave of popular home-computers elsewhere - e.g. the Commodore 64.

I understand the elements of nostalgia of people growing up around the 1980ies for the time when computers where new and exciting. Around that time, I thought myself programming in C and M68000 assembler on a Commodore Amiga and probably learned more in basic understanding about programming and computer architecture than during the years afterwards in engineering school. The home-computers of that era were hackable enough to encourage tinkering and simple enough to allow really getting to the bottom of how they worked. The gap between what could be produced by determined hobbyists and professional software publishers was not that great.

By today, computers have become so ubiquitous and commonplace that they are no longer considered exciting. Students today use computers in the form of PCs, tablets, game consoles or smart-phones for researching or writing as naturally as we used to use books, pen and paper or pocket calculators. But many of todays computer platforms are also much more complex, sophisticated, closed and don't invite to tinkering with the underlying technology. Children today are growing up in a way much more computer literate (as users) than any generation before, but may know or care much less about how computers actually work than their parents generation.

Maybe there is a natural cycle of when technology is attractive and inviting to hobbyists. While in the 60ies many teenage kids would be tinkering with old cars in the backyard, the grease monkey sub-culture has largely come out of main-stream fashion, as cars today just work and are sealed black-boxes which don't allow for much tinkering without access to proprietary diagnostic systems. For the same reason, tinkering with computers might have been a think unique to the end of the last century and might not come back despite efforts like the Raspberry Pi project.

For those of us interested in getting today's youth generation interested in information technology, the question remains on what would be the most suitable way. Maybe I am myself blinded by nostalgia, but I am optimistically hopefully for the impact of something like the Raspberry Pi, as it seems both sufficiently accessible and hackable. The bare-board without a case may help to encourage an interest to go beyond the surface of how computers work - even though the highly integrated SoC architecture allows less so than ever to understand computer architecture from a visual/physical reality.

From my limited experience, it seems important to avoid creating dumbed-down "toy technologies" without real-world usage when trying to get children and young people interested in technology. Instead, we should encourage the use of real-world technologies and platforms which are easily accessible, have a low barrier to entry learning curve and are open and flexible enough to encourage experiment for some applications which are cool and intriguing for today's generation.

This chart from the Economist gives and indication that today there is a similar frenzied innovation in mobile computing platforms as there was in personal computing in the 1980ies.

Maybe today's generation would more likely tinker around with a mobile device than a desktop computer and programming education should start with the development of apps for mobile devices. Both Android and iOS platforms allow for relatively easy application development, even though the device platforms on which users can easily get their hands on tend to be closed and locked down for a variety of reasons. Android is free and open-source, but only to those who own a cellphone factory and not to the end-user who buys a smart-phone, maybe even subsidized through a carrier. Also the tool-chain for mobile development is quite heavy and requires access to a PC typically - self-hosted development on a mobile platform so far is not typically an option.

Another obvious choice would be web applications. The browser is increasingly becoming the real platform for which applications are written, abstracting hardware and operating system differences. Cloud platforms like Google AppEngine and similar alternatives have essentially a very low barrier to entry in both cost and complexity for building and running a web application on the Internet. The modern browser standards with HTML5, CSS & JavaScript present a powerful and feature rich environment for application development with a high level of abstraction. However, the level of abstraction is so high and so far removed from the physical reality of the underlying hardware that web programmers may never need or want to understand how computers actually work.

Another area with lots of exciting potential might be robotics. Robotics encourages or even forces a confrontation with the physical reality of the systems we are developing. Given the improvements in miniaturization and power efficiency of computing hardware, there is much exciting activity and progress in the field across commercial development, cutting edge academic research and even hobbyist activities. Givent the combination of low-cost, low-power small size for a decently powerful compute platform, robotics might be the real sweet-spot for the new Raspberry Pi board in computer literacy education.

From my experience as a judge on a FIRST robotics competition, kids of a certain nerdy/technical inclination can certainly be excited about building robots. I would love to see integration and interoperability of the Raspberry Pi board e.g. with the Lego Minstorms robotics toolkit.

Friday, March 2, 2012

Tiny, low-cost Linux Device

Recently I was looking around for cheapest, smallest device which easily can run linux and which can be bought in small quantities down to one. The particular application in mind was to build a linux based print-server which exposes legacy USB or network connected printers via Apple AirPrint for iPads and iPhones or Google CloudPrint for ChromeBooks or some Android devices and maybe could provide some other services to such thin-client, "cloud-top" devices (local file server and/or backup, wifi/network gateway etc.).

A few years ago, I had a first compact, fan-less home-server in the form-factor of a mac-mini, i.e. about the foot-print of the optical drive it contains. Like the mac-mini, this was basically a compact PC, made largely out of laptop parts.

It seems that the clear winner in terms of cost today is the new Raspberry Pi board at $25/$35, whose launch this week caused an Apple-style opening-hour stampede on the online store selling its first production batch. It is a minimalist bare-board computer, about the size of a credit-card and based on a Broadcom BCM2835 embedded multi-media engine with a 700 MHZ ARM core. The Board a USB port/ HDMI & composite video output, some low-level IO (GPIO, I2C, SPI etc.) as well as 10/100 Ethernet port on the $35 version. Not included in the price is an external 5V micro-USB standard cell-phone power-supply, an SD card and maybe a case. With these extras the final price would likely be in the $50-$100 range. The heavy emphasis on video would make the Raspberry Pi ideal for applications which require a TV connection or some other form of display.

An alternative for less visible, network connected servers could be to use a plug computer. They seem to have typically a beefier CPU core, more networking options and often come in a case with integrated power-supply and wall-plug, so that they can be plugged directly into a power-outlet. Prices for a single unit seem to range from about $100 to $250.

However, since brand-new AirPrint capable printers are starting at around $100 as well, this project seems not worth its while, at least not just for re-using low-end home printers, e.g when moving to an iPad as the primary home-computer.