Qwerty Reverse Polish Notation
From Esolang
Qwerty Reverse Polish Notation is a Reverse Polish notation calculator that is designed to be generally Turing-complete. In Qwerty Reverse Polish Notation (QRPN), almost all opcodes (except literals, references, labels and variables) are as small as 1 keystroke. The opcodes are separated by space (" ").
Contents |
[edit] Quick Reference
+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
| ~ not | ! pop | @ getn | # putn | $ swap | % mod | ^ pow | & and | * mul | ( dec | ) inc | _ neg | + add |
| ` xor | 1 ---- | 2 ---- | 3 ---- | 4 ---- | 5 ---- | 6 ---- | 7 ---- | 8 ---- | 9 ---- | 0 ---- | - sub | = eq |
+--------+--------+--------+--------+--------+--------+--------+--------+-----------------+--------+--------+--------+
| Q | W | E 10^x | R root | T atan | Y | U | I | O | P | { shl | } shr | | or |
| q | w | e exp | r sqrt | t tan | y | u | i | o | p | [ flr | ] ceil | \ roun |
+--------+--------+--------+--------+--------+--------+--------+--------+-----------------+--------+--------+--------+
| A | S asin | D | F | G | H | J | K | L log | : dup | " |########|########|
| a abs | s sin | d | f | g | h | j | k | l ln | ; | ' |########|########|
+--------+--------+--------+--------+--------+--------+--------+--------+-----------------+--------+--------+--------+
| Z | X | C acos | V | B | N | M max | < lt | > gt | ? rand |########|########|########|
| z | x exit | c cos | v | b bool | n | m min | , getc | . putc | / div |########|########|########|
+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
[edit] Turing-Complete?
QRPN is stack-based, however, arrays/lists/tapes can be achieved by using variable-variables. For example, the following code creates a list of numbers from 1 to 5
5 l> ( : : =$ <l
[edit] Examples
Ask user to input 2 numbers, and print its sum.
@ @ + #
1 @ 1 - + 9 %
Locals-based factorial
@ =value // value = input_number();
1 =result // result = 1;
$value =i // i = value;
>loop // loop:
$result $i * =result // result *= i;
$i ( =i $i // i --;
<loop // if ($i) { goto loop; }
$result // return result;
without comments:
@ =value 1 =result $value =i >loop $result $i * =result $i ( =i $i <loop $result
[edit] Implementation
This is the implementation in Perl, for more details, scroll down and see the POD documentation.
package Math::QwertyRPN;
require Exporter;
use vars qw($VERSION @ISA @EXPORT_OK);
use Math::Trig qw(asin acos tan atan);
use Math::BigFloat qw(:constant);
use POSIX qw(ceil floor log10);
use strict;
@ISA = qw(Exporter);
@EXPORT_OK = qw(eval_rpn shell);
$VERSION = '0';
sub eval_rpn($) {
# init variables
our $code = shift @_;
our @tokens = (split /(?:\s|\n|\r)+/m, $code);
our %labels = { };
our $i = 0;
# process code
$code =~ s'//.*?$mg;
$code =~ s'/\*([^*]|\*[^\/])*\*/mg;
# index GOTO labels
$i ++, (/>(\w+)/ and $labels{$1} = $i) foreach @tokens;
# runtime variables
our @stack = ();
our %variables = { };
our $pc = 0;
$_ = 1;
sub op(&) {
@stack < 2 and die 'Not enough operands.';
my $sub = shift;
my ($r, $l) = (pop @stack, pop @stack);
push @stack, $sub->($l, $r);
}
sub unary(&) {
@stack < 1 and die 'Stack is empty.';
my $sub = shift;
$stack[-1] = $sub->($stack[-1]);
}
sub round($) {
my $n = shift;
return int $n + 0.5 * ($n <=> 0);
}
sub bool($) {
shift and return 1;
return 0;
}
# main loop
while ($_) {
$_ = $tokens[$pc++];
# numbers
/^[+-]?(\d+(\.\d+)?)$/
and push @stack, $1 + 0;
# goto statements
/^<(\w+)$/ and do { return if @stack < 1;
pop @stack and $pc = $labels{$1}; };
# get variable
/^\$(\w+)$/ and push @stack, $variables{$1};
# get variable-variables
/^\$\$$/ and do { die 'Not enough operands for variable-variable.' if @stack < 1;
push @stack, $variables{pop @stack}; };
# assign variables
/^\=(\w+)$/ and do { die 'Not enough operands for variable assignment.' if @stack < 1;
$variables{$1} = pop @stack; };
# assign variable-variables
/^\=\$$/ and do { die 'Not enough operands for variable-variable assignment.' if @stack < 2;
my $l = pop @stack;
my $r = pop @stack;
$variables{$l} = $r; };
# first row: 12345
/^\~$/ and unary { ~(shift @_) };
/^\!$/ and pop @stack;
/^\@$/ and push @stack, <STDIN> + 0;
/^\#$/ and print 0 + pop @stack;
/^\$$/ and do { $a = pop @stack;
$b = pop @stack;
push @stack, $a;
push @stack, $b; };
/^\%$/ and op { (shift @_) % (shift @_) };
/^\^$/ and op { (shift @_) ** (shift @_) };
/^\&$/ and op { (shift @_) & (shift @_) };
/^\*$/ and op { (shift @_) * (shift @_) };
/^\($/ and unary { (shift @_) - 1 };
/^\)$/ and unary { (shift @_) + 1 };
/^_$/ and unary { -(shift @_) };
/^\+$/ and op { (shift @_) + (shift @_) };
/^\`$/ and op { (shift @_) ^ (shift @_) };
/^\-$/ and op { (shift @_) - (shift @_) };
/^\=$/ and op { (shift @_) == (shift @_) };
# second row: qwerty
/^E$/ and unary { 10 ** shift @_ };
/^R$/ and op { (shift @_) ** (1 / (shift @_)) };
/^T$/ and unary { atan shift @_ };
/^\{$/ and op { (shift @_) << (shift @_) };
/^\}$/ and op { (shift @_) >> (shift @_) };
/^\|$/ and op { (shift @_) | (shift @_) };
/^e$/ and unary { exp shift @_ };
/^r$/ and unary { sqrt shift @_ };
/^t$/ and unary { tan shift @_ };
/^\[$/ and unary { floor shift @_ };
/^\]$/ and unary { ceil shift @_ };
/^\\$/ and unary { round shift @_ };
# third row: asdfgh
/^S$/ and unary { asin shift @_ };
/^L$/ and unary { log10 shift @_ };
/^\:$/ and push @stack, $stack[$#stack];
/^a$/ and unary { abs shift @_ };
/^s$/ and unary { sin shift @_ };
/^l$/ and unary { log shift @_ };
# fourth row: zxcvbnm
/^C$/ and unary { acos shift @_ };
/^M$/ and op { my ($l, $r) = @_;
return ($l > $r) ? $l : $r; };
/^\<$/ and op { bool (shift @_) < (shift @_) };
/^\>$/ and op { bool (shift @_) > (shift @_) };
/^\?$/ and push @stack, rand;
/^x$/ and return @stack;
/^c$/ and unary { cos shift @_ };
/^b$/ and unary { bool shift @_ };
/^m$/ and op { my ($l, $r) = @_;
return ($l < $r) ? $l : $r; };
/^\,$/ and push @stack, getc STDIN;
/^\.$/ and print chr (0 + pop @stack);
/^\/$/ and op { (shift @_) / (shift @_) };
}
return @stack;
}
sub shell() {
print '>';
while (<>) {
eval { print join ',', eval_rpn $_; };
print "\n";
print "ERROR: $@\n" if $@;
print ">";
}
}
1;
=head1 NAME
QWERTY Reverse Polish Notation Calculator
=head1 SYNOPSIS
use Math::QwertyRPN qw(eval_rpn);
print eval_rpn "12 54 + 12 *"; # 792
A Reverse Polish notation calculator that has most opcodes of stack-based
assembly languages. It is generally Turing-complete (needs to be tested).
=head1 DESCRIPTION
The eval_rpn function evaluates an expression. The first argument is a string
containing the expression. The function returns the stack after the evaluation.
When an error occurred, C<die> will be called. However, you can trap errors
by using C<eval>, C<do> or other try-catch modules.
An RPN expression contain a sequence of operations, seperated by whitespaces
or line breaks, to know more about Reverse Polish notation, visit its
article on Wikipedia: L<http://en.wikipedia.org/wiki/Reverse_Polish_notation>.
C/C++ style line/block comments are supported:
// Line comment
/* block comment */
The operators that do not exist in other RPN calculators include GOTO labels,
I/O and comparsion operators. To create a GOTO label, write C<< >label_name >>,
where C<label_name> is the name of the label.
The GOTO statement is like C<< >label_name >>. However, GOTO is conditional,
it is only made if the value on the top of stack is not 0 (zero). Also,
GOTO has a side effect of popping the stack.
C<< 12 3 <label >> will end up with 12 (instead of 12 3) on the stack.
Variables can be created and read by using the C<=> and C<$> operator.
To get a variable, write C<$name>, where C<name> is the
name of the variable. The value of that variable will be pushed
to the top of the stack.
To set a variable, write C<=name>. The stack will be popped.
For example, C<< 50 =value >> will set variable C<value> to 50. The stack
will end up empty because the 50 was popped to assign the variable.
You can read-write variables in the based on the value on the top of the stack
by using variable-variables. To read a variable-variable, use C<$$>.
The expression C<50 $$> pushes the value of variable C<50> to the stack.
The top of the stack will be popped
and it becomes the name of the variable-variable.
To write a variable-variable, write C<=$>. The top of the stack will be popped
and it becomes the name of the variable-variable.
The following expression outputs 10:
10 // stack:10
5 // stack:10 5
=$ // variables:$5=10
5 // stack:5 variables:$5=10
$$ // stack:10 variables:$5=10
Arrays can be made by using variable-variables.
=head2 ASSEMBLER to RPN
A typical stack-based assembly code looks like this:
push 180 ; stack is 180
push 250 ; stack is 180 250
add ; stack is 430
push 50 ; stack is 430 50
jeq LABEL ; jump if equals
It will be translated to RPN like this:
180 250 + 50 = <LABEL
The PUSH opcode will be converted to numbers, and ADD will be converted
to C<+> as expected. However, there is no JEQ, JLT, JGT and other
compare-and-goto opcodes in RPN, so you must compare manually and goto.
C<50 = > means to compare the top of the stack with 50, and pushes 0 or 1
based on the result of the comparsion.
=head2 QUICK REFERENCE
Here is a list of all operators by order of QWERTY keyboard.
I don't have time to document all of them, so I used assembler opcode names.
+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
| ~ not | ! pop | @ getn | # putn | $ swap | % mod | ^ pow | & and | * mul | ( dec | ) inc | _ neg | + add |
| ` xor | 1 ---- | 2 ---- | 3 ---- | 4 ---- | 5 ---- | 6 ---- | 7 ---- | 8 ---- | 9 ---- | 0 ---- | - sub | = eq |
+--------+--------+--------+--------+--------+--------+--------+--------+-----------------+--------+--------+--------+
| Q | W | E 10^x | R root | T atan | Y | U | I | O | P | { shl | } shr | | or |
| q | w | e exp | r sqrt | t tan | y | u | i | o | p | [ flr | ] ceil | \ roun |
+--------+--------+--------+--------+--------+--------+--------+--------+-----------------+--------+--------+--------+
| A | S asin | D | F | G | H | J | K | L log | : dup | " |########|########|
| a abs | s sin | d | f | g | h | j | k | l ln | ; | ' |########|########|
+--------+--------+--------+--------+--------+--------+--------+--------+-----------------+--------+--------+--------+
| Z | X | C acos | V | B | N | M max | < lt | > gt | ? rand |########|########|########|
| z | x exit | c cos | v | b bool | n | m min | , getc | . putc | / div |########|########|########|
+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
Here is the list of other operations.
=over 5
=item 1
I<NUMBER>: Pushes a number to the stack.
=item 2
C<< < >>: Jumps to a label if the value on the top of the stack is not 0 (zero).
Example C<< <loop >>
=item 3
C<< > >>: Creates a label. Example: C<< >loop >>
=item 4
C<$>I<NAME>: Gets a variable. C<$var1> will push the value of C<var1>
on the top of the stack.
=item 5
C<=>I<NAME>: Sets a variable. C<12 =var1> will set C<var1> to 12, because
the item on the top of the stack is 12. Then 12 on the top of the stack will
be popped.
=item 6
C<$>I<NAME>: Gets a variable-variable.
=item 7: Sets a variable-variable.
=back
=head1 EXAMPLES
Ask user to input 2 numbers, and print its sum.
@ @ + #
Digital root calculator
1 @ 1 - + 9 %
Locals-based factorial
@ =value // value = input_number();
1 =result // result = 1;
$value =i // i = value;
>loop // loop:
$result $i * =result // result *= i;
$i ( =i $i // i --;
<loop // if ($i) { goto loop; }
$result // return result;
without comments:
@ =value 1 =result $value =i >loop $result $i * =result $i ( =i $i <loop $result
=head1 TODO
Stack-based factorial example
Support of subroutines
More detailed documentation
=cut
