Path: csiph.com!weretis.net!feeder8.news.weretis.net!reader5.news.weretis.net!news.solani.org!.POSTED!not-for-mail
From: Mild Shock <janburse@fastmail.fm>
Newsgroups: comp.lang.javascript
Subject: Gap Buffers for Dogelog Player (Re: Jaffar's Unification in Dogelog Player)
Date: Thu, 2 Oct 2025 14:09:43 +0200
Message-ID: <10blq27$dhod$1@solani.org>
References: <10877t8$cm50$3@solani.org> <10auacq$qjhg$2@solani.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Thu, 2 Oct 2025 12:09:43 -0000 (UTC)
Injection-Info: solani.org; logging-data="444173"; mail-complaints-to="abuse@news.solani.org"
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:128.0) Gecko/20100101 Firefox/128.0 SeaMonkey/2.53.21
Cancel-Lock: sha1:OnMnHymcaZ+1sF5ZgLWHIs5uYHs=
In-Reply-To: <10auacq$qjhg$2@solani.org>
X-User-ID: eJwFwQkBwDAIA0BL7SBQ5PDFv4TdQexauxpMQbA/vNMqCZ9YN6+0He7NyvLAKPXhKaWOe1PVJWIWmE4e/mTyFj8=
Xref: csiph.com comp.lang.javascript:124408


Dogelog Player is a Prolog system for the
JavaScript, Python and Java platform. We
recently ventured into cyclic terms, re-
discovering Jaffar’s Unification for
binary operations such as (==)/2, (=)/2,
etc.. . Here we talk about unary operations
such as term_variables/2, ground/2, etc..

While we could already adopt a Peter Deutsch
algorithm for the Dogelog Player garbage
collection, freeing us from native stack
constraints. For performance reasons of unary
operations such as term_variables/2, ground/2,
etc.. gap buffers known from Emacs showed up.

See also:

Gap Buffers for Dogelog Player
https://medium.com/2989/bf3bc861ae04

Mild Shock schrieb:
> 
> We are currently in our third iteration of
> unification for rational trees. What first
> begun as a separate routine inside library(math),
> has now recently become a novel take on the
> host language routine unify() inside the
> Dogelog Player Prolog system.
> 
> We report how we replaced the union find map
> data structure inside unify() by some Prolog
> compound pointer swizzling as suggested by Jaxon
> Jaffar in 1984, arriving at a more competetive
> rational tree unification realization.
> 
> Jaxon Jaffar (1984) already proposed Hydra test
> cases. They take very less memory but are very
> large when written. We conducted according tests
> with Dogelog Player and Scryer Prolog. For
> N = 16'384, 65'536, 261'144 the Rust Prolog
> 
> has a minor advantage over the JavaScript Prolog,
> but interestingly losing it for N = 1'048'576.
> 
> See also:
> 
> Jaffar's Unification in Dogelog Player
> https://qiita.com/j4n_bur53/items/b0b754f02d88680d3249
> 
> Mild Shock schrieb:
>> Dear All,
>>
>> We are happy to announce a new edition
>> of the Dogelog Player:
>>
>> - Frozen Terms:
>> We extended our garbage collector marking bits
>> to Prolog compounds. Unlike Prolog variables, where
>> setting all bits is used to indicate change set
>> membership, we use it to indicate frozen objects.
>> This makes the garbage collector and certain
>> built-ins such as copy_term/2 etc.. aware of
>> program sharing (PS).
>>
>> - Marking Algorithms:
>> We now provide native implementations of (==)/2,
>> copy_term/2, etc.. with sharing and cycle detection.
>> We didn't deploy additional marking bits and/or
>> pointers inside the Prolog terms, instead used
>> additional datastructures, leaving the Prolog terms
>> untouched. The compare/3 implementation is
>> not a total order.
>>
>> - Canonical Compare:
>> The library(lists) has experimental predicates
>> term_decompose/3 and term_canonical/2, still written
>> in 100% Prolog. We showcase their usage in
>> library(sequence) and library(aggregate). The end-
>> user gets by default a structure compare, but can
>> also have a canonical compare, both being
>> total and natural orders.
>>
>> Have Fun!
>>
>> Jan Burse, http://www.herbrand.ai/ , 21.08.2025
>