April 2023 - Pharo-users - lists.pharo.org

Re: Collection>>reduce name clash with transducers

by Steffen MÃ¤rcker

Dear Richard, sorry for the delayed reply and thanks for your thoughts. I wrapped my head around your suggestions and tried a few thing to see how the play out in code. I tend towards the following names. - Reducing function (a role) is a binary block / object that responds to #value:value: and #numArgs; commonly used with #inject:into: - Completing function (a role) is an unary block / object that responds to #value:. - Reducer is a pair (rfn, cfn) of a reducing function and a completing function. - Reduction is a pair (red, val) of a reducer and an initial value. I like your idea to inverse the message flow and implement #reduce: in Reduction. It reads well in my eyes in actual code. I do not think that this is a misnomer, since it indeed reduces a sequence of elements to a single object. A reducer knows how to apply first its rfn to a sequence and then cfn to the result. negatedSum := (#+ completing: #negate) init: 0. result := negatedSum reduce: (1 to: 10). asSet := (#add completing: #trim) initializer: [Set new]. distinct := asSet reduce: aCollection I understand your concerns that we usually either do not need cfn or we applies it manually to the result of the reduction. Yes, most often cfn = identity and I took this into account. However, in some cases I actually need them to pass around as a single object. I also attempted to find names closer to #inject:into: but did not come up with any good ideas yet. That this makes sense so far? I deliberately did not mention transducers above to focus on the naming first. I heard about "obviously synchronizable series expressions" before and had a look at the paper just now. In short, transducers are in the same spirit and offer similar nice properties. But maybe we save the details for another thread? Regarding the examples. Yes, they are are simple, stupid and the reimplemenation of #reduce: is far from optimal. The goal was to show how the objects/messages are used rather then coming up with real world examples or showing off. ;-) Kind regards, Steffen Richard O'Keefe schrieb am Samstag, 15. April 2023 16:28:09 (+02:00): Let initial :: a combine :: a -> b -> a finish :: a -> c then (finish . foldl combine initial) :: Foldable t => t b -> c This appears to be analogous to your 'reduce with completion'. What *can* be done with composition generally *should* be done with composition; I really don't see any advantage in defining reduce finish combine initial = finish . combine initial As for growing a collection and then finally trimming it to its desired size, I've never known anything like that to be a good idea. There's a reason why my library includes Set BoundedSet IdentitySet BoundedIdentitySet Deque BoundedDeque Heap BoundedHeap I use BoundedHeap a lot. If I want to find the k best things out of n, using BoundedHeap lets me do it in O(n.log k) time and O(k) space instead of O(n.log n) time and O(n) space. Your example showing how much better #reduceLeft: is when expressed using transducers is not well chosen,because the implementation of #reduceLeft: in Pharo is (how to say this politely?) not up to the standards we expect from Pharo. Here is how it stands in my compatibility library: Enumerable methods for: 'summarising' reduceLeft: aBlock <compatibility: #pharo> |n| ^(n := aBlock argumentCount) > 2 ifTrue: [ |i a| a := Array new: n. i := 0. self do: [:each | a at: (i := i + 1) put: each. i = n ifTrue: [ a at: (i := 1) put: (aBlock valueWithArguments: a)]]. i = 1 ifTrue: [a at: i] ifFalse: [ self error: 'collection/block size mismatch']] ifFalse: [ "If n = 0 or 1 and the receiver has two or more elements, this will raise an exception passing two arguments to aBlock. That's a good way to complain about it." |r f| r := f := nil. self do: [:each | r := f ifNil: [f := self. each] ifNotNil: [aBlock value: r value: each]]. r == f ifNil: [CollectionTooSmall collection: self] ifNotNil: [r]] No OrderedCollection. And exactly one traversal of the collection. (Enumerables can only be traversed once. Collections can be traversed multiple times.) The only method the receiver needs to provide is #do:, so this method doesn't really need to be in Enumerable. It could, for example, be in Block. #reduceRight: I've placed in AbstractSequence because it needs #reverseDo:, but it equally makes sense as a method of Block (as it knows more about what Blocks can do than it does about what sequences can do). For example, I have SortedSet and SortedBag which can be traversed forwards and backwards but only #reduceLeft: is available to them; #reduceRight: is not, despite them sensibly supporting #reverseDo:. For that matter, Deques support #reverseDo: but are not sequences... To the limited extent that I understand the Transducers package, this view that (s reduce{Left,Right}: b) should really be (b reduce{Left,Right}) applyTo: s seems 100% in the spirit of Transducers. In fact, now that I understand a bit about Transducers, <collection> reduce: <transducer> (a) seems back to front compared with <reducer> applyTo: <collection> (b) seems like a misnomer because in general much may be generated transformed and retained, with nothing getting smaller, so why 'reduce'? It seems like a special case of applying a function-like object (the transducer) to an argument (the collection), so why not transducer applyTo: dataSource transducer applyTo: dataSource initially: initial Did you look at Richard Waters' "obviously synchronizable series expressions"? (MIT AI Memo 958A and 959A) Or his later SERIES package? (Appendix A of Common Lisp the Language, 2nd edition) On Fri, 14 Apr 2023 at 22:32, Steffen MÃ¤rcker <merkste(a)web.de> wrote: Hi Richard! Thanks for sharing your thoughts. There's a reason why #inject:into: puts the block argument last. It works better to have "heavy" constituents on the right in an English sentence, and it's easier to indent blocks when they come last. Nice, I never though of it this way. I always appreciate a historical background. Let me try to respond to the rest with a focus on the ideas. First of all, the point of the transducers framework is to cleanly separate between iteration over sequences, processing of the elements and accumulation of a result. It enables easy reuse the concepts common to different data structures. 1. What do I mean by completion? If we iterate over a sequence of objects, we sometimes want to do a final step after all elements have seen to complete the computation. For instance, after copying elements to a new collection, we may want to trim it to its actual size: distinct := col inject: Set new into: #add. distinct trim. For some cases it turns out to be useful to have an object that knows how to do both: distinct := col reduce: (#add completing: #trim) init: Set new. #reduce:init: knows how to deal with both this new objects and ordinary blocks. For now I will call both variants a "reducing function". Note, completion is completely optional and the implementation is literally #inject:into: plus completion if required. 2. What is a reduction? In some cases, it turns out to be useful to pair up a reducing function with an (initial) value. You called it a magma and often its indeed the neutral element of a mathematical operator, e.g., + and 0. But we can use a block that yields the initial value, too. For instance: sum := #+ init: 0. result := numbers reduce: sum. toSet := (#add completing: #trim) initializer: [Set new]. distinct := col reduce: toSet. #reduce: is just a shorthand that passes the function and the value to #reduce:init: Maybe #reduceMagma: is a reasonable name? 3. The reason I implemented #reduce:init: directly on collections, streams, etc. is that these objects know best how to efficiently iterate over their elements. And if a data structure knows how to #reduce:init: we can use it with all the transducers functions, e.g., for partitioning, filtering etc. Other useful methods could then be added to the behaviour with a trait, e.g., #transduce:reduce:init which first apples a transducer and then reduces. As traits are not available in plain VW 8.3, I did not try this approach, though. 4. Lets take #reduce:Left: as and example and reimplement the method using transducers, shall we? The following code works for each sequence/collection/stream that supports #transduce:reduce:init: reduceLeft: aBlock | head rest arity | head := self transduce: (Take number: 1) reduce: [:r :e | e] init: nil. rest := Drop number: 1. arity := aBlock arity. ^arity = 2 ifTrue: [self transduce: rest reduce: aBlock init: head] ifFalse: [ | size arguments | size := arity - 1. rest := rest * (Partition length: size) * (Remove predicate: [:part | part size < size]). arguments := Array new: arity. arguments at: 1 put: head. self transduce: rest reduce: ([:args :part | args replaceFrom: 2 to: arity with: part; at: 1 put: (aBlock valueWithArguments: args); yourself] completing: [:args | args first]) init: arguments] This code is both more general and faster: It does not create an intermediate OrderedCollection and it treats the common case of binary blocks efficiently. Note the implementation can more compact and optimized if it was specialized in certain class. For instance, SequenceableCollection allows accessing elements by index which turns the first line into a simple "self first". Thanks for staying with me for this long reply. I hope I did not miss a point. I do not insist on the existing names but will appreciate any ideas. Best, Steffen Richard O'Keefe schrieb am Freitag, 14. April 2023 09:43:32 (+02:00): #reduce: aReduction Are you saying that aReduction is an object from which a dyadic block and an initial value can be derived? That's going to confuse the heck out of Dolphin and Pharo users (like me, for example). And in my copy of Pharo, #reduce: calls #reduceLeft:, not #foldLeft:. The sad thing about #reduceLeft: in Pharo is that in order to provide extra generality I have no use for, it fails to provide a fast path for the common case of a dyadic block. reduceLeft: aBlock aBlock argumentCount = 2 ifTrue: [ |r| r := self first. self from: 2 to: self last do: [:each | r := aBlock value: r value: each]. ^r]. ... everything else as before ... Adding up a million floats takes half the time using the fast path (67 msec vs 137 msec). Does your #reduce: also perform "a completion action"? If so, it definitely should not be named after #inject:into:. At any rate, if it does something different, it should have a different name, so #reduce: is no good. #reduce:init: There's a reason why #inject:into: puts the block argument last. It works better to have "heavy" constituents on the right in an English sentence, and it's easier to indent blocks when they come last. Which of the arguments here specifies the 'completion action'? What does the 'completion action' do? (I can't tell from the name.) I think the answer is clear: * choose new intention-revealing names that do not clash. If I have have understood your reduce: aReduction correctly, a Reduction specifies - a binary operation (not necessarily associative) - a value which can be passed to that binary operation which suggests that it represents a magma with identity. By the way, it is not clear whether {x} reduce: <<ident. binop>> answers x or binop value: ident value: x. It's only when ident is an identity for binop that you can say 'it doesn't matter'. I don't suppose you could bring yourself to call aReduction aMagmaWithIdentity? Had you considered aMagmaWithIdentity reduce: aCollection where the #reduce: method is now in your class so can't *technically* clash with anything else? All you really need from aCollection is #do: so it could even be a stream. MagmaWithIdentity >> identity >> combine:with: >> reduce: anEnumerable |r| r := self identity. anEumerable do: [:each | r := self combine: r with: each]. ^r MagmaSansIdentity >> combine:with: >> reduce: anEnumerable |r f| f := r := nil. anEnumerable do: [:each | r := f ifNil: [f := self. each] ifNotNil: [self combine: r with: each]]. f ifNil: [anEnumerable error: 'is empty']. ^r On Fri, 14 Apr 2023 at 05:02, Steffen MÃ¤rcker <merkste(a)web.de> wrote: The reason I came up with the naming question in the first place is that I (finally !) finish my port of Transducers to Pharo. But currently, I am running into a name clash. Maybe you have some good ideas how to resolve the following situation in a pleasant way. - #fold: exists in Pharo and is an alias of #reduce: - #reduce: exists in Pharo and calls #foldLeft: which also deals with more than two block arguments Both of which are not present in VW. Hence, I used the following messages in VW with no name clash: - #reduce: aReduction "= block + initial value" - #reduce:init: is similar to #inject:into: but executes an additional completion action Some obvious ways to avoid a clash in Pharo are: 1) Make #reduce: distinguish between a reduction and a simple block (e.g. by double dispatch) 2) Rename the transducers #reduce: to #injectInto: and adapt #inject:into: to optionally do the completion 3) Find another selector that is not too counter-intuitive All three approaches have some downsides in my opinion: 1) Though straight forward to implement, both flavors behave quite different, especially with respect to the number of block arguments. The existing one creates a SequenceableCollection and partitions it according to the required number of args. Transducers' #reduce: considers binary blocks as the binary fold case but ternary blocks as fold with indexed elements. 2) This is a real extension of #inject:into: but requires to touch multiple implementations of that message. Something I consider undesirabe. 3) Currently, I cannot think of a good name that is not too far away from what we're familiar with. Do you have some constructive comments and ideas? Kind regards, Steffen Steffen MÃ¤rcker schrieb am Donnerstag, 13. April 2023 17:11:15 (+02:00): :-D I don't know how compress made onto that site. There is not even an example in the list of language examples where fold/reduce is named compress. Richard O'Keefe schrieb am Donnerstag, 13. April 2023 16:34:29 (+02:00): OUCH. Wikipedia is as reliable as ever, I see. compress and reduce aren't even close to the same thing. Since the rank of the result of compression is the same as the rank of the right operand, and the rank of the result of reducing is one lower, they are really quite different. compress is Fortran's PACK. https://gcc.gnu.org/onlinedocs/gfortran/PACK.html On Fri, 14 Apr 2023 at 01:34, Steffen MÃ¤rcker <merkste(a)web.de> wrote: Hi Richard and Sebastian! Interesting read. I obviously was not aware of the variety of meanings for fold/reduce. Thanks for pointing this out. Also, in some languages it seems the same name is used for both reductions with and without an initial value. There's even a list on WP on the matter: https://en.wikipedia.org/wiki/Fold_%28higher-order_function%29#In_various_l… Kind regards, Steffen Richard O'Keefe schrieb am Donnerstag, 13. April 2023 13:16:28 (+02:00): The standard prelude in Haskell does not define anything called "fold". It defines fold{l,r}{,1} which can be applied to any Foldable data (see Data.Foldable). For technical reasons having to do with Haskell's non-strict evaluation, foldl' and foldr' also exist. But NOT "fold". https://hackage.haskell.org/package/base-4.18.0.0/docs/Data-Foldable.html#l… On Thu, 13 Apr 2023 at 21:17, Sebastian Jordan Montano <sebastian.jordan(a)inria.fr> wrote: Hello Steffen, Let's take Kotlin documentation (https://kotlinlang.org/docs/collection-aggregate.html#fold-and-reduce) > The difference between the two functions is that fold() takes an initial value and uses it as the accumulated value on the first step, whereas the first step of reduce() uses the first and the second elements as operation arguments on the first step. Naming is not so consistent in all the programming languages, they mix up the names "reduce" and "fold". For example in Haskell "fold" does not take an initial value, so it is like a "reduce" in Kotlin. In Kotlin, Java, Scala and other oo languages "reduce" does not take an initial value while "fold" does. Pharo align with those languages (except that out fold is called #inject:into:) So for me the Pharo methods #reduce: and #inject:into represent well what they are doing and they are well named. Cheers, Sebastian ----- Mail original ----- > De: "Steffen MÃ¤rcker" <merkste(a)web.de> > Ã: "Any question about pharo is welcome" <pharo-users(a)lists.pharo.org> > EnvoyÃ©: Mercredi 12 Avril 2023 19:03:01 > Objet: [Pharo-users] Collection>>reduce naming > Hi! > > I wonder whether there was a specific reason to name this method #reduce:? > I would have expected #fold: as this is the more common term for what it > does. And in fact, even the comment reads "Fold the result of the receiver > into aBlock." Whereas #reduce: is the common term for what we call with > #inject:into: . > > I am asking not to annoy anyone but out of curiosity. It figured this out > only by some weird behaviour after porting some code that (re)defines > #reduce . > > Ciao! > Steffen -- Gesendet mit Vivaldi Mail. Laden Sie Vivaldi kostenlos unter vivaldi.com herunter

April 17, 2023

This week (15/2023) on the Pharo Issue Tracker.

by Marcus Denker

We merged ~ 80 PRs, closing 33 issues. # Pharo 11 Release is getting closer... - Use Microdown 2.4.0 and BeautifulComments 1.0.0 (preparing for release) #13388 https://github.com/pharo-project/pharo/pull/13388 - use fixed NewTools version #13412 https://github.com/pharo-project/pharo/pull/13412 - provide compatibility with old finalisation mechanism #13410 https://github.com/pharo-project/pharo/pull/13410 - Remove usage of old primitive 91 #13427 https://github.com/pharo-project/pharo/pull/13427 - 12885-Objectassert-fails-with-non-booleans-contradicting-its-own-comment #13251 https://github.com/pharo-project/pharo/pull/13251 - Calypso: check if node is nil before calling isCommentNode and cie #13418 https://github.com/pharo-project/pharo/pull/13418 - fix: ensure right method side (class vs instance) is chosen when looking through history https://github.com/pharo-vcs/iceberg/pulse - NewTools-Debugger-Breakpoints-Tools leaves the image in a dirty state. #504 https://github.com/pharo-spec/NewTools/pull/504 # Pharo12 Cleanups continue. The image is now ~5MB smaller due to the protocol cleanup and code removal. ## Fixes - Weekly Pharo11 sync #13429 https://github.com/pharo-project/pharo/pull/13429 - ClyJumpToTestMethodCommand>>#generateTestMethodNamed:in: use good protocol #13396 https://github.com/pharo-project/pharo/pull/13396 - Completion can extends keyword messages #13402 https://github.com/pharo-project/pharo/pull/13402 - Fix bug in syntaxt highlighting of comments #13319 https://github.com/pharo-project/pharo/pull/13319 - Refactoring rotten green test on Context #13411 https://github.com/pharo-project/pharo/pull/13411 - EpiceaBrowsers: stop catching all errors #13425 https://github.com/pharo-project/pharo/pull/13425 - Make protocol of super method a priority in MethodClassifier #13426 https://github.com/pharo-project/pharo/pull/13426 - 9778-InstructionStream-selectorToSendOrSelf-returns-GlobalVariable-bindings-too #13417 https://github.com/pharo-project/pharo/pull/13417 - Striked through symbols who are names of a deprecated global #13341 https://github.com/pharo-project/pharo/pull/13341 ## Bootrap - Remove dead code in Bootstrap #13435 https://github.com/pharo-project/pharo/pull/13435 - Use date and time as Stdio windows file name distinguisher #13299 https://github.com/pharo-project/pharo/pull/13299 - Cut dependency from Collection-Streams to UIManager #13406 https://github.com/pharo-project/pharo/pull/13406 - Fix dependies of RPackage-Core #13407 https://github.com/pharo-project/pharo/pull/13407 ## CI / Tests - Clean MCMethodDefinitionTest #13376 https://github.com/pharo-project/pharo/pull/13376 - Clean ClassRenameFixTest #13360 https://github.com/pharo-project/pharo/pull/13360 - Finish to cut 'Tests' package #13338 https://github.com/pharo-project/pharo/pull/13338 - Cleanup: Better ratio of commented classes #13329 https://github.com/pharo-project/pharo/pull/13329 - Add logs on Debugger-Oups-Tests to find error #13390 https://github.com/pharo-project/pharo/pull/13390 - FluidClassBuilder tests should clean the system #13404 https://github.com/pharo-project/pharo/pull/13404 - Remove ClassFactoryForTestCaseTest>>#testDuplicateClassWithNewName #13405 https://github.com/pharo-project/pharo/pull/13405 - CompiledCodeTest>>#testMessages should not assume order of elements #13438 https://github.com/pharo-project/pharo/pull/13438 ## Compiler: ASTCache - ASTCache: use a double weak dictionary #13379 https://github.com/pharo-project/pharo/pull/13379 - ASTCache>>#at:put: prevent TOCTOU when cleaning the cache #13408 https://github.com/pharo-project/pharo/pull/13408 - refactor ASTCache #13378 https://github.com/pharo-project/pharo/pull/13378 ## Compiler: CompiledMethods - Compiled methods: keep the source #13359 https://github.com/pharo-project/pharo/pull/13359 - Compiled method drop last property #13386 https://github.com/pharo-project/pharo/pull/13386 ## Compiler - Try to move workspace variables further (lite) #13393 https://github.com/pharo-project/pharo/pull/13393 - Compiler: remove OCASTTranslator subclasses #13352 https://github.com/pharo-project/pharo/pull/13352 - AST: fix node positions, and test them systematically #13350 https://github.com/pharo-project/pharo/pull/13350 - Faulty code importers: use new compiler API #13397 https://github.com/pharo-project/pharo/pull/13397 - OCASTSemanticAnalyzer chose the value of superOf of super-sends #13394 https://github.com/pharo-project/pharo/pull/13394 - OpalCompiler restore undeclared menu on the playground #13392 https://github.com/pharo-project/pharo/pull/13392 - implements RBBlockErrorNode>>#argumentNames #13384 https://github.com/pharo-project/pharo/pull/13384 ## ClassOrganizer/Protocol Cleanup - Introduce CompiledMethod>>#isClassified #13444 https://github.com/pharo-project/pharo/pull/13444 - Move class comment export to ClassDescription #13382 https://github.com/pharo-project/pharo/pull/13382 - Remove ClassDescription>>basicOrganization #13385 https://github.com/pharo-project/pharo/pull/13385 - Remove ClassOrganization>>hasOrganizedClass #13346 https://github.com/pharo-project/pharo/pull/13346 - Some cleanings protocol announcements and announcements #13381 https://github.com/pharo-project/pharo/pull/13381 - Rename Protocol class>>#ambiguous into #traitConflictName #13369 https://github.com/pharo-project/pharo/pull/13369 - Make protocols an array in ClassOrganization #13356 https://github.com/pharo-project/pharo/pull/13356 - Always announce creation of new protocols #13358 https://github.com/pharo-project/pharo/pull/13358 - Simplify protocol removals #13334 https://github.com/pharo-project/pharo/pull/13334 - Remove #protocolsOfSelector: and implement #protocolOfSelector: #13383 https://github.com/pharo-project/pharo/pull/13383 - Change Protocol to use an array for methodSelectors directly #13415 https://github.com/pharo-project/pharo/pull/13415 - Remove the need to give a SystemOrganizer to SystemDictionary #13314 https://github.com/pharo-project/pharo/pull/13314 ## Simple Cleanups - extract return from Float>>#asApproximateFractionAtOrder: #13400 https://github.com/pharo-project/pharo/pull/13400 - extract return from Rectangle>>#quickMerge: and use self class #13372 https://github.com/pharo-project/pharo/pull/13372 - rename truncation and roundoff to truncation and round off protocol in Rectangle #13375 https://github.com/pharo-project/pharo/pull/13375 - use and: expression instead of ifTrue:ifFalse: expression #13362 https://github.com/pharo-project/pharo/pull/13362 - extract return from Number>>#raisedTo: and add some tests #13355 https://github.com/pharo-project/pharo/pull/13355 - Cleanup-Define-subclassresponsability Boolean and Number #13416 https://github.com/pharo-project/pharo/pull/13416 - use and: expresion instead of ifTrue:ifFalse: expression #13439 https://github.com/pharo-project/pharo/pull/13439 - use and: expresion instead of ifTrue:ifFalse: expression in AST-Core #13441 https://github.com/pharo-project/pharo/pull/13441

April 17, 2023

Re: headless mode

by Jesus Mari Aguirre

pharo --nodisplay works for me (pharo 9 on ubuntu) On Tue, Apr 11, 2023 at 5:23â¯PM Christophe TouzÃ© <chris.touze(a)gmail.com> wrote: > Bonjour, > > Quelqu'un pourrait-il me dire svp comment lancer une image Pharo 10 en > mode headless (sous Ubuntu) ? > J'ai essayÃ© "pharo --headless monImage.image" sans succÃ¨s. > PrÃ©cision, j'ai Seaside dans mon image. > Merci d'avance ! > > > Hello, > > Could somebody tell me how to launch a Pharo 10 image in headless mode, > under Ubuntu ? > I have tried "pharo --headless myImage.image", without success. > I have the Seaside package in my image, I don't know if it matters. > Thanks ! > >

April 16, 2023

Re: Collection>>reduce name clash with transducers

by Richard O'Keefe

Let initial :: a combine :: a -> b -> a finish :: a -> c then (finish . foldl combine initial) :: Foldable t => t b -> c This appears to be analogous to your 'reduce with completion'. What *can* be done with composition generally *should* be done with composition; I really don't see any advantage in defining reduce finish combine initial = finish . combine initial As for growing a collection and then finally trimming it to its desired size, I've never known anything like that to be a good idea. There's a reason why my library includes Set BoundedSet IdentitySet BoundedIdentitySet Deque BoundedDeque Heap BoundedHeap I use BoundedHeap a lot. If I want to find the k best things out of n, using BoundedHeap lets me do it in O(n.log k) time and O(k) space instead of O(n.log n) time and O(n) space. Your example showing how much better #reduceLeft: is when expressed using transducers is not well chosen,because the implementation of #reduceLeft: in Pharo is (how to say this politely?) not up to the standards we expect from Pharo. Here is how it stands in my compatibility library: Enumerable methods for: 'summarising' reduceLeft: aBlock <compatibility: #pharo> |n| ^(n := aBlock argumentCount) > 2 ifTrue: [ |i a| a := Array new: n. i := 0. self do: [:each | a at: (i := i + 1) put: each. i = n ifTrue: [ a at: (i := 1) put: (aBlock valueWithArguments: a)]]. i = 1 ifTrue: [a at: i] ifFalse: [ self error: 'collection/block size mismatch']] ifFalse: [ "If n = 0 or 1 and the receiver has two or more elements, this will raise an exception passing two arguments to aBlock. That's a good way to complain about it." |r f| r := f := nil. self do: [:each | r := f ifNil: [f := self. each] ifNotNil: [aBlock value: r value: each]]. r == f ifNil: [CollectionTooSmall collection: self] ifNotNil: [r]] No OrderedCollection. And exactly one traversal of the collection. (Enumerables can only be traversed once. Collections can be traversed multiple times.) The only method the receiver needs to provide is #do:, so this method doesn't really need to be in Enumerable. It could, for example, be in Block. #reduceRight: I've placed in AbstractSequence because it needs #reverseDo:, but it equally makes sense as a method of Block (as it knows more about what Blocks can do than it does about what sequences can do). For example, I have SortedSet and SortedBag which can be traversed forwards and backwards but only #reduceLeft: is available to them; #reduceRight: is not, despite them sensibly supporting #reverseDo:. For that matter, Deques support #reverseDo: but are not sequences... To the limited extent that I understand the Transducers package, this view that (s reduce{Left,Right}: b) should really be (b reduce{Left,Right}) applyTo: s seems 100% in the spirit of Transducers. In fact, now that I understand a bit about Transducers, <collection> reduce: <transducer> (a) seems back to front compared with <reducer> applyTo: <collection> (b) seems like a misnomer because in general much may be generated transformed and retained, with nothing getting smaller, so why 'reduce'? It seems like a special case of applying a function-like object (the transducer) to an argument (the collection), so why not transducer applyTo: dataSource transducer applyTo: dataSource initially: initial Did you look at Richard Waters' "obviously synchronizable series expressions"? (MIT AI Memo 958A and 959A) Or his later SERIES package? (Appendix A of Common Lisp the Language, 2nd edition) On Fri, 14 Apr 2023 at 22:32, Steffen MÃ¤rcker <merkste(a)web.de> wrote: > Hi Richard! > > Thanks for sharing your thoughts. > > There's a reason why #inject:into: puts the block argument > last. It works better to have "heavy" constituents on the > right in an English sentence, and it's easier to indent > blocks when they come last. > > > Nice, I never though of it this way. I always appreciate a historical > background. > > Let me try to respond to the rest with a focus on the ideas. First of all, > the point of the transducers framework is to cleanly separate between > iteration over sequences, processing of the elements and accumulation of a > result. It enables easy reuse the concepts common to different data > structures. > > 1. What do I mean by completion? If we iterate over a sequence of objects, > we sometimes want to do a final step after all elements have seen to > complete the computation. For instance, after copying elements to a new > collection, we may want to trim it to its actual size: > > distinct := col inject: Set new into: #add. > distinct trim. > > For some cases it turns out to be useful to have an object that knows how > to do both: > > distinct := col reduce: (#add completing: #trim) init: Set new. > > #reduce:init: knows how to deal with both this new objects and ordinary > blocks. For now I will call both variants a "reducing function". Note, > completion is completely optional and the implementation is literally > #inject:into: plus completion if required. > > > 2. What is a reduction? In some cases, it turns out to be useful to pair > up a reducing function with an (initial) value. You called it a magma and > often its indeed the neutral element of a mathematical operator, e.g., + > and 0. But we can use a block that yields the initial value, too. For > instance: > > sum := #+ init: 0. > result := numbers reduce: sum. > > toSet := (#add completing: #trim) initializer: [Set new]. > distinct := col reduce: toSet. > > #reduce: is just a shorthand that passes the function and the value to > #reduce:init: Maybe #reduceMagma: is a reasonable name? > > > 3. The reason I implemented #reduce:init: directly on collections, > streams, etc. is that these objects know best how to efficiently iterate > over their elements. And if a data structure knows how to #reduce:init: we > can use it with all the transducers functions, e.g., for partitioning, > filtering etc. Other useful methods could then be added to the behaviour > with a trait, e.g., #transduce:reduce:init which first apples a transducer > and then reduces. As traits are not available in plain VW 8.3, I did not > try this approach, though. > > > 4. Lets take #reduce:Left: as and example and reimplement the method using > transducers, shall we? The following code works for each > sequence/collection/stream that supports #transduce:reduce:init: > > reduceLeft: aBlock > | head rest arity | > head := self transduce: (Take number: 1) reduce: [:r :e | e] init: nil. > rest := Drop number: 1. > > arity := aBlock arity. > ^arity = 2 > ifTrue: [self transduce: rest reduce: aBlock init: head] > ifFalse: [ > | size arguments | > size := arity - 1. > rest := rest * (Partition length: size) * (Remove predicate: [:part | part > size < size]). > arguments := Array new: arity. > arguments at: 1 put: head. > self > transduce: rest > reduce: ([:args :part | > args > replaceFrom: 2 to: arity with: part; > at: 1 put: (aBlock valueWithArguments: args); > yourself] completing: [:args | args first]) > init: arguments] > > This code is both more general and faster: It does not create an > intermediate OrderedCollection and it treats the common case of binary > blocks efficiently. Note the implementation can more compact and optimized > if it was specialized in certain class. For instance, > SequenceableCollection allows accessing elements by index which turns the > first line into a simple "self first". > > Thanks for staying with me for this long reply. I hope I did not miss a > point. I do not insist on the existing names but will appreciate any ideas. > > Best, Steffen > > > > > Richard O'Keefe schrieb am Freitag, 14. April 2023 09:43:32 (+02:00): > > #reduce: aReduction > Are you saying that aReduction is an object from which > a dyadic block and an initial value can be derived? > That's going to confuse the heck out of Dolphin and Pharo > users (like me, for example). And in my copy of Pharo, > #reduce: calls #reduceLeft:, not #foldLeft:. > The sad thing about #reduceLeft: in Pharo is that in order > to provide extra generality I have no use for, it fails to > provide a fast path for the common case of a dyadic block. > > reduceLeft: aBlock > aBlock argumentCount = 2 ifTrue: [ > |r| > r := self first. > self from: 2 to: self last do: [:each | > r := aBlock value: r value: each]. > ^r]. > ... everything else as before ... > > Adding up a million floats takes half the time using the > fast path (67 msec vs 137 msec). Does your #reduce: > also perform "a completion action"? If so, it definitely > should not be named after #inject:into:. > > > > At any rate, if it does something different, it should have > a different name, so #reduce: is no good. > > #reduce:init: > There's a reason why #inject:into: puts the block argument > last. It works better to have "heavy" constituents on the > right in an English sentence, and it's easier to indent > blocks when they come last. > > Which of the arguments here specifies the 'completion action'? > What does the 'completion action' do? (I can't tell from the name.) > > I think the answer is clear: > * choose new intention-revealing names that do not clash. > > If I have have understood your reduce: aReduction correctly, > a Reduction specifies > - a binary operation (not necessarily associative) > - a value which can be passed to that binary operation > which suggests that it represents a magma with identity. > By the way, it is not clear whether > {x} reduce: <<ident. binop>> > answers x or binop value: ident value: x. > It's only when ident is an identity for binop that you > can say 'it doesn't matter'. > I don't suppose you could bring yourself to call > aReduction aMagmaWithIdentity? > > Had you considered > aMagmaWithIdentity reduce: aCollection > where the #reduce: method is now in your class so > can't *technically* clash with anything else? > All you really need from aCollection is #do: so > it could even be a stream. > > MagmaWithIdentity > >> identity > >> combine:with: > >> reduce: anEnumerable > |r| > r := self identity. > anEumerable do: [:each | r := self combine: r with: each]. > ^r > > MagmaSansIdentity > >> combine:with: > >> reduce: anEnumerable > |r f| > f := r := nil. > anEnumerable do: [:each | > r := f ifNil: [f := self. each] ifNotNil: [self combine: r with: > each]]. > f ifNil: [anEnumerable error: 'is empty']. > ^r > > > > > On Fri, 14 Apr 2023 at 05:02, Steffen MÃ¤rcker <merkste(a)web.de> wrote: > >> The reason I came up with the naming question in the first place is that >> I (finally !) finish my port of Transducers to Pharo. But currently, I am >> running into a name clash. Maybe you have some good ideas how to resolve >> the following situation in a pleasant way. >> >> - #fold: exists in Pharo and is an alias of #reduce: >> - #reduce: exists in Pharo and calls #foldLeft: which also deals with >> more than two block arguments >> >> Both of which are not present in VW. Hence, I used the following messages >> in VW with no name clash: >> >> - #reduce: aReduction "= block + initial value" >> - #reduce:init: is similar to #inject:into: but executes an additional >> completion action >> >> Some obvious ways to avoid a clash in Pharo are: >> >> 1) Make #reduce: distinguish between a reduction and a simple block (e.g. >> by double dispatch) >> 2) Rename the transducers #reduce: to #injectInto: and adapt >> #inject:into: to optionally do the completion >> 3) Find another selector that is not too counter-intuitive >> >> All three approaches have some downsides in my opinion: >> 1) Though straight forward to implement, both flavors behave quite >> different, especially with respect to the number of block arguments. The >> existing one creates a SequenceableCollection and partitions it according >> to the required number of args. Transducers' #reduce: considers binary >> blocks as the binary fold case but ternary blocks as fold with indexed >> elements. >> 2) This is a real extension of #inject:into: but requires to touch >> multiple implementations of that message. Something I consider undesirabe. >> 3) Currently, I cannot think of a good name that is not too far away from >> what we're familiar with. >> >> Do you have some constructive comments and ideas? >> >> Kind regards, >> Steffen >> >> >> >> >> Steffen MÃ¤rcker schrieb am Donnerstag, 13. April 2023 17:11:15 (+02:00): >> >> :-D I don't know how compress made onto that site. There is not even an >> example in the list of language examples where fold/reduce is named >> compress. >> >> >> Richard O'Keefe schrieb am Donnerstag, 13. April 2023 16:34:29 (+02:00): >> >> OUCH. Wikipedia is as reliable as ever, I see. >> compress and reduce aren't even close to the same thing. >> Since the rank of the result of compression is the same >> as the rank of the right operand, and the rank of the >> result of reducing is one lower, they are really quite >> different. compress is Fortran's PACK. >> https://gcc.gnu.org/onlinedocs/gfortran/PACK.html >> >> On Fri, 14 Apr 2023 at 01:34, Steffen MÃ¤rcker <merkste(a)web.de> wrote: >> >>> Hi Richard and Sebastian! >>> >>> Interesting read. I obviously was not aware of the variety of meanings >>> for fold/reduce. Thanks for pointing this out. Also, in some languages it >>> seems the same name is used for both reductions with and without an initial >>> value. There's even a list on WP on the matter: >>> https://en.wikipedia.org/wiki/Fold_%28higher-order_function%29#In_various_l… >>> >>> Kind regards, >>> Steffen >>> >>> Richard O'Keefe schrieb am Donnerstag, 13. April 2023 13:16:28 (+02:00): >>> >>> The standard prelude in Haskell does not define anything >>> called "fold". It defines fold{l,r}{,1} which can be >>> applied to any Foldable data (see Data.Foldable). For >>> technical reasons having to do with Haskell's >>> non-strict evaluation, foldl' and foldr' also exist. >>> But NOT "fold". >>> >>> >>> https://hackage.haskell.org/package/base-4.18.0.0/docs/Data-Foldable.html#l… >>> >>> >>> On Thu, 13 Apr 2023 at 21:17, Sebastian Jordan Montano < >>> sebastian.jordan(a)inria.fr> wrote: >>> >>>> Hello Steffen, >>>> >>>> Let's take Kotlin documentation ( >>>> https://kotlinlang.org/docs/collection-aggregate.html#fold-and-reduce) >>>> >>>> > The difference between the two functions is that fold() takes an >>>> initial value and uses it as the accumulated value on the first step, >>>> whereas the first step of reduce() uses the first and the second elements >>>> as operation arguments on the first step. >>>> >>>> Naming is not so consistent in all the programming languages, they mix >>>> up the names "reduce" and "fold". For example in Haskell "fold" does not >>>> take an initial value, so it is like a "reduce" in Kotlin. In Kotlin, Java, >>>> Scala and other oo languages "reduce" does not take an initial value while >>>> "fold" does. Pharo align with those languages (except that out fold is >>>> called #inject:into:) >>>> >>>> So for me the Pharo methods #reduce: and #inject:into represent well >>>> what they are doing and they are well named. >>>> >>>> Cheers, >>>> Sebastian >>>> >>>> ----- Mail original ----- >>>> > De: "Steffen MÃ¤rcker" <merkste(a)web.de> >>>> > Ã: "Any question about pharo is welcome" <pharo-users(a)lists.pharo.org >>>> > >>>> > EnvoyÃ©: Mercredi 12 Avril 2023 19:03:01 >>>> > Objet: [Pharo-users] Collection>>reduce naming >>>> >>>> > Hi! >>>> > >>>> > I wonder whether there was a specific reason to name this method >>>> #reduce:? >>>> > I would have expected #fold: as this is the more common term for what >>>> it >>>> > does. And in fact, even the comment reads "Fold the result of the >>>> receiver >>>> > into aBlock." Whereas #reduce: is the common term for what we call >>>> with >>>> > #inject:into: . >>>> > >>>> > I am asking not to annoy anyone but out of curiosity. It figured this >>>> out >>>> > only by some weird behaviour after porting some code that (re)defines >>>> > #reduce . >>>> > >>>> > Ciao! >>>> > Steffen >>>> >>> >> -- >> Gesendet mit Vivaldi Mail. Laden Sie Vivaldi kostenlos von vivaldi.com >> herunter. >> >

April 15, 2023

Re: Collection>>reduce name clash with transducers

by Steffen MÃ¤rcker

Hi Richard! Thanks for sharing your thoughts. There's a reason why #inject:into: puts the block argument last. It works better to have "heavy" constituents on the right in an English sentence, and it's easier to indent blocks when they come last. Nice, I never though of it this way. I always appreciate a historical background. Let me try to respond to the rest with a focus on the ideas. First of all, the point of the transducers framework is to cleanly separate between iteration over sequences, processing of the elements and accumulation of a result. It enables easy reuse the concepts common to different data structures. 1. What do I mean by completion? If we iterate over a sequence of objects, we sometimes want to do a final step after all elements have seen to complete the computation. For instance, after copying elements to a new collection, we may want to trim it to its actual size: distinct := col inject: Set new into: #add. distinct trim. For some cases it turns out to be useful to have an object that knows how to do both: distinct := col reduce: (#add completing: #trim) init: Set new. #reduce:init: knows how to deal with both this new objects and ordinary blocks. For now I will call both variants a "reducing function". Note, completion is completely optional and the implementation is literally #inject:into: plus completion if required. 2. What is a reduction? In some cases, it turns out to be useful to pair up a reducing function with an (initial) value. You called it a magma and often its indeed the neutral element of a mathematical operator, e.g., + and 0. But we can use a block that yields the initial value, too. For instance: sum := #+ init: 0. result := numbers reduce: sum. toSet := (#add completing: #trim) initializer: [Set new]. distinct := col reduce: toSet. #reduce: is just a shorthand that passes the function and the value to #reduce:init: Maybe #reduceMagma: is a reasonable name? 3. The reason I implemented #reduce:init: directly on collections, streams, etc. is that these objects know best how to efficiently iterate over their elements. And if a data structure knows how to #reduce:init: we can use it with all the transducers functions, e.g., for partitioning, filtering etc. Other useful methods could then be added to the behaviour with a trait, e.g., #transduce:reduce:init which first apples a transducer and then reduces. As traits are not available in plain VW 8.3, I did not try this approach, though. 4. Lets take #reduce:Left: as and example and reimplement the method using transducers, shall we? The following code works for each sequence/collection/stream that supports #transduce:reduce:init: reduceLeft: aBlock | head rest arity | head := self transduce: (Take number: 1) reduce: [:r :e | e] init: nil. rest := Drop number: 1. arity := aBlock arity. ^arity = 2 ifTrue: [self transduce: rest reduce: aBlock init: head] ifFalse: [ | size arguments | size := arity - 1. rest := rest * (Partition length: size) * (Remove predicate: [:part | part size < size]). arguments := Array new: arity. arguments at: 1 put: head. self transduce: rest reduce: ([:args :part | args replaceFrom: 2 to: arity with: part; at: 1 put: (aBlock valueWithArguments: args); yourself] completing: [:args | args first]) init: arguments] This code is both more general and faster: It does not create an intermediate OrderedCollection and it treats the common case of binary blocks efficiently. Note the implementation can more compact and optimized if it was specialized in certain class. For instance, SequenceableCollection allows accessing elements by index which turns the first line into a simple "self first". Thanks for staying with me for this long reply. I hope I did not miss a point. I do not insist on the existing names but will appreciate any ideas. Best, Steffen Richard O'Keefe schrieb am Freitag, 14. April 2023 09:43:32 (+02:00): #reduce: aReduction Are you saying that aReduction is an object from which a dyadic block and an initial value can be derived? That's going to confuse the heck out of Dolphin and Pharo users (like me, for example). And in my copy of Pharo, #reduce: calls #reduceLeft:, not #foldLeft:. The sad thing about #reduceLeft: in Pharo is that in order to provide extra generality I have no use for, it fails to provide a fast path for the common case of a dyadic block. reduceLeft: aBlock aBlock argumentCount = 2 ifTrue: [ |r| r := self first. self from: 2 to: self last do: [:each | r := aBlock value: r value: each]. ^r]. ... everything else as before ... Adding up a million floats takes half the time using the fast path (67 msec vs 137 msec). Does your #reduce: also perform "a completion action"? If so, it definitely should not be named after #inject:into:. At any rate, if it does something different, it should have a different name, so #reduce: is no good. #reduce:init: There's a reason why #inject:into: puts the block argument last. It works better to have "heavy" constituents on the right in an English sentence, and it's easier to indent blocks when they come last. Which of the arguments here specifies the 'completion action'? What does the 'completion action' do? (I can't tell from the name.) I think the answer is clear: * choose new intention-revealing names that do not clash. If I have have understood your reduce: aReduction correctly, a Reduction specifies - a binary operation (not necessarily associative) - a value which can be passed to that binary operation which suggests that it represents a magma with identity. By the way, it is not clear whether {x} reduce: <<ident. binop>> answers x or binop value: ident value: x. It's only when ident is an identity for binop that you can say 'it doesn't matter'. I don't suppose you could bring yourself to call aReduction aMagmaWithIdentity? Had you considered aMagmaWithIdentity reduce: aCollection where the #reduce: method is now in your class so can't *technically* clash with anything else? All you really need from aCollection is #do: so it could even be a stream. MagmaWithIdentity >> identity >> combine:with: >> reduce: anEnumerable |r| r := self identity. anEumerable do: [:each | r := self combine: r with: each]. ^r MagmaSansIdentity >> combine:with: >> reduce: anEnumerable |r f| f := r := nil. anEnumerable do: [:each | r := f ifNil: [f := self. each] ifNotNil: [self combine: r with: each]]. f ifNil: [anEnumerable error: 'is empty']. ^r On Fri, 14 Apr 2023 at 05:02, Steffen MÃ¤rcker <merkste(a)web.de> wrote: The reason I came up with the naming question in the first place is that I (finally !) finish my port of Transducers to Pharo. But currently, I am running into a name clash. Maybe you have some good ideas how to resolve the following situation in a pleasant way. - #fold: exists in Pharo and is an alias of #reduce: - #reduce: exists in Pharo and calls #foldLeft: which also deals with more than two block arguments Both of which are not present in VW. Hence, I used the following messages in VW with no name clash: - #reduce: aReduction "= block + initial value" - #reduce:init: is similar to #inject:into: but executes an additional completion action Some obvious ways to avoid a clash in Pharo are: 1) Make #reduce: distinguish between a reduction and a simple block (e.g. by double dispatch) 2) Rename the transducers #reduce: to #injectInto: and adapt #inject:into: to optionally do the completion 3) Find another selector that is not too counter-intuitive All three approaches have some downsides in my opinion: 1) Though straight forward to implement, both flavors behave quite different, especially with respect to the number of block arguments. The existing one creates a SequenceableCollection and partitions it according to the required number of args. Transducers' #reduce: considers binary blocks as the binary fold case but ternary blocks as fold with indexed elements. 2) This is a real extension of #inject:into: but requires to touch multiple implementations of that message. Something I consider undesirabe. 3) Currently, I cannot think of a good name that is not too far away from what we're familiar with. Do you have some constructive comments and ideas? Kind regards, Steffen Steffen MÃ¤rcker schrieb am Donnerstag, 13. April 2023 17:11:15 (+02:00): :-D I don't know how compress made onto that site. There is not even an example in the list of language examples where fold/reduce is named compress. Richard O'Keefe schrieb am Donnerstag, 13. April 2023 16:34:29 (+02:00): OUCH. Wikipedia is as reliable as ever, I see. compress and reduce aren't even close to the same thing. Since the rank of the result of compression is the same as the rank of the right operand, and the rank of the result of reducing is one lower, they are really quite different. compress is Fortran's PACK. https://gcc.gnu.org/onlinedocs/gfortran/PACK.html On Fri, 14 Apr 2023 at 01:34, Steffen MÃ¤rcker <merkste(a)web.de> wrote: Hi Richard and Sebastian! Interesting read. I obviously was not aware of the variety of meanings for fold/reduce. Thanks for pointing this out. Also, in some languages it seems the same name is used for both reductions with and without an initial value. There's even a list on WP on the matter: https://en.wikipedia.org/wiki/Fold_%28higher-order_function%29#In_various_l… Kind regards, Steffen Richard O'Keefe schrieb am Donnerstag, 13. April 2023 13:16:28 (+02:00): The standard prelude in Haskell does not define anything called "fold". It defines fold{l,r}{,1} which can be applied to any Foldable data (see Data.Foldable). For technical reasons having to do with Haskell's non-strict evaluation, foldl' and foldr' also exist. But NOT "fold". https://hackage.haskell.org/package/base-4.18.0.0/docs/Data-Foldable.html#l… On Thu, 13 Apr 2023 at 21:17, Sebastian Jordan Montano <sebastian.jordan(a)inria.fr> wrote: Hello Steffen, Let's take Kotlin documentation (https://kotlinlang.org/docs/collection-aggregate.html#fold-and-reduce) > The difference between the two functions is that fold() takes an initial value and uses it as the accumulated value on the first step, whereas the first step of reduce() uses the first and the second elements as operation arguments on the first step. Naming is not so consistent in all the programming languages, they mix up the names "reduce" and "fold". For example in Haskell "fold" does not take an initial value, so it is like a "reduce" in Kotlin. In Kotlin, Java, Scala and other oo languages "reduce" does not take an initial value while "fold" does. Pharo align with those languages (except that out fold is called #inject:into:) So for me the Pharo methods #reduce: and #inject:into represent well what they are doing and they are well named. Cheers, Sebastian ----- Mail original ----- > De: "Steffen MÃ¤rcker" <merkste(a)web.de> > Ã: "Any question about pharo is welcome" <pharo-users(a)lists.pharo.org> > EnvoyÃ©: Mercredi 12 Avril 2023 19:03:01 > Objet: [Pharo-users] Collection>>reduce naming > Hi! > > I wonder whether there was a specific reason to name this method #reduce:? > I would have expected #fold: as this is the more common term for what it > does. And in fact, even the comment reads "Fold the result of the receiver > into aBlock." Whereas #reduce: is the common term for what we call with > #inject:into: . > > I am asking not to annoy anyone but out of curiosity. It figured this out > only by some weird behaviour after porting some code that (re)defines > #reduce . > > Ciao! > Steffen -- Gesendet mit Vivaldi Mail. Laden Sie Vivaldi kostenlos von vivaldi.com herunter.

April 14, 2023

Re: Collection>>reduce name clash with transducers

by Richard O'Keefe

#reduce: aReduction Are you saying that aReduction is an object from which a dyadic block and an initial value can be derived? That's going to confuse the heck out of Dolphin and Pharo users (like me, for example). And in my copy of Pharo, #reduce: calls #reduceLeft:, not #foldLeft:. The sad thing about #reduceLeft: in Pharo is that in order to provide extra generality I have no use for, it fails to provide a fast path for the common case of a dyadic block. reduceLeft: aBlock aBlock argumentCount = 2 ifTrue: [ |r| r := self first. self from: 2 to: self last do: [:each | r := aBlock value: r value: each]. ^r]. ... everything else as before ... Adding up a million floats takes half the time using the fast path (67 msec vs 137 msec). Does your #reduce: also perform "a completion action"? If so, it definitely should not be named after #inject:into:. At any rate, if it does something different, it should have a different name, so #reduce: is no good. #reduce:init: There's a reason why #inject:into: puts the block argument last. It works better to have "heavy" constituents on the right in an English sentence, and it's easier to indent blocks when they come last. Which of the arguments here specifies the 'completion action'? What does the 'completion action' do? (I can't tell from the name.) I think the answer is clear: * choose new intention-revealing names that do not clash. If I have have understood your reduce: aReduction correctly, a Reduction specifies - a binary operation (not necessarily associative) - a value which can be passed to that binary operation which suggests that it represents a magma with identity. By the way, it is not clear whether {x} reduce: <<ident. binop>> answers x or binop value: ident value: x. It's only when ident is an identity for binop that you can say 'it doesn't matter'. I don't suppose you could bring yourself to call aReduction aMagmaWithIdentity? Had you considered aMagmaWithIdentity reduce: aCollection where the #reduce: method is now in your class so can't *technically* clash with anything else? All you really need from aCollection is #do: so it could even be a stream. MagmaWithIdentity >> identity >> combine:with: >> reduce: anEnumerable |r| r := self identity. anEumerable do: [:each | r := self combine: r with: each]. ^r MagmaSansIdentity >> combine:with: >> reduce: anEnumerable |r f| f := r := nil. anEnumerable do: [:each | r := f ifNil: [f := self. each] ifNotNil: [self combine: r with: each]]. f ifNil: [anEnumerable error: 'is empty']. ^r On Fri, 14 Apr 2023 at 05:02, Steffen MÃ¤rcker <merkste(a)web.de> wrote: > The reason I came up with the naming question in the first place is that I > (finally !) finish my port of Transducers to Pharo. But currently, I am > running into a name clash. Maybe you have some good ideas how to resolve > the following situation in a pleasant way. > > - #fold: exists in Pharo and is an alias of #reduce: > - #reduce: exists in Pharo and calls #foldLeft: which also deals with more > than two block arguments > > Both of which are not present in VW. Hence, I used the following messages > in VW with no name clash: > > - #reduce: aReduction "= block + initial value" > - #reduce:init: is similar to #inject:into: but executes an additional > completion action > > Some obvious ways to avoid a clash in Pharo are: > > 1) Make #reduce: distinguish between a reduction and a simple block (e.g. > by double dispatch) > 2) Rename the transducers #reduce: to #injectInto: and adapt #inject:into: > to optionally do the completion > 3) Find another selector that is not too counter-intuitive > > All three approaches have some downsides in my opinion: > 1) Though straight forward to implement, both flavors behave quite > different, especially with respect to the number of block arguments. The > existing one creates a SequenceableCollection and partitions it according > to the required number of args. Transducers' #reduce: considers binary > blocks as the binary fold case but ternary blocks as fold with indexed > elements. > 2) This is a real extension of #inject:into: but requires to touch > multiple implementations of that message. Something I consider undesirabe. > 3) Currently, I cannot think of a good name that is not too far away from > what we're familiar with. > > Do you have some constructive comments and ideas? > > Kind regards, > Steffen > > > > > Steffen MÃ¤rcker schrieb am Donnerstag, 13. April 2023 17:11:15 (+02:00): > > :-D I don't know how compress made onto that site. There is not even an > example in the list of language examples where fold/reduce is named > compress. > > > Richard O'Keefe schrieb am Donnerstag, 13. April 2023 16:34:29 (+02:00): > > OUCH. Wikipedia is as reliable as ever, I see. > compress and reduce aren't even close to the same thing. > Since the rank of the result of compression is the same > as the rank of the right operand, and the rank of the > result of reducing is one lower, they are really quite > different. compress is Fortran's PACK. > https://gcc.gnu.org/onlinedocs/gfortran/PACK.html > > On Fri, 14 Apr 2023 at 01:34, Steffen MÃ¤rcker <merkste(a)web.de> wrote: > >> Hi Richard and Sebastian! >> >> Interesting read. I obviously was not aware of the variety of meanings >> for fold/reduce. Thanks for pointing this out. Also, in some languages it >> seems the same name is used for both reductions with and without an initial >> value. There's even a list on WP on the matter: >> https://en.wikipedia.org/wiki/Fold_%28higher-order_function%29#In_various_l… >> >> Kind regards, >> Steffen >> >> Richard O'Keefe schrieb am Donnerstag, 13. April 2023 13:16:28 (+02:00): >> >> The standard prelude in Haskell does not define anything >> called "fold". It defines fold{l,r}{,1} which can be >> applied to any Foldable data (see Data.Foldable). For >> technical reasons having to do with Haskell's >> non-strict evaluation, foldl' and foldr' also exist. >> But NOT "fold". >> >> >> https://hackage.haskell.org/package/base-4.18.0.0/docs/Data-Foldable.html#l… >> >> >> On Thu, 13 Apr 2023 at 21:17, Sebastian Jordan Montano < >> sebastian.jordan(a)inria.fr> wrote: >> >>> Hello Steffen, >>> >>> Let's take Kotlin documentation ( >>> https://kotlinlang.org/docs/collection-aggregate.html#fold-and-reduce) >>> >>> > The difference between the two functions is that fold() takes an >>> initial value and uses it as the accumulated value on the first step, >>> whereas the first step of reduce() uses the first and the second elements >>> as operation arguments on the first step. >>> >>> Naming is not so consistent in all the programming languages, they mix >>> up the names "reduce" and "fold". For example in Haskell "fold" does not >>> take an initial value, so it is like a "reduce" in Kotlin. In Kotlin, Java, >>> Scala and other oo languages "reduce" does not take an initial value while >>> "fold" does. Pharo align with those languages (except that out fold is >>> called #inject:into:) >>> >>> So for me the Pharo methods #reduce: and #inject:into represent well >>> what they are doing and they are well named. >>> >>> Cheers, >>> Sebastian >>> >>> ----- Mail original ----- >>> > De: "Steffen MÃ¤rcker" <merkste(a)web.de> >>> > Ã: "Any question about pharo is welcome" <pharo-users(a)lists.pharo.org> >>> > EnvoyÃ©: Mercredi 12 Avril 2023 19:03:01 >>> > Objet: [Pharo-users] Collection>>reduce naming >>> >>> > Hi! >>> > >>> > I wonder whether there was a specific reason to name this method >>> #reduce:? >>> > I would have expected #fold: as this is the more common term for what >>> it >>> > does. And in fact, even the comment reads "Fold the result of the >>> receiver >>> > into aBlock." Whereas #reduce: is the common term for what we call with >>> > #inject:into: . >>> > >>> > I am asking not to annoy anyone but out of curiosity. It figured this >>> out >>> > only by some weird behaviour after porting some code that (re)defines >>> > #reduce . >>> > >>> > Ciao! >>> > Steffen >>> >> > -- > Gesendet mit Vivaldi Mail. Laden Sie Vivaldi kostenlos von vivaldi.com > herunter. > >

April 14, 2023

Re: Collection>>reduce name clash with transducers

by Steffen MÃ¤rcker

The reason I came up with the naming question in the first place is that I (finally !) finish my port of Transducers to Pharo. But currently, I am running into a name clash. Maybe you have some good ideas how to resolve the following situation in a pleasant way. - #fold: exists in Pharo and is an alias of #reduce: - #reduce: exists in Pharo and calls #foldLeft: which also deals with more than two block arguments Both of which are not present in VW. Hence, I used the following messages in VW with no name clash: - #reduce: aReduction "= block + initial value" - #reduce:init: is similar to #inject:into: but executes an additional completion action Some obvious ways to avoid a clash in Pharo are: 1) Make #reduce: distinguish between a reduction and a simple block (e.g. by double dispatch) 2) Rename the transducers #reduce: to #injectInto: and adapt #inject:into: to optionally do the completion 3) Find another selector that is not too counter-intuitive All three approaches have some downsides in my opinion: 1) Though straight forward to implement, both flavors behave quite different, especially with respect to the number of block arguments. The existing one creates a SequenceableCollection and partitions it according to the required number of args. Transducers' #reduce: considers binary blocks as the binary fold case but ternary blocks as fold with indexed elements. 2) This is a real extension of #inject:into: but requires to touch multiple implementations of that message. Something I consider undesirabe. 3) Currently, I cannot think of a good name that is not too far away from what we're familiar with. Do you have some constructive comments and ideas? Kind regards, Steffen Steffen MÃ¤rcker schrieb am Donnerstag, 13. April 2023 17:11:15 (+02:00): :-D I don't know how compress made onto that site. There is not even an example in the list of language examples where fold/reduce is named compress. Richard O'Keefe schrieb am Donnerstag, 13. April 2023 16:34:29 (+02:00): OUCH. Wikipedia is as reliable as ever, I see. compress and reduce aren't even close to the same thing. Since the rank of the result of compression is the same as the rank of the right operand, and the rank of the result of reducing is one lower, they are really quite different. compress is Fortran's PACK. https://gcc.gnu.org/onlinedocs/gfortran/PACK.html On Fri, 14 Apr 2023 at 01:34, Steffen MÃ¤rcker <merkste(a)web.de> wrote: Hi Richard and Sebastian! Interesting read. I obviously was not aware of the variety of meanings for fold/reduce. Thanks for pointing this out. Also, in some languages it seems the same name is used for both reductions with and without an initial value. There's even a list on WP on the matter: https://en.wikipedia.org/wiki/Fold_%28higher-order_function%29#In_various_l… Kind regards, Steffen Richard O'Keefe schrieb am Donnerstag, 13. April 2023 13:16:28 (+02:00): The standard prelude in Haskell does not define anything called "fold". It defines fold{l,r}{,1} which can be applied to any Foldable data (see Data.Foldable). For technical reasons having to do with Haskell's non-strict evaluation, foldl' and foldr' also exist. But NOT "fold". https://hackage.haskell.org/package/base-4.18.0.0/docs/Data-Foldable.html#l… On Thu, 13 Apr 2023 at 21:17, Sebastian Jordan Montano <sebastian.jordan(a)inria.fr> wrote: Hello Steffen, Let's take Kotlin documentation (https://kotlinlang.org/docs/collection-aggregate.html#fold-and-reduce) > The difference between the two functions is that fold() takes an initial value and uses it as the accumulated value on the first step, whereas the first step of reduce() uses the first and the second elements as operation arguments on the first step. Naming is not so consistent in all the programming languages, they mix up the names "reduce" and "fold". For example in Haskell "fold" does not take an initial value, so it is like a "reduce" in Kotlin. In Kotlin, Java, Scala and other oo languages "reduce" does not take an initial value while "fold" does. Pharo align with those languages (except that out fold is called #inject:into:) So for me the Pharo methods #reduce: and #inject:into represent well what they are doing and they are well named. Cheers, Sebastian ----- Mail original ----- > De: "Steffen MÃ¤rcker" <merkste(a)web.de> > Ã: "Any question about pharo is welcome" <pharo-users(a)lists.pharo.org> > EnvoyÃ©: Mercredi 12 Avril 2023 19:03:01 > Objet: [Pharo-users] Collection>>reduce naming > Hi! > > I wonder whether there was a specific reason to name this method #reduce:? > I would have expected #fold: as this is the more common term for what it > does. And in fact, even the comment reads "Fold the result of the receiver > into aBlock." Whereas #reduce: is the common term for what we call with > #inject:into: . > > I am asking not to annoy anyone but out of curiosity. It figured this out > only by some weird behaviour after porting some code that (re)defines > #reduce . > > Ciao! > Steffen -- Gesendet mit Vivaldi Mail. Laden Sie Vivaldi kostenlos von vivaldi.com herunter.

April 13, 2023

Re: Collection>>reduce naming

by Steffen MÃ¤rcker

:-D I don't know how compress made onto that site. There is not even an example in the list of language examples where fold/reduce is named compress. Richard O'Keefe schrieb am Donnerstag, 13. April 2023 16:34:29 (+02:00): OUCH. Wikipedia is as reliable as ever, I see. compress and reduce aren't even close to the same thing. Since the rank of the result of compression is the same as the rank of the right operand, and the rank of the result of reducing is one lower, they are really quite different. compress is Fortran's PACK. https://gcc.gnu.org/onlinedocs/gfortran/PACK.html On Fri, 14 Apr 2023 at 01:34, Steffen MÃ¤rcker <merkste(a)web.de> wrote: Hi Richard and Sebastian! Interesting read. I obviously was not aware of the variety of meanings for fold/reduce. Thanks for pointing this out. Also, in some languages it seems the same name is used for both reductions with and without an initial value. There's even a list on WP on the matter: https://en.wikipedia.org/wiki/Fold_%28higher-order_function%29#In_various_l… Kind regards, Steffen Richard O'Keefe schrieb am Donnerstag, 13. April 2023 13:16:28 (+02:00): The standard prelude in Haskell does not define anything called "fold". It defines fold{l,r}{,1} which can be applied to any Foldable data (see Data.Foldable). For technical reasons having to do with Haskell's non-strict evaluation, foldl' and foldr' also exist. But NOT "fold". https://hackage.haskell.org/package/base-4.18.0.0/docs/Data-Foldable.html#l… On Thu, 13 Apr 2023 at 21:17, Sebastian Jordan Montano <sebastian.jordan(a)inria.fr> wrote: Hello Steffen, Let's take Kotlin documentation (https://kotlinlang.org/docs/collection-aggregate.html#fold-and-reduce) > The difference between the two functions is that fold() takes an initial value and uses it as the accumulated value on the first step, whereas the first step of reduce() uses the first and the second elements as operation arguments on the first step. Naming is not so consistent in all the programming languages, they mix up the names "reduce" and "fold". For example in Haskell "fold" does not take an initial value, so it is like a "reduce" in Kotlin. In Kotlin, Java, Scala and other oo languages "reduce" does not take an initial value while "fold" does. Pharo align with those languages (except that out fold is called #inject:into:) So for me the Pharo methods #reduce: and #inject:into represent well what they are doing and they are well named. Cheers, Sebastian ----- Mail original ----- > De: "Steffen MÃ¤rcker" <merkste(a)web.de> > Ã: "Any question about pharo is welcome" <pharo-users(a)lists.pharo.org> > EnvoyÃ©: Mercredi 12 Avril 2023 19:03:01 > Objet: [Pharo-users] Collection>>reduce naming > Hi! > > I wonder whether there was a specific reason to name this method #reduce:? > I would have expected #fold: as this is the more common term for what it > does. And in fact, even the comment reads "Fold the result of the receiver > into aBlock." Whereas #reduce: is the common term for what we call with > #inject:into: . > > I am asking not to annoy anyone but out of curiosity. It figured this out > only by some weird behaviour after porting some code that (re)defines > #reduce . > > Ciao! > Steffen -- Gesendet mit Vivaldi Mail. Laden Sie Vivaldi kostenlos von vivaldi.com herunter.

April 13, 2023

Re: Collection>>reduce naming

by Richard O'Keefe

OUCH. Wikipedia is as reliable as ever, I see. compress and reduce aren't even close to the same thing. Since the rank of the result of compression is the same as the rank of the right operand, and the rank of the result of reducing is one lower, they are really quite different. compress is Fortran's PACK. https://gcc.gnu.org/onlinedocs/gfortran/PACK.html On Fri, 14 Apr 2023 at 01:34, Steffen MÃ¤rcker <merkste(a)web.de> wrote: > Hi Richard and Sebastian! > > Interesting read. I obviously was not aware of the variety of meanings for > fold/reduce. Thanks for pointing this out. Also, in some languages it seems > the same name is used for both reductions with and without an initial > value. There's even a list on WP on the matter: > https://en.wikipedia.org/wiki/Fold_%28higher-order_function%29#In_various_l… > > Kind regards, > Steffen > > Richard O'Keefe schrieb am Donnerstag, 13. April 2023 13:16:28 (+02:00): > > The standard prelude in Haskell does not define anything > called "fold". It defines fold{l,r}{,1} which can be > applied to any Foldable data (see Data.Foldable). For > technical reasons having to do with Haskell's > non-strict evaluation, foldl' and foldr' also exist. > But NOT "fold". > > > https://hackage.haskell.org/package/base-4.18.0.0/docs/Data-Foldable.html#l… > > > On Thu, 13 Apr 2023 at 21:17, Sebastian Jordan Montano < > sebastian.jordan(a)inria.fr> wrote: > >> Hello Steffen, >> >> Let's take Kotlin documentation ( >> https://kotlinlang.org/docs/collection-aggregate.html#fold-and-reduce) >> >> > The difference between the two functions is that fold() takes an >> initial value and uses it as the accumulated value on the first step, >> whereas the first step of reduce() uses the first and the second elements >> as operation arguments on the first step. >> >> Naming is not so consistent in all the programming languages, they mix up >> the names "reduce" and "fold". For example in Haskell "fold" does not take >> an initial value, so it is like a "reduce" in Kotlin. In Kotlin, Java, >> Scala and other oo languages "reduce" does not take an initial value while >> "fold" does. Pharo align with those languages (except that out fold is >> called #inject:into:) >> >> So for me the Pharo methods #reduce: and #inject:into represent well what >> they are doing and they are well named. >> >> Cheers, >> Sebastian >> >> ----- Mail original ----- >> > De: "Steffen MÃ¤rcker" <merkste(a)web.de> >> > Ã: "Any question about pharo is welcome" <pharo-users(a)lists.pharo.org> >> > EnvoyÃ©: Mercredi 12 Avril 2023 19:03:01 >> > Objet: [Pharo-users] Collection>>reduce naming >> >> > Hi! >> > >> > I wonder whether there was a specific reason to name this method >> #reduce:? >> > I would have expected #fold: as this is the more common term for what it >> > does. And in fact, even the comment reads "Fold the result of the >> receiver >> > into aBlock." Whereas #reduce: is the common term for what we call with >> > #inject:into: . >> > >> > I am asking not to annoy anyone but out of curiosity. It figured this >> out >> > only by some weird behaviour after porting some code that (re)defines >> > #reduce . >> > >> > Ciao! >> > Steffen >> > > -- > Gesendet mit Vivaldi Mail. Laden Sie Vivaldi kostenlos von vivaldi.com > herunter. >

April 13, 2023

Re: Comparison of blocks

by Steffen MÃ¤rcker

I forgot: Is there currently a good way to test whether a block is a copying block (in the VW meaning) in Pharo (11)? This means a block that: - Copies only variables not changing after block creation - Does not need the outer context for evaluation So far did not find an obvious way. It seems that a block always has a reference to its outer context. Variables in copiedValues are not modified after block creation if I understand the class comment correctly, but variables in tempVector can, right? Best, Steffen Steffen MÃ¤rcker schrieb am Donnerstag, 13. April 2023 15:14:16 (+02:00): Hi Richard! You're completely right. Function equivalence is a beast and in the context of a computer program undecidable for nontrivial cases. And that's a valid reason to ban this entirely. Personally, I can also see some value in recognizing equality in trivial cases, e.g., 1) constant blocks: [ <same code> ] = [ <same code> ] 2) pure functions: [:a1 ... | <same code> ] = [:a1 ... | <same code> ] 3) enclosed constants: same as 1) and 2) but with references to variables that do not change after block creation. If I am not mistaken VW 1) and 2) are considered clean blocks and 3) a copying block. For both equality is recognized if the bytecode is identical even if they are created in different contexts. Why do think VW regards them not equal? Do you mean another case or did I miss something? I did a short positive test in my VW 8.3 image. Of course, one can have different opinions on the matter depending on the applications. I just wonder whether it was a conscious decision not to implement this in Pharo or just one of the thing that could be but haven't been done yet. And no, I do not rely on this functionality. I am just curious. ;-) Kind regards, Steffen Richard O'Keefe schrieb am Donnerstag, 13. April 2023 12:17:05 (+02:00): There is no agreement between Smalltalk systems about how to compare block contexts for equality. In Smalltalk-80 (and I have two versions of Smalltalk-80 to compare), block equality is identity. The same in VisualAge Smalltalk 8.6.3. The same in GNU Smalltalk. The same in Smalltalk/X-JV. Squeak has a similar definition to VW. My reading of the ANSI standard is that it is carefully vague about this. Equality of functions has been troublesome for decades. Haskell: bans it. Standard ML: bans it. Some other ML-family languages: it's a run-time error. Lisp family: varies. Interlisp says nothing. Scheme gives lower and upper bounds. Imagine a Smalltalk that recognises [<literal>] blocks and allocates one static closure per <literal>. Then [true] == [true] hence [true] = [true] even when the two <block constructor>s were in different methods. The Squeak and VW definitions would regard them as unequal. (This is on my TODO list, principally for [] [true] [false] and [0].) For the special case of [], you don't *have* to imagine it. If I'm reading VAST correctly, it treats "empty blocks" specially. If you *rely* on the definition of #= for block contexts/closures you are almost certainly doing something dangerous. You are certainly doing something that is not portable. On Thu, 13 Apr 2023 at 18:55, Steffen MÃ¤rcker <merkste(a)web.de> wrote: Hi! In VisualWorks, blocks can be compared with each other. In Pharo the comparison just checks for Identity. Is this on purpose? For reference, that's how BlockClosure>>= is implemented in VW: = aBlockClosure ^aBlockClosure class = self class and: [method = aBlockClosure method and: [outerContext = aBlockClosure outerContext and: [copiedValues = aBlockClosure copiedValues]]] Kind regards, Steffen -- Gesendet mit Vivaldi Mail. Laden Sie Vivaldi kostenlos von vivaldi.com herunter.

April 13, 2023