Programming Praxis

Bentley wrote in C and used an execution-count profiler that counted the number of times each statement in his program was executed. Scheme provides no standard profiler, so we have to build our own. Ours is very simple: it provides calling counts of functions that are made known to the profiler. We begin with a global variable to hold the profile counts and a function to reset it when desired:

(define *profile* (list))

(define (reset-profile)
  (set! *profile* (list)))

The heart of our profiler is syntax that replaces the normal define syntax with a profiling version. Each time a profiled function is called its name is consed onto the *profile list:

(define-syntax define-profiling
  (syntax-rules ()
    ((_ (name args ...) body ...)
      (define (name args ...)
        (begin
          (set! *profile*
            (cons 'name *profile*))
          body ...)))))

Then it’s easy to compute function-call counts:

(define (profile)
  (uniq-c string=?
    (sort string
      (map symbol->string *profile*))))

And that’s it. I said it was simple. Let’s use our profiler to recreate Bentley’s column, which is built on a function to determine if a number is prime:

(define-profiling (divides? d n)
 &nbsp(zero? (modulo n d)))

(define-profiling (prime? n)
  (let loop ((d 2))
    (cond ((= d n) #t)
          ((divides? d n) #f)
          (else (loop (+ d 1))))))

(define-profiling (prime-pi n)
  (let loop ((k 2) (pi 0))
    (cond ((< n k) pi)
          ((prime? k) (loop (+ k 1) (+ pi 1)))
          (else (loop (+ k 1) pi)))))

We organize our program a little bit differently than Bentley. Since we can only count function calls, not individual expressions, we separate the trial division into its own function. And we count the primes instead of making a list of them. Here’s what it looks like:

> (prime-pi 1000)
168
> (profile)
(("divides?" . 78022) ("prime-pi" . 1) ("prime?" . 999))

It’s good that our counts agree to Bentley’s. Now we make the change that Bentley made, testing divisors only to the square root of n:

(define-profiling (prime? n)
  (let loop ((d 2))
    (cond ((< (sqrt n) d) #t)
          ((divides? d n) #f)
          (else (loop (+ d 1))))))

> (reset-profile)
> (prime-pi 1000)
168
> (profile)
(("divides?" . 5288) ("prime-pi" . 1) ("prime?" . 999))

Again, our counts agree to Bentley’s. Bentley goes on, but we’ll stop here. We used uniq-c from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/d2S4qU1V.

Pages: 1 2