Homework 2

Due Date: Thursday January 23, 9pm.

Purpose: To write simple functions; design data; design World Programs

Expectations

• This will be an individual (non-pair) assignment.

• You must submit a single .rkt file containing your responses to all exercises via the Handin Server. We accept no email submissions.

• You must use the language specified at the top of this page.

• Your code must conform to the guidelines outlined in the style guide on the course website. The style guide will be updated as the semester progresses, so revisit it before submitting each assignment.

• Unless otherwise stated, for all programming problems you must provide (i) a signature, (ii) a purpose statement, (iii) check-expects, and (iv) the actual code, in the language specified at the top of this page.

Failure to comply with these expectations will result in deductions and possibly a 0 score.

Exercise 1 Design the function subset-interval? that takes four real numbers a,b,c,d interpreted to represent two closed real intervals [a,b] and [c,d], and returns #t exactly when the first is a subset of the second. That is, your function returns a Boolean (as also suggested by the ’?’ in the name). "Subset" means that the first interval is nested inside the second. That is, every element of the first interval is also an element of the second interval. In this case your function should return #t. It should return #f in all other cases.

Note that when a > b (which is a valid input), the interval [a,b] is considered "degenerate" and empty. In contrast, when a = b, the interval is non-empty and contains exactly one number (namely, a). Make sure your check-expects test such degenerate cases, and also boundary conditions, such as when the two intervals have the same left boundary: a = c.

Exercise 2 Design the function sort-three that takes three real numbers and sorts them, starting with the smallest. But there is a problem: how do we return the result, i.e. the sorted sequence of three numbers? We don’t know how to represent sequences in BSL (yet).

Here is a trick: convert the three numbers to strings, append these three strings, with a comma "," between neighbors, and enclose the result in "[...]". The output is the sorted sequence as a string. For example, given 1,2,3, your output should be "[1,2,3]".

Design a helper function 3nums->string that performs the conversion + appending + bracketing (not the sorting). Then call this helper as needed.

Hint: there are 6 permutations of (a,b,c). Maybe it is easiest to just consider these 6 cases, one after the other. To find out how to convert a number to a string, consult the documentation.

Exercise 3 Implication, denoted => , is probably the most frequently mis- understood binary Boolean connective! It is formally defined by the following truth table, which uses 0 in place of #f and 1 in place of #t.

x | y | x => y

--------------

0 | 0 |   1

0 | 1 |   1

1 | 0 |   0

1 | 1 |   1

Design the function => that takes two Booleans and returns the truth value of the implication connective applied to these two Booleans. That is, the return value is a Boolean, too. For this function you are not allowed to use any Boolean connectives built-in to BSL, such as and, or, or not. You are allowed to use if, Boolean constants, and of course the arguments to the function.

Design check-expects that cover all four cases in the mathematical definition of implication given above. Note what this means: if these tests pass, you have demonstrated the correctness of your implementation of => for all possible inputs.

So, by your implementation, is the following statement true or false?

"If Boston is the capital of the moon, there will be two exams in Fundies I."

Exercise 4 The following are some of the Combined Majors currently offered by Khoury and the College of Science towards a BS degree:

CS and Linguistics

CS and Biology

CS and Cognitive Psychology

CS and Mathematics

DS and Biochemistry

DS and Biology

DS and Ecology and Evolutionary Biology

DS and Mathematics

• Give a data definition CombinedMajor that can be used to represent information about the above combined majors. Add an interpretation of your data definition. (That is, follow the first two steps of the data design recipe in this part.)

• Define (in BSL) three examples of a CombinedMajor.

• Design a template for a function that takes in a CombinedMajor. (This completes the four steps of the data design recipe.)

• Design the function cs-or-ds that takes in a CombinedMajor and returns a string "CS" or "DS" indicating whether the combined major belongs to the Computer Science or Data Science part of Khoury programs. Define the function strictly based on the template.

  Now ask yourself whether, given your data design for combined majors, this function can be simplified. If so, give a simplified definition, cs-or-ds-v2. Good news: since the simplification is user-transparent (i.e., it does not change the input/output behavior of the function), the signature, purpose statement, and check-expects can stay the same (except for the name of the function)!

• Design the function alternative that takes in a CombinedMajor and returns another combined major that combines a Khoury program (CS or DS) with the same non-Khoury program, if such an alternative exists. For instance, given "CS and Mathematics", your function should return "DS and Mathematics" (as a possible alternative).

  What if no alternative exists? According to the signature we must return a CombinedMajor. Hence we cannot return a custom string, such as "No alternative!": this would violate the signature. The solution is to use BSL’s error function and supply an appropriate message. Since this message will be used several times in your code, define a constant. In check-expects, use BSL’s check-error function on inputs where you expect an error.

Exercise 5 Define two natural-number constants, BASE and LIMIT, as well as a constant SCENE in which to display image output produced in this exercise.

Now define the function powers-of-base that takes a natural number i as input and launches a World Program, using big-bang, that displays increasing powers of BASE, as follows. The first value to be displayed is BASEi. Upon each key-press event, your World should display the next power of BASE, i.e., the value obtained by raising BASE to the power of an exponent that is increased by 1. Your World should stop when the current number to be displayed exceeds LIMIT. At this point, display: "Value exceeds LIMIT !", where "LIMIT" is replaced by the value of LIMIT.

For example, given constants BASE=2 and LIMIT=100000 and input i=3, your function should initially display 23=8. Upon a key pressed, it displays 24=16, upon the next key: 25=32, then 26=64, and so forth. Stop when the term exceeds 100000.

Use the expt function to compute the initial World state, i.e. BASEi. Do not use the expt function in other places of this World program: it is expensive and unnecessary. Think about a good way of representing your World state, one that does not require you to call expt every time there is a change.

For the purposes of this program, we define 00 := 1.