CODEWITHSUNDEEP
lambdafunctional-programmingschemeracketoperator-precedence
Greenhorn
Greenhorn

Reputation: 411

Passing a function as a parameter but getting unexpected results

I'm using Racket with the "Advanced Student" language setting and I'm having difficulty trying to write a function that takes a function, executes it n times and reports the time elapsed for each run. This is what I've got so far.

(define (many n fn)
  (cond
    [(= n 0) true]
    [else (many (sub1 n) (local ((define k (time fn))) k))]))

I have a function called fact that computes the factorial of a number.

(define (fact n)
  (cond
    [(= 0 n) 1]
    [else (* n (fact (- n 1)))]))

If I evaluate (time (fact 10000)), I get reasonable results for cpu, real and gc time, as well as a large number. All well and good.

However, when I try to evaluate (many 3 (fact 10000)) I get:

cpu time: 0 real time: 0 gc time: 0
cpu time: 0 real time: 0 gc time: 0
cpu time: 0 real time: 0 gc time: 0
true

Why is the function not evaluating fact despite being passed as a parameter?

Upvotes: 1

Views: 2208

Answers (1)

Yasir Arsanukayev
Yasir Arsanukayev

Reputation: 9676

Let's examine what you many does. First you defined it:

(define (many n fn)
  (cond
    [(= n 0) true]
    [else (many (sub1 n) 
                (local ((define k (time fn))) 
                       k))]))

Then call it:

> (many 3 (add1 41))
cpu time: 0 real time: 0 gc time: 0
cpu time: 0 real time: 0 gc time: 0
cpu time: 0 real time: 0 gc time: 0
#t
>

Here what happens on every iteration when many calls itself recursively:

(define (many 3 42)
  (cond
    [(= 3 0) true]
    [else (many (sub1 3) 
                (local ((define k (time 42))) 
                       42))]))

(define (many 2 42)
  (cond
    [(= 2 0) true]
    [else (many (sub1 2) 
                (local ((define k (time 42))) 
                       42))]))

(define (many 1 42)
  (cond
    [(= 1 0) true]
    [else (many (sub1 1) 
                (local ((define k (time 42))) 
                       42))]))

(define (many 0 42)
  (cond
    [(= 0 0) true]
    [else (many (sub1 0) 
                (local ((define k (time 42))) 
                       42))]))

Your definition of many recursively calls itself with the result value of the first (time fn) application, but it is not correct, because you want to collect timing information for your procedure application, not the value (value of (add1 41) in our case). Just substitute true with fn in your definition of many:

(define (many n fn)
  (cond
    [(= n 0) fn]
    [else (many (sub1 n) 
                (local ((define k (time fn))) 
                 k))]))

and you'll get the following:

> (many 3 (add1 41))
cpu time: 0 real time: 0 gc time: 0
cpu time: 0 real time: 0 gc time: 0
cpu time: 0 real time: 0 gc time: 0
cpu time: 0 real time: 0 gc time: 0
42
>

You see that fn on every recursive call equals 42. This happens because many (if not all) FP languages use Applicative order of evaluation, and (add1 41) is evaluated before the first call to many happens.

Thus we have to use lambda to ensure a function (thunk in our case) is passed to many as it's second argument (fn). As you already know function application in Scheme is expressed as () around expression:

(define (many n fn)  
  (time (fn))  
  (if (= n 0) 
      true
      (many (sub1 n) fn)))

Example output:

> (many 3 (lambda () (fact 10000)))
cpu time: 2734 real time: 2828 gc time: 1922
cpu time: 906 real time: 953 gc time: 171
cpu time: 891 real time: 953 gc time: 204
cpu time: 938 real time: 984 gc time: 251
#t
>

As you see above (fn) performs application of the result of function (lambda () (fact 10000) (thunk), time gets exactly what you wanted to pass it (an expression) and displays the correct timing information.

Hope that helps. Correct me if I'm wrong.

Upvotes: 5

Related Questions