Bard College – Computer Science – Design of Programming Languages
In this week’s lab we will create our first interpreter. We’ll write a program — a 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. Try it out on on repl.it.
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.
Lexing
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 whitespace.
Write the procedure lex: string → list.
(lex "18 2 + 4 /") → '(18 2 "+" 4 "/")
This procedure should turn numbers in the string into numbers; this procedure is useful:
Evaluating expressions written in postfix is pretty straightforward using a stack.
Procedures(i.e., operators) take their input(e.g. operands) from the stack(pop), and put their output on the stack(push). Most things that aren’t procedures, like numbers, are pushed onto the stack. More details can be found here. Create the following stack functions:
Starting with an empty stack;
(define stack '())
(empty-stack?): tests if the stack is empty;
(push-stack <item>): put item on the top of the stack and return the new stack;
(top-stack): returns the top item of the stack without removing it.
(pop-stack): remove the top item from the stack and return it;
The following stack operations would occur when evaluating(18 2 "+" 4 "/"):
Write the procedure evaluate: list → stack using the post-fix evaluation strategy.
(evaluate (lex "18 2 + 4 /")) → '(5)
Read-Eval-Print-Loop
The procedure replshould read a postfix expression from the keyboard, lex it, evaluate that, print the result, and loop back and do it all over again.
Lexing
Evaluating
(define stack '())(push-stack 18) --> '(18)(push-stack 2) --> '(2 18)(push-stack (+ (pop-stack) (pop-stack))) --> '(20)(push-stack 4) --> '(20 4)(push-stack (/ (pop-stack) (pop-stack)) --> '(5)Read-Eval-Print-Loop
(define (repl) (let ((exp (read-line))) (unless (equal? "exit" exp) (display exp)