Bard College – Computer Science – Design of Programming Languages
In this week’s lab we will create a program — another meta-program — to evaluate programs written in postfix notation. Postfix programs look a little strange, although, maybe not that strange after a few weeks of Lisp. Postfix notation puts the operator after the operands. So 2 + 3 would be 2 3 + and(18 + 2) / 4 is represented by 18 2 + 4 /. This is known as Reverse Polish Notation.
The magic of postfix is that it is relatively easy to evaluate expressions using a single stack; very little parsing or parentheses. Forth, Postscript, and Joy all use postfix notation, and the Java virtual machine is stack-based. Try it out on on repl.it.
Postfix Warm-Up
Evaluating expressions written in postfix is relatively straightforward using a stack. Procedures(i.e., operators) take their input(i.e. operands) from the stack(pop), and put their output on the stack(push). Most things that are not procedures, like numbers, are pushed onto the stack. More details can be found hetre.
The following stack operations would occur when evaluating 18 2 + 4 /
make-stack --> '()
push 18 --> '(18)
push 2 --> '(218)
v1 = pop --> '(18) v1=2
v2 = pop --> '() v2=18
push v2 + v1 --> '(20)
push 4 --> '(420)
v3 = pop --> '(20) v3=4
v4 = pop --> '() v4=20
push v4 / v3 --> '(5)
Evaluate 18 2 + 4 / using the following stack; document how make-stack works.
Our first step is turning the string we want to evaluate into a list of tokens; breaking up one long string into its constituent pieces.
"18 2 + 4 / " → [18, 2, '+', 4, '/']
We could use racket’s lexer package, but that’s a little overkill; we will see that later. For now we can use racket’s string-split function since all of our tokens will be separated by white-space.
Write the procedure lex: string → list.
(lex "18 2 + 4 /") → '(18 2 "+" 4 "/")
lex should turn numbers in the string into scheme numbers(use the string→number procedure along with nan?).
Evaluating Postfix
Write the procedure evaluate: list x stack → stack using the post-fix evaluation strategy.
Postfix Warm-Up
make-stack --> '()push 18 --> '(18)push 2 --> '(2 18)v1 = pop --> '(18) v1=2v2 = pop --> '() v2=18push v2 + v1 --> '(20)push 4 --> '(4 20)v3 = pop --> '(20) v3=4v4 = pop --> '() v4=20push v4 / v3 --> '(5) (define (make-stack) (let ((s '())) (lambda (cmd . rest) (cond ((eq? 'top cmd) (car s)) ((eq? 'display cmd) (begin (display s) (newline)))) ((eq? 'push cmd) (set! s (cons (car rest) s))) ((eq? 'pop cmd) (let ((v (car s))) (begin (set! s (cdr s)) v))) (else (error 'unsupported-stack-op))))))Lexing
Evaluating Postfix
Forth-ward