My car gets 44 MPG. It's nothing special. A 4 door sedan with a 1.9 liter engine and a 5 speed manual. It was dirt cheap, all the more so because i bought it used.

But it could get 20% more, or 53 MPG if i put a turbocharger on it the engine it has. It could get 5% more than that, or 55 MPG (rounding) if i add a cruise control. It could get 5% more than that, or 58 MPG, if the bottom was smooth, rather than set up to induce turbulence. Bottom turbulence helps keep the car on the road at high speed, so put in a governor that caps speed to 90 MPH - which is more than fair. Then, replace the gas engine with a diesel, and get 15% more, or 67 MPG. And none of this is high tech, expensive or new. I'm with Carl Sagan, who in his 1981 Cosmos series asked why we don't have cars that get 70 MPG.

Then there's tech we don't use. The differential consumes 7-15% of your power just to let your car go around corners. An electric transmission (generator at the engine, electric motors near the wheels, should have a total loss of 6%. But, there'd be no engine drag (which is alot like braking - a waste), you'd get automatic like non-shifting - except that there'd really be no shifting - no jerks, and you'd get 4 wheel drive with zero economy penalty. You could also have two independent engines. Why is that good? Well, it only takes about 15 HP to cruise down the highway. A 300 HP engine is really poor at delivering 15 HP. So you put in a small engine for highway cruise, and a larger engine for pulling your boat. If an engine dies, the other will still get you home (remember, the little one will let you cruise down the highway). What's all this going to get you? More than 100 MPG. Oh, and since you've got electric, you can add batteries for regenerative braking, and put solar cells on top for another 10% boost when it's sunny - and it charges your batteries when you're parked. Some people might never have to fire up the diesels. We might even have to 'remove gas from our tanks' - in the form of electric energy transfer from the parked car. Your house could probably use it.

In the 70's, most of the problem was solved through improved economy, and much of that was the 55 MPH speed limit, which got us some 10 - 15%. Bush has said "There's no instant fix", but we could have new signs on our highways today.

While we're there, what about home heating? Houses get really poor gas mileage. Insulation already pays for itself in the near term. That's only going to increase. Why don't we have businesses that insulate your house, and get pay back from the improved economy?

Starship Sofa

Just listened to a short story, And the Deep Blue Sea by Elizabeth Bear, hosted on Starship Sofa. I've no idea how this mp3 got into my feed and therefore on my iPod.

It's a good story. I'm not going to give away the surprise ending. If i could figure out what the ending is, i wouldn't tell you. Not every story has to end with "...and they lived happily ever after...".

The intro can be safely ignored. He goes on for a bit about how he couldn't think of anything profound to say. Though he does introduce the author. I like his accent. It's not like mine. But he doesn't read the story. That's a relief. It's a pro reading all the way.

I'll probably add Starship Sofa to my feed. That'll put me years behind, i'm sure. but at least the episodes aren't two hours long like some napolean podcast that i'm still subscribed to. Isn't Napolean going to die soon? I don't know enough about history to know. Sigh. That's why it's in my feed. I really can't cope with 2 hour mp3's.

My commute has gone from an hour each way to twenty minutes. I did cut a few things from my feed. But the strange thing is that i seem to be getting through nearly as much as i used to. I'll have it on while cleaning the house, cooking, mowing the lawn (one of the mowers has no engine, and is therefore silent). All my really short feeds (half hour or less) get consumed right away. But i'm stuck on this 2 hour feed.

Good news in politics

I'm not much into politics. But this post is clearly the best news i've heard in a long time. The idea that micro-payments as campaign contributions amounts to more money than corporate contributions can only be a good thing. Utube over traditional media can only be a good thing. Perhaps i should run for office.

IT Management

What is it that IT managers do? Do they manage any Information Technology? Well, no. What they manage is the people who actually work with Information Technology. Most IT managers do no technical work themselves. Most IT managers have never performed any technical work. For the most part, they are ignorant of the issues, except where they intersect with the management of people.

What if there is a problem, and the optimal solution depends on the details of the technology involved? This happens all the time. What happens? Well, that depends on a number of things. First, it depends on what, exactly, is meant by "optimal solution". The manager might want to optimize cost. It might be short term cost, or long term maintenance cost. It might even be long term maintenance responsiveness.

There are two approaches of interest. First, they might look to see what other people have done in similar situations, and do that. This has the advantage that if some upper management asks them, they can point to some precedent. However, the IT industry has been changing at a breakneck speed, and many of the experiments of others have not had the benefit of enough time to be completed. That means that no one knows if it was a good idea or not.

Another thing that the manager can do is ask their senior development staff. This is, unfortunately, quite rare. So, despite having the experts at their finger tips, IT managers rarely make use of it. Why don't they ask? Well, for one, it seems that managers think that developers are interested in optimizing for something that is different than what managers are interested in optimizing. Perhaps managers think that developers are lazy. They'd expect that developers would be looking for the easiest solution. However, the easiest solution is the one that takes the least time. That means it's also the cheapest. After all, didn't Einstein prove that time equals money? This idea that management and developers have the same goals seems lost.

An unfortunate side effect of this state of affairs is that developers often end up implementing the mistakes of the managers. Repeatedly. This aggravates the developers, who are master craftspersons. It is really annoying when you are implementing the same mistakes again and again. Alienating your staff is never a good thing. More on that in another post.

If management of Information Technology is not what an IT manager does, then what does is an IT Manager good at doing? They keep track of things. They measure things. They document processes. Mind that they have no idea what math is about, much less IT. So, it's a good bet that they'll measure the wrong things, and do it inefficiently. IT managers are also good at telling other people what to do. It's their job. So, naturally, they'll tell their developers to do the measurements. It might be to track when they got to work, when they went home, how much time was spent on each task (for billing purposes, or if there's only one client, there's some fallback explanation). And the developers must write up the reports too. A line like this may be used in explanation. Remember, if you don't measure your performance, you can't tell if you're improving. It's sounds good, even if it's not true. But more on that in another post.

My point here is that the management overhead is often placed on the developer, which can only slow her down. Management is overhead. More overhead is not a good thing. When all you have is a hammer, everything starts to look like a nail.

What about process documentation? Managers do this also. If you'd written a perfect process, you'd never change it, right? But managers still have this skill, and will, from time to time, tinker with the processes. As time goes on these processes have a tendency to become more complicated. They have to be able to handle more of the day to day issues that come up. And, there's the inevitable bandwagon to jump on every so often. Does the senior staff get involved in these changes? No so much. But the thing that really gauls developers is that despite all the hours tracked, when some process is clearly changed for the worse, IT managers will breathlessly claim that the new process is oh so much more efficient. This is part of what makes developers think that IT managers don't actually understand arithmetic. Are you an IT manager? You should be able to do this in your head. What's three quarters of two thirds?

OK, that was a cheap shot, as most people don't get it right. That doesn't mean they shouldn't. The correct answer is one half. In word problems, "of" means multiply. One half of a dozen eggs is six. So three times two is divided by four times three. That's six divided by twelve, which reduces. For the record, this is taught in 5th grade, when you're about ten or eleven.

Shadow IT vs Silo IT

IT departments in larger companies seem to have a mandate to find and stamp out Shadow IT whereever it can find it. First, a bit about Shadow IT. Imagine that your department actually does something for the company. Let's say that it's at headquarters, and manages sales. Let's say that there is a sales force spread across the country, and this department is responsible for getting the most from it. One thing it might attempt is to track how each sales person, each small group of sales people, and each region are doing. The idea is that a group manager writes up sales data for each sales person in the group. The data is tagged with what the group is and what the region is. Then, the data will be analysed back at the headquarters.

Doing this analysis by hand is going to be time consuming (expensive, remember, Einstein proved that time = money), tedious (which was never stops businesses) and error prone. So you hire a programmer, and tell them what you want. She says, we need a way for the managers to enter the data. We'll write a web application where they'll enter the data, and it will get stored back here in a database. There's no budget of any kind, so she finds a PC that's so old, slow and has so little memory that no one wants it. She loads Linux on it, installs an Apache web server, and a Postgres database server and configures them. Then she writes a form, and a Perl script that takes form data and stuffs it into the database. She announces that it's in production, send this URL by email to the managers, and let them at it. And despite using a four year old PC instead of a quarter million dollar server, the application is responsive and reliable.

Soon, data is coming in. By then, she's written a quick report that adds up sales by group and region for each month, in a table. The analysts say it's great. For one thing, they're no longer swamped in paper. While our intrepid programmer adds logins and real security, someone gets the idea that there should be a report that graphs the groups and regions over time so that one can pick out which ones are doing better and which ones are doing worse. She grabs some graphing routines from CPAN and puts something up.

What's wrong with this picture? Well, corporate says that having a server sit under someone's desk is bad. For one thing, there's no backup. She counters that she does have backup. There's a second PC with Linux, and it gets a copy of the primary's data every night. They also complain that Perl isn't supported, that Java is the corporate standard. Further, they say that they can save money by having the server administrated by the Unix group, the database administrated by the database group, the web server administrated by the Web group, security managed by the network security group.

Two years later, the application is rewritten in Java, it's hosted in the server room, and it follows all the company rules. Everything's great, right? Except that the original developer has been spending the past two years bringing the offshore people up to speed on the app, instead of adding the new features that the customer now knows they want, and the app still doesn't do everything that the original did, and it cost a million dollars, and nothing was saved, because the original developer is still on the payroll.

Why did the rewrite, with 30 developers take so long? For one, they had to use the Silo IT development model. What's Silo IT?

Corporate management has labeled the department model Shadow IT. It's a negative name. It casts the endeavor as murky, hard to follow, uncontrollable, and underhanded. So, it's only fair that the popular alternative also has a negative name. Silo IT refers to this idea that under the idea that pooled resources are efficient resources, the endeavor is split up into areas of responsibility. Typically, this is systems administration, web administration, database administration, network administration, architechture, web framework, mentors and application developers. Each of these groups forms their own sub-department.

If a developer wants to create an application, it needs to follow the rules laid down by architects, and it needs to fit in with the framework. Now, there's a considerable amount of information to go through, and typically there are documents, hundreds or thousands of pages of documents, that one needs to go through to absorb it. No problem - there are mentors that can help, right? Wrong. The mentor's job is to make sure that the rules are followed. The developer gets the application to work, then submits the code to the mentor, who comments one sections that don't follow the rules. It's like an exam. Mentors never consult with the developers to get them going. Their job is to slow the deployment process down by several days while they review the code.

What does the developer do while waiting? Well, perhaps they have another application to work on. If they do, they'll generally find the going slow and error prone, because each shift in focus takes several hours for their brains to catch up. So, as often as not, they do nothing.

So, let's say that the developer needs a new table in the database. They submit a ticket, and it enters the database administrator's queue. In ten days, an administrator takes the ticket out of the queue and creates the table. The developer then tests it to make sure it's what they needed, then submits a ticket to get the change made to the test servers. Another ten days. Then ten more days to get the change into production. Mind you, new tables can have no negative impact on production, so it could have been there at the start. And in Shadow IT, that's what happens. Except that it doesn't take thirty days. It takes maybe half an hour in Shadow IT. It's not hard to see where this is going. The developers are easily thirty times more productive in a Shadow IT organization than in a Silo IT system. So, it's not that the Shadow IT developer is brilliant, she just doesn't have the same ball and chain attached to her ankle while she swims the English Channel.

So what if you can't find a developer who knows how to install and administrate Linux, Apache, Postgres, and knows a web aware language? Well, according to Fred Brooks, the department should build a surgical team. Maybe it takes two or three people. But since they are a single team, they can still be responsive. In particular, the database administrator can spend time learning the current applications, and tune both the database and the queries to the real needs.

IT Management Introduction

This blog hasn't enjoyed the content flood for a bit. Part of that is changes in life style, including a new job. But part was just that the river of ideas had run dry. I've been thinking about IT (Information Technology) management ideas for a bit. In particular, why is it that the best book on the subject to date, The Mythical Man Month by Fred Brooks, is so studiously ignored by the industry. Are IT managers all ignorant? It seems hard to imagine. But there are millions of people who claim to have seen UFOs (Unidentified Flying Objects) or even claim to have been abducted by aliens. Could there really be that much of a shared mass hallucination?

I sat down and brain stormed for just a few minutes, and came up with over 100 topics that could each rate an essay. This would be entry zero. In the back of my head, i've wanted to start a podcast for software that is easily consumable, for example, in your car on the way to work. No pictures. No code snippets. Ten to fifteen minutes each. This series may turn into that podcast. Who knows?

In prepartation for this first article, i read one on CIO.com. It's 20 things, each can be done in 20 minutes (6 hrs 40 minutes in all) to improve as a CIO. It highlights one of the reasons i think a blog like mine is better than CIO.com. I don't advertise. I have no incentive to hype anything. I have no incentive to conform.

Some of it is common sense. Try short meetings. Encourage staff training. Check your competitor's SEC (Securities Exchange Commission) 10-K reports. Check your own 10-K report. Introspection, including "is this a good job". Get input from users. Get input from senior staff. Get input from junior staff. Talk to people you wouldn't normally talk to. Talk to your vendors. Talk to your customers. Talk with the universe. Go for a walk. The iPhone as a user interface example. Encourage company encryption, especially for laptops. Very little of this is of earth shattering importance.

But some of it is just odd. Have an email free day. What? Email is a tool. It's queue'd communications. You don't have to have a popup tell you that new email has arrived. If it does, you don't have to stop what you're doing to handle it. Don't send me email to invite me to a meeting in twenty minutes. It's very unlikely i'll read it. This is misuse of email. Email has these properties: It's pretty quick to send an informal note. It's potentially imortal, the last copy of this message may never be deleted. Content can be used for reference - it's searchable as long as the content is plain text. And, it's queued. The reader will eventually see it. I don't need an email free day. I'm not addicted to it. I will consider email as an alternative to a meeting. But i'll also consider walking to someone's desk unannounced as an alternative. I don't want some CIO telling me not to use email once a week. It'd be just as silly to ask everyone to hop on one foot one day a week.

What would i add? Well, maybe not in 20 minute increments, but i'll start tomorrow.

Tiny digital picture frame

I picked up a Coby DP-151 "keychain" digital picture frame. As there's no cover, expect the keychain to scratch it up. I removed it, which can be done non-destructively. I can just imagine what keys would do to it. Or the inside of a purse. They come in more than one color - mine is blue.

It has a 128x128 pixel display (16 kilopixels - 1/64 megapixels). That's not alot. It's got an internal battery, and it is charged up when you plug it into USB. When you plug it in, it asks you if you want to charge the battery, or upload photos to it. When you charge it, it displays the charge state of the battery in the lower left. It also displays whatever you have it display during charge. It has a clock, and you can optionally have it display in the lower right corner. In slide show mode, it has a bunch of different fades from one image to the next.

It can have up to 60 pictures on it. It displays the picture number in red as 17/29 in the upper right corner. That means number 17 of 29 total images. You can't turn this feature off. The pictures you upload to it are exactly 128x128. You can't have a larger image. There's no pan and zoom. You must use the supplied software to upload pictures to it. It supports Windows and Mac OS. The device does not mount as a generic USB drive, so Linux users are SOL. Of course, a Linux box can be used as a charger. I don't run Wine, so i haven't tested to see if the supplied software can be made to work or not. For me, this is a deal breaker. I only run Linux at home. But for others, it's also less than optimal. It means you have to install software if you want to upload. That means you're less likely to want to upload any images while visiting a friend, for example. The upload software comes on one of those mini CDs. I'd never used one before. But there was no problem loading it.

You must plug the unit into USB before you launch the photo upload software. If it doesn't find it, it complains and exits. You can browse images that are on your hard disk. If your image is square, it scales it to 128x128 for upload. If it isn't, it scales the short dimension to 128 and grabs a center square. But you can slide a square selection tool over the image. However, i ran into a bug where you couldn't select one end of the rectangle, and though you got a square image, you didn't quite get the bit of it that you wanted. It shows that you can get one side, but it doesn't actually give it to you. This is under Windows. You also can't select a smaller square from the middle of the image - like just someone's face. You could do that in some other application, save a square image, and get what you want. The 128x128 image area is quite limited, and it's highly likely that you'll want to do something like that for many images.

The physical shape has another limitation. Let's say you want to set up a slide show. Change the picture every 60 seconds (it's settable in 5 second increments from 5 to 60). Put the thing on your desk, so it loops through all 60 of your images in an hour. Pretty cool, right? Except that you can't stand it on your desk. The rounded edges prevent this. Perhaps you could mount it on some Silly Putty or something. Or, you can make a stand by folding some stiff cardboard in half and cutting out a diagonal rest. Be creative.

There are two tiny screws on the back, but it seems likely that the rechargable battery inside is not replacable. Think of the whole thing as disposable. Mine was $20, delivered.

Little tiny pictures. What would you use it for? You might put a few family photo album like things on it. Show off your baby pictures or something. Don't have a baby? You were likely a baby at one time... show those off. Probably the last time you were cute when naked. The device is really, really portable. Small enough to get lost in a shirt pocket.

One might ask, since i only run Linux, why would i buy such a thing? It's a gift. I'm pretty sure the recipient doesn't read my blogs. I still get the odd comment, so i guess at least some people still read it.

Gas Mower

I mowed the grass today. Well, most of it anyway.   Uhm, some of it. I did this one patch.

In any case, i'd really been dragging all day. I didn't get nearly enough sleep. That's because i kept waking up all night. I stayed up too late. Working on a big, important project. Goofing off.

But I really did mow my lawn. Now, my lawnmower is a bit underpowered. It's a push-reel mower. There's no engine. I'd bought it to get some exercise.   to save gasoline.   so i could listen to podcasts as a backup for my powered mower that actually fits in my garage. And despite having the gas mower still, i still use the push-reel mower because then i can get some exercise.   save gasoline.   listen to podcasts. mow the lawn until my primary gas mower is repaired. And, i went all last season without getting the gas mower repaired because i can't get the parts   i can't afford a new mower i'm lazy. The fact is, the gas mower uses one gallon of gas a year, which i can afford even if gas triples, and i have the parts. Worse, the push-reel mower was more expensive than a new gas mower. Really.

But the interesting thing today is that after two hours   an hour   a half hour of mowing and listening to podcasts, i feel much, much better. More awake. Less awful. Just from mowing the lawn. Just as i'd predicted. Just as i've known from experience for years. Would i do it again? You bet!   Sure If i have to.

Forth Extension Language For Emacs

Stevey has a rant about Emacs. It's not the usual Emacs vs. Vi. or even Vim. It's about variants of Emacs. Emacs and the xemacs fork. There are hundreds of other emacsen filling various ecological niches out there.

And it got me to post a rant in the comments. Big enough to drive away some more readers from this blog had i posted it here. But it got me to thinking about TECO. Raise you're hand if you remeber TECO. That many? Wow.

Well, there are a couple versions of TECO around now. I've installed one on my desktop, and also on my shirt pocket computer. I found that though i remembered enough to do simple editing - insert, delete, copy, paste, change all of this to that, i'd forgotten lots of the stuff that made it such a powerful editor. Well, a quarter of a century of disuse will do that.

You see, TECO isn't just a Text Editor and COrector, it's a Turing complete language. It would be natural to represent the Turing tape with characters in the edit buffer. On today's gigabyte machines, the tape really is essentially infinitely long. And, for the most part, TECO was really fast. And, mind you, the machines it ran on were really, really slow by today's standards. Imagine if it took Windows 100,000 times longer to boot. TECO was fast on such machines.

But today's Emacs uses Lisp as an extension language. And it seems pretty fast, except that my benchmarks show it to be 500 times slower than C on various machines. It's only really fast compared to how it used to run on smaller, slower boxes. Why is that?

Well, for some reason, Lisp is compiled to a byte code langauge. There's a 3x to 5x performance penalty for byte code interpretation. And, unlike Java, the byte code is not usually written to disk. So, it's write once, compile everywhere. It could be compiled to native code. But 5x is not 500x. Where does that come in? My guess is memory management. But it's just a guess.

TECO isn't compiled to byte code. The commands are one or two bytes long. The commands themselves are interpreted. There aren't very many of them, and interpretation is very fast. And, for some reason, there is no garbage collection. At least none that you'd notice.

TECO is a stack language. So it should be comparible to Forth. Where TECO has a small fixed number of variables, beyond which you can't go, Forth allows the creation of an arbitrarily large number of new objects. Neither language has garbage collection, as near as i can tell. Yet stack languages are reverse polish notation, and Lisp (and friends) are polish notation. The one can be converted to the other mechanically. So, it's a mystery why Lisp has garbage collection and Forth does not.

Now, i doubt that anyone wants to go back to TECO as the extension language for Emacs. I've found Forth a much lower barrier to entry language than Lisp. So, perhaps Forth is a reasonable choice.

Which House?

What Hogwarts House Would the Sorting Hat Choose for You? Congratulations! You're a Gryffindor! You can make your way to the Gryffindor table in the Great Hall and sit with Harry, Hermione, Ron, and the rest of the Weasleys, among others. The Sorting Hat has found within you the potential for great bravery in the face of opposition. Your courage may remain hidden, like that of Neville Longbottom, but it will strengthen you in need. But don't rely on your membership in Gryffindor as a guarantee of steadfastness - remember, Peter Pettigrew was Gryffindor, too. "You might belong in Gryffindor, where dwell the brave at heart, their daring, nerve and chivalry set Gryffindors apart." Take the quiz: What Hogwarts House Would the Sorting Hat Choose for You? More Quizzes from FamilyEducation.com

Fun Fiction

Stumbled upon a new site with really short (mostly science) fiction stories called Burst Fiction. Stories are about 1000 characters. Not 1000 words. These are really short.

I thought, "hey, i could do that. How long could it take to write 1000 characters?". I wrote a little diddy, and it's up! Woot! Can't wait to see where this micro story series i've started goes...

Expelled

It's not a surprise that Scientific American has run articles with negative reviews of the Ben Stein movie: Expelled. It's anti-science.

I've not seen the movie. But i've heard the arguments before. It does not surprise me that the movie is chock full of misleading statements. That's what happened in the Kitzmiller trial in Dover. It does not surprise me that people interviewed for the movie were mislead about what they were interviewing for. There's nothing new here. But Intelligent Design is increasingly irritating.

It's probably because i'm christian. The whole creationism, and therefore Intelligent Design thing isn't just bad science or anti science. It's also really poor theology. It seems to be based on the idea that most Christians haven't read the bible. They don't remember half of the 468 passages that come up in the standard liturgical cycle that get read to them in church on Sunday. They've no idea what the central and important messages in the bible are. So when smacked over the head with cherry picked verses in ancient translations, they seem to buy it. Well, at least some do.

Let's start with Genesis. There's the Creation story. It says 'days', but the original words could just as easily be translated as 'eras', or 'eons', or 'vaguely defined time periods'. It makes no sense to take the King James English version literally word for word. Moses had no knowledge of this translation, and better sources are available. With the gist of the original translations, the creation story matches modern cosmology extraordinarily well. And, it isn't at odds with Evolution. The animals and plants really did come before humans. But, the creation story itself is not one of the main points. Ignoring it will not imperil your immortal soul.

Make no mistake. The Intelligent Design people are not just against Evolution. Cosmology, and indeed, all of modern science is under attack. Why does it matter? Well, for example, Evolution is the basis for modern medicine. Without antibiotics, i'd be dead. Literally. Recently, my gaul bladder became gangrenous. It had died and was infected. Doctors removed it, but the infection remained. Now infectious bacteria mutate and adapt. Unlike humans where 20 years goes by between generations, bacteria spawn new generations in 20 minutes. If you don't kill them all, the remaining ones are highly likely to be drug resistant by the end of a week. So not only do you need to know Evolution to create antibiotics, you need to know it to administrate them.

Back to theology. The idea that modern apes and humans evolved from a common animal seems to make some people squirm. Yet, the late Pope John Paul II has said that evolution is compatible with Roman Catholicism as an explanation for mankind's physical origins. That's not because it's an idea that has been tested. It's because it's an idea that is compatible with the bible. That Pope John Paul II was a devout christian is, one hopes, beyond question. That he and other theologians really thought about the question is also a pretty good bet. They had time to work it out. Time you and i probably don't have. And, they're really smart people.

One enticement of a literal interpretation of the Bible is that it can seem to lead to a very simple absolute morality. In my opinion, it's wishful thinking. For example, Psalm 105 reads like a moral justification of the murder infants and small children. Where is the Love of God there? Without a reasoned interpretation, nearly anything can be justified from biblical sources. It's highly dangerous. For example, the Intelligent Design leaders can then say pretty much anything they want. And since the justification is biblical, they can convince people to commit the most outrageous acts. Christianity is not alone here. Fundamentalism in essentially all religions leads down this path.

And, it matters. The Bible says "Many are called, but few are chosen.", and "The road to salvation is narrow, like the razor's edge." Your immortal soul is at stake. The time is now to study, and really think. Spiritual growth has to be a lifestyle, not just a buzzword. Did you want to be expelled from the kingdom of God?

Pope John Paul II has also said that truth is truth. There isn't theological truth and scientific truth. There is only truth.

So, if you feel that Evolution is evil, feel free to refuse antibiotics the next time you're in the Doctor's office or the hospital. If you happen to be well adapted to warding off your infection, you live. If not, well, natural selection will remove you from the gene pool. My plan is to swim as long as possible.

Another stance is to support basic science education and research, to keep America strong and Americans healthy.

From my perspective, those spouting Intelligent Design are heretics, and should be burned at the stake.

Scheme For Enlightenment Part Twenty Four Conclusion

Scheme is definitely worth learning. That said, this comes from someone who thinks that everything is worth learning. Nothing is too trivial. It's worth learning the slide rule and the abacus. More to the point, it seems unlikely that i'll use Scheme for production work. It does not appear that it makes creating applications significantly easier or quicker to write. It's performance relative to C is slow. (However, i've not yet played with Scheme compilers). It does have garbage collection, but that alone will not make Scheme applications bug free, or necessarily easier to debug. I may learn enough of it to write some small image manipulation stuff for the Gimp, however.

Web based applications might work. An application might have several dozen web pages. Many of the pages display a form, and then do something with the answer. The forms can be html files: essentially static text. The form handlers need to be scripts. These scripts gather the form information and do something with it - often update a database. The scripts have very short run times. Even in Perl, the CGI script run time is usually under a second. It's likely that speed doesn't matter, except the Slashdot effect. CGI scripts are often small. A terse language that starts up quickly might be ideal.

With CGI applications, one can use the tool that is ideal for each task. If the database is the glue that holds together an application, and most of the data editing bits are short pages, it might be that some longer running engine needs to be written in another language, which might be C or C++.

Scheme inherited Lisp's flexible run time handling of data, specifically lists. So it is much easier to envision lots of little cooperating scripts creating the emergent property of a coherant web based application. There already exist Scheme libraries for writing CGI based applications, as well as those to interface with databases.

Why is having lots of little scripts better than one huge one? For one, a little script can be easier to write, read and debug. It's easier to write because it's small. CGI provides most of the interfaces. In a script that fits on your screen, it might be evident that this is a handler for mainform.html, stuffs the data into the table app.mainform, then presents optform.html to the user. That and some sort of application overview for how it all fits together might be all you need. No ponderous code. No ponderous documentation.

The only thing left to optimize for a language like Scheme is the barrier to entry. After a year of study, on and off, it's still not easy for me to write more than trivial scripts. It is much easier for me to write 200 lines of C than 20 lines of Scheme. Though much of that is experience, it doesn' look as if it will change soon.

Scheme For Enlightenment Part Twenty Three History of Lisp

You should really check out this 1979 paper on the History of LISP. This John McCarthy paper is a first hand account of what problems LISP was designed to solve, and how LISP was developed. This is they guy who designed and built the first LISP. By 1979, LISP was hardly news, so this paper wasn't written to extoll LISPs many virtues. It seems to have been written as an objective history, with as little bias as possible. In any case, it's a great read, and reasonably short.

At the end, John McCarthy talks about what it will take for a language to replace LISP.

LISP will become obsolete when someone makes a more comprehensive language that dominates LISP practically and also gives a clear mathematical semantics to a more comprehensive set of features.

The word obsolete is a funny word. Today, people talk about technlogical products with one of two words. Obsolete and Bleeding Edge. The idea is that either something is brand new and buggy, or it's old and useless. A synonym for Obsolete is Legacy. This term suggests that the bulk of the product has been built. In the case of software, you may tweak it a bit here and there, but for the most part, you leave it alone.

Modern thinking for languages suggests that if a language is the most popular, then everything else is obsolete. This is wrong, of course. Many languages enjoy niche markets. And, rightly so, as some languages are better for some tasks than others. Most languages are better at some task than any other language. The stereotypes for languages are often misleading. Here are some examples: Fortran is great at number crunching. C is good at operating systems. Perl is great at text processing and integrating things together. LISP is good for artificial intelligence research.

In many ways, there are no general purpose computer languages. It depends on what you need. You might write a web site in Perl. But there might be a bit of the site that performs a long running computation, for example to look for a bit of DNA in a database that is a close match of your sample. That bit might be written in C. Another bit tries to match what genes look like to what they do. That might be in LISP. And so on.

From this perspective, a language is obsolete when another language fills the same niche, and is better at it. LISP is good for functional programming. But so are Python and Ruby. So is LISP obsolete? No, LISP has this mathematical nature to it, and will itself be analyzable in ways that Python and Ruby will never be. But isn't Forth a language that might be analyzed in much the same way? Is Forth a better tool than LISP?

Corporate management would prefer fewer languages to many, for fear of not being able to find someone who knows some obscure language. So a language like Java, which has infinite libraries available, is attractive. So now we just have to find people who know all these libraries.

LISP has a relatively small niche. A smaller dialect, like Scheme, is unlikely to take over the whole niche. A large dialect, like Common Lisp, is also unlikely to take over the whole niche. So LISP can either be thought of as always having been obsolete, or will never be obsolete.

Fortran is a language that has undergone many changes. There was Fortran-60, then Fortran 66, then ANSI 77, and so on. The old saying is, "I don't know what language people will be using in the year 2000, but it will be called Fortran". This is even more true for LISP. LISP is a language where it is convenient to build new languages. The new languages don't have to look much like LISP. LISP could replace itself.

Of course if a language is Turing Complete, then it is equivalent to every other language.

Scheme For Enlightenment Part Twenty Two Hackable By Extension

And yet, Guile makes sense when used as an extension language to C(++) applications. The user of a program should not have to modify the source code to that program to extend it a bit, if that can be avoided. The Gimp is written in C, but i'm not not that interested in grappling with such a huge chunk of code to add an image filter. The ability to do that in an extension language would be nicer. That language would have access to the Gimp's power, but would be protected from doing any lasting harm. It also is documented with a limited API of functions to use. (The Gimp uses Guile as an extension language.)

For simple tasks, like configuration (turn this feature on, turn that one off), using Guile is the nuclear bomb to swat a fly approach. This is what makes the Emacs startup file (in lisp) such a bear to deal with. Even Google doesn't always know the answer to what i'd thought were easy issues. Even an xml file is usually too much. But it might be good for allowing the user to add real functionality. Guile, an implementation of Scheme, is a somewhat simpler language than Lisp. It might have been a better choice for Emacs.

The Unix shell allows one to chain utilities together and provide new functionality easily. The shell itself doesn't have to be fast to make this work. It's much the same idea. But the Unix shell is a simple scripting language with relatively low barrier to entry. And yet, i've used the shell to create filter chains to do image manipulation (using pbmplus for a pool of the basic image manipulation commands), to resize an image to the current screen dimensions, changing the gamma to correspond to the monitor, and using the file name as a label in the corner. The simplicity of the Unix shell did not limit the task overmuch. These are things one might expect the Gimp to do. And, in fact, the Gimp has a command line batch mode, with commands in Guile.

So, Scheme might enjoy a niche as an extension language. Is it a very good extension language? Would Python, Java, Forth, or even BASIC be better? It seems that a very simple language, with very low barrier to entry, would be a win.

Scheme For Enlightenment Part Twenty One - Hackable Closures

In the case of Scheme, particular features that make programming easier - and more fun! - are its powerful mechanisms for abstracting parts of programs (closures - see About Closure) and for iteration (see while do).

The Guile Reference Manual defines closure as the ability to remember the local environment when creating a function. The manual goes on to list four uses of closure.

The first corresponds to C's static local variables.

The second, called Shared Persistent Variable corresponds roughly to C's file static variables. This is a variable that is not accessible to the caller, except in the way that the provided functions grant. While i grant that it is handy for a library to have state variables that the caller won't accidently change unexpectedly, many languages have extended this to absurdity. For example, in Java, one is supposed to never touch a class variable directly. One should use accessor functions to set and get values. This is true even if the function is supposed to get data from a database. That means that the class must have a zillion accessor functions to set and get values. The class is huge, the caller's syntax is ponderous. The compilers either must optimize the calls away, or leave the extra code in. It buys neither the class nor the caller anything of value. In C, Shared Persistent Variables are supported, and they tend to get used as needed, without being elevated to the level of the Holy Grail.

Third, The Callback Closure Problem. The argument is that with closures in Scheme, a call back function can be registered that has all the environment stuff it needs. The callee doesn't need to know all the arguments and such, it just has a function to call, and calls it.

C supports callback functions. They have more syntax associated with them, but that's mostly because C is a statically typed language. In my opinion, the library is where the complicated stuff should be. The caller shouldn't have to build a call back function factory to simplify the library. The library should do as much heavy lifting as possible. And, i've never found this bit of library creation to be error prone, frequent or difficult.

Function factories need to be addressed in more detail. This is as good a place as any. Let's say that one needs a serial number generator. Each number is unique. A function with internal persistent state can simply have a counter that can be incremented, and the new number can be returned. One nice thing in Scheme is that the number can be said to never overflow. Scheme makes the number bigger if needed. But let's say that you need two serial number sequences, one for each of two products. In Scheme, one makes a serial number function factory. Each returned object can be used to generate a sequence that is independent from every other sequence. Can this be done in C? You bet. The difference is that in C, what you do is return a token that the sequence generator uses to determine which sequence is desired. So, the caller must pass a parameter to the generator, rather than have a function that can be called with no parameter. The caller still must remember the function (pointer), which is it's own parameter. I just don't see this as a big deal.

Fourth, Object Orientation. Object and method encapsulation can be a good thing. C libraries can do this. But there isn't any syntax specifically there to support it. Now, having a language that provides object oriented syntax can be a good thing. Objective C is an example of a language that does this without going over the top, as IMO, was done in C++ and Java. And mixing C style code with object oriented code is very natural. Many libraries make sense if written in an object oriented manner. Objective C allows calls to such libraries at will. Even inheritance can be supported in C. It's just that supporting virtual functions takes more work than most C programmers are willing to do, so very few C applications do it. I've only written code that way perhaps twice in a quarter century of C. So only those functions that really needed it also paid the performance penalty required.

In C, Object Orientation can be achieved by convention, rather than be strictly enforced by syntax. So, the maintainer of a chunk of such C code does not have syntax to quickly prove that, for example, only these functions make any changes to this variable. Such things are good. Because if one can limit the scope of where to look for behavior, there is less to look at. Remember that humans are slow. But C has scope rules. And even if some convention is violated in the code, one should be able to spot C's scope rules. For example, i use the keyword static for file global variables often. That means that the text editor can be used to quickly search for all uses of that variable. In C, one knows that this variable is only accessible from that point to the end of the file. Less, if there are blocks where variables are shadowed by local variables. I essentially never intentionally shadow global variables with locals, as it can cause confusion later.

So, the argument is that you can try little bits of Scheme easily. I recall doing that in C. What i was trying to do is figure out the exact semantics of the C language. The White book, The C Language, talks about what the language does, but isn't very precise. So i'd write something quick, like

    for (i = 0; i < 5; i++) {
        call_something(i);
    }

compile it, and step through it with a debugger. I'd also ask the compiler for the assembly language to see what it really did. I had the good fortune to have written ten or twenty thousand lines of PDP-11 assembly language, and had access to Unix running on a PDP-11 with the language writer's own compiler - the Ritchie C compiler. At the time, this was the gold standard for how C should behave. This gave me insights not only into what the exact semantics were, but also why Dennis Ritchie designed them that way. No tricks like that are available for Scheme. The best you might do is read the Scheme standard - which at least is short. A C standard now exists. However, for real understanding, the translation to assembly can hardly be matched.

Scheme For Enlightenment Part twenty - Scheme Is Hackable

Having written this much English about Scheme, i now feel minimally competent to address one of the things that really bothers me about the Guile Reference Manual. Section 4.6.2 is entitled Why Scheme is more hackable than C. This hasn't been my experience, so i'll take the issues point by point, and be as fair as i can in my infinite bias.

* They [interpreted languages] lend themselves to rapid and experimental development cycles, owing usually to a combination of their interpretability and the integrated development environment in which they are used.

There are C interpreters. They are usually sold as debuggers. C compiles very fast. On a 1987 Macintosh II (about 1 MIPS) the Think C (then Lightspeed C) compiler could scan code at effectively 70,000 lines per minute. And, since it only needed to recompile modules that changed (perhaps due to include files), it typically only needed to recompile a few hundred to a thousand lines, taking less than a second. Further, the integrated debugger remembered break points, variable watches and so on, so a single key stroke compiled your code, ran it, and stopped at an interesting breakpoint in seconds. C interpreters often get to this point later, because the interpreter runs code much slower. Interpretive systems like Scheme, Perl, and so on have little to add to this. Unless, while stepping through your code, you see an error, modify your code and continue stepping. To date, the only language system i've used that supported this was C (using a C interpreter). And Guile performs a compile, though without saving it to disk. It can get away with this because compiles are so fast. The interesting bit is that the user doesn't have to do something special to make it happen. The user is very slow compared to the computer, so compiles are invisible. But even Emacs with gcc and gdb is an environment that is integrated enough to be quick. Emacs has a compile command that puts the errors in another window, and can quickly move the cursor to some line that caused an error or warning. It's very fast.

* They [Scheme and other languages] free developers from some of the low level bookkeeping tasks associated with C programming, notably memory management.

This is true. At least this isn't a totally lame argument. It is unfortunate, but at least at the moment, the human is capable of managing memory such that the overall performance is much higher than machines, despite enormous research into automatic memory management (mostly garbage collection). Explicit memory management is faster but more error prone. But Scheme replaces that task with the bookkeeping of managing parenthesis. So far, this one misfeature seems much worse than the syntax headaches that C presents. There are other handy abstractions, but unfortunately, this very ripe area is left unpursued.

* They provide high level features such as container objects and exception handling that make common programming tasks easier.

It may be that C has simpler (and less flexible) scope rules than Scheme. Learning Scheme's scope rules may simply take longer. The most challenging limitations in C's scope rules show up when writing libraries. If a library is viewed as an object class, then the library will want it's own class variables. The library must choose some names, and some could conflict with the names used in other libraries. But C's names are no longer limited to 7 characters, as they were on the PDP-11 with Ritchie's original C compiler. And name conflicts can be limited by using naming conventions. These conventions can be broken when it makes sense, so C retains flexibility. The Java convention for naming classes tries to make name conflicts impossible world wide. It's a very ugly solution. Container objects and exception handling can certainly be done in C. The resulting syntax looks much as it does in object oriented languages. One can use it if they want to. I personally don't find exception handling, that is try and catch, to be easier in most cases. It can get in the way really good error handling, that matches the problem at hand. My highest praise for try and catch is that novice programmers may be encouraged to think about error handling, at least at some minimal level. But it's both complicated and minimal. In the few cases where it is needed, often a simple setjmp/longjmp setup is often sufficient.

Additionally, library writing is relatively rare. Most code is not easily reused. Most code is designed to solve the problem at hand. Certainly, hacking (playing around with some ideas) is not library writing. So, languages with no scope rules, like BASIC, are significantly more hackable than languages with strict scope rules like Scheme. That should sting, being compared to BASIC and coming up short, even on one point of many. But compared to BASIC, essentially all languages are unhackable.

Scheme For Enlightenment Part Nineteen - Ackermann Cached

So, (a 3 13) fails on some machines. (a 3 14) fails on others. I got to thinking. This function is supposed to eventually return. And it does this by calling itself with smaller numbers. And it seems to go over the same space with high frequency. So, if the function was written to remember answers that it previously computed, it could avoid lots of redundant calls. It might be faster. It's a classic trade of memory for time. How much memory, and how much time?

#include <stdio.h>
#include <stdlib.h>

#define A 5
#define B 10000000 /* m gets really big fast */
int acks[A][B]; /* (A * B * sizeof(int) bytes.), eg 200 MB. */

void init_acks()
{
    register int i;
    register int j;

    for (i = 0; i < A; i++) {
 for (j = 0; j < B; j++) {
     acks[i][j] = -1;
 }
    }
}

void setacks(int n, int m, int v)
{
    if (v < 0) {
 return;  /* Don't store bad data. */
    }
    if (n >= 0 && m >= 0 && n < A && m < B) {
 acks[n][m] = v;
    }
}

int chkacks(int n, int m)
{
    if (n >= 0 && m >= 0 && n < A && m < B) {
 return acks[n][m];
    } else {
 return -1;
    }
}

int ack(int n, int m)
{
    register int x;
    register int y;

    if (n == 0) {
 return m + 1;
    }
    x = chkacks(n, m);
    if (x >= 0) {
 return x;
    }
    if (m == 0) {
 x = ack(n - 1, 1);
 setacks(n - 1, 1, x);
 return x;
    } else {
 x = ack(n, m - 1);
 setacks(n, m - 1, x);
 y = ack(n - 1, x);
 setacks(n - 1, x, y);
 return y;
    }
}

int main(int argc, char *argv[])
{
    register int n;
    register int m;

    init_acks();
    if (argc == 3) {
        n = atoi(argv[1]);
        m = atoi(argv[2]);
    } else {
        printf("Usage: ack n m\nwhere n and m are small integers.\n");
        exit(0);
    }
    printf("Answer = %d\n", ack(n, m));
    return 0;
}

You have to call init_acks() before using it. The Ackermann function is called ack(). And this function is good for (a 3 16), assuming you have 200 MB of RAM for the array. It returns the answer very quickly. However, (a 3 17) doesn't work. It gets a stack crash. That's because the cache isn't large enough, and this code reverts to deep recursion. This one can also compute (a 4 1), but not (a 4 2). Worse, 1.5 GB of RAM (which happens to be handy) doesn't get you to (a 3 17). What on Earth is going on?

The Little Schemer chapter nine is available on line. It's postscript, but i was able to read it online. It's an interesting read. And they mention this function. They don't really explain it. I like things spelled out for me. According to the Wikipedia article, Mathemeticians spent a very long time on this. I'm a limited mortal. I don't have time like that. The joke is that the Ackermann function's compute time goes up as 2 ^ 2 ... ^2, where the number of raisings to powers is related to the input values. The result also goes up pretty fast. So (a 3 17) might not fit in a 32 bit integer. And no 32 bit machine will have stack space or cache space to cope anyway.

Why bring this up? Well, at first glance, it looks alot like the change counting function. It's worthwhile to see how they're different, to get an idea of the run time of functions. This brick wall function is not computable for even moderate input values in practice.

Scheme For Enlightenment Part Eighteen - Ackermann

The Ackermann function is often used as a benchmark. It beats the crap out of your recursion system. But even with that caveat, it isn't a very good benchmark. Mainly, it's tough to scale it for reasonable run time for various systems. You can't just feed it new arguments and extrapolate times, though it could be put into a simple loop. The function is pretty simple. It only uses addition and subtraction. It has surprising runtime. There are tons of implementations out there. Here's one.

(define (a n m)
    (if (eqv? n 0) (+ m 1)
  (if (eqv? m 0)
      (a (- n 1) 1)
      (a (- n 1) (a n (- m 1))))))

The function a takes two arguments, n and m. If n is zero, it returns m + 1. This is the base condition, and eventually calls will be made to this ground state. If n isn't zero, then if m is zero, it calls itself with n - 1 and 1. Finally, if both n and m are not zero, it returns a funny nested call. It calls itself with n - 1, but the second argument is the return value of another call to itself. This last bit is interesting, as the return value of the Ackermann function can be really big. So it isn't clear that this function will ever return. It does. Eventually. If your machine is big enough. And if your Universe has been around long enough.

If you explore this function, you find that it seems to hit a brick wall. The enormous difference in speed between LispMe on the Palm and C on the desktop (146,000x) amounts to essentially nothing. You run into this wall right around (a 3 13).

int ack(int n, int m)
{
    if (n == 0) {
        return ++m;
    }
    if (m == 0) {
        return ack(n - 1, 1);
    } else {
        return ack(n - 1, ack(n, m - 1));
    }
}

So if you feed this C script arguments like (a 1 1), (a 1 13), (a 2 1), (a 2 13), (a 3 1), and even (a 3 11), you get answers quickly (less than 20 seconds). The argument (a 3 12) takes more like a minute, and (a 3 13) takes 3 1/2 minutes. And yet (a 3 14) stubbornly refuses to run. What i get is a stack crash, but only after quite some time goes by.

The Wikipedia article explains what's going on. While you read that, i'll write tomorrow's installment.

Scheme For Enlightenment Part Seventeen - C Change

So the next idea is to see what this looks like in C. I've said before that the Scheme version is fast enough. So this exercise is pointless, meaning that it is an exercise.

It's really handy to pass part of the list and use recursion. Can this be done in C without using a linked list library and making copies of lists? Yes. One might use an array, pass a pointer or an index potentially part way into the array, use a handy delimiter so we know when to stop. No need to make copies. The sub lists end at the same place as the full list. Arrays are dumb lists, but are good enough for this sort of thing.

But the recursive structure is still handy, so we'll continue using it.

#include <stdio.h>
#include <stdlib.h>

/* -1 for end of list of coins */
int coins[] = { 50, 20, 10, 5, 2, 1, -1 };

int cc(int am, int c[]) {
  if (am == 0) {
    return 1;
  } else {
    if (am < 0 || c[0] == -1) {
      return 0;
    } else {
      return cc(am - c[0], &c[0]) + cc(am, &c[1]);
    }
  }
}

int main(int argc, char *argv[]) {
  printf("%d\n", cc(atoi(argv[1]), coins));
  return 0;
}

This version works. But i wondered out loud what it might look like using a more Scheme-like syntax. I'm pretty sure no one (sane) would write it this way. The question mark operator isn't very commonly used. Most C programmers think nested comma operators are hard to read. They are. And yet, formulated this way you can still see what is returned fairly quickly. It's whatever is right after a '?', or the last colon.

/* -1 for end of list of coins */
int coins[] = { 50, 20, 10, 5, 2, 1, -1 };

int cc(int am, int c[]) {
  return (am == 0) ? 1 :
    (am < 0 || c[0] == -1) ? 0 :
      cc(am - c[0], &c[0]) +
      cc(am, &c[1]);
}

Again, the original LispMe version for comparison. I'm still trying to wrap my head around how to spot the Scheme return values. As near as i can tell, there's no way around matching the parenthesis for the if operators. The first one is easy. The second one has triple nested parenthesis. And the else clause of the second if starts with addition. The result of the addition is also possibly returned. I was hoping that the Emacs indention would give visual clues. It does. It says that the second if is nested as a clause of the first. It says that the addition operator is a clause of the second if, and the two cc calls are part of the addition. Look sharp for the two constants that are the first clauses of the if's. They seem to just hang there doing nothing. These can be returned.

; count change
(define coins '(50 20 10 5 2 1))

(define (cc am c)
  (if (eq? am 0) 1
      (if (or (< am 0) (null? c)) 0
   (+ (cc (- am (car c)) c)
      (cc am (cdr c))))))

Scheme For Enlightenment Part Sixteen - Time For Debugging

In Guile, i ran my new example with traces set on addition (+) and on the function, cc. (LispMe supports traces. But Guile's output can be trivially pasted into a text editor for these posts.) For a simple example, i asked for the coins needed for 2 cents.

(trace cc)
(trace +)
(cc 2 coins)

[cc 2 (50 25 10 5 1)]
[cc 2 (25 10 5 1)]
[cc 2 (10 5 1)]
[cc 2 (5 1)]
[cc 2 (1)]
|  [cc 1 (1)]
|  |  [cc 0 (1)]
|  |  [cc 0 ()]
|  |  0
|  [+ 1 0]
|  1
[+ 1 1]
2
2

This says that cc was called with 2 cents, and the list of coins. There were no 50's, so it called itself again without that in the list. And so on until just pennies were represented. It then called itself with one penny subtracted. Then called itself with both pennies subtracted. When nothing is left in the coin list, it returns zero. That caller adds one to that zero and returns it (one). That caller's caller adds one to this one, getting two. Two is returned. Finally, 2 coins is the answer.

Unlike the original script, this one only calls itself once. So, the time is more or less linear with the amount of money one starts with. It will never take much time, even on the Palm, even for largish input. The original script has two calls and exhibits some sort of exponential behavior. Two calls means that it has to branch left and right down some tree at each call level. One call becomes two, which becomes four, which becomes eight, and so on. At twenty calls deep, it's a million branches. Two self referencing calls. That's something to look for.

The trace also shows that the caller has something to do after it calls itself. That means that no tail recursion optimization is available to the language execution system. So, one might expect a stack overflow if one feeds it ten dollars (1000 cents). However, if one adds 100, 500 and 1000 (a dollar, a five dollar, and ten dollar bill) to the list, it turns out that 1000 cents isn't a big deal. The recursion depth has to do with the number of units counted in the answer. As long as that is small, there is no danger. Yet, it might still be worthwhile to write either a tail recursive version, or a straight looping version.

I've no idea how i might write a looping version. It's really handy to do the recursive call with a subset of the coins list. Scheme makes a copy of the list, so the original remains undamaged. I'm sure it can be done, the question is how ugly will it get? This is the kind of enlightenment i'm looking for, by the way.

If we do a trace on the original, we get a longer trace. At first, it subtracts the coins (dollars) until it gets below the amount (2). You can see that cc returns 1 for the first time. That's when it tried the $2 bill. Then it tries a $1 bill, and it needs a second bill to add up to $2. It returns one for the 2 singles, and returns this a bit until it gets to add one for the single $2 bill. It adds zero for other failures, and finally ends up with 2. Traces for larger numbers are much, much longer. But following them shows where it calls itself for the left and right recursive calls. Further, you get a feeling for how the function takes time proportional to maybe n^2, rather than the fully linear function i wrote. More on this idea later.

(trace cc)
(trace +)
(cc 2 coins)

[cc 2 (50 20 10 5 2 1)]
|  [cc -48 (50 20 10 5 2 1)]
|  0
|  [cc 2 (20 10 5 2 1)]
|  |  [cc -18 (20 10 5 2 1)]
|  |  0
|  |  [cc 2 (10 5 2 1)]
|  |  |  [cc -8 (10 5 2 1)]
|  |  |  0
|  |  |  [cc 2 (5 2 1)]
|  |  |  |  [cc -3 (5 2 1)]
|  |  |  |  0
|  |  |  |  [cc 2 (2 1)]
|  |  |  |  |  [cc 0 (2 1)]
|  |  |  |  |  1
|  |  |  |  |  [cc 2 (1)]
|  |  |  |  |  |  [cc 1 (1)]
|  |  |  |  |  |  |  [cc 0 (1)]
|  |  |  |  |  |  |  1
|  |  |  |  |  |  |  [cc 1 ()]
|  |  |  |  |  |  |  0
|  |  |  |  |  |  [+ 1 0]
|  |  |  |  |  |  1
|  |  |  |  |  |  [cc 2 ()]
|  |  |  |  |  |  0
|  |  |  |  |  [+ 1 0]
|  |  |  |  |  1
|  |  |  |  [+ 1 1]
|  |  |  |  2
|  |  |  [+ 0 2]
|  |  |  2
|  |  [+ 0 2]
|  |  2
|  [+ 0 2]
|  2
[+ 0 2]
2
2

Scheme For Enlightenment Part Fifteen - Time Is Change

So this change counting thing turns out to be a benchmark, complete with times run under various hardware on LispMe, MIT Scheme and PocketC (which is not Scheme, or really even C, but runs on a Palm). So i ran it on a 2.8 GHz Pentium 4 under Guile 1.8, and it took 0.156 seconds. Startup for Guile is around 0.028 seconds, so the run time was around 0.128 seconds, which doesn't tell me much. This benchmark is way too short for a modern desktop. I already knew that this P4 was faster than any of the hardware listed. I'd like to know how long other programs might take. The run time on the desktop was so short, one can't really extrapolate to other circumstances with much confidence. And i know nothing about what this program does or how it does it. So i ran it on the Handspring Visor Platinum in LispMe. I needed some way to get the time for the benchmark, so i added this code to the script, set the auto-off on the Palm to thirty minutes (1800 seconds) and ran it saying (doit).

(define (doit)
 (define tk (current-ticks))
 (cc 100 coins)
 (ticks-since tk))

I also ran (ticks-per-sec) to find out that my Palm counts time in hundredths of seconds. All this time stuff is LispMe specific, and i can divide by 100 in my head, so i didn't bother having LispMe do that. I should note that the Palm is otherwise useless when running long programs. I don't care that much that my rechargeable batteries are draining a little quicker than usual. There is no A/C adapter, so there are limits to run time. For example, no overnight runs.

Anyway, it returned 26296, which is 262.96 seconds. That makes my Visor faster than a Palm IIIc, which i already knew. It's not as fast as a Palm Tungsten T3, which might be a newer Arm based Palm. That would make sense too. From the desktop timing above, one might expect scripts to run anywhere from 1600 to 2000 times faster on a desktop than on a Palm. That means that even scripts that seem to take no time at all on the desktop may be impractical on the Palm. One second is half an hour.

My original confusion had to do with my expectations and not (yet) reading the manual. I thought that this script made change. It has many of the elements that i'd expected. The cryptic comment says it counts change. It has a list of dollars or coin values. The function takes an amount. It does some list walking, with car and cdr, checking for the end of the list with null?. It subtracts. But what would a function look like that does what i thought this one does?

; count change. How many coins does it take?
(define coins '(50 25 10 5 1))
(define (cc am c)
  (if (null? c) 0
      (if (< (- am (car c)) 0)
   (cc am (cdr c))
   (+ 1 (cc (- am (car c)) c)))))

For reference, here's the original:

; count change
(define coins '(50 20 10 5 2 1))
;(define coins '(50 25 10 5 1))
(define (cc am c)
  (if (eq? am 0) 1
      (if (or (< am 0) (null? c)) 0
   (+ (cc (- am (car c)) c)
      (cc am (cdr c))))))

They are the same number of lines. Both have two nested if's. They both use car, cdr and null? to walk the list. They both do a bit of the work and call themselves to finish it. They both use addition to count. They both use subtraction to mark that a coin has been used. So how can you tell that it does one thing instead of another? At the moment, it looks like one must step through them to see what each one does.

Scheme For Enlightenment Part Fourteen - Change Is Good

My investigations of Scheme started with LispMe, on the Palm Pilot. One might argue that, without a keyboard, the Palm is an awful environment on which to do programming. And, you'd be right in some ways. Scheme can be a terse language, so my eight words a minute text entry isn't so terrible. LispMe does feature an editor that does parenthesis matching. That helps. Part of the draw of the platform is that it runs on two AAA batteries, and fits in my shirt pocket. So, i can goof around with it whenever i have a few minutes. My Palm is about ten thousand times slower than a desktop. One might expect that this is a limitation. It doesn't seem to be. Lacking a fan or disk drive, the Palm makes no noise unless i ask it to. I'd like a laptop that makes no noise and runs on AA batteries. That's what attracted me to the Nokia.

Once the basic syntax was mastered, i looked around for example code to try. A subdirectory of the LispMe documentation has sample programs. One example that i did not understand in the slightest is called change.lispme.

; count change
(define coins '(50 20 10 5 2 1))
;(define coins '(50 25 10 5 1))
(define (cc am c)
  (if (eq? am 0) 1
      (if (or (< am 0) (null? c)) 0
   (+ (cc (- am (car c)) c)
      (cc am (cdr c))))))

It took some time to figure out how to run it. It takes two arguments. The first argument, am, is compared to zero, and is involved in subtraction. So it's a number. The second argument, c, gets passed to null?, car and cdr. That must be a list. A list, coins, is defined, so try it. I figured it must be a program that counts change, like the comment says.

I'd written something like that in BASIC a million years ago. You feed it 7 cents, and it tells you that you need a nickel and two pennies. But this function returns a single value. So perhaps it counts the coins you need. But when you call this with

(cc 7 coins)

it returns 6, not 3. I figured it was broken, and moved on. But eventually, i finished reading the manual from end to end. (Raise your had if you read manuals from end to end.) In the section entitled Sample programs, this program is introduced as a benchmark. You are supposed to call it with

(cc 100 coins)

The value is described as How many ways are there to change 100$ into 1, 2, 5, 10, 20, 50 dollar bills. Now i'm even more confused. One can use seven singles or one five and two singles. That's 2 ways to change $7, not 6. I have no idea what it's doing.