shortest solution to Einstein's Riddle

[Mark Tarver]

I've seen a few versions of this. What, in your opinion, is the the shortest Prolog solution to this problem - with the original problem in English?

Mark

[Mostowski Collapse]

I dont know whats the shortest, but "marlboro" possibly comes
from Bill Clementson, Allegro Prolog, a Prolog embedded in Allegro CL:

https://www.artima.com/forums/flat.jsp?forum=122&thread=71585

[Mark Tarver]

Ah; that's where I got the code! I didn't have the English to this program so I rewrote the program wrt a version I picked up over the internet

the Brit lives in the red house
the Swede keeps dogs as pets
the Dane drinks tea
the green house is on the left of the white house
the green house's owner drinks coffee
the person who smokes Pall Mall rears birds
the owner of the yellow house smokes Dunhill
the man living in the centre house drinks milk
the Norwegian lives in the first house
the man who smokes Blends lives next to the one who keeps cats
the man who keeps horses lives next to the man who smokes Dunhill
the owner who smokes BlueMaster drinks beer
the German smokes Prince
the Norwegian lives next to the blue house
the man who smokes Blend has a neighbour who drinks water

The question is: who owns the fish?

In Shen Prolog this problem is written

(defprolog riddle
<-- (house A) (house B) (house C) (house D) (house E) (is Houses [A B C D E])
(member [brit _ _ _ red] Houses)
(member [swede dog _ _ _] Houses)
(member [dane _ _ tea _] Houses)
(left [_ _ _ _ green] [_ _ _ _ white] Houses)
(member [_ _ _ coffee green] Houses)
(member [_ bird pallmall _ _] Houses)
(member [_ _ dunhill _ yellow] Houses)
(is C [_ _ _ milk _])
(is A [norwegian _ _ _ _])
(next [_ _ blends _ _] [_ cat _ _ _] Houses)
(next [_ horse _ _ _] [_ _ dunhill _ _] Houses)
(member [_ _ bluemaster beer _] Houses)
(member [german _ prince _ _] Houses)
(next [norwegian _ _ _ _] [_ _ _ _ blue] Houses)
(next [_ _ blends _ _] [_ _ _ water _] Houses)
(who-owns-the-fish? Nationality Houses);)

(defprolog member
X (- [X | _]) <--;
X (- [_ | Z]) <-- (member X Z);)

(defprolog house
[Nationality Pet Cigarette Drink Colour] <--;)

(defprolog next
X Y List <-- (left X Y List);
X Y List <-- (left Y X List);)
 
(defprolog left
L R (- [L R | _]) <--;
L R (- [_ | Houses]) <-- (left L R Houses);)

(defprolog who-owns-the-fish?
Nationality Houses <-- (member [Nationality fish _ _ _] Houses)
(return Nationality);)

It's pretty easy to translate this into Edinburgh syntax.

Mark

[Mostowski Collapse]

Now there is also a version with "luckystrike":

========== zebra.pl
/* -*- Mode: prolog -*-
*
* This file for benchmarking against SWI Prolog.
*/
nextto(X, Y, List) :- iright(X, Y, List).
nextto(X, Y, List) :- iright(Y, X, List).
iright(Left, Right, [Left, Right | _]).
iright(Left, Right, [_ | Rest]) :- iright(Left, Right, Rest).
zebra(H, W, Z) :-
H = [house(norwegian, _, _, _, _), _, house(_, _, _, milk, _), _, _],
member(house(englishman, _, _, _, red), H),
member(house(spaniard, dog, _, _, _), H),
member(house(_, _, _, coffee, green), H),
member(house(ukrainian, _, _, tea, _), H),
iright(house(_, _, _, _, ivory), house(_, _, _, _, green), H),
member(house(_, snails, winston, _, _), H),
member(house(_, _, kools, _, yellow), H),
nextto(house(_, _, chesterfield, _, _), house(_, fox, _, _, _), H),
nextto(house(_, _, kools, _, _), house(_, horse, _, _, _), H),
member(house(_, _, luckystrike, oj, _), H),
member(house(japanese, _, parliaments, _, _), H),
nextto(house(norwegian, _, _, _, _), house(_, _, _, _, blue), H),
member(house(W, _, _, water, _), H),
member(house(Z, zebra, _, _, _), H).
/* This runs the query a single time:
* ?- zebra(Houses, WaterDrinker, ZebraOwner).
*/

Seems they used it for benchmarking:

zebra1(Houses, WaterDrinker, ZebraOwner) :-
zebra(Houses, WaterDrinker, ZebraOwner), !.
benchmark1 :-
flag(benchmark,_,0),
repeat,
zebra1(Houses, WaterDrinker, ZebraOwner),
flag(benchmark,N,N+1),
N = 1000,
!.
benchmark :- time(benchmark1).

https://franz.com/support/documentation/current/doc/prolog.html

[Mark Tarver]

One interesting feature of this problem - and you don't appreciate it unless you have the English to hand -
is that the original formulation of the facts does not mention fish at all. So the question is answered by a process
of elimination in which 'fish' is unified to a variable. It should work for any animal not mentioned - the German has
quite a menagerie. It really is custom made for showing the power of Prolog.

Here are the contents of the houses (derived by adding (member [_ fish _ _ _] Houses) (return Houses) to the literals
in riddle.

(pprint (prolog? (riddle)))
[
[norwegian cat dunhill water yellow]
[dane horse blends tea blue]
[brit bird pallmall milk red]
[german fish prince coffee green]
[swede dog bluemaster beer white]]

In Edinburgh syntax

riddle() :-
house(A), house(B), house(C), house(D), house(E), Houses = [A, B, C, D, E],
member([brit, _, _, _, red], Houses),
member([swede, dog, _, _, _], Houses),
member([dane, _, _, tea, _], Houses),
left([_, _, _, _, green], [_, _, _, _, white], Houses),
member([_, _, _, coffee, green], Houses),
member([_, bird, pallmall, _, _], Houses),
member([_, _, dunhill, _, yellow], Houses),
C = [_, _, _, milk, _],
A = [norwegian, _, _, _, _],
next([_, _, blends, _, _], [_, cat, _, _, _], Houses),
next([_, horse, _, _, _], [_, _, dunhill, _, _], Houses),
member([_, _, bluemaster, beer, _], Houses),
member([german, _, prince, _, _], Houses),
next([norwegian, _, _, _, _], [_, _, _, _, blue], Houses),
next([_, _, blends, _, _], [_, _, _, water, _], Houses),
member([_, fish, _, _, _], Houses),
print(Houses).

house([Nationality, Pet, Cigarette, Drink, Colour]).

next(X, Y, List) :- left(X, Y, List).
next(X, Y, List) :- left(Y, X, List).

left(L, R, [L, R | _]).
left(L, R, [_ | Houses]) :- left(L, R, Houses).

Mark

[Mostowski Collapse]

The house/1 fact looks unecessary to me.
Maybe you should lookup the French version as well.
I am pretty sure you can make it run without house/1

in Prolog ISO core standard. Not sure about
Edinburgh syntax. But zebra.pl from Franz Lisp
doesn't have house/1, so I guess its **shorter**.

Mark Tarver schrieb am Montag, 8. März 2021 um 11:46:21 UTC+1:
> house([Nationality, Pet, Cigarette, Drink, Colour]).

[Mostowski Collapse]

Turbo Prolog has a quite crazy solution with a lot of (<>)/2:

qui appartient le zèbre?
https://www.epi.asso.fr/fic_pdf/b58p205.pdf

And this one doesn't reduce est_voisin_de to est_a_droite_de:

"Qui a le zèbre ?"
http://www.gecif.net/articles/linux/prolog.html#exemple3

So I guess zebra.pl from Franz Lisp is still the shortest.

[Mostowski Collapse]

How do I put the thingy into a file and then run zebra/3
a 1000 times? Is there a between/3 in Shen?

In SWI-Prolog I can do with zebra.pl, I am using a zebra.pl
with member/2 also implemented in Prolog, not using
a system implementation. My Prolog system cannot do

it that fast as SWI-Prolog. I am still investigating to
reach SWI-Prolog performance, my system chokes on
this example and is 3x times slower:

/* SWI-Prolog (threaded, 64 bits, version 8.3.20) */

?- ensure_loaded('C:\\Projects\\Jekejeke\\Prototyping\\experiment\\other\\diffuse\\swi\\owl3\\zebra.pl').
true.

?- time((between(1,1000,_), zebra(_,_,_), fail; true)).
% 29,272,003 inferences, 2.984 CPU in 2.974 seconds (100% CPU, 9808420 Lips)
true.

I tried in Shen:

/* Shen, copyright (C) 2010-2015 Mark Tarver */

(1-) (time time)

run time: 0.000000 secs
time

So there is a time routine. But then I am lost. And Shen in 15min
didn't help me either, this here http://shenlanguage.org/shenin15min.htm

But downloading Shen from here https://github.com/doublec/shen-wasp/releases
was ok. Used shen.zip on Windows. But the link here http://shenlanguage.org/download.htm
doesn't point to the latest download.

[Mark Tarver]

Since 2016 the work of OS maintenance and development has been taken over by members of the 2011 committee in the Shen Language Open Source Community. That does not include me BTW; I stepped down in 2015 and the work has been taken over by others. I'm using the closed source version SP30.

Shen Prolog is an embedded Prolog that runs under a very small instruction set which allowed it to be ported to 15 different languages. It also defaults to
occurs-check unification because it is used for automated deduction in type checking. These facts mean it does not run as quickly as stand-alone Prologs.

On my 4.7GHz desktop machine under SP30 this is what I get

(9-) (time (prolog? (riddle)))
run time: 0.06200003623962402 secs
german

in 33,542 inferences - about 540 KLips. In SWI Prolog I get

% 20,795 inferences, 0.016 CPU in 0.006 seconds (260% CPU, 1333004 Lips)

Mark

[Mostowski Collapse]

Can you run it a 100x times? 16ms is the granularity of walltime on
some systems, so it could be also 32ms or 0ms. The LIPS

of SWI-Prolog should be ca. 10'000'000 LIPS and not only
1'333004 LIPS, thats abnormally low, or old 32-bit SWI, I dunno.

Also I get on my desktop:

Mostowski Collapse schrieb am Dienstag, 9. März 2021 um 11:40:39 UTC+1:
> /* SWI-Prolog (threaded, 64 bits, version 8.3.20) */

> ?- time((between(1,1000,_), zebra(_,_,_), fail; true)).
> % 29,272,003 inferences, 2.984 CPU in 2.974 seconds (100% CPU, 9808420 Lips)
> true.

You see its 10x times faster, since it has 9808420 Lips, despite
that my desktop is only 2.6GHz. What would be the Shen equivalent

of loading Edinburgh syntax? Is this possible?

[Mostowski Collapse]

Also the 260% CPU in the SWI-Prolog measurements indicates
some abnormality. Should be 100% CPU with slight variation,

unless you run multiple threads.

[Mark Tarver]

For me I get 4,849,773 Lips for 1000 iterations in SWI Prolog
and 4,429,459 Lips for 50 iterations

for Shen Prolog/SBCL 600 KLips for 50 iterations

1000 iterations would require resetting the vector memory to a larger size.

Shen Prolog/SBCL is Shen Prolog under SBCL btw - one of 15 platforms.

Mark

[Mark Tarver]

SBCL/Shen is not the fastest version btw - that is likely Chez Scheme/Shen which
would probably clock about 1.8 MLips. However SP30 is a new version and has not been
ported yet to Chez Scheme.

Welcome to SWI-Prolog (threaded, 64 bits, version 7.4.2)
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software.
Please run ?- license. for legal details.

is what I get on startup.

Mark

[Mostowski Collapse]

I remember some example on sci.math.symbolic, running a computer
algebra system on different versions of lisp. SBCL was the fastest,
like 10x times faster than another lisp system.

But I don't know whether these differences also apply to Shen.
Why do you need a larger vector for a higher iteration? This iteration
here is a failure loop, shouldn't eat any memory:

Mostowski Collapse schrieb am Dienstag, 9. März 2021 um 11:40:39 UTC+1:
> /* SWI-Prolog (threaded, 64 bits, version 8.3.20) */
> ?- time((between(1,1000,_), zebra(_,_,_), fail; true)).
> % 29,272,003 inferences, 2.984 CPU in 2.974 seconds (100% CPU, 9808420 Lips)
> true.

The failure loop is:

between(1,1000,_),
zebra(_,_,_),
fail; true.

So all the bindings and stuff of zebra/3 should be freeed when
backtracking to between/3 and when a new interation is started.
But admittedly, this freeing can cause garbage.

In my Prolog system the freeing is left to the Java GC, and
subsequently performance depends on how good Java GC can
deal with first generation garbage. But JDK 1.8 does an ok job.

[Mostowski Collapse]

I have uploaded source code of zebra.pl and screenshots
to gist. Zebra is still a chanllenge for Jekejeke Prolog, estimated
Logical Inferences per Second (LIPS) for Jekejeke Prolog:

10'766'713 LIPS / 9'180 ms * 2'724 ms = 3'194'828 LIPS

Open source:

Allegro Prolog version of Einstein's Riddle
https://gist.github.com/jburse/dbd654073621f21333e3e4dbd330a30d#file-zebra-pl

SWI-Prolog 8.3.20 Measurement
Jekejeke Prolog 1.5.0 Measurement
https://gist.github.com/jburse/dbd654073621f21333e3e4dbd330a30d#gistcomment-3660084

BTW: A nasty test is set_prolog_flag(occurs_check, true) for Zebra.
I get overhead SWI-Prolog 116%, Jekejeke Prolog 108%. At least
something where we can beat SWI-Prolog currently. LoL

[Mostowski Collapse]

Does Shen have unify_with_occurs_check/2 or a Prolog
flag occurs_check. I have recently compile a couple
of benchmarks for the occurs check. They are:

Peano Arithmetic Factorial
http://www.jekejeke.ch/idatab/doclet/prod/en/docs/05_run/15_stdy/12_occurs/08_tests/01_peano.html

Code Linter List Types
http://www.jekejeke.ch/idatab/doclet/prod/en/docs/05_run/15_stdy/12_occurs/08_tests/02_check.html

Beckert & Posegga's Algorithm
http://www.jekejeke.ch/idatab/doclet/prod/en/docs/05_run/15_stdy/12_occurs/08_tests/03_aristo.html

They all make essential use of the occurs check. Could
Shen run them correctly?

[Mostowski Collapse]

Isn't ISO core standard just Edinburgh syntax with a few
predicate repertoire standardizations? Check for yourself:

Prolog Programming in Depth - Covington et al. 1997
Appendix: Summary of ISO Prolog
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.139.8870&rep=rep1&type=pdf

Mark Tarver schrieb am Montag, 8. März 2021 um 00:24:12 UTC+1:

[Mark Tarver]

Shen Prolog has a core of 11 primitive predicates including !, findall, call, var? and is,
but no library since it is embedded in a functional language.

It does have the capacity to call functions within Horn clauses and has optimisation directives
for dereferencing and swapping unification for pattern matching.

Mark

[Mostowski Collapse]

What happens if you do (transcripted to Shen language,
don't know what it will be):

?- X = f(X).

Or what happens if you do (again transcripted to Shen language,
don't know what it will be):

?- X = f(X), acyclic_term(X).

(acyclic_term/1 is Corr.2 8.3.11.4 of ISO standard,
https://www.complang.tuwien.ac.at/ulrich/iso-prolog/dtc2#acyclic_term)

[Mark Tarver]

(prolog? (is X [f X]))
true

that is unification w.o. an occurs check

(prolog? (is! X [f X]))
false

that's unification with an occurs check.

The difference comes when you try to dereference X which is what happens you use 'return' to get the value.
In that case you will get an infinite loop.

Shen uses lazy dereferencing within Prolog unless required which means that dereferencing is carried out only to the
extent needed to match to the Horn clause. So a cyclic binding can be carried around.

Mark

[Mostowski Collapse]

After success of this query:

?- X = f(X).

Dereferencing X gives only f(X), and then dereferencing should
stop. Or does Shen have a different notion of dereferencing?

Do you mean term traversal, like for printing? Or do you mean
term copy? What does Shen do here:

?- X = f(X), Y = f(Y), X = Y.

[Mostowski Collapse]

I am asking because you wrote: "The difference comes when you try to

dereference X which is what happens you use 'return' to get the value.

In that case you will get an infinite loop.".

The typicall Prolog deref() of a logical variable should not go into an
infinite loop when applied to X after sucess of the query "?- X = f(X)",
thats why in most Prolog systems you can safely do:

?- X = f(X), var(X).
false

Even in Prolog systems that do not have rational term aka cyclic term
unification. Usually the var/1 predication needs to dereference to check
the type of its argument.

Possibly the infinite loop is caused by get the value, that involves
more than dereferencing I guess.

[Mark Tarver]

You can do the same in Shen Prolog

(prolog? (is X [f X]) (var? X))
false

full or eager dereferencing is only applied within return and by default within
function calls in Horn clauses. There are compiler directives which can change
this behaviour.

Mark

[Mostowski Collapse]

I am using acyclic_term/1 for poor mans cyclic term
handling. To allow the end user to walk to the point where
a cyclic term happens, without making the Prolog system

crash. The pattern is relatively trivial. Once a predicate
acyclic_term/1 is available, that can traverse a potentially
cyclic term without an infinite loop, and determine

whether it is cyclic or not, one can use it via this idiom:

show_answer(T) :- acyclic_term(T), !,
write(T).
show_answer(_) :-
write('<cyclic term>').

Here is an example. Currently I have not everywhere this
sanity check, since one might not want it everywhere. Only the
top-level and the debugger has it. So the top-level does:

?- X = f(X).
X = <cyclic term>

And the debugger has it, was adding it today:

?- trace.
Yes
?- X = f(X).
0 Call X = f(X) ?
0 Exit <cyclic term> ?
X = <cyclic term>

Does Shen have a debugger? Other Prolog systems go to the
length to find a factoring of a cyclic term, and show this factoring.
But since the intended execution mode is occurs_check = true,

I rather don't support that.

[Mostowski Collapse]

Unlike unify_with_occurs_check/2, which can be implemented
in Prolog itself, acyclic_term/2 cannot be implemented in Prolog
itself when cyclic term unification isn't available. Right?

[Mostowski Collapse]

You still didn't explain why you call it dereferencing,
and what it should mean. Usually lazy dereferencing
leads to less performance.

SWI-Prolog had a bug, [Apr 25 2020], in bagof/3 and setof/3
because of some missing dereferencing or somesuch which
made it extremly slow. So every missed opportunity of

dereferencing, and storing logical variables that are not
dereferenced, potentially increases the length of dereferencing
path, and therefore causes troubles.

So lazy dereferencing is rather an anti-pattern for Prolog.
Especially the parameter passing, implicit in head to
goal unification, needs to be scrutinized.

[Mostowski Collapse]

lazy dereferencing, if you mean variable to instantiated
term dereferencing, which might have multiple hops,
mirrors problems in garbage collection with degradation

in performance. If there are long chains of undereferenced
variables, then this could be also indicative of a lot of garbage.
If I remember well in the SWI-Prolog bug, this was also seen.

It did not only become slow, but also resource hungry!

So if you want to create little monsters, deploy lazy
dereferencing. You might increase your LIPS with more
aggressive dereferencing. This is especially true for Prolog

systems that rely on the Java GC, like my Prolog system does.
I found myself doing a small reordering recently, with the
effect that something was more earlier potentially GCed,

just some commutative move. And woops performance got
up. It was a move where not really more memory was released
in total or less time was spend in total, only some reordering

to to something more early. And peng performance goes up!

[Mark Tarver]

dereferencing means following a pointer from a variable to its value. Lazy dereferencing follows
the pointer only as far as is needed to find a non-variable value if it exists which is sufficient for
Shen Prolog execution w.o. function calls. Eager dereferencing means you extract the full binding.
Lazy dereferencing is actually very fast.

Mark

[Mostowski Collapse]

I dont find a single paper or book that uses the term "eager dereferencing".
What is a "full binding"? Usually a variable is either bound or unbound, what
do you mean by fully bound? Do you refer to delayed goals?

Can you make an example? An example could be helpful...

[Mostowski Collapse]

Dereferencing is for example defined here in
section 3.1 Emulator Macros:

/* primitive Prolog operations */
# define deref(x) {int t; while(IsRef(x) && (t=x,x=*t,t!=x));}
https://ntrs.nasa.gov/api/citations/19930074153/downloads/19930074153.pdf

Or here:

function deref(a: address): address;
http://www.inf.tu-dresden.de/content/institutes/ki/cl/study/summer09/ils/slides/2_Prolog2.pdf

In the first paper an unbound variable is indicated by a self
reference. Dunno, could be that Scryer Prolog still does the same?
Even the second paper also interprets unbound variables this

way. In my Prolog system I use a null pointer to indicate that
a variable is unbound. This is less costly in Java, since objects
are created with intialized memory, not some random memory

in Java, and the default for an object pointer is null. But I
wonder what you want to do lazily or eager? And what would
be a full binding?

[Mark Tarver]

Here is naive reverse in Shen Prolog.

(defprolog nreverse
(- []) [] <--;
(- [X | Y]) R <-- (nreverse Y RY) (nappend RY [X] R);)

(defprolog nappend
(- []) X X <--;
(- [X | Y]) Z [X | W] <-- (nappend Y Z W);)

Running this with N = 100 + occurs-check takes 0.075s and 49,700 inferences
about 660 KLips.

Running it with the occurs-check flag turned off takes 0.048s and takes us
a tad over 1 MLip (1.03).

Running it with mode declarations put in + no occurs check - about 0.02s or
2.48 MLips.

This is under Shen/SBCL with a 4.7GHz processor. Increasing to N = 1000 shows the same Lips.

The technology is actually quite developed; I'm in the process of writing it up and it should be published
next month. The whole documentation is 500 pages of which Shen Prolog is a small part.

Shen Prolog is not ISO standard; it is designed to work as part of a larger whole and be super portable
(hence the many platforms).

The Prolog compiler is 469 loc of Shen.

Mark

[Mark Tarver]

what is meant by lazy is that one does not do work that may be wasted, so the object attached to
the variable is only unravelled wrt its structure as much as is needed to allow the computation to proceed

Mark

[Mostowski Collapse]

But then you have lazy compounds and not lazy variables. But
what do you want to unravel of a compound? Thats not a concept
from Prolog? Or do you intend this as an alternative mechanism

for delayed goals. Here is a lazy thunk in Prolog via freeze,
assume 99 is a costly computation, that might or might not
be needed. freeze is related to attributed variables.

SWI-Prolog (threaded, 64 bits, version 8.3.20)

?- freeze(X, (X=thunk(Z), write('calculemus'), nl, Z is 99)).
freeze(X, (X=thunk(Z), write(calculemus), nl, Z is 99)).

?- freeze(X, (X=thunk(Z), write('calculemus'), nl, Z is 99)), X=thunk(Y).
calculemus
X = thunk(99),
Z = Y, Y = 99.

Do you mean attributed variables by lazy dereferencing?
Could you make an example of your eager and lazy dereferencing?

[Mostowski Collapse]

The mechanims of attributed variables is not dereferencing,
because in Prolog you cannot trigger an attributed variable
through dereferencing. Its unification what triggers an attributed

variable, namely binding it to something else which is
either a compound or also an attributed variable. But dereferencing
stops at unbound attributed variables like it stops at unbound

ordinary variables. You cannot invoke a thunk through dereferencing.

[Mostowski Collapse]

Its good that Shen has an occurs check flag it seems!
Better would be also Edinburgh syntax, istead of (is A B)
when it means (= A B). But anyway, I get, for the occurs

check overhead, of naive reverse:

Shen: 0.075s / 0.048s = 156%
SWI-Prolog: 146%
Jekejeke Prolog: 109%

But absolutely I cannot yet beat SWI-Prolog, :-( .
naive reverse and Einsteins riddle are both challengers.
SWI-Prolog deploys some list branching, and

maybe some clever tail recursion. Dunno. Einsteins
riddle and naive reverse have both those tiny list
operations, that perform quite ok in SWI-Prolog.

[Mostowski Collapse]

P.S. lower overhead is better. If the ratio is ca. 100%,
then you can practically run with occurs_check=true.
There are also reported cases where occurs_check=true

is faster than an explicit unify_with_occurs_check/2.
But I never tried explicit unify_with_occurs_check/2 with
naive reverse. A case where occurs_check=true is

considerably faster than explicit unify_with_occurs_check/2
is the Scheme Quine:

Pure Prolog Scheme Quine
https://qiita.com/j4n_bur53/items/7e1cc1b8bf92e501aff3

Would this be something that can be solved by lazy
dereferencing in Shen. The above makes use of delayed
goals via freeze/2 and also dif/2 is used to delay.

[Mark Tarver]

On Friday, 12 March 2021 at 02:14:08 UTC, burs...@gmail.com wrote:
> Its good that Shen has an occurs check flag it seems!

It's easy to add so why not. Occurs check is OTT for many problems.

> Better would be also Edinburgh syntax, instead of (is A B)
> when it means (= A B). But anyway, I get, for the occurs.

Well Shen is actually a sort of super Lisp so it adopts a syntax for Prolog
that is conformant to its syntax. Even the [...]s are actually shorthands
for (cons ....) (eg. [1 2] is (cons 1 (cons 2 ())) ). So writing metaprograms
that generate Prolog is easier. = is reserved in Shen for equality.

Probably a compiler from Edinburgh syntax would be useful though Shen Prolog
is very minimal wrt primitives. It is not ISO standard.

It's very difficult, probably practically impossible, to beat a standalone Prolog
implemented in (e.g.) C wrt Lips. I'd say the one to beat is Sicstus which clocks
they say 134MLips on a 2.8GHz machine on naïve reverse. Shen Prolog
sacrifices speed to portability.

But in my book I conclude the chapter on compiling Prolog with this conclusion

These speeds all come down to the optimisation of low level Prolog operations
in languages like C, assembly and machine code (and the avoidance of occurs-check unification).
Going down to the metal on these operations is the key to performance. That's why purpose-built
Prologs are faster than ones built in high level languages like Shen. But this focus on Lips misses
two important points.

The first came from the lessons of the Fifth Generation Initiative project when the Japanese tried to
base their programming development on Prolog. They found Prolog was amazing at certain kinds of
problems requiring deduction, but it was missing ways of storing data in forms other than clauses.
For this reason the modern approach is to embed Prolog within a programming environment.

The second point is that speed in Lips is not an accurate measure of the speed of embedded Prolog
programs. Shen Prolog gives the ability to reach down into Shen to tackle those problems which are
amenable to functional programming. A single Shen ‘logical inference’ can contain a call to any random
Shen function of any degree of complexity. Used skillfully this feature can enable the Shen programmer
to construct Shen Prolog programs which are fully competitive in performance with most stand-alone Prologs.

Mark

[Mark Tarver]

You still didn't explain why you call it dereferencing,

AFAIK it was a term used in Maier and Warren but the text has left my hands. But Stack Overflow
says

Dereferencing a pointer means getting the value that is stored in the memory location pointed by the pointer

A Prolog variable is just a structure that contains the means for us to recognise it as a variable together
with the means (a pointer in abstract terms) to find the associated value.

Mark

[Mostowski Collapse]

I have no opinion on the pros and cons of Shen.
My goals are two fold:
- I want to learn new tricks, even if it comes from LISP side.
- I don't want to get headache or epilepsy through
crazy syntax like (is A B) when it means (= A B). LoL

The danger is there that I don't touch anything if it comes
with a lot of crazy syntax.

If you look at Scheme Quine, I am even referencing miniKanren,
but I rather kill myself than writing:

( condo ...)

Operators are part of the game in Prolog. If you cannot
define operators your are missing 66% of the Prolog fun.

LoL

[Mostowski Collapse]

Or maybe its 69%. Or 42%.

[Mostowski Collapse]

Pointer dereferencing and logical variable dereferencing are
two different things. I would also use the term dereferencing for:

t = *x

in the C-programming language. But in the Prolog context
it has its own meaning:

> /* primitive Prolog operations */
> # define deref(x) {int t; while(IsRef(x) && (t=x,x=*t,t!=x));}
> https://ntrs.nasa.gov/api/citations/19930074153/downloads/19930074153.pdf
> Or here:
> function deref(a: address): address;
> http://www.inf.tu-dresden.de/content/institutes/ki/cl/study/summer09/ils/slides/2_Prolog2.pdf

Its only needed internally. Basically dereferencing is not
so much **observable** from within Prolog, it refers to

a representation inside a Prolog engine. Can you write
acyclic_term/1 in Prolog itself?

[Mark Tarver]

On Thursday, 11 March 2021 at 21:22:33 UTC, burs...@gmail.com wrote:
> Unlike unify_with_occurs_check/2, which can be implemented
> in Prolog itself, acyclic_term/2 cannot be implemented in Prolog
> itself when cyclic term unification isn't available. Right?

There are certain concepts which cannot be implemented in Prolog *efficiently*.
In designing Shen Prolog I created only those primitives that I felt could not
be implemented efficiently in Prolog - findall was one them.

I've not used cyclic terms much; apparently they have a use but I haven't come
across it in my work. I'd say that if you wanted to handle them you might
need to step outside Prolog to do it. Yes. It really depends on how much
people have put into the ISO standard. Certainly it is outside Shen Prolog but it
is not outside the capacity of the Shen kernel functions to define it.

A Prolog recognisor for a cyclic term would be easy to code - probably about 10
lines of Shen.

Mark

[Mostowski Collapse]

What is a "Prolog recognisor"? a) A Prolog predicate written in Shen Prolog?
b) Or a Prolog predicate written in another language?

In case you mean a), could you please demonstrate such an implementation
of acyclic_term/1, so as to support your claim?

[Mostowski Collapse]

Something else. Does Shen Prolog have strings and/or Unicode?
And if it has Unicode, does also have Unicode digit characters?

Here is some fun with my Prolog system, the Arabic 2:

?- X = ٢ .
X = 2

?- atom_codes('٢', L), number_codes(N, L).
L = [1634],
N = 2

[Mostowski Collapse]

Is there a section in the Shen documentation
that describes lazy and eager dereferencing?

How is copy_term/2 in Shen Prolog implemented?
Whats going on under the hood?

Mostowski Collapse schrieb:

> Pointer dereferencing and logical variable dereferencing are
> two different things. I would also use the term dereferencing for:
>
> t = *x

[gallaxial]

On 15 Mar 2021, Mostowski Collapse said the following...

MC> Is there a section in the Shen documentation
MC> that describes lazy and eager dereferencing?
MC>
MC> How is copy_term/2 in Shen Prolog implemented?
MC> Whats going on under the hood?
MC>
MC> Mostowski Collapse schrieb:
MC> > Pointer dereferencing and logical variable dereferencing are
MC> > two different things. I would also use the term dereferencing
MC> for:
MC> >
MC> > t = *x
MC> > Mark Tarver schrieb am Freitag, 12. März 2021 um 03:38:25
MC> UTC+1:
MC> >> You still didn't explain why you call it dereferencing,
MC> >> AFAIK it was a term used in Maier and Warren but the text has
MC> left my h
MC> >> But Stack Overflow
MC> >> says
MC> >>

[Mark Tarver]

On Friday, 12 March 2021 at 10:16:29 UTC, burs...@gmail.com wrote:
> Something else. Does Shen Prolog have strings and/or Unicode?

Sure Shen Prolog supports strings.

Mark

[Mostowski Collapse]

Can Shen Prolog prove:

(p <=> (q <=> (r <=> s))) <=> (((s <=> r) <=> q) <=> p)

[Mark Tarver]

There is a system FTP - which compiles into Shen Prolog which can do this problem.

Mark

[Mostowski Collapse]

I thought it comes from a TRE.

Mark Tarver schrieb:

[Mostowski Collapse]

Any idea why this page is cropped?

http://shenlanguage.org/osmanual.htm

I only see at the end:

Syntax Rules for Shen Prolog Definitions

<prolog_definition> ::= (defprolog <lowercase> <clauses>)
<clauses> ::= <clause> | <clause> <clauses>
<

And then it stops.

Mark Tarver schrieb:
> I've seen a few versions of this. What, in your
> opinion, is the the shortest Prolog solution to
> this problem - with the original problem in English?
>
> Mark
>