Reverse Polish Notation
1 RPN Stacks
rpn-stack?
empty-rpn-stack
rpn-stack-push
2 RPN Instructions
rpn-instruction?
2.1 Pushing Operands
rpn-operand?
rpn-operand
rpn-operand-value
2.2 Calling Operators
rpn-operator?
binary-rpn-operator
rpn-operator
rpn-operator-function
rpn-operator-input-arity
rpn-operator-output-arity
2.3 Arithmetic Operators
r+
r-
r*
r/
3 RPN Notation
rpn
4 Streaming RPN Computations
into-rpn
7.4

Reverse Polish Notation

 (require rpn) package: rpn

Reverse Polish Notation (RPN) is a way of writing expressions commonly found in calculators and Forth-like programming languages. In RPN, an expression is a list of instructions for manipulating data on a stack. The most basic instruction is to push a value onto the stack. Function call instructions pop a function’s arguments off the stack and push its results onto the stack. The rpn library represents an RPN program as a call to the rpn function with the program instructions as arguments.

Examples:
> (rpn 1)

(rpn-stack 1)

> (rpn 1 2 3)

(rpn-stack 1 2 3)

> (rpn 1 2 3 r*)

(rpn-stack 1 6)

> (rpn 1 2 3 r* r+)

(rpn-stack 7)

> (rpn 1 2 3 r* r+ 2)

(rpn-stack 7 2)

> (rpn 1 2 3 r* r+ 2 r-)

(rpn-stack 5)

1 RPN Stacks

procedure

(rpn-stack? v)  boolean?

  v : any/c

value

empty-rpn-stack : rpn-stack? = (rpn)

procedure

(rpn-stack-push stack instruction)  rpn-stack?

  stack : rpn-stack?
  instruction : rpn-instruction?

2 RPN Instructions

procedure

(rpn-instruction? v)  boolean?

  v : any/c

2.1 Pushing Operands

procedure

(rpn-operand? v)  boolean?

  v : any/c

procedure

(rpn-operand v)  rpn-operand?

  v : any/c

procedure

(rpn-operand-value operand)  any/c

  operand : rpn-operand?

2.2 Calling Operators

procedure

(rpn-operator? v)  boolean?

  v : any/c

procedure

(binary-rpn-operator binary-function)  rpn-operator?

  binary-function : (-> any/c any/c any/c)

procedure

(rpn-operator #:function function    
  #:input-arity input-arity    
  #:output-arity output-arity)  rpn-operator?
  function : procedure?
  input-arity : natural?
  output-arity : natural?

procedure

(rpn-operator-function operator)  procedure?

  operator : rpn-operator?

procedure

(rpn-operator-input-arity operator)  natural?

  operator : rpn-operator?

procedure

(rpn-operator-output-arity operator)  natural?

  operator : rpn-operator?

2.3 Arithmetic Operators

3 RPN Notation

procedure

(rpn instruction ...)  rpn-stack?

  instruction : any/c

4 Streaming RPN Computations

value

into-rpn : reducer?