Administrative

This is another introductory homework, and again it is for individual work and submission. In this homework you will be introduced to the course language (which is based on Typed Racket) and some of the additional extensions in this language.

In this homework (and in all future homework) you should be working in the “Racket language” — in the language selection dialog (Ctrl+L/Command+L) choose the topmost option. In this mode (which is the default for most Racket work), the actual language is determined by an initial #lang line that names the language. In our case, this will be #lang pl for course work, and more specifically, it will be #lang pl 02 for this homework, and similar #lang pl NN for future homework.

You should also click the “Show Details” button at the bottom of the language selection dialog, and check the “Syntactic test suite coverage” option to see parts of your code that are not covered by tests. With this option on, parts of the code that were not covered by tests will be highlighted after you click “run”, and if you have complete coverage, then the colors will stay the same. Note that you can also set the default language that is inserted into new programs to #lang pl (also in the details of the language dialog), to make things more convenient. There are some other variants of the pl language for various purposes — in particular, #lang pl untyped will ignore all type declarations, and will essentially run your code in plain untyped Racket.

The language for this homework is:

This language is basically a restriction of the #lang pl language that we’re using in class. Such languages would be available for future homework too. They will usually be similarly restricted subsets of the course language, but some will be very different (you will be told about it, of course). The server will require the homework-specific language for each submission, so be sure to use it when you’re working on your solution.

Note: One purpose of this is to answer can I use foo questions: as long as you’re using the correct #lang pl NN for homework NN, then “if it’s in the language, you can use it”. (As an example, the language for this homework, #lang pl 02, doesn’t have lambda, and therefore you can’t use it.)

As shown in class, this language has a new special form for tests: test. It can be used to test that an expression is true, that an expression evaluates to some given value, or that an expressions raises an error with some expected text message. For example, the three kinds of tests are used in the following:

Note the second test: when you’re testing predicates, don’t use => #t or => #f since you can just use either the expression or it’s not negation directly. In addition, the last test demonstrates that you don’t need the whole error message, any matching part of it will do (you can also use * as a glob — same as in file names).

In case of an expected error, the string specifies a pattern to match against the error message. (Most text stands for itself, “?” matches a single character and “*” matches any sequence of characters.)

Note that the =error> facility checks only errors that your code throws, not Racket errors. For example, the following test will not succeed:

The server will require all bindings to be present; if you don’t know how to solve a problem, write some bogus definition and indicate this in a clear comment.

Warning: the submission server will be less restrictive this time, and will not complain if you submit buggy code; however, the fact that the language is statically typed will compensate for many bugs. Still, you should use proper tests to avoid bugs. Remember to test all code (except helpers), and to write proper types, otherwise your code will be rejected by the server. (For helper functions, they should be tested indirectly via the tests for the main function that uses them.)

Reminder: code quality will still be graded (now and in the future). Write clean and tidy code. Consult the Style Guide, and if something is unclear, ask questions on Piazza.

Question 1. Higher Order Function

Write a function called sequence that receives a function f, and two values first and last. The function should return a list of values (of the same type) that starts with first and ends with last, and for each consecutive pair of values a1, a2 in the list, (f a1) results in a2 — that is, (equal? (f a1) a2) should be #t.

A few test cases will clarify further how this function works:

You can also use these tests in your code (but do add more tests).

Side note: you cannot avoid bad uses of this function, where the final value is one that you will not reach, such as (sequence add1 1 0). This is essentially the halting problem: there is no way to forbid it in the type declaration, no way to test for it at runtime, and no good way to test for it.

Note also that Typed Racket cannot properly infer types for uses of polymorphic higher order functions, so if you want to try this function with a list function, you need to use inst to “instantiate” a polymorphic function with a specific type. For example:

(It is also possible by providing a redundant function just for its type, for example

but using inst is more convenient.)

Pay attention to the type you declare for sequence — if you use something like (Number -> Number) for the first argument you will reduce the utility of this function, since it can only work with numeric functions. Your solution must also be usable with other types too, as shown in the above tests.

Note, however, that Typed Racket has subtypes — and this can lead to a different extreme where the type declaration is too general:

This is also not a good type declaration, because it provides very little information about the function. Specifically, it will not allow you to use even apply the first argument, since it is not known that it is a function.

A proper type will need to be a polymorphic function: the type of sequence should refer to “some type A” in the following way:

Question 2. Defining and Using a New Type

In this question you will implement a type that is often useful: a possibly sparse set of integers. For the purpose of this question, we represent such sets as one of:

• A single integer;
• An inclusive range of integers;
• A combination of two integer sets.

Note that for simplicity there are no empty sets.

Begin by a type definition. Fill in the following template (2Sets is a valid Racket identifier):

Reminder: define-type is something that is specific to the #lang pl language, do not confuse it with the same syntax from Typed Racket. See how we used it in the type definition for the AE language implementation that we went over in class.

An integer set is said to be in normal form if no numbers are repeated (singleton numbers and ranges have no overlap), if all ranges are formed from two numbers where the first is smaller than the second, when 2Sets unions are also in order (the set on the left side is completely below the set on the right), and there is some gap between the two subsets in a 2Set value. In other words, a normalized integer set is one that is completely ordered and has the shortest number of elements. Implement an intset-normalized? predicate that checks this. Some examples of intsets that are not normalized:

It is relatively easy to define this function given two utility functions, intset-min and intset-max, that return the smallest and biggest members of an INTSET respectively. But these two functions are quite similar, so implement a third function, intset-min/max, that can return either result, based on a comparator function. Your intset-min/max should be implemented such that the other two utility functions are defined as follows:

Note that using this is not going to be too efficient; specifically, each side of a 2Sets construct is scanned twice (which makes the run-time asymptotically worse than a single scan — not just double!). Finding an implementation that performs a single scan is more difficult, however, so it is not necessary. But this does not mean that you should neglect common sense — for example, don’t do more scans than needed.

Remember: correct type, purpose statement, and tests. Note that since the main functionality in the above is intset-normalized?, then that’s what should be tested — do not test the helper functions directly.

Note that the only thing you can do with a type is pattern-match over it with cases. cases is very similar to match, only restricted to types that we define using define-type, and in addition you cannot do anything with values of these types other than using them in cases — you cannot use them in match patterns. Read about it more in the class notes. Again, refer to the AE example in the class notes to see how we used it in class.

[Ideally, the cases functionality would be folded into match, but achieving this has some technical limitations that we could never resolve.]

Question 3. BNF

The INTSET type is useful, for example, in representing a range of pages to print: a comma separated sequence of integers and integer ranges (two integers separated by a dash). For example,

Write a BNF for such specification. Write the grammar in a #|...|# comment. Don’t call it <INTSET> since that name relates to the implementation, call it <PAGES>. Also, make sure that it is unambiguous.

For simplicity, you can use <int> as a known terminal, so there’s no need to specify the syntax for integers. Note that you can use “...” as shown in class, but it won’t make the BNF shorter, so you can just as well avoid using it. (Also, note that this question is unrelated to the normalization thing which we discussed above in the implementation part.)

Finally

Define minutes-spent as the number of minutes you spent on your homework.