Implementation of LRU Cache in Scheme

lrucache.scm

;; LRU Cache Implementation
;; New items are added to the end and old items removed from the start.
;; Try running it at https://repl.it/languages/scheme

;; make-lru-cache: returns procedure with access to cache procedures
;; [arg] maxlen: maximum length of the cache
(define (make-lru-cache maxlen)
  
  ;; cache is initialized as empty list
  ;; first elem is actual cache, second elem is pointer to end of cache
  (let ((cache (cons '() '())))

    ;; check if the cache is empty
    (define (empty-queue?) 
      (null? (car cache)))

    ;; insert: adds a value to the cache
    ;; [arg] val: value to add
    (define (insert val)
      (display "inserting: ")(display val)
      (newline)
      
      ;; we actually add a pair of value and pointer to an empty list
      (let ((new-pair (cons val '())))
           
        ;; if cache is empty, set both cache and pointer to new value
        (cond ((empty-queue?)
               (begin
                (set-car! cache new-pair)
                (set-cdr! cache new-pair)
                cache))
              (else 
                (begin
                  
                 ;; check if value exists; if so, remove it
                 (search val)
                 
                 ;; if queue is at max length, remove first item
                 ;; either way, add new value to end and to pointer
                 (if (= (length (car cache)) maxlen)
                  (begin
                   (set-car! cache (cdr (car cache)))
                   (set-cdr! (cdr cache) new-pair)
                   (set-cdr! cache new-pair)
                   cache)
                  (begin
                   (set-cdr! (cdr cache) new-pair)
                   (set-cdr! cache new-pair)
                   cache)))))))

    ;; search: if value is in cache, remove it
    ;; [arg] val: value to remove
    (define (search val)
      
      (define (search-recur lst)
        (cond ((null? lst) '())
              ((null? (cdr lst)) '())
              ;; if the 2nd term matches
              ((eq? (car (cdr lst)) val)
                    (if (null? (cddr lst))
                        ;; if 2nd term is last term, replace 2nd term with 3rd term (null)
                        ;; and update pointer to end of cache
                        (begin 
                          (display "already in cache!")(newline)
                          (set-cdr! lst (cddr lst))
                          (set-cdr! cache lst)
                          cache)
                        ;; else, just replace 2nd term with 3rd term
                        ;; (pointer to end of cache still valid)
                        (begin 
                          (display "already in cache!")(newline)
                          (set-cdr! lst (cddr lst))
                          cache)))
                        
              ;; repeat starting with second term
              (else (search-recur (cdr lst)))))
            
      (if (eq? (car (car cache)) val)
          (begin 
            (display "already in cache!")(newline)
            (set-car! cache (cdr (car cache))))
          (search-recur (car cache))))
    
    ;; print: function to display cache
    (define (print)
      (display "current cache: ")(display cache)
      (newline)
      (newline))
      
    ;; dispatch: helper function to facilitate message passing
    ;; [arg] m: message with function to call
    (define (dispatch m)
      (cond ((eq? m 'insert) insert)
            ((eq? m 'print) print)
            (else (error "invalid message" m))))
          
    dispatch))
  
;; Usage and Tests
;; Define a new procedure as an instance of make-lru-cache.
;; Call the instance with messages to invoke private procedures.
(define mycache (make-lru-cache 4))
((mycache 'insert) 'a)
((mycache 'insert) 'b)
((mycache 'insert) 'c)
((mycache 'insert) 'd)
((mycache 'insert) 'e)
((mycache 'insert) 'c)
((mycache 'insert) 'd)
((mycache 'print))

(define mycache (make-lru-cache 6))
((mycache 'insert) 3)
((mycache 'insert) 4)
((mycache 'insert) 6)
((mycache 'insert) 4)
((mycache 'insert) 8)
((mycache 'insert) 5)
((mycache 'insert) 7)
((mycache 'insert) 8)
((mycache 'insert) 1)
((mycache 'print))

(define mycache (make-lru-cache 2))
((mycache 'insert) 'a)
((mycache 'insert) 'b)
((mycache 'insert) 'a)
((mycache 'insert) 'a)
((mycache 'insert) 'c)
((mycache 'print))