You can edit this page using wiki syntax for markup.

Article contents:== lru-cache [[toc:]] === Description An LRU (least recently used) cache for Chicken Scheme 5. Keys and values may be of any type. The cache uses a hash table for O(1) lookup and a doubly-linked list to maintain access ordering. When the cache reaches capacity, the least recently used entry is evicted. This implementation shares no lineage with the [[/eggref/4/lru-cache|lru-cache egg]], for Chicken Scheme 4, by Jim Ursetto. === Author Christopher Harrison ([[https://tweag.io|Tweag]]) === Repository [[https://github.com/tweag/lru-cache]] === Requirements * [[/egg/srfi-69|srfi-69]] * [[/egg/matchable|matchable]] === API ==== Cache creation <procedure>(make-lru-cache [capacity])</procedure> Create a new LRU cache. {{capacity}} is the maximum number of entries the cache will hold before evicting the least recently used entry; defaulting to 64. ==== Lookup and mutation <procedure>(lru-cache-ref cache key)</procedure> Returns the value associated with {{key}} in {{cache}}, promoting it to the most recently used position. Signals an error if {{key}} is not present. <procedure>(lru-cache-ref cache key thunk)</procedure> Returns the value associated with {{key}} in {{cache}} if present, promoting it to the most recently used position. If {{key}} is not present, calls {{thunk}} (a procedure of zero arguments) to compute the value, caches the result and returns it. <procedure>(lru-cache-set! cache key value)</procedure> Associates {{key}} with {{value}} in {{cache}}. If {{key}} already exists, updates its value and promotes it to the most recently used position. If {{key}} is new and the cache is at capacity, the least recently used entry is evicted. <procedure>(lru-cache-delete! cache key)</procedure> Removes the entry for {{key}} from {{cache}}. Signals an error if {{key}} is not present. <procedure>(lru-cache-clear! cache)</procedure> Removes all entries from {{cache}}. ==== Inspection <procedure>(lru-cache-size cache)</procedure> Returns the number of entries currently in {{cache}}. <procedure>(lru-cache-capacity cache)</procedure> Returns the maximum number of entries {{cache}} can hold. <procedure>(lru-cache-has-key? cache key)</procedure> Returns {{#t}} if {{key}} is present in {{cache}}, {{#f}} otherwise. Does not affect the access ordering. ==== Iteration <procedure>(lru-cache-for-each cache proc)</procedure> Apply {{proc}} (a procedure of two arguments: the entry key and value, respectively) to each entry in {{cache}}, ordered from most recently used to least recently used. Does not affect the access ordering. '''Note:''' {{proc}} must not mutate {{cache}}. <procedure>(lru-cache-fold cache proc init)</procedure> Calls {{proc}} (a procedure of three arguments: the entry key, value and accumulator, respectively) with each entry in {{cache}}, ordered from most recently to least recently used; the initial folded value is {{init}}, returns the final folded value. Does not affect the access ordering. '''Note:''' {{proc}} must not mutate {{cache}}. <procedure>(lru-cache->alist cache)</procedure> Returns an association list of all key-value pairs in {{cache}}, ordered from most recently used to least recently used. Does not affect the access ordering. <procedure>(lru-cache-keys cache)</procedure> Returns a list of all keys in {{cache}}, ordered from most recently used to least recently used. Does not affect the access ordering. <procedure>(lru-cache-values cache)</procedure> Returns a list of all values in {{cache}}, ordered from most recently used to least recently used. Does not affect the access ordering. ==== Memoisation <syntax>(define-memoised/lru [capacity] (name arg ...) body ...)</syntax> Defines a top-level procedure {{name}}, with its argument list and body definition per usual, but return values are cached based on the arguments (compared as a list). {{capacity}} defaults to 64. <procedure>(memoise/lru proc [capacity])</procedure> Returns a new procedure that caches the results of calling {{proc}}. Arguments are used as the cache key (compared as a list). {{capacity}} defaults to 64. '''Note:''' For recursive procedures, the memoised version must replace the original binding for recursive calls to benefit from caching. It is better to use {{define-memoised/lru}} in such cases, wherever possible. <enscript highlight="scheme"> (define (fib n) (cond ((= n 0) 1) ((= n 1) 1) (else (+ (fib (- n 1)) (fib (- n 2)))))) (set! fib (memoise/lru fib)) </enscript> === Examples <enscript highlight="scheme"> (import lru-cache (chicken format)) ;; Create a cache with capacity 3 (define cache (make-lru-cache 3)) ;; Add some entries (lru-cache-set! cache 'a 1) (lru-cache-set! cache 'b 2) (lru-cache-set! cache 'c 3) (lru-cache-keys cache) ; => (c b a) ;; Accessing an entry promotes it (lru-cache-ref cache 'a) ; => 1 (lru-cache-keys cache) ; => (a c b) ;; Adding a fourth entry evicts the LRU (lru-cache-set! cache 'd 4) (lru-cache-keys cache) ; => (d a c) (lru-cache-has-key? cache 'b) ; => #f ;; Using a thunk for cache-or-compute (lru-cache-ref cache 'e (lambda () (+ 40 2))) ; => 42 ;; Memoisation (define-memoised/lru (fib n) (printf "computing fib ~A~N" n) (cond ((= n 0) 1) ((= n 1) 1) (else (+ (fib (- n 1)) (fib (- n 2)))))) (fib 5) ; prints "computing fib 5" .. "computing fib 0", returns 8 (fib 5) ; returns 8, no printing </enscript> === License LGPL-3.0-or-later === Version history ; 0.1.0 : Initial releaseDescription of your changes:

I would like to authenticate

Spam control

What do you get when you multiply 0 by 1?