[mercury-users] Re: Determinism detection (Was Newbie problem.)

[Lee Naish]

In message <19990616122228.A29974 at hydra.cs.mu.oz.au>you write:
>On Wed, Jun 16, 1999 at 09:36:16AM EST, Richard A. O'Keefe wrote:
>> I also had in mind predicates as a replacement for patterns.
>> One of the serious weaknesses of Prolog, which Mercury has inherited,
>
>I remember talking about something like this with Fergus a long time ago
>(ie round 1994): doing switch detection after inlining, but that had the
>problem that inlining was optional, and making the correctness of you
>program depend on the optimization setting was a Bad Thing.

There are a few issues here.

There is a basic conflict between abstraction and determinism
detection: its nice to write code in an abstract way but compilers need
more specific information in order to recognise determinism.

Determinism detection is so important for efficiency that LP languages
typically sacrifice abstraction.  Inlining is the most obvious way to
get both efficiency and abstraction.   Typically it has been considered
just an optimisation rather than an important language design feature.
In Mercury, determinism detection is a very important part of the
language, so there are grounds for considering inlining (or other
mechanisms) more than just an optimisation.

As a bit of an aside, NUE-Prolog allowed functions to be defined using
== instead of =, to allow the programmer to specify the definitions
should be inlined.  Thus in NUE-Prolog you can write efficient yet
abstract code, for example:

nil == [].
cons(H, T) == H.T.

append(nil, As, As).
append(cons(A,As), ...

Some have suggested declarations to say certain things are mutually
exclusive.  Note that in general these things will have multiple
arguments, some output, so you need to be careful with quantifiers
(the examples given are simplistic in this respect).

Eg, using predicate notation append would be written something like

append(As, Bs, Cs) :-
	(	nil(As), ...
	;
		cons(B, Bs1, Bs), ...
	).

There are various issues to do with modules, and what determinism
information should be attached to.  One possibility, which works pretty
well in most cases I believe, is to attach it to types.  With the
abstract list example (and similar) its the most obvious place for it.
I think its also reasonable to attach exclusivity info about < and >= to
the types (as Richard pointed out, integers and floats have different
relationships between < and >=).  One place where this idea would fall
down is when you want to detect a switch on two variables of different
types:

detpred(X, Y, ...) :-
	(	case1(X,Y), ...
	;
		case2(X,Y), ...

I doubt this would occur much, and even if it did, the solution may be
to introduce a new abstract type containing both X and Y.

Back to exam marking...

	lee
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------