Homework #12 - 9/24

     I found this article an interesting read. Control flow graphs are kind of understood subconsciously by programmers, but when we actually look at them and investigate their properties, there's a lot more to them than you might think at first. One thing that was confusing to me, or at least not very intuitive, was the GEN KILL IN() OUT() sets. The GEN, IN, and OUT I understand: GEN meaning anything the line of code produces, IN consisting of all of the input variables, and OUT consisting of all of the output variables. The KILL set, however, is a little more difficult to wrap my head around. It is defined as the set of definitions that are killed if they reach the entry to the node. An example they give is the KILL set of {3 : sum, 5 : sum, 8 : sum} for the line of code sum = 0; I understand that the sum of 3 and 5 is 8 from the set (although I'm not sure if that's what is meant by the values in the set), but how did those numbers get derived for that particular line of code where it is merely setting a variable equal to zero?
     When reading about Definition-Use pairs, the first thing I thought was fields and methods of classes. Every node in the control flow graph is like a class (even though it could be just a single line of code) and its definition are the field values and its uses are the methods. It mentions an upward exposed use which it describes as a use of some variable which can be reached by a definition of the variable that reaches the node. This is a little confusion to me, it almost seems ambiguous. What I grasp from it is when a variable is defined, and then used in a child node, the use in the child node is considered upward exposed.
     Program paths are another one of those intuitive subjects in the article. My understanding is that any number of consecutive nodes where the output of node n leads to the input of node n+1 is a path (or subpath). A program path is complete if the starting node of the path is the starting node of the whole program and likewise the ending node is the exit node of the program. Definition-clear paths are something I never thought of, but easy enough to understand. A path is definition-clear with respect to a variable v if it does not depend (contain, basically) on v. Also, the article talks about infeasable paths, which are basically just any path that cannot be executed regardless of input of the program. An example would be:

     String myName = "";
     if(false) {
          myName = "Justin";
     }

The variable myName will never be set to "Justin" no matter what code comes before or after it, therefore that program path is infeasible.
     All of this material seems familiar or intuitive to us as programmers, because as seen in the code above, we use them regularly, we have just been unaware of it and their formal definitions until now.