Newbie: common Syntax error: Operator expected

classic Classic list List threaded Threaded
29 messages Options
12
Reply | Threaded
Open this post in threaded view
|

Re: Newbie: common Syntax error: Operator expected

Jan Wielemaker-3
On Wed, 2009-10-28 at 22:25 +0100, Bart Demoen wrote:

> > Given a call min(X, Y, Z), it is not possible for both clauses to
> >      succeed.  But Prolog doesn't know that.  (I _think_ XSB Prolog
> >      does or did know that; I know there was one Prolog that was smart
> >      enough to notice complementary goals.)
>
> hProlog is smart enough, if you write the clauses as
>
>        min(X, Y, Z) :- X =< Y, X = Z.
>        min(X, Y, Z) :- Y < X, Y = Z.
>
> But there is nothing "smart" about it, just a couple of 100s of LOC to
> implement some obvious source to source transformations.
>
> If we could supply such a module that can be plugged into the compiler
> without any further work for Jan, I bet he would use it. Anyone
> interested to work on this ?

Sure.  It fits with other source-to-source translation (when optimizing)
provided by library(apply_macros).  Richard did claim one issue though:
the issue of clause-by-clause or predicate-as-a-whole compilation.  In
particular when loading large fact bases (such as WordNet), you don't
want predicate-as-a-whole compilation.

Actually, it is doubtful whether you want to spent precious loading time
to the few things you are likely to improve.

Given the fact that SWI-Prolog is capable of decompiling all static
code, such optimizations can be done *after* the initial compilation.
One advantage is that you then already know the number of clauses
(which is available through predicate_property/2).  Ideally, I think
such optimizations should be realized after `hot-spot' analysis.

In this particular case, this is a bit of a challenge.  The flaw with
this predicate is not that it is implemented inefficiently (time-wise),
but that it leaves an unneeded choicepoint.  Is there a way to do this
lazily?

I could imagine that if the system runs out of local stack
(environment/choice stack), the system examines the choicepoints and
does source-code analysis to find dummy ones.  Next, it should be able
to reclaim the local space (not yet possible, but I see no good reason
why this cannot be done).  In the final step, it could rewrite the
predicates creating these choicepoints to avoid this in the future.

Another trigger can be choice-points in childs that are deleted due
to -> or !.

Note that both these things may not only allow you to improve code on
the fly, but also to give hints to the programmer on places where the
system is uncertain whether introducing a cut would really be `green'.

The advantages of such an approach are big: no slow-down of the compiler
and you do these optimizations only in those places where it really
matters.  If you need to do the optimization you have full access to all
source code of the program and you can even collect usage statistics.

     Cheers --- Jan

_______________________________________________
SWI-Prolog mailing list
[hidden email]
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog
Reply | Threaded
Open this post in threaded view
|

Re: Newbie: common Syntax error: Operator expected

Bart Demoen-2

> the issue of clause-by-clause or predicate-as-a-whole compilation

It is an issue, but not one to be ducked by saying that one should
rule out predicate-as-a-whole compilation.

> when loading large fact bases (such as WordNet), you don't
> want predicate-as-a-whole compilation.

Sure, but predicate-as-a-whole compilation has the advantage to kick
in only after all clauses (or facts) for a given predicate have been
seen, so one can still make a predicate by predicate decision on
whether to do something predicate-as-a-whole.

> Actually, it is doubtful whether you want to spent precious loading
> time to the few things you are likely to improve.

I'd rather spend a little (really veeeery little) loading time to
doing some "smart" things that save enormous time later. And you can
combine it with giving advice to the application programmer.
Runtime optimizations slow down another phase in the development
cycle, and you might discover late a performance problem, because it
was not covered by your test runs. I am not against doing hot-spot JIT
or whatever remedy at runtime, but why not let the compiler have a
shot at it first ?

Moreover, I think this small addition to the loader/compiler is more
likely to ever be actually incorporated in SWI than much more drastic
surgery to the runtime for achieving almost the same effect in many
cases.

If you feel like one would not want to spend some loading time to it,
make it dependant on a flag.


> SWI-Prolog is capable of decompiling all static code

The static code that hProlog generates for the following three
versions of min/3 is identical:

min1(X,Y,Z) :- X < Y, Z = X.
min1(X,Y,Z) :- X >= Y, Z = Y.

min2(X,Y,Z) :- X < Y, !, Z = X.
min2(X,Y,Z) :- Z = Y.

min3(X,Y,Z) :- (X < Y -> Z = X ; Z = Y).

and looks like

307304 test_smaller A1 A2 label: 307316
307312 gettval_proceed A1 A3
307316 gettval_proceed A2 A3

[the numbers are code addresses]

In BIM-Prolog, we stopped decompilation of the abstract machine code
when it became difficult to support because of optimizations.

Is there a way to print out in SWI the abstract machine code for a predicate ?
I have a print_code/1 builtin - very useful to me :-)

Cheers

Bart Demoen

Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm
_______________________________________________
SWI-Prolog mailing list
[hidden email]
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog
Reply | Threaded
Open this post in threaded view
|

Re: Newbie: common Syntax error: Operator expected

Jan Wielemaker-3
On Thu, 2009-10-29 at 11:11 +0100, Bart Demoen wrote:

> > the issue of clause-by-clause or predicate-as-a-whole compilation
>
> It is an issue, but not one to be ducked by saying that one should
> rule out predicate-as-a-whole compilation.
>
> > when loading large fact bases (such as WordNet), you don't
> > want predicate-as-a-whole compilation.
>
> Sure, but predicate-as-a-whole compilation has the advantage to kick
> in only after all clauses (or facts) for a given predicate have been
> seen, so one can still make a predicate by predicate decision on
> whether to do something predicate-as-a-whole.

How do you see the integration?  The current compile loop is (very much
simplified): repeat, read_term, assert, term == end_of_file, !.

Reading an entire predicate as a list of terms before processing it
seems a bad choice (can run out of stack, but surely wastes a lot
of stack).  In theory, we could have a hook that is called whenever
a predicate is `finished' (the code keeps track of a `current', so
it can warn about discontiguous code).  On the other hand, there
seems to be little point doing that.  One can just as well do the entire
job after loading the file (you can hack that by term_expanding
end_of_file, but I propose we add a better hook if we go that way).

You can of course also do the job simply on the loaded program as
a secondary step.  Everything is around, including file and line
info on a per-clause basis.

> > Actually, it is doubtful whether you want to spent precious loading
> > time to the few things you are likely to improve.
>
> I'd rather spend a little (really veeeery little) loading time to
> doing some "smart" things that save enormous time later. And you can
> combine it with giving advice to the application programmer.
> Runtime optimizations slow down another phase in the development
> cycle, and you might discover late a performance problem, because it
> was not covered by your test runs. I am not against doing hot-spot JIT
> or whatever remedy at runtime, but why not let the compiler have a
> shot at it first ?

Not so sure this is very little, but I'd be happy to stand corrected.
If we go the decompilation/recompilation route, you can simply write
a predicate optimise/0 and we can see how long it takes on big programs.

> Moreover, I think this small addition to the loader/compiler is more
> likely to ever be actually incorporated in SWI than much more drastic
> surgery to the runtime for achieving almost the same effect in many
> cases.

True.  And in all cases you need the same source-to-source translator.
Optimizing arithmetic by simplifying expressions and some (basic)
inlining would also be great.  It allows to write more readable and
more reusable code without paying a price.

> If you feel like one would not want to spend some loading time to it,
> make it dependant on a flag.

There is already -O for that.  (current_prolog_flag(optimise, X))

> > SWI-Prolog is capable of decompiling all static code
>
> The static code that hProlog generates for the following three
> versions of min/3 is identical:
>
> min1(X,Y,Z) :- X < Y, Z = X.
> min1(X,Y,Z) :- X >= Y, Z = Y.
>
> min2(X,Y,Z) :- X < Y, !, Z = X.
> min2(X,Y,Z) :- Z = Y.
>
> min3(X,Y,Z) :- (X < Y -> Z = X ; Z = Y).
>
> and looks like
>
> 307304 test_smaller A1 A2 label: 307316
> 307312 gettval_proceed A1 A3
> 307316 gettval_proceed A2 A3
>
> [the numbers are code addresses]

I guess the route is that all are compiled to the last form and
the compiler must turn that into sensible code.

> In BIM-Prolog, we stopped decompilation of the abstract machine code
> when it became difficult to support because of optimizations.
>
> Is there a way to print out in SWI the abstract machine code for a predicate ?
> I have a print_code/1 builtin - very useful to me :-)

?- [user].
|: min3(X,Y,Z) :- (X < Y -> Z = X ; Z = Y).
|: % user://1 compiled 0.00 sec, 688 bytes
true.

2 ?- vm_list(min3).
========================================================================
min3/3
========================================================================
   0 s_virgin
   1 i_exit
----------------------------------------
clause 1 (371528):
----------------------------------------
   0 i_enter
   1 c_ifthenelse(3, 11)
   4 b_var0
   5 b_var1
   6 i_call((<)/2)
   8 c_cut(3)
  10 b_unify_vv(2, 0)
  13 c_jmp(3)
  15 b_unify_vv(2, 1)
  18 i_exit
true.

3 ?-

A little explanation.  The first bit is the `supervisor' and deals with
dynamic indexing.  Before calling it is s_virgin.  The first call
replaces this:

?- min3(2,3,X).
X = 2.

5 ?- vm_list(min3).
========================================================================
min3/3
========================================================================
   0 s_trustme(clause(371528))
----------------------------------------

S_VIRGIN is already capable of calling Prolog for dealing with
autoloading, which provides another option for handling this.

Ideally, I would like to keep the original clauses and have a secondary
clause-list that contains the optimised version (or at least, have that
as an option).

As a footnote, most of this infrastructure is intended to deal with
JIT-like things in the future.   Little has been realised as I tend
to get trapped in providing functionality and stability ...

Its not hard to see some possible optimizations here, in particular
dealing with deterministic side-effect-free tests in if-then-else :-)
Before doing so, I'd like to extend the declarative description of
the VM instructions such that the code-walker in GC does not need
to know about these things.

     Cheers --- Jan


_______________________________________________
SWI-Prolog mailing list
[hidden email]
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog
Reply | Threaded
Open this post in threaded view
|

Re: Newbie: common Syntax error: Operator expected

Ceyhun Ciper
In reply to this post by Bart Demoen-2
The first one of you two who will have modeled this (\+ uninteresting) discussion in Prolog will have proven his point in indubitable (prolog-)terms.
 
Regards,
Ciper

On Thu, Oct 29, 2009 at 8:19 AM, Bart Demoen <[hidden email]> wrote:

> That's rather like saying "This knife is not sharp, it's just very
> good at cutting things."

Sharpness is a property of knives.
Smartness is not a property of Prolog.


> Does hProlog still insert the implicit cut when the predicate
> is declared to be dynamic?

hProlog has no dynamic predicates.

Cheers

Bart Demoen

Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm
_______________________________________________
SWI-Prolog mailing list
[hidden email]
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog

Reply | Threaded
Open this post in threaded view
|

Re: Newbie: common Syntax error: Operator expected

Eckard Brauer-3
In reply to this post by Richard A. O'Keefe
Am Thu, 29 Oct 2009 10:02:25 +1300
schrieb "Richard O'Keefe" <[hidden email]>:

> (2) Given a call min(X, Y, Z), it is not possible for both clauses to
>      succeed.  But Prolog doesn't know that.  (I _think_ XSB Prolog
>      does or did know that; I know there was one Prolog that was smart
>      enough to notice complementary goals.)  So it is necessary to use
>      a "green" cut.  Once again, the output unifications should be
>      done afterwards.
>
> min(X, Y, Z) :- X =< Y, !, Z = X.
> min(X, Y, Z) :- X >  Y, !, Z = Y.

That (from a very outside view on the possible semantics) leads to the
following questions:

- What exactly could this mean when one takes in account that variables
  may be constrined (state of a variable may be ternary: free, bound,
  constrained/semi-free; I already mentioned that the relational
  operators are a bit different for constraints)?

- What ordering relation will be choosen in which case (think of
  possible non-trivial integral values, strings, records)?

- Should a system be able to recognize inversion of ordering relations
  (see > and =< above; maybe that's leading to your "knive's sharpness"
  later on the thread)?



--
Buffer overflow in BundTroj.exe: Can't send KeyLog. Exiting.

signature.asc (205 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Newbie: common Syntax error: Operator expected

Bart Demoen-2
In reply to this post by Jan Wielemaker-3

> If we go the decompilation/recompilation route, you can simply write
> a predicate optimise/0 and we can see how long it takes on big programs.

Now we are talking :-)
I prefer optimise/2: in the first argument, I'd like to specify which
predicate to optimize; in the second argument perhaps some options
that one would like to provide (I can name some, but maybe not yet
now). optimise/0 can be build on top of that.

The possibility to deliver an optimized application end product might
also influence the above choices ?

> 2 ?- vm_list(min3).

Relatively recent apparently - not yet in 5.6.64, but present in 5.7.14.
Thanks !

Bart Demoen

Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm
_______________________________________________
SWI-Prolog mailing list
[hidden email]
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog
Reply | Threaded
Open this post in threaded view
|

Source optimization (was: Re: Newbie: common Syntax error: Operator expected)

Jan Wielemaker-3
On Thu, 2009-10-29 at 16:58 +0100, Bart Demoen wrote:
> > If we go the decompilation/recompilation route, you can simply write
> > a predicate optimise/0 and we can see how long it takes on big programs.
>
> Now we are talking :-)
> I prefer optimise/2: in the first argument, I'd like to specify which
> predicate to optimize; in the second argument perhaps some options
> that one would like to provide (I can name some, but maybe not yet
> now). optimise/0 can be build on top of that.

I guess you need various interfaces, the bottom line of which is
a predicate that takes a list of clauses and returns a new list
of clauses.   Here is the idea to do it:

========== opt.pl ===========
:- module(optimize,
          [ optimize_predicate/1
          ]).

:- meta_predicate
        optimize_predicate(:).

optimize_predicate(Module:Name/Arity) :-
        functor(Head, Name, Arity),
        findall((Head :- Body), clause(Module:Head, Body), Clauses),
        (   optimize_clauses(Clauses, Optimized),
            \+ Clauses =@= Optimized
        ->  abolish(Module:Name/Arity),
            forall(member(C, Optimized),
                   assert(Module:C)),
            compile_predicates([Module:Name/Arity])
        ;   true
        ).

optimize_clauses([( min(X,Y,Z) :- X =< Y, Z=X ),
                  ( min(X,Y,Z) :- X  > Y, Z=Y )
                 ],
                 [( min(X,Y,Z) :- X =< Y -> Z=X ; Z=Y)
                 ]).

=== min.pl ===
:- module(min,
          [ min/3
          ]).


min(X,Y,Z) :- X =< Y, Z=X.
min(X,Y,Z) :- X  > Y, Z=Y.


=== Running it ===

pl

1 ?- [opt,min].
% opt compiled into optimize 0.00 sec, 3,872 bytes
% min compiled into min 0.00 sec, 1,480 bytes
true.

2 ?- listing(min/3).
min:min(A, B, C) :-
        A=<B,
        C=A.
min:min(A, B, C) :-
        A>B,
        C=B.

true.

3 ?- optimize_predicate(min:min/3).
true.

4 ?- listing(min/3).
min:min(A, B, C) :-
        (   A=<B
        ->  C=A
        ;   C=B
        ).

true.

[ compile_predicates makes the predicate static again ]

> The possibility to deliver an optimized application end product might
> also influence the above choices ?
>
> > 2 ?- vm_list(min3).
>
> Relatively recent apparently - not yet in 5.6.64, but present in 5.7.14.

It was called differently in old version (and worked very different as
well).  The current releases are 5.8.0 and 5.9.0 (well, the binaries are
still called 5.7.15; they will become 5.9.0 if the stack-shifter is
sufficiently stable).

        Cheers --- Jan


_______________________________________________
SWI-Prolog mailing list
[hidden email]
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog
Reply | Threaded
Open this post in threaded view
|

Re: Newbie: common Syntax error: Operator expected

Richard A. O'Keefe
In reply to this post by Bart Demoen-2

On Oct 29, 2009, at 7:19 PM, Bart Demoen wrote:

>
>> That's rather like saying "This knife is not sharp, it's just very
>> good at cutting things."
>
> Sharpness is a property of knives.
> Smartness is not a property of Prolog.

Prolog is a language.  I was talking about *implementations*.
And via a perfectly standard everyday metaphoric transfer,
smartness *is* a property of Prolog *implementations*.
Some of them.


_______________________________________________
SWI-Prolog mailing list
[hidden email]
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog
Reply | Threaded
Open this post in threaded view
|

Re: Newbie: common Syntax error: Operator expected

Richard A. O'Keefe
In reply to this post by Bart Demoen-2

On Oct 29, 2009, at 11:11 PM, Bart Demoen wrote:

>
>> the issue of clause-by-clause or predicate-as-a-whole compilation
>
> It is an issue, but not one to be ducked by saying that one should
> rule out predicate-as-a-whole compilation.

Indeed.  My point was that dynamic and static predicates might well
benefit from different strategies.

Back in 1984, before I joined Quintus, I designed a Prolog system
for Xerox.  It never got implemented, because Quintus Prolog was
clearly better.  One of the strategies for that was going to be to
keep predicates in a semi-compiled form until their first call,
and then on the next change you'd revert to the semi-compiled form.
(Existing calls would continue to run the compiled version, so the
"logical" implementation of data base updates would follow
automatically.)  This is almost the strategy that Jan outlined.

>> when loading large fact bases (such as WordNet), you don't
>> want predicate-as-a-whole compilation.
>
> Sure, but predicate-as-a-whole compilation has the advantage to kick
> in only after all clauses (or facts) for a given predicate have been
> seen, so one can still make a predicate by predicate decision on
> whether to do something predicate-as-a-whole.

I believe Mercury has special support for predicates whose clauses
are all ground unit clauses.

Another issue, of course, is size.  Making *predicates* faster
doesn't always make *programs* faster.  Again back in the 80s,
threaded code was slower (per predicate) than native code, but
in the absence of type and mode declarations or inference,
native code was so much bigger that threaded *systems* often
ran faster.  Nowadays, of course, we have much bigger memories,
but we also have bigger programs and much more data to process.

This leads me to suspect that attention paid to reducing data
requirements is likely to pay off.  Since we are discussing a
particular improvement that makes plain readable code create
fewer choice points, this is one that _is_ likely to save worthwhile
amounts of data space at run time.
>
>

> In BIM-Prolog, we stopped decompilation of the abstract machine code
> when it became difficult to support because of optimizations.

As I recall it, decompilation was originally one of the features of
the Clocksin/Byrd "ZIP" system, and one that was eventually abandoned.


_______________________________________________
SWI-Prolog mailing list
[hidden email]
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog
12