Forth for Enlightenment, part seven of ten, Backwords 3

At this point, a diversion to playing the game is in order. If you examine the program, you might notice that when the program ends, it always says "You win!". You could quit before winning, but the game isn't that difficult. You always win. Compare that to a simple eye-hand coordination game like Tetris. There, you always lose. Always. With this positive reinforcement, one might expect that players would never stop playing.

There's a very simple algorithm for coming up with a solution to any problem. And, it turns out that 2 * n - 3 (on the HP-28, that's n 2 * 3 -) moves are required, as a maximum, and usually fewer. And when i learned this game so many ages ago, that's about all i knew about it. I had to figure out what the algorithm was. And it's pretty simple.

Note that if you get the last symbol, the "i" into the right most position, you should never have to move it again. So, if you build the string backwards one symbol at a time, you're done. What you do is search for "i", reverse it to the left most position. Then with "9", reverse it to the right most position. Then search for "h" and do the same. This seems to take two reverses per digit, so for a string with n symbols, you should have to perform 2 * n moves. But when you get to the first symbol, a in this case, it's already where you need it. So that's two moves you don't need, or 2 * n - 2. The remaining exercise is to figure out what other move you don't need. In any case, often, when you search for a symbol, it's already in the first position, so you don't need to get it there. Sometimes it's already in the position you need it to go to, so you save both moves. So the formula gets you a maximum number of moves. It may be fewer.

One might ask if there are optimum solutions that don't follow this algorithm. And there are. And in my opinion, that's where the real fun for this game lies. I've written optimal solution finders in C and Perl. And even the Perl version can find all optimal solutions for puzzles of length 9 in an hour on a modern computer. The C version can do it in under a second. How many puzzles of length 9 are there? Here's how to figure this out. If you're looking for a random puzzle, the first position can be any of 9 symbols. But having chosen one of these, there are only 8 symbols to choose from for the next symbol. So the first two symbols can be 9 * 8. Continue this way until the last symbol, from which there is only one left. The answer turns out to be 9! - that is 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 362,880. I'd like to say that this was computed with my factorial program, but it had already been deleted. So the built in FACT function was used instead. Blame it on the low total memory area of the HP-28C.

Once one has an optimal solution generator, then one can compare the simply algorithm performance to the optimal solutions. In this table, Moves is that number of moves required. Optimal is the number of games with that many moves, and Auto is the number of games with that many moves using the simple algorithm. You can see that zero moves (starting with the solution) through two moves have the same number of games. That's because for those games, the optimal solution is the same as the easy solution. But there are no games where the optimal solutin requires more than ten moves. This table is for games of length nine.

Moves	Optimal	Auto
0	1	1
1	8	8
2	56	56
3	391	252
4	2278	980
5	10666	2968
6	38015	7798
7	93585	16836
8	132697	31396
9	79379	48636
10	5804	63868
11	0	68432
12	0	59233
13	0	39268
14	0	18108
15	0	5040

My evolution for puzzle solvers for this game over the years is interesting in it's own right. The first solvers were brute force with minor optimizations. They were written in C, but ran on machines that required hours of CPU time to solve a single puzzle. It would take years to generate all solutions of length 9. Modern computers are easily 10,000 times faster, so it would only be days now. But an idea came to me for solving all puzzles of length 9. One started with the solution. Each possible last move was generated, and that puzzle with the final solution move was recorded. Then, each of those puzzles was subjected to a single move as well. If the puzzle had already been recorded, the solution was ignored. Otherwise the puzzle and the move to get to a solved puzzle was recorded. This proceeded until all puzzles were recorded. In the early 1980's 362,880 puzzles would not fit into RAM except on large and expensive machines. For home machines the answers had to be stored on disk, and searched. By the late 1980's, everything could be kept in RAM even on home machines. But then my buddy Karl came up with an algorithm that could get an optimal solution to a single puzzle essentially instantly. It was so fast that it was quicker to generate puzzle solutions independently than all at once. And, no significant data needed to be stored. Further, with it's principals, one could solve any puzzle by hand, and quickly. Now that this has happened, i don't play the game very much. It's peculiar, but one of the goals of writting these puzzle solvers is to render the game less interesting. And this is done by attempting new techniques, and using the computer to prove that they are, in fact, essentially perfect. In this case, the computer didn't teach me the techniques, however. I have other, more complicated games, where the computer's brute force searching has lead to strategies that can be learned from study of the computer's play.

Forth for Enlightenment, part six of ten, Backwords too

One of the problems that had yet to be solved in the previous post is creating a new puzzle. And, the cat was let out of the bag, in that the HP-28 has no way to write into the middle of a string. However, we have already created a function, REV, that changes a string. Further, if the string starts out with no duplicate characters, it stays having no duplicates. So one idea is to call it a bunch of times with random reversals. The idea is to call the function often enough to randomize the string, but not so often as to take too long. After some experimentation, 30 calls was settled on.

« 1 30 START
    RAND 8 * 2 + FLOOR REV
  NEXT
» 'SHFL' STO

You can test this function by keying in the string "abcdefghi" and pushing the user defined key under 'SHFL'. This function takes about 18 seconds to run. It's too long. Most people can wait about 7 seconds before they start thinking about something else. At 18 seconds, they're thinking about getting a cup of coffee. I don't drink coffee.

Back in 1988, i had an 7.16 MHz 8088 based PC clone (switch selectable to 4.77 MHz). There were two C compilers. Microsoft C 5.0, and Borland's Turbo C. Turbo C seemed like it was infinitely faster. But timing tests showed that it was only three times faster at compiling programs. The expectation was that Borland must have been at least ten times faster. But here's what was really going on. Compiling a program that took 20 seconds in Microsoft's compiler would take about 7 seconds to compile with Borland's Turbo C. It turned out that typical C program files acted exactly this way. For larger projects, there were multiple files, and each turned out to take about 7 seconds to compile with Turbo C. When modifications were made to a program, typically only one file would be edited, and the compiler was smart enough to compile only the edited files. The developer experience was that Turbo C was always quick, while Microsoft C was always slow. It was worse than this, though. Turbo C really understood the new ANSI (now ISO) C standard, where Microsoft C 5.0 would only happily ignore the new syntax. And i encountered real working C code that would actually crash the Microsoft C compiler. Microsoft could refund me the more than three times higher cost any time now, and i wouldn't be quite so pissed off.

All this to say that while this solution is quick to write, it isn't very satisfactory. However, i went on to write the rest of the game.

« CLLCD
  "abcdefghi" SHFL
  1 'BMV' STO
  WHILE DUP "abcdefghi" ≠ REPEAT
    BMV 1 DISP 'BMV' 1 STO+ DUP 2 DISP
    DO UNTIL KEY END STR→ REV
  END
  2 DISP
  "You win" 3 DISP
  'BMV' PURGE
» 'BACK' STO

After you enter this program, you can run it by clicking on the user key labeled 'BACK'. It clears the screen first, and after what seems like forever, it puts up the new random puzzle. It then waits for single key presses. When it gets a digit between 1 and 9, it reverses that many letters, checks to see if you won, and if not, waits for the next key. You might notice that there is a symbol on the top of the screen that says that a program is running, even though it's waiting for you. When you finish the game (that is, when you win), it prints "You win". You can quit a game by pressing the "ON" button. It will probably leave the current puzzle string on the stack.

A closer look at the program shows that it starts with the solution and passes it to SHFL. It creates the variable BMV, with the value 1. This is the count of moves so far. It might have meant "Backwords MoVes". It then loops until the string is the solution string. It displays the current puzzle and the current move. The DO UNTIL KEY END is an idiom to get a character for input. The KEY function does not wait for a key press. There isn't a built-in function to wait for a character. So you must provide the wait loop yourself. The key comes back as a string. What was needed was a number. The STR→ function converts the string into a number. It wasn't my first guess for a function that might do that. It's passed to REV without any error checking. I mean, you could press anything. If you press the SOLV button, it turns out that STR→ can't convert that to anything. The machine beeps, prints "Bad Argument Type" on the screen and stops. There's lots of crap on the stack, too. Not very graceful. If you press the zero key, the first character is duplicated in the string. Pressing the '1' key reverses one character, which is to say that it does nothing. But it does increment your move count. So, confine your entries to 2 through 9. Back in the day, i might have performed better data entry checking. Call me lazy.

Next up is a diversion about playing this game.

Forth for Enlightenment, part five of ten, Backwords

How about a game that fits on this tiny machine that's fun to play? With 2 KB of RAM, this is tough. Fortunately, i have a copy of 101 BASIC Computer Games, which was written mostly using a PDP-11/70 (i got to log into the actual system, briefly, way back when). Anyway, there's a fairly simple game called REVERSE. I call it Backwords. Yes, it's misspelled. I've used the game for a couple purposes over the years. One is as an early program to write in a variety of languages. So, I have versions in C, Perl and OPL.

The game is pretty simple to play. In the original version, the digits from one through nine are used, but as ordered symbols. They start out in non-repeated random order. At each move, the user can reverse the first few digits. That is, the first two, or the first three, or, ... and on up to the first nine digits. The goal is to sort the digits from 1 to 9. Here's an example.

342156789 - Reverse 2 to get
432156789 - Reverse 4 to get
123456789 - you win.

A number of language capabilities have already been used in this series. For whatever reason, i've decided to use the letters 'a' through 'i' for this version. That lets me consider string manipulation.

The first obviously hard problem to solve is to take a string and reverse the first n symbols in it. Imagine a function named REV that takes two arguments, a string, and a number, and returns a string. First, my solution.

« DUP2
DUP 'ACNT' STO 1 SWAP START
  DUP 1 1 SUB
  SWAP 2 20 SUB
NEXT
DROP "" SWAP 1 ACNT START
  SWAP +
NEXT
SWAP DROP SWAP
ACNT 1 + 20 SUB +
'ACNT' PURGE
» 'REV' STO

By the way. I just got my 25 year old HP28 printer working. New batteries were installed. The darkness slider was pushed all the way to full dark. About a meter (three feet) of paper was unspooled. And, it started working. So the main issue is that 25 year old thermal printer paper is pretty marginal, and the most external bits of it didn't work at all. When a function is printed using the printer, it prints the name of the function first, rather than the way i've done it above. I'm giving you the command to save the function.

But back to this function. You feed it a string, like "abcdefghi", and a number, like 3, and it spits out "cbadefghi". A little study of the function reveals that 'ACNT' is a variable used to remember something. It is incremented in the 2nd loop. The value is used with SUB, which is a built in string function to get part of a string. This variable is deleted before the function exits. Beyond that, we really need some stack diagrams to see what's going on. Here, the function is called with a string, and is directed to reverse the first 3 symbols. The stack trace is transposed so that time goes down, and the top of the stack is to the right. That's because web pages are potentially infinitely long, but in this forum, narrow. Stacks are often quite shallow. I'd only seen stack traces horizontally, but i find that i like them vertically now. Note that the Start at the begining is just to show what's on the stack before this segment runs. The START at the end is the loop START function.

Start	"abcdefghi"	3
DUP2	"abcdefghi"	3	"abcdefghi"	3
DUP	"abcdefghi"	3	"abcdefghi"	3	3
'ACNT'	"abcdefghi"	3	"abcdefghi"	3	3	'ACNT'
STO	"abcdefghi"	3	"abcdefghi"	3
1	"abcdefghi"	3	"abcdefghi"	3	1
SWAP	"abcdefghi"	3	"abcdefghi"	1	3
START	"abcdefghi"	3	"abcdefghi"

The DUP2 saves both arguments for later. The DUP is used to make a stack copy of the numeric argument that gets consumed when 'STO' is used to put it into 'ACNT'. Then, the loop needs a start value (1) and an end value, the number to reverse. So in this case, the loop will execute 3 times. The 'START' loop command does not iterate a variable that you can access. So one of the features of the language is that there is often stack setup several commands before a function is called. While you read this setup, it's not at all clear what it's for. And that's why my listing is in little chunks. And it's probably easiest to read these backwards. Which is to say, start with the function, and try to figure out what the arguments are.

So, let's consider the loop. Here, the original arguments are not modified in the loop. So, they're not considered in the stack trace.

Start	"abcdefghi"
DUP	"abcdefghi"	"abcdefghi"
1	"abcdefghi"	"abcdefghi"	1
1	"abcdefghi"	"abcdefghi"	1	1
SUB	"abcdefghi"	"a"
SWAP	"a"	"abcdefhgi"
2	"a"	"abcdefghi"	2
20	"a"	"abcdefghi"	2	20
SUB	"a"	"bcdefghi"
NEXT	"a"	"bcdefghi"

This is just one trip through the loop. In the first loop, it starts with the full string on the stack. It gets copied in the DUP. That's probably because it will get consumed shortly. Two constants, 1, and 1 are put on the stack. Then, SUB is called, which consumes both constants and the copy of the string. SUB takes the string and a position and a length from the stack and returns a string starting at the position and as long as the length. So, in this case, it returns the first character. SWAP pushes that first character one deeper on the stack and exposes the original copy of the string. The constants 2 and 20 are put on the stack, and SUB is called again. A substring is returned, starting with the 2nd character. But the returned string isn't 20 characters long because the original string isn't that long. So, clearly, this SUB returns the string from the 2nd character to the end of the string. And that's it for one pass. Each subsequent run through the loop effectively pushes one more character of the string onto the stack. The loop runs for as many times as we want to reverse.

The next code segment pops each of these characters off the stack and builds a new string. Since they were pushed onto the stack in order "a", "b", "c", they are popped off of the stack in the order "c", "b", "a", which is the reversing that we want.

DROP "" SWAP 1 ACNT START
  SWAP +
NEXT

The DROP discards any remaining string on the stack from the first loop. This exposes the "a", "b", "c" list on the stack. A zero length string is then pushed. This is the start of the answer string being built. A loop from 1 to ACNT (the number to reverse) is started. In each loop, the string being built and the next single character are SWAPed on the stack. Then "+" concatenates the string being built with the single character. All the single characters are consumed by the end of the last run through the loop, leaving the built reversed string. If this isn't clear from the code, build a stack diagram to see how it works. After a while, you end up recognizing patterns like this. Or, you get to be able to visualize the stack processing in your head. Or, you get good enough at the logic to be able to predict what happens. This last is cool, because you've just demonstrated that the Halting Problem can be solved after all, even though Alan Turing proved it can't be. There may be hope for computer program correctness after all.

The last bit does some stack cleanup, gets the rest of the string from the original, and pastes the reversed part and the rest of the string together. There's no loop here, but you may have forgotten some of the stack from the start of the function. So, we'll do a stack trace.

SWAP DROP SWAP
ACNT 1 + 20 SUB +
'ACNT' PURGE

Start	"abcdefghi"	3	"cba"
SWAP	"abcdefghi"	"cba"	3
DROP	"abcdefghi"	"cba"
SWAP	"cba"	"abcdefghi"
ACNT	"cba"	"abcdefghi"	3
1	"cba"	"abcdefghi"	3	1
+	"cba"	"abcdefghi"	4
20	"cba"	"abcdefghi"	4	20
SUB	"cba"	"defghi"
+	"cbadefghi"
'ACNT'	"cbadefghi"	'ACNT'
PURGE	"cbadefghi"

The SWAP exposes the count to reverse, which is then DROPped. The next SWAP exposes the original string. Then ACNT is recalled and one is added to it. The constant 20 is pushed so that the SUB gets the string from position 4 to the end. The "+" concatenates the two strings, yielding the answer. The 'ACNT' PURGE simply deletes the temporary variable.

At this point, the Forth programmer is thinking, "Why was 3, which is the number of characters to reverse, remembered on the stack for all this time, just to DROP it? And indeed, code like "SWAP 1 + SWAP ROT ROT 20 SUB +" would work as a replacement for the above sequence. It's the same length and doesn't need the 'ACNT' variable. Since it is the same length, it is likely to run in about the same amount of time. Then, one could also rewrite the rest of the function to eliminate the 'ACNT' variable. And that rewrite might be slightly shorter or longer. It's highly likely that Forth programmers do this sort of thing all the time. But consider that the 'ACNT' variable is labeled, whereas none of the stack positions are labeled. It's kind of like Star Trek, where on the bridge, there are huge panels full of unlabeled buttons. Labeled variables are easy to read.

It must be admitted that it was my intent to rewrite the function to eliminate the variable. It was easiest to get the gist of the function working by using the variable. I thought of it as a crutch to get the function written. But having gotten it written, it seems to me that it's better the way it is. A down side of using a variable is that some other program might accidently use the same name. Since programs all use the same name space, this function could possibly delete a variable that is in use by some other program. Yet, i have total control over the calling program, so it's simply not going to be an issue. And, a naming convention, such has using the name of the function as a variable name suffix, would also make this a non-issue. On the HP-28C, there's only 2 KB of RAM. That's not much for code and data. On the HP-28S, there's 32 KB of RAM. But even there, only the calling program parts of this function need be considered. Only one program can run at a time.

This function is basically enough to play the game. Key in "abcdefghi", the enter button, and a number like 3. It runs pretty fast, and returns "cbadefghi". It's reasonably fast because the two loops combined have ten functions. If you reverse 9, that's 90 functions. There are another 10 odd functions, so the maximum is about 100 functions. That takes place in a hair over a second. One should see how it performs on unexpected input. Key in other numbers and make sure they return the right result. Does it work right if you try to reverse 1 character? How about something longer than the string, like 20? How about zero? How about -2? Frankly, i was satisfied with it's behavior with unexpected input. This can be controlled by calling code anyway.

One of the design notes that was skipped is interesting. The stack is used to effectively reverse characters in the string. But in a language like C or Perl, it's more likely that pairs of characters would be swapped, using a temporary variable. And that's because in those languages, one can subscript into a string and write whatever you want there. The HP-28 RPL language does not have a function to put a character into the middle of a string. So this simply isn't possible. In fact, i considered not using strings at all. I considered using an array for everything. Arrays can't hold characters or strings. So i'd have to either convert the result array to a string or come up with some other way to display it. It's very likely that using arrays on this calculator would require less code that executes faster on this machine, despite conversion.

This function isn't the whole game. It doesn't know if you've "won", and it doesn't create a randomized string for a starting problem. What is amazing is how much code is needed to turn this almost-game into a game. And that's in the next post.

Forth for Enlightenment, part four of ten, GCD

GCD implements an interesting way to compute Greatest Common Divisor. You remember fractions? Let's say you need to reduce the fraction

210
---
462

They're both even, so you can divide by 2.

210   105
--- = ---
462   231

Uhm... the digits of 105 add to 6, and the digits of 231 add to 6, so they're both divisible by 3.

210   105   35
--- = --- = --
462   231   77

Then, 35 is 5 * 7, and 77 is 7 * 11, so they're both divisible by 7.

210   105   35   5
--- = --- = -- = -
462   231   77   11

So, effectively, 210 / 42 = 5, and 462 / 42 = 11. 42 is the greatest common divisor between 210 and 464. The way this was solved was to attempt to find prime numbers that are factors. And it turned out that it wasn't that difficult. That's because we were able to divide big numbers by small numbers until all the numbers were pretty small. But you might have felt a looming fear that you'd have to do a bigger divide. There are lots of ways to get the greatest common divisor. Astonishingly, there is one that doesn't involve division. In C, it looks something like this:

int gcd(int a, int b) {
  if (a == b) return a;
  if (a > b) {
    return gcd(a - b, a);
  } else {
    return gcd(a, b - a);
  }
}

Let's use this to figure out the GCD of 210 and 462. Since b > a, the first step is to subtract 462 - 210 = 252, so it's gcd(210, 252). Then, b > a, so gcd(210, 252 - 210 = 42). Then gcd(168, 42). Then gcd(126, 42). Then gcd(84, 42). Then gcd(42, 42). Since 42 = 42, the answer is 42. OK, maybe this isn't so easy to do in your head. But there used to be computer processors like the 8080 that did not know how to divide directly. Such processors could use this sort of thing, and they were really relatively fast at it.

Anyway, the recursive version of this function on the HP-28 looks like this.

« DUP2 IF == THEN
      DROP ; return a
   ELSE
      DUP2 IF > THEN
         SWAP DUP ROT - SWAP GCD ; return gcd(a-b, a)
      ELSE
         SWAP DUP ROT SWAP - GCD ; return gcd(a, b-a)
      END
   END
» 'GCD' STO

This GCD function is called with two numbers, which i'll call a and b on the stack. The first thing the function does is make copies of the two arguments. They are then compared. If they are the same as each other, one of them is dropped from the stack. This is the return value of the function. If a and b aren't the same, the if a > b it returns the value from the recursive call of gcd(a - b, a). Let's look at this with a stack trace.

Level	Start	SWAP	DUP	ROT	-	SWAP
3			b	a
2	a	b	a	a	a	a - b
1	b	a	a	b	a - b	a

And then GCD is called. The stack trace for when b > a follows.

Level	Start	SWAP	DUP	ROT	SWAP	-
3			b	a	a
2	a	b	a	a	b	a
1	b	a	a	b	a	b - a

This program works. However, for large arguments it can run out of memory. That is, despite not putting much in the way of data on the stack, it runs out of recursive call depth. For example, it chokes on gcd(100, 101). I wanted to know exactly how deep it could go, and i tried various number pairs that are separated by 1. And gcd(100, 101) failed. So i wrote this little program to find out when it first fails. It starts at 50, and tries up to 200. It then calls gcd(x + 1, x). And, unexpectedly, it returned that gcd(180,179) works. That was really unexpected. It turns out that gcd(179,180) fails. The order of the arguments is important, for no apparent reason.

« 50 200 FOR x
      x
      x 1 + x GCD
      DROP DROP
   NEXT
» 'G' STO

Anyway, the fact that fairly small arguments lead to a stack crash is not good. The C version, using the full -O3 optimization of the gcc compiler, never runs out of memory. That's because this compiler optimizes the tail recursion, and it never generates much of a call stack. Likewise, the Scheme version never runs out of memory. The Scheme language requires that tail recursion optimization is implemented. Perl 6 is supposed to do some simple tail recursion optimization. All my code is in Perl 5, and it fails pretty quickly. It complains of Deep recursion with gcd(101, 100). By gcd(131, 130) it runs out of stack memory. But could the program be written without recursion? Sure. In fact, it's pretty easy. First we'll see what it might look like in C. Often to eliminate tail recursion, all you need is a jump back to the top.

int gcd(int a, int b) {
  while (a != b) {
    if (a > b) {
      a = a - b;
    } else {
      b = b - a;
    }
  }
  return a;
}

What this does is loop until a and b are the same. It changes it's own arguments each loop instead of calling itself. If this is done on the HP-28, then there's no recursion, and large numbers can be handled, given time. Note that the ≠ in the first line is a single HP-28 character, a shifted '='.

« DUP2 WHILE ≠ REPEAT
      DUP2 IF > THEN
         SWAP DUP ROT - SWAP ; repeat with gcd(a-b, a)
      ELSE
         SWAP DUP ROT SWAP - ; repeat with gcd(a, b-a)
      END
      DUP2 ; for the != in WHILE
   END
   DROP ; drop one of the equal a, b.
» 'GCD2' STO

This version is also a little quicker, because the while loop is quicker than a function call. At first, things seem to be moved around at random compared with the original version. The DROP that removed one of the identical values on the stack moved to after the while loop, just as the C version's return statement moved. Otherwise, the first IF became a WHILE.

Is the iterative version easier or harder to follow than the recursive version? This is an important maintenance question. And it isn't clear that either one are very easy. After all, even having stepped through an example, it's not clear how the subtractions end up giving you what amounts to division. And the begining of the answer is that repeated subtraction can be used in division. Think about how you have to guess the next digit in long division. You don't really have to guess. You can try the digit one, do a subtraction of the divisor, and repeat this (while incrementing the answer digit) until just before it goes negative. But that's just a hint. On the other hand, the nonrecursive version demonstrates that nothing needs to be remembered and that the only time something is returned is when a == b.

Razor sharp humor

The radio show Okham's Razor, starring Robyn Williams has a show on humor, from a grammar point of view. It's good, but not very funny. Download it now and listen to it, or read the transcript. I'll wait.

Everyone knows that jokes that are explained are universally not funny. One assumes that people who study humor, called 'jokeologists', are singularly unfunny people. Comedians study humor. Most people will claim that they can't remember jokes. Jokes are generally nonsense - who could remember that? It seems that most people can't tell jokes very well. That may be because they don't practice. A good comedian can tell jokes and make it look easy because they practice telling jokes until the jokes are old and tired. They're literally not funny any more. And that gets us back to how jokeologists are people that are not funny, at least to themselves. But don't feel bad for the poor comedian. The jokes were funny for them once. And they get a rush when the audience is amused.

Groucho used elephants because elephants are inherently funny. He could have use a cow, if cows weren't so cuddly. Groundhogs are funny, but they also might fit in Groucho's pajamas. And shirts aren't nearly as funny as pajamas. Groucho even breaks the rule about explaining his joke, and gets away with it. That's genius. Anyone else trying that would be considered conceited. Content is important. This is the main problem with the humor constructed by ten year olds. It should be noted that your average ten year old knows how to properly use ten thousand rules of grammar. Where a ten year old's attempts at humor go wrong is generally in content, not grammar.

Many of my friends who are mathematicians are some of the funniest people around. Perhaps their jokes are funny because the rules their humor break have no ambiguity to exploit, and when broken shake the foundations of the Universe. Perhaps these jokes are funny because there's a sense that it took more work to create them. Mark Twain said that it takes about two weeks to come up with a really good extemporaneous comment.

The problems with teaching grammar are related to the problems of teaching math(s). 1) The plethora of definitions. 2) The applications that might provide context aren't elucidated. 3) The use of arbitrary rules that are difficult to cope with (where extra work is needed to avoid having a preposition at the very end). 4) The use of vocabulary that is specialized to the point of obfuscation. Math(s) teaching goes further with this obfuscation bit by using symbols that are apparently invented on the spot, often using glyphs pulled from other languages, without explanation. Symbols introduce indirection, which is an irritant to the non-specialist. For the mathematician, if one knows how to go from New York to Detroit, and one knows how to go from Detroit to Boston, then one knows how to go from New York to Boston. The rest of us will get out a map and figure out how to go from New York to Boston directly, since that's likely to be less than a tenth of the distance, as it was even when gas (petrol) was cheaper. Neither math(s) nor grammar make much sense or appear to have much use (power to achieve any likely goals). It's too bad, since both math and grammar are among the most powerful tools ever invented.

When the ten year old says, "My friend and me went to the store", i don't correct it by stating "My friend and I". I explain that 'Me went to the store' doesn't sound as good as 'I went to the store'. I have no idea what the formal rule is. Ten year olds don't get the rule right mainly because they don't think about the whole sentence before it comes out of their mouth. I want to teach the child to think a bit before they speak. It would solve so many other issues.

Just as with the doctor, a ten year old is only a little patient. Computers have infinite patience. If computers could be taught grammar, and were fed a dictionary, could they produce huge amounts of humor? Perhaps IBM's Watson could take up this new avocation.

My favorite one liner is this: A Zen master went to his hot dog vendor and said, "Make me one with everything"'.

I heard it again in the movie "The Bicentennial Man", starring of all people, Robin Williams. There aren't any jokes near it. I'd heard it before, and laughed right away. Some thirty seconds later, someone else in the theater laughed. Then a couple guys laughed at what must have been five minutes. When i tell it, not everyone gets it. I figured that they didn't know what Zen is or something. So i told it to a group of five of my Indian colleagues. They didn't laugh. I asked them about it. One said that "It's not a Zen Master. It's a Buddhist monk." Another said, "And they're vegetarian, so they wouldn't be eating hot dogs." And so on. In fact, i counted nearly as many errors in the joke as words in it. It's not that they didn't get it, it was just too broken for them to be funny. To me, that's what makes it funny. And listing the things wrong with it doesn't diminish it as a joke. Though, to be fair, i've practiced telling it quite a bit.

Forth For Enlightenment, part three of ten, Logic two

Last time, the four digit logic problem was introduced, with solution. This time, we'll develop a brute force solution for the HP-28, which we're thinking of as a Forth language engine.

We're looking for a four digit number. It must be greater than 2000. The digits of this number add to 14. The one hundred's digit is less than the one's digit. The ten's digit is three times the thousands digit. The number must be odd.

Since the number is four digits and greater than 2000, the number must be between 2001 and 9999. That suggests a loop. In Forth, the style is to use lots of little functions to get things done. So, in writing the top level function, we'll imagine that we have helper functions to solve smaller problems. The top level could be a loop that checks every digit. Call it 'TOP'. It effectively enforces the first two rules. The development plan was more or less top down design, bottom up implementation, though with some feedback leading to a little jumping around. It's presented as top down, that is callers first, however. For testing, it should be entered bottom up. The called functions can be tested first. If you don't recall the syntax for something, you can refer to my previous articles. Hewlett Packard has the full manual available as well, though not online or free.

By the way, using lots of little functions isn't how i learned to write C. I use C when performance is everything. When i learned C, subroutine calling always introduced a few instructions of overhead. The incentive is to only write subroutines when they'll be called more than once. But modern C compilers can perform function inlining automatically. And, statically declared functions can be inlined with the original function eliminated entirely. So the effect can be better readability and maintainability without the subroutine call performance penalties or extra code. However, there's still the issue of variable scope, parameter passing and return. So it's not something you can always do. By the way, when entering this routine, NEXT isn't the NEXT key on the machine. It's in the Program Branch menu on the 2nd level. This procedure ironically has you use the NEXT button to get to the 2nd level of the menu. Alternately, you can enter the 4 letters N E X T and a space.

« 2001 9999 FOR x x CHECK NEXT
» 'TOP' STO

So, the next thing to consider is CHECK, which enforces the last four rules. It takes a 4 digit number from the stack (and consumes it). How does it flag any correct answers? The stack is not a good place for this. We could store any answer we get in a variable called 'ANS'. If we assume that we don't know how many correct answers that there might be, 'ANS' could be a list which we can append to. So, TOP needs to initialize this list with an empy list before the loop that calls CHECK. We'll do that in a function called INIT. We might modify INIT later to add anything else that comes up. Also, TOP should recall the value of ANS. Here's the brand new INIT along with the new version of TOP.

« { } 'ANS' STO
» 'INIT' STO

« INIT 2001 9999 FOR x x CHECK NEXT ANS
» 'TOP' STO

Now CHECK needs to break the number into digits. I considered using an array for the digits, and index into the array. But there doesn't seem to be much advantage to that approach. A variable for each digit is OK. I went with 'THO', 'HUN', 'TEN' and 'ONE'. A function 'BRK' breaks the number into digits. The idea is to divide the number by 10 using the HP-28's MOD function - which gets the remainder. That's the low digit. Then divide the number by 10 and use FLOOR to get the integer part. This is repeated, so we'll write a GETDIG function to do that much. GETDIG takes the number to break and returns the new number to break and the digit obtained on the stack. BRK calls it 4 times, storing results.

« DUP 10 MOD 10 SWAP / FLOOR SWAP
» 'GETDIG' STO

« GETDIG 'ONE' STO
   GETDIG 'TEN' STO
   GETDIG 'HUN' STO
   'THO' STO
» 'BRK' STO

This much is easily tested. Type 1234 and using the USER function key setter run 'BRK'. Four variables are created, ONE, TEN, HUN and THO, and pressing those buttons shows their digit values. Testing again with 5678 shows that each value changes appropriately.

The CHECK function has four rules to enforce. The order doesn't matter. If the number passes all four rules, then the 4 digit number is added to the list. The tests are in the functions IS14, ISHLO, IST3T and ISODD. These functions look at the digits stored by BRK and return true or false. They could be all tested and the results ANDed together, but it's probably faster to have nested IFs so that if any are false, it can stop checking. Using AND would eliminate all but one of the IFs. A new typography thing. The →LIST notation is for an HP28 built in function. The function name really starts with a right arrow. In development, i wrote a version that kept the current potential answer on the stack as an unnamed variable. It even worked. But storing it in a real variable called 'PANS' is easier and shorter than goofing around with the stack. It looks like this:

« DUP 'PANS' STO
 BRK
 IF IS14 THEN
  IF ISHLO THEN
   IF IST3T THEN
    IF ISODD THEN
     ANS PANS 1 →LIST + 'ANS' STO ; a solution
    END
   END
  END
 END
» 'CHECK' STO

If there is a solution, it is converted to a list and appended to the ANS list of solutions. This function can't be checked yet. All the called check functions must in place first.

The first rule function is IS14. It checks to see that the digits add to 14. It recalls each digit and adds. It doesn't perform the IF, it just does the compare. The compare returns 0 for false or 1 for true. So Booleans are just numbers.

« THO HUN + TEN + ONE + 14 ==
» 'IS14' STO

One can check this function using 1234 BRK IS14. It should report 0. Then 2165 BRK IS14 should report 1.

The next rule is ISHLO, which checks that the one hundred's digit is less than the one's digit.

« HUN ONE <
» 'ISHLO' STO

2165 BRK ISHLO should report 1. 4321 BRK ISHLO should report 0.

The next rule is IST3T, which checks that the ten's digit is three times the thousands digit. I'm using * instead of X for multiply because that's what you get on an HP-28 when you press the X button when you are creating a function. The letter X could be a variable or function.

« THO 3 * TEN ==
» 'IST3T' STO

4321 BRK IST3T should report 0. 2165 BRK IST3T should report 1.

The last rule is ISODD, which checks that the number must be odd. One imagines that such a function could be handy for other things, and therefore is a candidate for a library function. Then any mistakes you make in creating it could be reused. No, no. Really, libraries are a good thing.

« ONE 2 MOD 1 ==
» 'ISODD' STO

2165 BRK ISODD should report 1. 1234 BRK ISODD should report 0. Visually, it may not be totally clear what it's doing. We don't need to know anything other than the least significant digit. Recall the one's digit, divide it by 2 with the MOD function, and compare the result to 1.

The CHECK function can now be checked using INIT 1234 CHECK ANS. It should report { }. Then INIT 2165 CHECK ANS should report { 2165 }. Of course, if we didn't know a solution to the problem, you'd have to check that TOP yields an answer with TOP.

Running the full program by invoking TOP takes 49:22 (2962 seconds) to run on my HP-28C. It should be faster on an HP-28S, since the processor speed is higher. Optimization or speed was not a particularly big consideration with this program. A logic program like this would be run once. There are no parameters. It should always produce the same answer. But it should be noted that some of the tests report false more often than others, so should be evaluated first. For example, one expects that IS14 is true 1/14th of the time, while ISODD is true half of the time. In fact, ISODD could have been incorportated into TOP's FOR loop by using a STEP clause of 2 and count just the odd numbers. And of course, if speed were required, a modern machine could have been used and with an efficient compiler. One expects that a C version should consume less than a second. That's because 8000 just isn't a very large number. And in fact, even a decade old PC requires only a millisecond, and sometimes reports zero time.

One of the things that is attractive about this language is that the check functions are all really tiny. Indeed, having a compact language makes considerable sense for small machines. I had heard that Forth for the 1970's batch of microcomputers could achieve 1/3rd of the speed that typical programmers could achieve using assembly language. However, i doubt it. If i recall right, the inner loop for a Forth engine required 21 instructions on a z80. This is all overhead. But perhaps the figure was for a Forth system where many of the primitives were in assembly language, and therefore much of the code executed in a Forth system was, in fact, assembly language. Given that Forth is arguably easier to write, that's quite promising. The low memory foot print for Forth is also encouraging. Java has achieved 1/3rd the performance of C, but it started out at about 1/350 of C's speed. Java has only achieved this performance through considerable heroics. It took over ten years to happen. By available evidence, every opportunity to trade memory for speed has been used to achieve it. Java is incredibly memory hungry.

The CHECK function shows that even a little complexity can give rise to an increased programmer burden tracking how the stack is used. Tracking what's on the stack is one of the major challenges with writing and debugging Forth. One ends up drawing stack diagrams all the time. When i wrote this program, the only problem was that the first version of the CHECK function left an extra value on the stack. I didn't happen to notice it, so my first run of TOP ran out of memory due to the accumulating values on the stack every loop.

Even as short as ISODD is, it's not evident from the code what it might be doing to the novice. It's probably more evident to the seasoned Forth programmer. But this forms a barrier to entry, and makes procedural (or imperitive) languages easier in general. In fact, i find that documenting my Forth code to the level of this article is what i need to have a clue even a year later. That's distressing.

Is the application of logic, or the crafting of a program faster if the goal is getting the answer? I'd have to say that the logic was marginally quicker for me. It's not as complicated. It took nearly twice as much text to describe the program as it did the mathematical logic. I don't attempt to solve this sort of logic problem very often. While i'm not currently an HP-28 RPL or Forth guru, i do write programs all the time. I'm much quicker at it than i was towards the start of my programming career. Although the debug cycle was short, the run time was pretty long. I don't count it, as i was able to do other things while it ran. Uhm, i added 440 1 BEEP at the end of TOP to alert me when it was finished with a 1 second long musical A note.

Forth for Enlightenment, part two of ten, Logic problem

Here's a logic problem that i came across while helping a 5th grade student with math. My interest in it is to solve it in a brute force manner on the HP-28C. But before i do that, i'll go through the problem and logic solution. First, the problem.

We're looking for a 4 digit number. It must be greater than 2000. The digits of this number add to 14. The one hundred's digit is less than the one's digit. The ten's digit is three times the thousands digit. The number must be odd.

So, first, the logic solution. In these sorts of logic search problems, you'd like to use the clues to narrow down the search, if possible. We'll start with the first two rules. It's a 4 digit number that is greater than 2000. So, the number is in the range from 2001 to 9999. That's roughly 8,000 numbers to check.

It's not immediately clear that adding digits to 14 helps narrow the search at this point. You'd have to check all 8,000 numbers or something. And for the same reason, we'll skip the hundred's digit rule for now as well. But consider that the ten's digit is three times the thousands digit. Well, the thousand's digit has to be at least 2. Three times two is 6. If the thousand's digit is 3, then the ten's digit must be 9. If the thousand's digit is 4, then ten's digit is 12, which is not a digit. So the thousand's digit must be either 2 or 3. That narrows the search to the range 2069 to 3999. And the number must be 2?6? or 3?9?. Here, i'm using ? to mean any digit. That looks like 200 numbers to check.

Now the hundred's digit must be less than the one's digit. So, for 2?6? numbers, the hundred's digit must be in the range of 0 through 5. For 3?9? numbers, the hundred's digit must be 0 through 8. Let's use [0-5] and [0-8] as notation for single digit ranges. We have 2[0-5]6? and 2[0-8]9? as possibilities. Since the hundred's digit must less than the one's digit, it follows that the one's digit must be greater than the hundred's digit. Since the hundred's digit must be at least zero, the one's digit must be at least one. So the ranges are 2[0-5]6[1-9] and 3[0-8]9[1-9]. That's 54 + 72 numbers or 126 possibilities remaining.

Let's check the rule that the digits must add to 14. In the 3[0-8]9[1-9] case, the two known digits add to 12. So the only valid combination is 0, 2. But since the one's digit must be odd, even this combination must be eliminated. In the 2[0-5]6[1-9] case, two of the digits are known, and add to 8. So the other two digits must add to 6. Since the hundreds digit has to be smaller, the valid combinations are 0, 6, and 1, 5, and 2, 4. Since the one's digit must be odd, that leaves 1, 5. So the answer is 2165.

What does a 5th grade student do with this problem? They guess. It's a 4 digit number. It must be greater than 2000. So the first guessed digit is 2. It's 2???. The "digits add to 14" rule is ignored. The 10's digit is 3x the 1000's digit. So, the guess is 2?6?. There's no rule that the numbers must be unique, but they guess '1' for the hundred's digit all the same. They could have guessed zero, since it's a digit. But they don't know much about zero. So that's 216?. The number must be odd. The next guess is 2163, because 1 was already taken and this is the next odd number. Some 5th graders stop there. And it's not quite the right answer. But really smart 5th graders go back to the "adds to 14" rule, and notice they need 4 more, and so guess 2165. And, it's the right answer.

Is this problem reasonable to hand to a 5th grade student? IMO, no. There are several skills that could have been taught first. For example, one could teach the idea of doing the easy stuff first. But my real complaint is that this exercise teaches the 5th grader to guess at answers, and fairly randomly. Usually, at this age, the guesses are not checked for correctness, and wrong answers come out. So, one should also explicitly teach students to check their answers. This problem also requires quite a bit of estimation and mental juggling for anyone, much less a 5th grader. Sorting the rules by next easiest is another teachable skill. But the school that assigned this problem taught none of these skills. Finally, this is a logic problem with no obvious (or explained) real world analogy. There seems to be no use for knowing how to solve it. Most math can be applied. IMO, it's criminal to expose students to math without explaining what it it might be for.

Admittedly, it took me much longer to solve than it took a smart 5th grader. But that's because i took the time to understand more about the problem. For all i know, there might be more than one solution. I invented notation to help keep track of the possible solutions. I did go with easy constraints first. So, i skipped the "adds to 14" constraint until later. But i also ignored the odd number constraint. I could have invented a [2-9]??[13579] notation. But that's really three notation inventions all at once. And when I was finished, not only did i know that i had an answer, i also knew it was the only answer.

There's a fear of math issue for the 5th grader (and, one imagines, for most of us). If one makes a mistake, one gets the wrong answer. If one adds 2 + 2 and gets 5, it's not close. It's wrong. Fear of math is mostly the fear of failure. That is, you invest your time and effort, but if you get the wrong answer, it's entirely wasted. At least, that's the fear. It's worthwhile to teach the idea that the problems are a challenge. One way to get over the fear is that getting the right answer is rewarding in itself. Frankly, i get a little rush. I find it addictive. I try not to let it go to my head and make me proud and boastful. That's not the person i want to be. But i do want it to build up my self esteam or self confidence. That will make it easier to do the next problem. But along with the fear of failure and wasted investment in time that comes from poor self confidence, there's also the fear that there may be no solution. As an adult working real world problems, i've come across problems that don't appear to have real solutions. Or if real solutions exist, there doesn't seem to be a way to get at them with logic. The 5th grade student should be assured that a solution exists. Still, this problem is way too complex for most parents, let alone typical 5th grade students. How an untrained 5th grade student is supposed to solve it as a homework problem is beyond my reckoning.

I've consumed enough of your consideration on the logic of this problem. The next article will dive into an HP-28 solution.

Forth for Enlightenment, part one of ten, Factorial

My Scheme series introduced factorials in part one (the 2nd post). The factorial function is strictly numerical. The factorial of 5 is 5! = 5 * 4 * 3 * 2 * 1 = 120. The factorial of any number is the product of the integers from 1 up to that number. The numbers are multiplied together. A series using the HP-28 calculator ought to have this function early on. After all, the factorial function works with numbers. So do calculators. But doesn't the HP-28 have a built-in factorial function? Yes it does. And it's fast. And it can deal with fractions. I mean, the factorial of 5 is 5! = 5 * 4 * 3 * 2 * 1 = 120. But what is the factorial of 5.5? Well, there's a gamma function, and it yields 287.9 (with more decimal digits). The gamma function closely tracks the factorial function. For very large factorials, the gamma function can get you an answer that is good enough without doing all those multiplies. The HP-28 can represent numbers up to 10^500. So the FACT function is limited to input up to 253.

If you write your own factorial function, you'll find that it's not as fast as the internal function. The internal function is pretty much instant. It's not clear if they coded it in assembler, if ROM is faster than RAM (as it was with the Texas Instruments TI-59 calculator), or if they used some tricks. It might be a combination of these. One of the tricks it might do is store the answers to all factorials up to 253. Or, they could use less space and only store every tenth factorial. So, 10! is 3,628,800. If you need 11!, you start with 10! and multiply by 11. Then, factorials would be really fast.

I wasn't so much interested in speed as programming. The recursive version is first. It doesn't support the gamma function. Just the multiplication of integers is considered.

« DUP IF 1 ≠ THEN    ; stop at 1. If not...
       DUP ROT *     ; multiply count into product
       SWAP          ; switch prod and count
       1 - FA        ; cnt = cnt - 1, call self
     END
» 'FA' STO

Typography first. The 'FA' STO at the end isn't really part of the function. It's how you enter the function. 'FA' is the function's name.

The function expects two arguments. The number 1, and the factorial to be computed. So, this can be run with 1 5 FA. But it also returns two items on the stack. And the answer, 120, is buried. It returns the answer and the number 1 on the stack. So, get the answer by running DROP. This isn't really clear to an end user, so there should be a wrapper function, which i call 'FAC'.

« 1 SWAP FA DROP
» 'FAC' STO

This FAC fucntion takes one argument, and returns the answer. So 5 FAC returns 120. FA, and therefore FAC, can compute factorials for numbers up to 253 properly. That's from the limitation of numbers, not from running out of memory for stack data.

But let's get back to FA again. In it, the HP-28 function ROT is used which rotates entries on the stack. It's pretty clever. But it's not clear what it should be good for. It works for this program. ROT comes from ROTate. Let's examine how it works. If a, b, and c are on the stack before ROT, then b, c and a are on the stack afterwords. Here it is in table form.

Level	Before ROT	After ROT
3	a	b
2	b	c
1	c	a

Now, FA takes two arguments on the stack, which are 1 and the factorial number to compute. It turns out that the 1 is needed as a running product. The count is multiplied by the current product on each loop down. The current count is at the top of the stack. In the first line, the count is copied, so that there are two of them. The IF consumes one count in the compare to 1. In the line with the count, we want to multiply the count into the product, but we need to remember the count also. So the count is duplicated, and then ROT does it's magic. Finally, we have the multiply. The next line does a SWAP to restore the product and count to where they started. Here's a stack diagram for operations starting in line 2. The stack shows what's on the stack after each operator.

Level	Start	DUP	ROT	*	SWAP	1	-
3		prod	count			prod
2	prod	count	count	count	prod	count	prod
1	count	count	prod	prod * count	count	1	count - 1

Note that in the column with the multilply, prod * count is shown. After that, it's the new product, so just prod is shown. The stack diagram should get you through the operation of this function. Forth programmers use these often. But i wouldn't be surprised if after awhile, idioms involving ROT become second nature. I timed this function with the highest argument, 253. It took 20 seconds. The built in function comes back with the answer almost right away, even for 253.

This is an acedemic excersise, so a version that uses a loop instead of recursion was written next. I used a new name, FACTO. It takes the number to compute, and returns the answer. It's also shorter and simpler.

« 1 SWAP 1 SWAP
     FOR x
       x *        ; multiply count into product
     NEXT
» 'FACTO' STO

The first line with the SWAPs might be confusing. The FOR operator takes two arguments, the start number, and the ending number. The count is already on the stack, but needs to be in level 1. A 1 is needed on level 2 to serve as the start number. A 1 is needed on level 3 to serve as the running product. Here's a stack diagram.

Level	start	1	SWAP	1	SWAP	FOR
3				1	1
2		count	1	count	1
1	count	1	count	1	count	1

The FOR loop's first iteration starts with 1 on the stack, which is the running product. The x in the FOR line is a local variable. It matches the x in the third line. This variable counts from 1 to count, stepping by one each loop. So x * multiplies the current running product by the current count number each loop. The NEXT function marks the end of the FOR loop. The local variable conveniently and automatically is removed when the loop is finished with all iterations. When each loop is finished, the current running product is the only thing on the stack. So when all loops are complete, the complete product is returned.

The start with the SWAPS can be made shorter, if perhaps more complicated. Consider this version:

« 1 1 ROT
     FOR x
       x *        ; multiply count into product
     NEXT
» 'FACTO' STO

Level	start	1	1	ROT	FOR
3			count	1
2		count	1	1
1	count	1	1	count	1

Clearly, it gets the stack to the same place and with 1 fewer command. It might be marginally faster, but it's only one command that is skipped, and only once. It is shorter, so it should take just a tiny bit less memory. While the HP-28C is memory starved, in reality one would use the built-in FACT function, which would take zero memory. It does show that the ROT function is often valuable.

This version of the factorial function is faster than the recursive version. It took 5.8 seconds. That's more than three times faster. It isn't anywhere near as fast as the built-in function, however. It also takes less memory, since it doesn't use more than three stack levels. It doesn't need a helper function.

Since recursion can always be converted to loops, one wonders why recursion is ever needed. And indeed, it isn't. But sometimes recursion is how the problem is presented. If that's the case, then often recursion is a good approach to take. But there are also algorithms that are easier with recursion. The Quick Sort algorithm comes to mind.

Forth for Enlightenment, part zero of ten - count

Back in 2008, i posted a series of articles as an introduction to the scheme computer language, and basically functional programming in general. One of the quotes one hears from functional programming enthusiasts says that languages are either functional or disfunctional. From my perspective, C can be used as a functional language, even if that isn't the usual case. For that matter, assembler can be used as a structured language if just a little discipline is used, despite only directly supporting GOTO. And back in the 70's, with 8 bit processors such as the 8080, z80, 6502, 6809, or 1800 (all of which i consider to be 16 bit processors, since that's the address space), memory space was so tight that having little tiny functions made sense. Therefore, assembler programs often had a functional feel to them.

Anyway, the next language i wanted to visit, or in this case revist, is Forth. I could download a Forth system for Linux, but i happen to have something like Forth in a more portable form. I have an HP-28C calculator from Hewlett-Packard. I got it in late 1986, i think. When i saw the HP-28S, i wished i'd gotten that one instead. The HP-28C has 2 KB RAM. The HP-28S has 32 KB RAM. The speed increase of the HP-28S would have been irrelevant to me. This might be considered blasphemy. But i had access to much faster computers with C compilers if i needed to perform serious computations. Battery life is more important. Battery life on the HP-28C is excellent, by the way. But lots of RAM (16 times more) would have opened up the range of potential applications dramatically. For example, one of my benchmarks involves performing a matrix multiply using three 20x20 arrays. That's 1,200 cells, which won't fit in 2 KB of RAM. Numbers take at least 8 bytes of storage. So 1,200 cells takes at least 9,600 bytes. So, it will fit fine in 32 KB, but not even close in 2 KB.

Anyway, the HP-28C doesn't implement Forth exactly. HP called the language RPL. This stands for Reverse Polish Lisp, though it looks more like Forth than Lisp. Forth was already available. In fact, Rockwell sold a version of their 6502 computer chip with a Forth system in ROM on the chip. The way i heard it, Rockwell was working on a version of the 6502 that would include ROM on the chip. Engineers asked around for some code that could be tested, and one guy handed them some code. They manufactured a chip, and gave it to the guy with the code for testing. Does it work? Sure. What is it? It's a Forth system. So then they had a product with no documentation. They had an external 2 KB ROM that implemented a text editor and floppy disk system for development. All this to say, Forth is extremely bit-efficient.

So, the HP-28C is something like Forth. Close enough for what i wanted to do. My 25 year old calculator works fine. And, it's very portable, allowing me to doodle with it while waiting for various things to happen. One of the Wiki pages suggests that the battery door tends to break, and most of these devices are taped shut. My battery door is intact. I love the machine. The keys have very nice tactile feedback, and there's a "back up a character" key that lets you edit numbers. Further, you can undo operations to find out what you did. And I have the printer. All this makes me gravitate towards this machine when i need to do my taxes. There just aren't the fat-finger unreliability issues i often have with other machines. But while i programmed the device extensively in the late 80's, i really only retained fairly simple arithmetic skills until recently. By comparison, i have another device from the late 80's that has a BASIC like language. After a couple decades of disuse, i found i could program it without the manual. So, there's something about Lisp and Forth like languages that make them more difficult to read and write than strictly procedural languages. The barrier to entry is higher. Yet, there are many who would advocate that procedural languages should be relegated to only where optimization is required. My opinion is that this is idea is neither practical nor desirable.

In Forth (or RPL), one puts one or more objects (which can be any of several types, but numbers for now) onto the stack, and then one runs a function which consumes value(s), and leaves some result(s). A function can call other functions. I recall that one of the manuals warns against having a function call itself, or call a function that ends up calling itself - since that can result in an infinite loop. But that's exactly what i wanted to do first. Not an infinite loop, but have a function call itself. The way it could work properly is if there was some way of terminating the recursive call somehow. RPL has IF...THEN...ELSE...END conditionals. So the first thing i did was create a recursive counting function. It counts down to zero. Yes, this function alway returns zero, if it works. And usually, that wouldn't be very interesting. But what i wanted to know was approximately how deep recursion can work on this system. I should also point out that there are two stacks in Forth. There's a call stack where the return address of the caller goes, and there's a data stack. In C (and many other languages), the call stack and data stack are implemented with a single structure. It makes memory management easier - especially for local variables. It has some disadvantages as well, though these are managed easily.

Two issues in typography need to be mentioned first. The HP-28 has single characters for double less than and double greater than. I'll use the web characters '«' and '»'. These single characters start and end procedures. If a procedure is stored in a variable - that is, if it has a name, then it is a callable function. Like Lisp (and Scheme), you can have unnamed procedures. I don't find unnamed procedures very valuable on a hand held calculator. They have limited, but important use on bigger systems. The other typographical note is that the HP-28 has a single character that is an '=' with a '/' through it. It means not equal, and it is represented with '≠'. Finally, I show end of line comments starting with a semicolon ';'. I don't actually enter comments into the calculator. Amazingly, comments can be entered into programs. I'm not using the HP-28 convention. With that, here is the first program, which i called 'BCNT'.

« DUP IF 0 ≠ THEN  ; If not zero...
   1 - BCNT        ; Subtract 1 and call self
  END              ; ends the IF.  Returns 0
» 'BCNT' STO       ; end of the procedure

Note that IF consumes the value on the stack. So this program starts with DUP. This makes a copy of the value on the top of the stack. Perhaps it retrieves the value, then pushes it twice. The next line puts the value '1' on the stack, and issues '-', which subtracts 1 from whatever was on the stack, and puts the result back on the stack. It then calls itself. The END is the end of the IF statement from the first line. And that's it. Except that the key to figuring out how it works is that if the value isn't zero, it subtracts one and calls itself. But what happens when it returns? Nothing. It hits the END, which ends the IF statement, but that doesn't actually do anything. It returns from the function, carrying with it whatever value was on the stack. But if it returned, it's always zero that's on the stack. It's worthwhile to trace what it does for a small value, like 3.

After typing in the program, i typed 'BCNT, the 'enter' key, and the STO key, which binds the program the the variable named 'BCNT'. Yes, that was a single quote, then the letters B C N & T. The 'enter' key closed the string with a single quote. You get used to it. To run it, type a number and the name of the function. The machine has a USER menu where the new function name appears under a function key. So, it's really enter a number an press a single key. I'm giving detailed instructions on how to enter programs because, after decades of disuse, i'd forgotten most of it. Should you have a functioning multiple decade old calculator to try this on, here it is.

After typing in the program, i typed 'BCNT, the 'enter' key, and the STO key, which binds the program the the variable named 'BCNT'. Yes, that was a single quote, then the letters B C N & T. The 'enter' key closed the string with a single quote. You get used to it. To run it, type a number and the name of the function. The machine has a USER menu where the new function name appears under a function key. So, it's really enter a number and press a single key. I'm giving detailed instructions on how to enter programs because, after decades of disuse, i'd forgotten most of it. Should you have a functioning multiple decade old calculator to try this on (i've seen it in two museums), here it is.

Anyway, with some trial and error, i discovered that this function could count down to zero from 317. There was nothing else in memory. The HP-28 is clearly not performing any tail recursion optimization. Otherwise it could count down from any integer it could represent, given enough time. I also timed this maximum depth count. And it counts at 18.2 per second. Calling and returning are fairly high overhead operations. A simple loop counts faster. That means that loops are faster than recursion. That's also true in C, lisp and scheme systems i've used. It's not a surprize.

This program adds 1000 to the current value on the stack, by adding 1 repeatedly. I uses a loop. It counts at 60.75 per second.

« 1 1000 START   ; Peform 1000 loops
    1 +          ; add 1 to the stack.
    NEXT         ; end of the loop
» 'C' STO        ; end of the procedure

I called it this version 'C'. Run it by typing any number and 'C' from the USER menu function key. So far, we have functions, recursive calls (which look like any other kind of call), conditional if, and loops. This is enough to write almost anything, given memory and time. More to come.