The Erlang Rationale (2008) [pdf]

https://drive.google.com/file/d/1zKsOgwZJ_YZ1bY3b3gNRjAxpn6VneR8b/view

by signa11 • 6 years ago

94 38 6 years ago

drive.google.com

triska3• 6 years 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• 6 years 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.

tormeh• 6 years 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

jpcooper10• 6 years 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?

triska3• 6 years 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

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

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.

dnautics3• 6 years 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.

sean_pedersen• 6 years 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.

ProfHewitt11• 6 years 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 :-(

ProfHewitt11• 6 years 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• 6 years 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...

"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...

ProfHewitt11• 6 years ago

In general, an Actor receiving a message enters its region of

mutual exclusion (which can have holes), which is explained

here:

https://papers.ssrn.com/abstract=3459566

Is there a rigorous formalization of Erlang message passing?

dnautics3• 6 years ago

I think Prof. Hewitt should one of these days actually write a working system in Erlang or Elixir. I suggest to Carl that he write something easy (and potentially useful), like a DNS server, as a starting point. Raft might also be fun, that's about 350-500 lines to do as it is in the paper, and maybe about 600 with the upgrades necessary to get a correct consensus protocol.

ProfHewitt11• 6 years ago

There are a number of very useful systems written for BEAM!

Consensus protocols are too slow for Universal Intelligent Systems (UIS) :-(

See the following for UIS:

https://papers.ssrn.com/abstract=3428114

jpcooper10• 6 years 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.

ProfHewitt11• 6 years 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• 6 years 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.

jpcooper10• 6 years 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.

ProfHewitt11• 6 years ago

Strong types are very important for concurrency.

However, by themselves, strong types do not provide proofs.

See the following for proofs of strongly-typed concurrent systems:

https://papers.ssrn.com/abstract=3418003

Strongly-typed programming languages need to provide

additional capabilities for error processing and recovery.

The Erlang Rationale (2008) [pdf]

Related Stories