[mercury-users] some [T] ...

[Fergus Henderson]

On 18-Nov-2002, Ralph Becket <rafe at cs.mu.OZ.AU> wrote:
> Michael Day, Monday, 18 November 2002:
> > 
> > [Fergus wrote:]
> > > Values of
> > > type foo are represented by a pointer to a cell containing two words. The
> > > first word is the "typeclass_info" pointer,  which records information
> > > about the `foo(T)' instance, including the type_info for T and function
> > > pointers for each of the methods of foo(T).  The second word is the
> > > value of type T.  It is not necessarily a pointer.
> > 
> > So the typeclass_info would point to a structure that is shared between
> > all values of foo that have the same type T?
> 
> These structures may be constructed at run-time

Right.  But the Mercury compiler will construct these values statically
when it can.  If the instance declaration which is being used is
`:- instance foo(t)' for some non-polymorphic ground type `t', then the
type class info for that instance declaration can be constructed
statically, and will be shared between all uses of that instance
declaration in the program.  However, if the instance declaration which
is being used is `:- instance foo(pt(T))' for some polymorphic type
`pt(T)', and `T' is not known statically at the point where the instance
declaration is used, then the type class info must be constructed
dynamically.

If you are using typeclasses as an alternative to passing around
higher-order procedures directly, then your type class instances will only
use ground types, and the Mercury compiler should be able to construct
all the type class infos statically.  It should also be able to construct
the values of your typeclass-constrained existentially quantified type
(`foo') statically.  So I think the overhead will only be a few extra
dereferences.

> > > Another alternative is to pass around a func -- if the function has mode
> > > func(in, in, ...) = out then in recent (ROTD) versions of Mercury you
> > > can just use mode `in' or `out'.
> > 
> > Sadly, I need to thrash the io state with this thing :)
> > 
> > The function-considered-ground feature really seems like a bandaid applied
> > to a sucking chest wound when it comes to making data structures
> > containing higher order stuff.
> 
> It was a pragmatic decision.  It allows one do write traditional
> functional programs, largely without having to worry about modes.
> 
> The new sub-typing scheme being worked on by Mark Brown may make
> even that special case go away, although it's not clear to me
> whether it'll handle uniqueness or not.

When you pass around higher-order values, as Michael Day wants to do,
and hence need to use higher-order modes, there are two issues that arise.
The first one is that the mode declarations for your procedures become a
bit more complicated.  This is not a major problem, but it can be somewhat
tedious.  The sub-typing proposal would provide a solution to this problem.

The second and more serious issue is that values of sub-types can't be
easily stored in and retrieved from the container types provided by
the standard library, since the standard library routines for creating
and accessing container types are not polymorphically moded.  The Mercury
compiler now supports polymorphic modes, so this issue could be solved
by changing the standard library to use polymorphic modes.  However,
we have not yet done so, mainly because we have observed that doing so
would significantly increase compilation time for programs that use the
affected parts of the standard library (i.e. almost all programs).

However, the use of existentially quantified typeclass-constrained types
as an alternative to passing higher-order values around directly solves
both of these problems, and I believe it should have only a minor impact
on efficiency compared to passing around higher-order values.  This is
IMHO a fairly elegant approach whose efficiency should be acceptable
for most uses.

The one area in which there might be a major efficiency impact is that
currently I think our optimizer probably does a better job of optimizing
away higher-order code (i.e. converting it into first order code) than
it does of optimizing away the use of typeclasses.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
The University of Melbourne         |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.
--------------------------------------------------------------------------
mercury-users mailing list
post:  mercury-users at cs.mu.oz.au
administrative address: owner-mercury-users at cs.mu.oz.au
unsubscribe: Address: mercury-users-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-users-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------