[Outreachy] Use of impure functional programming and use of vlists

[Outreachy] Use of impure functional programming and use of vlists

[Magali Lemes]

Hello, Guix.

As my Outreachy internship approaches an end, I'd like to know which of 
the following options is better for walking and displaying the Git 
commit history:
1) having a list and then using for-each it to display the commit 
information;
2) display the list while building it.

When it comes to option number 2, the main advantage is that it's faster 
to perform operations such as 'guix git log --oneline | head -n5'. The 
downside is that it's not a pure functional programming approach.
Another question is, could vlists be used? Since it would be fast to 
have the commits in a hash table implemented with vlists, we could use 
'vlist-for-each' to display the commits. I haven't seen vlist-for-each 
being used anywhere in Guix, so I wondered if there's a special reason 
for it not being used, or if it hasn't really been necessary at all thus 
far.

Regards,
Magali

Re: [Outreachy] Use of impure functional programming and use of vlists

[Arun Isaac]

[-- Attachment #1: Type: text/plain, Size: 362 bytes --]


> 1) having a list and then using for-each it to display the commit 
> information;
> 2) display the list while building it.

Would something like list-transduce from srfi-171 be useful?
list-transduce lets you avoid building intermediate lists that need to
be garbage collected.

https://www.gnu.org/software/guile/manual/html_node/SRFI_002d171.html

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 524 bytes --]

Re: [Outreachy] Use of impure functional programming and use of vlists

[Ludovic Courtès]

Hi Magali,

Magali Lemes <magalilemes00@gmail.com> skribis:

> As my Outreachy internship approaches an end, I'd like to know which
> of the following options is better for walking and displaying the Git 
> commit history:
> 1) having a list and then using for-each it to display the commit
> information;
> 2) display the list while building it.

In addition to Arun’s suggestion, an option would be to achieve #2 while
keeping a functional approach; this can be done using SRFI-41 “streams”.

Streams are lazy lists, meaning that the elements of a stream are
computed on demand.  If you do:

  (use-modules (srfi srfi-41))

  (stream-for-each (lambda (n)
                     (pk (car (gettimeofday)) n))
                   (stream-cons 1
                                (stream-cons (begin (sleep 2) 2)
                                             stream-null)))

You’ll see that the first element is printed before we sleep for two
seconds.

I don’t know if this could work in your case; the Guile-Git API is eager
(as opposed to lazy), so maybe it’s not directly applicable.

> Another question is, could vlists be used? Since it would be fast to
> have the commits in a hash table implemented with vlists, we could use 
> 'vlist-for-each' to display the commits. I haven't seen vlist-for-each
> being used anywhere in Guix, so I wondered if there's a special reason 
> for it not being used, or if it hasn't really been necessary at all
> thus far.

Vlists are a sort of immutable data structures for vectors; for a
regular list, the cost of random access is linear in the size of the
list, whereas for vlists random access is “typically” constant-time,
almost like a vector.

The graph of commits is usually traversed linearly, so the complexity of
random access doesn’t matter much.  Likewise, in Guix proper, there are
probably few or no occasions where we need vector-like structures, which
is why vlists are not used.

HTH!

Ludo’.

Re: [Outreachy] Use of impure functional programming and use of vlists

[zimoun]

Hi Magali,

On Sat, 27 Feb 2021 at 00:10, Magali Lemes <magalilemes00@gmail.com> wrote:

> As my Outreachy internship approaches an end, I'd like to know which of 
> the following options is better for walking and displaying the Git 
> commit history:
> 1) having a list and then using for-each it to display the commit 
> information;
> 2) display the list while building it.

What could be informative is to benchmark the two cases.  For an
example, see my previous tests on your code:

   <https://yhetil.org/guix/86eei4hamb.fsf@gmail.com>

Profiling the 2 functions should be also helpful.  Feel free to ask on
guix-devel how to profile with Guile.


Cheers,
simon