💾 Archived View for gemini.njms.ca › december_adventure › 2024.gmi captured on 2024-12-17 at 09:37:16. Gemini links have been rewritten to link to archived content
-=-=-=-=-=-=-
This year I'm participating in December Adventure, a month long response to Advent of Code where you're challenged to take some time each day to work on a software project
eli_oat's overview of December Adventure
I'll be working on ponderosa, a 16 bit virtual computing platform and extended metaphor for a forest. For more information and to see it first hand, check out my repository:
nat/ponderosa at git.nats.solutions
Today was a pretty low energy day, but I still managed to find some time to work on ponderosa. I continued looking into the issue I wrote about yesterday, with negative relative coordinates producing some weird results. I definitely think my awkward juggling of integer types had something to do with it, but making a more robust overflow checking system didn't fix the problem. After a lot of digging I realized the problem goes a lot deeper. The issue has to do with my implementation of the tree's land access buffer. Originally, I'd implemented it as an array—each cell in the 2D array corresponds to a cell in the land. The thing is, the tree's buffer doesn't account for overflow in the land as-is. So, one cell in the land may correspond to more than one cell in the land, and thus one might overwrite the latter when the buffer is being reconciled.
Basically, I need to reimplement the buffer in some way that accounts for this. Not today, though. Maybe tomorrow
Mostly bug fixes today. While trying to build some test programs, I noticed that forestry operations weren't actually affecting the land. Turns out I forgot to actually reconcile the tree's buffer with the land itself at the end of each generation. There were some subtleties to how to implement that correctly. Another issue I noticed was that my method for pulling from the trunk stack was actually trying to pull from the root stack; that was kind of hard to debug. A third issue, which I started looking into, had to do with negative indexes when trying to access the land relative to the base of a tree. I have a good sense for what's wrong at this point, but I don't think I have the time to finish it today. Part of it has to do with the fact that in my code for reconciling the trees' buffers from earlier, I forgot to account for it, but that's lead me to some related issues that are taking some more time.
Today I have the assembler working, in that it can assemble programs that'll be accepted by the ponderosa CPU. Still missing a number of instructions, but I'm pretty happy with what I managed to accomplish today. I got kind of hyperfixated on it; I don't expect I would have made nearly as much progress if I didn't spend as much of my day on it.
I also took the time to make the changes to the arithmetic instructions I described yesterday. Now, all arithmetic instructions can take an immediate argument, except for the not instruction.
Tomorrow I expect I'll be able to implement translations for the rest of the instructions in the assembler. From there, the next step would be to implement some example programs and build better tools for working with and visualizing ponderosa ROMs.
Today's goal was to implement parsing for stack instructions. In the end, I managed to implement parsing for the push instruction, which has a slightly different format because ideally it needs a lot of room to push larger numbers. Even then, the largest number you can push with a single instruction is 511. I'm a bit cautious about pseudo-instructions because ponderosa is supposed to have a hard limitation on how many instructions can be in a particular rule, but it'd be nice to do something similar to what MIPS does here to make pushing large numbers a little easier.
I think at some point I'm going to reconfigure the arithmetic instructions to support immediate values. The largest immediate value you could use would be relatively small (on the order of 64 or 128) but it's probably still worth it, and would make much better use of the available bit width for instructions. It'd also make dealing with the slightly exceptional left and right instructions a lot easier. That's what I was really hoping to accomplish in writing this assembler: the issues with ponderosa are becoming clearer the more I work around it rather than on it specifically, which gives me a pathway to improving it.
A lot of my time got eaten up by me accidentally reinventing how to handle exceptions in Rust, realizing it's way easier than I was making it out to be, and then rewriting everything to be more idiomatic. I had what I thought was a pretty good macro to facilitate doing early returns, but then I remembered that's what the question mark operator is for…
Today I started working on rule parsing. This is a lot more complicated than parsing the ROM's "front matter," so I've broken it down into small parts. Today I got most of the scaffolding done, and I have a routine that parses binary operations in math format. Doing the unary operators, of which there are many more, will be a lot easier I suspect. I can probably adapt what I already have.
Going through this stuff again gives me the feeling that I could have been a lot more careful in how I designed the instruction formats. Some of this feels kind of haphazard. But I did ostensibly put a good amount of thought into it. It's hard to be thrifty with only 16 bits, particularly when I'm mostly used to thinking in terms of gigabytes.
Day 7 of December Adventure, day one of implementing an assembly language. At this point I have a program that can take an input file and parse a complete description of the land. The next step will be parsing rule definitions.
Trying really hard not to overthink how it looks. The main goal here is to put something together that'll make writing programs a little easier. At some point I'd like to put a little more thought into a simple and friendly language for interacting with the ponderosa CPU. The big issue at this point is that I've never designed a programming language before and don't know much of the theory. Individually, I think I'd be a lot more interested in building tools to visualize forests rather than programming them, though we'll have to see how that pans out. Maybe what I'm working on now will gradually grow into something a little more sophisticated.
I finally implemented semaphores! That means all 29 instructions have been implemented, and what a round number it is. If I can come up with three more, that'll make for a round 32.
At this point, I think the next move is to create a small assembly language that'll make programming it easier. Once I can try out some programs with it, then I'll get a better idea of where the bugs and limitations are. That's probably what I'll start on tomorrow.
There's one big feature I haven't implemented yet: portals. At least, that's what I'm tentatively calling them. I envision portals being the way forests can receive input after they've started running. The idea is to have some number of contiguous cells mapped to a file that can be written to. Once a generation, the data of that file is read and written to the corresponding cells, which can then be acted on by trees. This would also help the limitation of trees with long rules "starving" the ones with shorter rules; you could potentially break a big forest into smaller, logical chunks that communicate with one another via portals. This would probably be a lot more efficient if the message passing was all done in memory, for which I suppose I'd need some kind of hypervisor. This is where we firmly get out of the realm of things that forestry jargon can accommodate.
Didn't have a lot of energy to work on things today, but in the spirit of sticking to commitments I took this opportunity to do some chores, cleaning up dead code, etc. These last few days I've tried to plan around having energy to work on ponderosa, though today it seems like I basically forgot to. So, I'll have to make an effort to do that tomorrow morning.
I actually managed to get things running today. In the end it amounted to temporarily commenting out some problematic blocks and patiently letting myself be guided by the borrow checker. I've found in general it helps a lot to store lots of references to trees as necessary, while making sure trees can only be directly accessed from a central hash map that maps numeric IDs to Tree structs. This is kind of hard for me to reason about as someone used to dynamic programming languages but I'm figuring things out as I go.
I also had the time to take another look at an issue I encountered and promptly gave up on a while back related to tree composting. Turns out the thrust of it was a typo I was having a hard time picking up on. Besides that, there also were some ownership rules I was running afoul of, but I managed to sort those out as well.
I only have two instructions left to implement: op_wait and op_signal. Those are going to take some more careful consideration, as I wrote yesterday. I really don't like the idea of having to keep semaphore values as a separate data structure but I'm also not sure there's a way to square the circle of how semaphores work and each tree having access to the land as it was at the beginning of a generation; the whole point of a semaphore is that it reflects state *at that moment*. So, while it may be "impure," it might also be strictly necessary
The two big challenges I have stalling further progress are as follows:
Today, I managed to complete challenge one. What's left to deal with is challenge two.
My plan has the nice property of all trees "seeing" the same environment at the beginning of their execution, which would make things like Conway's Game of Life almost trivial to implement in ponderosa assembly.
I've implemented an interface for trees to interact with their "span" as a separate entity from the land itself. I think I'll need a way to "punch through" the span for things like semaphores. This design might require that semaphores are not literally a value stored in the land; that's something I'll have to put some more thought into.
Overall, I feel like I'm on track with this project again!
Instead of working on ponderosa, I decided today would be the day that I finally reconstruct the database I use to build my website. I have a sort of meta-static site generator that generates files for both my gemlog and website, which is why I'm able to mirror all my articles between the two of them. Eventually I think I'd like to replace the set up with PHP and CGI scripts; having spent a good half year using PHP at work it's grown on me quite a bit, and today I had to relearn how hacky my "meta-static site generator" really is.
But, as a result, I was able to publish another article which motivates why I wanted to take up the December Adventure. Maybe tomorrow I'll actually get around to working on ponderosa :)
The Leetcodification of everything you love
I made a significant breakthrough on this project literally two days before my laptop died last month and a day after I'd made my weekly back up (I suppose this is why they encourage you to back up your devices every day…). A lot of what's stalled me working on it is the inertia, since the problem I was dealing with at the time was hard enough that I was starting to doubt whether or not I was even capable of solving it, and the solution wasn't specific enough for me to remember how to reimplement it as is. But, obviously, I *have* been able to solve it at least once, so the goal for today was to just open my text editor and see what happens.
In the end, I accidentally used the time I'd put aside for the project to fix my Gemini server, though I suppose that was worthwhile, given I can share this with you now. I did, however, make some edits to the specification document and upload the project to my Forgejo server.