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.
Posts
No comments:
Post a Comment