News for hackers. Stuff that matters.
Re:The Erlang Rationale (2008) [pdf] by triska on Friday December 25, 2020 @10:49AM (#25537084)
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.

Re:The Erlang Rationale (2008) [pdf] by styluss on Friday December 25, 2020 @12:18PM (#25537654)
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.

Re:The Erlang Rationale (2008) [pdf] by tormeh on Friday December 25, 2020 @07:16PM (#25540241)
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
Re:The Erlang Rationale (2008) [pdf] by froh on Friday December 25, 2020 @08:32PM (#25540611)
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

Re:The Erlang Rationale (2008) [pdf] by macintux on Friday December 25, 2020 @09:28PM (#25540842)
Re:The Erlang Rationale (2008) [pdf] by ProfHewitt on Sunday December 27, 2020 @12:29AM (#25549095)
It could be very difficult to implement an industrial-strength

Java on BEAM :-(

Re:The Erlang Rationale (2008) [pdf] by macintux on Sunday December 27, 2020 @08:23AM (#25550855)
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.

Re:The Erlang Rationale (2008) [pdf] by ProfHewitt on Sunday December 27, 2020 @01:31PM (#25553121)
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

Re:The Erlang Rationale (2008) [pdf] by jpcooper on Friday December 25, 2020 @12:57PM (#25537916)
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?
Re:The Erlang Rationale (2008) [pdf] by triska on Friday December 25, 2020 @01:44PM (#25538202)
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.
Re:The Erlang Rationale (2008) [pdf] by jpcooper on Friday December 25, 2020 @02:21PM (#25538404)
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.

Re:The Erlang Rationale (2008) [pdf] by triska on Saturday December 26, 2020 @04:17AM (#25542301)
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

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.

Re:The Erlang Rationale (2008) [pdf] by jpcooper on Saturday December 26, 2020 @08:51AM (#25543434)
I think it is nice in Haskell to retain the ability to control the underlying representation of a string. The laziness allows the native linked list representation without the user having to know about the underlying representation. Your memory mapping function can simply return a lazy linked list of chars in Haskell as well. If the underlying representation turns out to be inefficient on the current system, then that can always be tuned by the user. Maybe in Prolog it is sufficient to leave all of that to the runtime system.

Thanks for the Prolog tips. I had a look at clpqr, and could not find any reference to boolean variables and operators. Maybe clpqr intersects with another system whose docs do refer to boolean variables. I could not see how to combine clpqr with clpb. Basically what I would like is for certain linear constraints to be active only if other chosen boolean expressions are true.

Example: Choose energy price based on maximum power usage over past month. There are some Japanese electricity tariffs which do this. There would be a partition of maximum power usage ranges, and each range is associated with a price. Associate a binary variable to each range. Ensure exactly one of the variables is true (sum = 1). Create a range constraint over the maximum power usage for each partition, and multiply the bounds of that constraint with the associated binary variable. When a binary variable is set to zero, you have a trivial constraint.

It is indeed possible to represent boolean constraints as linear constraints over binary variables and develop a DSL to translate in this direction. I am wondering whether a system exists which allows easy expression of linear and boolean combined, and which provides tools for solving them efficiently.

Re:The Erlang Rationale (2008) [pdf] by lock-free on Friday December 25, 2020 @06:35PM (#25540010)
Is this equivalent to a vector backed list?
Re:The Erlang Rationale (2008) [pdf] by dnautics on Friday December 25, 2020 @05:13PM (#25539442)
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.

Re:The Erlang Rationale (2008) [pdf] by jpcooper on Saturday December 26, 2020 @03:16AM (#25542126)
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.

Re:The Erlang Rationale (2008) [pdf] by ProfHewitt on Sunday December 27, 2020 @12:23AM (#25549075)
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 :-(

Re:The Erlang Rationale (2008) [pdf] by sean_pedersen on Friday December 25, 2020 @04:23PM (#25539136)
I had the pleasure of using Erlang in Data Structures, Graph Theory and Distributed Systems classes in university, had been lucky with the professor.