Erlang Series

Introduction to Erlang : Shared Memory Example

This entry is part 16 of 16 in the series Introduction to Erlang

Shared Memory

This post will be about building step by step a shared memory abstraction in Erlang. As you should all know, variables in Erlang are immutable; once a variable is bound to a value, this value cannot change. Thus in order to implement a mutable variable/object we need to represent it with a recursive process responsible for keeping the current value and providing the interface for using the object (read and write operations for example).

So, in order to implement a memory abstraction we have to use the aforementioned approach. We can either create a single process to be responsible for keeping the whole address space as a simple list, or create one process for each allocation operation. We will follow the second approach because it is more interesting and protects the memory process from becoming the bottleneck.

Let’s start!

The Messaging Interface

The interface of the memory system is quite simple. We just need the following operations:

  • start : for starting the memory system
  • stop : for stopping the memory system
  • alloc : for allocating memory
  • free : for freeing memory
  • read : for reading the value of a memory address
  • write : for writing to a memory address

From the above, the four first operations will be handled by the memory system, while the two last by each memory address (process) that they refer to. We will create two modules:

  • mem : the memory system
  • memif : the memory interface

and one file called “common” with the parameters of the system.

-define(MEMREGNAME, mem).
-define(MAXSIZE, 100).

This file will be include in both other modules (-include("common") directive).
Read the rest of this entry »

Introduction to Erlang : Message Passing

This entry is part 15 of 16 in the series Introduction to Erlang

Message Passing

The communication model (among processes) in Erlang is message passing. No much need to be said about this. Erlang processes share no memory. The way that processes communicate is via (asynchronous) message passing. Every process (even the shell) holds a mailbox queue where incoming messages are placed until received by the process. Message passing is asynchronous because the sending process does not block on send. On the other hand, receiving a message in Erlang is a blocking operation.

Characteristics

In this subsection I will describe some of the characteristics of message passing in Erlang.

Asynchronous

As I already mentioned, message passing in Erlang is a non-blocking operation.

Data Copy

The message’s data are copied from the sending process to the receiver’s message queue, so the receiver gets a fresh copy of the data.

Ordering

Erlang runtime guarantees that if two messages are sent from node A to node B and both are delivered, then the ordering of these messages is kept (causal ordering).

Successful Send

The send operation always succeeds (even if the target is a non-existing process) and evaluates to the data sent. An exception is when trying to send data to a non-existing registered process.
Read the rest of this entry »

Introduction to Erlang : Concurrency (Processes)

This entry is part 14 of 16 in the series Introduction to Erlang

Concurrency

Concurrency is defined as “the temporal property of two things happening at the same time” (according to WordNet). In Computer Science, the definition is “concurrency is a property of systems in which several computations are executing simultaneously, and potentially interacting with each other. The computations may be executing on multiple cores in the same chip, preemptively time-shared threads on the same processor, or executed on physically separated processors.” (according to Wikipedia).

In practise, if two, or more, tasks are concurrent, then they can run in parallel. This implies that there are no data dependencies among them. For example, the following tasks

  • unlock the car (the car was locked)
  • start the engine of the car (the engine was off)
  • drive the car

are non-concurrent since they have dependencies. One cannot start the engine of the car without first entering the car and she cannot drive it without first starting the engine. These tasks have to be executed sequentially (with a predefined order) no matter if more than one person (processing unit) help. On the other hand

  • doing the laundry
  • washing the dishes
  • go for shopping

can be potentially run in parallel. For example, three different family members can handle one task each. Moreover, if only one person has to do all the tasks, she can decide to perform them in any order she decides since there are no dependencies among them.
Read the rest of this entry »

Introduction to Erlang : List Comprehension

This entry is part 13 of 16 in the series Introduction to Erlang

List Comprehension

Do you remember the lists:map/2 and lists:filter/2 functions from the previous post? If not, consult the Lists & lists Module post. lists:map(Function, List) returns a new list that results from List after applying the Function to each element. lists:filter(Predicate, List) returns a list that contains only the elements of List for which the call to Predicate returns true.

Both the aforementioned operations are commonly used, as well as their combination; map & filter (does it remind you map & reduce?). Erlang provides this combined functionality using the list comprehension construct.

Format

A list comprehension look like the following:

[Expression || Generators1, Guards1, Generators2, ...]
Generators

As their name suggests, generators create the data used in the filter-map operations. A generator has the Pattern < - Data format, where Data is a list or an expression that results to a list and Pattern is a pattern used to match with the elements of the list. This pattern can be used to disassembly elements. For example, two valid generators are I < - lists:seq(1, 10) and {X, Y} < - [{'A', 'Excellent'}, {'B', 'Good'}, {'C', 'Fair'}].

Expression

The expression specifies the elements of the result. For example, [I || I < - [1, 2, 3]] returns the input list element as is.

Guards

Guards are expressions that return either true or false, the same as the guards we have seen in the previous posts. They apply to the variables that are on the left of the guard and the ones that are accessible due to the scope where the comprehension runs. For example, I < - [1, 2, 3, 4], I rem 2 == 0 is a valid generator - guard combination (the result should be obvious; only the even numbers "pass" the guard's test).
Read the rest of this entry »

Introduction to Erlang : List & lists Module

This entry is part 12 of 16 in the series Introduction to Erlang

List

List is the the most important data type in Erlang, as in every (?) functional programming language. We have seen and used lists in almost every previous post. In this post, I will briefly present the “theory” of lists and then present the Erlang’s lists module and its most important functions.

Definition

A list can be recursively defined as the construct that

  • either is the empty list (denoted as [] in Erlang),
  • or is a cosntruct that its first element is a term (called head) and what remains if the head is removed is a list (called tail)

In Erlang a list of N elements has the [Element1, Element2, ..., ElementN] format (N is called the length of the list). So, [] is the empty list, [1], [{a}] are 1-element lists, [1, 2], [a, {b, c}] are 2-elements lists, etc. As we will see in a while, the format [Element1, Element2, ..., ElementN] is a shorthand for the [Element1 | [Element2 | ... | [ElementN | []] ... ] representation.
Read the rest of this entry »

Introduction to Erlang : BIFs & Predefined Modules

This entry is part 11 of 16 in the series Introduction to Erlang

Built-in Functions (BIFs)

Erlang’s Built-in Functions (shorthand BIFs) are commonly used functions that are intergrated into the Erlang’s VM for performance reasons. Most of them belong to the erlang module, but there are some in other modules, such as lists.

The BIFs can be separated to standard and non-standard. The standard ones are auto-imported; they can be called without the use of the module name prefix (remember the effect of the -import(...) directive). On the other hand, the non-standard ones have to be called following the normal module:function(...) convension. In the erlang module’s man pages (here) the distinction between standard and non-standard is visible by the lack or existence of the erlang (module’s name) prefix.

elrang

abs/1

Arithmetic absolut value of an integer or float.

erlang:append_element/2

Appends an element to a tuple.

apply/2|3

Calls the function passed as a parameter.

atom_to_list/1

Returns a string which corresponds to the text representation of Atom.
Read the rest of this entry »

Introduciton to Erlang : Recursion (2/2)

This entry is part 10 of 16 in the series Introduction to Erlang

Accumulators

In several cases, as with the mlists:length/1 example, the non-tail recursive function can be easily turned to a tail recursive one by using the notion of accumulator. An accumulator is an extra argument introduced to a function in order to aggregate the partial results of the function. It turns the “bottom-up” collection of the final result to “top-down”.

In order to add and initialize the accumulator argument one has to introduce an extra function definition.

tlr(...) ->
    tlr(..., Accumulator_initial_value).
 
% the clause that "breaks" the recursion and
% returns the result
tlr(..., Accumulator) -> 
    Accumulator;
tlr(..., Accumulator) ->
    ...,
    Accumulator_new_value = ...,
    ...,
    trl(..., Accumulator_new_value).

Notice that typically you would only export the tlr/1 function and the tlr/2 would remain for inner-module use and not visible to the module’s users.
Read the rest of this entry »

Introduction to Erlang : Recursion (1/2)

This entry is part 9 of 16 in the series Introduction to Erlang

Recursion

The definition of the word recursion is “(mathematics) an expression such that each term is generated by repeating a particular mathematical operation”, according to the WordNet. Recursion is one of the most powerful “tools” in a functional programming language and so it is for Erlang. Recursion can be used to apply divide and conquer techniques to problem solving, where a problem is broken to smaller subproblems, the subproblems are solved, and the results are “merged” to generate the final result.

Recursion happens when a function’s body definition includes a call to the function itself.

functionA(...) ->
    Body_before_recursion, % optional
    functionA(...),
    Body_after_recursion. % optional

Recursion is used instead of the conventional loop statements of other programming languages, such as while and for in C.
Read the rest of this entry »