Out: Monday, March 14, 2016
Due: Monday, March 21, 2016 at 5pm local time.
Corrected: Wednesday, March 16
(examples for least-argument-yielding
)
Corrected: Thursday, March 17
(added WHERE clause for least-argument-yielding
)
The goal of this problem set is to give you practice using most of what you've learned this semester.
Some of these problems may not be easy, so start early and leave yourself plenty of time to finish them.
You must use DrScheme's HtDP Intermediate Student Language with
Lambda. Use higher order functions such as
filter
and map
whenever
they are helpful. As before, you will be penalized for failing to
use these when they are "obviously" applicable.
Remember that you must follow the design recipe, and write invariants (as WHERE clauses) whenever an argument represents context information. We expect that your data definitions, interpretations, and invariants will be sufficient to explain the meaning of every quantity in your program. You will be judged on the adequacy of these deliverables.
For each function that you write using general recursion, you must deliver:
The example files contain numerous examples of the first three of these deliverables.
You will be judged on the correctness of your halting measures and termination arguments.
If you really need to do so, it is ok to write two mutually-recursive functions using general recursion. If you do this, you need make sure that your halting measure decreases on EVERY recursive call to the function, even if that call comes via the other function.
As before, if your function does not fulfill its purpose for all combinations of arguments that satisfy the contract, then you must write an invariant that documents what additional assumptions your function makes about its arguments.
Not everything on this problem set requires the use of invariants or the use of general recursion. Part of your task is to figure out when you need these things and when you do not. Remember, it is the purpose statement that determines whether or not you need to state an invariant.
Remember that you must follow the design recipe. Your deliverables include the data definitions (including interpretation and templates), contract and purpose header, strategies, code, and tests. Be sure to sync your work and fill out a Work Session Report at the end of every work session. Use the Work Session Report for PS08
As usual, the rubric for grading is here.
The first problem refers to the Fibonacci sequence f_{0}, f_{1}, f_{2}, ... defined by
The second and third problems refer to symbols, which are just Racket symbols. You have already read about them in Part IV of the textbook.
search.rkt
that provides the following four functions:
;;; fib : NonNegInt -> NonNegInt ;;; GIVEN: i ;;; RETURNS: the Fibonacci number f_{i} (defined above) ;;; EXAMPLES: ;;; (fib 0) => 0 ;;; (fib 10) => 55 ;;; ;;; next-fibonacci-number : Integer -> NonNegInt ;;; GIVEN: any integer n ;;; RETURNS: the smallest Fibonacci number greater than or equal to n ;;; EXAMPLES: ;;; (next-fibonacci-number -226) => 0 ;;; (next-fibonacci-number 50) => 55 ;;; ;;; least-result-as-large-as : (NonNegInt -> Integer) Integer -> Integer ;;; GIVEN: a function f and an integer n ;;; WHERE: f is monotonic ;;; RETURNS: the smallest value of (f i) such that ;;; i is a non-negative integer and (f i) is greater than or equal to n ;;; EXAMPLES: ;;; (least-result-as-large-as fib -226) => 0 ;;; (least-result-as-large-as fib 50) => 55 ;;; (least-result-as-large-as sqr 100) => 100 ;;; (least-result-as-large-as sqr 500) => 529 ;;; ;;; least-argument-yielding : (NonNegInt -> Integer) Integer -> Integer ;;; GIVEN: a function f and an integer n ;;; WHERE: there exists some non-negative integer k such that (f k) ;;; is greater than or equal to n ;;; RETURNS: the smallest value of i such that ;;; i is a non-negative integer and (f i) is greater than or equal to n ;;; EXAMPLES: ;;; (least-argument-yielding fib -226) => 0 ;;; (least-argument-yielding fib 50) => 10 ;;; (least-argument-yielding sqr 100) => 10 ;;; (least-argument-yielding sqr 500) => 23 ;;; (least-argument-yielding (lambda (i) (- (sqr i) (* 20 i))) 100) => 25
Be sure to spell the names of your functions correctly, both in their definitions and in your list of provided functions.
freevars.rkt
that provides functions to compute the free and bound variables
of programs written in a simple programming language.
That language's syntax is defined as follows:
;;; An Expr is one of ;;; -- Integer ;;; -- Symbol ;;; -- Call ;;; ;;; Interpretation: an Expr represents an integer, an identifier, ;;; or a function call. ;;; ;;; A Call is ;;; (cons Expr ListOfExpr) ;;; ;;; Interpretation: a Call represents a function call in which ;;; the value of the first expression in the Call must be a function, ;;; which is called on the values of the expressions in the ListOfExpr. ;;; ;;; A Defn is ;;; (list 'def (cons Symbol ListOfSymbol) Expr) ;;; ;;; Interpretation: a Defn represents a function. ;;; The lone Symbol is the name of the function, and the symbols ;;; in the ListOfSymbol are the names of its arguments. The Expr ;;; represents the value to be returned by the function. ;;; (Note that functions with no arguments can be defined.) ;;; ;;; A Program is ;;; (cons Defn ListOfDefn) ;;; Interpretation: a program is a non-empty list of definitions. ;;; When the program is run, the function defined by the first ;;; definition will be called with arguments obtained in some ;;; OS-dependent manner we needn't discuss here. ;;; ;;; A ListOfSymbol is ;;; -- empty ;;; -- (cons Symbol ListOfSymbol) ;;; ;;; A ListOfExpr is ;;; -- empty ;;; -- (cons Expr ListOfExpr) ;;; ;;; A ListOfDefn is ;;; -- empty ;;; -- (cons Defn ListOfDefn)
A SetOfSymbol
is a ListOfSymbol
in which no symbol appears more than once.
The set of free variables of an Expr
E
is the set of symbols that occur within E.
Formally:
(cons E_{0}
(list E_{1} ...
E_{n}))
,
then its set of free variables is the union of the sets
of free variables for
E_{0},
E_{1}, ... E_{n}.
The set of bound variables of a Defn
of the form
(list 'def (cons I_{0} (list I_{1} ... I_{n})) E)is the set {I_{0}, I_{1}, ... I_{n}}. The set of free variables of that definition is the set difference between the set of free variables of E and the definition's set of bound variables.
A program's set of free variables is the set difference between the union of the sets of free variables of its definitions and the set of function names defined by those definitions. A program's set of bound variables is the union of the sets of bound variables of its definitions.
Your freevars.rkt
file must provide
the following nine functions:
;;; expr-free : Expr -> SetOfSymbol ;;; defn-free : Defn -> SetOfSymbol ;;; program-free : Program -> SetOfSymbol ;;; GIVEN: (respectively) an expression, definition, or program ;;; RETURNS: the set of free variables ;;; of that expression, definition, or program ;;; EXAMPLES: see below ;;; ;;; expr-bound : Expr -> SetOfSymbol ;;; defn-bound : Defn -> SetOfSymbol ;;; program-bound : Program -> SetOfSymbol ;;; GIVEN: (respectively) an expression, definition, or program ;;; RETURNS: the set of bound variables ;;; of that expression, definition, or program ;;; EXAMPLES: see below ;;; ;;; expr-undefined : Expr SetOfSymbol -> SetOfSymbol ;;; defn-undefined : Defn SetOfSymbol -> SetOfSymbol ;;; program-undefined : Program SetOfSymbol -> SetOfSymbol ;;; GIVEN: (respectively) an expression, definition, or program ;;; and a set of symbols representing the set of identifiers ;;; that are defined by the expression's, definition's, or ;;; program's context ;;; RETURNS: the set of free variables of that expression, definition, ;;; or program minus the set of identifiers defined by its context ;;; EXAMPLES: see below (define expr1 '(+ x y 3)) (define expr2 (list '* expr1 expr1 'z)) (define defn1 (list 'def '(f x y) expr2)) (define defn2 '(def (g a z) (f z a))) (define pgm1 (list defn1 defn2)) (expr-free expr1) ; => { +, x, y } (expr-free expr2) ; => { *, +, x, y, z } (defn-free defn1) ; => { *, +, z } (defn-free defn2) ; => { f } (program-free pgm1) ; => { *, +, z } (expr-bound expr1) ; => { } (expr-bound expr2) ; => { } (defn-bound defn1) ; => { f, x, y } (defn-bound defn2) ; => { g, a, z } (program-bound pgm1) ; => { a, f, g, x, y, z } (expr-undefined expr1 '(+ - * f g x y)) ; => { } (expr-undefined expr2 '(+ - * f g x y)) ; => { z } (defn-undefined defn1 '(+ - * f g)) ; => { z } (defn-undefined defn2 '(+ - * f g)) ; => { } (program-undefined pgm1 '(+ - * f g)) ; => { z }
pretty.rkt
that defines a pretty-printer for the programming language defined
in the previous problem.
More precisely, you are to provide the following function:
;;; program-to-strings : Program PosInt -> ListOfString ;;; GIVEN: a program and a width ;;; RETURNS: a representation of the program as a sequence of lines, ;;; following the formatting rules described below
In the formatting rules below, a program fragment fits on a line if and only if a string that starts with the proper indentation for that program fragment and contains that program fragment is no longer than the given width.
(def (
I_{0}
I_{1} ...
I_{n})
E)
is formatted by formatting the
"(def (
I_{0}
I_{1} ...
I_{n})
"
part as described below, followed by E
starting on a new line with an additional two spaces of
indentation.
(def (
I_{0}
I_{1} ...
I_{n})
"
part of a definition is formatted on a single line if
it will fit on a line no longer than the given width,
with no indentation.
(def (
I_{0}
I_{1}"
part will fit on a single line (with no indentation),
and all of the
remaining arguments will fit if placed on separate
lines and indented so they line up under the first
argument, and the parenthesis that closes the list
of arguments will also fit on the line containing
the last argument, then the function header is
formatted that way.
(def (
I_{0}"
part is formatted on a single line (with no indentation),
and every one
of the remaining arguments is placed on a separate
line, indented to line up under I_{0},
with the parenthesis that closes the list of arguments
on the same line as the last argument.
(
E_{0}
E_{1} ...
E_{n})
will not fit within a single line when indented, but the
"(
E_{0}
E_{1}"
part will fit, then that much of the call is placed
on a single line and each of the remaining argument
expressions begins on a separate line, indented to
line up under E_{1}, and the
closing parenthesis is placed on the same line as
the last argument expression.
(
E_{0}
E_{1}"
part of a call will not fit within a single line when indented,
but the "(
E_{0}" part does,
then that much of the call expression gets a line all to itself,
and each of the argument expressions begins on a separate line,
indented to line up under E_{0}.
(
E_{0}"
part of a call will not fit within a single line when indented,
then E_{0} is formatted with one extra
space of indentation using as many lines as necessary,
the space immediately preceding the start of
E_{0} is replaced by the opening
parenthesis of the call, and each of the argument expressions
begins on a separate line, indented to line up under
E_{0}.
To help you debug your program, we have provided in extras.rkt the function:
;;; display-strings! : ListOfString -> Void ;;; GIVEN: a list of strings ;;; EFFECT: displays the strings on separate lines ;;; RETURNS: no value
Be sure to download a fresh copy of
extras.rkt containing this function.
Here is a sample interaction, using pgm1
as defined
in the previous problem statement:
> (display-strings! (program-to-strings pgm1 30)) (def (f x y) (* (+ x y 3) (+ x y 3) z)) (def (g a z) (f z a)) > (display-strings! (program-to-strings pgm1 25)) (def (f x y) (* (+ x y 3) (+ x y 3) z)) (def (g a z) (f z a))
Here is an example in which one line exceeds the given width:
> (display-strings! (program-to-strings pgm2 30)) (def (%vector-map1! f target vec len) (loop f target vec len)) (def (loop f target vec i) (if (zero? i) target (let ((j (- i 1))) (vector-set! target j (f (vector-ref vec j))) (loop f target vec j))))
Here are some hints on this problem.
display-strings!
is to help you to debug
your program, but we will be testing the lists of
strings produced by program-to-strings
.number->string
and
symbol->string
functions
convert numbers and symbols to strings.Last modified: Wed Mar 16 2016