Re: Re[4]: inside the GHC code generator
On 2/24/06, Bulat Ziganshin <[EMAIL PROTECTED]> wrote: > Hello Lemmih, > > Friday, February 24, 2006, 1:15:51 PM, you wrote: > > >> clean differs from Haskell in support of unique types and strictness > >> annotations. the last is slowly migrates into GHC in form of shebang > >> patters, but i think that it is a half-solution. i mentioned in > >> original letter my proposals to add strictness annotations to > >> function types declarations and to declare strict datastructures, such > >> as "![Int]" > > L> As I've understood it, Clean's strictness annotations are a bit of a > L> hack which only works on certain built-in types. Am I mistaking here? > > i don't know Clean very well, although i've seen rumors that it > supports strict datastructures. after all, this don't need changes in > language itself, it's just a syntax sugar: > > data [a] = [] | a:[a] > x :: ![Int] > > translates to the > > data StrictList a = Nil | Cons a !(StrictList a) > x :: !(StrictList a) Let's try this: x :: ![Int] -> Int It would translate to something like this: mkStrictList :: [a] -> StrictList a x = xStrict . mkStrictList xStrict = ... Wouldn't it be very expensive to strictify the list? -- Friendly, Lemmih ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re[4]: inside the GHC code generator
Hello Lemmih, Friday, February 24, 2006, 1:15:51 PM, you wrote: >> clean differs from Haskell in support of unique types and strictness >> annotations. the last is slowly migrates into GHC in form of shebang >> patters, but i think that it is a half-solution. i mentioned in >> original letter my proposals to add strictness annotations to >> function types declarations and to declare strict datastructures, such >> as "![Int]" L> As I've understood it, Clean's strictness annotations are a bit of a L> hack which only works on certain built-in types. Am I mistaking here? i don't know Clean very well, although i've seen rumors that it supports strict datastructures. after all, this don't need changes in language itself, it's just a syntax sugar: data [a] = [] | a:[a] x :: ![Int] translates to the data StrictList a = Nil | Cons a !(StrictList a) x :: !(StrictList a) ... i've found the following in the 6 feb letter in cafe by Brian Hulley: Bulat Ziganshin wrote: > yes, i remember this SPJ's question :) "[!a]" means that list > elements are strict, it's the same as defining new list type with > strict elements and using it here. "![a]" means "strict list", it is > the same as defining list with "next" field strict: > > data List1 a = Nil1 | List1 !a (List1 a) > data List2 a = Nil2 | List2 a !(List2 a) > data List3 a = Nil3 | List3 !a !(List3 a) Clean allows (AFAIK) several distinctions to be made: 1) ![a] means that the list of a's is a strict argument, just like writing !b 2) [!a] means that the list is head strict (List1 a) 3) [a!] means that the list is tail strict (List2 a) 4) [!a!] means that the list is head and tail strict (List3 a) 5) ![!a!] means that the head-and-tail-strict-list-argument is strict!!! I think also (though I'm not entirely sure) that these distinctions are generalized for other data types by talking about element strictness and spine strictness. One motivation seems to be that in the absence of whole program optimization, the strictness annotations on a function's type can allow the compiler to avoid creating thunks at the call site for cross-module calls whereas using seq in the function body itself means that the thunk still has to be created at the call site because the compiler can't possibly know that it's going to be immediately evaluated by seq. and my own letter earlier on the 6 feb: >> foo :: !Int -> !Int KM> (Is the second ! actually meaningful?) yes! it means that the function is strict in its result - i.e. can't return undefined value when strict arguments are given. this sort of knowledge should help a compiler to "propagate" strictness and figure out the parts of program that can be compiled as strict code. really, i think ghc is able to figure functions with strict result just like it is able to figure strict function arguments KM> Personally, I think is much nicer than sprinkling seq's around, and KM> generally sufficient. However, there could perhaps be disambiguities? btw, it's just implemented in the GHC HEAD KM> Last time this came up, I think examples resembling these were brought KM> up: KM> foo :: [!a] -> ![a] -> a yes, i remember this SPJ's question :) "[!a]" means that list elements are strict, it's the same as defining new list type with strict elements and using it here. "![a]" means "strict list", it is the same as defining list with "next" field strict: data List1 a = Nil1 | List1 !a (List1 a) data List2 a = Nil2 | List2 a !(List2 a) data List3 a = Nil3 | List3 !a !(List3 a) the type List3 is a simple strict list, like in any strict programming language. foo :: [!a] -> ![a] -> ![!a] -> a translates to foo :: List1 a -> List2 a -> List3 a -> a KM> foo' :: Map !Int String -> Int -> String that means that keys in this map saved as strict values. for example, the following definition type Map a b = [(a,b)] will be instantiated to Map !Int String ==> [(!Int, String)] KM> Anyway, if a reasonable semantics can be formulated, I think KM> strictness type annotations would be a great, useful, and KM> relatively non-intrusive (AFAICT, entirely backwards compatible) KM> addtion to Haskell'. such proposal already exists and supported by implementing this in GHC HEAD -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re[4]: inside the GHC code generator
Hello Jean-Philippe, Friday, February 24, 2006, 2:04:57 AM, you wrote: JPB> From my (limited) knowledge of GHC backend, the difficult part of your JPB> plan is that STG is not suited to compilation to native C at all. You JPB> might need to do quite advanced translation from STG to another JPB> intemediate language, (as GRIN for example), and then some more JPB> advanced analysis/optimization before C can be generated. your knowledge is very limited, because STG at all times was compiled to C and then compiled by gcc :) moreover, it's very easy to implement efficient compilation of fac() definition from STG to "natural C". it's one-hour task, maximum. the real problem is changing the whole environment, including AST representing C code inside the GHC, RTS and so on JPB> iirc, the tricky part is the handling of lazyness. At any point you JPB> may end up with a thunk (closure), which ghc handles easily by JPB> "evaluating" it: it's always a function pointer. (That's the tagless JPB> part) When in WHNF, it just calls a very simple function that fills JPB> registers with the evaluated data. Otherwise, the function call JPB> performs the reduction to WHNF. STG attaches explicit typing information to any var. i propose: 1) compile code that works with unboxed values to equivalent "natural C" code 2) for the boxed values, MAXIMALLY simplify test that they are already in WHNF. current solution leads to two jumps, what is a very expensive on modern cpus. i propose to make instead one check and one conditional jump what will be much cheaper. then, if value is in WHNF, we just load all the needed data himself. if it is not in WHNF, we perform just the same operations as in current GHC. for example, wrapper that calls the "int fac(int n, int r)" worker, can be something like this: if (p = n->closure) then goto eval_n; n_evaluated: if (p = r->closure) then goto eval_r; r_evaluated: return fac (n->value, r->value); eval_n: (*p) (); // sets n->closure=NULL; n->value to n's value goto n_evaluated; eval_r: (*p) (); goto r_evaluated; JPB> If you want to use the same trick, you'll end up with the same JPB> problems (bad C). So, you'll want to eliminate thunks statically, JPB> finally requiring a 'high level' analysis as I suggested above. really? :) JPB> Also, allocation + garbage collection is extremely efficient in JPB> current GHC... C/C++ alloc doesn't even come close. It's entirely JPB> possible that with even a very fast backend, the better ghc allocator JPB> will be enough to swing the balance. (see jhc) JPB> It might be possible to re-use most of it however. i don't propose to replace everything in ghc backend, just the way "unboxed" code is compiled and something around it. i just don't know enough about other parts of ghc backend/rts :))) -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
