<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE book PUBLIC "-//OASIS//DTD DocBook XML V4.1.2//EN"
          "http://www.oasis-open.org/docbook/xml/4.1.2/docbookx.dtd">
<book>
<bookinfo>
  <title>The HYDROGEN Virtual Machine Specification</title>
  <author><firstname>Alaric</firstname><surname>Snell-Pym</surname></author>
  <copyright><year>2006</year><year>2007</year><year>2008</year><year>2009</year><holder>Warhead.org.uk Ltd</holder></copyright>
</bookinfo>
<preface><title>Foreword</title>

<para>TODO: Explain our goals.</para>

<para>Document-wide TODOs: Make sure stack effect syntax is consistent (one hyphen or two?), standardise all words to lower-case.</para>

<para>Write a HYDROGEN primer chapter (non-normative) that assumes access to an interactive console. Explain how words are executed in order, operating on the stack, and that some words do runtime things while some are 'immediate words' that control the compilation process.</para>

<para>Docbook usage: words are in <sgmltag>function</sgmltag> elements, registers etc. in <sgmltag>varname</sgmltag>, examples in <sgmltag>programlisting</sgmltag>. See document for standard wordlist table layout.</para>

<para>Add rationales for things in <sgmltag>note</sgmltag> elements</para>

</preface>

<chapter><title>The core</title>

	<sect1 id="registers"><title>CPUs, registers, stacks, and memory</title>
		<para>Any HYDROGEN system as a whole has some key properties relating to its internal architecture.</para>

		<table><title>Core implementation parameters</title>
		<tgroup cols='2'>
			<colspec colname='name' />
			<colspec colname='restrictions' />
			<colspec colname='description' />
			<thead>
				<row>
					<entry>Name</entry>
					<entry>Restrictions</entry>
					<entry>Description</entry>
				</row>
			</thead>
			
			<tbody>
				<row>
					<entry>Cell Size (bits)</entry>
					<entry>&gt;=16, must be a power of two, must be a multiple of sixteen, and must be at least as large as an address</entry>
					<entry>The native integer size of the machine.</entry>
				</row>
				<row>
					<entry>Allocation Unit size</entry>
					<entry>'byte' or 'cell'</entry>
					<entry>Whether an address refers to a cell-sized region of memory, or to a
						particular byte. Most modern architectures are byte-addressed. An
						allocation unit is the smallest unit of memory that can be allocated, and the smallest
						offset that can be added to a pointer. Allocation Unit is frequently abbreviated to AU.</entry>
				</row>
			</tbody>
			
		</tgroup>
		</table>

		<para>A HYDROGEN system contains one or more CPUs. Each CPU has a set
			of registers, and set of stacks. All the CPUs in the system share a single memory, and memory is considered uniform, in that there is no special affinity between individual CPUs and individual regions of memory; applications should choose regions of memory without any concern for which CPUs may perform operations on that region of memory.</para>
			
		<para>CPU registers are one cell wide.</para>
			
		<table><title>CPU registers</title>
		<tgroup cols='2'>
			<colspec colname='name' />
			<colspec colname='function' />
			<thead>
				<row>
					<entry>Name</entry>
					<entry>Function</entry>
				</row>
			</thead>
			<tbody>
				<row>
					<entry><varname>IP</varname></entry>
					<entry>Instruction Pointer; the address in memory of the next instruction to execute</entry>
				</row>
				<row>
					<entry><varname>A</varname> and <varname>B</varname></entry>
					<entry>Address holding registers, used by application code as a store for memory addresses</entry>
				</row>
				<!-- More may be added to support call frames etc, perhaps as part of an HLL support feature -->
				<row>
					<entry><varname>IPL</varname></entry>
					<entry>Interrupt priority level
						(see <xref linkend="interrupts" />)</entry>
				</row>
			</tbody>
		</tgroup>
		</table>

		<para>The implementation
		may or may not check for stack overflows and underflows; if it does, it should panic (see <xref linkend="panic" />) in response to such eventualities.
		If it does not, then the results of an overflow or underflow are undefined.</para>
		
		<table><title>CPU stacks</title>
		<tgroup cols='4'>
			<colspec colname='name' />
			<colspec colname='type' />
			<colspec colname='size' />
			<colspec colname='function' />
			<thead>
				<row>
					<entry>Name</entry>
					<entry>Element type</entry>
					<entry>Minimum capacity</entry>
					<entry>Function</entry>
				</row>
			</thead>
			<tbody>
				<row>
					<entry>D</entry>
					<entry>Cells</entry>
					<entry>64</entry> <!-- revise this based on experience -->
					<entry>The D, or Data stack, is used by application code as a working store for
						data, much as most CPU architectures use general-purpose registers.</entry>
				</row>
				<row>
					<entry>R</entry>
					<entry>Cells</entry>
					<entry>64</entry> <!-- revise this based on experience -->
					<entry>The R, or Return stack, is used to record return addresses when subroutines or
						interrupt handlers are executed. It may also be used by the runtime system and applications as a secondary
						working store; as such, there are more strict requirements concerning its use, in order to prevent clashes. Also, unlike the Data stack, the Return stack must be stored in memory; in other words, every cell on the stack must have an address.</entry>
				</row>
			</tbody>
		</tgroup>
		</table>
			
		<para>Each CPU executes a stream of instructions from the memory. The format of instructions is
			implementation-dependent, but the <varname>IP</varname> register of any CPU always points to the next instruction it
			will execute, apart from changes caused by interrupts or flow control instructions.</para>
	</sect1>
	
	<sect1 id="types"><title>Data Types</title>
		<para>As well as the Cell, which is the fundamental word size of the underlying implementation,
			various other data types are defined by HYDROGEN. All data types are given a short codename.</para>
			
			<table><title>Data Types</title>
			<tgroup cols='3'>
				<colspec colname='code' />
				<colspec colname='name' />
				<colspec colname='description' />
				<thead>
					<row>
						<entry>Code</entry>
						<entry>Name</entry>
						<entry>Description</entry>
					</row>
				</thead>
				<tbody>
					<row>
						<entry>c</entry>
						<entry>Cell</entry>
						<entry>A single cell. When referred to merely as a cell, no information about the
							intended interpretation of its contents is implied; it is simply a string of bits.</entry>
					</row>
					<row>
						<entry>s</entry>
						<entry>Signed Integer</entry>
						<entry>A single cell, interpreted as a two's complement signed binary integer.</entry>
					</row>
					<row>
						<entry>u</entry>
						<entry>Unsigned Integer</entry>
						<entry>A single cell, interpreted as an unsigned binary integer.</entry>
					</row>
					<row>
						<entry>ch</entry>
						<entry>Character</entry>
						<entry>A single cell, interpreted as a character. The mapping between characters and Character values is not defined by this specification; instead, we provide a set of words to perform operations on characters, to abstract out their representation.</entry>
					</row>
					<row>
						<entry>2c</entry>
						<entry>Two Cells</entry>
						<entry>Two adjacent cells, with no information about their interpretation as anything
							other than a string of bits implied. The first cell of the pair is the one at
							the lowest address when in memory, or the deepest when on the stack.</entry>
					</row>
					<row>
						<entry>p</entry>
						<entry>Pointer</entry>
						<entry>A single cell, containing a memory address. Pointers are unsigned cells, specifying an offset in allocation units relative to the start of addressible memory. Note that the size of an allocation unit (byte, cell, or something else) is unspecified.</entry>
					</row>
					<row>
						<entry>b</entry>
						<entry>Block</entry>
						<entry>Two adjacent cells; the first one being a pointer, the second being an unsigned
							integer specifying the number of AUs of memory, from that address onwards, are
							part of the block. 'b' can be considered shorthand for 'p u', with the added
							implication of the relationship between the two cells.</entry>
					</row>
					<row>
						<entry>bool</entry>
						<entry>Boolean</entry>
						<entry>A single cell. If the cell consists entirely of zero bits, then the boolean
							represents the False value. Otherwise, it represents True.</entry>
					</row>
					<row>
						<entry>h</entry>
						<entry>Handle</entry>
						<entry>A single cell containing a reference to an executable subroutine. The
							exact meaning of the bits that comprise the handle are implementation dependent;
							for example, it could be an index into a table, a pointer to the executable code in
							memory, or a pointer to a memory block containing various fields, one of which is
							a pointer to the actual code.</entry>
					</row>
					<row>
						<entry>h(a b c - d e f)</entry>
						<entry>Handle with declared interface</entry>
						<entry>This is a handle, with an added assertion
							about the stack effect of the subroutine when invoked. The example given above
							states that the subroutine expects a value of type 'c' to be at the top of the D
							stack upon entry, then a value of type 'b', then a value of type 'a', and that
							when it returns, a value of type 'f' will be at the top of the stack, then a value
							of type 'e', then a value of type 'd'.</entry>
					</row>
					<row>
						<entry>u8</entry>
						<entry>Eight bit unsigned integer</entry>
						<entry></entry>
					</row>
					<row>
						<entry>u16</entry>
						<entry>16 bit unsigned integer</entry>
						<entry></entry>
					</row>
					<row>
						<entry>u32</entry>
						<entry>32 bit unsigned integer</entry>
						<entry></entry>
					</row>
					<row>
						<entry>s8</entry>
						<entry>Eight bit two's complement signed integer</entry>
						<entry></entry>
					</row>
					<row>
						<entry>s16</entry>
						<entry>16 bit two's complement signed integer</entry>
						<entry></entry>
					</row>
					<row>
						<entry>s32</entry>
						<entry>32 bit two's complement signed integer</entry>
						<entry></entry>
					</row>
					<row>
						<entry>c8</entry>
						<entry>Eight bits. No interpretation of the meaning of those bits is implied.</entry>
						<entry></entry>
					</row>
					<row>
						<entry>c16</entry>
						<entry>16 bits. No interpretation of the meaning of those bits is implied.</entry>
						<entry></entry>
					</row>
					<row>
						<entry>c32</entry>
						<entry>32 bits. No interpretation of the meaning of those bits is implied.</entry>
						<entry></entry>
					</row>
					
				</tbody>
			</tgroup>
			</table>
			
			<sect2><title>Fixed-width integer types</title>
				<para>The types u8, u16, u32, s8, s16, and s32 are known as the fixed-width
					integer types.</para>
					
				<para>The number of cells taken up by each of these types is implementation-specific,
					except where specified otherwise.</para>
				
				<para>In particular, the results of arithmetic operations on them are not bounded to 
					remain within the range that might be expected. An implementation must provide
					at least the specified number of bits, but may provide more. Therefore, the result of
					performing u8 addition on the u8 values 128 and 128 may either be 256 or 0. Provisions
					are made (see <xref linkend="arithmetic-normalise" />) to normalise such values into the legal
					range of any fixed-width integer type.</para>
			</sect2>
		
	</sect1>
	
	<sect1><title>Arithmetic</title>
		<sect2 id="arithmetic-ops"><title>Operators</title>
		<para>A full range of arithmetic operations on integers is provided.</para>
		<para>Versions of each operation exist for each integer type: the fixed-width
			types, and upon cells interpreted as integers. Where the signedness of integers
			is irrelevant - operations such as addition, subtraction, and bitwise operations - we 
			use the prefix 'c'; where signedness is relevant, we use the prefixes 'u' or 's' as
			appropriate. The prefix is followed by a bit-width number for fixed-width operations,
			which is omitted for cell-width operations.</para>
		<para>Note that pointers are just cell-width unsigned integers, so the cell-width
			operations may be used to perform pointer arithmetic. However, note that pointers
			address memory in allocation units, and the size of an allocation unit may vary
			between implementations, so the effect of adding an integer constant to a
			pointer is not specified. See <xref linkend="memory-access" /> for words
			that return the sizes of various objects in allocation units for pointer
			arithmetic.</para>
		
		<para>In the following table of integer arithmetic words, only the cell-width variants
			are listed, for brevity. For every word listed, four variants actually exist:
			the cell-width variant, as listed, plus fixed-width variants for 8, 16, and 32 bits.
			Implementations supporting the LARGE-INT or FLOAT features will also provide other
			variants of some or all words, too.</para>
			
		<table><title>Integer Arithmetic Words</title>
			<tgroup cols='3'>
				<colspec colname='name' />
				<colspec colname='stack' />
				<colspec colname='description' />
				<thead>
					<row>
						<entry>Name</entry>
						<entry>Stack Effect</entry>
						<entry>Description</entry>
					</row>
				</thead>
				<tbody>
					
					<!-- signedness-indifferent -->
					
					<row>
						<entry><function>c+</function></entry>
						<entry>c.1 c.2 -- c.3</entry>
						<entry>c.3 = c.1 + c.2</entry>
					</row>
					<row>
						<entry><function>c-</function></entry>
						<entry>c.1 c.2 -- c.3</entry>
						<entry>c.3 = c.1 - c.2</entry>
					</row>
					<row>
						<entry><function>cneg</function></entry>
						<entry>c.1 -- c.2</entry>
						<entry>c.2 = -(c.1)</entry>
					</row>
					
					<!-- unsigned -->
					
					<row>
						<entry><function>u*</function></entry>
						<entry>u.1 u.2 -- u.3</entry>
						<entry>u.3 = u.1 * u.2</entry>
					</row>
					<row>
						<entry><function>u**</function></entry>
						<entry>uN.1 uN.2 -- u[2N].3</entry>
						<entry>u.3 = u.1 * u.2. This is defined ONLY for fixed-width types; the result is of double the bit width of the two inputs, so overflow cannot occur. Eg, <function>u8**</function> multiples two u8 numbers and produces a single u16.</entry>
					</row>
					<row>
						<entry><function>u/</function></entry>
						<entry>u.1 u.2 -- u.3</entry>
						<entry>u.3 = u.1 / u.2, rounding towards 0</entry>
					</row>
					<row>
						<entry><function>u*/</function></entry>
						<entry>u.1 u.2 u.3 -- u.4</entry>
						<entry>u.4 = u.1 * u.2 / u.3, rounding towards 0, and with a double-width intermediate product so that u.1 * u.2 does NOT overflow.</entry>
					</row>
					<row>
						<entry><function>umod</function></entry>
						<entry>u.1 u.2 -- u.3</entry>
						<entry>u.3 = u.1 % u.2</entry>
					</row>
					<row>
						<entry><function>u/mod</function></entry>
						<entry>u.1 u.2 -- u.3 u.4</entry>
						<entry>u.3 = u.1 % u.2, u.4 = u.1 / u.2, rounding towards 0.</entry>
					</row>

					<!-- signed -->

					<row>
						<entry><function>s*</function></entry>
						<entry>s.1 s.2 -- s.3</entry>
						<entry>s.3 = s.1 * s.2</entry>
					</row>
					<row>
						<entry><function>s**</function></entry>
						<entry>sN.1 sN.2 -- s[2N].3</entry>
						<entry>s.3 = s.1 * s.2. This is defined ONLY for fixed-width types; the result is of double the bit width of the two inputs, so overflow cannot occur. Eg, <function>s8**</function> multiples two s8 numbers and produces a single s16.</entry>
					</row>
					<row>
						<entry><function>s/</function></entry>
						<entry>s.1 s.2 -- s.3</entry>
						<entry>s.3 = s.1 / s.2, rounding towards 0</entry>
					</row>
					<row>
						<entry><function>s*/</function></entry>
						<entry>s.1 s.2 s.3 -- s.4</entry>
						<entry>s.4 = s.1 * s.2 / s.3, rounding towards 0, and with a double-width intermediate product so that s.1 * s.2 does NOT overflow.</entry>
					</row>
					<row>
						<entry><function>smod</function></entry>
						<entry>s.1 s.2 -- s.3</entry>
						<entry>s.3 = s.1 % s.2</entry>
					</row>
					<row>
						<entry><function>s/mod</function></entry>
						<entry>s.1 s.2 -- s.3 s.4</entry>
						<entry>s.3 = s.1 % s.2, s.4 = s.1 / s.2, rounding towards 0.</entry>
					</row>
					
					<!-- bitwise -->
					
					<row>
						<entry><function>cAND</function></entry>
						<entry>c.1 c.2 -- c.3</entry>
						<entry>c.3 = c.1 AND c.2</entry>
					</row>
					<row>
						<entry><function>cOR</function></entry>
						<entry>c.1 c.2 -- c.3</entry>
						<entry>c.3 = c.1 OR c.2</entry>
					</row>
					<row>
						<entry><function>cXOR</function></entry>
						<entry>c.1 c.2 -- c.3</entry>
						<entry>c.3 = c.1 XOR c.2</entry>
					</row>
					<row>
						<entry><function>cNOT</function></entry>
						<entry>c.1 -- c.2</entry>
						<entry>c.2 = NOT c.1</entry>
					</row>

					<row>
						<entry><function>c1ROL</function></entry>
						<entry>c.1 -- c.2</entry>
						<entry>c.2 = c.1 rotated left 1 bit</entry>
					</row>
					<row>
						<entry><function>c1ROR</function></entry>
						<entry>c.1 -- c.2</entry>
						<entry>c.2 = c.1 rotated right 1 bit</entry>
					</row>
					<row>
						<entry><function>c1SHL</function></entry>
						<entry>c.1 -- c.2</entry>
						<entry>c.2 = c.1 shifted left 1 bit, with a zero for the least significant bit</entry>
					</row>
					<row>
						<entry><function>u1SHR</function></entry>
						<entry>u.1 -- u.2</entry>
						<entry>u.2 = u.1 shifted right 1 bit, with a zero for the most signiciant bit</entry>
					</row>
					<row>
						<entry><function>s1SHR</function></entry>
						<entry>s.1 -- s.2</entry>
						<entry>s.2 = s.1 arithmetic-shifted right 1 bit, with the most significant bit preserved and duplicated right one place</entry>
					</row>
					
					<row>
						<entry><function>cROL</function></entry>
						<entry>c.1 u8 -- c.2</entry>
						<entry>c.2 = c.1 rotated left u8 bits</entry>
					</row>
					<row>
						<entry><function>cROR</function></entry>
						<entry>c.1 u8 -- c.2</entry>
						<entry>c.2 = c.1 rotated right u8 bits</entry>
					</row>
					<row>
						<entry><function>cSHL</function></entry>
						<entry>c.1 u8 -- c.2</entry>
						<entry>c.2 = c.1 shifted left u8 bits, with zeroes for the least significant bits</entry>
					</row>
					<row>
						<entry><function>uSHR</function></entry>
						<entry>u.1 u8 -- u.2</entry>
						<entry>u.2 = u.1 shifted right u8 bits, with zeroes for the most signiciant bits</entry>
					</row>
					<row>
						<entry><function>sSHR</function></entry>
						<entry>s.1 u8 -- s.2</entry>
						<entry>s.2 = s.1 arithmetic-shifted right u8 bits, with the most significant bit preserved and duplicated right.</entry>
					</row>
					<row>
						<entry><function>c-getbit</function></entry>
						<entry>c u8 -- bool</entry>
						<entry>Extracts bit u8 of c, and returns TRUE if the bit is set, FALSE otherwise.</entry>
					</row>
					<row>
						<entry><function>c-setbit</function></entry>
						<entry>c.1 u8 bool -- c.2</entry>
						<entry>If bool is true, c.2 = c.1 with bit u8 set, otherwise c.2 = c.1 with bit u8 cleared.</entry>
					</row>
					
					<!-- comparison -->
					
					<row>
						<entry><function>c=?</function></entry>
						<entry>c.1 c.2 -- bool</entry>
						<entry>Returns TRUE of c.1 and c.2 are identical</entry>
					</row>
					
					<row>
						<entry><function>c/=?</function></entry>
						<entry>c.1 c.2 -- bool</entry>
						<entry>Returns TRUE of c.1 and c.2 are not identical</entry>
					</row>
					
					<row>
						<entry><function>u&lt;?</function></entry>
						<entry>u.1 u.2 -- bool</entry>
						<entry>Returns TRUE of u.1 is less than u.2</entry>
					</row>
					<row>
						<entry><function>u&lt;=?</function></entry>
						<entry>u.1 u.2 -- bool</entry>
						<entry>Returns TRUE of u.1 is less than or equal to u.2</entry>
					</row>
					<row>
						<entry><function>u&gt;?</function></entry>
						<entry>u.1 u.2 -- bool</entry>
						<entry>Returns TRUE of u.1 is greater than u.2</entry>
					</row>
					<row>
						<entry><function>u&gt;=?</function></entry>
						<entry>u.1 u.2 -- bool</entry>
						<entry>Returns TRUE of u.1 is greater than or equal to u.2</entry>
					</row>
					<row>
						<entry><function>u&lt;?</function></entry>
						<entry>u.1 u.2 -- bool</entry>
						<entry>Returns TRUE of u.1 is less than u.2</entry>
					</row>
					<row>
						<entry><function>u&lt;=?</function></entry>
						<entry>u.1 u.2 -- bool</entry>
						<entry>Returns TRUE of u.1 is less than or equal to u.2</entry>
					</row>
					<row>
						<entry><function>u&gt;</function></entry>
						<entry>u.1 u.2 -- bool</entry>
						<entry>Returns TRUE of u.1 is greater than u.2</entry>
					</row>
					<row>
						<entry><function>u&gt;&lt;?</function></entry>
						<entry>u.1 u.2 u.3 -- bool</entry>
						<entry>Returns TRUE of u.1 is greater than or equal to u.2, and less than or equal to u.3 (eg, within the inclusive range u.2..u.3)</entry>
					</row>
					<row>
						<entry><function>u&lt;&gt;?</function></entry>
						<entry>u.1 u.2 u.3 -- bool</entry>
						<entry>Returns TRUE of u.1 is less then u.2, or greater than u.3 (eg, NOT within the inclusive range u.2..u.3)</entry>
					</row>
					

					<row>
						<entry><function>s&lt;?</function></entry>
						<entry>s.1 s.2 -- bool</entry>
						<entry>Returns TRUE of s.1 is less than s.2</entry>
					</row>
					<row>
						<entry><function>s&lt;=?</function></entry>
						<entry>s.1 s.2 -- bool</entry>
						<entry>Returns TRUE of s.1 is less than or equal to s.2</entry>
					</row>
					<row>
						<entry><function>s&gt;?</function></entry>
						<entry>s.1 s.2 -- bool</entry>
						<entry>Returns TRUE of s.1 is greater than s.2</entry>
					</row>
					<row>
						<entry><function>s&gt;=?</function></entry>
						<entry>s.1 s.2 -- bool</entry>
						<entry>Returns TRUE of s.1 is greater than or equal to s.2</entry>
					</row>
					<row>
						<entry><function>s&lt;?</function></entry>
						<entry>s.1 s.2 -- bool</entry>
						<entry>Returns TRUE of s.1 is less than s.2</entry>
					</row>
					<row>
						<entry><function>s&lt;=?</function></entry>
						<entry>s.1 s.2 -- bool</entry>
						<entry>Returns TRUE of s.1 is less than or equal to s.2</entry>
					</row>
					<row>
						<entry><function>s&gt;?</function></entry>
						<entry>s.1 s.2 -- bool</entry>
						<entry>Returns TRUE of s.1 is greater than s.2</entry>
					</row>
					<row>
						<entry><function>s&gt;&lt;?</function></entry>
						<entry>s.1 s.2 s.3 -- bool</entry>
						<entry>Returns TRUE of s.1 is greater than or equal to s.2, and less than or equal to s.3 (eg, within the inclusive range s.2..s.3)</entry>
					</row>
					<row>
						<entry><function>s&lt;&gt;?</function></entry>
						<entry>s.1 s.2 s.3 -- bool</entry>
						<entry>Returns TRUE of s.1 is less then s.2, or greater than s.3 (eg, NOT within the inclusive range s.2..s.3)</entry>
					</row>
				</tbody>
			</tgroup>
		</table>
		
		<para>Many of the variants of these operations will simply be aliases to each other.
			For example, since cells have a minimum width of 16 bits, <function>c+</function>, <function>c8+</function>, and <function>c16+</function> are quite likely to all refer to the same actual operation. If cells are 32 bits in size, then <function>c32+</function> may also be an alias. However, the implementation is free to implement these operations individually.</para>
		
		</sect2>
	
		<sect2 id="arithmetic-stack"><title>Stack Control</title>
		<para>The fixed-width integer system exists to permit software to be precise about the
			precision it requires for different quantities (within the limitations of the
			available granularity), while remaining independent of the underlying cell width,
			and permitting the trivial generation of efficient code.</para>
		<para>However, not knowing the size of different objects on the stack - or, even, if
			they are actually all on the same stack, or split into different stacks for
			different sizes or types of objects - would make stack rearrangement nonportable
			in an environment with the traditional FORTH stack manipulation words like DROP
			and OVER that operate on single cells.</para>
		<para>Therefore, we provide a single powerful portable stack rearrangement operation
			that, during code generation, may be analysed with implementation-specific
			knowledge about the implementation of the stack to generate appropriate and
			efficient code.</para>
		<para>The word is <function>shuffle[</function>, and it is a parsing immediate word:
			that is, rather than a call to the word being compiled, the word is executed
			immediately by the compiler, and proceeds to parse from the input stream itself
			and process what it finds. Namely, it parses the input stream for a variant on stack
			picture notation, until it encounters a closing <function>]</function> marker.
			The first part of the stack picture, up to the <function>--</function> marker,
			represents the original state of the stack. It consists of one or more space-
			delimited entries, each of which consists of a type code, followed by a period,
			then a unique whitespace-terminated name which serves as an identifier for this entry
			. After the <function>--</function> marker is found a list of zero
			or more space-separated entries, which specify the desired state of the
			stack after the shuffle. Each name references an input object previously specified;
			using a name not defined to the left of the marker is illegal. What's more, a name may be used zero or more times. Failing to use a name on the right hand side causes
			the corresponding entry on the left hand side to be discarded. Using a name
			more than once causes it to be duplicated as many times as required. Using the same name with a different type requests a type conversion.</para>
			
			<para>TODO: List legal type conversions. Talk about what happens when we go from <programlisting>c</programlisting> to <programlisting>u8</programlisting> and there's an overflow (answer: implementation defined! See normalisation words!)</para>
		
		<para>For example, <programlisting>shuffle[ u8.1 c.2 c.3 -- c.2 c.2 ]</programlisting> will expect the stack

			to have two cells on top, then an unsigned 8-bit integer. After the operation has
			executed, the stack will simply have two copies of the lower of the two cells, with
			the other cell and the 8-bit integer having been discarded.</para>
			
			<para>The other stack-noise-avoidance words is <function>begin[</function>, which again takes a stack input picture in the notation used by <function>shuffle[</function>, but without a <function>--</function> marker and output specification; instead, it has a  <function>]</function> marker to end the stack picture then arbitrary source code up to a <function>end</function> marker. The <function>begin[</function> ... <function>]</function> consumes the stack items depicted, taking them off of the stack and placing them in a "stack frame" elsewhere; from there up to the <function>end</function>, references to the names of stack items defined in the <function>begin[</function> ... <function>]</function> block cause a copy of that stack item to be pushed onto the data stack. After the <function>end</function> the names are out of syntactic scope, and space reserved for the "stack frame" is discarded.</para>
			
      <para>TODO: Refer to the Return stack memory allocation words below to explain where the stack frame is declared. Do we make the details entirely implementation-private, or export the presence of a stack frame pointer register in the CPU and provide lower-level words to mess with it? Or would it be better to just say that <function>begin[</function> merely might use the return stack, but could be allocating things to registers for speed?</para>
		
		</sect2>
	
		<sect2 id="arithmetic-normalise"><title>Normalisation</title>
		<para>Implementations are free to implement the fixed-width integer types with more
			bits than necessary, but fixed-width arithmetic operations are not required to force
			their results to be valid values of the fixed-width integer type in question. This allows
			words such as <function>u8+</function> to be implemented as aliases to <function>c+</function>.</para>
			
		<para>In situations where it is required that values be within the normal range of the type
			rather than the implementation-defined range (which may be larger), the following words are
			provided to restrict a value to within that range:</para>
			
			<table><title>Fixed-Width Integer Normalisation Words</title>
			<tgroup cols='3'>
				<colspec colname='name' />
				<colspec colname='stack' />
				<colspec colname='description' />
				<thead>
					<row>
						<entry>Name</entry>
						<entry>Stack Effect</entry>
						<entry>Description</entry>
					</row>
				</thead>
				<tbody>
					<row>
						<entry><function>u8normalise</function></entry>
						<entry>u8 - u8</entry>
						<entry>Discard all but the lower 8 bits of the top of the stack</entry>
					</row>
					<row>
						<entry><function>s8normalise</function></entry>
						<entry>s8 - s8</entry>
						<entry>Discard all but the lower 8 bits of the top of the stack</entry>
					</row>
					<row>
						<entry><function>u16normalise</function></entry>
						<entry>u16 - u16</entry>
						<entry>Discard all but the lower 16 bits of the top of the stack</entry>
					</row>
					<row>
						<entry><function>s16normalise</function></entry>
						<entry>s16 - s16</entry>
						<entry>Discard all but the lower 16 bits of the top of the stack</entry>
					</row>
					<row>
						<entry><function>u32normalise</function></entry>
						<entry>u32 - u32</entry>
						<entry>Discard all but the lower 32 bits of the top of the stack</entry>
					</row>
					<row>
						<entry><function>s32normalise</function></entry>
						<entry>s32 - s32</entry>
						<entry>Discard all but the lower 32 bits of the top of the stack</entry>
					</row>
				</tbody>
			</tgroup>
		</table>
		</sect2>
	</sect1>
	
	<sect1 id="memory-access"><title>Memory Access</title>
	  <sect2><title>Basic memory access</title>
	
		<para>All CPUs share a single random-access memory, consisting of a series of allocation units. Each allocation unit
			has a unique address, which is one of the legal values of the pointer type. Pointers are the same size as a cell.</para>
		
		<para>Not all pointer values are valid, however. For a start, the system is unlikely to have precisely enough memory to use the entire range of the pointer type; secondly, the available memory need not be in one contiguous block.</para>
		
		<para>The HYDROGEN runtime system is responsible for knowing which ranges of pointer values are valid, and then allocating contiguous ranges for different functions.</para>
		
		<para>Attempts to read, write, or execute code from an invalid pointer may result in an invalid access panic if the system provides such a facility, or may have undefined effects if not.</para>
		
		<para>The size of an allocation unit is not specified. In practice, many systems will have bytes as the units of allocation, meaning that a pointer is capable of identifying any byte in memory, and the individual bytes of a multi-byte quantity can be addressed. However, some systems may have cells or other multi-byte objects as the fundamental unit of allocation. In which case, arrays of smaller types may actually be stored with an entire cell used for each. Applications need not be aware of this distinction, as they can use the array-indexing operations such as <function>8[]</function> to calculate indices into arrays.</para>

		<para>The memory system does not care about the signedness of integers stored in it, or indeed anything about them beyond their size; as such, all of the memory operations defined in the base operate in terms of five fundamental types: c8, c16, c32, c, and ch. All other core types are defined as being the same size as at least one of the types in that list.</para>
		
		<para>If a pointer is valid for loading and storing one type, it may not necessarily be valid for loading and storing values of another type. For example, systems with small allocation units such as bytes may have alignment restrictions, where byte-sized quantities may be read from any location but 32-bit quantities may only be read from addresses divisible by four. In which case, a pointer may be valid for loading eight-bit quantities but not larger quantities. Attempts to read, write, or execute code from a pointer that is not valid for the operation being performed may result in an invalid alignment panic if the system provides such a facility, or may have undefined effects if not.</para>
		
		<para>A pointer may be valid for reading, but not for writing. For example, there may be read-only regions of memory. Attempts to write to pointers that are not valid for writing may result in a write protection panic if the system provides such a facility, or may have undefined effects if not.</para>
		
		<para>The CPU model provides two address registers, <varname>A</varname> and <varname>B</varname>, which store pointers. These are used as the addresses for memory loads and stores, rather than a pointer on the stack, as this facility tends to make operations on memory blocks clearer for humans to understand.</para>
		
		<para>Note that there are versions of the reading and writing words that advance <varname>A</varname> or <varname>B</varname> to the next quantity of the appropriate size in memory. These are intended for implementing loops that examine each element of an array in turn. The advancing versions of words simply add the size of the object in question to the register, with no knowledge of pointer validity restrictions; using such words to advance a pointer beyond the end of the region of memory allocated by the system for the array may result in a pointer that is invalid.</para>
		
		<para>Conventionally, the words specified in this chapter do not alter the contents of  <varname>A</varname> or <varname>B</varname> unless otherwise specified, but any other words are not expected to preserve <varname>A</varname> or <varname>B</varname>.</para>

		<para>Memory access words are defined in terms of a "selected address register", which may be <varname>A</varname> or <varname>B</varname>; the selection of an address register is not done at run time, but is a syntactic concept. Memory access words must be prefixed immediately with at least <function>A</function> or <function>B</function>, and optionally additional modifiers from the table. Using the prefixes on a word other than one of the memory access words defined in this chapter is illegal, as is using such a word without at least <function>A</function> or <function>B</function>.</para>
		
		<table><title>Address Mode Selection Words</title>
		<tgroup cols='3'>
			<colspec colname='name' />
			<colspec colname='stack' />
			<colspec colname='description' />
			<thead>
				<row>
					<entry>Name</entry>
					<entry>Stack Effect</entry>
					<entry>Description</entry>
				</row>
			</thead>
			<tbody>
				<row>
					<entry><function>A</function></entry>
					<entry>-</entry>
					<entry>An immediate word that selects <varname>A</varname> as the selected address register for the subsequently compiled memory access word to use, with no post- or pre- increment or decrement.</entry>
				</row>
				<row>
					<entry><function>B</function></entry>
					<entry>-</entry>
					<entry>An immediate word that selects <varname>B</varname> as the selected address register for the subsequently compiled memory access word to use, with no post- or pre- increment or decrement.</entry>
				</row>
				<row>
					<entry><function>|++</function></entry>
					<entry>-</entry>
					<entry>An immediate word that modifies the subsequently compiled memory access word to increment the selected address register by the size of the object accessed after the word has completed.</entry>
				</row>
				<row>
					<entry><function>|--</function></entry>
					<entry>-</entry>
					<entry>An immediate word that modifies the subsequently compiled memory access word to decrement the selected address register by the size of the object accessed after the word has completed.</entry>
				</row>
				<row>
					<entry><function>++|</function></entry>
					<entry>-</entry>
					<entry>An immediate word that modifies the subsequently compiled memory access word to increment the selected address register by the size of the object accessed before the word executes.</entry>
				</row>
				<row>
					<entry><function>--|</function></entry>
					<entry>-</entry>
					<entry>An immediate word that modifies the subsequently compiled memory access word to decrement the selected address register by the size of the object accessed before the word executes.</entry>
				</row>
				<row>
					<entry><function>bulk-memory-operation</function></entry>
					<entry>-</entry>
					<entry>An immediate word that gives the implementation a hint that the next memory access is likely to be a small part of a large series of memory accesses, and thus unlikely to exhibit high locality. The implementation may ignore this or, if the implementation supports it, it may modify the implementation of the subsequently compiled memory access word in a way that will be more efficient for large bulk operations on memory (for example, by bypassing data caches). Applications should prefix memory operations such as large array scans with this word.</entry>
				</row>
		  </tbody>
		</tgroup>
	  </table>
		
		<para>TODO: Write some examples of the above. Eg, <programlisting>A |++ 8! A |++ 8! A |++ 8!</programlisting> writes the top three bytes on the stack to the addresses at A, A+1, and A+2, in order.</para>
		
		<table><title>Memory Reading Words</title>
		<tgroup cols='3'>
			<colspec colname='name' />
			<colspec colname='stack' />
			<colspec colname='description' />
			<thead>
				<row>
					<entry>Name</entry>
					<entry>Stack Effect</entry>
					<entry>Description</entry>
				</row>
			</thead>
			<tbody>
				<row>
					<entry><function>8@</function></entry>
					<entry>- c8</entry>
					<entry>If the selected address register contains a valid pointer, returns the contents of the eight-bit quantity stored at that location in memory.</entry>
				</row>
				<row>
					<entry><function>16@</function></entry>
					<entry>- c16</entry>
					<entry>If the selected address register contains a valid pointer, returns the contents of the sixteen-bit quantity stored at that location in memory.</entry>
				</row>
				<row>
					<entry><function>32@</function></entry>
					<entry>- c32</entry>
					<entry>If the selected address register contains a valid pointer, returns the contents of the thirty-two-bit quantity stored at that location in memory.</entry>
				</row>
				<row>
					<entry><function>c@</function></entry>
					<entry>- c</entry>
					<entry>If the selected address register contains a valid pointer, returns the contents of the cell stored at that location in memory.</entry>
				</row>
				<row>
					<entry><function>ch@</function></entry>
					<entry>- ch</entry>
					<entry>If the selected address register contains a valid pointer, returns the contents of the character stored at that location in memory.</entry>
				</row>
			</tbody>
		</tgroup>
		</table>
		
		<table><title>Memory Writing Words</title>
		<tgroup cols='3'>
			<colspec colname='name' />
			<colspec colname='stack' />
			<colspec colname='description' />
			<thead>
				<row>
					<entry>Name</entry>
					<entry>Stack Effect</entry>
					<entry>Description</entry>
				</row>
			</thead>
			<tbody>
				<row>
					<entry><function>8!</function></entry>
					<entry>c8 -</entry>
					<entry>If the selected address register contains a valid pointer, writes the eight-bit quantity supplied to that location in memory.</entry>
				</row>
				<row>
					<entry><function>16!</function></entry>
					<entry>c16 -</entry>
					<entry>If the selected address register contains a valid pointer, writes the 16-bit quantity supplied to that location in memory.</entry>
				</row>
				<row>
					<entry><function>32!</function></entry>
					<entry>c32 -</entry>
					<entry>If the selected address register contains a valid pointer, writes the 32-bit quantity supplied to that location in memory.</entry>
				</row>
				<row>
					<entry><function>c!</function></entry>
					<entry>c -</entry>
					<entry>If the selected address register contains a valid pointer, writes the cell supplied to that location in memory.</entry>
				</row>
				<row>
					<entry><function>ch!</function></entry>
					<entry>ch -</entry>
					<entry>If the selected address register contains a valid pointer, writes the character supplied to that location in memory.</entry>
				</row>
			</tbody>
		</tgroup>
		</table>
		
		<para>Array indexing words use the currently selected address register, but ignore the pre/post increment/decrement settings.</para>
		
		<table><title>Array Indexing Words</title>
		<tgroup cols='3'>
			<colspec colname='name' />
			<colspec colname='stack' />
			<colspec colname='description' />
			<thead>
				<row>
					<entry>Name</entry>
					<entry>Stack Effect</entry>
					<entry>Description</entry>
				</row>
			</thead>
			<tbody>
				<row>
					<entry><function>8[]@</function></entry>
					<entry>u - c8</entry>
					<entry>Given a pointer to the start of an array of eight-bit quantities stored in the selected address register, and an index into that array, reads the value of the indexed element of the array onto the top of the stack.</entry>
				</row>
				<row>
					<entry><function>8[]!</function></entry>
					<entry>c8 u - </entry>
					<entry>Given a pointer to the start of an array of eight-bit quantities stored in the selected address register, and an index into that array and a value, writes the value into the indexed element of the array.</entry>
				</row>

				<row>
					<entry><function>16[]@</function></entry>
					<entry>u - c16</entry>
					<entry>Given a pointer to the start of an array of sixteen-bit quantities stored in the selected address register, and an index into that array, reads the value of the indexed element of the array onto the top of the stack.</entry>
				</row>
				<row>
					<entry><function>16[]!</function></entry>
					<entry>c16 u - </entry>
					<entry>Given a pointer to the start of an array of sixteen-bit quantities stored in the selected address register, and an index into that array and a value, writes the value into the indexed element of the array.</entry>
				</row>

				<row>
					<entry><function>32[]@</function></entry>
					<entry>u - c32</entry>
					<entry>Given a pointer to the start of an array of thirty-two-bit quantities stored in the selected address register, and an index into that array, reads the value of the indexed element of the array onto the top of the stack.</entry>
				</row>
				<row>
					<entry><function>32[]!</function></entry>
					<entry>c32 u - </entry>
					<entry>Given a pointer to the start of an array of thirty-two-bit quantities stored in the selected address register, and an index into that array and a value, writes the value into the indexed element of the array.</entry>
				</row>

				<row>
					<entry><function>c[]@</function></entry>
					<entry>u - c</entry>
					<entry>Given a pointer to the start of an array of cell-sized quantities stored in the selected address register, and an index into that array, reads the value of the indexed element of the array onto the top of the stack.</entry>
				</row>
				<row>
					<entry><function>c[]!</function></entry>
					<entry>c u - </entry>
					<entry>Given a pointer to the start of an array of cell-sized quantities stored in the selected address register, and an index into that array and a value, writes the value into the indexed element of the array.</entry>
				</row>

				<row>
					<entry><function>ch[]@</function></entry>
					<entry>u - ch</entry>
					<entry>Given a pointer to the start of an array of characters stored in the selected address register, and an index into that array, reads the value of the indexed element of the array onto the top of the stack.</entry>
				</row>
				<row>
					<entry><function>ch[]!</function></entry>
					<entry>ch u - </entry>
					<entry>Given a pointer to the start of an array of characters stored in the selected address register, and an index into that array and a value, writes the value into the indexed element of the array.</entry>
				</row>
			</tbody>
		</tgroup>
		</table>

		<table><title>Array Sizing Words</title>
		<tgroup cols='3'>
			<colspec colname='name' />
			<colspec colname='stack' />
			<colspec colname='description' />
			<thead>
				<row>
					<entry>Name</entry>
					<entry>Stack Effect</entry>
					<entry>Description</entry>
				</row>
			</thead>
			<tbody>
				<row>
					<entry><function>8s->aus</function></entry>
					<entry>u - u</entry>
					<entry>Given a number, return the number of allocation units required for an array of that many eight-bit quantities.</entry>
				</row>
				<row>
					<entry><function>16s->aus</function></entry>
					<entry>u - u</entry>
					<entry>Given a number, return the number of allocation units required for an array of that many sixteen-bit quantities.</entry>
				</row>
				<row>
					<entry><function>32s->aus</function></entry>
					<entry>u - u</entry>
					<entry>Given a number, return the number of allocation units required for an array of that many thirty-two-bit quantities.</entry>
				</row>
				<row>
					<entry><function>cs->aus</function></entry>
					<entry>u - u</entry>
					<entry>Given a number, return the number of allocation units required for an array of that many cells.</entry>
				</row>
				<row>
					<entry><function>chs->aus</function></entry>
					<entry>u - u</entry>
					<entry>Given a number, return the number of allocation units required for an array of that many characters.</entry>
				</row>
			</tbody>
		</tgroup>
		</table>

		<table><title>Miscellaneous Memory-Related Words</title>
		<tgroup cols='3'>
			<colspec colname='name' />
			<colspec colname='stack' />
			<colspec colname='description' />
			<thead>
				<row>
					<entry>Name</entry>
					<entry>Stack Effect</entry>
					<entry>Description</entry>
				</row>
			</thead>
			<tbody>
				<row>
					<entry><function>&gt;A</function></entry>
					<entry>p -</entry>
					<entry>Loads the <varname>A</varname> register with a pointer from the stack.</entry>
				</row>
				<row>
					<entry><function>&lt;A</function></entry>
					<entry>- p</entry>
					<entry>Stores the contents of the <varname>A</varname> register to the stack, without modifying <varname>A</varname>.</entry>
				</row>
				<row>
					<entry><function>&gt;B</function></entry>
					<entry>p -</entry>
					<entry>Loads the <varname>B</varname> register with a pointer from the stack.</entry>
				</row>
				<row>
					<entry><function>&lt;B</function></entry>
					<entry>- p</entry>
					<entry>Stores the contents of the <varname>B</varname> register to the stack, without modifying <varname>B</varname>.</entry>
				</row>
				<row>
					<entry><function>block-copy</function></entry>
					<entry>b p - (may corrupt <varname>A</varname> or <varname>B</varname>)</entry>
					<entry>Copies the identified block of memory to the identically-sized region of memory starting at the supplied pointer. If the blocks overlap, the contents of the destination block will end up being identical to the contents the source block had before the copy.</entry>
				</row>
				<row>
					<entry><function>block-copy!</function></entry>
					<entry>b p - (may corrupt <varname>A</varname> or <varname>B</varname>)</entry>
					<entry>Copies the identified block of memory to the identically-sized region of memory starting at the supplied pointer. If the blocks overlap, the final state of the target block is undefined.</entry>
				</row>
				<row>
					<entry><function>background-block-copy</function></entry>
					<entry>b p h(-) -  (may corrupt <varname>A</varname> or <varname>B</varname>)</entry>
					<entry>Starts copying the identified block of memory to the identically-sized region of memory starting at the supplied pointer. If the blocks overlap, the contents of the destination block will end up being identical to the contents the source block had before the copy. The word may return before the copy is complete if the system has the facility to perform background copies. When the copy is complete, the supplied argumentless sburoutine is invoked (but see <xref linkend="threads" /> for notes on how the THREADS feature may affect this). Between the execution of this word and the start of the handler being called, the state of every aligned cell in memory overlapping the target region is undefined. If the source region is written to before the copy is complete, then the final state of the target memory region is undefined.</entry>
				</row>
				<row>
					<entry><function>background-block-copy!</function></entry>
					<entry>b p h(-) -  (may corrupt <varname>A</varname> or <varname>B</varname>)</entry>
					<entry>Starts copying the identified block of memory to the identically-sized region of memory starting at the supplied pointer. If the blocks overlap, the final state of the target block is undefined. The word may return before the copy is complete if the system has the facility to perform background copies. When the copy is complete, the supplied argumentless subroutine is invoked(but see <xref linkend="threads" /> for notes on how the THREADS feature may affect this). Between the execution of this word and the start of the handler being called, the state of every aligned cell in memory overlapping the target region is undefined. If the source region is written to before the copy is complete, then the final state of the target memory region is undefined.</entry>
				</row>
			</tbody>
		</tgroup>
		</table>
	</sect2>
	<sect2><title>Multi-Accessor Memory Semantics</title>
	  <para>"Normal Semantics" refers to the idea that if one writes a value to a valid location in memory, subsequent reads of that location should return the new value, previous reads return the old value, and never is any other value ever read.</para>
	  
	  <para>However, providing such semantics in multiprocessor systems can be expensive, so the HYDROGEN virtual machine does not guarantee it will be so. Additionally, some implementations may have elements of the system that behave like additional CPUs, despite not being capable of executing code; this includes background memory operations such as <function>background-block-copy!</function>, and potentially implementation-dependent things such as memory-mapped hardware or direct access to system memory from peripherals (a form of <function>background-block-copy!</function>). In this section, we will consider system CPUs and any other implementation-dependent subsystems that might independently and asynchronously write to memory as "writers", and any CPU or other subsystem that might read memory as a "reader".</para>
	  
	  <para>It is guaranteed that if a writer writes to a region of memory the size of a cell or larger, then unless another writer modifies that memory region, then if the writer is also a reader, it will read back exactly the data that was written. In other words, normal semantics apply when the same CPU or subsystem is the only reader and writer using a cell-sized or larger region of memory.</para>
	  
	  <para>For regions smaller than a cell, this may not hold. If two different writers are modifying objects smaller than a cell that happen to be located within the same aligned cell-sized region of memory, then the result of subsequent reads of the entire cell by any reader are undefined. This is because implementations may implement writes smaller than a cell as a non-atomic read-modify-write, in which case, two of them overlapping may succeed in one of the writes appearing to succeed but being invisible undone; we hedge our bets by specifying that the entire cell is completely undefined in such a situation. However, the undefined status of that cell may be cleared by a normal write to it.</para>
	  
	  <para>Also, if a writer writes to any sized region of memory, the contents of that region of memory as seen by <emphasis>other</emphasis> readers is undefined until the writer "commits" the write. This is why the target region of <function>background-block-copy!</function> is undefined until the completion-notification handler is called; the background block copy might only commit the entire block write just before calling the handler.</para>
	  
	  <para>Note that background operations such as block copies may be implemented using special hardware, which may be its own reader in order to read the source block of memory; in such implementations, the words that initiate background operations will automatically commit any uncommitted writes from the CPU that initiates the operation. However, if any writes occur to that region while the copy is in progress, then the background copier may then encounter regions of memory with uncommitted writes to them, producing undefined results.</para>
	  
    <para>In practice, this means that regions of memory that are shared between multiple writers need to be handled carefully. Some means must be taken to ensure that no readers attempt to read from the memory region between writing and committing; either locking or atomic writes (which are discussed below) or some higher-level means of synchronisation (as with background block copies; the background copy is not initiated until the source block of memory is ready to be copied).</para>
  </sect2>
  
  <sect2><title>Locking</title>
  
  <para>One way of ensuring that two indepedent CPUs do not use some shared resource (such as a region of memory) at the same time is locking.</para>
  
  <para>The HYDROGEN virtual machine provides only spin locks; issues such as suspending a blocked thread and rescheduling it when it gains the lock are the scope of the application.</para>
  
  <para>TODO: Document a simple spin-lock system</para>
  
  </sect2>
  
  <sect2><title>Atomic Writes</title>
  
  <para>One way of ensuring that no readers read memory regions with uncommitted writes pending (resulting in undefined state) is to use atomic writes. There are operations that perform a write and commit it in one indivisible operation, such that no reads or other writes may occur between the write and the commit.</para>
  
  <para>TODO: Document atomic cell-sized writes, compare-and-swap, and a timestamped compare-and-swap that's ABA-proof.</para>
  
  </sect2>
  
  <sect2><title>Atomic Data Structures</title>
  
  <para>TODO: Some platforms have hardware support for aiding queues, stacks, and dictionaries. Provide atomic versions of same. Portable implementation can use the atomic write operations or spin locks. Make no claims about lock-freedom, but we hope they are.</para>
  
  </sect2>
  
  <sect2><title>The Return Stack</title>
  
  <para>TODO: As mentioned above in the discussion of the CPU stacks, the Return stack must live in memory, because it must be possible to use it to allocate memory for a dynamic scope. Provide some words to allocate and free memory this way.</para>
  
  </sect2>
  
	</sect1>
	
	<sect1 id="subroutines"><title>Subroutines</title>
	  <para>Subroutine handles represent executable code, stored somewhere, as a cell-sized value.</para>
	  
	  <para>A subroutine contains code, which is notionally a list of fundamental operations to be executed in order, but the exact representation of which is implementation-dependent.</para>
    
    <para>TODO: Words to call a subroutine given its handle (indirect call), to tail-call, etc.</para>
    
    <para>TODO: Flow control words to conditionally or repeatedly call a subroutine, etc.</para>

  	<sect2 id="compilation"><title>Compilation</title>
  	  <para>New subroutines may be generated by compilation of code, by feeding fundamental ops to a compiler context (which wraps a heap stream), then getting a handle out at the end.</para>
  	  
  	  <para>TODO: Fundamental ops are literal pushes, and literal subroutine calls. Jumps (aka tail calls), indirect calls, and so on are modelled as calls to special subroutines. Smart implementations will peephole-optimise calls to such special 'primitives'.</para>
    </sect2>
    
    <sect2 id="interpretation"><title>Interpretation</title>
    
      <para>TODO: Describe the interpreter mechanism, mainly revolving around dictionaries, parsing words, etc. See HYDROGEN code generation post on my blog. <function>(</function> word invokes the compiler up to a closing <function>)</function> to generate a subroutine and pushes its handle on the stack (or, in compile mode, compiles code to push it on the stack). Document that core HYDROGEN words defined in this document appear in the a dictionary which is bound to the name <function>core-dictionary</function> in itself.</para>
      
      <para>Interpreter context contains a list of dictionaries to look stuff up in (as a kind of namespace stack that may be modified during interpretation), and a dictionary to bind new definitions into by default, which is always implicitly on the top of the namespace stack.</para>
      
      <para>Decide if we want an implicit thread-global "current interpret context" register (with an interpreter context containing a saved copy of the old value, so they form a stack), to make it easier to nest meta-operations.</para>
    
    </sect2>

  </sect1>
  
	<sect1 id="heap"><title>The Heap</title>

  <para>HYDROGEN itself provides a very simple memory allocation model suitable for bootstrapping or using as the sole memory allocate in a simple system, but with hooks so that it can be extended to support more general heaps built on top.</para>
  
  <para>The heap is a region of memory subject to dynamic allocation; and memory can be allocated using two main interfaces. Block allocation is used when the size of memory region desired is known in advance; you request a certain number of AUs and receive either a pointer to a cell-aligned block of that size, or a null pointer to indicate an out-of-memory error. Stream allocation, on the other hand, involves creating a stream, writing data items to it, then 'sealing' the stream, whereupon the system gives you back a pointer to the start of the stream in contiguous memory. However a block is allocated, it may be returned to the heap by giving the start and length of the block.</para>
  
  <para>During stream allocation, the application may request the current offset into the stream, in AUs; after the stream is sealed, it may then refer back to those offsets by adding them to the initial pointer.</para>

  <para>TODO: Write up words to do all this.</para>

  <para>The bootstrap heap engine is very simple. It starts off with a list of free memory regions, provided by an implementation-dependent mechanism; it picks the largest free block to use for allocation, and constructs a free list from the others, by placing the length of the block in the first cell and a pointer to the next block (or null if this is the last in the chain) in the second cell (blocks of less than two cells in size are just discarded).</para>
  
  <para>It has three variables, which it makes available in the core dictionary as the words <varname>HEAP-POSITION</varname>, <varname>HEAP-LIMIT</varname> and <varname>HEAP-FREELIST</varname>. <varname>HEAP-POSITION</varname> is a pointer initialised to the start of the block used for allocation, and <varname>HEAP-LIMIT</varname> points to the last AU of the block. <varname>HEAP-FREELIST</varname> points to the head of the free list.</para>
  
  <para><function>ALLOC</function> then works by copying <varname>HEAP-POSITION</varname>, adding the requested number of AUs to it (rounded up to cell-align the result), then returning the original <varname>HEAP-POSITION</varname>; unless this would exceed <varname>HEAP-LIMIT</varname>. <function>FREE</function> takes the specified position and length of block, and adds them to the head of the freelist. Stream allocation works by using a single global stream allocation start pointer which is private to the implementation; supplied values are written to <varname>HEAP-POSITION</varname>, moving it along as they go, and calculating offsets by subtracting the start pointer from <varname>HEAP-POSITION</varname>; sealing the stream simply returns the saved start pointer and the final offset, then advances <varname>HEAP-POSITION</varname> to cell-align it.</para>
  
  <para>Clearly, only one heap stream may be written to at once, and block allocation may not occur during heap allocation. This must be enforced by the application, or it can replace the heap implementation; all the allocation words are actually indirect handles which can be modified to point to application-supplied allocation primitives. If a more advanced heap package is installed, it will find the free list ready for it to use in <varname>HEAP-FREELIST</varname>, plus the space between <varname>HEAP-POSITION</varname> and <varname>HEAP-LIMIT</varname>. If you want to switch back to the original heap package, you can convert whatever free space you have into a free list and call it <varname>HEAP-FREELIST</varname>, apart from the largest block, which you can call <varname>HEAP-POSITION</varname>...<varname>HEAP-LIMIT</varname>, and reinstate the heap words.</para>
  
  </sect1>

	<sect1 id="interrupts"><title>Interrupts</title>
	
		<para>
			Interrupts are asynchronous events that interrupt
			the normal flow of execution on a CPU. A number of
			events may trigger an interrupt, ranging from external
			hardware events (the completion of an output operation,
			the arrival of a new input, or any other event indicating
			that the hardware needs attention) to software events
			that cause the CPU to divert the normal flow of execution,
			such as a panic.
		</para>
		
		<para>
			For each interrupt source present in the system,
			there will be a word which registers a handler for
			that interrupt. The specification of the interrupt
			source will state what arguments are to be passed to the
			handler subroutine, and in some cases, the subroutine will be expected
			to return results.
		</para>
		
		<para>
			If no subroutine (or a null handle) is registered for an interrupt, then
			the interrupt should be ignored. The implementation
			may effect this by disabling the interrupt in hardware,
			or if this is not possible, providing a null handle
			that returns instantly with some sensible default
			result.
		</para>
		
		<para>If the THREADS feature is provided, then interrupt
			handlers may use the <function>INTERRUPT-TASK-SWITCH</function> word to alter the CPU
			state saved by the interrupt, thus effecting task
			switches.
		</para>
			
		<para>With the exception of panic interrupts, which are
			covered later, all interrupts have a priority which is
			assigned at the same time as the handler. At the same
			time, each CPU has a priority level as part of its
			state, stored in the <varname>IPL</varname> register. When an interrupt occurs, the system chooses
			a CPU with priority level lower than the priority level
			of the interrupt to handle it. The currently executing
			code on that CPU is suspended, the CPU's priority
			is set to the priority of the interrupt, and the
			interrupt handler executes. When execution completes,
			the saved CPU state (including the priority level)
			is restored.
		</para>
			
		<para>If no CPU is currently able to handle the interrupt,
			then it must be queued, and executed on the first CPU
			that is able to handle it.
		</para>
		
		<para>Some implementations do not have the facility to
			reprogram the priorities of their interrupt hardware;
			many have priorities assigned to their interrupts
			in hardware. And some systems may have no notion of
			interrupt priority. In these cases, the implementation
			must emulate interrupt priorities in the platform-
			dependent interrupt handler stubs, by use of a 
			CPU priority level stored in the thread state and a
			queue of pending interrupts. When the stub runs, it
			checks to see if the interrupt may be serviced on this
			CPU by comparing the current priority to the interrupt
			priority, and if not, queue the interrupt for later.
			Whenever the CPU's current priority is lowered
			(be it by a load of a saved CPU state or an explicit
			<function>set-ipl</function> or <function>exchange-ipl</function>), the queue of pending interrupts
			should be checked for interrupts that are now eligible
			to run, and their handlers invoked.
		</para>
			
		<para>Interrupt priorities are specified as unsigned cells,
			which almost certainly provides a much finer resolution
			of priority specification than any underlying hardware.
			The implementation must map from the priority
			specifications to priority levels supported by the
			hardware, maintaining the relative ordering of
			priorities. In which case, the cell-sized <varname>IPL</varname> register
			must still be maintained and contain the full cell-sized
			value specified by the application, but on every
			setting of <varname>IPL</varname>, the hardware IPL must be calculated
			and stored into the underlying "real" <varname>IPL</varname> register.
		</para>
		
		<table><title>Interrupt priority control words</title>
		<tgroup cols='3'>
			<colspec colname='name' />
			<colspec colname='stack' />
			<colspec colname='description' />
			<thead>
				<row>
					<entry>Name</entry>
					<entry>Stack Effect</entry>
					<entry>Description</entry>
				</row>
			</thead>
			<tbody>
				<row>
					<entry><function>exchange-ipl</function></entry>
					<entry>u - u</entry>
					<entry>Sets the <varname>IPL</varname> register to the chosen value,
						and returns the old value.
					</entry>
				</row>
				<row>
					<entry><function>set-ipl</function></entry>
					<entry>u -</entry>
					<entry>Sets the <varname>IPL</varname> register to the chosen value.
					</entry>
				</row>
				<row>
					<entry><function>get-ipl</function></entry>
					<entry>- u</entry>
					<entry>Returns the contents of the <varname>IPL</varname> register.
					</entry>
				</row>
			</tbody>
		</tgroup>
		</table>
		
		
		<sect2 id="panic"><title>Panics</title>
			<para>A panic is a particular type of interrupt
				raised by the system when an unresolvable situation
				occurs. When the panic interrupt handler is entered,
				a panic code is supplied as the single argument
				and the saved CPU state is subsequently invalid.
				Returning from the panic handler without having
				used the <function>BOOT-THREAD</function> or <function>INTERRUPT-TASK-SWITCH</function> words to switch
				to a valid state will cause another panic.
			</para>
			
			<para>TODO: Think about how to handle panics in minimal systems with no THREADS feature: Just REBOOT/TERMINATE/SHUTDOWN?</para>
			
			<para>The panic interrupt handler will always run on
				the CPU upon which the panic occurred, with the
				code that caused the panic being the saved CPU state
				in effect. Panic interrupt handlers are
				invoked immediately upon a panic-causing
				event, regardless of the current CPU priority.
			</para>
				
			<para>It is expected (but not required), therefore, that
				panic handlers will either suspend the panicing CPU
				with <function>HALT</function>, or terminate the
				thread that caused the panic and then pass
				control to the scheduler to switch to a new thread.
			</para>
			
			<para>If we defined a DEBUG feature, then as part of
				that we may define ways to 'repair' CPU states
				that have suffered a panic and continue execution.
			</para>
				
			<para>
				There is a single system-wide panic handler
				shared by all CPUs.
			</para>
			
			<table><title>Panic interrupt handler control words</title>
			<tgroup cols='3'>
				<colspec colname='name' />
				<colspec colname='stack' />
				<colspec colname='description' />
				<thead>
					<row>
						<entry>Name</entry>
						<entry>Stack Effect</entry>
						<entry>Description</entry>
					</row>
				</thead>
				<tbody>
					<row>
						<entry><function>set-panic-handler</function></entry>
						<entry>h(c - ) -</entry>
						<entry>Use the given handle as the panic
							interrupt handler on all CPUs from
							this point onwards.
						</entry>
					</row>
				</tbody>
			</tgroup>
			</table>
			
			<para>TODO: Find all mentions of panics in this document, and construct a table of panic codes here.</para>
		
		</sect2>
	</sect1>
	
	<sect1 id="lifecycle"><title>System Lifecycle</title>
	
	<para>Some external event initiates startup of the system. For
	bare-metal systems, power is supplied to the system,
	initiating the implementation-dependent boot process. For
	hosted systems, some software action initiates the HYDROGEN
	runtime system's startup.</para>
	
	<para>The nature of the boot process is platform and
	implementation dependent, but it will involve using some set
	of "boot files" from a mass storage device, to initialise the
	basic HYDROGEN system, then load the application.</para>
	
	<para>By "platform", we mean the underlying platform upon
	which the HYDROGEN implementation runs; this may be bare metal
	of a certain type, or a virtual machine, or a host operating
	system. The platform defines the initial steps of the boot
	process, the format the HYDROGEN kernel must be in to be
	executed, and the resources the HYDROGEN kernel has available
	to it.</para>
	
	<para>By "implementation", we mean the precise version of the
	HYDROGEN kernel that runs on top of the platform and provides
	the HYDROGEN virtual machine. Different implementations on the
	same platform may provide different interfaces for extensions
	and drivers, or have a different format of
	configuration.</para>
	
	<para>For a bare-metal system, the boot files may consist of a
	number of stages of boot loader; perhaps a small boot sector,
	a larger second-stage loader, then the HYDROGEN kernel and
	perhaps a configuration file describing details of available
	hardware that cannot be gleaned through autoconfiguration,
	perhaps a set of extension files containing additional
	drivers, then finally, the application.</para>
	
	<para>For an embedded system, there might be only one physical
	boot file, the contents of a FLASH memory; but it will still
	logically consist of HYDROGEN kernel and application, at
	least.</para>
	
	<para>For a hosted system, there might be a platform-specific
	HYDROGEN kernel executable, then a number of drivers, a
	configuration file, and the application.</para>
	
	<para>In most situations, the system has the ability to
	replace its own boot files. Bare-metal systems can rewrite the
	boot sector and install new boot loaders and kernels; embedded
	systems may be able to re-FLASH themselves (but may not); and
	hosted systems may (subject to administrative restrictions) be
	able to replace their own binaries and configuration.</para>
	
	<para>Either way, the HYDROGEN boot process is responsible for loading the implementation-dependent installation-independent HYDROGEN kernel, loading any implementation-dependent installation-dependent additional drivers or configuration files, then loading the implementation-independent installation-independent application and its implementation-independent installation-dependent configuration. The nature of the kernel, additional drivers, and kernel configuration files is implementation-dependent, but an abstract interface for replacing them may be made available by implementations via the BOOT-MEDIA feature describe in <xref linkend="boot-media" />, along with more concrete interfaces for replacing the application and its configuration.</para>
	
	<para>The application and its configuration must be provided
	as one or more blocks of characters, with an ordering. If the
	BOOT-MEDIA feature is provided, then the identification of
	these blocks and their order of loading is as defined by the
	feature; if not, then an implementation-dependent mechanism
	for providing this series of blocks of characters in the
	correct order must be provided.</para>
	
	<para>Once the kernel and its drivers and configuration have
	been loaded, providing a basic system in an initial state with
	all the words defined in this document loaded into an initial
	wordlist, one CPU is started while any others remain
	suspended; this CPU then proceeds to interpret the application
	in the environment containing the words specified in this
	document, which is bound
	to <function>CORE-DICTIONARY</function> within
	itself. <function>CORE-DICTIONARY</function> should not be
	modified; the application interpreter context binds new words
	into an initially empty dictionary referenced
	by <function>APPLICATION-DICTIONARY</function>. Once
	interpreting the application terminates, the system is ready
	to run. At this point, the implementation may store a snapshot
	of the state of the system that can be "cached" and restored
	in subsequent boots, as if none of the boot files are changed,
	then rebooting should consistently return to this
	state.</para>
	
	<para>It is recommended, but not required, that
	implementations provide some implementation-specific means of
	interrupting this process and dropping to an interactive
	prompt at the console for maintenance.</para>
	
	<para>At this point, if the DEVICE-TREE feature is present and
	the application has installed a device tree change interrupt
	handler, then the interrupt handler will now be invoked with
	the initial change from an empty device tree to the current
	state of the system; when that handler has completed, the
	word <function>START</function>, which the application should
	have defined in <function>APPLICATION-DICTIONARY</function>,
	is executed on one CPU; any other CPUs
	execute <function>IDLE</function>, which is described
	below. If the application expects to use multiple processor
	other than for interrupt handling, then it should use
	the <function>CPU:POKE</function> word or dynamic CPU device
	calls to send "software interrupt"s to the other CPUs in the
	system to get them working.</para>
	
	<para>If no <function>START</function> word has been defined
	by the application, the implementation will panic.</para>
	
	<para>We need a few utility words for large-scale system
	  management. More fine-grained control can be had via power
	  management devices, but these words provide a basic core
	  that is adequate for many purposes.</para>
	
  	<table><title>System Management Words</title>
  	<tgroup cols='3'>
  		<colspec colname='name' />
  		<colspec colname='stack' />
  		<colspec colname='description' />
  		<thead>
  			<row>
  				<entry>Name</entry>
  				<entry>Stack Effect</entry>
  				<entry>Description</entry>
  			</row>
  		</thead>
  		<tbody>
  			<row>
  				<entry><function>IDLE</function></entry>
  				<entry></entry>
  				<entry>Suspend execution on this CPU, ideally reducing CPU power usage, until an interrupt occurs; at which point the CPU is restarted to handle the interrupt, and suspends again when the interrupt terminates. The word executes this idle loop forever, unless an interrupt handler switches to another thread with <varname>INTERRUPT-TASK-SWITCH</varname>.
  				</entry>
  			</row>
  			<row>
  				<entry><function>HALT</function></entry>
  				<entry></entry>
  				<entry>Suspend execution on this CPU, ideally reducing CPU power usage, but unlike <function>IDLE</function>, does not attempt to handle interrupts.
  				</entry>
  			</row>
  			<row>
  				<entry><function>REBOOT</function></entry>
  				<entry></entry>
  				<entry><function>HALT</function>s all CPUs, terminates all asynchronous operations, resets hardware devices, and initiates the boot process from scratch.
  				</entry>
  			</row>
  			<row>
  				<entry><function>TERMINATE</function></entry>
  				<entry></entry>
  				<entry><function>HALT</function>s all CPUs. What happens then is implementation-specific, but it must not reboot without some administrative action telling it to do so.
  				</entry>
  			</row>
  			<row>
  				<entry><function>SHUTDOWN</function></entry>
  				<entry></entry>
  				<entry><function>HALT</function>s all CPUs, then powers down the entire system if possible.
  				</entry>
  			</row>
  			<row>
  				<entry><function>PLATFORM-IDENTIFIER</function></entry>
  				<entry> -- b</entry>
  				<entry>Pushes a block which contains a character string, identifying the specific platform upon which HYDROGEN is implemented.
  				</entry>
  			</row>
  			<row>
  				<entry><function>IMPLEMENTATION-IDENTIFIER</function></entry>
  				<entry> -- b</entry>
  				<entry>Pushes a block which contains a character string, identifying the specific HYDROGEN implementation.
  				</entry>
  			</row>
  			<row>
  				<entry><function>SYSTEM-IDENTIFIER</function></entry>
  				<entry> -- b</entry>
  				<entry>Pushes a block which contains a character string, identifying this specific system. Ideally it should be immutable, such as a serial number. If there is no identifying information available, then an empty string should be returned.
  				</entry>
  			</row>
  		</tbody>
  	</tgroup>
  	</table>
	</sect1>
	
	<sect1><title>Features</title>
	<note><title>TODO</title><para>
	The REQUIRE word declares that the application requires a named feature
	
	This may be implemented as a kind of include file system, or the words for all
	supported features might already be present, and REQUIRE then merely becomes
	'abort if the desired feature is not available'
	
	Features roughly split into two types: features that provide access to a certain type
	of hardware (eg, clocks) and features that may benefit from certain types of hardware
	(eg, DSP operations, virtual machines) but that can still be provided without them.
	
	The latter kind should have portable implementations provided in the specification, as
	reference implementations; most implementations can then provide these features by just
	including the portable implementation of each feature verbatim. However, where special
	hardware is available, the implementation can instead use that hardware.
	</para></note>
	<para>TODO</para>
	</sect1>

</chapter>

<chapter><title>Common Features</title>

	<sect1><title>FLOAT: Floating point arithmetic</title>
	<para>TODO. Provide IEEE 32- and 64-bit floats. And maybe a 'native float' with variable characteristics?</para>
	</sect1>

	<sect1><title>LARGE-INT: Large Integers</title>
	<note><title>TODO</title><para> Adds [us]{64..128}, [us]2 arithmetic </para></note>
	<para>TODO</para>
	</sect1>
	
	<sect1><title>DSP-ARITH-n: DSP Arithmetic tools</title>
		<note><title>TODO</title><para> n being the width of the DSP 'cells', eg 16 or 32. Implementations may
		provide more than one DSP-ARITH-n feature.</para></note>
		<note><title>TODO</title><para> Saturating arithmetic - DSPn+ etc </para></note>
		<note><title>TODO</title><para> Fixpoint arithmetic </para></note>
		<note><title>TODO</title><para> Multiply-Add </para></note>
		<note><title>TODO</title><para> cyclic buffers </para></note>
		<note><title>TODO</title><para> 1d FFT, FIR, etc as well - common high level
		algorithms can be hardcoded in assembly for speed </para></note>
      	<para>TODO</para>
	</sect1>
	
	<sect1 id="threads"><title>THREADS: Process state manipulation</title>
	
	<para>The state of computation is modelled as the stacks and processor registers defined in <xref linkend="registers" /> along with the state of any background asynchronous operations such as <function>background-block-copy</function>, but as this is a virtual machine, the actual representation of that state is implementation-dependent. Therefore, a set of words is provided to load and store the state in a portable manner in order to facilitate task switching.</para>
	
	<para>If this feature is present, then an additional <varname>T</varname> register added to the virtual CPU pointers to a region of memory set aside for thread state, known as a Thread Control Block (TCB), which consists of any memory required by the runtime system for storing CPU context information, space to store any state that normally resides in other locations (eg, physical CPU registers), and a region for applications to store thread-local state in.</para>
	
  <para>A TCB starts with the platform-dependent context area, and the user area follows after that. Upon boot, each processor starts with their <varname>T</varname> register pointing to a primordial TCB which has a zero-length user area and may not even be able to store a CPU state; the initial contents of the <varname>T</varname> register must either be left in-place and the THREADS feature words not used, or replaced with the <function>BOOT-THREAD</function> word.</para>
  
  <para>A TCB is considered active if the <varname>T</varname> register of a CPU currently points to it. An active TCB may not completely represent the state of the CPU, as parts of it may be cached in physical CPU registers, so many words that modify TCB contents are illegal on active TCBs. A TCB still counts as active even if an interrupt handler is executing on that CPU.</para>
  
  <para>The application may allocated TCBs as it sees fit; however, the start of a TCB must be cell-aligned.</para>
	
	<table><title>THREADS feature words</title>
		<tgroup cols='3'>
			<colspec colname='name' />
			<colspec colname='stack' />
			<colspec colname='description' />
			<thead>
				<row>
					<entry>Name</entry>
					<entry>Stack Effect</entry>
					<entry>Description</entry>
				</row>
			</thead>
			<tbody>
				<row>
					<entry><function>thread-context-size</function></entry>
					<entry>-- u</entry>
					<entry>Pushes the (constant) size of the implementation-dependent area of a TCB, in AUs, onto the stack. This can be used to compute the size of a TCB to allocate storage for it, by adding the amount of space required for the user area.</entry>
				</row>
				<row>
					<entry><function>thread-context-initialise</function></entry>
					<entry>p h --</entry>
					<entry>Given a pointer to a region of memory at least <function>thread-context-size</function> AUs long, initialises the first <function>thread-context-size</function> AUs to represent an initial CPU state with empty stacks, zero <varname>A</varname>, <varname>B</varname> and <varname>IPL</varname> registers, no background operations in progress, and <varname>IP</varname> such that execution will start at the start of the supplied subroutine (which must never return).</entry>
				</row>
				<row>
					<entry><function>thread-context-push</function></entry>
					<entry>p c --</entry>
					<entry>Given a pointer to an initialised inactive TCB, pushes the supplied cell onto the <varname>D</varname> stack of the stored CPU state. Intended for supplying parameters to the initial handler of a thread, but may be extended by a DEBUGGING feature into a suite of introspection tools to examine and modify all the contents of a TCB.</entry>
				</row>
				<row>
					<entry><function>thread-context-@</function></entry>
					<entry>p u -- c</entry>
					<entry>Given a pointer to an initialised TCB, active or inactive, fetches the cell at the specified index (in cells) into the user area. Might be implemented as <programlisting>cs->aus thread-context-size + + >A A C@</programlisting>.</entry>
				</row>
				<row>
					<entry><function>thread-context-!</function></entry>
					<entry>c p u --</entry>
					<entry>Given a pointer to an initialised TCB, active or inactive, stores the cell into the specified index (in cells) into the user area. Might be implemented as <programlisting>cs->aus thread-context-size + + >A A C!</programlisting>.</entry>
				</row>
				<row>
					<entry><function>T@</function></entry>
					<entry>u -- c</entry>
					<entry>Fetches the cell at the specified index (in cells) into the user area of the TCB pointed at by <varname>T</varname>.</entry>
				</row>
				<row>
					<entry><function>T!</function></entry>
					<entry>u c --</entry>
					<entry>Stores the supplied cell into the cell at the specified index (in cells) into the user area of the TCB pointed at by <varname>T</varname>.</entry>
				</row>
				<row>
					<entry><function>&lt;T</function></entry>
					<entry>-- p</entry>
					<entry>Pushes the current value of <varname>T</varname> onto the stack. The TCB remains active.</entry>
				</row>
				<row>
					<entry><function>boot-thread</function></entry>
					<entry>p -- (never returns)</entry>
					<entry>Discards the current CPU state, sets <varname>T</varname> to the supplied pointer (which must refer to an inactive TCB), and loads the CPU state therein, making the TCB active.</entry>
				</row>
				<row>
					<entry><function>interrupt-task-switch</function></entry>
					<entry>p -- (never directly returns)</entry>
					<entry>This word may only be called from within an interrupt handler. It saves the CPU state as captured on entry to the interrupt handler into the TCB pointed at by <varname>T</varname>, making that TCB inactive, loads <varname>T</varname> with the supplied pointer (which must point to an inactive TCB), and exits the interrupt handler, returning to the state stored in the new TCB (which becomes active).</entry>
				</row>
				<row>
					<entry><function>task-switch</function></entry>
					<entry>p --</entry>
					<entry>Saves the entirety of the current CPU state into the TCB pointed at by <varname>T</varname>, making that TCB inactive, loads <varname>T</varname> with the supplied pointer (which must point to an inactive TCB), and returns to the state stored in the new TCB (which becomes active).</entry>
				</row>
	    </tbody>
	  </tgroup>
    </table>
	</sect1>
	
	<sect1><title>CONTINUATIONS: Explicit continuations</title>
		<para>Closely related to the THREADS feature, the CONTINUATIONS feature provides explicit support for continuations. A continuation represents the future execution of code after the current word has returned. As such, it contains a subset of the state of the current thread. Also, a thread context represents a region of memory that is potentially continuously modified while a thread runs, since on most implementations it will contain the stacks (or at least the portions of them not cached in the CPU itself); while a continuation is a read-only object, permanently freezing a particular state of the system that can be "copied" into a thread context as many times as required in future.</para>
		
		<para>A continuation object is created by the <function>MAKE-CONTINUATION</function> word, which captures the current state of the stacks along with the contents of the <varname>IPL</varname> register. This is copied into a block of memory allocated from the heap, in an implementation-dependent format, and a pointer to same is returned. The heap space (and any other resources) consumed by a continuation object can be freed by passing the pointer to <function>DESTROY-CONTINUATION</function>.</para>
		
		<para>A continuation may be restored with the <function>RESTORE-CONTINUATION</function> word. This takes two arguments, the continuation pointer and a single cell. It saves the current return address from the R stack, then discards the current contents of the stacks and replaces them with those stored within the continuation, then pushes its single cell argument onto the data stack and returns to the saved return address. Note that this means that <function>RESTORE-CONTINUATION</function> returns to the word that called it, regardless of the contents of the R stack saved in the continuation. The calling word must then perform any stack operations it needs to do in the new continuation context before returning. The return from the calling word will then return to whatever code called the word that saved the continuation.</para>
		
		<para>This feature is intended to be used to support the implementation of higher-level languages that provide explicit continuations.</para>
		
		<note><title>TODO</title><para> TODO: Formal definitions of the words </para></note>
		
	</sect1>
	
	<sect1><title>TAGGED-DATA: Runtime tagged data</title>
	    <para>NOTE: This is really a library abstracted out of IRON, so that it can be used in other systems wanting tagged data.</para>
		<para>This is a higher level language support feature, mainly. Higher level languages like runtime dynamic types</para>
		<para>Supports the idea of a 2-bit tag field, 00=fixnum, 01=flonum, 10=character, 11=pointer.</para>
		<para>Provides a set of base arithmetic operations on tagged value cells, which for fixnum/flonum operations work directly but invoke event handlers on overflow so the arguments can be promoted to bignums if supported, and for pointers call to appropriate user type handlers (which, along with the overflow handlers, are specified as registers with their own load/store instructions)</para>
		<para>Also provides BOX and UNBOX operations for the basic types.</para>
		<para>For pointers, we provide relative-to-pointer indexing operations. Given an offset in AUs and a tagged pointer, calculate a native unboxed pointer.</para>
	</sect1>

</chapter>
<chapter><title>Hardware Access Features</title>


	<sect1><title>DEVICE-TREE: Dynamic device access</title>
		<note><title>TODO</title><para> Interrupts defined for the system to notify the application of the addition, removal
		or change of devices. See <xref linkend="lifecycle" /> for details on how the initial state of the device tree is notified to the application.
		
		Devices have one or more of the types listed below. They have attributes, and
		operations.

		Many hardware features will both provide direct access words and,
		if the device tree feature is present, a device tree entry. This is so that
		embedded systems without the overhead of a device tree can still use a standard
		interface to the hardware they depend on.
		
		If the device tree feature is not present, then the DEVICE-* features listed below
		may still be REQUIREd to use the device via direct access words.
		
		See notes.oo3
		
		Note that if the application does not REQUIRE the feature corresponding to a type of
		device, then that device should still appear in the tree for dynamic access, although
		the application cannot call the direct access words for that feature; the whole point
		of the dynamic nature of the device tree is that applications may not require, but can
		take advantage of, devices that appear in it.
		
		Include sample device trees from notes.oo3
		</para></note>
		
		<sect2><title>DEVICE-STORAGE: Persistent storage device</title>
		<note><title>TODO</title><para> Asynchronous I/O interface to a block storage device.
		
		Available as a device-tree node type with properties such as STORAGE:BLOCK-SIZE (bytes), and STORAGE:BLOCKS
		
		Also available via direct-access words if the feature is REQUIREd; access words take
		a device number parameter, and there is a word to return the number of devices. No support
		for dynamic device addition and removal; use the device tree if you want that.
		</para></note>
			<sect3><title>DEVICE-REMOVABLE: Removable storage drive</title>
			<note><title>TODO</title><para> REMOVABLE:INSERTED attribute and REMOVABLE:EJECT, REMOVABLE:LOCK, etc. commands </para></note>
			<note><title>TODO</title><para> When media is inserted, this device sprouts a child device of type STORAGE </para></note>
            	<para>TODO</para>
			</sect3>
		</sect2>
		
		<sect2><title>DEVICE-FILESYSTEM: High level filesystem storage</title>
		<note><title>TODO</title><para> Provided by POSIX systems, or by native systems finding disk partitions
		 	containing known filesystem types</para></note>
            	<para>TODO</para>
		</sect2>

	
		<sect2><title>DEVICE-REALTIME: Real time clock</title>
		<note><title>TODO</title><para> REALTIME:TICK-N / REALTIME:TICK-D - number of ticks per second as a fraction N/D </para></note>
		<note><title>TODO</title><para> REALTIME:IS-SETTABLE - settable clock or not </para></note>
		<note><title>TODO</title><para> REALTIME:SOURCE - if non-NULL, name of reference clock (GPS, etc); NULL for non-accurate clocks </para></note>
		<note><title>TODO</title><para> REALTIME:GET-TIME ( - u64 ) returns the number of  clock ticks since the UNIX epoch </para></note>
		<note><title>TODO</title><para> REALTIME:SET-TIME ( u64 - ) sets the number of  clock ticks since the UNIX epoch </para></note>
      	<para>TODO</para>
		</sect2>
		
		<sect2><title>DEVICE-ETHERNET: Ethernet interface</title>
			<note><title>TODO</title><para> Include support for common Ethernet accelerator features </para></note>
            	<para>TODO</para>
		</sect2>
		<sect2><title>DEVICE-WIFI: Wireless Ethernet interface</title>
		<para>TODO</para>
      	</sect2>
		<sect2><title>DEVICE-IP: High-level IP interface</title>
		<para>TODO</para>
      	</sect2>
		<sect2><title>DEVICE-GPIO: General purpose I/O lines</title>
		<para>TODO</para>
      	</sect2>
		<sect2><title>DEVICE-PORT: Byte I/O stream</title>
			<sect3><title>DEVICE-PORT-SERIAL: Serial port</title>
			<note><title>TODO</title><para> Control lines generally also exist as a DEVICE-GPIO </para></note>
            	<para>TODO</para>
			</sect3>
			<sect3><title>DEVICE-PORT-PARALLEL: Centronics parallel port</title>
			<note><title>TODO</title><para> Generally also exists as a DEVICE-GPIO </para></note>
            	<para>TODO</para>
			</sect3>
		</sect2>
		<sect2><title>DEVICE-MONITOR: Hardware monitoring</title>
			<note><title>TODO</title><para> Monitor device instances are linked to the device they monitor
				by MONITOR:DEVICE, and have a MONITOR:UNIT and MONITOR:SCALE-FACTOR,
				and a MONITOR:NOMINAL value,
				as well as MONITOR:OK-MIN and MONITOR:OK-MAX, then MONITOR:ALLOWABLE-MIN
				and MONITOR:ALLOWABLE-MAX as a range outside. </para></note>
                  	<para>TODO</para>
		</sect2>
		<sect2><title>DEVICE-SYSTEM: System root node</title>
			<note><title>TODO</title><para> Mainly a placeholder to be a root to the device tree </para></note>
            	<para>TODO</para>
		</sect2>
		<sect2><title>DEVICE-SUBSYSTEM: System subdivision</title>
			<note><title>TODO</title><para> An administrative subdivision of the device tree, perhaps to
				group a number of devices with a common temperature monitor or some such </para></note>
                  	<para>TODO</para>
		</sect2>
		<sect2><title>DEVICE-CPU: Central processing unit</title>
		
			<note><title>TODO</title><para> Direct-access words are available to find the number of CPUs. <function>cpu:poke</function> takes a CPU number, an IPL, and a handler, and interrupts the CPU at that IPL to run that handler, in order to make an idle CPU do something other than handle interrupts as they come.</para></note>
            	<para>TODO</para>
		</sect2>
	</sect1>

  <sect1 id="console"><title>CONSOLE: System console</title>
  <para>Many systems have an interactive console hardwired to them; those that do not can have a virtual console, accessible through an appropriate mechanism.</para>
  
  <para>Traditional system consoles have been very simple, defined by such standards as VT100 or ANSI, with only character-based input and output, and do not encourage bulk administration of large numbers of systems.</para>
  
  <para>Therefore, we define a high-level console that can be implemented on top of even basic teletypes, but can take advantage of advanced interface hardware; and, more importantly, is amenable to bulk administration of large numbers of systems.</para>
  
  <para>The architecture of the console abstraction is as follows:</para>
  
  <itemizedlist>
  
    <listitem><para>Asynchronous events may be logged by any component of the system, given a log level (ranging from debug messages up to fatal errors), a subsystem (allowing filtering of messages), and the message text.</para></listitem>
    <listitem><para>The user may be prompted with a prompt string and then allowed to enter a string, which is then returned to the application, or the user may cancel. The application may reject it with an error message, or accept it.</para></listitem>
    <listitem><para>A number of monitorable statistics may be registered by the application, and then updated by the application whenever new data are available. Each statistic has a name and either a quantity (as an integer number or 'unknown', a unit string, minimum and maximum ok values, minimum and maximum warning values) or a status string and a state (ok, warning, unknown, error). Quantised statistics have a state calculated; if the measured quantity is unknown then the state is 'unknown', if it is within the ok values then it's 'ok', if it's outside of that range but within the warning values then the state is 'warning', and otherwise it's 'error'. Statistic state changes need not be explicitly logged by the application, as the console system will log them automatically, with suitable hysterisis when statistics 'flap'.</para></listitem>
    <listitem><para>For identification of a system in a large room full of identical hardware, there's also a locator signal that can be turned on and off by the implementation. The exact effect is platform and implementation dependent, but audible sounds and flashing lights are recommended.</para></listitem>
    <listitem><para>All of the above may be reflected in a hardware console, or instead diverted to a software implementation, if the application provides callbacks, or to both (the default).</para></listitem>
  </itemizedlist>
  
  <para>How these are implemented depends on the implementation and the capabilities of the platform. However, an implementation on something like present-day server hardware might divide a text-mode screen into three regions; one showing all statistics in states other than 'ok', one showing log events, and the last one appearing on demand whenever the user is being prompted for a string. A general alarm level is maintained, ranging from 'ok' to 'error'; whenever a log event at that level or above appears from the application, the alarm level is raised to the log event's severity, and the system may optionally sound an alarm and illuminate any "error" LEDs available, which can both be silenced by pressing a button on the keyboard. Statistics going out of bounds will also trigger the alarm, but in this case, the alarm will silence automatically if the statistic returns within normal bounds. The locator signal can be implemented via beeping, plus the illumination of any suitable software-controlled LEDs that are available.</para>
  
  <para>TODO: Write up the words for all this.</para>
  
  </sect1>

  <sect1 id="boot-media"><title>BOOT-MEDIA: Access to boot media</title>
    <para>As discussed in <xref linkend="lifecycle" />, some systems may be able to modify their own bootstrapping media. If so, they should provide the BOOT-MEDIA feature to standardise this process, even though the details of some parts of the boot media will be platform-dependent or implementation-dependent.</para>
    
    <para>The boot media can be split into four sections, but may have finer structure within. The four sections are the HYDROGEN kernel (which is platform-specific, but will be shared by many systems), configuration and additional drivers for the kernel (which are also platform-specific, and implementation-specific, but is generally unique to one system), the application (which is platform- and implementation-independent and will generally be shared by many systems), and application configuration and extension (which are platform- and implementation-independent but specific to this system).</para>
    
    <para>In order to identify the implementation and the system itself so that the correct platform-specific, implementation-specific or system-specific media may be obtained, <function>platform-identifier</function>, <function>implementation-identifier</function> and <function>system-identifier</function> words are provided in <xref linkend="lifecycle" />.</para>
    
    <para>Having obtained suitable boot media from some repository, it may be installed via the BOOT-MEDIA words:</para>
    
    <table><title>Boot media access words</title>
		<tgroup cols='3'>
			<colspec colname='name' />
			<colspec colname='stack' />
			<colspec colname='description' />
			<thead>
				<row>
					<entry>Name</entry>
					<entry>Stack Effect</entry>
					<entry>Description</entry>
				</row>
			</thead>
			<tbody>
				<row>
					<entry><function>boot-media:install-kernel</function></entry>
					<entry>b u -</entry>
					<entry>Install the given sequence of AUs (in some platform-specific format) into the HYDROGEN kernel boot phase identified by the supplied number. The meanings of the phases is platform- and implementation-specific, so it is not possible to switch HYDROGEN implementations using this word. By convention they should start at 0 and work upwards in the order of use during the boot sequence; eg, 0 for a boot sector, 1 for a second-stage loader, 2 for the HYDROGEN kernel. It is an error to attempt to load a phase that is not supported by this implementation combination, which will cause a panic. Ideally there should be some measure of checksumming in the phases, so that invalid phases can be rejected.
					</entry>
				</row>
				<row>
					<entry><function>boot-media:install-kernel-configuration</function></entry>
					<entry>b u -</entry>
					<entry>Install the given sequence of AUs (in some implementation-dependent format, but starting with a zero-terminated sequence of characters) into the kernel configuration area, indexed by the supplied number. The sequence of characters at the start of the configuration item must be a human-readable label, but the format of the rest of configuration item is implementation-dependent; if at all possible, items are encouraged to be valid HYDROGEN source code to be interpreted in order, with any other types of object (eg, precompiled native code libraries, configuration files in special formats, etc) being wrapped in a HYDROGEN envelope, but this is not enforced. It is intended that extra driver modules, configuration files to specify details of hardware devices that cannot be obtained via introspection, etc. be provided here. Some index numbers may be "special" (eg, perhaps slot zero must be a configuration file), but outside the range of special indices, the application is permitted to use any valid unsigned integer, to allow an unbounded number of drivers etc. to be added to the core kernel. A configuration item may be removed by installing a zero-AU block over it.
					</entry>
				</row>
				<row>
					<entry><function>boot-media:install-application-component</function></entry>
					<entry>b u -</entry>
					<entry>Install the given sequence of AUs into the application area, indexed by the supplied number. The contents of the block must be valid HYDROGEN source code. Any unsigned integer may be used as an application component index, and during booting, they will be interpreted in numeric order. An application component may be removed by installing a zero-AU block over it.
					</entry>
				</row>
			</tbody>
		</tgroup>
		</table>
		
	</sect1>


  <sect1 id="key-storage"><title>KEY-STORAGE: Secure cryptographic key
      storage</title>
    
    <para>In principle, applications could store their cryptographic
    secrets in the boot media area, but some platforms offer better
    places to keep them, such as trusted platform modules. Even in the
    absence of such a device, it may be possible to offer storage on
    regular mass storage or NVRAM devices, alongside boot media
    storage, but using a different storage method that makes secure
    erasure easier. And in addition, devices may store keys encrypted
    and require a password to be manually entered on boot, thereby
    decreasing the benefits of stealing the device.</para>

    <para>The secure key store is a key->value mapping, where keys and
    values are arbitrary strings, but which particularly supports the
    secure erasure of keys.</para>

    <table><title>Secury key storage access words</title>
      <tgroup cols='3'>
	<colspec colname='name' />
	<colspec colname='stack' />
	<colspec colname='description' />
	<thead>
	  <row>
	    <entry>Name</entry>
	    <entry>Stack Effect</entry>
	    <entry>Description</entry>
	  </row>
	</thead>
	<tbody>
	  <row>
	    <entry><function>key-storage:get-key</function></entry>
	    <entry>b - b</entry>
	    <entry>Given a key name, return the value of that key. If
	      there is no key with that name, return a null
	      block.</entry>
	  </row>
	  <row>
	    <entry><function>key-storage:set-key</function></entry>
	    <entry>b b - u</entry>
	    <entry>Given a key name and a key value, store the key.
            If the key name does not already appear, then a new entry
            is created. If it does already appear, then the existing
            key value is overwritten. The operation is synchronous,
            and returns a success or failure code. Failure reasons
            might be a fundamental hardware fault, some kind of
            external write-protect switch, or a lack of sufficient
            space.</entry>
	  </row>
	  <row>
	    <entry><function>key-storage:erase-key</function></entry>
	    <entry>b -</entry>
	    <entry>Given a key name, securely remove that key entry
	      from the key store. If there is no key with that name,
	      do nothing.</entry>
	  </row>
	  <row>
	    <entry><function>key-storage:erase-all-keys</function></entry>
	    <entry>-</entry>
	    <entry>Securely remove all keys from the key
	    store.</entry>
	  </row>
	</tbody>
      </tgroup>
    </table>
  </sect1>
	
	<sect1><title>CACHE: Memory block cache</title>
		<note><title>TODO</title><para> Rationale: access to fast memory outside of address space - PAE, EMS, XMS </para></note>
		<note><title>TODO</title><para> API from Cache section of notes.oo3 </para></note>
      	<para>TODO</para>
	</sect1>
	
	<sect1><title>CLOCK-INTERRUPT: Clock interrupts</title>
	<note><title>TODO</title><para> CLOCK-TICK ( - u u ) - returns number of ticks per second as a rational fraction
		CLOCK-REGULAR ( u h - ) - sets up handler h to be called every u ticks. Call it with NULL h to disable.
		CLOCK-ALARM ( u h - ) - sets up handler h to be called in u ticks, then never again. Call it
			again to change the schedule; only one alarm is 'stored'
	</para></note>
	<para>TODO</para>
	</sect1>

	<sect1><title>CLOCK-RUNTIME: Profiling clock</title>
	<note><title>TODO</title><para> CLOCK-RUNTIME-TICK ( - u u ) - returns number of ticks per second as a rational fraction </para></note>
	<note><title>TODO</title><para> CLOCK-RUNTIME ( - u64 ) returns the number of clock ticks since system boot, for this CPU. In a virtualised environment, this
	may not tally with the change to CLOCK-REALTIME, as only
	ticks spent running this VM count for CLOCK-RUNTIME. Likewise, the runtime clock does not tick when a CPU is suspended in an IDLE instruction, or halted. </para></note>
	<para>TODO</para>
	</sect1>
</chapter>

<chapter><title>Platform features</title>
	<sect1><title>POSIX: POSIX base OS interface</title>
	<note><title>TODO</title><para> POSIX syscall API as a set of words,
	plus a special POSIX-SYSTEM device tree node (which forms the root of the tree)
	</para></note>
	<para>TODO</para>
	</sect1>
</chapter>

<chapter><title>Hardware Virtualisation Features</title>
	<sect1><title>VM: Generic VM operations</title>
		<note><title>TODO</title><para> VMs are identified by a single-cell value
		(probably a pointer to a data area)
		The VM feature provides words to pause, resume, and
		destroy VMs, access their CPU time counters, etc </para></note>
		
		<note><title>TODO</title><para> Creation and configuration of VMs is handled by
		each VM type's own words, but the general process is:
		1) Create VM
		2) Set up virtualised resources (I/O ranges which are
		handled by code outside of the VM, negotiate amount of memory to allocate (which may be hardcoded, eg when the VM system uses a physical slave CPU+RAM, so the negotiation may fail), etc
		3) Load code
		4) Run!
	</para></note>
	<para>TODO</para>
	</sect1>

	<sect1><title>VM-HYDROGEN: Virtual HYDROGEN machine</title>
		<note><title>TODO</title><para> Create a VM which gets the same feature set as the current VM, then provide it with a device tree and/or sets of words that are 'upcalls' into the parent VM, then load code and run, with the option to trigger interrupts in the VM. Operations to access contents of memory, stacks, and registers of paused VMs. Upcall words must use VM introspection words to access their parameters from the VM stacks, memory, etc.</para></note>
      	<para>TODO</para>
	</sect1>

	<sect1><title>VM-X86: Virtual X86 machine</title>
		<note><title>TODO</title><para> The V86 machine is a basic x86 CPU+RAM. The creator
		must provide I/O mappings and memory mappings, and the VM provides 256
		interrupts that trigger the x86 vectored ints. Plus operations to access the RAM and CPU state of paused VMs. It's
		up to the creator to provide things like PCI systems.
		
		Implementations on x86 hardware may use virtualisation
		or VMWare techniques to provide this in hardware; others
		must emulate the CPU.
		 </para></note>
       	<para>TODO</para>
	</sect1>

	<sect1><title>VM-X86-XEN: Virtual X86/XEN machine</title>
		<note><title>TODO</title><para> Provides a XEN domain, which can be efficiently
		implemented on x86 hardware without virtualisation or
		VMWare tricks. Creator must provide Xen
		high level disk/network/etc devices.
		
		Non x86 implementations providing this feature must
		do so via CPU emulation.</para></note>
      	<para>TODO</para>
	</sect1>

</chapter>
<appendix><title>Implementation notes: Portable C</title>
<note><title>TODO</title><para> A very basic portable C kernel </para></note>
<para>TODO</para>
</appendix>
<appendix><title>Implementation notes: POSIX</title>
<note><title>TODO</title><para> The portable C kernel, plus POSIX interfaces: mass storage devices as raw block devices
or as files, IP interfaces, etc: and the POSIX feature </para></note>
<para>TODO</para>
</appendix>
<appendix><title>Implementation notes: x86 assembly</title>
<para>TODO</para>
</appendix>
</book>
