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

Re: Picking neighbouring elements

by Bernhard Pieber

Hi Richard, That sounds great. I am looking forward to playing with it. Bernhard > Am 25.04.2023 um 04:11 schrieb Richard O'Keefe <raoknz(a)gmail.com>: > > There is a much newer version. I've made some minor corrections today. > I really must put it up on github. > Let me get back to you about that. > > On Sat, 22 Apr 2023 at 18:57, Bernhard Pieber <bernhard(a)pieber.com> wrote: > >> Hi Richard, >> >> I really liked your concise description about what is the point of using an object-oriented language. It made my day. >> >> I searched the Web for your Smalltalk library and found this link: >> http://www.cs.otago.ac.nz/staffpriv/ok/astc-1711.tar.gz >> >> Is there a newer version available somewhere? >> >> Cheers, >> Bernhard >> >>> Am 22.04.2023 um 00:51 schrieb Richard O'Keefe <raoknz(a)gmail.com>: >>> >>> I'm sorry, it appears that I failed to explain the question >>> well enough. I thought I'd explained earlier. >>> >>> successor: target >>> ^(self select: [:each | target < each]) min >>> >>> is trivial. What's wrong with it is that it allocates >>> an intermediate collection and takes two passes. >>> FIXING that is is also trivial. >>> >>> successor: target >>> ^(self virtualSelect: [:each | target < each]) min >>> ^^^^^^^ >>> >>> This does allocate something, but it's just a few words, >>> and a single traversal is one. >>> >>> In other languages/contexts we'd be talking about >>> loop fusion/listless transformation/deforestation. >>> It is my understanding that using Transducers would >>> get me *this* level of improvement. >>> >>> The problem is that this is still a linear-time >>> algorithm. If you take advantage of the order in >>> a SortedCollection or SortedSet,it can take logarithmic >>> time. When SortedSet is implemented as a splay tree >>> -- as it is in my library -- iterating over all its >>> elements using #successor: is amortised CONSTANT time >>> per element. So we need THREE algorithms: >>> - worst case O(n) select+min >>> - worst case O(lg n) binary search >>> - amortised O(1) splaying >>> and we want the algorithm selection to be >>> >>> A U T O M A T I C. >>> >>> That's the point of using an object-oriented language. >>> I say what I want done and the receiver decides how to >>> do it. Anything where I have to write different >>> calling code depending on the structure of the receiver >>> doesn't count as a solution. >>> >>> Now we come to the heart of the problem. >>> The binary search algorithm is NOT a special case >>> of the linear search algorithm. It is not made of >>> pieces that can be related to the parts of the linear >>> search algorithm. >>> The splaying algorithm is NOT a special case of the >>> linear search algorithm OR the binary search algorithm. >>> It is not made of pieces that can be related to their >>> parts. >>> >>> So *IF* I want automatic selection of an appropriate >>> algorithm, then I have to rely on inheritance and >>> overriding, and in order to do that I have to have >>> a named method that *can* be overridden, and at that >>> point I'm no longer building a transducer out of >>> pluggable pieces. >>> >>> So that's the point of this exercise. >>> How do we get >>> (a) composition of transducers out of pluggable parts >>> AND >>> (b) automatic selection of appropriate algorithms >>> >>> On Fri, 21 Apr 2023 at 20:35, Steffen MÃ¤rcker <merkste(a)web.de> wrote: >>> >>>> Hi Richard, >>>> >>>> Now that's much clearer to me: >>>> min{y | y in c . y > x} "strict supremum" >>>> max{y | y in c . y < x} "strict infimum" >>>> >>>> For the general case of a sequence (not sorted) of elements we can do >>>> >>>> strictSupremumOf: x in: sequence >>>> >>>> ^(sequence transduce filter: [:y | y > x])"virtual sequence" >>>> inject: nil >>>> into: [:min :b | min ifNotNil: [:a | a min: b]] >>>> >>>> I just picked a variant of minimum that answers nil if no element is found. Other variants would work, too. >>>> The focus of transducers is on re-use and composition of processing steps. We can break this up into steps if needed: >>>> >>>> minimum := [:min :b | min ifNotNil: [:a | a min: b]] init: nil."reduction" >>>> upperBounds := Filter predicate: [:y | y > x]."transducer" >>>> strictSup := minimum transduce: upperBounds."transformed reduction" >>>> ^strictSup reduce: sequence >>>> >>>> We can also use a different notation similar to a data flow: >>>> >>>> minimum <~ upperBounds <~ sequence >>>> >>>> Of course, if we know how the sequence is sorted, we should use another algorithm. Assuming an ascending order with no random access, we'd change minimum to stop early: >>>> >>>> minimum := [:min :b | Stop result: b]. >>>> >>>> Kind regards, >>>> Steffen >>>> >>>> Richard O'Keefe schrieb am Freitag, 21. April 2023 05:33:44 (+02:00): >>>> >>>>> successor of x in c = the smallest element of c that is larger than x >>>>> min {y | y in c . y > x} >>>>> predecessor of x in c = the largest element of c that is smaller than x >>>>> max {y | y in c . y < x} >>>>> >>>>> On Thu, 20 Apr 2023 at 21:08, Steffen MÃ¤rcker <merkste(a)web.de> wrote: >>>>> >>>>>> Dear Richard, >>>>>> >>>>>> thanks for that additional piece. I'll put insert-<left/right> on my list of possible variants. I think we come back to naming after the initial port is done and everyone can play with it. Generally, I made the observation to better be careful with names since it's too easy to alienate other or trigger wrong assumptions. >>>>>> >>>>>> New topic! (quote below) >>>>>> >>>>>> Honestly, my knowledge of Haskell is rather limited and rusted. Hence, I am having difficulties understanding what exactly these operations with a sequence of elements. Can you give an example or some pseude/smalltalk code from your use-case and library? >>>>>> >>>>>> Kind regards >>>>>> >>>>>>> >>>>>> >>>>>>> Changing the subject a wee bit, there's an operation family >>>>>>> in my library, and I wonder how it would fit into Transducers? >>>>>>> To avoid bias, here's a specification in Haskell (for lists, >>>>>>> because I haven't had any luck installing Data.Witherable). >>>>>>> >>>>>>> uccessorBy, predecessorBy :: (a -> a -> Ordering) -> a -> [a] -> a >>>>>>> successor, predecessor :: Ord a => a -> [a] -> a >>>>>>> >>>>>>> successor = successorBy compare >>>>>>> >>>>>>> successorBy cmp x = minimumBy cmp . filter (\y -> cmp x y == LT) >>>>>>> >>>>>>> predecessor = predecessorBy compare >>>>>>> >>>>>>> predecessorBy cmp = successorBy (flip cmp) >>>>>>> >>>>>>> The reason these operations exist is to pick neighbouring >>>>>>> elements in SortedCollections and SortedSets. But they make >>>>>>> *sense* for any Enumerable. So there are "generic" >>>>>>> definitions with orderrides for those two classes. >>>>>>> >>>>>>> A filter + a reduce . Traditionally, a #select:thenFold:ifNone: >>>>>>> in order to avoid building an intermediate collection. That much >>>>>>> I see how to do with transducers. But you can't get the desired >>>>>>> override for #successor:[sortBlock:][ifNone:] by overriding >>>>>>> #select:thenFold:ifNone: in SortedCollection or SortedSet. So what >>>>>>> *should* one do? >>>> >>>> -- >>>> Gesendet mit Vivaldi Mail. Laden Sie Vivaldi kostenlos unter [vivaldi.com](http://vivaldi.com/) herunter

April 30, 2023

Re: Pharo being featured in Exercism's Mind Shifting May

by sean＠clipperadams.com

I clicked on the link and got an error that the page is private or doesnât exist. Also, what kind of help are you looking for?

April 29, 2023

This week (17/2023) on the Pharo Issue Tracker

by Marcus Denker

# Pharo 11 - Refactor block ensure during termination to allow override #13534 https://github.com/pharo-project/pharo/pull/13534 # Pharo 12 ## Small Improvements - Small cleanup #bitShift:, #<< and #<< #13523 https://github.com/pharo-project/pharo/pull/13523 - Clean info of MethodChangeRecord #13519 https://github.com/pharo-project/pharo/pull/13519 - remove some methods that are just copied from a superclass #13504 https://github.com/pharo-project/pharo/pull/13504 - Some RPackage cleanups #13505 https://github.com/pharo-project/pharo/pull/13505 - Adding inspector transmission node #510 https://github.com/pharo-spec/NewTools/pull/510 ## Protocol - Use #protocolOfSelector: in CompiledMethod>>#category #13457 https://github.com/pharo-project/pharo/pull/13457 - Improve ClassDescription>>#addAndClassifySelector:withMethod:inProtocol: #13533 https://github.com/pharo-project/pharo/pull/13533 - Fix case were method is in a class but not in a protocol #13572 https://github.com/pharo-project/pharo/pull/13572 - Simplify ClassOrganization>>removeElement: and remove protocol if empty #13530 https://github.com/pharo-project/pharo/pull/13530 - Classify method before installing them #13539 https://github.com/pharo-project/pharo/pull/13539 - Make Protocol announcements use real protocols #13506 https://github.com/pharo-project/pharo/pull/13506 ## AST - Style literal arrays #13502 https://github.com/pharo-project/pharo/pull/13502 - Do not hardcode stylers #13537 https://github.com/pharo-project/pharo/pull/13537 - AST: cleanup scanner #13562 https://github.com/pharo-project/pharo/pull/13562 - AST: kill multiple keyword token #13554 https://github.com/pharo-project/pharo/pull/13554 - AST: cleanup compiler API (and clients) #13520 https://github.com/pharo-project/pharo/pull/13520 - AST: cleanup extension methods from OpalCompiler #13514 https://github.com/pharo-project/pharo/pull/13514 ## Compiler - Compiler: doSemanticAnalysis yourself #13517 https://github.com/pharo-project/pharo/pull/13517 - add new test RBCodeSnippet class>>#badScanner with special scanner hacks #13553 https://github.com/pharo-project/pharo/pull/13553 - Add compiler option to not optimise special sends #13569 https://github.com/pharo-project/pharo/pull/13569 - Factorize some code in recompilation management #13551 https://github.com/pharo-project/pharo/pull/13551 - Scope: generalize target class #13540 https://github.com/pharo-project/pharo/pull/13540 - RBMethodMode: compiledMethod sould be a simple accessor #13525 https://github.com/pharo-project/pharo/pull/13525 - Detach compilationContext a little #13511 https://github.com/pharo-project/pharo/pull/13511 - Reduce usage of compilationContext from IR* Classes #13513 https://github.com/pharo-project/pharo/pull/13513 ## CompiledMethod trailer cleanup - Compiler: Cleanup trailer for the frontend #13575 https://github.com/pharo-project/pharo/pull/13575 - Compiler: Cleanup for trailer removal in IRByteCodeGenerator #13565 https://github.com/pharo-project/pharo/pull/13565 - Cleanup: do not reference CompiledMethodTrailer in ReflectiveMethod #13564 https://github.com/pharo-project/pharo/pull/13564 - Cleanup: Fuel does not need to use #copyWithTrailerBytes: #13560 https://github.com/pharo-project/pharo/pull/13560 - Cleanup-instanceCreationCompiledMethod #13559 https://github.com/pharo-project/pharo/pull/13559 - Do not use #trailer to read the sourcePointer #13558 https://github.com/pharo-project/pharo/pull/13558 - getSourceFromFile-return-nil #13556 https://github.com/pharo-project/pharo/pull/13556 - Cleanup: CompiledMethodTrailer should not create methods #13555 https://github.com/pharo-project/pharo/pull/13555 - CompiledMethodTrailer-Cleanup-even-more #13550 https://github.com/pharo-project/pharo/pull/13550 - CompiledMethodTrailer: more cleanup, do not use it for #endPC #13546 https://github.com/pharo-project/pharo/pull/13546 - CompiledMethodTrailer: remove #VarLengthSourcePointer support #13545 https://github.com/pharo-project/pharo/pull/13545 - CompiledMethodTrailer: use 4 bytes as sourcePointer #13527 https://github.com/pharo-project/pharo/pull/13527 - Cleanup-Tests-CompiledMethodTrailer #13528 https://github.com/pharo-project/pharo/pull/13528 - Cleanup-CompiledMethod-Source-Embedding #13522 https://github.com/pharo-project/pharo/pull/13522 - remove all unsused encodings from CompiledMethodTrailer. #13510 https://github.com/pharo-project/pharo/pull/13510 - CompiledMethod simplification: remove the last user of #copyWithSource: #13507 https://github.com/pharo-project/pharo/pull/13507 ## Improve Tests - Commit-Deprecation-Rewrites #13567 https://github.com/pharo-project/pharo/pull/13567 - Make shift tests more robust #13570 https://github.com/pharo-project/pharo/pull/13570 - Small cleanings in tests #13576 https://github.com/pharo-project/pharo/pull/13576 - Ensure ThreadedFFI tests terminate all launched processes #13538 https://github.com/pharo-project/pharo/pull/13538 - Make sure class parser tests clean the system #13536 https://github.com/pharo-project/pharo/pull/13536 - Reflectivity: make tests more reliable (and fix a bug) #13544 https://github.com/pharo-project/pharo/pull/13544

April 28, 2023

Pharo being featured in Exercism's Mind Shifting May

by bajger＠gmail.com

Hi there! Hi there! Pharo track will be promoted on Mind shifting May of Exercism initiative. Here are some details from one Exercism founder (Erik): \ \ https://forum.exercism.org/t/pharo-being-featured-in-mind-shifting-may/5420 There are couple of things we could improve here: \ where it is used: weâd definitely find better and newer examples that ATMs usecaseâ¦ where it is great: I would add productivity, once people get through initial learning curve. It is tightly connected to bullets below (image based approach and liveness and immersive env.) Features: embeddability and interoperability with othe PLs - working on minimal Pharo image that can be part of e.g. C program and vice versa. So if you have ideas, thoughts how this script can be improved, please reply!

April 27, 2023

Re: Picking neighbouring elements

by Steffen MÃ¤rcker

â¦ and after the second block #map

April 25, 2023

Re: Picking neighbouring elements

by Steffen MÃ¤rcker

Coding in mail is not easy after all. SortedCollection>>greaterThan: contains a silly mistake from editing. At the end it should read: Â Â ^[:y | y = x] dropWhileTrue Â Â Â Â Â <~ [:i | self at: i] Â Â Â Â Â <~ (index to: self size)

April 25, 2023

Re: Picking neighbouring elements

by Steffen MÃ¤rcker

Dear Richard, that would be nice. Your answers certainly made me curious about your Smalltalk. :-D Regarding strict supremum/infimum, I think that transducers do not lend themselves naturally to the complete problem. How did you solve it in your library? Out of curiosity, I came up with the following non-optimized hybrid solution. As I do not have an image at hand right now, I did not test the code snippets yet. Lets assume the following class hierarchy: Collection <- SortedCollection <- SplayTree Collection>>strictSupremumOf: x "Answer the least upper Bound that is strictly greater than x" ^self minimum <~ self greaterThan: x Collection>>minimum "Compute the minimum element of a sequence in the order of the receiver" ^[:min :b | min ifNotNil: [:a | a min: b]] init: nil Collection>>greaterThan: x "Answer a sequence of elements > x in the order of the receiver" ^[:y | y > x] filter <~ self SortedCollection>>minimum "The first element of a sorted sequence is the minimum" ^[:min :b | Stop return: b] init: nil SortedCollection>>greaterThan: x "Take advantage of binary search" index := self indexOf: x. "1. x not found" index = 0 ifTrue: [^#()]. "2. x found, skip to first y ~= x" ^[:i | self at: i] map <~ [:i | (self at: i) = x] dropWhileTrue <~ ((index + 1) to: self size) SplayTree>>greaterThan: x "Take advantage of the splay operation" top := (self splay: x) value. "1. x found, elements > x at right child" top = x ifTrue: [^root rightChild]. "2. x not found, elements > x at root" top > x ifTrue: [^root]. "3. x not found, no elements > x" ^SplayTree empty. Note, #map, #filter and #dropWhileTrue are (optional) shorthands to create respective transducers. All collections are expected to implement #inject:into:. The strict infimum can be computed analogously if we can reverse the order in #lessThan: efficiently. Kind regards, Steffen Richard O'Keefe schrieb am Dienstag, 25. April 2023 04:11:47 (+02:00): There is a much newer version. I've made some minor corrections today. I really must put it up on github. Let me get back to you about that. On Sat, 22 Apr 2023 at 18:57, Bernhard Pieber <bernhard(a)pieber.com> wrote: Hi Richard, I really liked your concise description about what is the point of using an object-oriented language. It made my day. I searched the Web for your Smalltalk library and found this link: http://www.cs.otago.ac.nz/staffpriv/ok/astc-1711.tar.gz Is there a newer version available somewhere? Cheers, Bernhard Am 22.04.2023 um 00:51 schrieb Richard O'Keefe <raoknz(a)gmail.com>: I'm sorry, it appears that I failed to explain the question well enough. I thought I'd explained earlier. successor: target ^(self select: [:each | target < each]) min is trivial. What's wrong with it is that it allocates an intermediate collection and takes two passes. FIXING that is is also trivial. successor: target ^(self virtualSelect: [:each | target < each]) min ^^^^^^^ This does allocate something, but it's just a few words, and a single traversal is one. In other languages/contexts we'd be talking about loop fusion/listless transformation/deforestation. It is my understanding that using Transducers would get me *this* level of improvement. The problem is that this is still a linear-time algorithm. If you take advantage of the order in a SortedCollection or SortedSet,it can take logarithmic time. When SortedSet is implemented as a splay tree -- as it is in my library -- iterating over all its elements using #successor: is amortised CONSTANT time per element. So we need THREE algorithms: - worst case O(n) select+min - worst case O(lg n) binary search - amortised O(1) splaying and we want the algorithm selection to be A U T O M A T I C. That's the point of using an object-oriented language. I say what I want done and the receiver decides how to do it. Anything where I have to write different calling code depending on the structure of the receiver doesn't count as a solution. Now we come to the heart of the problem. The binary search algorithm is NOT a special case of the linear search algorithm. It is not made of pieces that can be related to the parts of the linear search algorithm. The splaying algorithm is NOT a special case of the linear search algorithm OR the binary search algorithm. It is not made of pieces that can be related to their parts. So *IF* I want automatic selection of an appropriate algorithm, then I have to rely on inheritance and overriding, and in order to do that I have to have a named method that *can* be overridden, and at that point I'm no longer building a transducer out of pluggable pieces. So that's the point of this exercise. How do we get (a) composition of transducers out of pluggable parts AND (b) automatic selection of appropriate algorithms On Fri, 21 Apr 2023 at 20:35, Steffen MÃ¤rcker <merkste(a)web.de> wrote: Hi Richard, Now that's much clearer to me: min{y | y in c . y > x} "strict supremum" max{y | y in c . y < x} "strict infimum" For the general case of a sequence (not sorted) of elements we can do strictSupremumOf: x in: sequence ^(sequence transduce filter: [:y | y > x]) "virtual sequence" inject: nil into: [:min :b | min ifNotNil: [:a | a min: b]] I just picked a variant of minimum that answers nil if no element is found. Other variants would work, too. The focus of transducers is on re-use and composition of processing steps. We can break this up into steps if needed: minimum := [:min :b | min ifNotNil: [:a | a min: b]] init: nil. "reduction" upperBounds := Filter predicate: [:y | y > x]. "transducer" strictSup := minimum transduce: upperBounds. "transformed reduction" ^strictSup reduce: sequence We can also use a different notation similar to a data flow: minimum <~ upperBounds <~ sequence Of course, if we know how the sequence is sorted, we should use another algorithm. Assuming an ascending order with no random access, we'd change minimum to stop early: minimum := [:min :b | Stop result: b]. Kind regards, Steffen Richard O'Keefe schrieb am Freitag, 21. April 2023 05:33:44 (+02:00): successor of x in c = the smallest element of c that is larger than x min {y | y in c . y > x} predecessor of x in c = the largest element of c that is smaller than x max {y | y in c . y < x} On Thu, 20 Apr 2023 at 21:08, Steffen MÃ¤rcker <merkste(a)web.de> wrote: Dear Richard, thanks for that additional piece. I'll put insert-<left/right> on my list of possible variants. I think we come back to naming after the initial port is done and everyone can play with it. Generally, I made the observation to better be careful with names since it's too easy to alienate other or trigger wrong assumptions. New topic! (quote below) Honestly, my knowledge of Haskell is rather limited and rusted. Hence, I am having difficulties understanding what exactly these operations with a sequence of elements. Can you give an example or some pseude/smalltalk code from your use-case and library? Kind regards Changing the subject a wee bit, there's an operation family in my library, and I wonder how it would fit into Transducers? To avoid bias, here's a specification in Haskell (for lists, because I haven't had any luck installing Data.Witherable). uccessorBy, predecessorBy :: (a -> a -> Ordering) -> a -> [a] -> a successor, predecessor :: Ord a => a -> [a] -> a successor = successorBy compare successorBy cmp x = minimumBy cmp . filter (\y -> cmp x y == LT) predecessor = predecessorBy compare predecessorBy cmp = successorBy (flip cmp) The reason these operations exist is to pick neighbouring elements in SortedCollections and SortedSets. But they make *sense* for any Enumerable. So there are "generic" definitions with orderrides for those two classes. A filter + a reduce . Traditionally, a #select:thenFold:ifNone: in order to avoid building an intermediate collection. That much I see how to do with transducers. But you can't get the desired override for #successor:[sortBlock:][ifNone:] by overriding #select:thenFold:ifNone: in SortedCollection or SortedSet. So what *should* one do? -- Gesendet mit Vivaldi Mail. Laden Sie Vivaldi kostenlos unter vivaldi.com herunter

April 25, 2023

Re: Picking neighbouring elements

by Richard O'Keefe

There is a much newer version. I've made some minor corrections today. I really must put it up on github. Let me get back to you about that. On Sat, 22 Apr 2023 at 18:57, Bernhard Pieber <bernhard(a)pieber.com> wrote: > Hi Richard, > > I really liked your concise description about what is the point of using > an object-oriented language. It made my day. > > I searched the Web for your Smalltalk library and found this link: > http://www.cs.otago.ac.nz/staffpriv/ok/astc-1711.tar.gz > > Is there a newer version available somewhere? > > Cheers, > Bernhard > > > Am 22.04.2023 um 00:51 schrieb Richard O'Keefe <raoknz(a)gmail.com>: > > I'm sorry, it appears that I failed to explain the question > well enough. I thought I'd explained earlier. > > successor: target > ^(self select: [:each | target < each]) min > > is trivial. What's wrong with it is that it allocates > an intermediate collection and takes two passes. > FIXING that is is also trivial. > > successor: target > ^(self virtualSelect: [:each | target < each]) min > ^^^^^^^ > > This does allocate something, but it's just a few words, > and a single traversal is one. > > In other languages/contexts we'd be talking about > loop fusion/listless transformation/deforestation. > It is my understanding that using Transducers would > get me *this* level of improvement. > > The problem is that this is still a linear-time > algorithm. If you take advantage of the order in > a SortedCollection or SortedSet,it can take logarithmic > time. When SortedSet is implemented as a splay tree > -- as it is in my library -- iterating over all its > elements using #successor: is amortised CONSTANT time > per element. So we need THREE algorithms: > - worst case O(n) select+min > - worst case O(lg n) binary search > - amortised O(1) splaying > and we want the algorithm selection to be > > A U T O M A T I C. > > That's the point of using an object-oriented language. > I say what I want done and the receiver decides how to > do it. Anything where I have to write different > calling code depending on the structure of the receiver > doesn't count as a solution. > > Now we come to the heart of the problem. > The binary search algorithm is NOT a special case > of the linear search algorithm. It is not made of > pieces that can be related to the parts of the linear > search algorithm. > The splaying algorithm is NOT a special case of the > linear search algorithm OR the binary search algorithm. > It is not made of pieces that can be related to their > parts. > > So *IF* I want automatic selection of an appropriate > algorithm, then I have to rely on inheritance and > overriding, and in order to do that I have to have > a named method that *can* be overridden, and at that > point I'm no longer building a transducer out of > pluggable pieces. > > So that's the point of this exercise. > How do we get > (a) composition of transducers out of pluggable parts > AND > (b) automatic selection of appropriate algorithms > > > On Fri, 21 Apr 2023 at 20:35, Steffen MÃ¤rcker <merkste(a)web.de> wrote: > >> Hi Richard, >> >> Now that's much clearer to me: >> min{y | y in c . y > x} "strict supremum" >> max{y | y in c . y < x} "strict infimum" >> >> For the general case of a sequence (not sorted) of elements we can do >> >> strictSupremumOf: x in: sequence >> >> ^(sequence transduce filter: [:y | y > x]) "virtual sequence" >> inject: nil >> into: [:min :b | min ifNotNil: [:a | a min: b]] >> >> I just picked a variant of minimum that answers nil if no element is >> found. Other variants would work, too. >> The focus of transducers is on re-use and composition of processing >> steps. We can break this up into steps if needed: >> >> minimum := [:min :b | min ifNotNil: [:a | a min: b]] init: nil. >> "reduction" >> upperBounds := Filter predicate: [:y | y > x]. "transducer" >> strictSup := minimum transduce: upperBounds. "transformed reduction" >> ^strictSup reduce: sequence >> >> We can also use a different notation similar to a data flow: >> >> minimum <~ upperBounds <~ sequence >> >> Of course, if we know how the sequence is sorted, we should use another >> algorithm. Assuming an ascending order with no random access, we'd change >> minimum to stop early: >> >> minimum := [:min :b | Stop result: b]. >> >> Kind regards, >> Steffen >> >> >> Richard O'Keefe schrieb am Freitag, 21. April 2023 05:33:44 (+02:00): >> >> successor of x in c = the smallest element of c that is larger than x >> min {y | y in c . y > x} >> predecessor of x in c = the largest element of c that is smaller than x >> max {y | y in c . y < x} >> >> On Thu, 20 Apr 2023 at 21:08, Steffen MÃ¤rcker <merkste(a)web.de> wrote: >> >>> Dear Richard, >>> >>> thanks for that additional piece. I'll put insert-<left/right> on my >>> list of possible variants. I think we come back to naming after the initial >>> port is done and everyone can play with it. Generally, I made the >>> observation to better be careful with names since it's too easy to alienate >>> other or trigger wrong assumptions. >>> >>> New topic! (quote below) >>> >>> Honestly, my knowledge of Haskell is rather limited and rusted. Hence, I >>> am having difficulties understanding what exactly these operations with a >>> sequence of elements. Can you give an example or some pseude/smalltalk code >>> from your use-case and library? >>> >>> Kind regards >>> >>> >>> Changing the subject a wee bit, there's an operation family >>> in my library, and I wonder how it would fit into Transducers? >>> To avoid bias, here's a specification in Haskell (for lists, >>> because I haven't had any luck installing Data.Witherable). >>> >>> uccessorBy, predecessorBy :: (a -> a -> Ordering) -> a -> [a] -> a >>> successor, predecessor :: Ord a => a -> [a] -> a >>> >>> successor = successorBy compare >>> >>> successorBy cmp x = minimumBy cmp . filter (\y -> cmp x y == LT) >>> >>> predecessor = predecessorBy compare >>> >>> predecessorBy cmp = successorBy (flip cmp) >>> >>> The reason these operations exist is to pick neighbouring >>> elements in SortedCollections and SortedSets. But they make >>> *sense* for any Enumerable. So there are "generic" >>> definitions with orderrides for those two classes. >>> >>> A filter + a reduce . Traditionally, a #select:thenFold:ifNone: >>> in order to avoid building an intermediate collection. That much >>> I see how to do with transducers. But you can't get the desired >>> override for #successor:[sortBlock:][ifNone:] by overriding >>> #select:thenFold:ifNone: in SortedCollection or SortedSet. So what >>> *should* one do? >>> >>> >> -- >> Gesendet mit Vivaldi Mail. Laden Sie Vivaldi kostenlos unter vivaldi.com >> herunter >> > >

April 25, 2023

Re: Picking neighbouring elements

by Bernhard Pieber

Hi Richard, I really liked your concise description about what is the point of using an object-oriented language. It made my day. I searched the Web for your Smalltalk library and found this link: http://www.cs.otago.ac.nz/staffpriv/ok/astc-1711.tar.gz Is there a newer version available somewhere? Cheers, Bernhard > Am 22.04.2023 um 00:51 schrieb Richard O'Keefe <raoknz(a)gmail.com>: > > I'm sorry, it appears that I failed to explain the question > well enough. I thought I'd explained earlier. > > successor: target > ^(self select: [:each | target < each]) min > > is trivial. What's wrong with it is that it allocates > an intermediate collection and takes two passes. > FIXING that is is also trivial. > > successor: target > ^(self virtualSelect: [:each | target < each]) min > ^^^^^^^ > > This does allocate something, but it's just a few words, > and a single traversal is one. > > In other languages/contexts we'd be talking about > loop fusion/listless transformation/deforestation. > It is my understanding that using Transducers would > get me *this* level of improvement. > > The problem is that this is still a linear-time > algorithm. If you take advantage of the order in > a SortedCollection or SortedSet,it can take logarithmic > time. When SortedSet is implemented as a splay tree > -- as it is in my library -- iterating over all its > elements using #successor: is amortised CONSTANT time > per element. So we need THREE algorithms: > - worst case O(n) select+min > - worst case O(lg n) binary search > - amortised O(1) splaying > and we want the algorithm selection to be > > A U T O M A T I C. > > That's the point of using an object-oriented language. > I say what I want done and the receiver decides how to > do it. Anything where I have to write different > calling code depending on the structure of the receiver > doesn't count as a solution. > > Now we come to the heart of the problem. > The binary search algorithm is NOT a special case > of the linear search algorithm. It is not made of > pieces that can be related to the parts of the linear > search algorithm. > The splaying algorithm is NOT a special case of the > linear search algorithm OR the binary search algorithm. > It is not made of pieces that can be related to their > parts. > > So *IF* I want automatic selection of an appropriate > algorithm, then I have to rely on inheritance and > overriding, and in order to do that I have to have > a named method that *can* be overridden, and at that > point I'm no longer building a transducer out of > pluggable pieces. > > So that's the point of this exercise. > How do we get > (a) composition of transducers out of pluggable parts > AND > (b) automatic selection of appropriate algorithms > > On Fri, 21 Apr 2023 at 20:35, Steffen MÃ¤rcker <merkste(a)web.de> wrote: > >> Hi Richard, >> >> Now that's much clearer to me: >> min{y | y in c . y > x} "strict supremum" >> max{y | y in c . y < x} "strict infimum" >> >> For the general case of a sequence (not sorted) of elements we can do >> >> strictSupremumOf: x in: sequence >> >> ^(sequence transduce filter: [:y | y > x])"virtual sequence" >> inject: nil >> into: [:min :b | min ifNotNil: [:a | a min: b]] >> >> I just picked a variant of minimum that answers nil if no element is found. Other variants would work, too. >> The focus of transducers is on re-use and composition of processing steps. We can break this up into steps if needed: >> >> minimum := [:min :b | min ifNotNil: [:a | a min: b]] init: nil."reduction" >> upperBounds := Filter predicate: [:y | y > x]."transducer" >> strictSup := minimum transduce: upperBounds."transformed reduction" >> ^strictSup reduce: sequence >> >> We can also use a different notation similar to a data flow: >> >> minimum <~ upperBounds <~ sequence >> >> Of course, if we know how the sequence is sorted, we should use another algorithm. Assuming an ascending order with no random access, we'd change minimum to stop early: >> >> minimum := [:min :b | Stop result: b]. >> >> Kind regards, >> Steffen >> >> Richard O'Keefe schrieb am Freitag, 21. April 2023 05:33:44 (+02:00): >> >>> successor of x in c = the smallest element of c that is larger than x >>> min {y | y in c . y > x} >>> predecessor of x in c = the largest element of c that is smaller than x >>> max {y | y in c . y < x} >>> >>> On Thu, 20 Apr 2023 at 21:08, Steffen MÃ¤rcker <merkste(a)web.de> wrote: >>> >>>> Dear Richard, >>>> >>>> thanks for that additional piece. I'll put insert-<left/right> on my list of possible variants. I think we come back to naming after the initial port is done and everyone can play with it. Generally, I made the observation to better be careful with names since it's too easy to alienate other or trigger wrong assumptions. >>>> >>>> New topic! (quote below) >>>> >>>> Honestly, my knowledge of Haskell is rather limited and rusted. Hence, I am having difficulties understanding what exactly these operations with a sequence of elements. Can you give an example or some pseude/smalltalk code from your use-case and library? >>>> >>>> Kind regards >>>> >>>>> >>>> >>>>> Changing the subject a wee bit, there's an operation family >>>>> in my library, and I wonder how it would fit into Transducers? >>>>> To avoid bias, here's a specification in Haskell (for lists, >>>>> because I haven't had any luck installing Data.Witherable). >>>>> >>>>> uccessorBy, predecessorBy :: (a -> a -> Ordering) -> a -> [a] -> a >>>>> successor, predecessor :: Ord a => a -> [a] -> a >>>>> >>>>> successor = successorBy compare >>>>> >>>>> successorBy cmp x = minimumBy cmp . filter (\y -> cmp x y == LT) >>>>> >>>>> predecessor = predecessorBy compare >>>>> >>>>> predecessorBy cmp = successorBy (flip cmp) >>>>> >>>>> The reason these operations exist is to pick neighbouring >>>>> elements in SortedCollections and SortedSets. But they make >>>>> *sense* for any Enumerable. So there are "generic" >>>>> definitions with orderrides for those two classes. >>>>> >>>>> A filter + a reduce . Traditionally, a #select:thenFold:ifNone: >>>>> in order to avoid building an intermediate collection. That much >>>>> I see how to do with transducers. But you can't get the desired >>>>> override for #successor:[sortBlock:][ifNone:] by overriding >>>>> #select:thenFold:ifNone: in SortedCollection or SortedSet. So what >>>>> *should* one do? >> >> -- >> Gesendet mit Vivaldi Mail. Laden Sie Vivaldi kostenlos unter [vivaldi.com](http://vivaldi.com/) herunter

April 22, 2023

Re: Picking neighbouring elements

by Richard O'Keefe

I'm sorry, it appears that I failed to explain the question well enough. I thought I'd explained earlier. successor: target ^(self select: [:each | target < each]) min is trivial. What's wrong with it is that it allocates an intermediate collection and takes two passes. FIXING that is is also trivial. successor: target ^(self virtualSelect: [:each | target < each]) min ^^^^^^^ This does allocate something, but it's just a few words, and a single traversal is one. In other languages/contexts we'd be talking about loop fusion/listless transformation/deforestation. It is my understanding that using Transducers would get me *this* level of improvement. The problem is that this is still a linear-time algorithm. If you take advantage of the order in a SortedCollection or SortedSet,it can take logarithmic time. When SortedSet is implemented as a splay tree -- as it is in my library -- iterating over all its elements using #successor: is amortised CONSTANT time per element. So we need THREE algorithms: - worst case O(n) select+min - worst case O(lg n) binary search - amortised O(1) splaying and we want the algorithm selection to be A U T O M A T I C. That's the point of using an object-oriented language. I say what I want done and the receiver decides how to do it. Anything where I have to write different calling code depending on the structure of the receiver doesn't count as a solution. Now we come to the heart of the problem. The binary search algorithm is NOT a special case of the linear search algorithm. It is not made of pieces that can be related to the parts of the linear search algorithm. The splaying algorithm is NOT a special case of the linear search algorithm OR the binary search algorithm. It is not made of pieces that can be related to their parts. So *IF* I want automatic selection of an appropriate algorithm, then I have to rely on inheritance and overriding, and in order to do that I have to have a named method that *can* be overridden, and at that point I'm no longer building a transducer out of pluggable pieces. So that's the point of this exercise. How do we get (a) composition of transducers out of pluggable parts AND (b) automatic selection of appropriate algorithms On Fri, 21 Apr 2023 at 20:35, Steffen MÃ¤rcker <merkste(a)web.de> wrote: > Hi Richard, > > Now that's much clearer to me: > min{y | y in c . y > x} "strict supremum" > max{y | y in c . y < x} "strict infimum" > > For the general case of a sequence (not sorted) of elements we can do > > strictSupremumOf: x in: sequence > > ^(sequence transduce filter: [:y | y > x]) "virtual sequence" > inject: nil > into: [:min :b | min ifNotNil: [:a | a min: b]] > > I just picked a variant of minimum that answers nil if no element is > found. Other variants would work, too. > The focus of transducers is on re-use and composition of processing steps. > We can break this up into steps if needed: > > minimum := [:min :b | min ifNotNil: [:a | a min: b]] init: nil. > "reduction" > upperBounds := Filter predicate: [:y | y > x]. "transducer" > strictSup := minimum transduce: upperBounds. "transformed reduction" > ^strictSup reduce: sequence > > We can also use a different notation similar to a data flow: > > minimum <~ upperBounds <~ sequence > > Of course, if we know how the sequence is sorted, we should use another > algorithm. Assuming an ascending order with no random access, we'd change > minimum to stop early: > > minimum := [:min :b | Stop result: b]. > > Kind regards, > Steffen > > > Richard O'Keefe schrieb am Freitag, 21. April 2023 05:33:44 (+02:00): > > successor of x in c = the smallest element of c that is larger than x > min {y | y in c . y > x} > predecessor of x in c = the largest element of c that is smaller than x > max {y | y in c . y < x} > > On Thu, 20 Apr 2023 at 21:08, Steffen MÃ¤rcker <merkste(a)web.de> wrote: > >> Dear Richard, >> >> thanks for that additional piece. I'll put insert-<left/right> on my list >> of possible variants. I think we come back to naming after the initial port >> is done and everyone can play with it. Generally, I made the observation to >> better be careful with names since it's too easy to alienate other or >> trigger wrong assumptions. >> >> New topic! (quote below) >> >> Honestly, my knowledge of Haskell is rather limited and rusted. Hence, I >> am having difficulties understanding what exactly these operations with a >> sequence of elements. Can you give an example or some pseude/smalltalk code >> from your use-case and library? >> >> Kind regards >> >> >> Changing the subject a wee bit, there's an operation family >> in my library, and I wonder how it would fit into Transducers? >> To avoid bias, here's a specification in Haskell (for lists, >> because I haven't had any luck installing Data.Witherable). >> >> uccessorBy, predecessorBy :: (a -> a -> Ordering) -> a -> [a] -> a >> successor, predecessor :: Ord a => a -> [a] -> a >> >> successor = successorBy compare >> >> successorBy cmp x = minimumBy cmp . filter (\y -> cmp x y == LT) >> >> predecessor = predecessorBy compare >> >> predecessorBy cmp = successorBy (flip cmp) >> >> The reason these operations exist is to pick neighbouring >> elements in SortedCollections and SortedSets. But they make >> *sense* for any Enumerable. So there are "generic" >> definitions with orderrides for those two classes. >> >> A filter + a reduce . Traditionally, a #select:thenFold:ifNone: >> in order to avoid building an intermediate collection. That much >> I see how to do with transducers. But you can't get the desired >> override for #successor:[sortBlock:][ifNone:] by overriding >> #select:thenFold:ifNone: in SortedCollection or SortedSet. So what >> *should* one do? >> >> > -- > Gesendet mit Vivaldi Mail. Laden Sie Vivaldi kostenlos unter vivaldi.com > herunter >

April 21, 2023