CS 5010: Problem Set 05
Out: Monday, 9 October 2017
Due: Monday, 16 October 2017 at 6pm local time
This is an individual assignment. You are not allowed to discuss this problem set with any other person. You are also not allowed to search for or to view any solutions to similar problems that may be available on the WorldWide Web or in other resources that might otherwise have been available to you.
The main purpose of this problem set is to give you practice designing functions that deal with trees.
You must use Racket's Intermediate Student Language (ISL) for this problem set.
For these problems, download a copy of
extras.rkt
and put it in the directory with your solutions.
Then import rackunit
and this library
by including the lines
(require rackunit) (require "extras.rkt")
at the top of your file. Then, for each problem, put in lines that say
(provide function)
for each deliverable function, as you have done on previous
problem sets.
This will allow our testing framework to import your file
and do automated testing on it.
You can use checklocation
to doublecheck
that your solutions are in the right place.
Remember that you must follow the design recipe, which is a process, not a list of deliverables. Your deliverables include the artifacts produced by the various steps of the design recipe: data definitions (including interpretation and templates, contracts, purpose statements, definitions, and tests). Be sure to follow our coding conventions. Doing so will make codewalks easier for everyone.
Be sure to fill out a
work session report
at the end of each work session.
Tell git
to add it to the files you will commit,
and then commit and push (sync) that report in addition to
committing and pushing your entire set05
directory.
Do this at the end of every work session.
Remember to include a copy of extras.rkt
racket
in your set05
directory along with your
q1.rkt
and q2.rkt
files.
For both parts, you should require rackunit
and
"extras.rkt"
but nothing else.

(Arithmetic Expressions)
For this first part of Problem Set 05, you will design data types that make it possible to represent arithmetic expressions such as
x+(3*y)
. This first part of the problem set consists of nothing but routine data definitions and a few simple functions for creating and observing values of the data types you define. The functions you are asked to define should not have to do any nontrivial computations.The specific data types you must design and implement are:

A
Literal
represents a real number. 
A
Variable
represents a name whose meaning will depend upon the context in which it appears. 
An
Operation
represents an arithmetic operation such as addition or division. 
A
Call
represents a function call. 
A
Block
represents a variable definition and an expression within which that variable may be used. 
An
ArithmeticExpression
is one of the following: 
Literal

Variable

Operation

Call

Block
You are to deliver a file named
q1.rkt
that defines all of the data types named above and also defines and provides all 18 of the functions specified below.We are giving you two data definitions, for the itemization types
OperationName
andArithmeticExpression
. You should copy these data definitions into yourq1.rkt
file without changing them:;;; An OperationName is represented as one of the following strings: ;;;  "+" (indicating addition) ;;;  "" (indicating subtraction) ;;;  "*" (indicating multiplication) ;;;  "/" (indicating division) ;;; ;;; OBSERVER TEMPLATE: ;;; operationnamefn : OperationName > ?? #; (define (operationnamefn op) (cond ((string=? op "+") ...) ((string=? op "") ...) ((string=? op "*") ...) ((string=? op "/") ...))) ;;; An ArithmeticExpression is one of ;;;  a Literal ;;;  a Variable ;;;  an Operation ;;;  a Call ;;;  a Block ;;; ;;; OBSERVER TEMPLATE: ;;; arithmeticexpressionfn : ArithmeticExpression > ?? #; (define (arithmeticexpressionfn exp) (cond ((literal? exp) ...) ((variable? exp) ...) ((operation? exp) ...) ((call? exp) ...) ((block? exp) ...)))
The 18 functions you must define and
provide
are specified as follows:;;; lit : Real > Literal ;;; GIVEN: a real number ;;; RETURNS: a literal that represents that number ;;; EXAMPLE: (see the example given for literalvalue, ;;; which shows the desired combined behavior ;;; of lit and literalvalue) ;;; literalvalue : Literal > Real ;;; GIVEN: a literal ;;; RETURNS: the number it represents ;;; EXAMPLE: (literalvalue (lit 17.4)) => 17.4 ;;; var : String > Variable ;;; GIVEN: a string ;;; WHERE: the string begins with a letter and contains ;;; nothing but letters and digits ;;; RETURNS: a variable whose name is the given string ;;; EXAMPLE: (see the example given for variablename, ;;; which shows the desired combined behavior ;;; of var and variablename) ;;; variablename : Variable > String ;;; GIVEN: a variable ;;; RETURNS: the name of that variable ;;; EXAMPLE: (variablename (var "x15")) => "x15" ;;; op : OperationName > Operation ;;; GIVEN: the name of an operation ;;; RETURNS: the operation with that name ;;; EXAMPLES: (see the examples given for operationname, ;;; which show the desired combined behavior ;;; of op and operationname) ;;; operationname : Operation > OperationName ;;; GIVEN: an operation ;;; RETURNS: the name of that operation ;;; EXAMPLES: ;;; (operationname (op "+")) => "+" ;;; (operationname (op "/")) => "/" ;;; call : ArithmeticExpression ArithmeticExpressionList > Call ;;; GIVEN: an operator expression and a list of operand expressions ;;; RETURNS: a call expression whose operator and operands are as ;;; given ;;; EXAMPLES: (see the examples given for calloperator and ;;; calloperands, which show the desired combined ;;; behavior of call and those functions) ;;; calloperator : Call > ArithmeticExpression ;;; GIVEN: a call ;;; RETURNS: the operator expression of that call ;;; EXAMPLE: ;;; (calloperator (call (op "") ;;; (list (lit 7) (lit 2.5)))) ;;; => (op "") ;;; calloperands : Call > ArithmeticExpressionList ;;; GIVEN: a call ;;; RETURNS: the operand expressions of that call ;;; EXAMPLE: ;;; (calloperands (call (op "") ;;; (list (lit 7) (lit 2.5)))) ;;; => (list (lit 7) (lit 2.5)) ;;; block : Variable ArithmeticExpression ArithmeticExpression ;;; > ArithmeticExpression ;;; GIVEN: a variable, an expression e0, and an expression e1 ;;; RETURNS: a block that defines the variable's value as the ;;; value of e0; the block's value will be the value of e1 ;;; EXAMPLES: (see the examples given for blockvar, blockrhs, ;;; and blockbody, which show the desired combined ;;; behavior of block and those functions) ;;; blockvar : Block > Variable ;;; GIVEN: a block ;;; RETURNS: the variable defined by that block ;;; EXAMPLE: ;;; (blockvar (block (var "x5") ;;; (lit 5) ;;; (call (op "*") ;;; (list (var "x6") (var "x7"))))) ;;; => (var "x5") ;;; blockrhs : Block > ArithmeticExpression ;;; GIVEN: a block ;;; RETURNS: the expression whose value will become the value of ;;; the variable defined by that block ;;; EXAMPLE: ;;; (blockrhs (block (var "x5") ;;; (lit 5) ;;; (call (op "*") ;;; (list (var "x6") (var "x7"))))) ;;; => (lit 5) ;;; blockbody : Block > ArithmeticExpression ;;; GIVEN: a block ;;; RETURNS: the expression whose value will become the value of ;;; the block expression ;;; EXAMPLE: ;;; (blockbody (block (var "x5") ;;; (lit 5) ;;; (call (op "*") ;;; (list (var "x6") (var "x7"))))) ;;; => (call (op "*") (list (var "x6") (var "x7"))) ;;; literal? : ArithmeticExpression > Boolean ;;; variable? : ArithmeticExpression > Boolean ;;; operation? : ArithmeticExpression > Boolean ;;; call? : ArithmeticExpression > Boolean ;;; block? : ArithmeticExpression > Boolean ;;; GIVEN: an arithmetic expression ;;; RETURNS: true if and only the expression is (respectively) ;;; a literal, variable, operation, call, or block ;;; EXAMPLES: ;;; (variable? (blockbody (block (var "y") (lit 3) (var "z")))) ;;; => true ;;; (variable? (blockrhs (block (var "y") (lit 3) (var "z")))) ;;; => false
We will be doing automated testing of your solution, so be sure your solution is in the right place (
set05/q1.rkt
in your privatecs5010f17/pdpYOURUSERNAME
repository), and that it provides all the functions listed above. To see if your file is in the right place, insert the following line at the top of your file but after yourrequire
declarations:(checklocation "05" "q1.rkt")

A

(Constant Expressions)
For this second problem, your job is to define several functions that classify and extract information from arithmetic expressions.
We'll need the following definitions:

An operation expression is an arithmetic expression
that is either

an
Operation

or a
Block
whose body is an operation expression.

an

A constant expression is an arithmetic expression
that is either

a
Literal
, 
a
Call
whose operator is an operation expression and whose operands are all constant expressions, 
or a
Block
whose body is a constant expression.

a
You are to deliver a file named
q2.rkt
that defines all of the data types and functions defined in part 1 above, and also defines and provides the 4 functions specified below:;;; variablesdefinedby : ArithmeticExpression > StringList ;;; GIVEN: an arithmetic expression ;;; RETURNS: a list of the names of all variables defined by ;;; all blocks that occur within the expression, without ;;; repetitions, in any order ;;; EXAMPLE: ;;; (variablesdefinedby ;;; (block (var "x") ;;; (var "y") ;;; (call (block (var "z") ;;; (var "x") ;;; (op "+")) ;;; (list (block (var "x") ;;; (lit 5) ;;; (var "x")) ;;; (var "x"))))) ;;; => (list "x" "z") or (list "z" "x") ;;; variablesusedby : ArithmeticExpression > StringList ;;; GIVEN: an arithmetic expression ;;; RETURNS: a list of the names of all variables used in ;;; the expression, including variables used in a block ;;; on the right hand side of its definition or in its body, ;;; but not including variables defined by a block unless ;;; they are also used ;;; EXAMPLE: ;;; (variablesusedby ;;; (block (var "x") ;;; (var "y") ;;; (call (block (var "z") ;;; (var "x") ;;; (op "+")) ;;; (list (block (var "x") ;;; (lit 5) ;;; (var "x")) ;;; (var "x"))))) ;;; => (list "x" "y") or (list "y" "x") ;;; constantexpression? : ArithmeticExpression > Boolean ;;; GIVEN: an arithmetic expression ;;; RETURNS: true if and only if the expression is a constant ;;; expression ;;; EXAMPLES: ;;; (constantexpression? ;;; (call (var "f") (list (lit 3) (lit 44)))) ;;; => false ;;; (constantexpression? ;;; (call (op "+") (list (var "x") (lit 44)))) ;;; => false ;;; (constantexpression? ;;; (block (var "x") ;;; (var "y") ;;; (call (block (var "z") ;;; (call (op "*") ;;; (list (var "x") (var "y"))) ;;; (op "+")) ;;; (list (lit 3) ;;; (call (op "*") ;;; (list (lit 4) (lit 5))))))) ;;; => true ;;; constantexpressionvalue : ArithmeticExpression > Real ;;; GIVEN: an arithmetic expression ;;; WHERE: the expression is a constant expression ;;; RETURNS: the numerical value of the expression ;;; EXAMPLES: ;;; (constantexpressionvalue ;;; (call (op "/") (list (lit 15) (lit 3)))) ;;; => 5 ;;; (constantexpressionvalue ;;; (block (var "x") ;;; (var "y") ;;; (call (block (var "z") ;;; (call (op "*") ;;; (list (var "x") (var "y"))) ;;; (op "+")) ;;; (list (lit 3) ;;; (call (op "*") ;;; (list (lit 4) (lit 5))))))) ;;; => 23
Remember that we will be doing automated testing of your solution, so be sure your solution is in the right place (
set05/q2.rkt
in your privatecs5010f17/pdpYOURUSERNAME
repository), and that it provides all of the functions listed above. To see if your file is in the right place, insert the following line at the top of your file but after yourrequire
declarations:(checklocation "05" "q2.rkt")

An operation expression is an arithmetic expression
that is either