No subject

Fergus Henderson fjh at cs.mu.oz.au
Sun Nov 30 16:06:17 AEDT 1997


Return-Path: <henkv at idefix.cs.kuleuven.ac.be>
Received: from idefix.cs.kuleuven.ac.be by mulga.cs.mu.OZ.AU with SMTP (5.83--+1.3.1+0.51)
	id AA11796; Thu, 27 Nov 1997 23:19:19 +1100 (from henkv at idefix.cs.kuleuven.ac.be)
Received: from sneeuw.cs.kuleuven.ac.be (root at sneeuw.cs.kuleuven.ac.be [134.58.45.45])
	by idefix.cs.kuleuven.ac.be (8.8.6/8.8.6) with ESMTP id NAA09953
	for <mercury-users at cs.mu.OZ.AU>; Thu, 27 Nov 1997 13:19:15 +0100 (MET)
Received: from sneeuw (henkv at localhost [127.0.0.1])
	by sneeuw.cs.kuleuven.ac.be (8.8.5/8.8.5) with SMTP id NAA00363
	for <mercury-users at cs.mu.OZ.AU>; Thu, 27 Nov 1997 13:19:13 +0100
Sender: henkv at cs.kuleuven.ac.be
Message-Id: <347D653F.4760AD7A at cs.kuleuven.ac.be>
Date: Thu, 27 Nov 1997 13:19:11 +0100
From: Henk Vandecasteele <henkv at cs.kuleuven.ac.be>
X-Mailer: Mozilla 3.04Gold (X11; I; Linux 2.0.30 i586)
Mime-Version: 1.0
To: mercury-users at cs.mu.oz.au
Subject: Re: [mercury-users] Circular lists
References: <199711271118.WAA05133 at goanna.cs.rmit.edu.au>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Status: RO
Content-Length: 2007
Lines: 49

Richard A. O'Keefe wrote:
> 
>         So what happens if you get stuck with an application Mercury
>         does not give you the speed you need, and I am speaking of orders
>         of magnitude!
> 
> Show me one where (decimal) orders of magnitude are involved.
> (Binary orders of magnitude can easily show up in C with the
> same code compiled by different compilers.)
The application: A finite domain CLP solver.
In such a case a domain must be maintained for each finite 
domain variable, also a list of constraints, to be actived when 
a domain changes, must be maintained. During the search choices are made
and as a consequence of the choices the set of constraints and the 
domains change. On backtracking these changes have to undone.

Mercury before 0.7.2 could only offer a data-stucture with 
logarithmic access to the domains of variables and the constraints
connected to the variables, logarithmic in terms of the number of
finite domain-variables. 
For such an application you want constant access in time.
But maybe worse, an update of the data-stucture will consume
memory proportional to the log(number of variables)* mean number 
of constraints per variables.

As the number of finite domain variables can be quite large, 
you can image the execution time will orders of (decimal) magnitudes
larger in such a pure implementation. This has been proven by
experiments.


> If you want dangerous things to happen quietly,
> if you don't want to make INFORMED choices about safety,

If I use the C-interface to implement things which cannot be done
efficiently in Mercury then probably it will be dirty. If such a 
checker would be added it will always generate warnings. 
So I won't look at it and probably find it annoying.
Of course this is only one application of the C-interface, in other
cases it could be usefull.

> if you assume that speed and safety cannot be had together,

not always I guess. But hopefully in most cases.

> then we have nothing to say to each other.

Henk




More information about the users mailing list