August 2008 - Haskell-prime

Mutually-recursive/cyclic module imports
by Isaac Dupree 03 Sep '08

03 Sep '08

Haskell-98 specifies that module import cycles work automatically with cross-module type inference. It has some weird interactions with defaulting and the monomorphism restriction. In Haskell-prime we're planning on removing artificial monomorphism, but defaulting will still be necessary (and can still be set differently per module). Only JHC fully implements the recursive module imports of Haskell-98. GHC and NYhc each have their own proprietary "boot-files" with slightly odd semantics to allow this to work (albeit the syntax is simple enough) Hugs doesn't support it at all. I propose we simplify things and lay down some rules, without having to invent explicit module-interface signatures. Then I wouldn't complain(:-)) that GHC doesn't have reasonable support for cyclic modules [1][2]. (Compiler writers will have to give feedback how plausible this is :-) -- I think GHC and NYhc "should" be able to adapt their boot-interface-file mechanisms to the scheme I'm proposing.. (This is really more of a sketch than a complete proposal at this stage.) In particular, I propose an amount of annotation in a module that *shall* make it compile. Compilers are free to accept code for other reasons (e.g. .hs-boot files, or some official module interfaces). These first proposals are clean-ups that reflect how ridiculous people think the current standard's module interface semantics are compared to most languages. Also they make cross-module type inference unnecessary, eliminating the defaulting problem. namespace level: Haskell98 says that what a module exports is determined by the smallest fix-point of what is possible. I can't see a practical use for this behavior, which is easily confusing. I think that exports that depend on the result of a fix-point should be rejected. It can be useful in module A to import a few types/functions explicitly from a module B that then goes on to export the whole of module A though. type level: Inside any given SCC (loop) of modules, any function imported from another member of the SCC normally shall have an explicit type signature in the module that exports it. (This doesn't seem a great burden, since type-signature for top-level functions/values are considered good practice anyway. Can anyone think of a use-case where cross-module type inference would be particularly useful?) Exception: imports may be given the {-# SOURCE #-} pragma. This fulfills two purposes: (1) It is a hint to a compiler that compiles modules separately that the current module should be compiled before the module being imported with {-# SOURCE #-}. Obviously, this can make optimization worse, since it's likely that SOURCE-imported functions won't be strictness-analyzed or inlined or anything; but that's the .hs-boot situation already. (And in principle even a compiler that likes separate compilation could break individual functions down into dependency order to compile them, adding another tradeoff point...) (2) If SOURCE pragmas "break the loop", then only functions that are actually imported with SOURCE must be given type signatures, even if module B then goes on to import module A wholesale: example: module A where {import {-#SOURCE#-} B (bf); ...} module B (module A, module B) where {import A; bf :: ...; ...} Since defining data types in logical places is an important use of cyclic imports, I propose not to require any extra annotation for them; the compiler will have to chase them down and understand them in loops (how else to do it?). However, there are some particular things to keep in mind regarding potential recompilation: (with a bit of a GHC bias) Changing any orphan instances in an SCC will force the whole thing to recompile (but what pluckiness, putting orphan instances *there*!) If a data type or newtype is imported without its constructors, then the RHS changing doesn't really force a recompile. I imagine this could work in GHC by, for each SOURCE import, storing the MD5 of the imported interface. Then when checking if you seriously have to recompile module A, you don't have to if none of those MD5s have changed and none of the non-SOURCE-imported modules' interface MD5s have either. In module cycles that aren't explicitly broken by SOURCEs, GHC (or any compiler) should just insert an implicit SOURCE for *all* cyclic imports (and possibly emit a warning) (unless the compiler wants to guess which SOURCES are better for optimization?). Presumably compilers that can do separate as well as non-separate compilation could take an optimization flag that tells them to compile cycles together as one piece rather than obeying the SOURCES for recompilation efficiency. so what does the compiler have to look at in a SOURCE-imported modules? In the case of the proposed SOURCE imports without hs-boot files, GHC would move from calculating one interface(md5) per module (or two interfaces in the case of .hs-boots), to one-per-import. I think this is, in principle, an advantage, although it does require more re-scanning when files are changed (only lexer/parser/renamer/module-chaser work). For example, I've found myself adding to .hs-boot files for the purpose of one module that SOURCE-imports the .hs-boot, which forces the recompile of another module that happens to depend on the .hs-boot too. To replicate the current GHC .hs-boot behavior (in which the hash-recalculation is shared among SOURCE-importers), one could replace a X.hs-boot file with an X_boot.hs file that contains: module X_boot (module X) where import {-# SOURCE #-} X (list of things exported by the old .hs-boot file) , and in other modules, replace import {-# SOURCE #-} X (....) with import X_boot (....) Taking .hs-boot docs as a guide [2], the compiler must look in SOURCE-imported modules for: - if an import list is given explicitly, `B (....)` not `B hiding (....)` or `B`, the export list only needs to be *checked* to make sure it exports the requested things, not remembered. Exception: data or class imported with `Name(..)` must remember exactly which constructors/members were exported. It's recommended to specify exactly what you're importing. - function type signatures - imports of functions, types, etc. If it's imported from outside the SCC, it doesn't need a type signature/whatever. If it's defined somewhere within the SCC, it generally does need a type signature. - fixity declarations, which only have to be imported in conjunction with the corresponding functions/constructors/whatever - data type / newtype declarations. When no constructor is imported, only the *kind* of the data type needs to be recorded, which might have to involve inference on the RHS (possibly involving more import chasing) if there aren't explicit kind annotations for *every* type parameter. - type synonym declarations. The whole thing has to be imported, including RHS. - classes. Including superclasses, class-method signatures, and default methods? Is there some way that GHC manages to allow not declaring all of these in .hs-boots? - instances, whether generated by 'deriving', 'deriving instance', or ordinary 'instance'; everything before the "where" clause of 'instance's is relevant. But an instance is only relevant if it's orphan, or if goes with a data or class that's also being imported. - the compiler-specific RULES pragmas probably follow similar mandates as above for instances and for the functions referenced in the RULE. [1] my official "complaint": http://hackage.haskell.org/trac/ghc/ticket/1409 [2] the GHC .hs-boot docs: http://www.haskell.org/ghc/docs/latest/html/users_guide/separate-compilatio…

6 12

Re: New language feature: array-types
by Lennart Augustsson 20 Aug '08

20 Aug '08

As for array updating, there are many ways to improve the O(n) update. You can use a tree representation and get O(log n) for all operations. You can use the array single threaded in the ST monad and get all the usual array operation complexities. Etc. etc. On Mon, Aug 18, 2008 at 8:16 AM, Ramin Honary <ramin.honary(a)gmail.com> wrote: > Really? Where the bounds checking can be done at compile-time? (Excluding > cases where the array object is accessed by a constant value set at > run-time...) > I have seen an array type, but not a "bounded array" type where the size of > the array is given in the type definition, (as I explained with the example > in my last e-mail.) > Then is there any work being done in Haskell prime to improve the efficiency > of updating arrays. From the wiki pages I have read, it is impossible to > make any array that updates faster than O(n). > (Also, should I send replies to the haskell wiki?)

4 4

Re: New language feature: array-types
by Lennart Augustsson 18 Aug '08

18 Aug '08

Have a look at http://okmij.org/ftp/Haskell/eliminating-array-bound-check.lhs On Mon, Aug 18, 2008 at 8:16 AM, Ramin Honary <ramin.honary(a)gmail.com> wrote: > Really? Where the bounds checking can be done at compile-time? (Excluding > cases where the array object is accessed by a constant value set at > run-time...) > I have seen an array type, but not a "bounded array" type where the size of > the array is given in the type definition, (as I explained with the example > in my last e-mail.) > Then is there any work being done in Haskell prime to improve the efficiency > of updating arrays. From the wiki pages I have read, it is impossible to > make any array that updates faster than O(n). > (Also, should I send replies to the haskell wiki?)

1 0

New language feature: array-types
by Ramin 17 Aug '08

17 Aug '08

I am new to both the Haskell language, and to this group, but I have recently become obsessed with the mathematical precision of Haskell, and I want to help improve it, if members of the group could bear with me. The one thing I dislike about the Haskell language is it's treatment of arrays. I don't understand how things work internally to the system, and perhaps array-manipulating code can be efficiently optimized, but I would prefer to have a language feature for explicitly creating and modifying arrays in a way that does not require the entire array be copied on every update. My idea is this: a fixed-width mutable array can be declared as a type, much like a list, but can be evaluated more like a bitwise-integer operation. -- in an array of A's set the 5th item in the array with an "initial-A" value changeArrayFunc :: a^10 -> a^10 changeArrayFunc ar = (ar:5 <- initA) -- returns an array which is that same as the old array, except the value at index 5 is different. -- select the 5th item of an array getArrayItemFunc :: a^10 -> a getArrayItemFunc ar = (ar:5) Here, I use the caret (^) operator to indicate an "array-10" type. I used caret because it is typically used for exponents -- as in, if your data type has N possible values, an array with 10 units would have N^10 possible values. Then, I use the colon (:) operator to do indexing. I've seen the various proposals for indexing operators and honestly I don't care which operator is chosen; I just use the colon operator because that is how lists are treated in pattern matching. The important thing is that an array-type exists, that way all bounds-checking can be done at compile-time by the typing system. Using arrays of different lengths would result in a compile-time error: Obviously, this will increase the complexity of the typing system. data Something = Array Int^10 change5Array :: Int^5 -> Int^5 change5Array ar = ((ar:4) <- 0) -- Something has an array of type Int^10, but calls "change5Array" which expects an Int^5 badFunc :: Something -> Int badFunc (Array x) = (change5Array x) -- COMPILE-TIME ERROR -- Arrays.hs:8:16: -- Couldn't match expected type `Int^5' against inferred type `Int^10' -- In the first argument of `change5array', namely `x' -- In the expression: (change5array x) -- In the definition of `badFunc': -- badFunc (Array x) = (change5Array x) ...or something like that. An efficient implementation of array access would make Haskell very useful for a much wider variety of computationally intensive applications. Haskel could be used to efficiently model memory access, provided that the interpreter knew not to "copy" arrays upon update, but simply to update a value within an array. If arrays were a language feature of Haskell, then this optimization could be guaranteed. If anyone takes the time to consider this idea, or to tell my why this isn't necessary, I would be most greatful. -- Ramin Honary

2 1

empty case, empty definitions
by Isaac Dupree 16 Aug '08

16 Aug '08

There are two separate parts I propose, the second one I'm less sure of, but they're somewhat related. 1. Allow empty case, i.e. "case some_variable of { }" (GHC ticket [1]). This adds consistency, it always causes a pattern-match error, and it is a sensible way to look at all the cases of types with no constructors (recall EmptyDataDecls will probably be in Haskell' [4]) -- especially for automatic tools (or programmers familiar with dependent types; GADTs have some of these effects :-)). Presumably, any time that some_variable could be non-bottom, GHC will warn about the incomplete patterns :-). 2. When a type signature for a function is given, allow to not define any patterns (GHC ticket [2]). The result of calling the function is a pattern match failure (presumably the source-location given for the match failure will be the location of the type-signature). This can also be useful for calling functions before implementing them, helping the type-checker help me do incremental work (again, obviously produces a warning if the function could possibly be non-bottom). However I can think of a few things this (proposal 2) could interfere with: 2.i. Implementing a class method, will you get the default if that method has a default? Actually it turns out to be forbidden... class C n where foo :: n -> n foo = id instance C Int where foo :: Int -> Int --even if we define foo here too, it's an error: --misplaced type signature (perhaps thanks to improved --error messages, thanks simonpj! [5]). --Anyway, I think type signatures ought to be allowed here. I propose to allow type-signatures in instances, which must be equivalent to the signature in the class declaration after the class's signature is specialized to the particular instance type(s). If such a type-signature is found, allow the function to be defined as normal, which includes, if there are no patterns, an error if proposal 2 isn't adopted, and a pattern-match failure if proposal 2 is adopted. (also it turns out that pattern bindings aren't allowed in instances, such as {instance C Int where (foo) = negate}, but I can't say I have a compelling use-case for that!:-)) 2.ii. It could interfere with another feature request of mine (though I'm not sure I want it anymore) (GHC ticket [3]) : I'd like it to be allowed to give a (possibly more restrictive?) type signature at the top level of a module, to a function imported unqualified. Obviously in this case I don't want the function to be treated as pattern-match failure; but I think we can tell the difference because the name is in-scope in this case. Luckily there is no negative interaction with my related proposal to simply allow multiple equivalent type-signatures anywhere one of them is allowed in a declaration-list. So actually, in summary I can't really see anything wrong with proposal 2, especially if my proposal under 2.i. is adopted. [1] http://hackage.haskell.org/trac/ghc/ticket/2431 [2] http://hackage.haskell.org/trac/ghc/ticket/393 [3] http://hackage.haskell.org/trac/ghc/ticket/1404 [4] http://hackage.haskell.org/trac/haskell-prime/wiki/EmptyDataDecls [5] http://hackage.haskell.org/trac/ghc/ticket/1310

4 4