Anybody got a short Prolog program for computing terms that are alpha variants? i.e. identical up to the choice of variable names. That is by uniformly renaming variables the two terms can be made identical.
Mark
Mark Tarver schrieb am Donnerstag, 1. September 2022 um 02:21:09 UTC+2:
Anybody got a short Prolog program for computing terms that are alpha variants? i.e. identical up to the choice of variable names. That is by uniformly
renaming variables the two terms can be made identical.
variant(C, D) :- \+ \+ (numbervars(C, 0, _), numbervars(D, 0, _), C == D).
Strangely numbervars/3 is not defined in the ISO core standard,
On Thursday, 1 September 2022 at 12:51:52 UTC+2, burs...@gmail.com wrote:
Mark Tarver schrieb am Donnerstag, 1. September 2022 um 02:21:09 UTC+2:
Anybody got a short Prolog program for computing terms that are alpha variants? i.e. identical up to the choice of variable names. That is by uniformly
renaming variables the two terms can be made identical.
variant(C, D) :- \+ \+ (numbervars(C, 0, _), numbervars(D, 0, _), C == D).Structural equivalence (=@=) does exactly that.
Strangely numbervars/3 is not defined in the ISO core standard,At least, term_variables/2 is ISO, you lucky one...
HTH,
Julio
Anybody got a short Prolog program for computingterms that are alpha variants?
variant(C, D) :- \+ \+ (numbervars(C, 0, _),numbervars(D, 0, _), C == D).
On Friday, 2 September 2022 at 00:44:50 UTC+2, burs...@gmail.com wrote:
I recently made a test, numbervars/3 bootstrapped
from term_variables/2. It turns out that it is slower.
I'm all for a RISC-like specification and a solid one, I rather find
the present situation a total mess, the standard we got to begin
with. That said, I can't in fact imagine a case where numbervars
is not just used for printing/serialization, where the performance
of the predicate makes no significant difference: can you?
I had to rethink the implementation for Dogelog Player,
and ended with the classical way to do it.
(By which I take you mean implemented natively/VM-level.)
Julio
I recently made a test, numbervars/3 bootstrapped
from term_variables/2. It turns out that it is slower.
I had to rethink the implementation for Dogelog Player,
and ended with the classical way to do it.
A case where performance of numbervars/3 makes
a dent is this case. In case you bootstrap (=@=)/2
via numbervars/3:
Mark Tarver schrieb:
Anybody got a short Prolog program for computingterms that are alpha variants?
Mostowski Collapse schrieb:
variant(C, D) :- \+ \+ (numbervars(C, 0, _),numbervars(D, 0, _), C == D).
You can try yourself. Write some code that
needs (=@=)/2. Compare different versions
of it, implemented with different versions
of numbervars/2. Also numbervars/2 could
serve as a starting point to implement (=@=)/2,
by parallel unfolding the two numbervars/2
in the definition of variant/2.
Julio Di Egidio schrieb:
On Friday, 2 September 2022 at 00:44:50 UTC+2, burs...@gmail.com wrote:
I recently made a test, numbervars/3 bootstrapped
from term_variables/2. It turns out that it is slower.
I'm all for a RISC-like specification and a solid one, I rather find
the present situation a total mess, the standard we got to begin
with. That said, I can't in fact imagine a case where numbervars
is not just used for printing/serialization, where the performance
of the predicate makes no significant difference: can you?
I had to rethink the implementation for Dogelog Player,
and ended with the classical way to do it.
(By which I take you mean implemented natively/VM-level.)
Julio
A case where performance of numbervars/3 makes
a dent is this case. In case you bootstrap (=@=)/2
via numbervars/3:
Currently these Prolog system do not have (=@=)/2:
- Scryer Prolog
- Tau Prolog
- Jekejeke Prolog
- Dogelog Player
- Ciao Prolog
- What else?
But they have all have numbervars/3. You can make
some benchmarking now with a numbervars/3 bootstrapped
variant/2. For example using pocket unit resolution
theorem prover:
---------------- begin pocket unit resolution ----------------
next(C, S, S) :- member(D, S), variant(C, D), !.
next(C, S, T) :- apply(C, S, H), many(H, [C|S], T).
variant(C, D) :- \+ \+ (numbervars(C, 0, _),
numbervars(D, 0, _), C == D).
many([], S, S).
many([C|S], T, R) :- next(C, T, H), many(S, H, R).
apply(C, S, T) :-
findall(E, (member(D, S), resolvent(C, D, E)), T).
resolvent(C, D, _) :-
\+ C = [_], \+ D = [_], !, fail.
resolvent(C, D, E) :-
select(A, C, C2),
select(B, D, D2),
opposite(A, B),
append(C2, D2, E).
opposite(pos(A), neg(A)).
opposite(neg(A), pos(A)).
---------------- end pocket unit resolution ----------------
Mostowski Collapse schrieb:
A case where performance of numbervars/3 makes
a dent is this case. In case you bootstrap (=@=)/2
via numbervars/3:
Mark Tarver schrieb:
Anybody got a short Prolog program for computingterms that are alpha variants?
Mostowski Collapse schrieb:
variant(C, D) :- \+ \+ (numbervars(C, 0, _),numbervars(D, 0, _), C == D).
You can try yourself. Write some code that
needs (=@=)/2. Compare different versions
of it, implemented with different versions
of numbervars/2. Also numbervars/2 could
serve as a starting point to implement (=@=)/2,
by parallel unfolding the two numbervars/2
in the definition of variant/2.
Julio Di Egidio schrieb:
On Friday, 2 September 2022 at 00:44:50 UTC+2, burs...@gmail.com wrote: >>> I recently made a test, numbervars/3 bootstrapped
from term_variables/2. It turns out that it is slower.
I'm all for a RISC-like specification and a solid one, I rather find
the present situation a total mess, the standard we got to begin
with. That said, I can't in fact imagine a case where numbervars
is not just used for printing/serialization, where the performance
of the predicate makes no significant difference: can you?
I had to rethink the implementation for Dogelog Player,
and ended with the classical way to do it.
(By which I take you mean implemented natively/VM-level.)
Julio
On Friday, 2 September 2022 at 22:05:07 UTC+2, burs...@gmail.com wrote:
A case where performance of numbervars/3 makes
a dent is this case. In case you bootstrap (=@=)/2
via numbervars/3:
Well well, of course I wouldn't do that. But then again,
I am not the one who wrote the standard...
Have fun,
Julio
Sometimes you don't make any sense. You
write you wouldn't bootstrap (=@=)/2
from numbervars/2, you said "I wouldn't
do that" And then you say "I am not the
one who wrote the standard...".
Are you aware that a) "I wouldn't do that"
implies that you wouldn't need numbervars/2.
And that b) numbervars/2 is not in the standard.
There is no numbervars/2 in the standard!!!
So what does it have to do with the standard?
Sometimes you don't make any sense.
Julio Di Egidio schrieb:
On Friday, 2 September 2022 at 22:05:07 UTC+2, burs...@gmail.com wrote:
A case where performance of numbervars/3 makes
a dent is this case. In case you bootstrap (=@=)/2
via numbervars/3:
Well well, of course I wouldn't do that. But then again,
I am not the one who wrote the standard...
Have fun,
Julio
Sometimes you don't make any sense.
So the ISO core standard is already RISC like
There is no numbervars/2 in the standard!!!
So the ISO core standard is already RISC likeThat is utter nonsense: as most of your drivel.
On Saturday, 3 September 2022 at 18:03:16 UTC+2, burs...@gmail.com wrote:
Sometimes you don't make any sense.I simply don't bother that you are an imbecille.
So the ISO core standard is already RISC likeThat is utter nonsense: as most of your drivel.
There is no numbervars/2 in the standard!!!There is no =@= either... idiot.
*Plonk*
Julio
What does the ISO core standard not make RISC?So the ISO core standard is already RISC likeThat is utter nonsense: as most of your drivel.
ju...@diegidio.name schrieb am Samstag, 3. September 2022 um 19:57:05 UTC+2:
On Saturday, 3 September 2022 at 18:03:16 UTC+2, burs...@gmail.com wrote:
Sometimes you don't make any sense.I simply don't bother that you are an imbecille.
So the ISO core standard is already RISC likeThat is utter nonsense: as most of your drivel.
There is no numbervars/2 in the standard!!!There is no =@= either... idiot.
*Plonk*
Julio
It doesn't have (=@=)/2 it doesn't have
numbervars/3, so it must be RISC, right?
LoL
Or what do you understand by RISC?
You can compare:
- ISO core standard, without the Annex,
which isn't very useful anyway:
ISO/IEC 13211-1:1995(E) = 124 Pages
- On the other hand the Ruby standard:
ISO/IEC 30170:2012(E) = 313 Pages
Mostowski Collapse schrieb am Samstag, 3. September 2022 um 21:22:12 UTC+2:
What does the ISO core standard not make RISC?So the ISO core standard is already RISC likeThat is utter nonsense: as most of your drivel.
ju...@diegidio.name schrieb am Samstag, 3. September 2022 um 19:57:05 UTC+2:
On Saturday, 3 September 2022 at 18:03:16 UTC+2, burs...@gmail.com wrote:
Sometimes you don't make any sense.I simply don't bother that you are an imbecille.
So the ISO core standard is already RISC likeThat is utter nonsense: as most of your drivel.
There is no numbervars/2 in the standard!!!There is no =@= either... idiot.
*Plonk*
Julio
Whats your RISC metric Culio?
*Plonk* per year?
Things that are not in the ISO core standard are more
likely to behave differently across Prolog systems?
GNU Prolog behaves already differently to SWI-Prolog in
numbervars/3. I find this discrepancy:
/* GNU Prolog 1.5.0 */
?- X = f(A,X), numbervars(X, 0, _), write_canonical(A), nl.
_24
cannot display cyclic term for X
/* SWI-Prolog 9.1.16 */
?- X = f(A,X), numbervars(X, 0, _), write_canonical(A), nl.
'$VAR'(0)
X = f(A, X),
A = A.
LoL
I am not extremly convinced by Richard O'Keefes approach
for subsumes/2. Especially how I have implemented it in
Dogelog Player, avoiding term_variables/2 all togtether!
Possibly I can produce some drastic test cases where it
doesn't run very well. On the other hand Jan W. is conceptually
promoting this bootstrapping of subsumes/2:
subsumes(General, Specific) :-
term_variables(Specific, SVars),
General = Specific,
term_variables(SVars, SVars).
The above cannot fast fail like Richard O'Keefes approach
can do. The further boostrapping is identical:
subsumes_term(General, Specific) :-
\+ \+ subsumes(General, Specific).
So what goodies are there in library(compat) as well?
Check this out:
/* SWI-Prolog 9.1.16 */
?- numlist(1,100000,A), numlist(1,100000,B),
time((between(1,1000,_), subsumes((f(_),X,X),(_,A,B)),
fail; true)), fail.
% 2,999 inferences, 2.375 CPU in 2.498 seconds (95% CPU, 1263 Lips)
false.
/* Dogelog Player 1.1.3 for Java (new!) */
?- numlist(1,100000,A), numlist(1,100000,B),
time((between(1,1000,_), subsumes((f(_),X,X),(_,A,B)),
fail; true)), fail.
% Zeit 2 ms, GC 0 ms, Lips 1550000, Uhr 18.10.2023 17:40
fail.
Dogelog Player for Java came out a few days ago. To get
subsumes/2 you have to use ensure_loaded(library(compat)).
I am using Richard O’Keefes algorithm from 1984 for subsumes/2.
Mild Shock schrieb am Mittwoch, 18. Oktober 2023 um 14:59:26 UTC+2:
Things that are not in the ISO core standard are more
likely to behave differently across Prolog systems?
GNU Prolog behaves already differently to SWI-Prolog in
numbervars/3. I find this discrepancy:
/* GNU Prolog 1.5.0 */
?- X = f(A,X), numbervars(X, 0, _), write_canonical(A), nl.
_24
cannot display cyclic term for X
/* SWI-Prolog 9.1.16 */
?- X = f(A,X), numbervars(X, 0, _), write_canonical(A), nl.
'$VAR'(0)
X = f(A, X),
A = A.
LoL
Sysop: | Keyop |
---|---|
Location: | Huddersfield, West Yorkshire, UK |
Users: | 303 |
Nodes: | 16 (0 / 16) |
Uptime: | 01:39:07 |
Calls: | 6,794 |
Calls today: | 2 |
Files: | 12,316 |
Messages: | 5,392,738 |
Posted today: | 1 |