{"id":551,"date":"2007-11-25T15:33:52","date_gmt":"2007-11-25T15:33:52","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2007\/11\/25\/erlang-a-language-for-functional-concurrency-updated\/"},"modified":"2007-11-25T15:33:52","modified_gmt":"2007-11-25T15:33:52","slug":"erlang-a-language-for-functional-concurrency-updated","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2007\/11\/25\/erlang-a-language-for-functional-concurrency-updated\/","title":{"rendered":"Erlang: a Language for Functional Concurrency (Updated!)"},"content":{"rendered":"

Several commenters pointed out that I made several mistakes in my description of Erlang. It turns out that the main reference source I used for this post, an excerpt from a textbook on Erlang available on the Erlang website, is quite out of date. I didn’t realize this; I assumed that if they pointed towards that as a tutorial, that it would represent the current state of the language. My bad. As a result, several things that I said about Erlang – including some negative comments, were inaccurate. I’ve updated the article, and the changes are marked with comments.<\/em><\/p>\n

As long-time readers will recall, one of my greatest interests in programming languages. A while back, I wrote a tutorial on Haskell<\/a>, which is one of the most influential languages currently in the programming language research community. Haskell is a pure, lazy, functional language which gained a lot of attention in recent times for being incredibly expressive, while maintaining a solid theoretical basis with well-defined semantics. What made Haskell unusual was that it’s a completely pure functional language – meaning no true state at all – not for I\/O, not for assignment, not for mutable data – but through the
\nuse of a clever construct called a monad<\/em>, you can create the effect of state without disturbing the functional semantics of the language. It’s quite a nice idea, although I must admit that I remain somewhat skeptical about how scaleable it might be.<\/p>\n

One of the competitors of Haskell for mindshare in the community of people who are interested in functional programming languages is a language called Erlang<\/a>. In many ways, Erlang is a polar opposite to Haskell. Erlang is, basically, a functional language, but it’s designers didn’t object to tossing in a bit of state when it made things easier. It’s dynamically typed,
\nand even for a dynamically typed language, it’s support for typing is weak. It’s gotten its attention for a couple of big reasons:<\/p>\n

    \n
  1. Erlang was designed by Ericsson for implementing the software in their switches and routers. It’s the first functional language designed by a company for building production applications for extremely complex performance-critical low-level applications like switching and routing.<\/li>\n
  2. Erlang is specifically designed for building distributed systems. As I’ve mentioned before, programming for distributed systems is incredibly difficult, and most programming languages are terrible at it.<\/li>\n<\/ol>\n

    Concurrency and distributed systems are a big deal. I’d argue that programming for concurrency and distribution are the<\/em> biggest problems facing software developers today. Pretty much every computer that you can buy has multiple processors, and to take full advantage of their power, code needs to use concurrency. And the network is an unavoidable part of our environment: many of the applications that we’re writing today need to be aware of the internet, and need to interact with other systems. These are just simple facts of the modern computing world – and software developers need tools to deal with them.<\/p>\n

    <\/p>\n

    You see, concurrent programs are hard<\/em> to write. Part of that is intrinsic complexity: there are simply more issues that you need to address to write a correct program with concurrency than there would be in a similar non-concurrent program. The other part of it involves tools and languages: the programming languages and related tools that we use are terrible<\/em> at concurrency.<\/p>\n

    Many Haskell proponents claim that because Haskell doesn’t specify the order in which things are done, and it makes the data dependency relations explicit, and that therefore, it’s more amenable to automatic parallelization. The problem with that claim is that it doesn’t work. Haskell systems don’t, in general, parallelize well. They’re particularly bad for the kind of very coarse thread-based concurrency that
    \nwe need to program for on multi-core computers, or distributed systems. Haskell usually ends up falling back to Monads: monads provide an explicit way of writing parallel code. But Monad’s aren’t a great answer. In Haskell, almost everything ends up falling back to Monads – I\/O, state, mutable structures, and so on. And monads are hard to combine! So you’re generally stuck with an extremely difficult problem of how to manage the non-concurrent monads that you need with the concurrency monad. The end result is as bad as any other of the god-awful train-wrecks that we use.<\/p>\n

    Erlang is different. Concurrency operations aren’t a second-class mess grafted onto an existing non-concurrent language. Concurrency is exactly what it was designed for, and at least for the Ericsson applications which it was designed for, it does a great job. (The Ericsson folks have published case study papers<\/a> demonstrating how well Erlang performed.) The big question to me is, how much of the performance of Erlang comes from the fact that the people who designed it are the leaders of the team who used it? How much of it comes from the fact that it was specifically designed for the applications that were implemented in it? And how much comes from the general qualities of the language for implementing arbitrary distributed systems? That’s what I really want to know. (Plus, Erlang also looks like a good language for implementing Pica<\/a>, so
    \nthis also gives me a good excuse for learning enough about it to see if it will really do the
    \njob.)<\/em><\/p>\n

    All of this is an extremely long-winded, almost Oracian way of saying that I’m going to start
    \nwriting a series of tutorial articles on Erlang. For today, I’m not going to go into depth on
    \nanything – I’m just going to show a couple of examples of what Erlang looks like. I’ll get into
    \ndepth in subsequent posts.<\/p>\n

    For starters, let’s look at the pure functional part of it. We’ll start off with that canonical example of all functional programs, the factorial function.<\/p>\n

    \n-module(tut).\n-export([factorial\/1]).\nfactorial(0) -> 1;\nfactorial(N) -> N * factorial(N-1)\n<\/pre>\n
     Right off, you should notice that there’s two sub-languages: a  module language (where you describe how things fit together), and an expression language (where you describe what things do). The module language statements always start with “-“. A source file is a module, and always starts off with a module declaration, declaring its name. The standard Erlang implementation expects a module to share a name with the source file that contains it. So the example above would need to be in a file named “tut.erl”.<\/p>\n
     The export statement tells the Erlang compiler what declarations in the module should be visible to code outside of the file. This is one of the places where a bit of ugliness from the original implementation creeps through: in the prolog style, the name of a function is given by both its name, and its number of parameters. So factorial<\/code> is factorial\/1<\/code> in module tut<\/code>.<\/p>\n
     With the housekeeping stuff out of the way, we can look at the meat of things. It’s a simple pattern-matching based declaration of factorial – virtually identical to what you would have written in Haskell or SML. The first case declares the result when the parameter is “0”; the second case for any other value. There are no type declarations: unlike Haskell, Erlang is not<\/em> strongly typed. (As people who know me might guess, this doesn’t thrill me; I’m a big fan of strong typing. But I’m willing to keep an open mind, and see how it works out.)<\/p>\n
     Erlang has a small set of built-in primitive types, including:<\/p>\n
      \n
    1.  Integers, written in the usual syntax.<\/li>\n
    2.  Floating point numbers, again written in the usual syntax.<\/li>\n
    3.  Atoms. Atoms combine both the idea of strings, and the lisp notion of symbols. If an atom
      \nstarts with a lower-case letter, and contains no punctuation or spaces, then it doesn’t need
      \nto be quoted. Otherwise, it’s enclosed in single quotes.<\/li>\n
    4.  Pids. Pids are process identifiers – references to other processes which can be used
      \nfor communication.<\/li>\n
    5.  Functions. First class function values.<\/li>\n<\/ol>\n
      (I originally said there were only four basic types. I was wrong – there are more. I’m not mentioning them all here, but these are the key ones for the discussion in this article.)<\/em><\/p>\n
       There are two main kinds of data structures in Erlang: lists (which are variable length), and tuples (fixed length). Lists are written with square brackets like [1, 2, 3]<\/code>; tuples are written with curly braces like {1, 2, 3}. And like Haskell, everything <\/code>. As I said above, there’s really no type system here, so you build data types informally, using lists and tuples, rather than
      \ndeclaring strict types. There’s no enforced mechanism, but a common style is to use tuples where the first element is an atom, which is used the way that a type constructor name is used in Haskell. So, for example, we might declare a tree in Haskell as follows:<\/p>\n
      \ndata Tree a = Node (Tree a) (Tree a) | Leaf a\n<\/pre>\n
       And then we could define a tree value as:<\/p>\n
      \ntree = (Node (Node (Leaf 3) (Leaf 4)) (Leaf 1))\n<\/pre>\n
       In Erlang, we can dispense with the declaration, and just write it out:<\/p>\n
      \nTree = {node, {node, {leaf, 3}, {leaf, 4}}, {leaf, 1}}.\n<\/pre>\n
      (In addition, Erlang includes a preprocessing phase which helps reduce the amount of work involved in creating user defined record types. I’ll talk about this in a later post.)<\/em><\/p>\n
       Basic data structure manipulating programs are written in a style very similar to
      \nthe way you’d write them in Haskell or ML – basic pattern-matching style functional programming. But Erlang functions are eager – they evaluate their parameters before the function is executed. That means that a lot of Haskell-ish idioms won’t work, but it also means that the way things work is a lot more obvious: lazy evaluation is frequently confusing. To give an example of a list-based function in
      \nErlang, here’s an implementation of the basic “map” operator, which takes a function and a list, and returns a new list containing the result of applying the function to each element of the original list.<\/p>\n
      \n-module(map).\n-export(map\/2, two\/1).\nmap(F, []) -> [];\nmap(F,[Car|Cdr]) ->\nNewCar = F(Car),\nNewCdr = map(F,Cdr),\n[NewCar|NewCdr].\ntwo(X) -> 2*X.\n<\/pre>\n
       This takes function parameter, “F”, and applies it to each value in sequence.  This can be called as follows:<\/p>\n
      \nexample = map:map(fun map:twice\/1, [1, 2, 3]).\n> [2, 4, 6]\n<\/pre>\n
       To get the value of a non-anonymous function, you use its full name, qualified with the arity, and preface it with the word “fun”.  So “fun map:twice\/1” is the function “twice” from the module “map” which takes one parameter. (I originally  had a discussion here of how Erlang’s function parameters were dreadfully awkward. Turns out that that’s an anachronism: it was true in old versions of the language, but hasn’t been true for years.)<\/em><\/p>\n
       I’m just going to show you one more quick example today, which gives you a little taste of what
      \nconcurrency looks like in Erlang. This example I’ve copied verbatim from the Erlang manual.<\/p>\n
      \n-module(echo).\n-export([start\/0, loop\/0]).\nstart() ->\nspawn(echo, loop, []).\nloop() ->\nreceive\n{From, Message} ->\nFrom ! Message,\nloop()\nend.\n<\/pre>\n
       The “start” function creates a new process, using the “spawn” operator. Spawn takes three parameters: the module of the function to run in the new process; the name of the function to run in the new process; and a list of parameters to pass to the function when it’s invoked. So “start” spawns a new process running the “loop” function, returns the process identifier of that new process.<\/p>\n
       The “loop” function is a tail-recursive loop, which recieves a message from another process containing a tuple; the first element of the tuple is expected to be the process-ID of the sender, and the second is an arbitrary value. “loop” just echoes the value part of the message back to its sender; “!” is the mesage send operator, which sends its right parameter as  message to the process identified by its left parameter.<\/p>\n
       To use this, we’d first invoke “start” to create a process:<\/p>\n
      \nId = echo:start().\n<\/pre>\n
       That starts the new process, and stores its pid in “Id”. Using the process identifier of the newly
      \nspawned process, we can send it a message:<\/p>\n
      \nId ! {self(), hello}.\n> {,hello}\n<\/pre>\n
       This sends a message to the process in ID, containing the Pid of the sender (computed by invoking “self()”), and the value “hello”. The spawned process receives the message, and echoes it back to the sender. When the top-level process receives a message, it outputs a tuple containing the pid of the sender, and the contents of the message – so it printed “{,hello}”, because “” is the pid of the sender (the spawned loop), and “hello” was the contents of the message.<\/p>\n","protected":false},"excerpt":{"rendered":"
      Several commenters pointed out that I made several mistakes in my description of Erlang. It turns out that the main reference source I used for this post, an excerpt from a textbook on Erlang available on the Erlang website, is quite out of date. I didn’t realize this; I assumed that if they pointed towards […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[85],"tags":[],"class_list":["post-551","post","type-post","status-publish","format-standard","hentry","category-erlang"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-8T","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/551","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=551"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/551\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=551"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=551"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=551"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}