Scripting Languages CSCI-GA.3033.003, Summer 2012 hw08


Reading Assignments

Concept Questions

hw08_1 Scientific method

Consider the following buggy PHP script.
<?php                                                         // 1
function my_sort($a) {					      // 2
  $n = count($a);					      // 3
  $b = array($n);					      // 4
  foreach ($a as $i => $v)				      // 5
    $b[$i] = $v;					      // 6
  for ($i=0; $i<$n; $i++) {				      // 7
    $iMin = $i;						      // 8
    for ($j=$i; $j<$n; $j++)				      // 9
      if ($b[$j] < $b[$iMin])				      //10
        $iMin = $j;					      //11
    $min = $b[$iMin];					      //12
    $b[$iMin] = $b[$i];					      //13
    $b[$i] = $min;					      //14
  }							      //15
  return $b;						      //16
}							      //17
function is_sorted($c) {				      //18
  $n = count($c);					      //19
  for ($i=0; $i<$n; $i++)				      //20
    if ($c[$i] > $c[$i+1])				      //21
      return false;					      //22
  return true;						      //23
}							      //24
$d = array(1,3,2,5);					      //25
echo '$d is' . (is_sorted($d) ? " " : " not ") . "sorted\n";  //26
$e = my_sort($d);					      //27
echo '$e is' . (is_sorted($e) ? " " : " not ") . "sorted\n";  //28
?>
1a.
(3 points) Run the script. What does it print?
1b.
(12 points) Debug the script using the scientific method. Your answer should be a debugging log book, similar to the example in the lecture slides. The format should be similar to this:
1 Hypothesis  (e.g., variable has wrong value in given line)
  Experiment  (e.g., add print statement, run on command-line)
  Observation (e.g., the value of the variable at that place)
  Conclusion  (e.g., hypothesis verified, falsified, inconclusive)
2 Hypothesis  ...
  Experiment  ...
  Observation ...
  Conclusion  ...
3 ...
...

hw08_2 Debug closure trick

Consider the "debug closure trick" from the lecture, reproduced here for your convenience.
<html><head><script>                                                          // 1
  function breakpoint(evalFunc, msg) { 					      // 2
    var expr = "arguments.callee";					      // 3
    var result;								      // 4
    while (true) {							      // 5
      var line = "\n----------------------\n";				      // 6
      expr = prompt("BREAKPOINT: " + msg + "\n"				      // 7
        + (result ? "eval('" + expr + "') -> " + line + result + line : "\n") // 8
        + "Enter an expression:", expr); 				      // 9
      if (expr == null || expr == "") return;				      //10
      try {								      //11
        result = evalFunc(expr);					      //12
      } catch (e) {							      //13
        result = e;							      //14
      }									      //15
    }									      //16
  }									      //17
</script></head><body><script>						      //18
  function foo(x, y) {							      //19
    breakpoint(function(expr){return eval(expr);}, "bar");		      //20
  }									      //21
  foo(2, 4);								      //22
</script></body></html>
2a.
(5 points) What is the function part of the debug closure?
2b.
(5 points) What is the environment part of the debug closure?

Programming exercises

hw08_3 Delta debugging

When you learn a new language, a good way to make progress is by solving some moderately difficult programming problems. At the same time, when you learn a new algorithm, a good way to understand and remember it is by implementing it. Therefore, this question asks you to combine the two by using JavaScript to implement the delta debugging algorithm you learned in the lecture.
3a.
(5 points) Implement the helper functions subsets and list_minus. When you run with the following harness, what does it print?
<html><head><script>
  /* define your functions for 3a here */
</script></head><body><script>
  var subs = subsets([1,2,3,4,5], 3);
  document.write("subsets [");
  for (var i in subs) {
    if (0 < i) document.write(", ");
    document.write("[" + subs[i] + "]");
  }
  document.write("]<br/>\n");
  document.write("list_minus [" + list_minus([1,2,3,4,5], [3,4]) + "]<br/>");
</script></body></html>
3b.
(5 points) Implement the ddmin function. When you run with the following harness, what does it print?
<html><head><script>
  /* define your functions for 3a and 3b here */
</script></head><body><script>
  var m = ddmin([1,2,3,4,5], function(s){return 1<s.length ? 'fail' : 'pass';});
  document.write("ddmin [" + m + "]<br/>\n");
</script></body></html>
3c.
(5 points) Implement the test_sort function. When you run with the following harness, what does it print?
<html><head><script>
  /* define your other functions for 3a, 3b, and 3c here */
  function sort_ref_to_array() { /* buggy! */
    var arr = [ ];
    for (var i=0; i<arguments.length; i++)
      arr.push(arguments[i]);
    arr.sort();
    return arr[0];
  }
</script></head><body><script>
  var min = ddmin([1,3,5,2,4,6], test_sort);
  document.write("minimized to [" + min + "]<br/>\n");
</script></body></html>

http://cs.nyu.edu/courses/summer12/CSCI-GA.3033-003/hw08.html