Permutations: a tail of two representations

On 2012-03-18, Ulrich Neumerkel <ulrich@mips.complang.tuwien.ac.at> wrote:
> Joachim Schimpf <jschimpf@invalid.invalid> writes:
>>ECLiPSe has had compile_term(Clauses) for as long as I can remember.
>>A language where programs can be represented as normal data structures
>>should probably have a standard way of compiling those structures...
>
> Excellent observation! On the other hand, keep in mind that current
> systems do already differ in mundane syntax matters.

<snip>

> Expecting to agree on something as complex as compile_term/1 will certainly
> be a challenge too demanding for the current situation.
> Think of it: Are directives included? Etc.

Directives probably won't kill us, but term/goal expansion might. One solution
is to use the SWI-Prolog interface that resulted from some mailinglist
discussion (mostly Richard O'Keefe), which provides compile_predicates/1.

The argument is a list of predicate indicators of dynamic predicates and
the result is that these have become static. It breaks a little away
from the original intend: allowing goal expansion to deal with recursive
predicates such as maplist/N. This doesn't merely require creating the
recursive auxilary predicatem, but also associate it with the source in
most practical situations to properly deal with reloading, debugging,
etc.

For that, SWI offers compile_aux_clauses/1, which is probably very close
to ECLiPSe compile_term/1. It does however link the created predicate to
the original source term, such that it will be wiped on a reload or unload
of the file. In SWI-Prolog's interface compile_aux_clauses/1 does handle
directives, but does not do any form of expansion. If this is desired,
the user must call expansion explicitly. I don't know whether that is
good or bad and I'm happy to change it. Directives are required though
(think of meta-predicate declarations).

Cheers --- Jan

Jan Burse schrieb:
> Best would be to *withdraw* the following standards:
> - module (old flavor) standard
> - DCG standard
>
> And start working on the following standard:
> - Expansion & rebuild framework
> - Make DCG an example library
> - Make modules (modern flavor) an example library (sic!)

Made the following thought experiment. Started with
expand_term/2. What about allowing conjunction to
indicate multiple rules:

So inside a file:

p(a), p(b).

p(X) :- q(X), p(X) :- r(X).

Would be the same as:

p(a). p(b).

p(X) :- q(X). p(Y) :- r(Y).


Then one could for example define:

term_expansion((A, B :- C),((A :- C),(B :- C)).

Then we would have, that inside a file:

p(a), p(b) :- q(c).

Would be the same as:

p(a) :- q(c). p(b) :- q(c).


Bad/good things so far for the expand_term/2 with (,)/2:

- Old Prolog text that were illegal because of (,)/2 in head,
would now be legal.

= The forall quantifier is implicitly shifted, which is
no problem since we logically have:

forall x (A & B) <=> forall x A & forall B

+ The conjunction is the right choice, since we have
logically:

G, A & B |- C <=> G, A, B |- C



But I am a little bit lost with expand_goal/2. One idea I had
was that expand_goal is allowed to return:

- A goal
- Zero, one or many auxiliary clauses.

The operator (@)/2 (or some other operator) would indicate
auxiliary clauses. Here is an example (simplified), creating a
lambda closure as an auxiliary clause. The sys_gensym/1 would
be a thread local thing:

goal_expansion(X=Y^A, (X=N) @ (H :- A)) :-
sys_gensym(N),
H =.. [N,Y].

The expand_goal/2 and expand_term/2 would need additional
rules so that the (@)/2 ripples up is finally turned into
a conjunction, so that multiple clauses are asserted. Something
along:

goal_simplification(((A @ B), (C @ D)), ((A,B) @ (B,D))).
goal_simplification(((A @ B), C), ((A,C) @ B)).
goal_simplification((A, (B @ C)), ((A,B) @ C)).

term_simplification((A :- B @ C), ((A :- B), C)).

Question: How should the auxiliary clauses be related to the
main clause. Here I see the following solutions:

1) Don't establish a relation. When the main clause and
the auxiliary clause are asserted they are related
to the source that is currently consulted.

This allows for easy reload of a source, just remove
the clauses which are related to the source before
consulting again. This would remove both the auxiliary
clauses and the main clause.

During listing the end-user would see the expanded
main clause and the auxiliary clauses. Same as with
DCG here, the end-user would see the end product. This
is good and bad.

2) Establish a relationship. The auxiliary clauses are
linked to the main clause.

This is not necessary for the reconsult, see 1). But
could be useful when retracting a single clause. When
this single clause is a main clause, all associated
auxiliary clauses can also be removed.

But retract is doubtful for converted single clause.
So probably a rebuild is necessary as well. So that
the retract matches the rebuild clause. This rebuild
clause could be also used in listing.

So we end again on the question whether the expansion
framework should include rebuilders and rebuild hooks.
Places to be rebuild could be detected by the naming
conventions in sys_gensym/2 or some such.

Bad/good things so far for the expand_goal/2 with (@)/2:

= Some issues already discussed in 1) and 2) above.

+ Conservative extension. We don't need to introduce
a expand_goal/2 with a greater arity.

- Eventually a new plugin architecture needed for the
simplification step. Kind of post processing after
the expansion. Could also be used for things such
as follows used in DCG:

goal_simplification((A, true), A).
goal_simplification(((A,B),C), (A,(B,C))).

- But plugin architecture for simplification not enough.
Would need ripple the (@)/2 via meta programming, since
it should not only ripple for (,)/2, but also for (/2,
etc.. and any meta declared predicate.

- The (@)/2 might block existing expansion rules, since
the will not be detected anymore. But this could be fixed
by a different protocol between expand_goal/2 and
goal_expansion/2.

Bye

Jan Burse <janburse@fastmail.fm> writes:
>Jan Burse schrieb:
> > Best would be to *withdraw* the following standards:
> > - module (old flavor) standard
> > - DCG standard

FYI: There is no DCG standard. There is a draft. And there are
many comments. Like mine:

http://www.complang.tuwien.ac.at/ulrich/iso-prolog/#dcg

Feel free to comment.

Jan Wielemaker <jan@invalid.invalid> writes:
>On 2012-03-18, Ulrich Neumerkel <ulrich@mips.complang.tuwien.ac.at> wrote:
>> Joachim Schimpf <jschimpf@invalid.invalid> writes:
>>>ECLiPSe has had compile_term(Clauses) for as long as I can remember.
>>>A language where programs can be represented as normal data structures
>>>should probably have a standard way of compiling those structures...
>>
>> Excellent observation! On the other hand, keep in mind that current
>> systems do already differ in mundane syntax matters.
>
><snip>
>
>> Expecting to agree on something as complex as compile_term/1 will certainly
>> be a challenge too demanding for the current situation.
>> Think of it: Are directives included? Etc.
>
>Directives probably won't kill us, but term/goal expansion might.

Think of the include directive. Not that I am favoring it but it
would mean that certain things have to be handled differently.

> One solution
>is to use the SWI-Prolog interface that resulted from some mailinglist
>discussion (mostly Richard O'Keefe), which provides compile_predicates/1.

Do you exclusively rely on that interface? CHR?

Hi,

Ulrich Neumerkel schrieb:
> Feel free to comment.

Commenting the draft of a *standard* is out of scope
of the idea of doing DCG via expansion, if the draft
does not do DCG via expansion.

I commented already a year ago over various channels
that I would like to do DCG via expansion. You can
take this as a note if you did not like do so.

Bye

Jan Burse schrieb:
> take this as a note if you did not like do so.

take this as a note if you did not yet do so.

Ulrich Neumerkel schrieb:
> FYI: There is no DCG standard. There is a draft. And there are
> many comments. Like mine:
>
> http://www.complang.tuwien.ac.at/ulrich/iso-prolog/#dcg
>
> Feel free to comment.

I already commented:

[PROLOG-STANDARD] Advantages of using the expansion mechanism
Around 26.07.11

But the idea of using expansion for DCG dates back to
July 25th, 2010, Jekejeke Prolog release 0.8.4

So one mission is to explore an alternative based on the
expansion mechanism to the draft of a new *standard*
for DCG.

But the present post is about auxiliary clause compilation,
which I have not yet seen used in DCG. So the present post
has only with DCG in common that it mentions "DCG" in its
initial citation, and later as a side note on simplification
of goal conjunctions.

?? Or do you think auxiliary clause compilation could be
useful for DCG ??

I don't see any such thing in your draft, and I do not
propose (,)/2 and (@)/2 for DCG. Except maybe for the DCG
lambda extension I have in my system. But this has not been
picked up by you and is only experimental so far.

I propose (,)/2 and (@)/2 for auxiliary clause compilation.
And I rather see it for other things such as foreach, do,
lambda etc.. etc..

Bye

Jan Burse schrieb:
> I propose (,)/2 and (@)/2 for auxiliary clause compilation.
> And I rather see it for other things such as foreach, do,
> lambda etc.. etc..

But a foreach in DCG could be also nice...
What would this do?

On 2012-03-22, Ulrich Neumerkel <ulrich@mips.complang.tuwien.ac.at> wrote:
> Jan Wielemaker <jan@invalid.invalid> writes:
>>> Expecting to agree on something as complex as compile_term/1 will certainly
>>> be a challenge too demanding for the current situation.
>>> Think of it: Are directives included? Etc.
>>
>>Directives probably won't kill us, but term/goal expansion might.
>
> Think of the include directive. Not that I am favoring it but it
> would mean that certain things have to be handled differently.

I just implemented many enhancements to include that make it somewhat
useable. I still dislike it, and you just gave another reason ...

>> One solution
>>is to use the SWI-Prolog interface that resulted from some mailinglist
>>discussion (mostly Richard O'Keefe), which provides compile_predicates/1.
>
> Do you exclusively rely on that interface? CHR?

I don't know how to interpret this. Do you mean whether more systems use
this interface or whether code that needs to generate static code can
only do this through compile_predicates/1?

To make one thing clear, CHR is implemented using term-expansion,
collecting the constraints while reading the file, mapping them to []
and expanding end_of_file, generating a list of clauses that constitutes
the Prolog equivalent of the CHR program.

Using term-expansion is my typical way to create static predicates
programmatically, but that is limited to predicates you can create a
program load-time. Sometimes you want to generate a static program later
during the computation, for example some static model of the world.

Using dynamic predicates is the normal way out, but there is a price. In
SWI-Prolog, this is mostly the synchronization needed to keep threads
happy. In other systems this is lack of indexing on dynamic code or
much less efficient code due to to requirement to make clause/2 work
on dynamic code, etc.

Converting dynamic code into static has (I hope) clear semantics. As
the code was dynamic, the compiler must be able to run clause/2 and
get access to the full term-representation of the code. Other systems
may be able to do the transformation from dynamic to static more
efficient (e.g., SWI-Prolog simply removes the lock and changes the
`supervisor code' of the predicate).

compile_predicates/1 takes a list of predicates, such that it can do
cross-predicate optimizations (e.g., inlining).

Cheers --- Jan

Jan Wielemaker schrieb:
> Converting dynamic code into static has (I hope) clear semantics. As
> the code was dynamic, the compiler must be able to run clause/2 and
> get access to the full term-representation of the code. Other systems
> may be able to do the transformation from dynamic to static more
> efficient (e.g., SWI-Prolog simply removes the lock and changes the
> `supervisor code' of the predicate).
>

I guess the above limits the CHR rules,
they cannot be multi-file.

Or can I call compile_predicates from
within multiple consulted files, and it
will only compile (turn from dynamic
into static) the slice that came from
the currently consulted file? For those
predicates that occur multiple times.

Bye

Jan Burse schrieb:
> Jan Burse schrieb:
> > Best would be to *withdraw* the following standards:
> > - module (old flavor) standard
> > - DCG standard
> >
> > And start working on the following standard:
> > - Expansion & rebuild framework
> > - Make DCG an example library
> > - Make modules (modern flavor) an example library (sic!)

Further motivation for the above:

- The expansion mechanism can help in
implementing forward chaining rules,
their generation at compile time.

- Better forward chaining rules can
be generated when goal simplification
is also available.

- Via forward chaining rules a constraint
store can be implemented.

- Even a constraint store can be implemented
that deals with (A -> B) not as ~(A & ~B)
but more cleverer, in that the store has positive
and negative atoms.

- The constraint store could profit from
a brother of setup_call_cleanup/3, that
invokes a cleanup goal when bindings
are undone.

Experimental, see for example:
https://plus.google.com/u/0/b/103259...ts/8oHErwopKxK

The above contains a lot of stuff not found in ISO:
- Expansion Mechanism
- Goal Simplification
- Brother of setup_call_cleanup/3

How are constraint stores portably implemented
without such an infrastructure? I guess an
alternative approach is attribute variables,
not yet sure whether they can be outperformed
via a constraint store in the knowledge base.
But attribute variables seem kind of
pervasive now.

Eventually they can be outperformed for
forward chaining problems with conditions
on a combination of variables, also not
yet sure.

Bye