Template Haskell

Introduction

In this exercise, we will have a closer look at Template Haskell. The hierarchical libraries that are distributed with GHC include functions for writing Template Haskell code. Have a look at the module Language.Haskell.TH, and to Section 7.6 from the GHC User's Guide. To use Template Haskell code from the ghci interpreter, you need to use the flag -fth.

This exercise was inspired by research on automatically repairing ill-typed expressions. For some typical programming errors, a more advanced compiler could offer advise to a programmer how to correct an expression with a type error. In fact, the Helium Compiler offers such a facility. You are asked to write a number of functions that can be used to correct an expression (details are given below).

Resources

You are given two Haskell modules as a starting point.

• Correct.hs: contains the functions you have to define. Currently, these functions are set to undefined.
• Test.hs: contains a number of functions for testing your implementation. In some cases, the expected answer is provided. In the other cases, the test corresponds to an optional question. Note that you also have to make changes to this module because the compiler must be informed about which parts are meta-programs.

Submit your solution by sending me the two changed Haskell modules, and give short answers to the questions posed. Good luck!

Task Description

1. Removing an argument

The following expression contains a type error.

test0 = filter even () [1..10]

One possibility to get rid of the type error is removing the () from the application. We will use the following convention: 0 corresponds to the function of the application (filter), 1 to its first argument (even), etc. Implement a function remove that is given a number n (greater than or equal to 0), such that it conceptually ignores the =n=th argument. For example, (remove 2) filter even () [1..10] should yield the same result as filter even [1..10] (because n = 2 corresponds to ()).

Hint: write a (lambda) expression by hand that behaves as remove 2.

Questions:

• Why can't remove be defined as a normal (non-Template) Haskell function?
• remove n with n = 0 is a special case, since it removes the function of an application rather than some argument. Give an intuition for the meaning of remove 0.
• What happens if we choose n = 5 for the example presented above (the function filter is supplied only three parameters)?

2. Inserting an argument

In the following expression, the higher-order function foldr should be given an initial value. This expression can be repaired by inserting a second parameter.

test2 = foldr ((:) . toUpper) "afp 2005"

We will use the same convention for assigning numbers to the parameters. Hence, (insertHole 2) foldr ((:) . toUpper) "afp 2005" should be equal to foldr ((:) . toUpper) hole "afp 2005", where hole is the polymorphic "error function" predefined in the module Correct.hs.

Optional part for 2:

More ideally, we pass an additional parameter to insert, which is the value to be inserted. For instance, (insert 2 []) foldr ((:) . toUpper) "afp 2005" leads to foldr ((:) . toUpper) [] "afp 2005". Explain your solution.

3. Permuting arguments

In the next example, the arguments to foldr are supplied in the wrong order.

test4 = foldr 0 (+) [1..10]

A permutation can be represented by a value of type [Int]. For instance, the permutation [0,2,1] swaps the first and the second arguments of a function. Give an implementation of permute for permuting arguments.

Questions:

• Explain the difference between permute [0,2,1] and permute [0,2,1,3].
• The value [0,1,1] is not a valid permutation, but it can be passed to permute. What kind of corrections can we make by passing invalid permutations?

4. Inserting parentheses

Take a look at the following expression.

test5 = length filter even [1..10]

A common mistake made in functional programming is to forget some parentheses. The expression given above can be fixed by inserting two parentheses, yielding length (filter even [1..10]). This is the purpose of the function parens that you have to write. This function should be supplied two integers: the first indicates the location of the opening parenthesis, the second integer indicates how many parameters are enclosed by the parentheses. We use the convention that location 0 corresponds to the position just before the function (in our example, length), whereas 1 corresponds to the position between the function and its first argument (in our example, between length and filter). To correct test5, we thus need parens 1 3.

Question:

• What can you say about the values of the two integers that can be supplied to parens? Are there special cases?

5. Removing parentheses (optional)

In a similar way, we would like to remove a pair of parentheses.

foldr ((++) [] ["Template", "Meta", "Programming"])

Following our line of reasoning, we could fix the type error by using unparens 1 3. Can you give a definition for unparens?

6. Library for correcting expression

Template Haskell offers a facility to splice in declarations. Therefore, we could automatically bring the functions insert0, insert1, insert2, etcetera into the top-level scope of a module. These specialized functions can be used as any normal Haskell function. Of course, we can make use of the general insert function (see Step 2). Bring (a limited number of) specialized functions for insert into the scope.

Optional part for 6:

Do the same for the other correcting functions.

7. Extending the library (optional)

Of course, there are more mistakes resulting in a type error that can be fixed automatically. Can you think of more (useful) correcting functions?