Path: utzoo!attcan!uunet!lll-winken!lll-tis!helios.ee.lbl.gov!pasteur!ucbvax!ji.Berkeley.EDU!vanroy
From: vanroy@ji.Berkeley.EDU (Peter Van Roy)
Newsgroups: comp.lang.prolog
Subject: A question on semantics and program transformation
Message-ID: <26045@ucbvax.BERKELEY.EDU>
Date: 11 Sep 88 17:31:20 GMT
Sender: usenet@ucbvax.BERKELEY.EDU
Reply-To: vanroy@ji.Berkeley.EDU (Peter Van Roy)
Organization: University of California, Berkeley
Lines: 28

Is it allowable for a program transformation to change the
procedural semantics of a program while retaining the
declarative semantics?

For example, consider the predicate defined by the following two clauses:

	:-mode(max(input,input,output)).
	max(A, B, A) :- A>=B.
	max(A, B, B) :- A=<B.

This is a declaratively correct specification of the maximum relation,
and it gives two solutions when A=B.
Is a program transformation allowed to change these clauses into:

	max(A, B, A) :- A=:=B.
	max(A, B, A) :- A>B.
	max(A, B, B) :- A<B.

or into:

	max(A, B, A) :- A>=B, !.
	max(A, B, B) :- A=<B.

The transformed versions are declaratively equivalent to the original
specification, and they give only one solution when A=B.
Has a discussion of this question been published anywhere?

Peter Van Roy
vanroy@ji.Berkeley.edu