Scripting Languages CSCI-GA.3033.003, Summer 2012 hw08

Dates: Assigned Thursday 7/12/2012, due Friday 7/20/2012 at 6pm.
Topic: Debugging for scripting languages
Total points: 40
Instructions: Please put your solutions to all questions (including both the concept questions and the programming questions) in a single plain-text file, such as what you get when using Emacs, Vi, Notepad, or the “save as text only” feature in Word. Your JavaScript code must run in both Mozilla's Firefox browser and Microsoft's Internet Explorer browser. If you don't have a computer with these browsers, test your code on the Windows machines in the labs WWH 229 and WWH 230. Please email your solutions to hw08 to the grader.
Grader for hw08: Ashish Walia (ashish.walia@nyu.edu)

Reading Assignments

For lecture on 7/19/2012: Thomas Powell and Fritz Schneider. JavaScript Security. Chapter from the book JavaScript: The Complete Reference, second edition, McGraw-Hill/Osborne. October 4, 2004, Chapter available at http://www.devarticles.com/c/a/JavaScript/JavaScript-Security/.

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