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!
Copyright By PowCoder代写 加微信 powcoder
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
● (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.
Writing Comments
For this assignment, we require that you write comments in the style outlined below. It follows “How to design programs”, a textbook by the developers of DrScheme/DrRacket. There are 4 required sections: Contract, Purpose, Example, and Definition, as in the example comment for function area-of-ring:
;; Contract: area-of-ring : number * number -> number ;; Purpose: to compute the area of a ring whose radius is ;; outer and whose hole has a radius of inner
;; Example: (area-of-ring 5 3) should produce 50.24
;; Definition:
(define (area-of-ring outer inner)
(- (area-of-disk outer) (area-of-disk inner)))
The goal of designing a function is to create a mechanism that consumes and produces data. Therefore, every function has a meaningful name and a statement of what kind of information it consumes and
produces. This is called a CONTRACT and is, essentially, an unchecked type signature of the function. The contract for area-of-ring is:
;; Contract: area-of-ring : number * number -> number
Semicolons indicate that the line is a Scheme comment. The contract consists of two parts. The first, to the left of the colon, states the function’s name. The second, to the right of the colon, specifies what kind of data the function consumes and what it produces; the inputs are separated from the output by an arrow.
In addition, every function has a short PURPOSE statement, that briefly describes what the function computes. For most functions, one or two lines will suffice. The purpose statement for our running example area-of-ring is:
;; Purpose: to compute the area of a ring whose radius is ;; outer and whose hole has a radius of inner
The EXAMPLE section shows a call and the expected return result, and the DEFINITION section contains the actual Scheme code for the funtion:
;; Example: (area-of-ring 5 3) should produce 50.24 ;; Definition:
(define (area-of-ring outer inner)
(- (area-of-disk outer) (area-of-disk inner)))
Additional Examples
Function map (a higher-order polymorphic function):
;; Contract: map : (a -> b) * (list a) -> (list b)
;; Purpose: to apply function f on each element of list l ;; Example: (map abs ‘(-1 2 -3)) should produce (1 2 3) ;; Definition:
(define (map f l)
(if (null? l) ‘() (cons (f (car l)) (map f (cdr l)))))
The above contract states that map consumes 2 arguments: the first argument is a function that takes a value of type a and returns a value of type b, and the second argument is a list whose elements are of type a. Function map returns a list whose elements are of type b. Here a and b to denote type variables that can be instantiated to arbitrary concrete types. Note however that a and b link the arguments and return type of map: function f takes a type a, and therefore the list l must consists of elements of type a, as f is applied on each element of l; furthermore, the return value must be a list with elements of type b.
Function foldl (another higher-order polymorphic function):
;; Contract: foldl : (b * a -> b) * (list a) * b -> b
;; Purpose: to fold (i.e., reduce) the list l into a single value ;; Example: (foldl + ‘(1 2 3) 0) should produce 6
;; Definition:
(define (foldl op l id)
(if (null? l) id (foldl op (cdr l) (op id (car l)))))
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com