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 Subject: Re: Growable arrays? Date: Mon, 11 Jun 2012 17:24:45 +0200 Message-ID: References: <87hauku0mb.fsf@fencepost.gnu.org> <87fwa2dxmh.fsf@pobox.com> <87mx4aqijf.fsf@fencepost.gnu.org> <87zk8accoq.fsf@pobox.com> <87ehpmqcs7.fsf@fencepost.gnu.org> <87aa0aqc6y.fsf@fencepost.gnu.org> <8762ayqbus.fsf@fencepost.gnu.org> <87oboqorr2.fsf@fencepost.gnu.org> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary=14dae9340d8b2e951904c233f31e X-Trace: dough.gmane.org 1339428323 19604 80.91.229.3 (11 Jun 2012 15:25:23 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Mon, 11 Jun 2012 15:25:23 +0000 (UTC) Cc: guile-devel@gnu.org To: David Kastrup Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Mon Jun 11 17:25:20 2012 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 1Se6UT-0001mI-M9 for guile-devel@m.gmane.org; Mon, 11 Jun 2012 17:25:13 +0200 Original-Received: from localhost ([::1]:58933 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Se6UT-0000yo-H1 for guile-devel@m.gmane.org; Mon, 11 Jun 2012 11:25:13 -0400 Original-Received: from eggs.gnu.org ([208.118.235.92]:60075) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Se6UK-0000vS-VP for guile-devel@gnu.org; Mon, 11 Jun 2012 11:25:11 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1Se6UE-00083q-B3 for guile-devel@gnu.org; Mon, 11 Jun 2012 11:25:04 -0400 Original-Received: from mail-gg0-f169.google.com ([209.85.161.169]:36830) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Se6U5-00081R-Qb; Mon, 11 Jun 2012 11:24:49 -0400 Original-Received: by ggm4 with SMTP id 4so3103192ggm.0 for ; Mon, 11 Jun 2012 08:24:46 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=6y+gbGuSOylq1bqSGzBQUpkkw/u+wtfmST36OQEhX/I=; b=QD6LYjVDhRssX9cJuVS8uOM1rq4Kh4nE4SZV/LBxpUgGSq/Y+R5GqQMePgmvPxKHB0 n1NlsT7Ism0l9Q3ECq5Spl/YoCnOH0x1hCJfnmKzMRN3CaKcJ8MnPlAlteRY6pfXAVDJ TGT3njh1T06WLarl6excwLjbjXsjhCMMYyF7Wk038HaBcIHr2jBq8qigUD+3krEWy7Vj gzcaZjtdTVUHunQSrh5UG+jkMKwpPgHvztwvcWBXXpjSlPKdO+hsUI8vTl90Okyc4338 V2isMmN1hv/WPDzXmve8k/2QQ5dgxtBrCidRI5FlEC3KZQQF98/16BTOTIqBKcOwdT2Q 9xUQ== Original-Received: by 10.50.185.163 with SMTP id fd3mr6720285igc.22.1339428285879; Mon, 11 Jun 2012 08:24:45 -0700 (PDT) Original-Received: by 10.50.109.166 with HTTP; Mon, 11 Jun 2012 08:24:45 -0700 (PDT) In-Reply-To: <87oboqorr2.fsf@fencepost.gnu.org> X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 209.85.161.169 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:14602 Archived-At: --14dae9340d8b2e951904c233f31e Content-Type: multipart/alternative; boundary=14dae9340d8b2e951504c233f31c --14dae9340d8b2e951504c233f31c Content-Type: text/plain; charset=ISO-8859-1 Maybe this could be a first stub for a table structure that is uses both an array and a hash-table. I do think that implementing this might need fine tuning in order to have good defaults and so on. So in that sense one probably need to check out reference implementations. But this is for discussion! I Assumed growing here and have no shrinking! I made it nonfunctional. One note to the discussion. It is not just to combine a growable vector with a growable hash in ordder to have a one tool for all cases. The reason is that one need to tackle the issue with sparse tables with integer keys. I tried to add that feature as well in some way. Anyway it shows that you don't need a ton of code to get something pretty functional. On Mon, Jun 11, 2012 at 4:19 PM, David Kastrup wrote: > Daniel Hartwig writes: > > > On 11 June 2012 20:20, David Kastrup wrote: > >>> P.S.: I still need to look at vlists. They might already address this > >>> issue, though I can't use them in Guile 1.8. > >> > >> No, the "immutable" angle would make them unsuitable again. > > > > Note that vlists are only immutable in the sense that you can not > > modify the value of a slot already allocated. > > Which makes it useless here. > > >> Scheme/Guile vectors are fixed size. Now I have a situation where I > >> have a basic type lattice with records stored in vectors, and this type > >> lattice may be extended dynamically (which typically happens at the > >> start of a whole file, for potentially multi-file runs). > > > > From this I gather that your use case only appends to the lattice, if > > so, vlist is suitable for that task. > > Wrong. My use case only _allocates_ at the end of the existing type > lattice, but the records are not read-only. > > >> Cough, cough. Standard vectors are not growable. Which is the > >> original problem of this thread, never mind Lua. > > > > True, but a growable vector is a tiny step away from the standard > > vector. > > A tiny step if you are modifying the C code. A not so tiny step if you > are working with Scheme. > > >> hashtables have additional indirection > >> through hash buckets and coalescing lists > > > > This is fairly standard for a hash table. I would be quite surprised > > if the hash table part of a Lua table did not also use buckets. > > But it is not standard for a growable vector that it only comes with > buckets and chains. > > >> Except that this one isn't. > > > > Why not? > > > > You take a vector and a hash table, store your values in them, and > > grow either as needed. This is not a complicated type. > > Except that vectors don't grow. Are you even reading what you are > replying to? > > -- > David Kastrup > > > --14dae9340d8b2e951504c233f31c Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Maybe this could be a first stub for a table structure that is uses both an=
array and a hash-table. I do think that implementing this might need fi= ne tuning in order
to have good defaults and so on. So in that sense one= probably need to check out reference
implementations. But this is for discussion!

I Assumed growing here = and have no shrinking!

I made it nonfunctional.

One note to t= he discussion. It is not just to combine a growable vector with a growable = hash
in ordder to have a one tool for all cases. The reason is that one need to = tackle the issue with sparse tables with integer keys. I tried to add that = feature as well in some way.

Anyway it shows that you don't need= a ton of code to get something pretty functional.


On Mon, Jun 11, 2012 at 4:19 PM, David K= astrup <dak@gnu.org> wrote:
Daniel Hartwig <m= andyke@gmail.com> writes:

> On 11 June 2012 20:20, David Kastrup <dak@gnu.org> wrote:
>>> P.S.: I still need to look at vlists. =A0They might already ad= dress this
>>> =A0 =A0 =A0 issue, though I can't use them in Guile 1.8. >>
>> No, the "immutable" angle would make them unsuitable aga= in.
>
> Note that vlists are only immutable in the sense that you can not
> modify the value of a slot already allocated.

Which makes it useless here.

>> Scheme/Guile vectors are fixed size. =A0Now I have a situation whe= re I
>> have a basic type lattice with records stored in vectors, and this= type
>> lattice may be extended dynamically (which typically happens at th= e
>> start of a whole file, for potentially multi-file runs).
>
> From this I gather that your use case only appends to the lattice, if<= br> > so, vlist is suitable for that task.

Wrong. =A0My use case only _allocates_ at the end of the existing typ= e
lattice, but the records are not read-only.

>> Cough, cough. =A0Standard vectors are not growable. =A0Which is th= e
>> original problem of this thread, never mind Lua.
>
> True, but a growable vector is a tiny step away from the standard
> vector.

A tiny step if you are modifying the C code. =A0A not so tiny step if= you
are working with Scheme.

>> hashtables have additional indirection
>> through hash buckets and coalescing lists
>
> This is fairly standard for a hash table. =A0I would be quite surprise= d
> if the hash table part of a Lua table did not also use buckets.

But it is not standard for a growable vector that it only comes with<= br> buckets and chains.

>> Except that this one isn't.
>
> Why not?
>
> You take a vector and a hash table, store your values in them, and
> grow either as needed. =A0This is not a complicated type.

Except that vectors don't grow. =A0Are you even reading what you = are
replying to?

--
David Kastrup



--14dae9340d8b2e951504c233f31c-- --14dae9340d8b2e951904c233f31e Content-Type: application/octet-stream; name="hasharray.scm" Content-Disposition: attachment; filename="hasharray.scm" Content-Transfer-Encoding: base64 X-Attachment-Id: f_h3bp4l1x0 KHVzZS1tb2R1bGVzIChzcmZpIHNyZmktMTEpKQoKKGRlZmluZSAobWFrZS10YWJsZSkKICAobGlz dCAxMCAobWFrZS12ZWN0b3IgMTAgI2YpIChtYWtlLWhhc2gtdGFibGUpKSkKCihkZWZpbmUgdGFi bGUtcmVmIAogIChjYXNlLWxhbWJkYQogICAgKCh0YiB4KSAodGFibGUtcmVmIHRiIHggI2YpKQog ICAgKCh0YiB4IGZhaWwpCiAgICAgKGlmIChpbnRlZ2VyPyB4KQogICAgICAgICAobGV0ICgociAo dmVjdG9yLXJlZiAoY2FkciB0YikgKG1vZHVsbyB4IChjYXIgdGIpKSkpKQogICAgICAgICAgIChp ZiByCiAgICAgICAgICAgICAgIChpZiAoPSAoY2FyIHIpIHgpIAogICAgICAgICAgICAgICAgICAg KGNkciByKQogICAgICAgICAgICAgICAgICAgZmFpbCkKICAgICAgICAgICAgICAgZmFpbCkpCiAg ICAgICAgIChoYXNoLXJlZiAoY2FkZHIgdGIpIHggZmFpbCkpKSkpCgooZGVmaW5lIChtYWtlLWxh cmdlciB2ZWMgbikKICAobGV0IGxvb3AgKChuMiAoKiBuIDIpKSkKICAgIChsZXQgKCh2ZWMyICAo bWFrZS12ZWN0b3IgbjIgI2YpKSkKICAgICAgKGxldCBsb29wMiAoKGkgMCkpCiAgICAgICAgKGlm ICg8IGkgbikKICAgICAgICAgICAgKGxldCAoKHIgKHZlY3Rvci1yZWYgdmVjIGkpKSkKICAgICAg ICAgICAgICAoaWYgcgogICAgICAgICAgICAgICAgICAobGV0ICgocjIgKHZlY3Rvci1yZWYgdmVj MiAobW9kdWxvIChjYXIgcikgbjIpKSkpCiAgICAgICAgICAgICAgICAgICAgKGlmIHIyIAogICAg ICAgICAgICAgICAgICAgICAgICAobG9vcCAoKiAyIG4yKSkKICAgICAgICAgICAgICAgICAgICAg ICAgKGJlZ2luCiAgICAgICAgICAgICAgICAgICAgICAgICAgKHZlY3Rvci1zZXQhIHZlYzIgKG1v ZHVsbyAoY2FyIHIpIG4yKSByKQogICAgICAgICAgICAgICAgICAgICAgICAgIChsb29wMiAoKyBp IDEpKSkpKQogICAgICAgICAgICAgICAgICAobG9vcDIgKCsgaSAxKSkpKQogICAgICAgICAgICAo dmFsdWVzIHZlYzIgbjIpKSkpKSkKCihkZWZpbmUgKHRhYmxlLXNldCEgdGIgayB2KQogIChpZiAo aW50ZWdlcj8gaykKICAgICAgKGxldCAoKHZlYyAoY2FkciB0YikpCiAgICAgICAgICAgIChuICAg KGNhciAgdGIpKSkKICAgICAgICAobGV0ICgociAodmVjdG9yLXJlZiB2ZWMgKG1vZHVsbyBrIG4p KSkpCiAgICAgICAgICAoaWYgcgogICAgICAgICAgICAgIChpZiAoPSAoY2FyIHIpIGspCiAgICAg ICAgICAgICAgICAgIChzZXQtY2RyISByIHYpCiAgICAgICAgICAgICAgICAgIChsZXQtdmFsdWVz ICgoKHZlYzIgbjIpIChtYWtlLWxhcmdlciB2ZWMgbikpKQogICAgICAgICAgICAgICAgICAgIChz ZXQtY2FyISB0YiAgbjIpCiAgICAgICAgICAgICAgICAgICAgKHNldC1jYXIhIChjZHIgdGIpIHZl YzIpCiAgICAgICAgICAgICAgICAgICAgKHRhYmxlLXNldCEgdGIgayB2KSkpCiAgICAgICAgICAg ICAgKHZlY3Rvci1zZXQhIHZlYyAobW9kdWxvIGsgbikgKGNvbnMgayB2KSkpKSkKICAgICAgKGhh c2gtc2V0ISAoY2FkZHIgdGIpIGsgdikpKQogICAgICAgICAgICAgICAgICAgIAogICAgICAgICAg ICAgICAgICAgCg== --14dae9340d8b2e951904c233f31e--