6 ms·

This is extremely cool and I will be testing it out. I’m building large systems for handling biological data, and have wanted to use prolog for that use, but co

by koeng 5y ago

This is extremely cool and I will be testing it out. I’m building large systems for handling biological data, and have wanted to use prolog for that use, but couldn’t fit all of my data in RAM. This could help me a bunch.

triska 5y ago
Importantly for this use case, Scryer Prolog represents lists of characters very compactly internally, using a sequence of raw bytes! It is the first Prolog system to use this efficient representation. This helps considerably when processing huge amounts of data, for example when parsing large text corpora with Prolog's built-in grammar mechanism, definite clause grammars (DCGs).
- tannhaeuser 5y ago
  Sure about that? It is/was pretty common to keep strings as long as possible, and convert to list of chars lazily only when absolutely necessary.
  - triska 5y ago
    The key innovation of Scryer Prolog in this respect is that the system internally, i.e., within Rust, represents each string as a sequence of raw bytes (UTF-8 encoded, 0-terminated), and to Prolog programs, the string appears as if it were a list of characters (i.e., atoms of length 1). So, no conversion is necessary at all: The compact internal representation is used whenever possible, and Prolog programs only see lists of characters all of the time, making common predicates such as append/3 and length/2, and most importantly DCGs, automatically usable for reasoning about strings. For example, the string "abc" takes only 4 bytes in this representation, and the unification "abc" = [a,b,c] succeeds. Indeed, we have: ?- write_canonical("abc"). '.'(a,'.'(b,'.'(c,[]))) true. On 64-bit systems, a conventional internal representation of "abc" as the compound term .(a, .(b, .(c, []))) takes 8 bytes per functor (each '.'/2 takes 8 bytes, i.e., 1 cell in the WAM), 8 bytes per character (as a pointer to the atom table, again 1 cell in the WAM), and 8 bytes for each tail. All Prolog systems before Scryer Prolog use 16 to 24 times as much memory to represent a list of characters. As of recent, Trealla Prolog also uses the efficient representation, at least for fully instantiated strings. Scryer Prolog can also represent partial strings such as [a,b,c|Ls] with the efficient encoding.
    - tannhaeuser 5y ago
      > All Prolog systems before Scryer Prolog use 16 to 24 times as much memory to represent a list of characters. That's not correct. As I said, it's a pretty basic optimization to store strings as native char buffers, and then only convert to explicit list representation if a variable bound to a string in that way is used in eg unification against a (partial) list, or subjected to a list (or other non-string) builtin. Definitely not new with Scryer Prolog; maybe true of F/OSS Prologs though I doubt it.
      - triska 5y ago
        Scryer Prolog does not convert such char buffers to an explicit list representation, they always remain raw bytes. Erlang uses an analogous idea for lists of codes to represent strings. In Scryer Prolog, this pays off especially nicely because the flag double_quotes is set to chars by default; it is one of the few systems in several decades to do this (most other systems currently use the value codes), and therefore this compact internal representation can be easily used in programs, yielding readable strings that can be efficiently processed.
still_grokking 5y ago
A little bit off-topic, but still related: I could imagine the Flix language being a good fit for that use case. https://flix.dev/ https://flix.dev/ It has first-class Datalog constraints as a language feature! As being a FP language it's of course good at modeling data. At the same time it's fast enough for heavy tasks: It runs on the JVM, having also access to its rich ecosystem.

by koeng 5y ago

triska 5y ago

Importantly for this use case, Scryer Prolog represents lists of characters very compactly internally, using a sequence of raw bytes! It is the first Prolog system to use this efficient representation. This helps considerably when processing huge amounts of data, for example when parsing large text corpora with Prolog's built-in grammar mechanism, definite clause grammars (DCGs).

tannhaeuser 5y ago
Sure about that? It is/was pretty common to keep strings as long as possible, and convert to list of chars lazily only when absolutely necessary.
- triska 5y ago
  The key innovation of Scryer Prolog in this respect is that the system internally, i.e., within Rust, represents each string as a sequence of raw bytes (UTF-8 encoded, 0-terminated), and to Prolog programs, the string appears as if it were a list of characters (i.e., atoms of length 1). So, no conversion is necessary at all: The compact internal representation is used whenever possible, and Prolog programs only see lists of characters all of the time, making common predicates such as append/3 and length/2, and most importantly DCGs, automatically usable for reasoning about strings. For example, the string "abc" takes only 4 bytes in this representation, and the unification "abc" = [a,b,c] succeeds. Indeed, we have: ?- write_canonical("abc"). '.'(a,'.'(b,'.'(c,[]))) true. On 64-bit systems, a conventional internal representation of "abc" as the compound term .(a, .(b, .(c, []))) takes 8 bytes per functor (each '.'/2 takes 8 bytes, i.e., 1 cell in the WAM), 8 bytes per character (as a pointer to the atom table, again 1 cell in the WAM), and 8 bytes for each tail. All Prolog systems before Scryer Prolog use 16 to 24 times as much memory to represent a list of characters. As of recent, Trealla Prolog also uses the efficient representation, at least for fully instantiated strings. Scryer Prolog can also represent partial strings such as [a,b,c|Ls] with the efficient encoding.
  - tannhaeuser 5y ago
    > All Prolog systems before Scryer Prolog use 16 to 24 times as much memory to represent a list of characters. That's not correct. As I said, it's a pretty basic optimization to store strings as native char buffers, and then only convert to explicit list representation if a variable bound to a string in that way is used in eg unification against a (partial) list, or subjected to a list (or other non-string) builtin. Definitely not new with Scryer Prolog; maybe true of F/OSS Prologs though I doubt it.
    - triska 5y ago
      Scryer Prolog does not convert such char buffers to an explicit list representation, they always remain raw bytes. Erlang uses an analogous idea for lists of codes to represent strings. In Scryer Prolog, this pays off especially nicely because the flag double_quotes is set to chars by default; it is one of the few systems in several decades to do this (most other systems currently use the value codes), and therefore this compact internal representation can be easily used in programs, yielding readable strings that can be efficiently processed.

still_grokking 5y ago

A little bit off-topic, but still related: I could imagine the Flix language being a good fit for that use case. https://flix.dev/ https://flix.dev/ It has first-class Datalog constraints as a language feature! As being a FP language it's of course good at modeling data. At the same time it's fast enough for heavy tasks: It runs on the JVM, having also access to its rich ecosystem.