scheme-official

[scheme-official]

It's public!

The code for all the stuff ranted about so far is finally on github, webpages are not yet up to date but I'm getting there. Progress will be slow for the next couple weeks, as I finally got the raspberry to boot properly, and will thus be busy building a computer around that and porting Minix to it.

Have fun with it, fell free to reach out about it!

[scheme-official]

Oh, shit, right, I had a blog for this. Yeah tldr I found out that the env stuff was interacting with some other code in a really dumb way. Compiler is fully operational now, though I still have to implement strings and vectors and atomic memory and the like. And also a repl for the self-hosting image stuff. Those happen to be intertwined, so it's a bit complicated. I have ideas, but I was pretty burned out yesterday (from unrelated stuff), spent most of today on errands, and decided to spend my productive time on updating the corresponding webpage for the project - I have a lot to catch it up on, I fear the "implementation" section might have to be redone from scratch . . .

But yeah good news, compiler works now. Takes it about 12ms to compile ack(3,3) and ~20ms to actually run it. I might wanna get around to optimizing stuff a bit, but for now it works well enough (also that would probably require a bytecode intermediary, and as much as I love how flexible Scheme can be in defining new stuff, rewriting the entire output pipeline from scratch is uh, annoying).

[scheme-official]

Another delayed update: factorial works, but I'm still having issues with managing stack frame-local bindings. Realized yesterday that part of the issue is that the lambda preprocessor (implemented as a slimmed-down interpreter that tracks bindings) has the same issue the compiler had regarding state, and spent most of the day implementing the same fix. That fixed a lot of problems, but I'm still working on the rest. On my morning walk today I realized that the way it's handled corrupts one of the scratch registers (which I started using because the stack was getting corrupted, except it doesn't work when we need multiple values and also the stack kinda works now), so imma have to fix that. High hopes that Ackermann works soon, then I can get to weirder stuff!

[scheme-official]

Short but important update: factorial works! Had to rewrite some functions regarding closure creation and calling (and also some mathematical primitives), and now the factorial demo code compiles, runs, and produces correct results!

[scheme-official]

. . . yeah so um. Haven't gotten around to working on the lisper today, but um, updates from yesterday, I fixed the memory issue. No, it was not the GC. No, it was not unoptimized tailcalling either.

It was the one (print env) that I had put in all the way back before I implemented environments via objects, which now got confused that it was getting a closure instead of a list, and attempted printing the entire contents of every single variable including itself and obviously crashing the memory in the process. And yeah I guess I could have fixed that eventually by somehow optimizing the printing routines to just . . . not use any memory at all I guess? (sidenote, I use exactly one (1) routine to output stuff to a file, and it is called putch - you can guess what it does, and why it's a teensy bit of a memory issue when everything else is handled lisp-side).

But hey, compiler works - pretty well if I might add -, and tailcalls are optimized now, so the "Scheme" interpreter is in fact an actual Scheme interpreter now (since we have tailcalls)! I have ideas regarding continuations that I will not be pursuing in the foreseeable future, and it seems it can occasionally confuse itself regarding bindings - the factorial demo is not compiling properly. But hey, progress!

[scheme-official]

Update: didn't work on the lisper today because I decided to quickly throw together a space partitioning demo for a guy I chatted with last week, which led to me rewriting most of my graphic framework's interface with SDL2. Also a large part of my perlin noise library. Also, alpha blending is broken now.

At least the memory overflow sounds like an easy problem to fix, and once I've done that the compiler should be fully functional. Wish me luck that I may fix it tomorrow!

[scheme-official]

Okay so apparently the "dumbest possible solution I can think of, ffs this is moronic there HAS to be a better solution lemme open wikipedia real quick" is actually called trampoline functions and is the de-facto standard way of implementing tail calls in an interpreter :D they were actually really easy to implement, and it even let me clean up a lot of GC stuff I'd strewn throughout the codebase! I also realized I could easily expand it to fix the global environment collection nastiness as well!

Didn't get around to the debug stack, but I did confirm my suspicion that objects create circular guards, which then crash the clean-up. Unfortunately, I am not allowed to modify the data and I'd really rather not use auxilliary memory, so I have no idea how to solve this. But everything else is looking a lot better now!

[scheme-official]

Okayyy. Update. Short one because I have a lot of work ahead of me.

As mentioned, the compiler worked pretty well, and I was testing it with more and more complex expressions. The vast majority worked. defun did not. Turns out, I cannot set environments from inside functions as I had assumed. Once again, using Scheme almost feels like cheating, because introducing a state-based object-oriented paradigm to work around this took all of three lines of code (more if you include all the class functions for "temporarily incrementing the stack index for N cycles" and the like, but those are just vanity at this point).

Well, it didn't work. And it produced 65mb of debug output when I tried taking a look at it (for context, the entire source code of the project so far is ~50mb). Now, I'm pretty sure I know what the issue is, and it shouldn't be a hard fix (more elaborate garbage tagging, slight changes to memory guards and overflow handling), but those 65mb really bothered me, so I think I'll take this chance to overhaul some parts that have been bothering me for a while.

First off, tail recursion. Ironic as it seems for a "Scheme interpreter and compiler", I have not yet implemented tail recursion (except for tail sequences in begin, but c'mon). It won't really make it much more efficient, but it will explicitly separate the Scheme callstack (so far, to evaluate recursive expressions, the interpreter has been calling eval recursively) (the interpreter is written in C), which should make Scheme calls a lot easier to manage. I'm not entirely sure how to do this - tail sequences were trivially doable with a for-loop, but arbitrary tail calls are much tricker (and goto's are frowned upon for good reason). Fortunately, R5RS has a nice list of which cases need handling, and I have ideas for them.

Once we have that, a proper debug stack would be grand. So far, the debug output has been listing every call to eval (plus a lot more intermediary information), and I've had to figure out the exact call structure myself. Which is annoying but usually doable and simple enough to implement, but for 65mb it just won't do. I'll probably have to add a bunch of auxiliary debug structures (which I don't like, because it makes the code a lot bigger and more complex without necessarily adding anything directly related to its function), but it should help figuring things out a lot.

[scheme-official]

No update yesterday because I spent almost the entire day trying to get the bullshit BCM2837 to work. Long story short, I'll be getting oscillator probes tomorrow.

Today was much more productive. Rewrote the entire compiler (Scheme and Assembly parts) to use a different tagging system (which is ~700loc total, so not that much) - had to rethink some functions. Then went on to system testing, since integration testing between Scheme and Assembly seemed more complicated.

It produces code, and it works pretty well! I'm slowly ramping up the complexity of expressions and working out whatever bugs pop out. Also started considering using a bytecode intermediary (because things are not complicated enough) in order to optimize some Assembly nastiness - eg it outputs about ten times more instructions than necessary to put constants on the stack . . .

Oh right, I also had more adventures with the garbage collector. Turns out I'd overlooked yet another little edgecase that came back to bite me, and I had to work that one out as well (the collector uses special garbage tags to denote values it's already collected, except I couldn't use those for the guards since the guards use references and not direct values, so I had to put an extra thing around it). But now it works!

[scheme-official]

Wooo, compiler works! Spent most of the day on a goose chase along various tagging bugs - tldr the Scheme part of the compilers assumes everything is tagged, while the assembly builtins don't. I'm contemplating rewriting all the tagging stuff - besides aforementioned issues, the compiler also uses different tags than the interpreter, which is even more annoying to keep track of.

But yeah that minor thorn aside, the compiler works! Parses lambdas and environments correctly, interfaces properly with the bulitins (tags aside), slots in properly with the assembler/emulator infrastructure. Quite happy with how that's turning out. I'll have to do some more witchcraft to get a REPL going (global environments gonna be a mess to figure out), but yeah.

Oh also, I did get around to working on Minix! Fortunately, the BCM2835 is much better documented, and I was able to throw together a working first OS prototype in about an hour (including cross-compiler and assembler)! Unfortunately, the warnings were very misplaced in the docs, and it seems I managed to fry the UART interface, which is gonna make things a LOT harder now . . .

[scheme-official]

Yeah so I spent pretty much the entirety of the last two days trying to figure out that garbage collector conundrum, and it was very frustrating, and I kinda gave up, and then it hit me as I was walking the dog. Took one extra line of code. It's almost humiliating that I didn't think of that earlier.

But yeah gc works now, test case compiles, haven't yet checked it but I should have a functioning compiler now!

[scheme-official]

Good news, I'm almost done unit-testing the compiler, and most of it works like a charm! Some integration testing next, and I should be able to compile code soon!

Bad news: the part that doesn't work like a charm is that the garbage collector fritzes out and overwrites global data we set from a local environment - and I have no idea how to solve this. Hopefully I'll come up with something better tomorrow!

[scheme-official]

No update yesterday because the train broke and I had to spend the night in a bus. Good news is that the compiler largely works! Had to mess around with how the i/o routines handled strings and numbers, but details aside, the code was surprisingly usable!

However, it did keep running out of memory because it kept filling up the string buffer with numbers (implemented as symbols - arithmetics operate digit-wise). That got pretty annoying, so I finally got around to rewriting the interpreter to tag types.

Also had a brief aside this morning in retrofitting the SpaceCore terrain generator to work with heightmaps to test some worldbuilding stuff a friend did, then did a small deep dive into "The Secret of Monkey Island", then started messing around with the map projector while brainstorming a pirate sailing game. Honestly, whenever the Lisp special interest runs out, I'm hoping it gets back to Minix instead of starting yet another game . . .

[scheme-official]

Oh right, you kids had a thing going on. I forgot about that. Well, have fun in the forest!

There is a microscopic chance I might decide to potentially make my own programming language blog

Do it! Become one of many. All it takes is willingness to travel to Findland once a week.

I'm rather curious about which language. But best not say lest someone qould take it.

[scheme-official]

Wait what, Finland?

There is a microscopic chance I might decide to potentially make my own programming language blog

Do it! Become one of many. All it takes is willingness to travel to Findland once a week.

I'm rather curious about which language. But best not say lest someone qould take it.

[scheme-official]

So, macros were not hygienic (as suspected). I spent three hours perusing various Scheme implementations and getting more and more frustrated with how incapable people seem to be with making code concise and readable and USABLE, and uh . . . yeah the actual fix took me like, ten minutes.

Tldr: 'macros' are code that generates code - they work kind of like functions (aka lambdas), in that they are bound to a name (well, optional, really), and when you call them with arguments, they do stuff to those arguments. They are different from functions in that instead of evaluating their arguments and then doing something to the values, they shuffle the code of their arguments. Conveniently, we can implement them almost like regular functions - they take arguments, bind them to the names specified when the lambda was defined, then we evaluate the body of the lambda/macro, and return something. The difference is that to create a lambda closure (an environment where the arguments are bound to them names), we evaluate each argument and then bind it to the name - but with macros, we just bind whatever happened to be there to the name and pass it on to the body of the macro. This means that within the body of the macro, we are free to use the usual Lisp functions to inspect, (re)arrange, and reformat the code of the arguments however we want. Then, once the macro has returned a value, we evaluate that - the macro's job is to generate code, so the value it returns should be valid code (enforcing this is up to the author of the macro, and they are free to violate this as they see fit).

I wrote three paragraphs regarding implementing 'cond' via 'if' with macros before I decided that might be a bit too much for tumblr, so I'm saving this for the webpage. Good news is that it shouldn't be long before I finally get back around to writing that!

[scheme-official]

Yeah so uh. Estimating a bit regarding when the train departed, but implementing macros took me a grand total of 7 minutes.

More testing required regarding whether they are "hygienic", but also holy shit this was so much easier than anticipated.