But, if you look at the source code you’ll find it doesn’t select clauses based on the argument, so from a technical point there is no reason for one argument order or another. Only if you have multiple clauses you would like the selection to be based on the first argument. That is (I think) the reason to put input arguments before output arguments. In these days another motivation for argument placement is the use by call/N and through call/N by maplist/N and related high order predicates.
1 Like
ok. thank you.
Yes, usage of closure suggests ordering from most general to most specific argument, so that higher level functions can do their thing …
but, it also means that first index selection is most general …
but, i guess, if there aren’t many goal predicates involved then this doesn’t matter much.
Dan
In my code, using rdet expansion (which is essentially an inline version of once/1) resulted in about 2x slowdown.
I haven’t looked into the reason for the slowdown (because my use of rdet is only for debugging) but my guess is that last-call optimisation is inhibited in some places. (My code is supposed to be mostly deterministic; if it had a lot of choice points that were eliminated by rdet expansion (or use of once/1), I would expect a speedup … but I would also be suspicious of that code having some bugs in it.)
Some of my code has 3 or 4 accumulators and it’s very tedious to thread all of these through the code. I use the EDCG package to do all the tedious bookkeeping for me (EDCG also allows me to have custom accumulators; for example in some cases I use dicts instead of lists).
1 Like
thank you.
Its a bit counter intuitive – isn’t it …
last call optimization, at least in theory, should only be related sub-goal and argument ordering in recursive calls. How would “out of call” cuts interfere …
Dan
This looks really useful. What would it take to port to SWI-Prolog?
thanks.
Now sure why, but i wasnt so far able to get my head around DCG use – i would need to practice it a bit and could perhaps then understand how EDCG can help me go farther …
I think i am mostly concerned in my code right now that performance issues are not bottleneck based anymore but somehow equally distributed across the processing.
That’s perhaps due to hidden choice points i don’t understand that exists, due to unoptimized recursions I may have, or due to bulk parameter passing – and due to inherent performance issues related to Prologs hash based fact retrieval – where i will need to find ways to speed things up, or move to custom code in C (or C++).
Dan
If it’s helpful, I wrote a little bit about my experience learning EDCG’s when I recently found out about them: Extended DCGs in Prolog
For DCGs in general, I found Annie’s tutorial (based on Markus Triska’s tutorial) very useful: http://www.pathwayslms.com/swipltuts/dcg/ (Markus’ original here: Prolog DCG Primer)
Like everything Logtalk, it already runs on SWI-Prolog (otherwise I wouldn’t mention it here). I assume you mean instead using it plain Prolog code or Prolog modules? The tool takes advantage of Logtalk’s debug hooks from its reflection API. Thus, it requires compilation of the code using the Logtalk compiler. For plain Prolog code, simply wrapping it using an object provides a solution. A quick example, using the likes.pl file bundled with SWI-Prolog:
?- {ports_profiler(loader)}.
...
true.
?- create_object(O, [], [set_logtalk_flag(debug,on), public(likes/2), include('/Users/pmoura/Documents/Prolog/swipl-devel/demo/likes.pl')], []).
O = o1.
?- findall(A-B, o1::likes(A,B), _).
true.
?- ports_profiler::data.
-------------------------------------------------------------------
Entity Predicate Fact Rule Call Exit *Exit Fail Redo Error
-------------------------------------------------------------------
o1 chinese/1 3 0 1 1 2 0 2 0
o1 indian/1 4 0 1 1 3 0 3 0
o1 italian/1 2 0 1 1 1 0 1 0
o1 likes/2 1 3 1 1 8 0 8 0
o1 mild/1 3 0 4 3 0 1 0 0
-------------------------------------------------------------------
true.
But for better performance, it would be preferable to use a static object. For example:
:- object(likes).
:- set_logtalk_flag(debug,on).
:- public(likes/2).
:- include('/Users/pmoura/Documents/Prolog/swipl-devel/demo/likes.pl').
:- end_object.
For a Prolog module, you can simply try to compile its source file as an object:
?- logtalk_load(prolog_module_source_file, [debug(on)]).
This may or may not require changes to the module code (the lack of effective Prolog modules standard makes it impossible to do much better here).
If you want to stick with Prolog modules and the solutions above don’t work for you, SWI-Prolog includes a prolog_trace_interception/4 that may allow implementation of a similar tool. A ports profiler can also be found in ECLiPSe.
Cheers,
Paulo
1 Like
And simply using SWI-Prolog’s native ?- profile(Goal). I guess there is a point providing a little more detail, but this would be fairly trivial to add. Currently only shows the box entries (call and redo). It also does some extras, such as run or walltime spent with hierarchical zoom in and out.
P.S. The only reason I didn’t mentioned SWI-Prolog own GUI profiler is because this thread is about removing choice points and that is best enabled with data also on the exit port. As you wrote, the SWI-Prolog profiler only shows call and redo ports. The ports profiler also allows you to learn much more about an application behavior, notably due to providing also data on the unification ports (fact and rule). It also doesn’t use a sampling rate like the SWI-Prolog GUI profiler but reports the exact number of passages in each ports (this is not necessarily an advantage, however).
The port counts are exact. The profiler dynamically builds a data structure representing the call graph and adds counts to these. That is based on hooks in some of the VM instructions. Concurrently there is a sampler that adds ticks to these nodes that represent the wall or CPU time. So, yes the usefullness for debugging failure or non-determinism is limited. The redo port gives statistics on actually activated redos. These are of course the most costly ones, but choice points that are never activated still need to be created and provide access to more data, making GC slower and keeping more data around. You cannot track that using the current profiler.
It isn’t hard to extend the data structures and collect all this though. A strong point is that the impact on performance is typically 5-20% (mostly depending on the size and notably the depth of the call tree) and memory consumption is low so you can run it on large and long running programs. Even better, you can start and stop profiling another thread to give an idea what it is doing without interrupting it.
Thanks for clarifying the semantics of the sampling rate. The tools we are discussing do intercept in functionality but also provide unique features. I used several times the SWI-Prolog GUI profiler in the past and it always provided useful guidance to access the impact of different designs thanks to the wall/cpu time information. As a side note, I do support it for profiling Logtalk code.
This might help:
Prolog Digest Feb 1988)
[Apologies if the formatting is messed up by cut&paste]
Date: 13 Feb 88 06:31:30 GMT
From: quintus!o…@unix.sri.com (Richard A. O’Keefe)
Subject: Prolog Grammar Rules
One of the things I really like about Prolog is grammar rules.
Since some commercial Prologs do not support grammar rules (such as
Turbo Prolog – do correct me if I’m wrong, I’m used to that…),
and since many Prolog text-books do not give them the emphasis they
deserve, I thought it might be worth saying a few words here about
them.
There's a little joke which goes something like this: Prolog was
invented by Kowalski in 1974 and implemented by Colmerauer in
1973. (The dates are wrong, but their *order* is right!)
What Colmerauer implemented was (*very* roughly speaking) grammar rules.
They came first!
We can approach grammar rules from two angles:
– parsing
– building lists.
From the parsing perspective, the key idea is that we can regard a
non-terminal such as ‘date’ as a relation on sequences.
For example, we can regard a grammar rule such as
date --> day, "-", month, "-", year.
as meaning
'date' is true of a sequence ABCDE if
there exist sequences A, B, C, D, E such that
ABCDE = A ^ B ^ C ^ D ^ E and
'day' is true of A and
B is "-" and
'month' is true of C and
D is "-" and
'year' is true of E.
It turns out to be more convenient to represent a non-terminal as a
relation between pairs of positions in a sequence. To boot-strap
this interpretation, we need a predicate
connects(X, S0, S)
which means “S0 and S are positions in the same sequence, S0 is one
element to the left of S, and the element between them is X”. If
we are working with lists,
connects(X, [X|S], S).
Any rate, given this one basic predicate, we can translate the
grammar rule above to
date(S0, S) :- % S0 = A^B^C^D^E^S
day(S0, S1), % S0 = A^S1, S1 = "-"^S2
connects(`-`, S1, S2),
month(S2, S3), % S2 = C^S3, S3 = "-"^S4
connects(`-`, S3, S4),
year(S4, S). % S4 = E^S
Now the fact that we can so easily transliterate a grammar rule into
Prolog doesn’t mean a lot. What is interesting is that the simple
top-to-bottom left-to-right execution strategy of Prolog gives us a
parser, and not just any old parser, but the familiar old recursive
descent parser which is so thoroughly understood. (For example, if
the grammar you want to parse is LL(k) for some smallish k, and you
are parsing ground lists, you can add “green” cuts to your Prolog
code to let Prolog know that it is determinate, and the theory of
recursive descent parsing tells us exactly where to put those cuts.)
It is worth stressing that there is nothing about grammar rules which
forces them to be based on lists. The grammar rule translators in the
Prolog systems which have them are typically based on lists, but you
can easily write your own translator.
It’s also worth stressing that although Prolog grammar rules work by
adding two extra arguments at the end, there’s nothing sacred about
that either. Fernando Pereira’s “eXtraposition Grammars” (XGs) add
four extra parameters.
Now let’s approach grammar rules from the second angle: building lists.
While it would be a bad idea to use lists for everything in Prolog,
lists are very important, and you often write code that generates lists.
For example, suppose we have a problem where
units are made of boards
boards contain components
some components are resistors
and we want a predicate that will collect all the resistor descriptions
in the description of a given unit. We might write something like this:
unit_resistors(unit(_,_,_,Boards,_,_,_), Resistors) :-
boards_resistors(Boards, Resistors, []).
boards_resistors([], Rs, Rs).
boards_resistors([Board|Boards], Rs0, Rs) :-
board_resistors(Board, Rs0, Rs1),
boards_resistors(Boards, Rs1, Rs).
board_resistors(board(_,_,Components,_,_,_), Rs0, Rs) :-
components_resistors(Components, Rs0, Rs).
components_resistors([], Rs, Rs).
components_resistors([Component|Components], [Component|Rs1], Rs) :-
resistor(Component),
!,
components_resistors(Components, Rs1, Rs).
components_resistors([_|Components], Rs0, Rs) :-
components_resistors(Components, Rs0, Rs).
I don’t know about you, but I get awfully tired of writing stuff like
that over and over again. Can’t something be done? It can. We are
describing a sequence. How do you describe sequences? With grammar rules!
We get
boards_resistors([]) --> [].
boards_resistors([Board|Boards]) -->
board_resistors(Board),
board_resistors(Boards).
board_resistors(board(_,_,Components,_,_,_)) -->
components_resistors(Components).
components_resistors([]) --> [].
components_resistors([Component|Components]) -->
{ resistor(Component) },
!,
[ Component ],
components_resistors(Components).
components_resistors([_|Components]) -->
components_resistors(Components).
Note that the way the results are stitched together into a list is (a)
exactly what we want, (b) boring, (c) invisible. Best of all, since we
didn’t type it in, we couldn’t get it wrong.
Once again, it is important to realise that although lists are the
most important application of this idea, the principle applies to
anything. In fact, we can look at programs like this as transforming
a state (the current position in a list) into another state (the next
position in a list), and we can do any transformation we like.
As an example, suppose that instead of collecting the resistor
descriptions, you just want to count them. We would change the
top-level call and the second clause of components_resistors//1:
unit_resistor_count(unit(_,_,_,Boards,_,_,_), Count) :-
boards_resistors(Boards, 0, Resistors).
...
components_resistors([Component|Components]) -->
{ resistor(Component) },
!,
add(1),
components_resistors(Components).
...
where
add(Addend, Augend, Result) :-
Result is Augend+Addend.
Again, there is nothing magic about this, and nothing sacred about
having a single state parameter. A good Prolog system will let
you define your own translations.
So that’s why grammar rules are interesting.
What, however, do they look like? Which of the things your Prolog
system offers are features, and which are bugs?
Here is a Prolog program which recognises valid grammar rules.
Add a few extra arguments, chant the magic phrase “partial
execution of a meta-interpreter”, and you’ll have a grammar rule
translator. (Well, there’s error reporting to worry about too.
That’s probably the hardest part.) I take clause_body/2 as given.
The code has been written to provide you with another test at the
same time: everything here is valid DEC-10 Prolog syntax and is
accepted by Quintus Prolog, and by the public-domain tokeniser and
parser. If your Prolog complains, it’s broken.
grammar_rule(-->(Head,Body)) :- /* Note 1 */
grammar_rule_head(Head),
grammar_rule_body(Body, yes).
grammar_rule_head(','(NonTerminal,PushBack)) :- !,
nonterminal(NonTerminal),
proper_list(PushBack). /* Note 2 */
grammar_rule_head(NonTerminal) :- /* Note 3 */
nonterminal(NonTerminal).
nonterminal(NonTerminal) :-
nonvar(NonTerminal),
functor(NonTerminal, Symbol, _),
atom(Symbol).
proper_list(List) :-
nonvar(List),
proper_list_1(List).
proper_list_1([]).
proper_list_1([_|List]) :-
proper_list(List).
grammar_rule_body(Var, _) :- /* Note 4 */
var(Var),
!.
grammar_rule_body(!, CutsOk) :- !, /* Note 5 */
CutsOk = yes. /* Note 6 */
grammar_rule_body(','(And,Then), CutsOk) :- !,
grammar_rule_body(And, CutsOk),
grammar_rule_body(Then, CutsOk).
grammar_rule_body(;(IfThen,Else), CutsOk) :-
nonvar(IfThen),
IfThen = ->(If,Then),
!,
grammar_rule_body(If, no),
grammar_rule_body(Then, CutsOk),
grammar_rule_body(Else, CutsOk).
grammar_rule_body(;(Or,Else), CutsOk) :- !,
grammar_rule_body(Or, CutsOk),
grammar_rule_body(Else, CutsOk).
grammar_rule_body(->(If,Then), CutsOk) :- !,
grammar_rule_body(If, no),
grammar_rule_body(Then, CutsOk).
grammar_rule_body({ }(Goal), CutsOk) :- !, /* Note 7 */
clause_body(Goal, CutsOk).
grammar_rule_body([], _) :- !. /* Note 8 */
grammar_rule_body([_|Tail], _) :- !, /* Note 9 */
proper_list(Tail).
grammar_rule_body(NonTerminal, _) :- /* Note 10 */
nonterminal(NonTerminal).
Notes.
1. Unlike a clause, a grammar rule must have the arrow there.
The analogue of
p(X, Y) :- true.
is
p(X, Y) → .
Don’t forget the arrow or the empty sequence of literals.
This is a mistake I have to watch out for.
2. A rule can look like
head --> body
or like
head, [t1,...,tn] --> body.
The pushback list is meant for handling extraposition in
natural language parsers, and is definitely for advanced
players (who disdain it). The grammar rule translator in
the first two editions of Clocksin & Mellish got pushback
wrong, which shows how often the feature is used!
3. A NonTerminal is exactly the kind of thing that you could
write as the head of a clause. Two arguments will be
added to it. So if you wrote
date(D, M, Y) --> .....
you'll get
date(D, M, Y, S0, S) :- ...
Two arguments are added to every nonterminal in a grammar rule.
Here's a convention of mine which you might like to adopt.
(Better yet: suggest an improvement!)
We identify a predicate with predicate symbol P and arity N
by writing the term P/N. Now a non-terminal with symbol S
and arity M corresponds to a predicate with predicate symbol
S and arity N+2, but you have to think twice before you
realise that the nonterminal
month(X)
you see in a program corresponds to the predicate month/3.
So I've taken to writing S//M, with the interpretation that
this means the same as S/(M+2), and the convention that it
is only used when S/(M+2) is in fact defined by grammar rules.
So I'd refer to boards_resistors//1 in the example above.
If you don't find this helpful, ignore it.
4. There are two "correct" things a grammar rule translator can
see if it sees a variable when it is expecting a grammar rule
body. Just as a variable in a clause body should be treated
as something which will call the GOAL the variable is bound
to, so a variable in a grammar rule body should be treated as
something which will pass the right arguments to the NONTERMINAL
the variable is bound to. For example, you might want to write
:- op(100, xf, *).
NT* --> [].
NT* --> NT, NT*.
You would be rightly upset if the translator quietly did the
wrong thing with this. So the two correct things are
- to translate a variable to something like
phrase(TheVariable, S1, S2)
- to report a translation fault when the translation is done,
and plant code to report the error at run-time, e.g.
format(user_error, '~N! NT variable executed~n'), fail
The first translation is preferred.
5. Yes, cuts are allowed in grammar rule bodies. So are
and-then, if-then-else, or-else, and if-then. How can you
predict which things are allowed? All the basic control
structures are allowed. What about negation? Well, no.
In this context, negation can't possibly be sound.
The control structures, and only the control structures,
are transparent.
What should happen if your Prolog system has other control
structures, such as once/1, forall/2, or Arity's NIH "snips"?
(If you are converting from Arity Prolog to another dialect,
[! SnippedStuff !] ==> ( SnippedStuff -> true) should do it.)
The honest answer is that nobody has thought about it much.
But a good answer would be that if nonterminals embedded in
the control structure could extend the list, the control
structure should be transparent. Otherwise it should probably
be reported by the translator. For example, things like
forall/2, findall/3, and so on, where all the solutions found
by the embedded goals are failed over, would not be candidates
for transparency, but "soft cuts" and "cases" would be.
6. The "CutsOk" business is simply pointing out that you
shouldn't have cuts inside the If part of an If->Then;Else
or If->Then.
7. To include a test in a grammar rule, a test that doesn't
match any of the input sequence, you write it inside curly
braces. Any clause body can appear there: {a ; b} is
legal and means the same as {(a ; b)}.
8. The empty list matches the empty sequence. It is the
grammar rule body analogue of 'true'.
9. A list of n terms matches n terms in the sequence if the
unifications go through. Whether the sequence being matched
has to be a list or not depends on how the 'connects'
operation is defined. If you don't use this construct, and
don't use pushback, your code should not depend on sequences
being represented by lists.
-
Anything other than a control structure, a list, or a clause
body inside curly braces, is taken to be a nonterminal.
Note that there is supposed to be no connexion whatsoever
between the built-in predicate integer/1 and the non-terminal
integer//1 (the predicate integer/3). If I want to defineinteger(X) → …
there is no reason for the system to stop me. On the other
hand, it would be rather odd. So a grammar rule translator
would do well to report non-terminals which look like built-in
predicates (though it needn’t), but on no account should it
fail to treat even such an odd goal as a non-terminal.There is a Prolog system around which will take a rule like
constant(X) → integer(X).
and treat it as the equivalent of
constant(X) → {integer(X)}.
without warning you. Now if you had meant that, you
could have written the curly braces, and the system in question
is perfectly happy to let you define integer//1, it just
quietly stops you using it. This is a bug. Printing a
warning message about the oddity and producing the correct
translation would be a definite feature.
I said that omitting the “–> ” in the base case of a non-terminal
is a mistake I have to watch out for. This is probably the first
thing to look for if you have a grammar which is mysteriously failing.
If you have a cross-referencer, such as the one Quintus provide, you
should watch out for predicates which are defined but not called.
The book by Fernando Pereira and Stuart Shieber may be of interest.
1 Like