Questions about Scryer implementation choices

[abmclin]

Hello colleagues,

I am very new to Prolog, only started learning it in the past month and it's been a fascinating journey which I have enjoyed immensely. I've started learning about Prolog implementations and read some papers about various techniques and virtual machines.

I recently learned about Berkeley Abstract Machine (BAM) from reading Can Logic Programming Execute
as Fast as Imperative Programming? and Vienna Abstract Machine (VAM), along with Zip, TOAM, and others, which stimulated my curiosity about Scryer's implementation choices. The papers describing BAM and VAM claimed that they are an improvement over WAM. So I'm wondering why Scryer chose to use WAM to implement Prolog versus BAM or VAM or even Zip or TOAM?

I did notice that BAM seems to be encumbered with rather restrictive licensing terms which may explain why it's not found elsewhere in other Prologs (other than Aquarius). What about VAM? It seems it's not used anywhere, though please correct me if I'm mistaken!

I would love to learn more if you have any information to share regarding why one machine model was chosen versus others?

[mthom]

The WAM is the best documented of the Prolog abstract machines by far and has a wealth of literature on extending it with garbage collection, continuations, tabling, exceptions, compressing reference chains, lots of things. I did initially want to start with the WAM and in time refine it down to the BAM, but I was warned against doing that I believe because the BAM doesn't support ISO Prolog semantics as consistently and solidly as the WAM does. I think I was told Aquarius Prolog was impressively quick but had persistent semantics problems. Scryer prioritizes correctness and reliability over performance (performance is still very important as our #2 priority). Besides all that, our ultimate goal is to compile WAM code to native code. The global benchmark of Prolog performance is currently SICStus and it runs on a WAM-based JIT compiler, so this certainly seems doable using the WAM even if it is not strictly the fastest abstract machine.

I was never really aware of the VAM. The WAM got almost all of the publication ink in the area of Prolog abstract machines.

[abmclin]

That makes sense, it's a lot easier to develop something when there's plenty of available documentation. That is interesting about BAM's semantics issues, I will need to look for literature about that. Regarding correctness versus performance, I agree I would prefer a system be correct and reliable first before considering performance.

Thank you for your comments! I am looking forward to reading more about how a JIT compiler is implemented for WAM.

[UWN]

First, a bit of historical context. At the time of the development of the WAM, cheaper workstations became popular. Just to give an order-of-magnitude impression, there were 3 classes of machines: IBM hosts, then for a 10th of their price Vaxen, and for again a 10th of that, workstations. The idea was to provide more LIPS per $ with workstations like Apollo and later SUN which were Motorola 680x0 based. While the address space was flat and (for that time) virtually unlimited, real memory was quite expensive, and thus a compact emulator was seen as the primary option. That is, direct threaded decoding. In that context, the claim for improvement of the VAM must be seen. It effectively decoded head and goal simultaneously at practically the price of a single decode in the WAM (exploiting some 68k-specifica).

With increasing real memory and RISCs, compilation options became more attractive, but all required some extra work for the programmer. It is only since SICStus' Jitter that completely transparent machine code generation has become available lowering carbon footprint.

There are still clever developments on the abstract machine level. Like jumbo-instructions. And there is still no implementation that efficiently supports call/N. See a comparison of WAM and ZIP for some of their details and also a comparison of PLM and VAM.

[abmclin]

Thanks for the reference, it was helpful to understand better the differences between WAM and ZIP.

It's a challenge understanding the tradeoffs between different models, and what they mean for implementation efforts. So far my current impression is that WAM is in a good location in the design space for making compiling easier and taking advantage of available optimization opportunities.

By jumbo instructions, do you mean in this sense as explained by this paper https://academicworks.cuny.edu/gc_cs_tr/304/ ?

[UWN]

Yes. In particular how built-ins are implemented.

[emummel20]

Oh ok good - came across this paper today called "Global Optimizations in a Prolog Compiler for the TOAM" and wanted to do a search here to make sure this community was aware of it. Looks like you are.

Even if we're sticking to the WAM over BAM because we're prioritizing correctness over performance (an approach which I agree with!), wanted to run this paper up the flag pole to see if perhaps there are some ideas in there that could be implemented in the WAM to its benefit.

[UWN]

This is a relatively early paper of Neng-Fa. I believe he did not know of the VAM at that time. At least it is not cited. Later papers do. See this for more. So he started with a kind-of WAM, put a lot into indexing (this ATOAM) and then slowly migrated towards a ZIPish design. Giving up one WAM characteristic after the other.

Mark has decided to go for WAM. Yes, the ZIP in a very elaborated form (as in B-Prolog) could have some advantages, but I would say that first the nitty gritty details have a much bigger impact, like #1576, #1545, #1390, #1387, #1269 which are probably related to some issues related to its actual WAM implementation. In comparison to these, the advantages between different abstract machines are pretty small.

And just remember the very best and fastest system in existence, SICStus, is also 'only' WAM based. And they managed to make it a jitter thereby being completely transparent, even for abolishing static code dynamically (not required by ISO), think of it, even respecting the (ISO-wise implementation dependent) variable ordering. And it seems they now (in 4.8) removed most of the overheads in call/N. No, not all of it, hof course it's still a WAM, but these architectural disadvantages dwarf compared to the overheads typically incurred.

[emummel20]

Thanks for the response @UWN . You seem to be well versed in this. Can I ask for your opinion on this comment?

I did initially want to start with the WAM and in time refine it down to the BAM, but I was warned against doing that I believe because the BAM doesn't support ISO Prolog semantics as consistently and solidly as the WAM does.

Perhaps a silly question but so what if BAM is not quite as ISO consistent? Does that make the BAM inherently worse? ISO is simply a prolog specification, correct? So whatever spec the BAM follows may be different but not necessarily worse, I'm thinking? Or do we know it to be worse in some ways?

Appreciate the insight.

[UWN]

BAM is a finer grained WAM. There was a proof-of-concept implementation, but nothing larger than that. Probably because it was quite costly. All the ISO semantics for updates and the like have not been explored. That all this extra optimization effort is worth it, is not evident. Just think of exploiting determinism. What is much more important here is to find constructs that effectively lead to better forms of determinism.

[emummel20]

Thanks @UWN - in other words, if I understand you correctly, fwiw you agree with the approach the scryer team is taking?

[UWN]

I agree with any ISO conforming approach, for that matter. Regardless of the internal implementation decisions taken.

What I can say for the moment for Scryer, is that its term representation is very close to SICStus performance-wise. This in turn means that there does not seem to be any inherent limitations in that direction. Not sure how Rust can be used as a jitter, but if it can be used, then things look quite brite.

[emummel20]

@UWN thanks - one other thing: Do you know if there's a detailed whitepaper or anything similar to "A Tutorial Reconstruction" for WAM but for the BAM? I'm trying to find one but can't so far.

[UWN]

There is one proof-of-concept implementation of this abstract machine. You have the thesis. What else do you expect?

[emummel20]

I'm curious about what specific improvements or tradeoffs the BAM makes from the WAM.

[emummel20]

Maybe another implementation question, do we take advantage of the optimizations recommended in this paper - "Improving Efficiency of Prolog Programs by Fully Automated Unfold/Fold Transformation"

From their concluding remarks:

In the paper we have described a fully automated algorithm for eliminating unnecessary variables in definite programs. We have implemented this algorithm and applied it to several benchmarks of programs. The results showed that the transformed programs have approximately 31% speedup (measured in CPU runtime) compared to non-transformed originals. But there still exist programs for which UDF has worse results after transformation than their originals.

so looks like their technique is a matter of tradeoffs depending on the program but perhaps worth a look.