unofficial mirror of guile-user@gnu.org 
 help / color / mirror / Atom feed
* guile style
@ 2021-06-19  0:55 jerry
  2021-06-19 10:25 ` Tim Van den Langenbergh
                   ` (2 more replies)
  0 siblings, 3 replies; 10+ messages in thread
From: jerry @ 2021-06-19  0:55 UTC (permalink / raw)
  To: guile-devel-confirm+bec536c361a61d32a192d9a45ad6dea4f892df58, guile-user

I am fairly new to guile and scheme. People tell me that I should use a 
functional style.

I have 3 solutions for project euler problem #1. The first is 
functional, the second is imperative and the third is written in "Little 
Schemer" style.

I was hoping other guile users would comment on preferences or the 
"correct way". Sorry in advance for any wrapping problems that may occur.

#!/usr/local/bin/guile  -s
!#
(use-modules (srfi srfi-1) (jpd stdio)) ;; for folds
(define N 1000)

(define ans
   (fold + 0
     (filter
       (lambda (x) (or (= 0 (modulo x 3)) (= 0 (modulo x 5))))
       (iota N))))
(print ans)

(define ans 0)
(for i N
   (if (or (= 0 (modulo i 3)) (= 0 (modulo i 5))) (set! ans (+ ans i))))
(print ans)

(define ans
   (let loop ((i 1) (ans 0))
     (cond
       ((>= i N) ans)
       ((or (= 0 (modulo i 3)) (= 0 (modulo i 5))) (loop (1+ i) (+ ans i)))
       (else (loop (1+ i) ans)) )))



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

* Re: guile style
  2021-06-19  0:55 guile style jerry
@ 2021-06-19 10:25 ` Tim Van den Langenbergh
       [not found]   ` <CAGua6m1HSYGP6i60Qyj=sVAgeriOzZmb1abCtoxnTQQiOgyY-Q@mail.gmail.com>
  2021-06-19 11:31   ` jerry
  2021-06-19 11:17 ` Ricardo Wurmus
  2021-06-19 11:20 ` Christopher Lam
  2 siblings, 2 replies; 10+ messages in thread
From: Tim Van den Langenbergh @ 2021-06-19 10:25 UTC (permalink / raw)
  To: guile-user

On Saturday, 19 June 2021 02:55:34 CEST jerry wrote:
> I am fairly new to guile and scheme. People tell me that I should use a
> functional style.
>
> I have 3 solutions for project euler problem #1. The first is
> functional, the second is imperative and the third is written in "Little
> Schemer" style.
>
> I was hoping other guile users would comment on preferences or the
> "correct way". Sorry in advance for any wrapping problems that may occur.
>
> #!/usr/local/bin/guile  -s
> !#
> (use-modules (srfi srfi-1) (jpd stdio)) ;; for folds
> (define N 1000)
>
> (define ans
>    (fold + 0
>      (filter
>        (lambda (x) (or (= 0 (modulo x 3)) (= 0 (modulo x 5))))
>        (iota N))))
> (print ans)
>
> (define ans 0)
> (for i N
>    (if (or (= 0 (modulo i 3)) (= 0 (modulo i 5))) (set! ans (+ ans i))))
> (print ans)
>
> (define ans
>    (let loop ((i 1) (ans 0))
>      (cond
>        ((>= i N) ans)
>        ((or (= 0 (modulo i 3)) (= 0 (modulo i 5))) (loop (1+ i) (+ ans i)))
>        (else (loop (1+ i) ans)) )))

I'm not 100% sure about how Guile does it, but I know that some Scheme
implementations do some boxing for set! operations, which will make the second
variation poorly optimised. Personally I would use combine the first and third
answers by doing the divisible-by check during the fold, like this:

(use-modules (srfi srfi-1))

(define (divisible-by? divident divisor)
~~(zero? (modulo divident divisor)))

(define N 1000)

(define ans
~~(fold (lambda (i res)
~~~~~~~~~~(if (or (divisible-by? i 3)
~~~~~~~~~~~~~~~~~~(divisible-by? i 5))
~~~~~~~~~~~~(+ i res)
~~~~~~~~~~~~res))
~~~~~~~~0
~~~~~~~~(iota N)))

Vale,

-Tim





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

* Re: guile style
  2021-06-19  0:55 guile style jerry
  2021-06-19 10:25 ` Tim Van den Langenbergh
@ 2021-06-19 11:17 ` Ricardo Wurmus
  2021-06-19 11:20 ` Christopher Lam
  2 siblings, 0 replies; 10+ messages in thread
From: Ricardo Wurmus @ 2021-06-19 11:17 UTC (permalink / raw)
  To: jerry
  Cc: guile-devel-confirm+bec536c361a61d32a192d9a45ad6dea4f892df58, guile-user


Hi Jerry,

> I am fairly new to guile and scheme. People tell me that I 
> should use
> a functional style.
>
> I have 3 solutions for project euler problem #1. The first is
> functional, the second is imperative and the third is written in
> "Little Schemer" style.
>
> I was hoping other guile users would comment on preferences or 
> the
> "correct way". Sorry in advance for any wrapping problems that 
> may
> occur.
>
> #!/usr/local/bin/guile  -s
> !#
> (use-modules (srfi srfi-1) (jpd stdio)) ;; for folds
> (define N 1000)
>
> (define ans
>   (fold + 0
>     (filter
>       (lambda (x) (or (= 0 (modulo x 3)) (= 0 (modulo x 5))))
>       (iota N))))
> (print ans)

This is fine, though instead of (= 0 …) you could use (zero? …).

Using “fold” is good because it is a common higher-order 
abstraction, so it is easy to read and understand at a glance.

> (define ans 0)
> (for i N
>   (if (or (= 0 (modulo i 3)) (= 0 (modulo i 5))) (set! ans (+ 
>   ans i))))
> (print ans)

This is not idiomatic for two reasons: it uses SET! and a 
single-branched IF.  I have never before encounter FOR in Guile 
code.  A “named let” (as in your next variant) is much more 
common.

> (define ans
>   (let loop ((i 1) (ans 0))
>     (cond
>       ((>= i N) ans)
>       ((or (= 0 (modulo i 3)) (= 0 (modulo i 5))) (loop (1+ i) 
>       (+ ans i)))
>       (else (loop (1+ i) ans)) )))

This is explicit, which is fine, but for routine tasks like 
accumulation of results a fold is easier to understand at a 
glance.

-- 
Ricardo



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

* Re: guile style
  2021-06-19  0:55 guile style jerry
  2021-06-19 10:25 ` Tim Van den Langenbergh
  2021-06-19 11:17 ` Ricardo Wurmus
@ 2021-06-19 11:20 ` Christopher Lam
  2021-06-19 12:16   ` jerry
  2 siblings, 1 reply; 10+ messages in thread
From: Christopher Lam @ 2021-06-19 11:20 UTC (permalink / raw)
  To: jerry
  Cc: guile-devel-confirm+bec536c361a61d32a192d9a45ad6dea4f892df58, guile-user

Agree set! is not a desirable form. It is not consistently optimisable. I
cannot find the reference in the manual.

Also consider the first form: you're building a list in 3 passes -- call
iota to generate a list, call filter to navigate the list again, then fold
to accumulate your answer. Therefore it's O(3N).

The preferred form is definitely from the little schemer.

On Sat, 19 Jun 2021, 8:56 am jerry, <jdinardo@nycap.rr.com> wrote:

> I am fairly new to guile and scheme. People tell me that I should use a
> functional style.
>
> I have 3 solutions for project euler problem #1. The first is
> functional, the second is imperative and the third is written in "Little
> Schemer" style.
>
> I was hoping other guile users would comment on preferences or the
> "correct way". Sorry in advance for any wrapping problems that may occur.
>
> #!/usr/local/bin/guile  -s
> !#
> (use-modules (srfi srfi-1) (jpd stdio)) ;; for folds
> (define N 1000)
>
> (define ans
>    (fold + 0
>      (filter
>        (lambda (x) (or (= 0 (modulo x 3)) (= 0 (modulo x 5))))
>        (iota N))))
> (print ans)
>
> (define ans 0)
> (for i N
>    (if (or (= 0 (modulo i 3)) (= 0 (modulo i 5))) (set! ans (+ ans i))))
> (print ans)
>
> (define ans
>    (let loop ((i 1) (ans 0))
>      (cond
>        ((>= i N) ans)
>        ((or (= 0 (modulo i 3)) (= 0 (modulo i 5))) (loop (1+ i) (+ ans i)))
>        (else (loop (1+ i) ans)) )))
>
>


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

* Fwd: guile style
       [not found]   ` <CAGua6m1HSYGP6i60Qyj=sVAgeriOzZmb1abCtoxnTQQiOgyY-Q@mail.gmail.com>
@ 2021-06-19 11:24     ` Stefan Israelsson Tampe
  0 siblings, 0 replies; 10+ messages in thread
From: Stefan Israelsson Tampe @ 2021-06-19 11:24 UTC (permalink / raw)
  To: Guile User, guile-devel

---------- Forwarded message ---------
From: Stefan Israelsson Tampe <stefan.itampe@gmail.com>
Date: Sat, Jun 19, 2021 at 1:23 PM
Subject: Re: guile style
To: Tim Van den Langenbergh <tmt_vdl@gmx.com>


I'm a big fan of named let's which are a very general functional construct
and tons of commentaries
about the functional style misses that named let's exists and thinks that
functional programming is just
map, fold, filter etc. It beats me why when other languages go functional,
they consistently do not
implement named let.

On Sat, Jun 19, 2021 at 12:25 PM Tim Van den Langenbergh <tmt_vdl@gmx.com>
wrote:

> On Saturday, 19 June 2021 02:55:34 CEST jerry wrote:
> > I am fairly new to guile and scheme. People tell me that I should use a
> > functional style.
> >
> > I have 3 solutions for project euler problem #1. The first is
> > functional, the second is imperative and the third is written in "Little
> > Schemer" style.
> >
> > I was hoping other guile users would comment on preferences or the
> > "correct way". Sorry in advance for any wrapping problems that may occur.
> >
> > #!/usr/local/bin/guile  -s
> > !#
> > (use-modules (srfi srfi-1) (jpd stdio)) ;; for folds
> > (define N 1000)
> >
> > (define ans
> >    (fold + 0
> >      (filter
> >        (lambda (x) (or (= 0 (modulo x 3)) (= 0 (modulo x 5))))
> >        (iota N))))
> > (print ans)
> >
> > (define ans 0)
> > (for i N
> >    (if (or (= 0 (modulo i 3)) (= 0 (modulo i 5))) (set! ans (+ ans i))))
> > (print ans)
> >
> > (define ans
> >    (let loop ((i 1) (ans 0))
> >      (cond
> >        ((>= i N) ans)
> >        ((or (= 0 (modulo i 3)) (= 0 (modulo i 5))) (loop (1+ i) (+ ans
> i)))
> >        (else (loop (1+ i) ans)) )))
>
> I'm not 100% sure about how Guile does it, but I know that some Scheme
> implementations do some boxing for set! operations, which will make the
> second
> variation poorly optimised. Personally I would use combine the first and
> third
> answers by doing the divisible-by check during the fold, like this:
>
> (use-modules (srfi srfi-1))
>
> (define (divisible-by? divident divisor)
> ~~(zero? (modulo divident divisor)))
>
> (define N 1000)
>
> (define ans
> ~~(fold (lambda (i res)
> ~~~~~~~~~~(if (or (divisible-by? i 3)
> ~~~~~~~~~~~~~~~~~~(divisible-by? i 5))
> ~~~~~~~~~~~~(+ i res)
> ~~~~~~~~~~~~res))
> ~~~~~~~~0
> ~~~~~~~~(iota N)))
>
> Vale,
>
> -Tim
>
>
>
>


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

* Re: guile style
  2021-06-19 10:25 ` Tim Van den Langenbergh
       [not found]   ` <CAGua6m1HSYGP6i60Qyj=sVAgeriOzZmb1abCtoxnTQQiOgyY-Q@mail.gmail.com>
@ 2021-06-19 11:31   ` jerry
  1 sibling, 0 replies; 10+ messages in thread
From: jerry @ 2021-06-19 11:31 UTC (permalink / raw)
  To: guile-user

On 6/19/21 6:25 AM, Tim Van den Langenbergh wrote:
> On Saturday, 19 June 2021 02:55:34 CEST jerry wrote:
>> I am fairly new to guile and scheme. People tell me that I should use a
>> functional style.
>>
>> I have 3 solutions for project euler problem #1. The first is
>> functional, the second is imperative and the third is written in "Little
>> Schemer" style.
>>
>> I was hoping other guile users would comment on preferences or the
>> "correct way". Sorry in advance for any wrapping problems that may occur.
>>
>> #!/usr/local/bin/guile  -s
>> !#
>> (use-modules (srfi srfi-1) (jpd stdio)) ;; for folds
>> (define N 1000)
>>
>> (define ans
>>     (fold + 0
>>       (filter
>>         (lambda (x) (or (= 0 (modulo x 3)) (= 0 (modulo x 5))))
>>         (iota N))))
>> (print ans)
>>
>> (define ans 0)
>> (for i N
>>     (if (or (= 0 (modulo i 3)) (= 0 (modulo i 5))) (set! ans (+ ans i))))
>> (print ans)
>>
>> (define ans
>>     (let loop ((i 1) (ans 0))
>>       (cond
>>         ((>= i N) ans)
>>         ((or (= 0 (modulo i 3)) (= 0 (modulo i 5))) (loop (1+ i) (+ ans i)))
>>         (else (loop (1+ i) ans)) )))
> 
> I'm not 100% sure about how Guile does it, but I know that some Scheme
> implementations do some boxing for set! operations, which will make the second
> variation poorly optimised. Personally I would use combine the first and third
> answers by doing the divisible-by check during the fold, like this:
> 
> (use-modules (srfi srfi-1))
> 
> (define (divisible-by? divident divisor)
> ~~(zero? (modulo divident divisor)))
> 
> (define N 1000)
> 
> (define ans
> ~~(fold (lambda (i res)
> ~~~~~~~~~~(if (or (divisible-by? i 3)
> ~~~~~~~~~~~~~~~~~~(divisible-by? i 5))
> ~~~~~~~~~~~~(+ i res)
> ~~~~~~~~~~~~res))
> ~~~~~~~~0
> ~~~~~~~~(iota N)))
> 
> Vale,
> 
> -Tim
> 
> 
> 
I like the functional style best for problems like this which
lend themselves to a functional solution. I took up Haskell a couple of
years ago and I did the first 80 project Euler problems with it. About
10 percent of the problems would have been solved much easier with
imperative style (at least for me). That is why I started learning lisp. 
I found I liked scheme better than common lisp.
What I was really wondering is when, if ever do schemers use imperative 
style. Is there a book or article that would illustrate this?



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

* Re: guile style
  2021-06-19 11:20 ` Christopher Lam
@ 2021-06-19 12:16   ` jerry
  2021-06-19 17:02     ` Zelphir Kaltstahl
  2021-06-19 17:59     ` Linus Björnstam
  0 siblings, 2 replies; 10+ messages in thread
From: jerry @ 2021-06-19 12:16 UTC (permalink / raw)
  To: Christopher Lam; +Cc: guile-user

On 6/19/21 7:20 AM, Christopher Lam wrote:
> Agree set! is not a desirable form. It is not consistently optimisable. 
> I cannot find the reference in the manual.
> 
> Also consider the first form: you're building a list in 3 passes -- call 
> iota to generate a list, call filter to navigate the list again, then 
> fold to accumulate your answer. Therefore it's O(3N).
> 
> The preferred form is definitely from the little schemer.
> 
Haskell has something called stream fusion which can optimize the extra
passes out in many cases. I wonder if Guile or any of the other scheme
compilers can do that? As someone who has spent the majority of my life
writing high performance C and Fortran code, the inefficiencies in a lot
of functional programming is something I don't care for. On the other
hand, writing functional code is fun.




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

* Re: guile style
  2021-06-19 12:16   ` jerry
@ 2021-06-19 17:02     ` Zelphir Kaltstahl
  2021-06-19 17:59     ` Linus Björnstam
  1 sibling, 0 replies; 10+ messages in thread
From: Zelphir Kaltstahl @ 2021-06-19 17:02 UTC (permalink / raw)
  To: jerry, Christopher Lam; +Cc: guile-user


On 6/19/21 2:16 PM, jerry wrote:
> On 6/19/21 7:20 AM, Christopher Lam wrote:
>> Agree set! is not a desirable form. It is not consistently optimisable. I
>> cannot find the reference in the manual.
>>
>> Also consider the first form: you're building a list in 3 passes -- call iota
>> to generate a list, call filter to navigate the list again, then fold to
>> accumulate your answer. Therefore it's O(3N).
>>
>> The preferred form is definitely from the little schemer.
>>
> Haskell has something called stream fusion which can optimize the extra
> passes out in many cases. I wonder if Guile or any of the other scheme
> compilers can do that? As someone who has spent the majority of my life
> writing high performance C and Fortran code, the inefficiencies in a lot
> of functional programming is something I don't care for. On the other
> hand, writing functional code is fun.

I'd be surprised, if Guile did such an optimization. I think you are supposed to
write the optimized version of the algorithm. In my opinion, when you know a
better version, you should not rely on an optimization by one particular
compiler or language.

I think it is fine to have small (really small, hopefully not changing time or
space complexity class) performance trade-offs in order to achieve better
readability. Usually however, I well readable version of the better algorithm is
possible.

-- 
repositories: https://notabug.org/ZelphirKaltstahl




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

* Re: guile style
  2021-06-19 12:16   ` jerry
  2021-06-19 17:02     ` Zelphir Kaltstahl
@ 2021-06-19 17:59     ` Linus Björnstam
  2021-06-20  2:21       ` jerry
  1 sibling, 1 reply; 10+ messages in thread
From: Linus Björnstam @ 2021-06-19 17:59 UTC (permalink / raw)
  To: jerry, Christopher Lam; +Cc: guile-user


On Sat, 19 Jun 2021, at 14:16, jerry wrote:
> On 6/19/21 7:20 AM, Christopher Lam wrote:
> > Agree set! is not a desirable form. It is not consistently optimisable. 
> > I cannot find the reference in the manual.
> > 
> > Also consider the first form: you're building a list in 3 passes -- call 
> > iota to generate a list, call filter to navigate the list again, then 
> > fold to accumulate your answer. Therefore it's O(3N).
> > 
> > The preferred form is definitely from the little schemer.
> > 
> Haskell has something called stream fusion which can optimize the extra
> passes out in many cases. I wonder if Guile or any of the other scheme
> compilers can do that? 

Hi Jerry!

For this to work guile would need to be either pure or lazy. Lazy, because a value would only be pulled through the chain when needed, which would change the evaluation order in a way that would be compatible with side effects. Pure because without side effects fusing two loops can be done without fear.

Haskell is of course both. You can get lightweight laziness using srfi-158 - which isn't really loop fusion, but chaining 1000 generator clauses is still O(n). 

What guile does have is an eager construct that does something similar to loop fusion: transducers. Look at srfi-171. One can compose transducers without building want intermediate collections: (list-transduce (compose (tfilter even?) (tmap (lambda (x) (quotient x 2)))) + a-list) will keep all even numbers and divide them by 2, and sum them. No intermediate collections build. They have higher overhead, but are usually faster already at 2 steps.

Best regards
Linus Björnstam




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

* Re: guile style
  2021-06-19 17:59     ` Linus Björnstam
@ 2021-06-20  2:21       ` jerry
  0 siblings, 0 replies; 10+ messages in thread
From: jerry @ 2021-06-20  2:21 UTC (permalink / raw)
  To: guile-user

On 6/19/21 1:59 PM, Linus Björnstam wrote:

Unlike Donald Knuth, I can't stop myself from premature optimization and
so far, in my short Guile career, I have almost always used my option 3.
I will look into srfi-158 and srfi-171 because they look very interesting.

Based on the responses here, I get the feeling that there is no one 
right way which makes me happy. The reason that I reached out to the 
mailing list is that I recently read that explicit recursion was the 
"goto" of Lisp. Because I like things to be fast/efficient, I always try 
to find a tail call optimized recursion algorithm. I am just looking 
into prompts which apparently will let me break out of folds which was
often an annoyance for me in Haskell. Thanks for all the responses.


> 
> Hi Jerry!
> 
> For this to work guile would need to be either pure or lazy. Lazy, because a value would only be pulled through the chain when needed, which would change the evaluation order in a way that would be compatible with side effects. Pure because without side effects fusing two loops can be done without fear.
> 
> Haskell is of course both. You can get lightweight laziness using srfi-158 - which isn't really loop fusion, but chaining 1000 generator clauses is still O(n).
> 
> What guile does have is an eager construct that does something similar to loop fusion: transducers. Look at srfi-171. One can compose transducers without building want intermediate collections: (list-transduce (compose (tfilter even?) (tmap (lambda (x) (quotient x 2)))) + a-list) will keep all even numbers and divide them by 2, and sum them. No intermediate collections build. They have higher overhead, but are usually faster already at 2 steps.
> 
> Best regards
> Linus Björnstam
> 




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

end of thread, other threads:[~2021-06-20  2:21 UTC | newest]

Thread overview: 10+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-06-19  0:55 guile style jerry
2021-06-19 10:25 ` Tim Van den Langenbergh
     [not found]   ` <CAGua6m1HSYGP6i60Qyj=sVAgeriOzZmb1abCtoxnTQQiOgyY-Q@mail.gmail.com>
2021-06-19 11:24     ` Fwd: " Stefan Israelsson Tampe
2021-06-19 11:31   ` jerry
2021-06-19 11:17 ` Ricardo Wurmus
2021-06-19 11:20 ` Christopher Lam
2021-06-19 12:16   ` jerry
2021-06-19 17:02     ` Zelphir Kaltstahl
2021-06-19 17:59     ` Linus Björnstam
2021-06-20  2:21       ` jerry

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 NNTP newsgroup(s).