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

From	Mild Shock <janburse@fastmail.fm>
Newsgroups	comp.lang.prolog
Subject	Old Lady with Double Pointers and Frozen Info (Was: SWI-Prolog needs linear time)
Date	2025-08-21 03:31 +0200
Message-ID	<1085su0$brmu$3@solani.org> (permalink)
References	<107vi9k$7t1e$1@solani.org> <1085sot$brmu$1@solani.org> <1085src$brmu$2@solani.org>

Show all headers | View raw

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
>>>
>>
>

Back to comp.lang.prolog | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

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

csiph-web