Bridge to Mercury

Hi Jan,

With Mercury compiling to C, can you see a benefit to have an easy to use bridge to Mercury – say as an alternative to C, to create foreign predicates for SWI-Prolog programs, that take fully advantage of Mercury’s optimized compiling of code that is annotated with modes and types.

thanks,

Dan

We have a good bridge to C. You typically use that for things you cannot do in plain Prolog, such as accessing the OS. Another use case is stuff for which there is a nice C library and it is just a waste of time to redo all that in Prolog (e.g., the TLS (SSL) binding). Finally, there is stuff that is too slow in plain (SWI-)Prolog. Yes, Mercury is fast, but comes with the same type of extensive runtime system as Prolog and I don’t think you want two of those in your process. It is also a bit speculating why Mercury is that fast and even how fast it is compared to state-of-the-art Prolog. SWI-Prolog is feature rich, but not particularly fast. Some people claim it is really slow. That is true in some areas, but in others it is quite competitive.

I think that investing time in making SWI-Prolog faster is more valuable, notably as everybody profits and we achieve that without creating a complex to setup system with complex declarations.

Hi Jan,

With the Mercury approach in mind, what swi-prolog would need to become faster, is support for modes, types and those predicate signatures that indicate whether predicates are deterministic.

From what I read, these capabilities enables the compiler to create more optimized routines.

It would be really great if such extensions could be added … its quite out of my abilities though, to add such capabilities into the swi-prolog code (without a serious study of the code base, while putting my project on the side).

My thought was to use Mercury as a C replacement for code that is mostly deterministic, in the hope that this will be quite lean.

Dan

I don’t think there is consensus about that. You can probably find some old posts by (notably) Bart Demoen on these topics. Neither is there much consensus on the value of native code. There is consensus that it is possible to run Prolog faster than SWI-Prolog does :slight_smile: At least, on a subset of Prolog and particularly on the subset that you seem most interested in. Especially deterministic tail recursive loops can be a lot faster. Improving that is probably simpler than some fancy bridge to Mercury and will provide profit to many more users.

2 Likes

Hi Jan,

Thank you.

I guess, to (re?) hash some of the arguments – compiling to C and then machine code is probably faster for equivalent code that otherwise would run via a VM.

But, likely, much more importantly: when mode is provided, Mercury apparently generates separate routines per argument mode, and by taking determinism declaration into account – for example, no need for choice points, and optimized memory allocation and reuse, and the like – which is handled during compile time.

I guess, a benchmark would really be needed with representative examples, to make a case here.

Swi Prolog on the other hand has features, due to its VM approach, and that I am making use of, that can’t exist in Mercury.

Dan

The problem in a dynamic language as Prolog is that you may declare some property of a predicate, but the predicate still has to verify this is actually true rather than continuing with undefined behavior. You can win a little by doing the tests in a more optimal order, but typically that is just a modest gain.

All good questions.

No, i took it the benchmarks that were published, but didn’t actually check if they are dated …

Dan

Multi-argument indexing helps not/little for these traditional benchmarks. The speedup you can get from last call optimization (SWI-Prolog gets the space advantage, but no significant speedup) would probably help significantly. If I recall correctly, quite a few of these benchmarks depend heavily on arithmetic and if-then-else performance. Not really the most representative stuff :frowning:

I guess, my use case, requires close to system work – bit operations, memory locality, pointers, and little call overheads, that’s where C / C++ usually excels – perhaps this is a rather uncommon use case for prolog.

Dan

Many years ago, I helped someone speed up their LISP program by 10x or so (using cmucl). IIRC, the biggest wins were:

  • changed some lists to structs or arrays (Prolog already has terms, so this wouldn’t apply to Prolog).
  • added some “trust me” type declarations and compiling in unsafe mode.

Some of the LISP type declarations wouldn’t apply to Prolog, so it’s not clear how much gain there would be by allowing unsafe type declarations.

Some tools/features for declaring and detecting these loops would be helpful. (I use library(rdet) but it would be nicer to have something that’s more integrated with SWI-Prolog.)

One very important factor that has yet to be mentioned in detail is support.

For years Mercury was listed as a research language, it was only in the last year or so I noticed that it no longer states that. However I did experiment with it over a decade ago when it compiled to Microsoft CIL, the VM language under the language such as C# and F#; Mercury no longer supports that build path.

Back then support was limited to the user forum and hard to get help if no one was interested in answering Even now AFAIK, that is about the only way to get help. While I do like Mercury and do add it to the list of languages to check out for possible use with some projects, the lack of support typically sinks using Mercury.

So in addition to checking the performance stats, you need to see what is the current level of user support by asking some questions. It may be better now, and I would be glad if it has improved. :smiley:

Hi Jan

The problem in a dynamic language as Prolog is that you may declare some property of a predicate, but the predicate still has to verify this is actually true rather than continuing with undefined behavior.

I was thinking about it the other way around – you specify the property of a predicate, based on a design intent. That is, in a language that supports such a specification.

It may behave differently, which would indicate a design intent problem – which is a good thing – it helps clarify the understanding of the problem.

Dan

It you want to say that mode and type declarations are an important part of documentation/specification, I fully agree. I also think it is great that we do not need them everywhere and we can omit them completely. Mode declarations existed in old implementations such as DEC10 Prolog, I think mostly for performance reasons. The evidence that they are essential for performance is not hard though.

Hi Jan,

I think i am going a step further, to say, that when mode and type declaration are provided, then a compiler can do some additional checks, increasing the quality of the code.

re: performance

I my mind, it kind of self-evident, that if, you can omit creating choice points for declared determinstic goal predicate encountered, and you can skip such goals during backtracking, then this provides a key performance gain.

Also, when thinking about types:

person(dan).
programmer(dan)

could perhaps be resolved during compile time using polymorphic types, rather than a rule
programmer(X) :- person(X), saving runtime compute as well.

The few cycles wasted are likely not much of a problem in a domain where one can program, say, in Java as well – with its VM overhead (as well).

However, in domains were processor cycles are counted to ensure optimization, and where C and C++ are the preferred language choices – these omitted choice points and backracking steps, are significant.

The other area, i (intuitively) feel there is an overhead in Prolog is not support for pointers. to traverse structures – at each step there is a hash lookup which is much more costly than a “next” pointer – not sure if Mercury has an answer to that though.

But, perhaps, system level programming its just not the right domain to work with Prolog (or Mercury) and moving to C / C++ for those performance critical areas is the better choice.

Dan

Hello Dan,

it is sometimes dangerous to trust your intuition. You have at least two other options when it comes to understanding the behaviour of computer programs. You can study the source code and infer the behaviour; you can create controlled experiments and measure/observe. The two approaches complement each other.

With regards to quality of code Mercury also has Termination analysis.

However IMHO if you keep going down this path of quality of code I believe that you will eventually reach Curry–Howard correspondence, but also pay attention to Curry–Howard–Lambek correspondence.

Then you will probably want to use something like Coq and the program extraction feature. :smiley:

In other words, you don’t write programs but you write proofs, as in mathematical proofs, and via Curry-Howard correspondence convert that to a functional program.

Don’t ask me many questions on this as I have never done it, but am aware of it and do plan to use it some day, but not right now. Remember that these are proofs, so everything from the ground up has to be a proof or you can’t use it.

For some related history on this learn about the Four color theorem. Also see Automated theorem proving.

I don’t know how much of this you may or may not have known, but this is clearly taking you way off the path of using just Prolog.

EDIT 09/27/2019

Software Foundations

Perhaps you want a NoSql database such as Neo4j which directly connects a node to another node via a relationship which would be like your pointer. However with Neo4j the databases can be very large, Gigabytes or more, and so the entire database is not loaded into memory. However if you have a node, then getting the relationships is easy with getRelationships() as the way they are retrieved is more like following a pointer, but sadly, there is no Prolog driver for Neo4j.

Hi Eric,

Yes. That is the direction.

However, even Neo4J would be too much of an overhead – which is, perhaps, comparable to RDF relation lookup (if relations are materialized).

I would have liked to have a datastructure implemented via barebone pointers.

Where i could request the next (or ajdacent) element and its retrieved via a pointer access, rather than hashtable lookup

Perhaps, its not too hard to write.

Daniel

2 posts were split to a new topic: Process the mode/type/determinism declarations into executable cod