4 ms·

Can you explain a bit more how exactly this string representation works, and how it differs from how strings are represented in Haskell? Also, what are you appl

Can you explain a bit more how exactly this string representation works, and how it differs from how strings are represented in Haskell? Also, what are you applying Prolog to these days?

triska 6y ago
The "naive" and straight-forward way to internally represent a non-empty list is to use a structure of the form (CAR . CDR), where car is the first element of the list, and CDR is the rest of the list. So, you need 3 memory "cells" (i.e., pointers, addresses) for each element in the list: First, the indication that this is a structure of this form (a "cons-cell", in Lisp terminology), then, a pointer to the first element (or that first element itself, if it can be represented in a single tagged cell), and then a pointer to the remainder of the list, which is again of this shape. On 64-bit systems, a cell takes 8 bytes. Therefore, when representing a list of bytes, this representation incurs a 3×8 = 24-fold overhead (!) over a plain sequence of bytes in memory. For example, to represent a 1GB file (which is not very large by contemporary standards) in memory, this representation takes 24GB, which is unacceptable. There are ways to compress this slightly (by "slightly", I mean a small factor, such as a factor of 2), but the fundamental problem remains: Instead of using bytes directly, this representation uses one cell per byte, which is an 8-fold overhead. This is an overarching issue in all languages that represent strings as lists (lists of characters, or lists of integers), such as Erlang, Haskell and Prolog. At the same time, lists – especially lists of characters – are the desired representation we want to use in programs in these languages, because it means that the built-in functionality for reasoning about lists becomes directly available for strings too, and it helps to keep the number of language concepts small. So, how to solve it? Ideally, certainly not by adding another data type to the language ("binary object", "binary string" etc.), because that would forfeit the advantages we get from using lists, and would also make the language harder to teach and learn. Therefore, we ideally solve this with a better internal representation of strings: We internally (i.e., in the virtual machine), represent strings as sequences of plain bytes. Not cells, but direct bytes, using UTF-8 encoding. And when the virtual machine encounters this type internally, then it acts as if a list were encountered, making this array of bytes appear as a list (of characters, or of integers) to programmers. Internally, the system can "tell" whether a sequence of bytes denotes such a list, for example because they are allocated in a dedicated region of the memory, and suitably tagged pointers are used to refer to such sequences, as is the case for other data types such as large integers. This much more compact representation was first explained by Ulrich Neumerkel in an issue for Scryer Prolog: https://github.com/mthom/scryer-prolog/issues/24 https://github.com/mthom/scryer-prolog/issues/24 The general idea can be applied to Haskell and Erlang too. In another issue, Ulrich explained in more detail how to extend it to partial lists, i.e., Prolog terms that are not lists, but can still become lists: https://github.com/mthom/scryer-prolog/issues/95 https://github.com/mthom/scryer-prolog/issues/95 This latter issue is unique to logic programming languages like Prolog. Trealla Prolog has already taken the idea to its extreme in that it uses mmap to map an entire file as is into memory when parsing, so that parsing from files becomes extremely efficient: The data from disk appears as a sequence of bytes in memory (the underlying operating system performs the mapping), and the Prolog virtual machine ensures that the byte sequence appears as a list of characters to Prolog programs. So, finally, we can use Prolog for its intended application: efficient, general and convenient parsing of text. PostScript is another good existing example of this combination: Internally, the PostScript interpreter can represent strings very compactly, while to PostScript programs, strings can be used seamlessly like lists. For instance, we get: GS>(hello) { = } forall 104 101 108 108 111 As to your other question: These days, I am applying Prolog for example to reason about safety properties of clinical trial designs, and I am interested in applying logic programming to automate cross-border evidence exchange that member states of the European Union must ensure to satisfy the requirements of the Single Digital Gateway Regulation.
- jpcooper 6y ago
  Thanks for the explanation. This makes sense. In Haskell, strict ByteStrings are a pointer, plus an offset, plus a length. You can call the unpack function on them, which provides a lazy list (it reads from the pointer in blocks) of the characters pointed to. There is also a library that provides lazy ByteStrings from mmapped files. The Prolog stuff sounds quite interesting. I suppose you haven't published anything about the cross-border stuff? Quite a while ago I was using linear programming to build a home energy optimisation system, modelling the workings of a battery, solar panel, energy usage and energy tariffs. The whole thing was a big min-cost flow network. The output was a series of commands to hopefully optimise energy usage. I defined the programme with glpk-hs (a Haskell library which can output in the CPLEX format) and then ran the programmes with cbc. It was very complex, and I later realised that what I really needed was a more general system which combined linear and logic. Someone on HN mentioned ECLiPSe, but I see that you mention SWI quite a bit on your website. What can you recommend for the sort of thing I was doing? I am not an expert in linear programming, and I also found all the options of CBC a bit overwhelming.
  - triska 6y ago
    The key attraction of the representation I mentioned is that on the level of Prolog programs, the compactly represented lists appear like any other lists, no matter how they are internally represented. So, internally, it is a sequence of raw bytes, and to Prolog programmers, it appears as a Prolog list of characters. In Haskell, as long as we are forced to use ByteString or similar data types to get this efficient representation, the situation is not as convenient: ByteString is not the same type as String, and we have to convert manually between them, i.e., within Haskell programs. So, this causes overhead for programmers: We have to learn a new type with new interfaces, call an unpack function etc. A conceptually simpler solution would be to reduce the number of different types in Haskell programs, and instead implement String (i.e., [Char]) more efficiently internally so that it can be directly used instead. For comparison, in Trealla Prolog, when we write the string "hello", then it is automatically internally represented in the efficient way as raw bytes. And on the Prolog level, it appears as a list of characters, corresponding to a String in Haskell: ?- "hello" = [h,e,l,l,o]. true. To read from files, there is a single predicate phrase_from_file/2 that internally performs the mmap call. On the Prolog level, we again only see a list of characters, and we can use DCGs as usual to process them. So, the key attraction is that this efficient representation is transparent to the programmer in the sense that lists that are represented in this way are semantically completely indistinguishable from lists that are represented in the naive way internally. To Prolog programs, they have the exact same type, shape, length etc., they are only represented differently internally in the virtual machine. This idea can be used in Erlang and Haskell too to represent strings. Currently, SICStus Prolog is the only Prolog system that can be reliably used for linear programming with constraints and is fast enough, see its library(clpq). I hope that a free Prolog system with a similar feature set will eventually become available. Currently, Scryer Prolog is looking very promising, especially due to the mentioned efficient internal representation of characters and its strong commitment to the Prolog ISO standard. There is ongoing work on a simplex library for Scryer Prolog, please see this issue and the linked file: https://github.com/mthom/scryer-prolog/issues/463 https://github.com/mthom/scryer-prolog/issues/463 The library contains functionality for solving transportation and assignment problems via network flow algorithms. This sounds similar to your use case, and I hope it works for you.
dnautics 6y ago
it's a linked list of utf codepoints. It's actually a terrible representation for most purposes. More modern parts of the BEAM (e.g. tcp/udp) typically give the option to emit a "binary", which is a immutable contiguous memory region of bytes, and Elixir, which also runs on the BEAM defaults to using "Strings" (cap S) which are "binary"s, but semantically interpreted to contain UTF-8 encoded utf codepoints. For some things, though lists are REALLY good. BEAM languages constructs are generally immutable, so if you pass your string (or String), to a function that then changes the contents, it doesn't affect the value seen by the original function after it returns. This is a GOOD thing as it reduces the cognitive burden. Conversely, performance of binaries in this immutability regime can get hairy because as you start concatenating them or editing them you have to make tons of immutable copies of stuff, which is no fun for anyone. (Literally last month we had a problem in prod because megabytes-sized JSON strings were being copied around after minor appends). The middleground is something that erlang calls an "iolist" which is a (list of (iolist or binaries or utf codepoints)). Elixir has "iodata" which is (iolist or binary) This is nice, because you have o(1) append, o(1) prepend, and for long stretches that aren't going to change, you can use binaries instead of awkward utf codepoint list structures.
- jpcooper 6y ago
  Haskell allows you to build a (lazy) linked list of characters sourced in blocks from strict ByteStrings, which are pointers to bytes with an offset and length. Leaving out the garbage collection of the cons cells (I would hope that the cons cells are reused in some situations, but I don't know the specifics), I think this is quite a nice interface. iolist sounds like lazy ByteStrings in Haskell. They are lists of strict ByteStrings.

Can you explain a bit more how exactly this string representation works, and how it differs from how strings are represented in Haskell? Also, what are you applying Prolog to these days?

triska 6y ago

The "naive" and straight-forward way to internally represent a non-empty list is to use a structure of the form (CAR . CDR), where car is the first element of the list, and CDR is the rest of the list. So, you need 3 memory "cells" (i.e., pointers, addresses) for each element in the list: First, the indication that this is a structure of this form (a "cons-cell", in Lisp terminology), then, a pointer to the first element (or that first element itself, if it can be represented in a single tagged cell), and then a pointer to the remainder of the list, which is again of this shape. On 64-bit systems, a cell takes 8 bytes. Therefore, when representing a list of bytes, this representation incurs a 3×8 = 24-fold overhead (!) over a plain sequence of bytes in memory. For example, to represent a 1GB file (which is not very large by contemporary standards) in memory, this representation takes 24GB, which is unacceptable. There are ways to compress this slightly (by "slightly", I mean a small factor, such as a factor of 2), but the fundamental problem remains: Instead of using bytes directly, this representation uses one cell per byte, which is an 8-fold overhead. This is an overarching issue in all languages that represent strings as lists (lists of characters, or lists of integers), such as Erlang, Haskell and Prolog. At the same time, lists – especially lists of characters – are the desired representation we want to use in programs in these languages, because it means that the built-in functionality for reasoning about lists becomes directly available for strings too, and it helps to keep the number of language concepts small. So, how to solve it? Ideally, certainly not by adding another data type to the language ("binary object", "binary string" etc.), because that would forfeit the advantages we get from using lists, and would also make the language harder to teach and learn. Therefore, we ideally solve this with a better internal representation of strings: We internally (i.e., in the virtual machine), represent strings as sequences of plain bytes. Not cells, but direct bytes, using UTF-8 encoding. And when the virtual machine encounters this type internally, then it acts as if a list were encountered, making this array of bytes appear as a list (of characters, or of integers) to programmers. Internally, the system can "tell" whether a sequence of bytes denotes such a list, for example because they are allocated in a dedicated region of the memory, and suitably tagged pointers are used to refer to such sequences, as is the case for other data types such as large integers. This much more compact representation was first explained by Ulrich Neumerkel in an issue for Scryer Prolog: https://github.com/mthom/scryer-prolog/issues/24 https://github.com/mthom/scryer-prolog/issues/24 The general idea can be applied to Haskell and Erlang too. In another issue, Ulrich explained in more detail how to extend it to partial lists, i.e., Prolog terms that are not lists, but can still become lists: https://github.com/mthom/scryer-prolog/issues/95 https://github.com/mthom/scryer-prolog/issues/95 This latter issue is unique to logic programming languages like Prolog. Trealla Prolog has already taken the idea to its extreme in that it uses mmap to map an entire file as is into memory when parsing, so that parsing from files becomes extremely efficient: The data from disk appears as a sequence of bytes in memory (the underlying operating system performs the mapping), and the Prolog virtual machine ensures that the byte sequence appears as a list of characters to Prolog programs. So, finally, we can use Prolog for its intended application: efficient, general and convenient parsing of text. PostScript is another good existing example of this combination: Internally, the PostScript interpreter can represent strings very compactly, while to PostScript programs, strings can be used seamlessly like lists. For instance, we get: GS>(hello) { = } forall 104 101 108 108 111 As to your other question: These days, I am applying Prolog for example to reason about safety properties of clinical trial designs, and I am interested in applying logic programming to automate cross-border evidence exchange that member states of the European Union must ensure to satisfy the requirements of the Single Digital Gateway Regulation.

jpcooper 6y ago
Thanks for the explanation. This makes sense. In Haskell, strict ByteStrings are a pointer, plus an offset, plus a length. You can call the unpack function on them, which provides a lazy list (it reads from the pointer in blocks) of the characters pointed to. There is also a library that provides lazy ByteStrings from mmapped files. The Prolog stuff sounds quite interesting. I suppose you haven't published anything about the cross-border stuff? Quite a while ago I was using linear programming to build a home energy optimisation system, modelling the workings of a battery, solar panel, energy usage and energy tariffs. The whole thing was a big min-cost flow network. The output was a series of commands to hopefully optimise energy usage. I defined the programme with glpk-hs (a Haskell library which can output in the CPLEX format) and then ran the programmes with cbc. It was very complex, and I later realised that what I really needed was a more general system which combined linear and logic. Someone on HN mentioned ECLiPSe, but I see that you mention SWI quite a bit on your website. What can you recommend for the sort of thing I was doing? I am not an expert in linear programming, and I also found all the options of CBC a bit overwhelming.
- triska 6y ago
  The key attraction of the representation I mentioned is that on the level of Prolog programs, the compactly represented lists appear like any other lists, no matter how they are internally represented. So, internally, it is a sequence of raw bytes, and to Prolog programmers, it appears as a Prolog list of characters. In Haskell, as long as we are forced to use ByteString or similar data types to get this efficient representation, the situation is not as convenient: ByteString is not the same type as String, and we have to convert manually between them, i.e., within Haskell programs. So, this causes overhead for programmers: We have to learn a new type with new interfaces, call an unpack function etc. A conceptually simpler solution would be to reduce the number of different types in Haskell programs, and instead implement String (i.e., [Char]) more efficiently internally so that it can be directly used instead. For comparison, in Trealla Prolog, when we write the string "hello", then it is automatically internally represented in the efficient way as raw bytes. And on the Prolog level, it appears as a list of characters, corresponding to a String in Haskell: ?- "hello" = [h,e,l,l,o]. true. To read from files, there is a single predicate phrase_from_file/2 that internally performs the mmap call. On the Prolog level, we again only see a list of characters, and we can use DCGs as usual to process them. So, the key attraction is that this efficient representation is transparent to the programmer in the sense that lists that are represented in this way are semantically completely indistinguishable from lists that are represented in the naive way internally. To Prolog programs, they have the exact same type, shape, length etc., they are only represented differently internally in the virtual machine. This idea can be used in Erlang and Haskell too to represent strings. Currently, SICStus Prolog is the only Prolog system that can be reliably used for linear programming with constraints and is fast enough, see its library(clpq). I hope that a free Prolog system with a similar feature set will eventually become available. Currently, Scryer Prolog is looking very promising, especially due to the mentioned efficient internal representation of characters and its strong commitment to the Prolog ISO standard. There is ongoing work on a simplex library for Scryer Prolog, please see this issue and the linked file: https://github.com/mthom/scryer-prolog/issues/463 https://github.com/mthom/scryer-prolog/issues/463 The library contains functionality for solving transportation and assignment problems via network flow algorithms. This sounds similar to your use case, and I hope it works for you.

dnautics 6y ago

it's a linked list of utf codepoints. It's actually a terrible representation for most purposes. More modern parts of the BEAM (e.g. tcp/udp) typically give the option to emit a "binary", which is a immutable contiguous memory region of bytes, and Elixir, which also runs on the BEAM defaults to using "Strings" (cap S) which are "binary"s, but semantically interpreted to contain UTF-8 encoded utf codepoints. For some things, though lists are REALLY good. BEAM languages constructs are generally immutable, so if you pass your string (or String), to a function that then changes the contents, it doesn't affect the value seen by the original function after it returns. This is a GOOD thing as it reduces the cognitive burden. Conversely, performance of binaries in this immutability regime can get hairy because as you start concatenating them or editing them you have to make tons of immutable copies of stuff, which is no fun for anyone. (Literally last month we had a problem in prod because megabytes-sized JSON strings were being copied around after minor appends). The middleground is something that erlang calls an "iolist" which is a (list of (iolist or binaries or utf codepoints)). Elixir has "iodata" which is (iolist or binary) This is nice, because you have o(1) append, o(1) prepend, and for long stretches that aren't going to change, you can use binaries instead of awkward utf codepoint list structures.

jpcooper 6y ago
Haskell allows you to build a (lazy) linked list of characters sourced in blocks from strict ByteStrings, which are pointers to bytes with an offset and length. Leaving out the garbage collection of the cons cells (I would hope that the cons cells are reused in some situations, but I don't know the specifics), I think this is quite a nice interface. iolist sounds like lazy ByteStrings in Haskell. They are lists of strict ByteStrings.