There is actually NO way with haskell 98 to portably read and write binary files. and many libraries which provide this feature are inherently non portable, (they assume a Haskell Char = C char = byte) which is not necisarily the case. I wrote up a proposal for a binary file IO mechanism to be added as a 'blessed addendum' to the standard at best and as a commonly implmented extension (in hslibs) at least..
my original proposal messages to the list can be gotten from http://www.ugcs.caltech.edu/~john/computer/haskell/ although without the messages from others in the list they may seem out of context.
How about this slightly more general interface, which works with the new FFI libraries, and is trivial to implement on top of the primitives in GHC's IOExts: hPut :: Storable a => Handle -> a -> IO () hGet :: Storable a => Handle -> IO a Haskell 98 already defines the seek and file size operations to operate in units of 8-bit bytes, so these don't need to be duplicated. A version of hGetContents on Storable objects could also be included. Cheers, Simon
Simon Marlow wrote:
How about this slightly more general interface, which works with the new FFI libraries, and is trivial to implement on top of the primitives in GHC's IOExts:
hPut :: Storable a => Handle -> a -> IO () hGet :: Storable a => Handle -> IO a
What about endianess? In which format are Floats or even just Bools stored? For a file which probably shall be read from different machines this is not clear at all. I think John is right that there needs to be a primitive interface for just writing bytes. You can then build anything more complicated on top (probably different high-level ones for different purposes). I just see one problem with John's proposal: the type Byte. It is completely useless if you don't have operations that go with it; bit-operations and conversions to and from Int. The FFI already defines such a type: Word8. So I suggest that the binary IO library explicitely reads and writes Word8's. Cheers, Olaf -- OLAF CHITIL, Dept. of Computer Science, University of York, York YO10 5DD, UK. URL: http://www.cs.york.ac.uk/~olaf/ Tel: +44 1904 434756; Fax: +44 1904 432767
On Tue, 6 Feb 2001, Olaf Chitil wrote:
I just see one problem with John's proposal: the type Byte.
type Byte = Word8 IMHO it looks nicer to have Byte in function names, so there can be such type synonym too. I would call the module ByteIO or BinaryIO instead of cryptic BIO. -- Marcin 'Qrczak' Kowalczyk
Marcin 'Qrczak' Kowalczyk wrote:
type Byte = Word8
IMHO it looks nicer to have Byte in function names, so there can be such type synonym too.
I agree that Byte is nicer than Word8. So why is this type synonym not in the library Word of the FFI? I think that is the right place for it. -- OLAF CHITIL, Dept. of Computer Science, University of York, York YO10 5DD, UK. URL: http://www.cs.york.ac.uk/~olaf/ Tel: +44 1904 434756; Fax: +44 1904 432767
Since there seems to be general support for the idea of some sort of Portable Byte IO package, I will work on am implementation of my proposal for ghc being the platform I am most familiar with. I really like the simplicity of the hPut and hGet idea and will probably use it as my mechanism for implementation on ghc, however for a Portable API which should be implementable across a wide variety of Haskell 98 implementations and machine architectures it is too low level to allow certain portable applications to be written. I made the API at pretty much the exact level of the Haskell 98 IO API since it seems to strike a good balance between portability and expressiveness/power. A nice advantage of using my mid-level routines is that there are very little requirements placed on 'Byte' as a type, this means that as long as to the outside world you only read in 8 bit values and spit 8 bit values out you can represent it internally however you want. for example you might have a machine where a 16 bit word is the smallest addressable entity, if you relied on hPut Word8 then your program would not work since Word8 cannot exist on that platform. however if you made Byte be 16 bits and only used the bottom half of each word then your program will run unchanged even among architectures such as this. my requirements for Byte were going to basically mirror the C requirements for char, The smallest individually addressable integral type greater than 8 bits in width. The trick that makes programs using Byte portable is that ByteIO.read and ByteIO.write only utilize the lower 8 bits of that datatype at a time, therefore one can write portable Haskell applications which work on network sockets and file streams in a machine independent fashion. Anyone who is concerned about the space requirements of using up a little more memory than necessary on certain architectures will have to know about how those architectures store stuff in memory anyway to pack values into the architecture primitives properly so they can use hPut and hGet with explicit word widths... I guess what would be nice would be a portable ByteIO as the standard mid-level interface and the hPut, hGet idea available on those platforms which support Storable since they seem to make sense as the primitives for Haskell implementations which allow such fine grained access to the hardware representations. (but such access should not be required from a haskell implementation in order to write portable programs which can communicate in externally defined formats) John -- -------------------------------------------------------------- John Meacham http://www.ugcs.caltech.edu/~john/ California Institute of Technology, Alum. john@foo.net --------------------------------------------------------------
On 08-Feb-2001, John Meacham <john@foo.net> wrote:
A nice advantage of using my mid-level routines is that there are very little requirements placed on 'Byte' as a type, this means that as long as to the outside world you only read in 8 bit values and spit 8 bit values out you can represent it internally however you want.
for example you might have a machine where a 16 bit word is the smallest addressable entity, if you relied on hPut Word8 then your program would not work since Word8 cannot exist on that platform. however if you made Byte be 16 bits and only used the bottom half of each word then your program will run unchanged even among architectures such as this.
I agree that `Byte' is a useful abstraction. However, I think what you say about Word8 here is not correct. Word8 can be implemented on a 16-bit machine just by computing all arithmetic operations modulo 256. There is no requirement that Word8 be physically 8 bits, just that it represents an 8-bit quantity. Indeed, I think ghc uses this technique, representing Word8 as a full machine word (e.g. 32 bits for x86, of which the topmost 24 are always zero). -- Fergus Henderson <fjh@cs.mu.oz.au> | "I have always known that the pursuit | of excellence is a lethal habit" WWW: <http://www.cs.mu.oz.au/~fjh> | -- the last words of T. S. Garp.
Marcin 'Qrczak' Kowalczyk wrote: | IMHO it looks nicer to have Byte in function names, so | there can be such type synonym too. Style Warning! Why do many people when designing libraries not make full use of the Haskell module system? Instead of writeByte readByte (or so), one could also say: Byte.write Byte.read So that the context (Byte.) can be left out when unambiguous, and one can just say: write read /Koen. -- Koen Claessen http://www.cs.chalmers.se/~koen phone:+46-31-772 5424 mailto:koen@cs.chalmers.se ----------------------------------------------------- Chalmers University of Technology, Gothenburg, Sweden
Style Warning! ... writeByte -> Byte.write
Yes yes yes please! Often, if someone writes identifiersWithSuffix, the suffix actually carries a type information or a module information, and the programmer should use the type resp. module system of the language to express that. Should this also apply to names in the standard library? like Monad (filterM, zipWithM ,..) I mean, theoretically yes, but is it feasible to change it? While we're at it, stylistically: the sight of "g" changing to "G" in getLine -> hGetLine (and similar) always irritates me. Best regards, -- -- Johannes Waldmann ---- http://www.informatik.uni-leipzig.de/~joe/ -- -- joe@informatik.uni-leipzig.de -- phone/fax (+49) 341 9732 204/252 --
Johannes Waldmann wrote: | Should this also apply to names in the standard | library? like Monad (filterM, zipWithM ,..) I mean, | theoretically yes, but is it feasible to change it? Obviously, these functions should have been called: Monad.filter, Monad.zipWith The lazy programmer can then say: import Monad as M (*) M.filter, M.zipWith Just (asymptotically) 1 character more! :-) | getLine -> hGetLine always irritates me. How about: import Handle as H H.getLine (This is a good example where type classes would not help making this any better, since the types of getLine and H.getLine are very different.) While we're at it, how about instead of the "fmap" function: Functor.map (F.map) List.map (L.map) Maybe.map (M.map) The programmer can pick him/herself what function to use. (The Prelude really has too many functions in it, and very often the rationale for a function being in Prelude or in Char/List/Maybe/Monad/IO/etc. is not motivated.) What do people think about this? If people prefer these stylistic changes, I think we should not hesitate making them for Haskell/2 by completely redesigning the module structure and using more consistent naming conventions. /Koen. (*) What actually happened to the excellent proposal somebody made a while ago for Haskell98: import M = Monad ? I like it a lot! -- Koen Claessen http://www.cs.chalmers.se/~koen phone:+46-31-772 5424 mailto:koen@cs.chalmers.se ----------------------------------------------------- Chalmers University of Technology, Gothenburg, Sweden
This is exactly what I proposed when fmap and the other weird names were introduced. Hopefully there are more allies now. Erik ----- Original Message ----- From: "Koen Claessen" <koen@cs.chalmers.se> To: "The Haskell Mailing List" <haskell@haskell.org> Sent: Tuesday, February 06, 2001 6:25 AM Subject: Re: binary files in haskell
Johannes Waldmann wrote:
| Should this also apply to names in the standard | library? like Monad (filterM, zipWithM ,..) I mean, | theoretically yes, but is it feasible to change it?
Obviously, these functions should have been called:
Monad.filter, Monad.zipWith
The lazy programmer can then say:
import Monad as M (*)
M.filter, M.zipWith
Just (asymptotically) 1 character more! :-)
| getLine -> hGetLine always irritates me.
How about:
import Handle as H
H.getLine
(This is a good example where type classes would not help making this any better, since the types of getLine and H.getLine are very different.)
While we're at it, how about instead of the "fmap" function:
Functor.map (F.map) List.map (L.map) Maybe.map (M.map)
The programmer can pick him/herself what function to use. (The Prelude really has too many functions in it, and very often the rationale for a function being in Prelude or in Char/List/Maybe/Monad/IO/etc. is not motivated.)
What do people think about this? If people prefer these stylistic changes, I think we should not hesitate making them for Haskell/2 by completely redesigning the module structure and using more consistent naming conventions.
/Koen.
(*) What actually happened to the excellent proposal somebody made a while ago for Haskell98:
import M = Monad
? I like it a lot!
-- Koen Claessen http://www.cs.chalmers.se/~koen phone:+46-31-772 5424 mailto:koen@cs.chalmers.se ----------------------------------------------------- Chalmers University of Technology, Gothenburg, Sweden
_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
On Tue, Feb 06, 2001 at 03:25:11PM +0100, Koen Claessen wrote:
What do people think about this? If people prefer these stylistic changes, I think we should not hesitate making them for Haskell/2 by completely redesigning the module structure and using more consistent naming conventions.
These sound great to me. If Haskell/2 is indeed open to such changes, would also be possible to revamp the numeric modules? As a mathematician, I get annoyed by such things as * (+) and (-) being lumped in with (*) (doesn't anyone use vector spaces?) * the function 'atan2' being mixed in with a bunch of operations very specific to the floating point format in the 'RealFloat' class. Same problem (though less serious) with 'quot', etc., and 'toInteger' in the Integral class. * Superfluous superclasses: why are Show and Eq superclasses of Num? Not all numeric types have decidable equality. Think arbitrary precision reals. (I saw Mechvelliani's Basic Algebra Proposal; it strikes me as being too complicated for the task.) Best, Dylan Thurston
On Tue, 6 Feb 2001, Dylan Thurston wrote:
On Tue, Feb 06, 2001 at 03:25:11PM +0100, Koen Claessen wrote:
What do people think about this? If people prefer these stylistic changes, I think we should not hesitate making them for Haskell/2 by completely redesigning the module structure and using more consistent naming conventions.
These sound great to me. If Haskell/2 is indeed open to such changes, would also be possible to revamp the numeric modules? As a mathematician, I get annoyed by such things as
* (+) and (-) being lumped in with (*) (doesn't anyone use vector spaces?)
That also causes me some headaches. For various number-like algebras (*) is not even defined. Not defining it in an instance of Num leads to annoying runtime errors that would otherwise be caught at compile time. For others algebras (*) is self-multiplication (t -> t -> t). Even for others, it might be scaling (s -> t -> t). It may be the case that using (*) for scaling too is a generally bad idea... Another problem: The right place for fromInteger is probably not in class Num. One cannot use the remaining Num operations on everything one can construct from an Integer. Otherwise it would be possible to write `0' for different kinds of zero elements (and perhaps `1' for different one elements), even for things on a nominal scale.
* the function 'atan2' being mixed in with a bunch of operations very specific to the floating point format in the 'RealFloat' class. Same problem (though less serious) with 'quot', etc., and 'toInteger' in the Integral class.
* Superfluous superclasses: why are Show and Eq superclasses of Num? Not all numeric types have decidable equality. Think arbitrary precision reals.
Also not all instances of Num can be shown. I have a monad that is an instance of Num, for example. I cannot possibly show the monad.
(I saw Mechvelliani's Basic Algebra Proposal; it strikes me as being too complicated for the task.)
Best, Dylan Thurston
Regards, Andreas Gruenbacher. ------------------------------------------------------------------------ Andreas Gruenbacher gruenbacher@geoinfo.tuwien.ac.at Research Assistant Phone +43(1)58801-12723 Institute for Geoinformation Fax +43(1)58801-12799 Technical University of Vienna Cell phone +43(664)4064789
On Tue, Feb 06, 2001 at 10:29:36PM +0100, Andreas Gruenbacher wrote:
On Tue, 6 Feb 2001, Dylan Thurston wrote:
* (+) and (-) being lumped in with (*) (doesn't anyone use vector spaces?)
That also causes me some headaches.
... Even for others, it might be scaling (s -> t -> t).
It may be the case that using (*) for scaling too is a generally bad idea...
It may not be type sound to have the same operation, but there should be some standard operation for scaling. (Probably you need multi-parameter type classes for this.)
Another problem: The right place for fromInteger is probably not in class Num. One cannot use the remaining Num operations on everything one can construct from an Integer. Otherwise it would be possible to write `0' for different kinds of zero elements (and perhaps `1' for different one elements), even for things on a nominal scale.
When I thought about it, I concluded that '0' belongs with '+' and '-', '1' belongs with '*', and 'fromInteger' belongs with their join (which is mathematically called a Ring, but could keep the name Num). Best, Dylan Thurston
Dylan Thurston:
Andreas Gruenbacher:
It may be the case that using (*) for scaling too is a generally bad idea...
It may not be type sound to have the same operation, but there should be some standard operation for scaling. (Probably you need multi-parameter type classes for this.)
I'd like to point out the connection between the use of +, - on vector spaces and * for scaling with features in some data parallel languages. In these languages, writing a + b where a and b are arrays of numerics is interpreted as elementwise addition of a and b. This features generalises to other operations than +, -, other types than numerical ones, and other data structures than arrays. Furthermore, some of these languages support "promotion": "lifting" a "scalar"-typed expression, appearing in a context where an array (say) is expected, into an array with suitable dimensions containing copies of the scalar. Scaling can be seen as a special case of promotion, if "*" is interpreted elementwise: for instance, 17*a where a is an array is then seen as an array with elements 17 elementwise multiplied with a. Thus, using "*" both for scaling and elementwise multiplication can be made to work, and it is compatible with the data parallel generalizations of scaling and use of +, - on vector spaces. But using "*" for inner product is not compatible with these generalizations. Preference is probably dependent on background (mathematician or data parallel programmer...). Björn Lisper
On Wed, 7 Feb 2001, Bjorn Lisper wrote:
I'd like to point out the connection between the use of +, - on vector spaces and * for scaling with features in some data parallel languages. In these languages, writing a + b where a and b are arrays of numerics is interpreted as elementwise addition of a and b. This features generalises to other operations than +, -, other types than numerical ones, and other data structures than arrays.
This is what I dislike. It's implicit fmap / zipWith / etc. But it only works as long as there is only one meaningful way to insert these fmaps. When I apply length to a list of lists, is it the length of the whole list or a list of lengths of its elements? So there must be explicit ways of specifying the amount of fmaps, and one cannot assume that they will be always placed automatically. It might be convenient for very specific types computation but is not a working general idea.
Furthermore, some of these languages support "promotion": "lifting" a "scalar"-typed expression, appearing in a context where an array (say) is expected, into an array with suitable dimensions containing copies of the scalar.
Again, Haskell does not have subtyping. It is not compatible with type inference - it can only work in poor languages which require an operation to be fully applied where it is used, and either don't have static types or require them to be specified explicitly. In Haskell trying to implement such overloading would be too clumsy and would not work as expected in all cases, so better don't go this way. -- Marcin 'Qrczak' Kowalczyk
Marcin 'Qrczak' Kowalczyk:
Me: I'd like to point out the connection between the use of +, - on vector spaces and * for scaling with features in some data parallel languages. In these languages, writing a + b where a and b are arrays of numerics is interpreted as elementwise addition of a and b. This features generalises to other operations than +, -, other types than numerical ones, and other data structures than arrays.
This is what I dislike. It's implicit fmap / zipWith / etc. But it only works as long as there is only one meaningful way to insert these fmaps. When I apply length to a list of lists, is it the length of the whole list or a list of lengths of its elements? So there must be explicit ways of specifying the amount of fmaps, and one cannot assume that they will be always placed automatically. It might be convenient for very specific types computation but is not a working general idea.
A natural principle to adopt is that an already typeable expression should not be transformed. This will for instance resolve the ambiguity in the list of list example: if l :: [[a]] then length l is already well-typed and should not be transformed into map length l.
Furthermore, some of these languages support "promotion": "lifting" a "scalar"-typed expression, appearing in a context where an array (say) is expected, into an array with suitable dimensions containing copies of the scalar.
Again, Haskell does not have subtyping. It is not compatible with type inference - it can only work in poor languages which require an operation to be fully applied where it is used, and either don't have static types or require them to be specified explicitly.
I am not so sure about this. Could you exemplify? Note that you can do some of this overloading already within Haskell's class system. For instance, one can make lists of Nums into Nums by declaring instance (Num a) => Num [a] where x + y = zipWith (+) x y x * y = zipWith (*) x y ... fromInteger x = repeat (fromInteger x) ... Now, if x and y are lists of Nums, then 2*x + y becomes zipWith (+) (zipWith (*) (repeat fromInteger 2) x) y
In Haskell trying to implement such overloading would be too clumsy and would not work as expected in all cases, so better don't go this way.
I should point out that I didn't suggest adding this overloading in Haskell, I was merely pointing out the connection between vector space syntax/scaling and features in data parallel languages. Björn Lisper
Wed, 7 Feb 2001 13:04:12 +0100 (MET), Bjorn Lisper <lisper@it.kth.se> pisze:
A natural principle to adopt is that an already typeable expression should not be transformed. This will for instance resolve the ambiguity in the list of list example: if l :: [[a]] then length l is already well-typed and should not be transformed into map length l.
So there are ways to interpret an expression which are not chosen only because some other way is a better match? This is very dangerous in principle. Two interpretations of a code are "correct", but one is "more correct" than the other. Say there is a code which relies on the implicit fmap, and it's slightly changed by replacing the function with a more general function, which has the same result on this instance. Then suddenly without a warning the code has a different meaning, because it is now applied in a different way (different placement of implicit fmaps). Also, what is the inferred type of, for example f x y = x + length y ? It can be Int -> [a] -> Int [Int] -> [a] -> [Int] and neither is more general than the other. And this is a simple function.
Again, Haskell does not have subtyping. It is not compatible with type inference - it can only work in poor languages which require an operation to be fully applied where it is used, and either don't have static types or require them to be specified explicitly.
I am not so sure about this. Could you exemplify?
Sorry, I don't have a concrete example in mind. How to infer types when implicit conversions are possible anywhere? The above function f can be applied even to two numbers (because the second would be promoted to a list of length = 1), so what is its inferred most general type? Assuming that Ints can be implicitly converted to Doubles, is the function f :: Int -> Int -> Double -> Double f x y z = x + y + z ambiguous? Because there are two interpretations: f x y z = realToFrac x + realToFrac y + z f x y z = realToFrac (x + y) + z Making this and similar case ambiguous means inserting lots of explicit type signatures to disambiguate subexpressions. Again, arbitrarily choosing one of the alternatives basing on some set of weighting rules is dangerous, because a programmer might mean the other alternative - there is no simple way to ensure that the compiler interprets it in the same way as I wanted. It's not enough to check that all types match modulo conversions - I must carefully check that no "better" interpretation is possible.
Note that you can do some of this overloading already within Haskell's class system.
But it's quite rigorous: all uses of an identifier must be at a type which is an instance of a single generic type. There is enough type information to disambiguate the meaning in most cases - *without* rejecting an interpretation because another was better (except defaulting of numeric types - yes, it's ugly). Another advantage of the Haskell's class system is that no code relies on absence of something. Adding an instance does not make previously working code ambiguous or otherwise incorrect! Except when the instance conflicts with another one - this is the only kind of "negative constraint". -- __("< Marcin Kowalczyk * qrczak@knm.org.pl http://qrczak.ids.net.pl/ \__/ ^^ SYGNATURA ZASTÊPCZA QRCZAK
Marcin Kowalczyk:
Me:
A natural principle to adopt is that an already typeable expression should not be transformed. This will for instance resolve the ambiguity in the list of list example: if l :: [[a]] then length l is already well-typed and should not be transformed into map length l.
So there are ways to interpret an expression which are not chosen only because some other way is a better match? This is very dangerous in principle.
Two interpretations of a code are "correct", but one is "more correct" than the other.
It is quite similar in spirit to the concept of principal type in Hindley-Milner type systems. An expression can have many types but only one "best" (most general) type in that system.
Also, what is the inferred type of, for example f x y = x + length y ? It can be Int -> [a] -> Int [Int] -> [a] -> [Int] and neither is more general than the other. And this is a simple function.
Int -> [a] -> Int, since this is the type it will get in the original type system. The types you mention are incomparable w.r.t. the usual "more general"-ordering on types, but one could consider also other orderings. For the types you give, the second is more "lifted" than the first in that it contains [Int] in places where the first type has Int. One can define a "liftedness" order on types in this vein. (OK, so one would need to go through the formalities and prove that there are "principal types" w.r.t. this relation between types, and that this new principal type concept is not in conflict with the old one. I cannot say for sure that it works.) I should be more specific about what a type system could look like that implements this kind of overloading. It could be a coercive type system, with judgements of the form t -> t':a where t, t' are terms, a is a type, and t:a is a correct judgement in the original type system. So the type system not only gives a type but also a transformation that resolves the overloading into a well-typed term.
Again, Haskell does not have subtyping. It is not compatible with type inference - it can only work in poor languages which require an operation to be fully applied where it is used, and either don't have static types or require them to be specified explicitly.
I am not so sure about this. Could you exemplify?
Sorry, I don't have a concrete example in mind. How to infer types when implicit conversions are possible anywhere? The above function f can be applied even to two numbers (because the second would be promoted to a list of length = 1), so what is its inferred most general type?
Int -> [a] -> Int. If f is applied to some arguments with other types for which the overloading is defined, say f l1 l2 where l1 :: [Int] and l2 :: [a], then the term f l1 l2 would be transformed into a well-typed term but the type of f itself would not change.
Again, arbitrarily choosing one of the alternatives basing on some set of weighting rules is dangerous, because a programmer might mean the other alternative - there is no simple way to ensure that the compiler interprets it in the same way as I wanted. It's not enough to check that all types match modulo conversions - I must carefully check that no "better" interpretation is possible.
I surely agree that this kind of overloading should be used only when it is in accordance with the intuition of the programmer. This could, for instance, imply restrictions to certain types or operators. Björn Lisper
Thu, 8 Feb 2001 00:32:18 +0100 (MET), Bjorn Lisper <lisper@it.kth.se> pisze:
Two interpretations of a code are "correct", but one is "more correct" than the other.
It is quite similar in spirit to the concept of principal type in Hindley-Milner type systems. An expression can have many types but only one "best" (most general) type in that system.
But other are its instances! The point of HM is that I can forget that something is more general and treat a definition f xs = [] : xs as of type [[Int]] -> [[Int]]. Once I determine a possible meaning of a code, I know it's correct, no matter if it's the most general meaning or not. (Well, this is not exactly true when classes come. Two uses of f don't unify types of their arguments to the same type, where they would do that if f had type [[Int]] -> [[Int]]. Fortunately it's very rarely a problem I would say. Overloading should not be abused because it easily leads to ambiguous types.)
Also, what is the inferred type of, for example f x y = x + length y ? It can be Int -> [a] -> Int [Int] -> [a] -> [Int] and neither is more general than the other. And this is a simple function.
Int -> [a] -> Int, since this is the type it will get in the original type system.
So I can't apply f to lists, but I could if I inline its body. This means that I cannot arbitrarily refactor a piece of code by moving parts of it into separate definitions: subexpressions are given some extra meanings only if they are physically placed in certain contexts. This is bad.
The types you mention are incomparable w.r.t. the usual "more general"-ordering on types, but one could consider also other orderings. For the types you give, the second is more "lifted" than the first in that it contains [Int] in places where the first type has Int. One can define a "liftedness" order on types in this vein.
Argh, Haskell's type system is complex enough. This is going to be horror for people trying to understand it. I'm not saying that we should not think about extending the type system at all, but this is IMHO too ugly.
(OK, so one would need to go through the formalities and prove that there are "principal types" w.r.t. this relation between types, and that this new principal type concept is not in conflict with the old one. I cannot say for sure that it works.)
Here other types are not instances of the principal type! So it's not principal: it's just an arbitrary ordering.
Sorry, I don't have a concrete example in mind. How to infer types when implicit conversions are possible anywhere? The above function f can be applied even to two numbers (because the second would be promoted to a list of length = 1), so what is its inferred most general type?
Int -> [a] -> Int. If f is applied to some arguments with other types for which the overloading is defined, say f l1 l2 where l1 :: [Int] and l2:: [a], then the term f l1 l2 would be transformed into a well-typed term but the type of f itself would not change.
Ah, so what uses of f are correct depends on its definition, not type! Sorry, this is way to radical. Types exist to formalize possible ways a value can be used. HM allows to determine most general types variables in a let-block (or: of a module) before their uses, so separate compilation is possible. In your system typechecking of a function's definition is done each time it is used! -- __("< Marcin Kowalczyk * qrczak@knm.org.pl http://qrczak.ids.net.pl/ \__/ ^^ SYGNATURA ZASTÊPCZA QRCZAK
Also, what is the inferred type of, for example f x y = x + length y ? It can be Int -> [a] -> Int [Int] -> [a] -> [Int] and neither is more general than the other. And this is a simple function.
Int -> [a] -> Int, since this is the type it will get in the original type system.
So I can't apply f to lists, but I could if I inline its body. This means that I cannot arbitrarily refactor a piece of code by moving parts of it into separate definitions: subexpressions are given some extra meanings only if they are physically placed in certain contexts. This is bad.
This is a misunderstanding. the transformation of f l y , where l :: [Int] for instance, should depend only on the type of f and not its definition. It is the call to f, not f itself, that becomes transformed. No inlining takes place.
Ah, so what uses of f are correct depends on its definition, not type! Sorry, this is way to radical.
Types exist to formalize possible ways a value can be used. HM allows to determine most general types variables in a let-block (or: of a module) before their uses, so separate compilation is possible. In your system typechecking of a function's definition is done each time it is used!
No. See above. Björn Lisper
On Thu, 8 Feb 2001, Bjorn Lisper wrote:
Int -> [a] -> Int, since this is the type it will get in the original type system.
This is a misunderstanding. the transformation of f l y , where l :: [Int] for instance, should depend only on the type of f and not its definition. It is the call to f, not f itself, that becomes transformed. No inlining takes place.
I see. So you can transform arbitrary function of type a->b->c to a function of type [a]->b->[c], by applying \f x y -> map (\z -> f z y) x and similarly a->b->c to a->[b]->[c]. But then there are two ways of transforming a->b->c to [a]->[b]->[[c]] and the order of applying the former transformations does matter. Worse: a third way is to apply zipWith and then promote the result to a single-element list. Or maybe map the result to a list of single-element lists... Sorry, IMHO it's ambiguous as hell except very simple cases. -- Marcin 'Qrczak' Kowalczyk
I see. So you can transform arbitrary function of type a->b->c to a function of type [a]->b->[c], by applying \f x y -> map (\z -> f z y) x and similarly a->b->c to a->[b]->[c]. But then there are two ways of transforming a->b->c to [a]->[b]->[[c]] and the order of applying the former transformations does matter. Worse: a third way is to apply zipWith and then promote the result to a single-element list. Or maybe map the result to a list of single-element lists...
There should be no transformation to type [a]->[b]->[[c]] in this case. If f is applied to arguments of type [a] and [b] then this should be interpreted as the elementwise application of f to the two argument lists, and the result type should then be [c]. Note that [a]->[b]->[[c]] is "more lifted" than [a]->[b]->[c]. Elementwise application to one argument should transform to map, of several arguments to zipWith with appropriate arity. It is easier to see how it should work if we skip lists, so we don't have to deal with maps and zipWiths and other list functions. Let us consider elementwise application of f over indexed entitites. For simplicity we consider functions as our indexed entities, but it could as well be arrays. With f as above, then f x y should be transformed to: (1) x :: d -> a, y :: b yields \i -> f (x i) y (2) x :: a, y :: d -> b yields \i -> f x (y i) (3) x :: d -> a, y :: d -> b yields \i -> f (x i) (y i) Here (3) is "full" elementwise application, and (1) and (2) are "partial" elementwise applications where the unlifted argument can be seen as promoted. If you have list instead of functions, then the transformation should insert list primitives with the corresponding effect.
Sorry, IMHO it's ambiguous as hell except very simple cases.
Of course the type/term transformation system must have the property that if different transformations can yield the "best" type (wrt liftedness), then the transformed expressions should be semantically equivalent. I believe a type/term transformation system with this property can be designed, but the details remain to be worked out. Björn Lisper (Is this discussion still of interest to the Haskell list members? Or should we take it offline?)
Thu, 8 Feb 2001 13:39:51 +0100 (MET), Bjorn Lisper <lisper@it.kth.se> pisze:
I see. So you can transform arbitrary function of type a->b->c to a function of type [a]->b->[c], by applying \f x y -> map (\z -> f z y) x and similarly a->b->c to a->[b]->[c]. But then there are two ways of transforming a->b->c to [a]->[b]->[[c]
There should be no transformation to type [a]->[b]->[[c]] in this case.
Wait wait wait. You told that a->b->c is convertible to [a]->b->[c] for *any* a,b,c. Now I have x = [a], y = b, z = [c] and use the transformation x->y->z to x->[y]->[z] and obtain [a]->[b]->[[c]]. Both steps are legal, so their composition must be legal, or I don't like this Haskell-like language anymore. Unless you say that a->b->c is convertible to a->[b]->[c] *except* when a is a list. Then it's bad again. There should be no negative conditions in the type system! Moreover, in a polymorphic function you don't know yet if a will be a list or not.
Here (3) is "full" elementwise application, and (1) and (2) are "partial" elementwise applications where the unlifted argument can be seen as promoted.
There are no full and partial applications because of currying. It's impossible to say when you should consider a function as a multiparameter function. There are only single-argument functions. So you would have to say that some rule apply only *unless* the result has a function type, which does not work again. With your rules a programmer writes code which is meant to implicitly convert a value to a single-element list, because something tries to iterate over it like on a list. Unfortunately the element happens to be a string, and he gets iteration over its characters. And if it works the other way, another programmer meant iteration over characters and got iteration over a single string. You can't tell which was meant. Generally the concept of treating a single element as a list (promoting it when necessary) is ambiguous in its nature and it should not be used in any general purpose language. It might work in a poor language which operates only on numbers, vectors and matrices, but not in Haskell in which lists are perfectly first class objects, and similarly functions, and whose type system is polymorphic, so operations can be applied to values which are lists or not, functions or not, not statically known.
Of course the type/term transformation system must have the property that if different transformations can yield the "best" type (wrt liftedness), then the transformed expressions should be semantically equivalent.
It's not enough, because the least lifted type is not the most general answer. Answers for different amounts of liftedness are incompatible with that answer - they are not its instances as in the HM typing. There is no most general answer, so these rules are ambiguous and cannot be designed well. -- __("< Marcin Kowalczyk * qrczak@knm.org.pl http://qrczak.ids.net.pl/ \__/ ^^ SYGNATURA ZASTÊPCZA QRCZAK
I see. So you can transform arbitrary function of type a->b->c to a function of type [a]->b->[c], by applying \f x y -> map (\z -> f z y) x and similarly a->b->c to a->[b]->[c]. But then there are two ways of transforming a->b->c to [a]->[b]->[[c]
There should be no transformation to type [a]->[b]->[[c]] in this case.
Wait wait wait. You told that a->b->c is convertible to [a]->b->[c] for *any* a,b,c. Now I have x = [a], y = b, z = [c] and use the transformation x->y->z to x->[y]->[z] and obtain [a]->[b]->[[c]].
Both steps are legal, so their composition must be legal, or I don't like this Haskell-like language anymore.
(You never seem to have liked it much ... :-) No, the transformation is a single step procedure where a term is transformed into a typeable term (if possible) with a minimal amount of lifting. You don't compose transformations. Let us write [a]^n for the type of n-deep lists of lists of a. If f :: a -> b -> c, x :: [a]^m, and y :: [b]^n, then f x y is transformed into a term with type [c]^max(m,n). This is the minimal lifting necessary to obtain the correct elementwise application of f. If m < n then promotion will take place on the first argument, if m > n on the second, and if m = n then there will be an elementwise application without promotion.
Unless you say that a->b->c is convertible to a->[b]->[c] *except* when a is a list. Then it's bad again. There should be no negative conditions in the type system! Moreover, in a polymorphic function you don't know yet if a will be a list or not.
Due to the principle of minimal lifting (which implies already well-typed terms should not be transformed) a call to a polymorphic function should not be transformed unless there is a dependence between the type variable(s) of the function and of the argument(s) in the application. Such dependencies could possibly occur in recursive calls in function definitions. Consider, for instance the (somewhat meaningless) definition f x y = head (f [x,x] y) During type inference, f will first be assigned the type a -> b -> c. In the recursive call, f will be called on arguments with types [a] and b. This causes a lifting to occur, where f is elementwise applied to [x,x] with promotion of y. The transformed definition becomes f x y = head (zipWith f [x,x] (repeat y)) On the other hand, if f somewhere else is applied to some other arguments, with types not containing a, then no transformation of that call will occur.
There are no full and partial applications because of currying. It's impossible to say when you should consider a function as a multiparameter function. There are only single-argument functions. So you would have to say that some rule apply only *unless* the result has a function type, which does not work again.
Touché! To keep the discussion simple I have kept multiparameter functions curried, but you nailed me. Yes, there will be ambiguities if you allow overloading on other than the first argument in a curried definition (since there really is only one argument). So for a function f :: a -> b -> c we should only allow elementwise overloadings corresponding to functions of types [a]^n -> [b -> c]^n. Elementwise overloading on multiparameter functions must appear only on their uncurried forms, so only if f :: (a,b) -> c then we can allow transformations of calls corresponding to type signature ([a]^m,[b]^n) -> [c]^max(m,n). (This would give problems with elementwise overloading of arithmetic operators in Haskell, since these are curried. But, as I said earlier, I'm not proposing to actually extend Haskell with this overloading, I'm only discussing the concept as such in the Haskell context.)
With your rules a programmer writes code which is meant to implicitly convert a value to a single-element list, because something tries to iterate over it like on a list. Unfortunately the element happens to be a string, and he gets iteration over its characters. And if it works the other way, another programmer meant iteration over characters and got iteration over a single string. You can't tell which was meant.
I don't think there will be any ambiguities here. The overloading is resolved statically, at compile-time, for each call to the function. Calls to polymorphic functions are not transformed (except for cases like I showed above).
Of course the type/term transformation system must have the property that if different transformations can yield the "best" type (wrt liftedness), then the transformed expressions should be semantically equivalent.
It's not enough, because the least lifted type is not the most general answer. Answers for different amounts of liftedness are incompatible with that answer - they are not its instances as in the HM typing.
It does not matter that they are not instances. Each call is transformed statically, separately. The liftedness ordering is used only to direct the resolution of the overloading, so we pick the minimal lifting (the others are not interesting). The overloaded function itself will have the same type everywhere. Björn Lisper
Fri, 9 Feb 2001 15:21:45 +0100 (MET), Bjorn Lisper <lisper@it.kth.se> pisze:
No, the transformation is a single step procedure where a term is transformed into a typeable term (if possible) with a minimal amount of lifting. You don't compose transformations.
So functions implicitly lifted can't be used in the same ways as functions originally defined as lifted (namely, they can't be lifted again)... This is bad.
Due to the principle of minimal lifting (which implies already well-typed terms should not be transformed) a call to a polymorphic function should not be transformed unless there is a dependence between the type variable(s) of the function and of the argument(s) in the application.
Does f x y = (x, x + y) has type Num a => a -> a -> (a, a) and thus it cannot be used on the type Int -> [Int] -> (Int, [Int]) even though if its body was inlined into an expression requiring that type, it could (by lifting x+y to map (x+) y)? You can't lift arbitrary function of type Int -> Int -> (Int, Int) into Int -> [Int] -> (Int, [Int]) without knowing its defintion. Try it with g x y = (y, x). This is bad: I cannot always take a subexpression and move it into a separate function.
With your rules a programmer writes code which is meant to implicitly convert a value to a single-element list, because something tries to iterate over it like on a list. Unfortunately the element happens to be a string, and he gets iteration over its characters. And if it works the other way, another programmer meant iteration over characters and got iteration over a single string. You can't tell which was meant.
I don't think there will be any ambiguities here. The overloading is resolved statically, at compile-time, for each call to the function. Calls to polymorphic functions are not transformed (except for cases like I showed above).
Suppose there is a function fancyPrint :: Printable a => [a] -> IO () which applies some fancy printing rules to a list of printable values. A programmer knows that this function can be used on lists as well as on single elements, because those elements will be promoted to single-element lists as necessary. So far so good. Then he applies it to a single String. Guess what? It is not promoted to a single-element list, but each character is printed separately. Oops! The rule that fancyPrint works for single printable objects is valid as long as this single element is *not* a list. Your rules create many opportunites for functions which work on a certain well-described domain *except* some specific types on which they break.
It's not enough, because the least lifted type is not the most general answer. Answers for different amounts of liftedness are incompatible with that answer - they are not its instances as in the HM typing.
It does not matter that they are not instances.
It does. It's not enough to check that there exists a set of places to insert map or zipWith which transforms what is written to what I need. Because there can be a different, incompatible set of places, which is considered "better" by the compiler and my set is not obtainable from what the compiled has done. See the first example above. The HM type system does have the property that I can think about more specific types than ones inferred by the compiler, and as long as the program can be typed under stricter assumptions, it works as expected. The compiler may infer more general types than I thought about, but in such case my type is an instance of the compiler's type and the result is the same. -- __("< Marcin Kowalczyk * qrczak@knm.org.pl http://qrczak.ids.net.pl/ \__/ ^^ SYGNATURA ZASTÊPCZA QRCZAK
Marcin Kowalczyk:
Me: No, the transformation is a single step procedure where a term is transformed into a typeable term (if possible) with a minimal amount of lifting. You don't compose transformations.
So functions implicitly lifted can't be used in the same ways as functions originally defined as lifted (namely, they can't be lifted again)... This is bad.
Functions themselves are never lifted. They just appear to be lifted when applied to arguments of certain types, and then the function application is always statically resolved into an expression where the function has its original type.
Due to the principle of minimal lifting (which implies already well-typed terms should not be transformed) a call to a polymorphic function should not be transformed unless there is a dependence between the type variable(s) of the function and of the argument(s) in the application.
Does f x y = (x, x + y) has type Num a => a -> a -> (a, a) and thus it cannot be used on the type Int -> [Int] -> (Int, [Int]) even though if its body was inlined into an expression requiring that type, it could (by lifting x+y to map (x+) y)?
Your function has its polymorphism constrained to the Num class. So we could allow elemental overloading (on the uncurried form of f) as long as [Int] is not an instance of Num. Yes, if [Int] is made an instance of Num then the meaning of calls to f on lists will change from the elemental meaning to the meaning defined through the instance declarations for [Int]. This can surely be a problem in some cases. But this is not a property of the elemental overloading mechanism per se, but rather that we would have two different overloading mechanisms in the language powerful enough to specify conflicting overloading. BTW, the type signature for your "lifted f" (if it existed) should be (Int,[Int]) -> [(Int, Int)]. See second example below.
You can't lift arbitrary function of type Int -> Int -> (Int, Int) into Int -> [Int] -> (Int, [Int]) without knowing its defintion. Try it with g x y = (y, x).
Consider uncurried g: g (x,y) = (y,x) and assume it has an explicit type declaration to (Int,Int) -> (Int, Int) (so it's not polymorphic). if x :: Int and l :: [Int], then g (x,l) -> zipWith (g.(,)) (repeat x) l :: [(Int,Int)]. The rewrite of the overloaded application is guided only by type information. (Again note only the application of g is rewritten, neither g itself nor its type does change.)
Suppose there is a function fancyPrint :: Printable a => [a] -> IO () which applies some fancy printing rules to a list of printable values.
A programmer knows that this function can be used on lists as well as on single elements, because those elements will be promoted to single-element lists as necessary. So far so good.
The rules I have sketched so far only promote a value in connection with elemental overloading. A good example is g (x,l) above. Here, g is elementwise applied to l and in the process x becomes promoted into (repeat x), similar to the original scaling example a*x where a is a scalar and x a matrix. So with these rules alone fancyPrint 17 would not be rewritten into fancyPrint (repeat 17). But the rules can of course be extended to cover this case.
Then he applies it to a single String. Guess what? It is not promoted to a single-element list, but each character is printed separately. Oops!
Which is the original meaning of fancyPrint applied to a string. Why "oops"? A programmer must be aware of the meaning of function he writes. fancyPrint will always be a function over lists, no matter whether its use is overloaded on arguments of other types or not.
It's not enough, because the least lifted type is not the most general answer. Answers for different amounts of liftedness are incompatible with that answer - they are not its instances as in the HM typing.
It does not matter that they are not instances.
It does. It's not enough to check that there exists a set of places to insert map or zipWith which transforms what is written to what I need. Because there can be a different, incompatible set of places, which is considered "better" by the compiler and my set is not obtainable from what the compiled has done. See the first example above.
(I think your example was broken, but in principle you're right.) Of course, the use of the overloading I have described (and any kind of overloading) is justified only if the overloading matches the intuition of the programmer. If it misleads you then it is harmful. Regarding elemental overloading, my experience is that data parallel programmers quickly develop a strong intuition for it. What I have seen through examples is that elemental overloading using the rules I have sketched and the "minimal lifting" principle always seems to produce the intuitively correct meaning, also in a language like Haskell. If the produced result is the "right" one, then the fact that other possible transformations produce terms with incompatible types is not a concern. I can give no stronger justification than that. Björn Lisper
Mon, 12 Feb 2001 00:02:00 +0100 (MET), Bjorn Lisper <lisper@it.kth.se> pisze:
Functions themselves are never lifted. They just appear to be lifted when applied to arguments of certain types, and then the function application is always statically resolved into an expression where the function has its original type.
This does not solve the problems. Instead of composed liftings I will split the code into separate bindings. Suppose I write: let g x y = x + y f x y = g x y in f [1, 2] [10, 20] :: [[Int]] What does it mean? I could mean this: let g :: Int -> Int g x y = x + y f :: Int -> [Int] -> [Int] f x y = g x y in f [1, 2] [10, 20] :: [[Int]] which results in [[11, 21], [12, 22]], or this: let g :: Int -> Int g x y = x + y f :: [Int] -> Int -> [Int] f x y = g x y in f [1, 2] [10, 20] :: [[Int]] which results in [[11, 12], [21, 22]]. Anyway, somebody loses (one who thought that his version would be chosen by the compiler). If you think that the fact that bodies of let-bound variables are typechecked prior to their usage help, let's transform let to lambdas (it's not used polymorphically so it's possible): (\g -> (\f -> f [1, 2] [10, 20] :: [[Int]]) (\x y -> g x y)) (\x y -> x + y) Now it is not clear in what order this should be typechecked, and different orders give different results. It can be beta/eta-reduced to [1, 2] + [10, 20] :: [[Int]] and I really don't know what meaning would you give to it. Anyway, examples are pointless. Functional programming, as opposed to imperative programming, leads to more common use of lists and functions as values (instead of repeated stateful calls you return all elements in a list to process them later), also Maybes, tuples etc. Function explicitly take as arguments things they depend on, explicitly return things they modify, functions are curried, there are combinators like (.) or curry which manipulate functions without applying them... All this means that there are many more places when somebody can make a type error by mismatching levels of lifting functions or lifting repetition. When I am making a type error, the last thing I want from a compiler is to guess what I could mean and silently compile incorrect code basing on this assumption. I could have done the error in a different place!
Does f x y = (x, x + y) has type Num a => a -> a -> (a, a) and thus it cannot be used on the type Int -> [Int] -> (Int, [Int]) even though if its body was inlined into an expression requiring that type, it could (by lifting x+y to map (x+) y)?
Your function has its polymorphism constrained to the Num class. So we could allow elemental overloading (on the uncurried form of f) as long as [Int] is not an instance of Num.
Suppose [Int] is not Num. I want to treat f as if it meant f :: Int -> [Int] -> (Int, [Int]) f x y = (x, map (x+) y) because you told me that map is optional: it will be inserted automatically when necessary.
BTW, the type signature for your "lifted f" (if it existed) should be (Int,[Int]) -> [(Int, Int)]. See second example below.
I want to lift (+) used inside f. Haskell does not require from me to write all type signatures so I haven't write one in this case, because I know that Haskell's type system recovers principal types automatically (except ambiguities related to classes).
The rewrite of the overloaded application is guided only by type information.
Often there is no any type information at a given place. Only at some later point, when we are considering a toplevel definition with a type signature. Usually types are inferred from definitions and usages of each identifier, and a mismatch means that there is a type error. There is no attempt to guess how to fix it automatically because the error might be detected at a different place than the change really should be made.
So with these rules alone fancyPrint 17 would not be rewritten into fancyPrint (repeat 17). But the rules can of course be extended to cover this case.
I thought it was rewritten to fancyPrint [17], as this is the obvious way to convert a scalar to a list... See, it cannot be implicit, because different people mean different things.
Then he applies it to a single String. Guess what? It is not promoted to a single-element list, but each character is printed separately. Oops!
Which is the original meaning of fancyPrint applied to a string. Why "oops"?
Because I forgot that String is a list, did not treat it as a list, but as a scalar. I can do it now - except a few cases, but when I can't (some instances) the compiler will remind me by an error. This is not the case with your proposal.
fancyPrint will always be a function over lists, no matter whether its use is overloaded on arguments of other types or not.
Similarly, (+) will always be a function over scalars, unless you make Num instances for lists.
Of course, the use of the overloading I have described (and any kind of overloading) is justified only if the overloading matches the intuition of the programmer. If it misleads you then it is harmful. Regarding elemental overloading, my experience is that data parallel programmers quickly develop a strong intuition for it.
Perhaps because they don't use higher order functions and arrays they use always represent arrays of the problem domain, and not a way to produce multuple results together? It's a very specific need. And a request for convenience, not a functional feature. I'm sure it does not make sense to ever change the Haskell's type system in sush radical way. When Int is unified with [Int], it's simply an error. -- __("< Marcin Kowalczyk * qrczak@knm.org.pl http://qrczak.ids.net.pl/ \__/ ^^ SYGNATURA ZASTÊPCZA QRCZAK
Marcin 'Qrczak' Kowalczyk:
Me:
Functions themselves are never lifted. They just appear to be lifted when applied to arguments of certain types, and then the function application is always statically resolved into an expression where the function has its original type.
This does not solve the problems. Instead of composed liftings I will split the code into separate bindings. Suppose I write:
let g x y = x + y f x y = g x y in f [1, 2] [10, 20] :: [[Int]]
What does it mean? I could mean this:
let g :: Int -> Int g x y = x + y f :: Int -> [Int] -> [Int] f x y = g x y in f [1, 2] [10, 20] :: [[Int]]
which results in [[11, 21], [12, 22]], or this:
let g :: Int -> Int g x y = x + y f :: [Int] -> Int -> [Int] f x y = g x y in f [1, 2] [10, 20] :: [[Int]]
which results in [[11, 12], [21, 22]]. Anyway, somebody loses (one who thought that his version would be chosen by the compiler).
Actually, both will lose :-). If we change f to uncurried form f(x,y) = g x y then we will have f :: (Int,Int) -> Int, and f [1, 2] [10, 20] -> zipWith f.(,) [1, 2] [10, 20] :: [Int] which evaluates to [11,22]. If you mean that f [1, 2] [10, 20] is explicitly typed to [[Int]], then I'd say a type error is the correct result. I think explicit typing should only affect the HM typing of the transformed expression by possibly giving it a less general type, it should not coerce the elemental overloading into a more lifted result than necessary.
If you think that the fact that bodies of let-bound variables are typechecked prior to their usage help, let's transform let to lambdas (it's not used polymorphically so it's possible):
(\g -> (\f -> f [1, 2] [10, 20] :: [[Int]]) (\x y -> g x y)) (\x y -> x + y)
Now it is not clear in what order this should be typechecked, and different orders give different results.
Unlike algorithm W, a type inference algorithm that resolves elemental overloading as part of the type inference must (I believe) maintain a set of different possible assumptions about the type variables, and in the end make a choice guided by the "minimal lifting" principle. In your example (with uncurried f) there will be an assumption f::(Int,Int)->a stemming from (\f -> ...)(\x y -> g x y) and an assumption f::([Int],[Int])->b from f [1, 2] [10, 20]. These types cannot be unified, but can be made related wrt the "liftedness" order if b=[a]. Minimal lifting now dictates that (Int,Int)->a is chosen, and f [1, 2] [10, 20] is subsequently transformed as above into an expression of type [Int]. A type error follows since [Int] is not a substitution instance of [[Int]]. I should say I don't have the details of an inference algorithm sorted out, but I think something along the lines above should work.
It can be beta/eta-reduced to [1, 2] + [10, 20] :: [[Int]] and I really don't know what meaning would you give to it.
If + has uncurried type then [1, 2] + [10, 20] -> zipWith (+).(,) [1, 2] [10, 20] :: [Int], but in general one should not expect that unresolved overloaded expressions have the subject reduction property. (For instance, the example above breaks if + has curried type Int -> Int -> Int.)
Anyway, examples are pointless. Functional programming, as opposed to imperative programming, leads to more common use of lists and functions as values (instead of repeated stateful calls you return all elements in a list to process them later), also Maybes, tuples etc. Function explicitly take as arguments things they depend on, explicitly return things they modify, functions are curried, there are combinators like (.) or curry which manipulate functions without applying them...
All this means that there are many more places when somebody can make a type error by mismatching levels of lifting functions or lifting repetition.
Probably true. What I have tried to argue is merely that elemental overloading probably can be done in a consistent way even in language like Haskell that has an advanced type system. I don't deny that there can be problems if it behaves in ways unexpected to the programmer.
When I am making a type error, the last thing I want from a compiler is to guess what I could mean and silently compile incorrect code basing on this assumption. I could have done the error in a different place!
Well, "silent": as for any kind of syntactical convenience, the use of elemental overloading would require the possibility to obtain good diagnostics and information about the resulting typings and transformed expressions.
Of course, the use of the overloading I have described (and any kind of overloading) is justified only if the overloading matches the intuition of the programmer. If it misleads you then it is harmful. Regarding elemental overloading, my experience is that data parallel programmers quickly develop a strong intuition for it.
Perhaps because they don't use higher order functions and arrays they use always represent arrays of the problem domain, and not a way to produce multuple results together?
These languages are invariably first order, but some have datatypes like nested sequences. Arrays are used for different purposes, ranging from pointer tables to problem representations, and elemental overloading is used for both.
It's a very specific need. And a request for convenience, not a functional feature. I'm sure it does not make sense to ever change the Haskell's type system in sush radical way. When Int is unified with [Int], it's simply an error.
(They're not unified!) I should say something about the roots of my interest. I have been working on a dialect of Haskell directed towards data-parallel style specification/rapid prototyping of parallel algorithms. Thus, the idea is to combine all the powerful abstraction features of Haskell with the data parallel paradigm. In this context, I think the elemental overloading would fit in just fine. I will end this discussion unilaterally now. I don't think I have anything more to add. Björn Lisper
Wed, 14 Feb 2001 00:20:41 +0100 (MET), Bjorn Lisper <lisper@it.kth.se> pisze:
When Int is unified with [Int], it's simply an error.
(They're not unified!)
I meant: when the code leads to unification of Int with [Int], e.g. by applying a function of type Int->whatever to [Int]. -- __("< Marcin Kowalczyk * qrczak@knm.org.pl http://qrczak.ids.net.pl/ \__/ ^^ SYGNATURA ZASTÊPCZA QRCZAK
On Tue, Feb 06, 2001 at 10:29:36PM +0100, Andreas Gruenbacher wrote:
... Also not all instances of Num can be shown. I have a monad that is an instance of Num, for example. I cannot possibly show the monad.
I've been thinking about this a little. It's quite an interesting problem in general to write classes that can be defined for monads. This can be done for any class in which each member returns the type variable: class C a where foo :: ... -> a (etc.) is good, but anything else seems to cause problems. So '+', '-', 'max', etc., are good, but '<' and 'show' cause problems. 'quotRem' and 'divMod' are interesting cases: they return a pair (a,a), which is OK for some monads but not for others. I wonder if there is a way to set things up so that all classes could be written for monadic types. Best, Dylan Thurston
On Tue, 6 Feb 2001, Dylan Thurston wrote:
On Tue, Feb 06, 2001 at 03:25:11PM +0100, Koen Claessen wrote:
What do people think about this? If people prefer these stylistic changes, I think we should not hesitate making them for Haskell/2 by completely redesigning the module structure and using more consistent naming conventions.
These sound great to me. If Haskell/2 is indeed open to such changes, would also be possible to revamp the numeric modules? As a mathematician, I get annoyed by such things as
* (+) and (-) being lumped in with (*) (doesn't anyone use vector spaces?)
Another problem is that sometimes several types of multiplication are possible. In Matlab and PerlDL, for instance, matrixes can be multiplied cell by cell, or matrix-wise. Of course both languages differntiate those two uses: in Matlab matrix mulitplication is "*" and cell-by-cell one is ".*"; in PerlDL matrix multiplication is "x" (which is a perl operator that normally means string or array replication) and cell-by-cell one is "*". So I suppose each one of those operators should be on its own template (or class in Haskell-speak). Afterwards, all we have to do is write HaskellDL... :) Regards, Shlomi Fish ---------------------------------------------------------------------- Shlomi Fish shlomif@vipe.technion.ac.il Home Page: http://t2.technion.ac.il/~shlomif/ Home E-mail: shlomif@techie.com The prefix "God Said" has the extraordinary logical property of converting any statement that follows it into a true one.
Dylan Thurston wrote:
These sound great to me. If Haskell/2 is indeed open to such changes, would also be possible to revamp the numeric modules? As a mathematician, I get annoyed by such things as
* (+) and (-) being lumped in with (*) (doesn't anyone use vector spaces?)
* the function 'atan2' being mixed in with a bunch of operations very specific to the floating point format in the 'RealFloat' class. Same problem (though less serious) with 'quot', etc., and 'toInteger' in the Integral class.
* Superfluous superclasses: why are Show and Eq superclasses of Num? Not all numeric types have decidable equality. Think arbitrary precision reals.
Haskell was intended for use by programmers who may not be mathematicians, as a general purpose language. Changes to make keep mathematicians happy tend to make it less understandable and attractive to everyone else. Specifically: * most usage of (+), (-), (*) is on numbers which support all of them. * Haskell equality is a defined operation, not a primitive, and may not be decidable. It does not always define equivalence classes, because a==a may be Bottom, so what's the problem? It would be a problem, though, to have to explain to a beginner why they can't print the result of a computation. --brian
import Handle as H
H.getLine
(This is a good example where type classes would not help making this any better, since the types of getLine and H.getLine are very different.)
not too different, I think; static overloading would help. Just allow to have two (or more) identifiers with the same name, but different types. getLine :: IO String; getLine :: Handle -> IO String At each usage of getLine, the typechecker should follow both tracks, and take the one that is type-correct. There should be exactly one; and the programmer can achieve this by adding an explicit signature. (*) This would also allow algebraic data types to share field labels, without any changes to record syntax and semantics (I hope). (*) there is a problem if you have a class method (like `map' in Functor) and a function (like `map' for lists) of the same name, and an instance Functor []. This is really only a problem if all of these declarations are visible at once. But then, this can be fixed using qualified imports. Best regards, -- -- Johannes Waldmann ---- http://www.informatik.uni-leipzig.de/~joe/ -- -- joe@informatik.uni-leipzig.de -- phone/fax (+49) 341 9732 204/252 --
Wed, 7 Feb 2001 10:08:14 +0100 (MET), Johannes Waldmann <joe@isun.informatik.uni-leipzig.de> pisze:
getLine:: IO String; getLine :: Handle -> IO String
At each usage of getLine, the typechecker should follow both tracks, and take the one that is type-correct.
There is exponential growth of possibilities in compound expressions. And I'm afraid that ambiguities would happen in unexpected places and it would not be easy to find where to add type signatures. Especially as there is less explicit type information than in many other statically typed languages.
(*) there is a problem if you have a class method (like `map' in Functor) and a function (like `map' for lists) of the same name, and an instance Functor [].
In this case map for lists is unnecessary: just use Functor's map. So why is fmap separate now? Probably because having too much overloading causes ambiguities. -- __("< Marcin Kowalczyk * qrczak@knm.org.pl http://qrczak.ids.net.pl/ \__/ ^^ SYGNATURA ZASTÊPCZA QRCZAK
There is exponential growth of possibilities in compound expressions. And I'm afraid that ambiguities would happen in unexpected places and it would not be easy to find where to add type signatures. Especially as there is less explicit type information than in many other statically typed languages.
Yes, I see that. However I think that adding type signatures is good programming practice anyway, and I wouldn't mind if a future Haskell required me to do some explicit typing (for top-level definitions, say). What are the ergonomic benefits of allowing the programmer to omit type declarations? It does invite sloppy programming, no? And does it make life easier or harder for the compiler (writer)? Best regards, -- -- Johannes Waldmann ---- http://www.informatik.uni-leipzig.de/~joe/ -- -- joe@informatik.uni-leipzig.de -- phone/fax (+49) 341 9732 204/252 --
Thu, 8 Feb 2001 12:46:29 +0100 (MET), Johannes Waldmann <joe@isun.informatik.uni-leipzig.de> pisze:
Yes, I see that. However I think that adding type signatures is good programming practice anyway, and I wouldn't mind if a future Haskell required me to do some explicit typing (for top-level definitions, say).
Types of top-level definitions are not enough when every identifier can have many completely unrelated types, and types of subexpressions are derived both from their contents and context.
What are the ergonomic benefits of allowing the programmer to omit type declarations? It does invite sloppy programming, no? And does it make life easier or harder for the compiler (writer)?
Adding overloading like in C++ certainly it makes life harder for the compiler writer. IMHO it does not work at all in a language with HM type system when the type inference does not proceed inside-out only. -- __("< Marcin Kowalczyk * qrczak@knm.org.pl http://qrczak.ids.net.pl/ \__/ ^^ SYGNATURA ZASTÊPCZA QRCZAK
On 07-Feb-2001, Marcin 'Qrczak' Kowalczyk <qrczak@knm.org.pl> wrote:
So why is fmap separate now? Probably because having too much overloading causes ambiguities.
Perhaps. But I think there may be other reasons too. Having fmap separate is useful for beginners and for teaching, because you can describe `map' without having to talk about type classes. Also, it is possible that the error messages that you get when you make a mistake using `fmap' might be harder to understand. The reasoning here is similar to the reasons that Haskell 98 has list comprehensions rather than monad comprehensions. -- Fergus Henderson <fjh@cs.mu.oz.au> | "I have always known that the pursuit | of excellence is a lethal habit" WWW: <http://www.cs.mu.oz.au/~fjh> | -- the last words of T. S. Garp.
Marcin 'Qrczak' Kowalczyk schrieb folgendes am Tue, Feb 06, 2001 at 12:54:29PM +0100:
On Tue, 6 Feb 2001, Olaf Chitil wrote:
I just see one problem with John's proposal: the type Byte.
type Byte = Word8
I would prefer type Octet = Word8 to emphasise that the functions really uses 8 bits. -- Stefan Karrmann
On Tue, 6 Feb 2001, Stefan Karrmann wrote:
type Byte = Word8
I would prefer
type Octet = Word8
to emphasise that the functions really uses 8 bits.
I would define Byte as something different on an architecture where the basic file unit is not 8 bits. It's like char in C. -- Marcin 'Qrczak' Kowalczyk
participants (15)
-
Andreas Gruenbacher -
Bjorn Lisper -
Brian Boutel -
Dylan Thurston -
Erik Meijer -
Fergus Henderson -
Johannes Waldmann -
John Meacham -
Koen Claessen -
Marcin 'Qrczak' Kowalczyk -
Olaf Chitil -
qrczak＠knm.org.pl -
Shlomi Fish -
Simon Marlow -
Stefan Karrmann