________________

							 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.