* implementation idea for infinite cons lists aka scon(e)s lists.
@ 2014-09-10 20:10 Stefan Israelsson Tampe
0 siblings, 0 replies; only message in thread
From: Stefan Israelsson Tampe @ 2014-09-10 20:10 UTC (permalink / raw
To: guile-devel, guile-user@gnu.org
[-- 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 --]
^ permalink raw reply [flat|nested] only message in thread
only message in thread, other threads:[~2014-09-10 20:10 UTC | newest]
Thread overview: (only message) (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2014-09-10 20:10 implementation idea for infinite cons lists aka scon(e)s lists Stefan Israelsson Tampe
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).