Strict tuples

[Bulat Ziganshin]

Hello Simon,

Monday, March 20, 2006, 1:47:52 PM, you wrote:

>> i've proposed to allow adding strict mark to any type constructors and
>> type constructor parameters so that finally we can define any data
>> structure that can be defined in strict languages. in particular:
>> 
>> type StrictPair a b = !(,) a b
>> type StrictElements a b = (,) !a !b
>> type StrictBoth a b = !(,) !a !b
>> type StrictFunction a b = !(->) !a !b
>> 
>> strictMap :: StrictFunction a b -> ![!a] -> ![!b]
>> 
>> where ![!a] is a strict list with strict elements

SM> Bulat, this doesn't constitute a proposal.  It leaves too many questions
SM> unanswered.  If it is supposed to be just syntactic sugar, and I believe
SM> that is your intention, then can you show me how the above definitions
SM> translate into Haskell 98?  

i'm not sure that i can make complete proposal, but i can say what i
mean in more details:

one of the differences between Haskell and most other languages is what
even when we don't need laziness we are forced to "buy" it. so i want to
see the language where laziness is optional at any place.

shebang patterns allow to specify that concrete IMPLEMENTATION of some
function is strict in its using of parameters. but this can't help us
if we want to carry strict function in data structure, pass it as
function argument, has is as a class member. i was bitten by this
when i wrote Streams library - although Char encoding transformers are
simple strict computations that just read several bytes and then return
one Char, and byte reading operation by itself is very fast - they
cannot be combined to fast Char-reading function.

another problem is what while we can specify strictness of fields in
ADTs, we cannot "redefine" strictness of fields in existing ADT, such
as list.

my solutions to these problems:

1) make a strictness annotation part of function type declaration,
i.e. when function type can include strictness annotation on each of
its arguments and on result:

fac :: !Int -> !Int -> !Int

strictness annotation on argument means that function is strict in
this argument - if its value diverges then entire function diverges.
informally, strict argument can be evaluated before evaluation of
function body, as in the strict languages - what opens up possibility
to unbox such values and to omit checking of argument evaluation in
function body, moving this evaluation to the caller side

strictness annotation on result means that function DON'T DIVERGE if
all arguments are don't diverge. this allows to unbox result and to
skip checking that result was evaluated on callee side by moving real
computation inside the function. informally, this means that a
function is inexpensive enough and therefore can be computed non-lazily


2) to allow "changing" of strictness inside existing ADTs, i propose
to "copy" strictness annotations on type arguments to the type
declaration bodies:

data List a = Nil | Cons (List a) a
type StrictElements a = List !a

is equal to the:

data StrictElements a = Nil | Cons (List a) !a

i.e. it's the same list but each element is strict. using strictness
annotation on type constructor itself should mean strictifying of all
other (non-type-variable) fields:

type StrictList a = !List a
=>
data StrictList a = !Nil | !Cons !(List a) a

of course, i don't mean introducing new incompatible types - that is a
compiler responsibility (sorry, Simon :) ) to convert between variants
of types with different strictness. That we should fix at the language
definition level is what on strict types te user don't expects lazy
evaluation of list/it's elements and compiler is free to use program
transformations what non-lazily computes these data. for example, if
putStr function accepts strict list, then it can be implemented
without "evaluated?" checks on each step and the callers would ensure
that all strings passed to this function are fully evaluated

these two changes together should make it possible to implement
strictly strict algorithms in Haskell

-- 
Best regards,
 Bulat                            mailto:Bulat.Ziganshin at gmail.com