[clean-list] Trivial Algebraic Data Types...

Martin Wierich martinw@cs.kun.nl
Fri, 10 Nov 2000 11:43:58 +0100


Hi Fabien

Fabien Todescato wrote:
> 
> Dear Cleaners,
> 
> Let us assume I have the following algebraic data type :: STM s x = STM \ s
> -> ( s , x ) with a single unary constructor.
> 
> Does the compiler optimize away such a constructor so that at run-time the
> values of STM s x are not encapsulated within some "STM box", or are the
> values encapsulated within a "STM box" ?
> 
> Differently said, do we suffer some run-time penalty when using :: STM s x =
> STM \ s -> ( s , x ) instead of :: STM s x :== \ s -> ( s , x ), when
> possible ?

The compiler does not optimize such a box away if you use algebraic types. But
the compiler can unbox records, tuples and basic types. This happens when such
an object is passed as a strict argument to a function or if such an object is
returned in a strict position by a function. So if you define

  :: STM s x = { stm :: s -> (s, x) } 

  f :: !(STM a b) -> b

then calling f will unbox the record. In the following application

  g = f { stm = my_function }

no record will be allocated. The same holds for tuples. This has advantages and
disadvantages.

Advantage:
Take a look at this:

  :: Record = { field1 :: !Int, field2 :: !Int }

  h :: !Record -> (!Int, !Record)
  h record=:{field1}
     = (field1, { record & field1 = field1+1 })

h will allocate nothing in the heap! In fact the two fields are passed to h.
This pays especially for recursive functions. It is great if you use a lot of
record updates.

Disadvantage:
You could loose sharing:

  polymorph_identity :: !.a -> .a
  polymorph_identity x = x

  unbox_identity :: !Record -> Record   // with the upper Record type
  unbox_identity x = x
  
  Start = polymorph_identity 
            (unbox_identity (polymorph_identity { field1=0, field2 = 1 }))

Note that the argument of polymorph_identity is not unboxed because it is
polymorph! So the argument for the inner polymorph_identity call is put in a box
(all in all three words in the heap). For the call of unbox_identity this box is
unboxed: The two fields will be pushed on the B-stack and they will be returned
that way. Now a _second_ box is created for that record to form the argument of
the outer polymorph_identity call (again three words of heap memory).

Here are the rules:
- records, tuples & basic types can be unboxed.
- therefore they have to be in a unboxable position:
  Being in an unboxable position is lost for lazy arguments and record fields
  that are records themselves. Polymorph things can never be unboxed
  (exception: tuple arguments). Examples:
  
    :: Rec1 = { f11 :: Int, f12 :: !Rec2 }
    :: Rec2 = { f21 :: !Int, f22 :: !Int }

    :: Alg a = C1 !a | C2 Rec1 | C3 !Rec1 | C4 !(!Rec2, !(!Rec2, !Int))

    myRec = { f11=11, f12 = {f21=21, f22=22}}

  (C1 myRec) contains a pointer to a Rec1 object. The f11 field is not unboxed
  (because it is lazy) so it is a pointer to an integer box. The f12 field is
  not unboxed (see above, it's a record in a record) and so it is a pointer
  to a Rec2 field. Both fields of this Rec2 object are unboxed (no pointers).

  (C2 myRec) contains a pointer to a Rec1 object, because the argument is lazy.

  In (C3 myRec) the Rec1 object is unboxed so the C3 object has one pointer
  to an Int box (for f11) and one pointer to a Rec2 (for f12).

  C4 demonstrates that unboxing for tuples is nestedly applied. A C4 object
  contains no pointers, just 5 integers.

  The same rules that apply for constructor arguments also apply for function
  arguments and the function result.

  Note that for functions the strictness analyzer could find an argument to be
  strict, even if you havn't specified is as strict.

I hope I got it all right (I don't know where to look the rules up).

cheers
  Martin Wierich
  University of Nijmegen


P.S.: If you don't want to let the compiler unbox your record, then put it in a
box yourself:

  :: myBox a = { box :: a }

P.P.S: Wasn't the idea of declarative programming that one doesn't have to take
care about all these details?