PLACE |

spec |

solutions |

Refal |

Processing text and symbol structures is the kind of work Refal shows its best at. An implementation of the RPN calculator that is most likely to take advantage of that is one following the reduction approach, as formulated here. More precisely, the idea is to parse the input into a sequence of typed tokens – numbers and operators – and then reduce the sequence down to a single number by performing the operations ‘in-place’.

In principle, that should result in a very compact and clear program. However, as Refal only has integers, calculations on decimal fractions, along with input/ouput of such values, have to be modeled programmatically. In fact, it is more convenient to represent numbers as common fractions – actually, pairs of integers – and only have to deal with decimal representations in parsing the input and formatting the result for printing. It turns out that this ancillary work accounts for 5/7 of the size of the program below, in number of lines. The program (in the Refal-5 dialect) is still reasonably small, though.

The set of functions that make up the program is comprised of four groups, implementing the general working of the calculator, parsing and formatting of numbers, arithmetic operations on fractions, and numeric and other utilities of general use. Wherever repetition is needed, the corresponding functions are recursive, and almost everywhere it is a tail recursion, which the compiler recognizes and implements as iteration.

The function that runs the calculator is `Rpn`

. `Go`

is the name required for the program's main function, so is accordingly labeled as an `ENTRY`

point. As the calculator has to function in a repetitive way, it must be implemented by a recursive function. `Go`

, however, is not permitted to be recursive, so all it does is pass control to `Rpn`

.

`Rpn`

obtains a line of text from the standard input by calling the library function `Card`

(whose name is a historical remnant of the times when the standard input was a deck of punched cards). `Detab`

then changes possible tab characters in the text to spaces, and `Wds`

splits up the string into ‘words’ containing no blanks. The result is matched against being empty or not. In the former case nothing is produced. If the outcome of `Wds`

is anything else, which we specify by a most general pattern – an `e`

-variable named `e.2`

– that value is passed to `Tks`

for determining which of the ‘words’ are numbers and which are operations. A correspondingly transformed sequence is passed to `Eval`

where the RPN expression is evaluated, and whatever is returned is printed out. Finally – both when `Wds`

returned an empty or non-empty sequence – `Rpn`

calls itself again for reading another input line. A return value `0`

from `Card`

signifies end of input, and by specifying no expression to compute in the respective clause `Rpn`

ends, and so does the function `Go`

and the program.

Note that `Rpn`

is written so that it does not have an argument: its only pattern-matching clause has nothing to the left of the comma sign. In a way, `Rpn`

replaces the missing argument by the result of calling `Card`

, and proceeds by matching that result.

`Wds`

puts parentheses around each of the ‘words’ that it finds, so that the latter remain separated in the resulting sequence: each one is a *term* in the sequence. (Without that, the result would have been just a sequence of non-blank characters.) As `Tks`

traverses the result of `Wds`

, it generates a new sequence by replacing the ‘words’ that parse as numbers with representations of those numbers, and the ‘words’ that represent arithmetic operators – with symbols naming suitable procedures. In order to ensure that each number representation is a term in the resulting sequence, it is enclosed in parentheses.

For parsing numbers `Tks`

calls `Dec`

. `Dec`

finds out whether a decimal dot is present in the argument sequence (a string), removes it, and calls `Frac`

with arguments the resulting string and the former position of the decimal dot in it. `Frac`

makes use of `Snum`

to check whether the string is a correct representation of an integer, and if so, obtains – through calling `Pow10`

and `Nrz`

– a representation of the original number as a fraction. In order to do its job, `Snum`

calls `PM`

to strip a possible arithmetic sign off the string, and then uses `Digs`

for finding out whether the string contains digits and nothing else but digits (each individual character is being checked by calling the library function `Type`

). `Snum`

then uses the library function `Numb`

for obtaining an integer from the string, and returns that integer.

Each of `Digs`

, `Snum`

, and `Frac`

– and therefore also `Dec`

– may return an empty value to signify a failure, so that the respective caller can discriminate, through pattern matching, between the two possible outcomes.

`Tks`

has a two-sequence argument. If an item from the second sequence parses as a number or operator (checked in this order), the translated value moves to the first, initially empty sequence. Checking for an operator is done by the function `Op`

, returning a symbol that is the name of a function performing the corresponding operation, or an empty sequence for a non-operator token. All tokens from the second sequence in `Tks`

are thus processed, and finally the first sequence is returned. If an incorrect token is found (`Op`

returned empty), `Tks`

also returns an empty value to signal an error.

Computing the RPN expression within `Eval`

is done by finding a triple of successive elements in the argument sequence, the first two of which are (representations of) numbers, and the third is a symbol – a function name. The function is invoked by passing it, along with the two numbers, to the so called meta-function `Mu`

. Then, `Eval`

calls itself on the shortened sequence, obtained by replacing the triple with the result of `Mu`

, i.e. the result of applying an arithmetic operator. Eventually, a correct RPN expression reduces to a single number, matched by `(e.x)`

, of which `Fmt`

creates a string representation, and that is being returned from `Eval`

. If the argument sequence of `Eval`

neither contains a computable triple nor is a single number – including when that sequence is empty due to `Tks`

having found an incorrect token – the original sequence does not represent a correct RPN expression, so `Eval`

returns the symbol `error`

.

`Fmt`

's job is to format a common fraction to decimal form for printing, including properly rounding the fraction to a chosen decimal place, removing trailing 0s and possibly the dot from the fractional part, and prefixing the resulting string with a `-`

when the value is negative. `Trimt`

is a helper function used for removing the trailing part, if any.

For the purpose of their use in the functioning of the RPN calculator, fractions are represented as sequences of the form *(numerator)* *denominator*, where the two parts are integers. Each fraction is ‘normalized’ in the sense that it is irreducible and its denominator is positive (a possible negative sign is ascribed to the numerator). This is the representation returned by `Dec`

and used within the functions `Fadd`

, `Fsub`

, `Fmul`

, and `Fdiv`

, implementing arithmetic on fractions. `Nrz`

is being used in all of them to obtain the normalized form of the result.

As an integer in Refal may itself be represented as a sequence of ‘macrodigits’, i.e. ‘small’ integers (with a possible `'-'`

in front of it), parenthesizing the numerator is necessary for keeping the two parts of the fraction separate. Also, as `Fadd`

etc. take arguments of two fractions, another pair of parentheses is put around the first fraction to separate it from the second.

The ordinary arithmetic functions, such as `+`

and `-`

, use a slightly different convention: the first argument needs not be parenthesized when it is a single macrodigit.

The library function `Numb`

, used to obtain a numeric value from a string, copes with strings of any size, producing a sequence of one or more macrodigits as needed. The function `Symb`

, used in `Fmt`

, does the reverse: it produces the decimal string representation of the integer, atomic or not, that is its argument.

The group of functions marked ‘utilities’ solve various small problems: finding if an integer is non-negative or not, negating an integer, finding the absolute value of an integer, the GCD of two integers, a power of 10, and (`Vs`

) selecting one of two values depending on whether the value of an expression matches a constant pattern or not.

Note that, as integers in Refal are of unlimited magnitude, the fractions that the calculator operates with are also arbitrarily large and precise. All computations within an RPN expression are being carried out without loss of precision. Only when the result has to be formatted for printing inaccuracy is introduced by limiting the number of printed digits after the decimal point to a certain value, 6 being chosen for the purpose of being specific. Thus, this implementation of the RPN calculator operates with arbitrarily large numbers, and expressions such as of the form *a b / b ** are guaranteed to evaluate to *a*.

$ENTRY Go {= <Rpn>} Rpn {, <Card> : {0 = ; e.1, <Wds <Detab e.1> ' '> : {= <Rpn>; e.2 = <Prout <Eval <Tks () e.2>>> <Rpn>}}} Detab {e.1 '\t' e.2 = <Detab e.1 ' ' e.2>; e.x = e.x} Wds {= ; ' ' e.r = <Wds e.r> ; e.w ' ' e.r = (e.w) <Wds e.r>} Tks {(e.ts) = e.ts ;(e.ts) (e.t) e.r, <Dec e.t> : {, <Op e.t> : {= ; s.o = <Tks (e.ts s.o) e.r>} ;e.x = <Tks (e.ts (e.x)) e.r>}} Eval {e.h (e.a) (e.b) s.o e.t = <Eval e.h (<Mu s.o (e.a) e.b>) e.t> ;(e.x) = <Fmt e.x> ;e.x = error} Op {'+' = Fadd; '-' = Fsub; '*' = Fmul; '/' = Fdiv; e.x = } * parsing & formatting numbers Dec {e.h '.' e.t, <Lenw e.t> : {s.n e.a = <Frac (e.h e.t) s.n>} ;e.x = <Frac (e.x) 0>} Frac {(e.n) e.p, <Snum e.n> : {= ; e.i = <Nrz (e.i) <Pow10 e.p>>}} Snum {e.x, <PM e.x> : {e.t, <Digs e.t> : {= ; T = <Numb e.x>}}} PM {'+' e.r = e.r; '-' e.r = e.r; e.r = e.r} Digs {= ; T e.x = T; s.c e.r, <Type s.c> : {'D' e.x = <Digs e.r T>; e.x = }} Fmt {(e.n) e.d, <Divmod (e.n) e.d> : {(e.i) e.f, <Abs e.f> : {e.af, <Divmod (<* (e.af) <Pow10 6>>) e.d> : {(e.f1) e.f2, <Vs (<Compare (<* 2 e.f2>) e.d>) ('+') (1) 0> : s.a, <Vs (<ZPos e.n> e.i) (F 0) ('-') ''> : e.s = e.s <Symb e.i> <Trimt '.' <Symb <+ (e.f1) s.a>>>}}}} Trimt {'.' = ; e.s '0' = <Trimt e.s>; e.s = e.s} * arithmetic of fractions Fadd {((e.na) e.da) (e.nb) e.db = <Nrz (<+ (<* (e.na) e.db>) <* (e.da) e.nb>>) <* (e.da) e.db>>} Fsub {((e.na) e.da) (e.nb) e.db = <Fadd ((e.na) e.da) (<Neg e.nb>) e.db>} Fmul {((e.na) e.da) (e.nb) e.db = <Nrz (<* (e.na) e.nb>) <* (e.da) e.db>>} Fdiv {((e.na) e.da) (e.nb) e.db = <Fmul ((e.na) e.da) (e.db) e.nb>} Nrz {(e.n) e.d, <GCD (<Abs e.n>) <Abs e.d>> : {e.c, (<Div (e.n) e.c>) <Div (e.d) e.c> : {(e.1) e.2, <ZPos e.2> : {T = (e.1) e.2; F = (<Neg e.1>) <Neg e.2>}}}} * utilities ZPos {'-' e.n = F; e.n = T} Neg {e.x = <- 0 e.x>} Abs {e.x = <Vs (<ZPos e.x>) (F) (<Neg e.x>) e.x>} GCD {(e.a) e.b, <Compare (e.a) e.b> : {'-' = <GCD (e.b) e.a> ;e.1, e.b : {0 = e.a; e.2 = <GCD (e.b) <Mod (e.a) e.b>>}}} Pow10 {0 = 1; e.p = <* 10 <Pow10 <- (e.p) 1>>>} Vs {(e.val) (e.pat) (e.1) e.2, e.val : {e.pat = e.1; e.x = e.2}}

boykobbatgmaildotcom