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

Groups > comp.lang.prolog > #15893

From short-cut parallelism to true parallelism [π-WAM Musings] (Was: The stack and choice points as an after match)

Show all headers | View raw

Hi,

The word Musings has a totally new meaning:

Torbjörn Lager wrote:
 > When
 >
 > call(Goal), Self ! Pid-Goal
 >
 > succeeds, that top-level goal has completed
 > and the actor terminates successfully.

Ok, I see. I thought it will be automatically
redone, and thus rapid fire multiple solutions.
So you have already hardwired a once/1 semantic
into your spawn/3, in that the spawn/3 goal argument

when executed, is onced, only looking at its EXIT
and FAIL port, not calling once more its REDO port.
This also means that both parallel/1 and
first_solution/1 have a short-cut AND

respective OR semantic:

/* AND-parallelism with short-cut */
parallel([G1,..,Gn])   <=>   once(G1), .., once(G2)

/* OR-parallelism with short-cut */
first_solution([G1,..,Gn])   <=>   once(G1); ..; once(G2)

The short-cut is in that parallel/1 can stop
at the first failure, and that first_solution/1
can stop at the first success. I wonder whether
Web Prolog Trinity offers true AND-parallelism or

true OR-parallelism without a short-cut. Having
such constructs could be interesting for problem
solving and is often used parallel search. For
example SICStus Prolog offers, or offered, true

OR-parallelism in its Multi-sequential Prolog
engines (Muse) extension, from the SICS experiments
in the 1990s with the BNN Butterfly supercomputer
from the 1980s:

yes
| ?- muse_flag(num_workers,_,5).
| ?- run.
724 solutions in 2.760 seconds.

yes
| ?- muse_flag(num_workers,_,1).
| ?- run.
724 solutions in 10.400 seconds.

https://sicstus.sics.se/sicstus/docs/3.7.1/html/sicstus_6.html

The intervention for true OR-paralleism is usually
at rule choice points. So when you have a set
of rules, like for example in the case of
the select/3 predicate:

select([X|Xs], Xs, X).
select([Y|Ys], [Y|Zs], X) :- select(Ys, Zs, X).

You execute it as:

select(X, Y, Z) :-
     muse([select1(X,Y,Z), select2(X,Y,Z)]).

select1([X|Xs], Xs, X).
select2([Y|Ys], [Y|Zs], X) :- select(Ys, Zs, X).

Where the muse meta predicate has true OR parallelism:

muse([G1,..,Gn])    <=>    G1 | .. | Gn

Bye

See also:

The muse approach to Or-parallel prolog
https://link.springer.com/article/10.1007/BF01407834

BBN Butterfly
https://en.wikipedia.org/wiki/BBN_Butterfly

P.S.: Maybe this explains my Freundlian slip when
I expected your parallel/1 to be some OR-parallelism,
while it is some AND-parallism. The true OR-parallelism

can be mathematically formalized in logic via
non-determinism and π-calculus:

π-calculus
https://ncatlab.org/nlab/show/pi-calculus

You even don’t need actor mailboxes, only channel objects.

Mild Shock schrieb:
> Hi,
> 
> So the idea is to cover backtracking without
> stack and choice points, only with registers.
> So at the compute goto will use an instruction
> 
> that stores the PC target into a register,
> a new instruction for Hack:
> 
>     REG = PC + REL
> 
> And then the jump will be, again a new
> instruction for Hack:
> 
>     PC = REG
> 
> If we squeeze the lemon and compile as much
> with that, we will only find that it breaks for
> calling recursive predicates that can use
> 
> arbitary registers and choice points. But we
> could maybe add stack and choice point as an
> after match, instead of the classical WAM design
> 
> that starts with stack and choice points!
> 
> Bye
> 
> Mild Shock schrieb:
>> Hi,
>>
>> pi-WAM is a nice challenge, since its aim is to go
>> even blow the instruction set of SWI-Prolog,
>> while only using a Hack variant as instruction
>>
>> stream. But what is Hack? Well Hack seems to be
>> the missing legacy of Niclaus Wirths PL0. The
>> Hack (machine .asm) and Jack (highlevel compiler
>>
>> generating .vm which can be converted to .asm)
>> combo makes even the famous Crafting Interpreters
>> /Lox by Bob Nystrom redundant:
>>
>> Nand to Tetris courses are taught at 400+
>> universities, high schools, and bootcamps. The
>> students who take them range from high
>> schoolers to Ph.D. students to
>> https://www.nand2tetris.org/
>>
>> But digging deaper in Hack, it has no functions
>> pointers so objects don't use virtual tables.
>> But what will pi-WAM need and that is not yet
>>
>> in Hack? Given that my pi-WAM doesn't want a stack
>> nor a choice point lists? Currently there is the
>> idea to add a computed goto and that it can
>>
>> cover a more lightweight C_OR as known from
>> SWI-Prolog, that would have the C_OR branches
>> maybe restricted to have no outside
>>
>> clause calls? Lets see. Not yet sure.
>>
>> Bye

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

Thread

Prolog Education Group clueless about the AI Boom? Mild Shock <janburse@fastmail.fm> - 2025-03-03 14:18 +0100
  Re: Prolog Education Group clueless about the AI Boom? Mild Shock <janburse@fastmail.fm> - 2025-03-03 14:20 +0100
    Salary Templates if you "Grok" ML / AI [PhDs Negotiate Salaries] (Re: Prolog Education Group clueless about the AI Boom?) Mild Shock <janburse@fastmail.fm> - 2025-03-03 18:03 +0100
  ILP is still dreaming of higher order (Was: Prolog Education Group clueless about the AI Boom?) Mild Shock <janburse@fastmail.fm> - 2025-03-07 23:58 +0100
    Re: ILP is still dreaming of higher order (Was: Prolog Education Group clueless about the AI Boom?) Mild Shock <janburse@fastmail.fm> - 2025-03-08 00:00 +0100
  FYI: Philip Zucker’s Co-Egraphs (Was: Prolog Education Group clueless about the AI Boom?) Mild Shock <janburse@fastmail.fm> - 2025-08-12 18:37 +0200
    Using Hopcroft & Karp (HK) everywhere (Was: FYI: Philip Zucker’s Co-Egraphs) Mild Shock <janburse@fastmail.fm> - 2025-08-14 12:31 +0200
      Confusing "decidable problem" and "complete algorithm" (Was: Using Hopcroft & Karp (HK) everywhere) Mild Shock <janburse@fastmail.fm> - 2025-08-14 14:31 +0200
        DFA algorithms in a Python library (Re: Confusing "decidable problem" and "complete algorithm") Mild Shock <janburse@fastmail.fm> - 2025-08-14 15:14 +0200
      Static Variable Shunting in Dogelog Player (Was: Using Hopcroft & Karp (HK) everywhere) Mild Shock <janburse@fastmail.fm> - 2025-08-16 11:22 +0200
        Dynamic Variable Shunting in WebPL (Was: Static Variable Shunting in Dogelog Player) Mild Shock <janburse@fastmail.fm> - 2025-08-16 11:34 +0200
          SWI-Prolog is still the OG of GC (Was: Dynamic Variable Shunting in WebPL) Mild Shock <janburse@fastmail.fm> - 2025-08-16 11:46 +0200
            Cyclic Term Unification is Accounted (Was: SWI-Prolog is still the OG of GC) Mild Shock <janburse@fastmail.fm> - 2025-08-16 11:59 +0200
            WebPL is an interesting project (Was: SWI-Prolog is still the OG of GC) Mild Shock <janburse@fastmail.fm> - 2025-08-17 18:00 +0200
              Head to Head Race with Scryer Prolog (Was: WebPL is an interesting project) Mild Shock <janburse@fastmail.fm> - 2025-08-17 18:24 +0200
                Does Variable Age make Sense? [Prolog Unification] (Was: Head to Head Race with Scryer Prolog) Mild Shock <janburse@fastmail.fm> - 2026-02-10 12:05 +0100
                Type systems for non-deterministic concurrency [Amir Pnueli] (Was: Does Variable Age make Sense? [Prolog Unification]) Mild Shock <janburse@fastmail.fm> - 2026-07-20 12:20 +0200
                Robin Milners fickle gives non-determinism in practice [Parallel π-WAM] (Was: Type systems for non-deterministic concurrency [Amir Pnueli]) Mild Shock <janburse@fastmail.fm> - 2026-07-20 12:34 +0200
  Sleepy Joe and the Poor South (Local AI Emacs Mode) (Re: Prolog Education Group clueless about the AI Boom?) Mild Shock <janburse@fastmail.fm> - 2025-11-12 12:59 +0100
    Beyond Sleepy Joe around the World (Was: Sleepy Joe and the Poor South (Local AI Emacs Mode)) Mild Shock <janburse@fastmail.fm> - 2025-11-12 13:12 +0100
  GENESIS MISSION: Loosing it over Deep Pokets [Business wants A-Life] (Was: Prolog Education Group clueless about the AI Boom?) Mild Shock <janburse@fastmail.fm> - 2025-11-26 18:07 +0100
  Vanilla Prolog: semi-decidable =\= decidable (Re: Prolog Education Group clueless about the AI Boom?) Mild Shock <janburse@fastmail.fm> - 2026-03-14 20:40 +0100
    Its on the Internet, so it must be true? (Was: Vanilla Prolog: semi-decidable =\= decidable) Mild Shock <janburse@fastmail.fm> - 2026-03-16 11:01 +0100
    Hack + Computed Goto = Leightweigh C_OR (Was: Vanilla Prolog: semi-decidable =\= decidable) Mild Shock <janburse@fastmail.fm> - 2026-07-04 16:58 +0200
      The stack and choice points as an after match (Re: Hack + Computed Goto = Leightweigh C_OR) Mild Shock <janburse@fastmail.fm> - 2026-07-04 17:07 +0200
        Introduction to AI Accelerator Prolog [π-WAM of Dogelog] (Was: The stack and choice points as an after match) Mild Shock <janburse@fastmail.fm> - 2026-07-17 10:49 +0200
          Not praying to the god of lambda calculus [π beats α] (Was: Introduction to AI Accelerator Prolog [π-WAM of Dogelog]) Mild Shock <janburse@fastmail.fm> - 2026-07-17 11:13 +0200
          pi in pi-WAM refers to pi-calculus (Re: Introduction to AI Accelerator Prolog [π-WAM of Dogelog]) Mild Shock <janburse@fastmail.fm> - 2026-07-18 01:22 +0200
            Milners fickle() in pi-WAM [For fun and profit] (Re: pi in pi-WAM refers to pi-calculus (Re: Introduction to AI Accelerator Prolog [π-WAM of Dogelog]) Mild Shock <janburse@fastmail.fm> - 2026-07-18 01:49 +0200
              Robin Milners pi calculus is typeless (Re: Milners fickle() in pi-WAM [For fun and profit]) Mild Shock <janburse@fastmail.fm> - 2026-07-18 11:00 +0200
                Can the Church Turing hypotheses be refuted? [TLo @ FOM] (Re: Robin Milners pi calculus is typeless) Mild Shock <janburse@fastmail.fm> - 2026-07-18 11:10 +0200
          Accelerate Lean! From Theorem 3.11 to Corollary 3.12 [ZMC] (Was: Introduction to AI Accelerator Prolog [π-WAM of Dogelog]) Mild Shock <janburse@fastmail.fm> - 2026-07-19 16:06 +0200
            ANN: Library Pegg, for π-E-graphs [Not EXWM] (Was: Accelerate Lean! From Theorem 3.11 to Corollary 3.12 [ZMC]) Mild Shock <janburse@fastmail.fm> - 2026-07-19 16:21 +0200
            Harmonic Analysis collides with Gabriels Horn [9-11 Math Incident] (Was: Accelerate Lean! From Theorem 3.11 to Corollary 3.12 [ZMC]) Mild Shock <janburse@fastmail.fm> - 2026-09-11 20:38 +0200
              Math has found a new Muse [Grothendieck Hodges] (Was: Harmonic Analysis collides with Gabriels Horn) Mild Shock <janburse@fastmail.fm> - 2026-09-12 11:26 +0200
                Kurzweils prognostic failure [Nabokov Fallacy] (Re: Math has found a new Muse [Grothendieck Hodges]) Mild Shock <janburse@fastmail.fm> - 2026-09-12 12:14 +0200
        From short-cut parallelism to true parallelism [π-WAM Musings] (Was: The stack and choice points as an after match) Mild Shock <janburse@fastmail.fm> - 2026-08-27 17:55 +0200

csiph-web