Problem Four: Consider the folowig declarations: data Bool-F T data Nat ZS Nat Same as hwl but abbreviated --to make solutions easier to write. not :: Bool Bool not T F not FT if' : Bool-> Nat-> Nat-> Nat same as cond in lecture red :: Nat ->Nat red 2 red (S x) -red x inf Nat ->Nat inf x = inf x Recall that evaluation of expressions proceeds by searching for a redex (a subexpression where some rule defining a function will match) and rewriting the subexpression (using the bindings generated by the match). Consider the following algorithm, which thinks of the expression as a tree (as in Problem One): while the expression contains some function symbol: for each subexpression in a preorder search of the expression: for each rule in order (top to bottom) in the program: if the rule matches: then do one rewrite and start over at the top of the while loop For each of the following, show the expressions at each step, ending in the final value; if the sequence would not terminate, show a few steps and indicate that the rewrite sequence is infinite (A) if (not T) (red (S (S Z))) (if T Z (red Z) ) (B) if (not F) (red (S Z)) (red (inf Z)) NOW, for the next two problems, I want you to do the exact same expressions, but in the rewriting algorithm, search for the redex in a postorder (bottom-up, left to right) traversal of the expression (considered as a tree (C) if (not T) (red (S (S Z))) (if TZ (red Z)) (D) if (not F) (red (S Z)) (red (inf Z)) (E) Short answer: What was the difference between preorder (top down) and postorder (bottom up) in these examples? Be sure to comment on what happened in A compared with C, and B compared with D. Which seems to be a better strategy overall? Problem Four: Consider the folowig declarations: data Bool-F T data Nat ZS Nat Same as hwl but abbreviated --to make solutions easier to write. not :: Bool Bool not T F not FT if' : Bool-> Nat-> Nat-> Nat same as cond in lecture red :: Nat ->Nat red 2 red (S x) -red x inf Nat ->Nat inf x = inf x Recall that evaluation of expressions proceeds by searching for a redex (a subexpression where some rule defining a function will match) and rewriting the subexpression (using the bindings generated by the match). Consider the following algorithm, which thinks of the expression as a tree (as in Problem One): while the expression contains some function symbol: for each subexpression in a preorder search of the expression: for each rule in order (top to bottom) in the program: if the rule matches: then do one rewrite and start over at the top of the while loop For each of the following, show the expressions at each step, ending in the final value; if the sequence would not terminate, show a few steps and indicate that the rewrite sequence is infinite (A) if (not T) (red (S (S Z))) (if T Z (red Z) ) (B) if (not F) (red (S Z)) (red (inf Z)) NOW, for the next two problems, I want you to do the exact same expressions, but in the rewriting algorithm, search for the redex in a postorder (bottom-up, left to right) traversal of the expression (considered as a tree (C) if (not T) (red (S (S Z))) (if TZ (red Z)) (D) if (not F) (red (S Z)) (red (inf Z)) (E) Short answer: What was the difference between preorder (top down) and postorder (bottom up) in these examples? Be sure to comment on what happened in A compared with C, and B compared with D. Which seems to be a better strategy overall