Modules design for multi-agent modeling

[ssardina]

wow, wow, amazing @jan, ninja…

OK so I implemented both of your suggestions. It took me a while to reconstruct them so as to understand what is happening but seems to work. I did all this because I was now very curious, I totally lost track of my application!!!

So, TWO parts:

1. I have a solution using expansion, of goals and terms., that is generic. I think the doc does need an example as this is far from trivial. Agree not a huge example. As I want to document this somewhere, I will post here the simplest extract I could manage to write as example (I know this is long, but markdown makes all the post readable I hope):

/*
	This example shows how to expand both head and body of clauses
	using term_expand/2 and goal_expand/3.
	See post in forum:
		https://swi-prolog.discourse.group/t/modules-design-for-multi-agent-modeling/557

	So, user writes:

	far_away :-
		percepts(P),	
		member(loc(Loc), P), 
		Loc > 100.
	farther_than(D) :-
		^percepts(P),	
		member(loc(Loc), P), 
		Loc > D.


	... and it gets transformed into (percept/1 is outside the module):

	far_away(A) :-
		call(A:percepts(B)),
		member(loc(C), B),
		C>100.
	farther_than(D, A) :-
		call(A:percepts(B)),
		member(loc(C), B),
		C>D.
	
*/

% Operator used to signal that expansion is needed for the goal
:- op(1, fx, ^).

expand_clause((Head0 :- Body0), (Head :- Body)) :-
     expand_head(Head0, Head, ExtraArg),
     b_setval(extra_arg, ExtraArg),	% remember the created extra variable when processing the Body
     expand_goal(Body0, Body),	% will use defined goal_expansion/2
     b_setval(extra_arg, []).

% What heads to expand (add one more argument)
expand_head(far_away, far_away(M), M).
expand_head(farther_than(D), farther_than(D, M), M).

% What goals in bodies to change context module (use one stored in global var extra_arg
goal_expansion(^G, call(M:G)) :-
	b_getval(extra_arg, M).
goal_expansion(percepts(P), call(M:percepts(P))) :-
	b_getval(extra_arg, M).


% Domain-independent: this will be the trigger, one per clause in the DB
term_expansion(ClauseIn, ClauseOut) :-
    expand_clause(ClauseIn, ClauseOut).

% These are the clauses that will be transformed/expanded automatically
far_away :-
	percepts(P),	
	member(loc(Loc), P), 
	Loc > 100.
farther_than(D) :-
	^percepts(P),	
	member(loc(Loc), P), 
	Loc > D.

2. Then I went and implemented your “crazy” last solution. Amazing. This needs no expansion at all and works with many modules. So I have an agent using two modules kb1 and kb2, and even kb1 calls kb2, which itself is the one calling percepts/1 that is in the agent. Because I will have many kb modules for different aspects, I factored out your solution into a separate module called withself which provides the raw tools:

:- module(withself, [with_self/2, call_self/1, percepts/1]).

% The `no_lco_ is needed to avoid last call optimization while calling Goal. 
% We pass this Module to avoid it being garbage collected.
with_self(Module, Goal) :-
     Goal,	% this will call
     no_lco(Module).

no_lco(_).

call_self(Goal) :-
    prolog_current_frame(F),
    prolog_frame_attribute(F, parent_goal, withself:with_self(Module, _)),	% who called with_self/2?
    call(Module:Goal).

%% Below we need to define hooks for every predicate in the original module that needs to recover its module
%% by tracing back the call to with_self/2 from that caller module
percepts(P) :-
    call_self(percepts(P)).

I think that domain-dependent percepts/1 here can be factored out into a different module itself.

I am quite impressed. Seems to me Paolo has a point: not just because something can be done somehow, it has to be done that way. Seems Logtalk has all this all sorted out and can provide you with more. I will at some point look at that, I think it is worth a student project.

At this point Logtalk requires significant thinking and work, and the above solution, while is impressive, is hard to estimate the performance cost, as every time the agent access the percepts, Prolog will traverse the call stack…

For now, I will stick to my non-module solution: I have a copy of all the KB loaded in each agent module.

However, I now understand that a totally module-based solution that is clean and not too cumbersome is doable. Thanks @jan and @pmoura!

wow what a estar Friday…

Sebastian

[pmoura]

@pmoura

Logtalk indeed will add around ~460KB (if memory serves) to the application.

P.S. Actually, with SWI-Prolog 8.1.4 and the current Logtalk git version, using the Logtalk embedding script for SWI-Prolog, the size of the generated QLF (logtalk.qlf, containing the Logtalk compiler and runtime) is ~333 KB.

[pmoura]

@ssardina

I am quite impressed. Seems to me Paolo has a point: not just because something can be done somehow, it has to be done that way. Seems Logtalk has all this all sorted out and can provide you with more. I will at some point look at that, I think it is worth a student project.

At this point Logtalk requires significant thinking and work, and the above solution, while is impressive, is hard to estimate the performance cost, as every time the agent access the percepts, Prolog will traverse the call stack…

Curious if the code of your multi-agents application is public… I would likely be able to do a Logtalk version of it quickly so that you can compare.

@ssardina

wow what a estar Friday…

Indeed this is fun and compensates for a raining day with no bike time

[jan]

@ssardina

is hard to estimate the performance cost, as every time the agent access the percepts, Prolog will traverse the call stack…

I won’t be too worried. Although Prolog stacks can be really deep, on well written code the physical depth is often not that large due to last call optimization. As raised before in this discussion though I am thinking about an alternative implementation for environments that are scoped over a call tree that does not suffer from this problem. Technically that isn’t very hard as we can reuse the infrastructure for foreign predicate environments, but a good interface is still to be designed.

In the end, if things get slow use the profile/1 to figure our what the problem is.

[pmoura]

@jan

is hard to estimate the performance cost, as every time the agent access the percepts, Prolog will traverse the call stack…

I won’t be too worried. Although Prolog stacks can be really deep, on well written code the physical depth is often not that large due to last call optimization.

From my experience with Logtalk, notably usage patterns for self calls, I would also not expect a significant performance hit here from the stack traversal.

@jan

As raised before in this discussion though I am thinking about an alternative implementation for environments that are scoped over a call tree that does not suffer from this problem. Technically that isn’t very hard as we can reuse the infrastructure for foreign predicate environments, but a good interface is still to be designed.

The idea of environments is quite interesting as the alternative to adding an extra argument to predicates to carry execution context information (which includes, in the case of Logtalk, not only self but also sender, this, meta-call context, …). The other alternative we discussed, represented by the idea of the with_self/2 predicate is not ideal outside simple scenarios where we just need a very limited set of OO features.

Cheers,
Paulo

[jan]

@pmoura

The idea of environments is quite interesting as the alternative to adding an extra argument to predicates to carry execution context information (which includes, in the case of Logtalk, not only self but also sender , this , meta-call context, …). The other alternative we discussed, represented by the idea of the with_self/2 predicate is not ideal outside simple scenarios where we just need a very limited set of OO features.

The tricks with with_self I showed was just an illustration. You can use the same to keep track of multiple variables (of course) or some term/dict to store information. Be careful that the argument you are interested in is accessed after completion to avoid it being garbage collected! Using the stack primitives you can write any environment interface you would like (I think). The main downside is that it is relatively slow if deep recursion happens inside the environment and also the constant time is not very good by using the far too general stack traversal.

If you want to prototype the ideas I think there is enough for you to work with though and you will probably come up with a good set of requirements for the final beast. I will probably also have a use case in my work on the well founded semantics in the tabling implementation.

[pmoura]

@jan

The tricks with with_self I showed was just an illustration.

That was my understanding, yes.

@jan

You can use the same to keep track of multiple variables (of course) or some term/dict to store information. Be careful that the argument you are interested in is accessed after completion to avoid it being garbage collected!

After completion? Can you please clarify?

@jan

Using the stack primitives you can write any environment interface you would like (I think). The main downside is that it is relatively slow if deep recursion happens inside the environment and also the constant time is not very good by using the far too general stack traversal.

The alternative (that I’m currently using in Logtalk and also discussed in this thread) of appending an execution-context argument to all predicates have a significant performance advantage: access to individual arguments (e.g. self, sender, object parameters, …) in the execution-context are compiled into clause head unifications, thus providing O(1) access. When a predicate clause doesn’t require access to the execution-context, the term representing it is simply passed (note: in tight recursive-loops, this seems to have a small performance hit in the SWI-Prolog VM that is absent in some other Prolog VMs; we briefly looked into it in the past, tentatively concluding that is due to the lack of a compiler peephole optimization).

[jan]

@pmoura

After completion? Can you please clarify?

I mean that for the goal carrying the environment in an argument and than calls some subgoal (usually) to which to expose this environment must make sure to

• Avoid using last-call optimization when calling the subgoal.
• Make there the environment argument is referenced after the subgoal, such that a GC won’t clear the argument as not being accessible. Thus the below wont do as GC will remove Self from the stack if it is allocated on the global stack, which means it is not an atom or small integer.

    with_self(Self, Goal) :-
        Goal,
        no_lco.

    no_lco.

Instead, use

    with_self(Self, Goal) :-
        Goal,
        no_lco(Self).

    no_lco(_Self).

This is also good:

    with_self(Self, Goal) :-
        Goal,
        nonvar(Self).

@pmoura

… appending an execution-context argument to all predicates …

That is surely a viable way of doing things. The upside is portability and possibly performance. There is only a principled performance gain if these additional arguments are used for clause indexing though, and I doubt they are. Yes, using the prolog_frame_attribute/3 approach is slower, but I do expect to be able to provide a native implementation that avoids stack traversal and should get a performance similar to b_getval/2, etc.

SWI-Prolog’s still rather naive way of dealing with last-call optimization is probably the major reason for the slow-down. Its stack-based rather than register based argument passing will result in some slow down anyway. This is (I think) also true for the WAM. It might be unmeasurable One day that will probably be fixed, but so far functionality seems more valuable than a small performance gain.

The difference would be that you get passing of the OO parameter passing without program transformation. This has advantages and disadvantages. One of the advantages is that the native development and debugging tools keep working without the need for hooks or replacing them with Logtalk alternatives. Also nasty Prolog code for which you cannot analyse what is precisely being called will pass the Logtalk OO parameters (including Prolog->C->Prolog calls). It should also allow you to use Logtalk as a library to organize certain parts of your program where you want that rather than being a language that can (indeed) run 99% of Prolog code unmodified.

This disadvantage is that Logtalk will become less uniform on its different backend processors and probably be harder to maintain for you.

[pmoura]

@jan

After completion? Can you please clarify?

I mean that for the goal carrying the environment in an argument and than calls some subgoal (usually) to which to expose this environment must make sure to

• Avoid using last-call optimization when calling the subgoal.
• Make there the environment argument is referenced after the subgoal, such that a GC won’t clear the argument as not being accessible. Thus the below wont do as GC will remove Self from the stack if it is allocated on the global stack, which means it is not an atom or small integer.

    with_self(Self, Goal) :-
        Goal,
        no_lco.

    no_lco.

Instead, use

    with_self(Self, Goal) :-
        Goal,
        no_lco(Self).

    no_lco(_Self).

This is also good:

    with_self(Self, Goal) :-
        Goal,
        nonvar(Self).

I think is clearer now. As Self is a variable in Goal at runtime (as we access Self to call Goal in another context) I didn’t expect the need of the no_lco/1 or nonvar/1 workaround. My understanding of your explanation is that at the time GC happens, there isn’t yet a unification of Goal with a term that includes the variable Self.

@jan

pmoura:

… appending an execution-context argument to all predicates …

That is surely a viable way of doing things. The upside is portability and possibly performance. There is only a principled performance gain if these additional arguments are used for clause indexing though, and I doubt they are.

Indeed there’s no point in indexing the execution-context argument. Ideally, there would be a way to prevent any indexing on that argument.

@jan

Yes, using the prolog_frame_attribute/3 approach is slower, but I do expect to be able to provide a native implementation that avoids stack traversal and should get a performance similar to b_getval/2, etc.

Something register-based instead of stack-based, I assume.

@jan

SWI-Prolog’s still rather naive way of dealing with last-call optimization is probably the major reason for the slow-down. Its stack-based rather than register based argument passing will result in some slow down anyway. This is (I think) also true for the WAM. It might be unmeasurable One day that will probably be fixed, but so far functionality seems more valuable than a small performance gain.

Although I would love for this particular issue to be fixed, I agree that’s not an urgent fix.

@jan

The difference would be that you get passing of the OO parameter passing without program transformation. This has advantages and disadvantages. One of the advantages is that the native development and debugging tools keep working without the need for hooks or replacing them with Logtalk alternatives.

Most developer tools ideally work at the same abstraction level as the source code the user is writing. Thus, the existing developer tools would still benefit from being updated for the new abstractions.

Personally, my view of developer tools is that they should be regular applications (that’s true for all Logtalk tools, btw) and, as such, the ecosystem should be open and welcome to alternatives (the key here is a strong, comprehensive, reflection API). To be clear, I’m not saying that the SWI-Prolog ecosystem have a different philosophy but I always sensed a strong preference from you for integration with the native tools rather than alternative tools, which is, of course, quite understandable.

@jan

Also nasty Prolog code for which you cannot analyse what is precisely being called will pass the Logtalk OO parameters (including Prolog->C->Prolog calls). It should also allow you to use Logtalk as a library to organize certain parts of your program where you want that rather than being a language that can (indeed) run 99% of Prolog code unmodified.

Nothing ever prevented the scenario of using Logtalk as a library only for some parts of an application. You can send (efficiently) messages to objects from modules and call module predicates from objects. True, that may require using two sets of developer tool instead of a single one, which is a drawback.

Being able to run most Prolog code unmodified was always a main goal to present Logtalk as an evolutionary step for code encapsulation and reuse, which is just one of the key areas where Prolog is evolving and needs to evolve to compete with mainstream programming languages and showcase the potential of logic programming.

Ideally, with Logtalk implemented at the same low-level as currently Prolog modules are implemented, these could be fully replaced while keeping backwards compatibility. The trouble is that there are no two implementations of modules with the same exact semantics and feature set (outside simple usage scenarios). Thus, ensuring full compatibility can not be done in any portable way as one would need to emulate every single feature, corner case, and quirk of each particular module system. A way out, in the long term, is to promote coding best practices that move users away from (needing to write) tricky code that relies in harder to emulate specific, low-level details.

@jan

This disadvantage is that Logtalk will become less uniform on its different backend processors and probably be harder to maintain for you.

I sure hope that one day there will be multiple implementations of Logtalk as a language and/or a closer integration with Prolog systems. There’s a significant investment being made in, notably, specification and tests to sustain both scenarios while, ideally, avoiding the Babel tower of current Prolog implementations.

[jan]

@pmoura

I think is clearer now. As Self is a variable in Goal at runtime (as we access Self to call Goal in another context) I didn’t expect the need of the no_lco/1 or nonvar/1 workaround. My understanding of your explanation is that at the time GC happens, there isn’t yet a unification of Goal with a term that includes the variable Self .

I think close. Self does not appear as an argument to Goal (that was the whole point). Goal (or one of its children) can indeed access Self using some predicate that finds it in the environment stack. Without the nonvar/no_lco trick GC will detect that the argument is not further referenced and reclaim it if it points at data on the global stack (if this is not the case (e.g., for an atom) there is nothing to gain by reclaiming it, so it just leaves it around. Well, if we are picky there is as it can make the atom available for atom-GC. The gains is probably not that great though while possible stack traces get a lot harder to interpret.

@pmoura

Something register-based instead of stack-based, I assume.

No, as SWI-Prolog has no registers Besides linking environment frames (and choice points), the environment (local) stack also contains a linked list of foreign environments. These exist during foreign calls and form a stack on Prolog->C->Prolog->C->… nesting. These things contain exactly what we want (a block of Prolog terms) and thus we could easily use these to create an environment block. During normal Prolog execution there is no nesting and the nesting that exists is usually shallow.

Otherwise we seem to agree