From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Tim Meehan Newsgroups: gmane.lisp.guile.user Subject: Re: guile-user Digest, Vol 216, Issue 19 Date: Tue, 24 Nov 2020 15:26:13 -0600 Message-ID: References: Mime-Version: 1.0 Content-Type: text/plain; charset="UTF-8" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="7572"; mail-complaints-to="usenet@ciao.gmane.io" To: guile-user@gnu.org Original-X-From: guile-user-bounces+guile-user=m.gmane-mx.org@gnu.org Tue Nov 24 22:26:41 2020 Return-path: Envelope-to: guile-user@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1khfpg-0001rd-TW for guile-user@m.gmane-mx.org; Tue, 24 Nov 2020 22:26:41 +0100 Original-Received: from localhost ([::1]:58098 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1khfpf-0002pu-Ux for guile-user@m.gmane-mx.org; Tue, 24 Nov 2020 16:26:39 -0500 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:51358) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1khfpV-0002pY-HX for guile-user@gnu.org; Tue, 24 Nov 2020 16:26:29 -0500 Original-Received: from mail-qv1-xf2c.google.com ([2607:f8b0:4864:20::f2c]:44706) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1khfpR-0005Ar-WD for guile-user@gnu.org; Tue, 24 Nov 2020 16:26:29 -0500 Original-Received: by mail-qv1-xf2c.google.com with SMTP id 62so1153621qva.11 for ; Tue, 24 Nov 2020 13:26:25 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to; bh=8lnnZMBmfzjbLttvqCFN2Ns3Ta32sTaq5WHo3hHEBTc=; b=tKrN/PTshWWnafCU9WOkXqLdCUGQTDwGa+47WFJ47JRW4ojWxQy+j0zhr5n3ODAg80 enR8KfVSgoPSA8eNqYlc1BW6SoaEv5wMmTwKShMf50aCamXW6ixrbRbud1lDlqetb+gs g6CGKxdTBwYWOPAb10Kn21j/un5ryClUG5pPpBdPaELr8vaMxmTbQNmKZpXG1HW5z9ni WMb/uNgyloG0Qz6giXQhhkxVpG3sis+mqMH7Vh2JHjS16dtMAVmp8Cr/D9JUuWUs9a9b Qv4Z915sgKmPajTAbRgC4yfP6M71uyP1LYsAPhm3tGQjdLJsySe4J/A4mU2c9MVBynmv TTEw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to; bh=8lnnZMBmfzjbLttvqCFN2Ns3Ta32sTaq5WHo3hHEBTc=; b=T7w5AmEcc8c7pBR2y4BN6mG6G/JMPJTnQuKYaokLgpEE1/SJGfVm0vM9hQRf8EP4GU erReEWpw6QYztmEmSKxDxiUxng3eBALf6fbZ0qUj5N3YE3tKjW+chYxKW+Lr/pmnDusw MY3zhEFiYU2Qi5lk89eDMQbDHNKKeuFVb9Pxiccyq92ze2sN+h8tpJqDZE+Cl1/QDDNU xt5yWzitLZED6SPIAypyoN9yJ9v/DRaXBwQNlAi1AAF1Y307wcLCTYZFjDqzKPem0riw OBrJzgdli3HRhVOUQXZH34NylOiy7/rnxFfvhd9+XlZl3abC7o47GT2FIvjxKom0leWZ HPWg== X-Gm-Message-State: AOAM533MwZPKtme5RuEDBic4S5XlcDvr6AMHnMrf8Wpc7rp6cslosfor BnRwxd9R6+8rSPzSuP6bee8bcSZDuVROBCMaRa5Nkt7U X-Google-Smtp-Source: ABdhPJzwYAmEh4L72Io2I/SXNh84/rrXPTUAYiLIlz9z6P5JuuVcj79/gYNTdAlQCdwwpWBoOZgh0/M/NhlZ8LiAtTk= X-Received: by 2002:ad4:5b82:: with SMTP id 2mr448994qvp.28.1606253184601; Tue, 24 Nov 2020 13:26:24 -0800 (PST) In-Reply-To: Received-SPF: pass client-ip=2607:f8b0:4864:20::f2c; envelope-from=btmeehan@gmail.com; helo=mail-qv1-xf2c.google.com X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-Content-Filtered-By: Mailman/MimeDel 2.1.23 X-BeenThere: guile-user@gnu.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: General Guile related discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-user-bounces+guile-user=m.gmane-mx.org@gnu.org Original-Sender: "guile-user" Xref: news.gmane.io gmane.lisp.guile.user:17055 Archived-At: Matt - thanks for the help making the FFI pointers work! On Sun, Nov 22, 2020 at 10:44 PM 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 > 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 > 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 > To: guile-user@gnu.org > Subject: Re: Guile dynamic FFI, C function expecting pointer > Message-ID: > 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 ) 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 > To: Zelphir Kaltstahl , Guile User > > Subject: Re: Question about data structures > Message-ID: > 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 > To: Taylan Kammer > Cc: Zelphir Kaltstahl , Guile User > > Subject: Re: Question about data structures > Message-ID: > vFQVw@mail.gmail.com> > Content-Type: text/plain; charset="UTF-8" > > On Sun, Nov 22, 2020 at 10:43 PM Taylan Kammer > 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 > ******************************************* >