[mercury-users] Beginner questions

[Fergus Henderson]

On 15-Mar-1999, Sandy Harris <sandy.harris at sympatico.ca> wrote:
> 1):
> I've done no logic or functional programming at all. I'm
> basically a C hacker, though I've had enough Scheme exposure
> to have some understanding of backtracking, higher-order
> functions, tail recursion, . . . Looking at your docs, I
> feel a moderately urgent need to read an introductory
> book on logic programming. There's a fair number of places
> where you seem to asume the reader knows some basics, or
> even is fairly familar with Prolog.

If you haven't already had a look at it, Ralph Becket's Mercury tutorial
(which we recently added to the Mercury WWW pages) is a good place to start.

> Can anyone recommend a book? A web site? 

I quite like "The Art of Prolog" by Sterling and Shapiro.
>From memory, the first 100 pages or thereabouts discuss logic programming
in a language-independent way, so they are equally applicable to Mercury.

But I'd appreciate hearing other people's suggestions on this.

> 2):
> From the Reference manual section on Double Negation:
> 
> | after syntax analysis, and before mode analysis is performed,
> | the implementation must delete any double negations and must
> | replace any negations of conjunctions of negations with
> | disjunctions.
> 
> Why don't you also replace negations of disjunctions of
> negations with conjunctions? I think, using C notation with
> & | ~ for AND OR NOT, we have two DeMorgan rules:
> 
> 	~(~a & ~b) = a | b
>  	~(~a | ~b) = a & b
>
> Why is one a requirement & not the other? Is it just that you
> don't generate the second so you don't worry about it?

That is a good question.  For complicated reasons, it turns out
that with our current implementation, the second is a lot easier
to implement than the latter; also if you handle both of these,
then you really ought to handle more complicated combinations too.
So the short answer is that this would

 | (1) complicate the language a little, and
 | (2) require a fairly significant change to the current implementation,
 | 
 | and given that we have not yet come across any real-world examples
 | that would require the more complicated rules, I think we should
 | leave things as is, at least unless and until someone demonstrates
 | a real need for it.

For a longer answer, see my June 1998 mail to the mercury-developers mailing
list <http://www.cs.mu.oz.au/research/mercury/mailing-lists/mercury-developers/mercury-developers.9806/0209.html>.
(But be sure to read the rest of the thread too, because I made some
mistakes in that post, which Lee Naish pointed out in his followup,
and it took us several posts to converge...)

P.S.
If I recall correctly, "DeMorgan's rules" are actually slightly simpler:

 	~(a & b) = ~a | ~b
  	~(a | b) = ~a & ~b

Or does the term "DeMorgan's rule" have a more generic meaning?
Anyway, we use the rule ~(~a & ~b) = a | b rather than DeMorgan's
rule ~(a & b) = ~a | ~b because using DeMorgan's rule would not
preserve mode correctness.

> 3):
> My main application for Mercury would be as a tool for trying
> to break ciphers. Write a program that takes a set of known
> plaintext/ciphertext pairs encrypted under the same key, and
> outputs the key.
> 
> This is clearly possible in principle, but the cipher designers
> work hard to make it difficult in practice. The general form of
> the problem is the NP-complete Boolean satisfaction problem,
> but I'll be dealing only with specific finite-sized instances.

Hmm... what kind of algorithm are you thinking of using?

> Is there are data available on how Mercury's resource demands
> vary with problem size? I need to determine if my project is
> utterly silly before I invest too much effort.

Well, the resource demands will depend entirely on what kind of
algorithm you are using.  Logic programming isn't a silver bullet.
If you code up a brute-force search of an exponential search space,
then this will take exponential time.

But for any given algorithm, you should be able to implement that
algorithm in Mercury with efficiency that is competetive with C.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"
PGP: finger fjh at 128.250.37.3        |     -- the last words of T. S. Garp.