Taking and dropping prefix list takewhile and dropwhile

Functional programming in 𝜇Scheme Due Monday, October 5, 2020 at 11:59PM

Contents

This assignment develops new skills that you can use to write one kind of code from scratch: code that inspects and manipulates lists, trees, or other linked data structures. You already know how to manipu-late these structures using machine-level abstractions that operate on one word and one pointer at a time. You will start to develop a flexible, powerful vocabulary of functions that enable you to manipulate a whole list in just one or two operations. These skills come from the discipline of functional program-ming.

The key thing that’s new this week is that no data structure is ever mutated—instead of changing an existing list or tree, code allocates a new list or tree with the desired values and structure. This discipline of programming has benefits for testing, specification, and coding:

In addition to programming, you will get more practice with programming-language theory and proofs. You will see that algebraic laws are built on top of operational semantics, and you will learn that on top of algebraic laws, we can build calculational proofs of program properties. This “cheap and cheerful”way of assuring program correctness is another benefit of functional programming.

This week’s assignment is based primarily on material from sections 2.1 to 2.4 of Programming Lan-guages: Build, Prove, and Compare. You will also need to know the syntax in figure 2.2 (page 95), and the initial basis (also in section 2.2). The initial basis is summarized in table 2.3 on page 99—that table is your lifeline. Finally, although it is not necessary, you may find some problems easier to solve if you read ahead from section 2.7 to section 2.9.

1

2

-> (append '(a b c) '(1 2 3))

-> (set &trace 500)

• Each helper function has a meaningful name2.

• Each helper function is given an explicit contract—or, as described in the general coding rubric3, we can infer the contract by looking at the names of the function and its formal parameters.

3

without any error messages or unit-test failures. If your file produces error messages, we won’t test your solution and you will earn No Credit for functional correctness. (You can still earn credit for structure and organization). If your file includes failing unit tests, you might possibly get some credit for functional correctness, but we cannot guarantee it.

These problems will help guide you through the reading. Complete them before starting the other prob-lems below. You can download the questions5.

1. Read Sections 2.1 and 2.2 (the first part of the second lesson) in Seven Lessons in Program De- sign6.

(c) How many cases must you consider?

(d) To tell the cases apart, what condition or conditions will you use in if expressions? (List one fewer condition than cases.)

(= 'a 'b)

Write your answers as S-expression literals, like '(a b c), #t, or 17.

4. In Programming Languages: Build, Prove, and Compare, review the first few pages of sec-tion 2.3, through the end of section 2.3.2, and also section 2.3.6, which starts on page 106. Which of the following expressions evaluates to #t for every list of ordinary S-expressions xs?

(= (reverse (reverse xs)) xs)

(d) If no matter what expression is substituted for x and what list of expressions is substituted for xs, the two sides are equal.

You are now prepared to understand what is being proved in Exercise A.

(if p (if p x y) z) = ...

You are now prepared for the algebraic laws in exercises A and C.

(a) What does the let expression in the following program evaluate to?

7../design/lessons.pdf

Your answer:
(c) What does the let expression in the following program evaluate to?

You are now mostly ready for exercise E.

Programming and Proof Problems (90 percent)

Related Reading:
• The proof technique is described in section 2.5.7, which starts on page 116.

• Section 2.3.1, which starts on page 100, develops append, and it states two laws that you should use in your proof:

• The laws in the book are interrupted by explanations. We have condensed the basic laws of

design is to justify algebraic laws. In this problem, you use the operational semantics of 𝜇Scheme—which and xs are variables and are defined in 𝜌 (rho), use the operational semantics to prove that

Our expectations for your code: Algebraic laws and unit tests

For each function you define, you must specify not only a contract but also algebraic laws and unit tests. Even helper functions! For some problems, algebraic laws are not needed or are already given to you. Those problems are noted below.

7

• The left-hand sides break the inputs down by cases. In each case, each argument is a variable or is a form of data such as (cons y ys). A good left-hand side never has a call to a non-primitive function like list2 or append.

• No algebraic law is completely redundant. That is, no law is fully implied by a combination of other laws. (It is OK if some inputs are covered by more than one law, which we call “overlapping.”Overlapping laws are handy, but you must be sure that on the overlapping inputs, all laws agree on the result.)

• If, given a particular input, the function’s contract says that a value is returned, there must be some algebraic law that specifies what the value is.

It is always possible to structure your code so it has one case per law. But it is acceptable to take shortcuts with things like short-circuit && and ||. It is also acceptable, if unusual, to use if on the right-hand side of an algebraic law, in which case that law would cover two cases in the code.

• The names of formal parameters are consistent with the names used in algebraic laws. If there is no case analysis on a parameter, its name is the same everywhere it appears. If there is case analysis, a parameter’s name is different from the names of its parts. Example: parameter xs might take the form (cons y ys).

• If the function returns a Boolean, then when possible, each algebraic law is tested twice: once with a true result and once with a false result. (Such testing is not always possible; for example,

8

1. Recursive function on lists of values. Do part (a) of exercise 1 on page 180 of Build, Prove, and Compare (contig-sublist?).

The algebraic laws for contig-sublist? may be too challenging for beginners, so you may omit them. But do write laws for all other functions, including helper functions. And each function you define, including contig-sublist? and any helper functions, must be accompanied by unit tests written using check-expect or check-assert.

Related reading:

• Ordinary S-expressions are defined in in Figure 2.1 on page 93.

9

• Once you extend a contract, you can profitably break SEXP down by three cases: empty list, cons, and atom different from empty list.

C. Zip and unzip. Function zip converts a pair of lists to a list of pairs by associating corresponding values in the two lists. (If zip is given lists of unequal length, its behavior is not specified.) Function unzip converts a list of pairs to a pair of lists. In both functions, a “pair” is represented by a list of length two, e.g., a list formed using predefined function list2.

-> (zip '(1 2 3) '(a b c))

-> (zip '(11 11 15) '(Guyer Sheldon Korman))

((11 Guyer) (11 Sheldon) (15 Korman))

Implement zip and unzip.

Each function you define, including helper functions, must be accompanied by algebraic laws and by unit tests written using check-expect or check-assert, with this exception:

10

A nonempty list of 𝐴’s is notated LIST1(A).10The usual forms of data don’t work here: '() is not a

-> (define square (a) (* a a))

-> (arg-max square '(5 4 3 2 1))

Each function you define, including helper functions, must be accompanied by algebraic laws and by unit tests written using check-expect or check-assert.

Avoid this common mistake: It’s all too easy to return the result of applying f. But that’s not what’s in E. Rightmost point. Here is a 𝜇Scheme definition that defines a record for a point in the plane, with (record point [x y])

Here are two extra-credit problems about justification of algebraic laws.

10

(append (take n xs) (drop n xs)) == xs

As soon as you have the files listed above, run submit105-scheme to submit a preliminary version of your work. Keep submitting until your work is complete; we grade only the last submission.

13

Code must be well laid out, with attention to vertical space
In addition to following the layout rules in the general coding rubric (80 columns, no offside violations), we expect you to use vertical space wisely.

15

Code must load without errors
Ideally you want to pass all of our correctness tests, but at minimum, your own code must load and pass its own unit tests.

17