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