inside the GHC code generator

[Bulat Ziganshin]

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,
 Bulat                            mailto:Bulat.Ziganshin at gmail.com