Ch. 3. PDL, Part I (numbers, 'α', "ß", L, m, n, R, T, =, |, %, @σ)
Ch. 3. PDL, Part II (numbers, +, -, *, /, N, ~, ^, d, %, \, O, #, &)
Ch. 3. PDL, Part III (&, p, l, G, g, u, y, v, S, c, s, P, r, $, H, !, ?, h)
Ch. 3. PDL, Part IV (t, W, i, o)
:	Chapter 3.  The Pushdown List (Part I, Basic PDL operations)

The pushdown list (PDL) in REC is the principal medium for argument 
transmission among subroutines and operators.  Three pointers, called px, py 
and pz, are associated with it.  The value of px is always the starting 
address of the last argument to come onto the PDL,  py points to the next 
free location in the PDL (and thus py-px is the length of the top argument) 
and pz points to the current end of the PDL (since both ends of the PDL may 
be used to store arguments, pz is thus the stack pointer for the upper stack 
or PDL complement).  In addition, there are markers on both ends to prevent 
the excess removal of operands on either end.  Since the PDL accepts 
arguments of varying lengths, as soon as a new operand is to be pushed onto 
the list either a pointer or a length (depending on the specific 
implementation) is stored with the previous top argument so that it can be 
recovered once the new argument has been disposed of.

	This figure shows schematically the PDL when empty. 

   ┌─┬────────────────────────────────────────────────────────────┬─┐
   │░│								  │▒│
   └─┴────────────────────────────────────────────────────────────┴─┘
      └ px, py						        pz ┘

This figure shows the PDL after a few arguments have been stored at both ends.

    α ┐ ┌ ß	  ┌ δ					    ├─ l ─┤  
   ┌─┬─┬───────┬─┬───┬─┬────────┬─────────────────────────┬─┬─────┬─┐
   │░│α│       │ß│   │δ│	│			  │l│	  │▒│
   └─┴─┴───────┴─┴───┴─┴────────┴─────────────────────────┴─┴─────┴─┘
		     px	┘	 └ py			pz ┘


	The greek letters in the figure denote addresses; the letter l 
denotes a length; these occupy two bytes.  (In the MC68000 version of REC, 
lengths, rather than addresses, are used.)  The top argument is delimited by 
px and py; initially these pointers delimit a null string.  The shaded cells 
at either end denote markers preventing excessive erasures from the PDL.  In 
figure 1(b), there are three arguments (starting at addresses ß, δ and px) on 
the lower (or normal) end of the PDL; there is one argument (of length l) 
stored at the upper (or complementary) end of the PDL.

	The first REC operators we will need are those that load a constant 
from the program onto the PDL, delete an argument, and move it from one end 
of the PDL to the other.


Operator/Predicate		Function performed

      number	Operator, enters the number in its binary form into the PDL. 
		For the time being, we will consider "number" to be a string 
		of ASCII decimal digits not starting with 0 (except for an 
		isolated 0) or a minus sign followed by a nonzero digit, 
		followed by zero or more digits.  With these restrictions, 
		the number loaded will be the two-byte binary representation 
		of the corresponding decimal constant (modulo 2^16=65536); 
		negative numbers are entered in two's complement form.  We 
		will generalize the acceptable number forms in the next 
		section.  The order in which the least and most significant 
		bytes are placed on the PDL depends on the processor; on the 
		Intel processors the least significant byte is stored at the 
		lowest address (px), while on the Motorola MC68000 the 
		reverse applies.

  'α' or "α"	Operator, places the string α of ASCII characters on the PDL. 
		α may contain nests of quoted strings such that the 
		delimiting quotes alternate between " and '. The null 
		string may be entered into the PDL with '' or "".  
		Other examples follow:

  'α' or "α" (cont.)		"quoted string"
				'another quoted string'
				'nested "quoted 'string'"'
				"another 'nested "quoted" string'"

		The nesting feature prevents the characters ' and " to be 
		quoted singly; a single instance of them may be placed on the 
		pushdown list by "''"% and '""'%, respectively.
		Control characters such as carriage returns and line feeds 
		are included in quoted strings if the opening quote appears 
		on one line and the closing quote on another, but this 
		depends on how files are structured in a particular operating 
		system; for instance, Unix uses a single line feed to denote 
		the end of a line, whereas both CR and LF are stored in CP/M 
		and MS-DOS text files.  Control characters are best 
		introduced by stating their numeric value and restricting to 
		one byte if necessary.  For example, 26% is a two-operator 
		sequence leaving a single control-Z character on the PDL; 
		2573 leaves a two-character string consisting of the control 
		characters for carriage return and line feed.



	L	Operator, removes the last entry from the PDL. If it is	
		already empty, the error is noted and execution continues.
		
	m	Operator, moves the argument at the top of the PDL to the 
		complementary PDL and writes the size (in bytes) of the 
		argument moved in the two bytes just below its new location; 
		pz is updated to reflect the new high limit of available PDL 
		space.  The error flag is set and a null string is moved if 
		the normal end of the PDL is empty.

	n	Operator, retrieves the last argument moved to the 
		complementary PDL, making it the new top argument on the low 
		or normal end of the PDL.  An error is indicated in the 
		error flag if the complementary PDL is empty, but a null 
		string is nevertheless placed on top of the normal PDL.

	The following sequence of figures shows the successive states of the 
PDL as each of the operators in the REC program 

			('abc' 2573 'def' m L n;) 

is executed, starting with an empty PDL.  

	In these figures, the tick marks represent byte boundaries, which are 
omitted for the pointer and length cells.

   ┌─┬────────────────────────────────────────────────────────────┬─┐
   │░│								  │▒│
   └─┴────────────────────────────────────────────────────────────┴─┘
      └ px, py						        pz ┘
    α ┐
   ┌─┬─┬─┬─┬─┬────────────────────────────────────────────────────┬─┐
   │░│α│a b c│ 							  │▒│
   └─┴─┴─┴─┴─┴────────────────────────────────────────────────────┴─┘
     px	┘     └ py						pz ┘
    α ┐ ┌ ß
   ┌─┬─┬─┬─┬─┬─┬──┬──┬────────────────────────────────────────────┬─┐
   │░│α│a b c│ß│CR LF│						  │▒│
   └─┴─┴─┴─┴─┴─┴──┴──┴────────────────────────────────────────────┴─┘
	     px	┘     └ py					pz ┘
    α ┐ ┌ ß	┌ δ
   ┌─┬─┬─┬─┬─┬─┬──┬──┬─┬─┬─┬─┬────────────────────────────────────┬─┐
   │░│α│a b c│ß│CR LF│δ│d e f│					  │▒│
   └─┴─┴─┴─┴─┴─┴──┴──┴─┴─┴─┴─┴────────────────────────────────────┴─┘
		     px ┘     └ py				pz ┘

    α ┐ ┌ ß
   ┌─┬─┬─┬─┬─┬─┬──┬──┬────────────────────────────────────┬─┬─┬─┬─┬─┐
   │░│α│a b c│ß│CR LF│					  │3│d e f│▒│
   └─┴─┴─┴─┴─┴─┴──┴──┴────────────────────────────────────┴─┴─┴─┴─┴─┘
	     px	┘     └ py				pz ┘
    α ┐
   ┌─┬─┬─┬─┬─┬────────────────────────────────────────────┬─┬─┬─┬─┬─┐
   │░│α│a b c│						  │3│d e f│▒│
   └─┴─┴─┴─┴─┴────────────────────────────────────────────┴─┴─┴─┴─┴─┘
     px ┘     └ py					pz ┘
    α ┐ ┌ ß
   ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬────────────────────────────────────────────┬─┐
   │░│α│a b c│ß│d e f│						  │▒│
   └─┴─┴─┴─┴─┴─┴─┴─┴─┴────────────────────────────────────────────┴─┘
	     px	┘     └ py					pz ┘


	Since REC expressions are executed from left to right, operators 
creating operands on the PDL must be written before those operators which 
use the operands.  This is the postfix or reverse Polish notation, which 
dispenses with parentheses as grouping symbols.  We will have more to say 
about this when we address the arithmetic operators.

	The next thing to consider is communications between the program and 
the user.  At the simplest level, a program must be able to accept input 
from the console and display output on it.  Given an operator to read single 
characters from the console keyboard, we will also be needing a predicate to 
determine whether a given character arrived on the PDL.  Here are two more 
operators and a predicate:

Operator/Predicate		Function performed

	R	Operator, reads a character from the keyboard into the top 
		of the PDL.  It also provides a convenient way to introduce 
		a pause into a program by use of the combination RL, as R 
		will wait until a key is pressed if a character is not 
		already waiting to be read.  Notice that R does not echo to 
		the console the character it reads.

	T	Operator, types on the console the contents of the top of 
		the PDL, leftmost (lowest-addressed) byte first; its 
		argument would normally be an ASCII character string.  It 
		leaves its argument unchanged.



	=	Predicate, true if the last two entries on the PDL have the 
		same length and are composed of the same sequence of bytes.  
		The last entry is lifted regardless of the outcome of the 
		comparison, the next-to-last entry will be lifted only if 
		equality is established.  Note that since length is 
		important, pure numerical equality doesn't yield a true 
		result if the arguments are numerical data of different types 
		(e.g. integer/floating point, single/double precision, 
		short/long integer, etc.)


	We can now write a program which reads characters from the keyboard 
and echoes them until an asterisk is read:

			(R '*'=; T L:)

Notice the L following the T: since T does not modify the PDL, we must get 
rid of each character lest the PDL saturate.  The terminating asterisk is 
not echoed, and both the asterisk read by R and the one loaded on the PDL by 
the operator '*' get erased by the comparison predicate.



	If we now want to assemble a string from characters received through 
the use of R, we will be needing an operator that joins the characters 
into a single string.  We will now be using subroutines, so we also give at 
this point a full description of the subroutine-calling predicate @.

Operator/Predicate		Function performed

	|	Operator, concatenates the next-to-last argument with the 
		last argument, forming a new argument which replaces both. 

	%	Operator, converts the top argument to the next lower type. 
		For our present purposes, given a two-byte argument as the 
		top of the PDL, % replaces it with its least significant 
		byte: for instance 2573% leaves a single byte whose value is 
		the ASCII carriage return (13 decimal).

	@σ	Predicate which causes execution of the subroutine whose name 
		is the ASCII character σ.  If σ is the character @, this 
		predicate uses the top PDL argument, which should be one or 
		two bytes long, corresponding to the name or address, 
		respectively, of the subroutine whose execution is desired.  


  @σ (cont.)	If the subroutine called by this predicate has NOT been 
		defined in REC, it will return as though it were a false 
		predicate, so that (@@) should be used in this case.  @@ 
		lifts its argument from the PDL before starting execution of 
		the subroutine it invokes.  (In the MC68000 version, 
		addresses must be 4-byte operands.)
		
	Let us now write a few programs which put together a line typed in 
at the keyboard, with various editing options.  The simplest one is the 
following:

		[read string iteratively]
		{(R 13 % =; T |:) J
		 (''@J 2573 TL TL;)}

The main program places a null string on the PDL and calls subroutine J, 
which reads, types and concatenates each incoming character to the previous 
top of the PDL, until it reads a carriage return character, which causes a 
return to the main program.  The main program then types a carriage return, a 
line feed and the string of characters collected by subroutine J; arguments 
are lifted after being typed and the program terminates.


	We can also state the above procedure recursively:

		[read string recursively]
		{(R 13 % =; T @J |;) J
		 (''@J 2573 TL TL;)}

		[read string recursively - another version]
		{(R 13 % = ''; T @J |;) J
		 (@J 2573 TL TL;)}

The two versions differ in subroutine J: the second one is entirely self 
contained in that it provides the null string necessary to have n+1 operands 
available for the n concatenations [|] which will occur when n characters 
followed by a carriage return are read; the subroutine in the first version 
relies on the calling program to provide this null string.

	All three of the above programs allow no mistakes to be made during 
typing.  All characters preceding the CR are concatenated into the final 
string.  The simplest feature to add is backspacing to erase individual 
characters.  The recursive version is more appropriate for the addition of 
line editing features because the concatenation of the individual bytes is 
postponed until after the CR has been read.

Our next program allows erasure of the rightmost exposed character by using 
the backspace:

	[BACKSPACE to erase character and reposition cursor]
	{(R 8% = 8%; 13%=''; T @J 8% = L 8%T ' 'TL TL: |;) J
	 (@J 8% =: 2573 TL TL;)}

When a backspace is typed, subroutine J will lift the rightmost character 
from the PDL and backspace, overwrite with a blank and backspace again on its 
copy on the screen (performed by the sequence 8% = L 8%T ' 'TL TL); it will 
return a backspace if a backspace is given as the first character or if more 
backspaces are given in succession than the number of characters collected so 
far on the PDL.  The main program repeats the attempt to read a line if it 
receives a backspace on return from J.

	The following program is a variant of the above, except that it uses 
the rubout character "DEL" and echoes the rubbed out characters in reverse.  
This version would be useful on a hardcopy terminal, where backspacing and 
overprinting is impractical.

	[DEL to erase a character with echo]
	{(R127%=127%;13%='';T@J127%=TL:|;) J  (@J 127%=: 2573TLTL;)}

	Another editing option is cancellation of the entire set of 
characters collected so far; the following two programs allow this by use of 
the ASCII control characters NAK (control-U) and CAN (control-X) which we 
denote by ^U and ^X. The first program, on detection of ^U, lifts one by one 
all characters gathered, types the character #, repositions the cursor or 
print mechanism of the console to the beginning of the next line and resumes 
the reading of a line from the beginning.  The second program blanks out the 
characters written so far, returning the cursor or print mechanism to the 
beginning of the same line, lifting characters from the PDL as it backspaces. 
This second program will of course be better suited to a screen-type console, 
whereas the first one will be more appropriate for use with a hard-copy 
terminal.  In both programs the line-gathering process terminates when a 
carriage return is typed at the console; the resulting line is then typed out 
on a new line.

	[^U to redo a line from the beginning]
	{(R 21% = 21%; 13% = ''; T @J 21% = L 21%; |;) J
	 (@J 21% = '#' TL 2573 TL: 2573 TL TL;)}

	[^X to cancel a line - with rubouts]
	{(R 24% = 24%; 13% = ''; T @J 24% = 8% T' ' TL TL 24%; |;) J
	 (@J 24% =: 2573 TL TL;)}

	Yet another editing option is the capability to retype the characters 
gathered so far.  Our next two programs accomplish this, in iterative and 
recursive fashions, respectively.  Both type a number sign # on detection of 
control-R (whose decimal value is 18) and move all characters gathered so far 
to the complementary PDL, in order to type them out from the earliest 
character typed in to the latest, returning them to the low PDL in the 
process.  In the recursive version this is done by the sequence m@RnT in 
subroutine R; in the iterative version it is done by ''m(''=;m:) ''(n''=;T:). 
Both programs require an initial null string on the PDL which is used as a 
marker to signal the end of the iteration of (''=;m:) in the first program 
and of the recursion in the second program; this null string is removed from 
the PDL by the last L in the main program.
 
	[^R to retype a line - iterative version]
	{(R 18% = 18%; 13%= ''; T
	  (@J 18% = '#' TL 2573TL ''m (''=; m:) ''(n''=; T:) :;) |;) J
	 ('' (@J 18%=: 2573 TL TL L;);)}

	[^R to retype a line - recursive version]
	{('' = '#' TL 2573TL ''; m @R n T;) R
	 (R 18% = 18%; 13% = ''; T (@J 18% = @R:;) |;) J
	 ('' (@J 18% =: 2573 TL TL L;);)}

	As a final example of line editing, we present a program which 
incorporates the backspace, control-X and control-R editing options:

	[combine backspace, ^X and ^R]
	{(''= '#'TL 2573TL ''; m @R n T;) R
	 (R	18%= 18%;		[ctrl-R]
		24%= 24%;		[ctrl-X]
		8%=  8%;		[BS]
		13%= '';		[CR]
		T(@J18%= @R:;)
		    8%=  L 8%T ' 'TL TL:
		    24%= L 8%T ' 'TL TL 24%;
		    |;) J
	 (''(@J 18%=: 24%=: 8%=: 2573TL TL L;);)}

The main program may be replaced by a subroutine L such as

	 (2573TL'> 'TL''(@J 18%=:24%=:8%=: &L;);) L

and incorporated into other programs; a call @L would then prompt the user
for a string, read it from the keyboard and return it as top of the PDL.

:	The Pushdown List, Part II (arithmetic operations)

All arithmetic operations in REC are carried out on operands which must be 
present on the PDL, so that to evaluate an arithmetic expression we must use 
reverse Polish notation to express the corresponding formula in terms of REC 
operators.  Consider for example the following formula:

			π (3.5²  - 2.5²)

The first thing we can do is enter π into the PDL, but the product will have 
to be postponed until the value of the parenthesized expression becomes 
available.  Thus we enter 3.5 twice into the PDL and multiply (thus obtaining 
the square).  Again an operation (subtraction) must be postponed until the 
square of 2.5 is on the PDL.  Accordingly we enter 2.5 twice into the PDL and 
multiply.  At this point there are three arguments on the PDL: 6.25, 12.25 
and π (starting from the top).  We may now subtract 6.25 from 12.25 and 
multiply π and the difference together.  The sequence of REC operators is the 
following:

		    3.1415926 3.5 3.5 * 2.5 2.5 * - *



	Since each arithmetic operator requires a known and fixed number of 
arguments, no grouping symbols (such as the parentheses used in the original 
formula) are needed; in our example, each of the operators * and - uses the 
last two arguments entered into the PDL and leaves a single result. An 
alternative sequence of operators to produce the same result would be

		    3.5 3.5 * 2.5 2.5 * - 3.1415926 *

which has the advantage of minimizing the number of arguments present on the 
PDL at any given point.  In this formulation, however, one must take care 
that at least one space or comma separates the subtraction operator from the 
number-loading operator 3.1415926, for otherwise the dash would be compiled 
as part of the constant following it, rather than as the subtraction operator.

	We continue now our discussion of operators which take their arguments
from the PDL with a description of the arithmetic/logical operators.  A 
feature common to the operators +, - and * is that they require two arguments 
and return one result in place of the original two. The operator / returns 
two values if both arguments are of numeric types whose size doesn't exceed 4 
and one if at least one of them is of floating point type (size 5 or 8).  If 
arguments of different sizes are given to +, -, *, / or the predicate N, 
conversions of the argument of smaller size to larger sizes will occur until 
the sizes match, and then the operation will be performed. 
If the top argument is not a numeric type (size 0, 1, 2, 4, 5 or 8), the 
error flag is set, the operation is abandoned and the PDL remains unchanged.  
If the top argument is of numeric type but the next is not, the operation 
will be abandoned after setting the error flag and the top argument is lost, 
as it is removed from the PDL before testing the next argument and is not 
replaced in case of error.

	All arithmetic and logical operations are restricted to 1 and 2-byte 
integers in the case of REC80 and REC86, which do not incorporate long 
integers and floating point numbers, nor automatic type conversions for
operands of different sizes.

Operator/Predicate		Function performed

      number	Operator, enters the number in its binary form into the PDL. 
		"number"  may be an instance of any of the following 
		expressions, where in addition to the metasymbols introduced 
		in Chapter 1, d is any decimal digit (0-9), n is a nonzero 
		decimal digit (1-9) and ε stands for the null string:

			Two-byte integers:

				-n | d | [-|ε]nd*
  number (cont.)
			Four-byte integers:

				[-0|0d]d*

			Single precision floating point numbers:

				[-|ε]d*.d*  |
				[-|ε]d*.d*E[-|+|ε]d*  |
				[-|ε]dd*E[-|+|ε]d*

			Double precision floating point numbers:

				[-|ε]d*.d*D[+|-|ε]d*  |
				[-|ε]dd*D[+|-|ε]d*
		
		The terms "two-byte", "four-byte", "single" and "double 
		precision" refer to the internal representation of the 
		numbers, which require 2, 4, 5 and 8 bytes, respectively. 
		Note that all forms may be preceded by an optional minus 
		sign, but not by a plus sign, which would be interpreted as 
		the addition operator.  

  number (cont.)    Expressed in words, the above forms mean the following, 
		apart from the optional sign:  A two-byte integer is any 
		single digit, a string of digits whose first digit is not 
		zero or a minus sign followed by a string of digits the first 
		of which is not 0; a four byte integer is -0 or a string of 
		two or more digits the first of which is always zero.  A 
		single precision (SP) floating point number is signaled by 
		the presence of a period (indicating the decimal point), the 
		letter E followed by an optionally signed digit string, or 
		both, except that if the decimal point is not present, at 
		least one digit must appear for the E to be interpreted as 
		part of a number.  A double precision (DP) floating point 
		number always has the letter D followed by an optionally 
		signed and possibly empty digit string; again, in the absence 
		of a period at least one digit to the left of the D is 
		required for the presence of a numeric constant to be 
		recognized. The number on the right of the E or D (whose 
		value is zero if the digit string is empty) is interpreted as 
		a power of ten which multiplies the number represented by the 
		digit string on its left. 
		
		The following panel shows a few examples. 
		
  number (cont.)
			0		Two-byte integer zero.
			00		Four-byte integer zero.
			-127		Two-byte number.
			01000001	Four-byte number.
			.		Single precision 0.
			.1E-15		Single precision number.
			4D200		Double precision number.
			3.14159265358D	Double precision number.
			-E3		Not a number, but three	operators: 
					-,  E and the two-byte integer 3.

		The syntax of floating point numbers is mostly identical to 
		that of FORTRAN's REAL and DOUBLE PRECISION constants, the 
		exceptions being that an initial + is not part of the number, 
		that the period by itself yields a valid number (0) and that 
		the digit string in the exponent may be empty.  Finally, the 
		syntax allows no blanks or other characters within the string 
		defining a constant; any character not allowed by the above 
		possibilities terminates the conversion and compilation of 
		the number and is preserved and compiled as the next operator 
		or predicate in the program.

	+	Operator.  If either argument is the null string, the result 
		is the other argument; a null remains if both are null.  If 
		both arguments are one byte long, + returns the logical sum 
		(or) of its arguments (i.e., a bit of the result is 1 if 
		either of the corresponding bits in the arguments is 1, 0 if 
		both are 0). If either argument is of size 2 or greater, the 
		result will be the arithmetic sum of the two arguments 
		expressed in the type of the larger of the two arguments.

	-	Operator.  If the top argument is the null string, the 
		result is the other argument; if the lower argument is null, 
		the top argument is returned if its size is 1 and its 
		negative otherwise.  If both arguments are 1 byte items the 
		result will be their logical exclusive or (in which a given 
		bit of the result is 1 if the corresponding bits of the 
		arguments are different, 0 otherwise); for arguments of 
		larger sizes this operator returns the result of subtracting 
		the top argument from the next (e.g., 3.,5- yields -2.).

	*	Operator.  Returns a zero of the size of the longer argument 
		if the other argument is the null string, a null string if 
		both are null.  
		
  * (cont.)	If the size of both arguments is 1, the result is the logical 
		product (and) of the operands (the result will have a one 
		only where the corresponding bits of the original arguments 
		are one).  All other cases result in the arithmetic product 
		of the operands performed and expressed in the type of the 
		longer operand.

	/	Operator.  Returns two zeros of the size of the top argument 
		if the lower one is the null string; in all other cases it 
		attempts to divide the lower argument by the top.  Two one- 
		byte arguments always yield two-byte results; integer 
		divisions leave two results, the remainder and the quotient 
		(with the quotient as top argument) whereas floating point 
		divisions leave only the quotient.  Two-byte integers are 
		considered unsigned, so that -1,2/ yields 32767 as the 
		quotient and 1 as the remainder, because -1 is treated 
		as 65535.  The results of four byte integer divisions, on 
		the other hand, reflect the signs of the operands.  Integer 
		division by zero leaves the arguments unchanged (except for 
		one-byte operands which will have been converted to two-byte 
		integers); floating-point division by zero returns the 
		largest representable number of the corresponding type.

	N	Predicate. It requires two arguments, both of which are 
		lifted regardless of the logical outcome.  If both arguments 
		are null, N is true.  Otherwise, conversions are performed on 
		the smaller argument if the sizes are different; size one 
		operands make N true if their logical product is nonzero and 
		false otherwise; N is true for other sizes if the lower 
		argument is less than or equal to the top argument and false 
		otherwise.  (Note that two-byte integers are treated as 
		unsigned operands in the comparison.)

	~	Operator, requires one numeric argument.  Leaves null strings 
		unchanged, complements or negates its argument if its size is 
		one or greater than one, respectively.  The error flag is set 
		and the operation is abandoned if the argument is nonnumeric.

	^	Operator.  Mostly used to increment the top argument by one. 
		The top argument must be of a valid numeric operand size; 
		null strings are left unchanged.  In practice, ^ places a 1 
		of the size of its operand on the PDL and uses the + 
		operator to complete its action.



	d	Predicate.  Requires one numeric argument.  If d's argument 
		is the null string or a zero of any size, it gets lifted and 
		the truth value of the predicate is false.  Otherwise d 
		subtracts the value 1 of the appropriate size from its 
		operand and returns with the value true.


	%	Operator, converts the top argument to the next lower type, 
		where the order, from greater on down is double precision/ 
		single precision/four-byte integer/two-byte integer/ one-byte 
		argument/null string.  Arguments whose size is not 0, 1, 2, 
		4, 5 or 8 remain unchanged and cause an error to be noted.  
		DP to SP and SP to 4-byte integer conversions may cause 
		overflow, indicated by the largest number representable in 
		the corresponding format.  Integer to integer conversions are 
		always done by removal of the appropriate number of 
		high-order bytes. Null strings are left unchanged.  This 
		operator is often used to generate single ASCII control 
		characters.  For instance, a single carriage return may be 
		generated by the two-operator sequence 13%.



	\	Operator, converts the top argument to the next higher type; 
		see the above description of % for the ordering of operand 
		types.  \ is also restricted to numeric types.  Conversion of 
		an integer type to another integer type is accomplished by 
		appending the appropriate number of zero bytes on the left, 
		with no sign extension (one and two-byte numbers are treated 
		as unsigned integers); conversion of long integer to single 
		precision floating point does take the sign of the integer 
		into account.  Double precision operands are left unchanged.

	O	Predicate.  True if the argument on the PDL is an ASCII 
		string satisfying the syntax of numbers given above; the 
		result is the same number converted to the corresponding 
		binary representation.  Both the null string and a single 
		minus sign are accepted and convert to a two-byte zero.  O 
		is false if termination of the number conversion algorithm 
		doesn't occur at the end of the argument, in which case the 
		argument is left unchanged.





	#	Operator.  Converts a numeric argument to a decimal ASCII 
		string representation of the argument's value.  The null 
		string always yields a single ASCII 0, results from 
		four-byte integers always contain an extra leading 0, 
		single-precision floating point operands always produce a 
		string containing a decimal point and double-precision 
		arguments always produce a decimal point and a D-prefixed 
		exponent of ten in their result.  Nonnumeric arguments cause 
		the error flag to be set and the operation to be abandoned 
		with no changes to the PDL.

	&	Operator, exchanges the top two arguments, regardless of 
		their sizes.  The arguments need not be numeric.

	pG	A combination of the operators p and G (to be described in 
		detail later on) whose effect is to place on the PDL a 
		duplicate of the top argument.

	lyG	A combination of the operators l, y and G (described 
		individually in the next section); the net effect is to place 
		on the PDL a copy of the last operand moved to the PDL 
		complement without affecting it.  This combination is 
		equivalent to npGm, but it involves less byte movements. 

	Let us illustrate the use of the operators and predicates just 
described with a few examples.  In our first example a recursive factorial 
subroutine is driven by its main program to produce factorials for the 
integers 0 to 12 in four-byte arithmetic.  Subroutine F expects one 
argument on the PDL and replaces it with a single result.

	[4-byte factorial of an integer, defined as follows:
	 n! = n*(n-1)! for n>0;	   0! = 1]
       { [recursive factorial subroutine]
	 (pG -01 N 'Error' TL; 00 = 01; pG d @F *;) F

	 [main program: loop until PDL top becomes 013]
	 (00 (013 =; pG # T O '!=' TL @F # TL 2573TL ^:) ;) }

	Note that the factorial subroutine only gives valid results for 
input values between 0 and 12 (since 13! is greater than 2 147 483 647, the 
largest positive integer representable in the four-byte format), and that it 
rejects negative values of its argument.




	Our second program uses Newton's method for roots of equations to 
extract the square root of a non-negative numbers.

	[Square root by Newton's method]
       { [collect a string from the console, with editing options]
	 (''='#'TL@c''; m@RnT;) R
	 (R18%=18%; 24%=24%; 8%=8%; 13%='';
	  T(@J18%=@R:;) 8%=L8%T' 'TLTL: 24%=L8%T' 'TLTL24%; |;) J

	 [prompt for input, deliver the input string]
	 ('>'TL''(@J 18%=: 24%=: 8%=: @c&L;);) L
	 [type carriage return and line feed]	 (2573TL;) c

	 [Newton iteration routine: requires the number c whose 
	  root is sought to be on the complementary PDL and an 
	  approximation x to the root on the PDL]
	 (pG pG lyG & / + 0.5 *	      [yields new approx. (x+(c/x))/2.]
	  pG m -    [save approx. and compute difference with previous]
	  (pG 0. N ~;;)		[make absolute value of the difference]
	  lyG /			 [compute error relative to new approx]
	  1.E-8 N n;	  [exit if relative error below this threshold]
	  n pG # TL @c:) N	[type current approximation and repeat]

	 [Main program: get input, check validity, get root]
	 (@L (O)L 'Not a number' TL @c:
	  0.+ \%    [force argument to single precision floating point]
	  pG 0. N L;		       [exit if input is 0 or negative]
	  pG m @N			     [set up arguments, call N]
	  'sqrt('TL n #TL ')='TL #TL @c:) }	  [type result, repeat]

	This program illustrates the use of parentheses to negate a 
predicate [(O) in the first line of the main program], in this case to 
reject input strings that do not translate to a numeric value.  In the second 
line of the main program, 0.+ ensures that integer arguments of whatever 
size get converted to the single precision floating point formats; the pair 
\% ensures that double precision arguments get reduced to single precision, 
while leaving single precision values unchanged.  The program is terminated 
if a nonpositive argument was given; otherwise the arguments for N are set 
up, N is called, the result is displayed and the program repeats from the 
beginning.  N is called with the number itself as the initial approximation; 
we will show how to improve this in the next section.





	Subroutine N is a more extensive example of reverse Polish notation 
usage.  Given an approximation x to the root on the PDL and the number c 
whose root is sought on the PDL complement, the sequence pGpGnpGm& leaves the 
set of operands [x, x, c, x] on the PDL (listed from deepest to topmost) and 
c on the PDL complement; the operators /, +, 0.5 and * leave successively the 
operands [x, x, c/x], [x, x+(c/x)], [x, x+(c/x), 0.5] and [x, 0.5*(x+(c/x))] 
on the PDL.  The last result is the new approximation obtained by application 
of Newton's formula; let us call it x'.  The relative error │x-x'│/2 is 
computed, and if it does not exceed 1E-8, x' is returned as the final result, 
with c remaining in the PDL complement; otherwise the value of x' is typed 
and a new iteration is carried out.

	In our final example of this section we give a subroutine to compute 
the double precision cosine of its argument, assumed to be given in radians, 
by means of a range reduction to the interval [0,π/2] and a Taylor series 
expansion through the 10th term:

	  9      k   2k
 cos x ≈  Σ  (-1)   x  /(2k)! = (1 - (x²/2)(1 - (x²/12)(1 - (x²/30)(1 -
	 k=0
			    (x²/56)(1 - (x²/90)(1 - (x²/132)(1 -

			    (x²/182)(1 - (x²/240)(1 - (x²/306))))))))))
	[cosine, using range reduction and a Taylor series expansion]
	{(0.D0 +	     [make sure argument is double precision]
	  (pG 0.D0 N ~;;)	[take absolute value [cos(-x)=cos x]]
	  pG 1.5707963267948966D0 / 0.5D0 +	       [get x/(pi/2)]
	  (pG 2147483648D0 N; 'Out of range'TLL)	[check range]
	  %%			[floor of x/(pi/2): n = |_x/(pi/2)_|]
	  pG 04/Lm\\		     [save mod(n,4), convert n to DP]
	  1.5707963267948966D0 pGm * -	[x - n*pi/2: range reduction]
	  n lyG 02/L (00=L;L& -;)  [reverse interval if mod(n,4) odd]
	  pG * ~ pG m		    [ -x*x, a copy on the complement]
	  306.D/^ lyG240.D/*^ lyG182.D/*^	  [inner three terms]
	  lyG132.D/*^ lyG90.D/*^ lyG56.D/*^	   [next three terms]
	  lyG30.D/*^ lyG12.D/*^ n2.D/*^		   [last three terms]
	  n (d 01N ~;;)	     [give proper sign according to mod(n,4)]
	  ;;) c

	 [main program: call c to make a table]
	  (00 (025=; pG 015*	   [do table in 15 degree increments]  
		\\pG#TL			  [convert to DP, type value]
		3.1415926535897932D0 * 180D0/	 [convert to radians]
		@c '  'TL #TL 2573TL	[compute cosine, type result]
		^:)			       [increment and repeat]
	   ;) }
: The Pushdown List, Part III (Address handling, data movement and variables)

Since one of the purposes of REC is that it should be a language in which 
operating system functions can be conveniently expressed, it is clear that it 
should have a set of operators to move data between the PDL and anywhere in 
memory, and that it should allow creating blocks on the PDL itself for use as 
buffers.  Once blocks are created, a means for storing their addresses must 
be provided.  This role is filled by variables, which is an array where 
addresses (or address-sized data) may be stored.

	A word on addresses before going on to the list of operators.  In 
REC80 (the REC compiler for the 8080 and compatible processors like the 8085 
and Z80) all addresses are two byte integers.  In the compiler for the 8086 
processor (REC86), addresses may be two- or four-byte operands; if an address 
is a two-byte integer, it is assumed to be an offset relative to the data 
segment base.  The data segment contains the buffers for communicating with 
the operating system (CP/M-86 or MS-DOS), the variable and subroutine address 
tables, and the PDL.  A four-byte argument given as an address in REC86 is 
assumed to consist of a segment base (the upper two bytes) and an offset (the 
lower two bytes) relative to that base, allowing thus access to the entire 
address space of the 8086.  In REC68, the compiler for the MC68000, all 
addresses must be given as four-byte integers; conversely, operators 
producing addresses yield four-byte integers.
	In both REC80 and REC86 the table of variables is an array of 
two-byte cells; storing a four-byte 8086 address in a variable will occupy 
the given variable and the one following.  In REC68 the variable cells are 
four bytes long.

	In addition to the address, variable and block operations, we 
include in our next list operators and predicates to effect hexadecimal 
conversions, to test for the occurrence of errors and to save and restore 
the machine registers.

Operator/Predicate		Function performed
		
	&	Operator.  & exchanges the top two PDL arguments, regardless 
		of their sizes.
		
	p	Operator, places the two 2-byte values px and py-px on the 
		PDL; that is, the origin and the size of the top argument.
		In REC68, the origin is a four-byte value.

	l	Operator. Places on the PDL the value of pz, which is the 
		current high limit of the PDL as well as the address of the 
		cell containing the size of the last argument entered by the 
		operator m on the complementary PDL.
	G	Operator.  Requires two 2-byte values on the PDL, an origin 
		(lower) and a value n representing a size (top).  It 
		replaces both with an argument of n bytes copied from the n 
		locations starting at the given origin.  Thus pG duplicates 
		the top argument and 128pGG gets the 128 bytes starting 
		at address 128 (absolute on the 8085; data segment relative 
		on the 8086).

	g	Operator.  Given an address as the top argument, it fetches 
		the byte stored at that address and places it on the PDL.  
		The address is not removed, but remains as the lower 
		argument.

	u	Operator.  Identical to g except that it increments by one 
		the address operand after fetching the byte stored at the 
		given address. Only the offset in the lower two bytes is 
		incremented when a 4-byte address is given in the 8086 
		version.

	y	Operator.  Similar to u, but a word (two bytes) is fetched 
		and the address is incremented by two.  The same provisions 
		apply regarding 4-byte arguments in the 8086 version.

	v	Operator.  Given two arguments on the PDL, an address 
		(lower) and a datum (top), it stores the datum forward from 
		the designated memory location, erases it, and adds the size 
		of the datum to the address, which remains on the PDL.  
		Only the offset is modified when a four-byte address is
		given in the 8086 version of REC.

	S	Operator. Expects two arguments on the PDL, a datum (lower) 
		and an address (top).  It stores the datum forward from the 
		designated memory location and erases both arguments from 
		the PDL when done.  

	c	Operator.  Given a 2-byte integer n on the PDL, c creates in 
		its place a block of n bytes and leaves as top argument a 
		pointer to the beginning of this block (a two-byte address). 
		If n is 2 or larger, the value n-2 is stored in the first 
		two bytes of the block, a useful arrangement if the block is 
		to be used as a buffer by s or P; no other initialization is 
		made.




	s	Operator, stores into an area of limited size. Requires two 
		arguments, a datum (lower) and an address (top).  If the 
		address is α, s will store the datum beginning at α+2 if its 
		size does not exceed the value stored at the word pointed to 
		by α (notice the connection with operator c above); no data 
		is stored at all if all will not fit and the error flag will 
		be set in this case.  Both arguments are lifted if the datum 
		fits; the datum will remain if it does not fit.

	P	Operator, stores into a buffer and notes length.  Similar in 
		arguments and operation to s.  The size of the datum will be 
		stored at the word whose address is α+2 and the datum 
		itself will be stored starting at α+4 if it will fit, that 
		is, if its size plus 2 does not exceed the buffer size stored 
		at the word pointed to by α.  Both arguments are lifted if 
		the data fits, but only the address will be lifted if it 
		does not.  The error flag is set in the latter case.  

	r	Operator.  Given an address as top argument, r replaces it 
		by the two-byte value at which it points.  In REC68, the 
		result is the four-byte word contained at the given address.


	$	Operator. Given a one- or two-byte argument on the PDL, whose 
		value lies between 0 and 127, $ replaces it with the address 
		of the corresponding cell in the table of variables and 
		subroutines.  Values between 0 and 32, and the value 127 are 
		used as variables, as they correspond to ASCII control 
		characters and are thus never used as subroutine names. 
		Values between 33 and 126 correspond to cells containing the 
		current definitions of REC subroutines whose names are the 
		corresponding ASCII characters.  Since @ and } are also 
		excluded as subroutine names, their cells may be used for 
		storing other addresses.

	H	Predicate.  True if the top argument is a hexadecimal string 
		in ASCII (containing only the decimal digits 0-9 and the 
		letters A-F), in which case it is converted to binary.  
		Conversion of an n-digit string produces an |_(n+1)/2_|-byte 
		value stored according to the processor's convention (least 
		significant byte in the lowest-addressed location in the 
		Intel processors; most significant byte in the lowest-
		addressed location on the 68000); |_x_| is the greatest 
		integer not exceeding x.  


  H (cont.)	Notice that leading zeros in the string affect the size of 
		the result.  Arguments causing H to become false are left 
		unchanged.  The null string causes H to be true, but is left 
		unchanged.

	!	Operator.  Performs the conversion inverse to H.  Given an n 
		byte value on the PDL (assumed to be stored following the 
		appropriate convention) it produces the corresponding 2n 
		character hexadecimal string in ASCII (with leading zeros if 
		necessary).

	?	Predicate.  False if no error has been recorded in the error 
		flag, true if a notation exists.  In the latter case, the 
		value of the flag is placed on the PDL.  This value is the 
		address of the last location from which the error notation 
		routine was called. No indication is given as to how many 
		errors have occurred if this predicate is true.  The error 
		flag is reset after being consulted.





	h	Operator.  Stores, restores or eliminates stored machine 
		registers.  It requires a single null argument, an argument 
		consisting of a pointer to the machine stack or two 
		arguments, the lower one a pointer to the stack an the top 
		one a two-byte zero.  The first use of h must provide a 
		single null string.  On the 8080, this causes h to push onto 
		the stack the registers PSW, HL, DE and  BC, leaving the 
		value of the machine's stack pointer SP (which points to the 
		last of the stacked values) in place of the null argument. If 
		h is given a non-zero two-byte argument, it assumes it is the 
		value of SP pointing to the location on the machine stack at 
		which it stored previously the machine registers, which it 
		then proceeds to unstack, leaving out of reach anything else 
		which may have been stacked after the corresponding ''h call; 
		it lifts also the SP value given on the PDL.  If the top 
		argument is a two-byte zero, h will assume that an SP value 
		is the next argument, and uses it to restore SP to the value 
		prior to the first use of ''h, that is, it lifts the stacked 
		register values from the machine stack without restoring 
		them; it also lifts both given arguments from REC's PDL.  On 
		the 8086, the stack pointer argument is a 4-byte value 
		consisting of the SP value in the lower two bytes and the 
		Stack Segment base in the upper two bytes.  
   h (cont.)	The registers saved are the flags, AX, BX, CX, DX, BP, SI, 
		DI, DS and ES.  On the 68000, the SP argument is the address 
		value of register A7; the flags and all registers but A7 are 
		saved.  Since PDL and workspace pointers are kept in machine 
		registers in REC68, much care must be exercised in using this 
		operator.  In all versions, a store/restore or 
		store/eliminate operation pair must occur within the same 
		expression; otherwise other stack contents (notably return 
		addresses and entry points saved by braces) will be lost.

	The main operators for saving and fetching data are G and S.  The 
remainder were especially chosen on the one hand to scrutinize the memory 
under REC control, and on the other to give the widest possible latitude in 
defining variables in applications of REC.









	The following list shows a few ways to use the above operators; in 
it α, ß and δ represent any operations generating addresses, µ represents 
a two-byte constant, Θ represents a variable number (0-32, 127) and 'data' 
represents any operation producing on the PDL a datum to be stored.

	α(ß=;g[process]v:)	process bytewise from α to ß-1

	ßα(δ=L;u[proc]&mvn:)	fetch string from α to δ-1, process 
				bytewise, save at ß and following

	αµm(ndm pGr[proc]v:L;)	process µ words starting at α

	α Θ $S			store address α in variable cell Θ

	Θ $r			fetch contents of variable cell Θ

	'data' m l Θ $S		store datum in PDL complement, save its
				address in variable Θ

	Θ $r yG			retrieve datum from PDL complement (other 
				items may have been moved to the PDL 
				complement meanwhile, making the datum not 
				immediately available to n)

	'data' Θ $r s		use PDL complement block as buffer, redefine 
				its contents

	µ c Θ $S		create a (µ-2)-byte buffer on the PDL, save 
				its address in variable Θ

	µ cL m l Θ$S		create a µ-byte buffered variable on the 
				PDL complement

	'data' Θ $r s		write into a buffer (length not noted)

	'data' Θ $r P		write into a buffer (length noted)

	Θ $r^^yG		recover datum saved by P

	Θ $r yG			retrieve entire contents of a buffer

	To make our next examples interesting and useful, we will have them 
handle the information received by the program through the operating system's 
"command line".  This will require explaining some operating system internals;
we will restrict our discussion to CP/M and MS-DOS.

	In CP/M and MS-DOS, a program residing on a disk is called into 
execution by means of a "command line", consisting of the program name 
followed by a space and any parameters that the program is to receive.  This 
parameter string or "command line tail" is passed on to the program in the 
buffer starting at address 080H (hexadecimal); address 080H contains the 
character count of the string and the string is stored forward from address 
081H.  The first two parameters of the command line tail are parsed as file 
names and placed forward from locations 05CH and 06CH.  A file name consists 
of a disk identifier, a name of up to 8 characters and an extension of up to 
3 characters; omission of the disk designator causes a default of @ (which 
indicates the currently logged disk unit) before conversion to the internal 
disk-numbering scheme, the other two parts are blank filled on the right.  If 
the command line tail is empty, the file name buffer at 5CH is certain to 
contain eleven blanks starting at 05DH.

	When REC is called into execution and finds a file name at 05CH, it 
will attempt to open it, and read, compile and execute a program from it.  
Any parameters following this file name are treated as a command line tail to 
be received by the REC program at the beginning of its execution.




		rec80 sample file.one b:file.two

The above command line causes the program from file SAMPLE.REC to be compiled 
and executed; this compiled program will have available to it the file name 
FILE.ONE expanded and stored in the buffer at 5CH, the file name B:FILE.TWO 
expanded and stored in the buffer at 6CH and the command line tail "FILE.ONE 
B:FILE.TWO" starting at 81H with the character count (19) in location 80H.  
The program from file SAMPLE may access this information through the 
operators given above, as illustrated in the following examples.

	[make a buffer in which to save the second file name
	 and save it; type and return the buffer's address]
	(33 c pG '05D'H 12G & S ! T H;) M

In this example, 33c creates a 33-byte buffer and its address; the pG which 
follows makes a copy of the address to be used later by the operator S; 
'05D'H12G copies the 12-byte expanded file name to the PDL, & exchanges data 
and address for S and S stores the 12 data bytes starting at the beginning of 
the 33-byte buffer. !TH converts the address to ASCII, types it and restores 
is to binary.  The reason behind making a longer buffer is that CP/M requires 
a "file control block" (FCB) for its operation on disk files; prior to 
opening a file the last 21 bytes of the FCB should be 0.

	One way of initializing the rest of an FCB is illustrated by the next 
subroutine:

	[clear the upper 21 bytes of an FCB, given its
	 address; leave the original address]
	(pG 12 + 7m (n d m '000000'H v:;)L;) C

	This subroutine uses pG to ensure a copy of the original address is 
left on the PDL upon completion.  12+ adds 12 to the address, which is the 
starting location to be cleared. 7m sets up a counter in the PDL, and a loop 
starts.  The sequence n d m fetches the counter, decrements it and returns it 
to the PDL complement (if not zero), '000000'H makes a three-byte binary zero 
and v stores it forward from the current address, which it updates (adding 
three to it in this case) after storing.  Notice that d in the inner loop 
will be true 7 times so that v will store the 21 required zeros.  The final L 
erases the address left over from the last execution of v.

	We may use variable cells to store FCB addresses for later use by 
the operating system call operators k and K (treated in Chapter 5):

	[calls M and C above to make FCBs for the filenames at 05CH and 06CH;
	 the FCB addresses are saved in variables 30 and 31, respectively]
	('05C'H @M @C 30$S '06C'H @M @C 31$S;) F

The following subroutines illustrate the use of operators g and u.

	[Returns the address of the first nonblank character between
	 two addresses, searching from highest to lowest]
	(& m (g (" "=) nL; (d) n; pG n & =; m:) ;) <

	[Similar to the previous routine, searching from lowest to
	 highest]
	(m (u (" "=) dnL; pG n & =; m:) ;) >

In both subroutines the top PDL argument is assumed to be the higher address; 
the argument next to the top should be the lower address.  In the first 
subroutine the address left by g is explicitly decremented, whereas in the 
second the operator d is used only when a nonblank character is found.  
Operator & is used before predicate = in both subroutines to retain the 
limiting address of the search (the lowest address in the first case and the 
highest in the second); recall that predicate = always erases at least the 
top argument.

	Finally we exhibit an example in which l, y, s, P and r are used,
in the next panel.

[Execution of s and P, with diagnostics]
{(N n s;) s   (2- N n P;) P    (&mm p&L n lyGr & @@; n "Datum too big" TL)} Q

Subroutine Q must receive three arguments:  the two required by s or P and 
the letter s or the letter P as the top argument.  The first action taken is 
to exchange the letter and the buffer address and send both to the PDL 
complement [&mm].  The length of the datum to be stored is next placed on the 
PDL and the name of the subroutine to be called is retrieved [p&Ln].  The 
combination lyG puts on the normal end of the PDL a copy of the last argument 
sent to the PDL complement, which in this case is the buffer address; r 
replaces this address with its contents, i.e., leaves on the PDL the length 
of the buffer (assuming it was created by operator c).  & exchanges this 
value with the given letter and @@ calls the subroutine whose name is that 
letter.  If the letter is s, the length of the datum is tested against the 
buffer size, and if the former is less than or equal to the latter, the 
buffer address is retrieved and the datum is stored [Nns]; if the letter is 
P, 2 is subtracted from the buffer size (since P requires two bytes from the 
buffer to store the datum's length) and a comparison is performed before 
retrieving the address and executing operator P.  If in either s or P the 
comparison turns out to be false, predicate @@ becomes false, the address is 
retrieved and an error message is sent to the console; both datum and buffer 
address remain on the PDL, but subroutine Q terminates logically false.

	To close this section we give an improved version of the square root 
program.  This one distinguishes single and double precision arguments 
(integer arguments are converted to single precision) and computes (in 
subroutine I) the first approximation to the square root by dividing the 
number's exponent by two.  REC uses the ANSI/IEEE Standard 754-1985 for its 
floating point format, except that single precision numbers include an extra 
mantissa byte in order to distinguish them from long integers.  The standard 
specifies different exponent lengths for the single and double precision 
formats, as illustrated in the following figures, in which field boundaries 
are indicated by solid vertical bars, byte boundaries are denoted by broken 
lines, and bits are indicated by tick marks.  The most significant byte is on 
the left.

		┌┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┐
		s│   e  |│	|	|f	|	│	(a)
		└┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┘

    ┌┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┐
    s│   e  |	│   |	    |	    |	f   |	    |	    |	    │   (b)
    └┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┘

		(a) Single precision; (b) Double precision

	For a non-zero, in-range argument, in both cases 0.5 ≤ f < 1; the 
value of the single precision number is (-1)^s 2^(e-127) (1+f) and the value 
of the double precision number is (-1)^s 2^(e-1023) (1+f).  Thus, a better 
first approximation to the square root of a number whose biased exponent is e 
will be a number with the same mantissa and a biased exponent ((e-b)/2)+b, 
where b is the appropriate bias.  In order to compute this, we must extract 
the most significant two bytes, separate the exponent from the highest 
mantissa bits (we don't have to worry about s, since it is 0 in this 
problem), remove the bias, divide by 2, add back the bias, and reassemble.

	[Square root by Newton's method]
       { [collect a string from the console, with editing options]
	 (''='#'TL@c''; m@RnT;) R
	 (R18%=18%; 24%=24%; 8%=8%; 13%='';
	  T(@J18%=@R:;) 8%=L8%T' 'TLTL: 24%=L8%T' 'TLTL24%; |;) J
	 [prompt for input, deliver the input string]
	 ('>'TL''(@J 18%=: 24%=: 8%=: @c&L;);) L
	 [type carriage return and line feed]	 (2573TL;) c





	 [compute initial approximation: divide exponent by 2]
	 (p (8 =					  [test length]
		6+ 16pGm1023;		[expt. address & const. for DP]
		+2-,128pGm127;) pGmmm	  [constants on PDL complement]
	  pG2G		 [repeat address, get word containing exponent]
	  n/		    [separate exponent from high mantissa bits]
	  n-,2/ &L n+	       [remove bias, divide by 2, replace bias]
	  n*+ &S;) I			    [reassemble word, store it]

	 [Newton iteration routine: requires the number c whose 
	  root is sought to be on the complementary PDL and an 
	  approximation x to the root on the PDL]
	 (pG pG lyG & / + 0.5 *	      [yields new approx. (x+(c/x))/2.]
	  pG m -    [save approx. and compute difference with previous]
	  (pG 0. N ~;;)		[make absolute value of the difference]
	  lyG /			 [compute error relative to new approx]
	  (p&L8= 1.D-15;L1.E-8;)	 [choose appropriate threshold]
	  N n;		  [exit if relative error below this threshold]
	  n pG # TL @c:) N	[type current approximation and repeat]




	 [Main program: get input, check validity, get root]
	 (@L (O)L 'Not a number' TL @c:
	  0.+			     [force argument to floating point]
	  pG 0. N L;		       [exit if input is 0 or negative]
	  pG m @I @N	 [set up arguments, get initial approx, call N]
	  'sqrt('TL n #TL ')='TL #TL @c:) }	  [type result, repeat]


	In subroutine I, besides giving us the operand's address, p provides 
us with a means to test whether it is a single or double precision number.  
We use this again in subroutine N to choose the convergence threshold. In the 
exponent extraction and reassembly we take advantage of the fact that integer 
division leaves both quotient and remainder.  Note that the address of the 
most significant pair of bytes depends on the processor; when using REC68 we 
would have to remove the operator pair 6+ in the second line of subroutine I 
and replace +2- in the third line with the operator L, since the most 
significant word of the operand is already pointed at by px.

:			The Pushdown List, Part IV

	The last group of operators which take their arguments from the PDL 
is composed of input and output operators.

     Operator			Function performed

	t		Operator.  Given an address "org" (as top argument)
			and a length "l" (as lower argument), t displays on 
			the console the string of l characters stored in 
			memory starting at address org.  Both arguments are 
			lifted from the PDL.  Notice that T is equivalent to 
			the operator pair pt; t is often used in combination
			with q, an operator described in the next chapter.

	W		Operator whose arguments are identical to those
			required by t, but which sends the character string 
			described by the argument to the device logged in the 
			operating system as the list device (the LST: device 
			of CP/M; usually a printer).  W also removes both of 
			its arguments from the PDL after using them.


	i		Operator.  Given an argument on the PDL whose least
			significant byte represents the number of one of the 
			computer's communication ports, i reads in a byte 
			from that port, which it leaves on the PDL as top 
			argument.  The original argument stays on the PDL so 
			that it may be reused after disposing of the byte 
			read by i.

	o		Operator requiring two arguments, the lower one such
			that its least significant byte is the number of a 
			port and the top a byte to be written to that port.  
			o outputs the given byte to the indicated port and 
			lifts the byte from the PDL.  The port number stays 
			on the PDL, facilitating multiple outputs to the same 
			port.

	It should be clear that operators i and o afford the user detailed 
control of the peripheral resources of the computer, but for the same reason 
its use results in REC programs which are extremely dependent on the specific 
configuration of the computer for which they are written; consequently these 
two operators have not been used very frequently.

:[REC3.HLP]
[(c) G. Cisneros, 1985, 1990]
