Pocket Calculator: Stack

For this calculator, I am working on a more sophisticated stack system than I had for my RPN Scientific Calculator. Instead of stack items being fixed at the maximum length, which wastes a lot of memory, item length varies. With only 4k to work with on the LPC1114, it will be very important to conserve memory wherever possible. As I have it now, each item has a header that indicates its position on the RPN stack, its name, and an ID number for variables in functions. RPN stack positions start at one so that variables marked zero will not appear on the RPN stack. This is useful for named variables, so that they can use the same stack system internally. The ID numbers will allow me to keep track of variables local to functions, so I can easily clear them when the function exits.

The system I have now writes the result of an operation directly to the top of the stack then marks the two consumed items as free memory. This has the advantage of allowing the result to be larger than the operands, which can be useful for things like string concatenation. The screenshot above shows how I was testing the system in C# with a simple calculator that can only add. Freeing items like this will make the stack grow fairly quickly and eventually require garbage collection. The advantage, however, is that calculations should be very fast until garbage collection is required. A slower method would be to scan the stack for a free section that is large enough for the result before adding to the stack, but this will eventually require garbage collection as well. My suspicion is that just adding to the top of the stack will be faster overall, even if garbage collection happens more often.

To keep track of the memory, I decided to implement my own garbage collection system, since malloc in C would lead to unrecoverable fragmentation. On IRC one day I made the mistake of asking about how to implement garbage collected stacks like these internally and ended up wasting over an hour arguing with someone who was convinced I was going about everything totally wrong. In the end, one of the suggestions was to have the calculator user push a 0 onto the stack manually before entering values to be operated on so that the system can overwrite the 0 with the result. This recommendation (and a few of the others given) were just laughably horrible and would seriously cripple the functionality of the calculator. Sometimes people on IRC can give good suggestions, but I also have to remind myself not to argue with people who don't really know what they are talking about but won't admit it.

One of the useful suggestions given by a different person was to use two stacks for calculations. The result goes on the second stack and is then copied back to the main stack overwriting the consumed operands. In theory this system will never need garbage collection, although it seems to me that it will take the same amount of time on average. It may be simpler since calculating free memory, for example, is comparing just one pointer, rather than crawling the stack adding up free chunks. This system assumes, however, that operations always work on the top of the stack, which is not the case when named variables share the same internal stack as the RPN stack. It might make more sense in that case to use the second stack only for named variables and do garbage collection on that stack, while keeping the first stack RPN only to prevent garbage collection.

New project: Pocket Calculator

Recently I got interested in building a very small calculator I can carry around with me. The other calculator projects I worked on are neat, but I don't carry them around because they are too big and fragile. This time I want to make something really practical but also small enough to fit in my pocket. The smallest way I know how to do this with the chips I'm familiar with is using the same LPC1114 in DIP28 package I used for my Programmable RPN Calculator. There are a few changes I would like to make for this calculator, though. First, I want to be able to manipulate all kinds of data on the calculator's stack, such as strings, instead of just floating point BCD numbers. Second, I plan to redo the BCD format I used in the other calculators to store the least significant digits first, which should make them a little easier to deal with. Third, I plan to make all items on the stack variable length, rather than fixed length like on my other calculators. This will be necessary for this calculator since I plan to store the whole stack in the 4k RAM the microcontroller has, instead of on an external SPI RAM chip.

The main new feature I want this calculator to have is a BASIC interpreter. My experience with the first RPN calculator I worked on showed how much of the microcontroller's flash can be eaten up by interface code, so I really don't think I could fit all the calculator functions and interpreter in the LPC1114's 32k of flash. Instead, I plan to store a virtual machine on the chip that can interpret code stored on a large capacity flash or FRAM chip. Retrieving the code over SPI and interpreting it will be much slower than executing code natively on the chip, but I think it will be fast enough for the UI, BASIC editor, and maybe even the tokenizing part of the BASIC editor. On one hand I could switch to a chip with bigger flash, which I am not anxious to do, but I will need some kind of virtual machine anyway to interpret the code generated by the BASIC editor, so it is no loss to use the same virtual machine for the UI. The BASIC programs and editor data will be stored on an SPI SRAM chip, which should work fast enough to edit and tokenize programs, while all the stack and program variables will be stored on the microcontroller.