BitterSuite: Counting Function Calls

The attached is a scheme file which can be used as a filter when rst is run.

For instructions on how to implement the filtering, see the Filtering Student Code topic.

What does this do?

Filtering file.ss would create file.filt.ss. This new file modifies the original so that every user defined function, as well as every lambda statement, will now increment a global variable |hello counter| by one each time the function is called. More specifically

(define (id id...) exp exp...)
=>
(define (id id...) (begin (set! |hello counter| (add1 |hello counter|))
                          exp exp...))
AND
(lambda (id...) exp exp...)
=>
(lambda (id...) (begin (set! |hello counter| (add1 |hello counter|))
                       exp exp...))

The idea behind counting user defined function calls is to give an estimate of the running time of students' code. Since most of the work done in Scheme is by recursive functions rather than loops, the number of function calls can be used to determine the Big-O runtime of a particular function. This also avoids the problem of trying to estimate running time of code by the actual physically time it takes for it to run (as this could be affected by many factors).

Initially, there was going to be a variable for every user defined function; however, one variable to keep track of every function call will still be able to give an approximation of Big-O runtime.

How do I use this?

Using the standard testing method

The tests should be created like any other tests are created. The changes you will have to make are to the options file associated with these tests. If the file that was filtered was a2q3.ss, then

(language scheme)
(loadcode a2q3.filt.ss)

would be an acceptable options file for these tests. Keep in mind because mutation is involved, the language level must be advanced or higher, even if the student wrote his code in the beginner language.

There are two functions and one variable provided from the filtering:

• |hello counter| The variable which will keep track of the function calls.
• |int hello counter| A function that takes no parameters and sets |hello counter| to 0.
• |inc hello counter| A function that takes no parameters and increases |hello counter| by 1.

It's unlikely the user will need to increment the counter, but in tests, the counter should be initialized before any test. Example:

(result (begin (|int hello counter|)
               (function parameter)
               (< |hello counter| (+ (* 5 parameter) 10))))
(expected true)

Plotting function calls

There may be a way to use the filtered file to create data which could be plotted using a similar method to plotting running times. See the Plotting Running Times topic for more on this.

Things this may not handle properly

Quoted and Quasiquoted lists

As the filter stands, it WILL descend into quoted and quasiquoted lists and modify any sublist which has the format of one of the two expressions above. Whether this is the desired action or not could depend on the assignment.

Vectors and Structures

As the filter stands, it WILL NOT descend into vectors and structures written in the form #(contents of vector or structure). Any lambda statements or local definitions stored within vectors or structures will not be modified. Whether this is the desired action or not could depend on the assignment.

Built-in List Functions

A function may call a list function such as append recursively. We know that this would make the function O(n^2). If |hello counter| is being used to approximate Big-O, it would not reflect the time used for append. In order to avoid this, append would need to be redefined so that it increments the counter (example). Since there are a good portion of list functions, it's left up to the tutor implementing this to redefine any of the list functions they feel would be used by students on the particular assignment.

-- SteveT - 21 Apr 2009