Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.prolog > #14797 > unrolled thread

The roots Program Sharing (PS): J Strother Moore II (1973)

Back to article view | Back to comp.lang.prolog

Contents

  The roots Program Sharing (PS): J Strother Moore II (1973) Mild Shock <janburse@fastmail.fm> - 2025-08-18 17:53 +0200
    Avoiding OCCUR Checks / The BAROQUE Language (Was: The roots Program Sharing (PS): J Strother Moore II (1973)) Mild Shock <janburse@fastmail.fm> - 2025-08-18 18:00 +0200
    Frozen Prolog Terms make copy_term/2 constant (Was: The roots Program Sharing (PS): J Strother Moore II (1973) Mild Shock <janburse@fastmail.fm> - 2025-08-21 03:29 +0200
      SWI-Prolog needs linear time (Was: Frozen Prolog Terms make copy_term/2 constant) Mild Shock <janburse@fastmail.fm> - 2025-08-21 03:30 +0200
        Old Lady with Double Pointers and Frozen Info (Was: SWI-Prolog needs linear time) Mild Shock <janburse@fastmail.fm> - 2025-08-21 03:31 +0200

#14797 — The roots Program Sharing (PS): J Strother Moore II (1973)

Hi,

J Strother Moore II is the Original Gangster (OG)
of program sharng. Interestingly structure sharing
meant always program sharing in the theorem

proving community back then:

COMPUTATIONAL LOGIC: STRUCTURE SHARING AND
PROOF OF PROGRAM PROPERTIES
J Strother Moore II - 1973
https://era.ed.ac.uk/bitstream/handle/1842/2245/Moore-Thesis-1973-OCR.pdf

Only the WAM community managed to intsitutionalize
the term structure sharng, as a reduced form of
program sharing, namely goal argument sharing

not using pairs of two pointers with skeleton and binding
environment anymore, to indentify a Prolog term,
but simple single pointers for a Prolog term.

Bye

[toc] | [next] | [standalone]

#14798 — Avoiding OCCUR Checks / The BAROQUE Language (Was: The roots Program Sharing (PS): J Strother Moore II (1973))

Hi,

The below PhD thesis is a nice gem,
including marvels such as:

 > 2.3 Avoiding Unnecessary OCCUR Checks
 > It is possible to significantly reduce the number
 > of calls to OCCUR during a resolution unification
 > by the following observation. If two clauses are
 > being resolved, they are standardized apart.
 >
 > Thus, a variable from the left-hand parent will not
 > occur in a term from the right-hand parent unless
 > during this unification, there has been a binding of a
 > variable from the right to a term from the left.
 >
 > A similar statement holds for 1eft-to-right bindings.
 > Once again, in structure sharing, this condition
 > is easy to check.

The BAROQUE programming languages is also
a genious contraption, it can run functions
backwards, basically a Prolog based functional

language, using the reified IF-THEN-ELSE
from Ulrich Neumerkel. Only in 1973 there was
no EMACS yet. Now we have Prologers that know

EMACS but still know nothing otherwise.

Bye

Mild Shock schrieb:
> Hi,
> 
> J Strother Moore II is the Original Gangster (OG)
> of program sharng. Interestingly structure sharing
> meant always program sharing in the theorem
> 
> proving community back then:
> 
> COMPUTATIONAL LOGIC: STRUCTURE SHARING AND
> PROOF OF PROGRAM PROPERTIES
> J Strother Moore II - 1973
> https://era.ed.ac.uk/bitstream/handle/1842/2245/Moore-Thesis-1973-OCR.pdf
> 
> Only the WAM community managed to intsitutionalize
> the term structure sharng, as a reduced form of
> program sharing, namely goal argument sharing
> 
> not using pairs of two pointers with skeleton and binding
> environment anymore, to indentify a Prolog term,
> but simple single pointers for a Prolog term.
> 
> Bye
> 

[toc] | [prev] | [next] | [standalone]

#14800 — Frozen Prolog Terms make copy_term/2 constant (Was: The roots Program Sharing (PS): J Strother Moore II (1973)

Hi,

Frozen Prolog terms don’t need to be traversed to know
whether they are ground. They have a GC mask information
that shows that they are program shared (PS) ground Prolog

terms, so that copy can immediately return. One can modify
the testing slightly, going from this here in frozen.pl:

test(N) :- between(1,1000,_), data(N,_), fail.
test(_).

test2(N) :- between(1,1000,_), test(N), fail.
test2(_).

To this here, unfortunately copy_term/2 not available in WebPL:

test(X) :- between(1,1000,_), copy_term(X,_), fail.
test(_).

test2(N) :- data(N,X), between(1,1000,_), test(X), fail.
test2(_).

So basically departing from testing whether a first access
to a program sharing structure is fast, into testing
whether copy_term/2 has some smarts to detect

program sharing structures.

Bye

Mild Shock schrieb:
> Hi,
> 
> J Strother Moore II is the Original Gangster (OG)
> of program sharng. Interestingly structure sharing
> meant always program sharing in the theorem
> 
> proving community back then:
> 
> COMPUTATIONAL LOGIC: STRUCTURE SHARING AND
> PROOF OF PROGRAM PROPERTIES
> J Strother Moore II - 1973
> https://era.ed.ac.uk/bitstream/handle/1842/2245/Moore-Thesis-1973-OCR.pdf
> 
> Only the WAM community managed to intsitutionalize
> the term structure sharng, as a reduced form of
> program sharing, namely goal argument sharing
> 
> not using pairs of two pointers with skeleton and binding
> environment anymore, to indentify a Prolog term,
> but simple single pointers for a Prolog term.
> 
> Bye
> 

[toc] | [prev] | [next] | [standalone]

#14801 — SWI-Prolog needs linear time (Was: Frozen Prolog Terms make copy_term/2 constant)

Hi,

I get for SWI-Prolog WASM, that copy is faster
than knowledge base fact access:

/* SWI-Prolog WASM, copy_term/2 testing */
?- test2(10).
(645.4ms)

?- test2(30).
(1056.5ms)

?- test2(90).
(2245.2ms)

For example copying the 90 element list takes
only 2245.2ms while acccessing the 90 element
list from facts takes 5372.3ms, see previous post.

But the copy_term/2 is nevertheless linear.

Bye

Mild Shock schrieb:
> Hi,
> 
> Frozen Prolog terms don’t need to be traversed to know
> whether they are ground. They have a GC mask information
> that shows that they are program shared (PS) ground Prolog
> 
> terms, so that copy can immediately return. One can modify
> the testing slightly, going from this here in frozen.pl:
> 
> test(N) :- between(1,1000,_), data(N,_), fail.
> test(_).
> 
> test2(N) :- between(1,1000,_), test(N), fail.
> test2(_).
> 
> To this here, unfortunately copy_term/2 not available in WebPL:
> 
> test(X) :- between(1,1000,_), copy_term(X,_), fail.
> test(_).
> 
> test2(N) :- data(N,X), between(1,1000,_), test(X), fail.
> test2(_).
> 
> So basically departing from testing whether a first access
> to a program sharing structure is fast, into testing
> whether copy_term/2 has some smarts to detect
> 
> program sharing structures.
> 
> Bye
> 
> Mild Shock schrieb:
>> Hi,
>>
>> J Strother Moore II is the Original Gangster (OG)
>> of program sharng. Interestingly structure sharing
>> meant always program sharing in the theorem
>>
>> proving community back then:
>>
>> COMPUTATIONAL LOGIC: STRUCTURE SHARING AND
>> PROOF OF PROGRAM PROPERTIES
>> J Strother Moore II - 1973
>> https://era.ed.ac.uk/bitstream/handle/1842/2245/Moore-Thesis-1973-OCR.pdf
>>
>> Only the WAM community managed to intsitutionalize
>> the term structure sharng, as a reduced form of
>> program sharing, namely goal argument sharing
>>
>> not using pairs of two pointers with skeleton and binding
>> environment anymore, to indentify a Prolog term,
>> but simple single pointers for a Prolog term.
>>
>> Bye
>>
> 

[toc] | [prev] | [next] | [standalone]

#14802 — Old Lady with Double Pointers and Frozen Info (Was: SWI-Prolog needs linear time)

Hi,

For a Prolog system that is already some
decades old, and has a double pointer
implementation, and that can detect

frozen Prolog terms during copying I find,
that the copy_term/2 is constant time:

/* Formerly Jekejeke Prolog */
?- time(test2(10)).
% Zeit 403 ms, GC 8 ms, Uhr 21.08.2025 03:09

?- time(test2(30)).
% Zeit 419 ms, GC 4 ms, Uhr 21.08.2025 03:09

?- time(test2(90)).
% Zeit 426 ms, GC 4 ms, Uhr 21.08.2025 03:09

Bye

Mild Shock schrieb:
> Hi,
> 
> I get for SWI-Prolog WASM, that copy is faster
> than knowledge base fact access:
> 
> /* SWI-Prolog WASM, copy_term/2 testing */
> ?- test2(10).
> (645.4ms)
> 
> ?- test2(30).
> (1056.5ms)
> 
> ?- test2(90).
> (2245.2ms)
> 
> For example copying the 90 element list takes
> only 2245.2ms while acccessing the 90 element
> list from facts takes 5372.3ms, see previous post.
> 
> But the copy_term/2 is nevertheless linear.
> 
> Bye
> 
> Mild Shock schrieb:
>> Hi,
>>
>> Frozen Prolog terms don’t need to be traversed to know
>> whether they are ground. They have a GC mask information
>> that shows that they are program shared (PS) ground Prolog
>>
>> terms, so that copy can immediately return. One can modify
>> the testing slightly, going from this here in frozen.pl:
>>
>> test(N) :- between(1,1000,_), data(N,_), fail.
>> test(_).
>>
>> test2(N) :- between(1,1000,_), test(N), fail.
>> test2(_).
>>
>> To this here, unfortunately copy_term/2 not available in WebPL:
>>
>> test(X) :- between(1,1000,_), copy_term(X,_), fail.
>> test(_).
>>
>> test2(N) :- data(N,X), between(1,1000,_), test(X), fail.
>> test2(_).
>>
>> So basically departing from testing whether a first access
>> to a program sharing structure is fast, into testing
>> whether copy_term/2 has some smarts to detect
>>
>> program sharing structures.
>>
>> Bye
>>
>> Mild Shock schrieb:
>>> Hi,
>>>
>>> J Strother Moore II is the Original Gangster (OG)
>>> of program sharng. Interestingly structure sharing
>>> meant always program sharing in the theorem
>>>
>>> proving community back then:
>>>
>>> COMPUTATIONAL LOGIC: STRUCTURE SHARING AND
>>> PROOF OF PROGRAM PROPERTIES
>>> J Strother Moore II - 1973
>>> https://era.ed.ac.uk/bitstream/handle/1842/2245/Moore-Thesis-1973-OCR.pdf 
>>>
>>>
>>> Only the WAM community managed to intsitutionalize
>>> the term structure sharng, as a reduced form of
>>> program sharing, namely goal argument sharing
>>>
>>> not using pairs of two pointers with skeleton and binding
>>> environment anymore, to indentify a Prolog term,
>>> but simple single pointers for a Prolog term.
>>>
>>> Bye
>>>
>>
> 

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.prolog

csiph-web