RPN Calculator in K

Here is a program that implements the RPN calculator in K. The first four lines contain definitions of procedures. These adhere to K's convention of defaulting to x, y, and z the parameters of procedures of valence up to 3. The line that follows is the ‘main program’. The command \\ at the end exits the K interpreter.

op: {(4>"+-*/"?*x)&1~#x}                                          / is an operator?
pt: {:[op y; (,$.(x[1],:[y~,"/";"%";y],*x)),2_ x; (,$0.0$y),x]}   / process a token
ep: {r:@[{()pt/x};x;:]; `0:,:[(1~#r[1])&~*r;*r[1];"error"]}       / evaluate & print
tk: {x[&x="\t"]:" "; {(x?" ")#x}'(&>':0,~x=" ")_ x}               / tokenize
while[~*@[{if[0<#ts:tk x; ep ts]};0:`;:];]                        / read & process
\\                                                                / exit

Below I present another version of the same program, with greater number but shorter procedures. Such a detailed breakdown is not necessarily typical of real K programming, but the many definitions make the structure more immediately observable, and having more names that can be referred to helps keeping the discussion simple.

Note. Both the compact and the detailed versions are written in K2/K3. With small changes they can be made into K4.

The main part of the program calls an anonymous procedure – the text enclosed in curly braces – on the result of calling in. The latter returns individual text lines from the standard input which the former procedure processes. Processing consists of a single conditional statement calling tk for tokenizing the given line. If the resulting list ts of tokens is non-empty (0<#ts), it is passed to ep for evaluating the RPN expression and printing the outcome.

tk starts with replacing tab characters in the input string x with spaces. (The expression x="\t" produces a boolean vector with 1s at the tab positions in x. From it, & obtains a list of indices to apply the assignment :" " at.) Then, wp is used to determine the beginning positions of all non-blank substrings in x. The list of those indices is passed as a left argument to the cut (_) operator which breaks x down into a list of tokens. Finally, by means of ct, each token gets stripped off possible trailing spaces (ct itself only processes a single string; the adverb ' (‘each’) causes its application all over the list).

Within ep, evaluation is done by calling ev on the list (x) of tokens. In turn, ev calls pt, a processor for individual tokens, repeatedly on each token of the RPN expression list. Repetition is due to applying the ‘over’ (/) adverb. The evaluation starts with an empty list for a stack of intermediate values, and each call of pt returns an updated stack that gets used when processing the next token. The concluding value of that stack is the eventual result of ev.

The call of ev is indirect: it takes place in a protected evaluation mode enforced by pe. If any exceptional situation is raised in the course of evaluation, pe returns an error information rather than the normal result of the function being called.

More precisely, pe returns a two-item list. The first item is a boolean (0/1) indicating whether the evaluation failed or succeeded. In the latter case, the second item is the result. The ok procedure checks the failure/success flag, and also checks whether the result, if any, is a single-item list – this, too, is necessary in order to know that the RPN expression is correct. ok's call is nested in a conditional expression (:[…;…;…]), so that either the result or the string "error" is passed as the argument to pr which prints to the standard output.

The body of pt is another conditional expression, in which, depending on whether the current token y is an operator or a number, the corresponding action involving the stack x is taken. A string is an operator if its length is 1 and its first (and single) character is one of the four allowed. op is the procedure performing that test. If it yields true, co evaluates the arithmetic operation in y on the topmost two elements of the stack, and the result is pushed onto the shortened (2_) stack. If y is a number, that number is pushed onto x.

The co procedure joins its three string arguments in the necessary order – x and y are the arguments to the operator z, thus x z y – and evaluates the resulting string as a K expression using the . operator. As division is denoted by % in K, when z is "/" it gets replaced by "%".

The ft function tests a given string on containing a number by trying to convert it to one (0.0$). If the argument is not a number, the conversion operation raises an error condition; we already know that the string is not an operation either, so the given token is an incorrect one. Similarly, trying to shorten the stack x in pt by 2 items generates an error if the stack happens to be too small. Both errors are propagated up across function calls until they get trapped within pe, and so become visible to ep as described.

Note that, as the arithmetic evaluation has to be performed on strings, the partial results are stored in the stack as strings rather than numbers. Accordingly, both co and ft convert to strings (using $) the numbers that they return. (The , operation is added to give that string the status of a single item to be added to the stack; without it, the string would be melting down into separate character items.)

Also observe that the repeated processing of text lines, within while, until the standard input is exhausted, is achieved by calling in and the anonymous procedure through pe, i.e., ‘under protection against errors’. Thus the distinction between successful reading and end-of-input is being made by analysing pe's result as the condition that governs the loop continuation/termination.

in: {0:`}                                     / read
pr: {`0:x}                                    / print
ct: {(x?" ")#x}                               / cut trailing spaces
wp: {&>':0,~x=" "}                            / word positions
co: {,$ . x,:[z~,"/";"%";z],y}                / evaluate "x z y"
ft: {,$0.0$x}                                 / is a number?
op: {(4>"+-*/"?*x)&1~#x}                      / is an operator?
pt: {:[op y; co[x[1];*x;y], 2_ x; (ft y),x]}  / process a token
ev: {()pt/x}                                  / evaluate rpn
ok: {(1~#x[1])&~*x}                           / evaluation ok?
pe: {@[x;y;:]}                                / evaluate protected
ep: {pr[,:[ok r:pe[ev;x]; *r[1]; "error"]]}   / evaluate & print
tk: {x[&x="\t"]:" "; ct'wp[x]_ x}             / tokenize
while[~*pe[{if[0<#ts:tk x; ep ts]};in[]];]    / read & process
\\                                            / exit