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

1a.

In class we have seen the grammar for AE — a simple language for “Arithmetic Expressions”. Write a BNF for “SE”: a similarly simple language of “S-Expressions”. Valid “programs” in this language should correspond to Racket expressions that evaluate to S-expressions holding numbers and symbols. The valid functions that can be used in these expressions are cons, list, and append. null is also a valid expression. Note that the grammar should allow only cons with a second expression that represents a list (no numbers or symbols), list can have any number of arguments (including zero arguments), and append can have any number of list arguments. (A quick rule-of-thumb for the cons restriction: if an expression works fine in the course language, then it should be in SE.) Plain values are either numbers or quoted symbols — no quoted lists, and only the quote character can be used. You can use <num> and <sym> as known numbers and symbols terminals. (Note that we assume that <sym> corresponds to a Racket symbol, and that does not include the quote (') character, and note that we’re using ()s here.)

For example, some valid expressions in this language follow. Note that they are all valid Racket expressions too.

The following are examples of invalid expressions:

Note that some of these expressions would evaluate to valid S-expression values in Racket too — but this question specifies a restricted set of expressions.

For list and append you will need to use ellipsis (...) to specify zero-or-more occurrences of the previous piece of syntax.

Write the grammar in a #|...|# comment.

1b.

In class, we have also seen the implementation of the AE language. (The code is available as a single file in the Interpreters Section.) We mentioned the fact that we’re using an intermediate S-expression format for input code, and that this helps in making the syntax and the semantics independent. To see this in action, modify the AE implementation in two ways, and notice how each change affects different parts of the code:

• Make the language use infix syntax (still fully parenthesized, for simplicity). You will need to change both the BNF definition (the topmost comment) and the code in the parser. Make sure you properly comment your change to the parser. (Hint: this is extremely easy; if you find yourself writing new code, then you’re probably off track.)

• As it stands, the AE evaluator reflects Racket’s behavior for all arithmetics. For example, if you try to evaluate {5 / 0}, you get a Racket “division by zero” error. “Fix” this by returning infinity from such divisions, and to make things easy, use 999 as the value of infinity. (Sidenote₁: the spaces are important, dropping them with an input of {5/0} makes it parse as a rational number, which means that a division-by-zero error is thrown when converting this string to an S-expression; something that you can’t do anything about.) (Sidenote₂: consider 999 as a generic “bad result”-like value, so use it for any division by 0.)

For this question, copy the AE evaluator code in one chunk, including the tests at the end (but get rid of the #lang line, since you already have one). Note that to be able to submit your solution, you will need to add enough test cases that cover the code completely.

1c.

We’ve talked about the limitation of AE to simple calculations; some calculators use a “memory” cell to get more “power”. Say that you wanted to add just that functionality to your language. A naive attempt at the syntax for this language, call it “MAE”, is to add a set operator that sets the current memory value to some expression result, and a get operator to retrieve the current value:

where the intended meaning for a {set E} is to evaluate E, store the result in the memory cell, and return it.

There are, however, some problems with this approach.

1. The first problem can be seen if you consider evaluating the following expression:

   {* {+ {set 1} {set 2}} get}

   Describe the problem that is demonstrated by this, and suggest a feature to add to the MAE semantics that will solve it. Note that this feature is already present in our AE implementation, but it is only implicit there. (The solution is a short explanation. You do not need to implement anything. Write it in a single #|...|# comment.)

2. Even if the previous problem is fixed, the resulting language is not a good model for the way calculators are used. For example, we may want to extend the language to have a single memory cell for some limited level of abstraction — to compute the area of a 2-foot and 18-inches square in square-feet we would translate the obvious calculator operations to the following MAE syntax (assuming it is fixed as above):

   {* {set {+ 2 {/ 18 12}}} get}

   But if you were using a real calculator, you would more likely compute the {+ 2 {/ 18 12}} term first, store the result in memory, and then compute {* get get}. In other words, a computation is a non-empty sequence of sub-computations, each one gets stored in the memory and is available for the following sub-computation, except for the last one.

   Write a new MAE grammar that derives such programs. Add a toplevel seq for such MAE programs. To make it more interesting, make it impossible to use get in the first sub-computation in the sequence, force all expressions except for the last to be set expressions, and make set valid only around expressions (not inside them). Examples:

   ;; valid sequences
   {seq {set {+ 8 7}}
       {set {* get get}}
       {/ get 2}}
   {seq {- 8 2}}
   ;; invalid sequences
   {seq {* 8 get}          ; cannot begin with a `get'
       24}
   {seq {* 8 7}            ; must be a `set'
       24}
   {seq {set {+ 1 2}}
       {set {- get 2}}}    ; cannot end with a `set'
   {seq {* 2 {set {+ 1 2}}} ; `set' must be outside
       {- get 2}}

   Hint: you will need a toplevel <MAE> for a sequence of computations, then the usual <AE> and a new kind of <AE> (under a different name, of course) that includes a get operator.

   Note: be careful with this question, you need to get the details right! Remember that a BNF grammar is a formal piece of text, and as in any code — good style is important here too.

   Again, put your solution in a #|...|# comment.

Question 2. Higher Order Functions

As you already know, lists are a fundamental part of Racket. They are often used as a generic container for compound data of any kind. It is therefore not surprising that Racket comes with plenty of useful functions that operate on lists. One of the most useful list functions is foldl: it consumes a combiner function, an initial value, and an input list. It returns a value that is created in the following way:

• For the empty list, the initial value is returned,
• For a list with one item, it uses the combiner function with this item and the initial value,
• For two items, it uses the combiner function with the first and the result of folding the rest (a one-item list),
• etc.

In the general case, the value of foldl is:

Note that foldl is a higher-order function, like map. Its type is:

Use foldl together with map to define a sum-of-squares function which takes a list of numbers as input, and produces a number which is the sum of the squares of all of the numbers in the list. A correct solution should be a one-liner. Remember to write a proper description and contract line, and to provide sufficient tests (using the test form). You will need to do this for a definition of square too, which you would need to write for your implementation of sum-of-squares (but no tests needed for square since it is tested via sum-of-squares).

Question 3. Typed Racket (and more H.O. functions)

3a.

We define a binary tree as a something that is either a Leaf holding a number, or a Node that contains a binary tree on the left and one on the right. Write a define-type definition for BINTREE, with two variants called Node and Leaf.

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.

3b.

Using this BINTREE definition, write a (higher-order) function called tree-map that takes in a numeric function f and a binary tree, and returns a tree with the same shape but using f(n) for values in its leaves. For example, here is a test case:

Remember: correct type, purpose statement, and tests.

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

3c.

Continue to implement tree-fold, which is the equivalent of the swiss-army-knife tool that foldl is for lists. There are two differences between tree-fold and foldl: first, foldl has a single init argument that determines the result for the single empty list value. But with our trees, the base case is a Leaf that holds some number — so we use a (numeric) function instead of a constant. The second difference is that tree-fold’s combiner function receives different inputs: the two results for the two subtrees. tree-fold should therefore consume three values — the combiner function (a function of two arguments), the leaf function (a function of a single number argument), and the BINTREE value to process. Note also that tree-fold’s type is slightly simpler than foldl’s type — because we have only trees of numbers — but don’t confuse that with the output type, which does not have to be a number (or a list of numbers).

Note: tree-fold is a polymorphic function, so its type should be parameterized over “some type A” (which will be used for the output). The Typed Racket notation for this is

When your implementation is complete, you can use it, for example, to implement a tree-flatten function that consumes a BINTREE and returns a list of its values from left to right:

You can use this function, as well as others you come up with, to test your code.

Note the use of (inst f Number) — the Typed Racket inference has certain limitations that prevent it from inferring the correct type. We need to “help” it in these cases, and say explicitly that we use the two polymorphic functions append and list instantiated with Number. (Think about an (All (A) ...) type as a kind of a function at the type world, and inst is similar to calling such a function with an argument for A.) You will not need to use this elsewhere in your answers.

3d.

Use tree-fold to define a tree-reverse function that consumes a tree and returns a tree that is its mirror image. That is, for any tree t, the following equation holds:

and you can use it in your tests (but use test for the test). If you do things right, this should be easy using a one-line helper definition.

4. Finally

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