CS 135代做、代写C++程序设计、代做Java，Python语言

日期：2020-04-01 10:24

CS 135 Winter 2020

Istead

Assignment: 09

Due: Friday, April 3, 2020 11:59 pm

Language level: Intermediate Student with Lambda

Allowed recursion: No explicit recursion, see below

Files to submit: debug-a09.rkt, hoarding.rkt

Warmup exercises: Without using explicit recursion complete HtDP 9.5.2, 9.5.4, and

write your own versions of member? and append.

Practice exercises: HtDP 21.2.1, 21.2.2, and 21.2.3

For this assignment:

? Make sure you read the OFFICIAL A09 post on Piazza for the answers to frequently

asked questions.

? You may use only the following abstract list functions: build-list, filter, map, foldr,

and foldl.

? You may use any primitive functions, such as mathematical functions, cons, first, second,

third, list, empty, and equal.

? You may use cond.

? You may use lambda.

? You may not use explict recursion for any question. That is, functions that involve an

application of themselves, either directly or via mutual recursion. Use the abstract list

functions instead.

? You may not use any non-primitive list functions, including length, member, reverse,

append, and list-ref.

? You may only define non-local constants and helper functions if they will be used to answer

multiple parts of the same question. Otherwise, constants and helper functions should be

defined locally. Local helper functions do not require purposes, contracts, examples or tests.

? You may use functions defined in earlier parts of a question to help write or test functions

later in the same question.

1. [20% Correctness] Question 1

Consider the code in debug-a09.rkt, which may contain syntax, mathematical, and style

errors. The code may also be difficult to read and/or maintain, lack helper functions and

constants. Correct the code.

CS 135 — Winter 2020 Assignment 09 1

2. [60% Correctness] Question 2

A panic has struck your city. Grocery stores everywhere are under attack. Let’s build some

quick functions to help them out.

define-struct item (name cost taxable count))

;; An Item is a (make-item Str Num Bool Nat)

;; requires: Num >= 0, Str does not equal "", Nat > 0

;; where: Str is the name

;; Num is the price

;; Bool is true if the item is taxable

;; Nat is the quantity to purchase

;; A GroceryList (GL) is a (listof Item)

;; requires: item names are unique

;; A GItem is a (list Str Num Bool Nat)

;; requires: Num >= 0, Str does not equal ""

;; where: Str is the name

;; Num is the price

;; Bool is true if the item is taxable

;; Nat is the count in stock

;; An Inventory is a (listof GItem)

;; requires: item names are unique

Note that the names of items in GroceryList are unique, as are those in an Inventory.

(a) Write a function sum that consumes a GroceryList and computes the total cost of the

items in the list before tax.

(b) Write a function total-bill that consumes a GroceryList and computes the total cost

of the items in the list after tax. The only abstract list functions you may use are map

and foldl.

Note that tax does not apply to all items in the list. The tax rate is given in the starter

file as (define tax 0.13).

(c) Repeat (b), but the only abstract list function you may use is foldr. Call this function

total-bill-alt.

(d) Write a function in-stock? that consumes the name of an item, as a string, and an

Inventory, and produces true if the item is in stock.

Note: an item is in stock if there is at least one of that item in the inventory.

(e) Write a function can-fulfill? that consumes a GroceryList and an Inventory and

produces true if the order can be fulfilled, that is, all items in the grocery list are in stock

in the requested quantities.

Place your solutions in hoarding.rkt.

CS 135 — Winter 2020 Assignment 09 2

Enhancements: Reminder—enhancements are for your interest and are not to be handed in.

Professor Temple does not trust the built-in functions in Racket. In fact, Professor Temple does not

trust constants, either. Here is the grammar for the programs Professor Temple trusts.

hexpi = hvari|( lambda (hvari) hexpi ) | (hexpihexpi)

Although Professor Temple does not trust define, we can use it ourselves as a shorthand for

describing particular expressions constructed using this grammar.

It doesn’t look as if Professor Temple believes in functions with more than one argument, but in

fact Professor Temple is fine with this concept; it’s just expressed in a different way. We can create

a function with two arguments in the above grammar by creating a function which consumes the

first argument and returns a function which, when applied to the second argument, returns the

answer we want (this should be familiar from the make-adder example from class, slide 10-47).

This generalizes to multiple arguments.

But what can Professor Temple do without constants? Quite a lot, actually. To start with, here is

Professor Temple’s definition of zero. It is the function which ignores its argument and returns the

identity function.

(define my-zero (lambda (f) (lambda (x) x)))

Another way of describing this representation of zero is that it is the function which takes a function

f as its argument and returns a function which applies f to its argument zero times. Then “one”

would be the function which takes a function f as its argument and returns a function which applies

f to its argument once.

(define my-one (lambda (f) (lambda (x) (f x))))

Work out the definition of “two”. How might Professor Temple define the function add1? Show that

your definition of add1 applied to the above representation of zero yields one, and applied to one

yields two. Can you give a definition of the function which performs addition on its two arguments

in this representation? What about multiplication?

Now we see that Professor Temple’s representation can handle natural numbers. Can Professor

Temple handle Boolean values? Sure. Here are Professor Temple’s definitions of true and false.

(define my-true (lambda (x) (lambda (y) x)))

(define my-false (lambda (x) (lambda (y) y)))

CS 135 — Winter 2020 Assignment 09 3

Show that the expression ((c a) b), where c is one of the values my-true or my-false defined

above, evaluates to a and b, respectively. Use this idea to define the functions my-and, my-or, and

my-not.

What about my-cons, my-first, and my-rest? We can define the value of my-cons to be the

function which, when applied to my-true, returns the first argument my-cons was called with, and

when applied to the argument my-false, returns the second. Give precise definitions of my-cons,

my-first, and my-rest, and verify that they satisfy the algebraic equations that the regular Scheme

versions do. What should my-empty be?

The function my-sub1 is quite tricky. What we need to do is create the pair (0,0) by using my-cons.

Then we consider the operation on such a pair of taking the “rest” and making it the “first”, and

making the “rest” be the old “rest” plus one (which we know how to do). So the tuple (0,0) becomes

(0,1), then (1,2), and so on. If we repeat this operation n times, we get (n?1,n). We can then

pick out the “first” of this tuple to be n?1. Since our representation of n has something to do with

repeating things n times, this gives us a way of defining my-sub1. Make this more precise, and then

figure out my-zero?.

If we don’t have define, how can we do recursion, which we use in just about every function

involving lists and many involving natural numbers? It is still possible, but this is beyond even the

scope of this challenge; it involves a very ingenious (and difficult to understand) construction called

the Y combinator. You can read more about it at the following URL (PostScript document):

http://www.ccs.neu.edu/home/matthias/BTLS/tls-sample.ps

Be warned that this is truly mindbending.

Professor Temple has been possessed by the spirit of Alonzo Church (1903–1995), who used this

idea to define a model of computation based on the definition of functions and nothing else. This

is called the lambda calculus, and he used it in 1936 to show a function which was definable but

not computable (whether two lambda calculus expressions define the same function). Alan Turing

later gave a simpler proof which we discussed in the enhancement to Assignment 7. The lambda

calculus was the inspiration for LISP, a predecessor of Racket, and is the reason that the teaching

languages retain the keyword lambda for use in defining anonymous functions.

CS 135 — Winter 2020 Assignment 09 4