On Lisp, memoize, Y Combinator

memoized-Y.scm

(define memoized-Y
  (let ((cache (make-hash-table 'equal?)))
    (lambda (c)
      ((lambda (f)
         (f f))
       (lambda (g)
         (c (lambda x
              (let ((val (hash-table-get cache x #f)))
                (if val val
                    ((lambda (ret)
                       (hash-table-put! cache x ret)
                       ret)
                     (apply (g g) x)))))))))))

(time ((memoized-Y fib) 2000))
;(time ((memoized-Y fib) 2000))
; real   0.141
; user   0.125
; sys    0.000
6835702259575806647045396549170580107055408029365524565407553367798082454408054014954534318953113802726603726769523447478238192192714526677939943338306101405105414819705664090901813637296453767095528104868264704914433529355579148731044685634135487735897954629842516947101494253575869699893400976539545740214819819151952085089538422954565146720383752121972115725761141759114990448978941370030912401573418221496592822626

pluggable-y.scm

;; pluggable Y Combinator

(define Y
  (lambda (c)
    ((lambda (f)
       (f f))
     (lambda (g)
       (c (lambda x
            (apply (g g) x)))))))

(define (make-memoize)
  (let ((cache (make-hash-table 'equal?)))
    (lambda (f)
      (lambda args
        (let ((val (hash-table-get cache args #f)))
          (or val
              (let ((ret (apply f args)))
                (hash-table-put! cache args ret)
                ret)))))))

(time ((Y (compose (make-memoize) fib)) 35))
;(time ((Y (compose (make-memoize) fib)) 35))
; real   0.000
; user   0.000
; sys    0.000
14930352

(time ((Y (compose (make-memoize) fib)) 2000))
;(time ((Y (compose (make-memoize) fib)) 2000))
; real   0.250
; user   0.219
; sys    0.000
6835702259575806647045396549170580107055408029365524565407553367798082454408054014954534318953113802726603726769523447478238192192714526677939943338306101405105414819705664090901813637296453767095528104868264704914433529355579148731044685634135487735897954629842516947101494253575869699893400976539545740214819819151952085089538422954565146720383752121972115725761141759114990448978941370030912401573418221496592822626

trace.scm

(define (make-trace)
  (lambda (f)
    (lambda (n)
      (format #t "\; call with : ~a\n" n)
      (f n))))

(time ((Y (compose (make-trace) fib)) 5))
;(time ((Y (compose (make-trace) fib)) 5))
; real   0.000
; user   0.000
; sys    0.000
; call with : 5
; call with : 4
; call with : 3
; call with : 2
; call with : 1
; call with : 0
; call with : 1
; call with : 2
; call with : 1
; call with : 0
; call with : 3
; call with : 2
; call with : 1
; call with : 0
; call with : 1
8

(time ((Y (compose (make-memoize)(compose (make-trace) fib))) 5))
;(time ((Y (compose (make-memoize) (compose (make-trace) fib))) 5))
; real   0.000
; user   0.000
; sys    0.000
; call with : 5
; call with : 4
; call with : 3
; call with : 2
; call with : 1
; call with : 0
8

ycombinator5.scm

;; memoized Y Combinator
(define memoized-Y
  (let ((cache (make-hash-table 'equal?))
        (gethash (cut hash-table-get <> <> #f)))
    (lambda (c)
      ((lambda (f)
         (f f))
       (lambda (g)
         (c (lambda x
              (let ((val (gethash cache x)))
                (if val val
                    ((lambda (undef)
                       (gethash cache x))
                     (hash-table-put! cache x (apply (g g) x))))))))))))

(define fib
  (lambda (f)
    (lambda (n)
      (if (< n 2) 1
          (+ (f (- n 1))(f (- n 2)))))))

(time ((Y fib) 30))
;(time ((Y fib) 30))
; real  10.531
; user   9.391
; sys    0.922
1346269

(time ((memoized-Y fib) 30))
;(time ((memoized-Y fib) 30))
; real   0.000
; user   0.000
; sys    0.000
1346269

;(time ((memoized-Y fib) 1000))
; real   0.047
; user   0.031
; sys    0.000
70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501