PLACE
spec
solutions
Algol 68

RPN Calculator in Algol 68

This Algol 68 implementation consists of a main part, a recursive procedure evalrpn that evaluates an RPN expression, and some help procedures.

The main part is a loop near the end of the text starting at the label rep. It reads lines from the standard input, storing each one in the string variable s. The call of nonblank checks whether its argument contains any non-blank characters, i.e., is nonempty. If so, s is passed to evalrpn. If evalrpn does return and by that time s does not contain any unprocessed leftover, the result r of evaluating the arithmetic expression in s is appropriately formatted and printed. Then a goto command loops back to rep so that another input line may be processed.

The program is terminated upon ending the standard input by an implicit call of the procedural argument of on logical file end. That procedure has, by way of a requirement, a bool return type, but all it actually does is pass control to the stop label which the language defines to be implicitly present at the end of the program text. Thus on logical file end sets an end-of-input event handler that happens to end the program execution as well.

As seen in this program, the goto word is optional in Algol 68: a label name itself acts as a control transfer command. Thus stop is really goto stop and rep is goto rep, but omitting the goto, beside tightening the text, has the effect of making the label names look as if they themselves are commands. This also applies to the label err which is referred to at several places.

evalrpn evaluates the RPN expression recursively by extracting tokens from the end of the string. The gettoken procedure returns either a real number or an integer from 1 to 4 encoding an operator: +, -, *, or /. The type (or, in Algol 68 terms, mode) token is defined to unite these two possibilities formally. evalrpn discriminates between the two cases using a construct called a conformity clause. In it, a real value is immediately returned, whereas an integer 1-4 is mapped to its corresponding operation, x+y etc., by means of a case clause. The values x and y of the two operands are obtained through calls of evalrpn to itself.

gettoken searches backwards for a nonblank substring in the input string which is passed to it by evalrpn. If it finds one, it sets the value of tk of type token correspondingly: if the substring is an operator character, it is encoded by its position k within the string "+-*/", otherwise getnumber is called which tries to parse the substring s[i+1:j] as a number. The input string is then reduced by removing the just analysed part of it, and tk gets passed back to evalrpn. In the calls of nonblank and getnumber where a slice of s is passed as an argument the value actually passed is a reference to a copy (generated by loc string) of the respective slice. This is necessary because each of the called procedures needs a reference and a slice is not one. loc is the way to generate an anonymous variable dynamically on the program stack.

In order to obtain a numeric value from its string argument, getnumber opens an input channel on the string (using the built-in procedure associate) so that a built-in procedure, get in this case, can be used to do the conversion as if through reading from a file. However, getnumber has first to check whether the string to be read correctly represents a number. To this end it ensures that there is at least one digit, at most one decimal dot, and no other characters. In addition, getnumber strips the string off a possible arithmetic sign and a trailing decimal dot because these, although correct according to our calculator specification, are not allowed in a number denotation by Algol 68.

Eventually, getnumber either returns a real number if one can be read off the string, or does not return at all. In the latter case it passes control to the label err in the main part of the program, so that an error message is printed before possibly processing a new input line. So does gettoken when it cannot detect a token in the input string. As a result, a missing or incorrect token causes getnumber or gettoken, and thus all nested recursive calls of evalrpn, to abort immediately and yield control to err.

The text of the program is probably more easily read with the knowledge of the following syntactic conveniences of Algol 68 that are made use of:

For example, here is how nonblank searches backwards for a nonblank or blank character (depending on the value of b) in s. If the index is already 0, the search ends without success, and 0 — an invalid index — is produced and hence returned. If n is positive and s[n] is what is searched for, the index n is produced and returned. Otherwise, n decreases and the control is passed back to tst so that the tests are repeated with the new n.

Also unusual is upb, seen at several places in the program. It is an operator yielding the upper bound of a string's (or any array's) subscript.

The names of the procedures char in string and on logical file end, and that of the channel stand in contain blanks. Blanks within names are not meaningful in Algol 68, but may be used for better readability.

Certain identifiers are predefined in Algol 68 and form a separate namespace from the rest. The same applies to the identifiers that designate user-defined types (modes), such as token in this program. The language definition prescribes that these special names be represented in a way that distinguishes them in the text, but it is not specific about how to do that. In this implementation of the calculator they are underlined. Most Algol 68 translators expect them to be in capital letters.

proc nonblank = (ref string s, bool b) int: (
  int n := upb s;
  tst: (n = 0 | 0 |: b /= (s[n] = blank or s[n] = repr 9) | n | n -:= 1; tst)
);

proc evalrpn = (ref string s) real: (
  mode token = union (real,int);
  proc gettoken = (ref string s) token: (
    proc getnumber = (ref string s) real: (
      int sgn := 1;
      (s[1] = "+" or s[1] = "-" | (s[1] = "-" | sgn := -1); s := s[2:]);
      int nd := 0, dummy;
      for i to upb s while nd < 2 do
        (~char in string(s[i],dummy,"0123456789")
         | (s[i] = "." | nd +:= 1 | nd := 2))
      od;
      (nd = 1 and s[upb s] = "." | s := s[:upb s-1]);
      (nd < 2 and upb s > 0
        | file f; real x; associate(f,s); get(f,x); close(f); sgn*x
        | err)
    );   # getnumber #
    int j = nonblank(s,true);
    (j = 0 | err);
    int i = nonblank(loc string := s[:j], false);
    token tk := (int k := 0; j-i = 1 and char in string(s[j],k,"+-*/")
                 | k
                 | getnumber(loc string := s[i+1:j]));
    s := s[:i];
    tk
  );   # gettoken #
  (gettoken(s) | (real z): z,
                 (int op): (real y := evalrpn(s); real x := evalrpn(s);
                            (op | x+y, x-y, x*y, x/y)))
);   # evalrpn #

string s;
on logical file end(stand in, (ref file f) bool: stop);
rep:
read((s,newline));
(nonblank(s,true) > 0 |
  real r = evalrpn(s);
  (nonblank(s,true) > 0 | err);
  print((fixed(r,0,4),newline)));
rep;
err: print(("error",newline));
rep

boykobbatgmaildotcom