CSCI 4430 Programming Languages
Homework 4: Scheme Part 1
Due: Friday October 23 @ 1:59pm 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.