Submission
Instructions
This is an individual assignment! Discussion with friends,
TAs, and instructors is allowed, however, the actual work should be your own.
Course staff runs plagiarism detectors, and will treat
excessive similarities between submissions as evidence of cheating. Submit in Submitty. Your Scheme file should be named yabi.rkt. Submitty runs a command-line r5rs interpreter.
Make sure that you change the language in DrRacket to
R5RS!
Yet Another Boolean Interpreter
We've written Boolean expression
interpreters in Java and Prolog, and it's time to write one in Scheme! The goal
of this problem is to write an interpreter for a simple functional language
called BOOL. A BOOL program is a list, as defined by the following grammar; all
terminals are shown in boldface.
program →
(
prog expr )
expr → id
expr → const
expr → ( myignore expr )
expr → ( myor expr expr )
expr → ( myand expr expr )
expr → ( mynot expr )
expr → ( mylet id expr expr )
id → a | b | ... |
z
const → true | false
Here are five valid BOOL programs
- (prog true)
- (prog (myor
(myand true (myignore
(myor true false))) (myand
true false)))
- (prog (mylet
z (myor false true) (myand
z true)))
- (prog (mylet
a true (myor (mylet b
(myand true false) (myor
false b)) (myand false a))))
- (prog (mylet
x true (myor (mylet x
(myand true false) (myand
true x)) (myand true x))))
Each BOOL program and expression
evaluates to a boolean value. The semantics of a
program is defined as follows:
- The
entire program ( prog expr ) evaluates to whatever expr
evaluates to.
- ( myignore expr
) evalutes to the boolean value #f,
regardless of what the subexpression expr looks like.
- ( myand expr
expr ) evaluates to the logical conjunction of whatever values the two
subexpressions evaluate to.
- ( myor expr
expr ) evaluates to the logical disjunction of whatever values the two
subexpressions evaluate to.
- ( mynot expr
) evaluates to the negation of X, where X is the boolean value that the subexpression evaluates to.
- ( mylet id
expr1 expr2 ) has the following semantics.
First, subexpression expr1 is evaluated. The resulting boolean value is "bound" to the identifier id.
Then the second subexpression, expr2 is evaluated. The result of
that evaluation serves as the value of the entire mylet expression. The binding between
the id and the boolean value is active only
while expr2 is being evaluated!
- id evaluates to the value that the identifier is bound to by a
surrounding mylet expression. If there are multiple bindings for the identifier, the
last (i.e., latest) such binding is used.
- const true evaluates to Scheme's #t
and const false evaluates to #f.
Based on these rules, the five
programs from above are evaluated as follows:
- Program
1 evaluates to #t
- Program
2 evaluates to #f
- Program
3 evaluates to #t
- Program
4 evaluates to #f
- Program
5 evaluates to #t
Write a Scheme function myinterpreter that takes as input a list of BOOL
programs and produces a list of the corresponding boolean
values. For example, an invocation
( myinterpreter '( (prog false) (prog (mylet z (myor true false) (myand z true))) ) )
should evaluate to the list (#f #t). Your implementation should work with the R5RS Language in DrRacket.
- You
are guaranteed that the list given to the interpreter will not be empty, and will contain only valid BOOL programs. Also,
you may assume that any evaluation of an identifier has at least one
existing binding for that identifier.
- Useful
library functions for your implementation are symbol? and booolean?. The first checks if the argument
is a symbol such as a, true, etc. The second checks if the argument is a boolean
value.
- In
order to maintain the set of bindings, consider using a list where each
element of the list is one specific binding. A binding is really just a
pair of an identifier and a boolean value.
- The
only built-in Scheme functions you are allowed to use are equal?, car, cdr, cons, cond, if, or, and, not, null?, symbol?, and boolean?.
You should not use any other built-in function.
- You
must comment your code! You are requried to
write comments in the style described here.
Minimal starter code is provided here.
NOTE
on grading: This homework
is worth a total of 40 points. (Scheme Part 2 is worth 60 points.) 30 points
will be awarded for functional correctness by the autograder.
However, we will override the autograder if you have
violated the restrictions on functions! 10 points will be awarded for the
quality and completeness of your comments.
Errata
None yet. Check the Announcements page
regularly.