Optimizations of WAM implementations and others
Jan Burse
Could it be that the following optimizations
are commonly understud what they mean:
- Choice Point Elimination
Avoidance of choice point creation.
- Last Call Optimization
Reuse of enviroments
- Environment Triming
Shrinking of environments
Whereby the notions "choice point" and "environment"
have the meaning as in the early WAM spec of Warren.
Question is whether they are commonly understud in
their general aim, the details might of course vary.
Or would it be unfair to use these notions accross
all Prologs?
Bye
jb
The term Tail Call Optimization made it in favor
of Last Call Optimization. The google results
are as follows:
"Tail Call Optimization" Prolog --> 25'000 Hits
"Tail Call Optimization" Prolog --> 1'200 Hits
Total --> 26'200 Hits
"Last Call Optimization" Prolog --> 4'430 Hits
"Last Call Optimisation" Prolog --> 7'540 Hits
Total 11'970 Hits
Well this is a posteriori explanation. At least
the term Tail Call Optimization is now used in
a restructed comparison table on en.wikipedia.org.
But there are still many blanks, only two Prologs
have filled the table so far.
Bye
jb
The other terms have the following hits:
"Environment Trimming" Prolog --> 514 Hits
"Choice Point Elimination" Prolog --> practically none
So "Environment Trimming" seems to be a Prolog specific term.
On the other hand we find:
"Shallow Backtracking" Prolog --> 1'170 Hits
But I am not sure whether "Shallow Backtracking" has the
same breadth like "Choice Point Elimination".
Bye
k...@kymhorsell.com
...
> "Environment Trimming" Prolog --> 514 Hits
Ordering the "permanent variables" (try Google :) so successive
calls in a clause can eliminate those not referenced in the rest
of the relevant clause. Depending on what other optimisations are
done (e.g. massive inlining and special-casing) this can trim
memory usage down a significant amount.
> "Choice Point Elimination" Prolog --> practically none
Decide when no other clause can "possibly success" with the bindings
as seen in the present enviornment/arguments. It's like an implicit
green cut.
> So "Environment Trimming" seems to be a Prolog specific term.
> On the other hand we find:
Functional languages use many of the Prolog optimisations under
the same or different names.
> "Shallow Backtracking" Prolog --> 1'170 Hits
>
> But I am not sure whether "Shallow Backtracking" has the
> same breadth like "Choice Point Elimination".
From my understanding it is a completely different thing but some
considerations may overlap.
For all of these technical terms papers on WAM variants and
implementations should usually give all the gory details.
I don't think there's a need to USENET it. :)
--
R Kym Horsell <k...@kymhorsell.com>
If your ideas are any good you'll have to ram them down people's throats.
-- Howard Aiken
jb
Which of the papers is your favorite one, that would
cover a broad set of optimizations and give it a modern
name and definition?
Bye
k...@kymhorsell.com
[...]
The Prolog FAQ has a list
http://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/lang/prolog/impl/wam/0.html
but the one I got the most out of esp for details as you mentioned
Ait-Kaci, Hassan, "Warren's Abstract Machine:
A Tutorial Reconstruction", MIT Press, Cambridge, MA. 1991.
(It took me quite a while to get hold of a copy).
Jan Burse
> jb<burs...@gmail.com> wrote:
> [...]
>
> The Prolog FAQ has a list
> http://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/lang/prolog/impl/wam/0.html
> but the one I got the most out of esp for details as you mentioned
> Ait-Kaci, Hassan, "Warren's Abstract Machine:
> A Tutorial Reconstruction", MIT Press, Cambridge, MA. 1991.
> (It took me quite a while to get hold of a copy).
>
http://clip.dia.fi.upm.es/~logalg/slides/8_wam_AitKaci_book.pdf
I also saw PPT somewhere flying arround, that gives a brief overview.
He mentions explicitly:
- 5.5 Last Call Optimization
- 5.6 Environment trimming
But I am not sure where "choice point elimination" is burried.
It has to do with indexing as well, when the switch of
the index jumps to a trust_me, well then you don't need to
create a choice point. **Provided you avoid creating some
choice point structure before** you begin the indexing.
Not sure whether this is in the scope of Ait-Kaci...
And it has to do with cut. Neck cuts are easily seen
as allowing to eliminate choice points. You need to
do the switching and the unification, after that you
can do something like a trust_me. **Again provided you
avoid creating some choice point structure before** you
begin and complete indexing and unification. Not sure
whether this is in the scope of Ait-Kaci...
Non neck cuts that are able to eliminate choice points
preclude that you can separate choice points and
variable bindings. At least that is how I see the
situation. So it is related to environment trimming
maybe. In the appendix with the WAM instruction we clearly
see that cut Yn is defined as removing choice points
and some "tidy_trail", so I guess it is covered.
So maybe "choice point elimination":
- indexing: and the corresponding last clause stuff
- unification: and the corresponding neck cut stuff
- cut: and the corresponding choice point removal trail tidying
What else? Does the above always come in a package(*)?
Where does again shallow backtracking fit in? Is
choice point elimination a good name for the package?
Bye
(*) Not necessarily always in a package, Jekejeke
has 1) and 3), but not yet 2).
bart demoen
>
> Well this is a posteriori explanation. At least
> the term Tail Call Optimization is now used in
> a restructed comparison table on en.wikipedia.org.
Sorry, but I can't find it - can you give a more specific link ?
Thanks
Bart Demoen
bart demoen
> ....
I am not an expert on terminology, however, Google
"choice point elimination Prolog"
gives me the feeling that "choice point elimination" is something jb
coined, and does not belong to traditional Prolog implementation
terminology.
Anyway, I have no idea what "choice point elimination" is supposed to
refer to in literature.
Literally, "choice point elimination" should mean something related
to:
a choicepoint was created
some technique eliminates that choice point
What comes to mind is
cut !/0: but that is so specific and non-intelligent, that
it isn't worth a fancy name
removing a choicepoint during gc, because gc detects that
the alternatives cannot match the arguments - I do
not recollect exactly, but I think it is mentioned
in papers by Tarau-Demoen, and Wielemaker-
Neumerkel;
but my memory might fail me
a compile time technique that emits a trust instruction
earlier than a naive implementation would; Mercury
would be strong at that
"choice point elimination" could also be a fancy term for any
technique that does not create a (full) choicepoint where a more naive
implementation (read the Hassan tutorial) would. It would then apply
to
(deep &/\/ multi-arg) indexing (several papers)
shallow backtracking (see paper by Mats Carlsson)
transforming disjunction+! to if-then-else (folklore)
transforming predicates with shallow guards into
if-then-else (idem ditto)
i.e. choice point creation avoidance.
(note that shallow backtracking was abandoned by SICStus - not sure
what exactly pushed Mats over the edge, but the gains were not that
big, the related code in the compiler is non-trivial, and the
instruction set related to it needs maintaining as well).
> - Last Call Optimization
>
> Reuse of enviroments
Strictly speaking, the WAM does not reuse environments in its LCO: it
reuses the space, but not the contents. LCO in C - where it is often
restricted to self-recursive tail calls - often does reuse also (some
of) the contents. B-Prolog reuses as much as possible the contents of
its activation frames.
What all this means across Prologs ... who knows :-)
Environment trimming was considered useless already by Micha Meier in
the
80ties and some systems just didn't bother implementing it. Note that
when the WAM has the choice between optimizing for space versus for
speed,
it would choose for space - trimming might be an instance of that.
That was
probably the right systematic choice in the past. Now ... who knows.
Cheers
Bart Demoen
Chip Eastham
I found it using my preferred term, "tail recursion":
http://en.wikipedia.org/wiki/Prolog#Tail_recursion
The phrase "tail call" finds a more general application
in programming, according to this Wikipedia article:
http://en.wikipedia.org/wiki/Tail_call
which mentions the phrase "tail call elimination"
being also known as "tail call optimization". The
benefit is preserving stack space, as occurs in the
Prolog context too.
regards, chip
k...@kymhorsell.com
> On Oct 26, 7:50?pm, Jan Burse <janbu...@fastmail.fm> wrote:
>> ....
> I am not an expert on terminology, however, Google
> "choice point elimination Prolog"
> gives me the feeling that "choice point elimination" is something jb
> coined, and does not belong to traditional Prolog implementation
> terminology.
> Anyway, I have no idea what "choice point elimination" is supposed to
> refer to in literature.
> Literally, "choice point elimination" should mean something related
> to:
> a choicepoint was created
> some technique eliminates that choice point
I think it's more like something mentioned in passing by (I think
I remember) original Dave W related to knowing that a CP
need not be pushed rather than killing one that is extant.
Googline the term brings up a few papers. At the top of the Google
list seems to be an IEEE thing about Aquarius prolog where they
refer to David Warren's "original" (I assume the old Dec10 -- sigh) prolog.
I've also seen it called "choice point avoidance".
[...]
> but my memory might fail me
[...]
Yes, this is all getting a bit vague. :) I think the last time
I knew anyone was teaching this stuff was 20 years ago.
jb
jb
What I don't like in "tail recursion", that it somehow
implies recursion. But "tail call" or "last call" don't imply
recursion.
That "tail call" and "last call" gives some gain
also in non-recursive cases can be seen for backtracking
intensive examples. Assume I have a classical
generate and test problem:
?- p(X), q(X).
Now p generates an awful lot of X instantiations and
q has to test it. Now when q is something like:
q(t1) :- ... r1(s1).
q(t2) :- ... r2(s2).
..
q(tn) :- ... rn(sn)
And all the last calls ri(si) can be a little bit sped up,
by last call optimization, then although q is a hierarchical
predicate and not a recursive predicate, then this speed up
is multiplied by the number of backtrackings, and here you
go, the speed up will become visible (in order of millisecons
or so).
In recursion the speed up becomes visible when you recurse
a lot, i.e. when the number of invoked last called optimized
clauses is high not because of backtrack but because of
a high number of invocations of a deterministic predicate.
Bye