Hi,
I accidentally stumbled over a neat programming trick which I want to
share with other Oz users.
I'm not sure whether my explaination of /why/ the trick works is
correct, if its not, I surely would
like to hear what's wrong with it.
Inspired by the CTM Wiki page "99 problems in other languages:Oz"
(http://codepoetics.com/wiki/index.php?title=Topics:99_Problems_in_other_languages:Oz
)
I've been converting a number of prolog sample programs (originating
from http://kti.mff.cuni.cz/~bartak/prolog/combinatorics.html) into Oz
as an
exercise using the guidelines described in CTM section 9.7.3
"Translating
Prolog into a relational program".
Because these sample programs are written in pure prolog, the
guidelines make that
conversion effortless, but the resulting translation less elegantly
expresses the
program than the original prolog clauses.
Let me illustrate it by means of a contrived example, using relational
style:
(* In prolog: *)
fact(0,1).
fact(1,1).
fact(N,F) :- N>1, N1 is N-1, fact(N1, FN), F is N*FN.
Using the CTM guidelines, these clauses translate into Oz:
(note the use of the deterministic choice by the if-statement)
proc {Fact N F}
if N==0 then F=1
elseif N==1 then F=1
elseif N>1 then
FN in
{Fact N-1 FN}
F = N*FN
else
fail
end
end
% The next line just demonstrates the computation of 6! :
{ExploreOne proc{$ F} {Fact 6 F} end}
It is obvious that the lay-out and relatively large amount of text
of the Oz translation leaves something to be desired. It would have
been nice to be able to write:
proc {Fact N F}
choice
N==0 F=1
[] N==1 then F=1
[] FN in
N > 1
{Fact N-1 FN}
F = N*FN
end
end
The textual structure of this procedure is less cluttered and follows
the structure or the original prolog clauses closely. Moreover the use
of
the choice-statement keeps its semantics close the prolog-semantics of
its original.
But 'N==0', 'N==1' and 'N>1' are expressions and the Oz compiler will
complain and tell you it doesn't accept expression where it expects
statements.
Don't ask me why I tried it, but I did. I used the FD constraint
propagators instead
of the expressions; that is, "N>:1" instead of "N>1" and so on:
proc {Fact N F}
choice
N=:0 F=1
[] N=:1 F=1
[] FN in
N >: 1
{Fact N-1 FN}
F = N*FN
end
end
% And find the answer by using, e.g.
{Browse {Seach.base.one proc{$ F} {Fact 6 F} end}.1 }
At first I was suprised that this even would work, it seemed something
like magic.
One would expect constraint propagators to need a constraint store and
all other required CSP trappings.
But if you think a little bit further, I think, it is an obvious
(side) effect.
All constraint propagators must either return 'entailed', 'sleep', or
'failed'
(See the "constraint extension tutorial" ) to the current computation
space.
In case of a fail, the computation space failes and the search engine
explores the next choice points (See also Christian Schulte's
excellent "Programming
Constraint Services"). Since we use the same search engine for CSP as
well
as well to explore the choice points in {Fact}, the comparison
constraint propagators, we can expect the same behaviour.
I'm sure that the trick costs some performance, but who can resist
such elegance, moreover it
is a beautiful example of Oz's orthogonality.
Best regards,
/Twan
_________________________________________________________________________________
mozart-users mailing list
[email protected]
http://www.mozart-oz.org/mailman/listinfo/mozart-users
