Использование определенной процедуры в качестве аргумента дает другой результат, чем использование лямбда-выражения в качестве аргумента.

Проблема в том, что в вашей первой функции вы рекурсивно вызываете не запомненную версию фибоначчи, а не запомненную версию fib. Чтобы обойти это, можно было бы определить fib следующим образом:

(define (fib n)
    (display "computing fib of ")
    (display n) (newline)
    (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (mem-fib (- n 1)) ;; Notice we're calling the memoized version here
                (mem-fib (- n 2))))))
(define mem-fib (memoize fib))

Возможно, лучшим способом было бы сделать следующее:

(define (fib n)
    (display "computing fib of ")
    (display n) (newline)
    (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1)) ;; Notice we're calling the NON-memoized version here
                (fib (- n 2))))))
(set! fib (memoize fib)) ;; but we redefine fib to be memoized

Это означает, что мы используем только одно имя, и оно запоминается. Нет хорошего способа иметь обе версии, но если вы хотите, вот один из способов сделать это (если вы хотите сравнить производительность или что-то в этом роде):

(define (fib n)
    (display "computing fib of ")
    (display n) (newline)
    (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (mem-fib (- n 1)) ;; Notice we're calling the memoized version here
                (mem-fib (- n 2))))))
(define mem-fib (memoize fib))
(set! fib (lambda (n)
    (display "computing fib of ")
    (display n) (newline)
    (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1)) ;; Notice we're calling the NON-memoized version here
                (fib (- n 2)))))))

Вот альтернативный подход к этой проблеме. Это в Racket, а не в Scheme, за что я извиняюсь (это может быть Scheme, за исключением того, что я не знаю, как хеш-таблицы работают в Scheme).

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

(define (memoize f (table (make-hasheqv)))
  ;; Memoize a function on its first argument.
  ;; table, if given, should be a mutable hashtable
  (λ (k . more)
    ;; hash-ref! looks up k in table, and if it is not there
    ;; sets it to be the result of calling the third argument (or
    ;; to the third argument if it's not callable).  thunk just makes
    ;; a function of no arguments.
    (hash-ref! table k
               (thunk (apply f k more)))))

Теперь вот в чем хитрость: вместо того, чтобы определять fib как рекурсивную функцию, мы определяем fib/c как не-рекурсивную функцию, которая знает, как выполнить один шаг вычисления ряда Фибоначчи, и обращается к другой функции, чтобы выполнить отдых. Он также сообщает вам, что он делает, как и ваша функция.

(define (fib/c n c)
  ;; fib/c does one step of the fibonacci calculation,
  ;; calling c to do the remaining steps.
  (printf "fib of ~A~%" n)
  (if (<= n 2)
      1
      (+ (c (- n 1) c)
         (c (- n 2) c))))

Основываясь на этом, мы можем очень легко определить fib/u, не запомненную функцию Фибоначчи, которая имеет ужасную производительность, которую вы ожидаете, просто передав саму fib/c в качестве второго аргумента:

(define (fib/u n)
  ;; unmemoized fib
  (fib/c n fib/c))

Но теперь мы можем ее запомнить и определить версию с запоминаниями, fib/m (здесь вы видите, почему мне нужно было memoize, чтобы разрешить более одного аргумента: нам нужно продолжать передавать запомненную функцию вниз:

(define (fib/m n)
  ;; and here's a memoized fib
  (let ((fib/m (memoize fib/c)))
    (fib/m n fib/m)))

А теперь (4 — первый случай, когда они отличаются):

> (fib/u 4)
fib of 4
fib of 3
fib of 2
fib of 1
fib of 2
3
> (fib/m 4)
fib of 4
fib of 3
fib of 2
fib of 1
3

И со снятой печатью:

> (time (fib/u 40))
cpu time: 8025 real time: 7962 gc time: 26
102334155
> (time (fib/m 40))
cpu time: 1 real time: 1 gc time: 0
102334155

Обратите внимание, что такой подход, когда вы пишете нерекурсивную функцию и превращаете ее в рекурсивную, тесно связан с тем, как выполняется вывод Y (хотя обычно они очень строги и настаивают на функциях только с одним аргументом, так что вы получите (λ (f) (λ (n) ... (f ...) ...)), а не (λ (n c) ... (c ...) ...) Оказывается, это довольно полезный трюк.