canonical alternative to assert and retract
Simon Strobl
is there something like a canonical alternative to assert and retract?
In other words, are there algorithms for translating any Prolog
program that uses assert and retract into an equivalent program that
does without these predicates? And, if so, will the "compiled" (i.e.
the static) programs be, in general, equally or more or less
efficient? Do you know good articles about this issue?
Apart from aesthetical aspects, an obvious advantage of avoiding
assert and retract would be that one's programs are compatible with
more compilers. Thus, one could have Mercury or Yield Prolog compile
one's code.
The Mercury documentation is quite abstract about how to avoid assert
and retract: "The use of assert and retract should be replaced with a
collection data structure threaded through the relevant part of the
program."
Simon
Jan Wielemaker
> Hello,
>
> is there something like a canonical alternative to assert and retract?
> In other words, are there algorithms for translating any Prolog
> program that uses assert and retract into an equivalent program that
> does without these predicates? And, if so, will the "compiled" (i.e.
> the static) programs be, in general, equally or more or less
> efficient? Do you know good articles about this issue?
Considering that assert/retract are destructive operations
(i.e. survive backtracking) and using Prolog datastructures is subject
to backtracking, it will get very hard to convert the one
automatically into the other.
> Apart from aesthetical aspects, an obvious advantage of avoiding
> assert and retract would be that one's programs are compatible with
> more compilers. Thus, one could have Mercury or Yield Prolog compile
> one's code.
Its not just about aesthetics. Its also about global namespaces,
cleanup and consistency under backtracking. Assert/retract should
be banned from Prolog teaching, possibly except for issues such as
program transformation or importing semi-static external data into
a Prolog program.
> The Mercury documentation is quite abstract about how to avoid assert
> and retract: "The use of assert and retract should be replaced with a
> collection data structure threaded through the relevant part of the
> program."
It will be hard to say anything more concrete, I fear.
Cheers --- Jan
Eusebius
Jan Wielemaker a écrit :
> Assert/retract should
> be banned from Prolog teaching, possibly except for issues such as
> program transformation or importing semi-static external data into
> a Prolog program.
It's probably not very related to the original question, but I'm
interested in your remark. What would you use instead of assert/retract,
in order to simulate the learning of a new fact, say in an agent's
belief set?
I'd like to have your opinion on what should be used instead of assert
when it is possible.
Regards,
Eusebius
Jan Wielemaker
It is definitely possible to represent the agents beliefs in a binary
tree (i.e. library(assoc) or library(rbtrees)). In some cases you may
wish to represent the beliefs as a purely logical Prolog program, but
often you don't get very far as soon as recursion comes into play.
Anyway, if you do so, assert/retract may be appropriate. Also note that
assert/retract maintain a representation of a changing world, which
could justify the use of its destructive nature. When storing data for
reasoning about a constant environment (snapshot), the backtracking
nature of datastructures is much more appropriate.
There is rarely an absolute one and only answer, but in practise I see
far too much assert/retract. Things are improving a current project
that uses a lot of multi-threading. People are aware that simple
assert/retract will cause problems and prefer datastructures over
making the assert/retract code thread-safe :-) I.e. it must be made
more complicated :-)
Cheers --- Jan
Simon Strobl
O.k. Maybe I should have asked for a subset of the possible usages of
assert/retract.
A program of mine comes in two versions. Both versions do the same
thing. The difference is that version 1 does not use assert/retract
while version 2 does. In the vast majority of cases, version 2 is much
faster.
Both versions take as input a sentence and give as output a set of
parses. Version 1 simply tries all grammar rules to parse the
sentence. When there are many rules, this may take quite a long time.
Version 2 first uses the set of tokens the sentence consists of to
determine which rules may be relevant, asserts those rules, parses the
sentence and then retracts the rules.
Using standard parsing techniques is not an option for me because my
rules differ from standard rules and I want to be able to add more and
uncommon features to them in the future.
How could version 2 be made static?
Simon
Ulrich Neumerkel
>Hi Jan,
>
>Jan Wielemaker a écrit :
>> Assert/retract should
>> be banned from Prolog teaching, possibly except for issues such as
>> program transformation or importing semi-static external data into
>> a Prolog program.
>
>It's probably not very related to the original question, but I'm
>interested in your remark. What would you use instead of assert/retract,
>in order to simulate the learning of a new fact, say in an agent's
>belief set?
When an agent's state is represented by pairs of states before/after,
you can reason about alternative outcomes simultaneously. You can use
Prolog as a query language about the behaviour of an agent acting in
different worlds. You will be able to answer question like:
What must happen that an agent does something? Can this happen at all?
What must happen that an agent change/does not change its beliefs?
Is it possible that an agent changes its beliefs and then reconsiders
it?
In general such questions are about infinitely many possibilities. A
reduction to finite ones is inevitable. But even with this restriction,
this approach will produce much more coverage than single stepping
through of a single thread of one single world. It might help you to
discover interesting properties and is very useful for testing.
Jan Wielemaker
If compatibility is not an issue, I would not bother. If that is the
reason, I guess your rules need some quick selector at the start to
see which one could be applicable. I can imagine something along these
lines can be implemented, but it is mostly likely more complicated than
what you do now.
Cheers --- Jan
Ulrich Neumerkel
You can parameterize your rules with a further argument containing
a vector as a structure with an argument for each rule.
An argument 1 meaning, that rule is used, and 0 otherwise.
r(..., V) :- arg(23,V,1), ...
You might also use such a scheme in the other direction (provided your
programs are monotonic) by leaving the vector's arguments free.
This tells you what rules are required.
Eusebius
Thanks for the hints!
Regards,
Eusebius
Simon Strobl
> a vector as a structure with an argument for each rule.
> An argument 1 meaning, that rule is used, and 0 otherwise.
>
> r(..., V) :- arg(23,V,1), ...
Thanks for the hint. I already considered to use a solution of this
type. The problem is that I have no idea how the vectors should look
like.
Simon Strobl
I think I will continue to use the assert/retract solution. The only
thing I am not sure about is how to write an Swi web server for my
program and run it with several threads. My program has the structure
given below. Do I have to add code to make sure that the different
threads do not disturb each other? Or will the thread_httpd module
take care of this?
parse(Text, Solutions) :-
get_relevant_rules(Text, Rules),
assert_rules(Rules),
parse_with_asserted_rules(Text, Solutions),
retract_rules(Rules).
Jan Wielemaker
If you use simple assert/retract, you will end up with a very
interesting parser :-) There are two ways around. Typically, use the
:- thread_local Name/Arity, ... declaration. That ensures each thread
has its own set of clauses for the predicate. Alternatively, use a
pool of modules and do the parsing local in a module.
P.s. Especially if you have timeouts enabled, use
assert_rules(Rules),
call_cleanup(parse_with_asserted_rules(Text, Solutions),
retract_rules(Rules))
P.s. Using the GIT version, you can specify `spawn' in the handler
declaration that will cause the request to be handled in a new thread.
Together with thread_local your cleanup is now garanteed as
termination of a thread will erase all local clauses (they become
unreachable anyway).
Cheers --- Jan
Simon Strobl
This sounds easy. Thanks a lot for your tips.
One of the reasons why I wanted to have an alternative to assert/
retract was that I wanted to be able to use different Prolog compilers
and maybe also different web servers to increase efficiency. I thought
that if I used a compiler that generated C-Code (such as Mercury), I
could load this code into a C- or C++-based web server (such as
tntnet) and produce a very fast web version of my program. But
yesterday I wrote a thread_http-based web server. Having seen how easy
it is to bring Prolog to the web with Swi, I don't feel like mucking
about with all those interfaces between languages and tools anymore.
Simon
JeanMar...@mathworks.fr
I currently use a dictionary that I pass as an argument everywhere, as
an alternative to assert .
I adapted to SWI the program 15.9 from the Art Of Prolog book.
lookup/3 is like both put and get of Java Map .
You use it like this:
6 ?- lookup( a, D, aa), lookup( a, D, X).
D = dict(a, aa, _G510, _G511),
X = aa.
8 ?- lookup( a(b), D, aa(bb)), lookup( a(b), D, X).
D = dict(a(b), aa(bb), _G582, _G583),
X = aa(bb).
----------------------------------------------------
lookup( Key, dict( Key, X, _Left, _Right), Value) :-
!, X = Value.
lookup( Key, dict(Key1, _X, Left, _Right), Value) :-
compare('<',Key, Key1), lookup( Key,Left,Value).
lookup( Key, dict(Key1, _X, _Left,Right), Value) :-
compare('>',Key, Key1), lookup( Key,Right,Value).
% similar to lookup, but never modifies the Dictionary,
% just fails if the key is not present.
check_key( Key, Dictionary) :-
compound(Dictionary),
arg(1, Dictionary, Key),
! .
check_key( _Key, Dictionary) :- var(Dictionary ), !, fail.
check_key( Key, dict( Key1, _X, Left, _Right) ) :-
compare('<',Key, Key1), check_key( Key,Left).
check_key(Key, dict(Key1, _X, _Left,Right) ) :-
compare('>',Key, Key1), check_key( Key,Right).
A.L.
>I currently use a dictionary that I pass as an argument everywhere, as
>an alternative to assert .
I don't think that this is the issue whether you are using assert or
dictionary. The issue is whether computation is "state full" or "state
less", i.e. whether state of computation must be preserved between
consecutive invocations of the program or not
If "state full" model must be used, some mechanism for persisting data
must be also used, whether this is assert of something else.
A.L.
Jan Wielemaker
Thats what I sometimes try to tell people, but I often fail to get
the message across :-(
If scalability is an issue, doen't miss the latest GIT version that
comes with some enhancements to the HTTP library (chunked encoding
support and more flexible mapping of requests to threads). The
platform of choice for SWI-Prolog web-servers is 64-bit Unix on
multi-core hardware. If it really matters, choose the OS with some
care: there are huge differences in the performance of the thread and
socket APIs.
If you want to make it available through apache, simply load mod_proxy
and add rules like these (these are for the SWI-Prolog documentation
server, which is a Prolog running on port 8008):
ProxyPass /SWI-Prolog/pldoc/ http://localhost:8008/SWI-Prolog/pldoc/
ProxyPassReverse /SWI-Prolog/pldoc/ http://localhost:8008/SWI-Prolog/pldoc/
Of course this costs a bit of performance :-(
Cheers --- Jan
Simon Strobl
> an alternative to assert .
My problem is not that I do not know how to use a vector or a
dictionary as such. My problem is that I do not know exactly which
content the dictionary or vector should have and exactly how I should
"pass" the dictionary or the vector to the rules such that only the
relevant rules are loaded and such that the loading procedure is
reasonably efficient. But maybe someone can explain this to me?
Below is a simplified version of my rule lookup procedure. I do not
understand how to simulate this procedure using a vector or the like.
lookup(Sentence, Rules) :-
concat_atom(Tokens, ' ', Sentence),
get_rules(Tokens, Rules).
get_rules([], []).
get_rules([H|R], Rules) :-
trigger(H, HRules),
get_rules(R, RRules),
append(HRules, RRules, Rules).
get_rules([H|R], Rules) :-
\+(trigger(H, _)),
get_rules(R, Rules).
trigger('likes', [rule1, rule2, rule3]).
trigger('John', [rule4]).
trigger('Mary', [rule5]).
Jan Wielemaker
Someone else might answer that, but surely this
can be a bit faster:
get_rules([]) -->
[].
get_rules([H|T]) -->
( get_rule(H)
-> get_rules(T)
; get_rules(T)
).
trigger(likes) --> [rule1, rule2, rule3].
trigger('John') --> [rule4].
trigger('Mary') --> [rule5].
Cheers --- Jan
Simon Strobl
> > I currently use a dictionary that I pass as an argument everywhere, as
> > an alternative to assert .
>
> My problem is not that I do not know how to use a vector or a
Maybe I did not express myself clearly. What I wanted to say is this:
The set of rules that are relevant for a sentence depends on the
tokens the sentence consists of. Therefore, the data that has to be
passed to a rule must have to do something with the tokens of the
sentence to be parsed. The data might simply BE the set of tokens of
the sentence to be parsed. I.e. the parsing procedure might look like
this:
parse(Sentence) :-
tokenize(Sentence, Tokens),
s(Sentence, [], Tokens).
s(T1, T4, Tokens) :-
(
member('likes', Tokens) ;
member('like', Tokens) ;
member('liked', Tokens) ;
member('liking', Tokens) ;
member('owns', Tokens) ;
member('own', Tokens) ;
member('owned', Tokens) ;
member('owning', Tokens) ;
% here comes the rest of the list of all morphological forms
of all transitive verbs ...
),
np(T1, T2),
v(T2, T3),
np(T3, T4).
Yet, this does not seem to make much sense. It will probably be faster
to try the last three clauses of the body of the syntax rule than to
try the disjunction.
Jeff Thompson
I noticed you mentioned Yield Prolog. For what it's worth, 1.0 is
released which supports abolish and retract to be ISO compliant.
http://sourceforge.net/news/?group_id=176875
- Jeff (Yield Prolog author)