6 ms·

Erlang is an amazing language, with many great design decisions! For example, quoting from the paper: “Very early on we decided that strings were lists. This w

by triska 6y ago

Erlang is an amazing language, with many great design decisions! For example, quoting from the paper: “Very early on we decided that strings were lists. This was partly environment as many of the languages we were using, such as Prolog, use lists and partly practical as lists are a very powerful data type.” Lists are extremely convenient to handle in Erlang, and they are an ideal representation of text for many purposes. This convenient representation can also be implemented efficiently, in such a way that compact UTF-8 based encoding is used internally, while the string appears as a list to programmers. Two recent Prolog systems, Scryer Prolog and Trealla Prolog, do this already. It is to be hoped that future Erlang and also Haskell implementations will adopt this idea to combine convenience with efficiency, eliminating the need for additional types to compactly represent binary objects, and allowing fast reading from files via mmap. In university, we had a distributed systems class with many very involved exercises. They were involved mostly because we had to use Java: Out of interest, I also solved the exercises in Erlang, and that usually allowed much shorter and more convenient solutions.

styluss 6y ago
When I did Distributed Systems in Uni, it was in C (huuuge mess) and when I visited another Uni, they joked that they taught the course in Java, because "we're not savages". I keep thinking how much more we could've actually learned about DS if we weren't fighting fires with C.
- deleted 6y ago
  [deleted]
- tormeh 6y ago
  I regard all distributed systems not written in a BEAM language with suspicion. Just seems a bit weird not to use a tech stack designed specifically for your problem. It's not everything, of course, but it's definitely a strike against a project
  - froh 6y ago
    As I had to look it up: BEAM is the erlang virtual machine. A number of languages can be happily compiled to BEAM: https://news.ycombinator.com/item?id=13446521 https://news.ycombinator.com/item?id=13446521
    - macintux 6y ago
      Over 20 languages, in fact. https://gist.github.com/macintux/6349828#alternative-languages-targeting-the-erlang-vm https://gist.github.com/macintux/6349828#alternative-languag...
      - ProfHewitt 6y ago
        It could be very difficult to implement an industrial-strength Java on BEAM :-(
        macintux 6y ago
        I'd think so, given the immutability, lightweight processes, and other Erlang-specific features baked into the BEAM. That's one reason I like Erlang and the BEAM so much: it's an opinionated language running on an opinionated VM that are made for each other, not a general-purpose system that has to be all things to all people. The JVM is perfectly adequate as a kitchen sink. The BEAM doesn't need to be.
        ProfHewitt 6y ago
        Although the JVM has many limitations, it has important capabilities that are lacking in BEAM. The limitations of BEAM are severe, especially for implementing Universal Intelligent Systems, which is the primary challenge of Computer Science for this decade. See the following: Project Liftoff: Universal Intelligent Systems (UIS) by 2030 https://papers.ssrn.com/abstract=3428114 https://papers.ssrn.com/abstract=3428114
jpcooper 6y ago
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.
sean_pedersen 6y ago
I had the pleasure of using Erlang in Data Structures, Graph Theory and Distributed Systems classes in university, had been lucky with the professor.
ProfHewitt 6y ago
Erlang made a fundamentally good design decision in reinventing the Actor paradigm [Hewitt, Bishop, and Steiger 1973]. However, many of the language design decisions were compromised. It's amazing that Armstrong, et. al. got as far as they did without formal foundational principles. Unfortunately, Erlang still lacks a rigorous formal foundation :-(

by triska 6y ago

styluss 6y ago

When I did Distributed Systems in Uni, it was in C (huuuge mess) and when I visited another Uni, they joked that they taught the course in Java, because "we're not savages". I keep thinking how much more we could've actually learned about DS if we weren't fighting fires with C.

deleted 6y ago
[deleted]
tormeh 6y ago
I regard all distributed systems not written in a BEAM language with suspicion. Just seems a bit weird not to use a tech stack designed specifically for your problem. It's not everything, of course, but it's definitely a strike against a project
- froh 6y ago
  As I had to look it up: BEAM is the erlang virtual machine. A number of languages can be happily compiled to BEAM: https://news.ycombinator.com/item?id=13446521 https://news.ycombinator.com/item?id=13446521
  - macintux 6y ago
    Over 20 languages, in fact. https://gist.github.com/macintux/6349828#alternative-languages-targeting-the-erlang-vm https://gist.github.com/macintux/6349828#alternative-languag...
    - ProfHewitt 6y ago
      It could be very difficult to implement an industrial-strength Java on BEAM :-(
      - macintux 6y ago
        I'd think so, given the immutability, lightweight processes, and other Erlang-specific features baked into the BEAM. That's one reason I like Erlang and the BEAM so much: it's an opinionated language running on an opinionated VM that are made for each other, not a general-purpose system that has to be all things to all people. The JVM is perfectly adequate as a kitchen sink. The BEAM doesn't need to be.
        ProfHewitt 6y ago
        Although the JVM has many limitations, it has important capabilities that are lacking in BEAM. The limitations of BEAM are severe, especially for implementing Universal Intelligent Systems, which is the primary challenge of Computer Science for this decade. See the following: Project Liftoff: Universal Intelligent Systems (UIS) by 2030 https://papers.ssrn.com/abstract=3428114 https://papers.ssrn.com/abstract=3428114

jpcooper 6y ago

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.

sean_pedersen 6y ago

I had the pleasure of using Erlang in Data Structures, Graph Theory and Distributed Systems classes in university, had been lucky with the professor.

ProfHewitt 6y ago

Erlang made a fundamentally good design decision in reinventing the Actor paradigm [Hewitt, Bishop, and Steiger 1973]. However, many of the language design decisions were compromised. It's amazing that Armstrong, et. al. got as far as they did without formal foundational principles. Unfortunately, Erlang still lacks a rigorous formal foundation :-(