Reverse polish is the notation in which a+b is written a b +. For many purposes reverse Polish is the simplest possible representation of any kind of computation - there is no ambiguity about it at all, as operators appear in the order in which they are applied. In an algorithmic implementation, each operator takes its operands from a stack and replaces them with the result it produces.
Precisely because it is so well adapted to an algorithmic approach, reverse Polish is less well adapted to a purely linguistic approach - the push-down stack is an essentially algorthmic beast.
The language machine does in fact use a push-down stack behind the scenes for operands in purely interpreted implementations, and generally for use by the % operation which is used to capture input symbols in low-level lexical rules. But it was a design decision not to make the operand stack generally visible except as part of the external code api.
So here are rules for a reverse Polish calculator which exploits the ability to 'see' variables in enclosing contexts to enable operators to find their operands - a pure solution, if slightly devious:
.calc() - error output <- eof - ; - result output <- eof - ; - rp x :N '=' <- result 'result: ' N '\n' eom ;
- <- rp ; - x :A f1 :B <- rp - x :B ; - rp x :B f2 :C <- f1 :C ;
'N' <- f1 :(-A); '+' <- f2 :(A + B); '-' <- f2 :(A - B); '*' <- f2 :(A * B); '/' <- f2 :(A / B); '%' <- f2 :(A % B);
'~' <- f2 :(~A); '^' <- f2 :(A ^ B); '&' <- f2 :(A & B); '|' <- f2 :(A | B);
.calc(20L)
[ \t\n] <- - ;
[0-9] % { repeat .[0-9] % } { option '.' % repeat [0-9] % } toNum :N <- x :N;
'0x' .[0-9a-zA-Z] % { repeat .[0-9a-zA-Z] % } { option '.' % repeat [0-9] % } toHex :N <- x :N;
'0b' .[01] % { repeat .[01] % } toBix :N <- x :N;
.calc(30R) - anything <- line - ; eof <- line eof; '\n' <- line;
- line <- error '--- not understood - skipping one line\n' eom; - eom <- output ; - out <- eom - ;
Compile the calculator rules to internal format and wrap them to create shell script (a shebang script) called rpCalc.lm:
[peri@a4 examples]$ make rpCalc.lm
lmn2m -o rpCalc.lm -s $(which lm) rpCalc.lmn chmod +x rpCalc.lm
Try the calculator program:
[peri@p2 examples]$ ./rpCalc.lm 1 27 / 2 + = result: 2.03704 1 27 2 * 39 3 / + / = result: 0.0149254
And finally, here is the lm-diagram output from a single expression:
./rpCalc.lm -W 40 -t D
0 5 N + 2 * =
eof '1'
? eof '1'
.------------000090
| result '1'
|? result '1'
|.-----------000091
|| rp '1'
||? rp '1'
||.----------000092
||| x '1'
|||? x '1'
|||.---------000093
|||| % '0'
|||| repeat '0'
|||| [0-9] '0'
|||| % ' '
||||*
|||| [0-9] ' '
||||? [0-9] ' '
||||- [0-9] ' '
|||| option ' '
|||| '.' ' '
||||? '.' ' '
||||- '.' ' '
|||| toNum ' '
|||| : ' '
|||'---------000093---------- ----------000093-------------.
||| x x |
||| : : |
||| 000093-------------'
||| f1 ' '
|||? f1 ' '
||| f1 '5'
|||? f1 '5'
|||.---------000097
|||| rp '5'
||||? rp '5'
||||.--------000098
||||| x '5'
|||||? x '5'
|||||.-------000099
|||||| % ' '
|||||| repeat ' '
|||||| [0-9] ' '
||||||? [0-9] ' '
||||||- [0-9] ' '
|||||| option ' '
|||||| '.' ' '
||||||? '.' ' '
||||||- '.' ' '
|||||| toNum ' '
|||||| : ' '
|||||'-------000099---------- ----------000099-------------.
||||| x x |
||||| : : |
||||| 000099-------------'
||||| f1 ' '
|||||? f1 ' '
||||| f1 'N'
|||||? f1 'N'
||||| 000103-------------.
||||| f1 f1 |
||||| : : |
||||'--------000098---------- ----------000098------------.|
|||| rp x ||
||||? rp x ??
||||.--------000104 ||
||||| x x ||
||||| : : ||
||||| 000098------------'|
||||| 000103-------------'
||||| f1 ' '
|||||? f1 ' '
||||| f1 '+'
|||||? f1 '+'
|||||.-------000106
|||||| rp '+'
||||||? rp '+'
||||||.------000107
||||||| x '+'
|||||||? x '+'
|||||||- x '+'
|||||| 000107-------------.
|||||| rp rp |
|||||| 000107-------------'
|||||| x '+'
||||||? x '+'
||||||- x '+'
|||||- f1 '+'
|||| 000104-----------.||
|||| rp rp |||
|||| 000104-----------'||
|||| x x ||
|||| : : ||
|||| 000098------------'|
|||| 000103-------------'
|||| f2 ' '
||||? f2 ' '
|||| f2 '+'
||||? f2 '+'
|||| 000109-------------.
|||| f2 f2 |
|||| : : |
|||'---------000097---------- ----------000097------------.|
||| f1 f1 ||
||| : : ||
||'----------000092---------- ----------000092-----------.||
|| rp x |||
||? rp x ???
||.----------000110 |||
||| x x |||
||| : : |||
||| 000092-----------'||
||| 000097------------'|
||| 000109-------------'
||| f1 ' '
|||? f1 ' '
||| f1 '2'
|||? f1 '2'
|||.---------000112
|||| rp '2'
||||? rp '2'
||||.--------000113
||||| x '2'
|||||? x '2'
|||||.-------000114
|||||| % ' '
|||||| repeat ' '
|||||| [0-9] ' '
||||||? [0-9] ' '
||||||- [0-9] ' '
|||||| option ' '
|||||| '.' ' '
||||||? '.' ' '
||||||- '.' ' '
|||||| toNum ' '
|||||| : ' '
|||||'-------000114---------- ----------000114-------------.
||||| x x |
||||| : : |
||||| 000114-------------'
||||| f1 ' '
|||||? f1 ' '
||||| f1 '*'
|||||? f1 '*'
|||||.-------000118
|||||| rp '*'
||||||? rp '*'
||||||.------000119
||||||| x '*'
|||||||? x '*'
|||||||- x '*'
|||||| 000119-------------.
|||||| rp rp |
|||||| 000119-------------'
|||||| x '*'
||||||? x '*'
||||||- x '*'
|||||- f1 '*'
|||| 000113-------------.
|||| rp rp |
|||| 000113-------------'
|||| x '2'
||||? x '2'
||||.--------000120
||||| % ' '
||||| repeat ' '
||||| [0-9] ' '
|||||? [0-9] ' '
|||||- [0-9] ' '
||||| option ' '
||||| '.' ' '
|||||? '.' ' '
|||||- '.' ' '
||||| toNum ' '
||||| : ' '
||||'--------000120---------- ----------000120-------------.
|||| x x |
|||| : : |
|||| 000120-------------'
|||| f2 ' '
||||? f2 ' '
|||| f2 '*'
||||? f2 '*'
|||| 000124-------------.
|||| f2 f2 |
|||| : : |
|||'---------000112---------- ----------000112------------.|
||| f1 f1 ||
||| : : ||
||'----------000110---------- ----------000110-----------.||
|| rp x |||
||? rp x ???
||.----------000125 |||
||| x x |||
||| : : |||
||| 000110-----------'||
||| 000112------------'|
||| 000124-------------'
||| f1 ' '
|||? f1 ' '
||| f1 '='
|||? f1 '='
|||.---------000127
|||| rp '='
||||? rp '='
||||.--------000128
||||| x '='
|||||? x '='
|||||- x '='
|||| 000128-------------.
|||| rp rp |
|||| 000128-------------'
|||| x '='
||||? x '='
||||- x '='
|||- f1 '='
|| 000125----------.|||
|| rp rp ||||
|| 000125----------'|||
|| x x |||
|| : : |||
|| 000110-----------'||
|| 000112------------'|
|| 000124-------------'
|| '=' ' '
||? '=' ' '
|| '=' '='
|'-----------000091---------- ----------000091-------------.
| result result |
| output 'r' |
|? output 'r' ?
|.-----------000130 |
|| eom 'r' |
||? eom 'r' ?
||.----------000131 |
||| out 'r' |
r ||'----------000131 |
|| eom 'e' |
||? eom 'e' ?
||.----------000132 |
||| out 'e' |
e ||'----------000132 |
|| eom 's' |
||? eom 's' ?
||.----------000133 |
||| out 's' |
s ||'----------000133 |
|| eom 'u' |
||? eom 'u' ?
||.----------000134 |
||| out 'u' |
u ||'----------000134 |
|| eom 'l' |
||? eom 'l' ?
||.----------000135 |
||| out 'l' |
l ||'----------000135 |
|| eom 't' |
||? eom 't' ?
||.----------000136 |
||| out 't' |
t ||'----------000136 |
|| eom ':' |
||? eom ':' ?
||.----------000137 |
||| out ':' |
: ||'----------000137 |
|| eom ' ' |
||? eom ' ' ?
||.----------000138 |
||| out ' ' |
||'----------000138 |
|| eom 10 |
||? eom 10 ?
||.----------000139 |
||| out 10 |
10 ||'----------000139 |
|| eom '\n' |
||? eom '\n' ?
||.----------000140 |
||| out '\n' |
||'----------000140 |
|| eom eom |
|'-----------000130---------- ----------000130------------.|
| output output ||
'------------000090 ||
000130------------'|
000091-------------'
eof '\n'
? eof '\n'
eof eof
[peri@p2 examples]$
