Tuesday, February 12, 2008

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.

2 comments:

Fred said...

Hi, I'm Fred Bayer, the author of LispMe and found your blog via Google Alerts.

When counting change, you obviously missed the two-dollar bill (coin? I mixed this up in the docs, too ;-)

You can change 7$ into:
1111111
111112
11122
1222
115
25

That's 6 ways, just as (cc 7 coins) says.

Anyway, thanks for sharing your experience with LispMe!

Stephen said...

Right you are. I even had the coins commented out and the dollars 'live'. If you use the coins coins definition, you get '2', as you'd expect.