Does DCG standard [2025] say (Semi-)Deep indexing? (Was: Benefit and drawback: (Semi-)Deep indexing still rare!)

From	Mild Shock <janburse@fastmail.fm>
Newsgroups	comp.lang.prolog
Subject	Does DCG standard [2025] say (Semi-)Deep indexing? (Was: Benefit and drawback: (Semi-)Deep indexing still rare!)
Date	2025-07-10 22:03 +0200
Message-ID	<104p69u$22f2s$1@solani.org> (permalink)
References	(2 earlier) <104p3so$22dce$1@solani.org> <104p4cr$22dou$1@solani.org> <104p4lv$22dsf$1@solani.org> <104p54q$22e7j$1@solani.org> <104p60s$22esu$1@solani.org>

Show all headers | View raw

Hi,

Does the new DCG standard [2025] say something about
(Semi-)Deep indexing. Are these people even aware,
that practically no Prolog system can execute DCG

in a satisfactory way. And its not a problem of
being declarative or something, or having bared
(\+)/3 or (!)/2 or something.

Its just that (Semi-)Deep indexing is rare, and without
deep indexing DCG degenerte into linear scanning
their clause set. So 20 years elaborating DCG standard.

And still only SWI-Prolog has deep indexing and
can practically takle DCG parsing?

That is extremly cringe...

Bye

P.S.: Disclaimer: Have to double check Ciao Prolog
and ECLiPSe Prolog, could be also a candidate for
deep indexing. Or maybe SICStus Prolog as well.

Mild Shock schrieb:
> Hi,
> 
> Lets say these semi-deep Prolog argument indexing
> will really work. Then I could rollback some
> uses of ROKs trick in my DCG based code base,
> 
> where I massaged the DCG to have a terminal in
> the first argument, and DCG was somehow degraded
> in only doing  the concatenative stuff, through its
> 
> monad rewriting. This would lead to elegant code.
> But it will not perform on a couple of Prolog systems,
> that don't have deep indexing. I suspect the more
> 
> elegant code will not perform on these Prolog system:
> 
> - GNU Prolog
> - Scryer Prolog
> - Trealla Prolog
> -
> 
> I didn't check ECLiPSe Prolog towards deep indexing,
> and also I didn't check Ciao Prolog towards deep
> indexing yet. It will show good performance:
> 
> - SWI-Prolog
> - Dogelog Player (if I add semi-deep and skip there)
> - Jekejeke Runtime (if I add semi-deep there, it has already skip)
> -
> 
> Bye
> 
> Mild Shock schrieb:
>> Hi,
>>
>> Today I had an idea, of some semi-deep Prolog
>> argument indexing. Just because choice point
>> elimination is so important and has so many
>>
>> benefits for performance and the end user
>> experience, like also debugging. And because it is
>> tied to indexing. An index and the resulting clause
>>
>> list, which can be always checked for having reached
>> its end. This gives a look-ahead information to the
>> Prolog system  which answers this oracle, concering
>>
>> clause instantiation:
>>
>> ∃X ( p(X) & X =\= a1 & ... & X =\= ak)
>>
>> So the idea of semi-deep Prolog argument indexing
>> would be a hybrid between Scryer Prolog and
>> SWI-Prolog taking the best of both worls.
>>
>> It would adopt skip indexes from Scryer Prolog
>> and deep indexing of SWI-Prolog, but deep indexing
>> through a Key computation trick. The Key computation
>>
>> trick is quickly explained.
>>
>> Normal Key Computations:
>>
>> p(a, ..)      ~~>  Computed Key: a/0 or sometimes a alone
>> p(b(x,y), ..) ~~>  Computed Key: b/2 or sometimes b alone
>> Etc..
>>
>> Semi Deep Key Computation:
>>
>> p(a, ..)        ~~>  Computed Key: 'a'
>> p([a, ..], ..)  ~~>  Computed Key: '.a'
>> Ect..
>>
>> Got it?
>>
>> The Scryer Prolog skip index is needed because
>> in a DCG the interesting arguments are usually
>> not the first argument.
>>
>> Bye
>>
>> Mild Shock schrieb:
>>> Hi,
>>>
>>> Now one might ask, if we have a Prolog system
>>> that anyway juggles with choice points, why
>>> would we need a logical formula for choice points?
>>>
>>> Well there is a funny correctness criteria,
>>> for example in the top-level, if the top-level
>>> doesn't prompt the end user anymore in such a scenario:
>>>
>>> ?- p(X).
>>> X = a1 ;
>>> X = a2 ;
>>> ...
>>> X = ak-1 ;
>>> X = ak
>>>
>>> So the end user is not prompted because the
>>> Prolog system founds CP = []. This is licensed
>>> by this correctness statement for any choice
>>>
>>> point elimination:
>>>
>>> CP = [] => ~∃X ( p(X) & X =\= a1 & ... & X =\= ak)
>>>
>>> Have Fun!
>>>
>>> Bye
>>>
>>> Mild Shock schrieb:
>>>> Hi,
>>>>
>>>> Now what does a Prolog system do? Well when
>>>> it prompts the end-user it has somewhere
>>>> a list of the current query choice points:
>>>>
>>>> CPs = [CP1, CP2, .., CPn]
>>>>
>>>> This is implementation specific, what choice
>>>> points a system creates, also the ISO core standard
>>>> shows a machine in its more procedural explanation,
>>>>
>>>> that depicts something that has also somewhere
>>>> choice points. Since it is implementation specific
>>>> a Prolog System A and Prolog System B might
>>>>
>>>> use different choice points:
>>>>
>>>> System A:
>>>> CPs = [CP1, CP2, .., CPn]
>>>>
>>>> System B:
>>>> CP's = [CP'1, CP'2, .., CP'n]
>>>>
>>>> We say a System B could eliminate a choice point CP,
>>>> relative to a System A, if we have:
>>>>
>>>> System A:
>>>> CP ∈ CPs
>>>>
>>>> System B:
>>>> CP ∉ CPs
>>>>
>>>> So System B might have an advantage over System A,
>>>> since it will not backtrack over CP.
>>>>
>>>> When it comes to answer substitution display,
>>>> it is now very common, that a Prolog system checks
>>>> its own choice points, and when it finds that
>>>>
>>>> CP = []
>>>>
>>>> It knows that the query left no choice points,
>>>> either because there were never any, because
>>>> there was no branching in the executed code, or
>>>>
>>>> because a cut removed branching, or because
>>>> they were eliminated somehow. Like through
>>>> some index analysis.
>>>>
>>>> Bye
>>>>
>>>> Mild Shock schrieb:
>>>>> Hi,
>>>>>
>>>>> This is nothing for Bart Demoen, Physics PhD,
>>>>> academic fraud. The ideal choice point can
>>>>> be formulated as a logical formula, involving
>>>>>
>>>>> an existential quantifier. Assume we have
>>>>> a query and already these answers, and the
>>>>> Prolog system is prompting the interactive user:
>>>>>
>>>>> ?- p(X).
>>>>> X = a1 ;
>>>>> X = a2 ;
>>>>> ...
>>>>> X = ak-1 ;
>>>>> X = ak
>>>>>
>>>>> A mathematical oracle that could indicate whether
>>>>> it is even necessary to prompt the user could be:
>>>>>
>>>>>     ∃X ( p(X) & X =\= a1 & ... & X =\= ak)
>>>>>
>>>>> It doesn't match 100% Prolog since Prolog might
>>>>> give duplicate answers or non-ground answers,
>>>>> but assume for the moment the query q(X),
>>>>>
>>>>> produces only distinct and ground results.
>>>>> Nice existential FOL formula we have in the above.
>>>>>
>>>>> Bye
>>>>>
>>>>> Mild Shock schrieb:
>>>>>>
>>>>>> Henri Poincaré believed that mathematical
>>>>>> and scientific creativity came from a deep,
>>>>>> unconscious intuition that could not be
>>>>>>
>>>>>> captured by mechanical reasoning or formal
>>>>>> systems. He famously wrote about how insights
>>>>>> came not from plodding logic but from sudden
>>>>>>
>>>>>> illuminations — leaps of creative synthesis.
>>>>>>
>>>>>> But now we have generative AI — models like GPT — that:
>>>>>>
>>>>>> - produce poetry, proofs, stories, and code,
>>>>>>
>>>>>> - combine ideas in novel ways,
>>>>>>
>>>>>> - and do so by processing patterns in massive
>>>>>>    datasets, without conscious understanding.
>>>>>>
>>>>>> And that does seem to contradict Poincaré's belief
>>>>>> that true invention cannot come from automation.
>>>>>>
>>>>>> Mild Shock schrieb:
>>>>>>> Hi,
>>>>>>>
>>>>>>> But I shouldn't waste too much time.
>>>>>>> One shouldn't punish people for just
>>>>>>> being plain stupid.
>>>>>>>
>>>>>>> Like for example this clueless french
>>>>>>> philosopher who had a lot of troubles
>>>>>>> with non-classical logic.
>>>>>>>
>>>>>>> His brain tried to eliminate non-classical
>>>>>>> logic, it was keen on avoiding non-classical
>>>>>>> logic. A typical species of a human with
>>>>>>>
>>>>>>> an extremly small brain, again working
>>>>>>> in the wrong place!
>>>>>>>
>>>>>>> Bye
>>>>>>>
>>>>>>> P.S.: Maybe this a Poincaré thingy? Poincaré
>>>>>>> was a strong critic of logicism (as championed
>>>>>>> by Frege and Russell) and of Hilbert’s
>>>>>>> formalist program.
>>>>>>>
>>>>>>> But, he did not formally use or promote systems
>>>>>>> like intuitionistic logic, modal logic, or
>>>>>>> relevance logic. His logical framework remained
>>>>>>> within the bounds of classical logic,
>>>>>>>
>>>>>>> though he was skeptical of excessive formalism.
>>>>>>> He thought formal systems could miss the creative
>>>>>>> and synthetic nature of mathematical
>>>>>>> invention. 
>>>>>>
>>>>>
>>>>
>>>
>>
>

Thread

Prolog totally missed the AI Boom Mild Shock <janburse@fastmail.fm> - 2025-02-22 13:05 +0100
  Auto-Encoders as Prolog Fact Stores (Was: Prolog totally missed the AI Boom) Mild Shock <janburse@fastmail.fm> - 2025-02-22 22:51 +0100
    Ignorance in ILP circles confirmed (Was: Auto-Encoders as Prolog Fact Stores) Mild Shock <janburse@fastmail.fm> - 2025-02-23 18:33 +0100
    Neuro infused logic programming [NILP] (Was: Auto-Encoders as Prolog Fact Stores) Mild Shock <janburse@fastmail.fm> - 2025-03-19 20:58 +0100
  Last Exit Analogical Resoning (Was: Prolog totally missed the AI Boom) Mild Shock <janburse@fastmail.fm> - 2025-03-07 18:16 +0100
  A software engineering analyis why Prolog fails (Was: Prolog totally missed the AI Boom) Mild Shock <janburse@fastmail.fm> - 2025-03-25 12:22 +0100
    Lets re-iterate software engineering first! (Was: A software engineering analyis why Prolog fails) Mild Shock <janburse@fastmail.fm> - 2025-03-27 11:42 +0100
      Re: Lets re-iterate software engineering first! (Was: A software engineering analyis why Prolog fails) Mild Shock <janburse@fastmail.fm> - 2025-03-27 11:43 +0100
  No Coders completely Brain Dead (Was: Prolog totally missed the AI Boom) Mild Shock <janburse@fastmail.fm> - 2025-06-23 16:37 +0200
    Unicode and atom length=1 (Was: No Coders completely Brain Dead) Mild Shock <janburse@fastmail.fm> - 2025-06-23 16:47 +0200
      Most radical approach is Novacore from Dogelog Player (Was: Unicode and atom length=1) Mild Shock <janburse@fastmail.fm> - 2025-06-23 17:03 +0200
        SWI-Prolog master not wide awake, doing day-sleeping (Was: Most radical approach is Novacore from Dogelog Player) Mild Shock <janburse@fastmail.fm> - 2025-06-23 18:43 +0200
          Re: SWI-Prolog master not wide awake, doing day-sleeping (Was: Most radical approach is Novacore from Dogelog Player) Mild Shock <janburse@fastmail.fm> - 2025-06-23 18:44 +0200
          The beauty of a double hook (Was: SWI-Prolog master not wide awake, doing day-sleeping) Mild Shock <janburse@fastmail.fm> - 2025-06-23 18:45 +0200
          The beauty of a dual use hook (Was: SWI-Prolog master not wide awake, doing day-sleeping) Mild Shock <janburse@fastmail.fm> - 2025-06-23 19:01 +0200
            maplist(char_code, Chars, Codes) is bidirectional (Was: The beauty of a dual use hook) Mild Shock <janburse@fastmail.fm> - 2025-06-23 19:17 +0200
              I really have lost all hope and given up (Was: maplist(char_code, Chars, Codes) is bidirectional) Mild Shock <janburse@fastmail.fm> - 2025-06-23 19:31 +0200
        Do Prologers know the Unicode Range? (Was: Most radical approach is Novacore from Dogelog Player) Mild Shock <janburse@fastmail.fm> - 2025-06-27 13:21 +0200
          Can Prologers produce 100% Prolog Code? (Was: Do Prologers know the Unicode Range?) Mild Shock <janburse@fastmail.fm> - 2025-06-27 13:22 +0200
            Attention: Python versus Java (Was: Can Prologers produce 100% Prolog Code?) Mild Shock <janburse@fastmail.fm> - 2025-06-27 13:36 +0200
        Is there a Swiss Army Knife of launching a Prolog system (Was: Most radical approach is Novacore from Dogelog Player) Mild Shock <janburse@fastmail.fm> - 2025-07-13 15:17 +0200
          An -e option could be the more rational choice (Was: Is there a Swiss Army Knife of launching a Prolog system) Mild Shock <janburse@fastmail.fm> - 2025-07-13 15:19 +0200
        Prolog Cycle detection in the Top-Level (Was: Most radical approach is Novacore from Dogelog Player) Mild Shock <janburse@fastmail.fm> - 2025-07-20 13:39 +0200
          What does SWI-Prolog / Ciao Prolog produce? (Was: Prolog Cycle detection in the Top-Level) Mild Shock <janburse@fastmail.fm> - 2025-07-20 13:43 +0200
  Do not give dogs what is holy [Matthew 7:6] (Was: Prolog totally missed the AI Boom) Mild Shock <janburse@fastmail.fm> - 2025-06-23 20:33 +0200
    Typo:: Do not give dogs what is holy [Matthew 7:6] (Was: Prolog totally missed the AI Boom) Mild Shock <janburse@fastmail.fm> - 2025-06-23 20:38 +0200
      What WG17 could do to prevent segregation [DEC-10 Prolog (10 November 1982)] (Was: Typo:: Do not give dogs what is holy) Mild Shock <janburse@fastmail.fm> - 2025-06-23 21:16 +0200
        Avoid the cheap tricks by Scryer Prolog (Was: What WG17 could do to prevent segregation [DEC-10 Prolog (10 November 1982)]) Mild Shock <janburse@fastmail.fm> - 2025-06-23 22:19 +0200
          Why tuck the tail in front of a false Messias (Was: Avoid the cheap tricks by Scryer Prolog) Mild Shock <janburse@fastmail.fm> - 2025-06-23 22:20 +0200
  Missed the AI Boom because missed the Emojis (Was: Prolog totally missed the AI Boom) Mild Shock <janburse@fastmail.fm> - 2025-06-29 13:32 +0200
    Bonus in Trealla Prolog, different Tokenizer (Was: Missed the AI Boom because missed the Emojis) Mild Shock <janburse@fastmail.fm> - 2025-06-29 13:36 +0200
  Science is not prepared for the AI Revolution (Was: Prolog totally missed the AI Boom) Mild Shock <janburse@fastmail.fm> - 2025-06-29 16:35 +0200
  Bart Demoen's amageddon revisited (Was: Prolog totally missed the AI Boom) Mild Shock <janburse@fastmail.fm> - 2025-07-09 01:55 +0200
    Long story short: Not everybody was blended by Bart Demoen (Was: Bart Demoen's amageddon revisited) Mild Shock <janburse@fastmail.fm> - 2025-07-09 02:08 +0200
      On last sample: Barty Boy in full swing (Re: Long story short: Not everybody was blended by Bart Demoen) Mild Shock <janburse@fastmail.fm> - 2025-07-09 02:12 +0200
        I hope he doesn't get a heart attack (Was: On last sample: Barty Boy in full swing) Mild Shock <janburse@fastmail.fm> - 2025-07-09 02:23 +0200
  Would Poincaré miss the AI Boom (Was: Prolog totally missed the AI Boom) Mild Shock <janburse@fastmail.fm> - 2025-07-10 19:17 +0200
    The ideal choice point as a logical formula (Was: Would Poincaré miss the AI Boom) Mild Shock <janburse@fastmail.fm> - 2025-07-10 21:22 +0200
      What is practical choice point eliminaton then? (Was: The ideal choice point as a logical formula) Mild Shock <janburse@fastmail.fm> - 2025-07-10 21:30 +0200
        Relation of the practical to the mathematical oracle (Was: What is practical choice point eliminaton then?) Mild Shock <janburse@fastmail.fm> - 2025-07-10 21:35 +0200
          Should try semi-deep Prolog argument indexing (Was: Relation of the practical to the mathematical oracle) Mild Shock <janburse@fastmail.fm> - 2025-07-10 21:43 +0200
            Benefit and drawback: (Semi-)Deep indexing still rare! (Was: Should try semi-deep Prolog argument indexing) Mild Shock <janburse@fastmail.fm> - 2025-07-10 21:58 +0200
              Does DCG standard [2025] say (Semi-)Deep indexing? (Was: Benefit and drawback: (Semi-)Deep indexing still rare!) Mild Shock <janburse@fastmail.fm> - 2025-07-10 22:03 +0200
    Stack Overflow is declining, and GitHub might be next (Was: Would Poincaré miss the AI Boom) Mild Shock <janburse@fastmail.fm> - 2025-07-15 20:55 +0200
      GitHub 2.0: The no code companion repository (Was: Stack Overflow is declining, and GitHub might be next) Mild Shock <janburse@fastmail.fm> - 2025-07-15 21:15 +0200
    Gian-Carlo Rota’s legacy and modern AI (Was: Would Poincaré miss the AI Boom) Mild Shock <janburse@fastmail.fm> - 2025-07-17 12:00 +0200
  Will the world build on American Stacks? (Was: Prolog totally missed the AI Boom) Mild Shock <janburse@fastmail.fm> - 2025-07-14 15:55 +0200
    Analogy as a Core of Intelligence (Human & Artificial) (Re: Will the world build on American Stacks?) Mild Shock <janburse@fastmail.fm> - 2025-07-17 12:14 +0200
      Alain Colmerauer Analogy : Rational Terms / Rational Numbers (Was: Analogy as a Core of Intelligence) Mild Shock <janburse@fastmail.fm> - 2025-07-17 14:33 +0200
        FYI: Peter Aczel Memorial Conference [10th September 2025] (Re: Alain Colmerauer Analogy : Rational Terms / Rational Numbers) Mild Shock <janburse@fastmail.fm> - 2025-07-17 14:57 +0200
          s/Coq/Rocq not found (Re: FYI: Peter Aczel Memorial Conference [10th September 2025]) Mild Shock <janburse@fastmail.fm> - 2025-07-17 23:17 +0200
            Wonder Years are Over: Next Step Mars (Was: s/Coq/Rocq not found) Mild Shock <janburse@fastmail.fm> - 2025-07-17 23:36 +0200
          Some of the legacy of Alain Colmerauer (Re: FYI: Peter Aczel Memorial Conference [10th September 2025]) Mild Shock <janburse@fastmail.fm> - 2025-07-23 19:10 +0200
  Looks like sorting of rational trees needs an existential type (Was: Prolog totally missed the AI Boom) Mild Shock <janburse@fastmail.fm> - 2025-07-23 13:57 +0200
    LLMs / Autoencoders could profit for Bisimulation Quotienting (Re: Looks like sorting of rational trees needs an existential type) Mild Shock <janburse@fastmail.fm> - 2025-07-23 14:03 +0200
      Are you Geh? From bi-simulation to bi-similarity (Was: LLMs / Autoencoders could profit for Bisimulation Quotienting) Mild Shock <janburse@fastmail.fm> - 2025-07-23 15:18 +0200
        Quite vibrant logic history one can experience right now! (Re: Are you Geh? From bi-simulation to bi-similarity) Mild Shock <janburse@fastmail.fm> - 2025-07-23 19:14 +0200
  The Prolog Community is extremly embarrassing (Was: Prolog totally missed the AI Boom) Mild Shock <janburse@fastmail.fm> - 2025-07-25 21:27 +0200
    Non-Wellfounded and Russell Paradox, what is your opinion? (Re: The Prolog Community is extremly embarrassing) Mild Shock <janburse@fastmail.fm> - 2025-07-25 21:38 +0200
      Unfinished Bimbo Stuff: 4.1. Trees as terms (Re: Non-Wellfounded and Russell Paradox, what is your opinion?) Mild Shock <janburse@fastmail.fm> - 2025-07-25 23:03 +0200
        Gold medal waiting for the crankiest of cranks (Was: Unfinished Bimbo Stuff: 4.1. Trees as terms) Mild Shock <janburse@fastmail.fm> - 2025-07-26 16:10 +0200
          Old School Logicians waste time with compare/3 ? (Was: Gold medal waiting for the crankiest of cranks) Mild Shock <janburse@fastmail.fm> - 2025-07-26 16:17 +0200
            Is compare/3 a sunflower study subject? (Was: Old School Logicians waste time with compare/3 ?) Mild Shock <janburse@fastmail.fm> - 2025-07-26 16:36 +0200
  Lattent Thinking the forbidden Fruit (Was: Prolog totally missed the AI Boom) Mild Shock <janburse@fastmail.fm> - 2025-11-02 11:58 +0100
  Latent Thinking the forbidden Fruit (Was: Prolog totally missed the AI Boom) Mild Shock <janburse@fastmail.fm> - 2025-11-02 12:19 +0100
    Fully automated AI researcher in your team? (Re: Latent Thinking the forbidden Fruit) Mild Shock <janburse@fastmail.fm> - 2025-11-02 13:20 +0100

csiph-web