implementation idea for infinite cons lists aka scon(e)s lists.

implementation idea for infinite cons lists aka scon(e)s lists.

[Stefan Israelsson Tampe]

[-- Attachment #1: Type: text/plain, Size: 2884 bytes --]

#|
Basically a stream is
[x,y,z,...]

But we want to gc the tail of the stream if not reachable. How to do this?

Well consider a cons cell of
[tag,car,cdr]

and that the tag can be marked or not just as with the marking of
guile-log's
logical variables.

The technique to create persistant parts of the list is to just reference
the head of the part
under analysis. Then the tail of that is never reclaimed. This is a simple
version of gc-able
lists. Better versions might exists. But hey let's have fun ....
|#


;; This is a referetial structure, but it will not gc the end
(define id->data (make-weak-key-hash-table))

(define (new-cstream)
  (cons (cons 0 '()) (vector (cons 'cstream-id '()) '() '())))
(define (cstream-i       cs) (caar   cs))
(define (cstream-data    cs) (cdar  cs))
(define (cstream-id      cs) (vector-ref (cdr cs) 0))
(define (cstream-backlog cs) (vector-ref (cdr cs) 1))
(define (cstream-logback cs) (vector-ref (cdr cs) 2))
(define (update-cstream cs a b c d)
  (cons (cons a b) (vector (cstream-id cs) c d)))
(define (hash-new-cstream cs)
  (hashq-set! id->data (cstream-id cs) cs))

(define-syntax-rule (increment-cstream-count cstream val)
  (cons (cons (+ 1 (cstream-i cstream))
      (c-ref (scons val (c-unref (cstream-data cstream)))))
(cdr cstream)))

(define (update cstream val)
  (let ((i (cstream-i cstream)))
    (if (> i 30)
(let ((data    (c-ref (scons val (c-unref (cstream-data cstream)))))
      (backlog (cons data (cstream-backlog cstream)))
      (logback (cstream-logback cstream)))
  (hash-new-cstream
     (if (null? logback)
       (updtate-cstream cstream 0 data '() (cdr (reverse backlog)))
       (updtate-cstream cstream 0 data backlog (cdr logdata)))))
(increment-cstream-count cstream))))

(define (get-cstream-data cstream) (cstream-data cstream))

;; This is executed after the mark phase assuming the gc hack!
(define (sweep)
  (hash-for-each id->data
    (lambda (id cs)
      (let* ((data (cstream-data cs))
     (lb   (cstream-logback cs))
     (lb   (if (pair? lb) (car lb) '())))
(let lp ((d data))
  (if (eq? d lb)
      (let lp ((d d))
(if (and (pair? d) (marked-bit? d))
    (lp (cdr d))
    (if (pair? d)
(set-cdr! d '()))))
      (lp (cdr d))))))))

;; we have a WMARK procedure and a normal MARK procedure. WMARK will not set
;; the IS_MARKED bit of the containing scons, but that is what MARK will do
;; that is the normal marking procedure in the modded bdw-gc

;; c-ref makes a reference that is a box that will make sure that we WMARK
;; the scons list and c-unref will unbox the value

;; What is needed is special mark procedures
#|
Here is the schematic of the C mark procedures.
mark_scons(scm s)
{
 SCM tag = s[0];
 SCM x1  = s[1];
 SCM x2  = s[2];

 if(IS_MARKED(tag))
    MARK(x1)
    MARK(x2);
 else
    MARK(x1)
    WMARK(x2)
}

mark_ref(scm s)
{
 SCM tag = s[0]:
 SCM d   = s[1];
 WMARK(d);
}
|#

[-- Attachment #2: Type: text/html, Size: 5175 bytes --]