[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Stefan Israelsson Tampe
Subject: implementation idea for infinite cons lists aka scon(e)s lists.
Date: Wed, 10 Sep 2014 22:10:27 +0200

Basically a stream is

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

Well consider a cons cell of

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)))
    (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];


mark_ref(scm s)
 SCM tag = s[0]:
 SCM d   = s[1];

reply via email to

[Prev in Thread] Current Thread [Next in Thread]