From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Stefan Israelsson Tampe Newsgroups: gmane.lisp.guile.devel,gmane.lisp.guile.user Subject: implementation idea for infinite cons lists aka scon(e)s lists. Date: Wed, 10 Sep 2014 22:10:27 +0200 Message-ID: NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary=089e0158be6a9fb4c10502bba404 X-Trace: ger.gmane.org 1410379848 19847 80.91.229.3 (10 Sep 2014 20:10:48 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 10 Sep 2014 20:10:48 +0000 (UTC) To: guile-devel , "guile-user@gnu.org" Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Wed Sep 10 22:10:41 2014 Return-path: Envelope-to: guile-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1XRoDw-00008t-Hy for guile-devel@m.gmane.org; Wed, 10 Sep 2014 22:10:40 +0200 Original-Received: from localhost ([::1]:58455 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XRoDv-0005uv-W5 for guile-devel@m.gmane.org; Wed, 10 Sep 2014 16:10:39 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:43251) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XRoDq-0005sn-6I for guile-devel@gnu.org; Wed, 10 Sep 2014 16:10:35 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1XRoDo-0005a1-QM for guile-devel@gnu.org; Wed, 10 Sep 2014 16:10:34 -0400 Original-Received: from mail-pd0-x233.google.com ([2607:f8b0:400e:c02::233]:48399) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XRoDk-0005Yu-Tl; Wed, 10 Sep 2014 16:10:29 -0400 Original-Received: by mail-pd0-f179.google.com with SMTP id g10so12878109pdj.24 for ; Wed, 10 Sep 2014 13:10:27 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:date:message-id:subject:from:to:content-type; bh=yTyr1zy8Y9qeW0lXe6R0027oMRjEEeMp/xUt7MMP3TA=; b=sBdC+kmD511Zz6lkjxu4+4LAF4Ld5Xnfs2eqVTYZR0MgNEIyoX/QIWwDV2DQa+E/hP g6PyZp9xEvtgULHLTH2iMAKqcLyy8f2Y6yEPaFpBwkgkkFbDVKFPVRezsu5SeS/FRtKO pZrW5z052U4XRbrpqrdvSFwjtVqK6oagT7ZbdekNacQP9P7nkdpJECEgnQds0TYWrveP tEfMdLv4sTQkvXXWyZ2dWbSw5Y2KorKsU3AQHlSJaNjcFdf3t0LJjrKvmPA7rBfjRUUp 4H3ser5/3wxZY9EbamyC+sjk8TEiCY1x4tiZ91NeNrS8Y7d/Ml4TISZsrAgVzIUamzRo tqQw== X-Received: by 10.70.61.10 with SMTP id l10mr7574420pdr.154.1410379827620; Wed, 10 Sep 2014 13:10:27 -0700 (PDT) Original-Received: by 10.70.36.48 with HTTP; Wed, 10 Sep 2014 13:10:27 -0700 (PDT) X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-Received-From: 2607:f8b0:400e:c02::233 X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: "Developers list for Guile, the GNU extensibility library" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Original-Sender: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.lisp.guile.devel:17438 gmane.lisp.guile.user:11493 Archived-At: --089e0158be6a9fb4c10502bba404 Content-Type: text/plain; charset=UTF-8 #| 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); } |# --089e0158be6a9fb4c10502bba404 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
#|
Basically a stream is
[x,y,z,.= ..]

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

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

and that the tag c= an be marked or not just as with the marking of guile-log's=C2=A0
=
logical variables.

The technique to create pe= rsistant parts of the list is to just reference the head of the part
<= div>under analysis. Then the tail of that is never reclaimed. This is a sim= ple version of gc-able
lists. Better versions might exists. But h= ey 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) =C2=A0 =C2=A0=C2=A0
=C2=A0 (cons (cons 0 &#= 39;()) (vector (cons 'cstream-id '()) '() '())))
= (define (cstream-i =C2=A0 =C2=A0 =C2=A0 cs) (caar =C2=A0 cs))
(de= fine (cstream-data =C2=A0 =C2=A0cs) (cdar =C2=A0cs))
(define (cst= ream-id =C2=A0 =C2=A0 =C2=A0cs) (vector-ref (cdr cs) 0))
(define = (cstream-backlog cs) (vector-ref (cdr cs) 1))
(define (cstream-lo= gback cs) (vector-ref (cdr cs) 2))
(define (update-cstream cs a b= c d)
=C2=A0 (cons (cons a b) (vector (cstream-id cs) c d)))
(define (hash-new-cstream cs)
=C2=A0 (hashq-set! id->dat= a (cstream-id cs) cs))

(define-syntax-rule (increm= ent-cstream-count cstream val)
=C2=A0 (cons (cons (+ 1 (cstream-i= cstream))
= =C2=A0 =C2=A0 =C2=A0(c-ref (scons val (c-unref (cstream-data cstream)))))
(cdr cstream)))=

(define (update cstream val)
=C2=A0 (le= t ((i (cstream-i cstream)))
=C2=A0 =C2=A0 (if (> i 30)
(let ((data =C2=A0 = =C2=A0(c-ref (scons val (c-unref (cstream-data cstream)))))
=C2=A0 =C2=A0 =C2=A0(backlog= (cons data (cstream-backlog cstream)))
=C2=A0 =C2=A0 =C2=A0(logback (cstream-logback cs= tream)))
=C2= =A0(hash-new-cstream
= =C2=A0 =C2=A0 (if (null? logback)
=C2=A0 =C2=A0 =C2=A0 (updtate-cstream cstream= 0 data '() (cdr (reverse backlog)))
=C2=A0 =C2=A0 =C2=A0 (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 ha= ck!
(define (sweep)
=C2=A0 (hash-for-each id->data
=C2=A0 =C2=A0 (lambda (id cs)
=C2=A0 =C2=A0 =C2=A0 (let*= ((data (cstream-data cs))
=C2=A0 =C2=A0 (lb =C2=A0 (cstream-logback cs))
=C2=A0 =C2=A0 (lb =C2=A0 (i= f (pair? lb) (car lb) '())))
(let lp ((d data))
=C2=A0(if (eq? d lb)
=C2=A0 =C2=A0 =C2=A0(let lp ((d d))
<= div> (if (and (pair? d) = (marked-bit? d))
=C2=A0 =C2=A0(lp (cdr d))
=C2=A0 =C2=A0(if (pair? d)
(set-cdr! d '()))))
=C2=A0 =C2=A0 =C2=A0(lp (cdr d= ))))))))

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

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

<= div>;; What is needed is special mark procedures
#|
Her= e is the schematic of the C mark procedures.
mark_scons(scm s)
{
=C2=A0SCM tag =3D s[0];
=C2=A0SCM x1 =C2=A0= =3D s[1];
=C2=A0SCM x2 =C2=A0=3D s[2];

= =C2=A0if(IS_MARKED(tag))
=C2=A0 =C2=A0 MARK(x1)
=C2=A0 = =C2=A0 MARK(x2);
=C2=A0else
=C2=A0 =C2=A0 MARK(x1)
=C2=A0 =C2=A0 WMARK(x2)
}

mark_ref= (scm s)
{
=C2=A0SCM tag =3D s[0]:
=C2=A0SCM d= =C2=A0 =3D s[1];
=C2=A0WMARK(d);
}
|# =C2=A0=C2=A0

--089e0158be6a9fb4c10502bba404--