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 myletexpression. 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 #f). 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, HW7, 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.