Turbo Toolbox

home *** CD-ROM | disk | FTP | other *** search

/ Turbo Toolbox / Turbo_Toolbox.iso / sharew / exoten / rec / rec3.hlp < prev next >

Wrap

Text File | 1990-10-30 | 59.5 KB | 1,265 lines

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]