YouTube

Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

English subtitles

← The Living and the Dead Solution - Programming Languages

Get Embed Code
3 Languages

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

  1. For this homework, we asked you to remove dead code.
  2. That is code that could not have any effect
  3. on the final return result of the method we’re
  4. interested in. So, let’s go ahead and just dive right
  5. into this. We take a fragment; if you remember
  6. the fragments are of this shape where the first part
  7. of the tuple is the variable to be assigned to and
  8. then the next part of the tuple is the expression
  9. that is being assigned to it, in this case one is
  10. being assigned to A or A operational, one is being
  11. assigned to B, 2 is being assigned to C etcetera.
  12. Now we’re not really concerned with what
  13. specifically the operations are. We don’t care
  14. what operations are being done. We just care that
  15. something is being done to these variables,
  16. because if there is something being done, even if
  17. it ends up setting them to the exact same thing, we
  18. can’t necessarily know that ahead of time. So, if
  19. you have a fragment of this shape, then we store
  20. that as the old fragment, as the un-optimized
  21. fragment. And that’s the first argument to this
  22. method. And the return is the end return value;
  23. it’s the list of variables returned at the end of the
  24. fragment. And if they’re returned at the end of the
  25. fragment, they’re automatically live, as we said
  26. up here. Now we want to create a new optimized
  27. fragment of just the live variables. So we start off
  28. by initializing that to an empty list. And we set a
  29. variable called live equal to the returned live
  30. variables, because we know those are live.
  31. Now for every statement in the fragment starting from
  32. the back, so we’re working backwards from the
  33. return statement, back up to the top, we check if
  34. the first element of the tuple statement, that is the
  35. left hand side of the statement, is already in live.
  36. That is, it is one of the live variables currently.
  37. If it is, then we add that statement to the new
  38. optimized fragment. Otherwise we fall through
  39. and now we take the list of live variables and we
  40. remove the variables that we’re now assigning to.
  41. So we take all those out. From there, we update
  42. the live list with all the variables that are currently
  43. on the right hand side of statement. We run
  44. through the entire fragment doing that over and
  45. over until we get back to the top. Once we’re
  46. done with that, we check if the new fragment is
  47. equal to the old fragment. If it is, then we return
  48. the new fragment. We didn’t change anything.
  49. So we just return and stop and we’re done. If it isn’t,
  50. well, then we might have further optimizations as
  51. we discussed earlier. Then we return, removing
  52. dead of the new fragment in return. So we
  53. recursively call this until we don’t get any
  54. further changes, because hopefully we can
  55. optimize further. Now we’re going to check that
  56. removed dead gives us what we would expect if
  57. we ran through all the optimizations by hand, and
  58. I’m not going to bother going through all of these.
  59. You can read them fairly easily and when we do
  60. that, we see that we get true values for each of
  61. these. This is a fairly involved little bit of code.
  62. It takes a little bit to think about and this is a
  63. very useful optimization because we can
  64. potentially get rid of a lot of code doing this.