Array subclassing, .map and iterables (Re: Jan 30 TC39 Meeting Notes)
allen at wirfs-brock.com
Sun Feb 10 10:05:47 PST 2013
On Feb 10, 2013, at 1:33 AM, Claus Reinke wrote:
> Thanks for the explanations and additional details. Let me first try to rephrase, to see whether I've understood your reasoning:
> The problem comes from the partial integration of types in ES, specifically having typed arrays but no easy way to express and control the types of the functions mapped over them.
ECMAScript has various kinds of values and objects that are distinguished in various ways. However, these variations of kind are quite unlike the concept of type as used in PL theory and statically typed languages. For that reason I generally try to avoid use of the word "type" in the context of ES (although sometimes it is unavoidable, eg "TypedArrays") because it can lead to thinking that reflects static typing experience rather than dynamic language experiences that are often more appropriate for ES.
> And your solution is to fix Array.map to being type-preserving, and to use an auxiliary map in Container.from instead of Array.map when type changing mappings have to be expressed.
> Using <> for type parameters, => for function types, and suppressing a few details (such as prototype, this, index parameter), we can write the types of the two groups of operations as
> Array<Elem>.map : (<Elem> => <Elem>) => Array<Elem>
> Container<Elem2>.from : Iterable<Elem1> => (<Elem1> => <Elem2>) => Container<Elem2>
> where the ES5 Array is seen as Array<Any> (so arbitrary mappings are still supported at that level), and Array<Int32>, etc are written as type-level constants Int32Array, for lack of type-level constructor syntax (the parameterized Interface Iterable<> is also inexpressible).
Like I said above. This is a type theory view of the word. Static type systems require some sort parameterization or genercity in order to be sufficiently expressive. Few programmers actually understand the subtleties of the type systems. Dynamic languages typically don't use such type systems and achieve equivalent (arguably greater) expressiveness using different approaches. We don't want to turn ES into Java or C#.
> Since ES cannot guarantee that the mappings have the expected
> types, an implicit conversion of the mapped elements to the expected element type will be enforced (probably with a type
> check to avoid unexpected conversions?).
Right, dynamic languages typically use dynamic constraint checks or dynamic coercions when specific kinds of objects are required.
> int32Array.map( f )
> will be read as roughly
> int32Array.map( (elem) => Number( f(elem) ) )
> Int32Array.from( iterable, f )
> Int32Array.from( iterable, (elem) => Number( f(elem) ) )
> Do I have this right, so far?
yes, except that the Number coercion takes place at a much deeper layer -- If is part of the [[Put]] operation that actually stores values into the Int32Array
>> var intArray = new Int32Array([42,85,127649,32768]); //create a typed array from a regular array
>> var strArray = intArray.map(v=>v.toString());
>> If intArray.map() produces a new intArray then the above map function is invalid. If intArray.map() produces an Array instance
>> then you intArray.map instance of intArray.constructor desire won't hold. We can't have it both ways without provide some
>> additional mechanism that probably involves additional parameters to some methods or new methods.
> It is this additional mechanism which I'm after. In typed languages,
> it is long-established practice to put the additional parameters at
> the type level and to hang the interface on the type-level constructor,
> and I wonder how much of that could be translated for use in ES.
There is also plenty of dynamic language experience for the pattern I proposed. For example, withAll: is pretty much Smalltalk's equivalent of ES for. The conceptual model of this is not that the for method is being parameterized by the programmer. Instead, the model is that the programmer has chosen a specific kind of collection object that will be populated using for and it is the responsibility of that object to impose what ever constraints upon its elements as are appropriate for it.
> For instance, being able to specify an overloaded map function was the motivating example for introducing type constructor
> classes in Haskell
> A system of constructor classes: overloading and implicit higher-order polymorphism
> Mark P. Jones, In FPCA '93: Conference on Functional Programming Languages and Computer Architecture, Copenhagen, Denmark, June 1993.
Right, but this is all starting rom a static typing perspective rather than dynamic typing.
>> 1) Array.prototype.map produces the same kind of array that it was applied to, so:
>> for the above example
>> m instance of V will be true. intArray.map(v=>v.toSring()) produces an Int32Array. The strings produced by the map function get converted back to numbers.
> Given the history of implicit conversions in ES, have you considered just doing runtime type checks, without those new implicit conversions?
TypedArrays have already been implemented in browsers doing this sort of implicit conversion. It probably can't be changed.
>> 2) If you want to map the elements of an array to different kind of array use <ArrayClass>.from with a map function as the second parameter:
>> var strArray = Array.from(intArray, v=>v.toString());
>> This seemed like a less invasive change then adding additional target kind
>> parameters to Array.prototype.map. Also it seems like a very clear way for
>> programmers to state their intent.
>> ES isn't Java or C#. We don't have formalized interfaces (although it is useful to think and talk about informal interfaces) and since we are
>> dynamically typed we don't need to get sucked into the tar pit of generics.
> If a programming concept is as useful as interfaces are, it usually pays to think about language support for it. And I was certainly not thinking
> of Java or C#, more of TypeScript, where the team seems to be working
> Btw, parametric polymorphism in ML and its refinements and
> extensions in Haskell were elegant and concise tools before they got watered down in a multi-year process to fit into Java. If you have bad
> experience with generics, they probably come from Java's adaption.
TypeScript is, for the most part, a advisory compile-time only static type system. It isn't, at all, a part of the runtime model of the language. At runtime, the language still has to deal with all the runtime situations where the "wrong type" is passed.
Interfaces are a useful conceptual concept, but in a dynamic language you have to think about them as static approximations of dynamic behavior. They are useful for abstracting the design of a system in order to make it easier to comprehend. But, they don't need to be expressive enough to prove theorems about the system.
>> How would use produce an Array of strings from an Int32Array?
> Somewhat like
> Array.from( int32Array ).map( (elem) => elem.toString() )
> Implementations would be free to replace the syntactic pattern
> with an optimized single pass (in more conventional optimizing
> language implementations, such fusion of implicit or explicit loops is standard, but even ES JIT engines -with their limited time for optimization- should be able to spot the syntactic pattern).
Even if such an optimization was likely in ES, why would you want to write that instead of the shorter single call form. Does it come down to wanting to explicitly name the "map" parameter. Would you think differently if ES had keyword parameters:
Array.from(int32Array, map: elem=>elem.toString())
>>> - instead of limiting to Array, .from-map is now limited to iterables
>>> (it would work for Set, which is really OrderedSet, but it wouldn't
>>> work for WeakMap)
>> We already have Array.from that works with iterables, how does adding a map function change anything related to the <ArrayClass>.from result domains
> My point was that map is far more widely useful, not limited to
> Array (Array.prototype.map), and not limited to Array construction
> from Iterables (Array.prototype.from with second parameter). Consider map on event emitters, on promises, on exceptions, on generators, ..
> I don't have an alternative solution that would cover all use cases in ES uniformly, because the existing solutions in other languages
> do not translate directly.
> However, I wanted to ring a warning bell that adding a different partial solution for every new use case is not going to scale well (especially with things being so difficult to change once they are in ES), and misses potential for writing generic library code.
> If I have to write different code, depending on whether I need to map over a constructed Array, an Array under construction, an Array or an Int32Array, a generator, a promise, etc., then that will result in duplicate code instead of generic code.
Something that dynamic language support is the use of informal polymorphism. You can assign a name to a concept (like map) without requiring type consistent behavior among various uses of that name. As long as the actual behavior makes sense in context it doesn't cause any conceptual problems.
>>> With a general solution to the issue, I would expect to write
>>> SubArray.from( iterable ).map( val => val ) instanceof SubArray
>> yes, the above will produce an instance of SubArray. But the above also has the cost of an extra copy and the map function
>> doesn't get to see the original iterable's values.
> Implementations can fuse .from().map() as well as .map().from();
> if you want access to the unconverted elements, you want to map
> over the iterable, not the resulting Array (again, with loop fusion
> in the implementation):
> SubArray.from( iterable.map( val => f(val) ) )
> Of course, since map isn't part of a standard Array-independent
> interface, I have to write that as a generator expression (not sure
> whether I'm up to date on their syntax) instead of a map.
> SubArray.from( (for ( elem of iterable ) in f(elem) ) )
>>> while also getting
>>> new Mapable().map( val => val ) instanceof Mapable
>> I don't even know how to interpret the above, as we don't have a class or constructor named Mapable.
> fair enough - Mapable being intended as an interface for classes
> implementing map wouldn't be new-able, so this was pseudo code
> for instantiating any class that implements such a Mapable. I think a full solution for polymorphic map will require some way of specifying interfaces independent of the classes (Array, Int32Array, Promise, generators, ..) implementing them.
To me, you are describing steps into the static typing rat hole where to adequately express even simple concepts like mapping an Int32 array to an Array of strings require adding more complex language mechanisms and abstractions. A dynamic language can be conceptually much simpler because we just don't need those mechanism.
>>> PS. What about array comprehensions and generator expressions?
>> What about them? Array comprehensions are a for of Array initializer and always produce an Array instance. Generaltor expressions produce iterators (which are iterable).
> Array comprehensions are a full array processing language, which can be desugared to explicit array operations like map
> and filter, so they tend to have the same problems as map
> and filter do. Will I be able to use array comprehensions with Int32Arrays, or to convert between array types?
Nope, Array comprehensions create instances of Array. The syntax provides no mechanism for syntactically specify the kind of the generated object. Of course you can say:
Int32Array.from([for (i in thing) i]) //note that order of array comprehensions have changed
but this generates an extra object and copying unless an implementation is able to perform the sort of optimizations you hope they can do.
> Will I be able
> to call .map on iterators/generator expressions, without using
> case-specific syntax?
Generally, no. .map and other Array.prototype methods are a method on generic array-likes, not on iterators. It requires some behaviors that the generic iterator interface doesn't provide. Of course, you could define your own map function that worked on iterators.
More information about the es-discuss