Assignment #2: BNFs, Higher-Order Functions, Typed Scheme

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 Scheme) and some of the additional class extensions.

In this homework (and in all future homeworks) you should be working in the “Module” language, and use the appropriate language using a #lang line. You should also click the “Show Details” button in the language selection dialog, and check the “Syntactic test suite coverage” option to see parts of your code that are not covered by tests: after you click “run”, parts of the code that were covered will be colored in green, parts that were not covered will be colored in red, 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, to make things more convenient. There are some variants for the pl language for various purposes — in particular, #lang pl untyped will ignore all type declarations, and will essentially run your code in an untyped scheme.

The language for this homework is:

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 this example:

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 most easy bugs. Still, use proper tests to avoid bugs. Remember to test all code, and to write proper types, otherwise your code will be rejected by the server.

Reminder: code quality will be graded. Write clean and tidy code. Consult the Style Guide, and if something is unclear, ask questions on the mailing list.

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

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

Note that Typed Scheme 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:

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 Scheme has subtypes — and this can lead to a different extreme where the type declaration is too general:

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

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.

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.

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 an 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.

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,

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.

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