I'm guessing by kernel he meant any program that can host other programs in some way.
Can you clarify what batch process means in this case?
I /think/ the authors definition of a kernel is a program that can host other programs in some way.
A video game on a boot sector can't do that (even though it likely would have it's own kernel to function), but some kind of input loop to write memory could.
And what would do that “read data off disk, then write other data back”, if not a program? Even if you use a monitor (https://en.wikipedia.org/wiki/Machine_code_monitor) to write a program, that’s still a program.
The only way to avoid that is to hand-punch a tape or something like that (with lots of practice and patience, it may be possible to program a small PROM or write an early floppy by hand)
I've compiled some simple C (microcontroller blinky) by hand. Then assembled and linked the output, and written the machine code into a HEX (Intel format) file. Then tested it on the micro. It's a rather fun exercise (Type 2 fun).
Fun with extra twists and turns you weren't expecting. Usually quite an adventure, some unintended learning and growth. Hopefully a story worth telling.
As opposed to the obvious doing an activity for fun.
On a Commodore 64, the kernal [sic] was similar to the BIOS on a PC, with display and keyboard handlers, IO routines, etc. When you first turned on the machine, something had to say "** COMMODORE 64 BASIC V2 **", and that something was the kernal.
I always kind of thought the kernel was, at its core, the thing that handles processes and hardware io. Even if you use one of those tiny micro kernels it has to handle processes and present an api through which to communicate with devices (even if it doesn’t handle the devices itself.) I think it’s true you need a kernel to compile a kernel in this sense.
...and the EDSAC crew decided that that sort of thing was a mug's game as far back as 1949, so they added what amounts to a machine to do that for you (the Initial Orders unit). (No, I don't really miss the Altair, no matter how ecstatic I was about it in high school. Toogle-booting is fun maybe twice.)
Technically not true. As all computer starts with hardware and only that so e input process is needed. Of course, it really depends on howto define kennel. But you do not need very high level. Some feedback is better. Otherwise just input something, computer can take on. The “software” on the hardware need not be complete.
That's precisely the joke. "Kernel" here means the minimal feature set that let you compile a kernel. The sentence is tautological, except perhaps for the definition of "minimal", because there are various flavors of "minimal" (e.g. absolute minimum, practical minimum, ergonomic minimum...).
I find it amusing how often trying to do complex tasks with simple constraints, always ends up back at stack based languages. Probably why the stack based turing machine is academically important.
I suppose that prior art influences things. In my case, I went "a separate text editor won't fit, I need a REPL", and that basically filtered to just Forth and Lisp. It would be interesting to see what subset of Lisp would fit in a bootsector, but I wouldn't get my hopes up.
sectorlisp right now is 800 bytes but it implements LISP well enough that you can use its built-in LISP IDE to implement your own LISP engine on top of sectorlisp using high-level functional programming techniques. https://youtu.be/hvTHZ6E0Abo If we can trim down the code size another 250 bytes then all this will fit in the master boot record.
Man, Forth is such a cool language. It really captures (what I perceive to be) the "hacker mentality" of powerful but simple tools, without much overt concern for polish/slick interfaces.
I mean I know a lot of foundational code of yesteryear was hacked together in C, but C lacks a certain ineffable cachet in my view. A cachet that Forth definitely has.
FORTH is a fun little class of languages. These are easy to implement; in a few KB you can have a working development environment, with a screen editor, debugger and whatnot.
In my experience, FORTH doesn't really scale to big projects, or things that need a lot of dynamic allocation. It's great at low-level stuff like hardware bringup (we used it on the Atari ST, back in the day, and even the hardware engineers were writing code to exercise their designs), but doing anything at scale is going to be tough. You probably don't want to write a modern web server platform in it, for instance. But it's probably great on an Arduino with a serial port.
There were a lot of games started at Atari in FORTH ("Hey, this is simple! Who needs to hire expensive assembly language programmers?") but the only project that shipped was the pinball machine "Four by Four". I saw a bunch of expensive disasters and mostly steered away from it.
These were written by third parties and published by Atari. Atari did not have any game programmers on the payroll at that point (all the software folks were working on the ST and related things). There might have been some contracting going on, but the days of an Atari employee coming up with a new game idea and shipping a new cartridge were gone.
Worms? was a FORTH jam, or at least that's what David Maynard said in a recent interview (since it seems this thread is becoming a list of FORTH games.)
Surprise. Fortran was used as well but Forth was used quite a bit by NASA. In some ways it is extremely auditable. A handful of assembler functions sit at the bottom the rest is Forth. Minimal numbers of variables in memory if code is written to use the data stack for inputs and outputs to functions. Much easier to certify than GCC. :-)
There were a number of Shuttle experiments where the control software was written in Forth. It gives you a control interpreter out of the box and also bit level access to hardware so you can write custom drivers and then script the hardware control in the functions you wrote or compile them where speed is required, using an 8K..12K kernel.
The Cassini probe used Forth software running on a Forth 2-stack CPU.
No, and I didn't mean spaceflight either. Which Forth was apparently used for but I didn't recall until I googled it.
I associate Fortran with nuclear reactor engineers. I was told they were some of the earliest users of it, maybe even before it was out of "beta", so to speak.
Quote from 1955:
"Considerable effort is now being made by various groups to develop automatic coding techniques which would make the use of a large machine feasible on this kind of problem. The system of greatest interest is Fortran, which is being set up by IBM for the 704; there is some chance that it will be available by the end of the year. To use it, the engineer who is setting up the problem must formulate it in a somewhat modified algebraic notation, which is then entered directly in the machine. As a result, the task of stating detailed machine orders and assigning addresses, which is largely a clerical task and constitutes most of the work of coding, is completely eliminated. Some scepticism has been expressed by experienced programmers, on the grounds that the resulting code would be far less efficient than one designed by hand. Even if this is the case, however, a system of this kind will still have a wide range of applicability in reactor analysis and should be kept in mind in considering future machine work."
"scale up" is usually used as a counter-argument to a solution that is perfectly fitted to the scale it is supposed to be used. This is nothing but a salesmen argument.
It is not only in the Forth community that one hears disaster stories like: we did the software for client X in 3 weeks with a team of 4 programmers, but after a few decades they lost the know-how of our language so they decided to rewrite in a "modern" language that "can scale". They hired a team of 40 developers, it took 3 years, and the result is less reliable than the original. The only thing that scaled up were the development and maintenance costs and the only thing that was modernized is HR policy (i.e. let's hire disposable developers).
If you need dynamic allocation, you can invent a Forth dialect for your specific needs. And implement it in Forth. A domain-specific language for your problem domain, embedded in Forth.
Consider control statements like conditionals or loops. They are implemented in Forth to express what is essential for imperative programming.
You can just as easily implement region handling much like what Cyclone [1] did. Invent region, dispose region, allocate within region, etc. You can augment semicolon word to not only check for control statements to be valid, but also check for region handling correctness.
\ Forth dynamic storage managment.
\
\ By Don Hopkins, University of Maryland
\ Modified by Mitch Bradley, Bradley Forthware
\ Public Domain
\
\ First fit storage allocation of blocks of varying size.
\ Blocks are prefixed with a usage flag and a length count.
\ Free blocks are collapsed downwards during free-memory and while
\ searching during allocate-memory. Based on the algorithm described
\ in Knuth's _An_Introduction_To_Data_Structures_With_Applications_,
\ sections 5-6.2 and 5-6.3, pp. 501-511.
Forth systems running on C libraries can also call back to the native malloc/free implementation, but it's nice to have a pure FORTH implementation for embedded applications.
This may be a tangent but I've encountered this code comment before and been confused; nice to be able to reply to its author! The confusion is that there's no book by Knuth called "An Introduction to Data Structures With Applications" (and Knuth's TAOCP doesn't have a section 5.6; his Chapter 5 on Sorting ends with 5.5 and whatever stuff is in TAOCP about memory allocation is Chapter 2; page 501 would put you in "Answers to Exercises"). Most likely what was intended is the book "An Introduction to Data Structures With Applications" by Jean-Paul Tremblay and Paul G. Sorenson (https://www.amazon.com/dp/0070651574 , ISBN 0070651574, https://books.google.com/books?id=ha4mAAAAMAAJ) which from what I can find online has 7 chapters:
1. Information and its storage representation
2. The representation and manipulation of strings
3. Linear data structures and their storage representation
4. Linear data structures and their linked storage representation
5. Nonlinear data structures
6. Sorting and searching
7. File structures
And so Chapter 5 probably has a 5–6.2 and 5–6.3 that cover such a memory allocation algorithm.
Edit: I found a weird plagiarized/condensed version of the book online, and section 5.6 is indeed called "Memory Allocation; Garbage Collection", so quite likely that the book by Tremblay and Sorenson is what is meant.
Well nothing so romantic: I didn't read it 20 years ago; more like some time in the last couple of years. And though I vaguely recall seeing this comment in the context of its code (on GitHub?), I may have well ended up there via a HN comment in a thread much like this, so that wouldn't be surprising. :-)
Great question! I vaguely remember reading it in a tan Knuth book, and the subject and algorithm feels very Knuthian to me, but I can't remember exactly. But this book has that title and looks like the book I remember having, and also looks like Knuth's books, so maybe I got confused and that's the book:
Here's some old email I wrote about it -- it turns out I did go on to write an interactive Forth window manager (for X10, with pie menus, and you could "fling" windows and it would start a Forth task to bounce them around on the screen -- see hacks.f), which foreshadowed my later work with NeWS (or its original name SunDew, as Mitch called it, which he ported to the Atari ST).
I made a diagnostic test which memory mapped the black and white framebuffer and ran memory allocator tests in video memory, so I could watch them. But I was using a shitty random number generator, and it looked suspicious.
Mitch sent me a better one based on the Unix random number generator, but it was pretty shitty too: The low bit alternates between 0 and one, so if you use "RND 1 AND" to flip a coin you get 0 1 0 1 0 ... So Mitch warned me that "Try dividing by two to get rid of the bogus lsb."
After I got it to work, I used it as a screen saver, so people would think my Sun 3/160 was broken and would leave it alone.
Memory allocators are easy. Random number are hard!
To: Mitch Bradley <wmb@sun.com>
From: Don Hopkins <don@brillig.umd.edu>
Date: Mon, Jul 28, 1986, 6:16 AM
Subject: Dynamic storage manager
Here's a dynamic storage manager I wrote. It runs under cforth and the
68000 forth.
I'm sending two files: "records.f", and "dbuf.f". The first contains
some words that are used to define records, like in pascal. The second
is my dynamic storage manager.
I wrote an earlier version of this for my Apple ProDOS Forth system,
as well as a set of string functions that used it. I'm going to port
this much revised (and more portable) version back to the Apple, and
update the string handling functions.
You may want to change the records.f file. I commented out some code
in dopasrec that optomized field accessing words with zero offset,
that was not completely portable.
I ran it through 100000 tests, and it worked fine. (I can't wait to
port it to the Apple, and run the tests on the hires screen. Not as
many, though. A Vax 8600 running cforth can do things a 1 MHZ 6502 is
not allowed to think about.) Bet it would look cool run in the Sun
screen memory.
Mike Gallaher and I will be arriving in Fornicalia around the evening
of the 9th. We should be getting a rental car. When are you usualy
around Sun and how do we find you? Mike's staying with Gosling.
I may need a place to stay near Sun for a few days.
I'll bring a tape of interesting things. I've been doing some work
with the X window system, enhancing the "uwm" window manager. Do you
ha...
FORTH is all fun and such (well, the stack counting gets old after a while), but I have difficulties seeing it in larger, multi-person projects (were there any?). A good idea who's time came and went.
people talking about how cool FORTH is. @cblum made his own sector forth. this is my tribe. i honestly thought there were no stack fans left in the world, thanks for proving me wrong.
Although the standard was withdrawn in 2000, it continued to be used by PowerPC Macs until Apple moved to x86 and EFI/UEFI.
Open Firmware is now actually open source as OpenBIOS (and OpenBoot is also available under a BSD license.) Apparently it can be used as a qemu boot rom for Linux, BSD, Solaris, and PowerPC versions of Mac OS 9 and OS X.[2]
There must be lots of ole-school fixed-width machines, which have stack machine built-in. Especially if you decide that top-of-stack means contents of the accumulator(s). To make it a "forth", you need separate string space, where machine words are linked to symbols. 1+ for example is just INC.
Many modern RISC architectures have pre-increment and post-decrement addressing modes for all their general-purpose registers, so it's very easy and convenient to maintain multiple stacks and implement "NEXT".
You start with a very tiny address or bytecode interpreter, much smaller than 512 bytes. Then you load several levels of bootstrap interpreters into it until you have a fairly featureful Forth. So that occupies ram but not program space on the target computer. You would load the non-initial stuff from a remote computer that didn't have tiny memory constraints.
62 comments
[ 3.6 ms ] story [ 139 ms ] threadWhy? I guess it depends on how you define "kernel." But to be able to do a batch process like compilation, you can get away with a little.
Can you clarify what batch process means in this case?
I /think/ the authors definition of a kernel is a program that can host other programs in some way.
A video game on a boot sector can't do that (even though it likely would have it's own kernel to function), but some kind of input loop to write memory could.
You don't need to host another program to compile something. All you need to do is to read data off disk, then write other data back.
The only way to avoid that is to hand-punch a tape or something like that (with lots of practice and patience, it may be possible to program a small PROM or write an early floppy by hand)
As opposed to the obvious doing an activity for fun.
type 1 is fun at the time
On early machines (large and small) with front panel hardware, you could use switches to manually enter the boot loader into memory and then start it.
A Turing machine is not stack-based, but tape-based. A pushdown automaton (PDA) is stack-based.
The linked post is really impressive. The author went way beyond what I did. I'm especially impressed by the I/O stuff.
I mean I know a lot of foundational code of yesteryear was hacked together in C, but C lacks a certain ineffable cachet in my view. A cachet that Forth definitely has.
In my experience, FORTH doesn't really scale to big projects, or things that need a lot of dynamic allocation. It's great at low-level stuff like hardware bringup (we used it on the Atari ST, back in the day, and even the hardware engineers were writing code to exercise their designs), but doing anything at scale is going to be tough. You probably don't want to write a modern web server platform in it, for instance. But it's probably great on an Arduino with a serial port.
There were a lot of games started at Atari in FORTH ("Hey, this is simple! Who needs to hire expensive assembly language programmers?") but the only project that shipped was the pinball machine "Four by Four". I saw a bunch of expensive disasters and mostly steered away from it.
These were written by third parties and published by Atari. Atari did not have any game programmers on the payroll at that point (all the software folks were working on the ST and related things). There might have been some contracting going on, but the days of an Atari employee coming up with a new game idea and shipping a new cartridge were gone.
https://www.forth.com/resources/space-applications/
http://forth.org/tutorials.html
There were a number of Shuttle experiments where the control software was written in Forth. It gives you a control interpreter out of the box and also bit level access to hardware so you can write custom drivers and then script the hardware control in the functions you wrote or compile them where speed is required, using an 8K..12K kernel.
The Cassini probe used Forth software running on a Forth 2-stack CPU.
I associate Fortran with nuclear reactor engineers. I was told they were some of the earliest users of it, maybe even before it was out of "beta", so to speak.
Quote from 1955:
"Considerable effort is now being made by various groups to develop automatic coding techniques which would make the use of a large machine feasible on this kind of problem. The system of greatest interest is Fortran, which is being set up by IBM for the 704; there is some chance that it will be available by the end of the year. To use it, the engineer who is setting up the problem must formulate it in a somewhat modified algebraic notation, which is then entered directly in the machine. As a result, the task of stating detailed machine orders and assigning addresses, which is largely a clerical task and constitutes most of the work of coding, is completely eliminated. Some scepticism has been expressed by experienced programmers, on the grounds that the resulting code would be far less efficient than one designed by hand. Even if this is the case, however, a system of this kind will still have a wide range of applicability in reactor analysis and should be kept in mind in considering future machine work."
Interesting how developers today impicitly assume the term "scale" mean "scale up".
It is not only in the Forth community that one hears disaster stories like: we did the software for client X in 3 weeks with a team of 4 programmers, but after a few decades they lost the know-how of our language so they decided to rewrite in a "modern" language that "can scale". They hired a team of 40 developers, it took 3 years, and the result is less reliable than the original. The only thing that scaled up were the development and maintenance costs and the only thing that was modernized is HR policy (i.e. let's hire disposable developers).
Consider control statements like conditionals or loops. They are implemented in Forth to express what is essential for imperative programming.
You can just as easily implement region handling much like what Cyclone [1] did. Invent region, dispose region, allocate within region, etc. You can augment semicolon word to not only check for control statements to be valid, but also check for region handling correctness.
[1] https://en.wikipedia.org/wiki/Cyclone_(programming_language)
Of course, you have to be either well educated or highly inventive to do that. ;)
And at the time of Atari most of programming projects were expensive disasters, not only games written in Forth.
I wrote malloc.fth for Mitch Bradley's ForthMacs, which ended up in OpenFirmware:
https://github.com/openbios/openfirmware/blob/master/ofw/cor...
Forth systems running on C libraries can also call back to the native malloc/free implementation, but it's nice to have a pure FORTH implementation for embedded applications.1. Information and its storage representation
2. The representation and manipulation of strings
3. Linear data structures and their storage representation
4. Linear data structures and their linked storage representation
5. Nonlinear data structures
6. Sorting and searching
7. File structures
And so Chapter 5 probably has a 5–6.2 and 5–6.3 that cover such a memory allocation algorithm.
Edit: I found a weird plagiarized/condensed version of the book online, and section 5.6 is indeed called "Memory Allocation; Garbage Collection", so quite likely that the book by Tremblay and Sorenson is what is meant.
"I read your Forth code from 20 years ago, please help me understand your comment string" - to the original author.
I am praying this gets resolved. This needs to be on the front page by itself.
https://www.amazon.com/introduction-structures-applications-...
Here's some old email I wrote about it -- it turns out I did go on to write an interactive Forth window manager (for X10, with pie menus, and you could "fling" windows and it would start a Forth task to bounce them around on the screen -- see hacks.f), which foreshadowed my later work with NeWS (or its original name SunDew, as Mitch called it, which he ported to the Atari ST).
https://donhopkins.com/home/archive/piemenu/uwm1/
https://donhopkins.com/home/archive/piemenu/uwm1/uwm.f
https://donhopkins.com/home/archive/piemenu/uwm1/fuwm-main.f
https://donhopkins.com/home/archive/piemenu/uwm1/hacks.f
I made a diagnostic test which memory mapped the black and white framebuffer and ran memory allocator tests in video memory, so I could watch them. But I was using a shitty random number generator, and it looked suspicious.
Mitch sent me a better one based on the Unix random number generator, but it was pretty shitty too: The low bit alternates between 0 and one, so if you use "RND 1 AND" to flip a coin you get 0 1 0 1 0 ... So Mitch warned me that "Try dividing by two to get rid of the bogus lsb."
After I got it to work, I used it as a screen saver, so people would think my Sun 3/160 was broken and would leave it alone.
Memory allocators are easy. Random number are hard!
To: Mitch Bradley <wmb@sun.com> From: Don Hopkins <don@brillig.umd.edu> Date: Mon, Jul 28, 1986, 6:16 AM Subject: Dynamic storage manager
Here's a dynamic storage manager I wrote. It runs under cforth and the 68000 forth.
I'm sending two files: "records.f", and "dbuf.f". The first contains some words that are used to define records, like in pascal. The second is my dynamic storage manager.
I wrote an earlier version of this for my Apple ProDOS Forth system, as well as a set of string functions that used it. I'm going to port this much revised (and more portable) version back to the Apple, and update the string handling functions.
You may want to change the records.f file. I commented out some code in dopasrec that optomized field accessing words with zero offset, that was not completely portable.
I ran it through 100000 tests, and it worked fine. (I can't wait to port it to the Apple, and run the tests on the hires screen. Not as many, though. A Vax 8600 running cforth can do things a 1 MHZ 6502 is not allowed to think about.) Bet it would look cool run in the Sun screen memory.
Mike Gallaher and I will be arriving in Fornicalia around the evening of the 9th. We should be getting a rental car. When are you usualy around Sun and how do we find you? Mike's staying with Gosling. I may need a place to stay near Sun for a few days.
I'll bring a tape of interesting things. I've been doing some work with the X window system, enhancing the "uwm" window manager. Do you ha...
(Thanks for that interesting email thread too.)
FORTH is all fun and such (well, the stack counting gets old after a while), but I have difficulties seeing it in larger, multi-person projects (were there any?). A good idea who's time came and went.
Although the standard was withdrawn in 2000, it continued to be used by PowerPC Macs until Apple moved to x86 and EFI/UEFI.
Open Firmware is now actually open source as OpenBIOS (and OpenBoot is also available under a BSD license.) Apparently it can be used as a qemu boot rom for Linux, BSD, Solaris, and PowerPC versions of Mac OS 9 and OS X.[2]
[1] https://en.wikipedia.org/wiki/Open_Firmware
[2] https://www.openfirmware.info/OpenBIOS
most dangerous bridge in the world https://www.interestingnews.club/2021/06/most-dangerous-brid...
Norwegian man dead hangs for 16 minutes to break world record https://www.interestingnews.club/2021/06/norwegian-man-dead-...
https://github.com/nineties/planckforth
You start with a very tiny address or bytecode interpreter, much smaller than 512 bytes. Then you load several levels of bootstrap interpreters into it until you have a fairly featureful Forth. So that occupies ram but not program space on the target computer. You would load the non-initial stuff from a remote computer that didn't have tiny memory constraints.