Trealla – A compact, efficient Prolog interpreter written in plain-old C | Hacker News Reader

Trealla – A compact, efficient Prolog interpreter written in plain-old C

github.com

126 pointsnikolay34 comments

Trealla is one of the most interesting new Prolog systems: Notably, as in other new systems such as Scryer and Tau Prolog and ichiban/prolog, the default setting of the Prolog flag double_quotes is chars, and therefore lists of characters can be conveniently written as double-quoted strings in Prolog code. Second, as in Scryer Prolog, such lists are very compactly encoded internally, making Trealla suitable for analyzing and processing very large amounts of text conveniently and efficiently.

In addition, file contents can be processed directly with Prolog's built-in grammar formalism, Definite Clause Grammars (DCGs): Internally, Trealla maps the file contents directly to memory with mmap(2), an innovation that is currently unique to Trealla!

There is also a recent WASM embedding:

https://github.com/guregu/trealla-go

Thank you a lot Andrew and all contributors for your great work on Trealla! It is to be hoped that these implementation techniques are also adopted in other Prolog systems!

Ah, so 'codes' is the setting for that flag that erlang's behaviour matches. Which in an old-school prolog makes complete sense, but if you can encode the 'chars' variant efficiently then that works out fine.

For those not that prolog literate (like me): https://stackoverflow.com/questions/8264699/what-is-the-diff... seems to help.

Yes, that's correct!

Interestingly, Erlang does encode lists of codes efficiently internally! The advantage of chars is that in this way, we obtain much more readable answers to queries!

The very first Prolog system, Prolog 0, already used lists of characters for strings. Later systems tended to interpret them as lists of codes, and we now see several new Prolog systems that (again) interpret them as characters.

I really recognize the value of new implementations and the fact that each of them is filling a hole that old implementations do not cover (like new platform support, more embeddings, etc.).

But I have a controversial question: why is it better to start a system from scratch than contributing and helping to other less known, long running systems (Yap, XSB, ECLiPSe, Ciao, gprolog, B-Prolog, etc.)?

In the old times, a system became popular because you read a research paper which described carefully the implementation decisions and did good performance evaluations. Papers were reviewed and trusted, you could get objective information about why the implementation was good or not. This helped advance the state of the art.

Nowadays, this is completely broken and it is strangely feeling like a "popularity" contest and a social game. For example, some users were surprised about the performance of WASM-compiled Ciao Playground:

  https://ciao-lang.org/playground/

that despite being x2 slower than native, is faster than other popular Prolog implementations. We needed to tweet about it and use the forum of another popular Prolog system to have any visibility. Despite that, this fact will soon be ignored and buried.

When looking at the VM of each of the systems, we know why this happens, but the expertise of the people who wrote earlier Prolog systems, many of them run perfectly fine and blazingly fast in modern machines, is being lost.

Of course, we learned a long time ago that the selection of benchmarks is really complex. You can pick whatever is needed to make your system shine. Ciao Prolog is extremely fast for some benchmarks but it can also be much slower in others.

My claim is that despite it is cool to have new and nice Prolog implementations, this is adding a lot of noise and we are repeating mistakes from the past and going in the wrong direction:

- There is no incentive for proper benchmarking (e.g., should I implement mmap-based file mapping? when does it help? is it a good idea?) - The literature is being ignored (e.g., who reads and compares with Paul Tarau or Bart Demoen implementation papers?) - VM and libraries should be independent (it should be possible to implement a new VM while not requiring to reimplementing the whole set of libraries) - Systems copy/reimplement features without proper recognition of the original system (e.g., once a technique is adopted by the popular system, the original is forgotten, who knows that JITI was originally developed by Vitor Santos Costa in YAP?). - The community is extremely fragmented.

I wonder if it would be possible to create a more healthy Prolog forum which prioritizes ideas, authors, and results. Going through twitter, discourse, github discussions, github issues, of each of our individual Prolog system is NOT a solution. Each of us looking at decades of research papers and reproducing them in each of our systems is also not a good idea (indeed the unique advantage of old systems is that it takes decades to incorporate some of these ideas). Moreover, there are still many unsolved problems in modern Prolog systems that can only be addressed as programming language research.

Insightful. On the plus side OTOH, more Prolog implementations means more focus on standardization and shared Prolog code bases, when the dominance of certain commercial and F/OSS implementations might have pushed Prolog IMO too much into the CLP magic and/or procedural niche.

How does this and Scryer, Tau all compare with the SWI?

Apart from different implementation languages and techniques (Rust/JavaScript/C, WAM/AST interpretation etc.), one of the most striking and impactful differences is that Scryer, Tau and Trealla Prolog aspire towards ISO conformance, i.e., they try to adhere to the Prolog standard, whereas SWI intentionally does not adhere to the standard:

https://www.complang.tuwien.ac.at/ulrich/iso-prolog/SWI7_and...

Scryer already provides an interface for attributed variables that is compatible to SICStus Prolog, one of the most sophisticated Prolog systems, and uses it to implement various constraints such as dif/2 (also rudimentarily available in Trealla, but not yet in Tau), Boolean constraints etc., which I hope become available in Tau, Trealla and other upcoming systems such as ichiban/prolog in due time.

Is ISO adherence a big deal? Because SWI seems quite mature and featurefull. The impression I got is that SWI is to Prolog, what GHC is to Haskell.

Adherence to standards matters a lot for example in several kinds of governmental organizations, banks, the medical industry etc. If you want to use a Prolog system in safety-critical areas, it is best, and often in fact required by internal and external guidelines, to choose vendors who are committed to upholding standards: This simplifies procurement, settling legal disputes and warranty questions, it reduces the risk of depending on a single vendor etc.

Standards are also important when creating teaching material, and obviously for compatibility and interoperability between systems. I therefore recommend to use and provide Prolog systems with strong commitment to the Prolog ISO standard.

Standards aren't that much of a constraint for SQL/databases, for example. Mostly one works with the dialect that is used by the specific implementation. Moreover standard hasn't kept pace with innovation by various vendors.

So in the case of SQL more than de-jure standards, it is the generalized set of features that popular implementations support that matters. Isn't that the case with Prolog?

So I'd be more interested in reasons other than literal adherence to de-jure standards.

Regarding SQL, we find for example in the Oracle SQL documentation https://docs.oracle.com/database/121/SQLRF/intro002.htm#SQLR...:

"Oracle strives to comply with industry-accepted standards and participates actively in SQL standards committees."

and also https://docs.oracle.com/en/database/oracle/oracle-database/1...:

"This appendix declares Oracle's conformance to the SQL standards established by the American National Standards Institute (ANSI) and the International Organization for Standardization (ISO)."

A similar notion of intent and self-assessment is highly desirable in Prolog systems, for warranty reasons alone already.

The Prolog standard defines the minimum (not the maximum) of features that must be present in conforming implementations: Prolog implementations are free to provide extensions to the standard, as in SQL implementations. However, to still comply with the standard, all such extensions must be conforming extensions, i.e., they cannot render existing conforming Prolog code invalid or differently interpreted than the standard demands. Also, it must be possible to run the system without all such extensions. For example, in Scryer Prolog, this is achieved by not loading any modules.

Valid candidates for conforming extensions are for example Prolog programs that would yield a syntax error without that extension.

All true, but you make it sound boring. :( I was under the impression that the ISO standard was (arguably) the "best" way to write a Prolog implementation, providing a flexible foundation to build future features on top of. Was I misinformed?

Unfortunately the iso standard for prolog is kind of inadequate. It doesn't include a module system for instance. It also doesn't define the attributed variable interface which is fundamental to constraint logic programming.

It's kind of a Scheme r5rs situation.

Well, there is ISO 13211-2 - Prolog part 2: modules [1], but it was flawed, ignored, and didn't help portability. There was also the Prolog Commons [2] initiative to identify common ground for basic libs. The importance of these features are judged differently depending on whether you're belonging to those who want to use Prolog in the large (with types and libs, LogTalk being an extreme example) vs those who want to embed Prolog into a host language and use it just for what Prolog really excels at.

Having ported a non-trivial Prolog code base to ISO Prolog [3], I can say that lack of modules/libs wasn't the problem in that particular case (I really should come around and write up a more comprehensive tutorial for common problems in porting Yap- and SWI-specific code to ISO Prolog based on the material I have).

[1]: https://www.iso.org/standard/20775.html

[2]: https://prolog-commons.org/

[3]: https://quantumprolog.sgml.io/bioinformatics-demo/part1.html

It's a very big deal, especially if you're actually implementing commercial Prolog solutions rather than toy code for learning or academic papers. SWI is historically quite slow and SWI's model of explicit threading control and other choices tends to degenerate Prolog code for SWI into quasi-procedural, script-like execution. Also, while not Prolog proper, certain commercial Prolog engines do have much more powerful facilities for constraint logic programming over the reals which make them a preferred choice in eg (legacy) financial optimization models.

We had to write Prolog for a week or two in my language concepts class. A lot of the course was about language development and concepts at a more semantic level, and Prolog was an obvious choice to introduce the class to a paradigm none of us 19yos had ever seen.

It was a tricky assignment and project, but damn was it neat. I personally don't have any use for Prolog in my career, nor would I want to work in it daily, but I find it super interesting and such a unique language that everyone should at least read about once.

> Trealla is not WAM-based. It uses tree-walking, structure-sharing and deep-binding. Source is compiled to an AST that is interpreted at runtime

Can somebody familiar with prolog implementation techniques motivate this choice? It seems to me--given knowledge implementing very different sorts of languages--that tree-walk interpretation is generally slow compared with other methods, which seems strange given this implementation touts its efficiency, but perhaps there are reasons why that doesn't matter here?

Tree-walking is a bit of a misnomer here, it actually uses a compiled-to-bytecode representation of the AST. Part of the motivation is to avoid copying and structure building, which WAM's do, a lot.

I was actually trying to find where the bytecode is evaluated, but it doesn't leap out at you, can you provide any pointers?

It says page not found

Seems they just recreated the git repo to clear out ~1gb of history. https://github.com/trealla-prolog/trealla/issues/1

I wonder why that would be needed. There is always shallow clones if that is too much to download.

It was just made private, I guess. Only the Go WebAssembly project is still public: https://github.com/trealla-prolog/trealla-go

I think it's a mistake, probably reorganizing things at the moment. You can find a slightly outdated fork here: https://github.com/guregu/trealla (note that this isn't a "hard fork" -- just a WIP pull request fork).

Sorry, forgot to make it public again. Bad timing.

Just got a 404 too. I wonder why they took it private.

As a side note: the phrase "plain-old C" is meaningless, it's more useful to say "ANSI C", "C99" etc. When I see "plain-old C", I'm not sure if I should expect some ancient K&R C.

Can someone tell me how this works? It’s from parser.c but I just want a general idea of the C construct itself.

    const char *src = is_static(l) ? l->val_str : is_strbuf(l) ? (char*)l->val_strb->cstr + l->strb_off : (char*)l->val_chr;

(a ? b : c) means (if a then b else c). The line is a nested if-else construct:

  if l is static string (?)
  then src = l->val_str
  else if l is a string buffer
  then src = l->val_strb_cstr + l->strb_off
  else src = l->val_chr

?: Is like if, but it’s an expression rather than a statement so it can go lots of places.

I can’t see where l is declared. I’d guess it is a union. The tests figure out what kind of structure is passed in. either a plain old c string, a cstring in a big buffer, or a char.

I think that’s the gist in words. Kinda like a match expression over a sum type

Well l is a cell pointer to a list. The nested if-then-else is riffing on the cell's tag to hide all the numerous internal representations for an atom/string, eg. intern'd to cell, in fixed atom-table, as malloc'd C-string, as slice of some other string or somewhere in a mmap'd file. It's ugly, but that's C sometimes... the ugly truth.

Thanks, all. I recognized the ternary operator but should have been clearer. I am flummoxed as to what happens at compile time. This looks like a variable declaration but with executable code??

The conditions are evaluated at runtime, once.

I’ll be darned, thanks

Reply on news.ycombinator.com