Standard ML

RPN Calculator in Standard ML

There are three functions in this implementation. rpncalc is the main one. It calls inputLine to read in a line of input and then splits that line into non-blank pieces (calling tokens with the function isSpace as argument). Through the case expression the resulting list of tokens tks is checked on being non-empty; if it is, evalrpn is invoked and its return value is printed. Finally, rpncalc calls itself to repeat reading and evaluating. End of input causes inputLine to return the value NONE, in which case rpncalc ends the execution of the program by calling OS.Process.exit.

Normally, the return value of evalrpn is the string representation of a number – the outcome of computing an RPN expression. If the computation fails, however, an error message results.

Through the function foldl, evalrpn scans the list of tokens, passing to foldl the function evaltoken, so that the latter is applied to each token and some accumulated value. That value is a list, used by evaltoken as a stack for storing the intermediate results in the course of the computation. The initial value [] of the list is also passed to foldl. The return value of foldl is that same list, which then must contain only one number, otherwise the RPN expression is incorrect.

evaltoken processes a token tk by first checking if it represents a number. If so, that number is pushed onto the stack st. Otherwise, if the token is a character for one of the arithmetic operations, the corresponding operation (one of op + etc) is applied to the topmost two elements y and x of the stack, and the resulting number replaces them on the top of st. When a token is neither a number nor an operation, an exception is raised.

All syntax errors in the input RPN expression are dealt with by throwing exceptions. At several points this is done explicitly, using the raise operator. The exception Fail is thrown which the language defines to be a general-purpose exception with no predefined meaning. Fail requires an argument, so "" is passed, but this value is actually immaterial as the handler does not use it. Other exceptions are thrown implicitly. They occur when the stack st has no enough values stored for assigning to x and y, or when nth is called to select an operation from the list of four but its second argument is a wrong index, due to tk not being within "+-*/". Both explicit and implicit exceptions are handled at the same point – the expression that follows the keyword handle.

In the program we make use of functions from several modules of the language's Basis library. We open some of these modules so as the corresponding functions can be called with simple names. For the functions belonging to other modules, their names are prefixed by the module name and a dot.

One may notice that analyzing the token in evaltoken seems complicated beyond expectation and difficult to follow. The library support for manipulating text data in Standard ML is rich and flexible enough to meet all practical needs, but not always straightforward in use: switching back and forth between string and substring types is too frequent, string searching does not return a position (despite the name of the function), etc.

open TextIO String Char Real

fun evaltoken (tk,st) =
  case scan Substring.getc (Substring.full tk) of
    SOME (x,sr) => if Substring.string sr = ""
                   then x::st  else raise Fail ""
  | NONE        =>
      if size tk = 1 then
        let  val (s,_) = Substring.position tk (Substring.full "+-*/")
             val y::x::r = st
        in  List.nth ([op +, op -, op *, op /],
                      size (Substring.string s)) (x,y) :: r  end
      else  raise Fail ""

fun evalrpn s =
  (case foldl evaltoken [] s of
     [r] => toString r | _ => raise Fail "")  handle _ => "error"

fun rpncalc () =
  case inputLine stdIn of
    SOME s => (case tokens isSpace s of
                 [] => () | tks => print (evalrpn tks ^ "\n"))
              before rpncalc ()
  | NONE   => OS.Process.exit OS.Process.success

rpncalc ()