RPN Calculator in 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