13 ms·

The Erlang Rationale (2008) [pdf]

94 points by signa11 6y ago

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 :-(
ProfHewitt 6y ago
This is an excellent summary of rationale for Erlang with the goals stated at the beginning of the article! However, the Erlang language itself is now rather dated :-( In order to implement next generation Universal Intelligent Systems [Hewitt 2019], the following extensions to Erlang are needed: • Automatic reclamation of processes. For example, Erlang uses Process Identifiers (PIDs) to communicate between processes. However, a process that has a process identifier (say ProcessIdentifier) of a process with which it communicates can launch a denial of service attack to kill that process using exit(ProcessIdentifier, kill). An Erlang process can be orphaned if its Process Identifier (PID) becomes inaccessible. By default, the send operation in Erlang always succeeds (even if the target is a non-existing process). • Strong parameterized types with no type Any. • Region of mutual exclusion for an Erlang process. An Erlang process does not have a region of mutual exclusion, which can lead to internal conflicts within processes. • Behavior change using variables in a region of mutual exclusion instead of having to create auxiliary processes to hold state with callbacks. [Swain 2014] In particular, o Better support for holes in the region of mutual exclusion of an Actor implementation. For example, in Erlang it is necessary for application programmers to explicitly code a request handler for each re-entry into the region of mutual exclusion potentially enabling cyberattacks from outside the process. o Better ways to upgrade Actors in place without losing work in progress.
- al2o3cr 6y ago
  "However, a process that has a process identifier (say ProcessIdentifier) of a process with which it communicates can launch a denial of service attack to kill that process" The BEAM does not promise (or provide) secure isolation between processes within a single VM. It's even called out in their bug report policy: https://github.com/erlang/otp/wiki/FAQ:-What-kind-of-patches-will-be-approved%3F#can-i-write-a-patch-to-increase-the-security-of-the-erlang-distribution https://github.com/erlang/otp/wiki/FAQ:-What-kind-of-patches... "An Erlang process does not have a region of mutual exclusion, which can lead to internal conflicts within processes." I don't follow the use of "mutual exclusion" in this statement; the only thing that can write to a process's stack or heap is the process - what kind of "conflicts" do you mean? "For example, in Erlang it is necessary for application programmers to explicitly code a request handler for each re-entry into the region of mutual exclusion" This sentence doesn't help either, because the previous statement was that the processes don't _have_ the region this objects to writing handlers for entering...
jpcooper 6y ago
The author says that he sees no need to include types in the language. There have been efforts to create typed languages which run on the Erlang BEAM virtual machine. I would be interested to know more about why the author thought that types were not useful.
- ProfHewitt 6y ago
  Excellent point! Attempts are being made to graft types onto Erlang. However, they are limited by compatibility requirements with existing large existing programs and libraries :-(
- tyu2 6y ago
  From one perspective types (and I mean proofs encoded in types) is a compile time measure against bugs, while supervisors is a runtime measure. It's much easier and more productive to not do proofs and rely on runtime architecture for reliability, it adds relatively little complexity and asks very little from developers, it stays almost the same as regular software development. And it's still necessary to do regardless whether you have proofs or not. And types like machine types are of course irrelevant for BEAM, well, maybe they'll start to matter a bit with JIT, but probably still not, BEAM with JIT is still not going to be a performance miracle.
  - jpcooper 6y ago
    Without trying to sound too flamebaity, as typed versus untyped has been discussed endlessly, I would like to see a study which compares development time and reliability between a Erlang and another typed language running on BEAM. That is, typed versus untyped for the sort of systems which are built with Erlang.
    - lostcolony 6y ago
      So I can say from experience, none of the production issues we ran into in two and a half years of Erlang would have been solved by better typing. That said, our own practices meant we included a lot of unit and API level tests, and some of the issues I personally caught and fixed when testing might have been avoided by typing, and were, eventually, when we added Dialyzer about a year and a half into the project. Dialyzer itself was worth it to me only insofar as type specs gave me a language to express the typing I was going for, rather than leaving it implicit. It also helped me understand what my colleagues were trying to do in some cases. The explicitness helped me feel better about what I was doing as well; in hindsight I don't think it sped up development, nor did it reduce bugs (though it likely reduced testing time...but that's probably a wash given the time to get the spec right, and update it as data structures evolved). Can't speak to using another language on the BEAM, whose typing isn't optimistic like Dialyzer, but my experience with Dialyzer, at least, left me feeling subjectively better about the code, but objectively and in hindsight I don't feel it gave us measurable improvement. Just more confidence. Which may be enough of a gain; confidence in the system is what you want when you're optimizing for reliability, even if it's not really a gain on that front.
deleted 6y ago
[deleted]

94 points by signa11 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 :-(

ProfHewitt 6y ago

This is an excellent summary of rationale for Erlang with the goals stated at the beginning of the article! However, the Erlang language itself is now rather dated :-( In order to implement next generation Universal Intelligent Systems [Hewitt 2019], the following extensions to Erlang are needed: • Automatic reclamation of processes. For example, Erlang uses Process Identifiers (PIDs) to communicate between processes. However, a process that has a process identifier (say ProcessIdentifier) of a process with which it communicates can launch a denial of service attack to kill that process using exit(ProcessIdentifier, kill). An Erlang process can be orphaned if its Process Identifier (PID) becomes inaccessible. By default, the send operation in Erlang always succeeds (even if the target is a non-existing process). • Strong parameterized types with no type Any. • Region of mutual exclusion for an Erlang process. An Erlang process does not have a region of mutual exclusion, which can lead to internal conflicts within processes. • Behavior change using variables in a region of mutual exclusion instead of having to create auxiliary processes to hold state with callbacks. [Swain 2014] In particular, o Better support for holes in the region of mutual exclusion of an Actor implementation. For example, in Erlang it is necessary for application programmers to explicitly code a request handler for each re-entry into the region of mutual exclusion potentially enabling cyberattacks from outside the process. o Better ways to upgrade Actors in place without losing work in progress.

al2o3cr 6y ago
"However, a process that has a process identifier (say ProcessIdentifier) of a process with which it communicates can launch a denial of service attack to kill that process" The BEAM does not promise (or provide) secure isolation between processes within a single VM. It's even called out in their bug report policy: https://github.com/erlang/otp/wiki/FAQ:-What-kind-of-patches-will-be-approved%3F#can-i-write-a-patch-to-increase-the-security-of-the-erlang-distribution https://github.com/erlang/otp/wiki/FAQ:-What-kind-of-patches... "An Erlang process does not have a region of mutual exclusion, which can lead to internal conflicts within processes." I don't follow the use of "mutual exclusion" in this statement; the only thing that can write to a process's stack or heap is the process - what kind of "conflicts" do you mean? "For example, in Erlang it is necessary for application programmers to explicitly code a request handler for each re-entry into the region of mutual exclusion" This sentence doesn't help either, because the previous statement was that the processes don't _have_ the region this objects to writing handlers for entering...

jpcooper 6y ago

The author says that he sees no need to include types in the language. There have been efforts to create typed languages which run on the Erlang BEAM virtual machine. I would be interested to know more about why the author thought that types were not useful.

ProfHewitt 6y ago
Excellent point! Attempts are being made to graft types onto Erlang. However, they are limited by compatibility requirements with existing large existing programs and libraries :-(
tyu2 6y ago
From one perspective types (and I mean proofs encoded in types) is a compile time measure against bugs, while supervisors is a runtime measure. It's much easier and more productive to not do proofs and rely on runtime architecture for reliability, it adds relatively little complexity and asks very little from developers, it stays almost the same as regular software development. And it's still necessary to do regardless whether you have proofs or not. And types like machine types are of course irrelevant for BEAM, well, maybe they'll start to matter a bit with JIT, but probably still not, BEAM with JIT is still not going to be a performance miracle.
- jpcooper 6y ago
  Without trying to sound too flamebaity, as typed versus untyped has been discussed endlessly, I would like to see a study which compares development time and reliability between a Erlang and another typed language running on BEAM. That is, typed versus untyped for the sort of systems which are built with Erlang.
  - lostcolony 6y ago
    So I can say from experience, none of the production issues we ran into in two and a half years of Erlang would have been solved by better typing. That said, our own practices meant we included a lot of unit and API level tests, and some of the issues I personally caught and fixed when testing might have been avoided by typing, and were, eventually, when we added Dialyzer about a year and a half into the project. Dialyzer itself was worth it to me only insofar as type specs gave me a language to express the typing I was going for, rather than leaving it implicit. It also helped me understand what my colleagues were trying to do in some cases. The explicitness helped me feel better about what I was doing as well; in hindsight I don't think it sped up development, nor did it reduce bugs (though it likely reduced testing time...but that's probably a wash given the time to get the spec right, and update it as data structures evolved). Can't speak to using another language on the BEAM, whose typing isn't optimistic like Dialyzer, but my experience with Dialyzer, at least, left me feeling subjectively better about the code, but objectively and in hindsight I don't feel it gave us measurable improvement. Just more confidence. Which may be enough of a gain; confidence in the system is what you want when you're optimizing for reliability, even if it's not really a gain on that front.

deleted 6y ago

[deleted]