RPN Calculator in Algol 60

Algol 60 has no text processing facilities, and even no useful text datatype. Its I/O is also very basic. Implementing the RPN calculator therefore requires that all the work for reading and parsing the input and converting it to numbers and operators must be programmed explicitly in the utmost detail. Because of this, compared to most other implementations, the one below is large and complicated.

main
│
│    getchar <──┬──────┬─┬─┐
│               │      │ │ │
├──> skiprest ──┘      │ │ │
│ ┌────────────┐       │ │ │
└─┴> evalrpn ──┘       │ │ │
    │                  │ │ │
    ├──> isoper <───┐  │ │ │
    │               │  │ │ │
    └──> gettoken —─┴—─┘ │ │
        │                │ │
        ├──> skipws ─────┘ │
        │                  │
        └──> getnumber ────┘

The string NL represents an end-of-line (newline) character. It is enclosed in upper left and right corner marks – just as the string within which it appears – in order to form an inner string within it. Otherwise the two letters would be treated as ordinary ones and not as a special-character designator.

As there is no way in Algol 60 to detect the end of input, the program keeps infinitely calling evalrpn, and must be terminated by Ctrl-C or similar.

Evalrpn reads the input one character at a time until an end-of-line character is met, recognizing, as it goes along, arithmetic operators, or assembling numeric values from series of characters, and performing the respective computations.

Individual operators or numbers are read and extracted in evalrpn by calling gettoken. Gettoken, in turn, skips any possible whitespace (skipws), checks whether it is an operator or a number to return to evalrpn, and calls getnumber for reading numbers. Because a number may start with a plus or a minus character, which is also an operator, whenever gettoken encounters + or -, it sets sgn to 1 or -1 so that it can be used by getnumber for correctly computing a number, should that procedure become called. End of line and errors due to incorrect tokens are duly detected and propagated up the call chain. Gettoken makes sure that a token is followed by either a whitespace or an end-of-line. Thus, if more tokens are to be searched for in the input line, each next call of gettoken starts at a space. If a non-blank is found after a token, gettoken signals an error to its caller.

The basic procedure that gettoken, getnumber and skipws call to obtain a character is getchar. It reads a character and maps it to an integer-value character code. In this program-defined encoding, digits have codes from 0 to 9 that correspond to their values, and all other characters have codes greater than 9. Each such code is held by a variable – essentially a named constant: dd for the decimal dot, add for + etc. A special code err represents erroneous characters.

The very reading of a character takes place by calling the procedure inchar (from the standard environment) with the number, 0, of the standard input channel, and a string of all characters acceptable to the calculator, including end-of-line. If one of these characters is read, the argument i takes the position of that character within the string. If a non-acceptable character comes, i is assigned 0.

During the parsing process, a variable named c holds the code (as returned by getchar) of the most recently read character. The variable is declared in the main program, so that all the relevant procedures can access it, including giving it an initial value in the main part of the program before reading a new input line. Another variable, tk, declared within evalrpn, carries a code returned by gettoken and representing the type of the most recently parsed token, or signalling a parsing error. When that token is a number, the number itself is stored in the y variable of evalrpn. Getnumber only sets y if it indeed succeeds in reading a number. If it encounters an error, y is not changed.

Evalrpn implements an upward recursive evaluation as described elsewhere on this website. Note that we are forced to read an input line strictly sequentially, without storing anything, as we do not want to limit explicitly the amount of the input but there is no way to provide a dynamically enlargable storage for it. Also for the same reason, we are unable to use an explicit stack for intermediate values without arbitrarily and explicitly limiting it. And because we have no stored input, the more natural downward recursion is inapplicable. It follows then that the upward-recursive evaluation is a forced choice: it does not require stored input or an explicit stack, giving us an implicit, ‘free’, and virtually unlimited stack.

Evalrpn returns an integer which encodes the token that it processed. It also sets the values of its variables y and x accordingly, in order to maintain the state of the RPN expression evaluation. The values of x for the different pending calls constitute the stack of intermediate values. The procedure is called with a by-name parameter which is used to return the value read or computed at the current call.

When the main part of the program finds, by the code returned from evalrpn, that an error occured in the course of evaluation, it calls skiprest to read and discard all input up to the end of the current line.

In Algol 60, long jumps, i.e. interprocedural go tos are possible, although this program does not make use of them. In case of error, we could have transferred control from whatever procedure it occurs in to the end of the main loop directly, rather than propagating the error all the way up the call chain. The effect would be not unlike raising an exception.

begin
  integer sp, dd, eoln, add, sub, mul, div, err,num, c, tk;
  real x;

  integer procedure getchar;
  begin integer i;
    inchar(0,⌜0123456789.+-*/ ⌜NL⌝⌝,i);
    getchar := if i = 0  then err
               else if i < 11 then i-1
               else if i = 11 then dd
               else if i = 12 then add
               else if i = 13 then sub
               else if i = 14 then mul
               else if i = 15 then div
               else if i = 16 then sp
               else                eoln
  end getchar;
  
  procedure skiprest; for c := c while c ≠ eoln do c := getchar;

  integer procedure evalrpn(r); real r;
  begin integer tk; real x, y;
  
    Boolean procedure isoper(o); value o; integer o;
    isoper := o = add ∨ o = sub ∨ o = mul ∨ o = div;
  
    integer procedure gettoken;
    begin integer sgn, tk;
  
      procedure skipws; for c := c while c = sp do c := getchar;
    
      Boolean procedure getnumber;
      begin integer d; real z;
        getnumber := false;
        z := d := -1;
      loop:
        if c < 10 then begin
          if d ≥ 0 then d := 1+d;
          if z = -1 then z := 0;
          z := 10×z+c
        end else if c = dd then begin
          if d = -1 then d := 0 else go to en
        end else go to en;
        c := getchar;
        if ¬ (c = sp ∨ c = eoln) then go to loop;
        if z ≥ 0 then begin
          y := sgn×z;  if d > 0 then y := y/10↑d;
          getnumber := true
        end;
      en:
      end getnumber;
  
    comment begin gettoken;
      skipws;
      sgn := 1;
      tk := c;
      if isoper(c) then begin
        c := getchar;
        if (tk = add ∨ tk = sub) ∧ (c <  10 ∨ c = dd) then begin
          if tk = sub then sgn := -1;
          tk := if getnumber then num else err
        end else tk := if c = sp ∨ c = eoln then tk else err
      end else if ¬ (c = eoln ∨ c = err) then
        tk := if getnumber then num else err;
      if ¬ (c = sp ∨ c = eoln) then tk := err;
      gettoken := tk
    end gettoken;

  comment begin evalrpn;
    tk := gettoken;
    if ¬ (tk = eoln ∨ isoper(tk)) then begin
      if tk = num then begin
        x := y;
        for tk := evalrpn(y) while isoper(tk-num) do begin
          tk := tk-num;
          if      tk = add then x := x+y
          else if tk = sub then x := x-y
          else if tk = mul then x := x×y
          else                  x := x/y
        end;
        if tk = eoln ∨ isoper(tk) then begin
          r := x;
          tk := if tk = eoln then num else tk+num
        end else if tk = num then tk := err
      end
    end;
    evalrpn := tk
  end evalrpn;

comment begin main;
  num := 50;  add := 51;  sub := 52;  mul := 53;  div := 54;
  sp := 20;  dd := 30;  eoln := 10;  err := 1001;
  for c := sp while true do begin
    tk := evalrpn(x);
    if tk = num then begin outreal(1,x); outstring(1,⌜⌜NL⌝⌝) end
    else if tk ≠ eoln then begin outstring(1,⌜error⌜NL⌝⌝); skiprest end
  end
end

boykobbatgmaildotcom