"high risk AI" needs documentation, Prologs bad examples

[Mostowski Collapse]

"high risk AI" might require documentation, Prologs
shows with really bad examples concerning Prolog VMs.

Example: The Albufeira Prolog Interpreter from 1983
https://www.swi-prolog.org/download/publications/A_Portable_Prolog_Compiler.pdf

The paper is extremly dense, leaves most of the stuff
as an exercise to the reader. It has some specification

in the form of Prolog code, which is mostly useless.

[Mostowski Collapse]

Why is the specification useless? Well to implement
a Prolog VM that consists of a Prolog loop, we might want
to see the following more clearly:

- State Transitions:
The state transitions of the abstract machine,
during the execution of a single instruction, and
not some tail recursive mash up

- Delayed Goals:
Also I doubt that the abstract machine of
the Albufeira Prolog Interpreter can deal with
delayed goals, which is part of SWI-Prolog.

SWI-Prolog claims to be based on the Albufeira Prolog
Interpreter, which might be true for the delayed goals
free part. For the delayed goals part on the other hand

I doubt that the shown specification would reflect
the wakeup machanism. The specification might wakeup
even non deterministic goals, during some of the

instructions, whereby SWI-Prolog possibly has some
boundaries. Can we nevertheless show the Prolog
Interpreter without delayed goals so that it shows state

transitions more clearly? Challenge, the state transition
must be deterministic, but nevertheless the Prolog VM
must be able to perform backtracking!

Who is up to this task?

[Mostowski Collapse]

Here is a take, replicating the “pop” instruction and only term
building and unification, and simulating a C memory
pointer as a pair I-Z:

step(atom(C), _, [I-Z|S], [J-Z|S]) :-
arg(I, Z, C),
J is I+1.
step(var(N), V, [I-Z|S], [J-Z|S]) :-
arg(N, V, W),
arg(I, Z, W),
J is I+1.
step(functor(F,A), _, [I-Z|S], [1-K,J-Z|S]) :-
arg(I, Z, K),
functor(K, F, A),
J is I+1.
step(pop, _, [_|S], S).

And then iteratively executing the steps:

exec([X|L], V, S, T) :-
step(X, V, S, H),
exec(L, V, H, T).
exec([], _, S, S).

Seems to work for term building, here f(a,g(b,W),W):

?- exec([functor(f, 3), atom(a), functor(g, 2),
atom(b), var(1), pop, var(1), pop], display(W),
[1-result(_)], L).
L = [2-result(f(a, g(b, W), W))]

Works also for unification, here f(a,g(b,W),W)=f(a,X,Y) success
and f(a,g(b,W),W)=f(X,Y) failure:

?- exec([functor(f, 3), atom(a), functor(g, 2),
atom(b), var(1), pop, var(1), pop], display(W),
[1-result(f(a,X,Y))], L).
W = Y,
X = g(b, Y),
L = [2-result(f(a, g(b, Y), Y))]

?- exec([functor(f, 3), atom(a), functor(g, 2),
atom(b), var(1), pop, var(1), pop], display(W),
[1-result(f(X,Y))], L).
No

Open source:

Modern Albufeira Prolog Interpreter
https://gist.github.com/jburse/9fd22e8c3e8de6148fbd341817538ef6#file-modern-pl

[Mostowski Collapse]

Got also already a half way compile predicate for Prolog
terms, will post when finished. Did not yet get my head
around about simple backtracking.

But some idea is already to introduce a further parameter
for the program counter. But will possibly keep the instruction
stream a Prolog list. Currently its only step/4, and subsequently

only exec/4. This seems to be sufficient for Prolog terms.
But when we start executing Prolog clauses, we might see
instruction stream switching. So the arity of step and

exec might increase. Some books about operational semantics
allow mixing different arity steps. We could also define a
Prolog interpreter having specialized steps for Prolog terms

and specialized steps for Prolog clause. See also:

Operational semantics - Small-step_semantics
=> for expressions and -> for statements
https://en.wikipedia.org/wiki/Operational_semantics#Small-step_semantics

Also this is an execellent book:

Concrete Semantics - With Isabelle/HOL
https://www.springer.com/de/book/9783319105413

[Mostowski Collapse]

But the SWI-Prolog discussion also related to the Prolog VM already
lost steam, after millions of accusations C is better than Prolog.

Bitcoin had flash crash. SWI-Prolog VM had a flash crush.

LoL

[Mostowski Collapse]

Ok, we got already half of the Albufeira Interpreter running via JavaScript.
In term building mode the Albufeira Interpreter reads as follows.

The Prolog simulator used arg/3 to write once the index and
compound pair, that simulates our memory pointers. In JavaScript
this did translate into target[index++], writing into a JavaScript array.

function exec(list, display) {
stack=null;
target=[null];
index=0;
i=0;
while (i<list.length) {
switch (list[i++]) {
case 0: // var(N)
target[index++]=deref(display[list[i++]]);
break;
case 1: // functor(F,A)
args=new Array(list[i++]);
target[index++]=new Compound(list[i++], args);
stack=new List(new List(target, index), stack);
target=args;
index=0;
break;
case 2: // atom(C)
target[index++]=list[i++];
break;
case 3: // pop
target=stack.head.head;
index=stack.head.tail;
stack=stack.tail;
break;
}
}
return target[0];
}

There is also exec2 for unification mode. This needs a little bit
more infrastructure, see also.

Prolog Terms in the Modern Albufeira Interpreter
https://gist.github.com/jburse/3a1c76130bca0549e425d07cdc47a5d9#gistcomment-3727780

[Mostowski Collapse]

It should be noted that the below does not
replicate the Jekejeke Prolog term building
and term unification, which uses a different

representation of variable, which uses a
pointer pair. At the expense of little more
copying the Albufeira Prolog variables,

the way we do it here, work only with one
pointer. We are embarking on a new adventure
to explore a take that considerable differs

from the "archaic" Jekejeke Prolog. Will have
a second post when intelligent backtracking for
the Albufeira Prolog interpreter is ready.

Mostowski Collapse schrieb:

[Mostowski Collapse]

The step/4 and exec/4 can be rewritten, so
that it uses native JavaScript stack, both
in building and unification mode,

this should be possible. Just execute the
code until the pop instruction and then return.
The pushed value is then some

recursive argument in calling things
recursively. Didn't do that yet, but this
will eliminate stack and the possibly

costly pushing via heap cells:

stack=new List(new List(target, index), stack);

Such program transformations can be explored
in the Prolog simulator and then recoded
in the hand written JavaScript interpreter.

Maybe its even possibly to generate the
JavaScript interpreter automatically from
Prolog and some modes? Ok, I am not that

lazy that I would need that. So I am playing
manually the savy assembler for the JavaScript
version of the Prolog interpreter loop.

Mostowski Collapse schrieb:

[Mostowski Collapse]

Should name this Prolog "Dogelog".

DOGE, in a blink from 0.30 to 0.35:
https://coinmarketcap.com/de/currencies/dogecoin/

But I don't know yet whether this Prolog will be a total desaster.

LoL

[Mostowski Collapse]

But I know already which a first test case I want
to run with this Prolog system, namely this Ackerman
graph. There was critique about Prolog systems that

they are not good for graph algorithms. Since a graph
can be naturally represented by some C pointers. But
this can be challenged, what if the graph is

itself a function?

edge(ack(X, ack(Y, Z)), ack(X, H)) :- !, edge(ack(Y, Z), H).
edge(ack(0, N), X) :- !, X is N+1.
edge(ack(M, 0), ack(H, 1)) :- !, H is M-1.
edge(ack(M, N), ack(H, ack(M, J))) :- H is M-1, J is N-1.

depth(ack(X, Y), N, M) :- !,
edge(ack(X, Y), H),
J is N+1,
depth(H, J, M).
depth(_, N, N).

Example expected result:

?- depth(ack(3,4), 0, N).
N = 10307.

Can your Prolog system do it?

[Mostowski Collapse]

Ok, intelligent backtracking is here:

The main routine solve() is a call and redo trampoline. The
call points to the current goal list. This goal list gets advanced
whenever there is a success. A success might also change the

choice point list which is stored in redo. This is curtesy of the
routine solve2() and not shown here. But a choice point is only
created for a non last clause:

function solve(found) {
for(;;) {
if (found) {
if (is_compound(call)) {
var goal=call.args[0];
var list=kb[goal.functor][goal.args.length];
found=solve2(list, 0);
} else {
break;
}
} else {
if (redo) {
var choice=redo.head;
redo=redo.tail;
unbind(choice.tail.head);
call=choice.tail.tail;
found=solve2(choice.head.head, choice.head.tail);
} else {
break;
}
}
}
return found;
}

See also:

Prolog Solve in the Modern Albufeira Interpreter
https://gist.github.com/jburse/3a1c76130bca0549e425d07cdc47a5d9#gistcomment-3728006

[Mostowski Collapse]

We are now deliberating whether we can compile
our compiler, add some term reader, and eh voilà
we would have a a little complete pure Prolog

interpeter that can be embedded in HTML pages.
We will post more about the modern Albufeira
Interpreter when we did this bootstrapping stunt.

It will not yet answer our utter most couriosity,
namely how JavaScript JIT-ing might effect Prolog
execution. For this purpose we should more natively

compile or compile into web assembly.
Only then we would see an effect.

Mostowski Collapse schrieb:

[Mostowski Collapse]

Now I have also a solution that can do a cut (!).
But what is lacking is a good idea to do garbage
collection over the trail.

I have garbage collection over the trail in my
"archaic" system, in an exact way. But somehow I
am too lazy right now to think about

garbage collection for the Albufeira Prolog Interpreter.
Could compare with what SWI-Prolog does and maybe
try to bring it to JavaScript. But since my "archaic"

system can also do it, there is a kind of impasse.
What was funny was how I did cut. Might blog about it
later, since I have anyway a cut related ticket in my

own system, and this gives some brain food.
So kind of shelving the Albufeira Interpreter.

[Mostowski Collapse]

Lets say we implement a simple mark and sweep for the JavaScript
interpreter. Then we have not to bother with what is on the heap,
since JavaScript should be able to deal with that.

All we need to consider is the bound variables, luckly, not
like in my "archaic" system, the current take has no pointers into
the display. So we might do the following:

- mark phase, we could simply mark all variables use by the current call,
and the calls in the choice points. Keeping this data intact is the integrity
that is needed to keep the Prolog interpreter running.

- sweep phase, then we would walk along the trail, and remove
trail entries to variables that were not marked. But our choice points
have also trail pointers, these need to be locked or updated.

In the ackerman example, there wouldn't be any choice points, so
the whole trail gets reclaimed. But otherwise marking the variables
from calls in the choice points can be tricky, since they have overlapping

tails, so we might want something smarter to avoid double work.

[Mostowski Collapse]

Ok a simple mark and sweep works, and
a simple trigger mechanism does the job:

ANN: Dogelog Runtime, Prolog to the Moon (2021)
https://qiita.com/j4n_bur53/items/17f86429745426bd14fd

And we are 10x times faster than TauProlog! LoL
Here are benchmark results:

- TauProlog Benchmark:
We made ourselfs comfortable with the TauProlog API. They required us to
code a lot of call backs. We realized a logic that did try to execute
Peano factorials up to 10. But somehow TauProlog gave silently up at 7.
TauProlog Benchmark results are here.
https://gist.github.com/jburse/5b7d8e03308b2852e8f7135b1610d319#gistcomment-3728350

- Dogelog GC Demo:
The Dogelog API doesn't use inverted programming. The Prolog interpreter
is viewed as an iterator that can be asked for a next solution. The
Dogelog runtime is able to reach Prolog factorial 10 in a Chrome browser.
Dogelog GC Demo results are here.
https://gist.github.com/jburse/5b7d8e03308b2852e8f7135b1610d319#file-demo5-html

[Mostowski Collapse]

Corr.:

Dogelog GC Demo:
The Dogelog API doesn't use inverted programming. The Prolog interpreter
is viewed as an iterator that can be asked for a next solution. The
Dogelog runtime is able to reach Prolog factorial 10 in a Chrome browser.
Dogelog GC Demo results are here.

https://gist.github.com/jburse/5b7d8e03308b2852e8f7135b1610d319#gistcomment-3728353

We are mostly interested in the JIT-ing capabilities of JavaScript. So we
will need a future version of Dogelog that compiles closer to the metal,
either JavaScript code or even maybe Webassembly code. For this project
we will have to look again at the many ideas from the Albufeira instruction set.

[Mostowski Collapse]

Some morning shower thoughts:

- Clause Indexing
I am still flabbergasted that Peano runs reasonably fast. Since the
Dogelog runtime has no clause indexing yet. So it will leave
quite a bunch of choice points nevertheless. But how do
clause indexing? We might use JavaScript Object itself.

- Last Functor:
The Albufeira paper mentions a last functor instruction,
a slight optimization to the state machine while executing
the term building/unification instructions. Again flabbergasted
that Peano runs reasonably fast without these optimizations.

- Delayed Goals:
The "call" and "redo" trampolin is easy to extend by
delayed goals. We might do a prototype for Dogelog that
has freeze and friends, maybe some little constraint solver.

- Shift Reset:
Its not clear whether shift/reset is more or less complex.
We do not yet have it in our own "archaic" take, only a meta
interpreter prototype. Could then implement SLG tabling.
But other tabling might also be an option to explore.

- Code Quality:
This is a problem while writing JavaScript. Should we rather
use some Java to JavaScript transpiler. Or something like
TypeScript, what does it even offer?

- Class Hierarchie:
We use some primitive List(List()) construction for the
many datastructures used in the interpreter. We could replace
these by their own constructors.

- Built-Ins:
In as far we could also introduce an abstract class for
built-ins. As a first take make '$CUT'/1 a built-in, explore
dispatch into built-in. And later add quite a couple of
built-ins to the Dogelog runtime.

- Bootstrapping Read:
We might consider a term reader which only realizes
the ASCII subset of ISO core standard. And boostrap
cross compile it as Prolog code, with a minimum of built-ins

- GitHub Repository:
We might make a github repository for dogelog,
and continue elaborating changes via GitHub tickets,
so this might be the last post here with some musing
about Dogelog.

- What else?

[Mostowski Collapse]

Ok new plan is to make Dogelog a Jekejeke Prolog pack, and
keep the cross compiler intact. A scenario could also be
a server side compilation while delivering a HTML page,

instead a future client side compilation. So best have
server and future client compilation in sync and both intact.
There is now a new GitHub label "JavaScript":

Hello darkness my old friend, Dogelog variable ordering #32
Is Dogelog a good boy, where is the stack trace? #31
Tail recursive term_atom for Dogelog #30
Provide Dogelog disjunction and if-then-else #28
Provide Dogelog meta-calls #27
Provide Dogelog query compilation #26
Create a Dogelog pack #29
https://github.com/jburse/jekejeke-samples/issues

[Mostowski Collapse]

Now I found a more detailed paper about ZIP.
Its quite a jevel, since in the intro it delivers a snapshot
of the other systems floating around at that time:

Design and simulation of a sequential Prolog machine - Clocksin, 1984
http://www.softwarepreservation.org/projects/prolog/edinburgh/doc/Clocksin-Design_and_Simulation_of_a_SPM-1984.pdf

Practically ignored ZIP all the years. I wonder how
much of this went into SWI-Prolog? Will ask, since
I might get hit by a van next day, so need to hurry,

asking the right questions. On the other hand, when
I am six feet under, I wouldn't give a flying fuck. So
no, its for the living, not for the dead.

[Mostowski Collapse]

This Prolog-X based on ZIP is not the same as SWI-Prolog.
It has 3 different pop instructions. pop, popmatch, poparg.

But SWI-Prolog has H_POP and B_POP.
Or maybe SWI-Prolog has more pops?

Mostowski Collapse schrieb:

[Mostowski Collapse]

In our Dogelog explorations, we do not include a simulator anymore.
Since they code will get more and more complex, and we focus
on realizing the JavaScript interpreter instead running the simulator.

The simulator will be also not in need for future call/1 which will
be rather compiled than simulated. But I am still in learning mode,
kind of long life learning. The ZIP machine, which forms the basis

for SWI-Prolog, seems to be quite influential. It is also referenced
in “A History of Erlang”, by Joe Armstrong. And the 19 citations
mentioned on Research Gate, read like the Who-is-Who of Prolog.

http://cobweb.cs.uga.edu/~maria/classes/4500-Spring-2010/papers/ErlangHistory.pdf

https://www.researchgate.net/publication/273888197