Challenge behind Modules--> Truth Maintenance

[burs...@gmail.com]

The new predicate current_module/1 allowed me to
add a couple of test cases, that already test a
little bit name spaces.

A bigger challenge is testing the dynamics of
an interactive module system. Basic expectation here
could be the following: It shouldn't matter in

which order clauses are input, either clauses
from unnamed modules or clauses from named modules.
Sounds good? Very difficult to implement.

Here is an example with only unnamed modules, to
show what I mean:

Welcome to SWI-Prolog (threaded, 64 bits, version 7.7.14)
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software.

?- ['swiunnamed.p'].

?- test.
ERROR: Undefined procedure: foo/0

?- [user].
foo :- write(hello), nl.

?- test.
hello

So basically I had an interlevaing failed call to test/0,
and added foo/0 later. Does the same also work with
a named module. So far no:

Welcome to SWI-Prolog (threaded, 64 bits, version 7.7.14)
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software.

?- ['swinamed.p'].

?- test.
ERROR: Undefined procedure: swinamed:foo/0

?- [user].
foo :- write(hello), nl.

?- test.
ERROR: Undefined procedure: swinamed:foo/0

How can visual code IDE delivered with such a behaviour?
Here is the same test with Jekejeke Prolog. There is even a
help message, but the message is slightly off, it shows foo/0

qualifed, and it doesn't help it, since the named module was
anyway not notified of the new foo/0 predicate, and couldn't
change its lookup:

However, there are definitions for:
swinamed:foo/0

I am retesting the module system truth maintenance, because of
my intro of hierarchical knowledge bases. So I have to look
at everything again, to see whether it still works.

Here is what currently works, only showing the harder
named case:

Jekejeke Prolog 2, Runtime Library 1.2.7
(c) 1985-2018, XLOG Technologies GmbH, Switzerland

?- sys_add_path('nested').
Yes

?- ensure_loaded('nested/jeknamed.p').
% 1 consults and 0 unloads in 0 ms.
Yes

?- test.
Error: Undefined predicate foo/0.
foo/0
test/0

?- [user].
foo :- write(hello), nl.


Yes

?- test.
hello
Yes

I guess the problem is the interleaving call to test/0.
So this high interactivity might put a great challenge to
a Prolog system. The call test/0 causes possibly

a premature clause compilation, which is not undone
later on. It could be also only an inline call cache,
which is not invalidated...

For code and screenshots see here:
https://gist.github.com/jburse/baa1a055a1e2fb28f4defa539b787d1c#file-swinamed-p

[burs...@gmail.com]

Corr.:
There is even a help message in SWI-Prolog that
shows that foo/0 should be visible.

[burs...@gmail.com]

Maybe I will postpone the test cases for the module
dynamics, its truth maintenance. They are important
for a good working make/0 predicate.

Lets say the estimate would be in minimum like 100 new
test cases. I guess they can be done by test code,
that calls these built-ins:
- assertz/1
- abolish/1
- Etc..

I dont get a better result with assertz/1 in SWI-Prolog,
still the same for the named module testing scenario,
the interleaving test/0 call not shown:

Welcome to SWI-Prolog (threaded, 64 bits, version 7.7.14)
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software.

?- assertz((foo :- write(hello), nl)).
true.

?- test.
ERROR: Undefined procedure: swinamed:foo/0

But I guess if the stuff works for dynamic predicates
there are chances that the stame stuff also works for
static predicates:

Here is what Jekejeke Prolog does, the interleaving
test/0 call not shown:

Jekejeke Prolog 2, Runtime Library 1.2.7
(c) 1985-2018, XLOG Technologies GmbH, Switzerland

?- assertz((foo :- write(hello), nl)).

Yes

?- test.
hello
Yes

But it seems that I am running into testing hell.
I already added like 100 test cases last weak, in
connection with the module system here:

Test Results - Package system
http://www.jekejeke.ch/idatab/doclet/prod/en/docs/10_dev/15_stdy/08_compfreq/09_results/package.html?hash=system

[burs...@gmail.com]

The truth maintenace aspect is intersting, because
it gives more flexibility to interpreters. Do we need
compilers at all. Here is a little benchmark:



You can also make interpreters for object orientation which are quite fast. Jekejeke Prolog has a purely interpreted (::)/2 operator. There is not much overhead as of now. This is the test code:

Jekejeke Prolog 2, Runtime Library 1.2.7
(c) 1985-2018, XLOG Technologies GmbH, Switzerland

?- [user].

plain :- fail.

:- begin_module(obj).

simple(_) :- fail.

:- end_module.

And these are some actual results. There is not such a drastic difference between a plain call and an (::)/2 operator based call. Under the hood both predicate lookups are inline cached:

?- time((between(1,500000,_), plain, fail; true)).
% Up 452 ms, GC 7 ms, Thread Cpu 454 ms (Current 06/09/18 15:12:50)
Yes

?- time((between(1,500000,_), obj::simple, fail; true)).
% Up 493 ms, GC 7 ms, Thread Cpu 468 ms (Current 06/09/18 15:12:52)
Yes

We have still an overhead which might be removed in the future. It has to do that we still do a miniature rewrite for each (::)/2 call. But maybe this goes away, we are working on it.

Test is from here:

Logtalk method calls performance optimization
https://stackoverflow.com/q/32799458/502187

Am Montag, 28. Mai 2018 01:18:33 UTC+2 schrieb burs...@gmail.com:

[burs...@gmail.com]

Now upon writing this post, I just got the idea how
I could get more bang out of the (::)/2 operator.
Its a little evident, from its definition:

::(Receiver, Message) :-
Message =.. [Name|Args],
PythonStyleCall =.. [Name,Receiver|Args],
sys_get_module(Receiver, Module),
Module:PythonStyleCall .

Just unfold a part of the above definition during
compiletime. Maybe this could be the job of body
conversion. Need to experiment some time soon. At

the moment I have only concentrated on the inline
caches, and there were always changes...

[burs...@gmail.com]

The unfolding would be typically be done when
Receiver is ground. And we would need to generate
a module name which is not yet too much interpreted,

otherwise truth maintaince would not work. Truth
maintenance and unfolding are somehow different
poles and in conflict. Thats the sad story.

In as far the test case from SO, is not really
a single dispatch resp. late binding test case.
I am having problems finding a test suite, where

an intersting taxonomy of objects is involved,
and also all kind of dispatch on different levels,
so that much more can be measured...

[burs...@gmail.com]

Logtalk says, extra logical inferences:

Static binding: 0
Dynamic binding (object bound at compile time): 1
Dynamic binding (object bound at runtime time): 2

Amortizised or without amortization?

https://github.com/LogtalkDotOrg/logtalk3/wiki/Performance

Without amortization I guess this would include
that the truth maintenance system or the compiler
computes some transitive closure of the object

taxonomy. Otherwise its impossible to find in
constant time a predicate deep down in a module
hierarchy. Such a transitive closure can be very

innocently built by the reexport/1 directive during
consult, by adding stubs. But I don't do this.
Since its difficult to maintain such a transitive

closure and it needs space. So the inline caches
compute what they need. But its the same for all 3
sorts of call. Its always an interpreter and its

always the same cache:

Static binding: x
Dynamic binding (object bound at compile time): x
Dynamic binding (object bound at runtime time): x

x = amortizised performance of inline cache

Problem is the miniature rewriting I need, because
of the PythonStyleCall. Which adds a little extra
effort y, to the x, in the case of a (::)/2 call.

[burs...@gmail.com]

The test suite with deep taxonomy would also include private/
public declarations, and also test that these visibility
modifiers are quickly checked. So we would test the positive

and negative side of the cache. And with these modifiers in
place a global cache can be less effective. But I am
not sure about this, whether a negative cache is just

a luxury not really needed. The inline caches are much
more local. Basically my inline caches are inspired
by a paper of Urs Hözle, about polymorphic inline

caches in the Self Programming Language. But now, I even
don't know whether Self had private/public modifiers,
did check back whether they had it, and whether it

influenced any of their design. What is Self?
Here is a nice little video:

Self and Self: Whys and Wherefores
https://www.youtube.com/watch?v=3ka4KY7TMTU

[burs...@gmail.com]

Corr.:
did not yet check back whether they had it

[burs...@gmail.com]

I think Logtalk cannot do or doesn't do enough module
taxonomy stuff. Thats why it also doesn't have a lot
of taxonomy test case, where we would see what it

can do, and what it cannot do. For example {}/1 is
a way to do less taxonomy stuff, by avoiding the need
to resolve plain Prolog predicates. It seems that

is a core decision by Logtalk:

:- object(bench).

:- public(bench/0).
bench :-
write('Plain Prolog goal:'), nl,
prolog_statistics:time({plain_prolog_simple}).

https://stackoverflow.com/a/32799871/502187

But this runs counter the ISO module standard. In the ISO
module standard we do not find some {}/1 to braket plain
Prolog code. Its pretty clear, at least from this

SICStus mini interpreter, that the idea is that the
Prolog plain code is somewhere at the bottom of some
semantic taxonomy. We find in the SICStus mini

interpreter for a few plain predicates this code, see here:

call_goal(asserta(X), _) :- !,
asserta(X).
call_goal(asserta(X,R), _) :- !,
asserta(X, R).
% and so on for all built-in predicates
call_goal(Goal, M) :-
(M:Goal :- Body),
icall(Body, M).
https://sicstus.sics.se/sicstus/docs/latest4/html/sicstus.html/ref_002dmod_002dsem.html#ref_002dmod_002dsem

At least all builtins are at the bottom of
some taxonomy. But I guess this can be also
extended conceptually to user predicates.

In a module system there will be anyway not
many user predicates. The user is supposed to
do modules. But it might be useful to nevertheless

also add some user predicates by the user.

[burs...@gmail.com]

One argument in favor of the Logtalk {}/1 and against
the ISO module system approach could be the argument
that {}/1 is for classes and not for modules.

But well, it should be meanwhile clear, that my
opinion is that there is no difference between classes
and modules. See my posts here:

Best kept secret of Prolog, Lesson 1: reexport/1 directive as IS-A link
https://groups.google.com/d/msg/comp.lang.prolog/4_2WRm2EXCQ/0a6Pjr68AgAJ

Best kept secret of Prolog, Lesson 2: (:)/2 for late binding
https://groups.google.com/d/msg/comp.lang.prolog/4_2WRm2EXCQ/O5hELd6-AgAJ

There is no big difference between classes and modules.
There is only a difference between routines and methods.
Which is nicely captured by Pythonesk self parameter.

We can really thank Python, that they have so nicely
worked out the difference between routines and methods,
that many languages try to hide.

A feature I have not yet explored, and that is also
not so extensively present in Java, are classmethods.
Maybe this is present in Logtalk? See also here:

classmethod, useful for factory methods
https://www.programiz.com/python-programming/methods/built-in/classmethod

Without talking into account classmethods,
my opinion is classes = modules, we only need
to look after routines <> methods, but the Pythonesk

extra first argument for the Receiver does the
job. Concerning classmethods, I did not yet make
some experiments, since Java doesn't have it either.

Maybe, if this is desired, classmethod could be
also introduced, maintaining classes = modules?

[burs...@gmail.com]

Coming back to Truth Maintenance. What is exactly implemented
in Jekejeke Prolog? Our truth maintenance is two level.
We have two level versioning of source, depending

on what has changed. And over the last weeks we refined
the notification mechanism. It turned out that there is
a certain interplay of the two levels of versioning.

But a warning, the thing is still very prototypical, recent
additions were the local modules, now a refinement
was done for hiearchical knowledge bases.

But what is the basic idea behind this, and how would
it relate to Logtalk? Well the idea is basically JSR292
Java's Invokedynamic and this nifty detail:

A non-constant call site may be relinked by changing its target.
https://docs.oracle.com/javase/7/docs/api/java/lang/invoke/CallSite.html

What we do to provide such relinking is the following:
- We invalidate call sites indirectly by invalidating sources.
- And upon the next invocation, the call site updates its inline cache.

We made just now a snapshot of this invalidation
mechanism available on GitHub. The frist level
is fixvers, which is seen here:

public static void notifyFixvers(AbstractSource src, int f) {
https://github.com/jburse/jekejeke-devel/blob/master/jekrun/headless/jekpro/model/molec/CacheModule.java#L544

The second level is importvers,
which is is seen here:

public static void notifyImportvers(AbstractSource src, int f) {
https://github.com/jburse/jekejeke-devel/blob/master/jekrun/headless/jekpro/model/molec/CachePredicate.java#L726

Sorry for not yet having a complete source open source,
we are still working on it.

[burs...@gmail.com]

What comes immediately to mind concerning this relinking is:
- A Prolog compiler, that generates Java byte code,
could try to use invokedynamic. Not for lambda expression
or somesuch, but more because of relinking.

- One might thing about a new WAM with a relinking feature.
Possibly not much in the byte code itself would change,
maybe the extras around it and how the byte code interpreter
works needs to be specified.

- One might think about a new Logtalk, that is not a one go
transformation pipeline, but rather an interaktive system,
that can invalidate its invokation caches, and provide
a different experience.

- We might look around, like for example what was Erlang
doing, how does their Hot swap feature work, that allows
changing modules at runtime.

Disclaimer: The truth maintenance can get into a situation,
where its difficult to change the meaning of a predicate,
like from static to dynamic, etc.. so this relinking might

still fail. We find extra errors in SICStus prolog, which
have to do with the module loader. So although with relinking
we can give more dynamic user experience, still separate

or independent compilation or loading poses a lot of
challenges. These are the special errors:

4.15.4.8 Context Errors
https://sicstus.sics.se/sicstus/docs/4.0.4/html/sicstus/ref_002dere_002derr_002dcon.html#ref_002dere_002derr_002dcon

4.15.4.9 Consistency Errors
https://sicstus.sics.se/sicstus/docs/4.0.4/html/sicstus/ref_002dere_002derr_002dcns.html#ref_002dere_002derr_002dcns

[burs...@gmail.com]

Although Java CallSite doc talks about a concurent volatile
scenario. Our own scenario, not yet extremly tested, but ready
to go, everything very prototypical still, is rather a

tame one. In object oriented programming, it can happen that
when hierarchical knowledge bases are used, that a parent
knowledge base accumulates call sites pointing into some child

knowledge bases, especially when the (::)/2 is used in
the parent knowledge base. So in a web server, to do a hot
swap, we have a transaction level lock, can swap the child

knowledge base without any hurry at all, but the notification is
there, so that sooner or later, the parent knowledge base does
call the new correct child knowledge base, and not the old

knowledge base. More testing is needed in the time to come...

[burs...@gmail.com]

A more uncontrolled way of swapping the child knowledge
base, is when in web server, such as Tomcat for example,
a web context has the property "reload" and the class loader

is replaced. In this case we would polute memory and not
have any cache problem. The new web context would load a
new child knowledge base, and the parent knowledge

base would anyway recognize all child source as something
totally new, and add new cache entries. But the memory
then gets poluted both in the parent by inline cache entries

and in the overall heap of the web server by having unused
child knowledge bases. After like 10-20 such reloads the
web server has **Alzheimer**, and cannot anymore be used,

since all memory gets consumed. Such reloads are ok for fast
development and testing, locally on a test machine. But in
production where each GB of memory costs some money, Alzheimer

of a web server is not desired and interrupts production by
a server reboot. Everything has to be done more controlled
and careful. The Jekejeke Prolog knowledge bases have

- a finiKnowledgebase() method which should be called on an
old child knowledgebase, in case a class loader
replacement is desired.

- Otherwise the normal ensure_load/1 predicate and friends
can do the hot swap of modules correctly, notify parent as
well, thanks to the truth maintenance involved.

(*)
Currently considering whether this should be combined
with the new Java feature, that it is possible to call
close() on a class loader. Need platform testing.

[janb...@easel.ch]

I don't think a Prolog system is broken if it can do it
natively. You also don't say SWI-Prolog is broken,
because it implements between/3 natively.

Implementing a more richer module system natively,
up to providing an (::)/2 operator natively, has a lot
of advantages, that are difficult or impossible

to realize in a transpiler. Thats why relinking WAMs
should be studied or somesuch. The problem gets
much more aggravated when you want an

interactive system. Where the module system has
included what has in AI become known as "truth
maintenance", so that a kind of "believe revision"

is possible at runtime. A transpiler cannot necessarily
do this. I don't say its impossible. You would need to
have a incremental transpiler, which has an additional

input. Here is the difference:

Non-Incremental Transpiler:

Source --> Transpiler --> Results

Incremental Transpiler:

Delta Source --+
+--> Transpiler --> Delta Result
Old Result ---+

Truth maintenance inside a native module system, during
consult and reconsult of modules, does all this for you directly
inside memory.

A truth maintenance system, or TMS, is a knowledge representation
method for representing both beliefs and their dependencies and an
algorithm called the "truth maintenance algorithm" that manipulates and
maintains the dependencies. The name truth maintenance is due
to the ability of these systems to restore consistency.
https://en.wikipedia.org/wiki/Reason_maintenance

[janb...@easel.ch]

One more remark. The new hierachical knowledge bases
are again a additional dimension. They establish different
root namespaces which are stitched together.

Yesterday, I noticed that some of the call-site
caches might not work correctly, if a child knowledge
bases is abandoned.

So I just noted a few changes/improvements, which
still have to be applied to the implememt code. There
are still optimization opportunities abound...

What are the dimensions so far:
- flat or hierarchical module name space
- module name lookup, for qualified calls
/* fixvers notification does the truth maintenance */
- predicate name lookup, for unqualified calls
(and also for qualified calls in fact)
/* importvers notification does the truth maintenance */
- meta-predicate driven or meta-predicate less
- single or parent/child knowledge bases
/* class loaders and thread groups */

[burs...@gmail.com]

Here is a real life problem of truth maintenance
from another Prolog system. Innocently I tried
to do the following:

n^1 + n^2 + ... + n^n
lim n->oo ---------------------
1^n + 2^n + ... + n^n

My solution in my system and in SWI-Prolog read
the same, since both systems provide aggregate_all/3.
I was toying with:

/* :- use_module(library(misc/aggregate)). */
/* :- use_module(library(advanced/arith)). */

f(N, R) :-
aggregate_all(sum(K),(between(1,N,I), K is N^I), A),
aggregate_all(sum(K),(between(1,N,I), K is I^N), B),
R is A/B.

But in DOSEclipse I could not find aggregate_all/3. So
I needed to define it myself. I quickly figured
out that a sumlist/2 is already available from library(listut).

Watch this problem with truth maintenance:

Variant 1: first use_module then define predicate,
everything works fine:

ECLiPSe Constraint Logic Programming System [kernel threads]
Version 7.0 #36 (x86_64_nt), Sun Jan 28 10:18 2018

[eclipse 1]: use_module(library(listut)).

[eclipse 2]: [user].
aggregate_all(sum(X), G, R) :- findall(X, G, L), sumlist(L, R).
^Z

Variant 2: first define predicate then use_module, some
truth maintenance is in place but it is confusing:

ECLiPSe Constraint Logic Programming System [kernel threads]
Version 7.0 #36 (x86_64_nt), Sun Jan 28 10:18 2018

[eclipse 1]: [user].
aggregate_all(sum(X), G, R) :- findall(X, G, L), sumlist(L, R).
^Z

[eclipse 2]: use_module(library(listut)).
//C/Program Files/ECLiPSe 7.0/lib/listut.pl compiled 17024 bytes in 0.02 seconds
Definition of sumlist/2 in module listut is incompatible (mode declaration) with call in module eclipse

I don't think its incompatible. When doing it in a
different order everything works fine. The result of
this truth maintenance diagnosis is that I can throwaway
my [user] work.

I tried abolish(aggrebate_all/3) and tried to define
it anew. The system still believed that there is something
wrong and did let me call sumlist/2 anymore.

[burs...@gmail.com]

Corr.:
wrong and did not let me call sumlist/2 anymore.

[burs...@gmail.com]

Autoloading is also intimitadely connected to truth
maintenance. In auto loading a module is loaded
during execution for a qualified call.

It can be applied to library and foreign, and it
can be provided for (:)/2 and (::)/2. Here is
an example in my system:

Jekejeke Prolog 3, Runtime Library 1.3.0

(c) 1985-2018, XLOG Technologies GmbH, Switzerland

?- basic/lists:member(X, [1,2,3]).
X = 1 ;
X = 2 ;
X = 3

?- current_error(X), X::write('abc'), nl(X).
abc
X = 0r44bcd47d

In the first example the Prolog module basic/lists is
automatically loaded. And in the second example the
Java class java.io.Writer is automatically loaded.

For an OO-system that delegates to (:)/2, the
auto loading is handled there. No special need for
some auto loading handling in (::)/2.

So I don't know how Log-Nonsense-Talk would solve
the problem, since it is too shy to reuse (:)/2?
Write its own auto loader?