Передача функции в качестве параметра, но получение неожиданных результатов - PullRequest
Новая
       52

Передача функции в качестве параметра, но получение неожиданных результатов

1 голос
/ 19 января 2011

Я использую Racket с настройкой языка «Advanced Student», и мне трудно пытаться написать функцию, которая принимает функцию, выполняет ее n раз и сообщает о времени, прошедшем для каждого запуска.Это то, что у меня есть. 

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

У меня есть функция с именем fact, которая вычисляет факториал числа. 

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

Если я оцениваю (time (fact 10000))Я получаю разумные результаты для процессора, реального времени и времени, а также большое количество.Все хорошо.

Однако, когда я пытаюсь оценить (many 3 (fact 10000)), я получаю: 

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

Почему функция не оценивает fact несмотря на то, что она передается в качестве параметра?

1 Ответ

5 голосов
/ 19 января 2011

Давайте рассмотрим, что вы many делаете. Сначала вы определили это: 

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

Тогда назовите это: 

> (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
>

Вот что происходит на каждой итерации, когда many вызывает себя рекурсивно: 

(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))]))

Ваше определение many рекурсивно вызывает себя со значением результата первого (time fn) приложения, но это неверно, потому что вы хотите собрать информацию о времени для вашего приложения процедуры, а не значение (значение (add1 41) в нашем случае). Просто замените true на fn в вашем определении many: 

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

и вы получите следующее: 

> (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
>

Вы видите, что fn на каждом рекурсивном вызове равно 42. Это происходит потому, что многие (если не все) языки FP используют Аппликативный порядок оценки, а (add1 41) оценивается до первого вызова many.

Таким образом, мы должны использовать lambda, чтобы функция ( thunk в нашем случае) передавалась многим в качестве второго аргумента (fn). Как вы уже знаете, применение функции в схеме выражается как () вокруг выражения: 

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

Пример вывода: 

> (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
>

Как вы видите выше (fn) выполняет применение результата функции (lambda () (fact 10000) (thunk), time получает именно то, что вы хотели передать (выражение), и отображает правильную информацию о времени.

Надеюсь, это поможет. Поправь меня, если я ошибаюсь.

...