CSC 123 : AOP Lab and Assignment Due Wednesday 12/10 (last day of class) Work in your assigned group. Contact me if you don't know who your group is 0. A lot of programs are written that do no check for bounds and exceptions. For example: //////////////// public class fun { public static int factorial(int n, int ax) // tail-recursive factorial { if (n==0) return ax; else return factorial(n-1,ax*n) } public static void main(String[] args) { int x = factorial(5,4); // wrong answer x = factorial(-1,1); // infinite loop } } //////////////// There are two potential problems here. First, if n is accidentally passed a negative value, it will never return. Secondly, the *initial* value passed to ax must be 1, otherwise the wrong answer may be returned. Write aspects that cause an Error to be thrown when n is passed a negative value, and FORCE the initial value of ax to 1 if it's not. This is a bit more tricky than it looks, since your pointcut will have to distinguish between the initial call and subsequent, recursive calls. Demonstrate with a complete program. Preventing negative n's is easier and you should do that first as a way to warm up to aspectJ. 1. The following function is a classic example of recursion. Imagine a square grid. The problem is to find the number of different routes from a given coordinate (x,y) back to the origin (0,0). Routes may intersect eachother so there's going to be a lot of'em. The following is the easiest way to implement it, and it "works". /////////////////// public class routes { public long numroutes(int x, int y) { if (x<=0 || y<=0) return 1; else return numroutes(x-1,y) + numroutes(x,y-1); } public static void main(String[] args) { int x = Integer.parseInt(args[0]); int y = Integer.parseInt(args[1]); routes myroutes = new routes(); System.out.println(myroutes.numroutes(x,y)); } } // routes /////////////////// You can run this program using, for example: > time java routes 20 10 which will return the number of routes from (20,8) back to the origin as well as print the system time in seconds consumed by your program (run it in a Unix or Cygwin shell). Only problem is, running the following command: > time java routes 40 40 will take approximately 300 million years on a 400mhz Sun workstation. People who don't think carefully will say that the problem with this program is recursion. But that's a shallow answer. The real problem is redundant computation (similar to the inefficient fibonacci function). We can eliminate the redundancy by using a matrix (2D array) to "memoize" the results of the computation. That is, create an array of 500x500 longs: long M[][] = new long[500][500]; Initialize the array to contain values -1, which means that no answer has been found for a coordinate. Now, every time we compute numroutes(x,y), store the result in M[x][y] (unless x>=500 || y>=500) so that on subsequent, recursive calls, the result of numroutes(x,y) will be readily available by simply looking up the array. The function itself can REMAIN RECURSIVE. It only has to check if M[x-1][y] and M[x][y-1] contain pre-computed values (or if x or y is too big) before making the recursive calls. However, you will make this optimization even more elegant, by NOT TOUCHING the original program at all, using AspectJ. Write an aspect that includes the matrix, either as an element of the 'pertarget' aspect, or as an intertype declaration. pointcut that picks out calls to numroutes advice that implements the optimization IMPORTANT NOTE: Do not simply rewrite the entire recursive function and call it inside an advice. Use advice ONLY to update and lookup the array! Compile both the original UNTOUCHED program and your aspect together: ajc routes.java youraspect.java How long does 'time java routes 20 10' take compared to the original? How about 'time java routes 40 40'? 2. For this portion of the assignment, randomly select at least 4 Java programs of decent size. You can download some of the programs I have for my courses, some of your own (or your friends') past programs, as well as others you might find on the web. Don't choose ones all written by the same programmer. Please provide a brief description of each test program. Use aspectJ to record certain statistics about these programs, including: 1. number of times a variable within an object is 'get' versus number of times a variable is 'set'. Speculation has it that 85% of the time when a variable is accessed, it's a read access. 2. number of times a method is called within the same object versus number of times it's called externally (a similar stat is the number of public v.s. private calls). 3. How often are functions called that return values (versus void) 4. How many of the programs you tested made recursive calls? (since if there's recursion then the recursive calls will dominate, it makes no sense to measure recursive vs. non-recursive calls). To do this problem, you can call thisJoinPoint.getSignature().toString() which returns a string representation of the function being called. For example, calls to the "numroutes" function in the above problem have signature "long routes.numroutes(int, int)". You also need to keep track of all function calls using a *stack* of such call signatures. You push a new signature on the stack before each function call, and pop the stack afterwards. In fact, you can even detect mutual recursion with this technique. For example, in visitor pattern programs, accept calls visit, which in turn may call accept. Your program should be able to detect such cycles in call structure. Also, measure the depth of recursive calls (levels from top). What is the maximum depth of recursion exhibited by the test programs? Here's a stack class you can use (write your own if you don't like mine): class sigstack { private static final int size = 100000; private String[] S = new String[size]; private int tos = -1; // top of stack, -1 means empty stack void push(String N) { if (tos=0) return S[tos--]; else throw new Error("sigstack underflow"); } boolean found(String N) // is N anywhere on the stack { boolean ax = false; for(int i=tos;i>=0 && !ax;i--) ax = S[i].equals(N); return ax; } } // sigstack You need to write a bunch of before advice on appropriate point cuts, and collect the data. Note that all these stats are *runtime* stats. You can print the stats after join point execution(static void *.main(..)) or before call(* System.exit(..)). Another possibly tricky thing is to DISCOUNT calls from within your aspect and the stack class. Please give data in terms of percentages as well as raw numbers. Organize your data in some table or chart. Do you notice any common trends in your data? Collecting such info can be very important to language and software design. I may even use the data you collected for research purposes. Extra credit will be given for the group with the most interesting set of test cases.