Forth, stacks, and operating systems

[presidentbyamendment]

Some Ideas For Operating System Design

About a decade ago I wrote a 386 assembler in Bash, and a 3-stack TIL,
and I've had my 3-stacker
running as a Linux kernel thread. I still haven't re-written my 3-
stacker in assembly-in-Bash,
perhaps because I want to make the assembler portable first. I've
always been forming an operating
system design in my head, and it now seems to have taken a shape that
seems to include most of the
pieces that would allow it to be realized. For one thing, its rather
minimal. Since I've pulled off
some pretty crazy coding stunts in the past, I'll post this stuff as a
mere idea and the suggestion
that it looks doable, albeit to a guy who has a wide view of "doable".
The idea itself also leaves a
lot of ideas about users, processes, realtime issues, linking,
loading, and compiling, and other
heavyweight OS issues to experimentation. The minimal OS in mind
should ease such experimentation.

A machine monitor is a minimal operating system. A bootable Forth on a
register machine is a machine
monitor with some programming conveniences, such as a dictionary, a
stack machine model, flow
control abstractions, a blocks editor, and so on. I envision, and may
eventually write, something
that is half-way between e.g. SuperMON for the C64 and a Forth, but
I'd like to share my design
thoughts, since they seem to be achievable, but whether they are
achieveable by me alone is not so
clear. There's some interest arising in some other work of mine. Let's
call the design under
discussion OSTIL, One Stack (and later, Operating System) Threaded
Interpretive Language.

I have several design ideas in mind that look to me like they might
have a beneficial synergy.

Portable assembly, pa
Family picture frame procedures
one-stack TIL
blox storage management
TLB/MMU wirds
thrings data structures

Subsetting and macroing of machine languages of major commodity
register machines appears to give a
useable portable assembler, which can be written in the unix shell.
This gives a complete, portable,
small, extensible development environment, one-link, highly bitrot-
resistant toolchain. This is the
Forth philosophy applied to the tool to write the Forth. I am some
weeks away from having such a
critter. It is, in round figures, PISC, Portable Instruction Set
Computer, 386 registers with
load-store restrictions like a RISC. It also includes what may be
macros on a particular machine for
386 string loop instructions and ARM per-instruction conditionality.
The 386 back end is about 10k
of Bash. This subsetting is a performance hit, but how much of a
performance hit remains to be seen,
and should be close to, i.e. not many times worse than, compilers.

Family picture frame procedures are a calling convention for
subroutines with a standard frame size,
for which 16 ints/cells seems pretty good. Leaving aside the actual
return address, this gives 15
locals. You then have a family heirarchy of locals. The caller of
such a procedure is the parent,
the procedure with the PC is self, and procedures self calls are
children. The locals in self can
well be named a, b, c... o. Then there's no reason not to name the
parent's locals p_a, p_b, p_c...
or similar. The locals of a recently called child are similarly
available, particularly the locals
of "the baby". This gives a simple mechanism for something related to
what Martin Richards (BCPL)
might call dynamic free variables, which BCPL and C disallow. Frames
have near-zero performance cost
on 386 and probably anything else, as far as allocation. The cost on
386 is one literal byte, I
believe.

This is not quite as simple as Forth, but "familials" can stand in the
stead of the data stack in a
TIL interpreter to provide a post-fix syntax, by giving an implicit
action to a literal number;
"Numbers go in the next local in self." Interactively, that is
interpreter locals, i.e. INTERPRET's
locals. At define time, literals go in a, b, c... of the word being
defined. DOLIT has to keep track
of what locals have been assigned, i.e. a define-time frame pointer.
With a dictionary, where stacks
are dimensions, this is Forth In Flatland, or rather Forth on a line
segment, where Forth itself is
planar and my 3-stacker and Chuck's address register push Forth into 3-
space, and if we're on
one-stack or less hardware, it's a performance win over a non-
optimizing Forth. Doing the parameter
passing e.g. gcc does by hand may not be a lot of fun, but a
consistant set of names helps, and the
parameter passing is by hand, and copy-on-write, and so should be
maximally efficient. And there's
no stack-dancing, in the mind of the programmer, or in hardware. The
return stack on a commodity CPU
is not a pure stack, it is an addressable array in RAM, and hopefully
in the dcache. SO, we are
bending Forth to fit sub-Forth hardware. Forth comment stack diagrams
become frame diagrams, but
might usually look just about the same.

Writing such an interpreter is perhaps the highest hurdle between the
status quo and what I am
suggesting. However, given a dictionary and interpreter for a one-
stack TIL with frames, you want
the thing to be bootable. Boot code will include stuff that isn't
portable at all, but not much, and
there are plenty of examples, so that isn't as uncharted as a one-
stack Forth. But let's assume such
a thing arises, a bootable one-stack Forth, or a machine monitor with
a dictionary. Now what?

If you have a one-stack Forth with a 386-like register set, and a pa
assembler in OSTIL with a
backend for the host, ANS Forth e.g., variants thereof such as my 3-
stacker, Lisp, and a BCPL
interpreter or compiler become potential wordlists. There also appears
to be enough consistency in
caches and TLBs that there can be some portability to some primitives
for those. This gives a
greater degree of portability than C, which by the way, Linux is NOT
written in. I would try to
portableize MMUs, but I would not try to do so with FPUs, DSPs,
graphics coprocessors and so on.
Mercifully, those latter don't impinge on operating systems much.

There's much to experiment with, but I suggest a few simple standards
for bootable one-stack TILs.

Keep word headers to 8 ints, what I call a thring, and tend to use the
ints vaguely as follows...

<alignment padding>
<name string if namelen<>0 >

namelen
type tag
west ptr
east ptr
mask
index
ply
size

<non-meta data, i.e. CFA>

Metadata you don't use is very cheap these days. I'd use thrings for
any named text, for example,
and use the size field rather than a string terminator. That saves
namespace, at a memory
consumption cost. If you have thring handlers you don't need explicit
string handlers. Use east for
dictionary linking, I guess.

I'd suggest a critter I call blox for storage handling in memory and
beyond. A blox is a set of data
objects in levels, starting at 1k blox, with the same number of blox
in each level, say 16k blox of
1k, but where each blox in each succeeding level is 4x the size of the
blox in the prior level. blox
can accommodate terabytes in some dozens of levels, but a bitmap for
each level is of constant size.
The bitmap for a terabyte blox would be in the 32k range, depending on
level size. If your blox
develop filesystem features like directories and inodes, you'll
promote blox to the next level, and
physically move it, when your file consumes 4 blox at a particular
level, and maybe demote a blox
when it falls below half the blox size at a level. A blox header and
bitmap for physical RAM should
be in the OSTIL dictionary for memory allocation purposes.

Not everything needs to be a familial procedure. Primitives should be
inlineable. Interrupt handlers
should be in the dictionary as type "iret" perhaps. But a TIL
intepreter and colon-compiler need a
place to put literals.

Although Russell Fish called me on the phone to congratulate me on my
3-stacker, writing my
3-stacker, I found that my variable-size data stack items weren't
useful for writing the thing
itself. They also don't figure to be useful writing a bootable. They
may come back in applications,
and in conjunction with FPUs, DSPs, MMX gizmos and so on, but it seems
that for writing an OS on
one-stack hardware, less stacks even than Forth may be better than
more.

H3sm, Hohensee's 3-stack machine, had a couple ideas in it that I do
suggest for a de-minimus
one-stack TIL. H3sm doesn't have flow control abstractions like LOOP.
Its got five labels per
definition and conditional branches. That was adequate, and if
performance is paramount, it may also
help to preserve all 12 PISC/pa conditionals, which H3sm did not. You
also need a gizmo for
execution arrays. I also recommend H3sm's abbreviations mechanism.
H3sm's BYE is quit, and q. works,
regardless of what else you may define beginning with "q". I find that
very useful.

Best regards,

# Rick arrest Bush deport Obama Hohensee
rick_h...@email.com
# http://presidentbyamendment.com ftp.gwdg.de/pub/cLIeNUX/
interim
# presidentbyamendment on facebook and youtube
# shasm H3sm cLIeNUX libsys.a scale
LAAETTR :o)


echo "
some comps for a Forth blocks mutant of increasing block sizes and
blocks-in-use bitmaps.
"


Step=4 basic=1 K=1024 Pl=$((16*$K)) Rk=0
bx=0 rs=0 ts=0

echo "
Figuring blox in ranks of $Step, quantities in Kb, minblox of 1 (Kb),
$Pl blox per rank.

"

BpBM=$((Pl/8))
echo "
Rank KB/blox rank sz total size \
total bitmap size"

while test $Rk -lt 16 ; do
bx=$((4**Rk))
rs=$((bx*Pl/1024))
ts=$((ts+rs/1024))
echo "$Rk $bx $rs MB $ts GB \
$(( (Rk+1)*BpBM/1024))KB"
let Rk=$Rk+1



done