Re: guile style
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
Re: guile style
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
Re: guile style
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, 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)) ))) > >
Fwd: guile style
-- Forwarded message - From: Stefan Israelsson Tampe Date: Sat, Jun 19, 2021 at 1:23 PM Subject: Re: guile style To: Tim Van den Langenbergh 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 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 > > > >
Re: guile style
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?
Re: guile style
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.
Re: guile studio
> From: 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) > For minor calculations, I would say this is fine. It's not hard to understand what this function does. However, the more complicated a function is, the harder this style will be to read, compared to a recursive style (example 3). So in general I would recommend never to use fold, but that's probably somewhat a matter of taste. Personally I never use fold. > (define ans 0) > (for i N >(if (or (= 0 (modulo i 3)) (= 0 (modulo i 5))) (set! ans (+ ans i > (print ans) > Same here. For minor calculations, this is fine. In fact, this way is probably much easier to read than the first example. However, if you start using 'set!' on more than one variable, things can get very messy. Regarding performance, this might be both faster or slower depending on the scheme implementation. > (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)) ))) > Please note that this way is also functional. This way is also more efficient than example #1 since the program can do tail call optimization and doesn't have to allocate lists. In addition, if you had formatted this version properly I would have consider this version to be easier to read than example #1. Also note that if N is not too big (so that tail call optimization doesn't matter), the following version would be even simpler: (define ans (let loop ((i 1)) (cond ((>= i N) 0) ((or (= 0 (modulo i 3)) (= 0 (modulo i 5))) (+ i (loop (1+ i (else (loop (1+ i)) Training yourself to read and write functions this way is probably a good exercise. After a while you are able to easily make very advanced functions by using recursive functions. Also note that using less number of lines in a function does not make the function easier to read.
Re: guile style
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
Re: guile style
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
Re: guile style
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
