________________
RPN CALCULATOR
lro
________________
<2019-01-02 Wed>
Table of Contents
_________________
Introduction
How I think it works
The Stack
Main Loop
Calculator Functions
factorial function
Introduction
============
A common exercise for prorgramming is to implement a [Reverse Polish
Notation] calculator, usually just with a commandline interface.
I have never actually done this exercise before. So here is my first
attempt in R7RS scheme.
[Reverse Polish Notation]
https://en.wikipedia.org/wiki/Reverse_Polish_notation
How I think it works
====================
A simple way to implement an RPN calculator is to use a stack, and
push each value onto the stack, then operate on the stack when you hit
an operator like `+' or `/'. If you are familiar with Forth then this
will sound pretty familiar.
The Stack
=========
So first we will define our stack, we will just use a list at the
moment, and each new element of the stack will be pushed onto the head
of the list.
,----
| (define *stack* '())
`----
Probably best to define the basic stack operations like /pop!/ and
/push!/.
,----
| (define (pop!)
| (let ((ret (car *stack*)))
| (set! *stack* (cdr *stack*))
| ret))
|
| (define (push! val)
| (set! *stack* (append (list val) *stack*)))
|
| (define (dup!)
| (set! *stack* (append (list (car *stack*)) *stack*)))
`----
Main Loop
=========
The main loop will consist of:
1. Wait for input from standard input.
2. Read each token in and check if either a number or an operator.
3. If operator, do operation.
4. If number, push onto stack.
I have used a named let to loop through the standad input using
/read/, then each which kind of acts like a tokenizer where it returns
each scheme object for us from standard input. As you can see it is
trivially easy to add more functions too this calculator by just
adding a clause to the /cond/ by adding some syntax, and writing a new
function that just has to interact with the stack.
,----
| (let loop ((input (read)))
| (display "RPN> ")
| (cond
| ((number? input) (push! input))
| ((eq? '+ input) (rpn-add))
| ((eq? '- input) (rpn-sub))
| ((eq? '* input) (rpn-mult))
| ((eq? '/ input) (rpn-div))
| ((eq? '% input) (rpn-mod))
| ((eq? '! input) (push! (fact (pop!))))
| ((eq? '. input) (begin
| (display (pop!))
| (newline)))
| ((eq? 'dup input) (dup!))
| (else (begin
| (display "ERROR not valid input: ")
| (display input)
| (newline))))
| (loop (read)))
`----
Calculator Functions
====================
So as you can probably guess all the /rpn-*/ functions are just
wrappers of scheme functions that get there arguments from the stack
and their return values are pushed back onto it.
For example addition:
,----
| (define (rpn-add)
| (push! (+ (pop!) (pop!))))
`----
We could write a macro that expanded from something like `(rpn-func
\+)' to `(push! (\+ (pop!) (pop!)))'.
,----
| (define-syntax rpn-func
| (syntax-rules ()
| ((rpn-func x)
| (push! (x (pop!) (pop!))))))
`----
Sweet! But i think it over complicates things a little bit, and also
how would we deal with functions that only pop the stack once? or if a
function has a diffeent name in scheme than what we want its RPN
equivalent?
So for now I will only use the macro in the main loop to replace the
/rpn-*/ functions in the /cond/ that pop two stack elements and also
have the same identifer in scheme and our RPN calculator.
We might reconjigger things around if we can find a better way.
,----
| (let loop ((input (read)))
| (cond
| ((number? input) (push! input))
| ((eq? '+ input) (rpn-func +))
| ((eq? '- input) (rpn-func -))
| ((eq? '* input) (rpn-func *))
| ((eq? '/ input) (rpn-func /))
| ((eq? '% input) (push! (modulo (pop!) (pop!))))
| ((eq? '! input) (push! (fact (pop!))))
| ((eq? '^ input) (push! (pow (pop!) (pop!))))
| ((eq? '$ input) (begin
| (display (pop!))
| (newline)))
| ((eq? 'dup input) (dup!))
| (else (begin
| (display "ERROR not valid input: ")
| (display input)
| (newline))))
| (loop (read)))
`----
factorial function
==================
A simple factorial implementation.
,----
| (define (fact x)
| (define (fact-iter n current)
| (if (= n 1)
| current
| (fact-iter (- n 1) (* n current))))
| (fact-iter x 1))
`----
And thats it for a simple commandline RPN calculator.
