7 ms·

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

126 points by nikolay 4y ago

triska 4y ago
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 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!
- mst 4y ago
  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-difference-between-and-in-prolog/8269897#8269897 https://stackoverflow.com/questions/8264699/what-is-the-diff... seems to help.
  - triska 4y ago
    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.
- billfruit 4y ago
  How does this and Scryer, Tau all compare with the SWI?
  - triska 4y ago
    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_ISO 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.
    - billfruit 4y ago
      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.
      - triska 4y ago
        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.
        4y ago
- jfmc 4y ago
  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.
tomcam 4y ago
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;
- deleted 4y ago
  [deleted]
- i_don_t_know 4y ago
  (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
- jfoutz 4y ago
  ?: 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
- infradig 4y ago
  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.
- tomcam 4y ago
  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??
  - zeckalpha 4y ago
nextaccountic 4y ago
It says page not found
- james-redwood 4y ago
  Just got a 404 too. I wonder why they took it private.
- nikolay 4y ago
  It was just made private, I guess. Only the Go WebAssembly project is still public: https://github.com/trealla-prolog/trealla-go https://github.com/trealla-prolog/trealla-go
- grose 4y ago
  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 https://github.com/guregu/trealla (note that this isn't a "hard fork" -- just a WIP pull request fork).
- nreilly 4y ago
  Seems they just recreated the git repo to clear out ~1gb of history. https://github.com/trealla-prolog/trealla/issues/1 https://github.com/trealla-prolog/trealla/issues/1
  - pabs3 4y ago
    I wonder why that would be needed. There is always shallow clones if that is too much to download.
- infradig 4y ago
  Sorry, forgot to make it public again. Bad timing.
moonchild 4y ago
> 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?
- infradig 4y ago
  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.
  - dkjaudyeqooe 4y ago
    I was actually trying to find where the bytecode is evaluated, but it doesn't leap out at you, can you provide any pointers?
dvfjsdhgfv 4y ago
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.
jjice 4y ago
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.

126 points by nikolay 4y ago

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 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!

mst 4y ago
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-difference-between-and-in-prolog/8269897#8269897 https://stackoverflow.com/questions/8264699/what-is-the-diff... seems to help.
- triska 4y ago
  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.
billfruit 4y ago
How does this and Scryer, Tau all compare with the SWI?
- triska 4y ago
  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_ISO 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.
  - billfruit 4y ago
    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.
    - triska 4y ago
      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.
      - 4y ago
jfmc 4y ago
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.

tomcam 4y ago

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;

deleted 4y ago
[deleted]
i_don_t_know 4y ago
(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
jfoutz 4y ago
?: 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
infradig 4y ago
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.
tomcam 4y ago
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??
- zeckalpha 4y ago

nextaccountic 4y ago

It says page not found

james-redwood 4y ago
Just got a 404 too. I wonder why they took it private.
nikolay 4y ago
It was just made private, I guess. Only the Go WebAssembly project is still public: https://github.com/trealla-prolog/trealla-go https://github.com/trealla-prolog/trealla-go
grose 4y ago
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 https://github.com/guregu/trealla (note that this isn't a "hard fork" -- just a WIP pull request fork).
nreilly 4y ago
Seems they just recreated the git repo to clear out ~1gb of history. https://github.com/trealla-prolog/trealla/issues/1 https://github.com/trealla-prolog/trealla/issues/1
- pabs3 4y ago
  I wonder why that would be needed. There is always shallow clones if that is too much to download.
infradig 4y ago
Sorry, forgot to make it public again. Bad timing.

moonchild 4y ago

> 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?

infradig 4y ago
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.
- dkjaudyeqooe 4y ago
  I was actually trying to find where the bytecode is evaluated, but it doesn't leap out at you, can you provide any pointers?

dvfjsdhgfv 4y ago

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.

jjice 4y ago

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.