3 ;;;; Copyright (C) 1996, 2001, 2006 Free Software Foundation, Inc.
5 ;;;; This library is free software; you can redistribute it and/or
6 ;;;; modify it under the terms of the GNU Lesser General Public
7 ;;;; License as published by the Free Software Foundation; either
8 ;;;; version 3 of the License, or (at your option) any later version.
10 ;;;; This library is distributed in the hope that it will be useful,
11 ;;;; but WITHOUT ANY WARRANTY; without even the implied warranty of
12 ;;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 ;;;; Lesser General Public License for more details.
15 ;;;; You should have received a copy of the GNU Lesser General Public
16 ;;;; License along with this library; if not, write to the Free Software
17 ;;;; Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
21 (define-module (ice-9 poe)
22 :use-module (ice-9 hcons)
23 :export (pure-funcq perfect-funcq))
30 ;;; A pure function (of some sort) is characterized by two equality
31 ;;; relations: one on argument lists and one on return values.
32 ;;; A pure function is one that when applied to equal arguments lists
33 ;;; yields equal results.
35 ;;; If the equality relationship on return values can be eq?, it may make
36 ;;; sense to cache values returned by the function. Choosing the right
37 ;;; equality relation on arguments is tricky.
43 ;;; The simplest case of pure functions are those in which results
44 ;;; are only certainly eq? if all of the arguments are. These functions
45 ;;; are called "pure-funcq", for obvious reasons.
49 (define funcq-memo (make-weak-key-hash-table 523)) ; !!! randomly selected values
50 (define funcq-buffer (make-gc-buffer 256))
52 (define (funcq-hash arg-list n)
53 (let ((it (let loop ((x 0)
57 (loop (logior x (hashq (car arg-list) 4194303))
61 ;; return true if lists X and Y are the same length and each element is `eq?'
62 (define (eq?-list x y)
67 (eq?-list (cdr x) (cdr y)))))
69 (define (funcq-assoc arg-list alist)
72 (if (eq?-list arg-list (caar alist))
74 (funcq-assoc arg-list (cdr alist)))))
78 (define (pure-funcq base-func)
80 (let ((cached (hashx-get-handle funcq-hash funcq-assoc funcq-memo (cons base-func args))))
83 (funcq-buffer (car cached))
86 (let ((val (apply base-func args))
87 (key (cons base-func args)))
89 (hashx-set! funcq-hash funcq-assoc funcq-memo key val)
96 ;;; A pure funq may sometimes forget its past but a perfect
100 (define (perfect-funcq size base-func)
101 (define funcq-memo (make-hash-table size))
104 (let ((cached (hashx-get-handle funcq-hash funcq-assoc funcq-memo (cons base-func args))))
107 (funcq-buffer (car cached))
110 (let ((val (apply base-func args))
111 (key (cons base-func args)))
113 (hashx-set! funcq-hash funcq-assoc funcq-memo key val)