Showing Revision 2 created 05/25/2016 by Udacity Robot.

1. Title:
   The Living and the Dead Solution - Programming Languages
2. Description:

3. 0 0:00 - 0:04
   For this homework, we asked you to remove dead code.
4. 3759 0:04 - 0:07
   That is code that could not have any effect
5. 7067 0:07 - 0:11
   on the final return result of the method we’re
6. 10989 0:11 - 0:14
   interested in. So, let’s go ahead and just dive right
7. 13742 0:14 - 0:17
   into this. We take a fragment; if you remember
8. 17252 0:17 - 0:23
   the fragments are of this shape where the first part
9. 23041 0:23 - 0:28
   of the tuple is the variable to be assigned to and
10. 27746 0:28 - 0:32
    then the next part of the tuple is the expression
11. 32305 0:32 - 0:35
    that is being assigned to it, in this case one is
12. 35485 0:35 - 0:39
    being assigned to A or A operational, one is being
13. 39261 0:39 - 0:42
    assigned to B, 2 is being assigned to C etcetera.
14. 42071 0:42 - 0:45
    Now we’re not really concerned with what
15. 45217 0:45 - 0:48
    specifically the operations are. We don’t care
16. 47948 0:48 - 0:50
    what operations are being done. We just care that
17. 50491 0:50 - 0:54
    something is being done to these variables,
18. 53756 0:54 - 0:56
    because if there is something being done, even if
19. 56054 0:56 - 0:59
    it ends up setting them to the exact same thing, we
20. 59185 0:59 - 1:02
    can’t necessarily know that ahead of time. So, if
21. 62000 1:02 - 1:07
    you have a fragment of this shape, then we store
22. 66868 1:07 - 1:09
    that as the old fragment, as the un-optimized
23. 69425 1:09 - 1:13
    fragment. And that’s the first argument to this
24. 72549 1:13 - 1:18
    method. And the return is the end return value;
25. 78352 1:18 - 1:21
    it’s the list of variables returned at the end of the
26. 81352 1:21 - 1:24
    fragment. And if they’re returned at the end of the
27. 83858 1:24 - 1:26
    fragment, they’re automatically live, as we said
28. 86262 1:26 - 1:30
    up here. Now we want to create a new optimized
29. 89970 1:30 - 1:34
    fragment of just the live variables. So we start off
30. 93838 1:34 - 1:40
    by initializing that to an empty list. And we set a
31. 99653 1:40 - 1:43
    variable called live equal to the returned live
32. 103091 1:43 - 1:46
    variables, because we know those are live.
33. 105602 1:46 - 1:50
    Now for every statement in the fragment starting from
34. 109666 1:50 - 1:52
    the back, so we’re working backwards from the
35. 112200 1:52 - 1:56
    return statement, back up to the top, we check if
36. 115881 1:56 - 2:00
    the first element of the tuple statement, that is the
37. 119700 2:00 - 2:04
    left hand side of the statement, is already in live.
38. 123740 2:04 - 2:07
    That is, it is one of the live variables currently.
39. 126596 2:07 - 2:12
    If it is, then we add that statement to the new
40. 132198 2:12 - 2:16
    optimized fragment. Otherwise we fall through
41. 135604 2:16 - 2:20
    and now we take the list of live variables and we
42. 139573 2:20 - 2:24
    remove the variables that we’re now assigning to.
43. 144131 2:24 - 2:27
    So we take all those out. From there, we update
44. 146934 2:27 - 2:31
    the live list with all the variables that are currently
45. 150693 2:31 - 2:33
    on the right hand side of statement. We run
46. 153005 2:33 - 2:36
    through the entire fragment doing that over and
47. 156397 2:36 - 2:38
    over until we get back to the top. Once we’re
48. 158485 2:38 - 2:40
    done with that, we check if the new fragment is
49. 160298 2:40 - 2:44
    equal to the old fragment. If it is, then we return
50. 163646 2:44 - 2:46
    the new fragment. We didn’t change anything.
51. 165826 2:46 - 2:50
    So we just return and stop and we’re done. If it isn’t,
52. 169564 2:50 - 2:52
    well, then we might have further optimizations as
53. 171819 2:52 - 2:55
    we discussed earlier. Then we return, removing
54. 175184 2:55 - 2:57
    dead of the new fragment in return. So we
55. 177447 2:57 - 3:00
    recursively call this until we don’t get any
56. 180425 3:00 - 3:03
    further changes, because hopefully we can
57. 182817 3:03 - 3:05
    optimize further. Now we’re going to check that
58. 185141 3:05 - 3:08
    removed dead gives us what we would expect if
59. 188305 3:08 - 3:12
    we ran through all the optimizations by hand, and
60. 191594 3:12 - 3:15
    I’m not going to bother going through all of these.
61. 195247 3:15 - 3:18
    You can read them fairly easily and when we do
62. 197517 3:18 - 3:21
    that, we see that we get true values for each of
63. 200744 3:21 - 3:24
    these. This is a fairly involved little bit of code.
64. 204071 3:24 - 3:26
    It takes a little bit to think about and this is a
65. 205869 3:26 - 3:30
    very useful optimization because we can
66. 209805 3:30 - 3:33
    potentially get rid of a lot of code doing this.