4 ms·

This is so over my head I couldn't grasp it with a jetpack.

db48x 5y ago
Don’t underestimate yourself. His interpreter just has to read a byte, look up the definition in a dictionary, and then jump to the appropriate subroutine. The one he wrote reads from stdin; if you were actually bootstrapping a new machine from scratch you would be writing it to the boot sector of a disk, so it would need to read input from later sectors of that disk. Not really difficult to arrange, though the details would differ on different types of computers. You would just have it read a fixed number of sectors, long enough to read in your bootstrap program, and then everything would be in memory from then on out. It has a rather minimal set of commands in that dictionary to start with. The next thing you want to do is give it a program that adds new commands to the dictionary to make the language less annoying and more capable. This is in the bootstrap.fs file. The first two lines define a command called `\`, which reads and discards bytes from the program until it finds a newline byte. This allows the language to include comments. It also defines a command called ` ` which does nothing except allow the program to include spaces for formatting. :) Commands are added by writing to memory to add new entries to the dictionary. The dictionary is a linked list, and the bootstrap program “allocates” memory by simply starting at the beginning of free memory and writing values consecutively. That’s good enough to extend the dictionary as long as it never goes backwards. I haven’t read the whole bootstrap program, but presumably it implements something more sophisticated than that. On the other hand, memory is cheap. You can do a lot even if you never deallocate anything. Since the language is so simple, you can learn to decypher it pretty easily. You’ll pretty quickly start to notice elements that are frequently repeated, such as `h@!h@C+h!`, which stores the byte on the stack to the current address in memory, then moves the current address to point to the next location in memory. In C that would be `*ptr++ = foo`. These repeated bits are soon defined as new commands, so that the program gradually gets less repetitive. My favorite trick is actually one he does to improve readability. The command to read input, `k`, reads a single byte as a signed integer. If you want to read in something like -5, you could include that as a single byte with the value 251 (or 0xFB). Instead, he writes it as `k0k5-`. This reads the byte `0`, which has value 48 (0x30), then the value 53 (0x35), and subtracts them. But _visually_, it looks almost exactly like `0-5` to the programmer which is indeed the same as negative 5. This is used in the `\` command to jump backwards by 5 instructions after every read that doesn’t find a newline, for example. On line 645 he finally gets around to defining a command that negates a number, on line 1153 he defines one to read in a number in either decimal or hexadecimal, and on line 1304 is the command that reads in a double–quoted string. After that he can start writing out numbers almost directly: `s" -5" >number` reads in a decimal -5, but now it can be trivially modified to contain any number you need.

Don’t underestimate yourself. His interpreter just has to read a byte, look up the definition in a dictionary, and then jump to the appropriate subroutine. The one he wrote reads from stdin; if you were actually bootstrapping a new machine from scratch you would be writing it to the boot sector of a disk, so it would need to read input from later sectors of that disk. Not really difficult to arrange, though the details would differ on different types of computers. You would just have it read a fixed number of sectors, long enough to read in your bootstrap program, and then everything would be in memory from then on out. It has a rather minimal set of commands in that dictionary to start with. The next thing you want to do is give it a program that adds new commands to the dictionary to make the language less annoying and more capable. This is in the bootstrap.fs file. The first two lines define a command called `\`, which reads and discards bytes from the program until it finds a newline byte. This allows the language to include comments. It also defines a command called ` ` which does nothing except allow the program to include spaces for formatting. :) Commands are added by writing to memory to add new entries to the dictionary. The dictionary is a linked list, and the bootstrap program “allocates” memory by simply starting at the beginning of free memory and writing values consecutively. That’s good enough to extend the dictionary as long as it never goes backwards. I haven’t read the whole bootstrap program, but presumably it implements something more sophisticated than that. On the other hand, memory is cheap. You can do a lot even if you never deallocate anything. Since the language is so simple, you can learn to decypher it pretty easily. You’ll pretty quickly start to notice elements that are frequently repeated, such as `h@!h@C+h!`, which stores the byte on the stack to the current address in memory, then moves the current address to point to the next location in memory. In C that would be `*ptr++ = foo`. These repeated bits are soon defined as new commands, so that the program gradually gets less repetitive. My favorite trick is actually one he does to improve readability. The command to read input, `k`, reads a single byte as a signed integer. If you want to read in something like -5, you could include that as a single byte with the value 251 (or 0xFB). Instead, he writes it as `k0k5-`. This reads the byte `0`, which has value 48 (0x30), then the value 53 (0x35), and subtracts them. But _visually_, it looks almost exactly like `0-5` to the programmer which is indeed the same as negative 5. This is used in the `\` command to jump backwards by 5 instructions after every read that doesn’t find a newline, for example. On line 645 he finally gets around to defining a command that negates a number, on line 1153 he defines one to read in a number in either decimal or hexadecimal, and on line 1304 is the command that reads in a double–quoted string. After that he can start writing out numbers almost directly: `s" -5" >number` reads in a decimal -5, but now it can be trivially modified to contain any number you need.