RefacUnGuard

The main goal of this refactoring is to convert a function declaration where guards can be found into another with no guards, and with if then else expressions instead. But the biggest problem aboarded in this transformation is how to remove this guards if they afect more than one match that can be merged into a single one, where different name for the variables is used and some line swapping may be needed.

This refactoring is then divided into three different sub-problems, that will be explained in more detail in this document:

Check which matches can be converted and swaped with matches defined bellow, without changing the function behaviour;
Merge the similar matches with guards to a single match, renaming the needed variables;
In each match replace the guards by if then else when possible.

Stages of the refactoring

Consistency check

Before any other evaluation each match is compared with the matches below on the same declaration by isConsist. It is then associated with a boolean that states if the declaration has any inconsitency below. A match is said to be inconsitent with a second one below it if the patterns are not disjoint and if a constant value is found in the a pattern of the second match where a variable was in the first one. All possibles patterns were contemplated.

findConsist :: [HsMatchP] -> [(Bool, HsMatchP)]

Given a set of matches, checks which ones have guards that can be removed without afecting the program's behaviour. This implies going throw every pattern to check if each pair is similar, disjoint or inconsistent. It uses the binary function isConsist.

isConsist :: [HsPatP] -> [HsPatP] -> Maybe Bool

Checks if two lists of patterns are consistents. Possible results are:

Just True - if disjoint patterns are found
Just False - if an incongruence is found and there are no disjoint patterns
Nothing - if no incongruence nor disjoint patterns are found

Merge of matches

After knowing which matches can be manipulated and swaped, the next step is to try to merge matches using all possible combinations.

Because there are sometimes the need to create fresh variables, a name that is not the prefix of any of the variable names (in this case is the smaller sequence of x's) is used as the base name and a counter is added to the variable name. The mergeMatches is a function that uses a state monad with partiality, whith the base name and the conter inside the state, and that fails when the merging of two matches is not possible.

Before trying to merge matches, the declarations of the consistent matches are passed to inside the guards and to the main expressions, using the function declsToLet, since after the merging the declarations will afect more than the original expressions. This will duplicate the declarations inside the where clause.

getInitSt :: [HsMatchP] -> St

To get an initial state it is necessery to find a base name that is not prefix of any of the used names. In this case it will be x replicated until it is not a prefix. The counter is initiated to zero.

dmerge :: [(Bool, HsMatchP)] -> St -> [(Bool, HsMatchP)]

Distributes the binary function mergeMatches.

The state of each evaluation of mergeMatches as to be extracted to be passed to further calls. It doesn't make sense to put the same state inside dmerge, because it would fail when the first mergeMatches failed, which is not desired.

In the merge of two matches all the possible patterns were contemplated. In some cases there is more than way to merge patterns. Each case will now be explained in more detailed.

Similar patterns: If the two patterns are equivalent according to the function similar, then no transformation is applied. Since this is the first test to be performed, the patterns are considered to be different in the remaing tests;
Variables: When two different varibles are found they are replaced by a fresh variable, in the pattern, in the guards and in the main expression;
Parentisis: They are initialy ignored, and in the end they are placed back;
WildCard (underscore): Can only be matched with a variable. In this case a fresh variable will replace both the wild card and the variable, in every important place of the match;
var @ pattern: If both matches have this construction, then the variable and the associated pattern are splited into two different patterns, and after the recursive evaluation the resulting variable is "glued" back to the resulting pattern. If only one match have this construction, then the variable is replaced by a fresh variable, so that the same variable can also be assigned to the second pattern;
Irrefutable pattern: When a irrefutable pattern is found, it is replaced by a fresh variable, and inside the guards and in the main expression a let constructor is added, assigning the irrefutable pattern to take the value of the fresh variable. This way the fact that haskell uses lazy evaluation allows the behaviour of the function to be the same as before;
Constructors with fields: Whenever a constructor with fields is found, it is converted into a pattern where the constructor is applied to the different variable, using wild cards to when a variable name is not assigned;
Application: When in both matches a application of a constructor is found, and the constructors are similar (according to the similar function), then the list of arguments are added to the remaining patterns to be merged, and in the end they are extracted and "glued" with constructor again;
Infix application: Same approach to normal application was taken.
Tupples and lists: Each pattern inside the tupple or list is added to the remaining patterns to be merged, and in the end they are "glued" again with the tuple or list constructor.

mergeMatches :: HsMatchP -> HsMatchP -> ST HsMatchP

Tries to merge two matches with guards, using a state monad to create fresh variables whith partiality to fail when no merging is possible.

Conversion from guards to if then else's

The final stage is the most simple one, since there are not many cases to evaluate. The function guards2ifs is applied to each match with a guard and with the consisty check mark. When the otherwise guard is not found the else of the resultig expression issues an error message.

guards2ifs :: (Bool, HsMatchP) -> HsMatchP

Convert a match with guards to another match where the guards are translated to if then else's

Auxiliary functions

In this section some of the auxiliary functions used in this refactoring are presented. This functions may be of some use in later refactorings.

similar :: (Eq t1, Term t1) => t1 -> t1 -> Bool

Checks if two terms are similar, by using the defined equality, and after some simplifications to the term:

all locations are converted to the "unknown" location (are ignored)
the origin location of the PN's is set to a null position in a file with the same name that the variable, because two PN's are considered to be equal if they have the same origin location, but in this case two PN's should be similar if they have the same name.

differ :: (Eq t1, Term t1) => t1 -> t1 -> Bool

Checks if two terms differ by negating the similar definition

replaceExp :: Term t => PNT -> String -> Maybe PNT -> t -> t

Replaces a variable name (given a PNT) by changing the name to a new name and, when another PNT is passed, also changes the source location to the same the second PNT.

declsToLet :: RhsP -> [HsDeclP] -> RhsP

Places declarations inside an expression by the use of the let constructor

Future work

This refactoring tries to be as complete as possible, but it is still possible to improve some cases. A possible improvement would be to infer the otherwise case, as presented in the following example:

f x | x > 0 = 1
f x = 0

that could be initialy converted to

f x | x > 0 = 1
f x | otherwise = 0

but instead it does nothing to avoid overriding the last expression. This is not very easy because a single expression in the end may be used to merge with more then one group of matches above.

Another improvement would be to check if the declarations could also be merged before converting them into if then else's.

Produced by Haddock version 0.6