More linguistic maundering

kw: programming, languages

I sometimes joke that I've written a mile of computer code in my career. Someone challenged that, so I decided to figure it out. To avoid being too nit-picky, I'll mostly confine myself to the period during which I programmed all day, every day, and sometimes into the night like any good hacker (when "hacker" was an honorable term).

Definitions and standards:

• A "line" takes up 1/6 inch on a line printer listing (what else would a programmer print on?).
• One foot of printout (ignore margins) contains 72 lines; one mile is 72x5,280 = 380,160 lines. That is my goal.
• There are 260 weekdays per year, but we must subtract 10 holidays and 10 days of vacation, and also allow 10% of the rest for meetings and administrivia. The balance is 215 productive days per year.

I learned FORTRAN II early in 1968. I was soon doing nothing but writing programs, doing my own card punching. I typed slowly in that period, but I could produce about 20 code lines daily. In FORTRAN, using cards, that means an average of about 30 characters. "Lines" include comment lines that consist of more than the comment character. This continued until very late in 1970, so let's consider it to be 2.5 work years. 215 days times 20 lines is 4,300 lines per year, or 10,750 lines. The machines I used were an IBM 1130, a CDC 3100, and a Xerox Sigma 7. During this period I was sent to a class to learn the "executive system" (an early version of OS360) and FAP, an assembly programming language that worked with FORTRAN II. I wrote too little FAP to count.

I did a little programming here and there in the next few years, while finishing a BS degree, but not enough to count. My next heavy programming gig began in 1975, and lasted 3 years. I improved both my thinking and my typing, with the help of a good mentor, and my production was 30 usable lines of FORTRAN IV daily, on a CDC 3600. No card punch now, but terminal input. 3x215x30 = 19,350 lines. Total to this point: 30,100.

I started graduate school and, while studying engineering, worked for the computer science department, first tutoring and then teaching, starting at the beginning of 1979. This lasted five years. The first summer I worked hard on my touch typing, getting my speed up to 50 wpm. My programming rate also went from 40 lines/day in 1979 to an average 75 lines/day thereafter, when I was writing FORTRAN (IV and then 77). This was in addition to full time class work! My wife sometimes called herself a "computer widow". This was all on small CDC Cyber machines, 720, 825 and 835. One year at 40 lpd = 8,600 lines; 4y at 75 lpd = 64,500 lines. Total: 94,600. That's a quarter mile, minus 440 lines.

At the beginning of the next period I learned the COMPASS assembly languages; there are two, one for the CPU and another for PPU's the peripheral processors. I became a system analyst at the university while finishing my engineering degree. For the following three years I wrote 1/3 FORTRAN 77 and 2/3 CPU COMPASS, but very little PPU COMPASS. Assembly languages are harder and require more think time. My COMPASS productivity did not exceed 50 lpd. Thus I wrote about 16,125 lines of FORTRAN 77 and about 21,500 lines of COMPASS, a total of 37,625 lines for a total of 132,225. It's just past 1/3 mile…

I got work at an oil company in 1986 as a systems analyst. I wrote only COMPASS for the first year: 16,125 lines. The machine was a CYBER 860. Then I wrote mostly FORTRAN 77 on DEC VAXes for a few "skunk works" programming groups until mid 1995. Here I hit my stride, averaging 100 lines per day, but now I'd worked long enough to have another week of vacation each year, so there were about 210 days in those work years. It comes to 7.5 years, or 157,500 lines. Total: 289,725 lines or a little over 3/4 mile.

I am closing in on the goal, but there is little programming left. I transferred to the parent company in Delaware, where I now work (and will retire in a few weeks). They needed me to lead a database project. I used FORTRAN in a more ancillary mode, for no more than a quarter of my time for the next four years. Lines produced: 21,000 for a total of 310,725.

The company quite using FORTRAN altogether in 2000. I learned Perl with the help of a colleague (who is presently my supervisor). Since that time I have written very little, all in Perl, not for web pages but for file conversion and text processing. It totals no more than another half year out of the past 12 years, or at best, 9,500 lines, since I am a little slower in Perl than in FORTRAN (I have to look stuff up).

Thus my lifetime total is about 320,000 lines, maybe a little more, in all languages I have used. I suppose I could add in a little VBA for a couple of Excel macros I wrote as Functions, but let's ignore that, and conclude that I didn't quite make my mile. It totals 0.84 mile of code, if printed out at 6 lines per inch. But, hey, this is a metric world: I comes to 1.36 km!

The average "line" is about 30 characters. 9.6 million characters, or less than 10 MBytes, represents about 22.5 years of full time computer programming! (over a 40-yar span) In space taken, it is equal to three JPEG files from my digital camera. Sic transit gloria mundi! On the other hand, those programs kept a lot of scientists very busy for decades.

Maybe worse than impossible

kw: programming, computer science

A couple of decades ago I was working on a program to simulate the way oil fills up a "reservoir", really an impermeable surface with some shape that could trap oil as it trickled upward. A colleague and I tried out scheme after scheme, mainly based on how hard each one was to write into computer code. Of course the easiest one to write elicited my colleagues comment, "Boy, that is pretty bogus." He meant that whether it worked or not, it was a very inefficient way to proceed. We eventually found a pretty efficient method. Other projects throughout the years have been, sometimes a search for efficiency, and sometimes a frantic scramble to avoid too much bogosity.

Definition: Bogosity in computer programming is the inverse of efficiency. Where "bogus" usually means "fake", to a programmer it means a bad way to do something, one that will make the computer take too long. But we need to see just how bad "bad" can be. The standard programmer's example is sorting, so I'll use it.

Sorting data has received huge amounts of attention from thousands of bright people because it is needed so frequently, and is very slow unless clever methods are employed. Sorting bogosity is easy. The (almost) easiest method is one you can do by hand, and it matches the way people typically operate when sorting a small number of things, such as lining up a dozen rocks from smallest to largest. This easy method is called the Bubble Sort:

• Line up the rocks and look through them for the largest. Put it at the end of the line.
• Look for the largest among those that remain. Put it next to the other one.
• Repeat.

We can do this rather quickly because we can compare several items at once by eye. But in a computer, it must be done by comparing them pairwise. So a computer would have to use a few extra steps:

• Load numbers representing the "size" of the rocks (such as weight. That means weigh them first).
• Compare the first two numbers. If the first is bigger than the second, swap them.
• Compare the next two numbers, and so forth, swapping as needed, until you get to the end of the list.
• At that point, the last storage location contains the largest number.
• Start over, but stop one short of the end. Now you have two numbers in order.
• Repeat until you have made 11 passes through an ever-shortening list of numbers.

For 12 rocks, the program made 11 comparisons, then 10, and so forth, for a total of 66. That's OK for a dozen items, but what about sorting a deck of 52 cards? Once you determine which order the suits go in (whether to sort by suits or by numbers within suits), you have to make 1,326 comparisons. That is a lot for a human, though it is pretty quick for a computer. But computer programs need to do a good job even if sorting tens of thousands of items. For 10,000 items, the bubble sort takes almost 50 million comparisons.

A different kind of sort works better. I'll describe one variation of the Shell Sort. It takes fewer comparisons, but uses some extra space. First, for 12 rocks:

• Line up the rocks as before.
• Compare the first two. In a nearby space put the smaller one on the left and the larger one on the right.
• Compare the next two from the original line. Put them in order nearby.
• Continue until you have 6 sorted pairs.
• Now take the leftmost rock from the first pair and compare it to the leftmost rock from the second pair. Put the smaller rock at the left end of a new line. It is the smallest rock of the four.
• From whichever pair that smaller rock came from, pick up the other rock. Compare it with the one you are still holding.
• Put the smaller one next to the first, smallest rock.
• Pick up the fourth rock.
• Compare it with the one you are still holding. Put these two rocks in order next to the first two. Now you have four sorted rocks.
• Continue with the next pair of pairs.
• Continue with the third pair of pairs. Now you have three lines of four sorted rocks.
• These were merge operations. Perform a merge operation on the first two lines of four. This results in a line of eight sorted rocks, and the other line of four is still there.
• Merge the line of 8 and the line of 4.

If you were counting comparisons, there were 33. You went through the rocks four times instead of 11. Half the effort, at the cost of a little more complexity of planning. To sort 52 cards this way, you'd wind up making 253 comparisons. That is about 19% of the original effort to sort the deck. The general formula for comparisons is N Log/2(N), so sorting 10,000 items takes about 133,000 comparisons, or 1/376th the effort!

There are clever variations of the shell sort that reduce overhead a little, but that is basically the most efficient sort method. But we were talking about bogosity here. The bubble sort is quite "bogus" compared to the shell sort, which is what my friend meant. Is more bogosity possible?

Certainly. For example, if you play Klondike solitaire with the cards, you are only going to win about one time in four if you don't cheat, so each game you play will have some number of comparisons that is less than 1,326, unless you win, but the comparisons are accompanied by "overhead": stack moves and dealing and so forth that greatly lengthen the time to produce a sorted deck even if you win the first game. A typical "sort" might take four games of average length about 700 or nearly 3,000 total comparisons.

Let's declare that the bubble sort has a bogosity of 1. Then a series of games of Klondike
that leads to a win would have a bogosity of 2. Other solitaire games will also be 2's, though they vary a little in how frequently you win without cheating.

This is not nearly as bogus as it gets: I don't know what number to give it, maybe 100, but there is a "sort" that has maximum bogosity, so far as I know. We can call it the Bogo Sort:

• Throw the cards across the room.
• Pick them up and flip the face-down ones face up.
• Look through the deck to see if they are in order.
• If not, repeat. (Even if only one card is out of place! No cheating by moving it)

The average number of times you'd have to repeat this operation to achieve a sorted deck is a number with 68 digits (roughly 4E+67). If you could "throw-pick up-check" once per minute, it would take about 1E+62 years (That is a hundred trillion trillion trillion trillion trillion or so). Now that is real bogosity.

The hard and the really hard

kw: computers, software, programming, artificial intelligence

I noted earlier the report that a computer system now exists which exceeds the processing power and memory capacity of a human brain. It just needs about nine million watts of electricity to run. However, if things proceed into the future as they have in the past, in thirty years such capacity will be available in larger desktop personal computer systems, and in a further thirty years, in a pocket device, a successor to the smart phone.

There are good reasons to think that future progress may not follow the trend of the past half century or so. Moore's law may be running out of steam. There are several versions of the "law", actually a well-defined trend. The original trend identified by Gordon Moore in 1970 states that the number of devices on a CPU chip tends to double about every two years. In 1971 the 4004 CPU had 2,300 transistors on-chip. In 2011 a 10-core SPARC processor had about 2.6 billion. That is a factor of 1.13 million in 40 years, or just over 20 doublings. So that element of the law has been working just fine. I wonder, though, whether just another ten doublings (a factor of about 1,024) can be accommodated: 2.7 trillion transistors on one chip? On a watch-sized chip (4 sq cm), that is 150 square nanometers per transistor, or a feature size in the 10-12 nm range. That's where it gets hard to keep electrons going where they are supposed to, because of Heisenberg uncertainty.

Other elements? Performance does show signs of hitting a limit. Let's look at a fifteen-year span that is well studied. In 1994 the first Intel Pentium chip was introduced. At 75 MHz, its benchmark speed was 12.2 MFlops. Seven years later, the Pentium 4 ran at 1.7 GHz and benched 152 MFlops, 12.5x faster. From 2001-2009, CPU clock rate didn't quite double, to 3.07 GHz in turbo burst mode in a Core i7, but the benchmark (per core) increased to 667 MFlops, an increase of 4.34x, mainly due to better architecture. The benchmark doubling time in the first seven years was 1.9 years, while in the latter eight years, it was 3.8 years. In the 2006-2009 time frame, doubling time was more like seven years. But now the norm is four, six or eight cores on a large die, making single-thread codes less relevant. I don't expect single-core benchmark speeds to much exceed 1,000 MFlops for some years to come.

To me, all this means that getting the power of the brain into a watch-sized hunk of silicon or a successor material is going to take longer than we might predict, based on the past fifty years of computer hardware history.

There is a second hurdle in the way of getting useful work out of all that power: software development. Do we want a silicon brain to run the same way our lipid-based brain does? It seems a silly idea to me, but not to many proponents of artificial intelligence. Some people are saying that the Watson supercomputer, by winning two days of Jeopardy!, has passed the Turing test. Not really; nobody was trying to make it fool us into thinking it was human. It won a specific kind of trivia contest, as a machine, using machine methods rather than human ones. It was a successor to the Deep Blue chess match against Gary Kasparov. The computer didn't try to behave as a human would, nor was it in any way disguised. Neither system could navigate its way out of a crowded living room (were it mobile).

I don't have a definite figure, but IBM seems to have spent half a billion dollars developing the software code that makes Watson's hardware a Jeopardy! wizard. It will cost dozens of millions more to re-purpose the Watson hardware into a medical diagnostic machine, because of course, diagnostic medicine is not a trivia game, though it does require the marshaling of numerous loosely related facts.

Watson's software is on a par with an operating system. Even your telephone has an operating system. The popular Android OS for smart phones, according to a recent article, has 12 million lines of program code (plus 5 million lines of comments), in forty programming languages and scripts. Roughly speaking a "language" is converted into machine code before use, while a "script" is interpreted from a more human-readable version each time it is used. The compiler for a language is comparatively small: 150,000 lines of code in the case of the Perl compiler. The real heavyweights are full-scale OS's for computers: Linux has 200 million lines of code and Windows 7 is in the 100 million range (Vista had 50 million).

Here is where the kind of CPU you are using has some influence. Much of the code of an OS is in assembly code, and a "line" of assembly code does more on an Intel CPU than on one designed to run UNIX or Linux. So that 100 versus 200 million difference is smaller than it looks.

What does a line of code cost? It depends on the kind of code, but IBM long ago found that a "good" journeyman programmer could write and debug three lines of code daily. A small number of superprogrammers (I was one for thirty years) can do ten to 100 times as much code writing. In FORTRAN, I typically produced 50-100 lines per day. In assembly code, I produced half as much. During the last years I was an active programmer, I earned around $20 per hour, but my work cost my company $50 per hour with overhead, or $400 per day, so a line of my code cost in the $8 range. The larger teams of programmers needed for huge projects like Windows 7 typically include very few superprogrammers, so even with more efficient methods of code generation that are possible using "Visual" languages, a line of code costs $50-100.

Put the figures together. It cost close to a billion dollars to develop Android, and ten times that much to develop Windows 7. That's why Microsoft has to charge $100 to $400 for a copy of the OS, and hope to sell 100 million of them. The first 70-80 million copies just pay the development costs.

Now, consider the human brain. To duplicate all its functions might take billions to trillions of lines of code, if we go the software development route. 'Taint gonna be cheap! Of course, as with an OS, you only have to do it once. But the romantic notion that a lone programmer somewhere will develop a "soul in silicon" is just not in the cards. One of my colleagues was ten times as productive as I was: 500-1,000 lines of good FORTRAN daily (that's a lot of typing, each and every day). So a million lines of code would take him 1,000-2,000 work days. That's four to eight work years. Ten such programmers could produce Android in ten years or less. The actual Android crew, numbering much more than ten, took two years. I tip my hat to them.

Now that we're on the verge of software projects that might be of human-brain scale, can it be done? First, you have to know what you actually want. What would success look like? Right now, if we wanted to start programming "consciousness", we'd be in a position like these folks:

You lot start coding…

…I'll go find out what they want.

Source: www.abberley.co.uk/asap/

There are ten thousand or more studies of what consciousness is. They can't even agree on two or three basic rules to help them recognize consciousness when it appears. Philosophers have been arguing this for centuries (30-40 of them), without producing anything a computer programming team can use as a target. It is going to be an emergent property of some collection of parallel processes, not parallel as doing the same thing, but each set doing something different. But there is no agreement on what are the necessary processes and which ones are simply tools used by a conscious being.

There is not even agreement about whether a physico-chemical body is required. Our brain's operation is strongly affected by hormone levels, and it may be that "our" kind of consciousness (I am including all mammals and birds here) is intimately related to the body's responses to environment, via its chemical cues. I suspect our real "brain" is not just the 1.4 kg of gray+white matter inside our skulls, but includes the other 40+ kg of the body, or at least the 5-10 kg that comprise our nervous lashup plus our endocrine system. I suppose from the total brain's point of view, most of the body is a support system. But the endocrine system may turn out to be essential for any sort of consciousness that we can understand well enough to converse with.

Oh, there is so much to learn, and lots of eager folks trying hard to learn it. It is fun to watch, even though I am pretty much on the sidelines these days.