• Efficiency of Cuts vs. Conditionals
• On lambda Prolog
• Mercury, (PDC) Prolog, Cuts and If-Then-Elses
• New Developments
• Occurs-Check in Prolog
• Pre-processor for "Functional Prolog"

X = 500, Y = 594
X = 484, Y = 610
X = 500, Y = 593
X = 469, Y = 610

count_down(-1) :- !.
count_down(N) :-
   M is N - 1,
   count_down(M).

if_count_down(N) :-
   (  N = -1
   -> true
   ;  M is N - 1,
      if_count_down(M)
   ).

p(Time) :-
   cpu_time(count_down(10000000),Time).

q(Time) :-
   cpu_time(if_count_down(10000000),Time).

cpu_time(Goal, Duration) :-
   statistics(runtime, [Start|_]),
   ( call(Goal) -> true ),
   statistics(runtime, [Finish|_]),
   Duration is Finish - Start.

the predicate '=/2' that you use here in the condition part is not one
of the predicates listed for this optimization of the manual.

so, if you replace = with == we'd expect an improvement. However, I just
tried it and it is even slower!

btw, I don't think the manual intends to suggest that in examples like
yours the version with conditional is faster. But I had expected both
versions to be equally fast. The manual says that certain types of
conditionals are compiled into fast code, but this optimization applies
both if the conditional is expressed using !, or using if-then-else.

So, in my understanding, your two versions are expected to be faster
than something like:

count_down2(N) :-
    (  minus_one(N)
    -> true
    ;  M is N - 1,
       count_down2(M)
    ).

minus_one(-1).

And indeed it is much slower. If you use the profiler, you can see that
this version leaves choice-points behind, whereas the other two versions don't.

Still, this doesn't explain why your first version is a little faster than
your second version. Perhaps the people at sics can comment..

Gertjan van Noord:
> the predicate '=/2' that you use here in the condition part is not one
> of the predicates listed for this optimization of the manual.
>
> so, if you replace = with == we'd expect an improvement. However, I just
> tried it and it is even slower!

Arithmetic equality is =:=/2. That might be faster.

Jens Kilian wrote:
> Arithmetic equality is =:=/2. That might be faster.

(it isn't in SICStus - I was just about to post when I saw Jens' posting ...)

I have here some more figures - I have also added another version with
an if-then-else (see below)

                        |SICStus|  Yap    |  GNU |   SWI |ECLiPSe| XSB
         ----------------------------------------------------------------------
             count_down2|  1520 | 1050    | 1220 | 11050 |  2080 | 1839
              count_down|   580 |  220(*) | 1160 |  8729 |   770 | 1220
           if_count_down|   600 | 1240    | 1150 | 11640 |  1560 | 1651
    better_if_count_down|   790 |  860    | 1740 | 11671 |  2190 |  479

(sorry, this looks a bit messy)

Timings in millisecs, all ran on the same machine - the installation
of these systems is not in my hands, but is usually done right.

The versions of the different systems:

% all the programs
% for ECLiPSe I used a pragma+query to switch off pessimization
% XSB misses statistics/2

% count_down2 as by Gert-Jan

count_down2(N) :-
        (  minus_one(N)
        -> true
        ;  M is N - 1,
            count_down2(M)
        ).

minus_one(-1).

% original without if

count_down(-1) :- ! . %%%%%%%%%%%
count_down(N) :-
        M is N - 1,
        count_down(M).

% original with if

if_count_down(N) :-
        (  N = -1    %%%%%%%%%%%
        -> true
        ;  M is N - 1,
           if_count_down(M)
        ).

% my "better" clause with if

better_if_count_down(N) :-
        (  N =< -1
        -> true
        ;  M is N - 1,
           better_if_count_down(M)
        ).

I consider the code in the lines marked %%%%%%%%%%% bad Prolog code:
take for instance the definition of count_down/1,
you can call it as

        count_down(10-1)

and that finishes but

        count_down(0-1)

does not finish. Or even nicer: try count_down([9]) and count_down([-1]) as goals :-)

Same for the N = -1 in if_count_down.

I think that if one is dealing with arithmetic, one should stick to
using the arithmetic built-ins. That's why I named the last version
better_if_count_down :-)

Most often, the appearance of =/2 in the condition of the
if-then-else, means that compilers generates code that pushes a
choicepoint - and do other checks after the unification is finished,
because of delay for instance.
Of course, if the unification is "simple" - like (N = -1) or (N = a) -
this can be optimized, but why bother if the user can write better
code, like (N =:= -1) or (N == a) which is usually what is meant.
And that's another reason (for me) to prefer the better_if_count_down:
it let's any reader of your program (including the compiler) know
what you meant, instead of merely what you wrote.

I do not dare to even start interpreting the figures, but it is a pity
that in most systems, the form which conveys most information to the
compiler, is not always the faster, and sometimes even much slower.

(*) reminds me of something Vitor Santos Costa (main author of Yap)
wrote a couple of years ago (not verbatim - I lost his e-mail):

when will we stop optimizing bad Prolog code
and focus on optimizing good code ?

ps. You can see the code SICStus generates by using:

?- prolog:fshell_files('a.pl',wam,fcompile('a.pl')).
the code will appear in a.wam
(this might be an undocumented feature, but long ago, it was on the
SICStus mailing list - what you find in a.wam is not exactly what
is executed, and even if it where, it would still leave many questions open)

Just for the fun of it (I know I should start optimising someday), I
wanted to know the effect of SWI-Prolog optimise flag. Without this
flag arithmetic is fully interpreted: A is B - 1 means push -(B,1)
onto the stack and call the foreign function is/2 which finds the term
-/2, calls is/2 on both arguments, calls minus and unifies the result.

Of course this is a bit slow. Optimised arithetic compiles arithmetic
expressions to a stack machine so A is B - 1 becomes

	Eval B and push
	push -1
	call minus
	unify result

The results are (seconds):

Non-optimised:

1 ?- run(1000000).
count_down(1000000)           0.89
count_down2(1000000)          1.15
if_count_down(1000000)        1.21
better_if_count_down(1000000) 1.23

optimised:

1 ?- run(1000000).
count_down(1000000)           0.44
count_down2(1000000)          0.68
if_count_down(1000000)        0.72
better_if_count_down(1000000) 0.60

So you see indeed that the better-if wins over `naive'-if if the
system cares looking at the data.

Now you may wonder why optimised compilation isn't the default. First
of all the debugger cannot trace the execution of compiled arithmetic
code, but more curious is that while optimising arithmetic shows quite
large speedups on arithmetic intensive predicates it shows hardly any
and even frequently a slowdown on many arbitrary programs. The
slowdown is interesting in itself. For sure the CPU always executes
fewer instructions but it actively uses a larger part of the virtual
machine emulator. Most likely reduced cache performance reduces the
overall performance.

Jesper Matthiesen wrote:
>I recently noticed something called Lambda-Prolog. Can anyone give a hint as
>to why one would want to use
>the lambda calculus with Prolog? I don't know much about the Lambda-calculus
>so this is a kind of newbie-question.

Church wrote a thesis in metamathematics (logic) by formalizing the
function constructs x |-> f used in mathematics, using the notation
(lambda x.f) (no spaces in print), therefore called "lambda calculus". A
computer language interpretation of a lambda calculus variation is called
a "functional language". You can ask more about it in the newsgroups
comp.lang.functional and comp.theory.

Examples of non-typed functional languages are LISP and Scheme; examples
of types ones are SML and Haskell (http://haskell.org).

Most computer languages are Turing complete, so formally they can do the
same algorithmic tasks, given enough computer time and memory. But from
the structural point of view, different computer languages are good at
different things. The best way to see what is to try them out.
c1\pard\lang2067\f0\fs20 Hans Aberg}

Jesper Matthiesen wrote:
> I recently noticed something called Lambda-Prolog. Can anyone give a hint as
> to why one would want to use
> the lambda calculus with Prolog? I don't know much about the Lambda-calculus
> so this is a kind of newbie-question.

Lambda-abstraction (the ability to create a term that
stands for a function on terms) is useful if you want to be able
to substitute one term for another frequently in your code. The
place where this is almost indispensible is when you are trying
to program a logic that has "there exists", "for all" and other
such constructs. It's extremely tedious (I know because I have
been obliged to do it several times :-)) to do this with regular
Prolog or with a functional programming language. It's much
easier and clearer with Lambda Prolog... once you learn the
language.

However, the issue is deeper than that. Lambda Prolog is
based on "higher order logic", which is more than just "logic
with lambda calculus". Higher order logic allows you to state
properties of data, properties of properties of data, properties
of properties of properties of data, etc. For "data" you can
substitute "functions", "predicates" or just about anything else
you want. Many people (myself included) believe that a higher
order logic programming system like Lambda Prolog is the most
logical choice for writing programs like theorem provers and
programming language interpreters.

The main barriers to learning Lambda Prolog, given a knowledge of Prolog,
are (1) there is (necessarily) a different syntax for predicate applications,
giving a different look to the language, and (2) there is (very necessarily)
a type system, and you have to give types to all constants, predicates, function
symbols, variables etc. I say "very necessarily" because without the types,
the logic would be inconsistent and you would be able to prove anything. (The
reason is related to the old Russell paradox, but that's another long story.)
Gopalan Nadathur and Dale Miller developed an implementation of Lambda Prolog
and wrote some of the early papers. They and other researchers, such as Amy
Felty, John Hannan, Frank Pfenning, Ray McDowell, Andrew Appel et al. have applied
these ideas to computational linguistics, theorem provers, syntax and operational
semantics of programming languages, proof-carrying code and so on. You might
be interested in checking out some of their papers. I believe the latest, greatest
version of an interpreter is Teyjus, developed by Gopalan Nadathur and his team.

Jamie Andrews wrote:
> However, the issue is deeper than that. Lambda Prolog is
>based on "higher order logic", which is more than just "logic
>with lambda calculus". Higher order logic allows you to state
>properties of data, properties of properties of data, properties
>of properties of properties of data, etc. For "data" you can
>substitute "functions", "predicates" or just about anything else
>you want. Many people (myself included) believe that a higher
>order logic programming system like Lambda Prolog is the most
>logical choice for writing programs like theorem provers and
>programming language interpreters.

I am myself working on a proof verification system, based on first order
metamathematics, whose approach is similar to that of Qu-Prolog:
http://www.svrc.it.uq.edu.au/pages/QuProlog_release.html
Earlier versions
http://svrc.it.uq.edu.au/Bibliography/svrc-tr.html?00-20
http://svrc.it.uq.edu.au/Bibliography/svrc-tr.html?00-21
Ergo
http://www.svrc.it.uq.edu.au/pages/Ergo_release.html

When taking this approach, one ends up implementing a "binder"
constructor: a binder causes a free object variables to become bound in
the expression.

Examples of binders are the quantifiers, but also the (lambda x.f) of the
lambda calculus. Such binders are otherwise quite frequent in math (for
example in summation symbols, differential calculus, and many other
similar constructs).

So even though this is a first order metamathematical theory, it
apparently contains what computer scientists call higher order logic. I do
not know exactly why this is so: A proper metamathematical approach does
not admit one to apply mathematical objects to metamathematical objects.
It could be that an untyped (i.e., with respect to metamathematical
typing) Lambda-Prolog does not have that restriction. But then one might
end up with metamathematical problems. It could also be that the word
"order" that computer scientists use does not here refer to the order of
the underlying metamathematical theory.

The reason that I decided to settle for a first order metamathematical
logic does not depend on any restrictions in the underlying runtime model,
but is merely a purely syntactic restriction: First order metamathematical
logic is most commonly described in the metamathematical literature, so
going beyond that seems to be an unneeded complication in a first
approach.

Markus Greim wrote:
>what is the real difference between mercury and the good old
>turbo/pdc ?

The design of Mercury was influenced by the design of Turbo Prolog,
and the design of more recent versions of PDC Prolog has clearly
been influenced by Mercury too. So there is quite a bit in common.
But there are certainly also a lot of differences.

Some of the major language differences are

- Mercury is a "pure" logic language, whereas Turbo/PDC/Visual
Prolog is not;

- Mercury has a much more flexible type system, with parametric polymorphism,
type classes, existential types, optional dynamic typing, etc.

There are also some implementation differences:

- Visual Prolog comes with a good GUI environment,
Mercury does not (although it does work well with
standard Unix tools, e.g. vim or emacs).

- Visual Prolog 6 runs on Win32 x86 machines only (excluding Win95),
whereas Mercury runs on a variety of architectures (e.g. x86, Alpha,
Sparc, PowerPC), operating systems (e.g. Windows, MacOS, Linux,
Solaris, *BSD), and platforms (e.g. native code and the .NET CLR).

And some other differences:

- Mercury is free software, and comes with source code, whereas
Visual Prolog costs money (except for a somewhat crippled edition for
private personal/education use only) and does not include source code.

>You have to define your "functions", flow patterns, as well as an
>determ/undeterm switch

Yes, the mode and determinism systems of the two languages are quite similar,
as is the support for functions.

>and both are based on the C language.

No, neither Mercury nor PDC Prolog are based on C, as far as I know.

>Ok, mercury has some more modern extensions, but the idea behind is
>not real different, isn't it?

There is one guiding principle behind the design of Mercury which is
very different than that of PDC Prolog or standard Prolog: taking
the idea of "logic programming" seriously. In PDC Prolog or standard
Prolog, it is very common to have to use non-logical features such as cut,
but in Mercury we provide alternatives for these features which do not
destroy the declarative logical semantics of the language.

Fergus Henderson wrote:
> The design of Mercury was influenced by the design of Turbo Prolog,
> and the design of more recent versions of PDC Prolog has clearly
> been influenced by Mercury too. So there is quite a bit in common.
> But there are certainly also a lot of differences.

I think there was also the issue that Turbo Prolog etc claims to *be*
Prolog, whereas Mercury more correctly claims to be another language in
the logic programming paradigm. The name "Prolog" ought to be restricted
to the particular language that was first given that name - typeless,
sequential, with depth-first backtracking search. It ought not to be used
to mean any language in the logic programming paradigm.

Fergus Henderson wrote:
> There is one guiding principle behind the design of Mercury which is
> very different than that of PDC Prolog or standard Prolog: taking
> the idea of "logic programming" seriously. In PDC Prolog or standard
> Prolog, it is very common to have to use non-logical features such as cut,
> but in Mercury we provide alternatives for these features which do not
> destroy the declarative logical semantics of the language.

Hmm - I would not make the CUT vs. if-then-else difference argument
for "taking logic programming more seriously", simply because code
expressed in terms of one construct can be easily emulated in terms of
the other. Moreover, as the semantics of PDC Prolog or Mercury's
type/mode system, as such, is not logic based, one could also argue
that both of them "take logic less seriously" than ISO Prolog, which,
at least, has it's core Horn Clause subset accurately specified solely
through logical means.

Paul Tarau wrote:
>Hmm - I would not make the CUT vs. if-then-else difference argument
>for "taking logic programming more seriously", simply because code
>expressed in terms of one construct can be easily emulated in terms of
>the other.

1. Cut was just one example. Perhaps not the best example, but I
picked it because it is well known. There are lots of other examples.
Do you want me to list some of them?

2. If-then-else is not the only alternative to cut. Often cut is used in
Prolog to express what in Mercury is achieved automatically via
smarter indexing or automatic pruning, or by using committed choice
nondeterminism. You would, I hope, surely agree that using these
features of Mercury constitutes "taking the idea of logic programming
more seriously" than instead littering one's programs with cuts?

3. See Bart's comment about Mercury's if-then-else corresponding to if/3
in SICStus, not Prolog if-then-else.

4. Even if we restrict the discussion to just cut versus if-then-else,
and we ignore point 3, then yes, Mercury's sound if-then-else does
take the idea of logic programming more seriously. The reason is that
the logical semantics of if-then-else is independent of the modes,
whereas the logical semantics for predicates defined with cut is
mode-dependent. So you can't talk about the semantics for a predicate
involving cut without knowing which mode(s) it will be called in,
and furthermore the semantics may be different for different modes!

This is not just an academic argument, it has very serious real
practical consequences: code written using cut often fails to be
"steadfast" (see [1]). That is, such code can give wrong answers
if you call predicates with their arguments more instantiated than
expected.

>Moreover, as the semantics of PDC Prolog or Mercury's
>type/mode system, as such, is not logic based,

The semantics of Mercury's type system is certainly based on logic.
The meaning of (typed) Mercury programs is defined in terms of typed
predicate calculus, with Mercury types mapping directly to types in the
typed predicate calculus.

Mercury's mode system is intended to express operational, rather than
declarative, properties of programs. So as such it is not really
intended to be logic based. Nevertheless, many mode and determinism
declarations in Mercury do have a meaning in the declarative semantics,
and this can be directly expressed in logic, as explained in the
"Semantics" chapter of the Mercury language reference manual.

But perhaps you were wondering whether the rules for the type system
and mode system where themselves defined in logic. The answer to that
is yes, because they are implemented in Mercury! Because Mercury has a
simple declarative semantics, the Mercury definitions of the type checker
and mode checker can be regarded as themselves being statements in logic
(cf. "Typing Haskell in Haskell" [7]). Of course these are very complex
definitions, and are too implementation oriented to constitute a good
specification. But there has also been published work providing more
succinct formal definitions of both (the main parts of) the Mercury type
system [2,5] and, more recently, the Mercury mode system [6].

>one could also argue
>that both of them "take logic less seriously" than ISO Prolog, which,
>at least, has it's core Horn Clause subset accurately specified solely
>through logical means.

There is a tiny bit of truth in this. However, taken alone, it is IMHO
highly misleading. The semantics of Prolog's "Horn Clause" subset is
*nothing like* the semantics of Horn clauses in logic.

Although the Mercury language reference manual only describes the
translation of Mercury to logic in English, and does not include any
_formal_ definition of the semantics, it would be wrong to conclude
that no such semantics exists. In fact, there has been quite a bit of
work on this, which has led to a published formal declarative semantics
for (a substantial subset of) Mercury. See [3,4].

References

[1] Richard O'Keefe, "The Craft of Prolog." MIT Press, 1990.
See in particular pages 95-96, which discusses steadfastness.

[2] Dante Baldan, Baudouin Le Charlier, Christophe Leclere, Isabelle Pollet,
"Abstract Syntax and Typing Rules for Mercury."
Technical Report RR-98-001, Namur, 1998.
http://www.info.fundp.ac.be/cgi-publi/pub-spec-report?RR-98-002.

[3] Dante Baldan, Baudouin Le Charlier.
"A Declarative Semantics for Mercury Program Construction."
Technical Report RR-98-002, Namur, 1998.
http://www.info.fundp.ac.be/cgi-publi/pub-spec-report?RR-98-001.

[4] Dante Baldan, Baudouin Le Charlier, Christophe Leclère, Isabelle Pollet,
"A Step Towards a Methodology for Mercury Program Construction:
A Declarative Semantics for Mercury." In proceedings of LOPSTR'98,
LNCS, 1998. http://citeseer.nj.nec.com/baldan98step.html.

[5] David Jeffery, "Expressive type systems for logic programming languages."
Ph.D. thesis, Department of Computer Science and Software Engineering,
The University of Melbourne, February 2002.

[6] David Overton's Ph.D. thesis. Submitted, 2003.

[7] Mark Jones, "Typing Haskell in Haskell."
In Haskell Workshop, September 1999.
http://citeseer.nj.nec.com/jones99typing.html.

Paul Tarau wrote:
> Hmm - I would not make the CUT vs. if-then-else difference argument
> for "taking logic programming more seriously", simply because code
> expressed in terms of one construct can be easily emulated in terms of
> the other.

The semantics of the syntactic construct with -> ; in Mercury, is like
the semantics of if/3 in SICStus and it is not easily emulated in terms
of the ordinary Prolog cut.
Unless Paul knows of a new trick - I would not be surprised. Please tell us !

> Moreover, as the semantics of PDC Prolog or Mercury's
> type/mode system, as such, is not logic based,

As for types, I always thought it was logic based.
As for modes, I incline to your view, as the specification of correct
modes is very execution oriented.
So can you please explain your statement as far as types is concerned - focus
on Mercury please.

> one could also argue
> that both of them "take logic less seriously" than ISO Prolog, which,
> at least, has it's core Horn Clause subset accurately specified solely
> through logical means.

Are you referring to the formal specification in the ISO document ?
I would agree it adheres to some logic, but whether it is more than
a denotational semantics disguised in a logic syntax, I am not sure.
lots of other examples.
Do you want me to list some of them?

2. If-then-else is not the only alternative to cut. Often cut is used in
Prolog to express what in Mercury is achieved automatically via
smarter indexing or automatic pruning, or by using committed choice
nondeterminism. You would, I hope, surely agree that using these
features of Mercury constitutes "taking the idea of logic programming
more seriously" than instead littering one's programs with cuts?

3. See Bart's comment about Mercury's if-then-else corresponding to if/3
in SICStus, not Prolog if-then-else.

4. Even if we restrict the discussion to just cut versus if-then-else,
and we ignore point 3, then yes, Mercury's sound if-then-else does
take the idea of logic programming more seriously. The reason is that
the logical semantics of if-then-else is independent of the modes,
whereas the logical semantics for pred

Bart Demoen wrote:
> The semantics of the syntactic construct with -> ; in Mercury, is like
> the semantics of if/3 in SICStus and it is not easily emulated in terms
> of the ordinary Prolog cut.
> Unless Paul knows of a new trick - I would not be surprised. Please tell us !

Ok - here are 2 old tricks from 1999 (I will call the primitive
if_any/3 because if/3 conflicts with plain if-then-else in some
Prologs). You can search for "Tarau if_any" on Google groups for full
context - or you might skip to the new trick which follows them, if in
a rush!

The 2 old tricks use plain if-then-else which we all know how to
emulate in terms of CUT.

Under the assumption that "Cond" has a finite number of solutions:

if_any(Cond,Then,Else):-
  findall(Cond,Cond,Cs),
  ( Cs=[]->Else
  ; member(Cond,Cs),
    Then    
  ).

The most efficent one, using a fairly mild side effect, localized to a
heap term (see BinProlog 2004 and whatever BIM-Prolog has become) is:

if_any(Cond,Then,Else):-
  Ctr=s(0),
  ( Cond,change_arg(1,Ctr,1),Then
  ; arg(1,Ctr,0),Else
  ).

And here is the NEW trick, assuming that you have first order engines,
from Jinni 2004:

if_any(Cond,Then,Else):-
  new_engine(Cond,Cond,Engine),
  get(Engine,Answer),
  select_then_or_else(Answer,Engine,Cond,Then,Else).

select_then_or_else(no,_,_,_,Else):-Else.
select_then_or_else(the(BoundCond),Engine,Cond,Then,_):-
  backtrack_over_then(BoundCond,Engine,Cond,Then).

backtrack_over_then(Cond,_,Cond,Then):-Then.
backtrack_over_then(_,Engine,Cond,Then):-
  get(Engine,the(NewBoundCond)),
  backtrack_over_then(NewBoundCond,Engine,Cond,Then).

Well, there's no CUT or a "more logical" if-then-else in this one:-)

Paul Tarau wrote:

> Ok - here are 2 old tricks from 1999 (I will call the primitive
> if_any/3 because if/3 conflicts with plain if-then-else in some
> Prologs). You can search for "Tarau if_any" on Google groups for full
> context - or you might skip to the new trick which follows them, if in
> a rush!
>
[... then follow 3 tricks]

Nice tricks, but none of these 3 tricks is doing what Paul mentioned,
which was: emulate code expressed in terms of one construct (cut or if/3)
in terms of the other construct.

BTW, I think that the last two tricks suffer from not cleaning up ASAP
after the last solution of the condition.

Bart Demoen wrote:
> Nice tricks, but none of these 3 tricks is doing what Paul mentioned,
> which was: emulate code expressed in terms of one construct (cut or if/3)
> in terms of the other construct.

The third one does the backtracking "if-the-else" with NO reference to
CUT. I think that does not weaken the claim as such. Or, if you think
otherwise, you can add a CUT and comment it out :-)

The deeper issue here is that it can be no magic about metalogical
properties involving the number of solutions to a Cond goal, as it is
the case in "if_any(Cond,Then,Else)"! If you want to KNOW how many
solutions "Cond" has before deciding to call "Else", you will need a
strong enough reflection layer that is able to control their
enumeration. Conventional Prolog and Mercury's procedural tricks (CUT
and if-then-else) are really not up to the task to express reasoning
about the number of solutions to a query - and they have not really
been designed for that. My best guess is that SICStus, SWI and Mercury
will implement their flavor of "backtracking if-then-else" as
procedural primitives at emulator level rather than at source level
(but I would be more than delighted to be proven wrong on this:-))

> BTW, I think that the last two tricks suffer from not cleaning up ASAP
> after the last solution of the condition.

Agreed, but if you waited 1000 "Cond" steps to get there, you could
wait one more... Or else (assuming "Cond" has a finite number of
solutions!), I would just use trick 1, which also implicitely "garbage
collects" the computation performed by "Cond".

Paul Tarau wrote:
> The third one does the backtracking "if-the-else" with NO reference to
> CUT. I think that does not weaken the claim as such.

It does.
Paul is once more dodging the issue: the third trick references another
engine and that other engine seems to implement if/3 and that other
engine is either using a trick involving the !/0 construct which can
be - according to you - used easily to emulate the if/3, or it does
not ...
Relying on an infinite chain of engines which all dodge the
question is probably exactly what Paul would like to present to us,
but that does not solve the issue.

I know it is common practice these days - especially in the OO
approach to programming - to delegate issues instead of facing them,
but the question stands: can Paul show us how one can easily emulate
if/3 using ! ? That's what Paul claimed.

> The deeper issue here is that it can be no magic about metalogical
> properties involving the number of solutions to a Cond goal, as it is
> the case in "if_any(Cond,Then,Else)"! If you want to KNOW how many
> solutions "Cond" has before deciding to call "Else", you will need a
> strong enough reflection layer that is able to control their
> enumeration.

There is a big truth in here: there is no magic, not even about using
another engine. And cut can't do it.
Moreover, if/3 doesn't need to know HOW MANY solutions "Cond" has
before deciding [whether] to call "Else", it just needs to know there
is one.

> Conventional Prolog and Mercury's procedural tricks (CUT
> and if-then-else) are really not up to the task to express reasoning
> about the number of solutions to a query - and they have not really
> been designed for that.

if/3 is up to the task of deciding to do something (the Then) if the
number of solutions is at least one - even repeatedly. At no point did
anyone refer to "number of solutions". BTW, the interface to your new
engines (as far as you showed to us) does not allow to reason about
the NUMBER of solutions either - see later.

> My best guess is that SICStus, SWI and Mercury
> will implement their flavor of "backtracking if-then-else" as
> procedural primitives at emulator level rather than at source level
> (but I would be more than delighted to be proven wrong on this:-))

AFAIK SICStus does not implement if/3 (not "their flavor of
"backtracking if-then-else" - it is THE flavor :-) at the source level
(if you mean source level as in "pure ISO Prolog" level) - simply
because it is impossible. Same for SWI. Mercury usually doesn't come
with an emulator, but mutatis mutandis all applies here: Mercury has
no source level implementation of if/3 (Fergus, correct me if I err !)

And of course you would be delighted to be proven wrong on this,
because than your chances for showing that you can easily emulate if/3
with !/0 are increasing - but until then, your claim remains unprovem
right ?

> > BTW, I think that the last two tricks suffer from not cleaning up ASAP
> > after the last solution of the condition.
>
> Agreed, but if you waited 1000 "Cond" steps to get there, you could
> wait one more...

You miss the point. Just take the predicate:

        tailif(G) :- if(G,G,G), tailif(G).

Call it as ?- tailif(true).

if your definition of if/3 makes this query run out of (whatever)
stack, your definition is flawed (wrt clean-up). [I think an
implementation is already in trouble if it needs garbage collection on
this query, but it is better than giving up completely]

> Or else (assuming "Cond" has a finite number of
> solutions!), I would just use trick 1, which also implicitely "garbage
> collects" the computation performed by "Cond".

The trap you fall in, is however the same as the one described in
"Common Subexpressions are Uncommon in Lazy Functional Languages"
by Olaf Chitil: you keep alive for a long time data that you don't
need until much later, and that you should not compute until much
later.

I still want to add something about the trick with the new engine:
it should return

        no - if no solution to the query exists (it does for you)
        the(Sol,N,More) whenever it delivers a solution, where
                Sol is the solution
                N is the ordinal number of the solution
                More is unified with
                        no - if for sure this was the last solution
                        perhaps_more - if the engine cannot prove this
                                        is the last solution

Only then would you have "a strong enough reflection layer that is
able to control their [=set of solution] enumeration". And it would
help solving the clean up problem your engine solution has right now
as well.

Paul Tarau wrote:
>The third one does the backtracking "if-the-else" with NO reference to
>CUT. I think that does not weaken the claim as such. Or, if you think
>otherwise, you can add a CUT and comment it out :-)

The third one is attempting to emulate backtracking "if-then-else" using
a completely different feature, first-class engines. As I mentioned in
my previous post, the attempt fails, since it doesn't properly preserve
the operational semantics, losing important properties such as tail recursion.
But even if it had succeeded, I don't really see the point; neither
standard Prolog nor (AFAIK) PDC Prolog have first-class engines, so this
attempted emulation seems pretty irrelevant to any comparison between
those languages and Mercury.

Paul Tarau wrote:
>Under the assumption that "Cond" has a finite number of solutions:
>
>if_any(Cond,Then,Else):-
> findall(Cond,Cond,Cs),
> ( Cs=[]->Else
> ; member(Cond,Cs),
> Then
> ).

That has a different operational semantics. For example, if Cond has O(N)
solutions which take O(M) space each, this will use O(M * N) space.

>The most efficent one, using a fairly mild side effect, localized to a
>heap term (see BinProlog 2004 and whatever BIM-Prolog has become) is:
>
>if_any(Cond,Then,Else):-
> Ctr=s(0),
> ( Cond,change_arg(1,Ctr,1),Then
> ; arg(1,Ctr,0),Else
> ).

That one too has a different operational semantics. It won't garbage
collect the terms reachable from the "Else" clause during the execution
of the "Then" clause.

>And here is the NEW trick, assuming that you have first order engines,
>from Jinni 2004 (you can try it out online here:
>
>http://www.binnetcorp.com/download/jinnidemo/DemoGUIApplet.html )
>
>if_any(Cond,Then,Else):-
> new_engine(Cond,Cond,Engine),
> get(Engine,Answer),
> select_then_or_else(Answer,Engine,Cond,Then,Else).
>
>select_then_or_else(no,_,_,_,Else):-Else.
>select_then_or_else(the(BoundCond),Engine,Cond,Then,_):-
> backtrack_over_then(BoundCond,Engine,Cond,Then).
>
>backtrack_over_then(Cond,_,Cond,Then):-Then.
>backtrack_over_then(_,Engine,Cond,Then):-
> get(Engine,the(NewBoundCond)),
> backtrack_over_then(NewBoundCond,Engine,Cond,Then).

As Bart said, that one will leave an unnecessary choice point around
after the last solution of "Cond".

In addition, I'm pretty sure that this version is going to prevent
proper tail recursion optimization for recursive calls in the "Then"
or "Else" parts.

Bart Demoen wrote:
> Paul Tarau wrote:
> > The third [trick] does the backtracking "if-the-else" with NO reference to
> > CUT. I think that does not weaken the claim as such.
>
> It does.
> Paul is once more dodging the issue: the third trick references another
> engine and that other engine seems to implement if/3 and that other
> engine is either using a trick involving the !/0 construct which can
> be - according to you - used easily to emulate the if/3, or it does
> not ...
> Relying on an infinite chain of engines which all dodge the
> question is probably exactly what Paul would like to present to us,
> but that does not solve the issue.

I was relying on exactly ONE extra engine in the code I've shown! The
dialog with the parent engine, which recurses/backtracks over the
answers in pure Horn clause syntax implements if/3 with no need for
if-the-else or CUT.

> I know it is common practice these days - especially in the OO
> approach to programming - to delegate issues instead of facing them,
> but the question stands: can Paul show us how one can easily emulate
> if/3 using ! ? That's what Paul claimed.

Hmm, I would talk to an online Eliza (like the one written in
Mercury!) about how bad delegation really behaves in OO programming!
And not forget to mention the chains (of engines) :-)

Seriously, if you have the engine constructs, you do NOT need cuts at
source level to emulate if-the-else, negation, findall, SICStus-style
if/3 etc. Plain Horn clause syntax (with the added engine API) does
it! My CL2000 paper (or the open source Kernel Prolog implementation
at

http://www.binnetcorp.com/OpenCode/kernelprolog.html )

have details on how all that works).

> > Conventional Prolog and Mercury's procedural tricks (CUT
> > and if-then-else) are really not up to the task to express reasoning
> > about the number of solutions to a query - and they have not really
> > been designed for that.
>
> if/3 is up to the task of deciding to do something (the Then) if the
> number of solutions is at least one - even repeatedly. At no point did
> anyone refer to "number of solutions". BTW, the interface to your new
> engines (as far as you showed to us) does not allow to reason about
> the NUMBER of solutions either - see later.

You need to locate a program execution point between the end of the
computation of the first solution and the beginning of the computation
of the second one to be able to trim Else from the choicepoint before
it is too late. BTW, this is a fairly arcane optimization which I
would not include in the operational semantics of if/3 (see more later
on that).

> > > BTW, I think that the last two tricks suffer from not cleaning up ASAP
> > > after the last solution of the condition.
> >
> > Agreed, but if you waited 1000 "Cond" steps to get there, you could
> > wait one more...
>
> You miss the point. Just take the predicate:
>
> tailif(G) :- if(G,G,G), tailif(G).
>
> Call it as ?- tailif(true).
> if your definition of if/3 makes this query run out of (whatever)
> stack, your definition is flawed (wrt clean-up). [I think an
> implementation is already in trouble if it needs garbage collection on
> this query, but it is better than giving up completely]

This is a nice example, but unfortunately it has the same computed
answers (none!) as the goal tailif(G):-tailif(G), which passes all the
tests :-) Would you really wait until the goal terminates:-), instead
of getting an Out of Memory error?

> > Or else (assuming "Cond" has a finite number of
> > solutions!), I would just use trick 1, which also implicitely "garbage
> > collects" the computation performed by "Cond".
>
> The trap you fall in, is however the same as the one described in
> "Common Subexpressions are Uncommon in Lazy Functional Languages"
> by Olaf Chitil: you keep alive for a long time data that you don't
> need until much later, and that you should not compute until much
> later.

Again, if Cond uses more space to compute each of its answers than the
list of the answers, then the findall-based solution (posted as "trick
1") turns out to be more space efficient, given that findall trims the
space used to perform the computations. I would not advocate always
beeing eager to be lazy :-)

> I still want to add something about the trick with the new engine:
> it should return
>
> no - if no solution to the query exists (it does for you)
> the(Sol,N,More) whenever it delivers a solution, where
> Sol is the solution
> N is the ordinal number of the solution
> More is unified with
> no - if for sure this was the last solution
> perhaps_more - if the engine cannot prove this
> is the last solution
>
> Only then would you have "a strong enough reflection layer that is
> able to control their [=set of solution] enumeration". And it would
> help solving the clean up problem your engine solution has right now
> as well.

You can make an engine which computes a solution ahead and only gives
it to you one step later, to implement something like this at source
level, but keeping the engine API simple had more weight in the design
than accomodating choicepoint trimming - the engine interface is just
a plain "Iterator pattern".

However, I agree with you that a stronger reflection mechanism needs
to be added to the engine API. Jinni 2004 has now a return/1 operation
allowing you to return to the parent at any time - from where the
parent can resume its execution by simply asking for new answers.
This, together with a mechanism to feed a running engine with new
goals at a given program point, allows a dialog with the parent
engine, that seems quite important for people using of Jinni as an
agent programming language.

Paul Tarau wrote:
>You can make an engine which computes a solution ahead and only gives
>it to you one step later, to implement something like this at source
>level,

If Cond has side effects, that wouldn't preserve the operational
semantics. Any side effects in Cond would occur too early.

Paul Tarau wrote:
> I was relying on exactly ONE extra engine in the code I've shown! The
> dialog with the parent engine, which recurses/backtracks over the
> answers in pure Horn clause syntax implements if/3 with no need for
> if-the-else or CUT.
[...]
> Seriously, if you have the engine constructs, you do NOT need cuts at
> source level to emulate if-the-else, negation, findall, SICStus-style
> if/3 etc.

Paul, please backtrack a bit: NOBODY has ever claimed that one NEEDS
cuts at the source level to emulate if-then-else etc.
Only YOU wrote in the beginning:

> I would not make the CUT vs. if-then-else difference argument
> for "taking logic programming more seriously", simply because code
> expressed in terms of one construct can be easily emulated in terms of
> the other.

[the if-then-else you referred to in this sentence was the Mercury one]

So, we are still at square one: please show us how to use cut for
emulating if/3. Until now, you have shown how to emulate if/3 with
findall, with non-backtrackable destructive assignment and with a new
engine which itself implements if/3 one way or the other. All very
cunning, so cunning you can put a tail in it and call it a weasel, but
not at all what you hinted at initially.

> > tailif(G) :- if(G,G,G), tailif(G).
> >
>
> This is a nice example, but unfortunately it has the same computed
> answers (none!) as the goal tailif(G):-tailif(G), which passes all the
> tests :-) Would you really wait until the goal terminates:-), instead
> of getting an Out of Memory error?

It is easy to ridicule an artificial example that shows clearly the
problem. Unfortunately, it happens all too often that reasonable
programs run out of memory because the implementation does not behave
reasonably. And the test whether the implementation is the culprit is
most easily exposed by artificial examples, so that one cannot dodge
the responsability.

So, once more, can we get back to your original statement ?
Or shall we save band-width and conclude you have no emulation of
Mercury if-then-else in terms if cut ?

Bart Demoen wrote:
> So, once more, can we get back to your original statement ?
> Or shall we save band-width and conclude you have no emulation of
> Mercury if-then-else in terms if cut ?

Ok, this is my last say on this, we have indeed more useful things to
do than counting how many angels can sit on top of a ...
choicepoint:-) Anyway, here is an example for if_any/3 which uses CUTs
and runs your tailif/1 example forever:

if_any(Cond,Then,Else):-
  findall(Cond,Cond,Cs),
  ( Cs=[],!,Else
  ; Cs=[Cond],!,Then
  ; member(Cond,Cs),Then
  ).

As the example shows, if_any/3 (with backtracking on Cond) can do, at
source level, the choice-point trimming. Still, the main point I was
trying to make is that the practical expressivness of if_any/3 is
about the same as what you can do with basic Prolog goodies and
therefore it is not relevant for supporting the claim that Mercury
"takes logic more seriously" than Prolog.

	% Documentation of predicate foo/3.
	% ...
	% Note that (i) is somewhat redundant. It does some
	% preparation steps, speeding up (ii). 
	foo(X,S0,S) :-
	   bar(...),			(!),
	   ...,
	   baz(...),			(!,!).

If I remember correctly, long ago, Siemens Prolog did always unify with
occurs check, and those people claimed that it was not killing them
(Klaus Daessler, Christian Pichler, anyone from those days ???)

I know for sure that IBM Prolog did occurs check - implemented by
Marc Gillet - handcoded assembler. He used the double pointer trick
(I think - or a variant of it). IBM Prolog was very fast.

Of course, you can make artificial examples that will kill the Prolog system
performance wise when every unify is done with occurs check, but that
is inherent in the occurs check problem.
But in practice, it does not seem a big problem.
A little analysis of the program (you cited Sondergaard) can often avoid
many occurs checks as well, and make the problem less.

One more alternative (for a LP language designer) is to make the language
such that compile time checks make it impossible to construct cyclic
terms, and then of course you don't need occurs check at all :-)

I guess you are right, but i was particolary interested in a study on
the decision to exclude a occurs check from prolog(the reasons of this
choice supported by some surveys).
I found something about an article written by Plaisted in the
_Proceedings of the 1984 International Symposium on Logic
Programming,and another one by K. Marriott and H. Sondergaard, called
something like "the occur check problem in prolog", but i can't find
this articles, or menage to download them.

feffo wrote:
> So i wondered, is it possible that noone ever thought to carry on such
> a research or at least made an attempt?!how did they decided then, not
> to use this test at all and leave prolog unsound?

As a tangential response to your query, there is nothing necessarily
unsound about Prolog without occurs check: equations like X=f(X) have
unique solutions in the domain of rational trees.

(You'll find an old discussion of this in the Google archives for
comp.lang.prolog.)

For those who are interested and are not aware of the history.

You are right that Siemens Prolog and IF/Prolog have a very
efficient implementation of the unify_with_occurs_check/2
predicate. This is because IF/Prolog 5.0 is the original
Siemens Prolog 3.1 kernel. The IF/Prolog V4.1 kernel was
replaced with the ISO standard Siemens kernel as a major version
release.

Since 1994 when IF/Prolog 5.0 was released, all subsequent IF/Prolog
versions use this kernel. This also brought us the C/VC++ implementation
of finite domain constraints and performance improvments and
better debugging and compiler tracing, etc.

Since then development has concentrated more on interfaces and
improvements to the constraints. IF/Prolog now has an excellent
Windows version and Java interfaces...

Bart Demoen wrote:
> Of course, you can make artificial examples that will kill the Prolog system
> performance wise when every unify is done with occurs check, but that
> is inherent in the occurs check problem.
> But in practice, it does not seem a big problem.
> A little analysis of the program (you cited Sondergaard) can often avoid
> many occurs checks as well, and make the problem less.

Unifying without occurs check makes also some programs smaller and
faster. For exampl, interpreters for procedural languages where the
interpreted program is kept in a data structure and jumps are stored
by having a Prolog variable bound to the corresponding section of the
program.