Maths and Programming: Whence Recursion?

As a manager in the software engineering industry, one of the things that I see on a regular basis is a general lack of knowledge from less experienced developers (not always "younger"!) with regard to the foundations of computing and the several related fields of mathematics. There is often a great deal of focus on what the hottest new thing is, or how the industry can be changed, or how we can innovate on the decades of profound research that has been done. All noble goals.

Notably, another trend I've recognized is that in a large group of devs, there are often a committed few who really know their field and its history. That is always so amazing to me and I have a great deal of admiration for the commitment and passion they have for their art. Let's have more of that :-)

As for myself, these days I have many fewer hours a week which I can dedicate to programming compared to what I had 10 years ago. This is not surprising, given my career path. However, what it has meant is that I have to be much more focused when I do get those precious few hours a night (and sometimes just a few per week!). I've managed this in an ad hoc manner by taking quick notes about fields of study that pique my curiosity. Over time, these get filtered and a few pop to the top that I really want to give more time.

One of the driving forces of this filtering process is my never-ending curiosity: "Why is it that way?" "How did this come to be?" "What is the history behind that convention?" I tend to keep these musings to myself, exploring them at my leisure, finding some answers, and then moving on to the next question (usually this takes several weeks!).

However, given the observations of the recent years, I thought it might be constructive to ponder aloud, as it were. To explore in a more public forum, to set an example that the vulnerability of curiosity and "not knowing" is quite okay, that even those of us with lots of time in the industry are constantly learning, constantly asking.

My latest curiosity has been around recursion: who first came up with it? How did it make it's way from abstract maths to programming languages? How did it enter the consciousness of so many software engineers (especially those who are at ease in functional programming)? It turns out that an answer to this is actually quite closely related to a previous post I wrote on the secret history of lambda. A short version goes something like this:

Giuseppe Peano wanted to establish a firm foundation for logic and maths in general. As part of this, he ended up creating consistent axioms around the hard-to-define natural numbers, counting, and arithmetic operations (which utilized recursion).  While visiting a conference in Europe, Bertrand Russell was deeply impressed by the dialectic talent of Peano and his unfailing clarity; he queried Peano as to his secret for success (Peano told him) and them asked for all of his published works. Russell proceeded to study these quite deeply. With this in his background, he eventually co-wrote the Principia Mathematica. Later, Alonzo Church (along with his grad students) sought to improve upon this, and in the process Alonzo Church ended up developing the lambda calculus. His student, John McCarthy, later created the first functional programming language, Lisp, utilizing concepts from the lambda calculus (recursion and function composition).

In the course of reading between 40-50 mathematics papers (including various histories) over the last week, I have learned far more than I had originally intended. So much so, in fact, that I'm currently working on a very fun recursion tutorial that not only covers the usual practical stuff, but steps the reader through programming implementations of the Peano axioms, arithmetic definitions, the Ackermann function, and parts of the lambda calculus.

I've got a few more blog post ideas cooking that dive into functions, their history and evolution. We'll see how those pan out. Even more exciting, though, was having found interesting papers discussing the evolution of functions and the birth of category theory from algebraic topology. This, needless to say, spawned a whole new trail of research, papers, and books... and I've got some great ideas for future blog posts/tutorials around this topic as well. (I've encountered category theory before, but watching it appear unsearched and unbidden in the midst of the other reading was quite delightful).

In closing, I enjoy reading not only the original papers (and correspondence between great thinkers of a previous era), but also the meanderings and rediscoveries of my peers. I've run across blog posts like this in the past, and they were quite enchanting. I hope that we continue to foster that in our industry, and that we see more examples of it in the future.

Keep on questing ;-)

Probabilistic Input for uTouch?

Well, it seems to be the season for a flurry of multi-touch posts. Guess that's helped along by the release of uTouch in Maverick and next week's Ubuntu Developer Summit multi-touch buffet :-)

One of the talks that John, Mark and I enjoyed greatly at UIST was Julia Schwartz's presentation on "A Framework for Probabilistic Input". Julia's an HCI PhD student at Carnegie-Mellon and works in their exciting dev lab. The UIST paper was written by Julia, Professor Hudson, Professor Mankoff, and Andrew Wilson (the latter of Microsoft Research).

One of the reasons I was personally so deeply appreciative of the paper was that when we were building the uTouch framework, Henrik Rydberg and Chase Douglas brought up issues around input uncertainty, and started proposing ways that might be employed to counter this. Getting plugged into folks who are working on this actively and thoroughly is phenomenal.

Since UIST 2010, the uTouch team has been in contact with Julia, sharing ideas and asking questions. Today we had a call with her and Professor Scott Hudson; as such, we have now started exploring possible avenues of development for probabilistic input support in uTouch. Scott and Professor Jen Mankoff will be attending part of UDS this year, and we've set up a session where they can share their research with us and engage in discussions, Q&A, etc., about it, and explore ways in which we can start moving forward on this in Ubuntu (and Linux in general).

The UIST talk slides and related paper are available here:

• https://wiki.ubuntu.com/Multitouch#Probabilistic%20Input

Ultra Large-Scale Systems: An Example

The ULS Series

• Required Reading: Ultra Large-Scale Systems
• Ultra Large-Scale Systems: An Example

Background

My interest in this topic is as old as my love for science fiction. As a child who had not only just started teaching himself to program but had fallen deeply in love with I, Robot, I consumed everything I could by the Master of the Art himself, Isaac Asimov. Inevitably, an endless steam of science fiction began flowing into my brain: the harder the science, the more cherished it was.

Then came the discovery that computers could actually talk to each other. Holy network, Batman, that changed everything! Oh, how I lamented my Kaypro II's inability to dial out. Science fiction novels began touching on this aspect of technology more and more frequently, while the Internet began taking shape in the "real" world around us. Now, look at it. Regardless of the mess and chaos, it's really quite amazing: beowulf clusters, distributed computing, cloud services, and of course the Internet in general. These advances are actually quite mind-blowing when we take the time to examine them from a historical perspectve.

A lot has changed since those early days of the network. The past 10 years or so has seen the beginnings of a trend with regard to large systems. Certainly my views on the future of networks (and services that utilize them) have been pretty consistent:

• In Praise of Evolvable Systems (2003)
• Dinosaurs and Mammals (2004)
• Evolving Networks (2004)
• Everything as a Distributed Resource (2004)
• The King is dead! Long live the Kinglets! (2005)

As I indicated in the more recent ULS blog post, I have been exposed to some excellent resources for ultra large-scale systems. For some of those I recently provided links, and others I will be referencing in future posts.

Due to their nature, ULS systems pose interesting open source collaboration as well as business opportunities. They entail a massive collection of excellent problems to solve that cannot possibly be completely addressed in the next 6-12 months (where so many projects and businesses tend to put their focus, for obvious practical reasons). As such, there are a great number of research and development areas -- plenty for everyone, in fact. In this series of blog posts, my goal is to expose a wider audience to the topics and encourage folks to start thinking about both interim solutions as well as potential long-term ones.


Characteristics of a ULS

Let's start of with some semblance of a definition :-) What constitutes a ULS system? Here are some characteristics given by Scale Changes Everything:

• an unbelievable amount of code (on the order of trillions of lines of code)
• immense storage needs, network connections, processing
• lots of hardware, lots of people, lots of purposes
• decentralized components
• created by aggregation, not design
• unreliable components, reliable whole
• ongoing and real-time upgrades, changes, and deployments
• lots of functionality, likely in a focused area of concern

Here's an illuminating quote from Richard Gabriel's Design Beyond Human Abilities presentation:

The components that make up a ULS system are diverse as well as many, ranging from servers and clusters down to small sensors, perhaps the size of motes of dust. Some of the components will self-organize like swarms, and others will be carefully designed. The components will not only be computationally active but also physically active, including sensors, actuators...

Sounds like pure science fiction, doesn't it? Think about it, though. Is it really? Divmod's friend Raffi Krikorian co-wrote this paper at MIT. Check out the cheap network node that's smaller than a fingertip. At that size, hundreds of them would be innocuous. In a few years, we could have thousands of them in a room without even knowing it. Within a single home we could have the equivalents of what today are campus or regional networks. We probably can't even wrap our heads around how big these systems will be. But there is plenty of precedence for such natural short-sightedness. From Raffi's (et al.) 2004 paper:

The ARPAnet was ambitiously designed to handle up to 64 sites with up to 4 computers per site, far exceeding any perceived future requirement. Today there are more than 200 million registered hosts on the Internet, with still more computers connected to those.

Here are some other choice quotes:

[Internet 0] is not a replacement for the current Internet (call that Internet 1); it is a set of principles for extending the Internet down to individual devices...

An [Internet 0] network cannot be distinguished from the computers that it connects; it really is the computer. Because it allows devices for communications, computation, storage, sensing, and display to exchange information in exactly the same representation, around the corner or around the world, the components of a system can be dynamically assembled based on the needs of a problem, rather than fixed by the boundaries of a box.

We're already building this stuff. It's not science fiction. We may not have swarming, self-replicating nano machines... yet. But we're already heading in a direction where that's not just a possibility; it's a likelihood.

So, we've got lots of code, machines, storage, sensing and people; much of it decentralized. What else do we need? Failure tolerance and maintenance on-the-fly. Check. Finally, a ULS system will have to actually be useful, or it will never get built. Who would want such a thing besides militaries, big governements, and Dr. Evils? Now we start getting to our example: Health Care. But let's not get ahead of ourselves. First, let's examine why the biggest system of networked devices that we know of isn't a ULS system.


Why the Internet is not a ULS System

Most obvious of the criteria listed above, the Internet is not focused on a single or related set of goals; it's used for everything. However, it does meet many of the criteria. From the Carnegie Mellon report:

The Web foreshadows the characteristics of ULS systems. Its scale is much larger than that of any of today’s systems of systems. Its development, oversight, and operational control are decentralized. Its stakeholders have diverse, conflicting, complex, and changing requirements. The services it provides undergo continuous evolution. The actions of the people making use of the Web influence what services are provided, and the services provided influence the actions of people. It has been designed to avoid the worst problems deriving from the heterogeneity of its elements and to be insensitive to connection failures.

But ... Security was not given much attention in its original design, and its use for purposes for which it was not initially intended ... has revealed exploitable vulnerabilities ... And although the Web is an important element of people’s work lives, it is not as critical as a ULS ... system would be.

Now I think we're in a good place to talk about the health care system of the future...


Health Services as a ULS

Let's start this section with a quote from the presentation that inspired it. Richard Gabriel says:

An example of a ULS system (that doesn’t yet exist) would be a healthcare system that integrates not only all medical records, procedures, and institutions, but also gathers information about individual people continuously, monitoring their health and making recommendations about how to improve it or keep it good. Medical researchers would be hooked into the system, so that whenever new knowledge appeared, it could be applied to all who might need it. Imagining this system, though, requires also imagining that it is protected from the adversaries of governmental and commercial spying / abuse.

Modern hospitals are packed with countless computing devices: everything from charting PDAs to physiological monitors for patients; from mainframes and patient record data warehouses, to terminals and desktops. Wireless medical sensors have already been developed by a research project at Harvard. What's more, despite the concerns over associated health risks, implant research at Johns Hopkins and the University of Maryland is on-going and may produce results that are one day standard practice in hospitals.

As versions of theses decives are developed that produce no ill effects for humans, they will make their way into out-patient clinics, assited living facilities, and ulitmately HMO's, private practices, and our homes. The devices will grow in numbers, shrink in size, and provide more functionality at greater efficiency than their predecessors.

The volumes of information that will be exhanged between devices, analyzed and correlated by other devices, and consumed by end-users, doctors, and researchers will be mind-boggling. It will bring new insights on everything from personal health to epidemiology.

With this, though, will come the obvious need for security and privacy, for defense against information attack and denial of service. These devices will all have to dedicate compuational and storage resources for use by the whole system. Part of the system will have to monitor itself, properly escalate problems, observe and anticipate trends. Protection and defense capabilities will have to exist the likes of which barely exist in our every day lives at the marcoscopic level.

All of this will take time. They will truly be modern wonders of the world. Given that such systems are anticipated to exist sometime in the next 20 years, and will have accreted the component systems over time, where might such a thing start?


Google and a Health Care ULS

If you read my last post (which I think was posted to blogger before the official announcement by Google), you already knew what I was going to say :-) Google Health. Though obviously nowhere near a ULS system in and of itself, why might we suggest Google is moving in this direction?

Here are some interesting bullet points from google.org:

• InSTEDD: $5,000,000 multi-year grant to establish this nonprofit organization focused on improving early detection, preparedness, and response capabilities for global health threats and humanitarian crises
• Global Health and Security Initiative: $2,500,000 multi-year grant to strengthen national and sub-regional disease surveillance systems in the Mekong Basin area (Thailand, Vietnam, Cambodia, Lao PDR, Myanmar, and China-Yunnan province)
• Clark University for Clark Labs: $617,457 to Clark University, with equal funding from the Gordon and Betty Moore Foundation, to support the development of a system to improve monitoring, analysis and prediction of the impacts of climate variability and change on ecosystems, food, and health in Africa and the Amazon
• HealthMap: $450,000 multi-year grant to conduct in-depth research into the use of online data sources for disease surveillance

Does that sound familiar to anyone besides me? All paranoia-induced sinister thoughts and Google Ads jokes aside, it makes sense that this is where we're going with health. In fact, it makes sense this is where we're going with all of our lives. If data privacy, personal ownership of that data, and security concerns can all be addressed, our lives' information will be better served by moving through systems specially designed to provide maximal use of that information with the least work. It won't just be nice to have, it will be essential.

The balance of power, from individuals all the way to the top of whatever organizations exist in the future will rest in information. Not like it is today, however. The "information economy" of the today (+/- 10 years) will look like kids' games and playgrounds. The information economies this will evolve into will be so completely integrated into human existence that they will resemble the basic necessities like water and food.

If you could find yourself a corner of that market, 20 years before everyone else got there, wouldn't that be a smart business move?


Summary

Our world is changing much more than we realize. We're too tied up in our jobs and gas prices to see the larger picture... to see that our future is already being made, that even in our unconscious actions we are propagating it no less than the cells in our bodies conspire to propagate what will become our children.

In the same way that hominid nomadic/migratory patterns begat the distribution of villages and tribal communities, which in turn gave birth to civilization, our silly little Internet will one day have descendants that dwarf it in size, utility, complexity, and computational power. The amazing thing is that we are the ones that actually get to build them!

There is a lot to research, and just as much to prototype. There is a project for everyone, and by starting now, we can make sure that feudal lords of tomorrow don't have absolute control over our food and water. If you have ideas for collaboration, start talking! Get involved! If you have money, fund some research, sponsor some conferences. In simply writing this blog post, I have uncovered gobs of new research I didn't know was out there. We should all be reading more, catching up, and coding. The projects near and dear to our hearts can get a whole new life within the context of ULS systems.