4 ms·

Hi kragen! I've always loved the various Forth implementations -- especially the more terse ones! That's because in the continuity spectrum of Compilers/OS'es

• kragen 4y ago
  I'm glad you enjoyed it! Have you tried running it? One could reasonably argue that SKF isn't really "booting" on an old 386 PC; though it'll probably run on one, you need to get Linux running on the PC first, because SKF can't read the input source code from disk or write the output executable to disk on its own, and it needs something to load it into memory and start it running as well. And, unlike real Forths, it's a batch-mode compiler: it can't be used interactively. The sense in which it's a "tiny bootstrap" is that it's a compiler that compiles itself, not the sense of "bootstrapping" that means to load oneself into RAM. (I know you know this, but anyone else reading this later may not.) — ⁂ — In 02007 I wrote https://github.com/kragen/tokthr https://github.com/kragen/tokthr as an investigation into precisely the question of "just how small a fully functional Forth environment could be packed". By using bytecode ("token threading") rather than DTC or ITC, tokthr provides "90% of" a traditional interactive Forth environment in about 1400 bytes, all bytecode except for a 239-byte machine-code core. Unfortunately, because it's incomplete, it's impossible to know whether the remaining 10% of the functionality requires adding another 10% to the code or another 90%—as in the old joke about how the first 90% of the project takes the first 90% of the schedule, and the remaining 10% takes the other 90%. My best guess, though, is that it'd be about 1700 bytes, so in 2KiB you'd have about 350 bytes left for the user program, which is probably about 64–128 lines of code. Interpretation can be slow, but it sure makes for denser code, and you don't need to have two copies of the interpreted code in RAM when you're bootstrapping. There have definitely been 8KiB interactive Forth systems, and I think there have been 4KiB ones, which was also the size Wozniak required for a BASIC interpreter on the Apple. tokthr suggests that 2KiB might be achievable for a stripped-down Forth. Óscar Toledo G.'s bootOS https://github.com/nanochess/bootOS https://github.com/nanochess/bootOS is a particularly interesting non-Forth system in this OS/IDE/debugger vein, because it has enough functionality to write programs (in hexadecimal machine code), load them from disk, edit them, and save them, all in 512 bytes of code. It does require somewhat more than 512 bytes of RAM, but still very little—much less than has ever been present on a machine that it could run on. — ⁂ — My thinking on Forth, which is something I'm an amateur at, has changed a little bit since I wrote tokthr and SKF. I think that if you evaluate Forth as a programming language, it's generally going to look pretty deficient. It's more bug-prone and harder to read than alternatives like C, Lisp, BASIC, or assembly language, although it does support compile-time metaprogramming and powerful abstraction facilities. But if you ask the question, "What's the simplest usable development environment I can build?" the answer starts to look a lot like Forth, especially if you're running on a poorly characterized piece of hardware where you need to prioritize interactive experimentation with I/O ports. It gives you an interactive, scriptable environment for poking around, similar to what Tcl gives you https://yosefk.com/blog/i-cant-believe-im-praising-tcl.html https://yosefk.com/blog/i-cant-believe-im-praising-tcl.html but in 4 kilobytes rather than the megabyte and a half Tcl demands. And the environment includes not just a scriptable command line and the usual programming-language things like arithmetic, subroutines, variables, and arrays, but also compile-time metaprogramming, virtual memory, an editor that allows you to recompile code at screenful granularity (usually), a memory dumper, access to raw hardware devices, an assembler (usually), sometimes multithreading, and a sort of debugger. As in BASIC or Lisp or Python or Tcl, your UI is a REPL, so your programming language is also your command language; but, unlike in BASIC, your command language is extensible, so in many cases it can also work as the user interface to your application. In BASIC or in a C debugger you number the lines of code in your program; in Forth you name them, so you can "single-step" your program by running them one at a time. Then the ? word gives you a quick way to examine your variable values interactively, again as in a debugger. Like, here's me trying to interactively debug a square-root routine into existence in GForth on Linux: variable square variable guess ok : sqstep square @ guess @ / guess + 2/ guess ! ; ok 80346 square ! 1 guess ! ok sqstep ok guess ? 70107476356745 ok sqstep guess ? 70107476316572 ok sqstep guess ? 70107476316572 ok Hmm, I don't know how that's possible, is division doing some kind of double precision thing I've forgotten about? 80346 1 / . 80346 ok Oh, oops, I was adding the memory address of GUESS instead of the value stored in it. : sqstep square @ guess @ / guess @ + 2/ guess ! ; redefined sqstep ok 1 guess ! sqstep guess ? 40173 ok Skipping over 42 more lines of embarrassing floundering around over half an hour omitted (see interactive-forth.md in http://canonical.org/~kragen/pavnotes2.git http://canonical.org/~kragen/pavnotes2.git if you want the details) I eventually ended up with the following working code: : newtloop begin sqstep guess @ dup * square @ - abs guess @ < until ; redefined newtloop ok : newtsqrt dup square ! guess ! newtloop guess @ ; redefined newtsqrt ok 120 newtsqrt . 11 ok By virtue of doing everything interactively and in the most incremental possible way, I was able to get it to work properly even though I kept making dumb type errors, inverted the sense of my tests, couldn't remember the semantics of division, and so on. I was able to blunder my way into working code. And that's a very powerful thing, as you know if you've ever debugged someone else's Excel spreadsheet. And, in cases where the behavior of the underlying system is actually unknown—maybe it's a buggy hardware prototype—that kind of instant experimentation is the best possible facility to have at your fingertips. — ⁂ — However, in the case of the square root function, I probably would have gotten it working faster by reasoning through the algorithm's behavior instead of blundering around. In fact, it was only when I stopped for a while to think about the problem that I came up with the termination approach used in the code above. In this sense Forth's interactivity, like Excel's, can be an "attractive nuisance": a thing that tempts you into getting yourself into trouble. Being able to read the code easily so the bugs in it were obvious probably would have been helpful, too. The other attractive nuisance in Forth is cleverness. Forth is a puzzle box: you can always find a cleverer way to do whatever you've done, for whatever your ideal of cleverness is. You can always find a way to do it in Forth in less RAM, fewer lines of code, fewer VARIABLEs, in a more orthogonal and reusable way, with words that read more naturally, etc. (A particularly pernicious form of the cleverness problem is trying to use the stacks instead of VARIABLEs, which is always possible in the Turing-tarpit way but results in very slow progress.) It's the opposite extreme from what MJD says about Java in https://blog.plover.com/prog/Java.html https://blog.plover.com/prog/Java.html: > I am glad to have had the experience of programming in Java. I liked programming in Java mainly because I found it very relaxing. With a bad language, like say Fortran or csh, you struggle to do anything at all, and the language fights with you every step of the way forward. With a good language there is a different kind of struggle, to take advantage of the language's strengths, to get the maximum amount of functionality, and to achieve the clearest possible expression. > Java is neither a good nor a bad language. It is a mediocre language, and there is no struggle. In Haskell or even in Perl you are always worrying about whether you are doing something in the cleanest and the best way. In Java, you can forget about doing it in the cleanest or the best way, because that is impossible. Whatever you do, however hard you try, the code will come out mediocre, verbose, redundant, and bloated, and the only thing you can do is relax and keep turning the crank until the necessary amount of code has come out of the spout. If it takes ten times as much code as it would to program in Haskell, that is all right, because the IDE will generate half of it for you, and you are still being paid to write the other half. Forth is, in this taxonomy, a good language. In my attempt above it took me half an hour to write a simple square root function, which you could maybe describe as "you struggle to do anything at all, and the language fights with you every step of the way forward," but in fact the language semantics were perfectly adequate, just unfamiliar, and most of my problem was a lack of mental clarity about the algorithm. As long as you use variables roughly as often as you'd use them in other programming languages, instead of bending over backwards to never use them, there's nothing particularly difficult about writing code in Forth rather than C; it's a purely syntactic transformation from if (a >= MOD_ADLER) a -= MOD_ADLER; to a @ MOD_ADLER >= if MOD_ADLER negate a +! then and the like. And also you can do compile-time metaprogramming and you have closures so you don't suffer as much as you do in C. But in Forth you're always worrying about whether you're doing something in the cleanest and the best way. Should I define a -! word? Maybe that if statement should be a word of its own that takes A and/or MOD_ADLER as parameters? Maybe I should do the subtraction and just conditionally store the result into A if it's still positive?
  • peter_d_sherman 4y ago
    Hi Kragen! Wow, what an answer! It's longer and more well-nuanced than some of my posts on HN -- and some of my posts are long and well-nuanced! Hey, if you would like to take this conversation to an email discussion, I would certainly welcome you there! My email address is: peter.d.sherman@gmail.com >"My thinking on Forth, which is something I'm an amateur at, has changed a little bit since I wrote tokthr and SKF. I think that if you evaluate Forth as a programming language, it's generally going to look pretty deficient. It's more bug-prone and harder to read than alternatives like C, Lisp, BASIC, or assembly language, although it does support compile-time metaprogramming and powerful abstraction facilities." [...] >"But in Forth you're always worrying about whether you're doing something in the cleanest and the best way. Should I define a -! word? Maybe that if statement should be a word of its own that takes A and/or MOD_ADLER as parameters? Maybe I should do the subtraction and just conditionally store the result into A if it's still positive?" All of what you say about Forth is true -- but if and only if -- we evaluate it compared to the many other, frequently better, programming languages that exist today... I don't evaluate Forth in this way. "Beauty is in the eye of the beholder" -- as they say! You see, why Forth is so beautiful to me (at least as the smallest possible version of Forth that can still be extended) -- is because it exists somewhere in the "problem continuum" (for lack of a better term!) -- of all of the problems that computer scientists in history, exploring new technology for the first time (in history -- what's old to us was new to them) would have had to face down, and solve. I am interested in that "problem continuum" -- of problems -- now well-solved -- but historically, that would have not been the case! In other words, let's suppose you are one of the early computer scientists, and your computer only has a row of switches to specify an address, and another row of switches to specify a value for that address, and another switch which when toggled, writes the value of the row of switches into the address specified by the other row. OK, so that's a very primitive computer! No display, no keyboard, no nothing! So now from that computer -- what's the next thing that needs to be built to advance that state of computer science one step forward? Like, maybe that's you connect that computer to a typewriter with typewriter capabilities, like the Teletype 33 ASR: https://en.wikipedia.org/wiki/Teletype_Model_33 https://en.wikipedia.org/wiki/Teletype_Model_33 But, you first need a serial port (of sorts!) to do that! Also if you want to type data to/from the computer -- then you need a program to do that (of which, the first one of those COULD NOT have been entered via the teletype -- it would have had to been entered by switches, by hand!) You see computer history -- would have been, had we lived there, had we experienced it -- a "continuum of problems". With specific incremental solutions at those points in time -- each of which would incrementally, incrementally (a little bit here, a little bit there!) -- get us a bit closer to the computer programs, programming languages and systems of today -- that we all know and love! You see, I want to know how the early historical computer pioneers -- basically had to "MacGuyver" things (again, for lack of a better term!) -- Forth is an important step in all of that, because at the point in time that you have the smallest working Forth -- then you can pretty much start creating the infrastructure for all of the OS'es/Compilers/Debuggers, etc. -- that are to follow! But if and only if you know what you're doing! For example, using an existing compiler (as is done in many college-level compiler writing classes) to compile a new compiler -- is "cheating" (how did that original compiler come into existence in the first place? You see, it wouldn't have started its life as a fully functional compiler! It could have started its life as an assembler, and then features added (high level constructs) and eventually assembly language conversion removed -- until finally it became one of the first generation of true compilers, etc. Now, Forth is not a first generation true compiler -- but it is a very important stepping stone (again, in the "problem continuum", for lack of a better term!) -- for getting there one day -- being able to write assemblers and debuggers in Forth, and eventually extend them enough such that one day they're a true compiler -- like perhaps Algol/C/Pascal (was Algol ever a true one-pass compiler that didn't require a linker?). But anyway, you see what I'm looking for! Anyway, thanks for your awesome response, and if you'd like to continue this discussion, just shoot me an email, peter.d.sherman@gmail.com ! -Peter