unofficial mirror of guile-user@gnu.org 
 help / color / mirror / Atom feed
* Re: guile-user Digest, Vol 216, Issue 19
       [not found] <mailman.199.1606106579.13151.guile-user@gnu.org>
@ 2020-11-24 21:26 ` Tim Meehan
  2020-11-25 12:16   ` Adriano Peluso
  0 siblings, 1 reply; 3+ messages in thread
From: Tim Meehan @ 2020-11-24 21:26 UTC (permalink / raw)
  To: guile-user

Matt - thanks for the help making the FFI pointers work!

On Sun, Nov 22, 2020 at 10:44 PM <guile-user-request@gnu.org> wrote:

> Send guile-user mailing list submissions to
>         guile-user@gnu.org
>
> To subscribe or unsubscribe via the World Wide Web, visit
>         https://lists.gnu.org/mailman/listinfo/guile-user
> or, via email, send a message with subject or body 'help' to
>         guile-user-request@gnu.org
>
> You can reach the person managing the list at
>         guile-user-owner@gnu.org
>
> When replying, please edit your Subject line so it is more specific
> than "Re: Contents of guile-user digest..."
>
>
> Today's Topics:
>
>    1. Re: Question about data structures (Tim Van den Langenbergh)
>    2. broken link on "Learn" page (Tim Meehan)
>    3. Re: Guile dynamic FFI, C function expecting pointer (Matt Wette)
>    4. Re: Question about data structures (Taylan Kammer)
>    5. Re: Question about data structures (John Cowan)
>
>
> ----------------------------------------------------------------------
>
> Message: 1
> Date: Sun, 22 Nov 2020 23:50:47 +0100
> From: Tim Van den Langenbergh <tmt_vdl@gmx.com>
> To: guile-user@gnu.org
> Subject: Re: Question about data structures
> Message-ID: <4033601.nszuQzh3Xh@terra>
> Content-Type: text/plain; charset="utf-8"
>
> On Sunday, 22 November 2020 19:48:24 CET Zelphir Kaltstahl wrote:
> > Hello Guile Users!
> >
> > I have a question about data structures.
> >
> > Recently I read a file and the lines in the file would become a list in
> > my Guile program. The file was not super big or anything. However, I
> > usually try to avoid having to use `append` or `reverse`, whenever
> > possible, considering, that they are O(n) operations and in principle I
> > do not want to write code, that uses lists in inefficient ways, when
> > there is a more efficient way. That said, I hit a little snag:
> >
> > When I am reading a file and do not know how many lines there are in the
> > file, I can use a normal list and construct it using recursive calls
> > like `(cons line (iter ...))` where `iter` is the recursive call and.
> > Could also be called `process-next-line` or simply `next`. Since I am
> > building a recursive data structure, it is OK to have a non-tail
> > position recursive call. Then I would return that list and work with it.
> > However, what if I ever need to add a list entry and the order of list
> > entry matters? I would either have to use `append`, to add it to the
> > end, which would be O(n), or I would have to initially construct the
> > list of lines in reversed order from initially, so that I can add by
> > simply using `(cons new-entry lines)`. However, when I use the list in
> > reverse and ever need to output the lines in the list in their original
> > order, I would first need to `reverse` the list again.
> >
> > OK the whole reversing would not be a problem, if I used a vector to
> > store the lines. However, then I would need to know the number of lines
> > in the file ahead of time or look at the file once for counting the
> > lines, then create the vector of that length and then store the lines in
> > it. This seems inelegant again, because I look at the lines of the file
> > twice. I could read it in as a list and then use `list->vector`, but
> > that will also be an additional O(n) for converting every entry to
> > vector element.
> >
> > If I now think about Python, then I have Python lists (actually arrays?)
> > and those can be easily appended to in O(1) and random access is also
> > O(1) according to https://wiki.python.org/moin/TimeComplexity. This
> > means I do not need to think much about how I will use the lines of a
> > file, when reading in the file. A Python list will be appropriate.
> >
> > So in Guile I sometimes feel some mental overhead of thinking about the
> > choice of data structure, which I do not feel in Python. Generally I
> > like Guile a lot more, so I would like to know how others deal with
> > this. Here are some ideas for it:
> >
> > 1. I could create some abstraction layer for the "sequence of read
> > lines", which I use inside the procedure, which reads in the lines and
> > all other code, that works with the lines, so that I can rather easily
> > later exchange the data structure. A data abstraction. However, that
> > might only hide the complexities of some operations behind the
> > abstraction and not reduce them.
> >
> > 2. Perhaps I want Guile's arrays? (Can they be expanded in O(1)? I do
> > seem to remember reading, that Guile vectors are only a special case of
> > Guile arrays, so that would mean they are not expandable in O(1).)
> >
> > 3. Just convert list to vector after reading in the file until I hit a
> > problem, where that additional O(n) really becomes a problem. (In my
> > current project it is not realistically a problem.) But this does not
> > satisfy me. I should learn how to solve the problem in general and use
> > the best way to do things.
> >
> > 4. Perhaps I need to write another data structure, that creates a new
> > vector, when the previous one is full, managing the expansion myself.
> >
> > How do you approach this problem? Is it a problem at all?
> >
> > Best regards,
> > Zelphir
> >
> >
>
> Hey Zelphir,
>
> If you want to use a FIFO data structure, you may want to check out queues.
>
> They're already in ice-9, under (ice-9 q).
>
> Mandatory manual reference:
> https://www.gnu.org/software/guile/manual/html_node/Queues.html#Queues
>
> Alternatively, if you want constant-time random access you could try using
> Vlists, although they aren't thread-safe.
>
> https://www.gnu.org/software/guile/manual/html_node/VLists.html#VLists
>
> Finally you could implement either a doubly-linked list or array list type
> depending on your needs.
>
> If I understand your requirements correctly I would recommend queues. They
> are
> easy to work with.
>
> Sincerely yours,
>
> - Tim
> -------------- next part --------------
> A non-text attachment was scrubbed...
> Name: signature.asc
> Type: application/pgp-signature
> Size: 833 bytes
> Desc: This is a digitally signed message part.
> URL: <
> https://lists.gnu.org/archive/html/guile-user/attachments/20201122/ad299977/attachment.sig
> >
>
> ------------------------------
>
> Message: 2
> Date: Sun, 22 Nov 2020 16:56:56 -0600
> From: Tim Meehan <btmeehan@gmail.com>
> To: guile-user@gnu.org
> Subject: broken link on "Learn" page
> Message-ID:
>         <
> CACgrOx+2V+QgP5vezzAxBOngEAr5X0sXLj19XQAswKOr5ZG-8g@mail.gmail.com>
> Content-Type: text/plain; charset="UTF-8"
>
> There is a broken link to the "Internet Scheme Repository" on the "Learn"
> page of the GNU Guile website:
> https://www.gnu.org/software/guile/learn/
>
> I didn't see a contact email on the website, but I figured that someone
> here might know someone that ran the website ... if not, my apologies.
>
>
> ------------------------------
>
> Message: 3
> Date: Sun, 22 Nov 2020 16:16:47 -0800
> From: Matt Wette <matt.wette@gmail.com>
> To: guile-user@gnu.org
> Subject: Re: Guile dynamic FFI, C function expecting pointer
> Message-ID: <da5a069d-d156-6f69-386e-50b9364c7a65@gmail.com>
> Content-Type: text/plain; charset=utf-8; format=flowed
>
>
>
> On 11/22/20 2:50 PM, Tim Meehan wrote:
> > I tried to boil this question down to the most simple thing that
> > represented what I needed to understand. I have had luck getting C
> > functions that expect arguments "by value," but "by reference" has been
> > problematic.
> >
> > The failure mode is "Segmentation Fault," so I gather that I may not be
> > using the right Guile call at all.
> >
> > The Guile user manual is usually quite excellent, but I seem to be
> missing
> > something important.
> >
> > Thanks,
> >
> >
> ;;----------------------------------------------------------------------------;;
> > ;; C source for "libstuff.so":
> > ;; file stuff.c, compiled as:
> > ;; gcc stuff.c -o libstuff.so -fPIC -shared
> > #|
> > void int_ptr_example1(int *a) {
> >      *a = 5;
> > }
> > |#
> You'll need to make-bytevector a bytevector that holds sizeof(int) bytes.
> Then pass (bytevector->pointer <obj>) as the argument.
>
> (let ((obj (make-bytevector (sizeof int))))
>    (int-ptr-example (bytevector->pointer obj)))
>
> Now the 5 should be in the bytevector.  You will need to extract it.
>
>
>
>
>
>
> ------------------------------
>
> Message: 4
> Date: Mon, 23 Nov 2020 04:42:37 +0100
> From: Taylan Kammer <taylan.kammer@gmail.com>
> To: Zelphir Kaltstahl <zelphirkaltstahl@posteo.de>, Guile User
>         <guile-user@gnu.org>
> Subject: Re: Question about data structures
> Message-ID: <a5317e0c-9fe0-1fb9-c6b5-d3065d179285@gmail.com>
> Content-Type: text/plain; charset=utf-8; format=flowed
>
> On 22.11.2020 19:48, Zelphir Kaltstahl wrote:
> > Hello Guile Users!
> >
> > I have a question about data structures.
> >
> > [...]
> >
> > How do you approach this problem? Is it a problem at all?
>
> First of all, be cautious about premature optimization.  In many cases
> it's best to just write the code the most straightforward way possible
> with the tools at hand, and not bother with optimization unless it
> actually proves to be an issue.  Are you going to be processing files
> with millions of lines?  Thousands of lines but on a very weak CPU?
> Does it matter if your program takes 0.1 seconds or 2 seconds to run?
>
>
> Now the actual answer, in case you need to optimize, or just want to
> learn more:
>
>
> All data structures that offer a sequential list of elements have to
> make some trade-offs between the performance of various operations, as
> well as the implementation complexity.  Linked lists (i.e. "lists" in
> Scheme) are very simple, and a few operations are cheap as well, but
> they have the shortcomings you've described plus some more.
>
>
> Since your main concern seems to be appending, you could simply use a
> linked list where you keep a reference to the last cons pair (tail) of
> the list, so appending is simply a matter of a 'set-cdr!' operation on
> the tail.
>
>
> Python lists, JDK's ArrayList, and .NET ArrayList, among probably many
> other "list" or "array" data structures in popular languages nowadays
> use a relatively straightforward data structure that is backed by an
> actual array which can have empty slots (e.g. your Python list with 3
> elements might be backed by an array of size 10), and is reallocated
> whenever there's no space left.  This means that appending an element at
> the end is usually dirt cheap, until there's no space left, at which
> point the append operation is much heavier for one call, then the
> following calls are dirt cheap again, until it's full again...
>
> Inserting an element at the beginning or middle is also relatively
> expensive with those implementations, since all elements need to be
> shifted forward to make space for the new element.  (Although this might
> be done with an operation like C's memcpy which is still actually very
> fast.)
>
> It's called a "dynamic array" by Wikipedia:
>
>      https://en.wikipedia.org/wiki/Dynamic_array
>
> If you want to go on an adventure, you could implement a Scheme data
> structure called DVector that implements this strategy, using plain
> Scheme vectors for the backing array.
>
>
> The VList has also been mentioned in this thread, but from what I can
> tell it doesn't seem to offer a very efficient append operation.
>
>
> - Taylan
>
>
>
> ------------------------------
>
> Message: 5
> Date: Sun, 22 Nov 2020 23:42:44 -0500
> From: John Cowan <cowan@ccil.org>
> To: Taylan Kammer <taylan.kammer@gmail.com>
> Cc: Zelphir Kaltstahl <zelphirkaltstahl@posteo.de>, Guile User
>         <guile-user@gnu.org>
> Subject: Re: Question about data structures
> Message-ID:
>         <CAD2gp_RqX=UivHkLjD0NDGo3KJBdVjq+4hXVTR0zf3XM=
> vFQVw@mail.gmail.com>
> Content-Type: text/plain; charset="UTF-8"
>
> On Sun, Nov 22, 2020 at 10:43 PM Taylan Kammer <taylan.kammer@gmail.com>
> wrote:
>
> Since your main concern seems to be appending, you could simply use a
> > linked list where you keep a reference to the last cons pair (tail) of
> > the list, so appending is simply a matter of a 'set-cdr!' operation on
> > the tail.
> >
>
> SRFI 117, List Queues, does exactly that.
>
> > Python lists, JDK's ArrayList, and .NET ArrayList, among probably many
> > other "list" or "array" data structures in popular languages nowadays
> > use a relatively straightforward data structure that is backed by an
> > actual array which can have empty slots (e.g. your Python list with 3
> > elements might be backed by an array of size 10), and is reallocated
> > whenever there's no space left.  This means that appending an element at
> > the end is usually dirt cheap, until there's no space left, at which
> > point the append operation is much heavier for one call, then the
> > following calls are dirt cheap again, until it's full again...
> >
>
> And the recent SRFI 214, Flexvectors, provides exactly this.
>
> Packaging these two SRFIs for Guile would be a Good Thing.
>
>
>
> John Cowan          http://vrici.lojban.org/~cowan        cowan@ccil.org
> The present impossibility of giving a scientific explanation is no proof
> that there is no scientific explanation. The unexplained is not to be
> identified with the unexplainable, and the strange and extraordinary
> nature of a fact is not a justification for attributing it to powers
> above nature.  --The Catholic Encyclopedia, s.v. "telepathy" (1913)
>
>
> ------------------------------
>
> Subject: Digest Footer
>
> _______________________________________________
> guile-user mailing list
> guile-user@gnu.org
> https://lists.gnu.org/mailman/listinfo/guile-user
>
>
> ------------------------------
>
> End of guile-user Digest, Vol 216, Issue 19
> *******************************************
>


^ permalink raw reply	[flat|nested] 3+ messages in thread

* Re: guile-user Digest, Vol 216, Issue 19
  2020-11-24 21:26 ` guile-user Digest, Vol 216, Issue 19 Tim Meehan
@ 2020-11-25 12:16   ` Adriano Peluso
  2020-11-25 17:15     ` Tim Meehan
  0 siblings, 1 reply; 3+ messages in thread
From: Adriano Peluso @ 2020-11-25 12:16 UTC (permalink / raw)
  To: Tim Meehan, guile-user

Il giorno mar, 24/11/2020 alle 15.26 -0600, Tim Meehan ha scritto:
> Matt - thanks for the help making the FFI pointers work!

Would you mind publishing the working version of your code ?






^ permalink raw reply	[flat|nested] 3+ messages in thread

* Re: guile-user Digest, Vol 216, Issue 19
  2020-11-25 12:16   ` Adriano Peluso
@ 2020-11-25 17:15     ` Tim Meehan
  0 siblings, 0 replies; 3+ messages in thread
From: Tim Meehan @ 2020-11-25 17:15 UTC (permalink / raw)
  Cc: guile-user

Hi Adriano, I hope you mean the int pointer example and not the GTK
example. I wasn't able to get the GTK example working.

The int pointer example worked like this:
// C code, compiled with:
// gcc stuff.c -o libstuff.so -fPIC -shared
void increment_intptr(int *a) { *a += 1; }

;; Guile source
(use-modules (system foreign)
    (rnrs bytevectors))

(define libstuff (dynamic-link "./libstuff.so"))

(define increment
    (pointer->procedure
        void
        (dynamic-func "increment_intptr" libstuff)
        (list '*)))

(let ([b (make-bytevector (sizeof int))])
    (display b)
    (newline)
    (increment (bytevector->pointer b))
    (display b)
    (newline))

On Wed, Nov 25, 2020 at 6:17 AM Adriano Peluso <randomlooser@riseup.net>
wrote:

> Il giorno mar, 24/11/2020 alle 15.26 -0600, Tim Meehan ha scritto:
> > Matt - thanks for the help making the FFI pointers work!
>
> Would you mind publishing the working version of your code ?
>
>
>
>


^ permalink raw reply	[flat|nested] 3+ messages in thread

end of thread, other threads:[~2020-11-25 17:15 UTC | newest]

Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
     [not found] <mailman.199.1606106579.13151.guile-user@gnu.org>
2020-11-24 21:26 ` guile-user Digest, Vol 216, Issue 19 Tim Meehan
2020-11-25 12:16   ` Adriano Peluso
2020-11-25 17:15     ` Tim Meehan

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).