Linked lists, dictionaries, and AI

When I was learning the craft of programming, I spent a lot of time learning about data structures (linked lists, trees, and other things). How to create them. How to add a node. How to remove a node. How to find a node. There was a whole class in college about data structures.

At the time, everyone learning computer science learned those data structures. Those data structures were the tools to use when designing and building programs.

Yet now in the 21st century, we don't use them. (At least not directly.)

We use lists and dictionaries. Different languages use different names. C++ calls them 'vectors' and 'maps'. Perl calls them 'lists' and 'hashes'. Ruby calls them ... you get the idea. The names are not important.

What is important is that these data structures are the ones we use. Every modern language implements them. And I must admit that lists and dictionaries are much easier to use than linked lists and balanced trees.

Lists and dictionaries did not come for free, though. They cost more in terms of both execution time and memory. Yet we, as an industry, decided that the cost of lists and dictionaries was worth the benefit (which was less time and effort to write programs).

What does this have to do with AI?

It strikes me that AI is in a phase equivalent to the 'linked list' phase of programming.

Just as we were convinced, some years ago, that linked lists and trees were the key to programming, we are (today) convinced that our current techniques are the key to AI.

It would not surprise me to find that, in five or ten years, we are using completely different tools for AI.

I don't know what those new tools will be. (If I did, I would be making a small fortune implementing and selling them.)

But just as linked lists and trees morphed into lists and dictionaries with the aid of faster processors and more memory, I think AI tools of today will morph into the tools of tomorrow with better hardware. That better hardware might be faster processors and more memory, or it might be advanced network connections and coordination between processes on different computers, or it might even be better data structures. (The last, technically, is of course not hardware.)

Which doesn't mean we should stop work on AI. It doesn't mean that we should all just sit around and wait for better tools for AI to appear. (If no one is working on AI, then no one will have ideas for better tools.)

We should continue to work on AI. But just as we replaced to code that used older data structures with code that used newer data structures, we should expect to replace early AI techniques with later AI techniques. In other words, the things that we build in AI will be temporary. We can expect to replace them with better tools, better models -- and perhaps not that far off in the future!

Our technology shapes our systems

In the old days, computer programs were fairly linear things. They processed data in a linear fashion, and the source code often appeared in a linear fashion.

Early business applications of computers were for accounting applications: general ledger, accounts payable, payroll, inventory... etc. These systems were often designed with a master file and one or more transaction files. The master file held information about customers, accounts, and inventory, and the transaction files held information about, well, transactions, discrete events that changed something in the master file. (For example, a bank's checking accounts would have balances in the master file, and records in the transaction file would adjust those balances. Deposits would increase a balance, checks or fees would decrease a balance.)

The files were not stored on modern devices such as USB drives or even floppy disks. In the early days, the master file was on magnetic tape, and the transactions were on punch cards.

The thing about magnetic tape is that you must run through it from beginning to end. (Much like a tour through an Ikea store.) You cannot jump around from one position to another; you must start with the first record, then process the second record, and in sequence process every record until the last.

The same holds for punch cards. Paper punch cards were placed in a hopper and read and processed one at a time.

You might wonder how you can handle processing of accounts with such restrictions in place. One pass through the master file? And only one pass through the transactions? How can we match transactions to master records if we cannot move to the proper record?

The trick was to align the input files, keeping the master file sorted and sorting the transactions before starting the update process. With a bit of thought, you can imagine a system that reads a master record and a transaction record, compares the account numbers on each (both records need a key for matching) and if they match then updates the master record and moves on to the next transaction. If they don't match then the system stores the master record (on another tape, the output tape) and runs the comparison again. The algorithm does work (although I have simplified it somewhat) and this was a common model for program design.

The rise of direct-access storage devices and complex data structures has changed programming. As processors became less expensive and more powerful, as programming languages became more expressive and allowed complex data structures such as lists and trees, as memory became available to hold complex data structures in their entirety, our model for programming became more complex. No longer were programs limited to the simple cycle of "read-master, read-transaction, compare, update, write-master, repeat".

Programming in that model (perhaps we could call it the "Transaction Pattern") was easy and low-risk because clever people figured out the algorithm and other people could copy it.

This notion of a common system model is not unique to 1960s-style programming. Microsoft Windows programs at the API level follow a specific pattern of messages sent by the Windows core "message pump". Android programs use a similar technique.

Tablet/cloud systems will probably develop one (or perhaps a handful) of common patterns, repeated (perhaps with some variations) for the majority of applications. The trick will be to identify the patterns that let us leverage the platform with minimal thought and risk. Keep your eyes open for common templates for systems. When you find one that works, when you find one that lets lots of people leverage the cleverness of a few individuals, stick with it.

I'm guessing that the system model will not be a purely linear one, as we had in the 1960s. But it may have linear aspects, with message queues serializing transactions and updates.

Why we change languages

An acquaintance asked me: "Why do computer programmers change their languages?"

The question gave me pause. Why *do* we change our languages? It seems that every few years we introduce a new language. (BASIC in the mid-1960s, Pascal and C in the 1970s, C++ in the late 1980s, Java in 1995, C# in 2000... the list goes on.)

It is not about switching from one language to another. The question is more about why we modify our languages. Why do we change the language syntax over time?

The obvious answer is that hardware gets more powerful, and we (as programmers) can do more with languages when they take advantage of that hardware. The original FORTRAN was little more than a macro-assembler, converting source code into op-codes for the IBM 704. Later systems had more memory and more powerful processors, so compilers and interpreters could take advantage of the hardware. What was considered extravagant in the days of FORTRAN would be considered acceptable in the days of BASIC.

I have a different idea of languages, and our (seemingly-infinite) desire for new languages.

A programming language is a representation of our thought process. It (the language) allows us to define data in specific structures (or types), organize it in collections (classes or containers), and process it according to well-defined rules.

We change our languages according to our understanding of data, the collections and relationships of data, and our ideas for processing. Part of this is driven by hardware, but a lot of it is driven by psychology.

FORTRAN and COBOL were languages that considered data to be structured and mostly linear. The COBOL record definition was little more than a flexible punch card. (FORTRAN, too.)

Pascal (and all of the Algol languages) viewed data as a linked list or tree.

C++, Java, and C# considered data to be something contained in classes.

Perl included hashes ("dictionaries", in some venues) as a first-class members of the language. Python and Ruby have done the same.

As our view of data has matured, so have our languages. (Or perhaps, as our languages have changed, so has our view of data. I'm not sure about the direction of causality.)

It is not so much the language as it is (in my mind) the data structures that the languages provides. Those structures are still evolving, still growing as out knowledge increases.

We might think that our current collection of arrays, hashtables, and lists is sufficient. But I suspect that our confidence is ill-founded. I'm fairly sure that the FORTRAN programmers believed that zero-based arrays were sufficient for their programming challenges.

When we find a set of data structures that are "good enough", I think we will find that our languages are also "good enough".