+ is not associative for many types.
Reduce vs. Fold in Common Lisp
21–30 of 30 posts
Re: Reduce vs. Fold in Common Lisp
#22+ is not associative for many types.
True, which is why Common Lisp accepts a parameter to specify which order the + should be applied - from left to right or vice versa. Left to right is default.
Re: Reduce vs. Fold in Common Lisp
#23The history here is that Common Lisp gets reduce from APL ( https://aplwiki.com/wiki/Reduce ). It's not an attempt an ML-style fold, but a different formalism from a different lineage.
While reading this, I was immediately reminded of the reduce operator, glad to see my intuition wasn't far off. The nifty thing about this operator in the array-langs compared to the usual fold function is that they usually define identity elements for all primitive functions, which means that no initial value has to be provided: https://aplwiki.com/wiki/Identity_element The downside of this approach though, is that…
I had thought APL style was to specify initial values simply by pre-catenating the desired initial value onto the argument?
Re: Reduce vs. Fold in Common Lisp
#24Earlier quoted context omitted.
> So reduce can be obviated by just letting the function take variable args too. In Common Lisp the max number of arguments can be small. $ abcl Armed Bear Common Lisp 1.8.0 Java 11.0.19 Ubuntu OpenJDK 64-Bit Server VM Low-level initialization completed in 0.304 seconds. Startup completed in 1.501 seconds. Type ":help" for a list of available commands. CL-USER(1): CALL-ARGUMENTS-LIMIT 50
Interesting. Do you know if that is due to constraints coming from ABCL running on a JVM, or is it an arbitrary choice ? (By contrast, SBCL on a x86_64 laptop returns 4611686018427387903...)
Usually these limits are based on the capabilities of the underlying platform (like the JVM) or the implementation choice. One of the goals is to have fast function calls and less so to have long arguments lists. Less than 2^16 isn't that rare. SBCL is more on the large side. Implementations like ABCL, CLISP and some others have much smaller max arglist length limits.
Don't use
(apply #'+ long-list-of-numbers)
(reduce #'+ long-list-of-numbers)Re: Reduce vs. Fold in Common Lisp
#25so foldl is basically (defun foldl (function value sequence) (reduce function sequence :initial-value value))
Yeah, I'm not seeing what's so special either. Maybe it's that you do have to specify that initial value, so your return types are never something you don't expect?
The numeric tower in Common Lisp may surprise us with simple things as addition:
(+ #c(10 -1) #c(20 1))
Re: Reduce vs. Fold in Common Lisp
#26Earlier quoted context omitted.
While reading this, I was immediately reminded of the reduce operator, glad to see my intuition wasn't far off. The nifty thing about this operator in the array-langs compared to the usual fold function is that they usually define identity elements for all primitive functions, which means that no initial value has to be provided: https://aplwiki.com/wiki/Identity_element The downside of this approach though, is that…
I had thought APL style was to specify initial values simply by pre-catenating the desired initial value onto the argument?
that doesn't work when the desired initial value is not the same shape as the major cells of the argument array
Re: Reduce vs. Fold in Common Lisp
#27Earlier quoted context omitted.
While reading this, I was immediately reminded of the reduce operator, glad to see my intuition wasn't far off. The nifty thing about this operator in the array-langs compared to the usual fold function is that they usually define identity elements for all primitive functions, which means that no initial value has to be provided: https://aplwiki.com/wiki/Identity_element The downside of this approach though, is that…
I had thought APL style was to specify initial values simply by pre-catenating the desired initial value onto the argument?
No, as you can check with some of the weirder arithmetic functions:
Re: Reduce vs. Fold in Common Lisp
#28Earlier quoted context omitted.
Yeah, I'm not seeing what's so special either. Maybe it's that you do have to specify that initial value, so your return types are never something you don't expect?
The numeric tower in Common Lisp may surprise us with simple things as addition: (+ #c(10 -1) #c(20 1)) the result of adding these two complex numbers is the integer 30.
Huh. I did not know that. I am surprised that it actually coerces the result to an integer, although that's certainly an artificial type edge case.
SBCL is free software, provided as is, with absolutely no warranty.
It is mostly in the public domain; some portions are provided under
BSD-style licenses. See the CREDITS and COPYING files in the
distribution for more information.
* (+ #c(10 -1) #c(20 1))
30
* (type-of (+ #c(10 -1) #c(20 1)))
(INTEGER 0 4611686018427387903)
* (type-of (+ #c(10 -1) #c(20 1.0)))
(COMPLEX (SINGLE-FLOAT 0.0 30.0))Re: Reduce vs. Fold in Common Lisp
#29Earlier quoted context omitted.
Interesting. Do you know if that is due to constraints coming from ABCL running on a JVM, or is it an arbitrary choice ? (By contrast, SBCL on a x86_64 laptop returns 4611686018427387903...)
Usually these limits are based on the capabilities of the underlying platform (like the JVM) or the implementation choice. One of the goals is to have fast function calls and less so to have long arguments lists. Less than 2^16 isn't that rare. SBCL is more on the large side. Implementations like ABCL, CLISP and some others have much smaller max arglist length limits. Don't use (apply #'+ long-list-of-numbers) but us…
So this wasn't what I was expecting.
* (disassemble (lambda () (apply #'+ '(1 2 3 4 5))))
; disassembly for (LAMBDA ())
; Size: 21 bytes. Origin: #x5345C11B ; (LAMBDA ())
; 1B: 498B4510 MOV RAX, [R13+16] ; thread.binding-stack-pointer
; 1F: 488945F8 MOV [RBP-8], RAX
; 23: BA1E000000 MOV EDX, 30
; 28: 488BE5 MOV RSP, RBP
; 2B: F8 CLC
; 2C: 5D POP RBP
; 2D: C3 RET
; 2E: CC10 INT3 16 ; Invalid argument count trap
NIL
* (disassemble (lambda () (reduce #'+ '(1 2 3 4 5))))
; disassembly for (LAMBDA ())
; Size: 21 bytes. Origin: #x5345C1AB ; (LAMBDA ())
; AB: 498B4510 MOV RAX, [R13+16] ; thread.binding-stack-pointer
; AF: 488945F8 MOV [RBP-8], RAX
; B3: BA1E000000 MOV EDX, 30
; B8: 488BE5 MOV RSP, RBP
; BB: F8 CLC
; BC: 5D POP RBP
; BD: C3 RET
; BE: CC10 INT3 16 ; Invalid argument count trap
NILRe: Reduce vs. Fold in Common Lisp
#30Earlier quoted context omitted.
Usually these limits are based on the capabilities of the underlying platform (like the JVM) or the implementation choice. One of the goals is to have fast function calls and less so to have long arguments lists. Less than 2^16 isn't that rare. SBCL is more on the large side. Implementations like ABCL, CLISP and some others have much smaller max arglist length limits. Don't use (apply #'+ long-list-of-numbers) but us…
So this wasn't what I was expecting. * (disassemble (lambda () (apply #'+ '(1 2 3 4 5)))) ; disassembly for (LAMBDA ()) ; Size: 21 bytes. Origin: #x5345C11B ; (LAMBDA ()) ; 1B: 498B4510 MOV RAX, [R13+16] ; thread.binding-stack-pointer ; 1F: 488945F8 MOV [RBP-8], RAX ; 23: BA1E000000 MOV EDX, 30 ; 28: 488BE5 MOV RSP, RBP ; 2B: F8 CLC ; 2C: 5D POP RBP ; 2D: C3 RET ; 2E: CC10 INT3 16 ; Invalid argument count trap NIL *…
There is some SBCL compiler optimizer at work.