Kestrel-3

* Introduction

Part of me is inspired by the book, Project Oberon, to write up a kind
of report of what I'd like to see in one embodiment of the Kestrel-3
homebrew computer, pre-video-hardware of course.  I happen to have a
RISC-V software emulator, e2, which I believe can be used to emulate
to reasonable fidelity what the finished hardware will be like.

The hardware will consist of a single FPGA board, with the following

implementation methods.  In particular, I'd like to explore the use of
[[https://en.wikipedia.org/wiki/Top-down_and_bottom-up_design#Software_development][Stepwise Refinement]], a technique I haven't used in a long time.  In
particular, I'm interested in seeing how it can be applied both at the
systems level as well as individual procedure development.  Of course,
[[https://en.wikipedia.org/wiki/Test-driven_development][Test-Driven Development]] will continue to play a critical role as well.
It's a matter of knowing where one method works better than another,
and applying and switching amongst these tools accordingly.

A word on my stepwise refinement notation.  When I wish to express a
sequence of steps that need to be taken for some task, I will express
the pseudo-code like so:

#+BEGIN_SRC
  TO do something interesting DO
U   Perform some steps here.
R   Notify user of steps taken.
O   Continue with some more steps here.
  END
#+END_SRC

Along the left edge of the program listing is a line-by-line key
flagging the refinement status of that step.

| Flag | Meaning                                                                                                                                                          |
|------+------------------------------------------------------------------------------------------------------------------------------------------------------------------|
|      | This line either doesn't need any additional markup or it corresponds to an actual machine-executable instruction.                                               |
| O    | Obvious from context.  No further refinement is anticipated, but it will still need elaboration into machine-executable code.                                    |
| R    | Refined.  I define a finer-grained breakdown of steps to take elsewhere in this document.                                                                        |
| U    | Unrefined.  I don't (yet) know how to accomplish this step, but I have some idea of the pre- and post-conditions this step must accept and ensure, respectively. |

The goal of stepwise refinement, then, is to have as few lines of
pseudo-code marked with *U* as possible.  Note that steps marked *O*
or *R* are not immune from further elaboration; rather, it simply
means that a refinement exists.  The existence of a refinement is not
to be taken as a guarantee that it is the /correct/ refinement.

Sometimes, the ~TO~ line will be prefixed with *?*.  This simply
indicates that I've defined procedure or refinement which is not
referenced elsewhere.  It may be dead code.  Or, it might be useful
later, after further refinements have been made.  In either case, the
*?* signals to the reader that special attention should be paid to the
elaboration to make sure it still makes sense in the broader context
of the design.

* Goal for Kestrel-3 Pre-Media
The first release of the Kestrel-3 homebrew computer might seem
perhaps a bit schitzophrenic.  One of the core requirements for the
computer is that it remain useful to its owner even in the total
absence of secondary storage.  Insofar as it is possible, that means a
fully functional programming environment should be made available in

The user may re-enter the boot menu at any time by invoking the word
~BYE~, so as to exit from the Forth environment.

I anticipate that this is what the firmware should perform upon
cold-boot:

#+BEGIN_SRC
  TO cold-boot the Kestrel-3 DO
U   Relocate the ROM image into RAM for faster performance.
U   Initialize the Forth binary interface.
R   Cold-boot the Forth interpreter.
  END
#+END_SRC

Since the system's flash ROM is a serial device, the processor will
need to wait hundreds of clock cycles for each instruction it executes
out of ROM.  This is why we relocate the software image in ROM into
RAM before executing the rest of the bootstrap process.

Initializing the Forth binary interface involves determining
(statically or dynamically) where to place the data and return stacks,
any user and global variables, and of course the dictionary itself.

Once the VM has been established, we can then "cold boot" the Forth
environment.  It is here that the boot menu is built and presented to
the user.

#+BEGIN_SRC
  TO cold-boot the Forth interpreter DO
R   Direct console I/O to the operator's console.
R   Configure the Forth bootmenu items.
R   Show startup banner.
R   Discover available bootable volumes.
O   Start at first page of menu items.
    DO FOREVER
R     Present menu to the operator.
O     Wait for a key.
U     IF selection made identifies a boot option THEN
R       Attempt to boot from the selected source.
O       Notify the user of the failed boot attempt.
O     ELSIF operator wants to page the list down THEN
U       Advance to next page of items.
O     ELSIF operator wants to page the list up THEN
U       Retreat to previous page of items.
      ELSE
O       Notify the user of the erroneous selection.
      END
    END
  END
#+END_SRC

Device discovery necessarily implies device configuration as well.  In
the case of the operator's console, this should be configured
automatically when the computer comes out of reset.  (Still, when
media hardware is later contributed to the computer's configuration,
somehow choosing between the debug console and the VGA/keyboard
interface will need to happen.)

#+BEGIN_SRC
  TO Direct console I/O to the operator's console DO
O   Set default vectors for EMIT, EMIT?, KEY, KEY?, AT-XY, AT-XY?, CR, PAGE, and TYPE.
  END
#+END_SRC

Displaying the Forth logo on the screen happens before enumerating
storage devices, since the latter can potentially take a long time to
complete.  The banner at least lets the operator know that Forth is
running.

#+BEGIN_SRC
  TO show startup banner DO
O   Type the following message:

      Kestrel-3 ROM Forth System 2 Release 1
      Copyright (c) 2019 Samuel A. Falvo II
  END
#+END_SRC

See the secondary storage section in the Forth Interpreter chapter for
mass storage discovery information.

Boot menu items are described using a collection of menu item
descriptors.  Each descriptor binds a key that a user can press on the
keyboard to a particular boot action.  See the data structures chapter
for a complete description.

#+BEGIN_SRC
  TO Configure the Forth bootmenu items DO
U   Create a menu item descriptor that binds key 0 to boot into Forth environment w/out Auto-Load.
U   Create a menu item descriptor that binds key 1 to boot into Forth environment with Auto-Load.
  END
#+END_SRC

Assuming that the user's console is 80x25 characters in size, we can
reasonably display up to 16 items on a single screen.  If there are
more than 16 items to display, we'll need a mechanism for paging the
display.  Up to 36 items should be easily supported, being keyed to
'0'..'9', then 'A'..'Z'.

#+BEGIN_SRC
  TO Present menu to the operator DO
U   Clear the screen.
R   Show startup banner.
U   Skip to the item which is to appear first.
O   Start menu item counter at 0.
O   DO WHILE fewer than 16 items have been shown AND more items are left to print
O     Print the menu key and item description.
O     Count the menu item.
    END
O   Print page up/down menu items.
O   Prompt user for which action to take.
  END
#+END_SRC

When booting into the Forth environment, the following sequence of
code can be performed.  Note that the decision of whether or not to
auto-load was made when the user selected the appropriate menu
selection in the boot screen.

#+BEGIN_SRC
  TO boot into Forth environment DO
O   IF user wants to perform auto-boot sequence DO
U     Find valid Forth auto-start block.
O     IF found THEN
O       Load Forth auto-start block.
      ELSE
O        Report that no auto-start block was found.
      END
    ELSE
O     Report that auto-start was skipped on user request.
    END
O   Quit into Forth interpreter.
  END
#+END_SRC

We attempt to boot into a particular selection by invoking its custom
handler.  If the handler ever returns, then we can safely assume the
boot attempt failed.  It's expected that software which is
bootstrapped into will generally not return.

#+BEGIN_SRC
  TO attempt to boot from the selected source DO
O   Delegate control to handler specified by the selected menu item, passing the provided parameter as an argument.
  END
#+END_SRC

* Forth Interpreter
** Interpreter
I probably won't delve as deeply into the innards of the Forth
environment as I will other components of the firmware, if only
because of how fluid Forth's implementation details can be.  However,
I think it's useful to sketch something out if only to have a crude
idea of how I'd like the system software to be structured.

The interpreter is entered via the word called ~QUIT~.

#+BEGIN_SRC
  TO Quit into the Forth interpreter DO
O   Reset the return stack pointer.
R   Direct console I/O to the operator's console.
    DO FOREVER
U     Read one line of text.
U     Interpret the line of text received.
O     IF OK prompt is enabled THEN Print "OK" END
    END
  END
#+END_SRC

Note that this "outer interpreter" (as it's known formally in the
Forth community) resets the return stack pointer, but not the data
stack pointer.  When something produces an error, however, the data
stack does get reset.

#+BEGIN_SRC
  TO Handle uncaught exception DO
R   Direct console I/O to operator's console.
O   Print error code of current exception.
O   IF error code is a valid system exception code THEN
O     Print descriptive error message.
    END
O   Reset data stack.
R   Quit into the Forth interpreter.
  END
#+END_SRC

** Exception Handling
An uncaught exception happens when a program issues a ~THROW~ command
without a matching ~CATCH~ for it.  The simplest way to make this work
is to define ~THROW~ so that it just handles the "uncaught" exception
and immediately re-enters the Forth interpreter.  This results in the

behavior is with a dispatch vector for ~THROW~.  By default, before
any code is able to run ~CATCH~, it is configured to refer to the
unhandled exception handler above.  In this way, any
exception-throwing code will (in)directly find themselves invoking
~QUIT~, which is the intended behavior.

#+BEGIN_SRC
  TO Throw an exception DO
O   Delegate through the current throw handler vector.
  END
#+END_SRC

The ~CATCH~ word is responsible for /trying/ to execute a Forth word
that is capable of throwing an exception.  Since we desire strongly to
catch such exceptions, we need to establish some runtime attributes
that allow us to recover gracefully instead of just dropping into
~QUIT~.  Part of this is telling ~THROW~ not to just invoke the
unhandled exception handler directly.  Additionally, we need to know
where to restore the return stack pointer to when an exception does
occur.

This code should work for the happy path situation as well.  Assuming
the supervised word does /not/ raise an exception, we want to dispose
of the exception handling scaffolding seamlessly, and return a 0 to
the calling procedure, indicating that no exception happened.

#+BEGIN_SRC
? TO Try to run a Forth word capable of throwing an exception DO
U   Create an exception handling frame with the current return stack pointer and system variables.
O   Prepend the frame onto a list of exception handler frames.
O   Set the throw vector to catch an exception.
O   Execute the referenced colon definition.
O   Unlink the head of the exception handler list.
U   Restore system variables.
O   Restore the return stack pointer.
O   Return literal 0 indicating no exception.
  END
#+END_SRC

But, in the event of an exception, a third routine is necessary to
restore the environment.  At a minimum, this environment includes the
data stack and return stack pointers, the current throw vector, and
the current input source specification.  This is the routine that the
above code will need to vector invokations of ~THROW~

However, if the exception code is non-zero, we need to return that
code back to the caller of the corresponding ~CATCH~.  We do this by
restoring the environment from the exception handler frame (but
without disturbing the current data stack contents) and unlinking it,
just as we did in the happy path scenario.

#+BEGIN_SRC
  TO Catch an exception DO
O   IF exception code is 0 THEN Do nothing and just return. END
U   Save exception code in exception frame.
U   Unlink the head of the exception handler list.
U   Restore system variables.
O   Put exception code back onto the data stack.
O   Restore the return stack pointer.
  END
#+END_SRC

Thus, for the exception handling mechanism to work, we need two user
variables:

- Pointer to head of exception frame list.
- Vector to ~THROW~ implementation.

*** Discovering Available Bootable Volumes
When Forth starts up, it must find out what storage devices exist and
which ones can potentially be booted from.  Using this information, it
can populate the initial boot menu, which lets the operator select how
they want to use their computer from that moment forward.

#+BEGIN_SRC
X TO discover available bootable volumes DO
R   Discover attached devices and volumes.
O   FOR each mounted volume discovered DO
U     Check for a valid boot block.
    END
  END
#+END_SRC

One way to iterate through the list of detected volumes is to walk
throught a linked list of volume descriptors.  This implies that we
need a /mount list/, which maps mounted volumes and their allocated
spans of logical block numbers to physical devices somehow.

#+BEGIN_SRC
  TO discover available bootable volumes DO
R   Discover attached devices and volumes.
O   Start with first mount list record.
O   DO WHILE not nil
U     Read in first block of volume.
U     IF block has valid boot image match key THEN
U       Create boot menu item record from boot block contents.
      END
O     Step to the next volume in the mount list.
    END
  END
#+END_SRC

Mount list records have, at a minimum, the following fields:

| Field       | Purpose                                                                           |
|-------------+-----------------------------------------------------------------------------------|
| next        | Link to the next record                                                           |

In addition, each unit with a medium inserted can potentially have
more than one partition as well.  We know that partitions can come and
go at any time as well, as anyone who has used a partitioning tool
like ~fdisk~ can attest.

#+BEGIN_SRC
  TO Discover attached devices and volumes DO
U   Ask emulator for its complete unit list.
U   IF emulator responded THEN
O     DO WHILE not at end of unit list
U       Create a unit descriptor for the unit.
O       IF unit is mounted THEN
U         Create a mount-list descriptor.
        END
      END
U     Create device descriptor of type "Storage Emulator" as device 0.
    END
  END
#+END_SRC

Remark: I chose to build the unit list first, since that allows me to
create the device descriptor without having to go back and patch it up
later.  However, this might not be the best approach.

I'm of two minds when it comes to deciding whether or not to parse out

|-----------+----------------------------------------------------------------------------------------------------------|
| Match key | A known constant value intended to prevent random blocks from looking like valid boot information.       |
| Name      | A human-readable name for the bootable software.  This text would appear in the boot menu, for instance. |

* Unresolved Issues
These are design issues that either need resolution prior to further
refinement, or I know how to refine them but just haven't gotten
around to it yet.  These issues are /in addition/ to all steps which
need further refinement.










- Refine format of boot block format