This is FYI https://github.com/infradig/trealla/issues/281#issuecomment-950251166
2 Likes
Progress, far from consisting in change, depends on retentiveness. When change is absolute there remains no being to improve and no direction is set for possible improvement: and when experience is not retained, as among savages, infancy is perpetual. Those who cannot remember the past are condemned to repeat it.
(I hope that this doesn’t come across as an appeal to authority argument, it is just that there are several up-and-coming Prolog implementations out there, and they all treat garbage collection as an afterthought, and instead go hard on the ISO-compliance. Had they taken the time to understand the past developments they might have taken a different approach.)
2 Likes
I understand it is fun to write a Prolog engine, in particular because it is not hard to get something simple going. I don’t get the added value of yet another Prolog that merely implements the ISO standard and is otherwise rather immature. Bart Demoen is the only implementer who never made his toy hProlog system widely available because it was his opinion that less Prolog systems is better than more. Instead, he helped me to get his ideas on constraints and delimited continuations from his toy baby to SWI-Prolog.
Writing a toy Prolog system is easy. Prolog is more like SQL than like C/C++/Rust/… though: many of the improvements cannot be stacked on top of it, but must be implemented in the runtime engine. Getting all these desirable features into the runtime is not easy as several are related. Most of the algorithms have been published. Understanding the whole picture and getting it right is still a lot of work. Of course, if you start from scratch you can bypass the various mistakes that old projects such as SWI-Prolog have made and that left scars.
Life would be so much better if we could join forces 
8 Likes
Monoculture is not universally good, I agree, and diversity is definitely good. I wasn’t commenting on Dogelog, there are at least three other new Prolog implementations that pivot around “Implemented in Rust” or “ISO-compliance” and I was maybe talking about these.
2 Likes
There are (I think) roughly two approaches to implement Prolog. The classical way is to create a VM in a low level language (WAM, ZIP, B-Prolog, …) that takes full control of memory. The other is how to implement Prolog in high level garbage collected languages. There is surely value in native implementation of Prolog in JavaScript, Python, Scheme, etc. At least it is a challenge that gains insights. These systems typically also interface better with the hosting environment than creating a bridge from these languages to a Prolog system of the first category (or WASM for JavaScript).
I think these approaches are a nice way to create a simple Prolog engine for such languages. Once you want to go beyond simple though you are faced with a lot of work implementing debugging tools, optimizations, constraints, tabling, etc.
1 Like
I indeed keep lamenting (to myself, mostly) that those who have the skills and time to write a Prolog system don’t join forces around SWI-Prolog – and thereby are not only fragmenting technology, but more importantly, the minuscule Prolog community as well – which, despite all well intention, is mostly often the reason why such efforts end up abandoned …
And, commercially speaking – a better technology (such as claims: attribute variables are better in prolog X vs. Prolog Y) – is a very marginal value relative to the cost of a fragmented community and eco-system.
I am told by many serial entrepreneurs that technology is perhaps 15% of the overall success of a venture – the rest is organization – the people and roles driving the venture – and the business model – how the venture sustains itself financially.
Dan
Commercially speaking, i am not sure why having a c-base is a problem, if all relevant commercial targets are covered.
The only reason to consider Rust, for example, as a basis is its compile time guarantees – but, these are mostly used for new code, since existing code, in particular, in use for decades and has proven itself
CLP(Z) is the successor of CLP(FD) by Markus. It is indeed all Prolog, but requires a SICStus compatible implementation of attributed variables. Let us leave that discussion closed … For this stuff to work you need to implement this attributed variable API, which is far from trivial (especially if you want to keep it performant). As the introduction of attributed variables also tends to make cyclic structures creep into the code, you better make sure these can be handled safely. This complicates many of the low-level primitives and makes it nearly impossible to implement many of them in pure Prolog at a reasonable efficiency.
After all that work you have a nice and clean constraint implementation that is wonderfully reliable (thanks, Markus!). It performs poorly when compared to SICStus, GNU or ECLiPSe (and maybe others) that implement a large part of clp(fd) in C.
For tabling we have a similar story. Based on delimited continuations (can be implemented in a couple of days) we can fairly easily write tabling in Prolog as Benoit Desouter proved. It performed about 100 times worse than the SLG WAM as found in XSB and YAP though. After moving most of the admin to C, the gap is now somewhere between 1 and 10 times, depending on the program. I think that by moving some more to C and the VM we could get into the same league, although the different approach is faster for some problems and slower for others, a bit like structure sharing vs. structure copying Prolog engines. The beast got pretty complicated though.
I’ve encountered this tradeoff – but, in my case I rather opt for speed vs. the benefits of self-hosting … if a c implementation is significantly faster – all the while not sacrificing portability to commercially relevant platforms.
I don’t completely buy this premise, in a dynamic language you do sometimes compile at run time. I don’t claim to fully understand all the details but to me it seems that you were painting with a course brush here.
Writing only a small core in some other language is of course attractive. I doubt that language can be Prolog though (if we want good performance). Possibly it can be a dialect with limitations and annotations that allow defining all these nice (semi-det) internals such as copy_term/2 in such a way that they can be compiled to nice native code. That is also a direction @dmchurch has proposed. I don’t know whether that can work. Notably the algorithms for handling cyclic and partially shared terms during unification, comparison, copying and a good deal more are hard. They are all based on temporal modifications of the involved terms, turning them into invalid Prolog data.
You can use some Prolog-like language to specify the various algorithms and compile this. Quintus already did so for the VM. Jose Morales has done something like that for the Ciao VM. Now we could write a Prolog program that compiles this to our target implementation language. Then bootstrapping only requires changing this compilation step. It is not entirely clear how much better that is than compiling the C code using WASM and use it in JavaScript and similar transpiler projects we have seen in the past (Pascal → C, …) One of the serious problems is that this introduces a new (Prolog like) language people have to learn if they want to contribute. This new language also requires an eco system …
IMHO it is an interesting thought. We already have C though and nearly any relevant technology can talk to C: virtually all hardware is supported and virtually all programming languages can talk to C because the OS is either written in it or has a C binding. Yes, it is a tricky language and maybe ultimately it will be replaced by Rust or something yet to be invented. For now it is still a language with a huge number of competent programmers that allows one to use just about any feature of the hardware. Rust’s safe memory handling is of course great and would surely have avoided many bugs that got into (notably) multi-threaded SWI-Prolog. AFAIK it only has one approach to guarantee safety though (part compile time and partly runtime) while in my experience you need several because the various relevant objects (terms, atoms, clauses, etc) all have rather different access patterns and lifecycles. I’ve played with the Boehm garbage collector, hoping it would deal with atoms, clauses and a lot more objects elegantly. It worked. It didn’t scale though Notably Keri Harris implemented the dedicated garbage collectors that do scale.
2 Likes
Waw, I have learnt a lot today and thanks for the discussion!
As a user we are extremely happy with swipl to power The EYE Reasoner.
I came accross Scryer and Trealla while doing some research for The Retina Chainer.
It would be really great to have a Prolog community which is not the union of everyone but the intersection of “what will all want to go for” and have a unified platform, a bit like with The Python programming language.
Concerning C versus “not in C” cpython contains 480K lines of C code which about the same as swipl which has 484K. A further comparison shows that the cpython project has 877K lines of .py code and the swipl-devel project has 418K lines of .pl code.
2 Likes
For those like me looking for the code for EYE:
No problem and the memory consumption remains below 10 MB for the meta-interpreter of the-meta interpreter of the meta-interpreter … 25 levels deep:
$ swipl
Welcome to SWI-Prolog (threaded, 64 bits, version 8.5.1)
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software.
Please run ?- license. for legal details.
For online help and background, visit https://www.swi-prolog.org
For built-in help, use ?- help(Topic). or ?- apropos(Word).
?- [user].
|: mi([]).
|: mi([G|Gs]) :-
|: head_body_(G,Goals,Gs),
|: mi(Goals).
head_b|:
|: head_body_(mi([]),Rs,Rs).
|: head_body_(mi([G|Gs]),[head_body_(G,Goals,Gs),mi(Goals)|Rs],Rs).
y_(head_body_|:
|: head_body_(head_body_(Head,Goals0,Goals),Rs,Rs) :-
|: head_body_(Head,Goals0,Goals).
ead_bod|:
|: head_body_(factorial(0,s(0)),Rs,Rs).
body_(|: head_body_(facto(N),F),[factorial(N,F1),prod(s(N),F1,F)|Rs],Rs).
_body_|:
|: head_body_(prod(0,_,0),Rs,Rs).
body_(|: head_body_((N),M,P),[prod(N,M,K),sum(K,M,P)|Rs],Rs).
dy_(sum|:
|: head_body_(sum(0,M,M),Rs,Rs).
|: head_body_(sum(s(N),M,s(K)),[sum(N,M,K)|Rs],Rs).
|: ^D% user://1 compiled 0.02 sec, 11 clauses
true.
?- mi([mi([mi([mi([mi([mi([mi([mi([mi([mi([mi([mi([mi([mi([mi([mi([mi([mi([mi([mi([mi([mi([mi([mi([mi([factorial(X,Y)])])])])])])])])])])])])])])])])])])])])])])])])]).
X = 0,
Y = s(0) ;
X = Y, Y = s(0) ;
X = Y, Y = s(s(0)) ;
X = s(s(s(0))),
Y = s(s(s(s(s(s(0)))))) .
?-
While doing some further tests, there is indeed a problem with for instance:
$ cat mipf.pl
mi([]).
mi([G|Gs]) :-
head_body_(G,Goals,Gs),
mi(Goals).
head_body_(mi([]),Rs,Rs).
head_body_(mi([G|Gs]),[head_body_(G,Goals,Gs),mi(Goals)|Rs],Rs).
head_body_(head_body_(Head,Goals0,Goals),Rs,Rs) :-
head_body_(Head,Goals0,Goals).
head_body_(factorial(0,s(0)),Rs,Rs).
head_body_(factorial(s(N),F),[factorial(N,F1),prod(s(N),F1,F)|Rs],Rs).
head_body_(prod(0,_,0),Rs,Rs).
head_body_(prod(s(N),M,P),[prod(N,M,K),sum(K,M,P)|Rs],Rs).
head_body_(sum(0,M,M),Rs,Rs).
head_body_(sum(s(N),M,s(K)),[sum(N,M,K)|Rs],Rs).
$ swipl mipf.pl
Welcome to SWI-Prolog (threaded, 64 bits, version 8.5.1)
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software.
Please run ?- license. for legal details.
For online help and background, visit https://www.swi-prolog.org
For built-in help, use ?- help(Topic). or ?- apropos(Word).
?- set_prolog_flag(answer_write_options,[max_depth(0)]).
true.
?- mi([mi([mi([mi([mi([factorial(s(s(s(s(s(s(s(s(0)))))))),Y)])])])])]).
Y = s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(
...
s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(Segmentation fault
As far as I can see the memory is not exhausted when the segmentation fault happens.
FWIW, Python is undergoing some performance improvements, including better multithreading and better memory allocation / garbage collection (Python currently uses reference counts (but also needs a garbage collector for circular data structures), and has a “global interpreter lock” (“GIL”) that makes it easy to use containers such as dicts or lists across threads but performance).
It also uses a new thread-friendly memory allocator from Microsoft: mimalloc. More details, including some early performance results here:
1 Like
Unfortunately, SWI-Prolog still contains a few routines that use the C stack for walking over terms for some built-ins. Notably read_term/2 and write_term/2 and some parts of assert/1 (if I recall correctly). Some of these do last argument optimization, but not all. If this traps it simply says segmentation fault without any further details. In almost all other crash scenarios it is much more verbose about what went wrong. One day …
1 Like
It is a big community. They will fix it. It is not easy though. It took a month to build the first multi threaded version of SWI-Prolog. Next 10 years with involvement of several commercial users to make it robust and scalable. That would have been less when the design took care of threads from the beginning. As with Python, it didn’t 
It is my main development platform since to years 
On the other hand, I have not been doing much performance tuning during this period. Most of the advance comes from the profile guided optimization that was enhanced by @dmchurch and improvements in gcc (mostly around version 8 or 9, I think). Unfortunately clang got worse in the same period. Much worse. When Apple moved to clang, the gcc version was only slightly faster than the clang version. Now it is about twice as fast.
1 Like
All benchmarks need to be taken with a grain of salt. Also, the PyPy ones are against a rather old version of Python. And: if PyPy is so great, why isn’t it used more? There are probably long discussions about this on the internet … but at least part of the problem is that Python is extremely dynamic (e.g., all outer scope variables are looked up dynamically, which is why you see things like def foo(x, y, len=len)); and another reason is that most of the time, performance isn’t important …
There have been multiple attempts to speed up Python, including some failures (e.g., “Unladen Swallow”).
Apparently there have been over 25 attempts to build a Ruby compiler:
https://twitter.com/laurencetratt/status/1453260028232732675
1 Like