HW06 - james-bern/CS136 GitHub Wiki
![image](https://private-user-images.githubusercontent.com/5091875/260880979-8629464a-28ce-403a-9f72-8ffe7d8212e6.png?jwt=eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXVCJ9.eyJpc3MiOiJnaXRodWIuY29tIiwiYXVkIjoicmF3LmdpdGh1YnVzZXJjb250ZW50LmNvbSIsImtleSI6ImtleTUiLCJleHAiOjE3MjUxODYyODIsIm5iZiI6MTcyNTE4NTk4MiwicGF0aCI6Ii81MDkxODc1LzI2MDg4MDk3OS04NjI5NDY0YS0yOGNlLTQwM2EtOWY3Mi04ZmZlN2Q4MjEyZTYucG5nP1gtQW16LUFsZ29yaXRobT1BV1M0LUhNQUMtU0hBMjU2JlgtQW16LUNyZWRlbnRpYWw9QUtJQVZDT0RZTFNBNTNQUUs0WkElMkYyMDI0MDkwMSUyRnVzLWVhc3QtMSUyRnMzJTJGYXdzNF9yZXF1ZXN0JlgtQW16LURhdGU9MjAyNDA5MDFUMTAxOTQyWiZYLUFtei1FeHBpcmVzPTMwMCZYLUFtei1TaWduYXR1cmU9OThjN2ZlNmQ2YzUwMWZhOTJhMWIzMzZjZTFmODc1OWUyODU3Y2JkMTZkNjVlMzcxMTA5Mjg3NGEwMTQ0ZjgzYyZYLUFtei1TaWduZWRIZWFkZXJzPWhvc3QmYWN0b3JfaWQ9MCZrZXlfaWQ9MCZyZXBvX2lkPTAifQ.27-VWYGGOsI0TLhjNiSCUHuHRCkpoZhP8F54l-dd07g)
PostScript is an interpreted language (like Python). PostScript programs are NOT compiled. Instead, they are interpreted by another program called an interpreter.
In this homework, you will write a simple but very real PostScript interpreter! 🎉
- To check equality between String's, do NOT use the
stringA == stringB
.- Instead, use
stringA.equals(stringB)
.
- Instead, use
- To check (approximate) equality between double's, do NOT use
numA == numB
.- Instead, use
ARE_EQUAL(numA, numB)
- Instead, use
if (...) {
} else if (...) {
} else if (...) {
} else {
}
- Our interpreter will interpret a PostScript program one token at a time.
- A Token is be one of these four types:
- a boolean like
true
andfalse
- a double like
4.0
- a String
- a built-in function like
def
,add
,sub
,mul
,sqrt
,eq
,exch
,dup
- a key (any String's that is NOT a built-in function)
- a built-in function like
- a list of tokens like
[dup, mul, exch, dup, mul, add, sqrt]
- a boolean like
- the interpreter uses a stack to store tokens we're still working with
- the interpreter uses a map (dictionary, table, hash table, hash map) to store key-token pairs
- the
add
function pops two tokens (which must be doubles) off of the stack, adds them together, and pushes the result onto the stack - the
def
function will let us define our own constants and custom functions-
when defining a new constant using
def
, you prefix the name with a/
, like/pi
- after the constant has been defined, you use it without a slash, like
pi
-
when defining a new constant using
5.0
--- BEGIN INTERPRETING [5.0] ----------
> 5.0
5.0
-----
stack
--- END INTERPRETING [5.0] ------------
5.0 2.0 sub 3.0 eq
--- BEGIN INTERPRETING [5.0, 2.0, sub, 3.0, eq] ----------
> 5.0
5.0
-----
stack
> 2.0
2.0
5.0
-----
stack
> sub
3.0
-----
stack
> 3.0
3.0
3.0
-----
stack
> eq
true
-----
stack
--- END INTERPRETING [5.0, 2.0, sub, 3.0, eq] ------------
/pi 3.14 def /tau pi pi add def
--- BEGIN INTERPRETING [/pi, 3.14, def, /tau, pi, pi, add, def] ----------
> /pi
pi
-----
stack
> 3.14
3.14
pi
-----
stack
> def
-----
stack
+ map {pi=3.14}
> /tau
tau
-----
stack
+ map {pi=3.14}
> pi
3.14
tau
-----
stack
+ map {pi=3.14}
> pi
3.14
3.14
tau
-----
stack
+ map {pi=3.14}
> add
6.28
tau
-----
stack
+ map {pi=3.14}
> def
-----
stack
+ map {pi=3.14, tau=6.28}
--- END INTERPRETING [/pi, 3.14, def, /tau, pi, pi, add, def] ------------
/pythag { dup mul exch dup mul add sqrt } def 3.0 4.0 pythag
--- BEGIN INTERPRETING [/pythag, [dup, mul, exch, dup, mul, add, sqrt], def, 3.0, 4.0, pythag] ----------
> /pythag
pythag
-----
stack
> [dup, mul, exch, dup, mul, add, sqrt]
[dup, mul, exch, dup, mul, add, sqrt]
pythag
-----
stack
> def
-----
stack
+ map {pythag=[dup, mul, exch, dup, mul, add, sqrt]}
> 3.0
3.0
-----
stack
+ map {pythag=[dup, mul, exch, dup, mul, add, sqrt]}
> 4.0
4.0
3.0
-----
stack
+ map {pythag=[dup, mul, exch, dup, mul, add, sqrt]}
> pythag
--- BEGIN INTERPRETING [dup, mul, exch, dup, mul, add, sqrt] ----------
> dup
4.0
4.0
3.0
-----
stack
+ map {pythag=[dup, mul, exch, dup, mul, add, sqrt]}
> mul
16.0
3.0
-----
stack
+ map {pythag=[dup, mul, exch, dup, mul, add, sqrt]}
> exch
3.0
16.0
-----
stack
+ map {pythag=[dup, mul, exch, dup, mul, add, sqrt]}
> dup
3.0
3.0
16.0
-----
stack
+ map {pythag=[dup, mul, exch, dup, mul, add, sqrt]}
> mul
9.0
16.0
-----
stack
+ map {pythag=[dup, mul, exch, dup, mul, add, sqrt]}
> add
25.0
-----
stack
+ map {pythag=[dup, mul, exch, dup, mul, add, sqrt]}
> sqrt
5.0
-----
stack
+ map {pythag=[dup, mul, exch, dup, mul, add, sqrt]}
--- END INTERPRETING [dup, mul, exch, dup, mul, add, sqrt] ------------
5.0
-----
stack
+ map {pythag=[dup, mul, exch, dup, mul, add, sqrt]}
--- END INTERPRETING [/pythag, [dup, mul, exch, dup, mul, add, sqrt], def, 3.0, 4.0, pythag] ------------
- The
Token
class represents a PostScript token. - This class is a "sum type"; it can be a boolean, double, String, or ArrayList.
class Token {
// // the Token's type; can be:
// - TOKEN_TYPE_BOOLEAN
// - TOKEN_TYPE_DOUBLE
// - TOKEN_TYPE_STRING
// - TOKEN_TYPE_LIST
int type;
// // getters
// NOTE: these crash the program if Token is the wrong type
boolean getBoolean(); // get value of a boolean-type Token
double getDouble(); // get value of double-type Token
String getString(); // get value of String-type Token
ArrayList<Token> getList(); // get value of List-type Token
// // constructors
Token(boolean value); // create new boolean-type Token with given value
Token(double value); // create new double-type Token with given value
Token(String value); // create new String-type Token with given value
Token(ArrayList<Token> value); // create new List-type Token with given value
}
- The stack is a specialized version of
Stack<Token>
- It has specialized functions for pushing and popping if you know a Token's type
static class HW06_Stack {
// // core Stack functions
int size(); // number of Tokens in the stack
void push(Token token); // push a Token to the stack
Token pop(); // pop a Token from the stack
// // special push functions
void pushBoolean(boolean value); // push(new Token(value));
void pushDouble(double value); // push(new Token(value));
void pushString(String value); // push(new Token(value));
void pushList(ArrayList<Token> value); // push(new Token(value));
// // special pop functions
boolean popBoolean(); // return pop().getBoolean()
double popDouble(); // return pop.getDouble()
String popString(); // return pop.getString()
ArrayList<Token> PopList(); // return pop.getList()
}
class Map<String, Token> {
// put key-value pair into the map
void put(String key, Token value);
// get value corresponding to key;
// NOTE: this crashes the program if key not in map
Token get(String key);
// returns whether map contains a key-value pair with key
boolean containsKey(String key);
}
static void interpretListOfTokens(ArrayList<Token> tokens, HW06_Stack stack, HashMap<String, Token> map);
static void processSingleToken(Token token, HW06_Stack stack, HashMap<String, Token> map);
static ArrayList<Token> tokenizePostScriptProgram(String program);
- If you know you're about to push a double-type Token with value
num
, you have three equivalent options (Option A is probably the easiest to read):
// Option A
stack.pushDouble(num);
// Option B
stack.push(new Token(num));
// Option C
Token token = new Token(num);
stack.push(token);
- If you know you're about to pop a double-type Token, you have three equivalent options (Option A is probably the easiest to read):
// Option A
double num = stack.popDouble();
// Option B
double num = stack.pop().getDouble();
// Option C
Token token = stack.pop();
double num = token.getDouble();
- If you don't know what type of Token you're popping, you can always do something like this:
Token token = stackPopToken();
if (token.type == TOKEN_TYPE_BOOLEAN) {
boolean bool = token.getBoolean();
...
} else if (token.type == TOKEN_TYPE_DOUBLE) {
double num = token.getDouble();
...
} else if (token.type == TOKEN_TYPE_STRING) {
String string = token.getString();
...
} else if (token.type == TOKEN_TYPE_LIST) {
ArrayList<Token> list = token.getList();
}
-
A-
- Make
processSingleToken(...)
work for the first three example programs
- Make
-
A
- Make
processSingleToken(...)
work for all four example programs
- Make
-
A+
- Write a Postscript program that...
- Defines a custom function
is_prime
usingdef
(you may implement and use any standard PostScript commands from the reference, e.g.,if
,mod
). - Calls
is_prime
on2
,3
,33
, and37
- (Or, if you're feeling really ambitious, uses some sort of PostScript for loop or something to call
is_prime
on the first100
numbers)
- Defines a custom function
- Make
processSingleToken(...)
work for the PostScript program you wrote :D - NOTE: You will likely need to extend/modify
tokenizePostScriptProgram(...)
. 🙂👍 I recommend using aStack<ArrayList<Token>> stack;
is_prime num is_prime returns boolean for whether num is prime
- Write a Postscript program that...
import java.util.*;
class HW06 extends Cow {
static final int TOKEN_TYPE_BOOLEAN = 0;
static final int TOKEN_TYPE_DOUBLE = 1;
static final int TOKEN_TYPE_STRING = 2;
static final int TOKEN_TYPE_LIST = 3;
static class Token {
int type;
private boolean _boolean;
private double _double;
private String _String;
private ArrayList<Token> _List;
Token(boolean value) { type = TOKEN_TYPE_BOOLEAN; _boolean = value; }
Token(double value) { type = TOKEN_TYPE_DOUBLE; _double = value; }
Token(String value) { type = TOKEN_TYPE_STRING; _String = value; }
Token(ArrayList<Token> value) { type = TOKEN_TYPE_LIST; _List = value; }
boolean getBoolean() {
ASSERT(type == TOKEN_TYPE_BOOLEAN);
return _boolean;
}
double getDouble() {
ASSERT(type == TOKEN_TYPE_DOUBLE);
return _double;
}
String getString() {
ASSERT(type == TOKEN_TYPE_STRING);
return _String;
}
ArrayList<Token> getList() {
ASSERT(type == TOKEN_TYPE_LIST);
return _List;
}
public String toString() {
if (type == TOKEN_TYPE_BOOLEAN) { return "" + _boolean; }
if (type == TOKEN_TYPE_DOUBLE ) { return "" + _double; }
if (type == TOKEN_TYPE_STRING ) { return "" + _String; }
if (type == TOKEN_TYPE_LIST ) { return "" + _List; }
ASSERT(false);
return "";
}
}
static ArrayList<Token> tokenizePostScriptProgram(String program) {
ArrayList<Token> result = new ArrayList<>();
ArrayList<Token> list = null;
ArrayList<Token> target = result;
Scanner scanner = new Scanner(program);
scanner.useLocale(Locale.US);
while (scanner.hasNext()) {
if (scanner.hasNextDouble()) {
target.add(new Token(scanner.nextDouble()));
} else if (scanner.hasNextBoolean()) {
target.add(new Token(scanner.nextBoolean()));
} else {
String string = scanner.next().trim();
if (string.equals("{")) {
list = new ArrayList<Token>();
target = list;
} else if (string.equals("}")) {
target = result;
target.add(new Token(list));
} else if (string.length() != 0) {
target.add(new Token(string));
}
}
}
return result;
}
static class HW06_Stack {
private Stack<Token> _stack;
HW06_Stack() {
_stack = new Stack<>();
}
int size() { return _stack.size(); }
Token pop() { return _stack.pop(); }
boolean popBoolean() { return _stack.pop().getBoolean(); }
double popDouble() { return _stack.pop().getDouble(); }
String popString() { return _stack.pop().getString(); }
ArrayList<Token> PopList() { return _stack.pop().getList(); }
void push(Token token) { _stack.push(token); }
void pushBoolean(boolean value) { _stack.push(new Token(value)); }
void pushDouble(double value) { _stack.push(new Token(value)); }
void pushString(String value) { _stack.push(new Token(value)); }
void pushList(ArrayList<Token> value) { _stack.push(new Token(value)); }
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
ArrayList<Token> tmp = new ArrayList<>();
for (Token token : _stack) { tmp.add(token); }
for (int i = tmp.size() - 1; i >= 0; --i) {
stringBuilder.append(tmp.get(i).toString());
if (i != 0) stringBuilder.append('\n');
}
return stringBuilder.toString();
}
}
static void interpretListOfTokens(ArrayList<Token> tokens, HW06_Stack stack, HashMap<String, Token> map) {
boolean PRINT_TOKEN = true;
boolean PRINT_STACK_AND_MAP = true;
boolean PRINT_BEGIN_AND_END_INTERPRETING = true;
if (PRINT_BEGIN_AND_END_INTERPRETING) {
PRINT("--- BEGIN INTERPRETING " + tokens + " ----------\n");
}
for (Token token : tokens) {
if (PRINT_TOKEN) {
PRINT("> " + token + "\n");
}
processSingleToken(token, stack, map);
if (PRINT_STACK_AND_MAP) {
// NOTE: only prints map if nonempty
if (stack.size() > 0) PRINT(stack);
PRINT("----- \nstack");
if (map.size() > 0) {
System.out.print("+ map ");
PRINT(map);
}
PRINT();
}
}
if (PRINT_BEGIN_AND_END_INTERPRETING) {
PRINT("--- END INTERPRETING " + tokens + " ------------\n");
}
}
static void processSingleToken(Token token, HW06_Stack stack, HashMap<String, Token> map) {
// TODO
}
public static void main(String[] arguments) {
String program = "5.0";
// String program = "5.0 2.0 sub 3.0 eq";
// String program = "/pi 3.14 def /tau pi pi add def";
// String program = "/pythag { dup mul exch dup mul add sqrt } def 3.0 4.0 pythag";
ArrayList<Token> tokens = tokenizePostScriptProgram(program);
HW06_Stack stack = new HW06_Stack();
HashMap<String, Token> map = new HashMap<>();
interpretListOfTokens(tokens, stack, map);
}
}