Re: Cross-language comparison: function map and similar
On Thu, 17 Aug 2017 12:53 am, Steve D'Aprano wrote: [...] > Are there language implementations which evaluate the result of map() (or its > equivalent) in some order other than the obvious left-to-right first-to-last > sequential order? Is that order guaranteed by the language, or is it an > implementation detail? Thanks to everyone who answered. It also confirmed my suspicion: apart from explicitly parallel languages, and specialised parallel versions of map, mainstream programming languages do not treat the execution order of map() as an implementation detail. At least not the languages which people here (reading this thread, and motivated to reply) are familiar with. I take this as moderate evidence that programming languages do not *actually* treat execution order of map and equivalent as an implementation detail, even if they reserve the right to. Instead, they generally treat it as semantically a sequential loop[1]. Apart from explicitly parallel languages, if you want a parallel or concurrent map, you need to either call a specialised version, or specify an execution policy to set the execution model, or equivalent. What you can't do, in any language mentioned here, is simply call the regular, standard map function. Thanks again to everyone who answered, and if anyone want to point out an exception, its not too late :-) [1] Whether implemented as a loop, or by recursion, or something else. -- Steve “Cheer up,” they said, “things could be worse.” So I cheered up, and sure enough, things got worse. -- https://mail.python.org/mailman/listinfo/python-list
Re: Cross-language comparison: function map and similar
Op 2017-08-16, Steve D'Aprano schreef : > Are there language implementations which evaluate the result of map() > (or its equivalent) in some order other than the obvious left-to-right > first-to-last sequential order? Is that order guaranteed by the > language, or is it an implementation detail? > > Standard library functions implementing an explicitly "parallel map" > or "threaded map" are also relevant. (Less interested in third-party > libraries, unless they're practically a standard for the language in > question.) C++17 has such a facility in its standard library. std::transform (and many other functions operating on sequences, but you asked for a map() equivalent) takes an optional "execution_policy" parameter which indicates if the operation should be run sequentially (the default) or can be parallellized. See: http://en.cppreference.com/w/cpp/algorithm/transform Stephan -- https://mail.python.org/mailman/listinfo/python-list
Re: Cross-language comparison: function map and similar
On Thu, 17 Aug 2017 03:54 pm, Pavol Lisy wrote: > Is it guaranteed in python? Or future version could implement map with > something like subscriptability "propagation"? > range(1_000_000_000_000_000_000)[-1] > > map(lambda a:a+1,range(1_000_000_000_000_000_000))[-1] > TypeError: 'map' object is not subscriptable I don't recognise the term "subscriptability propagation". Given a suitable deprecation period, or another backwards-incompatible release like Python 3, anything is possible. But some things are very unlikely, such as another backwards-incompatible release, or map supporting indexing. Python's map() now returns an iterator, which means it must yield items one by one, in order. Because it is an iterator, in general it cannot know what the next item will be until it evaluates it. Unlike range, it cannot jump ahead In principle we could have map() return a magic iterator that delegated indexing to the underlying sequence, but that's not part of the iterator API and the benefit seems small. So, possible but unlikely. -- Steve “Cheer up,” they said, “things could be worse.” So I cheered up, and sure enough, things got worse. -- https://mail.python.org/mailman/listinfo/python-list
Re: Cross-language comparison: function map and similar
On Thu, Aug 17, 2017 at 3:54 PM, Pavol Lisy wrote: > On 8/16/17, Steve D'Aprano wrote: >> Over in another thread, we've been talking about comprehensions and their >> similarities and differences from the functional map() operation. >> >> Reminder: >> >> map(chr, [65, 66, 67, 68]) >> >> will return ['A', 'B', 'C']. >> >> My questions for those who know languages apart from Python: >> >> Are there language implementations which evaluate the result of map() (or >> its >> equivalent) in some order other than the obvious left-to-right first-to-last >> sequential order? Is that order guaranteed by the language, or is it an >> implementation detail? > > Is it guaranteed in python? Or future version could implement map with > something like subscriptability "propagation"? > range(1_000_000_000_000_000_000)[-1] > > map(lambda a:a+1,range(1_000_000_000_000_000_000))[-1] > TypeError: 'map' object is not subscriptable I think it is, partly because of the behaviour of map with additional arguments. If you want something subscriptable, you probably don't want an iterable, but a mapping type (it's no coincidence that the words are similar). The Python map() function expects a function and one or more iterables, and returns an iterator; but if you instead give it a function and a (subscriptable) collections, you could have it be a collection. (I'm not sure what to do about multiple collections. I guess you'd do something similar to map() - if any subcollection raises, Map raises. Not implemented here though.) class Map(dict): def __init__(self, func, coll): self.func, self.coll = func, coll def __missing__(self, key): self[key] = self.func(self.coll[key]) return self[key] This has the same subscripting semantics as the underlying collection, and will cache any result it sees. But watch out! It can't know about subscript aliasing, and will treat a key of -1 as completely different from any positive subscript. It also doesn't iterate the same way as the underlying collection does: >>> spam = Map(print, range(10)) >>> list(spam) [] Without knowing exactly what kind of "thing" you're mapping over, it's impossible to get everything right. ChrisA -- https://mail.python.org/mailman/listinfo/python-list
Re: Cross-language comparison: function map and similar
On 8/16/17, Steve D'Aprano wrote: > Over in another thread, we've been talking about comprehensions and their > similarities and differences from the functional map() operation. > > Reminder: > > map(chr, [65, 66, 67, 68]) > > will return ['A', 'B', 'C']. > > My questions for those who know languages apart from Python: > > Are there language implementations which evaluate the result of map() (or > its > equivalent) in some order other than the obvious left-to-right first-to-last > sequential order? Is that order guaranteed by the language, or is it an > implementation detail? Is it guaranteed in python? Or future version could implement map with something like subscriptability "propagation"? >>>range(1_000_000_000_000_000_000)[-1] >>> map(lambda a:a+1,range(1_000_000_000_000_000_000))[-1] TypeError: 'map' object is not subscriptable -- https://mail.python.org/mailman/listinfo/python-list
Re: Cross-language comparison: function map and similar
Steve D'Aprano writes: > Are there language implementations which evaluate the result of map() > (or its equivalent) in some order other than the obvious left-to-right > first-to-last sequential order? Is that order guaranteed by the > language, or is it an implementation detail? Haskell just gives back an unevaluated thunk. The elements are evaluated in whatever order you happen to use them in. Since the evaluation isn't supposed to have observable side effects, there's no way to tell the order. There are also parallel versions (Control.Parallel.Strategies.parMap etc.) and an extension that recognizes "racing stripes" on the square brackets to make list comprehensions run faster: foo = [| sqrt(x) | x <- [1.0 .. 1000.0] |] parallelizes the calculation and offloads it to a GPU or other vector processor. You might also like this old post https://donsbot.wordpress.com/2007/11/29/use-those-extra-cores-and-beat-c-today-parallel-haskell-redux/ "map" is conceptually the lifting of a function from a given type, to the type under the action of some functor. For historical reasons map only works on lists while fmap works on arbitrary functors, but they are in principle the same thing. Depending on what the functor does, the whole concept of left-to-right order might be meaningless. -- https://mail.python.org/mailman/listinfo/python-list
Re: Cross-language comparison: function map and similar
On 8/16/2017 10:53 AM, Steve D'Aprano wrote: Over in another thread, we've been talking about comprehensions and their similarities and differences from the functional map() operation. Reminder: map(chr, [65, 66, 67, 68]) will return ['A', 'B', 'C']. The comprehension 'while' proposal is for future Python 3. Asking your while question the restricted context of Python 2 encouraged the restricted list-based or concrete-collection-based thinking about comprehensions that you got in some of the answers. The above snipper is only true for Python-2 . In Python 3, >>> oracle = map(chr, [65, 66, 67, 68]) >>> oracle >>> next(oracle) 'A' >>> next(oracle) 'B' >>> next(oracle) 'C' When oracle is asked for the next value, it asks base_oracle = iter(iterable) for a value. If base_oracle gives one, oracle gives func(value). If base_iterable raises StopIteration, so does oracle. This process is inherently sequential. It remains so with multiple input iterables. >>> next(oracle) 'D' >>> next(oracle) Traceback (most recent call last): File "", line 1, in next(oracle) StopIteration Even in pre-2.2 Python, map's input was not restricted to being a list, but could be any 'sequence'. From 2.0 doc: "The list arguments may be *any kind of sequence*" [emphasis added]. I am rather sure that in this context, a 'sequence' was merely something that could be indexed and that a pre-defined length was not required. This means that map could use the old iterator protocol. So 'sequence' meant 'iterator' in current terms. The old spelling of 'next(iterator)' was 'iterator[i]' where i is 0 for the first request for an object and incremented thereafter. The 'sequence' was free to ignore i when generating the return object. It could also use external input. My questions for those who know languages apart from Python: Are there language implementations which evaluate the result of map() (or its equivalent) in some order other than the obvious left-to-right first-to-last sequential order? If map's collection input is unbounded, as with Python, a right-to-left or completely parallel order is not possible. If the input oracle creates objects on demand, as Python allows, then doing anything other that applying func as objects are made available requires internal storage. Asking an oracle for millions of objects when only the first few are needed, is foolish. Storing millions or billions of objects all at once when there are only needed one at a time is also foolish. Which is why map and filter were changed in Python 3. -- Terry Jan Reedy -- https://mail.python.org/mailman/listinfo/python-list
Re: Cross-language comparison: function map and similar
On Wednesday, August 16, 2017 at 8:24:46 PM UTC+5:30, Steve D'Aprano wrote: > Over in another thread, we've been talking about comprehensions and their > similarities and differences from the functional map() operation. > > Reminder: > > map(chr, [65, 66, 67, 68]) > > will return ['A', 'B', 'C']. > > My questions for those who know languages apart from Python: > > Are there language implementations which evaluate the result of map() (or its > equivalent) in some order other than the obvious left-to-right first-to-last > sequential order? Is that order guaranteed by the language, or is it an > implementation detail? There are dozens of parallel/concurrent languages: https://en.wikipedia.org/wiki/List_of_concurrent_and_parallel_programming_languages > > Standard library functions implementing an explicitly "parallel map" > or "threaded map" are also relevant. Here's the peach (parallel-each) 'adverb in Q/K http://code.kx.com/wiki/Reference/peach In more mainstream languages: parallel map in Julia https://docs.julialang.org/en/latest/manual/parallel-computing Haskell's parmap et al: http://chimera.labs.oreilly.com/books/123000929/ch03.html#sec_par-kmeans-perf -- https://mail.python.org/mailman/listinfo/python-list
Re: Cross-language comparison: function map and similar
On Thu, 17 Aug 2017 12:53 am, Steve D'Aprano wrote: > map(chr, [65, 66, 67, 68]) > > will return ['A', 'B', 'C']. Of course I meant ['A', 'B', 'C', 'D']. -- Steve “Cheer up,” they said, “things could be worse.” So I cheered up, and sure enough, things got worse. -- https://mail.python.org/mailman/listinfo/python-list
Cross-language comparison: function map and similar
Over in another thread, we've been talking about comprehensions and their similarities and differences from the functional map() operation. Reminder: map(chr, [65, 66, 67, 68]) will return ['A', 'B', 'C']. My questions for those who know languages apart from Python: Are there language implementations which evaluate the result of map() (or its equivalent) in some order other than the obvious left-to-right first-to-last sequential order? Is that order guaranteed by the language, or is it an implementation detail? Standard library functions implementing an explicitly "parallel map" or "threaded map" are also relevant. (Less interested in third-party libraries, unless they're practically a standard for the language in question.) E.g. given the map above, Blub language might promise to evaluate chr(65), chr(66), chr(67) and chr(68) in parallel if your computer has four cores. Or some Blub language implementation may unroll the above map to the equivalent of this pseudo-code: array = [None, None, None, None] array[3] = chr(68) array[2] = chr(67) array[1] = chr(66) array[0] = chr(65) I'm not terribly interested in hypothetical "Blub language doesn't specify evaluation order, so some implementation could do this". I'm more interested in actual concrete examples of mapping implementations which don't operate in the obvious first-to-last order. For example, Fortran has "do concurrent": do concurrent(i = 1:n) a(i) = a(i+m)+b(i) end do which tells the compiler that it can run the iterations in any order, or parallelize them and run them in parallel across threads, etc: https://www.hpcwire.com/2015/04/06/compilers-and-more-the-past-present-and-future-of-parallel-loops/ Wikipedia mentions a few specialised parallel processing languages which have equivalent forms of parallel map: https://en.wikipedia.org/wiki/Map_%28parallel_pattern%29 Wolfram Language (Mathematica?) has a parallel map: http://reference.wolfram.com/language/ref/ParallelMap.html as does Clojure: https://clojuredocs.org/clojure.core/pmap Any others? I'm especially interested in cases of languages where their regular map() function is performed in parallel, or out of order, *without* the performance hit that the Clojure docs warn about: "Only useful for computationally intensive functions where the time of f dominates the coordination overhead." -- Steve “Cheer up,” they said, “things could be worse.” So I cheered up, and sure enough, things got worse. -- https://mail.python.org/mailman/listinfo/python-list
